Blender V5.3
mesh_intersect.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9/* The #meshintersect API needs GMP. */
10#ifdef WITH_GMP
11
12# include <algorithm>
13# include <fstream>
14# include <functional>
15# include <iostream>
16# include <memory>
17# include <numeric>
18
19# include "BLI_array.hh"
20# include "BLI_assert.hh"
21# include "BLI_delaunay_2d.hh"
22# include "BLI_kdopbvh.hh"
23# include "BLI_map.hh"
24# include "BLI_math_geom_c.hh"
25# include "BLI_math_matrix_c.hh"
26# include "BLI_math_mpq.hh"
27# include "BLI_math_vector_c.hh"
30# include "BLI_mutex.hh"
31# include "BLI_ordered_edge.hh"
32# include "BLI_polyfill_2d.hh"
33# include "BLI_set.hh"
34# include "BLI_sort.hh"
35# include "BLI_span.hh"
36# include "BLI_task.hh"
37# include "BLI_task_c.hh"
38# include "BLI_threads.hh"
39# include "BLI_vector.hh"
40# include "BLI_vector_set.hh"
41
42# include "BLI_mesh_intersect.hh"
43
44// # define PERFDEBUG
45
46# ifdef _WIN_32
47# include "BLI_fileops.hh"
48# endif
49
50namespace blender::meshintersect {
51
52# ifdef PERFDEBUG
53static void perfdata_init();
54static void incperfcount(int countnum);
55static void bumpperfcount(int countnum, int amt);
56static void doperfmax(int maxnum, int val);
57static void dump_perfdata();
58# endif
59
61static constexpr bool intersect_use_threading = true;
62
63Vert::Vert(const mpq3 &mco, const double3 &dco, int id, int orig)
64 : co_exact(mco), co(dco), id(id), orig(orig)
65{
66}
67
68bool Vert::operator==(const Vert &other) const
69{
70 return this->co_exact == other.co_exact;
71}
72
73uint64_t Vert::hash() const
74{
75 uint64_t x = *reinterpret_cast<const uint64_t *>(&co.x);
76 uint64_t y = *reinterpret_cast<const uint64_t *>(&co.y);
77 uint64_t z = *reinterpret_cast<const uint64_t *>(&co.z);
78 x = (x >> 56) ^ (x >> 46) ^ x;
79 y = (y >> 55) ^ (y >> 45) ^ y;
80 z = (z >> 54) ^ (z >> 44) ^ z;
81 return x ^ y ^ z;
82}
83
84std::ostream &operator<<(std::ostream &os, const Vert *v)
85{
86 constexpr int dbg_level = 0;
87 os << "v" << v->id;
88 if (v->orig != NO_INDEX) {
89 os << "o" << v->orig;
90 }
91 os << v->co;
92 if (dbg_level > 0) {
93 os << "=" << v->co_exact;
94 }
95 return os;
96}
97
98bool Plane::operator==(const Plane &other) const
99{
100 return norm_exact == other.norm_exact && d_exact == other.d_exact;
101}
102
103void Plane::make_canonical()
104{
105 if (norm_exact[0] != 0) {
106 mpq_class den = norm_exact[0];
107 norm_exact = mpq3(1, norm_exact[1] / den, norm_exact[2] / den);
108 d_exact = d_exact / den;
109 }
110 else if (norm_exact[1] != 0) {
111 mpq_class den = norm_exact[1];
112 norm_exact = mpq3(0, 1, norm_exact[2] / den);
113 d_exact = d_exact / den;
114 }
115 else {
116 if (norm_exact[2] != 0) {
117 mpq_class den = norm_exact[2];
118 norm_exact = mpq3(0, 0, 1);
119 d_exact = d_exact / den;
120 }
121 else {
122 /* A degenerate plane. */
123 d_exact = 0;
124 }
125 }
126 norm = double3(norm_exact[0].get_d(), norm_exact[1].get_d(), norm_exact[2].get_d());
127 d = d_exact.get_d();
128}
129
130Plane::Plane(const mpq3 &norm_exact, const mpq_class &d_exact)
131 : norm_exact(norm_exact), d_exact(d_exact)
132{
133 norm = double3(norm_exact[0].get_d(), norm_exact[1].get_d(), norm_exact[2].get_d());
134 d = d_exact.get_d();
135}
136
137Plane::Plane(const double3 &norm, const double d) : norm(norm), d(d)
138{
139 norm_exact = mpq3(0, 0, 0); /* Marks as "exact not yet populated". */
140}
141
142bool Plane::exact_populated() const
143{
144 return norm_exact[0] != 0 || norm_exact[1] != 0 || norm_exact[2] != 0;
145}
146
147uint64_t Plane::hash() const
148{
149 uint64_t x = *reinterpret_cast<const uint64_t *>(&this->norm.x);
150 uint64_t y = *reinterpret_cast<const uint64_t *>(&this->norm.y);
151 uint64_t z = *reinterpret_cast<const uint64_t *>(&this->norm.z);
152 uint64_t d = *reinterpret_cast<const uint64_t *>(&this->d);
153 x = (x >> 56) ^ (x >> 46) ^ x;
154 y = (y >> 55) ^ (y >> 45) ^ y;
155 z = (z >> 54) ^ (z >> 44) ^ z;
156 d = (d >> 53) ^ (d >> 43) ^ d;
157 return x ^ y ^ z ^ d;
158}
159
160std::ostream &operator<<(std::ostream &os, const Plane *plane)
161{
162 os << "[" << plane->norm << ";" << plane->d << "]";
163 return os;
164}
165
166Face::Face(
167 Span<const Vert *> verts, int id, int orig, Span<int> edge_origs, Span<bool> is_intersect)
168 : vert(verts), edge_orig(edge_origs), is_intersect(is_intersect), id(id), orig(orig)
169{
170}
171
172Face::Face(Span<const Vert *> verts, int id, int orig) : vert(verts), id(id), orig(orig) {}
173
174void Face::populate_plane(bool need_exact)
175{
176 if (plane != nullptr) {
177 if (!need_exact || plane->exact_populated()) {
178 return;
179 }
180 }
181 if (need_exact) {
182 mpq3 normal_exact;
183 if (vert.size() > 3) {
184 Array<mpq3> co(vert.size());
185 for (int i : index_range()) {
186 co[i] = vert[i]->co_exact;
187 }
188 normal_exact = math::cross_poly(co.as_span());
189 }
190 else {
191 mpq3 tr02 = vert[0]->co_exact - vert[2]->co_exact;
192 mpq3 tr12 = vert[1]->co_exact - vert[2]->co_exact;
193 normal_exact = math::cross(tr02, tr12);
194 }
195 mpq_class d_exact = -math::dot(normal_exact, vert[0]->co_exact);
196 plane = new Plane(normal_exact, d_exact);
197 }
198 else {
199 double3 normal;
200 if (vert.size() > 3) {
201 Array<double3> co(vert.size());
202 for (int i : index_range()) {
203 co[i] = vert[i]->co;
204 }
205 normal = math::cross_poly(co.as_span());
206 }
207 else {
208 double3 tr02 = vert[0]->co - vert[2]->co;
209 double3 tr12 = vert[1]->co - vert[2]->co;
210 normal = math::cross(tr02, tr12);
211 }
212 double d = -math::dot(normal, vert[0]->co);
213 plane = new Plane(normal, d);
214 }
215}
216
217Face::~Face()
218{
219 delete plane;
220}
221
222bool Face::operator==(const Face &other) const
223{
224 if (this->size() != other.size()) {
225 return false;
226 }
227 for (FacePos i : index_range()) {
228 /* Can test pointer equality since we will have
229 * unique vert pointers for unique co_equal's. */
230 if (this->vert[i] != other.vert[i]) {
231 return false;
232 }
233 }
234 return true;
235}
236
237bool Face::cyclic_equal(const Face &other) const
238{
239 if (this->size() != other.size()) {
240 return false;
241 }
242 int flen = this->size();
243 for (FacePos start : index_range()) {
244 for (FacePos start_other : index_range()) {
245 bool ok = true;
246 for (int i = 0; ok && i < flen; ++i) {
247 FacePos p = (start + i) % flen;
248 FacePos p_other = (start_other + i) % flen;
249 if (this->vert[p] != other.vert[p_other]) {
250 ok = false;
251 }
252 }
253 if (ok) {
254 return true;
255 }
256 }
257 }
258 return false;
259}
260
261std::ostream &operator<<(std::ostream &os, const Face *f)
262{
263 os << "f" << f->id << "o" << f->orig << "[";
264 for (const Vert *v : *f) {
265 os << v;
266 if (v != f->vert[f->size() - 1]) {
267 os << " ";
268 }
269 }
270 os << "]";
271 if (f->orig != NO_INDEX) {
272 os << "o" << f->orig;
273 }
274 os << " e_orig[";
275 for (int i : f->index_range()) {
276 os << f->edge_orig[i];
277 if (f->is_intersect[i]) {
278 os << "#";
279 }
280 if (i != f->size() - 1) {
281 os << " ";
282 }
283 }
284 os << "]";
285 return os;
286}
287
295class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
296
302 struct VSetKey {
303 Vert *vert;
304
305 VSetKey(Vert *p) : vert(p) {}
306
307 uint64_t hash() const
308 {
309 return vert->hash();
310 }
311
312 bool operator==(const VSetKey &other) const
313 {
314 return *this->vert == *other.vert;
315 }
316 };
317
318 Set<VSetKey> vset_;
319
325 Vector<std::unique_ptr<Vert>> allocated_verts_;
326 Vector<std::unique_ptr<Face>> allocated_faces_;
327
328 /* Use these to allocate ids when Verts and Faces are allocated. */
329 int next_vert_id_ = 0;
330 int next_face_id_ = 0;
331
332 /* Need a lock when multi-threading to protect allocation of new elements. */
333 Mutex mutex_;
334
335 public:
336 void reserve(int vert_num_hint, int face_num_hint)
337 {
338 vset_.reserve(vert_num_hint);
339 allocated_verts_.reserve(vert_num_hint);
340 allocated_faces_.reserve(face_num_hint);
341 }
342
343 int tot_allocated_verts() const
344 {
345 return allocated_verts_.size();
346 }
347
348 int tot_allocated_faces() const
349 {
350 return allocated_faces_.size();
351 }
352
353 const Vert *add_or_find_vert(const mpq3 &co, int orig)
354 {
355 double3 dco(co[0].get_d(), co[1].get_d(), co[2].get_d());
356 return add_or_find_vert(co, dco, orig);
357 }
358
359 const Vert *add_or_find_vert(const double3 &co, int orig)
360 {
361 mpq3 mco(co[0], co[1], co[2]);
362 return add_or_find_vert(mco, co, orig);
363 }
364
365 const Vert *add_or_find_vert(Vert *vert)
366 {
367 return add_or_find_vert_(vert);
368 }
369
370 Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs, Span<bool> is_intersect)
371 {
372 Face *f = new Face(verts, next_face_id_++, orig, edge_origs, is_intersect);
373 std::lock_guard lock(mutex_);
374 allocated_faces_.append(std::unique_ptr<Face>(f));
375 return f;
376 }
377
378 Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs)
379 {
380 Array<bool> is_intersect(verts.size(), false);
381 return add_face(verts, orig, edge_origs, is_intersect);
382 }
383
384 Face *add_face(Span<const Vert *> verts, int orig)
385 {
386 Array<int> edge_origs(verts.size(), NO_INDEX);
387 Array<bool> is_intersect(verts.size(), false);
388 return add_face(verts, orig, edge_origs, is_intersect);
389 }
390
391 const Vert *find_vert(const mpq3 &co)
392 {
393 Vert vtry(co, double3(co[0].get_d(), co[1].get_d(), co[2].get_d()), NO_INDEX, NO_INDEX);
394 VSetKey vskey(&vtry);
395 std::lock_guard lock(mutex_);
396 const VSetKey *lookup = vset_.lookup_key_ptr(vskey);
397 if (!lookup) {
398 return nullptr;
399 }
400 return lookup->vert;
401 }
402
408 const Face *find_face(Span<const Vert *> vs)
409 {
410 Array<int> eorig(vs.size(), NO_INDEX);
411 Array<bool> is_intersect(vs.size(), false);
412 Face ftry(vs, NO_INDEX, NO_INDEX, eorig, is_intersect);
413 for (const int i : allocated_faces_.index_range()) {
414 if (ftry.cyclic_equal(*allocated_faces_[i])) {
415 return allocated_faces_[i].get();
416 }
417 }
418 return nullptr;
419 }
420
421 private:
422 const Vert *add_or_find_vert(const mpq3 &mco, const double3 &dco, int orig)
423 {
424 Vert *vtry = new Vert(mco, dco, NO_INDEX, NO_INDEX);
425 const Vert *ans;
426 VSetKey vskey(vtry);
427 std::lock_guard lock(mutex_);
428 const VSetKey *lookup = vset_.lookup_key_ptr(vskey);
429 if (!lookup) {
430 vtry->id = next_vert_id_++;
431 vtry->orig = orig;
432 vskey.vert = vtry; // new Vert(mco, dco, next_vert_id_++, orig);
433 vset_.add_new(vskey);
434 allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
435 ans = vskey.vert;
436 }
437 else {
438 /* It was a duplicate, so return the existing one.
439 * Note that the returned Vert may have a different orig.
440 * This is the intended semantics: if the Vert already
441 * exists then we are merging verts and using the first-seen
442 * one as the canonical one. */
443 delete vtry;
444 ans = lookup->vert;
445 }
446 return ans;
447 };
448
449 const Vert *add_or_find_vert_(Vert *vtry)
450 {
451 const Vert *ans;
452 VSetKey vskey(vtry);
453 std::lock_guard lock(mutex_);
454 const VSetKey *lookup = vset_.lookup_key_ptr(vskey);
455 if (!lookup) {
456 vtry->id = next_vert_id_++;
457 vskey.vert = vtry; // new Vert(mco, dco, next_vert_id_++, orig);
458 vset_.add_new(vskey);
459 allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
460 ans = vskey.vert;
461 }
462 else {
463 /* It was a duplicate, so return the existing one.
464 * Note that the returned Vert may have a different orig.
465 * This is the intended semantics: if the Vert already
466 * exists then we are merging verts and using the first-seen
467 * one as the canonical one. */
468 delete vtry;
469 ans = lookup->vert;
470 }
471 return ans;
472 };
473};
474
475IMeshArena::IMeshArena()
476{
477 pimpl_ = std::make_unique<IMeshArenaImpl>();
478}
479
480IMeshArena::~IMeshArena() = default;
481
482void IMeshArena::reserve(int vert_num_hint, int face_num_hint)
483{
484 pimpl_->reserve(vert_num_hint, face_num_hint);
485}
486
487int IMeshArena::tot_allocated_verts() const
488{
489 return pimpl_->tot_allocated_verts();
490}
491
492int IMeshArena::tot_allocated_faces() const
493{
494 return pimpl_->tot_allocated_faces();
495}
496
497const Vert *IMeshArena::add_or_find_vert(const mpq3 &co, int orig)
498{
499 return pimpl_->add_or_find_vert(co, orig);
500}
501
502const Vert *IMeshArena::add_or_find_vert(Vert *vert)
503{
504 return pimpl_->add_or_find_vert(vert);
505}
506
507Face *IMeshArena::add_face(Span<const Vert *> verts,
508 int orig,
509 Span<int> edge_origs,
510 Span<bool> is_intersect)
511{
512 return pimpl_->add_face(verts, orig, edge_origs, is_intersect);
513}
514
515Face *IMeshArena::add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs)
516{
517 return pimpl_->add_face(verts, orig, edge_origs);
518}
519
520Face *IMeshArena::add_face(Span<const Vert *> verts, int orig)
521{
522 return pimpl_->add_face(verts, orig);
523}
524
525const Vert *IMeshArena::add_or_find_vert(const double3 &co, int orig)
526{
527 return pimpl_->add_or_find_vert(co, orig);
528}
529
530const Vert *IMeshArena::find_vert(const mpq3 &co) const
531{
532 return pimpl_->find_vert(co);
533}
534
535const Face *IMeshArena::find_face(Span<const Vert *> verts) const
536{
537 return pimpl_->find_face(verts);
538}
539
540void IMesh::set_faces(Span<Face *> faces)
541{
542 face_ = faces;
543}
544
545void IMesh::populate_vert()
546{
547 /* This is likely an overestimate, since verts are shared between
548 * faces. It is ok if estimate is over or even under. */
549 constexpr int ESTIMATE_VERTS_PER_FACE = 4;
550 int estimate_verts_num = ESTIMATE_VERTS_PER_FACE * face_.size();
551 populate_vert(estimate_verts_num);
552}
553
554void IMesh::populate_vert(int max_verts)
555{
556 if (vert_populated_) {
557 return;
558 }
559 vert_to_index_.reserve(max_verts);
560 int next_allocate_index = 0;
561 for (const Face *f : face_) {
562 for (const Vert *v : *f) {
563 if (v->id == 1) {
564 }
565 int index = vert_to_index_.lookup_default(v, NO_INDEX);
566 if (index == NO_INDEX) {
567 BLI_assert(next_allocate_index < UINT_MAX - 2);
568 vert_to_index_.add(v, next_allocate_index++);
569 }
570 }
571 }
572 int tot_v = next_allocate_index;
573 vert_ = Array<const Vert *>(tot_v);
574 for (auto item : vert_to_index_.items()) {
575 int index = item.value;
576 BLI_assert(index < tot_v);
577 vert_[index] = item.key;
578 }
579 /* Easier debugging (at least when there are no merged input verts)
580 * if output vert order is same as input, with new verts at the end.
581 * TODO: when all debugged, set fix_order = false. */
582 const bool fix_order = true;
583 if (fix_order) {
584 parallel_sort(vert_.begin(), vert_.end(), [](const Vert *a, const Vert *b) {
585 if (a->orig != NO_INDEX && b->orig != NO_INDEX) {
586 return a->orig < b->orig;
587 }
588 if (a->orig != NO_INDEX) {
589 return true;
590 }
591 if (b->orig != NO_INDEX) {
592 return false;
593 }
594 return a->id < b->id;
595 });
596 for (int i : vert_.index_range()) {
597 const Vert *v = vert_[i];
598 vert_to_index_.add_overwrite(v, i);
599 }
600 }
601 vert_populated_ = true;
602}
603
604bool IMesh::erase_face_positions(int f_index, Span<bool> face_pos_erase, IMeshArena *arena)
605{
606 const Face *cur_f = this->face(f_index);
607 int cur_len = cur_f->size();
608 int to_erase_num = 0;
609 for (int i : cur_f->index_range()) {
610 if (face_pos_erase[i]) {
611 ++to_erase_num;
612 }
613 }
614 if (to_erase_num == 0) {
615 return false;
616 }
617 int new_len = cur_len - to_erase_num;
618 if (new_len < 3) {
619 /* This erase causes removal of whole face.
620 * Because this may be called from a loop over the face array,
621 * we don't want to compress that array right here; instead will
622 * mark with null pointer and caller should call remove_null_faces().
623 * the loop is done.
624 */
625 this->face_[f_index] = nullptr;
626 return true;
627 }
628 Array<const Vert *> new_vert(new_len);
629 Array<int> new_edge_orig(new_len);
630 Array<bool> new_is_intersect(new_len);
631 int new_index = 0;
632 for (int i : cur_f->index_range()) {
633 if (!face_pos_erase[i]) {
634 new_vert[new_index] = (*cur_f)[i];
635 new_edge_orig[new_index] = cur_f->edge_orig[i];
636 new_is_intersect[new_index] = cur_f->is_intersect[i];
637 ++new_index;
638 }
639 }
640 BLI_assert(new_index == new_len);
641 this->face_[f_index] = arena->add_face(new_vert, cur_f->orig, new_edge_orig, new_is_intersect);
642 return false;
643}
644
645void IMesh::remove_null_faces()
646{
647 int64_t nullcount = 0;
648 for (Face *f : this->face_) {
649 if (f == nullptr) {
650 ++nullcount;
651 }
652 }
653 if (nullcount == 0) {
654 return;
655 }
656 int64_t new_size = this->face_.size() - nullcount;
657 int64_t copy_to_index = 0;
658 int64_t copy_from_index = 0;
659 Array<Face *> new_face(new_size);
660 while (copy_from_index < face_.size()) {
661 Face *f_from = face_[copy_from_index++];
662 if (f_from) {
663 new_face[copy_to_index++] = f_from;
664 }
665 }
666 this->face_ = new_face;
667}
668
669std::ostream &operator<<(std::ostream &os, const IMesh &mesh)
670{
671 if (mesh.has_verts()) {
672 os << "Verts:\n";
673 int i = 0;
674 for (const Vert *v : mesh.vertices()) {
675 os << i << ": " << v << "\n";
676 ++i;
677 }
678 }
679 os << "\nFaces:\n";
680 int i = 0;
681 for (const Face *f : mesh.faces()) {
682 os << i << ": " << f << "\n";
683 if (f->plane != nullptr) {
684 os << " plane=" << f->plane << " eorig=[";
685 for (Face::FacePos p = 0; p < f->size(); ++p) {
686 os << f->edge_orig[p] << " ";
687 }
688 os << "]\n";
689 }
690 ++i;
691 }
692 return os;
693}
694
695bool bbs_might_intersect(const BoundingBox &bb_a, const BoundingBox &bb_b)
696{
697 return isect_aabb_aabb_v3(bb_a.min, bb_a.max, bb_b.min, bb_b.max);
698}
699
706struct BBChunkData {
707 double max_abs_val = 0.0;
708};
709
710struct BBCalcData {
711 const IMesh &im;
712 Array<BoundingBox> *face_bounding_box;
713
714 BBCalcData(const IMesh &im, Array<BoundingBox> *fbb) : im(im), face_bounding_box(fbb) {};
715};
716
717static void calc_face_bb_range_func(void *__restrict userdata,
718 const int iter,
719 const TaskParallelTLS *__restrict tls)
720{
721 BBCalcData *bbdata = static_cast<BBCalcData *>(userdata);
722 double max_abs = 0.0;
723 const Face &face = *bbdata->im.face(iter);
724 BoundingBox &bb = (*bbdata->face_bounding_box)[iter];
725 for (const Vert *v : face) {
726 bb.combine(v->co);
727 for (int i = 0; i < 3; ++i) {
728 max_abs = max_dd(max_abs, fabs(v->co[i]));
729 }
730 }
731 BBChunkData *chunk = static_cast<BBChunkData *>(tls->userdata_chunk);
732 chunk->max_abs_val = max_dd(max_abs, chunk->max_abs_val);
733}
734
735struct BBPadData {
736 Array<BoundingBox> *face_bounding_box;
737 double pad;
738
739 BBPadData(Array<BoundingBox> *fbb, double pad) : face_bounding_box(fbb), pad(pad) {};
740};
741
742static void pad_face_bb_range_func(void *__restrict userdata,
743 const int iter,
744 const TaskParallelTLS *__restrict /*tls*/)
745{
746 BBPadData *pad_data = static_cast<BBPadData *>(userdata);
747 (*pad_data->face_bounding_box)[iter].expand(pad_data->pad);
748}
749
750static void calc_face_bb_reduce(const void *__restrict /*userdata*/,
751 void *__restrict chunk_join,
752 void *__restrict chunk)
753{
754 BBChunkData *bbchunk_join = static_cast<BBChunkData *>(chunk_join);
755 BBChunkData *bbchunk = static_cast<BBChunkData *>(chunk);
756 bbchunk_join->max_abs_val = max_dd(bbchunk_join->max_abs_val, bbchunk->max_abs_val);
757}
758
764static Array<BoundingBox> calc_face_bounding_boxes(const IMesh &m)
765{
766 int n = m.face_size();
767 Array<BoundingBox> ans(n);
768 TaskParallelSettings settings;
769 BBCalcData data(m, &ans);
770 BBChunkData chunk_data;
772 settings.userdata_chunk = &chunk_data;
773 settings.userdata_chunk_size = sizeof(chunk_data);
774 settings.func_reduce = calc_face_bb_reduce;
775 settings.min_iter_per_thread = 1000;
776 settings.use_threading = intersect_use_threading;
777 BLI_task_parallel_range(0, n, &data, calc_face_bb_range_func, &settings);
778 double max_abs_val = chunk_data.max_abs_val;
779 constexpr float pad_factor = 10.0f;
780 float pad = max_abs_val == 0.0f ? FLT_EPSILON : 2 * FLT_EPSILON * max_abs_val;
781 pad *= pad_factor; /* For extra safety. */
782 TaskParallelSettings pad_settings;
784 settings.min_iter_per_thread = 1000;
785 settings.use_threading = intersect_use_threading;
786 BBPadData pad_data(&ans, pad);
787 BLI_task_parallel_range(0, n, &pad_data, pad_face_bb_range_func, &pad_settings);
788 return ans;
789}
790
800class CoplanarCluster {
801 Vector<int> tris_;
802 BoundingBox bb_;
803
804 public:
805 CoplanarCluster() = default;
806 CoplanarCluster(int t, const BoundingBox &bb)
807 {
808 this->add_tri(t, bb);
809 }
810
811 /* Assume that caller knows this will not be a duplicate. */
812 void add_tri(int t, const BoundingBox &bb)
813 {
814 tris_.append(t);
815 bb_.combine(bb);
816 }
817 int tot_tri() const
818 {
819 return tris_.size();
820 }
821 int tri(int index) const
822 {
823 return tris_[index];
824 }
825 const int *begin() const
826 {
827 return tris_.begin();
828 }
829 const int *end() const
830 {
831 return tris_.end();
832 }
833
834 const BoundingBox &bounding_box() const
835 {
836 return bb_;
837 }
838};
839
846class CoplanarClusterInfo {
847 Vector<CoplanarCluster> clusters_;
848 Array<int> tri_cluster_;
849
850 public:
851 CoplanarClusterInfo() = default;
852 explicit CoplanarClusterInfo(int numtri) : tri_cluster_(Array<int>(numtri))
853 {
854 tri_cluster_.fill(-1);
855 }
856
857 int tri_cluster(int t) const
858 {
859 BLI_assert(t < tri_cluster_.size());
860 return tri_cluster_[t];
861 }
862
863 int add_cluster(const CoplanarCluster &cl)
864 {
865 int c_index = clusters_.append_and_get_index(cl);
866 for (int t : cl) {
867 BLI_assert(t < tri_cluster_.size());
868 tri_cluster_[t] = c_index;
869 }
870 return c_index;
871 }
872
873 int tot_cluster() const
874 {
875 return clusters_.size();
876 }
877
878 const CoplanarCluster *begin()
879 {
880 return clusters_.begin();
881 }
882
883 const CoplanarCluster *end()
884 {
885 return clusters_.end();
886 }
887
888 IndexRange index_range() const
889 {
890 return clusters_.index_range();
891 }
892
893 const CoplanarCluster &cluster(int index) const
894 {
895 BLI_assert(index < clusters_.size());
896 return clusters_[index];
897 }
898};
899
900static std::ostream &operator<<(std::ostream &os, const CoplanarCluster &cl);
901
902static std::ostream &operator<<(std::ostream &os, const CoplanarClusterInfo &clinfo);
903
904enum ITT_value_kind { INONE, IPOINT, ISEGMENT, ICOPLANAR };
905
906struct ITT_value {
907 mpq3 p1; /* Only relevant for IPOINT and ISEGMENT kind. */
908 mpq3 p2; /* Only relevant for ISEGMENT kind. */
909 int t_source = -1; /* Index of the source triangle that intersected the target one. */
910 enum ITT_value_kind kind = INONE;
911
912 ITT_value() = default;
913 explicit ITT_value(ITT_value_kind k) : kind(k) {}
914 ITT_value(ITT_value_kind k, int tsrc) : t_source(tsrc), kind(k) {}
915 ITT_value(ITT_value_kind k, const mpq3 &p1) : p1(p1), kind(k) {}
916 ITT_value(ITT_value_kind k, const mpq3 &p1, const mpq3 &p2) : p1(p1), p2(p2), kind(k) {}
917};
918
919static std::ostream &operator<<(std::ostream &os, const ITT_value &itt);
920
926static mpq2 project_3d_to_2d(const mpq3 &p3d, int proj_axis)
927{
928 mpq2 p2d;
929 switch (proj_axis) {
930 case (0): {
931 p2d[0] = p3d[1];
932 p2d[1] = p3d[2];
933 break;
934 }
935 case (1): {
936 p2d[0] = p3d[0];
937 p2d[1] = p3d[2];
938 break;
939 }
940 case (2): {
941 p2d[0] = p3d[0];
942 p2d[1] = p3d[1];
943 break;
944 }
945 default:
946 BLI_assert(false);
947 }
948 return p2d;
949}
950
981static double supremum_dot_cross(const double3 &a, const double3 &b)
982{
983 double3 abs_a = math::abs(a);
984 double3 abs_b = math::abs(b);
985 double3 c;
986 /* This is dot(cross(a, b), cross(a,b)) but using absolute values for a and b
987 * and always using + when operation is + or -. */
988 c[0] = abs_a[1] * abs_b[2] + abs_a[2] * abs_b[1];
989 c[1] = abs_a[2] * abs_b[0] + abs_a[0] * abs_b[2];
990 c[2] = abs_a[0] * abs_b[1] + abs_a[1] * abs_b[0];
991 return math::dot(c, c);
992}
993
994/* The index of dot when inputs are plane_coords with index 1 is much higher.
995 * Plane coords have index 6.
996 */
997constexpr int index_dot_plane_coords = 15;
998
1009constexpr int index_dot_cross = 11;
1010
1019constexpr int index_plane_side = 3 + 2 * index_dot_plane_coords;
1020
1021static int filter_plane_side(const double3 &p,
1022 const double3 &plane_p,
1023 const double3 &plane_no,
1024 const double3 &abs_p,
1025 const double3 &abs_plane_p,
1026 const double3 &abs_plane_no)
1027{
1028 double d = math::dot(p - plane_p, plane_no);
1029 if (d == 0.0) {
1030 return 0;
1031 }
1032 double supremum = math::dot(abs_p + abs_plane_p, abs_plane_no);
1033 double err_bound = supremum * index_plane_side * DBL_EPSILON;
1034 if (fabs(d) > err_bound) {
1035 return d > 0 ? 1 : -1;
1036 }
1037 return 0;
1038}
1039
1040/*
1041 * #intersect_tri_tri and helper functions.
1042 * This code uses the algorithm of Guigue and Devillers, as described
1043 * in "Faster Triangle-Triangle Intersection Tests".
1044 * Adapted from code by Eric Haines:
1045 * https://github.com/erich666/jgt-code/tree/master/Volume_08/Number_1/Guigue2003
1046 */
1047
1056static inline mpq3 tti_interp(
1057 const mpq3 &a, const mpq3 &b, const mpq3 &c, const mpq3 &n, mpq3 &ab, mpq3 &ac, mpq3 &dotbuf)
1058{
1059 ab = a;
1060 ab -= b;
1061 ac = a;
1062 ac -= c;
1063 mpq_class den = math::dot_with_buffer(ab, n, dotbuf);
1064 BLI_assert(den != 0);
1065 mpq_class alpha = math::dot_with_buffer(ac, n, dotbuf) / den;
1066 return a - alpha * ab;
1067}
1068
1076static inline int tti_above(const mpq3 &a,
1077 const mpq3 &b,
1078 const mpq3 &c,
1079 const mpq3 &ad,
1080 mpq3 &ba,
1081 mpq3 &ca,
1082 mpq3 &n,
1083 mpq3 &dotbuf)
1084{
1085 ba = b;
1086 ba -= a;
1087 ca = c;
1088 ca -= a;
1089
1090 n.x = ba.y * ca.z - ba.z * ca.y;
1091 n.y = ba.z * ca.x - ba.x * ca.z;
1092 n.z = ba.x * ca.y - ba.y * ca.x;
1093
1094 return sgn(math::dot_with_buffer(ad, n, dotbuf));
1095}
1096
1110static ITT_value itt_canon2(const mpq3 &p1,
1111 const mpq3 &q1,
1112 const mpq3 &r1,
1113 const mpq3 &p2,
1114 const mpq3 &q2,
1115 const mpq3 &r2,
1116 const mpq3 &n1,
1117 const mpq3 &n2)
1118{
1119 constexpr int dbg_level = 0;
1120 if (dbg_level > 0) {
1121 std::cout << "\ntri_tri_intersect_canon:\n";
1122 std::cout << "p1=" << p1 << " q1=" << q1 << " r1=" << r1 << "\n";
1123 std::cout << "p2=" << p2 << " q2=" << q2 << " r2=" << r2 << "\n";
1124 std::cout << "n1=" << n1 << " n2=" << n2 << "\n";
1125 std::cout << "approximate values:\n";
1126 std::cout << "p1=(" << p1[0].get_d() << "," << p1[1].get_d() << "," << p1[2].get_d() << ")\n";
1127 std::cout << "q1=(" << q1[0].get_d() << "," << q1[1].get_d() << "," << q1[2].get_d() << ")\n";
1128 std::cout << "r1=(" << r1[0].get_d() << "," << r1[1].get_d() << "," << r1[2].get_d() << ")\n";
1129 std::cout << "p2=(" << p2[0].get_d() << "," << p2[1].get_d() << "," << p2[2].get_d() << ")\n";
1130 std::cout << "q2=(" << q2[0].get_d() << "," << q2[1].get_d() << "," << q2[2].get_d() << ")\n";
1131 std::cout << "r2=(" << r2[0].get_d() << "," << r2[1].get_d() << "," << r2[2].get_d() << ")\n";
1132 std::cout << "n1=(" << n1[0].get_d() << "," << n1[1].get_d() << "," << n1[2].get_d() << ")\n";
1133 std::cout << "n2=(" << n2[0].get_d() << "," << n2[1].get_d() << "," << n2[2].get_d() << ")\n";
1134 }
1135 mpq3 p1p2 = p2 - p1;
1136 mpq3 intersect_1;
1137 mpq3 intersect_2;
1138 mpq3 buf[4];
1139 bool no_overlap = false;
1140 /* Top test in classification tree. */
1141 if (tti_above(p1, q1, r2, p1p2, buf[0], buf[1], buf[2], buf[3]) > 0) {
1142 /* Middle right test in classification tree. */
1143 if (tti_above(p1, r1, r2, p1p2, buf[0], buf[1], buf[2], buf[3]) <= 0) {
1144 /* Bottom right test in classification tree. */
1145 if (tti_above(p1, r1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) > 0) {
1146 /* Overlap is [k [i l] j]. */
1147 if (dbg_level > 0) {
1148 std::cout << "overlap [k [i l] j]\n";
1149 }
1150 /* i is intersect with p1r1. l is intersect with p2r2. */
1151 intersect_1 = tti_interp(p1, r1, p2, n2, buf[0], buf[1], buf[2]);
1152 intersect_2 = tti_interp(p2, r2, p1, n1, buf[0], buf[1], buf[2]);
1153 }
1154 else {
1155 /* Overlap is [i [k l] j]. */
1156 if (dbg_level > 0) {
1157 std::cout << "overlap [i [k l] j]\n";
1158 }
1159 /* k is intersect with p2q2. l is intersect is p2r2. */
1160 intersect_1 = tti_interp(p2, q2, p1, n1, buf[0], buf[1], buf[2]);
1161 intersect_2 = tti_interp(p2, r2, p1, n1, buf[0], buf[1], buf[2]);
1162 }
1163 }
1164 else {
1165 /* No overlap: [k l] [i j]. */
1166 if (dbg_level > 0) {
1167 std::cout << "no overlap: [k l] [i j]\n";
1168 }
1169 no_overlap = true;
1170 }
1171 }
1172 else {
1173 /* Middle left test in classification tree. */
1174 if (tti_above(p1, q1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) < 0) {
1175 /* No overlap: [i j] [k l]. */
1176 if (dbg_level > 0) {
1177 std::cout << "no overlap: [i j] [k l]\n";
1178 }
1179 no_overlap = true;
1180 }
1181 else {
1182 /* Bottom left test in classification tree. */
1183 if (tti_above(p1, r1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) >= 0) {
1184 /* Overlap is [k [i j] l]. */
1185 if (dbg_level > 0) {
1186 std::cout << "overlap [k [i j] l]\n";
1187 }
1188 /* i is intersect with p1r1. j is intersect with p1q1. */
1189 intersect_1 = tti_interp(p1, r1, p2, n2, buf[0], buf[1], buf[2]);
1190 intersect_2 = tti_interp(p1, q1, p2, n2, buf[0], buf[1], buf[2]);
1191 }
1192 else {
1193 /* Overlap is [i [k j] l]. */
1194 if (dbg_level > 0) {
1195 std::cout << "overlap [i [k j] l]\n";
1196 }
1197 /* k is intersect with p2q2. j is intersect with p1q1. */
1198 intersect_1 = tti_interp(p2, q2, p1, n1, buf[0], buf[1], buf[2]);
1199 intersect_2 = tti_interp(p1, q1, p2, n2, buf[0], buf[1], buf[2]);
1200 }
1201 }
1202 }
1203 if (no_overlap) {
1204 return ITT_value(INONE);
1205 }
1206 if (intersect_1 == intersect_2) {
1207 if (dbg_level > 0) {
1208 std::cout << "single intersect: " << intersect_1 << "\n";
1209 }
1210 return ITT_value(IPOINT, intersect_1);
1211 }
1212 if (dbg_level > 0) {
1213 std::cout << "intersect segment: " << intersect_1 << ", " << intersect_2 << "\n";
1214 }
1215 return ITT_value(ISEGMENT, intersect_1, intersect_2);
1216}
1217
1218/* Helper function for intersect_tri_tri. Arguments have been canonicalized for triangle 1. */
1219
1220static ITT_value itt_canon1(const mpq3 &p1,
1221 const mpq3 &q1,
1222 const mpq3 &r1,
1223 const mpq3 &p2,
1224 const mpq3 &q2,
1225 const mpq3 &r2,
1226 const mpq3 &n1,
1227 const mpq3 &n2,
1228 int sp2,
1229 int sq2,
1230 int sr2)
1231{
1232 constexpr int dbg_level = 0;
1233 if (sp2 > 0) {
1234 if (sq2 > 0) {
1235 return itt_canon2(p1, r1, q1, r2, p2, q2, n1, n2);
1236 }
1237 if (sr2 > 0) {
1238 return itt_canon2(p1, r1, q1, q2, r2, p2, n1, n2);
1239 }
1240 return itt_canon2(p1, q1, r1, p2, q2, r2, n1, n2);
1241 }
1242 if (sp2 < 0) {
1243 if (sq2 < 0) {
1244 return itt_canon2(p1, q1, r1, r2, p2, q2, n1, n2);
1245 }
1246 if (sr2 < 0) {
1247 return itt_canon2(p1, q1, r1, q2, r2, p2, n1, n2);
1248 }
1249 return itt_canon2(p1, r1, q1, p2, q2, r2, n1, n2);
1250 }
1251 if (sq2 < 0) {
1252 if (sr2 >= 0) {
1253 return itt_canon2(p1, r1, q1, q2, r2, p2, n1, n2);
1254 }
1255 return itt_canon2(p1, q1, r1, p2, q2, r2, n1, n2);
1256 }
1257 if (sq2 > 0) {
1258 if (sr2 > 0) {
1259 return itt_canon2(p1, r1, q1, p2, q2, r2, n1, n2);
1260 }
1261 return itt_canon2(p1, q1, r1, q2, r2, p2, n1, n2);
1262 }
1263 if (sr2 > 0) {
1264 return itt_canon2(p1, q1, r1, r2, p2, q2, n1, n2);
1265 }
1266 if (sr2 < 0) {
1267 return itt_canon2(p1, r1, q1, r2, p2, q2, n1, n2);
1268 }
1269 if (dbg_level > 0) {
1270 std::cout << "triangles are co-planar\n";
1271 }
1272 return ITT_value(ICOPLANAR);
1273}
1274
1275static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
1276{
1277 constexpr int dbg_level = 0;
1278# ifdef PERFDEBUG
1279 incperfcount(1); /* Intersect_tri_tri calls. */
1280# endif
1281 const Face &tri1 = *tm.face(t1);
1282 const Face &tri2 = *tm.face(t2);
1283 BLI_assert(tri1.plane_populated() && tri2.plane_populated());
1284 const Vert *vp1 = tri1[0];
1285 const Vert *vq1 = tri1[1];
1286 const Vert *vr1 = tri1[2];
1287 const Vert *vp2 = tri2[0];
1288 const Vert *vq2 = tri2[1];
1289 const Vert *vr2 = tri2[2];
1290 if (dbg_level > 0) {
1291 std::cout << "\nINTERSECT_TRI_TRI t1=" << t1 << ", t2=" << t2 << "\n";
1292 std::cout << " p1 = " << vp1 << "\n";
1293 std::cout << " q1 = " << vq1 << "\n";
1294 std::cout << " r1 = " << vr1 << "\n";
1295 std::cout << " p2 = " << vp2 << "\n";
1296 std::cout << " q2 = " << vq2 << "\n";
1297 std::cout << " r2 = " << vr2 << "\n";
1298 }
1299
1300 /* Get signs of t1's vertices' distances to plane of t2 and vice versa. */
1301
1302 /* Try first getting signs with double arithmetic, with error bounds.
1303 * If the signs calculated in this section are not 0, they are the same
1304 * as what they would be using exact arithmetic. */
1305 const double3 &d_p1 = vp1->co;
1306 const double3 &d_q1 = vq1->co;
1307 const double3 &d_r1 = vr1->co;
1308 const double3 &d_p2 = vp2->co;
1309 const double3 &d_q2 = vq2->co;
1310 const double3 &d_r2 = vr2->co;
1311 const double3 &d_n2 = tri2.plane->norm;
1312
1313 const double3 &abs_d_p1 = math::abs(d_p1);
1314 const double3 &abs_d_q1 = math::abs(d_q1);
1315 const double3 &abs_d_r1 = math::abs(d_r1);
1316 const double3 &abs_d_r2 = math::abs(d_r2);
1317 const double3 &abs_d_n2 = math::abs(d_n2);
1318
1319 int sp1 = filter_plane_side(d_p1, d_r2, d_n2, abs_d_p1, abs_d_r2, abs_d_n2);
1320 int sq1 = filter_plane_side(d_q1, d_r2, d_n2, abs_d_q1, abs_d_r2, abs_d_n2);
1321 int sr1 = filter_plane_side(d_r1, d_r2, d_n2, abs_d_r1, abs_d_r2, abs_d_n2);
1322 if ((sp1 > 0 && sq1 > 0 && sr1 > 0) || (sp1 < 0 && sq1 < 0 && sr1 < 0)) {
1323# ifdef PERFDEBUG
1324 incperfcount(2); /* Triangle-triangle intersects decided by filter plane tests. */
1325# endif
1326 if (dbg_level > 0) {
1327 std::cout << "no intersection, all t1's verts above or below t2\n";
1328 }
1329 return ITT_value(INONE);
1330 }
1331
1332 const double3 &d_n1 = tri1.plane->norm;
1333 const double3 &abs_d_p2 = math::abs(d_p2);
1334 const double3 &abs_d_q2 = math::abs(d_q2);
1335 const double3 &abs_d_n1 = math::abs(d_n1);
1336
1337 int sp2 = filter_plane_side(d_p2, d_r1, d_n1, abs_d_p2, abs_d_r1, abs_d_n1);
1338 int sq2 = filter_plane_side(d_q2, d_r1, d_n1, abs_d_q2, abs_d_r1, abs_d_n1);
1339 int sr2 = filter_plane_side(d_r2, d_r1, d_n1, abs_d_r2, abs_d_r1, abs_d_n1);
1340 if ((sp2 > 0 && sq2 > 0 && sr2 > 0) || (sp2 < 0 && sq2 < 0 && sr2 < 0)) {
1341# ifdef PERFDEBUG
1342 incperfcount(2); /* Triangle-triangle intersects decided by filter plane tests. */
1343# endif
1344 if (dbg_level > 0) {
1345 std::cout << "no intersection, all t2's verts above or below t1\n";
1346 }
1347 return ITT_value(INONE);
1348 }
1349
1350 mpq3 buf[2];
1351 const mpq3 &p1 = vp1->co_exact;
1352 const mpq3 &q1 = vq1->co_exact;
1353 const mpq3 &r1 = vr1->co_exact;
1354 const mpq3 &p2 = vp2->co_exact;
1355 const mpq3 &q2 = vq2->co_exact;
1356 const mpq3 &r2 = vr2->co_exact;
1357
1358 const mpq3 &n2 = tri2.plane->norm_exact;
1359 if (sp1 == 0) {
1360 buf[0] = p1;
1361 buf[0] -= r2;
1362 sp1 = sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1363 }
1364 if (sq1 == 0) {
1365 buf[0] = q1;
1366 buf[0] -= r2;
1367 sq1 = sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1368 }
1369 if (sr1 == 0) {
1370 buf[0] = r1;
1371 buf[0] -= r2;
1372 sr1 = sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1373 }
1374
1375 if (dbg_level > 1) {
1376 std::cout << " sp1=" << sp1 << " sq1=" << sq1 << " sr1=" << sr1 << "\n";
1377 }
1378
1379 if ((sp1 * sq1 > 0) && (sp1 * sr1 > 0)) {
1380 if (dbg_level > 0) {
1381 std::cout << "no intersection, all t1's verts above or below t2 (exact)\n";
1382 }
1383# ifdef PERFDEBUG
1384 incperfcount(3); /* Triangle-triangle intersects decided by exact plane tests. */
1385# endif
1386 return ITT_value(INONE);
1387 }
1388
1389 /* Repeat for signs of t2's vertices with respect to plane of t1. */
1390 const mpq3 &n1 = tri1.plane->norm_exact;
1391 if (sp2 == 0) {
1392 buf[0] = p2;
1393 buf[0] -= r1;
1394 sp2 = sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1395 }
1396 if (sq2 == 0) {
1397 buf[0] = q2;
1398 buf[0] -= r1;
1399 sq2 = sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1400 }
1401 if (sr2 == 0) {
1402 buf[0] = r2;
1403 buf[0] -= r1;
1404 sr2 = sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1405 }
1406
1407 if (dbg_level > 1) {
1408 std::cout << " sp2=" << sp2 << " sq2=" << sq2 << " sr2=" << sr2 << "\n";
1409 }
1410
1411 if ((sp2 * sq2 > 0) && (sp2 * sr2 > 0)) {
1412 if (dbg_level > 0) {
1413 std::cout << "no intersection, all t2's verts above or below t1 (exact)\n";
1414 }
1415# ifdef PERFDEBUG
1416 incperfcount(3); /* Triangle-triangle intersects decided by exact plane tests. */
1417# endif
1418 return ITT_value(INONE);
1419 }
1420
1421 /* Do rest of the work with vertices in a canonical order, where p1 is on
1422 * positive side of plane and q1, r1 are not, or p1 is on the plane and
1423 * q1 and r1 are off the plane on the same side. */
1424 ITT_value ans;
1425 if (sp1 > 0) {
1426 if (sq1 > 0) {
1427 ans = itt_canon1(r1, p1, q1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1428 }
1429 else if (sr1 > 0) {
1430 ans = itt_canon1(q1, r1, p1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1431 }
1432 else {
1433 ans = itt_canon1(p1, q1, r1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1434 }
1435 }
1436 else if (sp1 < 0) {
1437 if (sq1 < 0) {
1438 ans = itt_canon1(r1, p1, q1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1439 }
1440 else if (sr1 < 0) {
1441 ans = itt_canon1(q1, r1, p1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1442 }
1443 else {
1444 ans = itt_canon1(p1, q1, r1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1445 }
1446 }
1447 else {
1448 if (sq1 < 0) {
1449 if (sr1 >= 0) {
1450 ans = itt_canon1(q1, r1, p1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1451 }
1452 else {
1453 ans = itt_canon1(p1, q1, r1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1454 }
1455 }
1456 else if (sq1 > 0) {
1457 if (sr1 > 0) {
1458 ans = itt_canon1(p1, q1, r1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1459 }
1460 else {
1461 ans = itt_canon1(q1, r1, p1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1462 }
1463 }
1464 else {
1465 if (sr1 > 0) {
1466 ans = itt_canon1(r1, p1, q1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1467 }
1468 else if (sr1 < 0) {
1469 ans = itt_canon1(r1, p1, q1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1470 }
1471 else {
1472 if (dbg_level > 0) {
1473 std::cout << "triangles are co-planar\n";
1474 }
1475 ans = ITT_value(ICOPLANAR);
1476 }
1477 }
1478 }
1479 if (ans.kind == ICOPLANAR) {
1480 ans.t_source = t2;
1481 }
1482
1483# ifdef PERFDEBUG
1484 if (ans.kind != INONE) {
1485 incperfcount(4);
1486 }
1487# endif
1488 return ans;
1489}
1490
1491struct CDT_data {
1492 const Plane *t_plane;
1493 Vector<mpq2> vert;
1494 Vector<int2> edge;
1495 Vector<int> face_offsets;
1496 Vector<int> face_vert_indices;
1498 Vector<int> input_face;
1500 Vector<bool> is_reversed;
1502 CDT_result<mpq_class> cdt_out;
1506 Map<OrderedEdge, int> verts_to_edge;
1507 int proj_axis;
1508};
1509
1513static int prepare_need_vert(CDT_data &cd, const mpq3 &p3d)
1514{
1515 mpq2 p2d = project_3d_to_2d(p3d, cd.proj_axis);
1516 int v = cd.vert.append_and_get_index(p2d);
1517 return v;
1518}
1519
1527static mpq3 unproject_cdt_vert(const CDT_data &cd, const mpq2 &p2d)
1528{
1529 mpq3 p3d;
1530 BLI_assert(cd.t_plane->exact_populated());
1531 BLI_assert(cd.t_plane->norm_exact[cd.proj_axis] != 0);
1532 const mpq3 &n = cd.t_plane->norm_exact;
1533 const mpq_class &d = cd.t_plane->d_exact;
1534 switch (cd.proj_axis) {
1535 case (0): {
1536 mpq_class num = n[1] * p2d[0] + n[2] * p2d[1] + d;
1537 num = -num;
1538 p3d[0] = num / n[0];
1539 p3d[1] = p2d[0];
1540 p3d[2] = p2d[1];
1541 break;
1542 }
1543 case (1): {
1544 p3d[0] = p2d[0];
1545 mpq_class num = n[0] * p2d[0] + n[2] * p2d[1] + d;
1546 num = -num;
1547 p3d[1] = num / n[1];
1548 p3d[2] = p2d[1];
1549 break;
1550 }
1551 case (2): {
1552 p3d[0] = p2d[0];
1553 p3d[1] = p2d[1];
1554 mpq_class num = n[0] * p2d[0] + n[1] * p2d[1] + d;
1555 num = -num;
1556 p3d[2] = num / n[2];
1557 break;
1558 }
1559 default:
1560 BLI_assert(false);
1561 }
1562 return p3d;
1563}
1564
1565static void prepare_need_edge(CDT_data &cd, const mpq3 &p1, const mpq3 &p2)
1566{
1567 int v1 = prepare_need_vert(cd, p1);
1568 int v2 = prepare_need_vert(cd, p2);
1569 cd.edge.append(int2(v1, v2));
1570}
1571
1572static void prepare_need_tri(CDT_data &cd, const IMesh &tm, int t)
1573{
1574 const Face &tri = *tm.face(t);
1575 int v0 = prepare_need_vert(cd, tri[0]->co_exact);
1576 int v1 = prepare_need_vert(cd, tri[1]->co_exact);
1577 int v2 = prepare_need_vert(cd, tri[2]->co_exact);
1578 bool rev;
1579 /* How to get CCW orientation of projected triangle? Note that when look down y axis
1580 * as opposed to x or z, the orientation of the other two axes is not right-and-up. */
1581 BLI_assert(cd.t_plane->exact_populated());
1582 if (tri.plane->norm_exact[cd.proj_axis] >= 0) {
1583 rev = cd.proj_axis == 1;
1584 }
1585 else {
1586 rev = cd.proj_axis != 1;
1587 }
1588 cd.face_offsets.append(cd.face_vert_indices.size());
1589 cd.face_vert_indices.append(v0);
1590 if (rev) {
1591 cd.face_vert_indices.append(v2);
1592 cd.face_vert_indices.append(v1);
1593 }
1594 else {
1595 cd.face_vert_indices.append(v1);
1596 cd.face_vert_indices.append(v2);
1597 }
1598 cd.input_face.append(t);
1599 cd.is_reversed.append(rev);
1600}
1601
1602static CDT_data prepare_cdt_input(const IMesh &tm, int t, const Span<ITT_value> itts)
1603{
1604 CDT_data ans;
1605 BLI_assert(tm.face(t)->plane_populated());
1606 ans.t_plane = tm.face(t)->plane;
1607 BLI_assert(ans.t_plane->exact_populated());
1608 ans.proj_axis = math::dominant_axis(ans.t_plane->norm_exact);
1609 prepare_need_tri(ans, tm, t);
1610 for (const ITT_value &itt : itts) {
1611 switch (itt.kind) {
1612 case INONE:
1613 break;
1614 case IPOINT: {
1615 prepare_need_vert(ans, itt.p1);
1616 break;
1617 }
1618 case ISEGMENT: {
1619 prepare_need_edge(ans, itt.p1, itt.p2);
1620 break;
1621 }
1622 case ICOPLANAR: {
1623 prepare_need_tri(ans, tm, itt.t_source);
1624 break;
1625 }
1626 }
1627 }
1628 ans.face_offsets.append(ans.face_vert_indices.size());
1629 return ans;
1630}
1631
1632static CDT_data prepare_cdt_input_for_cluster(const IMesh &tm,
1633 const CoplanarClusterInfo &clinfo,
1634 int c,
1635 const Span<ITT_value> itts)
1636{
1637 CDT_data ans;
1638 BLI_assert(c < clinfo.tot_cluster());
1639 const CoplanarCluster &cl = clinfo.cluster(c);
1640 BLI_assert(cl.tot_tri() > 0);
1641 int t0 = cl.tri(0);
1642 BLI_assert(tm.face(t0)->plane_populated());
1643 ans.t_plane = tm.face(t0)->plane;
1644 BLI_assert(ans.t_plane->exact_populated());
1645 ans.proj_axis = math::dominant_axis(ans.t_plane->norm_exact);
1646 for (const int t : cl) {
1647 prepare_need_tri(ans, tm, t);
1648 }
1649 for (const ITT_value &itt : itts) {
1650 switch (itt.kind) {
1651 case IPOINT: {
1652 prepare_need_vert(ans, itt.p1);
1653 break;
1654 }
1655 case ISEGMENT: {
1656 prepare_need_edge(ans, itt.p1, itt.p2);
1657 break;
1658 }
1659 default:
1660 break;
1661 }
1662 }
1663 ans.face_offsets.append(ans.face_vert_indices.size());
1664 return ans;
1665}
1666
1671static void populate_cdt_edge_map(Map<OrderedEdge, int> &verts_to_edge,
1672 const CDT_result<mpq_class> &cdt_out)
1673{
1674 verts_to_edge.reserve(cdt_out.edge.size());
1675 for (int e : cdt_out.edge.index_range()) {
1676 /* There should be only one edge for each vertex pair. */
1677 verts_to_edge.add(OrderedEdge(cdt_out.edge[e]), e);
1678 }
1679}
1680
1684static void do_cdt(CDT_data &cd)
1685{
1686 constexpr int dbg_level = 0;
1687 CDT_input<mpq_class> cdt_in;
1688 cdt_in.vert = Span<mpq2>(cd.vert);
1689 cdt_in.edge = Span<int2>(cd.edge);
1690 cdt_in.face_offsets = cd.face_offsets.as_span();
1691 cdt_in.face_vert_indices = cd.face_vert_indices;
1692 if (dbg_level > 0) {
1693 std::cout << "CDT input\nVerts:\n";
1694 for (int i : cdt_in.vert.index_range()) {
1695 std::cout << "v" << i << ": " << cdt_in.vert[i] << "=(" << cdt_in.vert[i][0].get_d() << ","
1696 << cdt_in.vert[i][1].get_d() << ")\n";
1697 }
1698 std::cout << "Edges:\n";
1699 for (int i : cdt_in.edge.index_range()) {
1700 std::cout << "e" << i << ": (" << cdt_in.edge[i][0] << ", " << cdt_in.edge[i][1] << ")\n";
1701 }
1702 std::cout << "Tris\n";
1703 const GroupedSpan<int> in_faces(cdt_in.face_offsets, cdt_in.face_vert_indices);
1704 for (int f : in_faces.index_range()) {
1705 std::cout << "f" << f << ": ";
1706 for (int j : in_faces[f].index_range()) {
1707 std::cout << in_faces[f][j] << " ";
1708 }
1709 std::cout << "\n";
1710 }
1711 }
1712 cdt_in.epsilon = 0; /* TODO: needs attention for non-exact T. */
1713 cdt_in.needed_ids = CDT_ORIG_VERTS | CDT_ORIG_EDGES | CDT_ORIG_FACES;
1714 cd.cdt_out = delaunay_2d_calc(cdt_in, CDT_INSIDE);
1715 constexpr int make_edge_map_threshold = 15;
1716 if (cd.cdt_out.edge.size() >= make_edge_map_threshold) {
1717 populate_cdt_edge_map(cd.verts_to_edge, cd.cdt_out);
1718 }
1719 if (dbg_level > 0) {
1720 std::cout << "\nCDT result\nVerts:\n";
1721 for (int i : cd.cdt_out.vert.index_range()) {
1722 std::cout << "v" << i << ": " << cd.cdt_out.vert[i] << "=(" << cd.cdt_out.vert[i][0].get_d()
1723 << "," << cd.cdt_out.vert[i][1].get_d() << "\n";
1724 }
1725 std::cout << "Tris\n";
1726 for (int f : cd.cdt_out.face.index_range()) {
1727 std::cout << "f" << f << ": ";
1728 for (int j : cd.cdt_out.face[f].index_range()) {
1729 std::cout << cd.cdt_out.face[f][j] << " ";
1730 }
1731 std::cout << "orig: ";
1732 for (int j : cd.cdt_out.face_orig[f].index_range()) {
1733 std::cout << cd.cdt_out.face_orig[f][j] << " ";
1734 }
1735 std::cout << "\n";
1736 }
1737 std::cout << "Edges\n";
1738 for (int e : cd.cdt_out.edge.index_range()) {
1739 std::cout << "e" << e << ": (" << cd.cdt_out.edge[e][0] << ", " << cd.cdt_out.edge[e][1]
1740 << ") ";
1741 std::cout << "orig: ";
1742 for (int j : cd.cdt_out.edge_orig[e].index_range()) {
1743 std::cout << cd.cdt_out.edge_orig[e][j] << " ";
1744 }
1745 std::cout << "\n";
1746 }
1747 }
1748}
1749
1750/* Find an original edge index that goes with the edge that the CDT output edge
1751 * that goes between verts i0 and i1 (in the CDT output vert indexing scheme).
1752 * There may be more than one: if so, prefer one that was originally a face edge.
1753 * The input to CDT for a triangle with some intersecting segments from other triangles
1754 * will have both edges and a face constraint for the main triangle (this is redundant
1755 * but allows us to discover which face edge goes with which output edges).
1756 * If there is any face edge, return one of those as the original.
1757 * If there is no face edge but there is another edge in the input problem, then that
1758 * edge must have come from intersection with another triangle, so set *r_is_intersect
1759 * to true in that case. */
1760static int get_cdt_edge_orig(
1761 int i0, int i1, const CDT_data &cd, const IMesh &in_tm, bool *r_is_intersect)
1762{
1763 uint32_t foff = cd.cdt_out.face_edge_offset;
1764 *r_is_intersect = false;
1765 int e = NO_INDEX;
1766 if (cd.verts_to_edge.size() > 0) {
1767 /* Use the populated map to find the edge, if any, between vertices i0 and i1. */
1768 e = cd.verts_to_edge.lookup_default(OrderedEdge(i0, i1), NO_INDEX);
1769 }
1770 else {
1771 for (int ee : cd.cdt_out.edge.index_range()) {
1772 const int2 edge = cd.cdt_out.edge[ee];
1773 if ((edge[0] == i0 && edge[1] == i1) || (edge[0] == i1 && edge[1] == i0)) {
1774 e = ee;
1775 break;
1776 }
1777 }
1778 }
1779 if (e == NO_INDEX) {
1780 return NO_INDEX;
1781 }
1782
1783 /* Pick an arbitrary orig, but not one equal to NO_INDEX, if we can help it. */
1784 /* TODO: if edge has origs from more than one part of the nary input,
1785 * then want to set *r_is_intersect to true. */
1786 int face_eorig = NO_INDEX;
1787 bool have_non_face_eorig = false;
1788 for (uint32_t orig_index : cd.cdt_out.edge_orig[e]) {
1789 /* orig_index encodes the triangle and pos within the triangle of the input edge. */
1790 if (orig_index >= foff) {
1791 if (face_eorig == NO_INDEX) {
1792 uint32_t in_face_index = (orig_index / foff) - 1;
1793 int pos = int(orig_index % foff);
1794 /* We need to retrieve the edge orig field from the Face used to populate the
1795 * in_face_index'th face of the CDT, at the pos'th position of the face. */
1796 int in_tm_face_index = cd.input_face[in_face_index];
1797 BLI_assert(in_tm_face_index < in_tm.face_size());
1798 const Face *facep = in_tm.face(in_tm_face_index);
1799 BLI_assert(pos < facep->size());
1800 bool is_rev = cd.is_reversed[in_face_index];
1801 int eorig = is_rev ? facep->edge_orig[2 - pos] : facep->edge_orig[pos];
1802 if (eorig != NO_INDEX) {
1803 face_eorig = eorig;
1804 }
1805 }
1806 }
1807 else {
1808 if (!have_non_face_eorig) {
1809 have_non_face_eorig = true;
1810 }
1811 if (face_eorig != NO_INDEX && have_non_face_eorig) {
1812 /* Only need at most one orig for each type. */
1813 break;
1814 }
1815 }
1816 }
1817 if (face_eorig != NO_INDEX) {
1818 return face_eorig;
1819 }
1820 if (have_non_face_eorig) {
1821 /* This must have been an input to the CDT problem that was an intersection edge. */
1822 /* TODO: maybe there is an orig index:
1823 * This happens if an input edge was formed by an input face having
1824 * an edge that is co-planar with the cluster, while the face as a whole is not. */
1825 *r_is_intersect = true;
1826 return NO_INDEX;
1827 }
1828 return NO_INDEX;
1829}
1830
1836static Face *cdt_tri_as_imesh_face(
1837 int cdt_out_t, int cdt_in_t, const CDT_data &cd, const IMesh &tm, IMeshArena *arena)
1838{
1839 const CDT_result<mpq_class> &cdt_out = cd.cdt_out;
1840 int t_orig = tm.face(cd.input_face[cdt_in_t])->orig;
1841 BLI_assert(cdt_out.face[cdt_out_t].size() == 3);
1842 int i0 = cdt_out.face[cdt_out_t][0];
1843 int i1 = cdt_out.face[cdt_out_t][1];
1844 int i2 = cdt_out.face[cdt_out_t][2];
1845 mpq3 v0co = unproject_cdt_vert(cd, cdt_out.vert[i0]);
1846 mpq3 v1co = unproject_cdt_vert(cd, cdt_out.vert[i1]);
1847 mpq3 v2co = unproject_cdt_vert(cd, cdt_out.vert[i2]);
1848 /* No need to provide an original index: if coord matches
1849 * an original one, then it will already be in the arena
1850 * with the correct orig field. */
1851 const Vert *v0 = arena->add_or_find_vert(v0co, NO_INDEX);
1852 const Vert *v1 = arena->add_or_find_vert(v1co, NO_INDEX);
1853 const Vert *v2 = arena->add_or_find_vert(v2co, NO_INDEX);
1854 Face *facep;
1855 bool is_isect0;
1856 bool is_isect1;
1857 bool is_isect2;
1858 if (cd.is_reversed[cdt_in_t]) {
1859 int oe0 = get_cdt_edge_orig(i0, i2, cd, tm, &is_isect0);
1860 int oe1 = get_cdt_edge_orig(i2, i1, cd, tm, &is_isect1);
1861 int oe2 = get_cdt_edge_orig(i1, i0, cd, tm, &is_isect2);
1862 facep = arena->add_face(
1863 {v0, v2, v1}, t_orig, {oe0, oe1, oe2}, {is_isect0, is_isect1, is_isect2});
1864 }
1865 else {
1866 int oe0 = get_cdt_edge_orig(i0, i1, cd, tm, &is_isect0);
1867 int oe1 = get_cdt_edge_orig(i1, i2, cd, tm, &is_isect1);
1868 int oe2 = get_cdt_edge_orig(i2, i0, cd, tm, &is_isect2);
1869 facep = arena->add_face(
1870 {v0, v1, v2}, t_orig, {oe0, oe1, oe2}, {is_isect0, is_isect1, is_isect2});
1871 }
1872 facep->populate_plane(false);
1873 return facep;
1874}
1875
1876/* Like BLI_math's is_quad_flip_v3_first_third_fast, with const double3's. */
1877static bool is_quad_flip_first_third(const double3 &v1,
1878 const double3 &v2,
1879 const double3 &v3,
1880 const double3 &v4)
1881{
1882 const double3 d_12 = v2 - v1;
1883 const double3 d_13 = v3 - v1;
1884 const double3 d_14 = v4 - v1;
1885
1886 const double3 cross_a = math::cross(d_12, d_13);
1887 const double3 cross_b = math::cross(d_14, d_13);
1888 return math::dot(cross_a, cross_b) > 0.0f;
1889}
1890
1903static Array<Face *> polyfill_triangulate_poly(Face *f, IMeshArena *arena)
1904{
1905 /* Similar to loop body in #BM_mesh_calc_tessellation. */
1906 int flen = f->size();
1907 BLI_assert(flen >= 4);
1908 if (!f->plane_populated()) {
1909 f->populate_plane(false);
1910 }
1911 const double3 &poly_normal = f->plane->norm;
1912 float no[3] = {float(poly_normal[0]), float(poly_normal[1]), float(poly_normal[2])};
1913 normalize_v3(no);
1914 if (flen == 4) {
1915 const Vert *v0 = (*f)[0];
1916 const Vert *v1 = (*f)[1];
1917 const Vert *v2 = (*f)[2];
1918 const Vert *v3 = (*f)[3];
1919 int eo_01 = f->edge_orig[0];
1920 int eo_12 = f->edge_orig[1];
1921 int eo_23 = f->edge_orig[2];
1922 int eo_30 = f->edge_orig[3];
1923 Face *f0, *f1;
1924 if (is_quad_flip_first_third(v0->co, v1->co, v2->co, v3->co)) [[unlikely]] {
1925 f0 = arena->add_face({v0, v1, v3}, f->orig, {eo_01, -1, eo_30}, {false, false, false});
1926 f1 = arena->add_face({v1, v2, v3}, f->orig, {eo_12, eo_23, -1}, {false, false, false});
1927 }
1928 else {
1929 f0 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1}, {false, false, false});
1930 f1 = arena->add_face({v0, v2, v3}, f->orig, {-1, eo_23, eo_30}, {false, false, false});
1931 }
1932 return Array<Face *>{f0, f1};
1933 }
1934 /* Project along negative face normal so (x,y) can be used in 2d. */
1935 float axis_mat[3][3];
1936 float (*projverts)[2];
1937 uint(*tris)[3];
1938 const int totfilltri = flen - 2;
1939 /* Prepare projected vertices and array to receive triangles in tessellation. */
1940 tris = MEM_new_array_uninitialized<uint[3]>(size_t(totfilltri), __func__);
1941 projverts = MEM_new_array_uninitialized<float[2]>(size_t(flen), __func__);
1942 axis_dominant_v3_to_m3_negate(axis_mat, no);
1943 for (int j = 0; j < flen; ++j) {
1944 const double3 &dco = (*f)[j]->co;
1945 float co[3] = {float(dco[0]), float(dco[1]), float(dco[2])};
1946 mul_v2_m3v3(projverts[j], axis_mat, co);
1947 }
1948 BLI_polyfill_calc(projverts, flen, 1, tris);
1949 /* Put tessellation triangles into Face form. Record original edges where they exist. */
1950 Array<Face *> ans(totfilltri);
1951 for (int t = 0; t < totfilltri; ++t) {
1952 uint *tri = tris[t];
1953 int eo[3];
1954 const Vert *v[3];
1955 for (int k = 0; k < 3; k++) {
1956 BLI_assert(tri[k] < flen);
1957 v[k] = (*f)[tri[k]];
1958 /* If tri edge goes between two successive indices in
1959 * the original face, then it is an original edge. */
1960 if ((tri[k] + 1) % flen == tri[(k + 1) % 3]) {
1961 eo[k] = f->edge_orig[tri[k]];
1962 }
1963 else {
1964 eo[k] = NO_INDEX;
1965 }
1966 ans[t] = arena->add_face(
1967 {v[0], v[1], v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {false, false, false});
1968 }
1969 }
1970
1971 MEM_delete(tris);
1972 MEM_delete(projverts);
1973
1974 return ans;
1975}
1976
1992static Array<Face *> exact_triangulate_poly(Face *f, IMeshArena *arena)
1993{
1994 int flen = f->size();
1995 Array<mpq2> in_verts(flen);
1996 const Array<int> face_offsets({0, flen});
1997 Array<int> face_vert_indices(flen);
1998 std::iota(face_vert_indices.begin(), face_vert_indices.end(), 0);
1999
2000 /* Project poly along dominant axis of normal to get 2d coords. */
2001 if (!f->plane_populated()) {
2002 f->populate_plane(false);
2003 }
2004 const double3 &poly_normal = f->plane->norm;
2005 int axis = math::dominant_axis(poly_normal);
2006 /* If project down y axis as opposed to x or z, the orientation
2007 * of the face will be reversed.
2008 * Yet another reversal happens if the poly normal in the dominant
2009 * direction is opposite that of the positive dominant axis. */
2010 bool rev1 = (axis == 1);
2011 bool rev2 = poly_normal[axis] < 0;
2012 bool rev = rev1 ^ rev2;
2013 for (int i = 0; i < flen; ++i) {
2014 int ii = rev ? flen - i - 1 : i;
2015 mpq2 &p2d = in_verts[ii];
2016 int k = 0;
2017 for (int j = 0; j < 3; ++j) {
2018 if (j != axis) {
2019 p2d[k++] = (*f)[ii]->co_exact[j];
2020 }
2021 }
2022 }
2023
2024 CDT_input<mpq_class> cdt_in;
2025 cdt_in.vert = in_verts;
2026 cdt_in.face_offsets = face_offsets.as_span();
2027 cdt_in.face_vert_indices = face_vert_indices;
2028 cdt_in.needed_ids = CDT_ORIG_VERTS | CDT_ORIG_EDGES | CDT_ORIG_FACES;
2029
2030 CDT_result<mpq_class> cdt_out = delaunay_2d_calc(cdt_in, CDT_INSIDE);
2031 int n_tris = cdt_out.face.size();
2032 Array<Face *> ans(n_tris);
2033 for (int t = 0; t < n_tris; ++t) {
2034 int i_v_out[3];
2035 const Vert *v[3];
2036 int eo[3];
2037 bool needs_steiner = false;
2038 for (int i = 0; i < 3; ++i) {
2039 i_v_out[i] = cdt_out.face[t][i];
2040 if (cdt_out.vert_orig[i_v_out[i]].is_empty()) {
2041 needs_steiner = true;
2042 break;
2043 }
2044 v[i] = (*f)[cdt_out.vert_orig[i_v_out[i]][0]];
2045 }
2046 if (needs_steiner) {
2047 /* Fall back on the polyfill triangulator. */
2048 return polyfill_triangulate_poly(f, arena);
2049 }
2050 Map<OrderedEdge, int> verts_to_edge;
2051 populate_cdt_edge_map(verts_to_edge, cdt_out);
2052 uint32_t foff = cdt_out.face_edge_offset;
2053 for (int i = 0; i < 3; ++i) {
2054 const OrderedEdge vpair_canon(i_v_out[i], i_v_out[(i + 1) % 3]);
2055 int e_out = verts_to_edge.lookup_default(vpair_canon, NO_INDEX);
2056 BLI_assert(e_out != NO_INDEX);
2057 eo[i] = NO_INDEX;
2058 for (uint32_t orig : cdt_out.edge_orig[e_out]) {
2059 if (orig >= foff) {
2060 int pos = int(orig % foff);
2061 BLI_assert(pos < f->size());
2062 eo[i] = f->edge_orig[pos];
2063 break;
2064 }
2065 }
2066 }
2067 if (rev) {
2068 ans[t] = arena->add_face(
2069 {v[0], v[2], v[1]}, f->orig, {eo[2], eo[1], eo[0]}, {false, false, false});
2070 }
2071 else {
2072 ans[t] = arena->add_face(
2073 {v[0], v[1], v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {false, false, false});
2074 }
2075 }
2076 return ans;
2077}
2078
2079static bool face_is_degenerate(const Face *f)
2080{
2081 const Face &face = *f;
2082 const Vert *v0 = face[0];
2083 const Vert *v1 = face[1];
2084 const Vert *v2 = face[2];
2085 if (v0 == v1 || v0 == v2 || v1 == v2) {
2086 return true;
2087 }
2088 double3 da = v2->co - v0->co;
2089 double3 db = v2->co - v1->co;
2090 double3 dab = math::cross(da, db);
2091 double dab_length_squared = math::length_squared(dab);
2092 double err_bound = supremum_dot_cross(dab, dab) * index_dot_cross * DBL_EPSILON;
2093 if (dab_length_squared > err_bound) {
2094 return false;
2095 }
2096 mpq3 a = v2->co_exact - v0->co_exact;
2097 mpq3 b = v2->co_exact - v1->co_exact;
2098 mpq3 ab = math::cross(a, b);
2099 if (ab.x == 0 && ab.y == 0 && ab.z == 0) {
2100 return true;
2101 }
2102
2103 return false;
2104}
2105
2107static bool any_degenerate_tris_fast(const Array<Face *> &triangulation)
2108{
2109 for (const Face *f : triangulation) {
2110 const Vert *v0 = (*f)[0];
2111 const Vert *v1 = (*f)[1];
2112 const Vert *v2 = (*f)[2];
2113 if (v0 == v1 || v0 == v2 || v1 == v2) {
2114 return true;
2115 }
2116 double3 da = v2->co - v0->co;
2117 double3 db = v2->co - v1->co;
2118 double da_length_squared = math::length_squared(da);
2119 double db_length_squared = math::length_squared(db);
2120 if (da_length_squared == 0.0 || db_length_squared == 0.0) {
2121 return true;
2122 }
2123 /* |da x db| = |da| |db| sin t, where t is angle between them.
2124 * The triangle is almost degenerate if sin t is almost 0.
2125 * sin^2 t = |da x db|^2 / (|da|^2 |db|^2)
2126 */
2127 double3 dab = math::cross(da, db);
2128 double dab_length_squared = math::length_squared(dab);
2129 double sin_squared_t = dab_length_squared / (da_length_squared * db_length_squared);
2130 if (sin_squared_t < 1e-8) {
2131 return true;
2132 }
2133 }
2134 return false;
2135}
2136
2145static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
2146{
2147 /* Try the much faster method using Blender's BLI_polyfill_calc. */
2148 Array<Face *> ans = polyfill_triangulate_poly(f, arena);
2149
2150 /* This may create degenerate triangles. If so, try the exact CDT-based triangulator. */
2151 if (any_degenerate_tris_fast(ans)) {
2152 return exact_triangulate_poly(f, arena);
2153 }
2154 return ans;
2155}
2156
2157IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
2158{
2159 Vector<Face *> face_tris;
2160 constexpr int estimated_tris_per_face = 3;
2161 face_tris.reserve(estimated_tris_per_face * imesh.face_size());
2162 threading::parallel_for(imesh.face_index_range(), 2048, [&](IndexRange range) {
2163 for (int i : range) {
2164 Face *f = imesh.face(i);
2165 if (!f->plane_populated() && f->size() >= 4) {
2166 f->populate_plane(false);
2167 }
2168 }
2169 });
2170 for (Face *f : imesh.faces()) {
2171 /* Tessellate face f, following plan similar to #BM_face_calc_tessellation. */
2172 int flen = f->size();
2173 if (flen == 3) {
2174 face_tris.append(f);
2175 }
2176 else {
2177 Array<Face *> tris = triangulate_poly(f, arena);
2178 for (Face *tri : tris) {
2179 face_tris.append(tri);
2180 }
2181 }
2182 }
2183 return IMesh(face_tris);
2184}
2185
2190static IMesh extract_subdivided_tri(const CDT_data &cd,
2191 const IMesh &in_tm,
2192 int t,
2193 IMeshArena *arena)
2194{
2195 const CDT_result<mpq_class> &cdt_out = cd.cdt_out;
2196 int t_in_cdt = -1;
2197 for (int i = 0; i < cd.input_face.size(); ++i) {
2198 if (cd.input_face[i] == t) {
2199 t_in_cdt = i;
2200 }
2201 }
2202 if (t_in_cdt == -1) {
2203 std::cout << "Could not find " << t << " in cdt input tris\n";
2204 BLI_assert(false);
2205 return IMesh();
2206 }
2207 constexpr int inline_buf_size = 20;
2208 Vector<Face *, inline_buf_size> faces;
2209 for (int f : cdt_out.face.index_range()) {
2210 if (cdt_out.face_orig[f].contains(t_in_cdt)) {
2211 Face *facep = cdt_tri_as_imesh_face(f, t_in_cdt, cd, in_tm, arena);
2212 faces.append(facep);
2213 }
2214 }
2215 return IMesh(faces);
2216}
2217
2218static bool bvhtreeverlap_cmp(const BVHTreeOverlap &a, const BVHTreeOverlap &b)
2219{
2220 if (a.indexA < b.indexA) {
2221 return true;
2222 }
2223 if ((a.indexA == b.indexA) && (a.indexB < b.indexB)) {
2224 return true;
2225 }
2226 return false;
2227}
2228class TriOverlaps {
2229 BVHTree *tree_{nullptr};
2230 BVHTree *tree_b_{nullptr};
2231 BVHTreeOverlap *overlap_{nullptr};
2232 Array<int> first_overlap_;
2233 uint overlap_num_{0};
2234
2235 struct CBData {
2236 const IMesh &tm;
2237 std::function<int(int)> shape_fn;
2238 int nshapes;
2239 bool use_self;
2240 };
2241
2242 public:
2243 TriOverlaps(const IMesh &tm,
2244 const Span<BoundingBox> tri_bb,
2245 int nshapes,
2246 std::function<int(int)> shape_fn,
2247 bool use_self)
2248 {
2249 constexpr int dbg_level = 0;
2250 if (dbg_level > 0) {
2251 std::cout << "TriOverlaps construction\n";
2252 }
2253 /* Tree type is 8 => octree; axis = 6 => using XYZ axes only. */
2254 tree_ = BLI_bvhtree_new(tm.face_size(), FLT_EPSILON, 8, 6);
2255 /* In the common case of a binary boolean and no self intersection in
2256 * each shape, we will use two trees and simple bounding box overlap. */
2257 bool two_trees_no_self = nshapes == 2 && !use_self;
2258 if (two_trees_no_self) {
2259 tree_b_ = BLI_bvhtree_new(tm.face_size(), FLT_EPSILON, 8, 6);
2260 }
2261
2262 /* Create a Vector containing face shape. */
2263 Vector<int> shapes;
2264 shapes.resize(tm.face_size());
2265 threading::parallel_for(tm.face_index_range(), 2048, [&](IndexRange range) {
2266 for (int t : range) {
2267 shapes[t] = shape_fn(tm.face(t)->orig);
2268 }
2269 });
2270
2271 float bbpts[6];
2272 for (int t : tm.face_index_range()) {
2273 const BoundingBox &bb = tri_bb[t];
2274 copy_v3_v3(bbpts, bb.min);
2275 copy_v3_v3(bbpts + 3, bb.max);
2276 int shape = shapes[t];
2277 if (two_trees_no_self) {
2278 if (shape == 0) {
2279 BLI_bvhtree_insert(tree_, t, bbpts, 2);
2280 }
2281 else if (shape == 1) {
2282 BLI_bvhtree_insert(tree_b_, t, bbpts, 2);
2283 }
2284 }
2285 else {
2286 if (shape != -1) {
2287 BLI_bvhtree_insert(tree_, t, bbpts, 2);
2288 }
2289 }
2290 }
2291 BLI_bvhtree_balance(tree_);
2292 if (two_trees_no_self) {
2293 BLI_bvhtree_balance(tree_b_);
2294 /* Don't expect a lot of trivial intersects in this case. */
2295 overlap_ = BLI_bvhtree_overlap(tree_, tree_b_, &overlap_num_, nullptr, nullptr);
2296 }
2297 else {
2298 CBData cbdata{tm, shape_fn, nshapes, use_self};
2299 if (nshapes == 1) {
2300 overlap_ = BLI_bvhtree_overlap(tree_, tree_, &overlap_num_, nullptr, nullptr);
2301 }
2302 else {
2303 overlap_ = BLI_bvhtree_overlap(
2304 tree_, tree_, &overlap_num_, only_different_shapes, &cbdata);
2305 }
2306 }
2307 /* The rest of the code is simpler and easier to parallelize if, in the two-trees case,
2308 * we repeat the overlaps with indexA and indexB reversed. It is important that
2309 * in the repeated part, sorting will then bring things with indexB together. */
2310 if (two_trees_no_self) {
2311 overlap_ = static_cast<BVHTreeOverlap *>(
2312 MEM_realloc_uninitialized(overlap_, 2 * overlap_num_ * sizeof(overlap_[0])));
2313 for (uint i = 0; i < overlap_num_; ++i) {
2314 overlap_[overlap_num_ + i].indexA = overlap_[i].indexB;
2315 overlap_[overlap_num_ + i].indexB = overlap_[i].indexA;
2316 }
2317 overlap_num_ += overlap_num_;
2318 }
2319 /* Sort the overlaps to bring all the intersects with a given indexA together. */
2320 std::sort(overlap_, overlap_ + overlap_num_, bvhtreeverlap_cmp);
2321 if (dbg_level > 0) {
2322 std::cout << overlap_num_ << " overlaps found:\n";
2323 for (BVHTreeOverlap ov : overlap()) {
2324 std::cout << "A: " << ov.indexA << ", B: " << ov.indexB << "\n";
2325 }
2326 }
2327 first_overlap_ = Array<int>(tm.face_size(), -1);
2328 for (int i = 0; i < int(overlap_num_); ++i) {
2329 int t = overlap_[i].indexA;
2330 if (first_overlap_[t] == -1) {
2331 first_overlap_[t] = i;
2332 }
2333 }
2334 }
2335
2336 ~TriOverlaps()
2337 {
2338 if (tree_) {
2339 BLI_bvhtree_free(tree_);
2340 }
2341 if (tree_b_) {
2342 BLI_bvhtree_free(tree_b_);
2343 }
2344 if (overlap_) {
2345 MEM_delete(overlap_);
2346 }
2347 }
2348
2349 Span<BVHTreeOverlap> overlap() const
2350 {
2351 return Span<BVHTreeOverlap>(overlap_, overlap_num_);
2352 }
2353
2354 int first_overlap_index(int t) const
2355 {
2356 return first_overlap_[t];
2357 }
2358
2359 private:
2360 static bool only_different_shapes(void *userdata, int index_a, int index_b, int /*thread*/)
2361 {
2362 CBData *cbdata = static_cast<CBData *>(userdata);
2363 return cbdata->tm.face(index_a)->orig != cbdata->tm.face(index_b)->orig;
2364 }
2365};
2366
2370struct OverlapIttsData {
2371 Vector<std::pair<int, int>> intersect_pairs;
2372 Map<std::pair<int, int>, ITT_value> &itt_map;
2373 const IMesh &tm;
2374 IMeshArena *arena;
2375
2376 OverlapIttsData(Map<std::pair<int, int>, ITT_value> &itt_map, const IMesh &tm, IMeshArena *arena)
2377 : itt_map(itt_map), tm(tm), arena(arena)
2378 {
2379 }
2380};
2381
2386static std::pair<int, int> canon_int_pair(int a, int b)
2387{
2388 if (a > b) {
2389 std::swap(a, b);
2390 }
2391 return std::pair<int, int>(a, b);
2392}
2393
2394static void calc_overlap_itts_range_func(void *__restrict userdata,
2395 const int iter,
2396 const TaskParallelTLS *__restrict /*tls*/)
2397{
2398 constexpr int dbg_level = 0;
2399 OverlapIttsData *data = static_cast<OverlapIttsData *>(userdata);
2400 std::pair<int, int> tri_pair = data->intersect_pairs[iter];
2401 int a = tri_pair.first;
2402 int b = tri_pair.second;
2403 if (dbg_level > 0) {
2404 std::cout << "calc_overlap_itts_range_func a=" << a << ", b=" << b << "\n";
2405 }
2406 ITT_value itt = intersect_tri_tri(data->tm, a, b);
2407 if (dbg_level > 0) {
2408 std::cout << "result of intersecting " << a << " and " << b << " = " << itt << "\n";
2409 }
2410 BLI_assert(data->itt_map.contains(tri_pair));
2411 data->itt_map.add_overwrite(tri_pair, itt);
2412}
2413
2418static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map,
2419 const IMesh &tm,
2420 const TriOverlaps &ov,
2421 IMeshArena *arena)
2422{
2423 OverlapIttsData data(itt_map, tm, arena);
2424 /* Put dummy values in `itt_map` initially,
2425 * so map entries will exist when doing the range function.
2426 * This means we won't have to protect the `itt_map.add_overwrite` function with a lock. */
2427 for (const BVHTreeOverlap &olap : ov.overlap()) {
2428 std::pair<int, int> key = canon_int_pair(olap.indexA, olap.indexB);
2429 if (!itt_map.contains(key)) {
2430 itt_map.add_new(key, ITT_value());
2431 data.intersect_pairs.append(key);
2432 }
2433 }
2434 int tot_intersect_pairs = data.intersect_pairs.size();
2435 TaskParallelSettings settings;
2437 settings.min_iter_per_thread = 1000;
2438 settings.use_threading = intersect_use_threading;
2439 BLI_task_parallel_range(0, tot_intersect_pairs, &data, calc_overlap_itts_range_func, &settings);
2440}
2441
2448static void calc_subdivided_non_cluster_tris(Array<IMesh> &r_tri_subdivided,
2449 const IMesh &tm,
2450 const Map<std::pair<int, int>, ITT_value> &itt_map,
2451 const CoplanarClusterInfo &clinfo,
2452 const TriOverlaps &ov,
2453 IMeshArena *arena)
2454{
2455 const int dbg_level = 0;
2456 if (dbg_level > 0) {
2457 std::cout << "\nCALC_SUBDIVIDED_TRIS\n\n";
2458 }
2459 Span<BVHTreeOverlap> overlap = ov.overlap();
2460 struct OverlapTriRange {
2461 int tri_index;
2462 int overlap_start;
2463 int len;
2464 };
2465 Vector<OverlapTriRange> overlap_tri_range;
2466 int overlap_num = overlap.size();
2467 overlap_tri_range.reserve(overlap_num);
2468 int overlap_index = 0;
2469 while (overlap_index < overlap_num) {
2470 int t = overlap[overlap_index].indexA;
2471 int i = overlap_index;
2472 while (i + 1 < overlap_num && overlap[i + 1].indexA == t) {
2473 ++i;
2474 }
2475 /* Now overlap[overlap_index] to overlap[i] have indexA == t.
2476 * We only record ranges for triangles that are not in clusters,
2477 * because the ones in clusters are handled separately. */
2478 if (clinfo.tri_cluster(t) == NO_INDEX) {
2479 int len = i - overlap_index + 1;
2480 if (!(len == 1 && overlap[overlap_index].indexB == t)) {
2481 OverlapTriRange range = {t, overlap_index, len};
2482 overlap_tri_range.append(range);
2483# ifdef PERFDEBUG
2484 bumpperfcount(0, len); /* Non-cluster overlaps. */
2485# endif
2486 }
2487 }
2488 overlap_index = i + 1;
2489 }
2490 int overlap_tri_range_num = overlap_tri_range.size();
2491 Array<CDT_data> cd_data(overlap_tri_range_num);
2492 int grain_size = 64;
2493 threading::parallel_for(overlap_tri_range.index_range(), grain_size, [&](IndexRange range) {
2494 for (int otr_index : range) {
2495 OverlapTriRange &otr = overlap_tri_range[otr_index];
2496 int t = otr.tri_index;
2497 if (dbg_level > 0) {
2498 std::cout << "handling overlap range\nt=" << t << " start=" << otr.overlap_start
2499 << " len=" << otr.len << "\n";
2500 }
2501 constexpr int inline_capacity = 100;
2502 Vector<ITT_value, inline_capacity> itts(otr.len);
2503 for (int j = otr.overlap_start; j < otr.overlap_start + otr.len; ++j) {
2504 int t_other = overlap[j].indexB;
2505 std::pair<int, int> key = canon_int_pair(t, t_other);
2506 ITT_value itt;
2507 if (itt_map.contains(key)) {
2508 itt = itt_map.lookup(key);
2509 }
2510 if (itt.kind != INONE) {
2511 itts.append(itt);
2512 }
2513 if (dbg_level > 0) {
2514 std::cout << " tri t" << t_other << "; result = " << itt << "\n";
2515 }
2516 }
2517 if (itts.size() > 0) {
2518 cd_data[otr_index] = prepare_cdt_input(tm, t, itts);
2519 do_cdt(cd_data[otr_index]);
2520 }
2521 }
2522 });
2523 /* Extract the new faces serially, so that Boolean is repeatable regardless of parallelism. */
2524 for (int otr_index : overlap_tri_range.index_range()) {
2525 CDT_data &cdd = cd_data[otr_index];
2526 if (cdd.vert.size() > 0) {
2527 int t = overlap_tri_range[otr_index].tri_index;
2528 r_tri_subdivided[t] = extract_subdivided_tri(cdd, tm, t, arena);
2529 if (dbg_level > 1) {
2530 std::cout << "subdivide output for tri " << t << " = " << r_tri_subdivided[t];
2531 }
2532 }
2533 }
2534 /* Now have to put in the triangles that are the same as the input ones, and not in clusters.
2535 */
2536 threading::parallel_for(tm.face_index_range(), 2048, [&](IndexRange range) {
2537 for (int t : range) {
2538 if (r_tri_subdivided[t].face_size() == 0 && clinfo.tri_cluster(t) == NO_INDEX) {
2539 r_tri_subdivided[t] = IMesh({tm.face(t)});
2540 }
2541 }
2542 });
2543}
2544
2552static void calc_cluster_tris(Array<IMesh> &tri_subdivided,
2553 const IMesh &tm,
2554 const CoplanarClusterInfo &clinfo,
2555 const Span<CDT_data> cluster_subdivided,
2556 IMeshArena *arena)
2557{
2558 for (int c : clinfo.index_range()) {
2559 const CoplanarCluster &cl = clinfo.cluster(c);
2560 const CDT_data &cd = cluster_subdivided[c];
2561 /* Each triangle in cluster c should be an input triangle in cd.input_faces.
2562 * (See prepare_cdt_input_for_cluster.)
2563 * So accumulate a Vector of Face* for each input face by going through the
2564 * output faces and making a Face for each input face that it is part of.
2565 * (The Boolean algorithm wants duplicates if a given output triangle is part
2566 * of more than one input triangle.)
2567 */
2568 int n_cluster_tris = cl.tot_tri();
2569 const CDT_result<mpq_class> &cdt_out = cd.cdt_out;
2570 BLI_assert(cd.input_face.size() == n_cluster_tris);
2571 Array<Vector<Face *>> face_vec(n_cluster_tris);
2572 for (int cdt_out_t : cdt_out.face.index_range()) {
2573 for (int cdt_in_t : cdt_out.face_orig[cdt_out_t]) {
2574 Face *f = cdt_tri_as_imesh_face(cdt_out_t, cdt_in_t, cd, tm, arena);
2575 face_vec[cdt_in_t].append(f);
2576 }
2577 }
2578 for (int cdt_in_t : cd.input_face.index_range()) {
2579 int tm_t = cd.input_face[cdt_in_t];
2580 BLI_assert(tri_subdivided[tm_t].face_size() == 0);
2581 tri_subdivided[tm_t] = IMesh(face_vec[cdt_in_t]);
2582 }
2583 }
2584}
2585
2586static CDT_data calc_cluster_subdivided(const CoplanarClusterInfo &clinfo,
2587 int c,
2588 const IMesh &tm,
2589 const TriOverlaps &ov,
2590 const Map<std::pair<int, int>, ITT_value> &itt_map,
2591 IMeshArena * /*arena*/)
2592{
2593 constexpr int dbg_level = 0;
2594 BLI_assert(c < clinfo.tot_cluster());
2595 const CoplanarCluster &cl = clinfo.cluster(c);
2596 /* Make a CDT input with triangles from C and intersects from other triangles in tm. */
2597 if (dbg_level > 0) {
2598 std::cout << "CALC_CLUSTER_SUBDIVIDED for cluster " << c << " = " << cl << "\n";
2599 }
2600 /* Get vector itts of all intersections of a triangle of cl with any triangle of tm not
2601 * in cl and not co-planar with it (for that latter, if there were an intersection,
2602 * it should already be in cluster cl). */
2603 Vector<ITT_value> itts;
2604 Span<BVHTreeOverlap> ovspan = ov.overlap();
2605 for (int t : cl) {
2606 if (dbg_level > 0) {
2607 std::cout << "find intersects with triangle " << t << " of cluster\n";
2608 }
2609 int first_i = ov.first_overlap_index(t);
2610 if (first_i == -1) {
2611 continue;
2612 }
2613 for (int i = first_i; i < ovspan.size() && ovspan[i].indexA == t; ++i) {
2614 int t_other = ovspan[i].indexB;
2615 if (clinfo.tri_cluster(t_other) != c) {
2616 if (dbg_level > 0) {
2617 std::cout << "use intersect(" << t << "," << t_other << "\n";
2618 }
2619 std::pair<int, int> key = canon_int_pair(t, t_other);
2620 if (itt_map.contains(key)) {
2621 ITT_value itt = itt_map.lookup(key);
2622 if (!ELEM(itt.kind, INONE, ICOPLANAR)) {
2623 itts.append(itt);
2624 if (dbg_level > 0) {
2625 std::cout << " itt = " << itt << "\n";
2626 }
2627 }
2628 }
2629 }
2630 }
2631 }
2632 /* Use CDT to subdivide the cluster triangles and the points and segments in itts. */
2633 CDT_data cd_data = prepare_cdt_input_for_cluster(tm, clinfo, c, itts);
2634 do_cdt(cd_data);
2635 return cd_data;
2636}
2637
2638static IMesh union_tri_subdivides(const Array<IMesh> &tri_subdivided)
2639{
2640 int tot_tri = 0;
2641 for (const IMesh &m : tri_subdivided) {
2642 tot_tri += m.face_size();
2643 }
2644 Array<Face *> faces(tot_tri);
2645 int face_index = 0;
2646 for (const IMesh &m : tri_subdivided) {
2647 for (Face *f : m.faces()) {
2648 faces[face_index++] = f;
2649 }
2650 }
2651 return IMesh(faces);
2652}
2653
2654static CoplanarClusterInfo find_clusters(const IMesh &tm,
2655 const Array<BoundingBox> &tri_bb,
2656 const Map<std::pair<int, int>, ITT_value> &itt_map)
2657{
2658 constexpr int dbg_level = 0;
2659 if (dbg_level > 0) {
2660 std::cout << "FIND_CLUSTERS\n";
2661 }
2662 CoplanarClusterInfo ans(tm.face_size());
2663 /* Use a VectorSet to get stable order from run to run. */
2664 VectorSet<int> maybe_coplanar_tris;
2665 maybe_coplanar_tris.reserve(2 * itt_map.size());
2666 for (auto item : itt_map.items()) {
2667 if (item.value.kind == ICOPLANAR) {
2668 int t1 = item.key.first;
2669 int t2 = item.key.second;
2670 maybe_coplanar_tris.add_multiple({t1, t2});
2671 }
2672 }
2673 if (dbg_level > 0) {
2674 std::cout << "found " << maybe_coplanar_tris.size() << " possible coplanar tris\n";
2675 }
2676 if (maybe_coplanar_tris.is_empty()) {
2677 if (dbg_level > 0) {
2678 std::cout << "No possible coplanar tris, so no clusters\n";
2679 }
2680 return ans;
2681 }
2682 /* There can be more than one #CoplanarCluster per plane. Accumulate them in
2683 * a Vector. We will have to merge some elements of the Vector as we discover
2684 * triangles that form intersection bridges between two or more clusters. */
2685 Map<Plane, Vector<CoplanarCluster>> plane_cls;
2686 plane_cls.reserve(maybe_coplanar_tris.size());
2687 for (int t : maybe_coplanar_tris) {
2688 /* Use a canonical version of the plane for map index.
2689 * We can't just store the canonical version in the face
2690 * since canonicalizing loses the orientation of the normal. */
2691 Plane tplane = *tm.face(t)->plane;
2692 BLI_assert(tplane.exact_populated());
2693 tplane.make_canonical();
2694 if (dbg_level > 0) {
2695 std::cout << "plane for tri " << t << " = " << &tplane << "\n";
2696 }
2697 /* Assume all planes are in canonical from (see canon_plane()). */
2698 if (plane_cls.contains(tplane)) {
2699 Vector<CoplanarCluster> &curcls = plane_cls.lookup(tplane);
2700 if (dbg_level > 0) {
2701 std::cout << "already has " << curcls.size() << " clusters\n";
2702 }
2703 /* Partition `curcls` into those that intersect t non-trivially, and those that don't. */
2704 Vector<CoplanarCluster *> int_cls;
2705 Vector<CoplanarCluster *> no_int_cls;
2706 for (CoplanarCluster &cl : curcls) {
2707 if (dbg_level > 1) {
2708 std::cout << "consider intersecting with cluster " << cl << "\n";
2709 }
2710 if (bbs_might_intersect(tri_bb[t], cl.bounding_box())) {
2711 if (dbg_level > 1) {
2712 std::cout << "append to int_cls\n";
2713 }
2714 int_cls.append(&cl);
2715 }
2716 else {
2717 if (dbg_level > 1) {
2718 std::cout << "append to no_int_cls\n";
2719 }
2720 no_int_cls.append(&cl);
2721 }
2722 }
2723 if (int_cls.is_empty()) {
2724 /* t doesn't intersect any existing cluster in its plane, so make one just for it. */
2725 if (dbg_level > 1) {
2726 std::cout << "no intersecting clusters for t, make a new one\n";
2727 }
2728 curcls.append(CoplanarCluster(t, tri_bb[t]));
2729 }
2730 else if (int_cls.size() == 1) {
2731 /* t intersects exactly one existing cluster, so can add t to that cluster. */
2732 if (dbg_level > 1) {
2733 std::cout << "exactly one existing cluster, " << int_cls[0] << ", adding to it\n";
2734 }
2735 int_cls[0]->add_tri(t, tri_bb[t]);
2736 }
2737 else {
2738 /* t intersections 2 or more existing clusters: need to merge them and replace all the
2739 * originals with the merged one in `curcls`. */
2740 if (dbg_level > 1) {
2741 std::cout << "merging\n";
2742 }
2743 CoplanarCluster mergecl;
2744 mergecl.add_tri(t, tri_bb[t]);
2745 for (CoplanarCluster *cl : int_cls) {
2746 for (int t : *cl) {
2747 mergecl.add_tri(t, tri_bb[t]);
2748 }
2749 }
2750 Vector<CoplanarCluster> newvec;
2751 newvec.append(mergecl);
2752 for (CoplanarCluster *cl_no_int : no_int_cls) {
2753 newvec.append(*cl_no_int);
2754 }
2755 plane_cls.add_overwrite(tplane, newvec);
2756 }
2757 }
2758 else {
2759 if (dbg_level > 0) {
2760 std::cout << "first cluster for its plane\n";
2761 }
2762 plane_cls.add_new(tplane, Vector<CoplanarCluster>{CoplanarCluster(t, tri_bb[t])});
2763 }
2764 }
2765 /* Does this give deterministic order for cluster ids? I think so, since
2766 * hash for planes is on their values, not their addresses. */
2767 for (auto item : plane_cls.items()) {
2768 for (const CoplanarCluster &cl : item.value) {
2769 if (cl.tot_tri() > 1) {
2770 ans.add_cluster(cl);
2771 }
2772 }
2773 }
2774
2775 return ans;
2776}
2777
2778/* Data and functions to test triangle degeneracy in parallel. */
2779struct DegenData {
2780 const IMesh &tm;
2781};
2782
2783struct DegenChunkData {
2784 bool has_degenerate_tri = false;
2785};
2786
2787static void degenerate_range_func(void *__restrict userdata,
2788 const int iter,
2789 const TaskParallelTLS *__restrict tls)
2790{
2791 DegenData *data = static_cast<DegenData *>(userdata);
2792 DegenChunkData *chunk_data = static_cast<DegenChunkData *>(tls->userdata_chunk);
2793 const Face *f = data->tm.face(iter);
2794 bool is_degenerate = face_is_degenerate(f);
2795 chunk_data->has_degenerate_tri |= is_degenerate;
2796}
2797
2798static void degenerate_reduce(const void *__restrict /*userdata*/,
2799 void *__restrict chunk_join,
2800 void *__restrict chunk)
2801{
2802 DegenChunkData *degen_chunk_join = static_cast<DegenChunkData *>(chunk_join);
2803 DegenChunkData *degen_chunk = static_cast<DegenChunkData *>(chunk);
2804 degen_chunk_join->has_degenerate_tri |= degen_chunk->has_degenerate_tri;
2805}
2806
2807/* Does triangle #IMesh tm have any triangles with zero area? */
2808static bool has_degenerate_tris(const IMesh &tm)
2809{
2810 DegenData degen_data = {tm};
2811 DegenChunkData degen_chunk_data;
2812 TaskParallelSettings settings;
2814 settings.userdata_chunk = &degen_chunk_data;
2815 settings.userdata_chunk_size = sizeof(degen_chunk_data);
2816 settings.func_reduce = degenerate_reduce;
2817 settings.min_iter_per_thread = 1000;
2818 settings.use_threading = intersect_use_threading;
2819 BLI_task_parallel_range(0, tm.face_size(), &degen_data, degenerate_range_func, &settings);
2820 return degen_chunk_data.has_degenerate_tri;
2821}
2822
2823static IMesh remove_degenerate_tris(const IMesh &tm_in)
2824{
2825 IMesh ans;
2826 Vector<Face *> new_faces;
2827 new_faces.reserve(tm_in.face_size());
2828 for (Face *f : tm_in.faces()) {
2829 if (!face_is_degenerate(f)) {
2830 new_faces.append(f);
2831 }
2832 }
2833 ans.set_faces(new_faces);
2834 return ans;
2835}
2836
2837IMesh trimesh_self_intersect(const IMesh &tm_in, IMeshArena *arena)
2838{
2839 return trimesh_nary_intersect(tm_in, 1, [](int /*t*/) { return 0; }, true, arena);
2840}
2841
2842IMesh trimesh_nary_intersect(const IMesh &tm_in,
2843 int nshapes,
2844 const FunctionRef<int(int)> shape_fn,
2845 bool use_self,
2846 IMeshArena *arena)
2847{
2848 constexpr int dbg_level = 0;
2849 if (dbg_level > 0) {
2850 std::cout << "\nTRIMESH_NARY_INTERSECT nshapes=" << nshapes << " use_self=" << use_self
2851 << "\n";
2852 for (const Face *f : tm_in.faces()) {
2853 BLI_assert(f->is_tri());
2855 }
2856 if (dbg_level > 1) {
2857 std::cout << "input mesh:\n" << tm_in;
2858 for (int t : tm_in.face_index_range()) {
2859 std::cout << "shape(" << t << ") = " << shape_fn(tm_in.face(t)->orig) << "\n";
2860 }
2861 write_obj_mesh(const_cast<IMesh &>(tm_in), "trimesh_input");
2862 }
2863 }
2864# ifdef PERFDEBUG
2865 perfdata_init();
2866 double start_time = BLI_time_now_seconds();
2867 std::cout << "trimesh_nary_intersect start\n";
2868# endif
2869 /* Usually can use tm_in but if it has degenerate or illegal triangles,
2870 * then need to work on a copy of it without those triangles. */
2871 const IMesh *tm_clean = &tm_in;
2872 IMesh tm_cleaned;
2873 if (has_degenerate_tris(tm_in)) {
2874 if (dbg_level > 0) {
2875 std::cout << "cleaning degenerate triangles\n";
2876 }
2877 tm_cleaned = remove_degenerate_tris(tm_in);
2878 tm_clean = &tm_cleaned;
2879 if (dbg_level > 1) {
2880 std::cout << "cleaned input mesh:\n" << tm_cleaned;
2881 }
2882 }
2883# ifdef PERFDEBUG
2884 double clean_time = BLI_time_now_seconds();
2885 std::cout << "cleaned, time = " << clean_time - start_time << "\n";
2886# endif
2887 Array<BoundingBox> tri_bb = calc_face_bounding_boxes(*tm_clean);
2888# ifdef PERFDEBUG
2889 double bb_calc_time = BLI_time_now_seconds();
2890 std::cout << "bbs calculated, time = " << bb_calc_time - clean_time << "\n";
2891# endif
2892 TriOverlaps tri_ov(*tm_clean, tri_bb, nshapes, shape_fn, use_self);
2893# ifdef PERFDEBUG
2894 double overlap_time = BLI_time_now_seconds();
2895 std::cout << "intersect overlaps calculated, time = " << overlap_time - bb_calc_time << "\n";
2896# endif
2897 Array<IMesh> tri_subdivided(tm_clean->face_size(), NoInitialization());
2898 threading::parallel_for(tm_clean->face_index_range(), 1024, [&](IndexRange range) {
2899 for (int t : range) {
2900 if (tri_ov.first_overlap_index(t) != -1) {
2901 tm_clean->face(t)->populate_plane(true);
2902 }
2903 new (static_cast<void *>(&tri_subdivided[t])) IMesh;
2904 }
2905 });
2906# ifdef PERFDEBUG
2907 double plane_populate = BLI_time_now_seconds();
2908 std::cout << "planes populated, time = " << plane_populate - overlap_time << "\n";
2909# endif
2910 /* itt_map((a,b)) will hold the intersection value resulting from intersecting
2911 * triangles with indices a and b, where a < b. */
2912 Map<std::pair<int, int>, ITT_value> itt_map;
2913 itt_map.reserve(tri_ov.overlap().size());
2914 calc_overlap_itts(itt_map, *tm_clean, tri_ov, arena);
2915# ifdef PERFDEBUG
2916 double itt_time = BLI_time_now_seconds();
2917 std::cout << "itts found, time = " << itt_time - plane_populate << "\n";
2918# endif
2919 CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb, itt_map);
2920 if (dbg_level > 1) {
2921 std::cout << clinfo;
2922 }
2923# ifdef PERFDEBUG
2924 double find_cluster_time = BLI_time_now_seconds();
2925 std::cout << "clusters found, time = " << find_cluster_time - itt_time << "\n";
2926 doperfmax(0, tm_in.face_size());
2927 doperfmax(1, clinfo.tot_cluster());
2928 doperfmax(2, tri_ov.overlap().size());
2929# endif
2930 calc_subdivided_non_cluster_tris(tri_subdivided, *tm_clean, itt_map, clinfo, tri_ov, arena);
2931# ifdef PERFDEBUG
2932 double subdivided_tris_time = BLI_time_now_seconds();
2933 std::cout << "subdivided non-cluster tris found, time = " << subdivided_tris_time - itt_time
2934 << "\n";
2935# endif
2936 Array<CDT_data> cluster_subdivided(clinfo.tot_cluster());
2937 for (int c : clinfo.index_range()) {
2938 cluster_subdivided[c] = calc_cluster_subdivided(clinfo, c, *tm_clean, tri_ov, itt_map, arena);
2939 }
2940# ifdef PERFDEBUG
2941 double cluster_subdivide_time = BLI_time_now_seconds();
2942 std::cout << "subdivided clusters found, time = "
2943 << cluster_subdivide_time - subdivided_tris_time << "\n";
2944# endif
2945 calc_cluster_tris(tri_subdivided, *tm_clean, clinfo, cluster_subdivided, arena);
2946# ifdef PERFDEBUG
2947 double extract_time = BLI_time_now_seconds();
2948 std::cout << "subdivided cluster tris found, time = " << extract_time - cluster_subdivide_time
2949 << "\n";
2950# endif
2951 IMesh combined = union_tri_subdivides(tri_subdivided);
2952 if (dbg_level > 1) {
2953 std::cout << "TRIMESH_NARY_INTERSECT answer:\n";
2954 std::cout << combined;
2955 }
2956# ifdef PERFDEBUG
2957 double end_time = BLI_time_now_seconds();
2958 std::cout << "triangles combined, time = " << end_time - extract_time << "\n";
2959 std::cout << "trimesh_nary_intersect done, total time = " << end_time - start_time << "\n";
2960 dump_perfdata();
2961# endif
2962 return combined;
2963}
2964
2965static std::ostream &operator<<(std::ostream &os, const CoplanarCluster &cl)
2966{
2967 os << "cl(";
2968 bool first = true;
2969 for (const int t : cl) {
2970 if (first) {
2971 first = false;
2972 }
2973 else {
2974 os << ",";
2975 }
2976 os << t;
2977 }
2978 os << ")";
2979 return os;
2980}
2981
2982static std::ostream &operator<<(std::ostream &os, const CoplanarClusterInfo &clinfo)
2983{
2984 os << "Coplanar Cluster Info:\n";
2985 for (int c : clinfo.index_range()) {
2986 os << c << ": " << clinfo.cluster(c) << "\n";
2987 }
2988 return os;
2989}
2990
2991static std::ostream &operator<<(std::ostream &os, const ITT_value &itt)
2992{
2993 switch (itt.kind) {
2994 case INONE:
2995 os << "none";
2996 break;
2997 case IPOINT:
2998 os << "point " << itt.p1;
2999 break;
3000 case ISEGMENT:
3001 os << "segment " << itt.p1 << " " << itt.p2;
3002 break;
3003 case ICOPLANAR:
3004 os << "co-planar t" << itt.t_source;
3005 break;
3006 }
3007 return os;
3008}
3009
3010void write_obj_mesh(IMesh &m, const std::string &objname)
3011{
3012 /* Would like to use #BKE_tempdir_base() here, but that brings in dependence on kernel library.
3013 * This is just for developer debugging anyway,
3014 * and should never be called in production Blender. */
3015# ifdef _WIN_32
3016 const char *objdir = BLI_dir_home();
3017 if (objdir == nullptr) {
3018 std::cout << "Could not access home directory\n";
3019 return;
3020 }
3021# else
3022 const char *objdir = "/tmp/";
3023# endif
3024
3025 if (m.face_size() == 0) {
3026 return;
3027 }
3028
3029 std::string fname = std::string(objdir) + objname + std::string(".obj");
3030 std::ofstream f;
3031 f.open(fname);
3032 if (!f) {
3033 std::cout << "Could not open file " << fname << "\n";
3034 return;
3035 }
3036
3037 if (!m.has_verts()) {
3038 m.populate_vert();
3039 }
3040 for (const Vert *v : m.vertices()) {
3041 const double3 dv = v->co;
3042 f << "v " << dv[0] << " " << dv[1] << " " << dv[2] << "\n";
3043 }
3044 for (const Face *face : m.faces()) {
3045 /* OBJ files use 1-indexing for vertices. */
3046 f << "f ";
3047 for (const Vert *v : *face) {
3048 int i = m.lookup_vert(v);
3049 BLI_assert(i != NO_INDEX);
3050 /* OBJ files use 1-indexing for vertices. */
3051 f << i + 1 << " ";
3052 }
3053 f << "\n";
3054 }
3055 f.close();
3056}
3057
3058# ifdef PERFDEBUG
3059struct PerfCounts {
3060 Vector<int> count;
3061 Vector<const char *> count_name;
3062 Vector<int> max;
3063 Vector<const char *> max_name;
3064};
3065
3066static PerfCounts *perfdata = nullptr;
3067
3068static void perfdata_init()
3069{
3070 perfdata = new PerfCounts;
3071
3072 /* count 0. */
3073 perfdata->count.append(0);
3074 perfdata->count_name.append("Non-cluster overlaps");
3075
3076 /* count 1. */
3077 perfdata->count.append(0);
3078 perfdata->count_name.append("intersect_tri_tri calls");
3079
3080 /* count 2. */
3081 perfdata->count.append(0);
3082 perfdata->count_name.append("tri tri intersects decided by filter plane tests");
3083
3084 /* count 3. */
3085 perfdata->count.append(0);
3086 perfdata->count_name.append("tri tri intersects decided by exact plane tests");
3087
3088 /* count 4. */
3089 perfdata->count.append(0);
3090 perfdata->count_name.append("final non-NONE intersects");
3091
3092 /* max 0. */
3093 perfdata->max.append(0);
3094 perfdata->max_name.append("total faces");
3095
3096 /* max 1. */
3097 perfdata->max.append(0);
3098 perfdata->max_name.append("total clusters");
3099
3100 /* max 2. */
3101 perfdata->max.append(0);
3102 perfdata->max_name.append("total overlaps");
3103}
3104
3105static void incperfcount(int countnum)
3106{
3107 perfdata->count[countnum]++;
3108}
3109
3110static void bumpperfcount(int countnum, int amt)
3111{
3112 perfdata->count[countnum] += amt;
3113}
3114
3115static void doperfmax(int maxnum, int val)
3116{
3117 perfdata->max[maxnum] = max_ii(perfdata->max[maxnum], val);
3118}
3119
3120static void dump_perfdata()
3121{
3122 std::cout << "\nPERFDATA\n";
3123 for (int i : perfdata->count.index_range()) {
3124 std::cout << perfdata->count_name[i] << " = " << perfdata->count[i] << "\n";
3125 }
3126 for (int i : perfdata->max.index_range()) {
3127 std::cout << perfdata->max_name[i] << " = " << perfdata->max[i] << "\n";
3128 }
3129 delete perfdata;
3130}
3131# endif
3132
3133} // namespace blender::meshintersect
3134
3135#endif // WITH_GMP
File and directory operations.
int pad[32 - sizeof(int)]
volatile int lock
#define UNUSED_VARS_NDEBUG(...)
#define BLI_assert(a)
#define ELEM(...)
#define MEM_realloc_uninitialized(vmemh, len)
long long int int64_t
unsigned long long int uint64_t
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition btDbvt.cpp:52
btScalar max
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
Definition btVector3.h:263
constexpr Span()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
std::ostream & operator<<(std::ostream &os, DeviceKernel kernel)
#define FLT_EPSILON
#define index(i)
#define UINT_MAX
Definition hash_md5.cc:46
if(state< num_states)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str)
Definition mallocn.cc:129
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
ccl_device_inline bool operator==(const float2 a, const float2 b)
ccl_device_inline void copy_v3_v3(ccl_private float *r, const float3 val)
constexpr ParallelGrainSize grain_size(int grain_size)
const MultiFunction & lookup(UString id)
CDT_result< T > delaunay_2d_calc(const CDT_input< T > &input, CDT_output_type output_type)
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
unsigned int uint
Definition BKE_text.h:55
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
void BLI_bvhtree_free(BVHTree *tree)
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
void BLI_bvhtree_balance(BVHTree *tree)
MINLINE int max_ii(int a, int b)
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
ATTR_WARN_UNUSED_RESULT const BMVert * v
const char * BLI_dir_home()
Definition storage.cc:99
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
Definition BLI_sort.hh:37
unsigned int uint32_t
Definition BKE_text.h:81
BMesh const char void * data
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
MINLINE double max_dd(double a, double b)
VecBase< double, 3 > double3
ATTR_WARN_UNUSED_RESULT const size_t num
MINLINE float normalize_v3(float n[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
iter begin(iter)
std::mutex Mutex
Definition BLI_mutex.hh:51
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
double BLI_time_now_seconds()
Definition time.cc:30
bool isect_aabb_aabb_v3(const float min1[3], const float max1[3], const float min2[3], const float max2[3])
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
void vert(const int vert_id, float4 &position)
#define hash
Definition noise_c.cc:156
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float