Blender V5.3
BLI_polyfill_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/* Use to write out OBJ files, handy for checking output */
8// #define USE_OBJ_PREVIEW
9
10/* test every possible offset and reverse */
11#define USE_COMBINATIONS_ALL
12#define USE_BEAUTIFY
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_array_utils_c.hh"
17#include "BLI_map.hh"
18#include "BLI_math_geom_c.hh"
19#include "BLI_ordered_edge.hh"
20#include "BLI_polyfill_2d.hh"
21#include "BLI_utildefines.hh"
22
23#ifdef USE_OBJ_PREVIEW
24# include "BLI_string.hh"
25#endif
26
27#ifdef USE_BEAUTIFY
28# include "BLI_heap.hh"
29# include "BLI_memarena.hh"
31#endif
32
33namespace blender {
34
35static void polyfill_to_obj(const char *id,
36 const float poly[][2],
37 const uint poly_num,
38 const uint tris[][3],
39 const uint tris_num);
40
46
47/* -------------------------------------------------------------------- */
48/* test utility functions */
49
50#define TRI_ERROR_VALUE uint(-1)
51
52static void test_valid_polyfill_prepare(uint tris[][3], uint tris_num)
53{
54 uint i;
55 for (i = 0; i < tris_num; i++) {
56 uint j;
57 for (j = 0; j < 3; j++) {
58 tris[i][j] = TRI_ERROR_VALUE;
59 }
60 }
61}
62
70static void test_polyfill_simple(const float /*poly*/[][2],
71 const uint poly_num,
72 const uint tris[][3],
73 const uint tris_num)
74{
75 uint i;
76 int *used_num = MEM_new_array_zeroed<int>(poly_num, __func__);
77 for (i = 0; i < tris_num; i++) {
78 uint j;
79 for (j = 0; j < 3; j++) {
80 EXPECT_NE(TRI_ERROR_VALUE, tris[i][j]);
81 used_num[tris[i][j]] += 1;
82 }
83 EXPECT_NE(tris[i][0], tris[i][1]);
84 EXPECT_NE(tris[i][1], tris[i][2]);
85 EXPECT_NE(tris[i][2], tris[i][0]);
86 }
87 for (i = 0; i < poly_num; i++) {
88 EXPECT_NE(0, used_num[i]);
89 }
90 MEM_delete(used_num);
91}
92
93static void test_polyfill_topology(const float /*poly*/[][2],
94 const uint poly_num,
95 const uint tris[][3],
96 const uint tris_num)
97{
98 Map<OrderedEdge, int> edgehash;
99 uint i;
100 for (i = 0; i < tris_num; i++) {
101 uint j;
102 for (j = 0; j < 3; j++) {
103 const uint v1 = tris[i][j];
104 const uint v2 = tris[i][(j + 1) % 3];
105 edgehash.add_or_modify(
106 {v1, v2}, [](int *value) { *value = 1; }, [](int *value) { (*value)++; });
107 }
108 }
109 EXPECT_EQ(edgehash.size(), poly_num + (poly_num - 3));
110
111 for (i = 0; i < poly_num; i++) {
112 const uint v1 = i;
113 const uint v2 = (i + 1) % poly_num;
114 EXPECT_TRUE(edgehash.contains({v1, v2}));
115 EXPECT_EQ(edgehash.lookup({v1, v2}), 1);
116 }
117
118 for (const int value : edgehash.values()) {
119 EXPECT_TRUE(ELEM(value, 1, 2));
120 }
121}
122
126static void test_polyfill_winding(const float poly[][2],
127 const uint /*poly_num*/,
128 const uint tris[][3],
129 const uint tris_num)
130{
131 uint i;
132 uint count[2] = {0, 0};
133 for (i = 0; i < tris_num; i++) {
134 float winding_test = cross_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
135 if (fabsf(winding_test) > FLT_EPSILON) {
136 count[winding_test < 0.0f] += 1;
137 }
138 }
139 EXPECT_TRUE(ELEM(0, count[0], count[1]));
140}
141
145static void test_polyfill_area(const float poly[][2],
146 const uint poly_num,
147 const uint tris[][3],
148 const uint tris_num)
149{
150 uint i;
151 const float area_total = area_poly_v2(poly, poly_num);
152 float area_total_tris = 0.0f;
153 const float eps_abs = 0.00001f;
154 const float eps = area_total > 1.0f ? (area_total * eps_abs) : eps_abs;
155 for (i = 0; i < tris_num; i++) {
156 area_total_tris += area_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
157 }
158 EXPECT_NEAR(area_total, area_total_tris, eps);
159}
160
164static void test_polyfill_area_tri_nonzero(const float poly[][2],
165 const uint /*poly_num*/,
166 const uint tris[][3],
167 const uint tris_num)
168{
169 uint i;
170 uint total = 0;
171 for (i = 0; i < tris_num; i++) {
172 if (area_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]) < 1e-6f) {
173 total += 1;
174 }
175 }
176 EXPECT_EQ(total, 0);
177}
178
179/* -------------------------------------------------------------------- */
180/* Macro and helpers to manage checking */
184static void test_polyfill_template_check(const char *id,
185 const ePolyFill2DTestFlag test_flag,
186 const float poly[][2],
187 const uint poly_num,
188 const uint tris[][3],
189 const uint tris_num)
190{
191 test_polyfill_simple(poly, poly_num, tris, tris_num);
192 test_polyfill_topology(poly, poly_num, tris, tris_num);
193 if (!(test_flag & POLYFILL2D_TEST_IS_DEGENERATE)) {
194 test_polyfill_winding(poly, poly_num, tris, tris_num);
195
196 test_polyfill_area(poly, poly_num, tris, tris_num);
197
198 /* Only check when non-degenerate, because the number of zero area triangles
199 * are undefined for degenerate polygons as there is no correct solution. */
200 if (test_flag & POLYFILL2D_TEST_NO_ZERO_AREA_TRIS) {
201 test_polyfill_area_tri_nonzero(poly, poly_num, tris, tris_num);
202 }
203 }
204 polyfill_to_obj(id, poly, poly_num, tris, tris_num);
205}
206
207static void test_polyfill_template(const char *id,
208 const ePolyFill2DTestFlag test_flag,
209 const float poly[][2],
210 const uint poly_num,
211 uint tris[][3],
212 const uint tris_num)
213{
214 test_valid_polyfill_prepare(tris, tris_num);
215 BLI_polyfill_calc(poly, poly_num, 0, tris);
216
217 /* check all went well */
218 test_polyfill_template_check(id, test_flag, poly, poly_num, tris, tris_num);
219
220#ifdef USE_BEAUTIFY
221 /* check beautify gives good results too */
222 {
225
226 BLI_polyfill_beautify(poly, poly_num, tris, pf_arena, pf_heap);
227
228 test_polyfill_template_check(id, test_flag, poly, poly_num, tris, tris_num);
229
230 BLI_memarena_free(pf_arena);
231 BLI_heap_free(pf_heap, nullptr);
232 }
233#endif
234}
235
236static void test_polyfill_template_flip_sign(const char *id,
237 const ePolyFill2DTestFlag test_flag,
238 const float poly[][2],
239 const uint poly_num,
240 uint tris[][3],
241 const uint tris_num)
242{
243 float (*poly_copy)[2] = MEM_new_array_uninitialized<float[2]>(poly_num, id);
244 for (int flip_x = 0; flip_x < 2; flip_x++) {
245 for (int flip_y = 0; flip_y < 2; flip_y++) {
246 float sign_x = flip_x ? -1.0f : 1.0f;
247 float sign_y = flip_y ? -1.0f : 1.0f;
248 for (int i = 0; i < poly_num; i++) {
249 poly_copy[i][0] = poly[i][0] * sign_x;
250 poly_copy[i][1] = poly[i][1] * sign_y;
251 }
252 test_polyfill_template(id, test_flag, poly_copy, poly_num, tris, tris_num);
253 }
254 }
255 MEM_delete(poly_copy);
256}
257
258#ifdef USE_COMBINATIONS_ALL
259static void test_polyfill_template_main(const char *id,
260 const ePolyFill2DTestFlag test_flag,
261 const float poly[][2],
262 const uint poly_num,
263 uint tris[][3],
264 const uint tris_num)
265{
266 /* overkill? - try at _every_ offset & reverse */
267 uint poly_reverse;
268 float (*poly_copy)[2] = MEM_new_array_uninitialized<float[2]>(poly_num, id);
269 float tmp[2];
270
271 memcpy(poly_copy, poly, sizeof(float[2]) * poly_num);
272
273 for (poly_reverse = 0; poly_reverse < 2; poly_reverse++) {
274 uint poly_cycle;
275
276 if (poly_reverse) {
277 BLI_array_reverse(poly_copy, poly_num);
278 }
279
280 for (poly_cycle = 0; poly_cycle < poly_num; poly_cycle++) {
281 // printf("polytest %s ofs=%d, reverse=%d\n", id, poly_cycle, poly_reverse);
282 test_polyfill_template_flip_sign(id, test_flag, poly, poly_num, tris, tris_num);
283
284 /* cycle */
285 copy_v2_v2(tmp, poly_copy[0]);
286 memmove(&poly_copy[0], &poly_copy[1], (poly_num - 1) * sizeof(float[2]));
287 copy_v2_v2(poly_copy[poly_num - 1], tmp);
288 }
289 }
290
291 MEM_delete(poly_copy);
292}
293#else /* USE_COMBINATIONS_ALL */
294static void test_polyfill_template_main(const char *id,
295 const ePolyFill2DTestFlag test_flag,
296 const float poly[][2],
297 const uint poly_num,
298 uint tris[][3],
299 const uint tris_num)
300{
301 test_polyfill_template_flip_sign(id, test_flag, poly, poly_num, tris, tris_num);
302}
303#endif /* USE_COMBINATIONS_ALL */
304
305#define TEST_POLYFILL_TEMPLATE_STATIC(poly, test_flag) \
306 { \
307 uint tris[POLY_TRI_COUNT(ARRAY_SIZE(poly))][3]; \
308 const uint poly_num = ARRAY_SIZE(poly); \
309 const uint tris_num = ARRAY_SIZE(tris); \
310 const char *id = typeid(*this).name(); \
311\
312 test_polyfill_template_main(id, test_flag, poly, poly_num, tris, tris_num); \
313 } \
314 (void)0
315
316/* -------------------------------------------------------------------- */
317/* visualization functions (not needed for testing) */
318
319#ifdef USE_OBJ_PREVIEW
320static void polyfill_to_obj(const char *id,
321 const float poly[][2],
322 const uint poly_num,
323 const uint tris[][3],
324 const uint tris_num)
325{
326 char path[1024];
327 FILE *f;
328 uint i;
329
330 SNPRINTF(path, "%s.obj", id);
331
332 f = fopen(path, "w");
333 if (!f) {
334 return;
335 }
336
337 for (i = 0; i < poly_num; i++) {
338 fprintf(f, "v %f %f 0.0\n", UNPACK2(poly[i]));
339 }
340
341 for (i = 0; i < tris_num; i++) {
342 fprintf(f, "f %u %u %u\n", UNPACK3_EX(1 +, tris[i], ));
343 }
344
345 fclose(f);
346}
347#else
348static void polyfill_to_obj(const char *id,
349 const float poly[][2],
350 const uint poly_num,
351 const uint tris[][3],
352 const uint tris_num)
353{
354 (void)id;
355 (void)poly, (void)poly_num;
356 (void)tris, (void)tris_num;
357}
358#endif /* USE_OBJ_PREVIEW */
359
360/* -------------------------------------------------------------------- */
361/* tests */
362
399
400#define POLY_TRI_COUNT(len) ((len) - 2)
401
402/* A counterclockwise triangle */
403TEST(polyfill2d, TriangleCCW)
404{
405 const float poly[][2] = {{0, 0}, {0, 1}, {1, 0}};
407}
408
409/* A counterclockwise square */
410TEST(polyfill2d, SquareCCW)
411{
412 const float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
414}
415
416/* A clockwise square */
417TEST(polyfill2d, SquareCW)
418{
419 const float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
421}
422
423/* Star-fleet insignia. */
424TEST(polyfill2d, Starfleet)
425{
426 const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
428}
429
430/* Star-fleet insignia with repeated point. */
431TEST(polyfill2d, StarfleetDegenerate)
432{
433 const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
435}
436
437/* Three collinear points */
438TEST(polyfill2d, 3Colinear)
439{
440 const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}};
442}
443
444/* Four collinear points */
445TEST(polyfill2d, 4Colinear)
446{
447 const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
449}
450
451/* Non-consecutive collinear points */
452TEST(polyfill2d, UnorderedColinear)
453{
454 const float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0}};
456}
457
458/* Plus shape */
459TEST(polyfill2d, PlusShape)
460{
461 const float poly[][2] = {
462 {1, 0},
463 {2, 0},
464 {2, 1},
465 {3, 1},
466 {3, 2},
467 {2, 2},
468 {2, 3},
469 {1, 3},
470 {1, 2},
471 {0, 2},
472 {0, 1},
473 {1, 1},
474 };
476}
477
478/* Star shape */
479TEST(polyfill2d, StarShape)
480{
481 const float poly[][2] = {{4, 0}, {5, 3}, {8, 4}, {5, 5}, {4, 8}, {3, 5}, {0, 4}, {3, 3}};
483}
484
485/* U shape */
486TEST(polyfill2d, UShape)
487{
488 const float poly[][2] = {
489 {1, 0}, {2, 0}, {3, 1}, {3, 3}, {2, 3}, {2, 1}, {1, 1}, {1, 3}, {0, 3}, {0, 1}};
491}
492
493/* Spiral */
494TEST(polyfill2d, Spiral)
495{
496 const float poly[][2] = {
497 {1, 0},
498 {4, 0},
499 {5, 1},
500 {5, 4},
501 {4, 5},
502 {1, 5},
503 {0, 4},
504 {0, 3},
505 {1, 2},
506 {2, 2},
507 {3, 3},
508 {1, 3},
509 {1, 4},
510 {4, 4},
511 {4, 1},
512 {0, 1},
513 };
515}
516
517/* Test case from http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml */
518TEST(polyfill2d, TestFlipCode)
519{
520 const float poly[][2] = {
521 {0, 6},
522 {0, 0},
523 {3, 0},
524 {4, 1},
525 {6, 1},
526 {8, 0},
527 {12, 0},
528 {13, 2},
529 {8, 2},
530 {8, 4},
531 {11, 4},
532 {11, 6},
533 {6, 6},
534 {4, 3},
535 {2, 6},
536 };
538}
539
540/* Self-intersection */
541TEST(polyfill2d, SelfIntersect)
542{
543 const float poly[][2] = {{0, 0}, {1, 1}, {2, -1}, {3, 1}, {4, 0}};
545}
546
547/* Self-touching */
548TEST(polyfill2d, SelfTouch)
549{
550 const float poly[][2] = {
551 {0, 0},
552 {4, 0},
553 {4, 4},
554 {2, 4},
555 {2, 3},
556 {3, 3},
557 {3, 1},
558 {1, 1},
559 {1, 3},
560 {2, 3},
561 {2, 4},
562 {0, 4},
563 };
565}
566
567/* Self-overlapping */
568TEST(polyfill2d, SelfOverlap)
569{
570 const float poly[][2] = {
571 {0, 0},
572 {4, 0},
573 {4, 4},
574 {1, 4},
575 {1, 3},
576 {3, 3},
577 {3, 1},
578 {1, 1},
579 {1, 3},
580 {3, 3},
581 {3, 4},
582 {0, 4},
583 };
585}
586
587/* Test case from http://www.davdata.nl/math/polygons.html */
588TEST(polyfill2d, TestDavData)
589{
590 const float poly[][2] = {
591 {190, 480}, {140, 180}, {310, 100}, {330, 390}, {290, 390}, {280, 260}, {220, 260},
592 {220, 430}, {370, 430}, {350, 30}, {50, 30}, {160, 560}, {730, 510}, {710, 20},
593 {410, 30}, {470, 440}, {640, 410}, {630, 140}, {590, 140}, {580, 360}, {510, 370},
594 {510, 60}, {650, 70}, {660, 450}, {190, 480},
595 };
597}
598
599/* Issue 815, http://code.google.com/p/libgdx/issues/detail?id=815 */
600TEST(polyfill2d, Issue815)
601{
602 const float poly[][2] = {
603 {-2.0f, 0.0f},
604 {-2.0f, 0.5f},
605 {0.0f, 1.0f},
606 {0.5f, 2.875f},
607 {1.0f, 0.5f},
608 {1.5f, 1.0f},
609 {2.0f, 1.0f},
610 {2.0f, 0.0f},
611 };
613}
614
615/* Issue 207, comment #1, http://code.google.com/p/libgdx/issues/detail?id=207#c1 */
616TEST(polyfill2d, Issue207_1)
617{
618 const float poly[][2] = {
619 {72.42465f, 197.07095f},
620 {78.485535f, 189.92776f},
621 {86.12059f, 180.92929f},
622 {99.68253f, 164.94557f},
623 {105.24325f, 165.79604f},
624 {107.21862f, 166.09814f},
625 {112.41958f, 162.78253f},
626 {113.73238f, 161.94562f},
627 {123.29477f, 167.93805f},
628 {126.70667f, 170.07617f},
629 {73.22717f, 199.51062f},
630 };
632}
633
634/* Issue 207, comment #11, http://code.google.com/p/libgdx/issues/detail?id=207#c11 */
635/* Also on issue 1081, http://code.google.com/p/libgdx/issues/detail?id=1081 */
636TEST(polyfill2d, Issue207_11)
637{
638 const float poly[][2] = {
639 {2400.0f, 480.0f}, {2400.0f, 176.0f}, {1920.0f, 480.0f},
640 {1920.0459f, 484.22314f}, {1920.1797f, 487.91016f}, {1920.3955f, 491.0874f},
641 {1920.6875f, 493.78125f}, {1921.0498f, 496.01807f}, {1921.4766f, 497.82422f},
642 {1921.9619f, 499.22607f}, {1922.5f, 500.25f}, {1923.085f, 500.92236f},
643 {1923.7109f, 501.26953f}, {1924.3721f, 501.31787f}, {1925.0625f, 501.09375f},
644 {1925.7764f, 500.62354f}, {1926.5078f, 499.9336f}, {1927.251f, 499.0503f},
645 {1928.0f, 498.0f}, {1928.749f, 496.80908f}, {1929.4922f, 495.5039f},
646 {1930.2236f, 494.11084f}, {1930.9375f, 492.65625f}, {1931.6279f, 491.1665f},
647 {1932.2891f, 489.66797f}, {1932.915f, 488.187f}, {1933.5f, 486.75f},
648 {1934.0381f, 485.3833f}, {1934.5234f, 484.11328f}, {1934.9502f, 482.9663f},
649 {1935.3125f, 481.96875f}, {1935.6045f, 481.14697f}, {1935.8203f, 480.52734f},
650 {1935.9541f, 480.13623f}, {1936.0f, 480.0f}};
652}
653
654/* Issue 1407, http://code.google.com/p/libgdx/issues/detail?id=1407 */
655TEST(polyfill2d, Issue1407)
656{
657 const float poly[][2] = {
658 {3.914329f, 1.9008259f},
659 {4.414321f, 1.903619f},
660 {4.8973203f, 1.9063174f},
661 {5.4979978f, 1.9096732f},
662 };
664}
665
666/* Issue 1407, http://code.google.com/p/libgdx/issues/detail?id=1407, */
667/* with an additional point to show what is happening. */
668TEST(polyfill2d, Issue1407_pt)
669{
670 const float poly[][2] = {
671 {3.914329f, 1.9008259f},
672 {4.414321f, 1.903619f},
673 {4.8973203f, 1.9063174f},
674 {5.4979978f, 1.9096732f},
675 {4, 4},
676 };
678}
679
680/* Simplified from Blender bug #40777 */
681TEST(polyfill2d, IssueT40777_colinear)
682{
683 const float poly[][2] = {
684 {0.7, 0.37}, {0.7, 0}, {0.76, 0}, {0.76, 0.4}, {0.83, 0.4}, {0.83, 0}, {0.88, 0},
685 {0.88, 0.4}, {0.94, 0.4}, {0.94, 0}, {1, 0}, {1, 0.4}, {0.03, 0.62}, {0.03, 0.89},
686 {0.59, 0.89}, {0.03, 1}, {0, 1}, {0, 0}, {0.03, 0}, {0.03, 0.37},
687 };
689}
690
691/* Blender bug #41986 */
692TEST(polyfill2d, IssueT41986_axis_align)
693{
694 const float poly[][2] = {
695 {-0.25, -0.07}, {-0.25, 0.27}, {-1.19, 0.14}, {-0.06, 0.73}, {0.17, 1.25},
696 {-0.25, 1.07}, {-0.38, 1.02}, {-0.25, 0.94}, {-0.40, 0.90}, {-0.41, 0.86},
697 {-0.34, 0.83}, {-0.25, 0.82}, {-0.66, 0.73}, {-0.56, 1.09}, {-0.25, 1.10},
698 {0.00, 1.31}, {-0.03, 1.47}, {-0.25, 1.53}, {0.12, 1.62}, {0.36, 1.07},
699 {0.12, 0.67}, {0.29, 0.57}, {0.44, 0.45}, {0.57, 0.29}, {0.66, 0.12},
700 {0.68, 0.06}, {0.57, -0.36}, {-0.25, -0.37}, {0.49, -0.74}, {-0.59, -1.21},
701 {-0.25, -0.15}, {-0.46, -0.52}, {-1.08, -0.83}, {-1.45, -0.33}, {-1.25, -0.04}};
702
704}
705
706/* Blender bug #52834 */
707TEST(polyfill2d, IssueT52834_axis_align_co_linear)
708{
709 const float poly[][2] = {
710 {40, 0}, {36, 0}, {36, 5}, {35, 5}, {35, 0}, {30, 0}, {30, 5}, {29, 5},
711 {29, 0}, {24, 0}, {24, 3}, {23, 4}, {23, 0}, {18, 0}, {18, 5}, {17, 5},
712 {17, 0}, {12, 0}, {12, 5}, {11, 5}, {11, 0}, {6, 0}, {6, 5}, {5, 5},
713 {5, 0}, {0, 0}, {0, 5}, {-1, 5}, {-1, 0}, {-6, 0}, {-9, -3}, {-6, -3},
714 {-6, -2}, {-1, -2}, {0, -2}, {5, -2}, {6, -2}, {11, -2}, {12, -2}, {17, -2},
715 {18, -2}, {23, -2}, {24, -2}, {29, -2}, {30, -2}, {35, -2}, {36, -2}, {40, -2},
716 };
717
719}
720
721/* Blender bug #67109 (version a). */
722/* Multiple versions are offset & rotated, this fails in cases where others works. */
723TEST(polyfill2d, IssueT67109_axis_align_co_linear_a)
724{
725 const float poly[][2] = {
726 {3.2060661, -11.438997},
727 {2.8720665, -5.796999},
728 {-2.8659325, -5.796999},
729 {-2.8659325, -8.307999},
730 {-3.2549324, -11.438997},
731 {-2.8659325, -5.4869995},
732 {2.8720665, -5.4869995},
733 {2.8720665, -2.9759989},
734 {2.8720665, -2.6659985},
735 {2.8720665, -0.15499878},
736 };
738}
739
740/* Blender bug #67109, (version b). */
741TEST(polyfill2d, IssueT67109_axis_align_co_linear_b)
742{
743 const float poly[][2] = {
744 {32.41416, -12.122593},
745 {28.094929, -8.477332},
746 {24.141455, -12.636018},
747 {25.96133, -14.366093},
748 {27.96254, -16.805279},
749 {23.916779, -12.422427},
750 {27.870255, -8.263744},
751 {26.050375, -6.533667},
752 {25.825695, -6.320076},
753 {24.00582, -4.5899982},
754 };
756}
757
758/* Blender bug #67109 (version c). */
759TEST(polyfill2d, IssueT67109_axis_align_co_linear_c)
760{
761 const float poly[][2] = {
762 {-67.10034, 43.677097},
763 {-63.253956, 61.399143},
764 {-80.98382, 66.36057},
765 {-83.15499, 58.601795},
766 {-87.06422, 49.263668},
767 {-80.71576, 67.31843},
768 {-62.985912, 62.35701},
769 {-60.81475, 70.11576},
770 {-60.546703, 71.07365},
771 {-58.37554, 78.83239},
772 };
774}
775
776/* Blender bug #103913 where co-linear edges create zero area tessellation
777 * when a valid solution exists without zero area triangles. */
778TEST(polyfill2d, Issue103913_axis_align_co_linear_no_zero_area_tri)
779{
780 const float poly[][2] = {
781 {-10, 0}, {-10, 2}, {-8, 2}, {-6, 2}, {-4, 2}, {-2, 2}, {-2, 4}, {-2, 6},
782 {-2, 8}, {-2, 10}, {0, 10}, {2, 10}, {2, 8}, {2, 6}, {2, 4}, {2, 2},
783 {4, 2}, {6, 2}, {8, 2}, {10, 2}, {10, 0}, {10, -2}, {8, -2}, {6, -2},
784 {4, -2}, {2, -2}, {2, -4}, {2, -6}, {2, -8}, {2, -10}, {0, -10}, {-2, -10},
785 {-2, -8}, {-2, -6}, {-2, -4}, {-2, -2}, {-4, -2}, {-6, -2}, {-8, -2}, {-10, -2},
786 };
788}
789
790} // namespace blender
Generic array manipulation API.
#define BLI_array_reverse(arr, arr_len)
A min-heap / priority queue ADT.
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
#define TRI_ERROR_VALUE
#define TEST_POLYFILL_TEMPLATE_STATIC(poly, test_flag)
#define SNPRINTF(dst, format,...)
Read Blender memory allocation and freeing.
#define UNPACK2(a)
#define UNPACK3_EX(pre, a, post)
#define ELEM(...)
ValueIterator values() const &
Definition BLI_map.hh:884
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
int64_t size() const
Definition BLI_map.hh:976
bool contains(const Key &key) const
Definition BLI_map.hh:353
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition BLI_map.hh:481
#define FLT_EPSILON
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_NEAR(result, expect, threshold)
BMesh Iterators.
static void test_polyfill_simple(const float[][2], const uint poly_num, const uint tris[][3], const uint tris_num)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
MINLINE void copy_v2_v2(float r[2], const float a[2])
static void test_polyfill_winding(const float poly[][2], const uint, const uint tris[][3], const uint tris_num)
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
static void test_polyfill_topology(const float[][2], const uint poly_num, const uint tris[][3], const uint tris_num)
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
static void test_polyfill_template_flip_sign(const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, uint tris[][3], const uint tris_num)
TEST(array_store, Nop)
float area_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:186
static void test_polyfill_area_tri_nonzero(const float poly[][2], const uint, const uint tris[][3], const uint tris_num)
static void test_polyfill_area(const float poly[][2], const uint poly_num, const uint tris[][3], const uint tris_num)
static void test_valid_polyfill_prepare(uint tris[][3], uint tris_num)
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
static void polyfill_to_obj(const char *id, const float poly[][2], const uint poly_num, const uint tris[][3], const uint tris_num)
static void test_polyfill_template_main(const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, uint tris[][3], const uint tris_num)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
@ POLYFILL2D_TEST_NO_ZERO_AREA_TRIS
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static void test_polyfill_template_check(const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, const uint tris[][3], const uint tris_num)
static void test_polyfill_template(const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, uint tris[][3], const uint tris_num)
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
const btScalar eps
Definition poly34.cpp:11
#define fabsf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float