Blender V5.3
delaunay_2d.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10#include <climits>
11#include <fstream>
12#include <iostream>
13#include <optional>
14#include <sstream>
15
16#include "BLI_array.hh"
17#include "BLI_linklist.hh"
18#include "BLI_map.hh"
19#include "BLI_math_boolean.hh"
21#include "BLI_offset_indices.hh"
22#include "BLI_set.hh"
23#include "BLI_task.hh"
24#include "BLI_vector.hh"
25#include "BLI_vector_set.hh"
26
27#include "BLI_delaunay_2d.hh"
28
29#include "PRF_profile.hh"
30
31namespace blender::meshintersect {
32
33using namespace blender::math;
34
40static constexpr bool USE_POW10_FACE_EDGE_OFFSET_ROUND_UP = false;
41
42/* Throughout this file, template argument T will be an
43 * arithmetic-like type, like float, double, or mpq_class. */
44
45template<typename T> T math_abs(const T v)
46{
47 return (v < 0) ? -v : v;
48}
49
50#ifdef WITH_GMP
51template<> mpq_class math_abs<mpq_class>(const mpq_class v)
52{
53 return abs(v);
54}
55#endif
56
57template<> double math_abs<double>(const double v)
58{
59 return fabs(v);
60}
61
62template<typename T> double math_to_double(const T /*v*/)
63{
64 BLI_assert(false); /* Need implementation for other type. */
65 return 0.0;
66}
67
68#ifdef WITH_GMP
69template<> double math_to_double<mpq_class>(const mpq_class v)
70{
71 return v.get_d();
72}
73#endif
74
75template<> double math_to_double<double>(const double v)
76{
77 return v;
78}
79
91template<typename T> struct CDTVert;
92template<typename T> struct CDTEdge;
93template<typename T> struct CDTFace;
94
95template<typename T> struct SymEdge {
97 SymEdge<T> *next{nullptr};
99 SymEdge<T> *rot{nullptr};
101 CDTVert<T> *vert{nullptr};
103 CDTEdge<T> *edge{nullptr};
105 CDTFace<T> *face{nullptr};
106
107 SymEdge() = default;
108};
109
113template<typename T> inline SymEdge<T> *sym(const SymEdge<T> *se)
114{
115 return se->next->rot;
116}
117
119template<typename T> inline SymEdge<T> *prev(const SymEdge<T> *se)
120{
121 return se->rot->next->rot;
122}
123
125
126template<typename T> struct FatCo {
130
132#ifdef WITH_GMP
133 FatCo(const mpq2 &v);
134#endif
135 FatCo(const double2 &v);
136};
137
138#ifdef WITH_GMP
139template<> struct FatCo<mpq_class> {
140 mpq2 exact;
143
144 FatCo() : exact(mpq2(0, 0)), approx(double2(0, 0)), abs_approx(double2(0, 0)) {}
145
146 FatCo(const mpq2 &v)
147 {
148 exact = v;
149 approx = double2(v.x.get_d(), v.y.get_d());
151 }
152
153 FatCo(const double2 &v)
154 {
155 exact = mpq2(v.x, v.y);
156 approx = v;
158 }
159};
160#endif
161
162template<> struct FatCo<double> {
166
167 FatCo() : exact(double2(0, 0)), approx(double2(0, 0)), abs_approx(double2(0, 0)) {}
168
169#ifdef WITH_GMP
170 FatCo(const mpq2 &v)
171 {
172 exact = double2(v.x.get_d(), v.y.get_d());
173 approx = exact;
175 }
176#endif
177
179 {
180 exact = v;
181 approx = v;
183 }
184};
185
186template<typename T> std::ostream &operator<<(std::ostream &stream, const FatCo<T> &co)
187{
188 stream << "(" << co.approx.x << ", " << co.approx.y << ")";
189 return stream;
190}
191
192template<typename T> struct CDTVert {
203 int index{-1};
210
211 CDTVert() = default;
212 explicit CDTVert(const VecBase<T, 2> &pt);
213};
214
215template<typename T> struct CDTEdge {
224
225 CDTEdge() = default;
226};
227
228template<typename T> struct CDTFace {
240 bool deleted{false};
242 bool hole{false};
243
244 CDTFace() = default;
245};
246
247template<typename T> struct CDTArrangement {
248 /* The arrangement owns the memory pointed to by the pointers in these vectors.
249 * They are pointers instead of actual structures because these vectors may be resized and
250 * other elements refer to the elements by pointer. */
251
260
261 CDTArrangement() = default;
263
268 void reserve(int verts_num, int edges_num, int faces_num);
269
275
283
289
292
300
306
313 T lambda,
314 Map<CDTEdge<T> *, int> *edge_winding_map,
315 Map<CDTEdge<T> *, int> *polygon_boundary_count_map);
316
322 void delete_edge(SymEdge<T> *se);
323
329 {
330 CDTVert<T> *v = this->verts[i];
331 if (v->merge_to_index != -1) {
332 v = this->verts[v->merge_to_index];
333 }
334 return v;
335 }
336};
337
338template<typename T> class CDT_state {
339 public:
369
393
394 explicit CDT_state(int input_verts_num,
395 int input_edges_num,
396 int input_faces_num,
397 T epsilon,
399};
400
402{
403 for (int i : this->verts.index_range()) {
404 CDTVert<T> *v = this->verts[i];
405 v->input_ids.clear();
406 delete v;
407 this->verts[i] = nullptr;
408 }
409 for (int i : this->edges.index_range()) {
410 CDTEdge<T> *e = this->edges[i];
411 e->input_ids.clear();
412 delete e;
413 this->edges[i] = nullptr;
414 }
415 for (int i : this->faces.index_range()) {
416 CDTFace<T> *f = this->faces[i];
417 f->input_ids.clear();
418 delete f;
419 this->faces[i] = nullptr;
420 }
421}
422
426static inline bool output_uses_evenodd_holes(const CDT_output_type output_type)
427{
429}
430
435static inline bool output_uses_nonzero_holes(const CDT_output_type output_type)
436{
437 return ELEM(
439}
440
441#define DEBUG_CDT
442#ifdef DEBUG_CDT
443/* Some functions to aid in debugging. */
444template<typename T> std::string vertname(const CDTVert<T> *v)
445{
446 std::stringstream ss;
447 ss << "[" << v->index << "]";
448 return ss.str();
449}
450
451/* Abbreviated pointer value is easier to read in dumps. */
452static std::string trunc_ptr(const void *p)
453{
454 constexpr int TRUNC_PTR_MASK = 0xFFFF;
455 std::stringstream ss;
456 ss << std::hex << (POINTER_AS_INT(p) & TRUNC_PTR_MASK);
457 return ss.str();
458}
459
460template<typename T> std::string sename(const SymEdge<T> *se)
461{
462 std::stringstream ss;
463 ss << "{" << trunc_ptr(se) << "}";
464 return ss.str();
465}
466
467template<typename T> std::ostream &operator<<(std::ostream &os, const SymEdge<T> &se)
468{
469 if (se.next) {
470 os << vertname(se.vert) << "(" << se.vert->co << "->" << se.next->vert->co << ")"
471 << vertname(se.next->vert);
472 }
473 else {
474 os << vertname(se.vert) << "(" << se.vert->co << "->null)";
475 }
476 return os;
477}
478
479template<typename T> std::ostream &operator<<(std::ostream &os, const SymEdge<T> *se)
480{
481 os << *se;
482 return os;
483}
484
485template<typename T> std::string short_se_dump(const SymEdge<T> *se)
486{
487 if (se == nullptr) {
488 return std::string("null");
489 }
490 return vertname(se->vert) +
491 (se->next == nullptr ? std::string("[null]") : vertname(se->next->vert));
492}
493
494template<typename T> std::ostream &operator<<(std::ostream &os, const CDT_state<T> &cdt_state)
495{
496 os << "\nCDT\n\nVERTS\n";
497 for (const CDTVert<T> *v : cdt_state.cdt.verts) {
498 os << vertname(v) << " " << trunc_ptr(v) << ": " << v->co
499 << " symedge=" << trunc_ptr(v->symedge);
500 if (v->merge_to_index == -1) {
501 os << "\n";
502 }
503 else {
504 os << " merge to " << vertname(cdt_state.cdt.verts[v->merge_to_index]) << "\n";
505 }
506 const SymEdge<T> *se = v->symedge;
507 int count = 0;
508 constexpr int print_count_limit = 25;
509 if (se) {
510 os << " edges out:\n";
511 do {
512 if (se->next == nullptr) {
513 os << " [null] next/rot symedge, se=" << trunc_ptr(se) << "\n";
514 break;
515 }
516 if (se->next->next == nullptr) {
517 os << " [null] next-next/rot symedge, se=" << trunc_ptr(se) << "\n";
518 break;
519 }
520 const CDTVert<T> *vother = sym(se)->vert;
521 os << " " << vertname(vother) << "(e=" << trunc_ptr(se->edge)
522 << ", se=" << trunc_ptr(se) << ")\n";
523 se = se->rot;
524 count++;
525 } while (se != v->symedge && count < print_count_limit);
526 os << "\n";
527 }
528 }
529 os << "\nEDGES\n";
530 for (const CDTEdge<T> *e : cdt_state.cdt.edges) {
531 if (e->symedges[0].next == nullptr) {
532 continue;
533 }
534 os << trunc_ptr(&e) << ":\n";
535 for (int i = 0; i < 2; ++i) {
536 const SymEdge<T> *se = &e->symedges[i];
537 os << " se[" << i << "] @" << trunc_ptr(se) << " next=" << trunc_ptr(se->next)
538 << ", rot=" << trunc_ptr(se->rot) << ", vert=" << trunc_ptr(se->vert) << " "
539 << vertname(se->vert) << " " << se->vert->co << ", edge=" << trunc_ptr(se->edge)
540 << ", face=" << trunc_ptr(se->face) << "\n";
541 }
542 }
543 os << "\nFACES\n";
544 os << "outer_face=" << trunc_ptr(cdt_state.cdt.outer_face) << "\n";
545 /* Only after prepare_output do faces have non-null symedges. */
546 if (cdt_state.cdt.outer_face->symedge != nullptr) {
547 for (const CDTFace<T> *f : cdt_state.cdt.faces) {
548 if (!f->deleted) {
549 os << trunc_ptr(f) << " symedge=" << trunc_ptr(f->symedge) << "\n";
550 }
551 }
552 }
553 return os;
554}
555
556template<typename T> void cdt_draw(const std::string &label, const CDTArrangement<T> &cdt)
557{
558 static bool append = false; /* Will be set to true after first call. */
559
560/* Would like to use #BKE_tempdir_base() here, but that brings in dependence on kernel library.
561 * This is just for developer debugging anyway, and should never be called in production Blender.
562 */
563# ifdef _WIN32
564 const char *drawfile = "./cdt_debug_draw.html";
565# else
566 const char *drawfile = "/tmp/cdt_debug_draw.html";
567# endif
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;
577
578 if (cdt.verts.is_empty()) {
579 return;
580 }
581 double2 vmin(std::numeric_limits<double>::max());
582 double2 vmax(std::numeric_limits<double>::lowest());
583 for (const CDTVert<T> *v : cdt.verts) {
584 math::min_max(v->co.approx, vmin, vmax);
585 }
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;
591
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);
600 }
601 double scale = view_width / width;
602
603# define SX(x) (((x) - minx) * scale)
604# define SY(y) ((maxy - (y)) * scale)
605
606 std::ofstream f;
607 if (append) {
608 f.open(drawfile, std::ios_base::app);
609 }
610 else {
611 f.open(drawfile);
612 }
613 if (!f) {
614 std::cout << "Could not open file " << drawfile << "\n";
615 return;
616 }
617
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";
624
625 for (const CDTEdge<T> *e : cdt.edges) {
626 if (e->symedges[0].next == nullptr) {
627 continue;
628 }
629 const CDTVert<T> *u = e->symedges[0].vert;
630 const CDTVert<T> *v = e->symedges[1].vert;
631 const double2 &uco = u->co.approx;
632 const double2 &vco = v->co.approx;
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";
637 f << " <title>" << vertname(u) << vertname(v) << "</title>\n";
638 f << "</line>\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">)";
642 f << vertname(u) << vertname(v) << sename(&e->symedges[0]) << sename(&e->symedges[1])
643 << "</text>\n";
644 }
645 }
646
647 int i = 0;
648 for (const CDTVert<T> *v : cdt.verts) {
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";
652 f << "</circle>\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";
656 }
657 ++i;
658 }
659
660 if (draw_face_labels) {
661 for (const CDTFace<T> *face : cdt.faces) {
662 if (!face->deleted) {
663 /* Since may not have prepared output yet, need a slow find of a SymEdge for this face. */
664 const SymEdge<T> *se_face_start = nullptr;
665 for (const CDTEdge<T> *e : cdt.edges) {
666 if (e->symedges[0].face == face) {
667 se_face_start = &e->symedges[0];
668 break;
669 }
670 if (e->symedges[1].face == face) {
671 se_face_start = &e->symedges[1];
672 }
673 }
674 if (se_face_start != nullptr) {
675 /* Find center of face. */
676 int face_nverts = 0;
677 double2 cen(0.0, 0.0);
678 if (face == cdt.outer_face) {
679 cen.x = minx;
680 cen.y = miny;
681 }
682 else {
683 const SymEdge<T> *se = se_face_start;
684 do {
685 if (se->face == face) {
686 cen = cen + se->vert->co.approx;
687 face_nverts++;
688 }
689 } while ((se = se->next) != se_face_start);
690 if (face_nverts > 0) {
691 cen = cen / double(face_nverts);
692 }
693 }
694 f << "<text x=\"" << SX(cen[0]) << "\" y=\"" << SY(cen[1]) << "\""
695 << " font-size=\"small\">[";
696 f << trunc_ptr(face);
697 if (face->input_ids.size() > 0) {
698 for (uint32_t id : face->input_ids) {
699 f << " " << id;
700 }
701 }
702 f << "]</text>\n";
703 }
704 }
705 }
706 }
707
708 append = true;
709# undef SX
710# undef SY
711}
712#endif
713
718template<typename T>
719static int filtered_orient2d(const FatCo<T> &a, const FatCo<T> &b, const FatCo<T> &c);
720
721#ifdef WITH_GMP
722template<>
724 const FatCo<mpq_class> &b,
725 const FatCo<mpq_class> &c)
726{
727 double det = (a.approx[0] - c.approx[0]) * (b.approx[1] - c.approx[1]) -
728 (a.approx[1] - c.approx[1]) * (b.approx[0] - c.approx[0]);
729 double supremum = (a.abs_approx[0] + c.abs_approx[0]) * (b.abs_approx[1] + c.abs_approx[1]) +
730 (a.abs_approx[1] + c.abs_approx[1]) * (b.abs_approx[0] + c.abs_approx[0]);
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;
735 }
736 return orient2d(a.exact, b.exact, c.exact);
737}
738#endif
739
740template<>
742 const FatCo<double> &b,
743 const FatCo<double> &c)
744{
745 return orient2d(a.approx, b.approx, c.approx);
746}
747
751template<typename T>
752static int filtered_incircle(const FatCo<T> &a,
753 const FatCo<T> &b,
754 const FatCo<T> &c,
755 const FatCo<T> &d);
756
757#ifdef WITH_GMP
758template<>
760 const FatCo<mpq_class> &b,
761 const FatCo<mpq_class> &c,
762 const FatCo<mpq_class> &d)
763{
764 double adx = a.approx[0] - d.approx[0];
765 double bdx = b.approx[0] - d.approx[0];
766 double cdx = c.approx[0] - d.approx[0];
767 double ady = a.approx[1] - d.approx[1];
768 double bdy = b.approx[1] - d.approx[1];
769 double cdy = c.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);
780
781 double sup_adx = a.abs_approx[0] + d.abs_approx[0]; /* index 2. */
782 double sup_bdx = b.abs_approx[0] + d.abs_approx[0];
783 double sup_cdx = c.abs_approx[0] + d.abs_approx[0];
784 double sup_ady = a.abs_approx[1] + d.abs_approx[1];
785 double sup_bdy = b.abs_approx[1] + d.abs_approx[1];
786 double sup_cdy = c.abs_approx[1] + d.abs_approx[1];
787 double sup_bdxcdy = sup_bdx * sup_cdy; /* index 5. */
788 double sup_cdxbdy = sup_cdx * sup_bdy;
789 double sup_alift = sup_adx * sup_adx + sup_ady * sup_ady; /* index 6. */
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);
798 int index = 14;
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);
802 }
803 return incircle(a.exact, b.exact, c.exact, d.exact);
804}
805#endif
806
807template<>
809 const FatCo<double> &b,
810 const FatCo<double> &c,
811 const FatCo<double> &d)
812{
813 return incircle(a.approx, b.approx, c.approx, d.approx);
814}
815
822template<typename T> static bool in_line(const FatCo<T> &a, const FatCo<T> &b, const FatCo<T> &c);
823
824#ifdef WITH_GMP
825template<>
827 const FatCo<mpq_class> &b,
828 const FatCo<mpq_class> &c)
829{
830 double2 ab = b.approx - a.approx;
831 double2 bc = c.approx - b.approx;
832 double2 ac = c.approx - a.approx;
833 double2 supremum_ab = b.abs_approx + a.abs_approx;
834 double2 supremum_bc = c.abs_approx + b.abs_approx;
835 double2 supremum_ac = c.abs_approx + a.abs_approx;
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) {
841 return false;
842 }
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) {
847 return false;
848 }
849 mpq2 exact_ab = b.exact - a.exact;
850 mpq2 exact_ac = c.exact - a.exact;
851 if (dot(exact_ab, exact_ac) < 0) {
852 return false;
853 }
854 mpq2 exact_bc = c.exact - b.exact;
855 return dot(exact_bc, exact_ac) >= 0;
856}
857#endif
858
859template<>
861{
862 double2 ab = b.approx - a.approx;
863 double2 ac = c.approx - a.approx;
864 if (dot(ab, ac) < 0) {
865 return false;
866 }
867 double2 bc = c.approx - b.approx;
868 return dot(bc, ac) >= 0;
869}
870
872{
873 this->co.exact = pt;
874 this->co.approx = pt;
875 this->co.abs_approx = pt; /* Not used, so doesn't matter. */
876 this->symedge = nullptr;
877 this->index = -1;
878 this->merge_to_index = -1;
879 this->visit_index = 0;
880}
881
882#ifdef WITH_GMP
883template<> CDTVert<mpq_class>::CDTVert(const mpq2 &pt)
884{
885 this->co.exact = 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;
889 this->index = -1;
890 this->merge_to_index = -1;
891 this->visit_index = 0;
892}
893#endif
894
896{
897 CDTVert<T> *v = new CDTVert<T>(pt);
898 int index = this->verts.append_and_get_index(v);
899 v->index = index;
900 return v;
901}
902
903template<typename T>
905 CDTVert<T> *v2,
906 CDTFace<T> *fleft,
907 CDTFace<T> *fright)
908{
909 CDTEdge<T> *e = new CDTEdge<T>();
910 this->edges.append(e);
911 SymEdge<T> *se = &e->symedges[0];
912 SymEdge<T> *sesym = &e->symedges[1];
913 se->edge = sesym->edge = e;
914 se->face = fleft;
915 sesym->face = fright;
916 se->vert = v1;
917 if (v1->symedge == nullptr) {
918 v1->symedge = se;
919 }
920 sesym->vert = v2;
921 if (v2->symedge == nullptr) {
922 v2->symedge = sesym;
923 }
924 se->next = sesym->next = se->rot = sesym->rot = nullptr;
925 return e;
926}
927
929{
930 CDTFace<T> *f = new CDTFace<T>();
931 this->faces.append(f);
932 return f;
933}
934
935template<typename T> void CDTArrangement<T>::reserve(int verts_num, int edges_num, int faces_num)
936{
937 /* These reserves are just guesses; OK if they aren't exactly right since vectors will resize. */
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);
941}
942
943template<typename T>
944CDT_state<T>::CDT_state(int input_verts_num,
945 int input_edges_num,
946 int input_faces_num,
947 T epsilon,
949{
950 this->input_vert_num = input_verts_num;
951 this->cdt.reserve(input_verts_num, input_edges_num, input_faces_num);
952 this->cdt.outer_face = this->cdt.add_face();
953 this->epsilon = epsilon;
954 this->needed_ids = needed_ids;
955 this->visit_count = 0;
956 this->edge_winding_map = nullptr;
957 this->polygon_boundary_count_map = nullptr;
958}
959
960/* Is any id in (range_start, range_start+1, ... , range_end) in id_list? */
961static bool id_range_in_list(const VectorSet<uint32_t> &id_list,
962 uint32_t range_start,
963 uint32_t range_end)
964{
966 for (uint32_t id : id_list) {
967 if (id >= range_start && id <= range_end) {
968 return true;
969 }
970 }
971 return false;
972}
973
975{
977 dst.add(input_id);
978}
979
981{
982 dst.add_multiple(src.as_span());
983}
984
985template<typename T> inline bool is_border_edge(const CDTEdge<T> *e, const CDT_state<T> *cdt)
986{
987 return e->symedges[0].face == cdt->outer_face || e->symedges[1].face == cdt->outer_face;
988}
989
990template<typename T> inline bool is_constrained_edge(const CDTEdge<T> *e)
991{
992 return e->input_ids.size() > 0;
993}
994
995template<typename T> inline bool is_deleted_edge(const CDTEdge<T> *e)
996{
997 return e->symedges[0].next == nullptr;
998}
999
1000template<typename T> inline bool is_original_vert(const CDTVert<T> *v, CDT_state<T> *cdt)
1001{
1002 return (v->index < cdt->input_vert_num);
1003}
1004
1008template<typename T>
1010{
1011 SymEdge<T> *t = v1->symedge;
1012 SymEdge<T> *tstart = t;
1013 do {
1014 if (t->next->vert == v2) {
1015 return t;
1016 }
1017 } while ((t = t->rot) != tstart);
1018 return nullptr;
1019}
1020
1024template<typename T> SymEdge<T> *find_symedge_with_face(const CDTVert<T> *v, const CDTFace<T> *f)
1025{
1026 SymEdge<T> *t = v->symedge;
1027 SymEdge<T> *tstart = t;
1028 do {
1029 if (t->face == f) {
1030 return t;
1031 }
1032 } while ((t = t->rot) != tstart);
1033 return nullptr;
1034}
1035
1039template<typename T> inline bool exists_edge(const CDTVert<T> *v1, const CDTVert<T> *v2)
1040{
1041 return find_symedge_between_verts(v1, v2) != nullptr;
1042}
1043
1047template<typename T> bool vert_touches_face(const CDTVert<T> *v, const CDTFace<T> *f)
1048{
1049 SymEdge<T> *se = v->symedge;
1050 do {
1051 if (se->face == f) {
1052 return true;
1053 }
1054 } while ((se = se->rot) != v->symedge);
1055 return false;
1056}
1057
1067{
1068 CDTFace<T> *fold = s1->face;
1069 CDTFace<T> *fnew = this->add_face();
1070 SymEdge<T> *s1prev = prev(s1);
1071 SymEdge<T> *s1prevsym = sym(s1prev);
1072 SymEdge<T> *s2prev = prev(s2);
1073 SymEdge<T> *s2prevsym = sym(s2prev);
1074 CDTEdge<T> *ediag = this->add_edge(s1->vert, s2->vert, fnew, fold);
1075 SymEdge<T> *sdiag = &ediag->symedges[0];
1076 SymEdge<T> *sdiagsym = &ediag->symedges[1];
1077 sdiag->next = s2;
1078 sdiagsym->next = s1;
1079 s2prev->next = sdiagsym;
1080 s1prev->next = sdiag;
1081 s1->rot = sdiag;
1082 sdiag->rot = s1prevsym;
1083 s2->rot = sdiagsym;
1084 sdiagsym->rot = s2prevsym;
1085 for (SymEdge<T> *se = s2; se != sdiag; se = se->next) {
1086 se->face = fnew;
1087 }
1089 return ediag;
1090}
1091
1092template<typename T>
1094{
1095 SymEdge<T> *se_rot = se->rot;
1096 SymEdge<T> *se_rotsym = sym(se_rot);
1097 /* TODO: check: I think last arg in next should be sym(se)->face. */
1098 CDTEdge<T> *e = this->add_edge(v, se->vert, se->face, se->face);
1099 SymEdge<T> *new_se = &e->symedges[0];
1100 SymEdge<T> *new_se_sym = &e->symedges[1];
1101 new_se->next = se;
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;
1107 return e;
1108}
1109
1115template<typename T>
1117{
1118 BLI_assert(se1->face == this->outer_face && se2->face == this->outer_face);
1119 SymEdge<T> *se1_rot = se1->rot;
1120 SymEdge<T> *se1_rotsym = sym(se1_rot);
1121 SymEdge<T> *se2_rot = se2->rot;
1122 SymEdge<T> *se2_rotsym = sym(se2_rot);
1123 CDTEdge<T> *e = this->add_edge(se1->vert, se2->vert, this->outer_face, this->outer_face);
1124 SymEdge<T> *new_se = &e->symedges[0];
1125 SymEdge<T> *new_se_sym = &e->symedges[1];
1126 new_se->next = se2;
1127 new_se_sym->next = se1;
1128 new_se->rot = se1_rot;
1129 new_se_sym->rot = se2_rot;
1130 se1->rot = new_se;
1131 se2->rot = new_se_sym;
1132 se1_rotsym->next = new_se;
1133 se2_rotsym->next = new_se_sym;
1134 return e;
1135}
1136
1145template<typename T>
1147 T lambda,
1148 Map<CDTEdge<T> *, int> *edge_winding_map,
1149 Map<CDTEdge<T> *, int> *polygon_boundary_count_map)
1150{
1151 /* Split e at lambda. */
1152 const VecBase<T, 2> *a = &se->vert->co.exact;
1153 const VecBase<T, 2> *b = &se->next->vert->co.exact;
1154 SymEdge<T> *sesym = sym(se);
1155 SymEdge<T> *sesymprev = prev(sesym);
1156 SymEdge<T> *sesymprevsym = sym(sesymprev);
1157 SymEdge<T> *senext = se->next;
1158 CDTVert<T> *v = this->add_vert(interpolate(*a, *b, lambda));
1159 /* Fresh allocation: not in either side map, so `add()` below is safe. */
1160 CDTEdge<T> *e = this->add_edge(v, se->next->vert, se->face, sesym->face);
1161 BLI_assert(this->edges.last() == e);
1162 sesym->vert = v;
1163 SymEdge<T> *newse = &e->symedges[0];
1164 SymEdge<T> *newsesym = &e->symedges[1];
1165 se->next = newse;
1166 newsesym->next = sesym;
1167 newse->next = senext;
1168 newse->rot = sesym;
1169 sesym->rot = newse;
1170 senext->rot = newsesym;
1171 newsesym->rot = sesymprevsym;
1172 sesymprev->next = newsesym;
1173 if (newsesym->vert->symedge == sesym) {
1174 newsesym->vert->symedge = newsesym;
1175 }
1176 add_list_to_input_ids(e->input_ids, se->edge->input_ids);
1177
1178 if (polygon_boundary_count_map) {
1179 /* Both halves of a split edge inherit the polygon-boundary count:
1180 * each input face boundary that crossed the original edge still crosses
1181 * both halves after the split. */
1182 const int count = polygon_boundary_count_map->lookup_default(se->edge, 0);
1183 if (count != 0) {
1184 polygon_boundary_count_map->add(e, count);
1185 }
1186 }
1187
1188 if (edge_winding_map) {
1189 /* Propagate winding from original edge to new edge.
1190 *
1191 * The new edge `e` goes from split point to `se->next->vert`.
1192 * When split is called via `symedges[0]`,
1193 * this matches the original edge direction (A->B becomes A->M + M->B).
1194 * When called via `symedges[1]`,
1195 * the new edge opposes it (A->B becomes M->B + M->A), so we negate the winding.
1196 *
1197 * This occurs when the crossing traversal encounters an edge from the
1198 * opposite face side from where winding was originally assigned. */
1199 int winding = edge_winding_map->lookup_default(se->edge, 0);
1200 if (winding != 0) {
1201 if (se == &se->edge->symedges[1]) {
1202 winding = -winding;
1203 }
1204 edge_winding_map->add(e, winding);
1205 }
1206 }
1207 return e;
1208}
1209
1231template<typename T> void CDTArrangement<T>::delete_edge(SymEdge<T> *se)
1232{
1233 SymEdge<T> *sesym = sym(se);
1234 CDTVert<T> *v1 = se->vert;
1235 CDTVert<T> *v2 = sesym->vert;
1236 CDTFace<T> *aface = se->face;
1237 CDTFace<T> *bface = sesym->face;
1238 SymEdge<T> *f = se->next;
1239 SymEdge<T> *h = prev(se);
1240 SymEdge<T> *i = sesym->next;
1241 SymEdge<T> *j = prev(sesym);
1242 SymEdge<T> *jsym = sym(j);
1243 SymEdge<T> *hsym = sym(h);
1244 bool v1_isolated = (i == se);
1245 bool v2_isolated = (f == sesym);
1246
1247 if (!v1_isolated) {
1248 h->next = i;
1249 i->rot = hsym;
1250 }
1251 if (!v2_isolated) {
1252 j->next = f;
1253 f->rot = jsym;
1254 }
1255 if (!v1_isolated && !v2_isolated && aface != bface) {
1256 for (SymEdge<T> *k = i; k != f; k = k->next) {
1257 k->face = aface;
1258 }
1259 }
1260
1261 /* If e was representative symedge for v1 or v2, fix that. */
1262 if (v1_isolated) {
1263 v1->symedge = nullptr;
1264 }
1265 else if (v1->symedge == se) {
1266 v1->symedge = i;
1267 }
1268 if (v2_isolated) {
1269 v2->symedge = nullptr;
1270 }
1271 else if (v2->symedge == sesym) {
1272 v2->symedge = f;
1273 }
1274
1275 /* Mark #SymEdge as deleted by setting all its pointers to null. */
1276 se->next = se->rot = nullptr;
1277 sesym->next = sesym->rot = nullptr;
1278 if (!v1_isolated && !v2_isolated && aface != bface) {
1279 bface->deleted = true;
1280 if (this->outer_face == bface) {
1281 this->outer_face = aface;
1282 }
1283 }
1284 else if (v1_isolated && v2_isolated) {
1285 /* `se` was `aface`'s last edge, leaving an empty boundary with no loop left to walk.
1286 * A `symedge` left pointing at the deleted edge crashed when walking the boundary
1287 * to generate output, see: #160787.
1288 *
1289 * Mark the face deleted so callers checking `deleted` (hole detection, output) skip it.
1290 * The outer face is the exception: it's dereferenced without null checks so it must never
1291 * be deleted, only clear its `symedge` (matching the handling in #dissolve_symedge). */
1292 BLI_assert(aface == bface);
1293 if (aface == this->outer_face) {
1294 if (ELEM(this->outer_face->symedge, se, sesym)) {
1295 this->outer_face->symedge = nullptr;
1296 }
1297 }
1298 else {
1299 aface->deleted = true;
1300 }
1301 }
1302}
1303
1304template<typename T> class SiteInfo {
1305 public:
1308};
1309
1313template<typename T> bool site_lexicographic_sort(const SiteInfo<T> &a, const SiteInfo<T> &b)
1314{
1315 const VecBase<T, 2> &co_a = a.v->co.exact;
1316 const VecBase<T, 2> &co_b = b.v->co.exact;
1317 if (co_a[0] < co_b[0]) {
1318 return true;
1319 }
1320 if (co_a[0] > co_b[0]) {
1321 return false;
1322 }
1323 if (co_a[1] < co_b[1]) {
1324 return true;
1325 }
1326 if (co_a[1] > co_b[1]) {
1327 return false;
1328 }
1329 return a.orig_index < b.orig_index;
1330}
1331
1337template<typename T> void find_site_merges(Array<SiteInfo<T>> &sites)
1338{
1339 int n = sites.size();
1340 for (int i = 0; i < n - 1; ++i) {
1341 int j = i + 1;
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;
1344 ++j;
1345 }
1346 if (j - i > 1) {
1347 i = j - 1; /* j-1 because loop head will add another 1. */
1348 }
1349 }
1350}
1351
1352template<typename T> inline bool vert_left_of_symedge(CDTVert<T> *v, SymEdge<T> *se)
1353{
1354 return filtered_orient2d(v->co, se->vert->co, se->next->vert->co) > 0;
1355}
1356
1357template<typename T> inline bool vert_right_of_symedge(CDTVert<T> *v, SymEdge<T> *se)
1358{
1359 return filtered_orient2d(v->co, se->next->vert->co, se->vert->co) > 0;
1360}
1361
1362/* Is se above basel? */
1363template<typename T>
1364inline bool dc_tri_valid(SymEdge<T> *se, SymEdge<T> *basel, SymEdge<T> *basel_sym)
1365{
1366 return filtered_orient2d(se->next->vert->co, basel_sym->vert->co, basel->vert->co) > 0;
1367}
1368
1375template<typename T>
1377 Array<SiteInfo<T>> &sites,
1378 int start,
1379 int end,
1380 SymEdge<T> **r_le,
1381 SymEdge<T> **r_re)
1382{
1384 constexpr int dbg_level = 0;
1385 if (dbg_level > 0) {
1386 std::cout << "DC_TRI start=" << start << " end=" << end << "\n";
1387 }
1388 int n = end - start;
1389 if (n <= 1) {
1390 *r_le = nullptr;
1391 *r_re = nullptr;
1392 return;
1393 }
1394
1395 /* Base case: if n <= 3, triangulate directly. */
1396 if (n <= 3) {
1397 CDTVert<T> *v1 = sites[start].v;
1398 CDTVert<T> *v2 = sites[start + 1].v;
1399 CDTEdge<T> *ea = cdt->add_edge(v1, v2, cdt->outer_face, cdt->outer_face);
1400 ea->symedges[0].next = &ea->symedges[1];
1401 ea->symedges[1].next = &ea->symedges[0];
1402 ea->symedges[0].rot = &ea->symedges[0];
1403 ea->symedges[1].rot = &ea->symedges[1];
1404 if (n == 2) {
1405 *r_le = &ea->symedges[0];
1406 *r_re = &ea->symedges[1];
1407 return;
1408 }
1409 CDTVert<T> *v3 = sites[start + 2].v;
1410 CDTEdge<T> *eb = cdt->add_vert_to_symedge_edge(v3, &ea->symedges[1]);
1411 int orient = filtered_orient2d(v1->co, v2->co, v3->co);
1412 if (orient > 0) {
1413 cdt->add_diagonal(&eb->symedges[0], &ea->symedges[0]);
1414 *r_le = &ea->symedges[0];
1415 *r_re = &eb->symedges[0];
1416 }
1417 else if (orient < 0) {
1418 cdt->add_diagonal(&ea->symedges[0], &eb->symedges[0]);
1419 *r_le = ea->symedges[0].rot;
1420 *r_re = eb->symedges[0].rot;
1421 }
1422 else {
1423 /* Collinear points. Just return a line. */
1424 *r_le = &ea->symedges[0];
1425 *r_re = &eb->symedges[0];
1426 }
1427 return;
1428 }
1429 /* Recursive case. Do left (L) and right (R) halves separately, then join. */
1430 int n2 = n / 2;
1431 BLI_assert(n2 >= 2 && end - (start + n2) >= 2);
1432 SymEdge<T> *ldo;
1433 SymEdge<T> *ldi;
1434 SymEdge<T> *rdi;
1435 SymEdge<T> *rdo;
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) + ")";
1447 cdt_draw(lab, *cdt);
1448 }
1449 }
1450 /* Find lower common tangent of L and R. */
1451 for (;;) {
1452 if (vert_left_of_symedge(rdi->vert, ldi)) {
1453 ldi = ldi->next;
1454 }
1455 else if (vert_right_of_symedge(ldi->vert, rdi)) {
1456 rdi = sym(rdi)->rot; /* Previous edge to rdi with same right face. */
1457 }
1458 else {
1459 break;
1460 }
1461 }
1462 if (dbg_level > 0) {
1463 std::cout << "common lower tangent in between\n"
1464 << "rdi " << rdi << "\n"
1465 << "ldi" << ldi << "\n";
1466 }
1467
1468 CDTEdge<T> *ebasel = cdt->connect_separate_parts(sym(rdi)->next, ldi);
1469 SymEdge<T> *basel = &ebasel->symedges[0];
1470 SymEdge<T> *basel_sym = &ebasel->symedges[1];
1471 if (dbg_level > 1) {
1472 std::cout << "basel " << basel;
1473 cdt_draw("after basel made", *cdt);
1474 }
1475 if (ldi->vert == ldo->vert) {
1476 ldo = basel_sym;
1477 }
1478 if (rdi->vert == rdo->vert) {
1479 rdo = basel;
1480 }
1481
1482 /* Merge loop. */
1483 for (;;) {
1484 /* Locate the first point lcand->next->vert encountered by rising bubble,
1485 * and delete L edges out of basel->next->vert that fail the circle test. */
1486 SymEdge<T> *lcand = basel_sym->rot;
1487 SymEdge<T> *rcand = basel_sym->next;
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";
1493 }
1494 if (dc_tri_valid(lcand, basel, basel_sym)) {
1495 if (dbg_level > 1) {
1496 std::cout << "found valid lcand\n";
1497 std::cout << " lcand" << lcand << "\n";
1498 }
1499 while (filtered_incircle(basel_sym->vert->co,
1500 basel->vert->co,
1501 lcand->next->vert->co,
1502 lcand->rot->next->vert->co) > 0.0)
1503 {
1504 if (dbg_level > 1) {
1505 std::cout << "incircle says to remove lcand\n";
1506 std::cout << " lcand" << lcand << "\n";
1507 }
1508 SymEdge<T> *t = lcand->rot;
1509 cdt->delete_edge(sym(lcand));
1510 lcand = t;
1511 }
1512 }
1513 /* Symmetrically, locate first R point to be hit and delete R edges. */
1514 if (dc_tri_valid(rcand, basel, basel_sym)) {
1515 if (dbg_level > 1) {
1516 std::cout << "found valid rcand\n";
1517 std::cout << " rcand" << rcand << "\n";
1518 }
1519 while (filtered_incircle(basel_sym->vert->co,
1520 basel->vert->co,
1521 rcand->next->vert->co,
1522 sym(rcand)->next->next->vert->co) > 0.0)
1523 {
1524 if (dbg_level > 0) {
1525 std::cout << "incircle says to remove rcand\n";
1526 std::cout << " rcand" << rcand << "\n";
1527 }
1528 SymEdge<T> *t = sym(rcand)->next;
1529 cdt->delete_edge(rcand);
1530 rcand = t;
1531 }
1532 }
1533 /* If both lcand and rcand are invalid, then basel is the common upper tangent. */
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";
1541 }
1542 if (!valid_lcand && !valid_rcand) {
1543 break;
1544 }
1545 /* The next cross edge to be connected is to either `lcand->next->vert` or `rcand->next->vert`;
1546 * if both are valid, choose the appropriate one using the #incircle test. */
1547 if (!valid_lcand ||
1548 (valid_rcand &&
1550 lcand->next->vert->co, lcand->vert->co, rcand->vert->co, rcand->next->vert->co) > 0))
1551 {
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";
1556 }
1557 ebasel = cdt->add_diagonal(rcand->next, basel_sym);
1558 }
1559 else {
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";
1564 }
1565 ebasel = cdt->add_diagonal(basel_sym->next, sym(lcand));
1566 }
1567 basel = &ebasel->symedges[0];
1568 basel_sym = &ebasel->symedges[1];
1569 BLI_assert(basel_sym->face == cdt->outer_face);
1570 if (dbg_level > 2) {
1571 cdt_draw("after adding new crossedge", *cdt);
1572 }
1573 }
1574 *r_le = ldo;
1575 *r_re = rdo;
1576 BLI_assert(sym(ldo)->face == cdt->outer_face && rdo->face == cdt->outer_face);
1577}
1578
1579/* Guibas-Stolfi Divide-and_Conquer algorithm. */
1580template<typename T> void dc_triangulate(CDTArrangement<T> *cdt, Array<SiteInfo<T>> &sites)
1581{
1583 /* Compress sites in place to eliminated verts that merge to others. */
1584 int i = 0;
1585 int j = 0;
1586 int nsites = sites.size();
1587 while (j < nsites) {
1588 /* Invariant: `sites[0..i-1]` have non-merged verts from `0..(j-1)` in them. */
1589 sites[i] = sites[j++];
1590 if (sites[i].v->merge_to_index < 0) {
1591 i++;
1592 }
1593 }
1594 int n = i;
1595 if (n == 0) {
1596 return;
1597 }
1598 SymEdge<T> *le;
1599 SymEdge<T> *re;
1600 dc_tri(cdt, sites, 0, n, &le, &re);
1601}
1602
1621template<typename T> void initial_triangulation(CDTArrangement<T> *cdt)
1622{
1624 int n = cdt->verts.size();
1625 if (n <= 1) {
1626 return;
1627 }
1628 Array<SiteInfo<T>> sites(n);
1629 for (int i = 0; i < n; ++i) {
1630 sites[i].v = cdt->verts[i];
1631 sites[i].orig_index = i;
1632 }
1633 std::ranges::sort(sites, site_lexicographic_sort<T>);
1634 find_site_merges(sites);
1635 dc_triangulate(cdt, sites);
1636}
1637
1645template<typename T> static void re_delaunay_triangulate(CDTArrangement<T> *cdt, SymEdge<T> *se)
1646{
1647 if (se->face == cdt->outer_face || sym(se)->face == cdt->outer_face) {
1648 return;
1649 }
1650 /* `se` is a diagonal just added, and it is base of area to re-triangulate (face on its left). */
1651 int count = 1;
1652 for (const SymEdge<T> *ss = se->next; ss != se; ss = ss->next) {
1653 count++;
1654 }
1655 if (count <= 3) {
1656 return;
1657 }
1658 /* First and last are the SymEdges whose verts are first and last off of base,
1659 * continuing from 'se'. */
1660 SymEdge<T> *first = se->next->next;
1661 /* We want to make a triangle with 'se' as base and some other c as 3rd vertex. */
1662 CDTVert<T> *a = se->vert;
1663 CDTVert<T> *b = se->next->vert;
1664 CDTVert<T> *c = first->vert;
1665 SymEdge<T> *cse = first;
1666 for (SymEdge<T> *ss = first->next; ss != se; ss = ss->next) {
1667 CDTVert<T> *v = ss->vert;
1668 if (filtered_incircle(a->co, b->co, c->co, v->co) > 0) {
1669 c = v;
1670 cse = ss;
1671 }
1672 }
1673 /* Add diagonals necessary to make `abc` a triangle. */
1674 CDTEdge<T> *ebc = nullptr;
1675 CDTEdge<T> *eca = nullptr;
1676 if (!exists_edge(b, c)) {
1677 ebc = cdt->add_diagonal(se->next, cse);
1678 }
1679 if (!exists_edge(c, a)) {
1680 eca = cdt->add_diagonal(cse, se);
1681 }
1682 /* Now recurse. */
1683 if (ebc) {
1684 re_delaunay_triangulate(cdt, &ebc->symedges[1]);
1685 }
1686 if (eca) {
1687 re_delaunay_triangulate(cdt, &eca->symedges[1]);
1688 }
1689}
1690
1691template<typename T> inline int tri_orient(const SymEdge<T> *t)
1692{
1693 return filtered_orient2d(t->vert->co, t->next->vert->co, t->next->next->vert->co);
1694}
1695
1721template<typename T> class CrossData {
1722 public:
1723 T lambda = T(0);
1727
1730 {
1731 }
1732 CrossData(const CrossData &other)
1733 : lambda(other.lambda), vert(other.vert), in(other.in), out(other.out)
1734 {
1735 }
1736 CrossData(CrossData &&other) noexcept
1737 : lambda(std::move(other.lambda)),
1738 vert(std::move(other.vert)),
1739 in(std::move(other.in)),
1740 out(std::move(other.out))
1741 {
1742 }
1743 ~CrossData() = default;
1745 {
1746 if (this != &other) {
1747 lambda = other.lambda;
1748 vert = other.vert;
1749 in = other.in;
1750 out = other.out;
1751 }
1752 return *this;
1753 }
1754 CrossData &operator=(CrossData &&other) noexcept
1755 {
1756 lambda = std::move(other.lambda);
1757 vert = std::move(other.vert);
1758 in = std::move(other.in);
1759 out = std::move(other.out);
1760 return *this;
1761 }
1762};
1763
1764template<typename T>
1765bool get_next_crossing_from_vert(CDT_state<T> *cdt_state,
1766 CrossData<T> *cd,
1767 CrossData<T> *cd_next,
1768 const CDTVert<T> *v2);
1769
1777template<typename T>
1779 SymEdge<T> *cd_out,
1780 CrossData<T> *cd,
1781 CrossData<T> *cd_next)
1782{
1783 SymEdge<T> *se;
1784
1785 cd_next->lambda = T(0);
1786 cd_next->vert = v;
1787 cd_next->in = nullptr;
1788 cd_next->out = nullptr;
1789 if (cd->lambda == 0) {
1790 cd->out = cd_out;
1791 }
1792 else {
1793 /* One of the edges in the triangle with edge sym(cd->in) contains v. */
1794 se = sym(cd->in);
1795 if (se->vert != v) {
1796 se = se->next;
1797 if (se->vert != v) {
1798 se = se->next;
1799 }
1800 }
1801 BLI_assert(se->vert == v);
1802 cd_next->in = se;
1803 }
1804}
1805
1819template<typename T>
1821 const CDTVert<T> *v2,
1822 SymEdge<T> *t,
1823 CrossData<T> *cd,
1824 CrossData<T> *cd_next,
1825 const T epsilon)
1826{
1828 CDTVert<T> *va = t->vert;
1829 CDTVert<T> *vb = t->next->vert;
1830 CDTVert<T> *vc = t->next->next->vert;
1831 SymEdge<T> *se_vcvb = sym(t->next);
1832 SymEdge<T> *se_vcva = t->next->next;
1833 BLI_assert(se_vcva->vert == vc && se_vcva->next->vert == va);
1834 BLI_assert(se_vcvb->vert == vc && se_vcvb->next->vert == vb);
1836 auto isect = isect_seg_seg(va->co.exact, vb->co.exact, curco.exact, v2->co.exact);
1837 T &lambda = isect.lambda;
1838 switch (isect.kind) {
1839 case isect_result<VecBase<T, 2>>::LINE_LINE_CROSS: {
1840#ifdef WITH_GMP
1841 if (!std::is_same_v<T, mpq_class>)
1842#else
1843 if (true)
1844#endif
1845 {
1846 double len_ab = distance(va->co.approx, vb->co.approx);
1847 if (lambda * len_ab <= epsilon) {
1848 fill_crossdata_for_through_vert(va, se_vcva, cd, cd_next);
1849 }
1850 else if ((1 - lambda) * len_ab <= epsilon) {
1851 fill_crossdata_for_through_vert(vb, se_vcvb, cd, cd_next);
1852 }
1853 else {
1854 *cd_next = CrossData<T>(lambda, nullptr, t, nullptr);
1855 if (cd->lambda == 0) {
1856 cd->out = se_vcva;
1857 }
1858 }
1859 }
1860 else {
1861 *cd_next = CrossData<T>(lambda, nullptr, t, nullptr);
1862 if (cd->lambda == 0) {
1863 cd->out = se_vcva;
1864 }
1865 }
1866 break;
1867 }
1868 case isect_result<VecBase<T, 2>>::LINE_LINE_EXACT: {
1869 if (lambda == 0) {
1870 fill_crossdata_for_through_vert(va, se_vcva, cd, cd_next);
1871 }
1872 else if (lambda == 1) {
1873 fill_crossdata_for_through_vert(vb, se_vcvb, cd, cd_next);
1874 }
1875 else {
1876 *cd_next = CrossData<T>(lambda, nullptr, t, nullptr);
1877 if (cd->lambda == 0) {
1878 cd->out = se_vcva;
1879 }
1880 }
1881 break;
1882 }
1883 case isect_result<VecBase<T, 2>>::LINE_LINE_NONE: {
1884#ifdef WITH_GMP
1885 if (std::is_same_v<T, mpq_class>) {
1886 BLI_assert(false);
1887 }
1888#endif
1889 /* It should be very near one end or other of segment. */
1890 const T middle_lambda = 0.5;
1891 if (lambda <= middle_lambda) {
1892 fill_crossdata_for_through_vert(va, se_vcva, cd, cd_next);
1893 }
1894 else {
1895 fill_crossdata_for_through_vert(vb, se_vcvb, cd, cd_next);
1896 }
1897 break;
1898 }
1899 case isect_result<VecBase<T, 2>>::LINE_LINE_COLINEAR: {
1900 if (distance_squared(va->co.approx, v2->co.approx) <=
1901 distance_squared(vb->co.approx, v2->co.approx))
1902 {
1903 fill_crossdata_for_through_vert(va, se_vcva, cd, cd_next);
1904 }
1905 else {
1906 fill_crossdata_for_through_vert(vb, se_vcvb, cd, cd_next);
1907 }
1908 break;
1909 }
1910 }
1911} // namespace blender::meshintersect
1912
1920template<typename T>
1922 CrossData<T> *cd,
1923 CrossData<T> *cd_next,
1924 const CDTVert<T> *v2)
1925{
1927 SymEdge<T> *tstart = cd->vert->symedge;
1928 SymEdge<T> *t = tstart;
1929 CDTVert<T> *vcur = cd->vert;
1930 bool ok = false;
1931 do {
1932 /* The ray from `vcur` to v2 has to go either between two successive
1933 * edges around `vcur` or exactly along them. This time through the
1934 * loop, check to see if the ray goes along `vcur-va`
1935 * or between `vcur-va` and `vcur-vb`, where va is the end of t
1936 * and vb is the next vertex (on the next rot edge around vcur, but
1937 * should also be the next vert of triangle starting with `vcur-va`). */
1938 if (t->face != cdt_state->cdt.outer_face && tri_orient(t) < 0) {
1939 BLI_assert(false); /* Shouldn't happen. */
1940 }
1941 CDTVert<T> *va = t->next->vert;
1942 CDTVert<T> *vb = t->next->next->vert;
1943 int orient1 = filtered_orient2d(t->vert->co, va->co, v2->co);
1944 if (orient1 == 0 && in_line<T>(vcur->co, va->co, v2->co)) {
1945 fill_crossdata_for_through_vert(va, t, cd, cd_next);
1946 ok = true;
1947 break;
1948 }
1949 if (t->face != cdt_state->cdt.outer_face) {
1950 int orient2 = filtered_orient2d(vcur->co, vb->co, v2->co);
1951 /* Don't handle orient2 == 0 case here: next rotation will get it. */
1952 if (orient1 > 0 && orient2 < 0) {
1953 /* Segment intersection. */
1954 t = t->next;
1955 fill_crossdata_for_intersect(vcur->co, v2, t, cd, cd_next, cdt_state->epsilon);
1956 ok = true;
1957 break;
1958 }
1959 }
1960 } while ((t = t->rot) != tstart);
1961 return ok;
1962}
1963
1972template<typename T>
1974 CrossData<T> *cd_next,
1975 const CDTVert<T> *v2,
1976 const T epsilon)
1977{
1979 CDTVert<T> *va = cd->in->vert;
1980 CDTVert<T> *vb = cd->in->next->vert;
1981 VecBase<T, 2> curco = interpolate(va->co.exact, vb->co.exact, cd->lambda);
1982 FatCo<T> fat_curco(curco);
1983 SymEdge<T> *se_ac = sym(cd->in)->next;
1984 CDTVert<T> *vc = se_ac->next->vert;
1985 int orient = filtered_orient2d(fat_curco, v2->co, vc->co);
1986 if (orient < 0) {
1987 fill_crossdata_for_intersect<T>(fat_curco, v2, se_ac->next, cd, cd_next, epsilon);
1988 }
1989 else if (orient > 0.0) {
1990 fill_crossdata_for_intersect(fat_curco, v2, se_ac, cd, cd_next, epsilon);
1991 }
1992 else {
1993 *cd_next = CrossData<T>{0.0, vc, se_ac->next, nullptr};
1994 }
1995}
1996
1997template<typename T> void dump_crossings(const Span<CrossData<T>> crossings)
1998{
1999 std::cout << "CROSSINGS\n";
2000 for (int i = 0; i < crossings.size(); ++i) {
2001 std::cout << i << ": ";
2002 const CrossData<T> &cd = crossings[i];
2003 if (cd.lambda == 0) {
2004 std::cout << "v" << cd.vert->index;
2005 }
2006 else {
2007 std::cout << "lambda=" << cd.lambda;
2008 }
2009 if (cd.in != nullptr) {
2010 std::cout << " in=" << short_se_dump(cd.in);
2011 std::cout << " out=" << short_se_dump(cd.out);
2012 }
2013 std::cout << "\n";
2014 }
2015}
2016
2028template<typename T>
2030 CDT_state<T> *cdt_state, CDTVert<T> *v1, CDTVert<T> *v2, uint32_t input_id, LinkNode **r_edges)
2031{
2033 constexpr int dbg_level = 0;
2034 if (dbg_level > 0) {
2035 std::cout << "\nADD EDGE CONSTRAINT\n" << vertname(v1) << " " << vertname(v2) << "\n";
2036 }
2037 LinkNodePair edge_list = {nullptr, nullptr};
2038
2039 if (r_edges) {
2040 *r_edges = nullptr;
2041 }
2042
2043 /*
2044 * Handle two special cases first:
2045 * 1) The two end vertices are the same (can happen because of merging).
2046 * 2) There is already an edge between v1 and v2.
2047 */
2048 if (v1 == v2) {
2049 return;
2050 }
2052 if (t != nullptr) {
2053 /* Segment already there. */
2054 add_to_input_ids(t->edge->input_ids, input_id);
2055 if (r_edges != nullptr) {
2056 BLI_linklist_append(&edge_list, t->edge);
2057 *r_edges = edge_list.list;
2058 }
2059 return;
2060 }
2061
2062 /*
2063 * Fill crossings array with CrossData points for intersection path from v1 to v2.
2064 *
2065 * At every point, the crossings array has the path so far, except that
2066 * the `.out` field of the last element of it may not be known yet -- if that
2067 * last element is a vertex, then we won't know the output edge until we
2068 * find the next crossing.
2069 *
2070 * To protect against infinite loops, we keep track of which vertices
2071 * we have visited by setting their visit_index to a new visit epoch.
2072 *
2073 * We check a special case first: where the segment is already there in
2074 * one hop. Saves a bunch of orient2d tests in that common case.
2075 */
2076 int visit = ++cdt_state->visit_count;
2077 Vector<CrossData<T>, 128> crossings;
2078 crossings.append(CrossData<T>(T(0), v1, nullptr, nullptr));
2079 int n;
2080 while (!((n = crossings.size()) > 0 && crossings[n - 1].vert == v2)) {
2081 crossings.append(CrossData<T>());
2082 CrossData<T> *cd = &crossings[n - 1];
2083 CrossData<T> *cd_next = &crossings[n];
2084 bool ok;
2085 if (crossings[n - 1].lambda == 0) {
2086 ok = get_next_crossing_from_vert(cdt_state, cd, cd_next, v2);
2087 }
2088 else {
2089 get_next_crossing_from_edge<T>(cd, cd_next, v2, cdt_state->epsilon);
2090 ok = true;
2091 }
2092 constexpr int unreasonably_large_crossings = 100000;
2093 if (!ok || crossings.size() == unreasonably_large_crossings) {
2094 /* Shouldn't happen but if does, just bail out. */
2095 BLI_assert(false);
2096 return;
2097 }
2098 if (crossings[n].lambda == 0) {
2099 if (crossings[n].vert->visit_index == visit) {
2100 /* Shouldn't happen but if it does, just bail out. */
2101 BLI_assert(false);
2102 return;
2103 }
2104 crossings[n].vert->visit_index = visit;
2105 }
2106 }
2107
2108 if (dbg_level > 0) {
2109 dump_crossings<T>(crossings);
2110 }
2111
2112 /*
2113 * Post-process crossings.
2114 * Some crossings may have an intersection crossing followed
2115 * by a vertex crossing that is on the same edge that was just
2116 * intersected. We prefer to go directly from the previous
2117 * crossing directly to the vertex. This may chain backwards.
2118 *
2119 * This loop marks certain crossings as "deleted", by setting
2120 * their lambdas to -1.0.
2121 */
2122 int ncrossings = crossings.size();
2123 for (int i = 2; i < ncrossings; ++i) {
2124 CrossData<T> *cd = &crossings[i];
2125 if (cd->lambda == 0.0) {
2126 CDTVert<T> *v = cd->vert;
2127 int j;
2128 CrossData<T> *cd_prev;
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))
2133 {
2134 break;
2135 }
2136 cd_prev->lambda = -1.0; /* Mark cd_prev as 'deleted'. */
2137 }
2138 if (j < i - 1) {
2139 /* Some crossings were deleted. Fix the in and out edges across gap. */
2140 cd_prev = &crossings[j];
2141 SymEdge<T> *se;
2142 if (cd_prev->lambda == 0.0) {
2143 se = find_symedge_between_verts(cd_prev->vert, v);
2144 if (se == nullptr) {
2145 return;
2146 }
2147 cd_prev->out = se;
2148 cd->in = nullptr;
2149 }
2150 else {
2151 se = find_symedge_with_face(v, sym(cd_prev->in)->face);
2152 if (se == nullptr) {
2153 return;
2154 }
2155 cd->in = se;
2156 }
2157 }
2158 }
2159 }
2160
2161 /*
2162 * Insert all intersection points on constrained edges.
2163 */
2164 for (int i = 0; i < ncrossings; ++i) {
2165 CrossData<T> *cd = &crossings[i];
2166 if (cd->lambda != 0.0 && cd->lambda != -1.0 && is_constrained_edge(cd->in->edge)) {
2167 CDTEdge<T> *edge = cdt_state->cdt.split_edge(
2168 cd->in, cd->lambda, cdt_state->edge_winding_map, cdt_state->polygon_boundary_count_map);
2169 cd->vert = edge->symedges[0].vert;
2170
2171 /* Keep track of original edges for the intersection point. */
2172 if (cdt_state->needed_ids & CDT_INTERSECTED_EDGES) {
2173 uint32_t edge1_id = -1;
2174 if (!cd->in->edge->input_ids.is_empty()) {
2175 /* Use the first original edge. */
2176 edge1_id = *cd->in->edge->input_ids.begin();
2177 }
2178 cd->vert->intersected_edges = {int(edge1_id), int(input_id)};
2179 }
2180 }
2181 }
2182
2183 /*
2184 * Remove any crossed, non-intersected edges.
2185 */
2186 for (int i = 0; i < ncrossings; ++i) {
2187 CrossData<T> *cd = &crossings[i];
2188 if (cd->lambda != 0.0 && cd->lambda != -1.0 && !is_constrained_edge(cd->in->edge)) {
2189 cdt_state->cdt.delete_edge(cd->in);
2190 }
2191 }
2192
2193 /*
2194 * Insert segments for v1->v2.
2195 */
2196 SymEdge<T> *tstart = crossings[0].out;
2197 for (int i = 1; i < ncrossings; i++) {
2198 CrossData<T> *cd = &crossings[i];
2199 if (cd->lambda == -1.0) {
2200 continue; /* This crossing was deleted. */
2201 }
2202 t = nullptr;
2203 SymEdge<T> *tnext = t;
2204 CDTEdge<T> *edge;
2205 if (cd->lambda != 0.0) {
2206 if (is_constrained_edge(cd->in->edge)) {
2207 t = cd->vert->symedge;
2208 tnext = sym(t)->next;
2209 }
2210 }
2211 else if (cd->lambda == 0.0) {
2212 t = cd->in;
2213 tnext = cd->out;
2214 if (t == nullptr) {
2215 /* Previous non-deleted crossing must also have been a vert, and segment should exist. */
2216 int j;
2217 CrossData<T> *cd_prev;
2218 for (j = i - 1; j >= 0; j--) {
2219 cd_prev = &crossings[j];
2220 if (cd_prev->lambda != -1.0) {
2221 break;
2222 }
2223 }
2224 BLI_assert(cd_prev->lambda == 0.0);
2225 BLI_assert(cd_prev->out->next->vert == cd->vert);
2226 edge = cd_prev->out->edge;
2227 add_to_input_ids(edge->input_ids, input_id);
2228 if (r_edges != nullptr) {
2229 BLI_linklist_append(&edge_list, edge);
2230 }
2231 }
2232 }
2233 if (t != nullptr) {
2234 if (tstart->next->vert == t->vert) {
2235 edge = tstart->edge;
2236 }
2237 else {
2238 edge = cdt_state->cdt.add_diagonal(tstart, t);
2239 }
2240 add_to_input_ids(edge->input_ids, input_id);
2241 if (r_edges != nullptr) {
2242 BLI_linklist_append(&edge_list, edge);
2243 }
2244 /* Now re-triangulate upper and lower gaps. */
2245 re_delaunay_triangulate(&cdt_state->cdt, &edge->symedges[0]);
2246 re_delaunay_triangulate(&cdt_state->cdt, &edge->symedges[1]);
2247 }
2248 if (i < ncrossings - 1) {
2249 if (tnext != nullptr) {
2250 tstart = tnext;
2251 }
2252 }
2253 }
2254
2255 if (r_edges) {
2256 *r_edges = edge_list.list;
2257 }
2258}
2259
2266template<typename T> void add_edge_constraints(CDT_state<T> *cdt_state, const CDT_input<T> &input)
2267{
2269 uint32_t ne = uint32_t(input.edge.size());
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) {
2275 /* Ignore invalid indices in edges. */
2276 continue;
2277 }
2278 CDTVert<T> *v1 = cdt_state->cdt.get_vert_resolve_merge(iv1);
2279 CDTVert<T> *v2 = cdt_state->cdt.get_vert_resolve_merge(iv2);
2280 /* Safe to drop to 0 here (unlike in `add_face_constraints`): loose-edge ids
2281 * stay below any face's id range, so `add_face_ids` doesn't depend on them. */
2282 uint32_t id = (cdt_state->needed_ids & (CDT_ORIG_EDGES | CDT_INTERSECTED_EDGES)) ? i : 0;
2283 add_edge_constraint(cdt_state, v1, v2, id, nullptr);
2284 }
2285 cdt_state->face_edge_offset = ne;
2286}
2287
2307template<typename T>
2309 SymEdge<T> *face_symedge,
2310 uint32_t face_id,
2311 uint32_t fedge_start,
2312 uint32_t fedge_end)
2313{
2315 /* Can't loop forever since eventually would visit every face. */
2316 cdt_state->visit_count++;
2317 int visit = cdt_state->visit_count;
2318 Vector<SymEdge<T> *> stack;
2319 stack.append(face_symedge);
2320 while (!stack.is_empty()) {
2321 SymEdge<T> *se = stack.pop_last();
2322 CDTFace<T> *face = se->face;
2323 if (face->visit_index == visit) {
2324 continue;
2325 }
2326 face->visit_index = visit;
2327 add_to_input_ids(face->input_ids, face_id);
2328 SymEdge<T> *se_start = se;
2329 for (se = se->next; se != se_start; se = se->next) {
2330 SymEdge<T> *se_sym = sym(se);
2331 CDTFace<T> *face_other = se_sym->face;
2332 if (face_other->visit_index == visit) {
2333 continue;
2334 }
2335 if (!id_range_in_list(se->edge->input_ids, fedge_start, fedge_end)) {
2336 stack.append(se_sym);
2337 }
2338 }
2339 }
2340}
2341
2342/* Return a power of 10 that is greater than or equal to x. */
2343[[maybe_unused]]
2345{
2346 if (x == 0) {
2347 return 1;
2348 }
2349 uint32_t ans = 1;
2350 BLI_assert(x < std::numeric_limits<uint32_t>::max() / 10);
2351 while (ans < x) {
2352 ans *= 10;
2353 }
2354 return ans;
2355}
2356
2367template<typename T>
2369 const CDT_input<T> &input,
2370 CDT_output_type output_type,
2371 const bool need_winding)
2372{
2374 int nv = input.vert.size();
2375 const GroupedSpan<int> input_faces(input.face_offsets, input.face_vert_indices);
2376 SymEdge<T> *face_symedge0 = nullptr;
2377 CDTArrangement<T> *cdt = &cdt_state->cdt;
2378
2379 uint32_t maxflen = 0;
2380 for (const int f : input_faces.index_range()) {
2381 maxflen = std::max<uint32_t>(maxflen, input_faces[f].size());
2382 }
2384 /* For convenience in debugging, make face_edge_offset be a power of 10. */
2386 std::max(maxflen, cdt_state->face_edge_offset));
2387 }
2388 else {
2389 cdt_state->face_edge_offset = std::max(maxflen, cdt_state->face_edge_offset);
2390 }
2391 /* The original_edge encoding scheme doesn't work if the following is false.
2392 * If we really have that many faces and that large a max face length that when multiplied
2393 * together the are >= UINT32_MAX, then the Delaunay calculation will take unreasonably
2394 * long anyway.
2395 */
2396 /* A zero offset means every face is too small to constrain, so no ids are encoded. */
2397 BLI_assert(input_faces.is_empty() || cdt_state->face_edge_offset == 0 ||
2398 std::numeric_limits<uint32_t>::max() / cdt_state->face_edge_offset >
2399 input_faces.size());
2400 int faces_added = 0;
2401
2402 /* A later optimization will skip propagating face_ids if `need_orig_face_ids` is `false`,
2403 * or will use a CW test to skip CW edges if `skip_cw_ids` is `true`. */
2404 const bool need_orig_face_ids = (cdt_state->needed_ids & CDT_ORIG_FACES) ||
2405 output_type == CDT_CONSTRAINTS_VALID_BMESH;
2406 const bool skip_cw_ids = need_orig_face_ids && !(cdt_state->needed_ids & CDT_CW_ORIG_FACES) &&
2407 !ELEM(output_type,
2411
2412 for (const int f : input_faces.index_range()) {
2413 const Span<int> face = input_faces[f];
2414 if (face.size() <= 2) {
2415 /* Ignore faces with fewer than 3 vertices. */
2416 continue;
2417 }
2418 /* If need face ids, then need to know orientation of boundary. */
2419 double signed_area = 0.0;
2420 uint32_t fedge_start = uint32_t(f + 1) * cdt_state->face_edge_offset;
2421 for (const int i : face.index_range()) {
2422 uint32_t face_edge_id = fedge_start + uint32_t(i);
2423 int iv1 = face[i];
2424 int iv2 = face[(i + 1) % face.size()];
2425 if (iv1 < 0 || iv1 >= nv || iv2 < 0 || iv2 >= nv) {
2426 /* Ignore face edges with invalid vertices. */
2427 continue;
2428 }
2429 ++faces_added;
2430 CDTVert<T> *v1 = cdt->get_vert_resolve_merge(iv1);
2432 if (skip_cw_ids) {
2433 signed_area += math::cross(v1->co.approx, v2->co.approx);
2434 }
2435 LinkNode *edge_list;
2436 /* Always tag with `face_edge_id` even when `needed_ids` doesn't have CDT_ORIG_EDGES:
2437 * `add_face_ids` interior flood reads it via `id_range_in_list` as a
2438 * boundary marker. Without it the flood escapes the face and walks the
2439 * whole CDT, doing significantly more work.
2440 * The orig id tagged here doesn't require the orig arrays to exist
2441 * (created when `needed_ids != 0`). */
2442 add_edge_constraint(cdt_state, v1, v2, face_edge_id, &edge_list);
2443 /* Set a new face_symedge0 each time since earlier ones may not
2444 * survive later symedge splits. Really, just want the one when
2445 * `i == face.size() - 1`, but this code guards against that one somehow being null. */
2446 if (edge_list != nullptr) {
2447 CDTEdge<T> *face_edge = static_cast<CDTEdge<T> *>(edge_list->link);
2448 face_symedge0 = &face_edge->symedges[0];
2449 if (face_symedge0->vert != v1) {
2450 face_symedge0 = &face_edge->symedges[1];
2451 BLI_assert(face_symedge0->vert == v1);
2452 }
2453 /* Per-edge: count polygon boundaries for even-odd,
2454 * accumulate signed winding for non-zero.
2455 * Mechanism documented on the maps themselves. */
2456 if (cdt_state->polygon_boundary_count_map || need_winding) {
2457 CDTVert<T> *curr_vert = v1;
2458 for (LinkNode *ln = edge_list; ln != nullptr; ln = ln->next) {
2459 CDTEdge<T> *e = static_cast<CDTEdge<T> *>(ln->link);
2460 CDTVert<T> *next_vert;
2461 int winding_delta;
2462 if (e->symedges[0].vert == curr_vert) {
2463 next_vert = e->symedges[1].vert;
2464 winding_delta = 1;
2465 }
2466 else {
2467 BLI_assert(e->symedges[1].vert == curr_vert);
2468 next_vert = e->symedges[0].vert;
2469 winding_delta = -1;
2470 }
2471 if (cdt_state->polygon_boundary_count_map) {
2472 cdt_state->polygon_boundary_count_map->lookup_or_add_default(e) += 1;
2473 }
2474 if (need_winding) {
2475 cdt_state->edge_winding_map->lookup_or_add_default(e) += winding_delta;
2476 }
2477 curr_vert = next_vert;
2478 }
2479 }
2480 }
2481 BLI_linklist_free(edge_list, nullptr);
2482 }
2483 uint32_t fedge_end = fedge_start + uint32_t(face.size()) - 1;
2484 if (face_symedge0 != nullptr) {
2485 /* We need to propagate face ids to all faces that represent #f, if #needed_ids has
2486 * `CDT_ORIG_FACES`. Even if #needed_ids doesn't specify that, we need to propagate at least
2487 * the fact that the face ids set would be non-empty for #CDT_CONSTRAINTS_VALID_BMESH
2488 * (the with-holes outputs use the hole status instead).
2489 * However we don't need this for hole-making faces (i.e., CW or mostly-CW ones), usually.
2490 * Only if the user added CDT_CW_ORIG_FACES to needed_ids will we flood-fill such faces.
2491 */
2492 if (need_orig_face_ids && (!skip_cw_ids || signed_area >= 0.0)) {
2493 uint32_t id = (cdt_state->needed_ids & CDT_ORIG_FACES) ? uint32_t(f) : 0;
2494 add_face_ids(cdt_state, face_symedge0, uint32_t(id), fedge_start, fedge_end);
2495 }
2496 }
2497 }
2498 return faces_added;
2499}
2500
2501/* Delete_edge but try not to mess up outer face.
2502 * Also faces have symedges now, so make sure not
2503 * to mess those up either. */
2504template<typename T> void dissolve_symedge(CDT_state<T> *cdt_state, SymEdge<T> *se)
2505{
2506 CDTArrangement<T> *cdt = &cdt_state->cdt;
2507 SymEdge<T> *symse = sym(se);
2508 if (symse->face == cdt->outer_face) {
2509 se = sym(se);
2510 symse = sym(se);
2511 }
2512 if (ELEM(cdt->outer_face->symedge, se, symse)) {
2513 /* Advancing by 2 to get past possible 'sym(se)'. */
2514 if (se->next->next == se) {
2515 cdt->outer_face->symedge = nullptr;
2516 }
2517 else {
2518 cdt->outer_face->symedge = se->next->next;
2519 }
2520 }
2521 else {
2522 /* Faces referencing `se` or `symse` must have their `symedge` updated to point to a live edge.
2523 * Always using `next` is incorrect: when the vertex `next` walks toward is isolated
2524 * (this is its last remaining edge), `next` is the *other* half of the edge being deleted,
2525 * leaving a dangling `symedge` that crashed output generation, see: #160787.
2526 *
2527 * Use `prev()` in that case as it walks toward the other vertex, only failing when
2528 * both vertices are isolated, a case #delete_edge handles by deleting the face outright.
2529 * Check `se` and `symse` separately, one side can be safe while the other dangles. */
2530 const bool v1_isolated = (symse->next == se);
2531 const bool v2_isolated = (se->next == symse);
2532 if (se->face->symedge == se) {
2533 se->face->symedge = v2_isolated ? prev(se) : se->next;
2534 }
2535 if (symse->face->symedge == symse) {
2536 symse->face->symedge = v1_isolated ? prev(symse) : symse->next;
2537 }
2538 }
2539 cdt->delete_edge(se);
2540}
2541
2545template<typename T> void remove_non_constraint_edges(CDT_state<T> *cdt_state)
2546{
2548 for (CDTEdge<T> *e : cdt_state->cdt.edges) {
2549 SymEdge<T> *se = &e->symedges[0];
2551 dissolve_symedge(cdt_state, se);
2552 }
2553 }
2554}
2555
2556/*
2557 * Remove the non-constraint edges, but leave enough of them so that all of the
2558 * faces that would be #BMesh faces (see the `use_hole_status` argument)
2559 * are valid: they can't have holes, they can't have repeated vertices, and they can't have
2560 * repeated edges.
2561 *
2562 * Not essential, but to make the result look more aesthetically nice,
2563 * remove the edges in order of decreasing length, so that it is more likely that the
2564 * final remaining support edges are short, and therefore likely to make a fairly
2565 * direct path from an outer face to an inner hole face.
2566 */
2567
2571template<typename T> struct EdgeToSort {
2572 double len_squared = 0.0;
2573 CDTEdge<T> *e{nullptr};
2574
2575 EdgeToSort() = default;
2576 EdgeToSort(const EdgeToSort &other) : len_squared(other.len_squared), e(other.e) {}
2577 EdgeToSort(EdgeToSort &&other) noexcept : len_squared(std::move(other.len_squared)), e(other.e)
2578 {
2579 }
2580 ~EdgeToSort() = default;
2582 {
2583 if (this != &other) {
2584 len_squared = other.len_squared;
2585 e = other.e;
2586 }
2587 return *this;
2588 }
2590 {
2591 len_squared = std::move(other.len_squared);
2592 e = other.e;
2593 return *this;
2594 }
2595};
2596
2604template<typename T>
2606 const bool use_hole_status)
2607{
2609 CDTArrangement<T> *cdt = &cdt_state->cdt;
2610 size_t nedges = cdt->edges.size();
2611 if (nedges == 0) {
2612 return;
2613 }
2614 Vector<EdgeToSort<T>> dissolvable_edges;
2615 dissolvable_edges.reserve(cdt->edges.size());
2616 int i = 0;
2617 for (CDTEdge<T> *e : cdt->edges) {
2619 dissolvable_edges.append(EdgeToSort<T>());
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;
2623 dissolvable_edges[i].len_squared = distance_squared(co1, co2);
2624 i++;
2625 }
2626 }
2627 std::ranges::sort(dissolvable_edges, [](const EdgeToSort<T> &a, const EdgeToSort<T> &b) -> bool {
2628 if (a.len_squared != b.len_squared) {
2629 return a.len_squared < b.len_squared;
2630 }
2631 /* Tie-break on the vertices, `std::ranges::sort` isn't stable so without this
2632 * equal length edges dissolve in a platform dependent order.
2633 * Order the pair so the result doesn't depend on the direction the edge was created. */
2634 const auto edge_verts_fn = [](const CDTEdge<T> *e) -> int2 {
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);
2638 };
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);
2642 });
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();
2645 };
2646 for (EdgeToSort<T> &ets : dissolvable_edges) {
2647 CDTEdge<T> *e = ets.e;
2648 SymEdge<T> *se = &e->symedges[0];
2649 bool dissolve = true;
2650 CDTFace<T> *fleft = se->face;
2651 CDTFace<T> *fright = sym(se)->face;
2652 if (fleft != cdt->outer_face && fright != cdt->outer_face &&
2653 (is_output_face_fn(fleft) || is_output_face_fn(fright)))
2654 {
2655 /* Is there another #SymEdge with same left and right faces?
2656 * Or is there a vertex not part of e touching the same left and right faces? */
2657 for (SymEdge<T> *se2 = se->next; dissolve && se2 != se; se2 = se2->next) {
2658 if (sym(se2)->face == fright ||
2659 (se2->vert != se->next->vert && vert_touches_face(se2->vert, fright)))
2660 {
2661 dissolve = false;
2662 }
2663 }
2664 }
2665
2666 if (dissolve) {
2667 dissolve_symedge(cdt_state, se);
2668 }
2669 }
2670}
2671
2672template<typename T> void remove_outer_edges_until_constraints(CDT_state<T> *cdt_state)
2673{
2675 int visit = ++cdt_state->visit_count;
2676
2677 cdt_state->cdt.outer_face->visit_index = visit;
2678 /* Walk around outer face, adding faces on other side of dissolvable edges to stack. */
2679 Vector<CDTFace<T> *> fstack;
2680 SymEdge<T> *se_start = cdt_state->cdt.outer_face->symedge;
2681 SymEdge<T> *se = se_start;
2682 do {
2683 if (!is_constrained_edge(se->edge)) {
2684 CDTFace<T> *fsym = sym(se)->face;
2685 if (fsym->visit_index != visit) {
2686 fstack.append(fsym);
2687 }
2688 }
2689 } while ((se = se->next) != se_start);
2690
2691 while (!fstack.is_empty()) {
2692 LinkNode *to_dissolve = nullptr;
2693 bool dissolvable;
2694 CDTFace<T> *f = fstack.pop_last();
2695 if (f->visit_index == visit) {
2696 continue;
2697 }
2698 BLI_assert(f != cdt_state->cdt.outer_face);
2699 f->visit_index = visit;
2700 se_start = se = f->symedge;
2701 do {
2702 dissolvable = !is_constrained_edge(se->edge);
2703 if (dissolvable) {
2704 CDTFace<T> *fsym = sym(se)->face;
2705 if (fsym->visit_index != visit) {
2706 fstack.append(fsym);
2707 }
2708 else {
2709 BLI_linklist_prepend(&to_dissolve, se);
2710 }
2711 }
2712 se = se->next;
2713 } while (se != se_start);
2714 while (to_dissolve != nullptr) {
2715 se = static_cast<SymEdge<T> *>(BLI_linklist_pop(&to_dissolve));
2716 if (se->next != nullptr) {
2717 dissolve_symedge(cdt_state, se);
2718 }
2719 }
2720 }
2721}
2722
2723template<typename T> void remove_faces_in_holes(CDT_state<T> *cdt_state)
2724{
2726 CDTArrangement<T> *cdt = &cdt_state->cdt;
2727 for (int i : cdt->faces.index_range()) {
2728 CDTFace<T> *f = cdt->faces[i];
2729 if (!f->deleted && f->hole) {
2730 f->deleted = true;
2731 SymEdge<T> *se = f->symedge;
2732 SymEdge<T> *se_start = se;
2733 SymEdge<T> *se_next = nullptr;
2734 do {
2735 BLI_assert(se != nullptr);
2736 se_next = se->next; /* In case we delete this edge. */
2737 if (se->edge && !is_constrained_edge(se->edge)) {
2738 /* Invalidate one half of this edge. The other will be, or has already been handled
2739 * with the adjacent triangle is processed: it should be part of the same hole. */
2740 se->next = nullptr;
2741 }
2742 se = se_next;
2743 } while (se != se_start);
2744 }
2745 }
2746}
2747
2748/* #CDTFace::visit_index sentinels used by the hole-detection flood-fill.
2749 * The fill assigns a region number in `[0, num_regions)` to every non-deleted face it visits.
2750 * `outer_face` is pre-set to #VISIT_INDEX_OUTER_FACE and skipped.
2751 * deleted faces retain #VISIT_INDEX_UNVISITED since the outer for-loop skips them.
2752 * Use `< 0` to check if a region isn't a "real" region. */
2753static constexpr int VISIT_INDEX_UNVISITED = -1;
2754static constexpr int VISIT_INDEX_OUTER_FACE = -2;
2755
2776template<typename Value, typename CombineFn>
2777void flood_fill_region_values(const Map<int2, Value> &region_pair_value,
2778 MutableSpan<Value> region_value,
2779 const Value unset_value,
2780 CombineFn combine)
2781{
2782 struct RegionEdge {
2783 int neighbor;
2784 Value value;
2785 };
2786 const int64_t num_regions = region_value.size();
2787
2788 /* Count outgoing neighbors per region directly into the offsets array. The accumulator
2789 * writes offsets in-place over [0..N-1] and overwrites [N] with the total, so the trailing
2790 * slot just needs to start at 0 (as the value-init does). */
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]]++;
2794 }
2796 region_adjacency_offset_data);
2797
2798 /* Fill flat adjacency, with a per-region write cursor for sequential appends. */
2799 Array<RegionEdge> adjacency_data(region_adjacency_offsets.total_size());
2800 Array<int> write_position(num_regions, 0);
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};
2806 }
2807
2808 /* Stack-based traversal from pre-seeded roots. */
2809 Vector<int> region_stack;
2810 region_stack.reserve(num_regions);
2811 for (const int r : region_value.index_range()) {
2812 if (region_value[r] != unset_value) {
2813 region_stack.append(r);
2814 }
2815 }
2816 while (!region_stack.is_empty()) {
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);
2824 }
2825 }
2826 }
2827}
2828
2836template<typename T> void detect_holes_with_fillrule_even_odd(CDT_state<T> *cdt_state)
2837{
2839 /* Algorithm:
2840 * - Flood-fill faces into regions (connected through non-constrained edges).
2841 * - For each region, seed its parity from boundary edges into `outer_face`.
2842 * - Build region adjacency graph with per-edge parity flips (boundary-count mod 2).
2843 * - Propagate: S.parity = R.parity XOR flip(R->S).
2844 * - A region is a hole if its parity is 0 (even crossings, or unreachable from outer).
2845 *
2846 * The per-edge flip uses polygon-boundary count rather than a boolean "constrained":
2847 * a CDT edge shared by N input polygon boundaries contributes N mod 2, so coincident
2848 * boundaries (stacked rectangles, etc.) cancel as SVG/PostScript even-odd requires.
2849 * Implementation matches CGAL's `mark_domain_in_triangulation`
2850 * (`Triangulation_2`, from 5.6), extended to handle arbitrary polygon-boundary count per edge.
2851 *
2852 * Complexity: `O(F + E)` where F = faces, E = edges.
2853 */
2854
2855 CDTArrangement<T> *cdt = &cdt_state->cdt;
2856 /* `delaunay_calc` allocates this for any output type that drives this detector,
2857 * so it is always non-null on this code path. */
2858 BLI_assert(cdt_state->polygon_boundary_count_map != nullptr);
2859 const Map<CDTEdge<T> *, int> &boundary_count = *cdt_state->polygon_boundary_count_map;
2860
2861 /* Boundary regions touch outer_face. Collected during flood-fill so the second edge sweep
2862 * only needs to handle cross-region adjacency. */
2863 struct BoundaryRegionInfo {
2864 int region;
2865 int8_t parity;
2866 };
2867 Vector<BoundaryRegionInfo> boundary_regions;
2868 boundary_regions.reserve(cdt->faces.size());
2869
2870 Vector<CDTFace<T> *> fstack;
2871 fstack.reserve(cdt->faces.size());
2872 for (CDTFace<T> *f : cdt->faces) {
2874 }
2875 cdt->outer_face->visit_index = VISIT_INDEX_OUTER_FACE;
2876
2877 int cur_region = -1;
2878 for (CDTFace<T> *f_init : cdt->faces) {
2879 if (f_init->deleted || !f_init->symedge || f_init->visit_index != VISIT_INDEX_UNVISITED) {
2880 continue;
2881 }
2882 cur_region++;
2883 /* Mark-on-push: visit_index is assigned the moment a face is queued, never on pop.
2884 * This guarantees each face is pushed at most once, removing the per-pop recheck. */
2885 f_init->visit_index = cur_region;
2886 fstack.append(f_init);
2887 /* `outer_parity` doubles as a "this region touches outer_face" flag: -1 = no outer-face
2888 * contact yet; 0/1 = parity reached, with "filled wins" merge on conflict. */
2889 int8_t outer_parity = -1;
2890
2891 while (!fstack.is_empty()) {
2892 CDTFace<T> *f = fstack.pop_last();
2893 BLI_assert(f->visit_index == cur_region);
2894
2895 SymEdge<T> *se_start = f->symedge;
2896 SymEdge<T> *se = se_start;
2897 do {
2898 if (!se->edge) {
2899 continue;
2900 }
2901 CDTFace<T> *neighbor = sym(se)->face;
2902 if (!neighbor) {
2903 continue;
2904 }
2905 /* NOTE: Loose edges (input edges not part of any face) are not supported.
2906 * To support them, they would need parity values assigned here. */
2907 const bool constrained = is_constrained_edge(se->edge);
2908 if (neighbor == cdt->outer_face) {
2909 /* Per-edge parity flip = polygon-boundary count mod 2. An unconstrained
2910 * convex-hull edge that is not on any input face boundary is not in the map and
2911 * defaults to 0; a constrained edge crossed by N coincident polygon boundaries
2912 * contributes N mod 2. Source is the side map (not `input_ids.size()`) so the
2913 * result is stable irrespective of #needed_ids. */
2914 const int8_t flip = int8_t(boundary_count.lookup_default(se->edge, 0) & 1);
2915 if (outer_parity == -1) {
2916 outer_parity = flip;
2917 }
2918 else if (outer_parity != flip) {
2919 /* Two boundary edges into this region disagree on parity (e.g. a hull section
2920 * with mixed polygon multiplicities). "Filled wins on conflict": once any seed
2921 * says 1 the region stays at 1, and any 0-vs-1 disagreement on a region still at
2922 * 0 promotes it to 1. The result is order-independent because 1 is a fixed
2923 * point under both orderings of the conflicting edges. */
2924 outer_parity = 1;
2925 }
2926 }
2927 else if (!constrained && !neighbor->deleted &&
2929 {
2930 neighbor->visit_index = cur_region;
2931 fstack.append(neighbor);
2932 }
2933 } while ((se = se->next) != se_start);
2934 }
2935 if (outer_parity != -1) {
2936 boundary_regions.append({cur_region, outer_parity});
2937 }
2938 }
2939
2940 const int num_regions = ++cur_region;
2941 cdt_state->visit_count = num_regions;
2942 if (num_regions == 0) {
2943 return;
2944 }
2945
2946 /* Cross-region adjacency. Each constrained edge between two distinct regions contributes
2947 * a parity flip equal to its polygon-boundary count mod 2. Both directions are stored;
2948 * XOR is symmetric so the same flip applies either way. `Map::add` ignores subsequent
2949 * inserts for an existing key, giving first-edge-wins. */
2950 Map<int2, int8_t> region_pair_flip;
2951 /* ~3 cross-region edges per region, two map entries per edge (one each direction). */
2952 region_pair_flip.reserve(6 * num_regions);
2953
2954 for (CDTEdge<T> *e : cdt->edges) {
2956 continue;
2957 }
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) {
2961 continue;
2962 }
2963 const int8_t flip = int8_t(boundary_count.lookup_default(e, 0) & 1);
2964 region_pair_flip.add(int2(region0, region1), flip);
2965 region_pair_flip.add(int2(region1, region0), flip);
2966 }
2967
2968 /* Seed region parities from boundary info, then propagate. */
2969 Array<int8_t> region_parity(num_regions, -1);
2970 for (const BoundaryRegionInfo &info : boundary_regions) {
2971 if (region_parity[info.region] == -1) {
2972 region_parity[info.region] = info.parity;
2973 }
2974 }
2975
2976 flood_fill_region_values<int8_t>(region_pair_flip,
2977 region_parity,
2978 int8_t(-1),
2979 [](int8_t cur, int8_t flip) { return int8_t(cur ^ flip); });
2980
2981 /* Apply hole status. A region is a hole when its parity is 0 (even crossings from
2982 * outer_face) or -1 (no constrained-edge path back to any boundary, so still zero
2983 * crossings). The single `!= 1` test covers both. */
2984 for (CDTFace<T> *f : cdt->faces) {
2985 const int region = f->visit_index;
2986 if (region >= 0) {
2987 f->hole = (region_parity[region] != 1);
2988 }
2989 }
2990}
2991
2999template<typename T> void detect_holes_with_fillrule_nonzero(CDT_state<T> *cdt_state)
3000{
3002 /* Algorithm:
3003 * - Flood-fill faces into regions (connected through non-constrained edges).
3004 * - For each region, seed its winding from boundary edges into `outer_face`.
3005 * - Build region adjacency graph with per-edge signed winding deltas.
3006 * - Propagate: S.winding = R.winding + delta(R->S).
3007 * - A region is a hole if its winding is 0 (or unreachable from outer).
3008 *
3009 * Unlike even-odd (which only toggles), non-zero accumulates signed winding through
3010 * the region graph - which is what lets overlapping faces produce correct fills rather
3011 * than just a boolean hole status.
3012 *
3013 * Complexity: `O(F + E)` where F = faces, E = edges.
3014 */
3015
3016 CDTArrangement<T> *cdt = &cdt_state->cdt;
3017
3018 /* Crossing direction convention used when populating the region adjacency below:
3019 * - Edge `winding > 0` means net CCW traversal from `symedge[0].vert` to `symedge[1].vert`.
3020 * - Crossing from `symedge[0].face` side INTO `symedge[1].face` side: subtract winding.
3021 * - Crossing from `symedge[1].face` side INTO `symedge[0].face` side: add winding.
3022 */
3023
3024 /* Boundary regions are those touching outer_face. We collect them during flood-fill
3025 * to avoid a separate pass over all edges. */
3026 struct BoundaryRegionInfo {
3027 int region;
3028 int winding; /* Initial winding from crossing outer boundary. */
3029 };
3030 Vector<BoundaryRegionInfo> boundary_regions;
3031
3032 /* Flood-fill faces into regions (faces connected through non-constrained edges).
3033 * During flood-fill, we also detect regions touching outer_face and compute their
3034 * initial winding. */
3035 Vector<CDTFace<T> *> fstack;
3036 fstack.reserve(cdt->faces.size()); /* Worst case: all faces in stack. */
3037 for (CDTFace<T> *f : cdt->faces) {
3039 }
3040 cdt->outer_face->visit_index = VISIT_INDEX_OUTER_FACE;
3041
3042 int cur_region = -1;
3043 for (CDTFace<T> *f_init : cdt->faces) {
3044 if (f_init->deleted || !f_init->symedge || f_init->visit_index != VISIT_INDEX_UNVISITED) {
3045 continue;
3046 }
3047 cur_region++;
3048 /* Mark-on-push: visit_index is assigned the moment a face is queued, never on pop.
3049 * This guarantees each face is pushed at most once, removing the per-pop recheck. */
3050 f_init->visit_index = cur_region;
3051 fstack.append(f_init);
3052 bool found_constrained_outer = false;
3053 bool found_any_outer = false;
3054 int outer_winding = 0;
3055
3056 while (!fstack.is_empty()) {
3057 CDTFace<T> *f = fstack.pop_last();
3058 BLI_assert(f->visit_index == cur_region);
3059
3060 SymEdge<T> *se_start = f->symedge;
3061 SymEdge<T> *se = se_start;
3062 do {
3063 if (!se->edge) {
3064 continue;
3065 }
3066 CDTFace<T> *neighbor = sym(se)->face;
3067 if (!neighbor) {
3068 continue;
3069 }
3070 /* NOTE: Loose edges (input edges not part of any face) are not supported.
3071 * To support them, they would need winding values assigned here. */
3072 if (is_constrained_edge(se->edge)) {
3073 if (neighbor == cdt->outer_face && !found_constrained_outer) {
3074 /* Constrained edge to outer face: a polygon boundary on the convex hull.
3075 * Compute initial winding from crossing into this region from outside.
3076 *
3077 * We only use the first constrained outer edge found. For simply-connected
3078 * regions (all CDT regions), a ray from inside to infinity crosses the outer
3079 * boundary once, so this matches ray-casting behavior. If multiple outer
3080 * edges exist with different windings (ambiguous overlapping input), the
3081 * result depends on which edge is encountered first - same as ray-casting
3082 * depends on ray direction. */
3083 found_constrained_outer = true;
3084 found_any_outer = true;
3085 const int winding = cdt_state->edge_winding_map->lookup_default(se->edge, 0);
3086 /* If our face is `symedges[0].face`, outer is `symedges[1].face`.
3087 * Crossing INTO our region from `outer = side1` -> `side0 = +winding`. */
3088 if (&se->edge->symedges[0] == se) {
3089 outer_winding = winding;
3090 }
3091 else {
3092 outer_winding = -winding;
3093 }
3094 }
3095 }
3096 else if (neighbor == cdt->outer_face) {
3097 /* Unconstrained edge to outer face: a convex hull edge that isn't a polygon
3098 * boundary. This region is outside all input polygons so its winding is 0
3099 * (the initialized value of `outer_winding`). A constrained outer edge takes
3100 * priority since it carries the actual winding from crossing a polygon boundary. */
3101 found_any_outer = true;
3102 }
3103 else if (!neighbor->deleted && neighbor->visit_index == VISIT_INDEX_UNVISITED) {
3104 neighbor->visit_index = cur_region;
3105 fstack.append(neighbor);
3106 }
3107 } while ((se = se->next) != se_start);
3108 }
3109
3110 if (found_any_outer) {
3111 boundary_regions.append({cur_region, outer_winding});
3112 }
3113 }
3114
3115 const int num_regions = ++cur_region;
3116 cdt_state->visit_count = num_regions;
3117 if (num_regions == 0) {
3118 return;
3119 }
3120
3121 /* Build region adjacency graph with winding deltas.
3122 *
3123 * For each pair of adjacent regions, we need ONE representative edge's winding delta.
3124 * A ray from inside one region to the other crosses exactly one constraint edge (for
3125 * simply-connected regions in CDT), so we use the first edge encountered between each
3126 * pair. The edge_winding_map already accounts for multiple input faces sharing an edge. */
3127
3128 /* Store one winding delta per region pair using a map.
3129 * Key: `(region_src, region_dst)`, Value: `winding_delta` from the first edge found. */
3130 Map<int2, int> region_pair_winding;
3131 /* Reserve based on region count: ~3 edges per region, 2 entries per edge.
3132 * This is an absolute floor (actual count is likely larger),
3133 * but avoids re-allocations at small values. */
3134 region_pair_winding.reserve(6 * num_regions);
3135
3136 for (CDTEdge<T> *e : cdt->edges) {
3138 continue;
3139 }
3140 const int region0 = e->symedges[0].face->visit_index;
3141 const int region1 = e->symedges[1].face->visit_index;
3142
3143 /* Skip edges within same region, or involving outer/unprocessed faces. */
3144 if (region0 == region1 || region0 < 0 || region1 < 0) {
3145 continue;
3146 }
3147
3148 const int winding = cdt_state->edge_winding_map->lookup_default(e, 0);
3149 const int delta_0_to_1 = -winding; /* Crossing from face0 to face1. */
3150 const int delta_1_to_0 = winding; /* Crossing from face1 to face0. */
3151
3152 /* Use first edge found for each direction. Multiple edges between the same regions
3153 * (e.g., 4 sides of an inner square) should all have consistent winding for valid input,
3154 * so we only need one. Using `add` ignores subsequent edges if key already exists. */
3155 region_pair_winding.add(int2(region0, region1), delta_0_to_1);
3156 region_pair_winding.add(int2(region1, region0), delta_1_to_0);
3157 }
3158
3159 /* Seed boundary regions with the winding from crossing the outer boundary. */
3160 Array<int> region_winding(num_regions);
3161 region_winding.fill(INT_MIN); /* INT_MIN = unknown / unreachable. */
3162 for (const BoundaryRegionInfo &info : boundary_regions) {
3163 if (region_winding[info.region] == INT_MIN) {
3164 region_winding[info.region] = info.winding;
3165 }
3166 }
3167
3168 /* Propagate winding through the region graph from the boundary seeds. */
3169 flood_fill_region_values<int>(region_pair_winding,
3170 region_winding,
3171 INT_MIN,
3172 [](int cur, int delta) { return cur + delta; });
3173
3174 /* Apply hole status to faces. Hole if winding == 0 (or unreachable). */
3175 for (CDTFace<T> *f : cdt->faces) {
3176 const int region = f->visit_index;
3177 if (region >= 0) {
3178 const int winding = region_winding[region];
3179 f->hole = (ELEM(winding, 0, INT_MIN));
3180 }
3181 }
3182}
3183
3188template<typename T>
3189void prepare_cdt_for_output(CDT_state<T> *cdt_state, const CDT_output_type output_type)
3190{
3192 CDTArrangement<T> *cdt = &cdt_state->cdt;
3193 if (cdt->edges.is_empty()) {
3194 return;
3195 }
3196
3197 /* Make sure all non-deleted faces have a symedge. */
3198 for (CDTEdge<T> *e : cdt->edges) {
3199 if (!is_deleted_edge(e)) {
3200 if (e->symedges[0].face->symedge == nullptr) {
3201 e->symedges[0].face->symedge = &e->symedges[0];
3202 }
3203 if (e->symedges[1].face->symedge == nullptr) {
3204 e->symedges[1].face->symedge = &e->symedges[1];
3205 }
3206 }
3207 }
3208
3209 /* Determine if hole detection is needed and which winding rule to use. */
3210 if (output_uses_evenodd_holes(output_type)) {
3212 }
3213 else if (output_uses_nonzero_holes(output_type)) {
3215 }
3216
3217 if (output_type == CDT_CONSTRAINTS) {
3218 remove_non_constraint_edges(cdt_state);
3219 }
3220 else if (output_type == CDT_CONSTRAINTS_VALID_BMESH) {
3222 }
3223 else if (output_type == CDT_INSIDE) {
3225 }
3228 remove_faces_in_holes(cdt_state);
3229 }
3230 else if (ELEM(output_type,
3233 {
3236 remove_faces_in_holes(cdt_state);
3237 }
3238}
3239
3240template<typename T>
3242{
3244 CDT_output_type oty = output_type;
3245 prepare_cdt_for_output(cdt_state, oty);
3247 CDTArrangement<T> *cdt = &cdt_state->cdt;
3248 result.face_edge_offset = cdt_state->face_edge_offset;
3249
3250 /* All verts without a merge_to_index will be output.
3251 * vert_to_output_map[i] will hold the output vertex index
3252 * corresponding to the vert in position i in cdt->verts.
3253 * This first loop sets vert_to_output_map for un-merged verts. */
3254 int verts_size = cdt->verts.size();
3255 Array<int> vert_to_output_map(verts_size);
3256 int nv = 0;
3257 for (int i = 0; i < verts_size; ++i) {
3258 CDTVert<T> *v = cdt->verts[i];
3259 if (v->merge_to_index == -1) {
3260 vert_to_output_map[i] = nv;
3261 ++nv;
3262 }
3263 }
3264 if (nv <= 0) {
3265 return result;
3266 }
3267 /* Now we can set vert_to_output_map for merged verts,
3268 * and also add the input indices of merged verts to the input_ids
3269 * list of the merge target if they were an original input id. */
3270 if (nv < verts_size) {
3271 for (int i = 0; i < verts_size; ++i) {
3272 CDTVert<T> *v = cdt->verts[i];
3273 if (v->merge_to_index != -1) {
3274 if (cdt_state->needed_ids & CDT_ORIG_VERTS) {
3275 if (i < cdt_state->input_vert_num) {
3276 add_to_input_ids(cdt->verts[v->merge_to_index]->input_ids, uint32_t(i));
3277 }
3278 }
3279 vert_to_output_map[i] = vert_to_output_map[v->merge_to_index];
3280 }
3281 }
3282 }
3283 result.vert = Array<VecBase<T, 2>>(nv);
3284 if (cdt_state->needed_ids & CDT_ORIG_VERTS) {
3285 result.vert_orig = Array<Vector<uint32_t>>(nv);
3286 }
3287 if (cdt_state->needed_ids & CDT_INTERSECTED_EDGES) {
3288 result.intersected_edges_orig = Array<int2>(nv, {-1, -1});
3289 }
3290 int i_out = 0;
3291 for (int i = 0; i < verts_size; ++i) {
3292 CDTVert<T> *v = cdt->verts[i];
3293 if (v->merge_to_index == -1) {
3294 result.vert[i_out] = v->co.exact;
3295 if (cdt_state->needed_ids & CDT_ORIG_VERTS) {
3296 if (i < cdt_state->input_vert_num) {
3297 result.vert_orig[i_out].append(uint32_t(i));
3298 }
3299 result.vert_orig[i_out].extend(v->input_ids.as_span());
3300 }
3301 if (cdt_state->needed_ids & CDT_INTERSECTED_EDGES) {
3302 result.intersected_edges_orig[i_out] = v->intersected_edges;
3303 }
3304 ++i_out;
3305 }
3306 }
3307
3308 /* All non-deleted edges will be output. */
3309 int ne = std::count_if(cdt->edges.begin(), cdt->edges.end(), [](const CDTEdge<T> *e) -> bool {
3310 return !is_deleted_edge(e);
3311 });
3312 result.edge = Array<int2>(ne);
3313 if (cdt_state->needed_ids & CDT_ORIG_EDGES) {
3314 result.edge_orig = Array<Vector<uint32_t>>(ne);
3315 }
3316 int e_out = 0;
3317 for (const CDTEdge<T> *e : cdt->edges) {
3318 if (!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];
3321 result.edge[e_out] = int2(vo1, vo2);
3322 if (cdt_state->needed_ids & CDT_ORIG_EDGES) {
3323 result.edge_orig[e_out].extend(e->input_ids.as_span());
3324 }
3325 ++e_out;
3326 }
3327 }
3328
3329 /* All non-deleted, non-outer faces will be output. */
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;
3332 });
3333 result.face = Array<Vector<int>>(nf);
3334 if (cdt_state->needed_ids & CDT_ORIG_FACES) {
3335 result.face_orig = Array<Vector<uint32_t>>(nf);
3336 }
3337 int f_out = 0;
3338 for (const CDTFace<T> *f : cdt->faces) {
3339 if (!f->deleted && f != cdt->outer_face) {
3340 SymEdge<T> *se = f->symedge;
3341 BLI_assert(se != nullptr);
3342 SymEdge<T> *se_start = se;
3343 do {
3344 result.face[f_out].append(vert_to_output_map[se->vert->index]);
3345 se = se->next;
3346 } while (se != se_start);
3347 if (cdt_state->needed_ids & CDT_ORIG_FACES) {
3348 result.face_orig[f_out].extend(f->input_ids.as_span());
3349 }
3350 ++f_out;
3351 }
3352 }
3353 return result;
3354}
3355
3360template<typename T> void add_input_verts(CDT_state<T> *cdt_state, const CDT_input<T> &input)
3361{
3362 for (int i = 0; i < cdt_state->input_vert_num; ++i) {
3363 cdt_state->cdt.add_vert(input.vert[i]);
3364 }
3365}
3366
3367template<typename T>
3369{
3371 int nv = input.vert.size();
3372 int ne = input.edge.size();
3373 int nf = input.face_offsets.size();
3374 CDT_state<T> cdt_state(nv, ne, nf, input.epsilon, input.needed_ids);
3375 const bool need_winding = output_uses_nonzero_holes(output_type);
3376 const bool need_polygon_boundary_count = output_uses_evenodd_holes(output_type);
3377
3378 /* Only constructed if winding is needed. */
3379 std::optional<Map<CDTEdge<T> *, int>> edge_winding_map;
3380 if (need_winding) {
3381 BLI_assert(cdt_state.edge_winding_map == nullptr);
3382 edge_winding_map.emplace();
3383 cdt_state.edge_winding_map = &edge_winding_map.value();
3384 }
3385
3386 /* Only constructed if even-odd hole detection runs. */
3387 std::optional<Map<CDTEdge<T> *, int>> polygon_boundary_count_map;
3388 if (need_polygon_boundary_count) {
3389 BLI_assert(cdt_state.polygon_boundary_count_map == nullptr);
3390 polygon_boundary_count_map.emplace();
3391 cdt_state.polygon_boundary_count_map = &polygon_boundary_count_map.value();
3392 }
3393
3394 add_input_verts(&cdt_state, input);
3395 initial_triangulation(&cdt_state.cdt);
3396 add_edge_constraints(&cdt_state, input);
3397 int actual_nf = add_face_constraints(&cdt_state, input, output_type, need_winding);
3398 if (actual_nf == 0 && !ELEM(output_type, CDT_FULL, CDT_INSIDE, CDT_CONSTRAINTS)) {
3399 /* Can't look for faces or holes if there were no valid input faces. */
3400 output_type = CDT_INSIDE;
3401 }
3402 return get_cdt_output(&cdt_state, output_type);
3403}
3404
3405template<typename T>
3407{
3408 return delaunay_calc(input, output_type);
3409}
3410
3412
3413#ifdef WITH_GMP
3415#endif
3416
3417} // namespace blender::meshintersect
Math vector functions needed specifically for mesh intersect and boolean.
#define PRF_scope(category)
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_AS_INT(i)
#define ELEM(...)
Array(Allocator allocator={}) noexcept
Definition BLI_array.hh:78
void fill(const T &value) const
Definition BLI_array.hh:283
bool add(const Key &key, const Value &value)
Definition BLI_map.hh:295
Value lookup_default(const Key &key, const Value &default_value) const
Definition BLI_map.hh:570
KeyIterator keys() const &
Definition BLI_map.hh:875
void reserve(int64_t n)
Definition BLI_map.hh:1028
ItemIterator items() const &
Definition BLI_map.hh:902
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
bool add(const Key &key)
void add_multiple(Span< Key > keys)
int64_t size() const
Span< Key > as_span() const
int64_t size() const
void append(const T &value)
bool is_empty() const
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
Map< CDTEdge< T > *, int > * polygon_boundary_count_map
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)
#define SY(y)
#define SX(x)
float dot(VecOp< float, D >, VecOp< float, D >) RET
#define abs
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)
Definition math_dual.h:241
#define T
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 > &region_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)
__int64 int64_t
Definition BKE_text.h:90
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_INSIDE_WITH_HOLES
@ 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)
unsigned int uint32_t
Definition BKE_text.h:81
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
signed char int8_t
Definition BKE_text.h:76
struct BMEdge * e
struct LinkNode * next
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)
CDTEdge< T > * add_vert_to_symedge_edge(CDTVert< T > *v, SymEdge< T > *se)
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)
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)