39 # include <tbb/parallel_reduce.h>
40 # include <tbb/spin_mutex.h>
53 const Vert *v_[2]{
nullptr,
nullptr};
59 if (v0->id <=
v1->id) {
69 const Vert *v0()
const
86 return v_[0]->id == other.v_[0]->id && v_[1]->id == other.v_[1]->id;
97 if (
e.v0() ==
nullptr) {
102 os <<
"(" <<
e.v0() <<
"," <<
e.v1() <<
")";
107 static std::ostream &
operator<<(std::ostream &os,
const Span<int> &
a)
109 for (
int i :
a.index_range()) {
111 if (i !=
a.size() - 1) {
118 static std::ostream &
operator<<(std::ostream &os,
const Array<int> &iarr)
120 os << Span<int>(iarr);
125 class TriMeshTopology : NonCopyable {
127 Map<Edge, Vector<int> *> edge_tri_;
129 Map<const Vert *, Vector<Edge>> vert_edges_;
132 TriMeshTopology(
const IMesh &tm);
137 int other_tri_if_manifold(
Edge e,
int t)
const
139 const auto *p = edge_tri_.lookup_ptr(
e);
140 if (p !=
nullptr && (*p)->size() == 2) {
141 return ((**p)[0] ==
t) ? (**p)[1] : (**p)[0];
147 const Vector<int> *edge_tris(
Edge e)
const
149 return edge_tri_.lookup_default(
e,
nullptr);
154 const Vector<Edge> &vert_edges(
const Vert *
v)
const
156 return vert_edges_.lookup(
v);
159 Map<Edge, Vector<int> *>::ItemIterator edge_tri_map_items()
const
161 return edge_tri_.items();
165 TriMeshTopology::TriMeshTopology(
const IMesh &tm)
167 const int dbg_level = 0;
169 std::cout <<
"TRIMESHTOPOLOGY CONSTRUCTION\n";
173 const int estimate_num_edges = 2 * tm.face_size();
174 const int estimate_verts_num = tm.face_size();
175 edge_tri_.reserve(estimate_num_edges);
176 vert_edges_.reserve(estimate_verts_num);
177 for (
int t : tm.face_index_range()) {
178 const Face &tri = *tm.face(
t);
180 for (
int i = 0; i < 3; ++i) {
181 const Vert *
v = tri[i];
182 const Vert *vnext = tri[(i + 1) % 3];
184 Vector<Edge> *edges = vert_edges_.lookup_ptr(
v);
185 if (edges ==
nullptr) {
186 vert_edges_.add_new(
v, Vector<Edge>());
187 edges = vert_edges_.lookup_ptr(
v);
190 edges->append_non_duplicates(
e);
192 auto *p = edge_tri_.lookup_ptr(
Edge(
v, vnext));
194 edge_tri_.add_new(
e,
new Vector<int>{
t});
197 (*p)->append_non_duplicates(
t);
203 std::cout <<
"After TriMeshTopology construction\n";
204 for (
auto item : edge_tri_.items()) {
205 std::cout <<
"tris for edge " << item.key <<
": " << *item.value <<
"\n";
206 constexpr
bool print_stats =
false;
208 edge_tri_.print_stats();
211 for (
auto item : vert_edges_.items()) {
212 std::cout <<
"edges for vert " << item.key <<
":\n";
213 for (
const Edge &
e : item.value) {
214 std::cout <<
" " <<
e <<
"\n";
221 TriMeshTopology::~TriMeshTopology()
223 Vector<Vector<int> *> values;
226 for (
auto *item : edge_tri_.values()) {
231 for (int i : range) {
259 IndexRange tri_range()
const
261 return IndexRange(tri_.size());
264 Span<int> tris()
const
266 return Span<int>(tri_);
269 int cell_above{NO_INDEX};
270 int cell_below{NO_INDEX};
276 os <<
"Patch " << patch.tris();
277 if (patch.cell_above != NO_INDEX) {
278 os <<
" cell_above=" << patch.cell_above;
281 os <<
" cell_above not set";
283 if (patch.cell_below != NO_INDEX) {
284 os <<
" cell_below=" << patch.cell_below;
287 os <<
" cell_below not set";
294 Vector<Patch> patch_;
296 Array<int> tri_patch_;
298 Map<std::pair<int, int>,
Edge> pp_edge_;
301 explicit PatchesInfo(
int ntri)
303 constexpr
int max_expected_patch_patch_incidences = 100;
304 tri_patch_ = Array<int>(ntri, NO_INDEX);
305 pp_edge_.reserve(max_expected_patch_patch_incidences);
308 int tri_patch(
int t)
const
310 return tri_patch_[
t];
315 int patch_index = patch_.append_and_get_index(
Patch());
319 void grow_patch(
int patch_index,
int t)
321 tri_patch_[
t] = patch_index;
322 patch_[patch_index].add_tri(
t);
325 bool tri_is_assigned(
int t)
const
327 return tri_patch_[
t] != NO_INDEX;
330 const Patch &patch(
int patch_index)
const
332 return patch_[patch_index];
335 Patch &patch(
int patch_index)
337 return patch_[patch_index];
340 int tot_patch()
const
342 return patch_.size();
345 IndexRange index_range()
const
347 return IndexRange(patch_.size());
350 const Patch *begin()
const
352 return patch_.begin();
355 const Patch *end()
const
362 return patch_.begin();
370 void add_new_patch_patch_edge(
int p1,
int p2,
Edge e)
372 pp_edge_.add_new(std::pair<int, int>(p1, p2),
e);
373 pp_edge_.add_new(std::pair<int, int>(p2, p1),
e);
376 Edge patch_patch_edge(
int p1,
int p2)
378 return pp_edge_.lookup_default(std::pair<int, int>(p1, p2),
Edge());
381 const Map<std::pair<int, int>,
Edge> &patch_patch_edge_map()
387 static bool apply_bool_op(BoolOpType bool_optype,
const Array<int> &winding);
397 int merged_to_{NO_INDEX};
398 bool winding_assigned_{
false};
400 bool in_output_volume_{
false};
403 bool zero_volume_{
false};
408 void add_patch(
int p)
411 zero_volume_ =
false;
414 const Set<int> &patches()
const
420 int patch_other(
int p)
const
422 if (patches_.size() != 2) {
425 for (
int pother : patches_) {
433 Span<int> winding()
const
435 return Span<int>(winding_);
438 void init_winding(
int winding_len)
440 winding_ = Array<int>(winding_len);
443 void seed_ambient_winding()
446 winding_assigned_ =
true;
449 void set_winding_and_in_output_volume(
const Cell &from_cell,
452 BoolOpType bool_optype)
454 std::copy(from_cell.winding().begin(), from_cell.winding().end(), winding_.begin());
456 winding_[shape] += delta;
458 winding_assigned_ =
true;
459 in_output_volume_ = apply_bool_op(bool_optype, winding_);
462 bool in_output_volume()
const
464 return in_output_volume_;
467 bool winding_assigned()
const
469 return winding_assigned_;
472 bool zero_volume()
const
477 int merged_to()
const
482 void set_merged_to(
int c)
491 void check_for_zero_volume(
const PatchesInfo &pinfo,
const IMesh &
mesh);
494 static std::ostream &
operator<<(std::ostream &os,
const Cell &cell)
496 os <<
"Cell patches";
497 for (
int p : cell.patches()) {
498 std::cout <<
" " << p;
500 if (cell.winding().size() > 0) {
501 os <<
" winding=" << cell.winding();
502 os <<
" in_output_volume=" << cell.in_output_volume();
504 os <<
" zv=" << cell.zero_volume();
509 static bool tris_have_same_verts(
const IMesh &
mesh,
int t1,
int t2)
513 BLI_assert(tri1.size() == 3 && tri2.size() == 3);
514 if (tri1.vert[0] == tri2.vert[0]) {
515 return ((tri1.vert[1] == tri2.vert[1] && tri1.vert[2] == tri2.vert[2]) ||
516 (tri1.vert[1] == tri2.vert[2] && tri1.vert[2] == tri2.vert[1]));
518 if (tri1.vert[0] == tri2.vert[1]) {
519 return ((tri1.vert[1] == tri2.vert[0] && tri1.vert[2] == tri2.vert[2]) ||
520 (tri1.vert[1] == tri2.vert[2] && tri1.vert[2] == tri2.vert[0]));
522 if (tri1.vert[0] == tri2.vert[2]) {
523 return ((tri1.vert[1] == tri2.vert[0] && tri1.vert[2] == tri2.vert[1]) ||
524 (tri1.vert[1] == tri2.vert[1] && tri1.vert[2] == tri2.vert[0]));
534 void Cell::check_for_zero_volume(
const PatchesInfo &pinfo,
const IMesh &
mesh)
536 if (patches_.size() == 2) {
537 int p1_index = NO_INDEX;
538 int p2_index = NO_INDEX;
539 for (
int p : patches_) {
540 if (p1_index == NO_INDEX) {
547 BLI_assert(p1_index != NO_INDEX && p2_index != NO_INDEX);
548 const Patch &p1 = pinfo.patch(p1_index);
549 const Patch &p2 = pinfo.patch(p2_index);
550 if (p1.tot_tri() == 1 && p2.tot_tri() == 1) {
551 if (tris_have_same_verts(
mesh, p1.tri(0), p2.tri(0))) {
563 CellsInfo() =
default;
567 int index = cell_.append_and_get_index(Cell());
576 const Cell &cell(
int c)
const
586 IndexRange index_range()
const
588 return cell_.index_range();
591 const Cell *begin()
const
593 return cell_.begin();
596 const Cell *end()
const
603 return cell_.begin();
611 void init_windings(
int winding_len)
613 for (Cell &cell : cell_) {
614 cell.init_winding(winding_len);
622 static void write_obj_cell_patch(
const IMesh &m,
623 const CellsInfo &cinfo,
624 const PatchesInfo &pinfo,
626 const std::string &name)
634 const char *objdir =
"/tmp/";
637 std::string fname = std::string(objdir) + name + std::string(
"_cellpatch.obj");
641 std::cout <<
"Could not open file " << fname <<
"\n";
648 f <<
"o cellpatch\n";
649 for (
const Vert *
v : mm.vertices()) {
651 f <<
"v " << dv[0] <<
" " << dv[1] <<
" " << dv[2] <<
"\n";
654 for (
int p : pinfo.index_range()) {
655 f <<
"g patch" << p <<
"\n";
656 const Patch &patch = pinfo.patch(p);
657 for (
int t : patch.tris()) {
658 const Face &tri = *mm.face(
t);
660 for (
const Vert *
v : tri) {
661 f << mm.lookup_vert(
v) + 1 <<
" ";
667 for (
int c : cinfo.index_range()) {
668 f <<
"g cell" <<
c <<
"\n";
669 const Cell &cell = cinfo.cell(
c);
670 for (
int p : cell.patches()) {
671 const Patch &patch = pinfo.patch(p);
672 for (
int t : patch.tris()) {
673 const Face &tri = *mm.face(
t);
675 for (
const Vert *
v : tri) {
676 f << mm.lookup_vert(
v) + 1 <<
" ";
685 static void merge_cells(
int merge_to,
int merge_from, CellsInfo &cinfo, PatchesInfo &pinfo)
687 if (merge_to == merge_from) {
690 Cell &merge_from_cell = cinfo.cell(merge_from);
691 Cell &merge_to_cell = cinfo.cell(merge_to);
692 int final_merge_to = merge_to;
693 while (merge_to_cell.merged_to() != NO_INDEX) {
694 final_merge_to = merge_to_cell.merged_to();
695 merge_to_cell = cinfo.cell(final_merge_to);
697 for (
int cell_p : merge_from_cell.patches()) {
698 merge_to_cell.add_patch(cell_p);
699 Patch &patch = pinfo.patch(cell_p);
700 if (patch.cell_above == merge_from) {
701 patch.cell_above = merge_to;
703 if (patch.cell_below == merge_from) {
704 patch.cell_below = merge_to;
707 merge_from_cell.set_merged_to(final_merge_to);
713 static PatchesInfo find_patches(
const IMesh &tm,
const TriMeshTopology &tmtopo)
715 const int dbg_level = 0;
717 std::cout <<
"\nFIND_PATCHES\n";
719 int ntri = tm.face_size();
720 PatchesInfo pinfo(ntri);
722 Stack<int> cur_patch_grow;
725 Array<std::array<int, 3>> t_others(tm.face_size());
727 for (int t : range) {
728 const Face &tri = *tm.face(t);
729 for (int i = 0; i < 3; ++i) {
730 Edge e(tri[i], tri[(i + 1) % 3]);
731 t_others[t][i] = tmtopo.other_tri_if_manifold(e, t);
735 for (
int t : tm.face_index_range()) {
736 if (pinfo.tri_patch(
t) == -1) {
737 cur_patch_grow.push(
t);
738 int cur_patch_index = pinfo.add_patch();
739 while (!cur_patch_grow.is_empty()) {
740 int tcand = cur_patch_grow.pop();
742 std::cout <<
"pop tcand = " << tcand <<
"; assigned = " << pinfo.tri_is_assigned(tcand)
745 if (pinfo.tri_is_assigned(tcand)) {
749 std::cout <<
"grow patch from seed tcand=" << tcand <<
"\n";
751 pinfo.grow_patch(cur_patch_index, tcand);
752 const Face &tri = *tm.face(tcand);
753 for (
int i = 0; i < 3; ++i) {
754 Edge e(tri[i], tri[(i + 1) % 3]);
755 int t_other = t_others[tcand][i];
757 std::cout <<
" edge " <<
e <<
" generates t_other=" << t_other <<
"\n";
759 if (t_other != NO_INDEX) {
760 if (!pinfo.tri_is_assigned(t_other)) {
762 std::cout <<
" push t_other = " << t_other <<
"\n";
764 cur_patch_grow.push(t_other);
770 std::cout <<
" e non-manifold case\n";
772 const Vector<int> *etris = tmtopo.edge_tris(
e);
773 if (etris !=
nullptr) {
774 for (
int i : etris->index_range()) {
775 int t_other = (*etris)[i];
776 if (t_other != tcand && pinfo.tri_is_assigned(t_other)) {
777 int p_other = pinfo.tri_patch(t_other);
778 if (p_other == cur_patch_index) {
781 if (pinfo.patch_patch_edge(cur_patch_index, p_other).v0() ==
nullptr) {
782 pinfo.add_new_patch_patch_edge(cur_patch_index, p_other,
e);
784 std::cout <<
"added patch_patch_edge (" << cur_patch_index <<
"," << p_other
785 <<
") = " <<
e <<
"\n";
797 std::cout <<
"\nafter FIND_PATCHES: found " << pinfo.tot_patch() <<
" patches\n";
798 for (
int p : pinfo.index_range()) {
799 std::cout << p <<
": " << pinfo.patch(p) <<
"\n";
802 std::cout <<
"\ntriangle map\n";
803 for (
int t : tm.face_index_range()) {
804 std::cout <<
t <<
": " << tm.face(
t) <<
" patch " << pinfo.tri_patch(
t) <<
"\n";
807 std::cout <<
"\npatch-patch incidences\n";
808 for (
int p1 : pinfo.index_range()) {
809 for (
int p2 : pinfo.index_range()) {
810 Edge e = pinfo.patch_patch_edge(p1, p2);
811 if (
e.v0() !=
nullptr) {
812 std::cout <<
"p" << p1 <<
" and p" << p2 <<
" share edge " <<
e <<
"\n";
826 static const Vert *find_flap_vert(
const Face &tri,
const Edge e,
bool *r_rev)
830 if (tri[0] ==
e.v0()) {
831 if (tri[1] ==
e.v1()) {
836 if (tri[2] !=
e.v1()) {
843 else if (tri[1] ==
e.v0()) {
844 if (tri[2] ==
e.v1()) {
849 if (tri[0] !=
e.v1()) {
857 if (tri[2] !=
e.v0()) {
860 if (tri[0] ==
e.v1()) {
865 if (tri[1] !=
e.v1()) {
889 static int sort_tris_class(
const Face &tri,
const Face &tri0,
const Edge e)
891 const int dbg_level = 0;
893 std::cout <<
"classify e = " <<
e <<
"\n";
895 mpq3 a0 = tri0[0]->co_exact;
896 mpq3 a1 = tri0[1]->co_exact;
897 mpq3 a2 = tri0[2]->co_exact;
900 const Vert *flapv0 = find_flap_vert(tri0,
e, &rev0);
901 const Vert *flapv = find_flap_vert(tri,
e, &rev);
903 std::cout <<
" t0 = " << tri0[0] <<
" " << tri0[1] <<
" " << tri0[2];
904 std::cout <<
" rev0 = " << rev0 <<
" flapv0 = " << flapv0 <<
"\n";
905 std::cout <<
" t = " << tri[0] <<
" " << tri[1] <<
" " << tri[2];
906 std::cout <<
" rev = " << rev <<
" flapv = " << flapv <<
"\n";
908 BLI_assert(flapv !=
nullptr && flapv0 !=
nullptr);
909 const mpq3 flap = flapv->co_exact;
911 int orient =
orient3d(a0, a1, a2, flap);
916 else if (orient < 0) {
920 ans = flapv == flapv0 ? 1 : 2;
923 std::cout <<
" orient = " << orient <<
" ans = " << ans <<
"\n";
928 constexpr
int EXTRA_TRI_INDEX = INT_MAX;
936 static void sort_by_signed_triangle_index(Vector<int> &
g,
939 const Face *extra_tri)
941 Array<int> signed_g(
g.size());
942 for (
int i :
g.index_range()) {
943 const Face &tri =
g[i] == EXTRA_TRI_INDEX ? *extra_tri : *tm.face(
g[i]);
945 find_flap_vert(tri,
e, &rev);
946 signed_g[i] = rev ? -
g[i] :
g[i];
948 std::sort(signed_g.begin(), signed_g.end());
950 for (
int i :
g.index_range()) {
951 g[i] =
abs(signed_g[i]);
969 static Array<int> sort_tris_around_edge(
970 const IMesh &tm,
const Edge e,
const Span<int> tris,
const int t0,
const Face *extra_tri)
982 const int dbg_level = 0;
983 if (tris.size() == 0) {
990 std::cout <<
"sort_tris_around_edge " <<
e <<
"\n";
991 std::cout <<
"tris = " << tris <<
"\n";
992 std::cout <<
"t0 = " << t0 <<
"\n";
994 Vector<int> g1{tris[0]};
998 std::array<Vector<int> *, 4> groups = {&g1, &g2, &g3, &g4};
999 const Face &triref = *tm.face(tris[0]);
1000 for (
int i : tris.index_range()) {
1005 BLI_assert(
t < tm.face_size() || (
t == EXTRA_TRI_INDEX && extra_tri !=
nullptr));
1006 const Face &tri = (
t == EXTRA_TRI_INDEX) ? *extra_tri : *tm.face(
t);
1007 if (dbg_level > 2) {
1008 std::cout <<
"classifying tri " <<
t <<
" with respect to " << tris[0] <<
"\n";
1010 int group_num = sort_tris_class(tri, triref,
e);
1011 if (dbg_level > 2) {
1012 std::cout <<
" classify result : " << group_num <<
"\n";
1014 groups[group_num - 1]->append(
t);
1016 if (dbg_level > 1) {
1017 std::cout <<
"g1 = " << g1 <<
"\n";
1018 std::cout <<
"g2 = " << g2 <<
"\n";
1019 std::cout <<
"g3 = " << g3 <<
"\n";
1020 std::cout <<
"g4 = " << g4 <<
"\n";
1022 if (g1.size() > 1) {
1023 sort_by_signed_triangle_index(g1,
e, tm, extra_tri);
1024 if (dbg_level > 1) {
1025 std::cout <<
"g1 sorted: " << g1 <<
"\n";
1028 if (g2.size() > 1) {
1029 sort_by_signed_triangle_index(g2,
e, tm, extra_tri);
1030 if (dbg_level > 1) {
1031 std::cout <<
"g2 sorted: " << g2 <<
"\n";
1034 if (g3.size() > 1) {
1035 Array<int> g3sorted = sort_tris_around_edge(tm,
e, g3, t0, extra_tri);
1036 std::copy(g3sorted.begin(), g3sorted.end(), g3.begin());
1037 if (dbg_level > 1) {
1038 std::cout <<
"g3 sorted: " << g3 <<
"\n";
1041 if (g4.size() > 1) {
1042 Array<int> g4sorted = sort_tris_around_edge(tm,
e, g4, t0, extra_tri);
1043 std::copy(g4sorted.begin(), g4sorted.end(), g4.begin());
1044 if (dbg_level > 1) {
1045 std::cout <<
"g4 sorted: " << g4 <<
"\n";
1048 int group_tot_size = g1.size() + g2.size() + g3.size() + g4.size();
1049 Array<int> ans(group_tot_size);
1050 int *p = ans.begin();
1051 if (tris[0] == t0) {
1063 if (dbg_level > 0) {
1064 std::cout <<
"sorted tris = " << ans <<
"\n";
1075 static void find_cells_from_edge(
const IMesh &tm,
1076 const TriMeshTopology &tmtopo,
1081 const int dbg_level = 0;
1082 if (dbg_level > 0) {
1083 std::cout <<
"FIND_CELLS_FROM_EDGE " <<
e <<
"\n";
1085 const Vector<int> *edge_tris = tmtopo.edge_tris(
e);
1087 Array<int> sorted_tris = sort_tris_around_edge(
1088 tm,
e, Span<int>(*edge_tris), (*edge_tris)[0],
nullptr);
1090 int n_edge_tris = edge_tris->size();
1091 Array<int> edge_patches(n_edge_tris);
1092 for (
int i = 0; i < n_edge_tris; ++i) {
1093 edge_patches[i] = pinfo.tri_patch(sorted_tris[i]);
1094 if (dbg_level > 1) {
1095 std::cout <<
"edge_patches[" << i <<
"] = " << edge_patches[i] <<
"\n";
1098 for (
int i = 0; i < n_edge_tris; ++i) {
1099 int inext = (i + 1) % n_edge_tris;
1100 int r_index = edge_patches[i];
1101 int rnext_index = edge_patches[inext];
1102 Patch &
r = pinfo.patch(r_index);
1103 Patch &rnext = pinfo.patch(rnext_index);
1106 find_flap_vert(*tm.face(sorted_tris[i]),
e, &r_flipped);
1107 find_flap_vert(*tm.face(sorted_tris[inext]),
e, &rnext_flipped);
1108 int *r_follow_cell = r_flipped ? &
r.cell_below : &
r.cell_above;
1109 int *rnext_prev_cell = rnext_flipped ? &rnext.cell_above : &rnext.cell_below;
1110 if (dbg_level > 0) {
1111 std::cout <<
"process patch pair " << r_index <<
" " << rnext_index <<
"\n";
1112 std::cout <<
" r_flipped = " << r_flipped <<
" rnext_flipped = " << rnext_flipped <<
"\n";
1113 std::cout <<
" r_follow_cell (" << (r_flipped ?
"below" :
"above")
1114 <<
") = " << *r_follow_cell <<
"\n";
1115 std::cout <<
" rnext_prev_cell (" << (rnext_flipped ?
"above" :
"below")
1116 <<
") = " << *rnext_prev_cell <<
"\n";
1118 if (*r_follow_cell == NO_INDEX && *rnext_prev_cell == NO_INDEX) {
1120 int c = cinfo.add_cell();
1122 *rnext_prev_cell =
c;
1123 Cell &cell = cinfo.cell(
c);
1124 cell.add_patch(r_index);
1125 cell.add_patch(rnext_index);
1126 cell.check_for_zero_volume(pinfo, tm);
1127 if (dbg_level > 0) {
1128 std::cout <<
" made new cell " <<
c <<
"\n";
1129 std::cout <<
" p" << r_index <<
"." << (r_flipped ?
"cell_below" :
"cell_above") <<
" = c"
1131 std::cout <<
" p" << rnext_index <<
"." << (rnext_flipped ?
"cell_above" :
"cell_below")
1132 <<
" = c" <<
c <<
"\n";
1135 else if (*r_follow_cell != NO_INDEX && *rnext_prev_cell == NO_INDEX) {
1136 int c = *r_follow_cell;
1137 *rnext_prev_cell =
c;
1138 Cell &cell = cinfo.cell(
c);
1139 cell.add_patch(rnext_index);
1140 cell.check_for_zero_volume(pinfo, tm);
1141 if (dbg_level > 0) {
1142 std::cout <<
" reuse r_follow: p" << rnext_index <<
"."
1143 << (rnext_flipped ?
"cell_above" :
"cell_below") <<
" = c" <<
c <<
"\n";
1146 else if (*r_follow_cell == NO_INDEX && *rnext_prev_cell != NO_INDEX) {
1147 int c = *rnext_prev_cell;
1149 Cell &cell = cinfo.cell(
c);
1150 cell.add_patch(r_index);
1151 cell.check_for_zero_volume(pinfo, tm);
1152 if (dbg_level > 0) {
1153 std::cout <<
" reuse rnext prev: rprev_p" << r_index <<
"."
1154 << (r_flipped ?
"cell_below" :
"cell_above") <<
" = c" <<
c <<
"\n";
1158 if (*r_follow_cell != *rnext_prev_cell) {
1159 int follow_cell_num_patches = cinfo.cell(*r_follow_cell).patches().size();
1160 int prev_cell_num_patches = cinfo.cell(*rnext_prev_cell).patches().size();
1161 if (follow_cell_num_patches >= prev_cell_num_patches) {
1162 if (dbg_level > 0) {
1163 std::cout <<
" merge cell " << *rnext_prev_cell <<
" into cell " << *r_follow_cell
1166 merge_cells(*r_follow_cell, *rnext_prev_cell, cinfo, pinfo);
1170 if (dbg_level > 0) {
1171 std::cout <<
" merge cell " << *r_follow_cell <<
" into cell " << *rnext_prev_cell
1174 merge_cells(*rnext_prev_cell, *r_follow_cell, cinfo, pinfo);
1184 static CellsInfo find_cells(
const IMesh &tm,
const TriMeshTopology &tmtopo, PatchesInfo &pinfo)
1186 const int dbg_level = 0;
1187 if (dbg_level > 0) {
1188 std::cout <<
"\nFIND_CELLS\n";
1192 Set<Edge> processed_edges;
1193 for (
const auto item : pinfo.patch_patch_edge_map().items()) {
1194 int p = item.key.first;
1195 int q = item.key.second;
1197 const Edge &
e = item.value;
1198 if (!processed_edges.contains(
e)) {
1199 processed_edges.add_new(
e);
1200 find_cells_from_edge(tm, tmtopo, pinfo, cinfo,
e);
1209 for (
int p : pinfo.index_range()) {
1210 Patch &patch = pinfo.patch(p);
1211 if (patch.cell_above == NO_INDEX) {
1212 int c = cinfo.add_cell();
1213 patch.cell_above =
c;
1214 Cell &cell = cinfo.cell(
c);
1217 if (patch.cell_below == NO_INDEX) {
1218 int c = cinfo.add_cell();
1219 patch.cell_below =
c;
1220 Cell &cell = cinfo.cell(
c);
1224 if (dbg_level > 0) {
1225 std::cout <<
"\nFIND_CELLS found " << cinfo.tot_cell() <<
" cells\nCells\n";
1226 for (
int i : cinfo.index_range()) {
1227 std::cout << i <<
": " << cinfo.cell(i) <<
"\n";
1229 std::cout <<
"Patches\n";
1230 for (
int i : pinfo.index_range()) {
1231 std::cout << i <<
": " << pinfo.patch(i) <<
"\n";
1233 if (dbg_level > 1) {
1234 write_obj_cell_patch(tm, cinfo, pinfo,
false,
"postfindcells");
1245 static Vector<Vector<int>> find_patch_components(
const CellsInfo &cinfo, PatchesInfo &pinfo)
1247 constexpr
int dbg_level = 0;
1248 if (dbg_level > 0) {
1249 std::cout <<
"FIND_PATCH_COMPONENTS\n";
1251 if (pinfo.tot_patch() == 0) {
1252 return Vector<Vector<int>>();
1254 int current_component = 0;
1255 Array<bool> cell_processed(cinfo.tot_cell(),
false);
1257 Vector<Vector<int>> ans;
1258 for (
int pstart : pinfo.index_range()) {
1259 Patch &patch_pstart = pinfo.patch(pstart);
1260 if (patch_pstart.component != NO_INDEX) {
1263 ans.append(Vector<int>());
1264 ans[current_component].append(pstart);
1266 patch_pstart.component = current_component;
1267 while (!stack.is_empty()) {
1268 int p = stack.pop();
1269 Patch &patch = pinfo.patch(p);
1270 BLI_assert(patch.component == current_component);
1271 for (
int c : {patch.cell_above, patch.cell_below}) {
1272 if (cell_processed[
c]) {
1275 cell_processed[
c] =
true;
1276 for (
int pn : cinfo.cell(
c).patches()) {
1277 Patch &patch_neighbor = pinfo.patch(pn);
1278 if (patch_neighbor.component == NO_INDEX) {
1279 patch_neighbor.component = current_component;
1281 ans[current_component].append(pn);
1286 ++current_component;
1288 if (dbg_level > 0) {
1289 std::cout <<
"found " << ans.size() <<
" components\n";
1290 for (
int comp : ans.index_range()) {
1291 std::cout << comp <<
": " << ans[comp] <<
"\n";
1301 static bool patch_cell_graph_ok(
const CellsInfo &cinfo,
const PatchesInfo &pinfo)
1303 for (
int c : cinfo.index_range()) {
1304 const Cell &cell = cinfo.cell(
c);
1305 if (cell.merged_to() != NO_INDEX) {
1308 if (cell.patches().size() == 0) {
1309 std::cout <<
"Patch/Cell graph disconnected at Cell " <<
c <<
" with no patches\n";
1312 for (
int p : cell.patches()) {
1313 if (p >= pinfo.tot_patch()) {
1314 std::cout <<
"Patch/Cell graph has bad patch index at Cell " <<
c <<
"\n";
1319 for (
int p : pinfo.index_range()) {
1320 const Patch &patch = pinfo.patch(p);
1321 if (patch.cell_above == NO_INDEX || patch.cell_below == NO_INDEX) {
1322 std::cout <<
"Patch/Cell graph disconnected at Patch " << p
1323 <<
" with one or two missing cells\n";
1326 if (patch.cell_above >= cinfo.tot_cell() || patch.cell_below >= cinfo.tot_cell()) {
1327 std::cout <<
"Patch/Cell graph has bad cell index at Patch " << p <<
"\n";
1347 static bool is_pwn(
const IMesh &tm,
const TriMeshTopology &tmtopo)
1349 constexpr
int dbg_level = 0;
1350 std::atomic<bool> is_pwn =
true;
1351 Vector<std::pair<Edge, Vector<int> *>> tris;
1353 for (
auto item : tmtopo.edge_tri_map_items()) {
1354 tris.append(std::pair<
Edge, Vector<int> *>(item.key, item.value));
1358 if (!is_pwn.load()) {
1363 for (
int j : range) {
1368 for (
int t : *tris[j].second) {
1369 const Face &face = *tm.face(
t);
1371 for (
int i : face.index_range()) {
1372 if (face[i] ==
edge.v0()) {
1373 if (face[(i + 1) % 3] ==
edge.v1()) {
1383 if (tot_orient != 0) {
1384 if (dbg_level > 0) {
1385 std::cout <<
"edge causing non-pwn: " <<
edge <<
"\n";
1392 return is_pwn.load();
1402 static int find_cell_for_point_near_edge(mpq3 p,
1405 const TriMeshTopology &tmtopo,
1406 const PatchesInfo &pinfo,
1409 constexpr
int dbg_level = 0;
1410 if (dbg_level > 0) {
1411 std::cout <<
"FIND_CELL_FOR_POINT_NEAR_EDGE, p=" << p <<
" e=" <<
e <<
"\n";
1413 const Vector<int> *etris = tmtopo.edge_tris(
e);
1414 const Vert *dummy_vert = arena->add_or_find_vert(p, NO_INDEX);
1415 const Face *dummy_tri = arena->add_face({
e.v0(),
e.v1(), dummy_vert},
1417 {NO_INDEX, NO_INDEX, NO_INDEX},
1418 {
false,
false,
false});
1420 Array<int> edge_tris(etris->size() + 1);
1421 std::copy(etris->begin(), etris->end(), edge_tris.begin());
1422 edge_tris[edge_tris.size() - 1] = EXTRA_TRI_INDEX;
1423 Array<int> sorted_tris = sort_tris_around_edge(tm,
e, edge_tris, edge_tris[0], dummy_tri);
1424 if (dbg_level > 0) {
1425 std::cout <<
"sorted tris = " << sorted_tris <<
"\n";
1427 int *p_sorted_dummy = std::find(sorted_tris.begin(), sorted_tris.end(), EXTRA_TRI_INDEX);
1428 BLI_assert(p_sorted_dummy != sorted_tris.end());
1429 int dummy_index = p_sorted_dummy - sorted_tris.begin();
1430 int prev_tri = (dummy_index == 0) ? sorted_tris[sorted_tris.size() - 1] :
1431 sorted_tris[dummy_index - 1];
1432 if (dbg_level > 0) {
1433 int next_tri = (dummy_index == sorted_tris.size() - 1) ? sorted_tris[0] :
1434 sorted_tris[dummy_index + 1];
1435 std::cout <<
"prev tri to dummy = " << prev_tri <<
"; next tri to dummy = " << next_tri
1438 const Patch &prev_patch = pinfo.patch(pinfo.tri_patch(prev_tri));
1439 if (dbg_level > 0) {
1440 std::cout <<
"prev_patch = " << prev_patch <<
"\n";
1443 find_flap_vert(*tm.face(prev_tri),
e, &prev_flipped);
1444 int c = prev_flipped ? prev_patch.cell_below : prev_patch.cell_above;
1445 if (dbg_level > 0) {
1446 std::cout <<
"find_cell_for_point_near_edge returns " <<
c <<
"\n";
1465 static int find_ambient_cell(
const IMesh &tm,
1466 const Vector<int> *component_patches,
1467 const TriMeshTopology &tmtopo,
1468 const PatchesInfo &pinfo,
1472 if (dbg_level > 0) {
1473 std::cout <<
"FIND_AMBIENT_CELL\n";
1477 const Vert *v_extreme;
1478 auto max_x_vert = [](
const Vert *
a,
const Vert *
b) {
1479 return (
a->co_exact.x >
b->co_exact.x) ?
a :
b;
1481 if (component_patches ==
nullptr) {
1483 tm.face_index_range(),
1486 [&](IndexRange range,
const Vert *
init) {
1487 const Vert *ans = init;
1488 for (int i : range) {
1489 const Face *f = tm.face(i);
1490 for (const Vert *v : *f) {
1491 if (v->co_exact.x > ans->co_exact.x) {
1501 if (dbg_level > 0) {
1502 std::cout <<
"restrict to patches " << *component_patches <<
"\n";
1504 int p0 = (*component_patches)[0];
1506 component_patches->index_range(),
1508 (*tm.face(pinfo.patch(p0).tri(0)))[0],
1509 [&](IndexRange range,
const Vert *
init) {
1510 const Vert *ans = init;
1511 for (int pi : range) {
1512 int p = (*component_patches)[pi];
1513 const Vert *tris_ans = threading::parallel_reduce(
1514 IndexRange(pinfo.patch(p).tot_tri()),
1517 [&](IndexRange tris_range, const Vert *t_init) {
1518 const Vert *v_ans = t_init;
1519 for (int i : tris_range) {
1520 int t = pinfo.patch(p).tri(i);
1521 const Face *f = tm.face(t);
1522 for (const Vert *v : *f) {
1523 if (v->co_exact.x > v_ans->co_exact.x) {
1531 if (tris_ans->co_exact.x > ans->co_exact.x) {
1539 if (dbg_level > 0) {
1540 std::cout <<
"v_extreme = " << v_extreme <<
"\n";
1545 const Vector<Edge> &edges = tmtopo.vert_edges(v_extreme);
1546 const mpq_class &extreme_x = v_extreme->co_exact.x;
1547 const mpq_class &extreme_y = v_extreme->co_exact.y;
1549 mpq_class max_abs_slope = -1;
1550 for (
Edge e : edges) {
1551 const Vert *v_other = (
e.v0() == v_extreme) ?
e.v1() :
e.v0();
1552 const mpq3 &co_other = v_other->co_exact;
1553 mpq_class delta_x = co_other.x - extreme_x;
1559 mpq_class abs_slope =
abs((co_other.y - extreme_y) / delta_x);
1560 if (abs_slope > max_abs_slope) {
1562 max_abs_slope = abs_slope;
1565 if (dbg_level > 0) {
1566 std::cout <<
"ehull = " << ehull <<
" slope = " << max_abs_slope <<
"\n";
1570 mpq3 p_in_ambient = v_extreme->co_exact;
1571 p_in_ambient.x += 1;
1572 int c_ambient = find_cell_for_point_near_edge(p_in_ambient, ehull, tm, tmtopo, pinfo, arena);
1573 if (dbg_level > 0) {
1574 std::cout <<
"FIND_AMBIENT_CELL returns " << c_ambient <<
"\n";
1588 static Edge find_good_sorting_edge(
const Vert *testp,
1589 const Vert *closestp,
1590 const TriMeshTopology &tmtopo)
1592 constexpr
int dbg_level = 0;
1593 if (dbg_level > 0) {
1594 std::cout <<
"FIND_GOOD_SORTING_EDGE testp = " << testp <<
", closestp = " << closestp <<
"\n";
1602 const mpq3 &co_closest = closestp->co_exact;
1603 const mpq3 &co_test = testp->co_exact;
1605 mpq3 abscissa = co_test - co_closest;
1608 for (axis = 0; axis < 3; ++axis) {
1609 if (abscissa[axis] != 0) {
1614 int axis_next = (axis + 1) % 3;
1615 int axis_next_next = (axis_next + 1) % 3;
1617 ordinate[axis] = abscissa[axis_next];
1618 ordinate[axis_next] = -abscissa[axis];
1619 ordinate[axis_next_next] = 0;
1622 if (dbg_level > 0) {
1623 std::cout <<
"abscissa = " << abscissa <<
"\n";
1624 std::cout <<
"ordinate = " << ordinate <<
"\n";
1625 std::cout <<
"normal = " <<
normal <<
"\n";
1628 mpq_class max_abs_slope = -1;
1630 const Vector<Edge> &edges = tmtopo.vert_edges(closestp);
1631 for (
Edge e : edges) {
1632 const Vert *v_other = (
e.v0() == closestp) ?
e.v1() :
e.v0();
1633 const mpq3 &co_other = v_other->co_exact;
1634 mpq3 evec = co_other - co_closest;
1640 mpq_class evec_a =
math::dot(proj_evec, abscissa);
1641 mpq_class evec_o =
math::dot(proj_evec, ordinate);
1642 if (dbg_level > 0) {
1643 std::cout <<
"e = " <<
e <<
"\n";
1644 std::cout <<
"v_other = " << v_other <<
"\n";
1645 std::cout <<
"evec = " << evec <<
", proj_evec = " << proj_evec <<
"\n";
1646 std::cout <<
"evec_a = " << evec_a <<
", evec_o = " << evec_o <<
"\n";
1651 if (dbg_level > 0) {
1652 std::cout <<
"perpendicular esort is " << esort <<
"\n";
1656 mpq_class abs_slope =
abs(evec_o / evec_a);
1657 if (abs_slope > max_abs_slope) {
1659 max_abs_slope = abs_slope;
1660 if (dbg_level > 0) {
1661 std::cout <<
"with abs_slope " << abs_slope <<
" new esort is " << esort <<
"\n";
1680 static int find_containing_cell(
const Vert *
v,
1684 const PatchesInfo &pinfo,
1686 const TriMeshTopology &tmtopo,
1689 constexpr
int dbg_level = 0;
1690 if (dbg_level > 0) {
1691 std::cout <<
"FIND_CONTAINING_CELL v=" <<
v <<
", t=" <<
t <<
"\n";
1693 const Face &tri = *tm.face(
t);
1695 if (close_edge == -1 && close_vert == -1) {
1699 if (close_edge != -1) {
1700 const Vert *v0 = tri[close_edge];
1701 const Vert *
v1 = tri[(close_edge + 1) % 3];
1702 const Vector<Edge> &edges = tmtopo.vert_edges(v0);
1703 if (dbg_level > 0) {
1704 std::cout <<
"look for edge containing " << v0 <<
" and " <<
v1 <<
"\n";
1705 std::cout <<
" in edges: ";
1706 for (
Edge e : edges) {
1707 std::cout <<
e <<
" ";
1711 for (
Edge e : edges) {
1712 if ((
e.v0() == v0 &&
e.v1() ==
v1) || (
e.v0() ==
v1 &&
e.v1() == v0)) {
1719 int cv = close_vert;
1720 const Vert *vert_cv = tri[cv];
1723 vert_cv = tri[(cv + 1) % 3];
1726 etest = find_good_sorting_edge(
v, vert_cv, tmtopo);
1729 if (dbg_level > 0) {
1730 std::cout <<
"etest = " << etest <<
"\n";
1732 int c = find_cell_for_point_near_edge(
v->co_exact, etest, tm, tmtopo, pinfo, arena);
1733 if (dbg_level > 0) {
1734 std::cout <<
"find_containing_cell returns " <<
c <<
"\n";
1752 static mpq_class closest_on_tri_to_point(
const mpq3 &p,
1766 constexpr
int dbg_level = 0;
1767 if (dbg_level > 0) {
1768 std::cout <<
"CLOSEST_ON_TRI_TO_POINT p = " << p <<
"\n";
1769 std::cout <<
" a = " <<
a <<
", b = " <<
b <<
", c = " <<
c <<
"\n";
1779 mpq_class d1 = math::dot_with_buffer(ab, ap, m);
1780 mpq_class d2 = math::dot_with_buffer(ac, ap, m);
1781 if (d1 <= 0 && d2 <= 0) {
1785 if (dbg_level > 0) {
1786 std::cout <<
" answer = a\n";
1788 return math::distance_squared_with_buffer(p,
a, m);
1793 mpq_class d3 = math::dot_with_buffer(ab, bp, m);
1794 mpq_class d4 = math::dot_with_buffer(ac, bp, m);
1795 if (d3 >= 0 && d4 <= d3) {
1799 if (dbg_level > 0) {
1800 std::cout <<
" answer = b\n";
1802 return math::distance_squared_with_buffer(p,
b, m);
1805 mpq_class vc = d1 * d4 - d3 * d2;
1806 if (vc <= 0 && d1 >= 0 && d3 <= 0) {
1807 mpq_class
v = d1 / (d1 - d3);
1814 if (dbg_level > 0) {
1815 std::cout <<
" answer = on ab at " <<
r <<
"\n";
1817 return math::distance_squared_with_buffer(p,
r, m);
1822 mpq_class d5 = math::dot_with_buffer(ab, cp, m);
1823 mpq_class d6 = math::dot_with_buffer(ac, cp, m);
1824 if (d6 >= 0 && d5 <= d6) {
1828 if (dbg_level > 0) {
1829 std::cout <<
" answer = c\n";
1831 return math::distance_squared_with_buffer(p,
c, m);
1834 mpq_class vb = d5 * d2 - d1 * d6;
1835 if (vb <= 0 && d2 >= 0 && d6 <= 0) {
1836 mpq_class
w = d2 / (d2 - d6);
1843 if (dbg_level > 0) {
1844 std::cout <<
" answer = on ac at " <<
r <<
"\n";
1846 return math::distance_squared_with_buffer(p,
r, m);
1849 mpq_class va = d3 * d6 - d5 * d4;
1850 if (va <= 0 && (d4 - d3) >= 0 && (d5 - d6) >= 0) {
1851 mpq_class
w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
1859 if (dbg_level > 0) {
1860 std::cout <<
" answer = on bc at " <<
r <<
"\n";
1862 return math::distance_squared_with_buffer(p,
r, m);
1865 mpq_class denom = 1 / (va + vb + vc);
1866 mpq_class
v = vb * denom;
1867 mpq_class
w = vc * denom;
1875 if (dbg_level > 0) {
1876 std::cout <<
" answer = inside at " <<
r <<
"\n";
1878 return math::distance_squared_with_buffer(p,
r, m);
1881 static float closest_on_tri_to_point_float_dist_squared(
const float3 &p,
1894 struct ComponentContainer {
1895 int containing_component{NO_INDEX};
1896 int nearest_cell{NO_INDEX};
1897 mpq_class dist_to_cell;
1899 ComponentContainer(
int cc,
int cell, mpq_class d)
1900 : containing_component(cc), nearest_cell(cell), dist_to_cell(
d)
1911 static Vector<ComponentContainer> find_component_containers(
int comp,
1912 const Vector<Vector<int>> &components,
1913 const Array<int> &ambient_cell,
1915 const PatchesInfo &pinfo,
1916 const TriMeshTopology &tmtopo,
1917 Array<BoundingBox> &comp_bb,
1920 constexpr
int dbg_level = 0;
1921 if (dbg_level > 0) {
1922 std::cout <<
"FIND_COMPONENT_CONTAINERS for comp " << comp <<
"\n";
1924 Vector<ComponentContainer> ans;
1925 int test_p = components[comp][0];
1926 int test_t = pinfo.patch(test_p).tri(0);
1927 const Vert *test_v = tm.face(test_t)[0].vert[0];
1928 if (dbg_level > 0) {
1929 std::cout <<
"test vertex in comp: " << test_v <<
"\n";
1931 const double3 &test_v_d = test_v->co;
1932 float3 test_v_f(test_v_d[0], test_v_d[1], test_v_d[2]);
1936 for (
int comp_other : components.index_range()) {
1937 if (comp == comp_other) {
1940 if (dbg_level > 0) {
1941 std::cout <<
"comp_other = " << comp_other <<
"\n";
1943 if (!bbs_might_intersect(comp_bb[comp], comp_bb[comp_other])) {
1944 if (dbg_level > 0) {
1945 std::cout <<
"bounding boxes don't overlap\n";
1949 int nearest_tri = NO_INDEX;
1950 int nearest_tri_close_vert = -1;
1951 int nearest_tri_close_edge = -1;
1952 mpq_class nearest_tri_dist_squared;
1953 float nearest_tri_dist_squared_float = FLT_MAX;
1954 for (
int p : components[comp_other]) {
1955 const Patch &patch = pinfo.patch(p);
1956 for (
int t : patch.tris()) {
1957 const Face &tri = *tm.face(
t);
1958 if (dbg_level > 1) {
1959 std::cout <<
"tri " <<
t <<
" = " << &tri <<
"\n";
1964 float d2_f = closest_on_tri_to_point_float_dist_squared(
1965 test_v_f, tri[0]->co, tri[1]->co, tri[2]->co);
1966 if (d2_f - FLT_EPSILON > nearest_tri_dist_squared_float) {
1969 mpq_class d2 = closest_on_tri_to_point(test_v->co_exact,
1982 if (dbg_level > 1) {
1983 std::cout <<
" close_edge=" << close_edge <<
" close_vert=" << close_vert
1984 <<
" dsquared=" << d2.get_d() <<
"\n";
1986 if (nearest_tri == NO_INDEX || d2 < nearest_tri_dist_squared) {
1988 nearest_tri_close_edge = close_edge;
1989 nearest_tri_close_vert = close_vert;
1990 nearest_tri_dist_squared = d2;
1991 nearest_tri_dist_squared_float = d2_f;
1995 if (dbg_level > 0) {
1996 std::cout <<
"closest tri to comp=" << comp <<
" in comp_other=" << comp_other <<
" is t"
1997 << nearest_tri <<
"\n";
1998 const Face *tn = tm.face(nearest_tri);
1999 std::cout <<
"tri = " << tn <<
"\n";
2000 std::cout <<
" (" << tn->vert[0]->co <<
"," << tn->vert[1]->co <<
"," << tn->vert[2]->co
2003 int containing_cell = find_containing_cell(test_v,
2005 nearest_tri_close_edge,
2006 nearest_tri_close_vert,
2012 if (dbg_level > 0) {
2013 std::cout <<
"containing cell = " << containing_cell <<
"\n";
2015 if (containing_cell != ambient_cell[comp_other]) {
2016 ans.append(ComponentContainer(comp_other, containing_cell, nearest_tri_dist_squared));
2027 static void populate_comp_bbs(
const Vector<Vector<int>> &components,
2028 const PatchesInfo &pinfo,
2030 Array<BoundingBox> &comp_bb)
2032 const int comp_grainsize = 16;
2036 Array<double> max_abs(components.size(), 0.0);
2038 for (int c : comp_range) {
2039 BoundingBox &bb = comp_bb[c];
2040 double &maxa = max_abs[c];
2041 for (int p : components[c]) {
2042 const Patch &patch = pinfo.patch(p);
2043 for (int t : patch.tris()) {
2044 const Face &tri = *im.face(t);
2045 for (const Vert *v : tri) {
2047 for (int i = 0; i < 3; ++i) {
2048 maxa = max_dd(maxa, fabs(v->co[i]));
2055 double all_max_abs = 0.0;
2056 for (
int c : components.index_range()) {
2057 all_max_abs =
max_dd(all_max_abs, max_abs[
c]);
2059 constexpr
float pad_factor = 10.0f;
2060 float pad = all_max_abs == 0.0 ? FLT_EPSILON : 2 * FLT_EPSILON * all_max_abs;
2062 for (
int c : components.index_range()) {
2063 comp_bb[
c].expand(
pad);
2074 static void finish_patch_cell_graph(
const IMesh &tm,
2077 const TriMeshTopology &tmtopo,
2080 constexpr
int dbg_level = 0;
2081 if (dbg_level > 0) {
2082 std::cout <<
"FINISH_PATCH_CELL_GRAPH\n";
2084 Vector<Vector<int>> components = find_patch_components(cinfo, pinfo);
2085 if (components.size() <= 1) {
2086 if (dbg_level > 0) {
2087 std::cout <<
"one component so finish_patch_cell_graph does no work\n";
2091 if (dbg_level > 0) {
2092 std::cout <<
"components:\n";
2093 for (
int comp : components.index_range()) {
2094 std::cout << comp <<
": " << components[comp] <<
"\n";
2097 Array<int> ambient_cell(components.size());
2098 for (
int comp : components.index_range()) {
2099 ambient_cell[comp] = find_ambient_cell(tm, &components[comp], tmtopo, pinfo, arena);
2101 if (dbg_level > 0) {
2102 std::cout <<
"ambient cells:\n";
2103 for (
int comp : ambient_cell.index_range()) {
2104 std::cout << comp <<
": " << ambient_cell[comp] <<
"\n";
2107 int tot_components = components.size();
2108 Array<Vector<ComponentContainer>> comp_cont(tot_components);
2109 if (tot_components > 1) {
2110 Array<BoundingBox> comp_bb(tot_components);
2111 populate_comp_bbs(components, pinfo, tm, comp_bb);
2112 for (
int comp : components.index_range()) {
2113 comp_cont[comp] = find_component_containers(
2114 comp, components, ambient_cell, tm, pinfo, tmtopo, comp_bb, arena);
2116 if (dbg_level > 0) {
2117 std::cout <<
"component containers:\n";
2118 for (
int comp : comp_cont.index_range()) {
2119 std::cout << comp <<
": ";
2120 for (
const ComponentContainer &cc : comp_cont[comp]) {
2121 std::cout <<
"[containing_comp=" << cc.containing_component
2122 <<
", nearest_cell=" << cc.nearest_cell <<
", d2=" << cc.dist_to_cell <<
"] ";
2128 if (dbg_level > 1) {
2129 write_obj_cell_patch(tm, cinfo, pinfo,
false,
"beforemerge");
2132 Vector<int> outer_components;
2133 for (
int comp : comp_cont.index_range()) {
2134 if (comp_cont[comp].
size() == 0) {
2135 outer_components.append(comp);
2138 ComponentContainer &
closest = comp_cont[comp][0];
2139 for (
int i = 1; i < comp_cont[comp].size(); ++i) {
2140 if (comp_cont[comp][i].dist_to_cell <
closest.dist_to_cell) {
2144 int comp_ambient = ambient_cell[comp];
2145 int cont_cell =
closest.nearest_cell;
2146 if (dbg_level > 0) {
2147 std::cout <<
"merge comp " << comp <<
"'s ambient cell=" << comp_ambient <<
" to cell "
2148 << cont_cell <<
"\n";
2150 merge_cells(cont_cell, comp_ambient, cinfo, pinfo);
2154 if (outer_components.size() > 1) {
2155 int merged_ambient = ambient_cell[outer_components[0]];
2156 for (
int i = 1; i < outer_components.size(); ++i) {
2157 if (dbg_level > 0) {
2158 std::cout <<
"merge comp " << outer_components[i]
2159 <<
"'s ambient cell=" << ambient_cell[outer_components[i]] <<
" to cell "
2160 << merged_ambient <<
"\n";
2162 merge_cells(merged_ambient, ambient_cell[outer_components[i]], cinfo, pinfo);
2165 if (dbg_level > 0) {
2166 std::cout <<
"after FINISH_PATCH_CELL_GRAPH\nCells\n";
2167 for (
int i : cinfo.index_range()) {
2168 if (cinfo.cell(i).merged_to() == NO_INDEX) {
2169 std::cout << i <<
": " << cinfo.cell(i) <<
"\n";
2172 std::cout <<
"Patches\n";
2173 for (
int i : pinfo.index_range()) {
2174 std::cout << i <<
": " << pinfo.patch(i) <<
"\n";
2176 if (dbg_level > 1) {
2177 write_obj_cell_patch(tm, cinfo, pinfo,
false,
"finished");
2195 static void propagate_windings_and_in_output_volume(PatchesInfo &pinfo,
2200 std::function<
int(
int)> shape_fn)
2203 if (dbg_level > 0) {
2204 std::cout <<
"PROPAGATE_WINDINGS, ambient cell = " << c_ambient <<
"\n";
2206 Cell &cell_ambient = cinfo.cell(c_ambient);
2207 cell_ambient.seed_ambient_winding();
2210 queue.reserve(cinfo.tot_cell());
2212 queue.append(c_ambient);
2213 while (queue_head <
queue.size()) {
2214 int c =
queue[queue_head++];
2215 if (dbg_level > 1) {
2216 std::cout <<
"process cell " <<
c <<
"\n";
2218 Cell &cell = cinfo.cell(
c);
2219 for (
int p : cell.patches()) {
2220 Patch &patch = pinfo.patch(p);
2221 bool p_above_c = patch.cell_below ==
c;
2222 int c_neighbor = p_above_c ? patch.cell_above : patch.cell_below;
2223 if (dbg_level > 1) {
2224 std::cout <<
" patch " << p <<
" p_above_c = " << p_above_c <<
"\n";
2225 std::cout <<
" c_neighbor = " << c_neighbor <<
"\n";
2227 Cell &cell_neighbor = cinfo.cell(c_neighbor);
2228 if (!cell_neighbor.winding_assigned()) {
2229 int winding_delta = p_above_c ? -1 : 1;
2230 int t = patch.tri(0);
2231 int shape = shape_fn(
t);
2234 if (dbg_level > 1) {
2235 std::cout <<
" representative tri " <<
t <<
": in shape " << shape <<
"\n";
2237 cell_neighbor.set_winding_and_in_output_volume(cell, shape, winding_delta, op);
2238 if (dbg_level > 1) {
2239 std::cout <<
" now cell_neighbor = " << cell_neighbor <<
"\n";
2241 queue.append(c_neighbor);
2246 if (dbg_level > 0) {
2247 std::cout <<
"\nPROPAGATE_WINDINGS result\n";
2248 for (
int i = 0; i < cinfo.tot_cell(); ++i) {
2249 std::cout << i <<
": " << cinfo.cell(i) <<
"\n";
2263 static bool apply_bool_op(BoolOpType bool_optype,
const Array<int> &winding)
2265 int nw = winding.size();
2267 switch (bool_optype) {
2269 for (
int i = 0; i < nw; ++i) {
2270 if (winding[i] == 0) {
2276 case BoolOpType::Union: {
2277 for (
int i = 0; i < nw; ++i) {
2278 if (winding[i] != 0) {
2284 case BoolOpType::Difference: {
2286 if (winding[0] == 0) {
2292 for (
int i = 1; i < nw; ++i) {
2293 if (winding[i] >= 1) {
2309 static void extract_zero_volume_cell_tris(Vector<Face *> &r_tris,
2310 const IMesh &tm_subdivided,
2311 const PatchesInfo &pinfo,
2312 const CellsInfo &cinfo,
2316 if (dbg_level > 0) {
2317 std::cout <<
"extract_zero_volume_cell_tris\n";
2320 Array<bool> adj_to_zv(pinfo.tot_patch());
2321 for (
int p : pinfo.index_range()) {
2322 const Patch &patch = pinfo.patch(p);
2323 if (cinfo.cell(patch.cell_above).zero_volume() || cinfo.cell(patch.cell_below).zero_volume()) {
2324 adj_to_zv[p] =
true;
2327 adj_to_zv[p] =
false;
2331 Vector<Vector<int>> patch_stacks;
2332 Array<bool> allocated_to_stack(pinfo.tot_patch(),
false);
2333 for (
int p : pinfo.index_range()) {
2334 if (!adj_to_zv[p] || allocated_to_stack[p]) {
2337 int stack_index = patch_stacks.size();
2338 patch_stacks.append(Vector<int>{p});
2339 Vector<int> &stack = patch_stacks[stack_index];
2340 Vector<bool> flipped{
false};
2341 allocated_to_stack[p] =
true;
2348 const Patch *pwalk_patch = &pinfo.patch(pwalk);
2349 int c = pwalk_patch->cell_above;
2350 const Cell *cell = &cinfo.cell(
c);
2351 while (cell->zero_volume()) {
2354 int pother = cell->patch_other(pwalk);
2355 bool flip = pinfo.patch(pother).cell_above ==
c;
2356 flipped.append(flip);
2357 stack.append(pother);
2358 allocated_to_stack[pother] =
true;
2360 pwalk_patch = &pinfo.patch(pwalk);
2361 c = flip ? pwalk_patch->cell_below : pwalk_patch->cell_above;
2362 cell = &cinfo.cell(
c);
2364 const Cell *above_stack_cell = cell;
2367 pwalk_patch = &pinfo.patch(pwalk);
2368 c = pwalk_patch->cell_below;
2369 cell = &cinfo.cell(
c);
2370 while (cell->zero_volume()) {
2372 int pother = cell->patch_other(pwalk);
2373 bool flip = pinfo.patch(pother).cell_below ==
c;
2374 flipped.append(flip);
2375 stack.append(pother);
2376 allocated_to_stack[pother] =
true;
2378 pwalk_patch = &pinfo.patch(pwalk);
2379 c = flip ? pwalk_patch->cell_above : pwalk_patch->cell_below;
2380 cell = &cinfo.cell(
c);
2382 const Cell *below_stack_cell = cell;
2383 if (dbg_level > 0) {
2384 std::cout <<
"process zero-volume patch stack " << stack <<
"\n";
2385 std::cout <<
"flipped = ";
2386 for (
bool b : flipped) {
2387 std::cout <<
b <<
" ";
2391 if (above_stack_cell->in_output_volume() ^ below_stack_cell->in_output_volume()) {
2392 bool need_flipped_tri = above_stack_cell->in_output_volume();
2393 if (dbg_level > 0) {
2394 std::cout <<
"need tri " << (need_flipped_tri ?
"flipped" :
"") <<
"\n";
2396 int t_to_add = NO_INDEX;
2397 for (
int i : stack.index_range()) {
2398 if (flipped[i] == need_flipped_tri) {
2399 t_to_add = pinfo.patch(stack[i]).tri(0);
2400 if (dbg_level > 0) {
2401 std::cout <<
"using tri " << t_to_add <<
"\n";
2403 r_tris.append(tm_subdivided.face(t_to_add));
2407 if (t_to_add == NO_INDEX) {
2408 const Face *f = tm_subdivided.face(pinfo.patch(p).tri(0));
2409 const Face &tri = *f;
2411 std::array<const Vert *, 3> flipped_vs = {tri[0], tri[2], tri[1]};
2412 std::array<int, 3> flipped_e_origs = {
2413 tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
2414 std::array<bool, 3> flipped_is_intersect = {
2415 tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
2416 Face *flipped_f = arena->add_face(
2417 flipped_vs, f->orig, flipped_e_origs, flipped_is_intersect);
2418 r_tris.append(flipped_f);
2435 static IMesh extract_from_in_output_volume_diffs(
const IMesh &tm_subdivided,
2436 const PatchesInfo &pinfo,
2437 const CellsInfo &cinfo,
2440 constexpr
int dbg_level = 0;
2441 if (dbg_level > 0) {
2442 std::cout <<
"\nEXTRACT_FROM_FLAG_DIFFS\n";
2444 Vector<Face *> out_tris;
2445 out_tris.reserve(tm_subdivided.face_size());
2446 bool any_zero_volume_cell =
false;
2447 for (
int t : tm_subdivided.face_index_range()) {
2448 int p = pinfo.tri_patch(
t);
2449 const Patch &patch = pinfo.patch(p);
2450 const Cell &cell_above = cinfo.cell(patch.cell_above);
2451 const Cell &cell_below = cinfo.cell(patch.cell_below);
2452 if (dbg_level > 0) {
2453 std::cout <<
"tri " <<
t <<
": cell_above=" << patch.cell_above
2454 <<
" cell_below=" << patch.cell_below <<
"\n";
2455 std::cout <<
" in_output_volume_above=" << cell_above.in_output_volume()
2456 <<
" in_output_volume_below=" << cell_below.in_output_volume() <<
"\n";
2458 bool adjacent_zero_volume_cell = cell_above.zero_volume() || cell_below.zero_volume();
2459 any_zero_volume_cell |= adjacent_zero_volume_cell;
2460 if (cell_above.in_output_volume() ^ cell_below.in_output_volume() &&
2461 !adjacent_zero_volume_cell) {
2462 bool flip = cell_above.in_output_volume();
2463 if (dbg_level > 0) {
2464 std::cout <<
"need tri " <<
t <<
" flip=" << flip <<
"\n";
2466 Face *f = tm_subdivided.face(
t);
2469 std::array<const Vert *, 3> flipped_vs = {tri[0], tri[2], tri[1]};
2470 std::array<int, 3> flipped_e_origs = {
2471 tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
2472 std::array<bool, 3> flipped_is_intersect = {
2473 tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
2474 Face *flipped_f = arena->add_face(
2475 flipped_vs, f->orig, flipped_e_origs, flipped_is_intersect);
2476 out_tris.append(flipped_f);
2483 if (any_zero_volume_cell) {
2484 extract_zero_volume_cell_tris(out_tris, tm_subdivided, pinfo, cinfo, arena);
2486 return IMesh(out_tris);
2489 static const char *bool_optype_name(BoolOpType op)
2492 case BoolOpType::None:
2496 case BoolOpType::Union:
2498 case BoolOpType::Difference:
2499 return "difference";
2505 static double3 calc_point_inside_tri_db(
const Face &tri)
2507 const Vert *v0 = tri.vert[0];
2508 const Vert *
v1 = tri.vert[1];
2509 const Vert *
v2 = tri.vert[2];
2513 class InsideShapeTestData {
2516 std::function<int(
int)> shape_fn;
2519 Array<int> hit_parity;
2521 InsideShapeTestData(
const IMesh &tm, std::function<
int(
int)> shape_fn,
int nshapes)
2522 : tm(tm), shape_fn(shape_fn), nshapes(nshapes)
2527 static void inside_shape_callback(
void *userdata,
2532 const int dbg_level = 0;
2533 if (dbg_level > 0) {
2534 std::cout <<
"inside_shape_callback, index = " << index <<
"\n";
2536 InsideShapeTestData *
data =
static_cast<InsideShapeTestData *
>(userdata);
2537 const Face &tri = *
data->tm.face(index);
2538 int shape =
data->shape_fn(tri.orig);
2546 for (
int i = 0; i < 3; ++i) {
2547 fv0[i] =
float(tri.vert[0]->co[i]);
2548 fv1[i] =
float(tri.vert[1]->co[i]);
2549 fv2[i] =
float(tri.vert[2]->co[i]);
2551 if (dbg_level > 0) {
2552 std::cout <<
" fv0=(" << fv0[0] <<
"," << fv0[1] <<
"," << fv0[2] <<
")\n";
2553 std::cout <<
" fv1=(" << fv1[0] <<
"," << fv1[1] <<
"," << fv1[2] <<
")\n";
2554 std::cout <<
" fv2=(" << fv2[0] <<
"," << fv2[1] <<
"," << fv2[2] <<
")\n";
2557 ray->
origin, ray->
direction, fv0, fv1, fv2, &dist,
nullptr, FLT_EPSILON)) {
2561 int parity =
orient3d(tri.vert[0]->co, tri.vert[1]->co, tri.vert[2]->co, o_db);
2562 if (dbg_level > 0) {
2563 std::cout <<
"origin at " << o_db <<
", parity = " << parity <<
"\n";
2565 data->hit_parity[shape] += parity;
2578 static void test_tri_inside_shapes(
const IMesh &tm,
2579 std::function<
int(
int)> shape_fn,
2583 Array<float> &in_shape)
2585 const int dbg_level = 0;
2586 if (dbg_level > 0) {
2587 std::cout <<
"test_point_inside_shapes, t_index = " << test_t_index <<
"\n";
2589 Face &tri_test = *tm.face(test_t_index);
2590 int shape = shape_fn(tri_test.orig);
2592 in_shape.fill(0.0f);
2595 double3 test_point = calc_point_inside_tri_db(tri_test);
2597 tri_test.populate_plane(
false);
2599 const double offset_amount = 1
e-5;
2600 double3 offset_test_point = test_point + offset_amount *
norm;
2601 if (dbg_level > 0) {
2602 std::cout <<
"test tri is in shape " << shape <<
"\n";
2603 std::cout <<
"test point = " << test_point <<
"\n";
2604 std::cout <<
"offset_test_point = " << offset_test_point <<
"\n";
2610 constexpr
int rays_num = 6;
2611 constexpr
float r1 = 0.9987025295199663f;
2612 constexpr
float ra = 0.04993512647599832f;
2613 constexpr
float rb = 0.009987025295199663f;
2614 const float test_rays[rays_num][3] = {
2615 {r1, ra, rb}, {-r1, -ra, -rb}, {rb, r1, ra}, {-rb, -r1, -ra}, {ra, rb, r1}, {-ra, -rb, -r1}};
2616 InsideShapeTestData
data(tm, shape_fn, nshapes);
2617 data.hit_parity = Array<int>(nshapes, 0);
2618 Array<int> count_insides(nshapes, 0);
2619 const float co[3] = {
2620 float(offset_test_point[0]),
float(offset_test_point[1]),
float(offset_test_point[2])};
2621 for (
int i = 0; i < rays_num; ++i) {
2622 if (dbg_level > 0) {
2623 std::cout <<
"shoot ray " << i <<
"(" << test_rays[i][0] <<
"," << test_rays[i][1] <<
","
2624 << test_rays[i][2] <<
")\n";
2627 if (dbg_level > 0) {
2628 std::cout <<
"ray " << i <<
" result:";
2629 for (
int j = 0; j < nshapes; ++j) {
2630 std::cout <<
" " <<
data.hit_parity[j];
2634 for (
int j = 0; j < nshapes; ++j) {
2635 if (j != shape &&
data.hit_parity[j] > 0) {
2639 data.hit_parity.fill(0);
2641 for (
int j = 0; j < nshapes; ++j) {
2646 in_shape[j] =
float(count_insides[j]) /
float(rays_num);
2648 if (dbg_level > 0) {
2649 std::cout <<
"shape " << j <<
" inside = " << in_shape[j] <<
"\n";
2660 static BVHTree *raycast_tree(
const IMesh &tm)
2663 for (
int i : tm.face_index_range()) {
2664 const Face *f = tm.face(i);
2666 for (
int j = 0; j < 3; ++j) {
2667 const Vert *
v = f->vert[j];
2668 for (
int k = 0; k < 3; ++k) {
2669 t_cos[3 * j + k] =
float(
v->
co[k]);
2682 static bool raycast_test_remove(BoolOpType op, Array<int> &winding,
int shape,
bool *r_do_flip)
2684 constexpr
int dbg_level = 0;
2690 bool in_output_volume_0 = apply_bool_op(op, winding);
2692 bool in_output_volume_1 = apply_bool_op(op, winding);
2693 bool do_remove = in_output_volume_0 == in_output_volume_1;
2694 bool do_flip = !do_remove && op == BoolOpType::Difference && shape != 0;
2695 if (dbg_level > 0) {
2696 std::cout <<
"winding = ";
2697 for (
int i = 0; i < winding.size(); ++i) {
2698 std::cout << winding[i] <<
" ";
2700 std::cout <<
"\niv0=" << in_output_volume_0 <<
", iv1=" << in_output_volume_1 <<
"\n";
2701 std::cout <<
" remove=" << do_remove <<
", flip=" << do_flip <<
"\n";
2703 *r_do_flip = do_flip;
2708 static void raycast_add_flipped(Vector<Face *> &out_faces,
Face &tri, IMeshArena *arena)
2711 Array<const Vert *> flipped_vs = {tri[0], tri[2], tri[1]};
2712 Array<int> flipped_e_origs = {tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
2713 Array<bool> flipped_is_intersect = {
2714 tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
2715 Face *flipped_f = arena->add_face(flipped_vs, tri.orig, flipped_e_origs, flipped_is_intersect);
2716 out_faces.append(flipped_f);
2727 static IMesh raycast_tris_boolean(
const IMesh &tm,
2730 std::function<
int(
int)> shape_fn,
2733 constexpr
int dbg_level = 0;
2734 if (dbg_level > 0) {
2735 std::cout <<
"RAYCAST_TRIS_BOOLEAN\n";
2739 Vector<Face *> out_faces;
2740 out_faces.reserve(tm.face_size());
2742 tbb::spin_mutex mtx;
2744 const int grainsize = 256;
2746 Array<float> in_shape(nshapes, 0);
2747 Array<int> winding(nshapes, 0);
2748 for (int t : range) {
2749 Face &tri = *tm.face(t);
2750 int shape = shape_fn(tri.orig);
2751 if (dbg_level > 0) {
2752 std::cout <<
"process triangle " << t <<
" = " << &tri <<
"\n";
2753 std::cout <<
"shape = " << shape <<
"\n";
2755 test_tri_inside_shapes(tm, shape_fn, nshapes, t, tree, in_shape);
2756 for (int other_shape = 0; other_shape < nshapes; ++other_shape) {
2757 if (other_shape == shape) {
2767 bool need_high_confidence = (op == BoolOpType::Difference && shape != 0) ||
2768 op == BoolOpType::Intersect;
2769 bool inside = in_shape[other_shape] >= (need_high_confidence ? 0.5f : 0.1f);
2770 if (dbg_level > 0) {
2771 std::cout <<
"test point is " << (inside ?
"inside" :
"outside") <<
" other_shape "
2772 << other_shape <<
" val = " << in_shape[other_shape] <<
"\n";
2774 winding[other_shape] = inside;
2777 bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
2780 tbb::spin_mutex::scoped_lock lock(mtx);
2784 out_faces.append(&tri);
2787 raycast_add_flipped(out_faces, tri, arena);
2794 ans.set_faces(out_faces);
2802 static IMesh raycast_patches_boolean(
const IMesh &tm,
2805 std::function<
int(
int)> shape_fn,
2806 const PatchesInfo &pinfo,
2809 constexpr
int dbg_level = 0;
2810 if (dbg_level > 0) {
2811 std::cout <<
"RAYCAST_PATCHES_BOOLEAN\n";
2815 Vector<Face *> out_faces;
2816 out_faces.reserve(tm.face_size());
2817 Array<float> in_shape(nshapes, 0);
2818 Array<int> winding(nshapes, 0);
2819 for (
int p : pinfo.index_range()) {
2820 const Patch &patch = pinfo.patch(p);
2823 int test_t_index = patch.tri(patch.tot_tri() / 2);
2824 Face &tri_test = *tm.face(test_t_index);
2826 int shape = shape_fn(tri_test.orig);
2827 if (dbg_level > 0) {
2828 std::cout <<
"process patch " << p <<
" = " << patch <<
"\n";
2829 std::cout <<
"test tri = " << test_t_index <<
" = " << &tri_test <<
"\n";
2830 std::cout <<
"shape = " << shape <<
"\n";
2835 test_tri_inside_shapes(tm, shape_fn, nshapes, test_t_index,
tree, in_shape);
2836 for (
int other_shape = 0; other_shape < nshapes; ++other_shape) {
2837 if (other_shape == shape) {
2840 bool need_high_confidence = (op == BoolOpType::Difference && shape != 0) ||
2842 bool inside = in_shape[other_shape] >= (need_high_confidence ? 0.5f : 0.1f);
2843 if (dbg_level > 0) {
2844 std::cout <<
"test point is " << (inside ?
"inside" :
"outside") <<
" other_shape "
2845 << other_shape <<
" val = " << in_shape[other_shape] <<
"\n";
2847 winding[other_shape] = inside;
2850 bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
2852 for (
int t : patch.tris()) {
2853 Face *f = tm.face(
t);
2855 out_faces.append(f);
2858 raycast_add_flipped(out_faces, *f, arena);
2865 ans.set_faces(out_faces);
2873 static std::pair<int, int> find_tris_common_edge(
const Face &tri1,
const Face &tri2)
2875 for (
int i = 0; i < 3; ++i) {
2876 for (
int j = 0; j < 3; ++j) {
2877 if (tri1[(i + 1) % 3] == tri2[j] && tri1[i] == tri2[(j + 1) % 3]) {
2878 return std::pair<int, int>(i, j);
2882 return std::pair<int, int>(-1, -1);
2889 const Vert *
v1 =
nullptr;
2890 const Vert *
v2 =
nullptr;
2893 int right_face = -1;
2896 bool dissolvable =
false;
2898 bool is_intersect =
false;
2900 MergeEdge() =
default;
2902 MergeEdge(
const Vert *va,
const Vert *vb)
2904 if (va->id < vb->id) {
2917 Vector<const Vert *> vert;
2925 struct FaceMergeState {
2929 Vector<MergeFace> face;
2934 Vector<MergeEdge>
edge;
2939 Map<std::pair<int, int>,
int> edge_map;
2942 static std::ostream &
operator<<(std::ostream &os,
const FaceMergeState &fms)
2945 for (
int f : fms.face.index_range()) {
2946 const MergeFace &mf = fms.face[f];
2947 std::cout << f <<
": orig=" << mf.orig <<
" verts ";
2948 for (
const Vert *
v : mf.vert) {
2949 std::cout <<
v <<
" ";
2952 std::cout <<
" edges " << mf.edge <<
"\n";
2953 std::cout <<
" merge_to = " << mf.merge_to <<
"\n";
2956 for (
int e : fms.edge.index_range()) {
2957 const MergeEdge &me = fms.edge[
e];
2958 std::cout <<
e <<
": (" << me.v1 <<
"," << me.v2 <<
") left=" << me.left_face
2959 <<
" right=" << me.right_face <<
" dis=" << me.dissolvable <<
" orig=" << me.orig
2960 <<
" is_int=" << me.is_intersect <<
"\n";
2975 static void init_face_merge_state(FaceMergeState *fms,
2976 const Vector<int> &tris,
2980 constexpr
int dbg_level = 0;
2982 fms->face.reserve(tris.size() + 1);
2983 fms->edge.reserve(3 * tris.size());
2984 fms->edge_map.reserve(3 * tris.size());
2985 if (dbg_level > 0) {
2986 std::cout <<
"\nINIT_FACE_MERGE_STATE\n";
2988 for (
int t : tris.index_range()) {
2990 const Face &tri = *tm.face(tris[
t]);
2991 if (dbg_level > 0) {
2992 std::cout <<
"process tri = " << &tri <<
"\n";
2996 if (dbg_level > 0) {
2997 std::cout <<
"triangle has wrong orientation, skipping\n";
3001 mf.vert.append(tri[0]);
3002 mf.vert.append(tri[1]);
3003 mf.vert.append(tri[2]);
3005 int f = fms->face.append_and_get_index(mf);
3006 if (dbg_level > 1) {
3007 std::cout <<
"appended MergeFace for tri at f = " << f <<
"\n";
3009 for (
int i = 0; i < 3; ++i) {
3010 int inext = (i + 1) % 3;
3011 MergeEdge new_me(mf.vert[i], mf.vert[inext]);
3012 std::pair<int, int> canon_vs(new_me.v1->id, new_me.v2->id);
3013 int me_index = fms->edge_map.lookup_default(canon_vs, -1);
3014 if (dbg_level > 1) {
3015 std::cout <<
"new_me = canon_vs = " << new_me.v1 <<
", " << new_me.v2 <<
"\n";
3016 std::cout <<
"me_index lookup = " << me_index <<
"\n";
3018 if (me_index == -1) {
3019 double3 vec = new_me.v2->co - new_me.v1->co;
3021 new_me.orig = tri.edge_orig[i];
3022 new_me.is_intersect = tri.is_intersect[i];
3023 new_me.dissolvable = (new_me.orig == NO_INDEX && !new_me.is_intersect);
3024 fms->edge.append(new_me);
3025 me_index = fms->edge.size() - 1;
3026 fms->edge_map.add_new(canon_vs, me_index);
3027 if (dbg_level > 1) {
3028 std::cout <<
"added new me with me_index = " << me_index <<
"\n";
3029 std::cout <<
" len_squared = " << new_me.len_squared <<
" orig = " << new_me.orig
3030 <<
", is_intersect" << new_me.is_intersect
3031 <<
", dissolvable = " << new_me.dissolvable <<
"\n";
3034 MergeEdge &me = fms->edge[me_index];
3035 if (dbg_level > 1) {
3036 std::cout <<
"retrieved me at index " << me_index <<
":\n";
3037 std::cout <<
" v1 = " << me.v1 <<
" v2 = " << me.v2 <<
"\n";
3038 std::cout <<
" dis = " << me.dissolvable <<
" int = " << me.is_intersect <<
"\n";
3039 std::cout <<
" left_face = " << me.left_face <<
" right_face = " << me.right_face <<
"\n";
3041 if (me.dissolvable && tri.edge_orig[i] != NO_INDEX) {
3042 if (dbg_level > 1) {
3043 std::cout <<
"reassigning orig to " << tri.edge_orig[i] <<
", dissolvable = false\n";
3045 me.dissolvable =
false;
3046 me.orig = tri.edge_orig[i];
3048 if (me.dissolvable && tri.is_intersect[i]) {
3049 if (dbg_level > 1) {
3050 std::cout <<
"reassigning dissolvable = false, is_intersect = true\n";
3052 me.dissolvable =
false;
3053 me.is_intersect =
true;
3056 if (me.v1 == mf.vert[i]) {
3057 if (dbg_level > 1) {
3058 std::cout <<
"me.v1 == mf.vert[i] so set edge[" << me_index <<
"].left_face = " << f
3061 if (me.left_face != -1) {
3066 if (dbg_level > 1) {
3067 std::cout <<
"me.left_face was already occupied, so triangulation wasn't good\n";
3069 me.dissolvable =
false;
3072 fms->edge[me_index].left_face = f;
3076 if (dbg_level > 1) {
3077 std::cout <<
"me.v1 != mf.vert[i] so set edge[" << me_index <<
"].right_face = " << f
3080 if (me.right_face != -1) {
3082 if (dbg_level > 1) {
3083 std::cout <<
"me.right_face was already occupied, so triangulation wasn't good\n";
3085 me.dissolvable =
false;
3088 fms->edge[me_index].right_face = f;
3091 fms->face[f].edge.append(me_index);
3094 if (dbg_level > 0) {
3105 static bool dissolve_leaves_valid_bmesh(FaceMergeState *fms,
3106 const MergeEdge &me,
3108 const MergeFace &mf_left,
3109 const MergeFace &mf_right)
3111 int a_edge_start = mf_left.edge.first_index_of_try(me_index);
3113 int alen = mf_left.vert.size();
3114 int blen = mf_right.vert.size();
3115 int b_left_face = me.right_face;
3118 for (
int a_e_index = (a_edge_start + 1) % alen; ok && a_e_index != a_edge_start;
3119 a_e_index = (a_e_index + 1) % alen) {
3120 const MergeEdge &a_me_cur = fms->edge[mf_left.edge[a_e_index]];
3121 if (a_me_cur.right_face == b_left_face) {
3128 for (
int a_v_index = 0; ok && a_v_index < alen; ++a_v_index) {
3129 const Vert *a_v = mf_left.vert[a_v_index];
3130 if (!
ELEM(a_v, me.v1, me.v2)) {
3131 for (
int b_v_index = 0; b_v_index < blen; ++b_v_index) {
3132 const Vert *b_v = mf_right.vert[b_v_index];
3149 static void splice_faces(
3150 FaceMergeState *fms, MergeEdge &me,
int me_index, MergeFace &mf_left, MergeFace &mf_right)
3152 int a_edge_start = mf_left.edge.first_index_of_try(me_index);
3153 int b_edge_start = mf_right.edge.first_index_of_try(me_index);
3154 BLI_assert(a_edge_start != -1 && b_edge_start != -1);
3155 int alen = mf_left.vert.size();
3156 int blen = mf_right.vert.size();
3157 Vector<const Vert *> splice_vert;
3158 Vector<int> splice_edge;
3159 splice_vert.reserve(alen + blen - 2);
3160 splice_edge.reserve(alen + blen - 2);
3162 while (ai < a_edge_start) {
3163 splice_vert.append(mf_left.vert[ai]);
3164 splice_edge.append(mf_left.edge[ai]);
3167 int bi = b_edge_start + 1;
3168 while (bi != b_edge_start) {
3171 if (bi == b_edge_start) {
3175 splice_vert.append(mf_right.vert[bi]);
3176 splice_edge.append(mf_right.edge[bi]);
3177 if (mf_right.vert[bi] == fms->edge[mf_right.edge[bi]].v1) {
3178 fms->edge[mf_right.edge[bi]].left_face = me.left_face;
3181 fms->edge[mf_right.edge[bi]].right_face = me.left_face;
3185 ai = a_edge_start + 1;
3187 splice_vert.append(mf_left.vert[ai]);
3188 splice_edge.append(mf_left.edge[ai]);
3191 mf_right.merge_to = me.left_face;
3192 mf_left.vert = splice_vert;
3193 mf_left.edge = splice_edge;
3205 static void do_dissolve(FaceMergeState *fms)
3207 const int dbg_level = 0;
3208 if (dbg_level > 1) {
3209 std::cout <<
"\nDO_DISSOLVE\n";
3211 Vector<int> dissolve_edges;
3212 for (
int e : fms->edge.index_range()) {
3213 if (fms->edge[
e].dissolvable) {
3214 dissolve_edges.append(
e);
3217 if (dissolve_edges.size() == 0) {
3222 dissolve_edges.begin(), dissolve_edges.end(), [fms](
const int &
a,
const int &
b) ->
bool {
3223 return (fms->edge[a].len_squared > fms->edge[b].len_squared);
3225 if (dbg_level > 0) {
3226 std::cout <<
"Sorted dissolvable edges: " << dissolve_edges <<
"\n";
3228 for (
int me_index : dissolve_edges) {
3229 MergeEdge &me = fms->edge[me_index];
3230 if (me.left_face == -1 || me.right_face == -1) {
3233 MergeFace &mf_left = fms->face[me.left_face];
3234 MergeFace &mf_right = fms->face[me.right_face];
3235 if (!dissolve_leaves_valid_bmesh(fms, me, me_index, mf_left, mf_right)) {
3238 if (dbg_level > 0) {
3239 std::cout <<
"Removing edge " << me_index <<
"\n";
3241 splice_faces(fms, me, me_index, mf_left, mf_right);
3242 if (dbg_level > 1) {
3243 std::cout <<
"state after removal:\n";
3259 static Vector<Face *> merge_tris_for_face(Vector<int> tris,
3261 const IMesh &imesh_in,
3264 constexpr
int dbg_level = 0;
3265 if (dbg_level > 0) {
3266 std::cout <<
"merge_tris_for_face\n";
3267 std::cout <<
"tris: " << tris <<
"\n";
3270 if (tris.size() <= 1) {
3271 if (tris.size() == 1) {
3272 ans.append(tm.face(tris[0]));
3277 double3 first_tri_normal = tm.face(tris[0])->plane->norm;
3278 double3 second_tri_normal = tm.face(tris[1])->plane->norm;
3279 if (tris.size() == 2 &&
math::dot(first_tri_normal, second_tri_normal) > 0.0) {
3282 Face &tri1 = *tm.face(tris[0]);
3283 Face &tri2 = *tm.face(tris[1]);
3284 Face *in_face = imesh_in.face(tri1.orig);
3285 if (in_face->size() == 4) {
3286 std::pair<int, int> estarts = find_tris_common_edge(tri1, tri2);
3287 if (estarts.first != -1 && tri1.edge_orig[estarts.first] == NO_INDEX) {
3288 if (dbg_level > 0) {
3289 std::cout <<
"try recovering orig quad case\n";
3290 std::cout <<
"tri1 = " << &tri1 <<
"\n";
3291 std::cout <<
"tri1 = " << &tri2 <<
"\n";
3293 int i0 = estarts.first;
3294 int i1 = (i0 + 1) % 3;
3295 int i2 = (i0 + 2) % 3;
3296 int j2 = (estarts.second + 2) % 3;
3297 Face tryface({tri1[
i1], tri1[i2], tri1[i0], tri2[j2]}, -1, -1, {}, {});
3298 if (tryface.cyclic_equal(*in_face)) {
3299 if (dbg_level > 0) {
3300 std::cout <<
"inface = " << in_face <<
"\n";
3301 std::cout <<
"quad recovery worked\n";
3303 ans.append(in_face);
3313 double3 first_tri_normal_rev = -first_tri_normal;
3314 for (
const double3 &
norm : {first_tri_normal, first_tri_normal_rev}) {
3316 init_face_merge_state(&fms, tris, tm,
norm);
3318 if (dbg_level > 0) {
3319 std::cout <<
"faces in merged result:\n";
3321 for (
const MergeFace &mf : fms.face) {
3322 if (mf.merge_to == -1) {
3323 Array<int> e_orig(mf.edge.size());
3324 Array<bool> is_intersect(mf.edge.size());
3325 for (
int i : mf.edge.index_range()) {
3326 e_orig[i] = fms.edge[mf.edge[i]].orig;
3327 is_intersect[i] = fms.edge[mf.edge[i]].is_intersect;
3329 Face *facep = arena->add_face(mf.vert, mf.orig, e_orig, is_intersect);
3331 if (dbg_level > 0) {
3332 std::cout <<
" " << facep <<
"\n";
3345 return fabs(cos_ang - 1.0) < 1
e-4;
3354 static Array<bool> find_dissolve_verts(IMesh &imesh_out,
int *r_count_dissolve)
3356 imesh_out.populate_vert();
3358 Array<bool> dissolve(imesh_out.vert_size());
3359 for (
int v_index : imesh_out.vert_index_range()) {
3360 const Vert &vert = *imesh_out.vert(v_index);
3361 dissolve[v_index] = (vert.orig == NO_INDEX);
3366 Array<std::pair<const Vert *, const Vert *>> neighbors(
3367 imesh_out.vert_size(), std::pair<const Vert *, const Vert *>(
nullptr,
nullptr));
3368 for (
int f : imesh_out.face_index_range()) {
3369 const Face &face = *imesh_out.face(f);
3370 for (
int i : face.index_range()) {
3371 const Vert *
v = face[i];
3372 int v_index = imesh_out.lookup_vert(
v);
3374 if (dissolve[v_index]) {
3375 const Vert *n1 = face[face.next_pos(i)];
3376 const Vert *n2 = face[face.prev_pos(i)];
3377 const Vert *f_n1 = neighbors[v_index].first;
3378 const Vert *f_n2 = neighbors[v_index].second;
3379 if (f_n1 !=
nullptr) {
3381 if (!((n1 == f_n2 && n2 == f_n1) || (n1 == f_n1 && n2 == f_n2))) {
3383 dissolve[v_index] =
false;
3388 neighbors[v_index] = std::pair<const Vert *, const Vert *>(n1, n2);
3394 for (
int v_out : imesh_out.vert_index_range()) {
3395 if (dissolve[v_out]) {
3396 dissolve[v_out] =
false;
3397 const std::pair<const Vert *, const Vert *> &nbrs = neighbors[v_out];
3398 if (nbrs.first !=
nullptr) {
3400 const Vert *v_v_out = imesh_out.vert(v_out);
3401 if (approx_in_line(nbrs.first->co, v_v_out->co, nbrs.second->co)) {
3402 dissolve[v_out] =
true;
3408 if (r_count_dissolve !=
nullptr) {
3409 *r_count_dissolve =
count;
3419 static void dissolve_verts(IMesh *imesh,
const Array<bool> dissolve, IMeshArena *arena)
3421 constexpr
int inline_face_size = 100;
3422 Vector<bool, inline_face_size> face_pos_erase;
3423 bool any_faces_erased =
false;
3424 for (
int f : imesh->face_index_range()) {
3425 const Face &face = *imesh->face(f);
3426 face_pos_erase.clear();
3428 for (
const Vert *
v : face) {
3429 int v_index = imesh->lookup_vert(
v);
3431 if (dissolve[v_index]) {
3432 face_pos_erase.append(
true);
3436 face_pos_erase.append(
false);
3439 if (erase_num > 0) {
3440 any_faces_erased |= imesh->erase_face_positions(f, face_pos_erase, arena);
3443 imesh->set_dirty_verts();
3444 if (any_faces_erased) {
3445 imesh->remove_null_faces();
3460 static IMesh polymesh_from_trimesh_with_dissolve(
const IMesh &tm_out,
3461 const IMesh &imesh_in,
3464 const int dbg_level = 0;
3465 if (dbg_level > 1) {
3466 std::cout <<
"\nPOLYMESH_FROM_TRIMESH_WITH_DISSOLVE\n";
3469 const int grainsize = 1024;
3471 for (int i : range) {
3472 Face *tri = tm_out.face(i);
3473 tri->populate_plane(false);
3479 int tot_in_face = imesh_in.face_size();
3480 Array<Vector<int>> face_output_tris(tot_in_face);
3481 for (
int t : tm_out.face_index_range()) {
3482 const Face &tri = *tm_out.face(
t);
3483 int in_face = tri.orig;
3484 face_output_tris[in_face].append(
t);
3486 if (dbg_level > 1) {
3487 std::cout <<
"face_output_tris:\n";
3488 for (
int f : face_output_tris.index_range()) {
3489 std::cout << f <<
": " << face_output_tris[f] <<
"\n";
3496 Array<Vector<Face *>> face_output_face(tot_in_face);
3497 int tot_out_face = 0;
3498 for (
int in_f : imesh_in.face_index_range()) {
3499 if (dbg_level > 1) {
3500 std::cout <<
"merge tris for face " << in_f <<
"\n";
3502 int out_tris_for_face_num = face_output_tris.size();
3503 if (out_tris_for_face_num == 0) {
3506 face_output_face[in_f] = merge_tris_for_face(face_output_tris[in_f], tm_out, imesh_in, arena);
3507 tot_out_face += face_output_face[in_f].size();
3509 Array<Face *> face(tot_out_face);
3510 int out_f_index = 0;
3511 for (
int in_f : imesh_in.face_index_range()) {
3512 const Vector<Face *> &f_faces = face_output_face[in_f];
3513 if (f_faces.size() > 0) {
3514 std::copy(f_faces.begin(), f_faces.end(), &face[out_f_index]);
3515 out_f_index += f_faces.size();
3518 IMesh imesh_out(face);
3523 Array<bool> v_dissolve = find_dissolve_verts(imesh_out, &count_dissolve);
3524 if (count_dissolve > 0) {
3525 dissolve_verts(&imesh_out, v_dissolve, arena);
3527 if (dbg_level > 1) {
3528 write_obj_mesh(imesh_out,
"boolean_post_dissolve");
3540 IMesh boolean_trimesh(IMesh &tm_in,
3543 std::function<
int(
int)> shape_fn,
3548 constexpr
int dbg_level = 0;
3549 if (dbg_level > 0) {
3550 std::cout <<
"BOOLEAN of " << nshapes <<
" operand" << (nshapes == 1 ?
"" :
"s")
3551 <<
" op=" << bool_optype_name(op) <<
"\n";
3552 if (dbg_level > 1) {
3553 tm_in.populate_vert();
3554 std::cout <<
"boolean_trimesh input:\n" << tm_in;
3555 write_obj_mesh(tm_in,
"boolean_in");
3558 if (tm_in.face_size() == 0) {
3559 return IMesh(tm_in);
3563 std::cout <<
" boolean_trimesh, timing begins\n";
3566 IMesh tm_si = trimesh_nary_intersect(tm_in, nshapes, shape_fn, use_self, arena);
3567 if (dbg_level > 1) {
3568 write_obj_mesh(tm_si,
"boolean_tm_si");
3569 std::cout <<
"\nboolean_tm_input after intersection:\n" << tm_si;
3573 std::cout <<
" intersected, time = " << intersect_time - start_time <<
"\n";
3577 if (tm_si.face_size() == 0 || op == BoolOpType::None) {
3580 auto si_shape_fn = [shape_fn, tm_si](
int t) {
return shape_fn(tm_si.face(
t)->orig); };
3581 TriMeshTopology tm_si_topo(tm_si);
3584 std::cout <<
" topology built, time = " << topo_time - intersect_time <<
"\n";
3586 bool pwn = is_pwn(tm_si, tm_si_topo);
3589 std::cout <<
" pwn checked, time = " << pwn_time - topo_time <<
"\n";
3593 if (dbg_level > 0) {
3594 std::cout <<
"Input is not PWN, using raycast method\n";
3596 if (hole_tolerant) {
3597 tm_out = raycast_tris_boolean(tm_si, op, nshapes, shape_fn, arena);
3600 PatchesInfo pinfo = find_patches(tm_si, tm_si_topo);
3601 tm_out = raycast_patches_boolean(tm_si, op, nshapes, shape_fn, pinfo, arena);
3605 std::cout <<
" raycast_boolean done, time = " << raycast_time - pwn_time <<
"\n";
3609 PatchesInfo pinfo = find_patches(tm_si, tm_si_topo);
3612 std::cout <<
" patches found, time = " << patch_time - pwn_time <<
"\n";
3614 CellsInfo cinfo = find_cells(tm_si, tm_si_topo, pinfo);
3615 if (dbg_level > 0) {
3616 std::cout <<
"Input is PWN\n";
3620 std::cout <<
" cells found, time = " << cell_time - pwn_time <<
"\n";
3622 finish_patch_cell_graph(tm_si, cinfo, pinfo, tm_si_topo, arena);
3625 std::cout <<
" finished patch-cell graph, time = " << finish_pc_time - cell_time <<
"\n";
3627 bool pc_ok = patch_cell_graph_ok(cinfo, pinfo);
3630 std::cout <<
"Something funny about input or a bug in boolean\n";
3631 return IMesh(tm_in);
3633 cinfo.init_windings(nshapes);
3634 int c_ambient = find_ambient_cell(tm_si,
nullptr, tm_si_topo, pinfo, arena);
3637 std::cout <<
" ambient cell found, time = " << amb_time - finish_pc_time <<
"\n";
3639 if (c_ambient == NO_INDEX) {
3641 std::cout <<
"Could not find an ambient cell; input not valid?\n";
3642 return IMesh(tm_si);
3644 propagate_windings_and_in_output_volume(pinfo, cinfo, c_ambient, op, nshapes, si_shape_fn);
3647 std::cout <<
" windings propagated, time = " << propagate_time - amb_time <<
"\n";
3649 tm_out = extract_from_in_output_volume_diffs(tm_si, pinfo, cinfo, arena);
3652 std::cout <<
" extracted, time = " << extract_time - propagate_time <<
"\n";
3654 if (dbg_level > 0) {
3656 TriMeshTopology tm_out_topo(tm_out);
3657 if (!is_pwn(tm_out, tm_out_topo)) {
3658 std::cout <<
"OUTPUT IS NOT PWN!\n";
3662 if (dbg_level > 1) {
3663 write_obj_mesh(tm_out,
"boolean_tm_output");
3664 std::cout <<
"boolean tm output:\n" << tm_out;
3668 std::cout <<
" boolean_trimesh done, total time = " << end_time - start_time <<
"\n";
3673 static void dump_test_spec(IMesh &imesh)
3675 std::cout <<
"test spec = " << imesh.vert_size() <<
" " << imesh.face_size() <<
"\n";
3676 for (
const Vert *
v : imesh.vertices()) {
3677 std::cout <<
v->co_exact[0] <<
" " <<
v->co_exact[1] <<
" " <<
v->co_exact[2] <<
" # "
3678 <<
v->
co[0] <<
" " <<
v->
co[1] <<
" " <<
v->
co[2] <<
"\n";
3680 for (
const Face *f : imesh.faces()) {
3681 for (
const Vert *fv : *f) {
3682 std::cout << imesh.lookup_vert(fv) <<
" ";
3688 IMesh boolean_mesh(IMesh &imesh,
3691 std::function<
int(
int)> shape_fn,
3694 IMesh *imesh_triangulated,
3697 constexpr
int dbg_level = 0;
3698 if (dbg_level > 0) {
3699 std::cout <<
"\nBOOLEAN_MESH\n"
3700 << nshapes <<
" operand" << (nshapes == 1 ?
"" :
"s")
3701 <<
" op=" << bool_optype_name(op) <<
"\n";
3702 if (dbg_level > 1) {
3703 write_obj_mesh(imesh,
"boolean_mesh_in");
3705 if (dbg_level > 2) {
3706 dump_test_spec(imesh);
3710 IMesh *tm_in = imesh_triangulated;
3711 IMesh our_triangulation;
3714 std::cout <<
"boolean_mesh, timing begins\n";
3716 if (tm_in ==
nullptr) {
3717 our_triangulation = triangulate_polymesh(imesh, arena);
3718 tm_in = &our_triangulation;
3722 std::cout <<
"triangulated, time = " << tri_time - start_time <<
"\n";
3724 if (dbg_level > 1) {
3725 write_obj_mesh(*tm_in,
"boolean_tm_in");
3727 IMesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, use_self, hole_tolerant, arena);
3730 std::cout <<
"boolean_trimesh done, time = " << bool_tri_time - tri_time <<
"\n";
3732 if (dbg_level > 1) {
3733 std::cout <<
"bool_trimesh_output:\n" << tm_out;
3734 write_obj_mesh(tm_out,
"bool_trimesh_output");
3736 IMesh ans = polymesh_from_trimesh_with_dissolve(tm_out, imesh, arena);
3739 std::cout <<
"polymesh from dissolving, time = " << dissolve_time - bool_tri_time <<
"\n";
3741 if (dbg_level > 0) {
3742 std::cout <<
"boolean_mesh output:\n" << ans;
3743 if (dbg_level > 2) {
3744 ans.populate_vert();
3745 dump_test_spec(ans);
3750 std::cout <<
"boolean_mesh done, total time = " << end_time - start_time <<
"\n";
typedef float(TangentPoint)[2]
void BLI_bvhtree_balance(BVHTree *tree)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
void BLI_bvhtree_free(BVHTree *tree)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
void BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata)
MINLINE double max_dd(double a, double b)
Math vector functions needed specifically for mesh intersect and boolean.
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
bool isect_ray_tri_epsilon_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void copy_v3fl_v3db(float r[3], const double a[3])
const char * BLI_getenv(const char *env) ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT
#define UNUSED_VARS_NDEBUG(...)
typedef double(DMatrix)[4][4]
static uint8 component(Color32 c, uint i)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Platform independent time functions.
int pad[32 - sizeof(int)]
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
SIMD_FORCE_INLINE btVector3 & operator[](int i)
Get a mutable reference to a row of the matrix as a vector.
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
SIMD_FORCE_INLINE btScalar norm() const
Return the norm (length) of the vector.
bool closest(btVector3 &v)
BLI_INLINE float fb(float length, float L)
IconTextureDrawCall normal
ccl_device_inline float2 fabs(const float2 &a)
ccl_device_inline float len_squared(const float3 a)
std::ostream & operator<<(std::ostream &stream, const AssetCatalogPath &path_to_append)
T dot(const vec_base< T, Size > &a, const vec_base< T, Size > &b)
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
vec_base< T, Size > normalize(const vec_base< T, Size > &v)
T length_squared(const vec_base< T, Size > &a)
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
constexpr bool operator==(StringRef a, StringRef b)
vec_base< double, 3 > double3
int orient3d(const double3 &a, const double3 &b, const double3 &c, const double3 &d)
uint64_t get_default_hash_2(const T1 &v1, const T2 &v2)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static const pxr::TfToken g("g", pxr::TfToken::Immortal)
static void copy(bNodeTree *dest_ntree, bNode *dest_node, const bNode *src_node)
unsigned __int64 uint64_t
double PIL_check_seconds_timer(void)