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();
61static constexpr bool intersect_use_threading =
true;
63Vert::Vert(
const mpq3 &mco,
const double3 &dco,
int id,
int orig)
64 : co_exact(mco), co(dco), id(id), orig(orig)
68bool Vert::operator==(
const Vert &other)
const
70 return this->co_exact == other.co_exact;
78 x = (
x >> 56) ^ (
x >> 46) ^
x;
79 y = (
y >> 55) ^ (
y >> 45) ^
y;
80 z = (
z >> 54) ^ (
z >> 44) ^
z;
84std::ostream &
operator<<(std::ostream &os,
const Vert *v)
86 constexpr int dbg_level = 0;
88 if (
v->orig != NO_INDEX) {
93 os <<
"=" <<
v->co_exact;
98bool Plane::operator==(
const Plane &other)
const
100 return norm_exact == other.norm_exact && d_exact == other.d_exact;
103void Plane::make_canonical()
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;
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;
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;
126 norm =
double3(norm_exact[0].get_d(), norm_exact[1].get_d(), norm_exact[2].get_d());
130Plane::Plane(
const mpq3 &norm_exact,
const mpq_class &d_exact)
131 : norm_exact(norm_exact), d_exact(d_exact)
133 norm =
double3(norm_exact[0].get_d(), norm_exact[1].get_d(), norm_exact[2].get_d());
137Plane::Plane(
const double3 &
norm,
const double d) :
norm(
norm), d(d)
139 norm_exact = mpq3(0, 0, 0);
142bool Plane::exact_populated()
const
144 return norm_exact[0] != 0 || norm_exact[1] != 0 || norm_exact[2] != 0;
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;
160std::ostream &
operator<<(std::ostream &os,
const Plane *plane)
162 os <<
"[" << plane->norm <<
";" << plane->d <<
"]";
168 :
vert(verts), edge_orig(edge_origs), is_intersect(is_intersect), id(id), orig(orig)
174void Face::populate_plane(
bool need_exact)
176 if (plane !=
nullptr) {
177 if (!need_exact || plane->exact_populated()) {
183 if (
vert.size() > 3) {
184 Array<mpq3> co(
vert.size());
185 for (
int i : index_range()) {
186 co[i] =
vert[i]->co_exact;
188 normal_exact = math::cross_poly(co.as_span());
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);
195 mpq_class d_exact = -math::dot(normal_exact, vert[0]->co_exact);
196 plane =
new Plane(normal_exact, d_exact);
200 if (
vert.size() > 3) {
201 Array<double3> co(
vert.size());
202 for (
int i : index_range()) {
205 normal = math::cross_poly(co.as_span());
210 normal = math::cross(tr02, tr12);
212 double d = -math::dot(normal, vert[0]->co);
213 plane =
new Plane(normal, d);
222bool Face::operator==(
const Face &other)
const
224 if (this->
size() != other.size()) {
227 for (FacePos i : index_range()) {
230 if (this->vert[i] != other.vert[i]) {
237bool Face::cyclic_equal(
const Face &other)
const
239 if (this->
size() != other.size()) {
242 int flen = this->
size();
243 for (FacePos start : index_range()) {
244 for (FacePos start_other : index_range()) {
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]) {
261std::ostream &
operator<<(std::ostream &os,
const Face *f)
263 os <<
"f" << f->id <<
"o" << f->orig <<
"[";
264 for (
const Vert *v : *f) {
266 if (v != f->vert[f->size() - 1]) {
271 if (f->orig != NO_INDEX) {
272 os <<
"o" << f->orig;
275 for (
int i : f->index_range()) {
276 os << f->edge_orig[i];
277 if (f->is_intersect[i]) {
280 if (i != f->size() - 1) {
295class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
305 VSetKey(Vert *p) :
vert(p) {}
314 return *this->
vert == *other.vert;
325 Vector<std::unique_ptr<Vert>> allocated_verts_;
326 Vector<std::unique_ptr<Face>> allocated_faces_;
329 int next_vert_id_ = 0;
330 int next_face_id_ = 0;
336 void reserve(
int vert_num_hint,
int face_num_hint)
338 vset_.reserve(vert_num_hint);
339 allocated_verts_.reserve(vert_num_hint);
340 allocated_faces_.reserve(face_num_hint);
343 int tot_allocated_verts()
const
345 return allocated_verts_.size();
348 int tot_allocated_faces()
const
350 return allocated_faces_.size();
353 const Vert *add_or_find_vert(
const mpq3 &co,
int orig)
355 double3 dco(co[0].get_d(), co[1].get_d(), co[2].get_d());
356 return add_or_find_vert(co, dco, orig);
359 const Vert *add_or_find_vert(
const double3 &co,
int orig)
361 mpq3 mco(co[0], co[1], co[2]);
362 return add_or_find_vert(mco, co, orig);
365 const Vert *add_or_find_vert(Vert *vert)
367 return add_or_find_vert_(vert);
370 Face *add_face(Span<const Vert *> verts,
int orig, Span<int> edge_origs, Span<bool> is_intersect)
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));
378 Face *add_face(Span<const Vert *> verts,
int orig, Span<int> edge_origs)
380 Array<bool> is_intersect(verts.
size(),
false);
381 return add_face(verts, orig, edge_origs, is_intersect);
384 Face *add_face(Span<const Vert *> verts,
int orig)
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);
391 const Vert *find_vert(
const mpq3 &co)
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);
408 const Face *find_face(Span<const Vert *> vs)
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();
422 const Vert *add_or_find_vert(
const mpq3 &mco,
const double3 &dco,
int orig)
424 Vert *vtry =
new Vert(mco, dco, NO_INDEX, NO_INDEX);
427 std::lock_guard
lock(mutex_);
428 const VSetKey *
lookup = vset_.lookup_key_ptr(vskey);
430 vtry->id = next_vert_id_++;
433 vset_.add_new(vskey);
434 allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
449 const Vert *add_or_find_vert_(Vert *vtry)
453 std::lock_guard
lock(mutex_);
454 const VSetKey *
lookup = vset_.lookup_key_ptr(vskey);
456 vtry->id = next_vert_id_++;
458 vset_.add_new(vskey);
459 allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
475IMeshArena::IMeshArena()
477 pimpl_ = std::make_unique<IMeshArenaImpl>();
480IMeshArena::~IMeshArena() =
default;
482void IMeshArena::reserve(
int vert_num_hint,
int face_num_hint)
484 pimpl_->reserve(vert_num_hint, face_num_hint);
487int IMeshArena::tot_allocated_verts()
const
489 return pimpl_->tot_allocated_verts();
492int IMeshArena::tot_allocated_faces()
const
494 return pimpl_->tot_allocated_faces();
497const Vert *IMeshArena::add_or_find_vert(
const mpq3 &co,
int orig)
499 return pimpl_->add_or_find_vert(co, orig);
502const Vert *IMeshArena::add_or_find_vert(Vert *vert)
504 return pimpl_->add_or_find_vert(vert);
512 return pimpl_->add_face(verts, orig, edge_origs, is_intersect);
517 return pimpl_->add_face(verts, orig, edge_origs);
522 return pimpl_->add_face(verts, orig);
525const Vert *IMeshArena::add_or_find_vert(
const double3 &co,
int orig)
527 return pimpl_->add_or_find_vert(co, orig);
530const Vert *IMeshArena::find_vert(
const mpq3 &co)
const
532 return pimpl_->find_vert(co);
537 return pimpl_->find_face(verts);
545void IMesh::populate_vert()
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);
554void IMesh::populate_vert(
int max_verts)
556 if (vert_populated_) {
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) {
565 int index = vert_to_index_.lookup_default(v, NO_INDEX);
566 if (
index == NO_INDEX) {
568 vert_to_index_.add(v, next_allocate_index++);
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;
577 vert_[
index] = item.key;
582 const bool fix_order =
true;
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;
588 if (a->orig != NO_INDEX) {
591 if (
b->orig != NO_INDEX) {
594 return a->id <
b->id;
596 for (
int i : vert_.index_range()) {
597 const Vert *
v = vert_[i];
598 vert_to_index_.add_overwrite(v, i);
601 vert_populated_ =
true;
604bool IMesh::erase_face_positions(
int f_index,
Span<bool> face_pos_erase, IMeshArena *arena)
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]) {
614 if (to_erase_num == 0) {
617 int new_len = cur_len - to_erase_num;
625 this->face_[f_index] =
nullptr;
628 Array<const Vert *> new_vert(new_len);
629 Array<int> new_edge_orig(new_len);
630 Array<bool> new_is_intersect(new_len);
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];
641 this->face_[f_index] = arena->add_face(new_vert, cur_f->orig, new_edge_orig, new_is_intersect);
645void IMesh::remove_null_faces()
648 for (Face *f : this->face_) {
653 if (nullcount == 0) {
656 int64_t new_size = this->face_.size() - nullcount;
659 Array<Face *> new_face(new_size);
660 while (copy_from_index < face_.size()) {
661 Face *f_from = face_[copy_from_index++];
663 new_face[copy_to_index++] = f_from;
666 this->face_ = new_face;
669std::ostream &
operator<<(std::ostream &os,
const IMesh &mesh)
671 if (mesh.has_verts()) {
674 for (
const Vert *v : mesh.vertices()) {
675 os << i <<
": " <<
v <<
"\n";
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] <<
" ";
707 double max_abs_val = 0.0;
712 Array<BoundingBox> *face_bounding_box;
714 BBCalcData(
const IMesh &im, Array<BoundingBox> *fbb) : im(im), face_bounding_box(fbb) {};
717static void calc_face_bb_range_func(
void *__restrict userdata,
719 const TaskParallelTLS *__restrict tls)
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) {
727 for (
int i = 0; i < 3; ++i) {
731 BBChunkData *chunk =
static_cast<BBChunkData *
>(tls->userdata_chunk);
732 chunk->max_abs_val =
max_dd(max_abs, chunk->max_abs_val);
736 Array<BoundingBox> *face_bounding_box;
739 BBPadData(Array<BoundingBox> *fbb,
double pad) : face_bounding_box(fbb),
pad(
pad) {};
742static void pad_face_bb_range_func(
void *__restrict userdata,
744 const TaskParallelTLS *__restrict )
746 BBPadData *pad_data =
static_cast<BBPadData *
>(userdata);
747 (*pad_data->face_bounding_box)[iter].expand(pad_data->pad);
750static void calc_face_bb_reduce(
const void *__restrict ,
751 void *__restrict chunk_join,
752 void *__restrict chunk)
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);
764static Array<BoundingBox> calc_face_bounding_boxes(
const IMesh &m)
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;
778 double max_abs_val = chunk_data.max_abs_val;
779 constexpr float pad_factor = 10.0f;
782 TaskParallelSettings pad_settings;
784 settings.min_iter_per_thread = 1000;
785 settings.use_threading = intersect_use_threading;
786 BBPadData pad_data(&ans,
pad);
800class CoplanarCluster {
805 CoplanarCluster() =
default;
806 CoplanarCluster(
int t,
const BoundingBox &bb)
808 this->add_tri(t, bb);
812 void add_tri(
int t,
const BoundingBox &bb)
821 int tri(
int index)
const
825 const int *
begin()
const
827 return tris_.begin();
829 const int *end()
const
846class CoplanarClusterInfo {
847 Vector<CoplanarCluster> clusters_;
848 Array<int> tri_cluster_;
851 CoplanarClusterInfo() =
default;
852 explicit CoplanarClusterInfo(
int numtri) : tri_cluster_(
Array<int>(numtri))
854 tri_cluster_.fill(-1);
857 int tri_cluster(
int t)
const
860 return tri_cluster_[t];
863 int add_cluster(
const CoplanarCluster &cl)
865 int c_index = clusters_.append_and_get_index(cl);
868 tri_cluster_[t] = c_index;
873 int tot_cluster()
const
875 return clusters_.size();
878 const CoplanarCluster *
begin()
880 return clusters_.begin();
883 const CoplanarCluster *end()
885 return clusters_.end();
888 IndexRange index_range()
const
890 return clusters_.index_range();
893 const CoplanarCluster &cluster(
int index)
const
896 return clusters_[
index];
900static std::ostream &
operator<<(std::ostream &os,
const CoplanarCluster &cl);
902static std::ostream &
operator<<(std::ostream &os,
const CoplanarClusterInfo &clinfo);
904enum ITT_value_kind { INONE, IPOINT, ISEGMENT, ICOPLANAR };
910 enum ITT_value_kind kind = INONE;
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) {}
919static std::ostream &
operator<<(std::ostream &os,
const ITT_value &itt);
926static mpq2 project_3d_to_2d(
const mpq3 &p3d,
int proj_axis)
981static double supremum_dot_cross(
const double3 &a,
const double3 &
b)
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);
997constexpr int index_dot_plane_coords = 15;
1009constexpr int index_dot_cross = 11;
1019constexpr int index_plane_side = 3 + 2 * index_dot_plane_coords;
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)
1028 double d = math::dot(p - plane_p, plane_no);
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;
1056static inline mpq3 tti_interp(
1057 const mpq3 &a,
const mpq3 &
b,
const mpq3 &c,
const mpq3 &n, mpq3 &ab, mpq3 &ac, mpq3 &dotbuf)
1063 mpq_class den = math::dot_with_buffer(ab, n, dotbuf);
1065 mpq_class alpha = math::dot_with_buffer(ac, n, dotbuf) / den;
1066 return a - alpha * ab;
1076static inline int tti_above(
const mpq3 &a,
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;
1094 return sgn(math::dot_with_buffer(ad, n, dotbuf));
1110static ITT_value itt_canon2(
const mpq3 &p1,
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";
1135 mpq3 p1p2 = p2 - p1;
1139 bool no_overlap =
false;
1141 if (tti_above(p1, q1, r2, p1p2, buf[0], buf[1], buf[2], buf[3]) > 0) {
1143 if (tti_above(p1, r1, r2, p1p2, buf[0], buf[1], buf[2], buf[3]) <= 0) {
1145 if (tti_above(p1, r1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) > 0) {
1147 if (dbg_level > 0) {
1148 std::cout <<
"overlap [k [i l] j]\n";
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]);
1156 if (dbg_level > 0) {
1157 std::cout <<
"overlap [i [k l] j]\n";
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]);
1166 if (dbg_level > 0) {
1167 std::cout <<
"no overlap: [k l] [i j]\n";
1174 if (tti_above(p1, q1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) < 0) {
1176 if (dbg_level > 0) {
1177 std::cout <<
"no overlap: [i j] [k l]\n";
1183 if (tti_above(p1, r1, q2, p1p2, buf[0], buf[1], buf[2], buf[3]) >= 0) {
1185 if (dbg_level > 0) {
1186 std::cout <<
"overlap [k [i j] l]\n";
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]);
1194 if (dbg_level > 0) {
1195 std::cout <<
"overlap [i [k j] l]\n";
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]);
1204 return ITT_value(INONE);
1206 if (intersect_1 == intersect_2) {
1207 if (dbg_level > 0) {
1208 std::cout <<
"single intersect: " << intersect_1 <<
"\n";
1210 return ITT_value(IPOINT, intersect_1);
1212 if (dbg_level > 0) {
1213 std::cout <<
"intersect segment: " << intersect_1 <<
", " << intersect_2 <<
"\n";
1215 return ITT_value(ISEGMENT, intersect_1, intersect_2);
1220static ITT_value itt_canon1(
const mpq3 &p1,
1232 constexpr int dbg_level = 0;
1235 return itt_canon2(p1, r1, q1, r2, p2, q2, n1, n2);
1238 return itt_canon2(p1, r1, q1, q2, r2, p2, n1, n2);
1240 return itt_canon2(p1, q1, r1, p2, q2, r2, n1, n2);
1244 return itt_canon2(p1, q1, r1, r2, p2, q2, n1, n2);
1247 return itt_canon2(p1, q1, r1, q2, r2, p2, n1, n2);
1249 return itt_canon2(p1, r1, q1, p2, q2, r2, n1, n2);
1253 return itt_canon2(p1, r1, q1, q2, r2, p2, n1, n2);
1255 return itt_canon2(p1, q1, r1, p2, q2, r2, n1, n2);
1259 return itt_canon2(p1, r1, q1, p2, q2, r2, n1, n2);
1261 return itt_canon2(p1, q1, r1, q2, r2, p2, n1, n2);
1264 return itt_canon2(p1, q1, r1, r2, p2, q2, n1, n2);
1267 return itt_canon2(p1, r1, q1, r2, p2, q2, n1, n2);
1269 if (dbg_level > 0) {
1270 std::cout <<
"triangles are co-planar\n";
1272 return ITT_value(ICOPLANAR);
1275static ITT_value intersect_tri_tri(
const IMesh &tm,
int t1,
int t2)
1277 constexpr int dbg_level = 0;
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";
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;
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);
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)) {
1326 if (dbg_level > 0) {
1327 std::cout <<
"no intersection, all t1's verts above or below t2\n";
1329 return ITT_value(INONE);
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);
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)) {
1344 if (dbg_level > 0) {
1345 std::cout <<
"no intersection, all t2's verts above or below t1\n";
1347 return ITT_value(INONE);
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;
1358 const mpq3 &n2 = tri2.plane->norm_exact;
1362 sp1 = sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1367 sq1 = sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1372 sr1 = sgn(math::dot_with_buffer(buf[0], n2, buf[1]));
1375 if (dbg_level > 1) {
1376 std::cout <<
" sp1=" << sp1 <<
" sq1=" << sq1 <<
" sr1=" << sr1 <<
"\n";
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";
1386 return ITT_value(INONE);
1390 const mpq3 &n1 = tri1.plane->norm_exact;
1394 sp2 = sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1399 sq2 = sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1404 sr2 = sgn(math::dot_with_buffer(buf[0], n1, buf[1]));
1407 if (dbg_level > 1) {
1408 std::cout <<
" sp2=" << sp2 <<
" sq2=" << sq2 <<
" sr2=" << sr2 <<
"\n";
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";
1418 return ITT_value(INONE);
1427 ans = itt_canon1(r1, p1, q1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1430 ans = itt_canon1(q1, r1, p1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1433 ans = itt_canon1(p1, q1, r1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1438 ans = itt_canon1(r1, p1, q1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1441 ans = itt_canon1(q1, r1, p1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1444 ans = itt_canon1(p1, q1, r1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1450 ans = itt_canon1(q1, r1, p1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1453 ans = itt_canon1(p1, q1, r1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1458 ans = itt_canon1(p1, q1, r1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1461 ans = itt_canon1(q1, r1, p1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1466 ans = itt_canon1(r1, p1, q1, p2, q2, r2, n1, n2, sp2, sq2, sr2);
1469 ans = itt_canon1(r1, p1, q1, p2, r2, q2, n1, n2, sp2, sr2, sq2);
1472 if (dbg_level > 0) {
1473 std::cout <<
"triangles are co-planar\n";
1475 ans = ITT_value(ICOPLANAR);
1479 if (ans.kind == ICOPLANAR) {
1484 if (ans.kind != INONE) {
1492 const Plane *t_plane;
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;
1513static int prepare_need_vert(CDT_data &cd,
const mpq3 &p3d)
1515 mpq2 p2d = project_3d_to_2d(p3d, cd.proj_axis);
1516 int v = cd.vert.append_and_get_index(p2d);
1527static mpq3 unproject_cdt_vert(
const CDT_data &cd,
const mpq2 &p2d)
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) {
1536 mpq_class
num = n[1] * p2d[0] + n[2] * p2d[1] + d;
1538 p3d[0] =
num / n[0];
1545 mpq_class
num = n[0] * p2d[0] + n[2] * p2d[1] + d;
1547 p3d[1] =
num / n[1];
1554 mpq_class
num = n[0] * p2d[0] + n[1] * p2d[1] + d;
1556 p3d[2] =
num / n[2];
1565static void prepare_need_edge(CDT_data &cd,
const mpq3 &p1,
const mpq3 &p2)
1567 int v1 = prepare_need_vert(cd, p1);
1568 int v2 = prepare_need_vert(cd, p2);
1569 cd.edge.append(
int2(v1, v2));
1572static void prepare_need_tri(CDT_data &cd,
const IMesh &tm,
int t)
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);
1582 if (tri.plane->norm_exact[cd.proj_axis] >= 0) {
1583 rev = cd.proj_axis == 1;
1586 rev = cd.proj_axis != 1;
1588 cd.face_offsets.append(cd.face_vert_indices.size());
1589 cd.face_vert_indices.append(v0);
1591 cd.face_vert_indices.append(v2);
1592 cd.face_vert_indices.append(v1);
1595 cd.face_vert_indices.append(v1);
1596 cd.face_vert_indices.append(v2);
1598 cd.input_face.append(t);
1599 cd.is_reversed.append(rev);
1602static CDT_data prepare_cdt_input(
const IMesh &tm,
int t,
const Span<ITT_value> itts)
1606 ans.t_plane = tm.face(t)->plane;
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) {
1615 prepare_need_vert(ans, itt.p1);
1619 prepare_need_edge(ans, itt.p1, itt.p2);
1623 prepare_need_tri(ans, tm, itt.t_source);
1628 ans.face_offsets.append(ans.face_vert_indices.size());
1632static CDT_data prepare_cdt_input_for_cluster(
const IMesh &tm,
1633 const CoplanarClusterInfo &clinfo,
1639 const CoplanarCluster &cl = clinfo.cluster(c);
1643 ans.t_plane = tm.face(t0)->plane;
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);
1649 for (
const ITT_value &itt : itts) {
1652 prepare_need_vert(ans, itt.p1);
1656 prepare_need_edge(ans, itt.p1, itt.p2);
1663 ans.face_offsets.append(ans.face_vert_indices.size());
1671static void populate_cdt_edge_map(Map<OrderedEdge, int> &verts_to_edge,
1672 const CDT_result<mpq_class> &cdt_out)
1674 verts_to_edge.reserve(cdt_out.edge.size());
1675 for (
int e : cdt_out.edge.index_range()) {
1677 verts_to_edge.add(OrderedEdge(cdt_out.edge[e]), e);
1684static void do_cdt(CDT_data &cd)
1686 constexpr int dbg_level = 0;
1687 CDT_input<mpq_class> cdt_in;
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";
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";
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] <<
" ";
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);
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";
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] <<
" ";
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] <<
" ";
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]
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] <<
" ";
1760static int get_cdt_edge_orig(
1761 int i0,
int i1,
const CDT_data &cd,
const IMesh &in_tm,
bool *r_is_intersect)
1763 uint32_t foff = cd.cdt_out.face_edge_offset;
1764 *r_is_intersect =
false;
1766 if (cd.verts_to_edge.size() > 0) {
1768 e = cd.verts_to_edge.lookup_default(OrderedEdge(i0, i1), NO_INDEX);
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)) {
1779 if (e == NO_INDEX) {
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]) {
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);
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);
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) {
1808 if (!have_non_face_eorig) {
1809 have_non_face_eorig =
true;
1811 if (face_eorig != NO_INDEX && have_non_face_eorig) {
1817 if (face_eorig != NO_INDEX) {
1820 if (have_non_face_eorig) {
1825 *r_is_intersect =
true;
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)
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]);
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);
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});
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});
1872 facep->populate_plane(
false);
1877static bool is_quad_flip_first_third(
const double3 &v1,
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;
1903static Array<Face *> polyfill_triangulate_poly(Face *f, IMeshArena *arena)
1906 int flen = f->size();
1908 if (!f->plane_populated()) {
1909 f->populate_plane(
false);
1911 const double3 &poly_normal = f->plane->norm;
1912 float no[3] = {
float(poly_normal[0]),
float(poly_normal[1]),
float(poly_normal[2])};
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];
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});
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});
1932 return Array<Face *>{f0, f1};
1935 float axis_mat[3][3];
1936 float (*projverts)[2];
1938 const int totfilltri = flen - 2;
1943 for (
int j = 0; j < flen; ++j) {
1944 const double3 &dco = (*f)[j]->co;
1950 Array<Face *> ans(totfilltri);
1951 for (
int t = 0; t < totfilltri; ++t) {
1952 uint *tri = tris[t];
1955 for (
int k = 0; k < 3; k++) {
1957 v[k] = (*f)[tri[k]];
1960 if ((tri[k] + 1) % flen == tri[(k + 1) % 3]) {
1961 eo[k] = f->edge_orig[tri[k]];
1966 ans[t] = arena->add_face(
1967 {
v[0],
v[1],
v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {
false,
false,
false});
1972 MEM_delete(projverts);
1992static Array<Face *> exact_triangulate_poly(Face *f, IMeshArena *arena)
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);
2001 if (!f->plane_populated()) {
2002 f->populate_plane(
false);
2004 const double3 &poly_normal = f->plane->norm;
2005 int axis = math::dominant_axis(poly_normal);
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];
2017 for (
int j = 0; j < 3; ++j) {
2019 p2d[k++] = (*f)[ii]->co_exact[j];
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;
2031 int n_tris = cdt_out.face.size();
2032 Array<Face *> ans(n_tris);
2033 for (
int t = 0; t < n_tris; ++t) {
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;
2044 v[i] = (*f)[cdt_out.vert_orig[i_v_out[i]][0]];
2046 if (needs_steiner) {
2048 return polyfill_triangulate_poly(f, arena);
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);
2058 for (uint32_t orig : cdt_out.edge_orig[e_out]) {
2060 int pos = int(orig % foff);
2062 eo[i] = f->edge_orig[pos];
2068 ans[t] = arena->add_face(
2069 {
v[0],
v[2],
v[1]}, f->orig, {eo[2], eo[1], eo[0]}, {
false,
false,
false});
2072 ans[t] = arena->add_face(
2073 {
v[0],
v[1],
v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {
false,
false,
false});
2079static bool face_is_degenerate(
const Face *f)
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) {
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) {
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) {
2107static bool any_degenerate_tris_fast(
const Array<Face *> &triangulation)
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) {
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) {
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) {
2145static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
2148 Array<Face *> ans = polyfill_triangulate_poly(f, arena);
2151 if (any_degenerate_tris_fast(ans)) {
2152 return exact_triangulate_poly(f, arena);
2157IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
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);
2170 for (Face *f : imesh.faces()) {
2172 int flen = f->size();
2174 face_tris.append(f);
2177 Array<Face *> tris = triangulate_poly(f, arena);
2178 for (Face *tri : tris) {
2179 face_tris.append(tri);
2183 return IMesh(face_tris);
2190static IMesh extract_subdivided_tri(
const CDT_data &cd,
2195 const CDT_result<mpq_class> &cdt_out = cd.cdt_out;
2197 for (
int i = 0; i < cd.input_face.size(); ++i) {
2198 if (cd.input_face[i] == t) {
2202 if (t_in_cdt == -1) {
2203 std::cout <<
"Could not find " << t <<
" in cdt input tris\n";
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);
2215 return IMesh(faces);
2218static bool bvhtreeverlap_cmp(
const BVHTreeOverlap &a,
const BVHTreeOverlap &
b)
2220 if (a.indexA <
b.indexA) {
2223 if ((a.indexA ==
b.indexA) && (a.indexB <
b.indexB)) {
2229 BVHTree *tree_{
nullptr};
2230 BVHTree *tree_b_{
nullptr};
2231 BVHTreeOverlap *overlap_{
nullptr};
2232 Array<int> first_overlap_;
2233 uint overlap_num_{0};
2237 std::function<int(
int)> shape_fn;
2243 TriOverlaps(
const IMesh &tm,
2244 const Span<BoundingBox> tri_bb,
2246 std::function<
int(
int)> shape_fn,
2249 constexpr int dbg_level = 0;
2250 if (dbg_level > 0) {
2251 std::cout <<
"TriOverlaps construction\n";
2257 bool two_trees_no_self = nshapes == 2 && !use_self;
2258 if (two_trees_no_self) {
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);
2272 for (
int t : tm.face_index_range()) {
2276 int shape = shapes[t];
2277 if (two_trees_no_self) {
2281 else if (shape == 1) {
2292 if (two_trees_no_self) {
2298 CBData cbdata{tm, shape_fn, nshapes, use_self};
2304 tree_, tree_, &overlap_num_, only_different_shapes, &cbdata);
2310 if (two_trees_no_self) {
2311 overlap_ =
static_cast<BVHTreeOverlap *
>(
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;
2317 overlap_num_ += overlap_num_;
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";
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;
2345 MEM_delete(overlap_);
2354 int first_overlap_index(
int t)
const
2356 return first_overlap_[t];
2360 static bool only_different_shapes(
void *userdata,
int index_a,
int index_b,
int )
2362 CBData *cbdata =
static_cast<CBData *
>(userdata);
2363 return cbdata->tm.face(index_a)->orig != cbdata->tm.face(index_b)->orig;
2370struct OverlapIttsData {
2371 Vector<std::pair<int, int>> intersect_pairs;
2372 Map<std::pair<int, int>, ITT_value> &itt_map;
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)
2386static std::pair<int, int> canon_int_pair(
int a,
int b)
2391 return std::pair<int, int>(a,
b);
2394static void calc_overlap_itts_range_func(
void *__restrict userdata,
2396 const TaskParallelTLS *__restrict )
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";
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";
2411 data->itt_map.add_overwrite(tri_pair, itt);
2418static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map,
2420 const TriOverlaps &ov,
2423 OverlapIttsData
data(itt_map, tm, arena);
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);
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;
2448static void calc_subdivided_non_cluster_tris(Array<IMesh> &r_tri_subdivided,
2450 const Map<std::pair<int, int>, ITT_value> &itt_map,
2451 const CoplanarClusterInfo &clinfo,
2452 const TriOverlaps &ov,
2455 const int dbg_level = 0;
2456 if (dbg_level > 0) {
2457 std::cout <<
"\nCALC_SUBDIVIDED_TRIS\n\n";
2460 struct OverlapTriRange {
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) {
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);
2484 bumpperfcount(0,
len);
2488 overlap_index = i + 1;
2490 int overlap_tri_range_num = overlap_tri_range.size();
2491 Array<CDT_data> cd_data(overlap_tri_range_num);
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";
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);
2507 if (itt_map.contains(key)) {
2508 itt = itt_map.lookup(key);
2510 if (itt.kind != INONE) {
2513 if (dbg_level > 0) {
2514 std::cout <<
" tri t" << t_other <<
"; result = " << itt <<
"\n";
2517 if (itts.size() > 0) {
2518 cd_data[otr_index] = prepare_cdt_input(tm, t, itts);
2519 do_cdt(cd_data[otr_index]);
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];
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)});
2552static void calc_cluster_tris(Array<IMesh> &tri_subdivided,
2554 const CoplanarClusterInfo &clinfo,
2558 for (
int c : clinfo.index_range()) {
2559 const CoplanarCluster &cl = clinfo.cluster(c);
2560 const CDT_data &cd = cluster_subdivided[c];
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);
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]);
2586static CDT_data calc_cluster_subdivided(
const CoplanarClusterInfo &clinfo,
2589 const TriOverlaps &ov,
2590 const Map<std::pair<int, int>, ITT_value> &itt_map,
2593 constexpr int dbg_level = 0;
2595 const CoplanarCluster &cl = clinfo.cluster(c);
2597 if (dbg_level > 0) {
2598 std::cout <<
"CALC_CLUSTER_SUBDIVIDED for cluster " << c <<
" = " << cl <<
"\n";
2603 Vector<ITT_value> itts;
2606 if (dbg_level > 0) {
2607 std::cout <<
"find intersects with triangle " << t <<
" of cluster\n";
2609 int first_i = ov.first_overlap_index(t);
2610 if (first_i == -1) {
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";
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)) {
2624 if (dbg_level > 0) {
2625 std::cout <<
" itt = " << itt <<
"\n";
2633 CDT_data cd_data = prepare_cdt_input_for_cluster(tm, clinfo, c, itts);
2638static IMesh union_tri_subdivides(
const Array<IMesh> &tri_subdivided)
2641 for (
const IMesh &m : tri_subdivided) {
2642 tot_tri += m.face_size();
2644 Array<Face *> faces(tot_tri);
2646 for (
const IMesh &m : tri_subdivided) {
2647 for (Face *f : m.faces()) {
2648 faces[face_index++] = f;
2651 return IMesh(faces);
2654static CoplanarClusterInfo find_clusters(
const IMesh &tm,
2655 const Array<BoundingBox> &tri_bb,
2656 const Map<std::pair<int, int>, ITT_value> &itt_map)
2658 constexpr int dbg_level = 0;
2659 if (dbg_level > 0) {
2660 std::cout <<
"FIND_CLUSTERS\n";
2662 CoplanarClusterInfo ans(tm.face_size());
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});
2673 if (dbg_level > 0) {
2674 std::cout <<
"found " << maybe_coplanar_tris.size() <<
" possible coplanar tris\n";
2676 if (maybe_coplanar_tris.is_empty()) {
2677 if (dbg_level > 0) {
2678 std::cout <<
"No possible coplanar tris, so no clusters\n";
2685 Map<Plane, Vector<CoplanarCluster>> plane_cls;
2686 plane_cls.reserve(maybe_coplanar_tris.size());
2687 for (
int t : maybe_coplanar_tris) {
2691 Plane tplane = *tm.face(t)->plane;
2693 tplane.make_canonical();
2694 if (dbg_level > 0) {
2695 std::cout <<
"plane for tri " << t <<
" = " << &tplane <<
"\n";
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";
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";
2710 if (bbs_might_intersect(tri_bb[t], cl.bounding_box())) {
2711 if (dbg_level > 1) {
2712 std::cout <<
"append to int_cls\n";
2714 int_cls.append(&cl);
2717 if (dbg_level > 1) {
2718 std::cout <<
"append to no_int_cls\n";
2720 no_int_cls.append(&cl);
2723 if (int_cls.is_empty()) {
2725 if (dbg_level > 1) {
2726 std::cout <<
"no intersecting clusters for t, make a new one\n";
2728 curcls.append(CoplanarCluster(t, tri_bb[t]));
2730 else if (int_cls.size() == 1) {
2732 if (dbg_level > 1) {
2733 std::cout <<
"exactly one existing cluster, " << int_cls[0] <<
", adding to it\n";
2735 int_cls[0]->add_tri(t, tri_bb[t]);
2740 if (dbg_level > 1) {
2741 std::cout <<
"merging\n";
2743 CoplanarCluster mergecl;
2744 mergecl.add_tri(t, tri_bb[t]);
2745 for (CoplanarCluster *cl : int_cls) {
2747 mergecl.add_tri(t, tri_bb[t]);
2750 Vector<CoplanarCluster> newvec;
2751 newvec.append(mergecl);
2752 for (CoplanarCluster *cl_no_int : no_int_cls) {
2753 newvec.append(*cl_no_int);
2755 plane_cls.add_overwrite(tplane, newvec);
2759 if (dbg_level > 0) {
2760 std::cout <<
"first cluster for its plane\n";
2762 plane_cls.add_new(tplane, Vector<CoplanarCluster>{CoplanarCluster(t, tri_bb[t])});
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);
2783struct DegenChunkData {
2784 bool has_degenerate_tri =
false;
2787static void degenerate_range_func(
void *__restrict userdata,
2789 const TaskParallelTLS *__restrict tls)
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;
2798static void degenerate_reduce(
const void *__restrict ,
2799 void *__restrict chunk_join,
2800 void *__restrict chunk)
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;
2808static bool has_degenerate_tris(
const IMesh &tm)
2810 DegenData degen_data = {tm};
2811 DegenChunkData degen_chunk_data;
2812 TaskParallelSettings settings;
2814 settings.userdata_chunk = °en_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;
2820 return degen_chunk_data.has_degenerate_tri;
2823static IMesh remove_degenerate_tris(
const IMesh &tm_in)
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);
2833 ans.set_faces(new_faces);
2837IMesh trimesh_self_intersect(
const IMesh &tm_in, IMeshArena *arena)
2839 return trimesh_nary_intersect(tm_in, 1, [](
int ) {
return 0; },
true, arena);
2842IMesh trimesh_nary_intersect(
const IMesh &tm_in,
2844 const FunctionRef<
int(
int)> shape_fn,
2848 constexpr int dbg_level = 0;
2849 if (dbg_level > 0) {
2850 std::cout <<
"\nTRIMESH_NARY_INTERSECT nshapes=" << nshapes <<
" use_self=" << use_self
2852 for (
const Face *f : tm_in.faces()) {
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";
2861 write_obj_mesh(
const_cast<IMesh &
>(tm_in),
"trimesh_input");
2867 std::cout <<
"trimesh_nary_intersect start\n";
2871 const IMesh *tm_clean = &tm_in;
2873 if (has_degenerate_tris(tm_in)) {
2874 if (dbg_level > 0) {
2875 std::cout <<
"cleaning degenerate triangles\n";
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;
2885 std::cout <<
"cleaned, time = " << clean_time - start_time <<
"\n";
2887 Array<BoundingBox> tri_bb = calc_face_bounding_boxes(*tm_clean);
2890 std::cout <<
"bbs calculated, time = " << bb_calc_time - clean_time <<
"\n";
2892 TriOverlaps tri_ov(*tm_clean, tri_bb, nshapes, shape_fn, use_self);
2895 std::cout <<
"intersect overlaps calculated, time = " << overlap_time - bb_calc_time <<
"\n";
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);
2903 new (static_cast<void *>(&tri_subdivided[t])) IMesh;
2908 std::cout <<
"planes populated, time = " << plane_populate - overlap_time <<
"\n";
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);
2917 std::cout <<
"itts found, time = " << itt_time - plane_populate <<
"\n";
2919 CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb, itt_map);
2920 if (dbg_level > 1) {
2921 std::cout << clinfo;
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());
2930 calc_subdivided_non_cluster_tris(tri_subdivided, *tm_clean, itt_map, clinfo, tri_ov, arena);
2933 std::cout <<
"subdivided non-cluster tris found, time = " << subdivided_tris_time - itt_time
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);
2942 std::cout <<
"subdivided clusters found, time = "
2943 << cluster_subdivide_time - subdivided_tris_time <<
"\n";
2945 calc_cluster_tris(tri_subdivided, *tm_clean, clinfo, cluster_subdivided, arena);
2948 std::cout <<
"subdivided cluster tris found, time = " << extract_time - cluster_subdivide_time
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;
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";
2965static std::ostream &
operator<<(std::ostream &os,
const CoplanarCluster &cl)
2969 for (
const int t : cl) {
2982static std::ostream &
operator<<(std::ostream &os,
const CoplanarClusterInfo &clinfo)
2984 os <<
"Coplanar Cluster Info:\n";
2985 for (
int c : clinfo.index_range()) {
2986 os << c <<
": " << clinfo.cluster(c) <<
"\n";
2991static std::ostream &
operator<<(std::ostream &os,
const ITT_value &itt)
2998 os <<
"point " << itt.p1;
3001 os <<
"segment " << itt.p1 <<
" " << itt.p2;
3004 os <<
"co-planar t" << itt.t_source;
3010void write_obj_mesh(IMesh &m,
const std::string &objname)
3017 if (objdir ==
nullptr) {
3018 std::cout <<
"Could not access home directory\n";
3022 const char *objdir =
"/tmp/";
3025 if (m.face_size() == 0) {
3029 std::string fname = std::string(objdir) + objname + std::string(
".obj");
3033 std::cout <<
"Could not open file " << fname <<
"\n";
3037 if (!m.has_verts()) {
3040 for (
const Vert *v : m.vertices()) {
3042 f <<
"v " << dv[0] <<
" " << dv[1] <<
" " << dv[2] <<
"\n";
3044 for (
const Face *face : m.faces()) {
3047 for (
const Vert *v : *face) {
3048 int i = m.lookup_vert(v);
3061 Vector<const char *> count_name;
3063 Vector<const char *> max_name;
3066static PerfCounts *perfdata =
nullptr;
3068static void perfdata_init()
3070 perfdata =
new PerfCounts;
3073 perfdata->count.append(0);
3074 perfdata->count_name.append(
"Non-cluster overlaps");
3077 perfdata->count.append(0);
3078 perfdata->count_name.append(
"intersect_tri_tri calls");
3081 perfdata->count.append(0);
3082 perfdata->count_name.append(
"tri tri intersects decided by filter plane tests");
3085 perfdata->count.append(0);
3086 perfdata->count_name.append(
"tri tri intersects decided by exact plane tests");
3089 perfdata->count.append(0);
3090 perfdata->count_name.append(
"final non-NONE intersects");
3093 perfdata->max.append(0);
3094 perfdata->max_name.append(
"total faces");
3097 perfdata->max.append(0);
3098 perfdata->max_name.append(
"total clusters");
3101 perfdata->max.append(0);
3102 perfdata->max_name.append(
"total overlaps");
3105static void incperfcount(
int countnum)
3107 perfdata->count[countnum]++;
3110static void bumpperfcount(
int countnum,
int amt)
3112 perfdata->count[countnum] += amt;
3115static void doperfmax(
int maxnum,
int val)
3117 perfdata->max[maxnum] =
max_ii(perfdata->max[maxnum], val);
3120static void dump_perfdata()
3122 std::cout <<
"\nPERFDATA\n";
3123 for (
int i : perfdata->count.index_range()) {
3124 std::cout << perfdata->count_name[i] <<
" = " << perfdata->count[i] <<
"\n";
3126 for (
int i : perfdata->max.index_range()) {
3127 std::cout << perfdata->max_name[i] <<
" = " << perfdata->max[i] <<
"\n";
File and directory operations.
int pad[32 - sizeof(int)]
#define UNUSED_VARS_NDEBUG(...)
#define MEM_realloc_uninitialized(vmemh, len)
unsigned long long int uint64_t
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
constexpr int64_t size() const
std::ostream & operator<<(std::ostream &os, DeviceKernel kernel)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
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)
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()
void parallel_sort(RandomAccessIterator begin, RandomAccessIterator end)
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
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
double BLI_time_now_seconds()
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)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float