33using namespace blender::math;
47 return (
v < 0) ? -
v :
v;
91template<
typename T>
struct CDTVert;
92template<
typename T>
struct CDTEdge;
93template<
typename T>
struct CDTFace;
115 return se->
next->rot;
121 return se->
rot->next->rot;
139template<>
struct FatCo<mpq_class> {
188 stream <<
"(" << co.
approx.x <<
", " << co.
approx.y <<
")";
268 void reserve(
int verts_num,
int edges_num,
int faces_num);
331 if (
v->merge_to_index != -1) {
332 v = this->verts[
v->merge_to_index];
403 for (
int i : this->
verts.index_range()) {
405 v->input_ids.clear();
407 this->
verts[i] =
nullptr;
409 for (
int i : this->
edges.index_range()) {
411 e->input_ids.clear();
413 this->
edges[i] =
nullptr;
415 for (
int i : this->
faces.index_range()) {
419 this->
faces[i] =
nullptr;
446 std::stringstream ss;
447 ss <<
"[" <<
v->index <<
"]";
454 constexpr int TRUNC_PTR_MASK = 0xFFFF;
455 std::stringstream ss;
462 std::stringstream ss;
488 return std::string(
"null");
496 os <<
"\nCDT\n\nVERTS\n";
500 if (
v->merge_to_index == -1) {
504 os <<
" merge to " <<
vertname(cdt_state.
cdt.verts[
v->merge_to_index]) <<
"\n";
508 constexpr int print_count_limit = 25;
510 os <<
" edges out:\n";
512 if (se->
next ==
nullptr) {
513 os <<
" [null] next/rot symedge, se=" <<
trunc_ptr(se) <<
"\n";
516 if (se->
next->next ==
nullptr) {
517 os <<
" [null] next-next/rot symedge, se=" <<
trunc_ptr(se) <<
"\n";
525 }
while (se !=
v->symedge && count < print_count_limit);
531 if (
e->symedges[0].next ==
nullptr) {
535 for (
int i = 0; i < 2; ++i) {
544 os <<
"outer_face=" <<
trunc_ptr(cdt_state.
cdt.outer_face) <<
"\n";
546 if (cdt_state.
cdt.outer_face->symedge !=
nullptr) {
558 static bool append =
false;
564 const char *drawfile =
"./cdt_debug_draw.html";
566 const char *drawfile =
"/tmp/cdt_debug_draw.html";
568 constexpr int max_draw_width = 1800;
569 constexpr int max_draw_height = 1600;
570 constexpr double margin_expand = 0.05;
571 constexpr int thin_line = 1;
572 constexpr int thick_line = 4;
573 constexpr int vert_radius = 3;
574 constexpr bool draw_vert_labels =
true;
575 constexpr bool draw_edge_labels =
false;
576 constexpr bool draw_face_labels =
false;
578 if (cdt.
verts.is_empty()) {
581 double2 vmin(std::numeric_limits<double>::max());
582 double2 vmax(std::numeric_limits<double>::lowest());
586 double draw_margin = ((vmax.x - vmin.x) + (vmax.y - vmin.y)) * margin_expand;
587 double minx = vmin.x - draw_margin;
588 double maxx = vmax.x + draw_margin;
589 double miny = vmin.y - draw_margin;
590 double maxy = vmax.y + draw_margin;
592 double width = maxx - minx;
593 double height = maxy - miny;
594 double aspect = height / width;
595 int view_width = max_draw_width;
596 int view_height = int(view_width * aspect);
597 if (view_height > max_draw_height) {
598 view_height = max_draw_height;
599 view_width = int(view_height / aspect);
601 double scale = view_width / width;
603# define SX(x) (((x) - minx) * scale)
604# define SY(y) ((maxy - (y)) * scale)
608 f.open(drawfile, std::ios_base::app);
614 std::cout <<
"Could not open file " << drawfile <<
"\n";
618 f <<
"<div>" << label <<
"</div>\n<div>\n"
619 <<
"<svg version=\"1.1\" "
620 "xmlns=\"http://www.w3.org/2000/svg\" "
621 "xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
622 "xml:space=\"preserve\"\n"
623 <<
"width=\"" << view_width <<
"\" height=\"" << view_height <<
"\">n";
626 if (
e->symedges[0].next ==
nullptr) {
633 int strokew =
e->input_ids.size() == 0 ? thin_line : thick_line;
634 f << R
"(<line fill="none" stroke="black" stroke-width=")" << strokew << "\" x1=\""
635 <<
SX(uco[0]) <<
"\" y1=\"" <<
SY(uco[1]) <<
"\" x2=\"" <<
SX(vco[0]) <<
"\" y2=\""
636 <<
SY(vco[1]) <<
"\">\n";
639 if (draw_edge_labels) {
640 f <<
"<text x=\"" <<
SX((uco[0] + vco[0]) / 2) <<
"\" y=\"" <<
SY((uco[1] + vco[1]) / 2)
641 << R
"(" font-size="small">)";
649 f << R
"(<circle fill="black" cx=")" << SX(v->co.approx[0]) << "\" cy=\"" <<
SY(
v->
co.approx[1])
650 <<
"\" r=\"" << vert_radius <<
"\">\n";
651 f <<
" <title>[" << i <<
"]" <<
v->
co.approx <<
"</title>\n";
653 if (draw_vert_labels) {
654 f <<
"<text x=\"" <<
SX(
v->
co.approx[0]) + vert_radius <<
"\" y=\""
655 <<
SY(
v->
co.approx[1]) - vert_radius << R
"(" font-size="small">[)" << i << "]</text>\n";
660 if (draw_face_labels) {
666 if (
e->symedges[0].face == face) {
667 se_face_start = &
e->symedges[0];
670 if (
e->symedges[1].face == face) {
671 se_face_start = &
e->symedges[1];
674 if (se_face_start !=
nullptr) {
685 if (se->
face == face) {
686 cen = cen + se->
vert->co.approx;
689 }
while ((se = se->
next) != se_face_start);
690 if (face_nverts > 0) {
691 cen = cen / double(face_nverts);
694 f <<
"<text x=\"" <<
SX(cen[0]) <<
"\" y=\"" <<
SY(cen[1]) <<
"\""
695 <<
" font-size=\"small\">[";
731 constexpr double index_orient2d = 6;
732 double err_bound = supremum * index_orient2d * DBL_EPSILON;
733 if (
fabs(det) > err_bound) {
734 return det > 0 ? 1 : -1;
765 double bdx =
b.approx[0] - d.
approx[0];
768 double bdy =
b.approx[1] - d.
approx[1];
770 double bdxcdy = bdx * cdy;
771 double cdxbdy = cdx * bdy;
772 double alift = adx * adx + ady * ady;
773 double cdxady = cdx * ady;
774 double adxcdy = adx * cdy;
775 double blift = bdx * bdx + bdy * bdy;
776 double adxbdy = adx * bdy;
777 double bdxady = bdx * ady;
778 double clift = cdx * cdx + cdy * cdy;
779 double det = alift * (bdxcdy - cdxbdy) + blift * (cdxady - adxcdy) + clift * (adxbdy - bdxady);
782 double sup_bdx =
b.abs_approx[0] + d.
abs_approx[0];
785 double sup_bdy =
b.abs_approx[1] + d.
abs_approx[1];
787 double sup_bdxcdy = sup_bdx * sup_cdy;
788 double sup_cdxbdy = sup_cdx * sup_bdy;
789 double sup_alift = sup_adx * sup_adx + sup_ady * sup_ady;
790 double sup_cdxady = sup_cdx * sup_ady;
791 double sup_adxcdy = sup_adx * sup_cdy;
792 double sup_blift = sup_bdx * sup_bdx + sup_bdy * sup_bdy;
793 double sup_adxbdy = sup_adx * sup_bdy;
794 double sup_bdxady = sup_bdx * sup_ady;
795 double sup_clift = sup_cdx * sup_cdx + sup_cdy * sup_cdy;
796 double sup_det = sup_alift * (sup_bdxcdy + sup_cdxbdy) + sup_blift * (sup_cdxady + sup_adxcdy) +
797 sup_clift * (sup_adxbdy + sup_bdxady);
799 double err_bound = sup_det *
index * DBL_EPSILON;
800 if (
fabs(det) > err_bound) {
801 return det < 0.0 ? -1 : (det > 0.0 ? 1 : 0);
836 double dot_ab_ac = ab.x * ac.x + ab.y * ac.y;
837 double supremum_dot_ab_ac = supremum_ab.x * supremum_ac.x + supremum_ab.y * supremum_ac.y;
838 constexpr double index = 6;
839 double err_bound = supremum_dot_ab_ac *
index * DBL_EPSILON;
840 if (dot_ab_ac < -err_bound) {
843 double dot_bc_ac = bc.x * ac.x + bc.y * ac.y;
844 double supremum_dot_bc_ac = supremum_bc.x * supremum_ac.x + supremum_bc.y * supremum_ac.y;
845 err_bound = supremum_dot_bc_ac *
index * DBL_EPSILON;
846 if (dot_bc_ac < -err_bound) {
849 mpq2 exact_ab =
b.exact - a.
exact;
851 if (
dot(exact_ab, exact_ac) < 0) {
854 mpq2 exact_bc = c.
exact -
b.exact;
855 return dot(exact_bc, exact_ac) >= 0;
864 if (
dot(ab, ac) < 0) {
868 return dot(bc, ac) >= 0;
874 this->
co.approx = pt;
875 this->
co.abs_approx = pt;
886 this->co.approx =
double2(pt.x.get_d(), pt.y.get_d());
887 this->co.abs_approx =
double2(
fabs(this->co.approx.x),
fabs(this->co.approx.y));
888 this->symedge =
nullptr;
890 this->merge_to_index = -1;
891 this->visit_index = 0;
915 sesym->
face = fright;
921 if (
v2->symedge ==
nullptr) {
931 this->
faces.append(f);
938 this->
verts.reserve(2 * verts_num);
939 this->
edges.reserve(3 * verts_num + 2 * edges_num + 3 * 2 * faces_num);
940 this->
faces.reserve(2 * verts_num + 2 * edges_num + 2 * faces_num);
951 this->
cdt.reserve(input_verts_num, input_edges_num, input_faces_num);
952 this->
cdt.outer_face = this->
cdt.add_face();
967 if (
id >= range_start &&
id <= range_end) {
987 return e->symedges[0].face == cdt->outer_face ||
e->symedges[1].face == cdt->outer_face;
992 return e->input_ids.size() > 0;
997 return e->symedges[0].next ==
nullptr;
1014 if (t->
next->vert ==
v2) {
1017 }
while ((t = t->
rot) != tstart);
1032 }
while ((t = t->
rot) != tstart);
1051 if (se->
face == f) {
1054 }
while ((se = se->
rot) !=
v->symedge);
1078 sdiagsym->
next = s1;
1079 s2prev->
next = sdiagsym;
1080 s1prev->
next = sdiag;
1082 sdiag->
rot = s1prevsym;
1084 sdiagsym->
rot = s2prevsym;
1102 new_se_sym->
next = new_se;
1103 new_se->
rot = new_se;
1104 new_se_sym->
rot = se_rot;
1105 se->
rot = new_se_sym;
1106 se_rotsym->
next = new_se_sym;
1127 new_se_sym->
next = se1;
1128 new_se->
rot = se1_rot;
1129 new_se_sym->
rot = se2_rot;
1131 se2->
rot = new_se_sym;
1132 se1_rotsym->
next = new_se;
1133 se2_rotsym->
next = new_se_sym;
1166 newsesym->
next = sesym;
1167 newse->
next = senext;
1170 senext->
rot = newsesym;
1171 newsesym->
rot = sesymprevsym;
1172 sesymprev->
next = newsesym;
1173 if (newsesym->
vert->symedge == sesym) {
1174 newsesym->
vert->symedge = newsesym;
1178 if (polygon_boundary_count_map) {
1182 const int count = polygon_boundary_count_map->lookup_default(se->
edge, 0);
1184 polygon_boundary_count_map->add(
e, count);
1188 if (edge_winding_map) {
1199 int winding = edge_winding_map->lookup_default(se->
edge, 0);
1201 if (se == &se->
edge->symedges[1]) {
1204 edge_winding_map->add(
e, winding);
1244 bool v1_isolated = (i == se);
1245 bool v2_isolated = (f == sesym);
1255 if (!v1_isolated && !v2_isolated && aface != bface) {
1269 v2->symedge =
nullptr;
1271 else if (
v2->symedge == sesym) {
1277 sesym->
next = sesym->
rot =
nullptr;
1278 if (!v1_isolated && !v2_isolated && aface != bface) {
1284 else if (v1_isolated && v2_isolated) {
1317 if (co_a[0] < co_b[0]) {
1320 if (co_a[0] > co_b[0]) {
1323 if (co_a[1] < co_b[1]) {
1326 if (co_a[1] > co_b[1]) {
1339 int n = sites.size();
1340 for (
int i = 0; i < n - 1; ++i) {
1342 while (j < n && sites[j].
v->
co.exact == sites[i].v->co.exact) {
1343 sites[j].v->merge_to_index = sites[i].orig_index;
1384 constexpr int dbg_level = 0;
1385 if (dbg_level > 0) {
1386 std::cout <<
"DC_TRI start=" << start <<
" end=" << end <<
"\n";
1388 int n = end - start;
1417 else if (orient < 0) {
1431 BLI_assert(n2 >= 2 && end - (start + n2) >= 2);
1436 dc_tri(cdt, sites, start, start + n2, &ldo, &ldi);
1437 dc_tri(cdt, sites, start + n2, end, &rdi, &rdo);
1438 if (dbg_level > 0) {
1439 std::cout <<
"\nDC_TRI merge step for start=" << start <<
", end=" << end <<
"\n";
1440 std::cout <<
"ldo " << ldo <<
"\n"
1441 <<
"ldi " << ldi <<
"\n"
1442 <<
"rdi " << rdi <<
"\n"
1443 <<
"rdo " << rdo <<
"\n";
1444 if (dbg_level > 1) {
1445 std::string lab =
"dc_tri (" + std::to_string(start) +
"," + std::to_string(start + n2) +
1446 ")(" + std::to_string(start + n2) +
"," + std::to_string(end) +
")";
1456 rdi =
sym(rdi)->rot;
1462 if (dbg_level > 0) {
1463 std::cout <<
"common lower tangent in between\n"
1464 <<
"rdi " << rdi <<
"\n"
1465 <<
"ldi" << ldi <<
"\n";
1471 if (dbg_level > 1) {
1472 std::cout <<
"basel " << basel;
1473 cdt_draw(
"after basel made", *cdt);
1488 if (dbg_level > 1) {
1489 std::cout <<
"\ntop of merge loop\n";
1490 std::cout <<
"lcand " << lcand <<
"\n"
1491 <<
"rcand " << rcand <<
"\n"
1492 <<
"basel " << basel <<
"\n";
1495 if (dbg_level > 1) {
1496 std::cout <<
"found valid lcand\n";
1497 std::cout <<
" lcand" << lcand <<
"\n";
1501 lcand->
next->vert->co,
1502 lcand->
rot->next->vert->co) > 0.0)
1504 if (dbg_level > 1) {
1505 std::cout <<
"incircle says to remove lcand\n";
1506 std::cout <<
" lcand" << lcand <<
"\n";
1515 if (dbg_level > 1) {
1516 std::cout <<
"found valid rcand\n";
1517 std::cout <<
" rcand" << rcand <<
"\n";
1521 rcand->
next->vert->co,
1522 sym(rcand)->next->next->vert->co) > 0.0)
1524 if (dbg_level > 0) {
1525 std::cout <<
"incircle says to remove rcand\n";
1526 std::cout <<
" rcand" << rcand <<
"\n";
1534 bool valid_lcand =
dc_tri_valid(lcand, basel, basel_sym);
1535 bool valid_rcand =
dc_tri_valid(rcand, basel, basel_sym);
1536 if (dbg_level > 0) {
1537 std::cout <<
"after bubbling up, valid_lcand=" << valid_lcand
1538 <<
", valid_rand=" << valid_rcand <<
"\n";
1539 std::cout <<
"lcand" << lcand <<
"\n"
1540 <<
"rcand" << rcand <<
"\n";
1542 if (!valid_lcand && !valid_rcand) {
1550 lcand->
next->vert->co, lcand->
vert->co, rcand->
vert->co, rcand->
next->vert->co) > 0))
1552 if (dbg_level > 0) {
1553 std::cout <<
"connecting rcand\n";
1554 std::cout <<
" se1=basel_sym" << basel_sym <<
"\n";
1555 std::cout <<
" se2=rcand->next" << rcand->
next <<
"\n";
1560 if (dbg_level > 0) {
1561 std::cout <<
"connecting lcand\n";
1562 std::cout <<
" se1=sym(lcand)" <<
sym(lcand) <<
"\n";
1563 std::cout <<
" se2=basel_sym->next" << basel_sym->
next <<
"\n";
1570 if (dbg_level > 2) {
1571 cdt_draw(
"after adding new crossedge", *cdt);
1586 int nsites = sites.size();
1587 while (j < nsites) {
1589 sites[i] = sites[j++];
1590 if (sites[i].
v->merge_to_index < 0) {
1600 dc_tri(cdt, sites, 0, n, &le, &re);
1624 int n = cdt->
verts.size();
1629 for (
int i = 0; i < n; ++i) {
1630 sites[i].v = cdt->
verts[i];
1631 sites[i].orig_index = i;
1737 :
lambda(std::move(other.lambda)),
1738 vert(std::move(other.vert)),
1739 in(std::move(other.in)),
1740 out(std::move(other.out))
1746 if (
this != &other) {
1756 lambda = std::move(other.lambda);
1757 vert = std::move(other.vert);
1758 in = std::move(other.in);
1759 out = std::move(other.out);
1767 CrossData<T> *cd_next,
1768 const CDTVert<T> *
v2);
1787 cd_next->
in =
nullptr;
1788 cd_next->
out =
nullptr;
1795 if (se->
vert !=
v) {
1797 if (se->
vert !=
v) {
1837 T &lambda = isect.lambda;
1838 switch (isect.kind) {
1841 if (!std::is_same_v<T, mpq_class>)
1846 double len_ab =
distance(va->
co.approx, vb->
co.approx);
1847 if (lambda * len_ab <= epsilon) {
1850 else if ((1 - lambda) * len_ab <= epsilon) {
1872 else if (lambda == 1) {
1885 if (std::is_same_v<T, mpq_class>) {
1890 const T middle_lambda = 0.5;
1891 if (lambda <= middle_lambda) {
1949 if (t->
face != cdt_state->
cdt.outer_face) {
1952 if (orient1 > 0 && orient2 < 0) {
1960 }
while ((t = t->
rot) != tstart);
1989 else if (orient > 0.0) {
1999 std::cout <<
"CROSSINGS\n";
2000 for (
int i = 0; i < crossings.size(); ++i) {
2001 std::cout << i <<
": ";
2004 std::cout <<
"v" << cd.
vert->index;
2007 std::cout <<
"lambda=" << cd.
lambda;
2009 if (cd.
in !=
nullptr) {
2033 constexpr int dbg_level = 0;
2034 if (dbg_level > 0) {
2035 std::cout <<
"\nADD EDGE CONSTRAINT\n" <<
vertname(v1) <<
" " <<
vertname(
v2) <<
"\n";
2055 if (r_edges !=
nullptr) {
2057 *r_edges = edge_list.
list;
2080 while (!((n = crossings.
size()) > 0 && crossings[n - 1].vert ==
v2)) {
2085 if (crossings[n - 1].lambda == 0) {
2092 constexpr int unreasonably_large_crossings = 100000;
2093 if (!ok || crossings.
size() == unreasonably_large_crossings) {
2098 if (crossings[n].lambda == 0) {
2099 if (crossings[n].vert->visit_index == visit) {
2104 crossings[n].vert->visit_index = visit;
2108 if (dbg_level > 0) {
2122 int ncrossings = crossings.
size();
2123 for (
int i = 2; i < ncrossings; ++i) {
2129 for (j = i - 1; j > 0; --j) {
2130 cd_prev = &crossings[j];
2131 if ((cd_prev->
lambda == 0.0 && cd_prev->
vert !=
v) ||
2132 (cd_prev->
lambda != 0.0 && cd_prev->
in->vert !=
v && cd_prev->
in->next->vert !=
v))
2140 cd_prev = &crossings[j];
2142 if (cd_prev->
lambda == 0.0) {
2144 if (se ==
nullptr) {
2152 if (se ==
nullptr) {
2164 for (
int i = 0; i < ncrossings; ++i) {
2174 if (!cd->
in->edge->input_ids.is_empty()) {
2176 edge1_id = *cd->
in->edge->input_ids.begin();
2178 cd->
vert->intersected_edges = {int(edge1_id), int(input_id)};
2186 for (
int i = 0; i < ncrossings; ++i) {
2189 cdt_state->
cdt.delete_edge(cd->
in);
2197 for (
int i = 1; i < ncrossings; i++) {
2199 if (cd->
lambda == -1.0) {
2207 t = cd->
vert->symedge;
2208 tnext =
sym(t)->next;
2211 else if (cd->
lambda == 0.0) {
2218 for (j = i - 1; j >= 0; j--) {
2219 cd_prev = &crossings[j];
2220 if (cd_prev->
lambda != -1.0) {
2226 edge = cd_prev->
out->edge;
2228 if (r_edges !=
nullptr) {
2234 if (tstart->
next->vert == t->
vert) {
2235 edge = tstart->
edge;
2238 edge = cdt_state->
cdt.add_diagonal(tstart, t);
2241 if (r_edges !=
nullptr) {
2248 if (i < ncrossings - 1) {
2249 if (tnext !=
nullptr) {
2256 *r_edges = edge_list.
list;
2270 int nv = input.
vert.size();
2271 for (
uint32_t i = 0; i < ne; i++) {
2272 int iv1 = input.
edge[i][0];
2273 int iv2 = input.
edge[i][1];
2274 if (iv1 < 0 || iv1 >= nv || iv2 < 0 || iv2 >= nv) {
2278 CDTVert<T> *v1 = cdt_state->
cdt.get_vert_resolve_merge(iv1);
2319 stack.
append(face_symedge);
2329 for (se = se->
next; se != se_start; se = se->
next) {
2350 BLI_assert(
x < std::numeric_limits<uint32_t>::max() / 10);
2371 const bool need_winding)
2374 int nv = input.
vert.size();
2381 maxflen = std::max<uint32_t>(maxflen, input_faces[f].size());
2399 input_faces.
size());
2400 int faces_added = 0;
2414 if (face.
size() <= 2) {
2419 double signed_area = 0.0;
2424 int iv2 = face[(i + 1) % face.
size()];
2425 if (iv1 < 0 || iv1 >= nv || iv2 < 0 || iv2 >= nv) {
2446 if (edge_list !=
nullptr) {
2448 face_symedge0 = &face_edge->
symedges[0];
2449 if (face_symedge0->vert != v1) {
2450 face_symedge0 = &face_edge->
symedges[1];
2458 for (
LinkNode *ln = edge_list; ln !=
nullptr; ln = ln->
next) {
2462 if (
e->symedges[0].vert == curr_vert) {
2463 next_vert =
e->symedges[1].vert;
2468 next_vert =
e->symedges[0].vert;
2477 curr_vert = next_vert;
2484 if (face_symedge0 !=
nullptr) {
2492 if (need_orig_face_ids && (!skip_cw_ids || signed_area >= 0.0)) {
2514 if (se->
next->next == se) {
2530 const bool v1_isolated = (symse->
next == se);
2531 const bool v2_isolated = (se->
next == symse);
2532 if (se->
face->symedge == se) {
2535 if (symse->
face->symedge == symse) {
2536 symse->
face->symedge = v1_isolated ?
prev(symse) : symse->
next;
2583 if (
this != &other) {
2606 const bool use_hole_status)
2610 size_t nedges = cdt->
edges.size();
2620 dissolvable_edges[i].e =
e;
2621 const double2 &co1 =
e->symedges[0].vert->
co.approx;
2622 const double2 &co2 =
e->symedges[1].vert->
co.approx;
2635 const int v0 =
e->symedges[0].vert->index;
2636 const int v1 =
e->symedges[1].vert->index;
2637 return (v0 < v1) ?
int2(v0, v1) :
int2(v1, v0);
2639 const int2 a_verts = edge_verts_fn(a.
e);
2640 const int2 b_verts = edge_verts_fn(
b.e);
2641 return (a_verts.x != b_verts.x) ? (a_verts.x < b_verts.x) : (a_verts.y < b_verts.y);
2643 const auto is_output_face_fn = [use_hole_status](
const CDTFace<T> *f) {
2644 return use_hole_status ? !f->hole : !f->input_ids.is_empty();
2649 bool dissolve =
true;
2653 (is_output_face_fn(fleft) || is_output_face_fn(fright)))
2658 if (
sym(se2)->face == fright ||
2677 cdt_state->
cdt.outer_face->visit_index = visit;
2689 }
while ((se = se->
next) != se_start);
2713 }
while (se != se_start);
2714 while (to_dissolve !=
nullptr) {
2716 if (se->
next !=
nullptr) {
2727 for (
int i : cdt->
faces.index_range()) {
2743 }
while (se != se_start);
2776template<
typename Value,
typename CombineFn>
2779 const Value unset_value,
2791 Array<int> region_adjacency_offset_data(num_regions + 1, 0);
2792 for (
const int2 &key : region_pair_value.
keys()) {
2793 region_adjacency_offset_data[key[0]]++;
2796 region_adjacency_offset_data);
2801 for (
const auto &item : region_pair_value.
items()) {
2802 const int region_src = item.key[0];
2803 const int region_dst = item.key[1];
2804 const int index = region_adjacency_offset_data[region_src] + write_position[region_src]++;
2805 adjacency_data[
index] = {region_dst, item.value};
2810 region_stack.
reserve(num_regions);
2812 if (region_value[r] != unset_value) {
2817 const int region = region_stack.
pop_last();
2818 const Value cur = region_value[region];
2819 for (
const int i : region_adjacency_offsets[region]) {
2820 const RegionEdge &re = adjacency_data[i];
2821 if (region_value[re.neighbor] == unset_value) {
2822 region_value[re.neighbor] = combine(cur, re.value);
2823 region_stack.
append(re.neighbor);
2863 struct BoundaryRegionInfo {
2877 int cur_region = -1;
2889 int8_t outer_parity = -1;
2915 if (outer_parity == -1) {
2916 outer_parity = flip;
2918 else if (outer_parity != flip) {
2927 else if (!constrained && !neighbor->
deleted &&
2933 }
while ((se = se->
next) != se_start);
2935 if (outer_parity != -1) {
2936 boundary_regions.
append({cur_region, outer_parity});
2940 const int num_regions = ++cur_region;
2942 if (num_regions == 0) {
2952 region_pair_flip.
reserve(6 * num_regions);
2958 const int region0 =
e->symedges[0].face->visit_index;
2959 const int region1 =
e->symedges[1].face->visit_index;
2960 if (region0 == region1 || region0 < 0 || region1 < 0) {
2964 region_pair_flip.
add(
int2(region0, region1), flip);
2965 region_pair_flip.
add(
int2(region1, region0), flip);
2970 for (
const BoundaryRegionInfo &info : boundary_regions) {
2971 if (region_parity[info.region] == -1) {
2972 region_parity[info.region] = info.parity;
2987 f->
hole = (region_parity[region] != 1);
3026 struct BoundaryRegionInfo {
3042 int cur_region = -1;
3052 bool found_constrained_outer =
false;
3053 bool found_any_outer =
false;
3054 int outer_winding = 0;
3073 if (neighbor == cdt->
outer_face && !found_constrained_outer) {
3083 found_constrained_outer =
true;
3084 found_any_outer =
true;
3088 if (&se->
edge->symedges[0] == se) {
3089 outer_winding = winding;
3092 outer_winding = -winding;
3101 found_any_outer =
true;
3107 }
while ((se = se->
next) != se_start);
3110 if (found_any_outer) {
3111 boundary_regions.
append({cur_region, outer_winding});
3115 const int num_regions = ++cur_region;
3117 if (num_regions == 0) {
3134 region_pair_winding.
reserve(6 * num_regions);
3140 const int region0 =
e->symedges[0].face->visit_index;
3141 const int region1 =
e->symedges[1].face->visit_index;
3144 if (region0 == region1 || region0 < 0 || region1 < 0) {
3149 const int delta_0_to_1 = -winding;
3150 const int delta_1_to_0 = winding;
3155 region_pair_winding.
add(
int2(region0, region1), delta_0_to_1);
3156 region_pair_winding.
add(
int2(region1, region0), delta_1_to_0);
3161 region_winding.
fill(INT_MIN);
3162 for (
const BoundaryRegionInfo &info : boundary_regions) {
3163 if (region_winding[info.region] == INT_MIN) {
3164 region_winding[info.region] = info.winding;
3172 [](
int cur,
int delta) {
return cur + delta; });
3178 const int winding = region_winding[region];
3179 f->
hole = (
ELEM(winding, 0, INT_MIN));
3193 if (cdt->
edges.is_empty()) {
3200 if (
e->symedges[0].face->symedge ==
nullptr) {
3201 e->symedges[0].face->symedge = &
e->symedges[0];
3203 if (
e->symedges[1].face->symedge ==
nullptr) {
3204 e->symedges[1].face->symedge = &
e->symedges[1];
3230 else if (
ELEM(output_type,
3254 int verts_size = cdt->
verts.size();
3257 for (
int i = 0; i < verts_size; ++i) {
3259 if (
v->merge_to_index == -1) {
3260 vert_to_output_map[i] = nv;
3270 if (nv < verts_size) {
3271 for (
int i = 0; i < verts_size; ++i) {
3273 if (
v->merge_to_index != -1) {
3275 if (i < cdt_state->input_vert_num) {
3279 vert_to_output_map[i] = vert_to_output_map[
v->merge_to_index];
3291 for (
int i = 0; i < verts_size; ++i) {
3293 if (
v->merge_to_index == -1) {
3296 if (i < cdt_state->input_vert_num) {
3299 result.vert_orig[i_out].extend(
v->input_ids.as_span());
3302 result.intersected_edges_orig[i_out] =
v->intersected_edges;
3310 return !is_deleted_edge(e);
3319 int vo1 = vert_to_output_map[
e->symedges[0].vert->index];
3320 int vo2 = vert_to_output_map[
e->symedges[1].vert->index];
3323 result.edge_orig[e_out].extend(
e->input_ids.as_span());
3330 int nf = std::count_if(cdt->
faces.begin(), cdt->
faces.end(), [=](
const CDTFace<T> *f) ->
bool {
3331 return !f->deleted && f != cdt->outer_face;
3344 result.face[f_out].append(vert_to_output_map[se->
vert->index]);
3346 }
while (se != se_start);
3363 cdt_state->
cdt.add_vert(input.
vert[i]);
3371 int nv = input.
vert.size();
3372 int ne = input.
edge.size();
3379 std::optional<Map<CDTEdge<T> *,
int>> edge_winding_map;
3382 edge_winding_map.emplace();
3387 std::optional<Map<CDTEdge<T> *,
int>> polygon_boundary_count_map;
3388 if (need_polygon_boundary_count) {
3390 polygon_boundary_count_map.emplace();
Math vector functions needed specifically for mesh intersect and boolean.
#define PRF_scope(category)
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_AS_INT(i)
Array(Allocator allocator={}) noexcept
void fill(const T &value) const
bool add(const Key &key, const Value &value)
Value lookup_default(const Key &key, const Value &default_value) const
KeyIterator keys() const &
ItemIterator items() const &
constexpr int64_t size() const
constexpr IndexRange index_range() const
constexpr int64_t size() const
constexpr IndexRange index_range() const
void add_multiple(Span< Key > keys)
Span< Key > as_span() const
void append(const T &value)
void reserve(const int64_t min_capacity)
CDT_state(int input_verts_num, int input_edges_num, int input_faces_num, T epsilon, CDT_ids_needed_type needed_ids)
Map< CDTEdge< T > *, int > * edge_winding_map
uint32_t face_edge_offset
Map< CDTEdge< T > *, int > * polygon_boundary_count_map
CDT_ids_needed_type needed_ids
CrossData(T l, CDTVert< T > *v, SymEdge< T > *i, SymEdge< T > *o)
CrossData(const CrossData &other)
CrossData(CrossData &&other) noexcept
CrossData & operator=(CrossData &&other) noexcept
CrossData & operator=(const CrossData &other)
float dot(VecOp< float, D >, VecOp< float, D >) RET
float distance(float, float) RET
float3x3 scale(float3x3 mat, float2 scale)
Quaternion interpolate(Quaternion a, Quaternion b, float t)
float distance_squared(VecT a, VecT b)
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
isect_result< VecBase< T, Size > > isect_seg_seg(const VecBase< T, Size > &v1, const VecBase< T, Size > &v2, const VecBase< T, Size > &v3, const VecBase< T, Size > &v4)
AxisSigned cross(const AxisSigned a, const AxisSigned b)
void min_max(const T &value, T &min, T &max)
void remove_non_constraint_edges_leave_valid_bmesh(CDT_state< T > *cdt_state, const bool use_hole_status)
CDT_result< T > delaunay_calc(const CDT_input< T > &input, CDT_output_type output_type)
static void add_list_to_input_ids(VectorSet< uint32_t > &dst, const VectorSet< uint32_t > &src)
void dissolve_symedge(CDT_state< T > *cdt_state, SymEdge< T > *se)
static constexpr bool USE_POW10_FACE_EDGE_OFFSET_ROUND_UP
bool is_original_vert(const CDTVert< T > *v, CDT_state< T > *cdt)
void flood_fill_region_values(const Map< int2, Value > ®ion_pair_value, MutableSpan< Value > region_value, const Value unset_value, CombineFn combine)
int tri_orient(const SymEdge< T > *t)
void add_edge_constraint(CDT_state< T > *cdt_state, CDTVert< T > *v1, CDTVert< T > *v2, uint32_t input_id, LinkNode **r_edges)
SymEdge< T > * find_symedge_with_face(const CDTVert< T > *v, const CDTFace< T > *f)
void add_edge_constraints(CDT_state< T > *cdt_state, const CDT_input< T > &input)
bool is_border_edge(const CDTEdge< T > *e, const CDT_state< T > *cdt)
bool vert_touches_face(const CDTVert< T > *v, const CDTFace< T > *f)
std::string sename(const SymEdge< T > *se)
static void add_to_input_ids(VectorSet< uint32_t > &dst, uint32_t input_id)
static bool id_range_in_list(const VectorSet< uint32_t > &id_list, uint32_t range_start, uint32_t range_end)
void dump_crossings(const Span< CrossData< T > > crossings)
bool vert_left_of_symedge(CDTVert< T > *v, SymEdge< T > *se)
std::string vertname(const CDTVert< T > *v)
void cdt_draw(const std::string &label, const CDTArrangement< T > &cdt)
bool site_lexicographic_sort(const SiteInfo< T > &a, const SiteInfo< T > &b)
bool vert_right_of_symedge(CDTVert< T > *v, SymEdge< T > *se)
std::string short_se_dump(const SymEdge< T > *se)
int add_face_constraints(CDT_state< T > *cdt_state, const CDT_input< T > &input, CDT_output_type output_type, const bool need_winding)
void find_site_merges(Array< SiteInfo< T > > &sites)
CDT_result< T > get_cdt_output(CDT_state< T > *cdt_state, CDT_output_type output_type)
bool is_deleted_edge(const CDTEdge< T > *e)
static bool output_uses_nonzero_holes(const CDT_output_type output_type)
SymEdge< T > * sym(const SymEdge< T > *se)
void dc_triangulate(CDTArrangement< T > *cdt, Array< SiteInfo< T > > &sites)
void fill_crossdata_for_intersect(const FatCo< T > &curco, const CDTVert< T > *v2, SymEdge< T > *t, CrossData< T > *cd, CrossData< T > *cd_next, const T epsilon)
static bool in_line(const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c)
void remove_non_constraint_edges(CDT_state< T > *cdt_state)
bool dc_tri_valid(SymEdge< T > *se, SymEdge< T > *basel, SymEdge< T > *basel_sym)
void add_face_ids(CDT_state< T > *cdt_state, SymEdge< T > *face_symedge, uint32_t face_id, uint32_t fedge_start, uint32_t fedge_end)
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
void prepare_cdt_for_output(CDT_state< T > *cdt_state, const CDT_output_type output_type)
static int filtered_orient2d(const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c)
bool is_constrained_edge(const CDTEdge< T > *e)
void detect_holes_with_fillrule_even_odd(CDT_state< T > *cdt_state)
void detect_holes_with_fillrule_nonzero(CDT_state< T > *cdt_state)
static constexpr int VISIT_INDEX_OUTER_FACE
static std::string trunc_ptr(const void *p)
static void re_delaunay_triangulate(CDTArrangement< T > *cdt, SymEdge< T > *se)
void initial_triangulation(CDTArrangement< T > *cdt)
void remove_outer_edges_until_constraints(CDT_state< T > *cdt_state)
double math_to_double(const T)
CDT_result< T > delaunay_2d_calc(const CDT_input< T > &input, CDT_output_type output_type)
void remove_faces_in_holes(CDT_state< T > *cdt_state)
void get_next_crossing_from_edge(CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2, const T epsilon)
void dc_tri(CDTArrangement< T > *cdt, Array< SiteInfo< T > > &sites, int start, int end, SymEdge< T > **r_le, SymEdge< T > **r_re)
static uint32_t power_of_10_greater_equal_to(uint32_t x)
void fill_crossdata_for_through_vert(CDTVert< T > *v, SymEdge< T > *cd_out, CrossData< T > *cd, CrossData< T > *cd_next)
SymEdge< T > * prev(const SymEdge< T > *se)
bool exists_edge(const CDTVert< T > *v1, const CDTVert< T > *v2)
static int filtered_incircle(const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c, const FatCo< T > &d)
bool get_next_crossing_from_vert(CDT_state< T > *cdt_state, CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2)
static bool output_uses_evenodd_holes(const CDT_output_type output_type)
void add_input_verts(CDT_state< T > *cdt_state, const CDT_input< T > &input)
static constexpr int VISIT_INDEX_UNVISITED
SymEdge< T > * find_symedge_between_verts(const CDTVert< T > *v1, const CDTVert< T > *v2)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void void * BLI_linklist_pop(LinkNode **listp) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
int orient2d(const double2 &a, const double2 &b, const double2 &c)
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES_NONZERO
@ CDT_CONSTRAINTS_VALID_BMESH
@ CDT_INSIDE_WITH_HOLES_NONZERO
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES
VecBase< double, 2 > double2
ATTR_WARN_UNUSED_RESULT const BMVert * v
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
int incircle(const double2 &a, const double2 &b, const double2 &c, const double2 &d)
VecBase< int32_t, 2 > int2
void void void void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) ATTR_NONNULL(1)
void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
CDTEdge< T > * split_edge(SymEdge< T > *se, T lambda, Map< CDTEdge< T > *, int > *edge_winding_map, Map< CDTEdge< T > *, int > *polygon_boundary_count_map)
CDTEdge< T > * add_edge(CDTVert< T > *v1, CDTVert< T > *v2, CDTFace< T > *fleft, CDTFace< T > *fright)
CDTVert< T > * get_vert_resolve_merge(int i)
CDTVert< T > * add_vert(const VecBase< T, 2 > &pt)
CDTFace< T > * outer_face
void delete_edge(SymEdge< T > *se)
CDTEdge< T > * add_vert_to_symedge_edge(CDTVert< T > *v, SymEdge< T > *se)
Vector< CDTVert< T > * > verts
void reserve(int verts_num, int edges_num, int faces_num)
CDTEdge< T > * add_diagonal(SymEdge< T > *s1, SymEdge< T > *s2)
CDTEdge< T > * connect_separate_parts(SymEdge< T > *se1, SymEdge< T > *se2)
CDTFace< T > * add_face()
Vector< CDTFace< T > * > faces
Vector< CDTEdge< T > * > edges
VectorSet< uint32_t > input_ids
VectorSet< uint32_t > input_ids
CDTVert(const VecBase< T, 2 > &pt)
VectorSet< uint32_t > input_ids
EdgeToSort(EdgeToSort &&other) noexcept
EdgeToSort(const EdgeToSort &other)
EdgeToSort & operator=(const EdgeToSort &other)
EdgeToSort & operator=(EdgeToSort &&other)
IndexRange index_range() const