33 return (
v < 0) ? -
v :
v;
37 template<> mpq_class math_abs<mpq_class>(
const mpq_class
v)
55 template<>
double math_to_double<mpq_class>(
const mpq_class
v)
77 template<
typename Arith_t>
struct CDTVert;
78 template<
typename Arith_t>
struct CDTEdge;
79 template<
typename Arith_t>
struct CDTFace;
81 template<
typename Arith_t>
struct SymEdge {
119 FatCo(
const vec2<mpq_class> &
v);
125 template<>
struct FatCo<mpq_class> {
126 vec2<mpq_class> exact;
128 vec2<double> abs_approx;
131 : exact(vec2<mpq_class>(0, 0)), approx(vec2<
double>(0, 0)), abs_approx(vec2<
double>(0, 0))
135 FatCo(
const vec2<mpq_class> &
v)
138 approx = vec2<double>(
v.x.get_d(),
v.y.get_d());
139 abs_approx = vec2<double>(
fabs(approx.x),
fabs(approx.y));
142 FatCo(
const vec2<double> &
v)
144 exact = vec2<mpq_class>(
v.x,
v.y);
146 abs_approx = vec2<double>(
fabs(approx.x),
fabs(approx.y));
161 FatCo(
const vec2<mpq_class> &
v)
163 exact = vec2<double>(
v.x.get_d(),
v.y.get_d());
165 abs_approx = vec2<double>(
fabs(approx.x),
fabs(approx.y));
173 abs_approx = vec2<double>(
fabs(approx.x),
fabs(approx.y));
179 stream <<
"(" << co.
approx.x <<
", " << co.
approx.y <<
")";
193 int merge_to_index{-1};
248 void reserve(
int verts_num,
int edges_num,
int faces_num);
310 if (
v->merge_to_index != -1) {
311 v = this->verts[
v->merge_to_index];
335 int input_verts_num,
int input_edges_num,
int input_faces_num,
T epsilon,
bool need_ids);
340 for (
int i : this->
verts.index_range()) {
342 v->input_ids.clear();
344 this->
verts[i] =
nullptr;
346 for (
int i : this->edges.index_range()) {
348 e->input_ids.clear();
350 this->edges[i] =
nullptr;
352 for (
int i : this->
faces.index_range()) {
356 this->
faces[i] =
nullptr;
365 std::stringstream ss;
366 ss <<
"[" <<
v->index <<
"]";
373 constexpr
int TRUNC_PTR_MASK = 0xFFFF;
374 std::stringstream ss;
381 std::stringstream ss;
407 return std::string(
"NULL");
415 os <<
"\nCDT\n\nVERTS\n";
419 if (
v->merge_to_index == -1) {
427 constexpr
int print_count_limit = 25;
429 os <<
" edges out:\n";
431 if (se->
next ==
nullptr) {
432 os <<
" [NULL] next/rot symedge, se=" <<
trunc_ptr(se) <<
"\n";
436 os <<
" [NULL] next-next/rot symedge, se=" <<
trunc_ptr(se) <<
"\n";
444 }
while (se !=
v->symedge &&
count < print_count_limit);
450 if (
e->symedges[0].next ==
nullptr) {
454 for (
int i = 0; i < 2; ++i) {
477 static bool append =
false;
483 const char *drawfile =
"./cdt_debug_draw.html";
485 const char *drawfile =
"/tmp/cdt_debug_draw.html";
487 constexpr
int max_draw_width = 1800;
488 constexpr
int max_draw_height = 1600;
489 constexpr
double margin_expand = 0.05;
490 constexpr
int thin_line = 1;
491 constexpr
int thick_line = 4;
492 constexpr
int vert_radius = 3;
493 constexpr
bool draw_vert_labels =
true;
494 constexpr
bool draw_edge_labels =
false;
495 constexpr
bool draw_face_labels =
false;
497 if (cdt.
verts.size() == 0) {
500 vec2<double> vmin(DBL_MAX, DBL_MAX);
501 vec2<double> vmax(-DBL_MAX, -DBL_MAX);
503 for (
int i = 0; i < 2; ++i) {
504 double dvi =
v->
co.approx[i];
513 double draw_margin = ((vmax.x - vmin.x) + (vmax.y - vmin.y)) * margin_expand;
514 double minx = vmin.x - draw_margin;
515 double maxx = vmax.x + draw_margin;
516 double miny = vmin.y - draw_margin;
517 double maxy = vmax.y + draw_margin;
519 double width = maxx - minx;
520 double height = maxy - miny;
522 int view_width = max_draw_width;
523 int view_height =
static_cast<int>(view_width * aspect);
524 if (view_height > max_draw_height) {
525 view_height = max_draw_height;
526 view_width =
static_cast<int>(view_height / aspect);
528 double scale = view_width /
width;
530 # define SX(x) (((x)-minx) * scale)
531 # define SY(y) ((maxy - (y)) * scale)
535 f.open(drawfile, std::ios_base::app);
541 std::cout <<
"Could not open file " << drawfile <<
"\n";
545 f <<
"<div>" <<
label <<
"</div>\n<div>\n"
546 <<
"<svg version=\"1.1\" "
547 "xmlns=\"http://www.w3.org/2000/svg\" "
548 "xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
549 "xml:space=\"preserve\"\n"
550 <<
"width=\"" << view_width <<
"\" height=\"" << view_height <<
"\">n";
553 if (
e->symedges[0].next ==
nullptr) {
558 const vec2<double> &uco = u->
co.approx;
559 const vec2<double> &vco =
v->
co.approx;
560 int strokew =
e->input_ids.size() == 0 ? thin_line : thick_line;
561 f << R
"(<line fill="none" stroke="black" stroke-width=")" << strokew << "\" x1=\""
562 <<
SX(uco[0]) <<
"\" y1=\"" <<
SY(uco[1]) <<
"\" x2=\"" <<
SX(vco[0]) <<
"\" y2=\""
563 <<
SY(vco[1]) <<
"\">\n";
566 if (draw_edge_labels) {
567 f <<
"<text x=\"" <<
SX((uco[0] + vco[0]) / 2) <<
"\" y=\"" <<
SY((uco[1] + vco[1]) / 2)
568 << R
"(" font-size="small">)";
576 f << R
"(<circle fill="black" cx=")" << SX(v->co.approx[0]) << "\" cy=\"" <<
SY(
v->
co.approx[1])
577 <<
"\" r=\"" << vert_radius <<
"\">\n";
578 f <<
" <title>[" << i <<
"]" <<
v->
co.approx <<
"</title>\n";
580 if (draw_vert_labels) {
581 f <<
"<text x=\"" <<
SX(
v->
co.approx[0]) + vert_radius <<
"\" y=\""
582 <<
SY(
v->
co.approx[1]) - vert_radius << R
"(" font-size="small">[)" << i << "]</text>\n";
587 if (draw_face_labels) {
593 if (
e->symedges[0].face == face) {
594 se_face_start = &
e->symedges[0];
597 if (
e->symedges[1].face == face) {
598 se_face_start = &
e->symedges[1];
601 if (se_face_start !=
nullptr) {
604 vec2<double> cen(0.0, 0.0);
612 if (se->
face == face) {
613 cen = cen + se->
vert->co.approx;
616 }
while ((se = se->
next) != se_face_start);
617 if (face_nverts > 0) {
618 cen = cen /
double(face_nverts);
621 f <<
"<text x=\"" <<
SX(cen[0]) <<
"\" y=\"" <<
SY(cen[1]) <<
"\""
622 <<
" font-size=\"small\">[";
650 int filtered_orient2d<mpq_class>(
const FatCo<mpq_class> &
a,
651 const FatCo<mpq_class> &
b,
652 const FatCo<mpq_class> &
c)
654 double det = (
a.approx[0] -
c.approx[0]) * (
b.approx[1] -
c.approx[1]) -
655 (
a.approx[1] -
c.approx[1]) * (
b.approx[0] -
c.approx[0]);
656 double supremum = (
a.abs_approx[0] +
c.abs_approx[0]) * (
b.abs_approx[1] +
c.abs_approx[1]) +
657 (
a.abs_approx[1] +
c.abs_approx[1]) * (
b.abs_approx[0] +
c.abs_approx[0]);
658 constexpr
double index_orient2d = 6;
659 double err_bound = supremum * index_orient2d * DBL_EPSILON;
660 if (
fabs(det) > err_bound) {
661 return det > 0 ? 1 : -1;
669 const FatCo<double> &
b,
670 const FatCo<double> &
c)
686 int filtered_incircle<mpq_class>(
const FatCo<mpq_class> &
a,
687 const FatCo<mpq_class> &
b,
688 const FatCo<mpq_class> &
c,
689 const FatCo<mpq_class> &d)
691 double adx =
a.approx[0] - d.approx[0];
692 double bdx =
b.approx[0] - d.approx[0];
693 double cdx =
c.approx[0] - d.approx[0];
694 double ady =
a.approx[1] - d.approx[1];
695 double bdy =
b.approx[1] - d.approx[1];
696 double cdy =
c.approx[1] - d.approx[1];
697 double bdxcdy = bdx * cdy;
698 double cdxbdy = cdx * bdy;
699 double alift = adx * adx + ady * ady;
700 double cdxady = cdx * ady;
701 double adxcdy = adx * cdy;
702 double blift = bdx * bdx + bdy * bdy;
703 double adxbdy = adx * bdy;
704 double bdxady = bdx * ady;
705 double clift = cdx * cdx + cdy * cdy;
706 double det = alift * (bdxcdy - cdxbdy) + blift * (cdxady - adxcdy) + clift * (adxbdy - bdxady);
708 double sup_adx =
a.abs_approx[0] + d.abs_approx[0];
709 double sup_bdx =
b.abs_approx[0] + d.abs_approx[0];
710 double sup_cdx =
c.abs_approx[0] + d.abs_approx[0];
711 double sup_ady =
a.abs_approx[1] + d.abs_approx[1];
712 double sup_bdy =
b.abs_approx[1] + d.abs_approx[1];
713 double sup_cdy =
c.abs_approx[1] + d.abs_approx[1];
714 double sup_bdxcdy = sup_bdx * sup_cdy;
715 double sup_cdxbdy = sup_cdx * sup_bdy;
716 double sup_alift = sup_adx * sup_adx + sup_ady * sup_ady;
717 double sup_cdxady = sup_cdx * sup_ady;
718 double sup_adxcdy = sup_adx * sup_cdy;
719 double sup_blift = sup_bdx * sup_bdx + sup_bdy * sup_bdy;
720 double sup_adxbdy = sup_adx * sup_bdy;
721 double sup_bdxady = sup_bdx * sup_ady;
722 double sup_clift = sup_cdx * sup_cdx + sup_cdy * sup_cdy;
723 double sup_det = sup_alift * (sup_bdxcdy + sup_cdxbdy) + sup_blift * (sup_cdxady + sup_adxcdy) +
724 sup_clift * (sup_adxbdy + sup_bdxady);
726 double err_bound = sup_det * index * DBL_EPSILON;
727 if (
fabs(det) > err_bound) {
728 return det < 0.0 ? -1 : (det > 0.0 ? 1 : 0);
736 const FatCo<double> &
b,
737 const FatCo<double> &
c,
738 const FatCo<double> &d)
740 return incircle(
a.approx,
b.approx,
c.approx, d.approx);
749 template<
typename T>
static bool in_line(
const FatCo<T> &
a,
const FatCo<T> &
b,
const FatCo<T> &
c);
753 bool in_line<mpq_class>(
const FatCo<mpq_class> &
a,
754 const FatCo<mpq_class> &
b,
755 const FatCo<mpq_class> &
c)
757 vec2<double> ab =
b.approx -
a.approx;
758 vec2<double> bc =
c.approx -
b.approx;
759 vec2<double> ac =
c.approx -
a.approx;
760 vec2<double> supremum_ab =
b.abs_approx +
a.abs_approx;
761 vec2<double> supremum_bc =
c.abs_approx +
b.abs_approx;
762 vec2<double> supremum_ac =
c.abs_approx +
a.abs_approx;
763 double dot_ab_ac = ab.x * ac.x + ab.y * ac.y;
764 double supremum_dot_ab_ac = supremum_ab.x * supremum_ac.x + supremum_ab.y * supremum_ac.y;
765 constexpr
double index = 6;
766 double err_bound = supremum_dot_ab_ac * index * DBL_EPSILON;
767 if (dot_ab_ac < -err_bound) {
770 double dot_bc_ac = bc.x * ac.x + bc.y * ac.y;
771 double supremum_dot_bc_ac = supremum_bc.x * supremum_ac.x + supremum_bc.y * supremum_ac.y;
772 err_bound = supremum_dot_bc_ac * index * DBL_EPSILON;
773 if (dot_bc_ac < -err_bound) {
776 vec2<mpq_class> exact_ab =
b.exact -
a.exact;
777 vec2<mpq_class> exact_ac =
c.exact -
a.exact;
778 if (
dot(exact_ab, exact_ac) < 0) {
781 vec2<mpq_class> exact_bc =
c.exact -
b.exact;
782 return dot(exact_bc, exact_ac) >= 0;
789 vec2<double> ab =
b.approx -
a.approx;
790 vec2<double> ac =
c.approx -
a.approx;
791 if (
dot(ab, ac) < 0) {
794 vec2<double> bc =
c.approx -
b.approx;
795 return dot(bc, ac) >= 0;
801 this->co.approx = pt;
802 this->co.abs_approx = pt;
803 this->symedge =
nullptr;
805 this->merge_to_index = -1;
806 this->visit_index = 0;
813 this->co.approx =
double2(pt.x.get_d(), pt.y.get_d());
814 this->co.abs_approx =
double2(
fabs(this->co.approx.x),
fabs(this->co.approx.y));
815 this->symedge =
nullptr;
817 this->merge_to_index = -1;
818 this->visit_index = 0;
824 CDTVert<T> *
v =
new CDTVert<T>(pt);
825 int index = this->
verts.append_and_get_index(v);
836 CDTEdge<T> *
e =
new CDTEdge<T>();
837 this->edges.append(
e);
838 SymEdge<T> *se = &
e->symedges[0];
839 SymEdge<T> *sesym = &
e->symedges[1];
840 se->edge = sesym->edge =
e;
842 sesym->face = fright;
844 if (
v1->symedge ==
nullptr) {
848 if (
v2->symedge ==
nullptr) {
851 se->next = sesym->next = se->rot = sesym->rot =
nullptr;
857 CDTFace<T> *f =
new CDTFace<T>();
858 this->
faces.append(f);
865 this->
verts.reserve(2 * verts_num);
866 this->edges.reserve(3 * verts_num + 2 * edges_num + 3 * 2 * faces_num);
867 this->
faces.reserve(2 * verts_num + 2 * edges_num + 2 * faces_num);
872 int input_verts_num,
int input_edges_num,
int input_faces_num,
T epsilon,
bool need_ids)
874 this->input_vert_num = input_verts_num;
875 this->cdt.reserve(input_verts_num, input_edges_num, input_faces_num);
876 this->cdt.outer_face = this->cdt.add_face();
878 this->need_ids = need_ids;
879 this->visit_count = 0;
885 for (
int id : id_list) {
886 if (
id >= range_start &&
id <= range_end) {
900 for (
int value :
src) {
905 template<
typename T>
inline bool is_border_edge(
const CDTEdge<T> *
e,
const CDT_state<T> *cdt)
907 return e->symedges[0].face == cdt->outer_face ||
e->symedges[1].face == cdt->outer_face;
912 return e->input_ids.size() > 0;
917 return e->symedges[0].next ==
nullptr;
922 return (
v->index < cdt->input_vert_num);
931 SymEdge<T> *
t =
v1->symedge;
932 SymEdge<T> *tstart =
t;
934 if (
t->next->vert ==
v2) {
937 }
while ((
t =
t->rot) != tstart);
946 SymEdge<T> *
t =
v->symedge;
947 SymEdge<T> *tstart =
t;
952 }
while ((
t =
t->rot) != tstart);
959 template<
typename T>
inline bool exists_edge(
const CDTVert<T> *
v1,
const CDTVert<T> *
v2)
969 SymEdge<T> *se =
v->symedge;
974 }
while ((se = se->rot) !=
v->symedge);
988 CDTFace<T> *fold = s1->face;
989 CDTFace<T> *fnew = this->add_face();
990 SymEdge<T> *s1prev =
prev(s1);
991 SymEdge<T> *s1prevsym =
sym(s1prev);
992 SymEdge<T> *s2prev =
prev(s2);
993 SymEdge<T> *s2prevsym =
sym(s2prev);
994 CDTEdge<T> *ediag = this->
add_edge(s1->vert, s2->vert, fnew, fold);
995 SymEdge<T> *sdiag = &ediag->symedges[0];
996 SymEdge<T> *sdiagsym = &ediag->symedges[1];
999 s2prev->next = sdiagsym;
1000 s1prev->next = sdiag;
1002 sdiag->rot = s1prevsym;
1004 sdiagsym->rot = s2prevsym;
1005 for (SymEdge<T> *se = s2; se != sdiag; se = se->next) {
1012 template<
typename T>
1015 SymEdge<T> *se_rot = se->rot;
1016 SymEdge<T> *se_rotsym =
sym(se_rot);
1018 CDTEdge<T> *
e = this->
add_edge(v, se->vert, se->face, se->face);
1019 SymEdge<T> *new_se = &
e->symedges[0];
1020 SymEdge<T> *new_se_sym = &
e->symedges[1];
1022 new_se_sym->next = new_se;
1023 new_se->rot = new_se;
1024 new_se_sym->rot = se_rot;
1025 se->rot = new_se_sym;
1026 se_rotsym->next = new_se_sym;
1035 template<
typename T>
1038 BLI_assert(se1->face == this->outer_face && se2->face == this->outer_face);
1039 SymEdge<T> *se1_rot = se1->rot;
1040 SymEdge<T> *se1_rotsym =
sym(se1_rot);
1041 SymEdge<T> *se2_rot = se2->rot;
1042 SymEdge<T> *se2_rotsym =
sym(se2_rot);
1043 CDTEdge<T> *
e = this->
add_edge(se1->vert, se2->vert, this->outer_face, this->outer_face);
1044 SymEdge<T> *new_se = &
e->symedges[0];
1045 SymEdge<T> *new_se_sym = &
e->symedges[1];
1047 new_se_sym->next = se1;
1048 new_se->rot = se1_rot;
1049 new_se_sym->rot = se2_rot;
1051 se2->rot = new_se_sym;
1052 se1_rotsym->next = new_se;
1053 se2_rotsym->next = new_se_sym;
1065 const vec2<T> *
a = &se->vert->co.exact;
1066 const vec2<T> *
b = &se->next->vert->co.exact;
1067 SymEdge<T> *sesym =
sym(se);
1068 SymEdge<T> *sesymprev =
prev(sesym);
1069 SymEdge<T> *sesymprevsym =
sym(sesymprev);
1070 SymEdge<T> *senext = se->next;
1072 CDTEdge<T> *
e = this->
add_edge(v, se->next->vert, se->face, sesym->face);
1074 SymEdge<T> *newse = &
e->symedges[0];
1075 SymEdge<T> *newsesym = &
e->symedges[1];
1077 newsesym->next = sesym;
1078 newse->next = senext;
1081 senext->rot = newsesym;
1082 newsesym->rot = sesymprevsym;
1083 sesymprev->next = newsesym;
1084 if (newsesym->vert->symedge == sesym) {
1085 newsesym->vert->symedge = newsesym;
1114 SymEdge<T> *sesym =
sym(se);
1115 CDTVert<T> *
v1 = se->vert;
1116 CDTVert<T> *
v2 = sesym->vert;
1117 CDTFace<T> *aface = se->face;
1118 CDTFace<T> *bface = sesym->face;
1119 SymEdge<T> *f = se->next;
1120 SymEdge<T> *h =
prev(se);
1121 SymEdge<T> *i = sesym->next;
1122 SymEdge<T> *j =
prev(sesym);
1123 SymEdge<T> *jsym =
sym(j);
1124 SymEdge<T> *hsym =
sym(h);
1125 bool v1_isolated = (i == se);
1126 bool v2_isolated = (f == sesym);
1136 if (!v1_isolated && !v2_isolated && aface != bface) {
1137 for (SymEdge<T> *k = i; k != f; k = k->next) {
1144 v1->symedge =
nullptr;
1146 else if (
v1->symedge == se) {
1150 v2->symedge =
nullptr;
1152 else if (
v2->symedge == sesym) {
1157 se->next = se->rot =
nullptr;
1158 sesym->next = sesym->rot =
nullptr;
1159 if (!v1_isolated && !v2_isolated && aface != bface) {
1160 bface->deleted =
true;
1161 if (this->outer_face == bface) {
1162 this->outer_face = aface;
1178 const vec2<T> &co_a =
a.v->co.exact;
1179 const vec2<T> &co_b =
b.v->co.exact;
1180 if (co_a[0] < co_b[0]) {
1183 if (co_a[0] > co_b[0]) {
1186 if (co_a[1] < co_b[1]) {
1189 if (co_a[1] > co_b[1]) {
1192 return a.orig_index <
b.orig_index;
1202 int n = sites.size();
1203 for (
int i = 0; i < n - 1; ++i) {
1205 while (j < n && sites[j].
v->
co.exact == sites[i].v->co.exact) {
1206 sites[j].v->merge_to_index = sites[i].orig_index;
1226 template<
typename T>
1227 inline bool dc_tri_valid(SymEdge<T> *se, SymEdge<T> *basel, SymEdge<T> *basel_sym)
1229 return filtered_orient2d(se->next->vert->co, basel_sym->vert->co, basel->vert->co) > 0;
1238 template<
typename T>
1246 constexpr
int dbg_level = 0;
1247 if (dbg_level > 0) {
1248 std::cout <<
"DC_TRI start=" << start <<
" end=" << end <<
"\n";
1250 int n = end - start;
1259 CDTVert<T> *
v1 = sites[start].v;
1260 CDTVert<T> *
v2 = sites[start + 1].v;
1261 CDTEdge<T> *ea = cdt->add_edge(
v1,
v2, cdt->outer_face, cdt->outer_face);
1262 ea->symedges[0].next = &ea->symedges[1];
1263 ea->symedges[1].next = &ea->symedges[0];
1264 ea->symedges[0].rot = &ea->symedges[0];
1265 ea->symedges[1].rot = &ea->symedges[1];
1267 *r_le = &ea->symedges[0];
1268 *r_re = &ea->symedges[1];
1271 CDTVert<T> *v3 = sites[start + 2].v;
1272 CDTEdge<T> *eb = cdt->add_vert_to_symedge_edge(v3, &ea->symedges[1]);
1275 cdt->add_diagonal(&eb->symedges[0], &ea->symedges[0]);
1276 *r_le = &ea->symedges[0];
1277 *r_re = &eb->symedges[0];
1279 else if (orient < 0) {
1280 cdt->add_diagonal(&ea->symedges[0], &eb->symedges[0]);
1281 *r_le = ea->symedges[0].rot;
1282 *r_re = eb->symedges[0].rot;
1286 *r_le = &ea->symedges[0];
1287 *r_re = &eb->symedges[0];
1293 BLI_assert(n2 >= 2 && end - (start + n2) >= 2);
1298 dc_tri(cdt, sites, start, start + n2, &ldo, &ldi);
1299 dc_tri(cdt, sites, start + n2, end, &rdi, &rdo);
1300 if (dbg_level > 0) {
1301 std::cout <<
"\nDC_TRI merge step for start=" << start <<
", end=" << end <<
"\n";
1302 std::cout <<
"ldo " << ldo <<
"\n"
1303 <<
"ldi " << ldi <<
"\n"
1304 <<
"rdi " << rdi <<
"\n"
1305 <<
"rdo " << rdo <<
"\n";
1306 if (dbg_level > 1) {
1324 if (dbg_level > 0) {
1325 std::cout <<
"common lower tangent in between\n"
1326 <<
"rdi " << rdi <<
"\n"
1327 <<
"ldi" << ldi <<
"\n";
1330 CDTEdge<T> *ebasel = cdt->connect_separate_parts(
sym(rdi)->
next, ldi);
1331 SymEdge<T> *basel = &ebasel->symedges[0];
1332 SymEdge<T> *basel_sym = &ebasel->symedges[1];
1333 if (dbg_level > 1) {
1334 std::cout <<
"basel " << basel;
1335 cdt_draw(
"after basel made", *cdt);
1337 if (ldi->vert == ldo->vert) {
1340 if (rdi->vert == rdo->vert) {
1348 SymEdge<T> *lcand = basel_sym->rot;
1349 SymEdge<T> *rcand = basel_sym->next;
1350 if (dbg_level > 1) {
1351 std::cout <<
"\ntop of merge loop\n";
1352 std::cout <<
"lcand " << lcand <<
"\n"
1353 <<
"rcand " << rcand <<
"\n"
1354 <<
"basel " << basel <<
"\n";
1357 if (dbg_level > 1) {
1358 std::cout <<
"found valid lcand\n";
1359 std::cout <<
" lcand" << lcand <<
"\n";
1363 lcand->next->vert->co,
1364 lcand->rot->next->vert->co) > 0.0) {
1365 if (dbg_level > 1) {
1366 std::cout <<
"incircle says to remove lcand\n";
1367 std::cout <<
" lcand" << lcand <<
"\n";
1369 SymEdge<T> *
t = lcand->rot;
1370 cdt->delete_edge(
sym(lcand));
1376 if (dbg_level > 1) {
1377 std::cout <<
"found valid rcand\n";
1378 std::cout <<
" rcand" << rcand <<
"\n";
1382 rcand->next->vert->co,
1383 sym(rcand)->
next->next->vert->co) > 0.0) {
1384 if (dbg_level > 0) {
1385 std::cout <<
"incircle says to remove rcand\n";
1386 std::cout <<
" rcand" << rcand <<
"\n";
1389 cdt->delete_edge(rcand);
1394 bool valid_lcand =
dc_tri_valid(lcand, basel, basel_sym);
1395 bool valid_rcand =
dc_tri_valid(rcand, basel, basel_sym);
1396 if (dbg_level > 0) {
1397 std::cout <<
"after bubbling up, valid_lcand=" << valid_lcand
1398 <<
", valid_rand=" << valid_rcand <<
"\n";
1399 std::cout <<
"lcand" << lcand <<
"\n"
1400 <<
"rcand" << rcand <<
"\n";
1402 if (!valid_lcand && !valid_rcand) {
1410 rcand->next->vert->co) > 0)) {
1411 if (dbg_level > 0) {
1412 std::cout <<
"connecting rcand\n";
1413 std::cout <<
" se1=basel_sym" << basel_sym <<
"\n";
1414 std::cout <<
" se2=rcand->next" << rcand->next <<
"\n";
1416 ebasel = cdt->add_diagonal(rcand->next, basel_sym);
1419 if (dbg_level > 0) {
1420 std::cout <<
"connecting lcand\n";
1421 std::cout <<
" se1=sym(lcand)" <<
sym(lcand) <<
"\n";
1422 std::cout <<
" se2=basel_sym->next" << basel_sym->
next <<
"\n";
1424 ebasel = cdt->add_diagonal(basel_sym->next,
sym(lcand));
1426 basel = &ebasel->symedges[0];
1427 basel_sym = &ebasel->symedges[1];
1428 BLI_assert(basel_sym->face == cdt->outer_face);
1429 if (dbg_level > 2) {
1430 cdt_draw(
"after adding new crossedge", *cdt);
1444 int nsites = sites.size();
1445 while (j < nsites) {
1447 sites[i] = sites[j++];
1448 if (sites[i].
v->merge_to_index < 0) {
1458 dc_tri(cdt, sites, 0, n, &le, &re);
1481 int n = cdt->verts.size();
1485 Array<SiteInfo<T>> sites(n);
1486 for (
int i = 0; i < n; ++i) {
1487 sites[i].v = cdt->verts[i];
1488 sites[i].orig_index = i;
1490 std::sort(sites.begin(), sites.end(), site_lexicographic_sort<T>);
1504 if (se->face == cdt->outer_face ||
sym(se)->face == cdt->outer_face) {
1509 for (SymEdge<T> *ss = se->next; ss != se; ss = ss->next) {
1517 SymEdge<T> *first = se->next->next;
1519 CDTVert<T> *
a = se->vert;
1520 CDTVert<T> *
b = se->next->vert;
1521 CDTVert<T> *
c = first->vert;
1522 SymEdge<T> *cse = first;
1523 for (SymEdge<T> *ss = first->next; ss != se; ss = ss->next) {
1524 CDTVert<T> *
v = ss->vert;
1531 CDTEdge<T> *ebc =
nullptr;
1532 CDTEdge<T> *eca =
nullptr;
1534 ebc = cdt->add_diagonal(se->next, cse);
1537 eca = cdt->add_diagonal(cse, se);
1592 : lambda(other.lambda), vert(other.vert), in(other.in),
out(other.
out)
1596 : lambda(std::move(other.lambda)),
1597 vert(std::move(other.vert)),
1598 in(std::move(other.in)),
1599 out(std::move(other.out))
1605 if (
this != &other) {
1615 lambda = std::move(other.lambda);
1616 vert = std::move(other.vert);
1617 in = std::move(other.in);
1618 out = std::move(other.out);
1623 template<
typename T>
1627 const CDTVert<T> *
v2);
1636 template<
typename T>
1646 cd_next->
in =
nullptr;
1647 cd_next->
out =
nullptr;
1654 if (se->vert !=
v) {
1656 if (se->vert !=
v) {
1678 template<
typename T>
1680 const CDTVert<T> *
v2,
1686 CDTVert<T> *va =
t->vert;
1687 CDTVert<T> *vb =
t->next->vert;
1688 CDTVert<T> *vc =
t->next->next->vert;
1689 SymEdge<T> *se_vcvb =
sym(
t->next);
1690 SymEdge<T> *se_vcva =
t->next->next;
1691 BLI_assert(se_vcva->vert == vc && se_vcva->next->vert == va);
1692 BLI_assert(se_vcvb->vert == vc && se_vcvb->next->vert == vb);
1694 auto isect =
isect_seg_seg(va->co.exact, vb->co.exact, curco.exact,
v2->
co.exact);
1695 T &lambda = isect.lambda;
1696 switch (isect.kind) {
1699 if (!std::is_same<T, mpq_class>::value) {
1703 double len_ab =
distance(va->co.approx, vb->co.approx);
1704 if (lambda * len_ab <=
epsilon) {
1707 else if ((1 - lambda) * len_ab <=
epsilon) {
1729 else if (lambda == 1) {
1742 if (std::is_same<T, mpq_class>::value) {
1747 const T middle_lambda = 0.5;
1748 if (lambda <= middle_lambda) {
1776 template<
typename T>
1780 const CDTVert<T> *
v2)
1782 SymEdge<T> *tstart = cd->
vert->symedge;
1783 SymEdge<T> *
t = tstart;
1784 CDTVert<T> *vcur = cd->
vert;
1793 if (
t->face != cdt_state->cdt.outer_face &&
tri_orient(
t) < 0) {
1796 CDTVert<T> *va =
t->next->vert;
1797 CDTVert<T> *vb =
t->next->next->vert;
1799 if (orient1 == 0 && in_line<T>(vcur->co, va->co,
v2->
co)) {
1804 if (
t->face != cdt_state->cdt.outer_face) {
1807 if (orient1 > 0 && orient2 < 0) {
1815 }
while ((
t =
t->rot) != tstart);
1827 template<
typename T>
1830 const CDTVert<T> *
v2,
1833 CDTVert<T> *va = cd->
in->
vert;
1836 FatCo<T> fat_curco(curco);
1838 CDTVert<T> *vc = se_ac->
next->
vert;
1841 fill_crossdata_for_intersect<T>(fat_curco,
v2, se_ac->next, cd, cd_next,
epsilon);
1843 else if (orient > 0.0) {
1847 *cd_next =
CrossData<T>{0.0, vc, se_ac->next,
nullptr};
1852 template<
typename T>
1855 std::cout <<
"CROSSINGS\n";
1856 for (
int i = 0; i < crossings.size(); ++i) {
1857 std::cout << i <<
": ";
1860 std::cout <<
"v" << cd.
vert->index;
1863 std::cout <<
"lambda=" << cd.
lambda;
1865 if (cd.
in !=
nullptr) {
1884 template<
typename T>
1886 CDT_state<T> *cdt_state, CDTVert<T> *
v1, CDTVert<T> *
v2,
int input_id,
LinkNode **r_edges)
1888 constexpr
int dbg_level = 0;
1889 if (dbg_level > 0) {
1910 if (r_edges !=
nullptr) {
1912 *r_edges = edge_list.
list;
1931 int visit = ++cdt_state->visit_count;
1935 while (!((n = crossings.size()) > 0 && crossings[n - 1].vert ==
v2)) {
1940 if (crossings[n - 1].lambda == 0) {
1944 get_next_crossing_from_edge<T>(cd, cd_next,
v2, cdt_state->epsilon);
1947 constexpr
int unreasonably_large_crossings = 100000;
1948 if (!ok || crossings.size() == unreasonably_large_crossings) {
1953 if (crossings[n].lambda == 0) {
1954 if (crossings[n].vert->visit_index == visit) {
1959 crossings[n].vert->visit_index = visit;
1963 if (dbg_level > 0) {
1977 int ncrossings = crossings.size();
1978 for (
int i = 2; i < ncrossings; ++i) {
1981 CDTVert<T> *
v = cd->
vert;
1984 for (j = i - 1; j > 0; --j) {
1985 cd_prev = &crossings[j];
1986 if ((cd_prev->
lambda == 0.0 && cd_prev->
vert !=
v) ||
1994 cd_prev = &crossings[j];
1996 if (cd_prev->
lambda == 0.0) {
1998 if (se ==
nullptr) {
2006 if (se ==
nullptr) {
2018 for (
int i = 0; i < ncrossings; ++i) {
2021 CDTEdge<T> *edge = cdt_state->cdt.split_edge(cd->
in, cd->
lambda);
2022 cd->
vert = edge->symedges[0].vert;
2029 for (
int i = 0; i < ncrossings; ++i) {
2032 cdt_state->cdt.delete_edge(cd->
in);
2039 SymEdge<T> *tstart = crossings[0].
out;
2040 for (
int i = 1; i < ncrossings; i++) {
2042 if (cd->
lambda == -1.0) {
2046 SymEdge<T> *tnext =
t;
2050 t = cd->
vert->symedge;
2054 else if (cd->
lambda == 0.0) {
2061 for (j = i - 1; j >= 0; j--) {
2062 cd_prev = &crossings[j];
2063 if (cd_prev->
lambda != -1.0) {
2071 if (r_edges !=
nullptr) {
2077 if (tstart->next->vert ==
t->vert) {
2078 edge = tstart->edge;
2081 edge = cdt_state->cdt.add_diagonal(tstart,
t);
2084 if (r_edges !=
nullptr) {
2091 if (i < ncrossings - 1) {
2092 if (tnext !=
nullptr) {
2099 *r_edges = edge_list.
list;
2111 int ne =
input.edge.size();
2112 int nv =
input.vert.size();
2113 for (
int i = 0; i < ne; i++) {
2114 int iv1 =
input.edge[i].first;
2115 int iv2 =
input.edge[i].second;
2116 if (iv1 < 0 || iv1 >= nv || iv2 < 0 || iv2 >= nv) {
2120 CDTVert<T> *
v1 = cdt_state->cdt.get_vert_resolve_merge(iv1);
2121 CDTVert<T> *
v2 = cdt_state->cdt.get_vert_resolve_merge(iv2);
2122 int id = cdt_state->need_ids ? i : 0;
2125 cdt_state->face_edge_offset = ne;
2146 template<
typename T>
2148 CDT_state<T> *cdt_state, SymEdge<T> *face_symedge,
int face_id,
int fedge_start,
int fedge_end)
2151 cdt_state->visit_count++;
2152 int visit = cdt_state->visit_count;
2153 Vector<SymEdge<T> *> stack;
2154 stack.append(face_symedge);
2155 while (!stack.is_empty()) {
2156 SymEdge<T> *se = stack.pop_last();
2157 CDTFace<T> *face = se->face;
2158 if (face->visit_index == visit) {
2161 face->visit_index = visit;
2163 SymEdge<T> *se_start = se;
2164 for (se = se->next; se != se_start; se = se->next) {
2166 SymEdge<T> *se_sym =
sym(se);
2167 CDTFace<T> *face_other = se_sym->face;
2168 if (face_other->visit_index != visit) {
2169 stack.append(se_sym);
2200 template<
typename T>
2205 int nv =
input.vert.size();
2206 int nf =
input.face.size();
2207 SymEdge<T> *face_symedge0 =
nullptr;
2208 CDTArrangement<T> *cdt = &cdt_state->cdt;
2210 for (
int f = 0; f < nf; f++) {
2215 max_ii(maxflen, cdt_state->face_edge_offset));
2220 BLI_assert(INT_MAX / cdt_state->face_edge_offset > nf);
2221 int faces_added = 0;
2222 for (
int f = 0; f < nf; f++) {
2223 int flen =
input.face[f].size();
2228 int fedge_start = (f + 1) * cdt_state->face_edge_offset;
2229 for (
int i = 0; i < flen; i++) {
2230 int face_edge_id = fedge_start + i;
2231 int iv1 =
input.face[f][i];
2232 int iv2 =
input.face[f][(i + 1) % flen];
2233 if (iv1 < 0 || iv1 >= nv || iv2 < 0 || iv2 >= nv) {
2238 CDTVert<T> *
v1 = cdt->get_vert_resolve_merge(iv1);
2239 CDTVert<T> *
v2 = cdt->get_vert_resolve_merge(iv2);
2241 int id = cdt_state->need_ids ? face_edge_id : 0;
2248 if (edge_list !=
nullptr) {
2249 CDTEdge<T> *face_edge =
static_cast<CDTEdge<T> *
>(edge_list->
link);
2250 face_symedge0 = &face_edge->symedges[0];
2251 if (face_symedge0->vert !=
v1) {
2252 face_symedge0 = &face_edge->symedges[1];
2258 int fedge_end = fedge_start + flen - 1;
2259 if (face_symedge0 !=
nullptr) {
2264 int id = cdt_state->need_ids ? f : 0;
2265 add_face_ids(cdt_state, face_symedge0,
id, fedge_start, fedge_end);
2266 if (cdt_state->need_ids ||
2268 add_face_ids(cdt_state, face_symedge0, f, fedge_start, fedge_end);
2280 CDTArrangement<T> *cdt = &cdt_state->cdt;
2281 SymEdge<T> *symse =
sym(se);
2282 if (symse->face == cdt->outer_face) {
2286 if (
ELEM(cdt->outer_face->symedge, se, symse)) {
2288 if (se->next->next == se) {
2289 cdt->outer_face->symedge =
nullptr;
2292 cdt->outer_face->symedge = se->next->next;
2296 if (se->face->symedge == se) {
2297 se->face->symedge = se->next;
2299 if (symse->face->symedge == symse) {
2300 symse->face->symedge = symse->next;
2303 cdt->delete_edge(se);
2311 for (CDTEdge<T> *
e : cdt_state->cdt.edges) {
2312 SymEdge<T> *se = &
e->symedges[0];
2336 CDTEdge<T> *
e{
nullptr};
2348 if (
this != &other) {
2364 CDTArrangement<T> *cdt = &cdt_state->cdt;
2365 size_t nedges = cdt->edges.size();
2369 Vector<EdgeToSort<T>> dissolvable_edges;
2370 dissolvable_edges.reserve(cdt->edges.size());
2372 for (CDTEdge<T> *
e : cdt->edges) {
2375 dissolvable_edges[i].e =
e;
2376 const vec2<double> &co1 =
e->symedges[0].vert->
co.approx;
2377 const vec2<double> &co2 =
e->symedges[1].vert->
co.approx;
2383 dissolvable_edges.end(),
2385 return (a.len_squared < b.len_squared);
2388 CDTEdge<T> *
e = ets.
e;
2389 SymEdge<T> *se = &
e->symedges[0];
2390 bool dissolve =
true;
2391 CDTFace<T> *fleft = se->face;
2392 CDTFace<T> *fright =
sym(se)->
face;
2393 if (fleft != cdt->outer_face && fright != cdt->outer_face &&
2394 (fleft->input_ids.size() > 0 || fright->input_ids.size() > 0)) {
2397 for (SymEdge<T> *se2 = se->next; dissolve && se2 != se; se2 = se2->next) {
2398 if (
sym(se2)->face == fright ||
2413 int visit = ++cdt_state->visit_count;
2415 cdt_state->cdt.outer_face->visit_index = visit;
2417 Vector<CDTFace<T> *> fstack;
2418 SymEdge<T> *se_start = cdt_state->cdt.outer_face->symedge;
2419 SymEdge<T> *se = se_start;
2422 CDTFace<T> *fsym =
sym(se)->
face;
2423 if (fsym->visit_index != visit) {
2424 fstack.append(fsym);
2427 }
while ((se = se->next) != se_start);
2429 while (!fstack.is_empty()) {
2432 CDTFace<T> *f = fstack.pop_last();
2433 if (f->visit_index == visit) {
2437 f->visit_index = visit;
2438 se_start = se = f->symedge;
2442 CDTFace<T> *fsym =
sym(se)->
face;
2443 if (fsym->visit_index != visit) {
2444 fstack.append(fsym);
2451 }
while (se != se_start);
2452 while (to_dissolve !=
nullptr) {
2454 if (se->next !=
nullptr) {
2463 CDTArrangement<T> *cdt = &cdt_state->cdt;
2464 for (
int i : cdt->faces.index_range()) {
2465 CDTFace<T> *f = cdt->faces[i];
2466 if (!f->deleted && f->hole) {
2468 SymEdge<T> *se = f->symedge;
2469 SymEdge<T> *se_start = se;
2470 SymEdge<T> *se_next =
nullptr;
2481 }
while (se != se_start);
2498 CDTArrangement<T> *cdt = &cdt_state->cdt;
2502 Vector<CDTFace<T> *> fstack;
2503 Vector<CDTFace<T> *> region_rep_face;
2504 for (
int i : cdt->faces.index_range()) {
2505 cdt->faces[i]->visit_index = -1;
2507 int cur_region = -1;
2508 cdt->outer_face->visit_index = -2;
2509 for (
int i : cdt->faces.index_range()) {
2510 CDTFace<T> *f = cdt->faces[i];
2511 if (!f->deleted && f->symedge && f->visit_index == -1) {
2514 region_rep_face.append(f);
2515 while (!fstack.is_empty()) {
2516 CDTFace<T> *f = fstack.pop_last();
2517 if (f->visit_index != -1) {
2520 f->visit_index = cur_region;
2521 SymEdge<T> *se_start = f->symedge;
2522 SymEdge<T> *se = se_start;
2525 CDTFace<T> *fsym =
sym(se)->
face;
2526 if (fsym && !fsym->deleted && fsym->visit_index == -1) {
2527 fstack.append(fsym);
2531 }
while (se != se_start);
2535 cdt_state->visit_count = ++cur_region;
2542 ray_end.exact = vec2<T>(123456, 654321);
2543 for (
int i : region_rep_face.index_range()) {
2544 CDTFace<T> *f = region_rep_face[i];
2546 mid.exact[0] = (f->symedge->vert->co.exact[0] + f->symedge->next->vert->co.exact[0] +
2547 f->symedge->next->next->vert->co.exact[0]) /
2549 mid.exact[1] = (f->symedge->vert->co.exact[1] + f->symedge->next->vert->co.exact[1] +
2550 f->symedge->next->next->vert->co.exact[1]) /
2552 std::atomic<int> hits = 0;
2555 for (const int i : range) {
2556 const CDTEdge<T> *e = cdt->edges[i];
2557 if (!is_deleted_edge(e) && is_constrained_edge(e)) {
2558 if (e->symedges[0].face->visit_index == e->symedges[1].face->visit_index) {
2561 auto isect = isect_seg_seg(ray_end.exact,
2563 e->symedges[0].vert->co.exact,
2564 e->symedges[1].vert->co.exact);
2565 switch (isect.kind) {
2566 case isect_result<vec2<T>>::LINE_LINE_CROSS: {
2570 case isect_result<vec2<T>>::LINE_LINE_EXACT:
2571 case isect_result<vec2<T>>::LINE_LINE_NONE:
2572 case isect_result<vec2<T>>::LINE_LINE_COLINEAR:
2578 f->hole = (hits.load() % 2) == 0;
2582 for (
int i : cdt->faces.index_range()) {
2583 CDTFace<T> *f = cdt->faces[i];
2584 int region = f->visit_index;
2588 CDTFace<T> *f_region_rep = region_rep_face[region];
2590 f->hole = f_region_rep->hole;
2599 template<
typename T>
2602 CDTArrangement<T> *cdt = &cdt_state->cdt;
2603 if (cdt->edges.is_empty()) {
2608 for (CDTEdge<T> *
e : cdt->edges) {
2610 if (
e->symedges[0].face->symedge ==
nullptr) {
2611 e->symedges[0].face->symedge = &
e->symedges[0];
2613 if (
e->symedges[1].face->symedge ==
nullptr) {
2614 e->symedges[1].face->symedge = &
e->symedges[1];
2646 template<
typename T>
2654 CDTArrangement<T> *cdt = &cdt_state->cdt;
2655 result.face_edge_offset = cdt_state->face_edge_offset;
2661 int verts_size = cdt->verts.size();
2662 Array<int> vert_to_output_map(verts_size);
2664 for (
int i = 0; i < verts_size; ++i) {
2665 CDTVert<T> *
v = cdt->verts[i];
2666 if (
v->merge_to_index == -1) {
2667 vert_to_output_map[i] = nv;
2677 if (nv < verts_size) {
2678 for (
int i = 0; i < verts_size; ++i) {
2679 CDTVert<T> *
v = cdt->verts[i];
2680 if (
v->merge_to_index != -1) {
2681 if (cdt_state->need_ids) {
2682 if (i < cdt_state->input_vert_num) {
2686 vert_to_output_map[i] = vert_to_output_map[
v->merge_to_index];
2690 result.vert = Array<vec2<T>>(nv);
2691 if (cdt_state->need_ids) {
2692 result.vert_orig = Array<Vector<int>>(nv);
2695 for (
int i = 0; i < verts_size; ++i) {
2696 CDTVert<T> *
v = cdt->verts[i];
2697 if (
v->merge_to_index == -1) {
2699 if (cdt_state->need_ids) {
2700 if (i < cdt_state->input_vert_num) {
2701 result.vert_orig[i_out].append(i);
2703 for (
int vert :
v->input_ids) {
2704 result.vert_orig[i_out].append(vert);
2712 int ne = std::count_if(cdt->edges.begin(), cdt->edges.end(), [](
const CDTEdge<T> *
e) ->
bool {
2713 return !is_deleted_edge(e);
2715 result.edge = Array<std::pair<int, int>>(ne);
2716 if (cdt_state->need_ids) {
2717 result.edge_orig = Array<Vector<int>>(ne);
2720 for (
const CDTEdge<T> *
e : cdt->edges) {
2722 int vo1 = vert_to_output_map[
e->symedges[0].vert->index];
2723 int vo2 = vert_to_output_map[
e->symedges[1].vert->index];
2724 result.edge[e_out] = std::pair<int, int>(vo1, vo2);
2725 if (cdt_state->need_ids) {
2726 for (
int edge :
e->input_ids) {
2727 result.edge_orig[e_out].append(edge);
2735 int nf = std::count_if(cdt->faces.begin(), cdt->faces.end(), [=](
const CDTFace<T> *f) ->
bool {
2736 return !f->deleted && f != cdt->outer_face;
2738 result.face = Array<Vector<int>>(nf);
2739 if (cdt_state->need_ids) {
2740 result.face_orig = Array<Vector<int>>(nf);
2743 for (
const CDTFace<T> *f : cdt->faces) {
2744 if (!f->deleted && f != cdt->outer_face) {
2745 SymEdge<T> *se = f->symedge;
2747 SymEdge<T> *se_start = se;
2749 result.face[f_out].append(vert_to_output_map[se->vert->index]);
2751 }
while (se != se_start);
2752 if (cdt_state->need_ids) {
2753 for (
int face : f->input_ids) {
2754 result.face_orig[f_out].append(face);
2769 for (
int i = 0; i < cdt_state->input_vert_num; ++i) {
2770 cdt_state->cdt.add_vert(
input.vert[i]);
2774 template<
typename T>
2777 int nv =
input.vert.size();
2778 int ne =
input.edge.size();
2779 int nf =
input.face.size();
2780 CDT_state<T> cdt_state(nv, ne, nf,
input.epsilon,
input.need_ids);
2820 blender::meshintersect::CDT_input<double> in;
2824 for (
int v = 0;
v <
input->verts_len; ++
v) {
2825 double x =
static_cast<double>(
input->vert_coords[
v][0]);
2826 double y =
static_cast<double>(
input->vert_coords[
v][1]);
2827 in.vert[
v] = blender::meshintersect::vec2<double>(
x,
y);
2829 for (
int e = 0;
e <
input->edges_len; ++
e) {
2830 in.edge[
e] = std::pair<int, int>(
input->edges[
e][0],
input->edges[
e][1]);
2832 for (
int f = 0; f <
input->faces_len; ++f) {
2834 int fstart =
input->faces_start_table[f];
2835 for (
int j = 0; j <
input->faces_len_table[f]; ++j) {
2836 in.face[f][j] =
input->faces[fstart + j];
2839 in.epsilon =
static_cast<double>(
input->epsilon);
2840 in.need_ids =
input->need_ids;
2846 int nv =
output->verts_len = res.vert.size();
2847 int ne =
output->edges_len = res.edge.size();
2848 int nf =
output->faces_len = res.face.size();
2853 if (
input->need_ids) {
2854 for (
int v = 0;
v < nv; ++
v) {
2855 tot_v_orig += res.vert_orig[
v].size();
2857 for (
int e = 0;
e < ne; ++
e) {
2858 tot_e_orig += res.edge_orig[
e].size();
2861 for (
int f = 0; f < nf; ++f) {
2862 if (
input->need_ids) {
2863 tot_f_orig += res.face_orig[f].size();
2865 tot_f_lens += res.face[f].size();
2868 output->vert_coords =
static_cast<decltype(
output-
>vert_coords)>(
2875 if (
input->need_ids) {
2877 output->verts_orig_start_table =
static_cast<int *
>(
2879 output->verts_orig_len_table =
static_cast<int *
>(
2882 output->edges_orig_start_table =
static_cast<int *
>(
2884 output->edges_orig_len_table =
static_cast<int *
>(
2887 output->faces_orig_start_table =
static_cast<int *
>(
2889 output->faces_orig_len_table =
static_cast<int *
>(
2893 output->verts_orig =
nullptr;
2894 output->verts_orig_start_table =
nullptr;
2895 output->verts_orig_len_table =
nullptr;
2896 output->edges_orig =
nullptr;
2897 output->edges_orig_start_table =
nullptr;
2898 output->edges_orig_len_table =
nullptr;
2899 output->faces_orig =
nullptr;
2900 output->faces_orig_start_table =
nullptr;
2901 output->faces_orig_len_table =
nullptr;
2904 int v_orig_index = 0;
2905 for (
int v = 0;
v < nv; ++
v) {
2906 output->vert_coords[
v][0] =
static_cast<float>(res.vert[
v][0]);
2907 output->vert_coords[
v][1] =
static_cast<float>(res.vert[
v][1]);
2908 if (
input->need_ids) {
2909 int this_start = v_orig_index;
2910 output->verts_orig_start_table[
v] = this_start;
2911 for (
int j : res.vert_orig[
v].index_range()) {
2912 output->verts_orig[v_orig_index++] = res.vert_orig[
v][j];
2914 output->verts_orig_len_table[
v] = v_orig_index - this_start;
2917 int e_orig_index = 0;
2918 for (
int e = 0;
e < ne; ++
e) {
2919 output->edges[
e][0] = res.edge[
e].first;
2920 output->edges[
e][1] = res.edge[
e].second;
2921 if (
input->need_ids) {
2922 int this_start = e_orig_index;
2923 output->edges_orig_start_table[
e] = this_start;
2924 for (
int j : res.edge_orig[
e].index_range()) {
2925 output->edges_orig[e_orig_index++] = res.edge_orig[
e][j];
2927 output->edges_orig_len_table[
e] = e_orig_index - this_start;
2930 int f_orig_index = 0;
2932 for (
int f = 0; f < nf; ++f) {
2934 output->faces_start_table[f] = f_index;
2935 int flen = res.face[f].size();
2936 output->faces_len_table[f] = flen;
2937 for (
int j = 0; j < flen; ++j) {
2938 output->faces[f_index++] = res.face[f][j];
2940 if (
input->need_ids) {
2941 int this_start = f_orig_index;
2942 output->faces_orig_start_table[f] = this_start;
2943 for (
int k : res.face_orig[f].index_range()) {
2944 output->faces_orig[f_orig_index++] = res.face_orig[f][k];
2946 output->faces_orig_len_table[f] = f_orig_index - this_start;
2959 if (
result->verts_orig) {
@ CDT_CONSTRAINTS_VALID_BMESH
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES
struct CDT_input CDT_input
void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc)
void void void void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) ATTR_NONNULL(1)
void void void * BLI_linklist_pop(LinkNode **listp) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
MINLINE int max_ii(int a, int b)
Math vector functions needed specifically for mesh intersect and boolean.
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_AS_INT(i)
typedef double(DMatrix)[4][4]
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei height
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei width
_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
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
CrossData & operator=(CrossData &&other) noexcept
CrossData(const CrossData &other)
CrossData(CrossData &&other) noexcept
CrossData & operator=(const CrossData &other)
CrossData(T l, CDTVert< T > *v, SymEdge< T > *i, SymEdge< T > *o)
CDT_state(int input_verts_num, int input_edges_num, int input_faces_num, T epsilon, bool need_ids)
bool vert_touches_face(const CDTVert< T > *v, const CDTFace< T > *f)
bool is_deleted_edge(const CDTEdge< T > *e)
constexpr int inline_crossings_size
bool vert_left_of_symedge(CDTVert< T > *v, SymEdge< T > *se)
void dump_crossings(const Vector< CrossData< T >, inline_crossings_size > &crossings)
static void add_to_input_ids(blender::Set< int > &dst, int input_id)
void add_face_ids(CDT_state< T > *cdt_state, SymEdge< T > *face_symedge, int face_id, int fedge_start, int fedge_end)
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)
void prepare_cdt_for_output(CDT_state< T > *cdt_state, const CDT_output_type output_type)
static int power_of_10_greater_equal_to(int x)
bool is_constrained_edge(const CDTEdge< T > *e)
static int filtered_orient2d(const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c)
bool get_next_crossing_from_vert(CDT_state< T > *cdt_state, CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2)
void detect_holes(CDT_state< T > *cdt_state)
bool is_original_vert(const CDTVert< T > *v, CDT_state< T > *cdt)
void remove_non_constraint_edges(CDT_state< T > *cdt_state)
int filtered_orient2d< double >(const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c)
bool exists_edge(const CDTVert< T > *v1, const CDTVert< T > *v2)
static void re_delaunay_triangulate(CDTArrangement< T > *cdt, SymEdge< T > *se)
void dc_triangulate(CDTArrangement< T > *cdt, Array< SiteInfo< T >> &sites)
SymEdge< T > * find_symedge_with_face(const CDTVert< T > *v, const CDTFace< T > *f)
void get_next_crossing_from_edge(CrossData< T > *cd, CrossData< T > *cd_next, const CDTVert< T > *v2, const T epsilon)
static bool in_line(const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c)
void remove_non_constraint_edges_leave_valid_bmesh(CDT_state< T > *cdt_state)
void BLI_delaunay_2d_cdt_free(::CDT_result *result)
CDT_result< T > get_cdt_output(CDT_state< T > *cdt_state, const CDT_input< T > UNUSED(input), CDT_output_type output_type)
int tri_orient(const SymEdge< T > *t)
void add_edge_constraint(CDT_state< T > *cdt_state, CDTVert< T > *v1, CDTVert< T > *v2, int input_id, LinkNode **r_edges)
bool vert_right_of_symedge(CDTVert< T > *v, SymEdge< T > *se)
int filtered_incircle< double >(const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c, const FatCo< double > &d)
void add_edge_constraints(CDT_state< T > *cdt_state, const CDT_input< T > &input)
bool dc_tri_valid(SymEdge< T > *se, SymEdge< T > *basel, SymEdge< T > *basel_sym)
bool in_line< double >(const FatCo< double > &a, const FatCo< double > &b, const FatCo< double > &c)
void fill_crossdata_for_through_vert(CDTVert< T > *v, SymEdge< T > *cd_out, CrossData< T > *cd, CrossData< T > *cd_next)
void remove_outer_edges_until_constraints(CDT_state< T > *cdt_state)
static bool id_range_in_list(const blender::Set< int > &id_list, int range_start, int range_end)
void remove_faces_in_holes(CDT_state< T > *cdt_state)
void dissolve_symedge(CDT_state< T > *cdt_state, SymEdge< T > *se)
bool site_lexicographic_sort(const SiteInfo< T > &a, const SiteInfo< T > &b)
int add_face_constraints(CDT_state< T > *cdt_state, const CDT_input< T > &input, CDT_output_type output_type)
void find_site_merges(Array< SiteInfo< T >> &sites)
void initial_triangulation(CDTArrangement< T > *cdt)
void add_input_verts(CDT_state< T > *cdt_state, const CDT_input< T > &input)
SymEdge< T > * find_symedge_between_verts(const CDTVert< T > *v1, const CDTVert< T > *v2)
blender::meshintersect::CDT_result< double > delaunay_2d_calc(const CDT_input< double > &input, CDT_output_type output_type)
CDT_result< T > delaunay_calc(const CDT_input< T > &input, CDT_output_type output_type)
static int filtered_incircle(const FatCo< T > &a, const FatCo< T > &b, const FatCo< T > &c, const FatCo< T > &d)
void dc_tri(CDTArrangement< T > *cdt, Array< SiteInfo< T >> &sites, int start, int end, SymEdge< T > **r_le, SymEdge< T > **r_re)
static void add_list_to_input_ids(blender::Set< int > &dst, const blender::Set< int > &src)
bool is_border_edge(const CDTEdge< T > *e, const CDT_state< T > *cdt)
::CDT_result * BLI_delaunay_2d_cdt_calc(const ::CDT_input *input, const CDT_output_type output_type)
SyclQueue void void * src
ccl_global KernelShaderEvalInput ccl_global float * output
ccl_global KernelShaderEvalInput * input
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
void(* MEM_freeN)(void *vmemh)
void *(* MEM_mallocN)(size_t len, const char *str)
ccl_device_inline float2 fabs(const float2 &a)
ccl_device_inline float len_squared(const float3 a)
void interpolate(const Span< T > src, const Span< int > indices, const Span< float > factors, MutableSpan< T > dst)
T distance_squared(const vec_base< T, Size > &a, const vec_base< T, Size > &b)
T dot(const vec_base< T, Size > &a, const vec_base< T, Size > &b)
T distance(const T &a, const T &b)
isect_result< vec_base< T, Size > > isect_seg_seg(const vec_base< T, Size > &v1, const vec_base< T, Size > &v2, const vec_base< T, Size > &v3, const vec_base< T, Size > &v4)
double math_to_double< double >(const double v)
std::string sename(const SymEdge< T > *se)
std::string vertname(const CDTVert< T > *v)
double math_to_double(const T UNUSED(v))
void cdt_draw(const std::string &label, const CDTArrangement< T > &cdt)
SymEdge< T > * sym(const SymEdge< T > *se)
std::string short_se_dump(const SymEdge< T > *se)
static std::string trunc_ptr(const void *p)
SymEdge< T > * prev(const SymEdge< T > *se)
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
double math_abs< double >(const double v)
static void add_edge(const Mesh &mesh, const int old_edge_i, const int v1, const int v2, Vector< int > &new_to_old_edges_map, Vector< MEdge > &new_edges, Vector< int > &loop_edges)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
vec_base< double, 2 > double2
int orient2d(const double2 &a, const double2 &b, const double2 &c)
int incircle(const double2 &a, const double2 &b, const double2 &c, const double2 &d)
std::string to_string(const T &n)
static const pxr::TfToken out("out", pxr::TfToken::Immortal)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
EdgeToSort(EdgeToSort &&other) noexcept
EdgeToSort & operator=(const EdgeToSort &other)
EdgeToSort & operator=(EdgeToSort &&other)
EdgeToSort(const EdgeToSort &other)
CDTEdge< Arith_t > * add_diagonal(SymEdge< Arith_t > *s1, SymEdge< Arith_t > *s2)
Vector< CDTFace< Arith_t > * > faces
CDTVert< Arith_t > * get_vert_resolve_merge(int i)
void reserve(int verts_num, int edges_num, int faces_num)
CDTVert< Arith_t > * add_vert(const vec2< Arith_t > &pt)
void delete_edge(SymEdge< Arith_t > *se)
CDTEdge< Arith_t > * split_edge(SymEdge< Arith_t > *se, Arith_t lambda)
CDTEdge< Arith_t > * add_vert_to_symedge_edge(CDTVert< Arith_t > *v, SymEdge< Arith_t > *se)
Vector< CDTVert< Arith_t > * > verts
CDTFace< Arith_t > * outer_face
Vector< CDTEdge< Arith_t > * > edges
CDTFace< Arith_t > * add_face()
CDTEdge< Arith_t > * connect_separate_parts(SymEdge< Arith_t > *se1, SymEdge< Arith_t > *se2)
CDTEdge< Arith_t > * add_edge(CDTVert< Arith_t > *v1, CDTVert< Arith_t > *v2, CDTFace< Arith_t > *fleft, CDTFace< Arith_t > *fright)
blender::Set< int > input_ids
blender::Set< int > input_ids
SymEdge< Arith_t > * symedge
blender::Set< int > input_ids
CDTVert(const vec2< T > &pt)
FatCo(const vec2< double > &v)
vec2< double > abs_approx
vec2< double > abs_approx
FatCo(const vec2< double > &v)
SymEdge< Arith_t > * next
CDTFace< Arith_t > * face
CDTVert< Arith_t > * vert
CDTEdge< Arith_t > * edge
static const char hex[17]