Blender V5.3
BLI_delaunay_2d_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include "testing/testing.h"
6
7#include "MEM_guardedalloc.h"
8
9#include "BLI_rand_c.hh"
10#include "BLI_time.hh"
11
12#include <fstream>
13#include <iostream>
14#include <sstream>
15#include <type_traits>
16
17#define DO_CPP_TESTS 1
18#define DO_TEXT_TESTS 0
19#define DO_RANDOM_TESTS 0
20
21#include "BLI_array.hh"
22#include "BLI_math_boolean.hh"
23#include "BLI_math_mpq.hh"
25#include "BLI_vector.hh"
26
27#include "BLI_delaunay_2d.hh"
28
29namespace blender::meshintersect {
30
37
38/* The spec should have the form:
39 * #verts #edges #faces
40 * <float> <float> [#verts lines]
41 * <int> <int> [#edges lines]
42 * <int> <int> ... <int> [#faces lines]
43 */
44template<typename T>
46{
47 std::istringstream ss(spec);
48 std::string line;
49 getline(ss, line);
50 std::istringstream hdrss(line);
51 int nverts, nedges, nfaces;
52 hdrss >> nverts >> nedges >> nfaces;
53 if (nverts == 0) {
54 return CDT_input<T>();
55 }
56 r_storage.vert.reinitialize(nverts);
57 r_storage.edge.reinitialize(nedges);
58 r_storage.face_offsets.reinitialize(nfaces + 1);
59 int i = 0;
60 while (i < nverts && getline(ss, line)) {
61 std::istringstream iss(line);
62 double dp0, dp1;
63 iss >> dp0 >> dp1;
64 T p0(dp0);
65 T p1(dp1);
66 r_storage.vert[i] = VecBase<T, 2>(p0, p1);
67 i++;
68 }
69 i = 0;
70 while (i < nedges && getline(ss, line)) {
71 std::istringstream ess(line);
72 int e0, e1;
73 ess >> e0 >> e1;
74 r_storage.edge[i] = int2(e0, e1);
75 i++;
76 }
77 i = 0;
78 while (i < nfaces && getline(ss, line)) {
79 r_storage.face_offsets[i] = r_storage.face_vert_indices.size();
80 std::istringstream fss(line);
81 int v;
82 while (fss >> v) {
83 r_storage.face_vert_indices.append(v);
84 }
85 i++;
86 }
87 r_storage.face_offsets.last() = r_storage.face_vert_indices.size();
88
89 CDT_input<T> ans;
90 ans.vert = r_storage.vert;
91 ans.edge = r_storage.edge;
92 ans.face_offsets = r_storage.face_offsets.as_span();
95#ifdef WITH_GMP
96 if (std::is_same_v<mpq_class, T>) {
97 ans.epsilon = T(0);
98 }
99 else {
100 ans.epsilon = T(0.00001);
101 }
102#else
103 ans.epsilon = T(0.00001);
104#endif
105 return ans;
106}
107
108/* Find an original index in a table mapping new to original.
109 * Return -1 if not found.
110 */
111[[maybe_unused]]
112static int get_orig_index(const Span<Vector<uint32_t>> out_to_orig, int orig_index)
113{
114 int n = int(out_to_orig.size());
115 for (int i = 0; i < n; ++i) {
116 for (uint32_t orig : out_to_orig[i]) {
117 if (orig == uint32_t(orig_index)) {
118 return i;
119 }
120 }
121 }
122 return -1;
123}
124
125template<typename T> static double math_to_double(const T /*v*/)
126{
127 BLI_assert(false); /* Need implementation for other type. */
128 return 0.0;
129}
130
131template<> double math_to_double<double>(const double v)
132{
133 return v;
134}
135
136#ifdef WITH_GMP
137template<> double math_to_double<mpq_class>(const mpq_class v)
138{
139 return v.get_d();
140}
141#endif
142
143template<typename T> static T math_abs(const T v);
144
145#ifdef WITH_GMP
146template<> mpq_class math_abs(const mpq_class v)
147{
148 return abs(v);
149}
150#endif
151
152template<> double math_abs(const double v)
153{
154 return fabs(v);
155}
156
157/* Find an output index corresponding to a given coordinate (approximately).
158 * Return -1 if not found.
159 */
160template<typename T> int get_vertex_by_coord(const CDT_result<T> &out, double x, double y)
161{
162 int nv = int(out.vert.size());
163 for (int i = 0; i < nv; ++i) {
164 double vx = math_to_double(out.vert[i][0]);
165 double vy = math_to_double(out.vert[i][1]);
166 if (fabs(vx - x) <= 1e-5 && fabs(vy - y) <= 1e-5) {
167 return i;
168 }
169 }
170 return -1;
171}
172
173/* Find an edge between two given output vertex indices. -1 if not found, */
174template<typename T>
175int get_output_edge_index(const CDT_result<T> &out, int out_index_1, int out_index_2)
176{
177 int ne = int(out.edge.size());
178 for (int i = 0; i < ne; ++i) {
179 if ((out.edge[i][0] == out_index_1 && out.edge[i][1] == out_index_2) ||
180 (out.edge[i][0] == out_index_2 && out.edge[i][1] == out_index_1))
181 {
182 return i;
183 }
184 }
185 return -1;
186}
187
188template<typename T>
190 int out_vert_index,
191 int in_edge1_index,
192 int in_edge2_index)
193{
194 return out_vert_index < int(out.vert_orig.size()) &&
195 out_vert_index < int(out.intersected_edges_orig.size()) &&
196 out.intersected_edges_orig[out_vert_index][0] == in_edge1_index &&
197 out.intersected_edges_orig[out_vert_index][1] == in_edge2_index;
198}
199
200template<typename T>
201bool output_edge_has_input_id(const CDT_result<T> &out, int out_edge_index, uint32_t in_edge_index)
202{
203 return out_edge_index < int(out.edge_orig.size()) &&
204 out.edge_orig[out_edge_index].contains(in_edge_index);
205}
206
207/* Which out face is for a give output vertex ngon? -1 if not found.
208 * Allow for cyclic shifts vertices of one poly vs the other.
209 */
210template<typename T> int get_output_face_index(const CDT_result<T> &out, const Array<int> &poly)
211{
212 int nf = int(out.face.size());
213 int npolyv = int(poly.size());
214 for (int f = 0; f < nf; ++f) {
215 if (out.face[f].size() != poly.size()) {
216 continue;
217 }
218 for (int cycle_start = 0; cycle_start < npolyv; ++cycle_start) {
219 bool ok = true;
220 for (int k = 0; ok && k < npolyv; ++k) {
221 if (out.face[f][(cycle_start + k) % npolyv] != poly[k]) {
222 ok = false;
223 }
224 }
225 if (ok) {
226 return f;
227 }
228 }
229 }
230 return -1;
231}
232
233template<typename T>
235 int out_index_1,
236 int out_index_2,
237 int out_index_3)
238{
239 Array<int> tri{out_index_1, out_index_2, out_index_3};
240 return get_output_face_index(out, tri);
241}
242
243template<typename T>
244bool output_face_has_input_id(const CDT_result<T> &out, int out_face_index, uint32_t in_face_index)
245{
246 return out_face_index < int(out.face_orig.size()) &&
247 out.face_orig[out_face_index].contains(in_face_index);
248}
249
250/* For debugging. */
251template<typename T> std::ostream &operator<<(std::ostream &os, const CDT_result<T> &r)
252{
253 os << "\nRESULT\n";
254 os << r.vert.size() << " verts, " << r.edge.size() << " edges, " << r.face.size() << " faces\n";
255 os << "\nVERTS\n";
256 for (int i : r.vert.index_range()) {
257 os << "v" << i << " = " << r.vert[i] << "\n";
258 os << " orig: ";
259 for (int j : r.vert_orig[i].index_range()) {
260 os << r.vert_orig[i][j] << " ";
261 }
262 os << "\n";
263 }
264 os << "\nEDGES\n";
265 for (int i : r.edge.index_range()) {
266 os << "e" << i << " = (" << r.edge[i][0] << ", " << r.edge[i][1] << ")\n";
267 os << " orig: ";
268 for (int j : r.edge_orig[i].index_range()) {
269 os << r.edge_orig[i][j] << " ";
270 }
271 os << "\n";
272 }
273 os << "\nFACES\n";
274 for (int i : r.face.index_range()) {
275 os << "f" << i << " = ";
276 for (int j : r.face[i].index_range()) {
277 os << r.face[i][j] << " ";
278 }
279 os << "\n";
280 os << " orig: ";
281 for (int j : r.face_orig[i].index_range()) {
282 os << r.face_orig[i][j] << " ";
283 }
284 os << "\n";
285 }
286 return os;
287}
288
289static bool draw_append = false; /* Will be set to true after first call. */
290
291template<typename T>
292void graph_draw(const std::string &label,
293 const Span<VecBase<T, 2>> verts,
294 const Span<int2> edges,
295 const Span<Vector<int>> faces)
296{
297 /* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library.
298 * This is just for developer debugging anyway, and should never be called in production Blender.
299 */
300#ifdef WIN32
301 constexpr const char *drawfile = "./cdt_test_draw.html";
302#else
303 constexpr const char *drawfile = "/tmp/cdt_test_draw.html";
304#endif
305 constexpr int max_draw_width = 1400;
306 constexpr int max_draw_height = 1000;
307 constexpr int thin_line = 1;
308 constexpr int vert_radius = 3;
309 constexpr bool draw_vert_labels = false;
310 constexpr bool draw_edge_labels = false;
311
312 if (verts.is_empty()) {
313 return;
314 }
315 double2 vmin(1e10, 1e10);
316 double2 vmax(-1e10, -1e10);
317 for (const VecBase<T, 2> &v : verts) {
318 for (int i = 0; i < 2; ++i) {
319 double dvi = math_to_double(v[i]);
320 if (dvi < vmin[i]) {
321 vmin[i] = dvi;
322 }
323 if (dvi > vmax[i]) {
324 vmax[i] = dvi;
325 }
326 }
327 }
328 double draw_margin = ((vmax.x - vmin.x) + (vmax.y - vmin.y)) * 0.05;
329 double minx = vmin.x - draw_margin;
330 double maxx = vmax.x + draw_margin;
331 double miny = vmin.y - draw_margin;
332 double maxy = vmax.y + draw_margin;
333
334 double width = maxx - minx;
335 double height = maxy - miny;
336 double aspect = height / width;
337 int view_width = max_draw_width;
338 int view_height = int(view_width * aspect);
339 if (view_height > max_draw_height) {
340 view_height = max_draw_height;
341 view_width = int(view_height / aspect);
342 }
343 double scale = view_width / width;
344
345#define SX(x) ((math_to_double(x) - minx) * scale)
346#define SY(y) ((maxy - math_to_double(y)) * scale)
347
348 std::ofstream f;
349 if (draw_append) {
350 f.open(drawfile, std::ios_base::app);
351 }
352 else {
353 f.open(drawfile);
354 }
355 if (!f) {
356 std::cout << "Could not open file " << drawfile << "\n";
357 return;
358 }
359
360 f << "<div>" << label << "</div>\n<div>\n"
361 << "<svg version=\"1.1\" "
362 "xmlns=\"http://www.w3.org/2000/svg\" "
363 "xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
364 "xml:space=\"preserve\"\n"
365 << "width=\"" << view_width << "\" height=\"" << view_height << "\">n";
366
367 for (const int i : faces.index_range()) {
368 f << "<polygon fill=\"azure\" stroke=\"none\"\n points=\"";
369 for (int vi : faces[i]) {
370 const VecBase<T, 2> &co = verts[vi];
371 f << SX(co[0]) << "," << SY(co[1]) << " ";
372 }
373 f << "\"\n />\n";
374 }
375
376 for (const int2 &e : edges) {
377 const VecBase<T, 2> &uco = verts[e[0]];
378 const VecBase<T, 2> &vco = verts[e[1]];
379 int strokew = thin_line;
380 f << R"(<line fill="none" stroke="black" stroke-width=")" << strokew << "\" x1=\""
381 << SX(uco[0]) << "\" y1=\"" << SY(uco[1]) << "\" x2=\"" << SX(vco[0]) << "\" y2=\""
382 << SY(vco[1]) << "\">\n";
383 f << " <title>[" << e[0] << "][" << e[1] << "]</title>\n";
384 f << "</line>\n";
385 if (draw_edge_labels) {
386 f << "<text x=\"" << SX(0.5 * (uco[0] + vco[0])) << "\" y=\"" << SY(0.5 * (uco[1] + vco[1]))
387 << R"(" font-size="small">)";
388 f << "[" << e[0] << "][" << e[1] << "]</text>\n";
389 }
390 }
391
392 int i = 0;
393 for (const VecBase<T, 2> &vco : verts) {
394 f << R"(<circle fill="black" cx=")" << SX(vco[0]) << "\" cy=\"" << SY(vco[1]) << "\" r=\""
395 << vert_radius << "\">\n";
396 f << " <title>[" << i << "]" << vco << "</title>\n";
397 f << "</circle>\n";
398 if (draw_vert_labels) {
399 f << "<text x=\"" << SX(vco[0]) + vert_radius << "\" y=\"" << SY(vco[1]) - vert_radius
400 << R"(" font-size="small">[)" << i << "]</text>\n";
401 }
402 ++i;
403 }
404
405 draw_append = true;
406#undef SX
407#undef SY
408}
409
410/* Should tests draw their output to an html file? */
411constexpr bool DO_DRAW = false;
412
413template<typename T>
414void expect_coord_near(const VecBase<T, 2> &testco, const VecBase<T, 2> &refco);
415
416#ifdef WITH_GMP
417template<> void expect_coord_near<mpq_class>(const mpq2 &testco, const mpq2 &refco)
418{
419 EXPECT_EQ(testco[0], refco[0]);
420 EXPECT_EQ(testco[0], refco[0]);
421}
422#endif
423
424template<> void expect_coord_near<double>(const double2 &testco, const double2 &refco)
425{
426 EXPECT_NEAR(testco[0], refco[0], 1e-5);
427 EXPECT_NEAR(testco[1], refco[1], 1e-5);
428}
429
430#if DO_CPP_TESTS
431
432template<typename T> void empty_test()
433{
435
437 EXPECT_EQ(0, out.vert.size());
438 EXPECT_EQ(0, out.edge.size());
439 EXPECT_EQ(0, out.face.size());
440 EXPECT_EQ(0, out.vert_orig.size());
441 EXPECT_EQ(0, out.edge_orig.size());
442 EXPECT_EQ(0, out.face_orig.size());
443}
444
445template<typename T> void onept_test()
446{
447 const char *spec = R"(1 0 0
448 0.0 0.0
449 )";
450 InputStorage<T> store;
453 EXPECT_EQ(out.vert.size(), 1);
454 EXPECT_EQ(out.edge.size(), 0);
455 EXPECT_EQ(out.face.size(), 0);
456 if (out.vert.size() >= 1) {
457 expect_coord_near<T>(out.vert[0], VecBase<T, 2>(0, 0));
458 }
460
461template<typename T> void twopt_test()
462{
463 const char *spec = R"(2 0 0
464 0.0 -0.75
465 0.0 0.75
466 )";
467 InputStorage<T> store;
468 CDT_input<T> in = fill_input_from_string<T>(spec, store);
469 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
470 EXPECT_EQ(out.vert.size(), 2);
471 EXPECT_EQ(out.edge.size(), 1);
472 EXPECT_EQ(out.face.size(), 0);
473 int v0_out = get_orig_index(out.vert_orig, 0);
474 int v1_out = get_orig_index(out.vert_orig, 1);
475 EXPECT_NE(v0_out, -1);
476 EXPECT_NE(v1_out, -1);
477 EXPECT_NE(v0_out, v1_out);
478 if (out.vert.size() >= 1) {
479 expect_coord_near<T>(out.vert[v0_out], VecBase<T, 2>(0.0, -0.75));
480 expect_coord_near<T>(out.vert[v1_out], VecBase<T, 2>(0.0, 0.75));
481 }
482 int e0_out = get_output_edge_index(out, v0_out, v1_out);
483 EXPECT_EQ(e0_out, 0);
484 if (DO_DRAW) {
485 graph_draw<T>("TwoPt", out.vert, out.edge, out.face);
486 }
487}
488
489template<typename T> void threept_test()
490{
491 const char *spec = R"(3 0 0
492 -0.1 -0.75
493 0.1 0.75
494 0.5 0.5
495 )";
496 InputStorage<T> store;
497 CDT_input<T> in = fill_input_from_string<T>(spec, store);
498 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
499 EXPECT_EQ(out.vert.size(), 3);
500 EXPECT_EQ(out.edge.size(), 3);
501 EXPECT_EQ(out.face.size(), 1);
502 int v0_out = get_orig_index(out.vert_orig, 0);
503 int v1_out = get_orig_index(out.vert_orig, 1);
504 int v2_out = get_orig_index(out.vert_orig, 2);
505 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1);
506 EXPECT_TRUE(v0_out != v1_out && v0_out != v2_out && v1_out != v2_out);
507 int e0_out = get_output_edge_index(out, v0_out, v1_out);
508 int e1_out = get_output_edge_index(out, v1_out, v2_out);
509 int e2_out = get_output_edge_index(out, v2_out, v0_out);
510 EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
511 EXPECT_TRUE(e0_out != e1_out && e0_out != e2_out && e1_out != e2_out);
512 int f0_out = get_output_tri_index(out, v0_out, v2_out, v1_out);
513 EXPECT_EQ(f0_out, 0);
514 if (DO_DRAW) {
515 graph_draw<T>("ThreePt", out.vert, out.edge, out.face);
516 }
517}
518
519template<typename T> void mixedpts_test()
520{
521 /* Edges form a chain of length 3. */
522 const char *spec = R"(4 3 0
523 0.0 0.0
524 -0.5 -0.5
525 -0.4 -0.25
526 -0.3 0.8
527 0 1
528 1 2
529 2 3
530 )";
531 InputStorage<T> store;
532 CDT_input<T> in = fill_input_from_string<T>(spec, store);
533 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
534 EXPECT_EQ(out.vert.size(), 4);
535 EXPECT_EQ(out.edge.size(), 6);
536 int v0_out = get_orig_index(out.vert_orig, 0);
537 int v1_out = get_orig_index(out.vert_orig, 1);
538 int v2_out = get_orig_index(out.vert_orig, 2);
539 int v3_out = get_orig_index(out.vert_orig, 3);
540 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
541 int e0_out = get_output_edge_index(out, v0_out, v1_out);
542 int e1_out = get_output_edge_index(out, v1_out, v2_out);
543 int e2_out = get_output_edge_index(out, v2_out, v3_out);
544 EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
548 if (DO_DRAW) {
549 graph_draw<T>("MixedPts", out.vert, out.edge, out.face);
550 }
552
553template<typename T> void quad0_test()
554{
555 const char *spec = R"(4 0 0
556 0.0 1.0
557 1.0 0.0
558 2.0 0.1
559 2.25 0.5
560 )";
561 InputStorage<T> store;
562 CDT_input<T> in = fill_input_from_string<T>(spec, store);
563 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
564 EXPECT_EQ(out.vert.size(), 4);
565 EXPECT_EQ(out.edge.size(), 5);
566 int e_diag_out = get_output_edge_index(out, 1, 3);
567 EXPECT_NE(e_diag_out, -1);
568 if (DO_DRAW) {
569 graph_draw<T>("Quad0", out.vert, out.edge, out.face);
570 }
571}
572
573template<typename T> void quad1_test()
574{
575 const char *spec = R"(4 0 0
576 0.0 0.0
577 0.9 -1.0
578 2.0 0.0
579 0.9 3.0
580 )";
584 EXPECT_EQ(out.vert.size(), 4);
585 EXPECT_EQ(out.edge.size(), 5);
586 int e_diag_out = get_output_edge_index(out, 0, 2);
587 EXPECT_NE(e_diag_out, -1);
588 if (DO_DRAW) {
589 graph_draw<T>("Quad1", out.vert, out.edge, out.face);
590 }
591}
592
593template<typename T> void quad2_test()
594{
595 const char *spec = R"(4 0 0
596 0.5 0.0
597 0.15 0.2
598 0.3 0.4
599 .45 0.35
600 )";
601 InputStorage<T> store;
604 EXPECT_EQ(out.vert.size(), 4);
605 EXPECT_EQ(out.edge.size(), 5);
606 int e_diag_out = get_output_edge_index(out, 1, 3);
607 EXPECT_NE(e_diag_out, -1);
608 if (DO_DRAW) {
609 graph_draw<T>("Quad2", out.vert, out.edge, out.face);
610 }
612
613template<typename T> void quad3_test()
614{
615 const char *spec = R"(4 0 0
616 0.5 0.0
617 0.0 0.0
618 0.3 0.4
619 .45 0.35
620 )";
621 InputStorage<T> store;
622 CDT_input<T> in = fill_input_from_string<T>(spec, store);
623 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
624 EXPECT_EQ(out.vert.size(), 4);
625 EXPECT_EQ(out.edge.size(), 5);
626 int e_diag_out = get_output_edge_index(out, 0, 2);
627 EXPECT_NE(e_diag_out, -1);
628 if (DO_DRAW) {
629 graph_draw<T>("Quad3", out.vert, out.edge, out.face);
630 }
631}
632
633template<typename T> void quad4_test()
634{
635 const char *spec = R"(4 0 0
636 1.0 1.0
637 0.0 0.0
638 1.0 -3.0
639 0.0 1.0
640 )";
641 InputStorage<T> store;
644 EXPECT_EQ(out.vert.size(), 4);
645 EXPECT_EQ(out.edge.size(), 5);
646 int e_diag_out = get_output_edge_index(out, 0, 1);
647 EXPECT_NE(e_diag_out, -1);
648 if (DO_DRAW) {
649 graph_draw<T>("Quad4", out.vert, out.edge, out.face);
650 }
651}
652
653template<typename T> void lineinsquare_test()
654{
655 const char *spec = R"(6 1 1
656 -0.5 -0.5
657 0.5 -0.5
658 -0.5 0.5
659 0.5 0.5
660 -0.25 0.0
661 0.25 0.0
662 4 5
663 0 1 3 2
664 )";
665 InputStorage<T> store;
666 CDT_input<T> in = fill_input_from_string<T>(spec, store);
667 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
668 EXPECT_EQ(out.vert.size(), 6);
669 EXPECT_EQ(out.face.size(), 6);
670 if (DO_DRAW) {
671 graph_draw<T>("LineInSquare - full", out.vert, out.edge, out.face);
672 }
674 EXPECT_EQ(out2.vert.size(), 6);
675 EXPECT_EQ(out2.face.size(), 1);
676 if (DO_DRAW) {
677 graph_draw<T>("LineInSquare - constraints", out2.vert, out2.edge, out2.face);
678 }
679 CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
680 EXPECT_EQ(out3.vert.size(), 6);
681 EXPECT_EQ(out3.face.size(), 6);
682 if (DO_DRAW) {
683 graph_draw<T>("LineInSquare - inside with holes", out3.vert, out3.edge, out3.face);
684 }
686 EXPECT_EQ(out4.vert.size(), 6);
687 EXPECT_EQ(out4.face.size(), 2);
688 if (DO_DRAW) {
689 graph_draw<T>("LineInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
690 }
691}
692
693template<typename T> void lineholeinsquare_test()
694{
695 const char *spec = R"(10 1 2
696 -0.5 -0.5
697 0.5 -0.5
698 -0.5 0.5
699 0.5 0.5
700 -0.25 0.0
701 0.25 0.0
702 -0.4 -0.4
703 0.4 -0.4
704 0.4 -0.3
705 -0.4 -0.3
706 4 5
707 0 1 3 2
708 6 7 8 9
709 )";
710 InputStorage<T> store;
713 EXPECT_EQ(out.vert.size(), 10);
714 EXPECT_EQ(out.face.size(), 14);
715 if (DO_DRAW) {
716 graph_draw<T>("LineHoleInSquare - full", out.vert, out.edge, out.face);
717 }
719 EXPECT_EQ(out2.vert.size(), 10);
720 EXPECT_EQ(out2.face.size(), 2);
721 if (DO_DRAW) {
722 graph_draw<T>("LineHoleInSquare - constraints", out2.vert, out2.edge, out2.face);
723 }
725 EXPECT_EQ(out3.vert.size(), 10);
726 EXPECT_EQ(out3.face.size(), 12);
727 if (DO_DRAW) {
728 graph_draw<T>("LineHoleInSquare - inside with holes", out3.vert, out3.edge, out3.face);
731 EXPECT_EQ(out4.vert.size(), 10);
732 EXPECT_EQ(out4.face.size(), 2);
733 if (DO_DRAW) {
734 graph_draw<T>("LineHoleInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
735 }
736}
737
738template<typename T> void nestedholes_test()
739{
740 const char *spec = R"(12 0 3
741 -0.5 -0.5
742 0.5 -0.5
743 -0.5 0.5
744 0.5 0.5
745 -0.4 -0.4
746 0.4 -0.4
747 0.4 0.4
748 -0.4 0.4
749 -0.2 -0.2
750 0.2 -0.2
751 0.2 0.2
752 -0.2 0.2
753 0 1 3 2
754 4 7 6 5
755 8 9 10 11
756 )";
757 InputStorage<T> store;
760 EXPECT_EQ(out.vert.size(), 12);
761 EXPECT_EQ(out.face.size(), 18);
762 if (DO_DRAW) {
763 graph_draw<T>("NestedHoles - full", out.vert, out.edge, out.face);
764 }
766 EXPECT_EQ(out2.vert.size(), 12);
767 EXPECT_EQ(out2.face.size(), 3);
768 if (DO_DRAW) {
769 graph_draw<T>("NestedHoles - constraints", out2.vert, out2.edge, out2.face);
770 }
772 EXPECT_EQ(out3.vert.size(), 12);
773 EXPECT_EQ(out3.face.size(), 10);
774 {
775 int v8 = get_orig_index(out3.vert_orig, 8);
776 int v9 = get_orig_index(out3.vert_orig, 9);
777 int v10 = get_orig_index(out3.vert_orig, 10);
778 int v11 = get_orig_index(out3.vert_orig, 11);
779 EXPECT_NE(v8, -1);
780 EXPECT_NE(v9, -1);
781 EXPECT_NE(v10, -1);
782 EXPECT_NE(v11, -1);
783
784 int f_inner_a = get_output_tri_index(out3, v8, v9, v10);
785 int f_inner_b = get_output_tri_index(out3, v8, v10, v11);
786 int f_inner_c = get_output_tri_index(out3, v8, v9, v11);
787 int f_inner_d = get_output_tri_index(out3, v9, v10, v11);
788 EXPECT_TRUE((f_inner_a != -1 && f_inner_b != -1) || (f_inner_c != -1 && f_inner_d != -1));
789
790 bool found_face_2 = false;
791 for (int f = 0; f < int(out3.face.size()); f++) {
792 if (output_face_has_input_id(out3, f, 2)) {
793 found_face_2 = true;
794 break;
795 }
796 }
797 EXPECT_TRUE(found_face_2);
798 }
799 if (DO_DRAW) {
800 graph_draw<T>("NestedHoles - inside with holes", out3.vert, out3.edge, out3.face);
801 }
803 EXPECT_EQ(out4.vert.size(), 12);
804 EXPECT_EQ(out4.face.size(), 3);
805 if (DO_DRAW) {
806 graph_draw<T>("NestedHoles - valid bmesh with holes", out4.vert, out4.edge, out4.face);
807 }
808}
809
810template<typename T> void even_odd_nested_holes_deep_test()
811{
812 /* Five concentric squares - one nesting level deeper than `NestedHoles`. Filled bands are
813 * the outermost ring, the third ring, and the innermost square; the second and fourth
814 * rings are holes. An off-by-one in the parity XOR would mis-fill an alternate ring. */
815 const char *spec = R"(20 0 5
816 -0.5 -0.5
817 0.5 -0.5
818 0.5 0.5
819 -0.5 0.5
820 -0.4 -0.4
821 0.4 -0.4
822 0.4 0.4
823 -0.4 0.4
824 -0.3 -0.3
825 0.3 -0.3
826 0.3 0.3
827 -0.3 0.3
828 -0.2 -0.2
829 0.2 -0.2
830 0.2 0.2
831 -0.2 0.2
832 -0.1 -0.1
833 0.1 -0.1
834 0.1 0.1
835 -0.1 0.1
836 0 1 2 3
837 4 5 6 7
838 8 9 10 11
839 12 13 14 15
840 16 17 18 19
841 )";
842
843 InputStorage<T> store;
846
847 /* Three filled bands: outermost ring (8 tris), middle filled ring (8 tris),
848 * innermost square (2 tris) -> 18 triangles total. */
849 EXPECT_EQ(out.vert.size(), 20);
850 EXPECT_EQ(out.face.size(), 18);
851
852 /* Innermost square (input ids 16..19) must be present and filled. */
853 int v_i[4];
854 for (int k = 0; k < 4; k++) {
855 v_i[k] = get_orig_index(out.vert_orig, k + 16);
856 EXPECT_NE(v_i[k], -1);
857 }
858 bool inner_a = get_output_tri_index(out, v_i[0], v_i[1], v_i[2]) != -1 &&
859 get_output_tri_index(out, v_i[0], v_i[2], v_i[3]) != -1;
860 bool inner_b = get_output_tri_index(out, v_i[0], v_i[1], v_i[3]) != -1 &&
861 get_output_tri_index(out, v_i[1], v_i[2], v_i[3]) != -1;
862 EXPECT_TRUE(inner_a || inner_b);
863
864 /* Innermost-square input-id (4) appears on at least one output face. */
865 bool found_inner_id = false;
866 for (int f = 0; f < int(out.face.size()); f++) {
867 if (output_face_has_input_id(out, f, 4)) {
868 found_inner_id = true;
869 break;
870 }
871 }
872 EXPECT_TRUE(found_inner_id);
873
874 /* The ring between sq1 and sq2 (input ids 1 and 2) must be a hole - no output face is
875 * "inside sq1 but not sq2". Without this, a buggy `{ring2, ring3, innermost}` fill would
876 * pass the count + innermost checks (8 + 8 + 2 = 18, innermost filled). */
877 bool found_ring2_face = false;
878 for (int f = 0; f < int(out.face.size()); f++) {
880 found_ring2_face = true;
881 break;
882 }
883 }
884 EXPECT_FALSE(found_ring2_face);
885
886 if (DO_DRAW) {
887 graph_draw<T>("EvenOddNestedHolesDeep", out.vert, out.edge, out.face);
888 }
889}
890
891template<typename T> void even_odd_boundary_disagreement_test()
892{
893 /* Outer rectangle (input id 0) and inner rectangle (input id 1) sharing a portion of the
894 * convex hull. The inner's bottom edge `(1,0)-(3,0)` lies on the outer's bottom edge
895 * `(0,0)-(4,0)`, so the CDT splits the bottom hull at verts 4 and 5 and produces three
896 * boundary edges with mixed multiplicities:
897 * `(0,0)-(1,0)` and `(3,0)-(4,0)` carry only the outer polygon -> flip 1.
898 * `(1,0)-(3,0)` carries both polygons -> flip 0.
899 * The "inside outer, outside inner" flood-region thus has multiple boundary edges to
900 * `outer_face` with mixed flips, so the boundary-disagreement branch in
901 * `detect_holes_with_fillrule_even_odd` is reachable on this input.
902 *
903 * Note: this test pins the *output* ("inside outer, outside inner" filled, "inside inner"
904 * a hole) on a specific input that exercises the disagreement branch; it does not by
905 * itself distinguish "filled wins" from a hypothetical "first wins" rule, since for this
906 * input the `cdt->edges` iteration order happens to visit a flip=1 edge first. A more
907 * discriminating test would need to control that order. */
908 const char *spec = R"(8 0 2
909 0 0
910 4 0
911 4 2
912 0 2
913 1 0
914 3 0
915 3 1
916 1 1
917 0 1 2 3
918 4 5 6 7
919 )";
920
921 InputStorage<T> store;
924
925 /* All 8 input verts survive. Total Delaunay triangles with `H = 6` hull verts (the four
926 * outer corners plus 4 and 5, both collinear on the bottom hull) is `2V - H - 2 = 8`.
927 * The 2 inner-rectangle triangles are holes; the remaining 6 in the U-shaped outer region
928 * survive. */
929 EXPECT_EQ(out.vert.size(), 8);
930 EXPECT_EQ(out.face.size(), 6);
931
932 /* Every output face is inside the outer polygon (input id 0) and none is inside the
933 * inner one (input id 1). A regression that flipped the conflict-resolution rule and
934 * marked the outer region as a hole would invert this: only the 2 inner-rect triangles
935 * would survive and all output faces would have input id 1. */
936 for (int f = 0; f < int(out.face.size()); f++) {
939 }
940
941 if (DO_DRAW) {
942 graph_draw<T>("EvenOddBoundaryDisagreement", out.vert, out.edge, out.face);
944}
945
946/* Outer 4x4 rect plus a 2x2 inner rect listed twice.
947 *
948 * Ensure fixed:
949 *
950 * - Outer edges count 1 (flip 1), inner edges count 2 (flip 0): outer ring reaches
951 * parity 1 from `outer_face`, "inside inner" inherits via flip 0. All 10 triangles
952 * filled.
953 * - Even-odd is independent of `needed_ids`: the detector reads `polygon_boundary_count_map`,
954 * not `CDTEdge::input_ids` (which collapses when `needed_ids = 0`). */
956{
957 const char *spec = R"(8 0 3
958 0.0 0.0
959 4.0 0.0
960 4.0 4.0
961 0.0 4.0
962 1.0 1.0
963 3.0 1.0
964 3.0 3.0
965 1.0 3.0
966 0 1 2 3
967 4 5 6 7
968 4 5 6 7
969 )";
971 InputStorage<T> store_with_ids;
972 CDT_input<T> in_with_ids = fill_input_from_string<T>(spec, store_with_ids);
973 in_with_ids.needed_ids = CDT_ORIG_FACES;
974 CDT_result<T> out_with_ids = delaunay_2d_calc(in_with_ids, CDT_INSIDE_WITH_HOLES);
975
976 InputStorage<T> store_no_ids;
977 CDT_input<T> in_no_ids = fill_input_from_string<T>(spec, store_no_ids);
978 in_no_ids.needed_ids = CDT_NO_ORIG_IDS;
980
981 /* V=8, H=4 hull -> 2V - H - 2 = 10 triangles. */
982 EXPECT_EQ(out_with_ids.vert.size(), 8);
983 EXPECT_EQ(out_with_ids.face.size(), 10);
984
985 EXPECT_EQ(out_no_ids.vert.size(), out_with_ids.vert.size());
986 EXPECT_EQ(out_no_ids.edge.size(), out_with_ids.edge.size());
987 EXPECT_EQ(out_no_ids.face.size(), out_with_ids.face.size());
988
989 /* Non-zero fills everywhere too (outer ring winding +1, inside inner +3). */
991 EXPECT_EQ(out_nonzero.vert.size(), 8);
992 EXPECT_EQ(out_nonzero.face.size(), 10);
993
994 if (DO_DRAW) {
995 graph_draw<T>("EvenOddCoincidentPolygonsNeedIdsStable - even-odd",
996 out_with_ids.vert,
997 out_with_ids.edge,
998 out_with_ids.face);
999 graph_draw<T>("EvenOddCoincidentPolygonsNeedIdsStable - non-zero",
1000 out_nonzero.vert,
1001 out_nonzero.edge,
1002 out_nonzero.face);
1003 }
1004}
1005
1006
1011template<typename T> void cw_orig_face_ids_test()
1012{
1013 const char *spec = R"(8 0 2
1014 0.0 0.0
1015 4.0 0.0
1016 4.0 4.0
1017 0.0 4.0
1018 1.0 1.0
1019 1.0 3.0
1020 3.0 3.0
1021 3.0 1.0
1022 0 1 2 3
1023 4 5 6 7
1024 )";
1025
1026 InputStorage<T> store_ccw_ids;
1027 CDT_input<T> in_ccw_ids = fill_input_from_string<T>(spec, store_ccw_ids);
1028 in_ccw_ids.needed_ids = CDT_ORIG_FACES;
1029 CDT_result<T> out_ccw_ids = delaunay_2d_calc(in_ccw_ids, CDT_INSIDE_WITH_HOLES);
1030
1031 InputStorage<T> store_cw_ids;
1032 CDT_input<T> in_cw_ids = fill_input_from_string<T>(spec, store_cw_ids);
1034 CDT_result<T> out_cw_ids = delaunay_2d_calc(in_cw_ids, CDT_INSIDE_WITH_HOLES);
1035
1036 EXPECT_EQ(out_ccw_ids.face.size(), 8);
1037 EXPECT_EQ(out_cw_ids.face.size(), out_ccw_ids.face.size());
1038
1039 for (const int f : out_ccw_ids.face.index_range()) {
1040 EXPECT_TRUE(output_face_has_input_id(out_ccw_ids, f, 0));
1041 EXPECT_FALSE(output_face_has_input_id(out_ccw_ids, f, 1));
1042 }
1043 for (const int f : out_cw_ids.face.index_range()) {
1044 EXPECT_TRUE(output_face_has_input_id(out_cw_ids, f, 0));
1045 EXPECT_TRUE(output_face_has_input_id(out_cw_ids, f, 1));
1046 }
1047}
1048
1050
1053template<typename T> void looping_back_2x_test()
1055 const char *spec = R"(6 0 1
1056 1.0 0.0
1057 0.5 1.0
1058 -0.5 1.0
1059 -1.0 0.0
1060 -0.5 -1.0
1061 0.5 -1.0
1062 0 1 2 3 4 5 0 1 2 3 4 5
1063 )";
1064 InputStorage<T> store;
1066 in.needed_ids = CDT_NO_ORIG_IDS;
1068 EXPECT_EQ(out.vert.size(), 6);
1069 EXPECT_EQ(out.edge.size(), 6);
1070 EXPECT_EQ(out.face.size(), 0);
1071}
1072
1076template<typename T> void looping_back_3x_test()
1077{
1078 const char *spec = R"(6 0 1
1079 1.0 0.0
1080 0.5 1.0
1081 -0.5 1.0
1082 -1.0 0.0
1083 -0.5 -1.0
1084 0.5 -1.0
1085 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
1086 )";
1087 InputStorage<T> store;
1088 CDT_input<T> in = fill_input_from_string<T>(spec, store);
1089 in.needed_ids = CDT_NO_ORIG_IDS;
1091 EXPECT_EQ(out.vert.size(), 6);
1092 EXPECT_EQ(out.edge.size(), 6);
1093 EXPECT_EQ(out.face.size(), 1);
1094}
1095
1100template<typename T> void looping_back_hole_2x_test()
1101{
1102 const char *spec = R"(10 0 2
1103 -2.0 -2.0
1104 2.0 -2.0
1105 2.0 2.0
1106 -2.0 2.0
1107 1.0 0.0
1108 0.5 1.0
1109 -0.5 1.0
1110 -1.0 0.0
1111 -0.5 -1.0
1112 0.5 -1.0
1113 0 1 2 3
1114 4 5 6 7 8 9 4 5 6 7 8 9
1115 )";
1116 InputStorage<T> store;
1117 CDT_input<T> in = fill_input_from_string<T>(spec, store);
1118 in.needed_ids = CDT_NO_ORIG_IDS;
1120 EXPECT_EQ(out.vert.size(), 10);
1121 EXPECT_EQ(out.edge.size(), 12);
1122 EXPECT_EQ(out.face.size(), 3);
1123}
1124
1128template<typename T> void looping_back_hole_3x_test()
1129{
1130 const char *spec = R"(10 0 2
1131 -2.0 -2.0
1132 2.0 -2.0
1133 2.0 2.0
1134 -2.0 2.0
1135 1.0 0.0
1136 0.5 1.0
1137 -0.5 1.0
1138 -1.0 0.0
1139 -0.5 -1.0
1140 0.5 -1.0
1141 0 1 2 3
1142 4 5 6 7 8 9 4 5 6 7 8 9 4 5 6 7 8 9
1143 )";
1144 InputStorage<T> store;
1146 in.needed_ids = CDT_NO_ORIG_IDS;
1148 EXPECT_EQ(out.vert.size(), 10);
1149 EXPECT_EQ(out.edge.size(), 12);
1150 EXPECT_EQ(out.face.size(), 2);
1151}
1152
1153template<typename T> void disjoint_polys_in_large_hull_test()
1154{
1155 const char *spec = R"(6 0 2
1156 0.0 0.0
1157 1.0 0.0
1158 0.5 1.0
1159 3.0 0.0
1160 4.0 0.0
1161 3.5 1.0
1162 0 1 2
1163 3 4 5
1164 )";
1165
1166 InputStorage<T> store;
1168
1170 EXPECT_EQ(out.vert.size(), 6);
1171 EXPECT_EQ(out.face.size(), 2);
1172
1173 int verts[6];
1174 for (int i = 0; i < 6; i++) {
1175 verts[i] = get_orig_index(out.vert_orig, i);
1176 EXPECT_NE(verts[i], -1);
1177 }
1178
1179 int f_a = get_output_tri_index(out, verts[0], verts[1], verts[2]);
1180 int f_b = get_output_tri_index(out, verts[3], verts[4], verts[5]);
1181 EXPECT_NE(f_a, -1);
1182 EXPECT_NE(f_b, -1);
1185
1186 /* The non-zero rule gets count checks only, not per-face checks.
1187 * The optimization being validated lives in the even-odd path.
1188 * the non-zero check exists only to confirm this geometry does
1189 * not distinguish the two rules. */
1190 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
1191 EXPECT_EQ(out_nonzero.vert.size(), 6);
1192 EXPECT_EQ(out_nonzero.face.size(), 2);
1193
1194 if (DO_DRAW) {
1195 graph_draw<T>("DisjointPolysInLargeHull", out.vert, out.edge, out.face);
1196 }
1197}
1198
1199/* Two overlapping squares with the same winding direction (both CCW).
1200 * Even-odd: overlap region is excluded (2 crossings = outside).
1201 * Non-zero: overlap region is included (winding = 2 = inside). */
1202template<typename T> void nonzero_winding_test()
1203{
1204 /* Square 1: (0,0)-(1,1) CCW, Square 2: (0.5,0.5)-(1.5,1.5) CCW. */
1205 const char *spec = R"(8 0 2
1206 0.0 0.0
1207 1.0 0.0
1208 1.0 1.0
1209 0.0 1.0
1210 0.5 0.5
1211 1.5 0.5
1212 1.5 1.5
1213 0.5 1.5
1214 0 1 2 3
1215 4 5 6 7
1216 )";
1217
1218 InputStorage<T> store;
1220
1221 /* Even-odd: the overlap region (0.5,0.5)-(1,1) is a hole. */
1223 EXPECT_EQ(out_evenodd.vert.size(), 10); /* 8 input + 2 intersections */
1224 if (DO_DRAW) {
1226 "NonZeroWinding - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
1227 }
1228
1229 /* Non-zero: overlapping same-winding squares union. */
1230 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
1231 EXPECT_EQ(out_nonzero.vert.size(), 10); /* 8 input + 2 intersections */
1232 if (DO_DRAW) {
1234 "NonZeroWinding - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
1235 }
1236
1237 /* Non-zero should have more faces than even-odd (union vs hole in overlap). */
1238 EXPECT_EQ(out_evenodd.face.size(), 8);
1239 EXPECT_EQ(out_nonzero.face.size(), 10);
1240
1241 /* Verify non-zero rule is winding-independent: flipping all face windings
1242 * should produce identical results since we only check if winding == 0. */
1243 Vector<int> indices_flipped = store.face_vert_indices;
1244 for (const int i : in.face_offsets.index_range()) {
1245 std::ranges::reverse(indices_flipped.as_mutable_span().slice(in.face_offsets[i]));
1246 }
1247 CDT_input<T> in_flipped = in;
1248 in_flipped.face_vert_indices = indices_flipped;
1250 EXPECT_EQ(out_flipped.vert.size(), out_nonzero.vert.size());
1251 EXPECT_EQ(out_flipped.face.size(), out_nonzero.face.size());
1252}
1253
1254/* One square inside another - tests hole creation with winding rules.
1255 * Outer square CCW, inner square CW (opposite winding) = inner is a hole.
1256 * Outer square CCW, inner square CCW (same winding) = inner is filled. */
1257template<typename T> void nonzero_winding_nested_test()
1258{
1259 /* Outer square (0,0)-(2,2) CCW, inner square (0.5,0.5)-(1.5,1.5) CW. */
1260 const char *spec_hole = R"(8 0 2
1261 0.0 0.0
1262 2.0 0.0
1263 2.0 2.0
1264 0.0 2.0
1265 0.5 0.5
1266 0.5 1.5
1267 1.5 1.5
1268 1.5 0.5
1269 0 1 2 3
1270 4 5 6 7
1271 )";
1272
1273 InputStorage<T> spec, store_hole;
1274 CDT_input<T> in_hole = fill_input_from_string<T>(spec_hole, store_hole);
1275
1276 /* Even-odd: inner square is a hole (2 crossings = outside). */
1277 CDT_result<T> out_evenodd_hole = delaunay_2d_calc(in_hole, CDT_INSIDE_WITH_HOLES);
1278 EXPECT_EQ(out_evenodd_hole.vert.size(), 8);
1279 if (DO_DRAW) {
1280 graph_draw<T>("NonZeroWindingNested - even-odd, inner CW (hole)",
1281 out_evenodd_hole.vert,
1282 out_evenodd_hole.edge,
1283 out_evenodd_hole.face);
1284 }
1285
1286 /* Non-zero: inner CW square creates a hole (winding: +1 - 1 = 0). */
1288 EXPECT_EQ(out_nonzero_hole.vert.size(), 8);
1289 if (DO_DRAW) {
1290 graph_draw<T>("NonZeroWindingNested - non-zero, inner CW (hole)",
1291 out_nonzero_hole.vert,
1292 out_nonzero_hole.edge,
1293 out_nonzero_hole.face);
1294 }
1295
1296 /* Both rules produce same face count when inner has opposite winding. */
1297 EXPECT_EQ(out_evenodd_hole.face.size(), 8);
1298 EXPECT_EQ(out_nonzero_hole.face.size(), out_evenodd_hole.face.size());
1299
1300 /* Now test with inner square also CCW (same winding as outer). */
1301 const char *spec_filled = R"(8 0 2
1302 0.0 0.0
1303 2.0 0.0
1304 2.0 2.0
1305 0.0 2.0
1306 0.5 0.5
1307 1.5 0.5
1308 1.5 1.5
1309 0.5 1.5
1310 0 1 2 3
1311 4 5 6 7
1312 )";
1313
1314 InputStorage<T> store_filled;
1315 CDT_input<T> in_filled = fill_input_from_string<T>(spec_filled, store_filled);
1316
1317 /* Even-odd: inner square is still a hole (2 crossings = outside). */
1318 CDT_result<T> out_evenodd_filled = delaunay_2d_calc(in_filled, CDT_INSIDE_WITH_HOLES);
1319 EXPECT_EQ(out_evenodd_filled.vert.size(), 8);
1320 if (DO_DRAW) {
1321 graph_draw<T>("NonZeroWindingNested - even-odd, inner CCW (hole)",
1322 out_evenodd_filled.vert,
1323 out_evenodd_filled.edge,
1324 out_evenodd_filled.face);
1325 }
1326
1327 /* Non-zero: inner CCW square is filled (winding: +1 + 1 = 2 = inside). */
1328 CDT_result<T> out_nonzero_filled = delaunay_2d_calc(in_filled, CDT_INSIDE_WITH_HOLES_NONZERO);
1329 EXPECT_EQ(out_nonzero_filled.vert.size(), 8);
1330 if (DO_DRAW) {
1331 graph_draw<T>("NonZeroWindingNested - non-zero, inner CCW (filled)",
1332 out_nonzero_filled.vert,
1333 out_nonzero_filled.edge,
1334 out_nonzero_filled.face);
1335 }
1336
1337 /* Non-zero should have more faces (inner filled vs inner hole). */
1338 EXPECT_EQ(out_evenodd_filled.face.size(), 8);
1339 EXPECT_EQ(out_nonzero_filled.face.size(), 10);
1340}
1341
1382template<typename T> void nonzero_winding_nested_union_test()
1383{
1384 const char *spec = R"(16 0 4
1385 0.0 0.0
1386 4.0 0.0
1387 4.0 4.0
1388 0.0 4.0
1389 0.5 0.5
1390 0.5 3.5
1391 3.5 3.5
1392 3.5 0.5
1393 1.0 1.0
1394 2.5 1.0
1395 2.5 2.5
1396 1.0 2.5
1397 1.5 1.5
1398 3.0 1.5
1399 3.0 3.0
1400 1.5 3.0
1401 0 1 2 3
1402 4 5 6 7
1403 8 9 10 11
1404 12 13 14 15
1405 )";
1406
1407 InputStorage<T> store;
1409
1410 /* Even-odd: inner overlap has 4 crossings (outer, hole, inner1, inner2) = outside. */
1412 EXPECT_EQ(out_evenodd.vert.size(), 18); /* 16 input + 2 intersections */
1413 if (DO_DRAW) {
1414 graph_draw<T>("NonZeroWindingNestedUnion - even-odd",
1415 out_evenodd.vert,
1416 out_evenodd.edge,
1417 out_evenodd.face);
1418 }
1419
1420 /* Non-zero: inner squares union.
1421 * Winding in overlap: outer(+1) + hole(-1) + inner1(+1) + inner2(+1) = +2 = inside. */
1423 EXPECT_EQ(out_nonzero.vert.size(), 18); /* 16 input + 2 intersections */
1424 if (DO_DRAW) {
1425 graph_draw<T>("NonZeroWindingNestedUnion - non-zero",
1426 out_nonzero.vert,
1427 out_nonzero.edge,
1428 out_nonzero.face);
1429 }
1430
1431 /* Non-zero should have more faces (union vs hole in overlap). */
1432 EXPECT_EQ(out_evenodd.face.size(), 16);
1433 EXPECT_EQ(out_nonzero.face.size(), 18);
1434}
1435
1463
1472template<typename T> void nonzero_winding_multi_face_edge_test()
1473{
1474 const char *spec = R"(8 0 3
1475 0.0 0.0
1476 3.0 0.0
1477 3.0 1.0
1478 0.0 1.0
1479 3.0 2.0
1480 0.0 2.0
1481 3.0 3.0
1482 0.0 3.0
1483 0 1 2 3
1484 0 1 4 5
1485 0 1 6 7
1486 )";
1487
1488 InputStorage<T> store;
1489 CDT_input<T> in = fill_input_from_string<T>(spec, store);
1490
1491 CDT_result<T> out_evenodd = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
1492 if (DO_DRAW) {
1493 graph_draw<T>("NonZeroWindingMultiFaceEdge - even-odd",
1494 out_evenodd.vert,
1495 out_evenodd.edge,
1496 out_evenodd.face);
1497 }
1498
1499 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
1500 if (DO_DRAW) {
1501 graph_draw<T>("NonZeroWindingMultiFaceEdge - non-zero",
1502 out_nonzero.vert,
1503 out_nonzero.edge,
1504 out_nonzero.face);
1505 }
1506
1507 /* 8 input vertices, no intersections needed. */
1508 EXPECT_EQ(out_evenodd.vert.size(), 8);
1509 EXPECT_EQ(out_nonzero.vert.size(), 8);
1510
1511 /* The 3 stacked rectangles share the bottom edge (multiplicity 3). The bottom
1512 * band (y=0..1) is inside all 3 polygons (3 crossings -> odd -> filled),
1513 * the middle band (y=1..2) is inside 2 polygons (-> hole), and the top
1514 * band (y=2..3) is inside 1 polygon (-> filled). So even-odd fills the
1515 * bottom and top bands and removes the middle band; non-zero has all
1516 * positive winding so it fills all 3 bands. */
1517 EXPECT_EQ(out_evenodd.face.size(), 4);
1518 EXPECT_EQ(out_nonzero.face.size(), 6);
1519
1520 /* Pin which 4 triangles survive in even-odd. Each band is a quadrilateral
1521 * split into 2 triangles. The bottom band uses verts 0,1,2,3; the middle
1522 * band 2,3,4,5; the top band 4,5,6,7. Even-odd output must contain the
1523 * bottom band's 2 tris and the top band's 2 tris, and must NOT contain
1524 * the middle band's 2 tris. Catches a balanced-swap bug that would
1525 * preserve the count of 4 by filling middle and removing top, for
1526 * example. */
1527 for (CDT_result<T> *out_p : {&out_evenodd, &out_nonzero}) {
1528 CDT_result<T> &out = *out_p;
1529 int verts[8];
1530 for (int i = 0; i < 8; i++) {
1531 verts[i] = get_orig_index(out.vert_orig, i);
1532 EXPECT_NE(verts[i], -1);
1533 }
1534 /* Bottom band tris (v0,v1,v3) and (v1,v2,v3): present in both rules. */
1535 EXPECT_NE(get_output_tri_index(out, verts[3], verts[0], verts[1]), -1);
1536 EXPECT_NE(get_output_tri_index(out, verts[1], verts[2], verts[3]), -1);
1537 /* Top band tris (v4,v5,v7) and (v4,v6,v7): present in both rules. */
1538 EXPECT_NE(get_output_tri_index(out, verts[7], verts[5], verts[4]), -1);
1539 EXPECT_NE(get_output_tri_index(out, verts[4], verts[6], verts[7]), -1);
1540 /* Middle band tris (v2,v3,v5) and (v2,v4,v5): present only in non-zero. */
1541 int f_mid_a = get_output_tri_index(out, verts[5], verts[3], verts[2]);
1542 int f_mid_b = get_output_tri_index(out, verts[2], verts[4], verts[5]);
1543 if (out_p == &out_evenodd) {
1544 EXPECT_EQ(f_mid_a, -1);
1545 EXPECT_EQ(f_mid_b, -1);
1546 }
1547 else {
1548 EXPECT_NE(f_mid_a, -1);
1549 EXPECT_NE(f_mid_b, -1);
1550 }
1551 }
1552}
1553
1558 * \code{.unparsed}
1559 * Geometry (same as MultiFaceEdge):
1560 * 7---------6 y=3 Face 2 (CCW)
1561 * | |
1562 * 5---------4 y=2 Face 1 (CW - reversed!)
1563 * | |
1564 * 3---------2 y=1 Face 0 (CCW)
1565 * | |
1566 * 0---------1 y=0
1567 * x=0,3
1568 * \endcode
1569 *
1570 * Edge windings:
1571 * - Bottom (0,0)->(3,0): +1 - 1 + 1 = +1.
1572 * - Edge (3,0)->(3,1): +1 - 1 + 1 = +1.
1573 * - Edge (3,1)->(3,2): -1 + 1 = 0 (key difference).
1574 * - Edge (3,2)->(3,3): +1.
1575 *
1576 * With mixed winding, the middle band [1,2] has edges with zero net winding,
1577 * so it behaves differently than the all-CCW case. This tests that winding
1578 * accumulation correctly handles cancellation from opposite-wound faces.
1579 */
1580template<typename T> void nonzero_winding_multi_face_edge_mixed_test()
1581{
1582 /* Same vertices, but face 1 is CW (reversed order). */
1583 const char *spec = R"(8 0 3
1584 0.0 0.0
1585 3.0 0.0
1586 3.0 1.0
1587 0.0 1.0
1588 3.0 2.0
1589 0.0 2.0
1590 3.0 3.0
1591 0.0 3.0
1592 0 1 2 3
1593 5 4 1 0
1594 0 1 6 7
1595 )";
1596
1597 InputStorage<T> store;
1599
1601 if (DO_DRAW) {
1602 graph_draw<T>("NonZeroWindingMultiFaceEdgeMixed - even-odd",
1603 out_evenodd.vert,
1604 out_evenodd.edge,
1605 out_evenodd.face);
1606 }
1607
1609 if (DO_DRAW) {
1610 graph_draw<T>("NonZeroWindingMultiFaceEdgeMixed - non-zero",
1611 out_nonzero.vert,
1612 out_nonzero.edge,
1613 out_nonzero.face);
1614 }
1615
1616 EXPECT_EQ(out_evenodd.vert.size(), 8);
1617 EXPECT_EQ(out_nonzero.vert.size(), 8);
1618
1619 /* Same 3-stacked-rectangles geometry as the all-CCW test, but face 1 is
1620 * declared CW (`5 4 1 0`). Even-odd is winding-independent: only the
1621 * multiplicity of each unique CDT edge matters. Edge (0,1) is still in
1622 * all 3 faces (multiplicity 3 -> flip 1) and the y=1, y=2 inner edges
1623 * still have multiplicity 2 (flip 0) - so the even-odd output is
1624 * identical to the non-mixed test: bottom band (y=0..1) and top band
1625 * (y=2..3) filled, middle band (y=1..2) is a hole. 4 triangles total.
1626 *
1627 * For non-zero, face 1's CW direction contributes -1 winding to the
1628 * middle band, cancelling face 2's +1, so the middle band has net
1629 * winding 0 and is a hole. The non-zero output is therefore *also*
1630 * 4 triangles (not 6 as in the all-CCW non-mixed test). */
1631 EXPECT_EQ(out_evenodd.face.size(), 4);
1632 EXPECT_EQ(out_nonzero.face.size(), 4);
1633
1634 /* Pin which 4 triangles are filled in both rules. Same band tris as
1635 * the non-mixed test: bottom band (verts 0,1,2,3) split into
1636 * (v0,v1,v3) and (v1,v2,v3); top band (verts 4,5,6,7) split into
1637 * (v4,v5,v7) and (v4,v6,v7). Middle band (verts 2,3,4,5) tris must
1638 * be ABSENT in both even-odd AND non-zero. */
1639 for (CDT_result<T> *out_p : {&out_evenodd, &out_nonzero}) {
1640 CDT_result<T> &out = *out_p;
1641 int verts[8];
1642 for (int i = 0; i < 8; i++) {
1643 verts[i] = get_orig_index(out.vert_orig, i);
1644 EXPECT_NE(verts[i], -1);
1645 }
1646 /* Bottom band tris (v0,v1,v3) and (v1,v2,v3): present in both rules. */
1647 EXPECT_NE(get_output_tri_index(out, verts[3], verts[0], verts[1]), -1);
1648 EXPECT_NE(get_output_tri_index(out, verts[1], verts[2], verts[3]), -1);
1649 /* Top band tris (v4,v5,v7) and (v4,v6,v7): present in both rules. */
1650 EXPECT_NE(get_output_tri_index(out, verts[7], verts[5], verts[4]), -1);
1651 EXPECT_NE(get_output_tri_index(out, verts[4], verts[6], verts[7]), -1);
1652 /* Middle band tris must be absent in both rules. */
1653 EXPECT_EQ(get_output_tri_index(out, verts[5], verts[3], verts[2]), -1);
1654 EXPECT_EQ(get_output_tri_index(out, verts[2], verts[4], verts[5]), -1);
1655 }
1656}
1657
1671 * | |
1672 * 5---------4 y=2 Face 1 (CCW, +1)
1673 * | |
1674 * 3---------2 y=1 Face 0 (CCW, +1)
1675 * | |
1676 * 0---------1 y=0
1677 * x=0,3
1678 * \endcode
1679 *
1680 * - Face 0: (0,0)-(3,1) CCW (+1).
1681 * - Face 1: (0,0)-(3,2) CCW (+1).
1682 * - Face 2: (0,0)-(3,3) CW (-1).
1683 * - Face 3: (0,0)-(3,4) CW (-1).
1684 *
1685 * Winding by y-band:
1686 * - [0,1]: All 4 faces overlap giving +1+1-1-1 = 0 (HOLE - this is correct).
1687 * - [1,2]: Faces 1,2,3 overlap giving +1-1-1 = -1 (filled).
1688 * - [2,3]: Faces 2,3 overlap giving -1-1 = -2 (filled).
1689 * - [3,4]: Only face 3 giving -1 (filled).
1690 *
1691 * EXPECTED RESULT for non-zero: bottom band [0,1] is empty, top 3 bands filled.
1692 * This looks unusual but is correct - the bottom band has winding=0 because
1693 * two CCW faces (+1+1) and two CW faces (-1-1) cancel out exactly.
1694 *
1695 * Even-odd by y-band (for comparison):
1696 * - [0,1]: 4 crossings means outside (hole).
1697 * - [1,2]: 3 crossings means inside (filled).
1698 * - [2,3]: 2 crossings means outside (hole).
1699 * - [3,4]: 1 crossing means inside (filled).
1700 */
1701template<typename T> void nonzero_winding_cancel_to_zero_test()
1702{
1703 const char *spec = R"(10 0 4
1704 0.0 0.0
1705 3.0 0.0
1706 3.0 1.0
1707 0.0 1.0
1708 3.0 2.0
1709 0.0 2.0
1710 3.0 3.0
1711 0.0 3.0
1712 3.0 4.0
1713 0.0 4.0
1714 0 1 2 3
1715 0 1 4 5
1716 7 6 1 0
1717 9 8 1 0
1718 )";
1719
1720 InputStorage<T> store;
1722
1724 if (DO_DRAW) {
1725 graph_draw<T>("NonZeroWindingCancelToZero - even-odd",
1726 out_evenodd.vert,
1727 out_evenodd.edge,
1728 out_evenodd.face);
1729 }
1730
1732 if (DO_DRAW) {
1733 graph_draw<T>("NonZeroWindingCancelToZero - non-zero",
1734 out_nonzero.vert,
1735 out_nonzero.edge,
1736 out_nonzero.face);
1737 }
1738
1739 EXPECT_EQ(out_evenodd.vert.size(), 10);
1740 EXPECT_EQ(out_nonzero.vert.size(), 10);
1741
1742 /* Non-zero fills 3 bands, even-odd fills 2 bands:
1743 * - Even-odd: [0,1] and [2,3] are holes (alternating pattern)
1744 * - Non-zero: only [0,1] is a hole (winding=0), bands [1,2],[2,3],[3,4] filled
1745 * The empty bottom band in non-zero is correct: winding cancels to zero there. */
1746 EXPECT_LT(out_evenodd.face.size(), out_nonzero.face.size());
1747}
1748
1768 * 0---------1 y=0
1769 * x=0,3
1770 * \endcode
1771 *
1772 * The bottom edge (0,0)->(3,0) has winding = +6.
1773 *
1774 * Winding by y-band (all positive, all inside for non-zero):
1775 * bands [0,1]: 6, [1,2]: 5, [2,3]: 4, [3,4]: 3, [4,5]: 2, [5,6]: 1.
1776 *
1777 * Even-odd: alternating inside/outside (odd crossings = inside).
1778 */
1779template<typename T> void nonzero_winding_high_count_test()
1780{
1781 const char *spec = R"(14 0 6
1782 0.0 0.0
1783 3.0 0.0
1784 3.0 1.0
1785 0.0 1.0
1786 3.0 2.0
1787 0.0 2.0
1788 3.0 3.0
1789 0.0 3.0
1790 3.0 4.0
1791 0.0 4.0
1792 3.0 5.0
1793 0.0 5.0
1794 3.0 6.0
1795 0.0 6.0
1796 0 1 2 3
1797 0 1 4 5
1798 0 1 6 7
1799 0 1 8 9
1800 0 1 10 11
1801 0 1 12 13
1802 )";
1803
1804 InputStorage<T> store;
1806
1808 if (DO_DRAW) {
1809 graph_draw<T>("NonZeroWindingHighCount - even-odd",
1810 out_evenodd.vert,
1811 out_evenodd.edge,
1812 out_evenodd.face);
1813 }
1814
1816 if (DO_DRAW) {
1817 graph_draw<T>("NonZeroWindingHighCount - non-zero",
1818 out_nonzero.vert,
1819 out_nonzero.edge,
1820 out_nonzero.face);
1821 }
1822
1823 EXPECT_EQ(out_evenodd.vert.size(), 14);
1824 EXPECT_EQ(out_nonzero.vert.size(), 14);
1825
1826 /* Non-zero: all bands have positive winding, all filled.
1827 * Even-odd: bands with even crossing count are holes.
1828 * Non-zero should have more faces. */
1829 EXPECT_LT(out_evenodd.face.size(), out_nonzero.face.size());
1830}
1831
1856
1863template<typename T> void nonzero_winding_fan_test()
1864{
1865 const char *spec = R"(5 0 4
1866 0.0 0.0
1867 2.0 0.0
1868 0.0 2.0
1869 -2.0 0.0
1870 0.0 -2.0
1871 0 1 2
1872 0 2 3
1873 0 3 4
1874 0 4 1
1875 )";
1876
1877 InputStorage<T> store;
1878 CDT_input<T> in = fill_input_from_string<T>(spec, store);
1879
1880 CDT_result<T> out_evenodd = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
1881 if (DO_DRAW) {
1883 "NonZeroWindingFan - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
1884 }
1885
1886 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
1887 if (DO_DRAW) {
1889 "NonZeroWindingFan - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
1890 }
1891
1892 EXPECT_EQ(out_evenodd.vert.size(), 5);
1893 EXPECT_EQ(out_nonzero.vert.size(), 5);
1894
1895 /* Spokes count 2 (flip 0), rims count 1 (flip 1). All four wedges reach parity 1 from
1896 * `outer_face` and are filled, matching non-zero. */
1897 EXPECT_EQ(out_evenodd.face.size(), 4);
1898 EXPECT_EQ(out_nonzero.face.size(), 4);
1899}
1900
1921
1926template<typename T> void nonzero_winding_edge_split_test()
1927{
1928 const char *spec = R"(8 0 2
1929 0.0 1.0
1930 2.0 1.0
1931 2.0 -1.0
1932 0.0 -1.0
1933 0.5 2.0
1934 1.5 2.0
1935 1.5 -2.0
1936 0.5 -2.0
1937 0 1 2 3
1938 4 5 6 7
1939 )";
1940
1941 InputStorage<T> store;
1942 CDT_input<T> in = fill_input_from_string<T>(spec, store);
1943
1944 CDT_result<T> out_evenodd = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
1945 if (DO_DRAW) {
1946 graph_draw<T>("NonZeroWindingEdgeSplit - even-odd",
1947 out_evenodd.vert,
1948 out_evenodd.edge,
1949 out_evenodd.face);
1950 }
1951
1953 if (DO_DRAW) {
1954 graph_draw<T>("NonZeroWindingEdgeSplit - non-zero",
1955 out_nonzero.vert,
1956 out_nonzero.edge,
1957 out_nonzero.face);
1958 }
1959
1960 /* 8 input vertices + 4 intersection points where rectangles cross. */
1961 EXPECT_EQ(out_evenodd.vert.size(), 12);
1962 EXPECT_EQ(out_nonzero.vert.size(), 12);
1963
1964 /* The overlap region has winding +2 (both CCW), so non-zero fills it.
1965 * Even-odd treats it as a hole (2 crossings = outside).
1966 * Non-zero should have more faces. */
1967 EXPECT_LT(out_evenodd.face.size(), out_nonzero.face.size());
1968}
1969
1984
1998template<typename T> void nonzero_winding_self_intersect_test()
1999{
2000 const char *spec = R"(4 0 1
2001 -1.0 -1.0
2002 1.0 1.0
2003 -1.0 1.0
2004 1.0 -1.0
2005 0 1 2 3
2006 )";
2008 InputStorage<T> store;
2010
2012 if (DO_DRAW) {
2013 graph_draw<T>("NonZeroWindingSelfIntersect - even-odd",
2014 out_evenodd.vert,
2015 out_evenodd.edge,
2016 out_evenodd.face);
2017 }
2018
2019 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2020 if (DO_DRAW) {
2021 graph_draw<T>("NonZeroWindingSelfIntersect - non-zero",
2022 out_nonzero.vert,
2023 out_nonzero.edge,
2024 out_nonzero.face);
2025 }
2026
2027 /* 4 input vertices + 1 intersection point at the crossing. */
2028 EXPECT_EQ(out_evenodd.vert.size(), 5);
2029 EXPECT_EQ(out_nonzero.vert.size(), 5);
2030
2031 /* Self-intersecting polygon creates two triangular lobes of the figure-8.
2032 * Both fill rules should produce exactly those two filled triangles. */
2033 EXPECT_EQ(out_evenodd.face.size(), 2);
2034 EXPECT_EQ(out_nonzero.face.size(), 2);
2035
2036 /* Verify the two filled faces are the top and bottom lobes, not the
2037 * side wedges (which would have the same count but wrong geometry). */
2038 int verts[4];
2039 for (int i = 0; i < 4; i++) {
2040 verts[i] = get_orig_index(out_evenodd.vert_orig, i);
2041 EXPECT_NE(verts[i], -1);
2042 }
2043
2044 /* The intersection vertex at (0, 0) is the only output vertex not
2045 * mapped from one of the four input vertices. */
2046 int v_int = -1;
2047 for (int i = 0; i < int(out_evenodd.vert.size()); i++) {
2048 if (!ELEM(i, verts[0], verts[1], verts[2], verts[3])) {
2049 v_int = i;
2050 break;
2051 }
2052 }
2053 EXPECT_NE(v_int, -1);
2054
2055 /* Top lobe: (-1,1), (1,1), (0,0) -> v2, v1, v_int.
2056 * Bottom lobe: (1,-1), (-1,-1), (0,0) -> v3, v0, v_int.
2057 * Output winding is not guaranteed; accept either orientation. */
2058 int top_lobe = get_output_tri_index(out_evenodd, verts[2], verts[1], v_int);
2059 if (top_lobe == -1) {
2060 top_lobe = get_output_tri_index(out_evenodd, verts[1], verts[2], v_int);
2061 }
2062 int bot_lobe = get_output_tri_index(out_evenodd, verts[3], verts[0], v_int);
2063 if (bot_lobe == -1) {
2064 bot_lobe = get_output_tri_index(out_evenodd, verts[0], verts[3], v_int);
2065 }
2066 EXPECT_NE(top_lobe, -1);
2067 EXPECT_NE(bot_lobe, -1);
2068}
2101template<typename T> void nonzero_winding_deep_nest_test()
2102{
2103 const char *spec = R"(20 0 5
2104 0.0 0.0
2105 10.0 0.0
2106 10.0 10.0
2107 0.0 10.0
2108 1.0 1.0
2109 1.0 9.0
2110 9.0 9.0
2111 9.0 1.0
2112 2.0 2.0
2113 8.0 2.0
2114 8.0 8.0
2115 2.0 8.0
2116 3.0 3.0
2117 3.0 7.0
2118 7.0 7.0
2119 7.0 3.0
2120 4.0 4.0
2121 6.0 4.0
2122 6.0 6.0
2123 4.0 6.0
2124 0 1 2 3
2125 4 5 6 7
2126 8 9 10 11
2127 12 13 14 15
2128 16 17 18 19
2129 )";
2130
2131 InputStorage<T> store;
2133
2135 if (DO_DRAW) {
2137 "NonZeroWindingDeepNest - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
2138 }
2139
2140 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2141 if (DO_DRAW) {
2143 "NonZeroWindingDeepNest - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
2144 }
2145
2146 EXPECT_EQ(out_evenodd.vert.size(), 20);
2147 EXPECT_EQ(out_nonzero.vert.size(), 20);
2148
2149 /* With alternating winding (CCW, CW, CCW, CW, CCW):
2150 * - Regions between levels have winding: +1, 0, +1, 0, +1
2151 * - Non-zero fills regions with winding != 0
2152 * - Even-odd fills regions with odd crossing count
2153 * Both should produce similar results for alternating pattern. */
2154 EXPECT_EQ(out_evenodd.face.size(), out_nonzero.face.size());
2155}
2156
2183template<typename T> void nonzero_winding_shared_subsegment_test()
2184{
2185 const char *spec = R"(12 0 3
2186 0.0 0.0
2187 4.0 0.0
2188 4.0 1.0
2189 0.0 1.0
2190 1.0 0.0
2191 3.0 0.0
2192 3.0 2.0
2193 1.0 2.0
2194 2.0 0.0
2195 5.0 0.0
2196 5.0 1.0
2197 2.0 1.0
2198 0 1 2 3
2199 4 5 6 7
2200 8 9 10 11
2201 )";
2202
2203 InputStorage<T> store;
2205
2207 if (DO_DRAW) {
2208 graph_draw<T>("NonZeroWindingSharedSubsegment - even-odd",
2209 out_evenodd.vert,
2210 out_evenodd.edge,
2211 out_evenodd.face);
2212 }
2213
2214 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2215 if (DO_DRAW) {
2216 graph_draw<T>("NonZeroWindingSharedSubsegment - non-zero",
2217 out_nonzero.vert,
2218 out_nonzero.edge,
2219 out_nonzero.face);
2220 }
2221
2222 /* Multiple intersection points are created where edges cross. */
2223 EXPECT_GE(out_evenodd.vert.size(), 12);
2224 EXPECT_GE(out_nonzero.vert.size(), 12);
2225
2226 /* The region where all 3 faces overlap (around x=2-3, y=0-1) has winding +3.
2227 * Non-zero fills it, while even-odd treats odd crossings as inside.
2228 * Different overlap patterns create different results. */
2229 EXPECT_NE(out_evenodd.face.size(), out_nonzero.face.size());
2230}
2231
2239 * 3-----------------------2 Face 0 (CCW, outer)
2240 * | |
2241 * | 4---------------7 | Face 1 (CW, hole)
2242 * | | | |
2243 * | | 8-------9 | | Face 2 (CCW, island)
2244 * | | | | | |
2245 * | | 11------10 | |
2246 * | | | |
2247 * | 5---------------6 |
2248 * | |
2249 * 0-----------------------1
2250 * \endcode
2251 *
2252 * - Face 0: (0,0)-(6,0)-(6,6)-(0,6) CCW is the outer boundary.
2253 * - Face 1: (1,1)-(1,5)-(5,5)-(5,1) CW is the hole (cancels outer).
2254 * - Face 2: (2,2)-(4,2)-(4,4)-(2,4) CCW is the island inside hole (re-adds winding).
2255 *
2256 * Winding:
2257 * - Outer band has winding +1 (inside).
2258 * - Hole band has winding +1-1 = 0 (outside).
2259 * - Island has winding +1-1+1 = +1 (inside).
2260 *
2261 * This pattern is common in font glyphs with counter-shapes.
2262 */
2263template<typename T> void nonzero_winding_island_in_hole_test()
2264{
2265 const char *spec = R"(12 0 3
2266 0.0 0.0
2267 6.0 0.0
2268 6.0 6.0
2269 0.0 6.0
2270 1.0 1.0
2271 1.0 5.0
2272 5.0 5.0
2273 5.0 1.0
2274 2.0 2.0
2275 4.0 2.0
2276 4.0 4.0
2277 2.0 4.0
2278 0 1 2 3
2279 4 5 6 7
2280 8 9 10 11
2281 )";
2282
2283 InputStorage<T> store;
2285
2287 if (DO_DRAW) {
2288 graph_draw<T>("NonZeroWindingIslandInHole - even-odd",
2289 out_evenodd.vert,
2290 out_evenodd.edge,
2291 out_evenodd.face);
2292 }
2293
2294 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2295 if (DO_DRAW) {
2296 graph_draw<T>("NonZeroWindingIslandInHole - non-zero",
2297 out_nonzero.vert,
2298 out_nonzero.edge,
2299 out_nonzero.face);
2300 }
2301
2302 EXPECT_EQ(out_evenodd.vert.size(), 12);
2303 EXPECT_EQ(out_nonzero.vert.size(), 12);
2304
2305 /* Both rules should produce the same result:
2306 * - Outer band is filled (1 or +1)
2307 * - Hole is empty (2 or 0)
2308 * - Island is filled (3 or +1)
2309 * This is the standard nested hole+island pattern. */
2310 EXPECT_EQ(out_evenodd.face.size(), out_nonzero.face.size());
2311}
2312
2328
2329 * \endcode
2330 *
2331 * - Face 0: Triangle with base (0,0)-(2,0), apex at (1,1), CCW, uses vertices 0,1,2.
2332 * - Face 1: Triangle with base (0,0)-(2,0), apex at (1,-1), CW, uses vertices 3,4,5.
2333 * - Vertices 0,3 are coincident (both at 0,0).
2334 * - Vertices 1,4 are coincident (both at 2,0).
2335 *
2336 * The shared edge (0,0)-(2,0) comes from two different vertex pairs that
2337 * get merged by CDT. Face 0 is CCW (+1), Face 1 is CW (-1).
2338 * The shared edge has winding +1-1 = 0.
2339 *
2340 * This tests that winding is correctly accumulated when vertex merging
2341 * creates shared edges, even when the faces have opposite orientations.
2342 */
2343template<typename T> void nonzero_winding_coincident_verts_test()
2345 const char *spec = R"(6 0 2
2346 0.0 0.0
2347 2.0 0.0
2348 1.0 1.0
2349 0.0 0.0
2350 2.0 0.0
2351 1.0 -1.0
2352 0 1 2
2353 3 4 5
2354 )";
2355
2356 InputStorage<T> store;
2358
2360 if (DO_DRAW) {
2361 graph_draw<T>("NonZeroWindingCoincidentVerts - even-odd",
2362 out_evenodd.vert,
2363 out_evenodd.edge,
2364 out_evenodd.face);
2365 }
2366
2368 if (DO_DRAW) {
2369 graph_draw<T>("NonZeroWindingCoincidentVerts - non-zero",
2370 out_nonzero.vert,
2371 out_nonzero.edge,
2372 out_nonzero.face);
2373 }
2374
2375 /* 6 input vertices but 2 pairs are coincident, so 4 unique after merging. */
2376 EXPECT_EQ(out_evenodd.vert.size(), 4);
2377 EXPECT_EQ(out_nonzero.vert.size(), 4);
2378
2379 /* Merged base edge has count 2 (flip 0); both triangles reach parity 1 via their rims
2380 * and are filled, matching non-zero. */
2381 EXPECT_EQ(out_evenodd.face.size(), 2);
2382 EXPECT_EQ(out_nonzero.face.size(), 2);
2384
2397
2398 * x=0-1 x=2-3 x=4-5 x=6-7 x=8-9
2399 * CCW CW CCW CW CCW
2400 * \endcode
2401 *
2402 * Strips have alternating CCW/CW orientation due to vertex ordering.
2403 * Since they don't overlap, each strip is independently "inside" for
2404 * both even-odd and non-zero rules (winding +/-1 != 0).
2405 * Tests that ray casting correctly handles many separate regions.
2406 */
2407template<typename T> void nonzero_winding_many_crossings_test()
2408{
2409 const char *spec = R"(20 0 5
2410 0.0 0.0
2411 1.0 0.0
2412 1.0 2.0
2413 0.0 2.0
2414 2.0 0.0
2415 2.0 2.0
2416 3.0 2.0
2417 3.0 0.0
2418 4.0 0.0
2419 5.0 0.0
2420 5.0 2.0
2421 4.0 2.0
2422 6.0 0.0
2423 6.0 2.0
2424 7.0 2.0
2425 7.0 0.0
2426 8.0 0.0
2427 9.0 0.0
2428 9.0 2.0
2429 8.0 2.0
2430 0 1 2 3
2431 4 5 6 7
2432 8 9 10 11
2433 12 13 14 15
2434 16 17 18 19
2435 )";
2436
2437 InputStorage<T> store;
2439
2441 if (DO_DRAW) {
2442 graph_draw<T>("NonZeroWindingManyCrossings - even-odd",
2443 out_evenodd.vert,
2444 out_evenodd.edge,
2445 out_evenodd.face);
2446 }
2447
2448 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2449 if (DO_DRAW) {
2450 graph_draw<T>("NonZeroWindingManyCrossings - non-zero",
2451 out_nonzero.vert,
2452 out_nonzero.edge,
2453 out_nonzero.face);
2454 }
2455
2456 EXPECT_EQ(out_evenodd.vert.size(), 20);
2457 EXPECT_EQ(out_nonzero.vert.size(), 20);
2458
2459 /* 5 non-overlapping strips with alternating CCW/CW orientation.
2460 * Both rules fill all strips (1 crossing = inside for even-odd,
2461 * winding +/-1 != 0 for non-zero). */
2462 EXPECT_EQ(out_evenodd.face.size(), out_nonzero.face.size());
2463}
2464
2495template<typename T> void nonzero_winding_negative_only_test()
2496{
2497 /* All faces are CW (vertices listed clockwise). */
2498 const char *spec = R"(8 0 3
2499 0.0 0.0
2500 3.0 0.0
2501 3.0 1.0
2502 0.0 1.0
2503 3.0 2.0
2504 0.0 2.0
2505 3.0 3.0
2506 0.0 3.0
2507 3 2 1 0
2508 5 4 1 0
2509 7 6 1 0
2510 )";
2511
2512 InputStorage<T> store;
2514
2516 if (DO_DRAW) {
2517 graph_draw<T>("NonZeroWindingNegativeOnly - even-odd",
2518 out_evenodd.vert,
2519 out_evenodd.edge,
2520 out_evenodd.face);
2521 }
2522
2523 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2524 if (DO_DRAW) {
2525 graph_draw<T>("NonZeroWindingNegativeOnly - non-zero",
2526 out_nonzero.vert,
2527 out_nonzero.edge,
2528 out_nonzero.face);
2529 }
2530
2531 EXPECT_EQ(out_evenodd.vert.size(), 8);
2532 EXPECT_EQ(out_nonzero.vert.size(), 8);
2533
2534 /* Non-zero fills all bands (winding -3, -2, -1 are all != 0).
2535 * Even-odd has holes in even-crossing bands.
2536 * Non-zero should have more faces. */
2537 EXPECT_LT(out_evenodd.face.size(), out_nonzero.face.size());
2538}
2539
2562template<typename T> void nonzero_winding_tjunction_test()
2563{
2564 const char *spec = R"(8 0 2
2565 0.0 2.0
2566 4.0 2.0
2567 4.0 0.0
2568 0.0 0.0
2569 1.0 1.0
2570 3.0 1.0
2571 3.0 0.0
2572 1.0 0.0
2573 0 1 2 3
2574 4 5 6 7
2575 )";
2576
2577 InputStorage<T> store;
2579
2581 if (DO_DRAW) {
2582 graph_draw<T>("NonZeroWindingTJunction - even-odd",
2583 out_evenodd.vert,
2584 out_evenodd.edge,
2585 out_evenodd.face);
2586 }
2587
2588 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2589 if (DO_DRAW) {
2590 graph_draw<T>("NonZeroWindingTJunction - non-zero",
2591 out_nonzero.vert,
2592 out_nonzero.edge,
2593 out_nonzero.face);
2594 }
2595
2596 /* 8 input vertices. Face 1's bottom edge shares segment with Face 0's bottom edge. */
2597 EXPECT_EQ(out_evenodd.vert.size(), 8);
2598 EXPECT_EQ(out_nonzero.vert.size(), 8);
2599
2600 /* The overlap region (1,0)-(3,1) has winding +2 (both CCW).
2601 * Non-zero fills it, even-odd treats it as a hole.
2602 * Non-zero should have more faces. */
2603 EXPECT_LT(out_evenodd.face.size(), out_nonzero.face.size());
2604}
2605
2638template<typename T> void nonzero_winding_exact_shared_edge_test()
2639{
2640 const char *spec = R"(5 0 3
2641 0.0 0.0
2642 2.0 0.0
2643 1.0 2.0
2644 1.0 -2.0
2645 1.0 1.0
2646 0 1 2
2647 0 1 4
2648 0 1 3
2649 )";
2650
2651 InputStorage<T> store;
2653
2655 if (DO_DRAW) {
2656 graph_draw<T>("NonZeroWindingExactSharedEdge - even-odd",
2657 out_evenodd.vert,
2658 out_evenodd.edge,
2659 out_evenodd.face);
2660 }
2661
2662 CDT_result<T> out_nonzero = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES_NONZERO);
2663 if (DO_DRAW) {
2664 graph_draw<T>("NonZeroWindingExactSharedEdge - non-zero",
2665 out_nonzero.vert,
2666 out_nonzero.edge,
2667 out_nonzero.face);
2668 }
2669
2670 EXPECT_EQ(out_evenodd.vert.size(), 5);
2671 EXPECT_EQ(out_nonzero.vert.size(), 5);
2672
2673 /* 3 triangles all sharing edge 0-1 with same traversal direction (+1 each).
2674 * Face 1 (small triangle) is inside Face 0 (large triangle).
2675 * Face 2 (down triangle) is separate.
2676 *
2677 * Edge 0-1 has total winding = +3.
2678 *
2679 * Even-odd: small triangle region has 2 crossings = hole
2680 * Non-zero: small triangle region has winding = 2 = inside
2681 * Non-zero should have more faces. */
2682 EXPECT_LT(out_evenodd.face.size(), out_nonzero.face.size());
2683}
2684
2686
2687 * Three corners form a triangle, three midpoints are slightly inside each edge.
2688 * The convex hull uses only the corners, so the CDT has no constrained edges
2689 * adjacent to the outer face.
2690 *
2691 * Regression test: non-zero winding hole detection must treat unconstrained
2692 * edges to the outer face as boundary regions with winding 0.
2693 * This simple polygon should triangulate to exactly 4 faces under both rules;
2694 * the broken path produced 0 faces for the non-zero case.
2695 */
2696template<typename T> void nonzero_winding_concave_outer_test()
2697{
2698 const char *spec = R"(6 0 1
2699 0 0
2700 5 1
2701 10 0
2702 7 4
2703 5 9
2704 3 4
2705 0 1 2 3 4 5
2706 )";
2707
2708 InputStorage<T> store;
2710
2713
2714 EXPECT_EQ(out_evenodd.face.size(), 4);
2715 EXPECT_EQ(out_nonzero.face.size(), 4);
2716}
2717
2718template<typename T> void crosssegs_test()
2719{
2720 const char *spec = R"(4 2 0
2721 -0.5 0.0
2722 0.5 0.0
2723 -0.4 -0.5
2724 0.4 0.5
2725 0 1
2726 2 3
2727 )";
2728 InputStorage<T> store;
2729 CDT_input<T> in = fill_input_from_string<T>(spec, store);
2730 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
2731 EXPECT_EQ(out.vert.size(), 5);
2732 EXPECT_EQ(out.edge.size(), 8);
2733 EXPECT_EQ(out.face.size(), 4);
2734 int v0_out = get_orig_index(out.vert_orig, 0);
2735 int v1_out = get_orig_index(out.vert_orig, 1);
2736 int v2_out = get_orig_index(out.vert_orig, 2);
2737 int v3_out = get_orig_index(out.vert_orig, 3);
2738 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
2739 if (out.vert.size() == 5) {
2740 int v_intersect = -1;
2741 for (int i = 0; i < 5; i++) {
2742 if (!ELEM(i, v0_out, v1_out, v2_out, v3_out)) {
2743 EXPECT_EQ(v_intersect, -1);
2744 v_intersect = i;
2745 }
2746 }
2747 EXPECT_NE(v_intersect, -1);
2748 if (v_intersect != -1) {
2749 expect_coord_near<T>(out.vert[v_intersect], VecBase<T, 2>(0, 0));
2750 }
2751 }
2752 if (DO_DRAW) {
2753 graph_draw<T>("CrossSegs", out.vert, out.edge, out.face);
2754 }
2755}
2756
2757template<typename T> void cutacrosstri_test()
2758{
2759 /* Right triangle with horizontal segment exactly crossing in the middle. */
2760 const char *spec = R"(5 1 1
2761 0.0 0.0
2762 1.0 0.0
2763 0.0 1.0
2764 0.0 0.5
2765 0.5 0.5
2766 3 4
2767 0 1 2
2768 )";
2769 InputStorage<T> store;
2772 EXPECT_EQ(out.vert.size(), 5);
2773 EXPECT_EQ(out.edge.size(), 7);
2774 EXPECT_EQ(out.face.size(), 3);
2775 int v0_out = get_orig_index(out.vert_orig, 0);
2776 int v1_out = get_orig_index(out.vert_orig, 1);
2777 int v2_out = get_orig_index(out.vert_orig, 2);
2778 int v3_out = get_orig_index(out.vert_orig, 3);
2779 int v4_out = get_orig_index(out.vert_orig, 4);
2780 EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1 && v4_out != -1);
2781 if (out.face.size() == 3) {
2782 int e0_out = get_orig_index(out.edge_orig, 0);
2783 EXPECT_NE(e0_out, -1);
2784 int fe0_out = get_output_edge_index(out, v0_out, v1_out);
2785 EXPECT_NE(fe0_out, -1);
2786 int fe1a_out = get_output_edge_index(out, v1_out, v4_out);
2787 EXPECT_NE(fe1a_out, -1);
2788 int fe1b_out = get_output_edge_index(out, v4_out, v2_out);
2789 EXPECT_NE(fe1b_out, -1);
2790 if (fe1a_out != 0 && fe1b_out != 0) {
2791 /* Face 0, edge 1 is encoded as (0 + 1) * face_edge_offset + 1. */
2792 uint32_t face0_edge1 = out.face_edge_offset + 1;
2793 EXPECT_EQ(e0_out, get_orig_index(out.edge_orig, 0));
2794 EXPECT_TRUE(out.edge_orig[fe1a_out].size() == 1 &&
2795 out.edge_orig[fe1a_out][0] == face0_edge1);
2796 EXPECT_TRUE(out.edge_orig[fe1b_out].size() == 1 &&
2797 out.edge_orig[fe1b_out][0] == face0_edge1);
2798 }
2799 int e_diag = get_output_edge_index(out, v0_out, v4_out);
2800 EXPECT_NE(e_diag, -1);
2801 if (e_diag != -1) {
2802 EXPECT_EQ(out.edge_orig[e_diag].size(), 0);
2803 }
2804 }
2805 if (DO_DRAW) {
2806 graph_draw<T>("CutAcrossTri", out.vert, out.edge, out.face);
2807 }
2808}
2809
2810template<typename T> void diamondcross_test()
2811{
2812 /* Diamond with constraint edge from top to bottom. Some dup verts. */
2813 const char *spec = R"(7 5 0
2814 0.0 0.0
2815 1.0 3.0
2816 2.0 0.0
2817 1.0 -3.0
2818 0.0 0.0
2819 1.0 -3.0
2820 1.0 3.0
2821 0 1
2822 1 2
2823 2 3
2824 3 4
2825 5 6
2826 )";
2827 InputStorage<T> store;
2830 EXPECT_EQ(out.vert.size(), 4);
2831 EXPECT_EQ(out.edge.size(), 5);
2832 EXPECT_EQ(out.face.size(), 2);
2833 if (DO_DRAW) {
2834 graph_draw<T>("DiamondCross", out.vert, out.edge, out.face);
2835 }
2836}
2837
2838template<typename T> void twodiamondscross_test()
2839{
2840 const char *spec = R"(12 9 0
2841 0.0 0.0
2842 1.0 2.0
2843 2.0 0.0
2844 1.0 -2.0
2845 0.0 0.0
2846 3.0 0.0
2847 4.0 2.0
2848 5.0 0.0
2849 4.0 -2.0
2850 3.0 0.0
2851 0.0 0.0
2852 5.0 0.0
2853 0 1
2854 1 2
2855 2 3
2856 3 4
2857 5 6
2858 6 7
2859 7 8
2860 8 9
2861 10 11
2862 )";
2863 InputStorage<T> store;
2864 CDT_input<T> in = fill_input_from_string<T>(spec, store);
2865 CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
2866 EXPECT_EQ(out.vert.size(), 8);
2867 EXPECT_EQ(out.edge.size(), 15);
2868 EXPECT_EQ(out.face.size(), 8);
2869 if (out.vert.size() == 8 && out.edge.size() == 15 && out.face.size() == 8) {
2870 int v_out[12];
2871 for (int i = 0; i < 12; ++i) {
2872 v_out[i] = get_orig_index(out.vert_orig, i);
2873 EXPECT_NE(v_out[i], -1);
2874 }
2875 EXPECT_EQ(v_out[0], v_out[4]);
2876 EXPECT_EQ(v_out[0], v_out[10]);
2877 EXPECT_EQ(v_out[5], v_out[9]);
2878 EXPECT_EQ(v_out[7], v_out[11]);
2879 int e_out[9];
2880 for (int i = 0; i < 8; ++i) {
2881 e_out[i] = get_output_edge_index(out, v_out[in.edge[i][0]], v_out[in.edge[i][1]]);
2882 EXPECT_NE(e_out[i], -1);
2883 }
2884 /* there won't be a single edge for the input cross edge, but rather 3 */
2885 EXPECT_EQ(get_output_edge_index(out, v_out[10], v_out[11]), -1);
2886 int e_cross_1 = get_output_edge_index(out, v_out[0], v_out[2]);
2887 int e_cross_2 = get_output_edge_index(out, v_out[2], v_out[5]);
2888 int e_cross_3 = get_output_edge_index(out, v_out[5], v_out[7]);
2889 EXPECT_TRUE(e_cross_1 != -1 && e_cross_2 != -1 && e_cross_3 != -1);
2893 }
2894 if (DO_DRAW) {
2895 graph_draw<T>("TwoDiamondsCross", out.vert, out.edge, out.face);
2896 }
2897}
2898
2899template<typename T> void manycross_test()
2900{
2901 /* Input has some repetition of vertices, on purpose */
2902 const char *spec = R"(27 21 0
2903 0.0 0.0
2904 6.0 9.0
2905 15.0 18.0
2906 35.0 13.0
2907 43.0 18.0
2908 57.0 12.0
2909 69.0 10.0
2910 78.0 0.0
2911 91.0 0.0
2912 107.0 22.0
2913 123.0 0.0
2914 0.0 0.0
2915 10.0 -14.0
2916 35.0 -8.0
2917 43.0 -12.0
2918 64.0 -13.0
2919 78.0 0.0
2920 91.0 0.0
2921 102.0 -9.0
2922 116.0 -9.0
2923 123.0 0.0
2924 43.0 18.0
2925 43.0 -12.0
2926 107.0 22.0
2927 102.0 -9.0
2928 0.0 0.0
2929 123.0 0.0
2930 0 1
2931 1 2
2932 2 3
2933 3 4
2934 4 5
2935 5 6
2936 6 7
2937 7 8
2938 8 9
2939 9 10
2940 11 12
2941 12 13
2942 13 14
2943 14 15
2944 15 16
2945 17 18
2946 18 19
2947 19 20
2948 21 22
2949 23 24
2950 25 26
2951 )";
2952 InputStorage<T> store;
2955 EXPECT_EQ(out.vert.size(), 19);
2956 EXPECT_EQ(out.edge.size(), 46);
2957 EXPECT_EQ(out.face.size(), 28);
2958 if (DO_DRAW) {
2959 graph_draw<T>("ManyCross", out.vert, out.edge, out.face);
2960 }
2962
2963template<typename T> void twoface_test()
2964{
2965 const char *spec = R"(6 0 2
2966 0.0 0.0
2967 1.0 0.0
2968 0.5 1.0
2969 1.1 1.0
2970 1.1 0.0
2971 1.6 1.0
2972 0 1 2
2973 3 4 5
2974 )";
2975 InputStorage<T> store;
2978 EXPECT_EQ(out.vert.size(), 6);
2979 EXPECT_EQ(out.edge.size(), 9);
2980 EXPECT_EQ(out.face.size(), 4);
2981 if (out.vert.size() == 6 && out.edge.size() == 9 && out.face.size() == 4) {
2982 int v_out[6];
2983 for (int i = 0; i < 6; i++) {
2984 v_out[i] = get_orig_index(out.vert_orig, i);
2985 EXPECT_NE(v_out[i], -1);
2986 }
2987 int f0_out = get_output_tri_index(out, v_out[0], v_out[1], v_out[2]);
2988 int f1_out = get_output_tri_index(out, v_out[3], v_out[4], v_out[5]);
2989 EXPECT_NE(f0_out, -1);
2990 EXPECT_NE(f1_out, -1);
2991 int e0_out = get_output_edge_index(out, v_out[0], v_out[1]);
2992 int e1_out = get_output_edge_index(out, v_out[1], v_out[2]);
2993 int e2_out = get_output_edge_index(out, v_out[2], v_out[0]);
2994 EXPECT_NE(e0_out, -1);
2995 EXPECT_NE(e1_out, -1);
2996 EXPECT_NE(e2_out, -1);
2997 EXPECT_TRUE(output_edge_has_input_id(out, e0_out, out.face_edge_offset + 0));
2998 EXPECT_TRUE(output_edge_has_input_id(out, e1_out, out.face_edge_offset + 1));
2999 EXPECT_TRUE(output_edge_has_input_id(out, e2_out, out.face_edge_offset + 2));
3003 if (DO_DRAW) {
3004 graph_draw<T>("TwoFace", out.vert, out.edge, out.face);
3005 }
3006}
3008template<typename T> void twoface2_test()
3009{
3010 const char *spec = R"(6 0 2
3011 0.0 0.0
3012 4.0 4.0
3013 -4.0 2.0
3014 3.0 0.0
3015 3.0 6.0
3016 -1.0 2.0
3017 0 1 2
3018 3 4 5
3019 )";
3020 InputStorage<T> store;
3023 EXPECT_EQ(out.vert.size(), 10);
3024 EXPECT_EQ(out.edge.size(), 18);
3025 EXPECT_EQ(out.face.size(), 9);
3026 if (out.vert.size() == 10 && out.edge.size() == 18 && out.face.size() == 9) {
3027 /* Input verts have no duplicates, so expect output ones match input ones. */
3028 for (int i = 0; i < 6; i++) {
3029 EXPECT_EQ(get_orig_index(out.vert_orig, i), i);
3030 }
3031 int v6 = get_vertex_by_coord(out, 3.0, 3.0);
3032 EXPECT_NE(v6, -1);
3033 int v7 = get_vertex_by_coord(out, 3.0, 3.75);
3034 EXPECT_NE(v7, -1);
3035 int v8 = get_vertex_by_coord(out, 0.0, 3.0);
3036 EXPECT_NE(v8, -1);
3037 int v9 = get_vertex_by_coord(out, 1.0, 1.0);
3038 EXPECT_NE(v9, -1);
3039 /* f0 to f3 should be triangles part of input face 0, not part of input face 1. */
3040 int f0 = get_output_tri_index(out, 0, 9, 5);
3041 EXPECT_NE(f0, -1);
3056 /* f4 and f5 should be triangles part of input face 1, not part of input face 0. */
3061 int f5 = get_output_tri_index(out, 3, 6, 9);
3062 EXPECT_NE(f5, -1);
3065 /* f6 to f8 should be triangles part of both input faces. */
3066 int f6 = get_output_tri_index(out, 5, 9, 6);
3071 EXPECT_NE(f7, -1);
3078 }
3079 if (DO_DRAW) {
3080 graph_draw<T>("TwoFace2", out.vert, out.edge, out.face);
3081 }
3083
3084template<typename T> void overlapfaces_test()
3085{
3086 const char *spec = R"(12 0 3
3087 0.0 0.0
3088 1.0 0.0
3089 1.0 1.0
3090 0.0 1.0
3091 0.5 0.5
3092 1.5 0.5
3093 1.5 1.3
3094 0.5 1.3
3095 0.1 0.1
3096 0.3 0.1
3097 0.3 0.3
3098 0.1 0.3
3099 0 1 2 3
3100 4 5 6 7
3101 8 9 10 11
3106 EXPECT_EQ(out.vert.size(), 14);
3107 EXPECT_EQ(out.edge.size(), 33);
3108 EXPECT_EQ(out.face.size(), 20);
3109 if (out.vert.size() == 14 && out.edge.size() == 33 && out.face.size() == 20) {
3110 int v_out[12];
3111 for (int i = 0; i < 12; i++) {
3112 v_out[i] = get_orig_index(out.vert_orig, i);
3113 EXPECT_NE(v_out[i], -1);
3114 }
3115 int v_int1 = 12;
3116 int v_int2 = 13;
3117 T x = out.vert[v_int1][0] - T(1);
3118 if (math_abs(x) > in.epsilon) {
3119 v_int1 = 13;
3120 v_int2 = 12;
3121 }
3123 expect_coord_near<T>(out.vert[v_int2], VecBase<T, 2>(0.5, 1));
3124 EXPECT_EQ(out.vert_orig[v_int1].size(), 0);
3125 EXPECT_EQ(out.vert_orig[v_int2].size(), 0);
3126 int f0_out = get_output_tri_index(out, v_out[1], v_int1, v_out[4]);
3127 EXPECT_NE(f0_out, -1);
3129 int f1_out = get_output_tri_index(out, v_out[4], v_int1, v_out[2]);
3130 EXPECT_NE(f1_out, -1);
3133 int f2_out = get_output_tri_index(out, v_out[8], v_out[9], v_out[10]);
3134 if (f2_out == -1) {
3135 f2_out = get_output_tri_index(out, v_out[8], v_out[9], v_out[11]);
3136 }
3137 EXPECT_NE(f2_out, -1);
3140 }
3141 if (DO_DRAW) {
3142 graph_draw<T>("OverlapFaces - full", out.vert, out.edge, out.face);
3143 }
3144
3145 /* Different output types. */
3146 CDT_result<T> out2 = delaunay_2d_calc(in, CDT_INSIDE);
3147 EXPECT_EQ(out2.face.size(), 18);
3148 if (DO_DRAW) {
3149 graph_draw<T>("OverlapFaces - inside", out2.vert, out2.edge, out2.face);
3150 }
3151
3153 EXPECT_EQ(out3.face.size(), 14);
3154 if (DO_DRAW) {
3155 graph_draw<T>("OverlapFaces - inside with holes", out3.vert, out3.edge, out3.face);
3156 }
3159 EXPECT_EQ(out4.face.size(), 4);
3160 if (DO_DRAW) {
3161 graph_draw<T>("OverlapFaces - constraints", out4.vert, out4.edge, out4.face);
3163
3164 CDT_result<T> out5 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH);
3165 EXPECT_EQ(out5.face.size(), 5);
3166 if (DO_DRAW) {
3167 graph_draw<T>("OverlapFaces - valid bmesh", out5.vert, out5.edge, out5.face);
3168 }
3169
3171 EXPECT_EQ(out6.face.size(), 3);
3172 if (DO_DRAW) {
3173 graph_draw<T>("OverlapFaces - valid bmesh with holes", out6.vert, out6.edge, out6.face);
3174 }
3175}
3176
3177template<typename T> void twosquaresoverlap_test()
3178{
3179 const char *spec = R"(8 0 2
3180 1.0 -1.0
3181 -1.0 -1.0
3182 -1.0 1.0
3183 1.0 1.0
3184 -1.5 1.5
3185 0.5 1.5
3186 0.5 -0.5
3187 -1.5 -0.5
3188 7 6 5 4
3189 3 2 1 0
3190 )";
3191 InputStorage<T> store;
3196 EXPECT_EQ(out.face.size(), 3);
3197 if (DO_DRAW) {
3198 graph_draw<T>("TwoSquaresOverlap", out.vert, out.edge, out.face);
3199 }
3200}
3201
3202template<typename T> void twofaceedgeoverlap_test()
3203{
3204 const char *spec = R"(6 0 2
3205 5.657 0.0
3206 -1.414 -5.831
3207 0.0 0.0
3208 5.657 0.0
3209 -2.121 -2.915
3210 0.0 0.0
3211 2 1 0
3212 5 4 3
3213 )";
3214 InputStorage<T> store;
3217 EXPECT_EQ(out.vert.size(), 5);
3218 EXPECT_EQ(out.edge.size(), 7);
3219 EXPECT_EQ(out.face.size(), 3);
3220 if (out.vert.size() == 5 && out.edge.size() == 7 && out.face.size() == 3) {
3221 int v_int = 4;
3222 int v_out[6];
3223 for (int i = 0; i < 6; i++) {
3224 v_out[i] = get_orig_index(out.vert_orig, i);
3225 EXPECT_NE(v_out[i], -1);
3226 EXPECT_NE(v_out[i], v_int);
3228 EXPECT_EQ(v_out[0], v_out[3]);
3229 EXPECT_EQ(v_out[2], v_out[5]);
3230 int e01 = get_output_edge_index(out, v_out[0], v_out[1]);
3231 uint32_t foff = out.face_edge_offset;
3233 int e1i = get_output_edge_index(out, v_out[1], v_int);
3234 EXPECT_TRUE(output_edge_has_input_id(out, e1i, foff + 0));
3235 int ei2 = get_output_edge_index(out, v_int, v_out[2]);
3236 EXPECT_TRUE(output_edge_has_input_id(out, ei2, foff + 0));
3237 int e20 = get_output_edge_index(out, v_out[2], v_out[0]);
3238 EXPECT_TRUE(output_edge_has_input_id(out, e20, foff + 2));
3239 EXPECT_TRUE(output_edge_has_input_id(out, e20, 2 * foff + 2));
3240 int e24 = get_output_edge_index(out, v_out[2], v_out[4]);
3241 EXPECT_TRUE(output_edge_has_input_id(out, e24, 2 * foff + 0));
3242 int e4i = get_output_edge_index(out, v_out[4], v_int);
3243 EXPECT_TRUE(output_edge_has_input_id(out, e4i, 2 * foff + 1));
3244 int ei0 = get_output_edge_index(out, v_int, v_out[0]);
3245 EXPECT_TRUE(output_edge_has_input_id(out, ei0, 2 * foff + 1));
3246 int f02i = get_output_tri_index(out, v_out[0], v_out[2], v_int);
3247 EXPECT_NE(f02i, -1);
3250 int f24i = get_output_tri_index(out, v_out[2], v_out[4], v_int);
3251 EXPECT_NE(f24i, -1);
3254 int f10i = get_output_tri_index(out, v_out[1], v_out[0], v_int);
3255 EXPECT_NE(f10i, -1);
3258 }
3259 if (DO_DRAW) {
3260 graph_draw<T>("TwoFaceEdgeOverlap", out.vert, out.edge, out.face);
3261 }
3263
3264template<typename T> void triintri_test()
3265{
3266 const char *spec = R"(6 0 2
3267 -5.65685 0.0
3268 1.41421 -5.83095
3269 0.0 0.0
3270 -2.47487 -1.45774
3271 -0.707107 -2.91548
3272 -1.06066 -1.45774
3273 0 1 2
3274 3 4 5
3275 )";
3276 InputStorage<T> store;
3281 EXPECT_EQ(out.face.size(), 3);
3282 if (DO_DRAW) {
3283 graph_draw<T>("TriInTri", out.vert, out.edge, out.face);
3284 }
3285}
3286
3287template<typename T> void diamondinsquare_test()
3288{
3289 const char *spec = R"(8 0 2
3290 0.0 0.0
3291 1.0 0.0
3292 1.0 1.0
3293 0.0 1.0
3294 0.14644660940672627 0.5
3295 0.5 0.14644660940672627
3296 0.8535533905932737 0.5
3297 0.5 0.8535533905932737
3298 0 1 2 3
3299 4 5 6 7
3300 )";
3301 InputStorage<T> store;
3306 EXPECT_EQ(out.face.size(), 3);
3307 if (DO_DRAW) {
3308 graph_draw<T>("DiamondInSquare", out.vert, out.edge, out.face);
3309 }
3310}
3311
3312template<typename T> void diamondinsquarewire_test()
3313{
3314 const char *spec = R"(8 8 0
3315 0.0 0.0
3316 1.0 0.0
3317 1.0 1.0
3318 0.0 1.0
3319 0.14644660940672627 0.5
3320 0.5 0.14644660940672627
3321 0.8535533905932737 0.5
3322 0.5 0.8535533905932737
3323 0 1
3324 1 2
3325 2 3
3326 3 0
3327 4 5
3328 5 6
3329 6 7
3330 7 4
3331 )";
3332 InputStorage<T> store;
3335 EXPECT_EQ(out.vert.size(), 8);
3336 EXPECT_EQ(out.edge.size(), 8);
3337 EXPECT_EQ(out.face.size(), 2);
3338 if (DO_DRAW) {
3339 graph_draw<T>("DiamondInSquareWire", out.vert, out.edge, out.face);
3340 }
3341}
3342
3343template<typename T> void repeatedge_test()
3344{
3345 const char *spec = R"(5 3 0
3346 0.0 0.0
3347 0.0 1.0
3348 1.0 1.1
3349 0.5 -0.5
3350 0.5 2.5
3351 0 1
3352 2 3
3353 2 3
3354 )";
3355 InputStorage<T> store;
3356 CDT_input<T> in = fill_input_from_string<T>(spec, store);
3357 CDT_result<T> out = delaunay_2d_calc(in, CDT_CONSTRAINTS);
3358 EXPECT_EQ(out.edge.size(), 2);
3359 if (DO_DRAW) {
3360 graph_draw<T>("RepeatEdge", out.vert, out.edge, out.face);
3361 }
3362}
3363
3364template<typename T> void repeattri_test()
3365{
3366 const char *spec = R"(3 0 2
3367 0.0 0.0
3368 1.0 0.0
3369 0.5 1.0
3370 0 1 2
3371 0 1 2
3372 )";
3373 InputStorage<T> store;
3376 EXPECT_EQ(out.edge.size(), 3);
3377 EXPECT_EQ(out.face.size(), 1);
3380 if (DO_DRAW) {
3381 graph_draw<T>("RepeatTri", out.vert, out.edge, out.face);
3382 }
3383}
3384
3385/* Adjacency-deduplication exercise: two adjacent CCW rectangles share a
3386 * boundary that has been split by a midpoint vertex, so the shared
3387 * boundary becomes TWO distinct constrained CDT edges - both between
3388 * the same pair of regions (left rect interior, right rect interior).
3389 *
3390 * The even-odd region-adjacency build appends a canonical entry for
3391 * each cross-region constrained edge it encounters; with two edges
3392 * between the same region pair, the second entry is a duplicate that
3393 * the helper's stable_sort + std::unique must collapse. The test pins
3394 * the BEHAVIOR: both rectangles must be correctly filled.
3395 *
3396 * Geometry (7 verts, 2 face constraints):
3397 *
3398 * 4-------3-------6 y=1
3399 * | | |
3400 * | X 2 Y | y=0.5 (vert 2 is the midpoint)
3401 * | | |
3402 * 0-------1-------5 y=0
3403 *
3404 * Face 0 (X, left): 0,1,2,3,4 (CCW). 5 verts because of midpoint 2.
3405 * Face 1 (Y, right): 1,5,6,3,2 (CCW). 5 verts because of midpoint 2.
3406 *
3407 * Shared CDT edges between X and Y: (1,2) and (2,3) - both with
3408 * multiplicity 2, both with parity flip 0. */
3409template<typename T> void shared_split_boundary_test()
3410{
3411 const char *spec = R"(7 0 2
3412 0.0 0.0
3413 1.0 0.0
3414 1.0 0.5
3415 1.0 1.0
3416 0.0 1.0
3417 2.0 0.0
3418 2.0 1.0
3419 0 1 2 3 4
3420 1 5 6 3 2
3421 )";
3422 InputStorage<T> store;
3424
3427
3428 /* No new vertices needed (no intersections); both 5-vert pentagons
3429 * triangulate into 3 triangles each. */
3430 EXPECT_EQ(out_evenodd.vert.size(), 7);
3431 EXPECT_EQ(out_nonzero.vert.size(), 7);
3432 EXPECT_EQ(out_evenodd.face.size(), 6);
3433 EXPECT_EQ(out_nonzero.face.size(), 6);
3434
3435 if (DO_DRAW) {
3437 "SharedSplitBoundary - even-odd", out_evenodd.vert, out_evenodd.edge, out_evenodd.face);
3439 "SharedSplitBoundary - non-zero", out_nonzero.vert, out_nonzero.edge, out_nonzero.face);
3440 }
3441}
3442
3443template<typename T> void square_o_test()
3444{
3445 const char *spec = R"(8 0 2
3446 0.0 0.0
3447 1.0 0.0
3448 1.0 1.0
3449 0.0 1.0
3450 0.2 0.2
3451 0.2 0.8
3452 0.8 0.8
3453 0.8 0.2
3454 0 1 2 3
3455 4 5 6 7
3456 )";
3457 InputStorage<T> store;
3460 EXPECT_EQ(out1.face.size(), 8);
3461 if (DO_DRAW) {
3462 graph_draw<T>("Square O - inside with holes", out1.vert, out1.edge, out1.face);
3463 }
3464
3466 EXPECT_EQ(out2.face.size(), 2);
3467 if (DO_DRAW) {
3468 graph_draw<T>("Square O - valid bmesh with holes", out2.vert, out2.edge, out2.face);
3469 }
3470}
3471
3480template<typename T> void fill_curve_letter_b_test()
3481{
3482 const char *spec = R"(15 0 3
3483 0.0 1.0
3484 0.4 1.0
3485 0.55 0.75
3486 0.45 0.5
3487 0.6 0.25
3488 0.4 0.0
3489 0.0 0.0
3490 0.15 0.6
3491 0.4 0.6
3492 0.4 0.9
3493 0.15 0.9
3494 0.15 0.1
3495 0.45 0.1
3496 0.45 0.4
3497 0.15 0.4
3498 0 1 2 3 4 5 6
3499 7 8 9 10
3500 11 12 13 14
3501 )";
3502 InputStorage<T> store;
3504 in.needed_ids = CDT_NO_ORIG_IDS;
3506 EXPECT_EQ(out.vert.size(), 15);
3507 EXPECT_EQ(out.edge.size(), 18);
3508 EXPECT_EQ(out.face.size(), 2);
3509 if (DO_DRAW) {
3510 graph_draw<T>("FillCurveLetterB", out.vert, out.edge, out.face);
3511 }
3512
3513 /* Fill again with every contour reversed (CCW outline, CW counters). */
3514 for (const int i : in.face_offsets.index_range()) {
3515 store.face_vert_indices.as_mutable_span().slice(in.face_offsets[i]).reverse();
3516 }
3518 EXPECT_EQ(out_reversed.vert.size(), 15);
3519 EXPECT_EQ(out_reversed.edge.size(), 18);
3520 EXPECT_EQ(out_reversed.face.size(), 2);
3521 if (DO_DRAW) {
3523 "FillCurveLetterB - reversed", out_reversed.vert, out_reversed.edge, out_reversed.face);
3524 }
3525}
3526
3533template<typename T> void fill_curve_degenerate_interior_faces_test()
3534{
3535 const int grid_size = 10;
3536 const int cells_num = grid_size - 1;
3537 const int boundary_num = 4 * grid_size - 4;
3538 const int interior_faces_num = cells_num * cells_num;
3539 const int verts_num = boundary_num + 2 * interior_faces_num;
3540 const int faces_num = 1 + interior_faces_num;
3541 const double min = -0.5;
3542 const double max = 0.5;
3543 const double step = 1.0 / double(cells_num);
3544
3545 Array<VecBase<T, 2>> verts(verts_num);
3546 Array<Vector<int>> faces(faces_num);
3547
3548 int vert_index = 0;
3549 auto add_vert = [&](const double x, const double y) {
3550 verts[vert_index++] = VecBase<T, 2>(T(x), T(y));
3551 };
3552
3553 for (int i = 0; i < grid_size; i++) {
3554 add_vert(min, min + i * step);
3555 }
3556 for (int i = 1; i < grid_size; i++) {
3557 add_vert(min + i * step, max);
3558 }
3559 for (int i = 1; i < grid_size; i++) {
3560 add_vert(max, max - i * step);
3561 }
3562 for (int i = 1; i < grid_size - 1; i++) {
3563 add_vert(max - i * step, min);
3564 }
3565 for (int i = 0; i < boundary_num; i++) {
3566 faces[0].append(i);
3567 }
3568
3569 int face_index = 1;
3570 for (int x = 0; x < cells_num; x++) {
3571 for (int y = 0; y < cells_num; y++) {
3572 const double cx = min + (x + 0.5) * step;
3573 const double cy = min + (y + 0.5) * step;
3574 const int first_vert = vert_index;
3575 add_vert(cx, cy);
3576 add_vert(cx, cy);
3577 faces[face_index].append(first_vert);
3578 faces[face_index].append(first_vert + 1);
3579 face_index++;
3580 }
3581 }
3582
3583 BLI_assert(vert_index == verts_num);
3584 BLI_assert(face_index == faces_num);
3585
3586 Vector<int> face_offsets;
3587 Vector<int> face_vert_offsets;
3588 for (const int i : faces.index_range()) {
3589 face_offsets.append(face_vert_offsets.size());
3590 face_vert_offsets.extend(faces[i]);
3591 }
3592 face_offsets.append(face_vert_offsets.size());
3593
3595 in.vert = verts;
3596 in.face_offsets = OffsetIndices<int>(face_offsets);
3597 in.face_vert_indices = face_vert_offsets;
3598 in.epsilon = T(0.00001);
3599 in.needed_ids = CDT_NO_ORIG_IDS;
3600
3602 EXPECT_EQ(out.vert.size(), 117);
3603 EXPECT_EQ(out.edge.size(), 126);
3604 EXPECT_EQ(out.face.size(), 10);
3605}
3606
3620template<typename T> void dissolve_pendant_edge_face_test()
3621{
3622 const char *spec = R"(8 0 1
3623 -0.5 0.3
3624 -0.5 0.4
3625 -0.1 0.5
3626 0.5 0.2
3627 0.5 -0.4
3628 0.5 -0.5
3629 0.44 -0.2
3630 0.44 -0.1
3631 0 1 2 3 4 5
3632 )";
3633 InputStorage<T> store;
3635 in.needed_ids = CDT_NO_ORIG_IDS;
3637 EXPECT_EQ(out.vert.size(), 8);
3638 EXPECT_EQ(out.edge.size(), 10);
3639 EXPECT_EQ(out.face.size(), 3);
3640 if (DO_DRAW) {
3641 graph_draw<T>("DissolvePendantEdgeFace", out.vert, out.edge, out.face);
3642 }
3643}
3644
3651template<typename T> void stale_symedge_before_remove_faces_in_holes_test()
3652{
3653 const char *spec = R"(9 0 1
3654 0.7 1.0
3655 -1.0 -0.66667
3656 0.7 -1.0
3657 -1.0 1.0
3658 1.0 1.0
3659 -1.0 -0.66667
3660 0.3 -0.3
3661 0.0 -0.3
3662 0.0 0.0
3663 0 1 2 3 4 5 6
3664 )";
3665 InputStorage<T> store;
3667 in.needed_ids = CDT_NO_ORIG_IDS;
3669 EXPECT_EQ(out.vert.size(), 12);
3670 EXPECT_EQ(out.edge.size(), 18);
3671 EXPECT_EQ(out.face.size(), 6);
3672 if (DO_DRAW) {
3673 graph_draw<T>("StaleSymedgeBeforeRemoveFacesInHoles", out.vert, out.edge, out.face);
3674 }
3675}
3676
3680template<typename T> void fuzz_repro_minimize_test1()
3681{
3682 const char *spec = R"(9 0 1
3683 0.16514 -0.823874
3684 0.349776 0.174872
3685 -0.528584 0.489292
3686 0.916708 0.728511
3687 -0.85114 0.07962
3688 -0.23437 -0.996308
3689 0.433229 -0.892684
3690 -0.957911 0.517122
3691 0.257921 0.862028
3692 0 1 0 3 4
3693 )";
3694 InputStorage<T> store;
3696 in.needed_ids = CDT_ORIG_FACES;
3698 (void)out;
3699}
3700
3704template<typename T> void fuzz_repro_minimize_test2()
3705{
3706 const char *spec = R"(9 0 1
3707 -0.255233 0.780605
3708 0.789803 0.974262
3709 -0.78598 -0.701386
3710 0.871088 0.566743
3711 0.752273 -0.476301
3712 -0.747342 0.0773856
3713 -0.3056 -0.229194
3714 -0.260009 -0.0515187
3715 0.459831 0.861793
3716 0 1 2 3 4
3717 )";
3718 InputStorage<T> store;
3720 in.needed_ids = CDT_NO_ORIG_IDS;
3722 (void)out;
3723}
3724
3725template<typename T> void intersection_simple_edge_ids_test()
3726{
3727 const char *spec = R"(4 2 0
3728 0.0 0.0
3729 2.0 2.0
3730 0.0 2.0
3731 2.0 0.0
3732 0 1
3733 2 3
3734 )";
3735 InputStorage<T> store;
3736 CDT_input<T> input = fill_input_from_string<T>(spec, store);
3739 EXPECT_EQ(result.intersected_edges_orig.size(), 5);
3741 if (DO_DRAW) {
3742 graph_draw<T>("Intersections Simple", result.vert, result.edge, result.face);
3743 }
3744}
3745
3746template<typename T> void intersection_squares_edge_ids_test()
3747{
3748 const char *spec = R"(8 0 2
3749 0.0 0.0
3750 1.0 0.0
3751 1.0 1.0
3752 0.0 1.0
3753 0.2 0.2
3754 0.2 1.2
3755 1.2 1.2
3756 1.2 0.2
3757 0 1 2 3
3758 4 5 6 7
3759 )";
3760 InputStorage<T> store;
3761 CDT_input<T> input = fill_input_from_string<T>(spec, store);
3764 EXPECT_EQ(result.intersected_edges_orig.size(), 10);
3766 result, 8, result.face_edge_offset + 2, result.face_edge_offset + 4));
3768 result, 9, result.face_edge_offset + 1, result.face_edge_offset + 7));
3769 if (DO_DRAW) {
3770 graph_draw<T>("Intersections Squares", result.vert, result.edge, result.face);
3771 }
3772}
3773
3774TEST(delaunay_d, Empty)
3775{
3777}
3778
3779TEST(delaunay_d, OnePt)
3780{
3782}
3783
3784TEST(delaunay_d, TwoPt)
3785{
3787}
3788
3789TEST(delaunay_d, ThreePt)
3790{
3792}
3793
3794TEST(delaunay_d, MixedPts)
3795{
3797}
3798
3799TEST(delaunay_d, Quad0)
3800{
3802}
3803
3804TEST(delaunay_d, Quad1)
3805{
3807}
3808
3809TEST(delaunay_d, Quad2)
3810{
3812}
3813
3814TEST(delaunay_d, Quad3)
3815{
3817}
3818
3819TEST(delaunay_d, Quad4)
3820{
3822}
3823
3824TEST(delaunay_d, LineInSquare)
3825{
3827}
3828
3829TEST(delaunay_d, LineHoleInSquare)
3830{
3832}
3833
3834TEST(delaunay_d, NestedHoles)
3835{
3837}
3838
3839TEST(delaunay_d, EvenOddNestedHolesDeep)
3840{
3842}
3843
3844TEST(delaunay_d, EvenOddBoundaryDisagreement)
3845{
3847}
3848
3849TEST(delaunay_d, EvenOddCoincidentPolygonsNeedIdsStable)
3850{
3852}
3853
3854TEST(delaunay_d, CwOrigFaceIds)
3855{
3857}
3858
3859TEST(delaunay_d, NonZeroWinding)
3860{
3862}
3863
3864TEST(delaunay_d, NonZeroWindingNested)
3865{
3867}
3868
3869TEST(delaunay_d, NonZeroWindingNestedUnion)
3870{
3872}
3873
3874TEST(delaunay_d, NonZeroWindingMultiFaceEdge)
3875{
3877}
3878
3879TEST(delaunay_d, NonZeroWindingMultiFaceEdgeMixed)
3880{
3882}
3883
3884TEST(delaunay_d, NonZeroWindingCancelToZero)
3885{
3887}
3888
3889TEST(delaunay_d, NonZeroWindingHighCount)
3890{
3892}
3893
3894TEST(delaunay_d, NonZeroWindingFan)
3895{
3897}
3898
3899TEST(delaunay_d, NonZeroWindingEdgeSplit)
3900{
3902}
3903
3904TEST(delaunay_d, NonZeroWindingSelfIntersect)
3905{
3907}
3908
3909TEST(delaunay_d, NonZeroWindingDeepNest)
3910{
3912}
3913
3914TEST(delaunay_d, NonZeroWindingSharedSubsegment)
3915{
3917}
3918
3919TEST(delaunay_d, NonZeroWindingIslandInHole)
3920{
3922}
3923
3924TEST(delaunay_d, NonZeroWindingCoincidentVerts)
3925{
3927}
3928
3929TEST(delaunay_d, NonZeroWindingManyCrossings)
3930{
3932}
3933
3934TEST(delaunay_d, NonZeroWindingNegativeOnly)
3935{
3937}
3938
3939TEST(delaunay_d, NonZeroWindingTJunction)
3940{
3942}
3943
3944TEST(delaunay_d, NonZeroWindingExactSharedEdge)
3945{
3947}
3948
3949TEST(delaunay_d, NonZeroWindingConcaveOuter)
3950{
3952}
3953
3954TEST(delaunay_d, CrossSegs)
3955{
3957}
3958
3959TEST(delaunay_d, CutAcrossTri)
3960{
3962}
3963
3964TEST(delaunay_d, DiamondCross)
3965{
3967}
3968
3969TEST(delaunay_d, TwoDiamondsCross)
3970{
3972}
3973
3974TEST(delaunay_d, ManyCross)
3975{
3977}
3978
3979TEST(delaunay_d, TwoFace)
3980{
3982}
3983
3984TEST(delaunay_d, TwoFace2)
3985{
3987}
3988
3989TEST(delaunay_d, OverlapFaces)
3990{
3992}
3993
3994TEST(delaunay_d, TwoSquaresOverlap)
3995{
3997}
3998
3999TEST(delaunay_d, TwoFaceEdgeOverlap)
4000{
4002}
4003
4004TEST(delaunay_d, TriInTri)
4005{
4007}
4008
4009TEST(delaunay_d, DiamondInSquare)
4010{
4012}
4013
4014TEST(delaunay_d, DiamondInSquareWire)
4015{
4017}
4018
4019TEST(delaunay_d, LoopingBack2x)
4020{
4022}
4023
4024TEST(delaunay_d, LoopingBack3x)
4025{
4027}
4028
4029TEST(delaunay_d, LoopingBackHole2x)
4030{
4032}
4033
4034TEST(delaunay_d, LoopingBackHole3x)
4035{
4037}
4038
4039TEST(delaunay_d, DisjointPolysInLargeHull)
4040{
4042}
4043
4044TEST(delaunay_d, RepeatEdge)
4045{
4047}
4048
4049TEST(delaunay_d, RepeatTri)
4050{
4052}
4053
4054TEST(delaunay_d, SharedSplitBoundary)
4055{
4057}
4058
4059TEST(delaunay_d, SquareO)
4060{
4062}
4063
4064TEST(delaunay_d, FillCurveLetterB)
4065{
4067}
4068
4069TEST(delaunay_d, FillCurveDegenerateInteriorFaces)
4070{
4072}
4073
4074TEST(delaunay_d, DissolvePendantEdgeFace)
4075{
4077}
4078
4079TEST(delaunay_d, StaleSymedgeBeforeRemoveFacesInHoles)
4080{
4082}
4083
4084TEST(delaunay_d, FuzzReproMinimize1)
4085{
4087}
4088
4089TEST(delaunay_d, FuzzReproMinimize2)
4090{
4092}
4093
4094TEST(delaunay_d, IntersectionSimpleEdgeIds)
4095{
4097}
4098
4099TEST(delaunay_d, IntersectionSquaresEdgeIds)
4100{
4102}
4103
4104# ifdef WITH_GMP
4105TEST(delaunay_m, Empty)
4106{
4108}
4109
4110TEST(delaunay_m, OnePt)
4111{
4113}
4114TEST(delaunay_m, TwoPt)
4115{
4117}
4118
4119TEST(delaunay_m, ThreePt)
4120{
4122}
4123
4124TEST(delaunay_m, MixedPts)
4125{
4127}
4128
4129TEST(delaunay_m, Quad0)
4130{
4132}
4133
4134TEST(delaunay_m, Quad1)
4135{
4137}
4138
4139TEST(delaunay_m, Quad2)
4140{
4142}
4143
4144TEST(delaunay_m, Quad3)
4145{
4147}
4148
4149TEST(delaunay_m, Quad4)
4150{
4152}
4153
4154TEST(delaunay_m, LineInSquare)
4155{
4157}
4158
4159TEST(delaunay_m, DisjointPolysInLargeHull)
4160{
4162}
4163
4164TEST(delaunay_m, LineHoleInSquare)
4165{
4167}
4168
4169TEST(delaunay_m, NestedHoles)
4170{
4172}
4173
4174TEST(delaunay_m, EvenOddNestedHolesDeep)
4175{
4177}
4178
4179TEST(delaunay_m, EvenOddBoundaryDisagreement)
4180{
4182}
4183
4184TEST(delaunay_m, EvenOddCoincidentPolygonsNeedIdsStable)
4185{
4187}
4188
4189TEST(delaunay_m, CwOrigFaceIds)
4190{
4192}
4193
4194TEST(delaunay_m, NonZeroWinding)
4195{
4197}
4198
4199TEST(delaunay_m, NonZeroWindingNested)
4200{
4202}
4203
4204TEST(delaunay_m, NonZeroWindingNestedUnion)
4205{
4207}
4208
4209TEST(delaunay_m, NonZeroWindingMultiFaceEdge)
4210{
4212}
4213
4214TEST(delaunay_m, NonZeroWindingMultiFaceEdgeMixed)
4215{
4217}
4218
4219TEST(delaunay_m, NonZeroWindingCancelToZero)
4220{
4222}
4223
4224TEST(delaunay_m, NonZeroWindingHighCount)
4225{
4227}
4228
4229TEST(delaunay_m, NonZeroWindingFan)
4230{
4232}
4233
4234TEST(delaunay_m, NonZeroWindingEdgeSplit)
4235{
4237}
4238
4239TEST(delaunay_m, NonZeroWindingSelfIntersect)
4240{
4242}
4243
4244TEST(delaunay_m, NonZeroWindingDeepNest)
4245{
4247}
4248
4249TEST(delaunay_m, NonZeroWindingSharedSubsegment)
4250{
4252}
4253
4254TEST(delaunay_m, NonZeroWindingIslandInHole)
4255{
4257}
4258
4259TEST(delaunay_m, NonZeroWindingCoincidentVerts)
4260{
4262}
4263
4264TEST(delaunay_m, NonZeroWindingManyCrossings)
4265{
4267}
4268
4269TEST(delaunay_m, NonZeroWindingNegativeOnly)
4270{
4272}
4273
4274TEST(delaunay_m, NonZeroWindingTJunction)
4275{
4277}
4278
4279TEST(delaunay_m, NonZeroWindingExactSharedEdge)
4280{
4282}
4283
4284TEST(delaunay_m, NonZeroWindingConcaveOuter)
4285{
4287}
4288
4289TEST(delaunay_m, CrossSegs)
4290{
4292}
4293
4294TEST(delaunay_m, CutAcrossTri)
4295{
4297}
4298
4299TEST(delaunay_m, DiamondCross)
4300{
4302}
4303
4304TEST(delaunay_m, TwoDiamondsCross)
4305{
4307}
4308
4309TEST(delaunay_m, ManyCross)
4310{
4312}
4313
4314TEST(delaunay_m, TwoFace)
4315{
4317}
4318
4319TEST(delaunay_m, TwoFace2)
4320{
4322}
4323
4324TEST(delaunay_m, OverlapFaces)
4325{
4327}
4328
4329TEST(delaunay_m, TwoSquaresOverlap)
4330{
4332}
4333
4334TEST(delaunay_m, TwoFaceEdgeOverlap)
4335{
4337}
4338
4339TEST(delaunay_m, TriInTri)
4340{
4342}
4343
4344TEST(delaunay_m, DiamondInSquare)
4345{
4347}
4348
4349TEST(delaunay_m, DiamondInSquareWire)
4350{
4352}
4353
4354TEST(delaunay_m, LoopingBack2x)
4355{
4357}
4358
4359TEST(delaunay_m, LoopingBack3x)
4360{
4362}
4363
4364TEST(delaunay_m, LoopingBackHole2x)
4365{
4367}
4368
4369TEST(delaunay_m, LoopingBackHole3x)
4370{
4372}
4373
4374TEST(delaunay_m, RepeatEdge)
4375{
4377}
4378
4379TEST(delaunay_m, RepeatTri)
4380{
4382}
4383
4384TEST(delaunay_m, SharedSplitBoundary)
4385{
4387}
4388
4389TEST(delaunay_m, IntersectionSimpleEdgeIds)
4390{
4392}
4393
4394TEST(delaunay_m, IntersectionSquaresEdgeIds)
4395{
4397}
4398
4399TEST(delaunay_m, FillCurveLetterB)
4400{
4402}
4403# endif
4404#endif
4405
4406#if DO_TEXT_TESTS
4407template<typename T>
4408void text_test(int arc_points_num,
4409 int lets_per_line_num,
4410 int lines_num,
4411 CDT_output_type otype,
4412 CDT_ids_needed_type needed_ids,
4413 bool invert)
4414{
4415 constexpr bool print_timing = true;
4416 /*
4417 * Make something like a letter B:
4418 * \code{.unparsed}
4419 * 4------------3
4420 * | )
4421 * | 12--11 )
4422 * | | ) a3 ) a1
4423 * | 9---10 )
4424 * | )
4425 * | 2
4426 * | )
4427 * | 8----7 )
4428 * | | ) a2 ) a0
4429 * | 5----6 )
4430 * | )
4431 * 0------------1
4432 * \endcode
4433 * Where the numbers are the first 13 vertices, and the rest of
4434 * the vertices are in arcs a0, a1, a2, a3, each of which have
4435 * arc_points_num per arc in them.
4436 */
4437
4438 const char *b_before_arcs = R"(13 0 3
4439 0.0 0.0
4440 1.0 0.0
4441 1.0 1.5
4442 1.0 3.0
4443 0.0 3.0
4444 0.2 0.2
4445 0.6 0.2
4446 0.6 1.4
4447 0.2 1.4
4448 0.2 1.6
4449 0.6 1.6
4450 0.6 2.8
4451 0.2 2.8
4452 3 4 0 1 2
4453 6 5 8 7
4454 10 9 12 11
4455 )";
4456
4457 InputStorage<T> b_store;
4458 CDT_input<T> b_before_arcs_in = fill_input_from_string<T>(b_before_arcs, b_store);
4459 constexpr int narcs = 4;
4460 int b_npts = b_store.vert.size() + narcs * arc_points_num;
4461 constexpr int b_nfaces = 3;
4462 Array<VecBase<T, 2>> b_vert(b_npts);
4463 Array<Vector<int>> b_face(b_nfaces);
4464 std::copy(b_store.vert.begin(), b_store.vert.end(), b_vert.begin());
4465 for (const int f : IndexRange(b_nfaces)) {
4466 IndexRange fspan = b_before_arcs_in.face_offsets[f];
4467 b_face[f] = Vector<int>(fspan.size());
4468 for (const int i : fspan.index_range()) {
4469 b_face[f][i] = b_before_arcs_in.face_vert_indices[fspan[i]];
4470 }
4471 }
4472 if (arc_points_num > 0) {
4473 b_face[0].pop_last(); /* We'll add center point back between arcs for outer face. */
4474 for (int arc = 0; arc < narcs; ++arc) {
4475 int arc_origin_vert;
4476 int arc_terminal_vert;
4477 bool ccw;
4478 switch (arc) {
4479 case 0:
4480 arc_origin_vert = 1;
4481 arc_terminal_vert = 2;
4482 ccw = true;
4483 break;
4484 case 1:
4485 arc_origin_vert = 2;
4486 arc_terminal_vert = 3;
4487 ccw = true;
4488 break;
4489 case 2:
4490 arc_origin_vert = 7;
4491 arc_terminal_vert = 6;
4492 ccw = false;
4493 break;
4494 case 3:
4495 arc_origin_vert = 11;
4496 arc_terminal_vert = 10;
4497 ccw = false;
4498 break;
4499 default:
4500 BLI_assert(false);
4501 return;
4502 }
4503 VecBase<T, 2> start_co = b_vert[arc_origin_vert];
4504 VecBase<T, 2> end_co = b_vert[arc_terminal_vert];
4505 VecBase<T, 2> center_co = 0.5 * (start_co + end_co);
4506 BLI_assert(start_co[0] == end_co[0]);
4507 double radius = abs(math_to_double<T>(end_co[1] - center_co[1]));
4508 double angle_delta = M_PI / (arc_points_num + 1);
4509 int start_vert = b_before_arcs_in.vert.size() + arc * arc_points_num;
4510 Vector<int> &face = b_face[(arc <= 1) ? 0 : arc - 1];
4511 for (int i = 0; i < arc_points_num; ++i) {
4512 VecBase<T, 2> delta;
4513 float ang = ccw ? (-M_PI_2 + (i + 1) * angle_delta) : (M_PI_2 - (i + 1) * angle_delta);
4514 delta[0] = T(radius * cos(ang));
4515 delta[1] = T(radius * sin(ang));
4516 b_vert[start_vert + i] = center_co + delta;
4517 face.append(start_vert + i);
4518 }
4519 if (arc == 0) {
4520 face.append(arc_terminal_vert);
4521 }
4522 }
4523 }
4524
4525 InputStorage<T> store;
4526 int tot_instances = lets_per_line_num * lines_num;
4527 BLI_assert(b_nfaces == 3);
4528 int b_tot_face_verts = b_face[0].size() + b_face[1].size() + b_face[2].size();
4529 int tot_face_verts = tot_instances * b_tot_face_verts + (invert ? 4 : 0);
4530 int tot_faces = tot_instances * b_nfaces + (invert ? 1 : 0);
4531 store.vert.reinitialize(tot_face_verts);
4532 store.face_offsets.reinitialize(tot_faces + 1);
4533 store.face_vert_indices.reinitialize(tot_face_verts);
4534
4535 T cur_x = T(0);
4536 T cur_y = T(0);
4537 T delta_x = T(2);
4538 T delta_y = T(3.25);
4539 int instance = 0;
4540 store.face_offsets[0] = 0;
4541 for (int line = 0; line < lines_num; ++line) {
4542 for (int let = 0; let < lets_per_line_num; ++let) {
4543 VecBase<T, 2> co_offset(cur_x, cur_y);
4544 int in_v_offset = instance * b_vert.size();
4545 for (const int v : b_vert.index_range()) {
4546 store.vert[in_v_offset + v] = b_vert[v] + co_offset;
4547 }
4548 for (const int f : IndexRange(b_nfaces)) {
4549 const int inst_off = instance * b_nfaces;
4550 const int fsize = b_face[f].size();
4551 const int foff_start = store.face_offsets[inst_off + f];
4552 store.face_offsets[inst_off + f + 1] = foff_start + fsize;
4553 for (int i = store.face_offsets[inst_off + f]; i < store.face_offsets[inst_off + f + 1];
4554 i++)
4555 {
4556 store.face_vert_indices[i] = b_face[f][i - store.face_offsets[inst_off + f]] +
4557 in_v_offset;
4558 }
4559 }
4560 cur_x += delta_x;
4561 ++instance;
4562 }
4563 cur_y += delta_y;
4564 cur_x = T(0);
4565 }
4566 if (invert) {
4567 for (const int f : IndexRange(tot_faces - 1)) {
4568 const int fstart = store.face_offsets[f];
4569 const int fend = store.face_offsets[f + 1];
4570 std::reverse(store.face_vert_indices.begin() + fstart,
4571 store.face_vert_indices.begin() + fend);
4572 }
4573 constexpr double margin = 0.25;
4574 T xmin = T(-margin);
4575 T ymin = T(-margin);
4576 T xmax = T(lets_per_line_num * delta_x + margin);
4577 T ymax = T(lines_num * delta_y + margin);
4578 const int rect_base = tot_face_verts - 4;
4579 store.vert[rect_base] = VecBase<T, 2>(xmin, ymin);
4580 store.vert[rect_base + 1] = VecBase<T, 2>(xmax, ymin);
4581 store.vert[rect_base + 2] = VecBase<T, 2>(xmax, ymax);
4582 store.vert[rect_base + 3] = VecBase<T, 2>(xmin, ymax);
4583 store.face_vert_indices[tot_face_verts - 4] = rect_base;
4584 store.face_vert_indices[tot_face_verts - 3] = rect_base + 1;
4585 store.face_vert_indices[tot_face_verts - 2] = rect_base + 2;
4586 store.face_vert_indices[tot_face_verts - 1] = rect_base + 3;
4587 store.face_offsets[tot_faces] = store.face_offsets[tot_faces - 1] + 4;
4588 }
4589
4591 in.vert = store.vert;
4592 in.face_offsets = store.face_offsets.as_span();
4593 in.face_vert_indices = store.face_vert_indices;
4594 in.edge = store.edge;
4595 in.epsilon = b_before_arcs_in.epsilon;
4596 in.needed_ids = needed_ids;
4597 double tstart = BLI_time_now_seconds();
4599 double tend = BLI_time_now_seconds();
4600 if (print_timing) {
4601 std::cout << "time = " << tend - tstart << "\n";
4602 }
4603 if (needed_ids == 0) {
4604 EXPECT_EQ(out.vert_orig.size(), 0);
4605 EXPECT_EQ(out.edge_orig.size(), 0);
4606 EXPECT_EQ(out.face_orig.size(), 0);
4607 }
4608 if (DO_DRAW) {
4609 std::string label = "Text arcpts=" + std::to_string(arc_points_num);
4610 if (lets_per_line_num > 1) {
4611 label += " linelen=" + std::to_string(lets_per_line_num);
4612 }
4613 if (lines_num > 1) {
4614 label += " lines=" + std::to_string(lines_num);
4615 }
4616 if (needed_ids == 0) {
4617 label += " no_ids";
4618 }
4619 if (otype != CDT_INSIDE_WITH_HOLES) {
4620 label += " otype=" + std::to_string(otype);
4621 }
4622 if (invert) {
4623 label += " invert";
4624 }
4625 graph_draw<T>(label, out.vert, out.edge, out.face);
4626 }
4627}
4628
4630
4631TEST(delaunay_d, TextB1)
4632{
4633 text_test<double>(1, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4634}
4635
4636TEST(delaunay_d, TextB10)
4637{
4638 text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4639}
4640
4641TEST(delaunay_d, TextB10_noids)
4642{
4643 text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, CDT_NO_ORIG_IDS, false);
4644}
4645
4646TEST(delaunay_d, TextB10_inside)
4647{
4648 text_test<double>(10, 1, 1, CDT_INSIDE, need_vef_ids, false);
4649}
4650
4651TEST(delaunay_d, TextB10_inside_noids)
4652{
4653 text_test<double>(10, 1, 1, CDT_INSIDE, CDT_NO_ORIG_IDS, false);
4654}
4655
4656TEST(delaunay_d, TextB10_constraints)
4657{
4658 text_test<double>(10, 1, 1, CDT_CONSTRAINTS, need_vef_ids, false);
4659}
4660
4661TEST(delaunay_d, TextB10_constraints_noids)
4662{
4663 text_test<double>(10, 1, 1, CDT_CONSTRAINTS, CDT_NO_ORIG_IDS, false);
4664}
4665
4666TEST(delaunay_d, TextB10_constraints_valid_bmesh)
4667{
4668 text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, need_vef_ids, false);
4669}
4670
4671TEST(delaunay_d, TextB10_constraints_valid_bmesh_noids)
4672{
4673 text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, CDT_NO_ORIG_IDS, false);
4674}
4675
4676TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes)
4677{
4678 text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, need_vef_ids, false);
4679}
4680
4681TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes_noids)
4682{
4683 text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, CDT_NO_ORIG_IDS, false);
4684}
4685
4686TEST(delaunay_d, TextB200)
4687{
4688 text_test<double>(200, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4689}
4690
4691TEST(delaunay_d, TextB10_10_10)
4692{
4693 text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4694}
4695
4696TEST(delaunay_d, TextB10_10_10_noids)
4697{
4698 text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES, CDT_NO_ORIG_IDS, false);
4699}
4700
4701TEST(delaunay_d, TextB1_inverted)
4702{
4703 /* Single B letter with inverted contours inside an outer rectangle.
4704 * The letter faces are wound CW (holes) inside the CCW outer rectangle. */
4705 text_test<double>(1, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, true);
4706}
4707
4708TEST(delaunay_d, TextB10_inverted)
4709{
4710 text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, true);
4711}
4712
4713TEST(delaunay_d, TextB10_inverted_nonzero)
4714{
4715 text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES_NONZERO, need_vef_ids, true);
4716}
4717
4718TEST(delaunay_d, TextB10_10_10_inverted_noids)
4719{
4720 text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES, CDT_NO_ORIG_IDS, true);
4721}
4722
4723TEST(delaunay_d, TextB10_20_20_inverted)
4724{
4725 text_test<double>(10, 20, 20, CDT_INSIDE_WITH_HOLES, CDT_NO_ORIG_IDS, true);
4726}
4727
4728# ifdef WITH_GMP
4729TEST(delaunay_m, TextB10)
4730{
4731 text_test<mpq_class>(10, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4732}
4733
4734TEST(delaunay_m, TextB200)
4735{
4736 text_test<mpq_class>(200, 1, 1, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4737}
4738
4739TEST(delaunay_m, TextB10_10_10)
4740{
4741 text_test<mpq_class>(10, 10, 10, CDT_INSIDE_WITH_HOLES, need_vef_ids, false);
4742}
4743
4744TEST(delaunay_m, TextB10_10_10_noids)
4745{
4746 text_test<mpq_class>(10, 10, 10, CDT_INSIDE_WITH_HOLES, CDT_NO_ORIG_IDS, false);
4747}
4748# endif
4749#endif
4750
4751#if DO_RANDOM_TESTS
4752
4753enum {
4754 RANDOM_PTS,
4755 RANDOM_SEGS,
4756 RANDOM_POLY,
4757 RANDOM_TILTED_GRID,
4758 RANDOM_CIRCLE,
4759 RANDOM_TRI_BETWEEN_CIRCLES,
4760};
4761
4762template<typename T>
4763void rand_delaunay_test(int test_kind,
4764 int start_lg_size,
4765 int max_lg_size,
4766 int reps_per_size,
4767 double param,
4768 CDT_output_type otype)
4769{
4770 constexpr bool print_timing = true;
4771 RNG *rng = BLI_rng_new(0);
4772 Array<double> times(max_lg_size + 1);
4773
4774 /* For powers of 2 sizes up to max_lg_size power of 2. */
4775 for (int lg_size = start_lg_size; lg_size <= max_lg_size; ++lg_size) {
4776 int size = 1 << lg_size;
4777 times[lg_size] = 0.0;
4778 if (size == 1 && test_kind != RANDOM_PTS) {
4779 continue;
4780 }
4781 /* Do 'rep' repetitions. */
4782 for (int rep = 0; rep < reps_per_size; ++rep) {
4783 /* First use test type and size to set npts, nedges, and nfaces. */
4784 int npts = 0;
4785 int nedges = 0;
4786 int nfaces = 0;
4787 std::string test_label;
4788 switch (test_kind) {
4789 case RANDOM_PTS: {
4790 npts = size;
4791 test_label = std::to_string(npts) + "Random points";
4792 break;
4793 }
4794 case RANDOM_SEGS: {
4795 npts = size;
4796 nedges = npts - 1;
4797 test_label = std::to_string(nedges) + "Random edges";
4798 break;
4799 }
4800 case RANDOM_POLY: {
4801 npts = size;
4802 nedges = npts;
4803 test_label = "Random poly with " + std::to_string(nedges) + " edges";
4804 break;
4805 }
4806 case RANDOM_TILTED_GRID: {
4807 /* A 'size' x 'size' grid of points, tilted by angle 'param'.
4808 * Edges will go from left ends to right ends and tops to bottoms,
4809 * so 2 x size of them.
4810 * Depending on epsilon, the vertical-ish edges may or may not go
4811 * through the intermediate vertices, but the horizontal ones always should.
4812 * 'param' is slope of tilt of vertical lines.
4813 */
4814 npts = size * size;
4815 nedges = 2 * size;
4816 test_label = "Tilted grid " + std::to_string(npts) + "x" + std::to_string(npts) +
4817 " (tilt=" + std::to_string(param) + ")";
4818 break;
4819 }
4820 case RANDOM_CIRCLE: {
4821 /* A circle with 'size' points, a random start angle,
4822 * and equal spacing thereafter. Will be input as one face.
4823 */
4824 npts = size;
4825 nfaces = 1;
4826 test_label = "Circle with " + std::to_string(npts) + " points";
4827 break;
4828 }
4829 case RANDOM_TRI_BETWEEN_CIRCLES: {
4830 /* A set of 'size' triangles, each has two random points on the unit circle,
4831 * and the third point is a random point on the circle with radius 'param'.
4832 * Each triangle will be input as a face.
4833 */
4834 npts = 3 * size;
4835 nfaces = size;
4836 test_label = "Random " + std::to_string(nfaces) +
4837 " triangles between circles (inner radius=" + std::to_string(param) + ")";
4838 break;
4839 }
4840 default:
4841 std::cout << "unknown delaunay test type\n";
4842 BLI_rng_free(rng);
4843 return;
4844 }
4845 if (otype != CDT_FULL) {
4846 if (otype == CDT_INSIDE) {
4847 test_label += " (inside)";
4848 }
4849 else if (otype == CDT_CONSTRAINTS) {
4850 test_label += " (constraints)";
4851 }
4852 else if (otype == CDT_CONSTRAINTS_VALID_BMESH) {
4853 test_label += " (valid bmesh)";
4854 }
4855 }
4856
4857 InputStorage<T> store;
4858 store.vert.reinitialize(npts);
4859 if (nedges > 0) {
4860 store.edge.reinitialize(nedges);
4861 }
4862 if (nfaces > 0) {
4863 store.face_offsets.reinitialize(nfaces + 1);
4864 }
4865
4866 /* Make vertices and edges or faces. */
4867 switch (test_kind) {
4868 case RANDOM_PTS:
4869 case RANDOM_SEGS:
4870 case RANDOM_POLY: {
4871 for (int i = 0; i < size; i++) {
4872 store.vert[i][0] = T(BLI_rng_get_double(rng)); /* will be in range in [0,1) */
4873 store.vert[i][1] = T(BLI_rng_get_double(rng));
4874 if (test_kind != RANDOM_PTS) {
4875 if (i > 0) {
4876 store.edge[i - 1][0] = i - 1;
4877 store.edge[i - 1][1] = i;
4878 }
4879 }
4880 }
4881 if (test_kind == RANDOM_POLY) {
4882 store.edge[size - 1][0] = size - 1;
4883 store.edge[size - 1][1] = 0;
4884 }
4885 break;
4886 }
4887 case RANDOM_TILTED_GRID: {
4888 for (int i = 0; i < size; ++i) {
4889 for (int j = 0; j < size; ++j) {
4890 store.vert[i * size + j][0] = T(i * param + j);
4891 store.vert[i * size + j][1] = T(i);
4892 }
4893 }
4894 for (int i = 0; i < size; ++i) {
4895 /* Horizontal edges: connect `p(i,0)` to `p(i,size-1)`. */
4896 store.edge[i][0] = i * size;
4897 store.edge[i][1] = i * size + size - 1;
4898 /* Vertical edges: connect `p(0,i)` to `p(size-1,i)`. */
4899 store.edge[size + i][0] = i;
4900 store.edge[size + i][1] = (size - 1) * size + i;
4901 }
4902 break;
4903 }
4904 case RANDOM_CIRCLE: {
4905 double start_angle = BLI_rng_get_double(rng) * 2.0 * M_PI;
4906 double angle_delta = 2.0 * M_PI / size;
4907 store.face_vert_indices.reinitialize(size);
4908 for (int i = 0; i < size; i++) {
4909 store.vert[i][0] = T(cos(start_angle + i * angle_delta));
4910 store.vert[i][1] = T(sin(start_angle + i * angle_delta));
4911 store.face_vert_indices[i] = i;
4912 }
4913 store.face_offsets[0] = 0;
4914 store.face_offsets[1] = size;
4915 break;
4916 }
4917 case RANDOM_TRI_BETWEEN_CIRCLES: {
4918 store.face_vert_indices.reinitialize(3 * size);
4919 store.face_offsets[0] = 0;
4920 for (int i = 0; i < size; i++) {
4921 /* Get three random angles in [0, 2pi). */
4922 double angle1 = BLI_rng_get_double(rng) * 2.0 * M_PI;
4923 double angle2 = BLI_rng_get_double(rng) * 2.0 * M_PI;
4924 double angle3 = BLI_rng_get_double(rng) * 2.0 * M_PI;
4925 int ia = 3 * i;
4926 int ib = 3 * i + 1;
4927 int ic = 3 * i + 2;
4928 store.vert[ia][0] = T(cos(angle1));
4929 store.vert[ia][1] = T(sin(angle1));
4930 store.vert[ib][0] = T(cos(angle2));
4931 store.vert[ib][1] = T(sin(angle2));
4932 store.vert[ic][0] = T((param * cos(angle3)));
4933 store.vert[ic][1] = T((param * sin(angle3)));
4934 /* Put the coordinates in CCW order. */
4935 store.face_vert_indices[ia] = ia;
4936 int orient = orient2d(store.vert[ia], store.vert[ib], store.vert[ic]);
4937 store.face_vert_indices[ib] = orient >= 0 ? ib : ic;
4938 store.face_vert_indices[ic] = orient >= 0 ? ic : ib;
4939 store.face_offsets[i + 1] = store.face_offsets[i] + 3;
4940 }
4941 break;
4942 }
4943 }
4944
4946 in.vert = store.vert;
4947 in.edge = store.edge;
4948 in.face_offsets = store.face_offsets.as_span();
4949 in.face_vert_indices = store.face_vert_indices;
4950 /* Can change this to time effect of calculating ids. */
4951 in.needed_ids = need_vef_ids;
4952
4953 /* Run the test. */
4954 double tstart = BLI_time_now_seconds();
4956 EXPECT_NE(out.vert.size(), 0);
4957 times[lg_size] += BLI_time_now_seconds() - tstart;
4958 if (DO_DRAW) {
4959 graph_draw<T>(test_label, out.vert, out.edge, out.face);
4960 }
4961 }
4962 }
4963 if (print_timing) {
4964 std::cout << "\nsize,time\n";
4965 for (int lg_size = 0; lg_size <= max_lg_size; lg_size++) {
4966 int size = 1 << lg_size;
4967 std::cout << size << "," << times[lg_size] << "\n";
4968 }
4969 }
4970 BLI_rng_free(rng);
4971}
4972
4973TEST(delaunay_d, RandomPts)
4974{
4975 rand_delaunay_test<double>(RANDOM_PTS, 0, 7, 1, 0.0, CDT_FULL);
4976}
4977
4978TEST(delaunay_d, RandomSegs)
4979{
4980 rand_delaunay_test<double>(RANDOM_SEGS, 1, 7, 1, 0.0, CDT_FULL);
4981}
4982
4983TEST(delaunay_d, RandomPoly)
4984{
4985 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_FULL);
4986}
4987
4988TEST(delaunay_d, RandomPolyConstraints)
4989{
4990 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS);
4991}
4992
4993TEST(delaunay_d, RandomPolyValidBmesh)
4994{
4995 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS_VALID_BMESH);
4996}
4997
4998TEST(delaunay_d, Grid)
4999{
5000 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0, CDT_FULL);
5001}
5002
5003TEST(delaunay_d, TiltedGridA)
5004{
5005 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0, CDT_FULL);
5006}
5007
5008TEST(delaunay_d, TiltedGridB)
5009{
5010 rand_delaunay_test<double>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01, CDT_FULL);
5011}
5012
5013TEST(delaunay_d, RandomCircle)
5014{
5015 rand_delaunay_test<double>(RANDOM_CIRCLE, 1, 7, 1, 0.0, CDT_FULL);
5016}
5017
5018TEST(delaunay_d, RandomTrisCircle)
5019{
5020 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25, CDT_FULL);
5021}
5022
5023TEST(delaunay_d, RandomTrisCircleB)
5024{
5025 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1e-4, CDT_FULL);
5026}
5027
5028# ifdef WITH_GMP
5029TEST(delaunay_m, RandomPts)
5030{
5031 rand_delaunay_test<mpq_class>(RANDOM_PTS, 0, 7, 1, 0.0, CDT_FULL);
5032}
5033
5034TEST(delaunay_m, RandomSegs)
5035{
5036 rand_delaunay_test<mpq_class>(RANDOM_SEGS, 1, 7, 1, 0.0, CDT_FULL);
5037}
5038
5039TEST(delaunay_m, RandomPoly)
5040{
5041 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_FULL);
5042}
5043
5044TEST(delaunay_d, RandomPolyInside)
5045{
5046 rand_delaunay_test<double>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_INSIDE);
5047}
5048
5049TEST(delaunay_m, RandomPolyInside)
5050{
5051 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_INSIDE);
5052}
5053
5054TEST(delaunay_m, RandomPolyConstraints)
5055{
5056 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS);
5057}
5058
5059TEST(delaunay_m, RandomPolyValidBmesh)
5060{
5061 rand_delaunay_test<mpq_class>(RANDOM_POLY, 1, 7, 1, 0.0, CDT_CONSTRAINTS_VALID_BMESH);
5062}
5063
5064TEST(delaunay_m, Grid)
5065{
5066 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.0, CDT_FULL);
5067}
5068
5069TEST(delaunay_m, TiltedGridA)
5070{
5071 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 1.0, CDT_FULL);
5072}
5073
5074TEST(delaunay_m, TiltedGridB)
5075{
5076 rand_delaunay_test<mpq_class>(RANDOM_TILTED_GRID, 1, 6, 1, 0.01, CDT_FULL);
5077}
5078
5079TEST(delaunay_m, RandomCircle)
5080{
5081 rand_delaunay_test<mpq_class>(RANDOM_CIRCLE, 1, 7, 1, 0.0, CDT_FULL);
5082}
5083
5084TEST(delaunay_m, RandomTrisCircle)
5085{
5086 rand_delaunay_test<mpq_class>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 0.25, CDT_FULL);
5087}
5088
5089TEST(delaunay_m, RandomTrisCircleB)
5090{
5091 rand_delaunay_test<double>(RANDOM_TRI_BETWEEN_CIRCLES, 1, 6, 1, 1e-4, CDT_FULL);
5092}
5093# endif
5094
5095#endif
5096
5097} // namespace blender::meshintersect
Math vector functions needed specifically for mesh intersect and boolean.
#define M_PI_2
#define M_PI
Random number functions.
Platform independent time functions.
Read Blender memory allocation and freeing.
#define BLI_assert(a)
#define ELEM(...)
btScalar max
int64_t size() const
Definition BLI_array.hh:267
Span< T > as_span() const
Definition BLI_array.hh:254
const T & last(const int64_t n=0) const
Definition BLI_array.hh:307
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr IndexRange()=default
int64_t size() const
void append(const T &value)
Array< Vector< uint32_t > > vert_orig
Array< Vector< uint32_t > > face_orig
Array< Vector< uint32_t > > edge_orig
#define SY(y)
#define SX(x)
#define sin
#define cos
#define abs
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
float2x2 invert(float2x2 mat)
float3x3 scale(float3x3 mat, float2 scale)
#define EXPECT_FALSE(result)
#define EXPECT_LT(result, expect)
#define EXPECT_GE(result, expect)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_EQ(result, expect)
#define EXPECT_NEAR(result, expect, threshold)
#define DO_DRAW
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
#define T
int size(const AssetLibraryReference *library_reference)
static int get_orig_index(const Span< Vector< uint32_t > > out_to_orig, int orig_index)
void expect_coord_near(const VecBase< T, 2 > &testco, const VecBase< T, 2 > &refco)
bool output_vert_is_intersection_and_has_edge_input_ids(const CDT_result< T > &out, int out_vert_index, int in_edge1_index, int in_edge2_index)
int get_output_edge_index(const CDT_result< T > &out, int out_index_1, int out_index_2)
void graph_draw(const std::string &label, const Span< VecBase< T, 2 > > verts, const Span< int2 > edges, const Span< Vector< int > > faces)
void even_odd_coincident_polygons_needed_ids_stable_test()
int get_output_tri_index(const CDT_result< T > &out, int out_index_1, int out_index_2, int out_index_3)
std::ostream & operator<<(std::ostream &stream, const FatCo< T > &co)
int get_vertex_by_coord(const CDT_result< T > &out, double x, double y)
CDT_input< T > fill_input_from_string(const char *spec, InputStorage< T > &r_storage)
bool output_face_has_input_id(const CDT_result< T > &out, int out_face_index, uint32_t in_face_index)
double math_to_double(const T)
CDT_result< T > delaunay_2d_calc(const CDT_input< T > &input, CDT_output_type output_type)
int get_output_face_index(const CDT_result< T > &out, const Array< int > &poly)
bool output_edge_has_input_id(const CDT_result< T > &out, int out_edge_index, uint32_t in_edge_index)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
double BLI_rng_get_double(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:85
int orient2d(const double2 &a, const double2 &b, const double2 &c)
@ CDT_INSIDE_WITH_HOLES
@ 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
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
unsigned int uint32_t
Definition BKE_text.h:81
VecBase< int32_t, 2 > int2
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
double BLI_time_now_seconds()
Definition time.cc:30
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define min(a, b)
Definition sort.cc:38