46 static void perfdata_init();
47 static void incperfcount(
int countnum);
48 static void bumpperfcount(
int countnum,
int amt);
49 static void doperfmax(
int maxnum,
int val);
50 static void dump_perfdata();
54 static constexpr
bool intersect_use_threading =
true;
57 : co_exact(mco), co(dco),
id(
id), orig(orig)
63 return this->co_exact == other.co_exact;
71 x = (
x >> 56) ^ (
x >> 46) ^
x;
72 y = (
y >> 55) ^ (
y >> 45) ^
y;
73 z = (
z >> 54) ^ (
z >> 44) ^
z;
79 constexpr
int dbg_level = 0;
81 if (
v->orig != NO_INDEX) {
86 os <<
"=" <<
v->co_exact;
93 return norm_exact == other.norm_exact && d_exact == other.d_exact;
96 void Plane::make_canonical()
98 if (norm_exact[0] != 0) {
99 mpq_class den = norm_exact[0];
100 norm_exact = mpq3(1, norm_exact[1] / den, norm_exact[2] / den);
101 d_exact = d_exact / den;
103 else if (norm_exact[1] != 0) {
104 mpq_class den = norm_exact[1];
105 norm_exact = mpq3(0, 1, norm_exact[2] / den);
106 d_exact = d_exact / den;
109 if (norm_exact[2] != 0) {
110 mpq_class den = norm_exact[2];
111 norm_exact = mpq3(0, 0, 1);
112 d_exact = d_exact / den;
119 norm =
double3(norm_exact[0].get_d(), norm_exact[1].get_d(), norm_exact[2].get_d());
123 Plane::Plane(
const mpq3 &norm_exact,
const mpq_class &d_exact)
124 : norm_exact(norm_exact), d_exact(d_exact)
126 norm =
double3(norm_exact[0].get_d(), norm_exact[1].get_d(), norm_exact[2].get_d());
132 norm_exact = mpq3(0, 0, 0);
135 bool Plane::exact_populated()
const
137 return norm_exact[0] != 0 || norm_exact[1] != 0 || norm_exact[2] != 0;
146 x = (
x >> 56) ^ (
x >> 46) ^
x;
147 y = (
y >> 55) ^ (
y >> 45) ^
y;
148 z = (
z >> 54) ^ (
z >> 44) ^
z;
149 d = (
d >> 53) ^ (d >> 43) ^
d;
150 return x ^
y ^
z ^
d;
153 std::ostream &
operator<<(std::ostream &os,
const Plane *plane)
155 os <<
"[" << plane->norm <<
";" << plane->d <<
"]";
160 Span<const Vert *>
verts,
int id,
int orig, Span<int> edge_origs, Span<bool> is_intersect)
161 : vert(
verts), edge_orig(edge_origs), is_intersect(is_intersect),
id(
id), orig(orig)
169 void Face::populate_plane(
bool need_exact)
171 if (plane !=
nullptr) {
172 if (!need_exact || plane->exact_populated()) {
178 if (vert.size() > 3) {
179 Array<mpq3> co(vert.size());
180 for (
int i : index_range()) {
181 co[i] = vert[i]->co_exact;
186 mpq3 tr02 = vert[0]->co_exact - vert[2]->co_exact;
187 mpq3 tr12 = vert[1]->co_exact - vert[2]->co_exact;
190 mpq_class d_exact = -
math::dot(normal_exact, vert[0]->co_exact);
191 plane =
new Plane(normal_exact, d_exact);
195 if (vert.size() > 3) {
196 Array<double3> co(vert.size());
197 for (
int i : index_range()) {
203 double3 tr02 = vert[0]->co - vert[2]->co;
204 double3 tr12 = vert[1]->co - vert[2]->co;
208 plane =
new Plane(
normal, d);
219 if (this->
size() != other.size()) {
222 for (FacePos i : index_range()) {
225 if (this->vert[i] != other.vert[i]) {
232 bool Face::cyclic_equal(
const Face &other)
const
234 if (this->
size() != other.size()) {
237 int flen = this->
size();
238 for (FacePos start : index_range()) {
239 for (FacePos start_other : index_range()) {
241 for (
int i = 0; ok && i < flen; ++i) {
242 FacePos p = (start + i) % flen;
243 FacePos p_other = (start_other + i) % flen;
244 if (this->vert[p] != other.vert[p_other]) {
258 os <<
"f" << f->id <<
"o" << f->orig <<
"[";
259 for (
const Vert *
v : *f) {
261 if (
v != f->vert[f->size() - 1]) {
266 if (f->orig != NO_INDEX) {
267 os <<
"o" << f->orig;
270 for (
int i : f->index_range()) {
271 os << f->edge_orig[i];
272 if (f->is_intersect[i]) {
275 if (i != f->size() - 1) {
298 class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
308 VSetKey(
Vert *p) : vert(p)
319 return *this->vert == *other.vert;
330 Vector<std::unique_ptr<Vert>> allocated_verts_;
331 Vector<std::unique_ptr<Face>> allocated_faces_;
334 int next_vert_id_ = 0;
335 int next_face_id_ = 0;
347 if (intersect_use_threading) {
357 if (intersect_use_threading) {
366 void reserve(
int vert_num_hint,
int face_num_hint)
368 vset_.reserve(vert_num_hint);
369 allocated_verts_.reserve(vert_num_hint);
370 allocated_faces_.reserve(face_num_hint);
373 int tot_allocated_verts()
const
375 return allocated_verts_.size();
378 int tot_allocated_faces()
const
380 return allocated_faces_.size();
383 const Vert *add_or_find_vert(
const mpq3 &co,
int orig)
385 double3 dco(co[0].get_d(), co[1].get_d(), co[2].get_d());
386 return add_or_find_vert(co, dco, orig);
389 const Vert *add_or_find_vert(
const double3 &co,
int orig)
391 mpq3 mco(co[0], co[1], co[2]);
392 return add_or_find_vert(mco, co, orig);
395 const Vert *add_or_find_vert(
Vert *vert)
397 return add_or_find_vert_(vert);
400 Face *add_face(Span<const Vert *>
verts,
int orig, Span<int> edge_origs, Span<bool> is_intersect)
402 Face *f =
new Face(
verts, next_face_id_++, orig, edge_origs, is_intersect);
403 if (intersect_use_threading) {
410 allocated_faces_.append(std::unique_ptr<Face>(f));
411 if (intersect_use_threading) {
421 Face *add_face(Span<const Vert *>
verts,
int orig, Span<int> edge_origs)
423 Array<bool> is_intersect(
verts.size(),
false);
424 return add_face(
verts, orig, edge_origs, is_intersect);
427 Face *add_face(Span<const Vert *>
verts,
int orig)
429 Array<int> edge_origs(
verts.size(), NO_INDEX);
430 Array<bool> is_intersect(
verts.size(),
false);
431 return add_face(
verts, orig, edge_origs, is_intersect);
434 const Vert *find_vert(
const mpq3 &co)
436 Vert vtry(co,
double3(co[0].get_d(), co[1].get_d(), co[2].get_d()), NO_INDEX, NO_INDEX);
437 VSetKey vskey(&vtry);
438 if (intersect_use_threading) {
445 const VSetKey *
lookup = vset_.lookup_key_ptr(vskey);
446 if (intersect_use_threading) {
464 const Face *find_face(Span<const Vert *> vs)
466 Array<int> eorig(vs.size(), NO_INDEX);
467 Array<bool> is_intersect(vs.size(),
false);
468 Face ftry(vs, NO_INDEX, NO_INDEX, eorig, is_intersect);
469 for (
const int i : allocated_faces_.index_range()) {
470 if (ftry.cyclic_equal(*allocated_faces_[i])) {
471 return allocated_faces_[i].get();
478 const Vert *add_or_find_vert(
const mpq3 &mco,
const double3 &dco,
int orig)
480 Vert *vtry =
new Vert(mco, dco, NO_INDEX, NO_INDEX);
483 if (intersect_use_threading) {
490 const VSetKey *
lookup = vset_.lookup_key_ptr(vskey);
492 vtry->id = next_vert_id_++;
495 vset_.add_new(vskey);
496 allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
508 if (intersect_use_threading) {
518 const Vert *add_or_find_vert_(
Vert *vtry)
522 if (intersect_use_threading) {
529 const VSetKey *
lookup = vset_.lookup_key_ptr(vskey);
531 vtry->id = next_vert_id_++;
533 vset_.add_new(vskey);
534 allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
546 if (intersect_use_threading) {
557 IMeshArena::IMeshArena()
559 pimpl_ = std::make_unique<IMeshArenaImpl>();
562 IMeshArena::~IMeshArena() =
default;
564 void IMeshArena::reserve(
int vert_num_hint,
int face_num_hint)
566 pimpl_->reserve(vert_num_hint, face_num_hint);
569 int IMeshArena::tot_allocated_verts()
const
571 return pimpl_->tot_allocated_verts();
574 int IMeshArena::tot_allocated_faces()
const
576 return pimpl_->tot_allocated_faces();
579 const Vert *IMeshArena::add_or_find_vert(
const mpq3 &co,
int orig)
581 return pimpl_->add_or_find_vert(co, orig);
584 const Vert *IMeshArena::add_or_find_vert(
Vert *vert)
586 return pimpl_->add_or_find_vert(vert);
589 Face *IMeshArena::add_face(Span<const Vert *>
verts,
591 Span<int> edge_origs,
592 Span<bool> is_intersect)
594 return pimpl_->add_face(
verts, orig, edge_origs, is_intersect);
597 Face *IMeshArena::add_face(Span<const Vert *>
verts,
int orig, Span<int> edge_origs)
599 return pimpl_->add_face(
verts, orig, edge_origs);
602 Face *IMeshArena::add_face(Span<const Vert *>
verts,
int orig)
604 return pimpl_->add_face(
verts, orig);
607 const Vert *IMeshArena::add_or_find_vert(
const double3 &co,
int orig)
609 return pimpl_->add_or_find_vert(co, orig);
612 const Vert *IMeshArena::find_vert(
const mpq3 &co)
const
614 return pimpl_->find_vert(co);
617 const Face *IMeshArena::find_face(Span<const Vert *>
verts)
const
619 return pimpl_->find_face(
verts);
622 void IMesh::set_faces(Span<Face *>
faces)
627 int IMesh::lookup_vert(
const Vert *
v)
const
630 return vert_to_index_.lookup_default(
v, NO_INDEX);
633 void IMesh::populate_vert()
637 constexpr
int ESTIMATE_VERTS_PER_FACE = 4;
638 int estimate_verts_num = ESTIMATE_VERTS_PER_FACE * face_.size();
639 populate_vert(estimate_verts_num);
642 void IMesh::populate_vert(
int max_verts)
644 if (vert_populated_) {
647 vert_to_index_.reserve(max_verts);
648 int next_allocate_index = 0;
649 for (
const Face *f : face_) {
650 for (
const Vert *
v : *f) {
653 int index = vert_to_index_.lookup_default(
v, NO_INDEX);
654 if (index == NO_INDEX) {
656 vert_to_index_.add(
v, next_allocate_index++);
660 int tot_v = next_allocate_index;
661 vert_ = Array<const Vert *>(tot_v);
662 for (
auto item : vert_to_index_.items()) {
663 int index = item.value;
665 vert_[index] = item.key;
670 const bool fix_order =
true;
673 if (a->orig != NO_INDEX && b->orig != NO_INDEX) {
674 return a->orig < b->orig;
676 if (
a->orig != NO_INDEX) {
679 if (
b->orig != NO_INDEX) {
682 return a->id <
b->id;
684 for (
int i : vert_.index_range()) {
685 const Vert *
v = vert_[i];
686 vert_to_index_.add_overwrite(
v, i);
689 vert_populated_ =
true;
692 bool IMesh::erase_face_positions(
int f_index, Span<bool> face_pos_erase, IMeshArena *arena)
694 const Face *cur_f = this->face(f_index);
695 int cur_len = cur_f->size();
696 int to_erase_num = 0;
697 for (
int i : cur_f->index_range()) {
698 if (face_pos_erase[i]) {
702 if (to_erase_num == 0) {
705 int new_len = cur_len - to_erase_num;
713 this->face_[f_index] =
NULL;
716 Array<const Vert *> new_vert(new_len);
717 Array<int> new_edge_orig(new_len);
718 Array<bool> new_is_intersect(new_len);
720 for (
int i : cur_f->index_range()) {
721 if (!face_pos_erase[i]) {
722 new_vert[new_index] = (*cur_f)[i];
723 new_edge_orig[new_index] = cur_f->edge_orig[i];
724 new_is_intersect[new_index] = cur_f->is_intersect[i];
729 this->face_[f_index] = arena->add_face(new_vert, cur_f->orig, new_edge_orig, new_is_intersect);
733 void IMesh::remove_null_faces()
736 for (
Face *f : this->face_) {
741 if (nullcount == 0) {
744 int64_t new_size = this->face_.size() - nullcount;
747 Array<Face *> new_face(new_size);
748 while (copy_from_index < face_.size()) {
749 Face *f_from = face_[copy_from_index++];
751 new_face[copy_to_index++] = f_from;
754 this->face_ = new_face;
759 if (
mesh.has_verts()) {
763 os << i <<
": " <<
v <<
"\n";
769 for (
const Face *f :
mesh.faces()) {
770 os << i <<
": " << f <<
"\n";
771 if (f->plane !=
nullptr) {
772 os <<
" plane=" << f->plane <<
" eorig=[";
773 for (Face::FacePos p = 0; p < f->size(); ++p) {
774 os << f->edge_orig[p] <<
" ";
795 double max_abs_val = 0.0;
800 Array<BoundingBox> *face_bounding_box;
802 BBCalcData(
const IMesh &im, Array<BoundingBox> *fbb) : im(im), face_bounding_box(fbb){};
805 static void calc_face_bb_range_func(
void *__restrict userdata,
809 BBCalcData *bbdata =
static_cast<BBCalcData *
>(userdata);
810 double max_abs = 0.0;
811 const Face &face = *bbdata->im.face(iter);
812 BoundingBox &bb = (*bbdata->face_bounding_box)[iter];
813 for (
const Vert *
v : face) {
815 for (
int i = 0; i < 3; ++i) {
819 BBChunkData *chunk =
static_cast<BBChunkData *
>(tls->userdata_chunk);
820 chunk->max_abs_val =
max_dd(max_abs, chunk->max_abs_val);
824 Array<BoundingBox> *face_bounding_box;
827 BBPadData(Array<BoundingBox> *fbb,
double pad) : face_bounding_box(fbb),
pad(
pad){};
830 static void pad_face_bb_range_func(
void *__restrict userdata,
834 BBPadData *pad_data =
static_cast<BBPadData *
>(userdata);
835 (*pad_data->face_bounding_box)[iter].expand(pad_data->pad);
838 static void calc_face_bb_reduce(
const void *__restrict
UNUSED(userdata),
839 void *__restrict chunk_join,
840 void *__restrict chunk)
842 BBChunkData *bbchunk_join =
static_cast<BBChunkData *
>(chunk_join);
843 BBChunkData *bbchunk =
static_cast<BBChunkData *
>(chunk);
844 bbchunk_join->max_abs_val =
max_dd(bbchunk_join->max_abs_val, bbchunk->max_abs_val);
852 static Array<BoundingBox> calc_face_bounding_boxes(
const IMesh &m)
854 int n = m.face_size();
855 Array<BoundingBox> ans(n);
857 BBCalcData
data(m, &ans);
858 BBChunkData chunk_data;
866 double max_abs_val = chunk_data.max_abs_val;
867 constexpr
float pad_factor = 10.0f;
868 float pad = max_abs_val == 0.0f ? FLT_EPSILON : 2 * FLT_EPSILON * max_abs_val;
874 BBPadData pad_data(&ans,
pad);
888 class CoplanarCluster {
893 CoplanarCluster() =
default;
896 this->add_tri(
t, bb);
909 int tri(
int index)
const
913 const int *begin()
const
915 return tris_.
begin();
917 const int *end()
const
934 class CoplanarClusterInfo {
935 Vector<CoplanarCluster> clusters_;
936 Array<int> tri_cluster_;
939 CoplanarClusterInfo() =
default;
940 explicit CoplanarClusterInfo(
int numtri) : tri_cluster_(
Array<int>(numtri))
942 tri_cluster_.fill(-1);
945 int tri_cluster(
int t)
const
948 return tri_cluster_[
t];
951 int add_cluster(CoplanarCluster cl)
953 int c_index = clusters_.append_and_get_index(cl);
956 tri_cluster_[
t] = c_index;
961 int tot_cluster()
const
963 return clusters_.size();
966 const CoplanarCluster *begin()
968 return clusters_.begin();
971 const CoplanarCluster *end()
973 return clusters_.end();
976 IndexRange index_range()
const
978 return clusters_.index_range();
981 const CoplanarCluster &cluster(
int index)
const
984 return clusters_[index];
988 static std::ostream &
operator<<(std::ostream &os,
const CoplanarCluster &cl);
990 static std::ostream &
operator<<(std::ostream &os,
const CoplanarClusterInfo &clinfo);
992 enum ITT_value_kind { INONE, IPOINT, ISEGMENT, ICOPLANAR };
998 enum ITT_value_kind kind = INONE;
1000 ITT_value() =
default;
1001 explicit ITT_value(ITT_value_kind k) : kind(k)
1004 ITT_value(ITT_value_kind k,
int tsrc) : t_source(tsrc), kind(k)
1007 ITT_value(ITT_value_kind k,
const mpq3 &p1) : p1(p1), kind(k)
1010 ITT_value(ITT_value_kind k,
const mpq3 &p1,
const mpq3 &p2) : p1(p1), p2(p2), kind(k)
1015 static std::ostream &
operator<<(std::ostream &os,
const ITT_value &itt);
1022 static mpq2 project_3d_to_2d(
const mpq3 &p3d,
int proj_axis)
1025 switch (proj_axis) {
1084 c[0] = abs_a[1] * abs_b[2] + abs_a[2] * abs_b[1];
1085 c[1] = abs_a[2] * abs_b[0] + abs_a[0] * abs_b[2];
1086 c[2] = abs_a[0] * abs_b[1] + abs_a[1] * abs_b[0];
1093 constexpr
int index_dot_plane_coords = 15;
1105 constexpr
int index_dot_cross = 11;
1115 constexpr
int index_plane_side = 3 + 2 * index_dot_plane_coords;
1117 static int filter_plane_side(
const double3 &p,
1128 double supremum =
math::dot(abs_p + abs_plane_p, abs_plane_no);
1129 double err_bound = supremum * index_plane_side * DBL_EPSILON;
1130 if (
fabs(d) > err_bound) {
1131 return d > 0 ? 1 : -1;
1152 static inline mpq3 tti_interp(
1153 const mpq3 &
a,
const mpq3 &
b,
const mpq3 &
c,
const mpq3 &n, mpq3 &ab, mpq3 &ac, mpq3 &dotbuf)
1159 mpq_class den = math::dot_with_buffer(ab, n, dotbuf);
1161 mpq_class alpha = math::dot_with_buffer(ac, n, dotbuf) / den;
1162 return a - alpha * ab;
1172 static inline int tti_above(
const mpq3 &
a,
1186 n.x = ba.y * ca.z - ba.z * ca.y;
1187 n.y = ba.z * ca.x - ba.x * ca.z;
1188 n.z = ba.x * ca.y - ba.y * ca.x;
1190 return sgn(math::dot_with_buffer(ad, n, dotbuf));
1206 static ITT_value itt_canon2(
const mpq3 &p1,
1215 constexpr
int dbg_level = 0;
1216 if (dbg_level > 0) {
1217 std::cout <<
"\ntri_tri_intersect_canon:\n";
1218 std::cout <<
"p1=" << p1 <<
" q1=" <<
q1 <<
" r1=" << r1 <<
"\n";
1219 std::cout <<
"p2=" << p2 <<
" q2=" << q2 <<
" r2=" << r2 <<
"\n";
1220 std::cout <<
"n1=" << n1 <<
" n2=" << n2 <<
"\n";
1221 std::cout <<
"approximate values:\n";
1222 std::cout <<
"p1=(" << p1[0].get_d() <<
"," << p1[1].get_d() <<
"," << p1[2].get_d() <<
")\n";
1223 std::cout <<
"q1=(" <<
q1[0].get_d() <<
"," <<
q1[1].get_d() <<
"," <<
q1[2].get_d() <<
")\n";
1224 std::cout <<
"r1=(" << r1[0].get_d() <<
"," << r1[1].get_d() <<
"," << r1[2].get_d() <<
")\n";
1225 std::cout <<
"p2=(" << p2[0].get_d() <<
"," << p2[1].get_d() <<
"," << p2[2].get_d() <<
")\n";
1226 std::cout <<
"q2=(" << q2[0].get_d() <<
"," << q2[1].get_d() <<
"," << q2[2].get_d() <<
")\n";
1227 std::cout <<
"r2=(" << r2[0].get_d() <<
"," << r2[1].get_d() <<
"," << r2[2].get_d() <<
")\n";
1228 std::cout <<
"n1=(" << n1[0].get_d() <<
"," << n1[1].get_d() <<
"," << n1[2].get_d() <<
")\n";
1229 std::cout <<
"n2=(" << n2[0].get_d() <<
"," << n2[1].get_d() <<
"," << n2[2].get_d() <<
")\n";
1231 mpq3 p1p2 = p2 - p1;
1235 bool no_overlap =
false;
1237 if (tti_above(p1,
q1, r2, p1p2, buf[0], buf[1], buf[2], buf[3]) > 0) {
1239 if (tti_above(p1, r1, r2, p1p2, buf[0], buf[1], buf[2], buf[3]) <= 0) {
1241 if (tti_above(p1, r1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) > 0) {
1243 if (dbg_level > 0) {
1244 std::cout <<
"overlap [k [i l] j]\n";
1247 intersect_1 = tti_interp(p1, r1, p2, n2, buf[0], buf[1], buf[2]);
1248 intersect_2 = tti_interp(p2, r2, p1, n1, buf[0], buf[1], buf[2]);
1252 if (dbg_level > 0) {
1253 std::cout <<
"overlap [i [k l] j]\n";
1256 intersect_1 = tti_interp(p2, q2, p1, n1, buf[0], buf[1], buf[2]);
1257 intersect_2 = tti_interp(p2, r2, p1, n1, buf[0], buf[1], buf[2]);
1262 if (dbg_level > 0) {
1263 std::cout <<
"no overlap: [k l] [i j]\n";
1270 if (tti_above(p1,
q1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) < 0) {
1272 if (dbg_level > 0) {
1273 std::cout <<
"no overlap: [i j] [k l]\n";
1279 if (tti_above(p1, r1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) >= 0) {
1281 if (dbg_level > 0) {
1282 std::cout <<
"overlap [k [i j] l]\n";
1285 intersect_1 = tti_interp(p1, r1, p2, n2, buf[0], buf[1], buf[2]);
1286 intersect_2 = tti_interp(p1,
q1, p2, n2, buf[0], buf[1], buf[2]);
1290 if (dbg_level > 0) {
1291 std::cout <<
"overlap [i [k j] l]\n";
1294 intersect_1 = tti_interp(p2, q2, p1, n1, buf[0], buf[1], buf[2]);
1295 intersect_2 = tti_interp(p1,
q1, p2, n2, buf[0], buf[1], buf[2]);
1300 return ITT_value(INONE);
1302 if (intersect_1 == intersect_2) {
1303 if (dbg_level > 0) {
1304 std::cout <<
"single intersect: " << intersect_1 <<
"\n";
1306 return ITT_value(IPOINT, intersect_1);
1308 if (dbg_level > 0) {
1309 std::cout <<
"intersect segment: " << intersect_1 <<
", " << intersect_2 <<
"\n";
1311 return ITT_value(ISEGMENT, intersect_1, intersect_2);
1316 static ITT_value itt_canon1(
const mpq3 &p1,
1328 constexpr
int dbg_level = 0;
1331 return itt_canon2(p1, r1,
q1, r2, p2, q2, n1, n2);
1334 return itt_canon2(p1, r1,
q1, q2, r2, p2, n1, n2);
1336 return itt_canon2(p1,
q1, r1, p2, q2, r2, n1, n2);
1340 return itt_canon2(p1,
q1, r1, r2, p2, q2, n1, n2);
1343 return itt_canon2(p1,
q1, r1, q2, r2, p2, n1, n2);
1345 return itt_canon2(p1, r1,
q1, p2, q2, r2, n1, n2);
1349 return itt_canon2(p1, r1,
q1, q2, r2, p2, n1, n2);
1351 return itt_canon2(p1,
q1, r1, p2, q2, r2, n1, n2);
1355 return itt_canon2(p1, r1,
q1, p2, q2, r2, n1, n2);
1357 return itt_canon2(p1,
q1, r1, q2, r2, p2, n1, n2);
1360 return itt_canon2(p1,
q1, r1, r2, p2, q2, n1, n2);
1363 return itt_canon2(p1, r1,
q1, r2, p2, q2, n1, n2);
1365 if (dbg_level > 0) {
1366 std::cout <<
"triangles are co-planar\n";
1368 return ITT_value(ICOPLANAR);
1371 static ITT_value intersect_tri_tri(
const IMesh &tm,
int t1,
int t2)
1373 constexpr
int dbg_level = 0;
1377 const Face &tri1 = *tm.face(t1);
1378 const Face &tri2 = *tm.face(t2);
1379 BLI_assert(tri1.plane_populated() && tri2.plane_populated());
1380 const Vert *vp1 = tri1[0];
1381 const Vert *vq1 = tri1[1];
1382 const Vert *vr1 = tri1[2];
1383 const Vert *vp2 = tri2[0];
1384 const Vert *vq2 = tri2[1];
1385 const Vert *vr2 = tri2[2];
1386 if (dbg_level > 0) {
1387 std::cout <<
"\nINTERSECT_TRI_TRI t1=" << t1 <<
", t2=" << t2 <<
"\n";
1388 std::cout <<
" p1 = " << vp1 <<
"\n";
1389 std::cout <<
" q1 = " << vq1 <<
"\n";
1390 std::cout <<
" r1 = " << vr1 <<
"\n";
1391 std::cout <<
" p2 = " << vp2 <<
"\n";
1392 std::cout <<
" q2 = " << vq2 <<
"\n";
1393 std::cout <<
" r2 = " << vr2 <<
"\n";
1401 const double3 &d_p1 = vp1->co;
1402 const double3 &d_q1 = vq1->co;
1403 const double3 &d_r1 = vr1->co;
1404 const double3 &d_p2 = vp2->co;
1405 const double3 &d_q2 = vq2->co;
1406 const double3 &d_r2 = vr2->co;
1407 const double3 &d_n2 = tri2.plane->norm;
1415 int sp1 = filter_plane_side(d_p1, d_r2, d_n2, abs_d_p1, abs_d_r2, abs_d_n2);
1416 int sq1 = filter_plane_side(d_q1, d_r2, d_n2, abs_d_q1, abs_d_r2, abs_d_n2);
1417 int sr1 = filter_plane_side(d_r1, d_r2, d_n2, abs_d_r1, abs_d_r2, abs_d_n2);
1418 if ((sp1 > 0 && sq1 > 0 && sr1 > 0) || (sp1 < 0 && sq1 < 0 && sr1 < 0)) {
1422 if (dbg_level > 0) {
1423 std::cout <<
"no intersection, all t1's verts above or below t2\n";
1425 return ITT_value(INONE);
1428 const double3 &d_n1 = tri1.plane->norm;
1433 int sp2 = filter_plane_side(d_p2, d_r1, d_n1, abs_d_p2, abs_d_r1, abs_d_n1);
1434 int sq2 = filter_plane_side(d_q2, d_r1, d_n1, abs_d_q2, abs_d_r1, abs_d_n1);
1435 int sr2 = filter_plane_side(d_r2, d_r1, d_n1, abs_d_r2, abs_d_r1, abs_d_n1);
1436 if ((sp2 > 0 && sq2 > 0 && sr2 > 0) || (sp2 < 0 && sq2 < 0 && sr2 < 0)) {
1440 if (dbg_level > 0) {
1441 std::cout <<
"no intersection, all t2's verts above or below t1\n";
1443 return ITT_value(INONE);
1447 const mpq3 &p1 = vp1->co_exact;
1448 const mpq3 &
q1 = vq1->co_exact;
1449 const mpq3 &r1 = vr1->co_exact;
1450 const mpq3 &p2 = vp2->co_exact;
1451 const mpq3 &q2 = vq2->co_exact;
1452 const mpq3 &r2 = vr2->co_exact;
1454 const mpq3 &n2 = tri2.plane->norm_exact;
1458 sp1 =
sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1463 sq1 =
sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1468 sr1 =
sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1471 if (dbg_level > 1) {
1472 std::cout <<
" sp1=" << sp1 <<
" sq1=" << sq1 <<
" sr1=" << sr1 <<
"\n";
1475 if ((sp1 * sq1 > 0) && (sp1 * sr1 > 0)) {
1476 if (dbg_level > 0) {
1477 std::cout <<
"no intersection, all t1's verts above or below t2 (exact)\n";
1482 return ITT_value(INONE);
1486 const mpq3 &n1 = tri1.plane->norm_exact;
1490 sp2 =
sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1495 sq2 =
sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1500 sr2 =
sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1503 if (dbg_level > 1) {
1504 std::cout <<
" sp2=" << sp2 <<
" sq2=" << sq2 <<
" sr2=" << sr2 <<
"\n";
1507 if ((sp2 * sq2 > 0) && (sp2 * sr2 > 0)) {
1508 if (dbg_level > 0) {
1509 std::cout <<
"no intersection, all t2's verts above or below t1 (exact)\n";
1514 return ITT_value(INONE);
1523 ans = itt_canon1(r1, p1,
q1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1526 ans = itt_canon1(
q1, r1, p1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1529 ans = itt_canon1(p1,
q1, r1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1534 ans = itt_canon1(r1, p1,
q1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1537 ans = itt_canon1(
q1, r1, p1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1540 ans = itt_canon1(p1,
q1, r1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1546 ans = itt_canon1(
q1, r1, p1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1549 ans = itt_canon1(p1,
q1, r1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1554 ans = itt_canon1(p1,
q1, r1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1557 ans = itt_canon1(
q1, r1, p1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1562 ans = itt_canon1(r1, p1,
q1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1565 ans = itt_canon1(r1, p1,
q1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1568 if (dbg_level > 0) {
1569 std::cout <<
"triangles are co-planar\n";
1571 ans = ITT_value(ICOPLANAR);
1575 if (ans.kind == ICOPLANAR) {
1580 if (ans.kind != INONE) {
1588 const Plane *t_plane;
1590 Vector<std::pair<int, int>>
edge;
1591 Vector<Vector<int>> face;
1593 Vector<int> input_face;
1595 Vector<bool> is_reversed;
1600 Map<std::pair<int, int>,
int> verts_to_edge;
1607 static int prepare_need_vert(CDT_data &cd,
const mpq3 &p3d)
1609 mpq2 p2d = project_3d_to_2d(p3d, cd.proj_axis);
1610 int v = cd.vert.append_and_get_index(p2d);
1621 static mpq3 unproject_cdt_vert(
const CDT_data &cd,
const mpq2 &p2d)
1625 BLI_assert(cd.t_plane->norm_exact[cd.proj_axis] != 0);
1626 const mpq3 &n = cd.t_plane->norm_exact;
1627 const mpq_class &
d = cd.t_plane->d_exact;
1628 switch (cd.proj_axis) {
1630 mpq_class num = n[1] * p2d[0] + n[2] * p2d[1] +
d;
1632 p3d[0] = num / n[0];
1639 mpq_class num = n[0] * p2d[0] + n[2] * p2d[1] +
d;
1641 p3d[1] = num / n[1];
1648 mpq_class num = n[0] * p2d[0] + n[1] * p2d[1] +
d;
1650 p3d[2] = num / n[2];
1659 static void prepare_need_edge(CDT_data &cd,
const mpq3 &p1,
const mpq3 &p2)
1661 int v1 = prepare_need_vert(cd, p1);
1662 int v2 = prepare_need_vert(cd, p2);
1663 cd.edge.append(std::pair<int, int>(
v1,
v2));
1666 static void prepare_need_tri(CDT_data &cd,
const IMesh &tm,
int t)
1668 const Face &tri = *tm.face(
t);
1669 int v0 = prepare_need_vert(cd, tri[0]->co_exact);
1670 int v1 = prepare_need_vert(cd, tri[1]->co_exact);
1671 int v2 = prepare_need_vert(cd, tri[2]->co_exact);
1676 if (tri.plane->norm_exact[cd.proj_axis] >= 0) {
1677 rev = cd.proj_axis == 1;
1680 rev = cd.proj_axis != 1;
1682 int cd_t = cd.face.append_and_get_index(Vector<int>());
1683 cd.face[cd_t].append(v0);
1685 cd.face[cd_t].append(
v2);
1686 cd.face[cd_t].append(
v1);
1689 cd.face[cd_t].append(
v1);
1690 cd.face[cd_t].append(
v2);
1692 cd.input_face.append(
t);
1693 cd.is_reversed.append(rev);
1696 static CDT_data prepare_cdt_input(
const IMesh &tm,
int t,
const Vector<ITT_value> itts)
1700 ans.t_plane = tm.face(
t)->plane;
1703 prepare_need_tri(ans, tm,
t);
1704 for (
const ITT_value &itt : itts) {
1709 prepare_need_vert(ans, itt.p1);
1713 prepare_need_edge(ans, itt.p1, itt.p2);
1717 prepare_need_tri(ans, tm, itt.t_source);
1725 static CDT_data prepare_cdt_input_for_cluster(
const IMesh &tm,
1726 const CoplanarClusterInfo &clinfo,
1728 const Vector<ITT_value> itts)
1732 const CoplanarCluster &cl = clinfo.cluster(
c);
1736 ans.t_plane = tm.face(t0)->plane;
1739 for (
const int t : cl) {
1740 prepare_need_tri(ans, tm,
t);
1742 for (
const ITT_value &itt : itts) {
1745 prepare_need_vert(ans, itt.p1);
1749 prepare_need_edge(ans, itt.p1, itt.p2);
1760 static inline std::pair<int, int> sorted_int_pair(std::pair<int, int> pair)
1762 if (pair.first <= pair.second) {
1765 return std::pair<int, int>(pair.second, pair.first);
1772 static void populate_cdt_edge_map(
Map<std::pair<int, int>,
int> &verts_to_edge,
1775 verts_to_edge.reserve(cdt_out.edge.size());
1776 for (
int e : cdt_out.edge.index_range()) {
1777 std::pair<int, int> vpair = sorted_int_pair(cdt_out.edge[
e]);
1779 verts_to_edge.add(vpair,
e);
1786 static void do_cdt(CDT_data &cd)
1788 constexpr
int dbg_level = 0;
1790 cdt_in.vert = Span<mpq2>(cd.vert);
1791 cdt_in.edge = Span<std::pair<int, int>>(cd.edge);
1792 cdt_in.face = Span<Vector<int>>(cd.face);
1793 if (dbg_level > 0) {
1794 std::cout <<
"CDT input\nVerts:\n";
1795 for (
int i : cdt_in.vert.index_range()) {
1796 std::cout <<
"v" << i <<
": " << cdt_in.vert[i] <<
"=(" << cdt_in.vert[i][0].get_d() <<
","
1797 << cdt_in.vert[i][1].get_d() <<
")\n";
1799 std::cout <<
"Edges:\n";
1800 for (
int i : cdt_in.edge.index_range()) {
1801 std::cout <<
"e" << i <<
": (" << cdt_in.edge[i].first <<
", " << cdt_in.edge[i].second
1804 std::cout <<
"Tris\n";
1805 for (
int f : cdt_in.face.index_range()) {
1806 std::cout <<
"f" << f <<
": ";
1807 for (
int j : cdt_in.face[f].index_range()) {
1808 std::cout << cdt_in.face[f][j] <<
" ";
1815 constexpr
int make_edge_map_threshold = 15;
1816 if (cd.cdt_out.edge.size() >= make_edge_map_threshold) {
1817 populate_cdt_edge_map(cd.verts_to_edge, cd.cdt_out);
1819 if (dbg_level > 0) {
1820 std::cout <<
"\nCDT result\nVerts:\n";
1821 for (
int i : cd.cdt_out.vert.index_range()) {
1822 std::cout <<
"v" << i <<
": " << cd.cdt_out.vert[i] <<
"=(" << cd.cdt_out.vert[i][0].get_d()
1823 <<
"," << cd.cdt_out.vert[i][1].get_d() <<
"\n";
1825 std::cout <<
"Tris\n";
1826 for (
int f : cd.cdt_out.face.index_range()) {
1827 std::cout <<
"f" << f <<
": ";
1828 for (
int j : cd.cdt_out.face[f].index_range()) {
1829 std::cout << cd.cdt_out.face[f][j] <<
" ";
1831 std::cout <<
"orig: ";
1832 for (
int j : cd.cdt_out.face_orig[f].index_range()) {
1833 std::cout << cd.cdt_out.face_orig[f][j] <<
" ";
1837 std::cout <<
"Edges\n";
1838 for (
int e : cd.cdt_out.edge.index_range()) {
1839 std::cout <<
"e" <<
e <<
": (" << cd.cdt_out.edge[
e].first <<
", "
1840 << cd.cdt_out.edge[
e].second <<
") ";
1841 std::cout <<
"orig: ";
1842 for (
int j : cd.cdt_out.edge_orig[
e].index_range()) {
1843 std::cout << cd.cdt_out.edge_orig[
e][j] <<
" ";
1860 static int get_cdt_edge_orig(
1861 int i0,
int i1,
const CDT_data &cd,
const IMesh &in_tm,
bool *r_is_intersect)
1863 int foff = cd.cdt_out.face_edge_offset;
1864 *r_is_intersect =
false;
1866 if (cd.verts_to_edge.size() > 0) {
1868 std::pair<int, int> vpair = sorted_int_pair(std::pair<int, int>(i0,
i1));
1869 e = cd.verts_to_edge.lookup_default(vpair, NO_INDEX);
1872 for (
int ee : cd.cdt_out.edge.index_range()) {
1873 std::pair<int, int>
edge = cd.cdt_out.edge[ee];
1880 if (
e == NO_INDEX) {
1887 int face_eorig = NO_INDEX;
1888 bool have_non_face_eorig =
false;
1889 for (
int orig_index : cd.cdt_out.edge_orig[
e]) {
1891 if (orig_index >= foff) {
1892 if (face_eorig == NO_INDEX) {
1893 int in_face_index = (orig_index / foff) - 1;
1894 int pos = orig_index % foff;
1897 int in_tm_face_index = cd.input_face[in_face_index];
1898 BLI_assert(in_tm_face_index < in_tm.face_size());
1899 const Face *facep = in_tm.face(in_tm_face_index);
1901 bool is_rev = cd.is_reversed[in_face_index];
1902 int eorig = is_rev ? facep->edge_orig[2 -
pos] : facep->edge_orig[
pos];
1903 if (eorig != NO_INDEX) {
1909 if (!have_non_face_eorig) {
1910 have_non_face_eorig =
true;
1912 if (face_eorig != NO_INDEX && have_non_face_eorig) {
1918 if (face_eorig != NO_INDEX) {
1921 if (have_non_face_eorig) {
1926 *r_is_intersect =
true;
1937 static Face *cdt_tri_as_imesh_face(
1938 int cdt_out_t,
int cdt_in_t,
const CDT_data &cd,
const IMesh &tm, IMeshArena *arena)
1941 int t_orig = tm.face(cd.input_face[cdt_in_t])->orig;
1942 BLI_assert(cdt_out.face[cdt_out_t].size() == 3);
1943 int i0 = cdt_out.face[cdt_out_t][0];
1944 int i1 = cdt_out.face[cdt_out_t][1];
1945 int i2 = cdt_out.face[cdt_out_t][2];
1946 mpq3 v0co = unproject_cdt_vert(cd, cdt_out.vert[i0]);
1947 mpq3 v1co = unproject_cdt_vert(cd, cdt_out.vert[
i1]);
1948 mpq3 v2co = unproject_cdt_vert(cd, cdt_out.vert[i2]);
1952 const Vert *v0 = arena->add_or_find_vert(v0co, NO_INDEX);
1953 const Vert *
v1 = arena->add_or_find_vert(v1co, NO_INDEX);
1954 const Vert *
v2 = arena->add_or_find_vert(v2co, NO_INDEX);
1959 if (cd.is_reversed[cdt_in_t]) {
1960 int oe0 = get_cdt_edge_orig(i0, i2, cd, tm, &is_isect0);
1961 int oe1 = get_cdt_edge_orig(i2,
i1, cd, tm, &is_isect1);
1962 int oe2 = get_cdt_edge_orig(
i1, i0, cd, tm, &is_isect2);
1963 facep = arena->add_face(
1964 {v0,
v2,
v1}, t_orig, {oe0, oe1, oe2}, {is_isect0, is_isect1, is_isect2});
1967 int oe0 = get_cdt_edge_orig(i0,
i1, cd, tm, &is_isect0);
1968 int oe1 = get_cdt_edge_orig(
i1, i2, cd, tm, &is_isect1);
1969 int oe2 = get_cdt_edge_orig(i2, i0, cd, tm, &is_isect2);
1970 facep = arena->add_face(
1971 {v0,
v1,
v2}, t_orig, {oe0, oe1, oe2}, {is_isect0, is_isect1, is_isect2});
1973 facep->populate_plane(
false);
1978 static bool is_quad_flip_first_third(
const double3 &
v1,
2002 static Array<Face *> polyfill_triangulate_poly(
Face *f, IMeshArena *arena)
2005 int flen = f->size();
2007 if (!f->plane_populated()) {
2008 f->populate_plane(
false);
2010 const double3 &poly_normal = f->plane->norm;
2011 float no[3] = {
float(poly_normal[0]),
float(poly_normal[1]),
float(poly_normal[2])};
2014 const Vert *v0 = (*f)[0];
2015 const Vert *
v1 = (*f)[1];
2016 const Vert *
v2 = (*f)[2];
2017 const Vert *v3 = (*f)[3];
2018 int eo_01 = f->edge_orig[0];
2019 int eo_12 = f->edge_orig[1];
2020 int eo_23 = f->edge_orig[2];
2021 int eo_30 = f->edge_orig[3];
2023 if (
UNLIKELY(is_quad_flip_first_third(v0->co,
v1->co,
v2->
co, v3->co, f->plane->norm))) {
2024 f0 = arena->add_face({v0,
v1, v3}, f->orig, {eo_01, -1, eo_30}, {
false,
false,
false});
2025 f1 = arena->add_face({
v1,
v2, v3}, f->orig, {eo_12, eo_23, -1}, {
false,
false,
false});
2028 f0 = arena->add_face({v0,
v1,
v2}, f->orig, {eo_01, eo_12, -1}, {
false,
false,
false});
2029 f1 = arena->add_face({v0,
v2, v3}, f->orig, {-1, eo_23, eo_30}, {
false,
false,
false});
2031 return Array<Face *>{f0, f1};
2033 float axis_mat[3][3];
2034 float(*projverts)[2];
2035 unsigned int(*tris)[3];
2036 const int totfilltri = flen - 2;
2038 tris =
static_cast<unsigned int(*)[3]
>(
MEM_malloc_arrayN(totfilltri,
sizeof(*tris), __func__));
2039 projverts =
static_cast<float(*)[2]
>(
MEM_malloc_arrayN(flen,
sizeof(*projverts), __func__));
2041 for (
int j = 0; j < flen; ++j) {
2042 const double3 &dco = (*f)[j]->co;
2048 Array<Face *> ans(totfilltri);
2049 for (
int t = 0;
t < totfilltri; ++
t) {
2050 unsigned int *tri = tris[
t];
2053 for (
int k = 0; k < 3; k++) {
2055 v[k] = (*f)[tri[k]];
2058 if ((tri[k] + 1) % flen == tri[(k + 1) % 3]) {
2059 eo[k] = f->edge_orig[tri[k]];
2064 ans[
t] = arena->add_face(
2065 {
v[0],
v[1],
v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {
false,
false,
false});
2090 static Array<Face *> exact_triangulate_poly(
Face *f, IMeshArena *arena)
2092 int flen = f->size();
2094 cdt_in.vert = Array<mpq2>(flen);
2095 cdt_in.face = Array<Vector<int>>(1);
2096 cdt_in.face[0].reserve(flen);
2097 for (
int i : f->index_range()) {
2098 cdt_in.face[0].append(i);
2101 if (!f->plane_populated()) {
2102 f->populate_plane(
false);
2104 const double3 &poly_normal = f->plane->norm;
2110 bool rev1 = (axis == 1);
2111 bool rev2 = poly_normal[axis] < 0;
2112 bool rev = rev1 ^ rev2;
2113 for (
int i = 0; i < flen; ++i) {
2114 int ii = rev ? flen - i - 1 : i;
2115 mpq2 &p2d = cdt_in.vert[ii];
2117 for (
int j = 0; j < 3; ++j) {
2119 p2d[k++] = (*f)[ii]->co_exact[j];
2124 int n_tris = cdt_out.face.size();
2125 Array<Face *> ans(n_tris);
2126 for (
int t = 0;
t < n_tris; ++
t) {
2130 bool needs_steiner =
false;
2131 for (
int i = 0; i < 3; ++i) {
2132 i_v_out[i] = cdt_out.face[
t][i];
2133 if (cdt_out.vert_orig[i_v_out[i]].size() == 0) {
2134 needs_steiner =
true;
2137 v[i] = (*f)[cdt_out.vert_orig[i_v_out[i]][0]];
2139 if (needs_steiner) {
2141 return polyfill_triangulate_poly(f, arena);
2143 Map<std::pair<int, int>,
int> verts_to_edge;
2144 populate_cdt_edge_map(verts_to_edge, cdt_out);
2146 for (
int i = 0; i < 3; ++i) {
2147 std::pair<int, int> vpair(i_v_out[i], i_v_out[(i + 1) % 3]);
2148 std::pair<int, int> vpair_canon = sorted_int_pair(vpair);
2149 int e_out = verts_to_edge.lookup_default(vpair_canon, NO_INDEX);
2152 for (
int orig : cdt_out.edge_orig[e_out]) {
2154 int pos = orig % foff;
2156 eo[i] = f->edge_orig[
pos];
2162 ans[
t] = arena->add_face(
2163 {
v[0],
v[2],
v[1]}, f->orig, {eo[2], eo[1], eo[0]}, {
false,
false,
false});
2166 ans[
t] = arena->add_face(
2167 {
v[0],
v[1],
v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {
false,
false,
false});
2173 static bool face_is_degenerate(
const Face *f)
2175 const Face &face = *f;
2176 const Vert *v0 = face[0];
2177 const Vert *
v1 = face[1];
2178 const Vert *
v2 = face[2];
2179 if (v0 ==
v1 || v0 ==
v2 ||
v1 ==
v2) {
2186 double err_bound = supremum_dot_cross(dab, dab) * index_dot_cross * DBL_EPSILON;
2187 if (dab_length_squared > err_bound) {
2190 mpq3
a =
v2->co_exact - v0->co_exact;
2191 mpq3
b =
v2->co_exact -
v1->co_exact;
2193 if (ab.x == 0 && ab.y == 0 && ab.z == 0) {
2201 static bool any_degenerate_tris_fast(
const Array<Face *> triangulation)
2203 for (
const Face *f : triangulation) {
2204 const Vert *v0 = (*f)[0];
2205 const Vert *
v1 = (*f)[1];
2206 const Vert *
v2 = (*f)[2];
2207 if (v0 ==
v1 || v0 ==
v2 ||
v1 ==
v2) {
2214 if (da_length_squared == 0.0 || db_length_squared == 0.0) {
2223 double sin_squared_t = dab_length_squared / (da_length_squared * db_length_squared);
2224 if (sin_squared_t < 1
e-8) {
2239 static Array<Face *> triangulate_poly(
Face *f, IMeshArena *arena)
2242 Array<Face *> ans = polyfill_triangulate_poly(f, arena);
2245 if (any_degenerate_tris_fast(ans)) {
2246 return exact_triangulate_poly(f, arena);
2251 IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
2253 Vector<Face *> face_tris;
2254 constexpr
int estimated_tris_per_face = 3;
2255 face_tris.reserve(estimated_tris_per_face * imesh.face_size());
2257 for (int i : range) {
2258 Face *f = imesh.face(i);
2259 if (!f->plane_populated() && f->size() >= 4) {
2260 f->populate_plane(false);
2264 for (
Face *f : imesh.faces()) {
2266 int flen = f->size();
2268 face_tris.append(f);
2271 Array<Face *> tris = triangulate_poly(f, arena);
2272 for (
Face *tri : tris) {
2273 face_tris.append(tri);
2277 return IMesh(face_tris);
2284 static IMesh extract_subdivided_tri(
const CDT_data &cd,
2291 for (
int i = 0; i < cd.input_face.size(); ++i) {
2292 if (cd.input_face[i] ==
t) {
2296 if (t_in_cdt == -1) {
2297 std::cout <<
"Could not find " <<
t <<
" in cdt input tris\n";
2301 constexpr
int inline_buf_size = 20;
2302 Vector<Face *, inline_buf_size>
faces;
2303 for (
int f : cdt_out.face.index_range()) {
2304 if (cdt_out.face_orig[f].contains(t_in_cdt)) {
2305 Face *facep = cdt_tri_as_imesh_face(f, t_in_cdt, cd, in_tm, arena);
2306 faces.append(facep);
2309 return IMesh(
faces);
2314 if (
a.indexA <
b.indexA) {
2317 if ((
a.indexA ==
b.indexA) & (
a.indexB <
b.indexB)) {
2326 Array<int> first_overlap_;
2327 uint overlap_num_{0};
2331 std::function<int(
int)> shape_fn;
2337 TriOverlaps(
const IMesh &tm,
2338 const Array<BoundingBox> &tri_bb,
2340 std::function<
int(
int)> shape_fn,
2343 constexpr
int dbg_level = 0;
2344 if (dbg_level > 0) {
2345 std::cout <<
"TriOverlaps construction\n";
2351 bool two_trees_no_self = nshapes == 2 && !use_self;
2352 if (two_trees_no_self) {
2358 shapes.resize(tm.face_size());
2360 for (int t : range) {
2361 shapes[t] = shape_fn(tm.face(t)->orig);
2366 for (
int t : tm.face_index_range()) {
2370 int shape = shapes[
t];
2371 if (two_trees_no_self) {
2375 else if (shape == 1) {
2386 if (two_trees_no_self) {
2392 CBData cbdata{tm, shape_fn, nshapes, use_self};
2398 tree_, tree_, &overlap_num_, only_different_shapes, &cbdata);
2404 if (two_trees_no_self) {
2406 MEM_reallocN(overlap_, 2 * overlap_num_ *
sizeof(overlap_[0])));
2407 for (
uint i = 0; i < overlap_num_; ++i) {
2408 overlap_[overlap_num_ + i].
indexA = overlap_[i].indexB;
2409 overlap_[overlap_num_ + i].indexB = overlap_[i].indexA;
2411 overlap_num_ += overlap_num_;
2414 std::sort(overlap_, overlap_ + overlap_num_, bvhtreeverlap_cmp);
2415 if (dbg_level > 0) {
2416 std::cout << overlap_num_ <<
" overlaps found:\n";
2418 std::cout <<
"A: " << ov.indexA <<
", B: " << ov.indexB <<
"\n";
2421 first_overlap_ = Array<int>(tm.face_size(), -1);
2422 for (
int i = 0; i < static_cast<int>(overlap_num_); ++i) {
2423 int t = overlap_[i].indexA;
2424 if (first_overlap_[
t] == -1) {
2425 first_overlap_[
t] = i;
2443 Span<BVHTreeOverlap> overlap()
const
2445 return Span<BVHTreeOverlap>(overlap_, overlap_num_);
2448 int first_overlap_index(
int t)
const
2450 return first_overlap_[
t];
2454 static bool only_different_shapes(
void *userdata,
int index_a,
int index_b,
int UNUSED(
thread))
2457 return cbdata->tm.face(index_a)->orig != cbdata->tm.face(index_b)->orig;
2464 struct OverlapIttsData {
2465 Vector<std::pair<int, int>> intersect_pairs;
2466 Map<std::pair<int, int>, ITT_value> &itt_map;
2470 OverlapIttsData(
Map<std::pair<int, int>, ITT_value> &itt_map,
const IMesh &tm, IMeshArena *arena)
2471 : itt_map(itt_map), tm(tm), arena(arena)
2480 static std::pair<int, int> canon_int_pair(
int a,
int b)
2485 return std::pair<int, int>(
a,
b);
2488 static void calc_overlap_itts_range_func(
void *__restrict userdata,
2492 constexpr
int dbg_level = 0;
2493 OverlapIttsData *
data =
static_cast<OverlapIttsData *
>(userdata);
2494 std::pair<int, int> tri_pair =
data->intersect_pairs[iter];
2495 int a = tri_pair.first;
2496 int b = tri_pair.second;
2497 if (dbg_level > 0) {
2498 std::cout <<
"calc_overlap_itts_range_func a=" <<
a <<
", b=" <<
b <<
"\n";
2500 ITT_value itt = intersect_tri_tri(
data->tm,
a,
b);
2501 if (dbg_level > 0) {
2502 std::cout <<
"result of intersecting " <<
a <<
" and " <<
b <<
" = " << itt <<
"\n";
2505 data->itt_map.add_overwrite(tri_pair, itt);
2512 static void calc_overlap_itts(
Map<std::pair<int, int>, ITT_value> &itt_map,
2514 const TriOverlaps &ov,
2517 OverlapIttsData
data(itt_map, tm, arena);
2522 std::pair<int, int> key = canon_int_pair(olap.indexA, olap.indexB);
2523 if (!itt_map.contains(key)) {
2524 itt_map.add_new(key, ITT_value());
2525 data.intersect_pairs.append(key);
2528 int tot_intersect_pairs =
data.intersect_pairs.size();
2542 static void calc_subdivided_non_cluster_tris(Array<IMesh> &r_tri_subdivided,
2544 const Map<std::pair<int, int>, ITT_value> &itt_map,
2545 const CoplanarClusterInfo &clinfo,
2546 const TriOverlaps &ov,
2549 const int dbg_level = 0;
2550 if (dbg_level > 0) {
2551 std::cout <<
"\nCALC_SUBDIVIDED_TRIS\n\n";
2553 Span<BVHTreeOverlap> overlap = ov.overlap();
2554 struct OverlapTriRange {
2559 Vector<OverlapTriRange> overlap_tri_range;
2560 int overlap_num = overlap.size();
2561 overlap_tri_range.reserve(overlap_num);
2562 int overlap_index = 0;
2563 while (overlap_index < overlap_num) {
2564 int t = overlap[overlap_index].indexA;
2565 int i = overlap_index;
2566 while (i + 1 < overlap_num && overlap[i + 1].indexA ==
t) {
2572 if (clinfo.tri_cluster(
t) == NO_INDEX) {
2573 int len = i - overlap_index + 1;
2574 if (!(
len == 1 && overlap[overlap_index].indexB ==
t)) {
2575 OverlapTriRange range = {
t, overlap_index,
len};
2576 overlap_tri_range.append(range);
2578 bumpperfcount(0,
len);
2582 overlap_index = i + 1;
2584 int overlap_tri_range_num = overlap_tri_range.size();
2585 Array<CDT_data> cd_data(overlap_tri_range_num);
2586 int grain_size = 64;
2588 for (int otr_index : range) {
2589 OverlapTriRange &otr = overlap_tri_range[otr_index];
2590 int t = otr.tri_index;
2591 if (dbg_level > 0) {
2592 std::cout <<
"handling overlap range\nt=" << t <<
" start=" << otr.overlap_start
2593 <<
" len=" << otr.len <<
"\n";
2595 constexpr int inline_capacity = 100;
2596 Vector<ITT_value, inline_capacity> itts(otr.len);
2597 for (int j = otr.overlap_start; j < otr.overlap_start + otr.len; ++j) {
2598 int t_other = overlap[j].indexB;
2599 std::pair<int, int> key = canon_int_pair(t, t_other);
2601 if (itt_map.contains(key)) {
2602 itt = itt_map.lookup(key);
2604 if (itt.kind != INONE) {
2607 if (dbg_level > 0) {
2608 std::cout <<
" tri t" << t_other <<
"; result = " << itt <<
"\n";
2611 if (itts.size() > 0) {
2612 cd_data[otr_index] = prepare_cdt_input(tm, t, itts);
2613 do_cdt(cd_data[otr_index]);
2618 for (
int otr_index : overlap_tri_range.index_range()) {
2619 CDT_data &cdd = cd_data[otr_index];
2620 if (cdd.vert.size() > 0) {
2621 int t = overlap_tri_range[otr_index].tri_index;
2622 r_tri_subdivided[
t] = extract_subdivided_tri(cdd, tm,
t, arena);
2623 if (dbg_level > 1) {
2624 std::cout <<
"subdivide output for tri " <<
t <<
" = " << r_tri_subdivided[
t];
2631 for (int t : range) {
2632 if (r_tri_subdivided[t].face_size() == 0 && clinfo.tri_cluster(t) == NO_INDEX) {
2633 r_tri_subdivided[t] = IMesh({tm.face(t)});
2646 static void calc_cluster_tris(Array<IMesh> &tri_subdivided,
2648 const CoplanarClusterInfo &clinfo,
2649 const Array<CDT_data> &cluster_subdivided,
2652 for (
int c : clinfo.index_range()) {
2653 const CoplanarCluster &cl = clinfo.cluster(
c);
2654 const CDT_data &cd = cluster_subdivided[
c];
2662 int n_cluster_tris = cl.tot_tri();
2664 BLI_assert(cd.input_face.size() == n_cluster_tris);
2665 Array<Vector<Face *>> face_vec(n_cluster_tris);
2666 for (
int cdt_out_t : cdt_out.face.index_range()) {
2667 for (
int cdt_in_t : cdt_out.face_orig[cdt_out_t]) {
2668 Face *f = cdt_tri_as_imesh_face(cdt_out_t, cdt_in_t, cd, tm, arena);
2669 face_vec[cdt_in_t].append(f);
2672 for (
int cdt_in_t : cd.input_face.index_range()) {
2673 int tm_t = cd.input_face[cdt_in_t];
2674 BLI_assert(tri_subdivided[tm_t].face_size() == 0);
2675 tri_subdivided[tm_t] = IMesh(face_vec[cdt_in_t]);
2680 static CDT_data calc_cluster_subdivided(
const CoplanarClusterInfo &clinfo,
2683 const TriOverlaps &ov,
2684 const Map<std::pair<int, int>, ITT_value> &itt_map,
2685 IMeshArena *
UNUSED(arena))
2687 constexpr
int dbg_level = 0;
2689 const CoplanarCluster &cl = clinfo.cluster(
c);
2691 if (dbg_level > 0) {
2692 std::cout <<
"CALC_CLUSTER_SUBDIVIDED for cluster " <<
c <<
" = " << cl <<
"\n";
2697 Vector<ITT_value> itts;
2698 Span<BVHTreeOverlap> ovspan = ov.overlap();
2700 if (dbg_level > 0) {
2701 std::cout <<
"find intersects with triangle " <<
t <<
" of cluster\n";
2703 int first_i = ov.first_overlap_index(
t);
2704 if (first_i == -1) {
2707 for (
int i = first_i; i < ovspan.size() && ovspan[i].indexA ==
t; ++i) {
2708 int t_other = ovspan[i].indexB;
2709 if (clinfo.tri_cluster(t_other) !=
c) {
2710 if (dbg_level > 0) {
2711 std::cout <<
"use intersect(" <<
t <<
"," << t_other <<
"\n";
2713 std::pair<int, int> key = canon_int_pair(
t, t_other);
2714 if (itt_map.contains(key)) {
2715 ITT_value itt = itt_map.lookup(key);
2716 if (!
ELEM(itt.kind, INONE, ICOPLANAR)) {
2718 if (dbg_level > 0) {
2719 std::cout <<
" itt = " << itt <<
"\n";
2727 CDT_data cd_data = prepare_cdt_input_for_cluster(tm, clinfo,
c, itts);
2735 for (
const IMesh &m : tri_subdivided) {
2736 tot_tri += m.face_size();
2738 Array<Face *>
faces(tot_tri);
2740 for (
const IMesh &m : tri_subdivided) {
2741 for (
Face *f : m.faces()) {
2742 faces[face_index++] = f;
2745 return IMesh(
faces);
2748 static CoplanarClusterInfo find_clusters(
const IMesh &tm,
2749 const Array<BoundingBox> &tri_bb,
2750 const Map<std::pair<int, int>, ITT_value> &itt_map)
2752 constexpr
int dbg_level = 0;
2753 if (dbg_level > 0) {
2754 std::cout <<
"FIND_CLUSTERS\n";
2756 CoplanarClusterInfo ans(tm.face_size());
2758 VectorSet<int> maybe_coplanar_tris;
2759 maybe_coplanar_tris.reserve(2 * itt_map.size());
2760 for (
auto item : itt_map.items()) {
2761 if (item.value.kind == ICOPLANAR) {
2762 int t1 = item.key.first;
2763 int t2 = item.key.second;
2764 maybe_coplanar_tris.add_multiple({t1, t2});
2767 if (dbg_level > 0) {
2768 std::cout <<
"found " << maybe_coplanar_tris.size() <<
" possible coplanar tris\n";
2770 if (maybe_coplanar_tris.size() == 0) {
2771 if (dbg_level > 0) {
2772 std::cout <<
"No possible coplanar tris, so no clusters\n";
2779 Map<Plane, Vector<CoplanarCluster>> plane_cls;
2780 plane_cls.reserve(maybe_coplanar_tris.size());
2781 for (
int t : maybe_coplanar_tris) {
2785 Plane tplane = *tm.face(
t)->plane;
2787 tplane.make_canonical();
2788 if (dbg_level > 0) {
2789 std::cout <<
"plane for tri " <<
t <<
" = " << &tplane <<
"\n";
2792 if (plane_cls.contains(tplane)) {
2793 Vector<CoplanarCluster> &curcls = plane_cls.lookup(tplane);
2794 if (dbg_level > 0) {
2795 std::cout <<
"already has " << curcls.size() <<
" clusters\n";
2798 Vector<CoplanarCluster *> int_cls;
2799 Vector<CoplanarCluster *> no_int_cls;
2800 for (CoplanarCluster &cl : curcls) {
2801 if (dbg_level > 1) {
2802 std::cout <<
"consider intersecting with cluster " << cl <<
"\n";
2804 if (bbs_might_intersect(tri_bb[
t], cl.bounding_box())) {
2805 if (dbg_level > 1) {
2806 std::cout <<
"append to int_cls\n";
2808 int_cls.append(&cl);
2811 if (dbg_level > 1) {
2812 std::cout <<
"append to no_int_cls\n";
2814 no_int_cls.append(&cl);
2817 if (int_cls.size() == 0) {
2819 if (dbg_level > 1) {
2820 std::cout <<
"no intersecting clusters for t, make a new one\n";
2822 curcls.append(CoplanarCluster(
t, tri_bb[
t]));
2824 else if (int_cls.size() == 1) {
2826 if (dbg_level > 1) {
2827 std::cout <<
"exactly one existing cluster, " << int_cls[0] <<
", adding to it\n";
2829 int_cls[0]->add_tri(
t, tri_bb[
t]);
2834 if (dbg_level > 1) {
2835 std::cout <<
"merging\n";
2837 CoplanarCluster mergecl;
2838 mergecl.add_tri(
t, tri_bb[
t]);
2839 for (CoplanarCluster *cl : int_cls) {
2841 mergecl.add_tri(
t, tri_bb[
t]);
2844 Vector<CoplanarCluster> newvec;
2845 newvec.append(mergecl);
2846 for (CoplanarCluster *cl_no_int : no_int_cls) {
2847 newvec.append(*cl_no_int);
2849 plane_cls.add_overwrite(tplane, newvec);
2853 if (dbg_level > 0) {
2854 std::cout <<
"first cluster for its plane\n";
2856 plane_cls.add_new(tplane, Vector<CoplanarCluster>{CoplanarCluster(
t, tri_bb[
t])});
2861 for (
auto item : plane_cls.items()) {
2862 for (
const CoplanarCluster &cl : item.value) {
2863 if (cl.tot_tri() > 1) {
2864 ans.add_cluster(cl);
2877 struct DegenChunkData {
2878 bool has_degenerate_tri =
false;
2881 static void degenerate_range_func(
void *__restrict userdata,
2885 DegenData *
data =
static_cast<DegenData *
>(userdata);
2886 DegenChunkData *chunk_data =
static_cast<DegenChunkData *
>(tls->userdata_chunk);
2887 const Face *f =
data->tm.face(iter);
2888 bool is_degenerate = face_is_degenerate(f);
2889 chunk_data->has_degenerate_tri |= is_degenerate;
2892 static void degenerate_reduce(
const void *__restrict
UNUSED(userdata),
2893 void *__restrict chunk_join,
2894 void *__restrict chunk)
2896 DegenChunkData *degen_chunk_join =
static_cast<DegenChunkData *
>(chunk_join);
2897 DegenChunkData *degen_chunk =
static_cast<DegenChunkData *
>(chunk);
2898 degen_chunk_join->has_degenerate_tri |= degen_chunk->has_degenerate_tri;
2902 static bool has_degenerate_tris(
const IMesh &tm)
2904 DegenData degen_data = {tm};
2905 DegenChunkData degen_chunk_data;
2914 return degen_chunk_data.has_degenerate_tri;
2917 static IMesh remove_degenerate_tris(
const IMesh &tm_in)
2920 Vector<Face *> new_faces;
2921 new_faces.reserve(tm_in.face_size());
2922 for (
Face *f : tm_in.faces()) {
2923 if (!face_is_degenerate(f)) {
2924 new_faces.append(f);
2927 ans.set_faces(new_faces);
2931 IMesh trimesh_self_intersect(
const IMesh &tm_in, IMeshArena *arena)
2933 return trimesh_nary_intersect(
2934 tm_in, 1, [](
int UNUSED(
t)) {
return 0; },
true, arena);
2937 IMesh trimesh_nary_intersect(
const IMesh &tm_in,
2939 std::function<
int(
int)> shape_fn,
2943 constexpr
int dbg_level = 0;
2944 if (dbg_level > 0) {
2945 std::cout <<
"\nTRIMESH_NARY_INTERSECT nshapes=" << nshapes <<
" use_self=" << use_self
2947 for (
const Face *f : tm_in.faces()) {
2951 if (dbg_level > 1) {
2952 std::cout <<
"input mesh:\n" << tm_in;
2953 for (
int t : tm_in.face_index_range()) {
2954 std::cout <<
"shape(" <<
t <<
") = " << shape_fn(tm_in.face(
t)->orig) <<
"\n";
2956 write_obj_mesh(
const_cast<IMesh &
>(tm_in),
"trimesh_input");
2962 std::cout <<
"trimesh_nary_intersect start\n";
2966 const IMesh *tm_clean = &tm_in;
2968 if (has_degenerate_tris(tm_in)) {
2969 if (dbg_level > 0) {
2970 std::cout <<
"cleaning degenerate triangles\n";
2972 tm_cleaned = remove_degenerate_tris(tm_in);
2973 tm_clean = &tm_cleaned;
2974 if (dbg_level > 1) {
2975 std::cout <<
"cleaned input mesh:\n" << tm_cleaned;
2980 std::cout <<
"cleaned, time = " << clean_time - start_time <<
"\n";
2982 Array<BoundingBox> tri_bb = calc_face_bounding_boxes(*tm_clean);
2985 std::cout <<
"bbs calculated, time = " << bb_calc_time - clean_time <<
"\n";
2987 TriOverlaps tri_ov(*tm_clean, tri_bb, nshapes, shape_fn, use_self);
2990 std::cout <<
"intersect overlaps calculated, time = " << overlap_time - bb_calc_time <<
"\n";
2992 Array<IMesh> tri_subdivided(tm_clean->face_size(), NoInitialization());
2994 for (int t : range) {
2995 if (tri_ov.first_overlap_index(t) != -1) {
2996 tm_clean->face(t)->populate_plane(true);
2998 new (static_cast<void *>(&tri_subdivided[t])) IMesh;
3003 std::cout <<
"planes populated, time = " << plane_populate - overlap_time <<
"\n";
3007 Map<std::pair<int, int>, ITT_value> itt_map;
3008 itt_map.reserve(tri_ov.overlap().size());
3009 calc_overlap_itts(itt_map, *tm_clean, tri_ov, arena);
3012 std::cout <<
"itts found, time = " << itt_time - plane_populate <<
"\n";
3014 CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb, itt_map);
3015 if (dbg_level > 1) {
3016 std::cout << clinfo;
3020 std::cout <<
"clusters found, time = " << find_cluster_time - itt_time <<
"\n";
3021 doperfmax(0, tm_in.face_size());
3022 doperfmax(1, clinfo.tot_cluster());
3023 doperfmax(2, tri_ov.overlap().size());
3025 calc_subdivided_non_cluster_tris(tri_subdivided, *tm_clean, itt_map, clinfo, tri_ov, arena);
3028 std::cout <<
"subdivided non-cluster tris found, time = " << subdivided_tris_time - itt_time
3031 Array<CDT_data> cluster_subdivided(clinfo.tot_cluster());
3032 for (
int c : clinfo.index_range()) {
3033 cluster_subdivided[
c] = calc_cluster_subdivided(clinfo,
c, *tm_clean, tri_ov, itt_map, arena);
3037 std::cout <<
"subdivided clusters found, time = "
3038 << cluster_subdivide_time - subdivided_tris_time <<
"\n";
3040 calc_cluster_tris(tri_subdivided, *tm_clean, clinfo, cluster_subdivided, arena);
3043 std::cout <<
"subdivided cluster tris found, time = " << extract_time - cluster_subdivide_time
3046 IMesh combined = union_tri_subdivides(tri_subdivided);
3047 if (dbg_level > 1) {
3048 std::cout <<
"TRIMESH_NARY_INTERSECT answer:\n";
3049 std::cout << combined;
3053 std::cout <<
"triangles combined, time = " << end_time - extract_time <<
"\n";
3054 std::cout <<
"trimesh_nary_intersect done, total time = " << end_time - start_time <<
"\n";
3060 static std::ostream &
operator<<(std::ostream &os,
const CoplanarCluster &cl)
3064 for (
const int t : cl) {
3077 static std::ostream &
operator<<(std::ostream &os,
const CoplanarClusterInfo &clinfo)
3079 os <<
"Coplanar Cluster Info:\n";
3080 for (
int c : clinfo.index_range()) {
3081 os <<
c <<
": " << clinfo.cluster(
c) <<
"\n";
3086 static std::ostream &
operator<<(std::ostream &os,
const ITT_value &itt)
3093 os <<
"point " << itt.p1;
3096 os <<
"segment " << itt.p1 <<
" " << itt.p2;
3099 os <<
"co-planar t" << itt.t_source;
3105 void write_obj_mesh(IMesh &m,
const std::string &objname)
3113 const char *objdir =
"/tmp/";
3115 if (m.face_size() == 0) {
3119 std::string fname = std::string(objdir) + objname + std::string(
".obj");
3123 std::cout <<
"Could not open file " << fname <<
"\n";
3127 if (!m.has_verts()) {
3130 for (
const Vert *
v : m.vertices()) {
3132 f <<
"v " << dv[0] <<
" " << dv[1] <<
" " << dv[2] <<
"\n";
3135 for (
const Face *face : m.faces()) {
3138 for (
const Vert *
v : *face) {
3139 int i = m.lookup_vert(
v);
3153 Vector<const char *> count_name;
3155 Vector<const char *> max_name;
3158 static PerfCounts *perfdata =
nullptr;
3160 static void perfdata_init()
3162 perfdata =
new PerfCounts;
3165 perfdata->count.append(0);
3166 perfdata->count_name.append(
"Non-cluster overlaps");
3169 perfdata->count.append(0);
3170 perfdata->count_name.append(
"intersect_tri_tri calls");
3173 perfdata->count.append(0);
3174 perfdata->count_name.append(
"tri tri intersects decided by filter plane tests");
3177 perfdata->count.append(0);
3178 perfdata->count_name.append(
"tri tri intersects decided by exact plane tests");
3181 perfdata->count.append(0);
3182 perfdata->count_name.append(
"final non-NONE intersects");
3185 perfdata->max.append(0);
3186 perfdata->max_name.append(
"total faces");
3189 perfdata->max.append(0);
3190 perfdata->max_name.append(
"total clusters");
3193 perfdata->max.append(0);
3194 perfdata->max_name.append(
"total overlaps");
3197 static void incperfcount(
int countnum)
3199 perfdata->count[countnum]++;
3202 static void bumpperfcount(
int countnum,
int amt)
3204 perfdata->count[countnum] += amt;
3207 static void doperfmax(
int maxnum,
int val)
3209 perfdata->max[maxnum] =
max_ii(perfdata->max[maxnum], val);
3212 static void dump_perfdata()
3214 std::cout <<
"\nPERFDATA\n";
3215 for (
int i : perfdata->count.index_range()) {
3216 std::cout << perfdata->count_name[i] <<
" = " << perfdata->count[i] <<
"\n";
3218 for (
int i : perfdata->max.index_range()) {
3219 std::cout << perfdata->max_name[i] <<
" = " << perfdata->max[i] <<
"\n";
typedef float(TangentPoint)[2]
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
void BLI_bvhtree_balance(BVHTree *tree)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
void BLI_bvhtree_free(BVHTree *tree)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
MINLINE int max_ii(int a, int b)
MINLINE double max_dd(double a, double b)
Math vector functions needed specifically for mesh intersect and boolean.
bool isect_aabb_aabb_v3(const float min1[3], const float max1[3], const float min2[3], const float max2[3])
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
MINLINE float normalize_v3(float r[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
const char * BLI_getenv(const char *env) ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
pthread_spinlock_t SpinLock
void BLI_mutex_free(ThreadMutex *mutex)
ThreadMutex * BLI_mutex_alloc(void)
void BLI_mutex_lock(ThreadMutex *mutex)
void BLI_mutex_unlock(ThreadMutex *mutex)
void BLI_spin_init(SpinLock *spin)
void BLI_spin_unlock(SpinLock *spin)
void BLI_spin_lock(SpinLock *spin)
pthread_mutex_t ThreadMutex
void BLI_spin_end(SpinLock *spin)
#define UNUSED_VARS_NDEBUG(...)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble z
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
#define MEM_reallocN(vmemh, len)
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object for example to give variation to multiple instances of an object Point Retrieve information about points in a point cloud Retrieve the edges of an object as it appears to Cycles topology will always appear triangulated Convert a blackbody temperature to an RGB value Normal Map
Platform independent time functions.
int pad[32 - sizeof(int)]
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
blender::meshintersect::CDT_result< double > delaunay_2d_calc(const CDT_input< double > &input, CDT_output_type output_type)
IconTextureDrawCall normal
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
void(* MEM_freeN)(void *vmemh)
ccl_device_inline float2 fabs(const float2 &a)
GAttributeReader lookup(const void *owner, const AttributeIDRef &attribute_id)
std::ostream & operator<<(std::ostream &stream, const AssetCatalogPath &path_to_append)
bool operator==(const AttributeIDRef &a, const AttributeIDRef &b)
T dot(const vec_base< T, Size > &a, const vec_base< T, Size > &b)
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
vec_base< T, 3 > cross_poly(Span< vec_base< T, 3 >> poly)
T length_squared(const vec_base< T, Size > &a)
int dominant_axis(const vec_base< T, 3 > &a)
static meshintersect::CDT_result< double > do_cdt(const bke::CurvesGeometry &curves, const CDT_output_type output_type)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
vec_base< double, 3 > double3
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
unsigned __int64 uint64_t
TaskParallelReduceFunc func_reduce
size_t userdata_chunk_size
double PIL_check_seconds_timer(void)