Blender  V3.3
BLI_polyfill_2d_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
5 /* Use to write out OBJ files, handy for checking output */
6 // #define USE_OBJ_PREVIEW
7 
8 /* test every possible offset and reverse */
9 #define USE_COMBINATIONS_ALL
10 #define USE_BEAUTIFY
11 
12 #include "MEM_guardedalloc.h"
13 
14 #include "BLI_array_utils.h"
15 #include "BLI_edgehash.h"
16 #include "BLI_math.h"
17 #include "BLI_polyfill_2d.h"
18 #include "BLI_utildefines.h"
19 
20 #ifdef USE_OBJ_PREVIEW
21 # include "BLI_string.h"
22 #endif
23 
24 #ifdef USE_BEAUTIFY
25 # include "BLI_heap.h"
26 # include "BLI_memarena.h"
28 #endif
29 
30 static void polyfill_to_obj(const char *id,
31  const float poly[][2],
32  const unsigned int poly_num,
33  const unsigned int tris[][3],
34  const unsigned int tris_num);
35 
36 /* -------------------------------------------------------------------- */
37 /* test utility functions */
38 
39 #define TRI_ERROR_VALUE (unsigned int)-1
40 
41 static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int tris_num)
42 {
43  unsigned int i;
44  for (i = 0; i < tris_num; i++) {
45  unsigned int j;
46  for (j = 0; j < 3; j++) {
47  tris[i][j] = TRI_ERROR_VALUE;
48  }
49  }
50 }
51 
59 static void test_polyfill_simple(const float /*poly*/[][2],
60  const unsigned int poly_num,
61  const unsigned int tris[][3],
62  const unsigned int tris_num)
63 {
64  unsigned int i;
65  int *used_num = (int *)MEM_callocN(poly_num * sizeof(int), __func__);
66  for (i = 0; i < tris_num; i++) {
67  unsigned int j;
68  for (j = 0; j < 3; j++) {
69  EXPECT_NE(TRI_ERROR_VALUE, tris[i][j]);
70  used_num[tris[i][j]] += 1;
71  }
72  EXPECT_NE(tris[i][0], tris[i][1]);
73  EXPECT_NE(tris[i][1], tris[i][2]);
74  EXPECT_NE(tris[i][2], tris[i][0]);
75  }
76  for (i = 0; i < poly_num; i++) {
77  EXPECT_NE(0, used_num[i]);
78  }
79  MEM_freeN(used_num);
80 }
81 
82 static void test_polyfill_topology(const float /*poly*/[][2],
83  const unsigned int poly_num,
84  const unsigned int tris[][3],
85  const unsigned int tris_num)
86 {
87  EdgeHash *edgehash = BLI_edgehash_new(__func__);
88  EdgeHashIterator *ehi;
89  unsigned int i;
90  for (i = 0; i < tris_num; i++) {
91  unsigned int j;
92  for (j = 0; j < 3; j++) {
93  const unsigned int v1 = tris[i][j];
94  const unsigned int v2 = tris[i][(j + 1) % 3];
95  void **p = BLI_edgehash_lookup_p(edgehash, v1, v2);
96  if (p) {
97  *p = (void *)((intptr_t)*p + (intptr_t)1);
98  }
99  else {
100  BLI_edgehash_insert(edgehash, v1, v2, (void *)(intptr_t)1);
101  }
102  }
103  }
104  EXPECT_EQ(BLI_edgehash_len(edgehash), poly_num + (poly_num - 3));
105 
106  for (i = 0; i < poly_num; i++) {
107  const unsigned int v1 = i;
108  const unsigned int v2 = (i + 1) % poly_num;
109  void **p = BLI_edgehash_lookup_p(edgehash, v1, v2);
110  EXPECT_NE((void *)p, nullptr);
111  EXPECT_EQ((intptr_t)*p, 1);
112  }
113 
114  for (ehi = BLI_edgehashIterator_new(edgehash), i = 0; BLI_edgehashIterator_isDone(ehi) == false;
115  BLI_edgehashIterator_step(ehi), i++) {
116  void **p = BLI_edgehashIterator_getValue_p(ehi);
117  EXPECT_TRUE(ELEM((intptr_t)*p, 1, 2));
118  }
119 
121  BLI_edgehash_free(edgehash, nullptr);
122 }
123 
127 static void test_polyfill_winding(const float poly[][2],
128  const unsigned int /*poly_num*/,
129  const unsigned int tris[][3],
130  const unsigned int tris_num)
131 {
132  unsigned int i;
133  unsigned int count[2] = {0, 0};
134  for (i = 0; i < tris_num; i++) {
135  float winding_test = cross_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
136  if (fabsf(winding_test) > FLT_EPSILON) {
137  count[winding_test < 0.0f] += 1;
138  }
139  }
140  EXPECT_TRUE(ELEM(0, count[0], count[1]));
141 }
142 
146 static void test_polyfill_area(const float poly[][2],
147  const unsigned int poly_num,
148  const unsigned int tris[][3],
149  const unsigned int tris_num)
150 {
151  unsigned int i;
152  const float area_total = area_poly_v2(poly, poly_num);
153  float area_total_tris = 0.0f;
154  const float eps_abs = 0.00001f;
155  const float eps = area_total > 1.0f ? (area_total * eps_abs) : eps_abs;
156  for (i = 0; i < tris_num; i++) {
157  area_total_tris += area_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
158  }
159  EXPECT_NEAR(area_total, area_total_tris, eps);
160 }
161 
162 /* -------------------------------------------------------------------- */
163 /* Macro and helpers to manage checking */
167 static void test_polyfill_template_check(const char *id,
168  bool is_degenerate,
169  const float poly[][2],
170  const unsigned int poly_num,
171  const unsigned int tris[][3],
172  const unsigned int tris_num)
173 {
174  test_polyfill_simple(poly, poly_num, tris, tris_num);
175  test_polyfill_topology(poly, poly_num, tris, tris_num);
176  if (!is_degenerate) {
177  test_polyfill_winding(poly, poly_num, tris, tris_num);
178 
179  test_polyfill_area(poly, poly_num, tris, tris_num);
180  }
181  polyfill_to_obj(id, poly, poly_num, tris, tris_num);
182 }
183 
184 static void test_polyfill_template(const char *id,
185  bool is_degenerate,
186  const float poly[][2],
187  const unsigned int poly_num,
188  unsigned int tris[][3],
189  const unsigned int tris_num)
190 {
191  test_valid_polyfill_prepare(tris, tris_num);
192  BLI_polyfill_calc(poly, poly_num, 0, tris);
193 
194  /* check all went well */
195  test_polyfill_template_check(id, is_degenerate, poly, poly_num, tris, tris_num);
196 
197 #ifdef USE_BEAUTIFY
198  /* check beautify gives good results too */
199  {
200  MemArena *pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
202 
203  BLI_polyfill_beautify(poly, poly_num, tris, pf_arena, pf_heap);
204 
205  test_polyfill_template_check(id, is_degenerate, poly, poly_num, tris, tris_num);
206 
207  BLI_memarena_free(pf_arena);
208  BLI_heap_free(pf_heap, nullptr);
209  }
210 #endif
211 }
212 
213 static void test_polyfill_template_flip_sign(const char *id,
214  bool is_degenerate,
215  const float poly[][2],
216  const unsigned int poly_num,
217  unsigned int tris[][3],
218  const unsigned int tris_num)
219 {
220  float(*poly_copy)[2] = (float(*)[2])MEM_mallocN(sizeof(float[2]) * poly_num, id);
221  for (int flip_x = 0; flip_x < 2; flip_x++) {
222  for (int flip_y = 0; flip_y < 2; flip_y++) {
223  float sign_x = flip_x ? -1.0f : 1.0f;
224  float sign_y = flip_y ? -1.0f : 1.0f;
225  for (int i = 0; i < poly_num; i++) {
226  poly_copy[i][0] = poly[i][0] * sign_x;
227  poly_copy[i][1] = poly[i][1] * sign_y;
228  }
229  test_polyfill_template(id, is_degenerate, poly_copy, poly_num, tris, tris_num);
230  }
231  }
232  MEM_freeN(poly_copy);
233 }
234 
235 #ifdef USE_COMBINATIONS_ALL
236 static void test_polyfill_template_main(const char *id,
237  bool is_degenerate,
238  const float poly[][2],
239  const unsigned int poly_num,
240  unsigned int tris[][3],
241  const unsigned int tris_num)
242 {
243  /* overkill? - try at _every_ offset & reverse */
244  unsigned int poly_reverse;
245  float(*poly_copy)[2] = (float(*)[2])MEM_mallocN(sizeof(float[2]) * poly_num, id);
246  float tmp[2];
247 
248  memcpy(poly_copy, poly, sizeof(float[2]) * poly_num);
249 
250  for (poly_reverse = 0; poly_reverse < 2; poly_reverse++) {
251  unsigned int poly_cycle;
252 
253  if (poly_reverse) {
254  BLI_array_reverse(poly_copy, poly_num);
255  }
256 
257  for (poly_cycle = 0; poly_cycle < poly_num; poly_cycle++) {
258  // printf("polytest %s ofs=%d, reverse=%d\n", id, poly_cycle, poly_reverse);
259  test_polyfill_template_flip_sign(id, is_degenerate, poly, poly_num, tris, tris_num);
260 
261  /* cycle */
262  copy_v2_v2(tmp, poly_copy[0]);
263  memmove(&poly_copy[0], &poly_copy[1], (poly_num - 1) * sizeof(float[2]));
264  copy_v2_v2(poly_copy[poly_num - 1], tmp);
265  }
266  }
267 
268  MEM_freeN(poly_copy);
269 }
270 #else /* USE_COMBINATIONS_ALL */
271 static void test_polyfill_template_main(const char *id,
272  bool is_degenerate,
273  const float poly[][2],
274  const unsigned int poly_num,
275  unsigned int tris[][3],
276  const unsigned int tris_num)
277 {
278  test_polyfill_template_flip_sign(id, is_degenerate, poly, poly_num, tris, tris_num);
279 }
280 #endif /* USE_COMBINATIONS_ALL */
281 
282 #define TEST_POLYFILL_TEMPLATE_STATIC(poly, is_degenerate) \
283  { \
284  unsigned int tris[POLY_TRI_COUNT(ARRAY_SIZE(poly))][3]; \
285  const unsigned int poly_num = ARRAY_SIZE(poly); \
286  const unsigned int tris_num = ARRAY_SIZE(tris); \
287  const char *id = typeid(*this).name(); \
288 \
289  test_polyfill_template_main(id, is_degenerate, poly, poly_num, tris, tris_num); \
290  } \
291  (void)0
292 
293 /* -------------------------------------------------------------------- */
294 /* visualization functions (not needed for testing) */
295 
296 #ifdef USE_OBJ_PREVIEW
297 static void polyfill_to_obj(const char *id,
298  const float poly[][2],
299  const unsigned int poly_num,
300  const unsigned int tris[][3],
301  const unsigned int tris_num)
302 {
303  char path[1024];
304  FILE *f;
305  unsigned int i;
306 
307  BLI_snprintf(path, sizeof(path), "%s.obj", id);
308 
309  f = fopen(path, "w");
310  if (!f) {
311  return;
312  }
313 
314  for (i = 0; i < poly_num; i++) {
315  fprintf(f, "v %f %f 0.0\n", UNPACK2(poly[i]));
316  }
317 
318  for (i = 0; i < tris_num; i++) {
319  fprintf(f, "f %u %u %u\n", UNPACK3_EX(1 +, tris[i], ));
320  }
321 
322  fclose(f);
323 }
324 #else
325 static void polyfill_to_obj(const char *id,
326  const float poly[][2],
327  const unsigned int poly_num,
328  const unsigned int tris[][3],
329  const unsigned int tris_num)
330 {
331  (void)id;
332  (void)poly, (void)poly_num;
333  (void)tris, (void)tris_num;
334 }
335 #endif /* USE_OBJ_PREVIEW */
336 
337 /* -------------------------------------------------------------------- */
338 /* tests */
339 
377 #define POLY_TRI_COUNT(len) ((len)-2)
378 
379 /* A counterclockwise triangle */
380 TEST(polyfill2d, TriangleCCW)
381 {
382  const float poly[][2] = {{0, 0}, {0, 1}, {1, 0}};
383  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
384 }
385 
386 /* A counterclockwise square */
387 TEST(polyfill2d, SquareCCW)
388 {
389  const float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
390  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
391 }
392 
393 /* A clockwise square */
394 TEST(polyfill2d, SquareCW)
395 {
396  const float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
397  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
398 }
399 
400 /* Starfleet insigna */
401 TEST(polyfill2d, Starfleet)
402 {
403  const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
404  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
405 }
406 
407 /* Starfleet insigna with repeated point */
408 TEST(polyfill2d, StarfleetDegenerate)
409 {
410  const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
411  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
412 }
413 
414 /* Three collinear points */
415 TEST(polyfill2d, 3Colinear)
416 {
417  const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}};
418  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
419 }
420 
421 /* Four collinear points */
422 TEST(polyfill2d, 4Colinear)
423 {
424  const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
425  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
426 }
427 
428 /* Non-consecutive collinear points */
429 TEST(polyfill2d, UnorderedColinear)
430 {
431  const float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0}};
432  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
433 }
434 
435 /* Plus shape */
436 TEST(polyfill2d, PlusShape)
437 {
438  const float poly[][2] = {
439  {1, 0},
440  {2, 0},
441  {2, 1},
442  {3, 1},
443  {3, 2},
444  {2, 2},
445  {2, 3},
446  {1, 3},
447  {1, 2},
448  {0, 2},
449  {0, 1},
450  {1, 1},
451  };
452  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
453 }
454 
455 /* Star shape */
456 TEST(polyfill2d, StarShape)
457 {
458  const float poly[][2] = {{4, 0}, {5, 3}, {8, 4}, {5, 5}, {4, 8}, {3, 5}, {0, 4}, {3, 3}};
459  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
460 }
461 
462 /* U shape */
463 TEST(polyfill2d, UShape)
464 {
465  const float poly[][2] = {
466  {1, 0}, {2, 0}, {3, 1}, {3, 3}, {2, 3}, {2, 1}, {1, 1}, {1, 3}, {0, 3}, {0, 1}};
467  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
468 }
469 
470 /* Spiral */
471 TEST(polyfill2d, Spiral)
472 {
473  const float poly[][2] = {
474  {1, 0},
475  {4, 0},
476  {5, 1},
477  {5, 4},
478  {4, 5},
479  {1, 5},
480  {0, 4},
481  {0, 3},
482  {1, 2},
483  {2, 2},
484  {3, 3},
485  {1, 3},
486  {1, 4},
487  {4, 4},
488  {4, 1},
489  {0, 1},
490  };
491  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
492 }
493 
494 /* Test case from http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml */
495 TEST(polyfill2d, TestFlipCode)
496 {
497  const float poly[][2] = {
498  {0, 6},
499  {0, 0},
500  {3, 0},
501  {4, 1},
502  {6, 1},
503  {8, 0},
504  {12, 0},
505  {13, 2},
506  {8, 2},
507  {8, 4},
508  {11, 4},
509  {11, 6},
510  {6, 6},
511  {4, 3},
512  {2, 6},
513  };
514  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
515 }
516 
517 /* Self-intersection */
518 TEST(polyfill2d, SelfIntersect)
519 {
520  const float poly[][2] = {{0, 0}, {1, 1}, {2, -1}, {3, 1}, {4, 0}};
521  TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
522 }
523 
524 /* Self-touching */
525 TEST(polyfill2d, SelfTouch)
526 {
527  const float poly[][2] = {
528  {0, 0},
529  {4, 0},
530  {4, 4},
531  {2, 4},
532  {2, 3},
533  {3, 3},
534  {3, 1},
535  {1, 1},
536  {1, 3},
537  {2, 3},
538  {2, 4},
539  {0, 4},
540  };
541  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
542 }
543 
544 /* Self-overlapping */
545 TEST(polyfill2d, SelfOverlap)
546 {
547  const float poly[][2] = {
548  {0, 0},
549  {4, 0},
550  {4, 4},
551  {1, 4},
552  {1, 3},
553  {3, 3},
554  {3, 1},
555  {1, 1},
556  {1, 3},
557  {3, 3},
558  {3, 4},
559  {0, 4},
560  };
561  TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
562 }
563 
564 /* Test case from http://www.davdata.nl/math/polygons.html */
565 TEST(polyfill2d, TestDavData)
566 {
567  const float poly[][2] = {
568  {190, 480}, {140, 180}, {310, 100}, {330, 390}, {290, 390}, {280, 260}, {220, 260},
569  {220, 430}, {370, 430}, {350, 30}, {50, 30}, {160, 560}, {730, 510}, {710, 20},
570  {410, 30}, {470, 440}, {640, 410}, {630, 140}, {590, 140}, {580, 360}, {510, 370},
571  {510, 60}, {650, 70}, {660, 450}, {190, 480},
572  };
573  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
574 }
575 
576 /* Issue 815, http://code.google.com/p/libgdx/issues/detail?id=815 */
577 TEST(polyfill2d, Issue815)
578 {
579  const float poly[][2] = {
580  {-2.0f, 0.0f},
581  {-2.0f, 0.5f},
582  {0.0f, 1.0f},
583  {0.5f, 2.875f},
584  {1.0f, 0.5f},
585  {1.5f, 1.0f},
586  {2.0f, 1.0f},
587  {2.0f, 0.0f},
588  };
589  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
590 }
591 
592 /* Issue 207, comment #1, http://code.google.com/p/libgdx/issues/detail?id=207#c1 */
593 TEST(polyfill2d, Issue207_1)
594 {
595  const float poly[][2] = {
596  {72.42465f, 197.07095f},
597  {78.485535f, 189.92776f},
598  {86.12059f, 180.92929f},
599  {99.68253f, 164.94557f},
600  {105.24325f, 165.79604f},
601  {107.21862f, 166.09814f},
602  {112.41958f, 162.78253f},
603  {113.73238f, 161.94562f},
604  {123.29477f, 167.93805f},
605  {126.70667f, 170.07617f},
606  {73.22717f, 199.51062f},
607  };
608  TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
609 }
610 
611 /* Issue 207, comment #11, http://code.google.com/p/libgdx/issues/detail?id=207#c11 */
612 /* Also on issue 1081, http://code.google.com/p/libgdx/issues/detail?id=1081 */
613 TEST(polyfill2d, Issue207_11)
614 {
615  const float poly[][2] = {
616  {2400.0f, 480.0f}, {2400.0f, 176.0f}, {1920.0f, 480.0f},
617  {1920.0459f, 484.22314f}, {1920.1797f, 487.91016f}, {1920.3955f, 491.0874f},
618  {1920.6875f, 493.78125f}, {1921.0498f, 496.01807f}, {1921.4766f, 497.82422f},
619  {1921.9619f, 499.22607f}, {1922.5f, 500.25f}, {1923.085f, 500.92236f},
620  {1923.7109f, 501.26953f}, {1924.3721f, 501.31787f}, {1925.0625f, 501.09375f},
621  {1925.7764f, 500.62354f}, {1926.5078f, 499.9336f}, {1927.251f, 499.0503f},
622  {1928.0f, 498.0f}, {1928.749f, 496.80908f}, {1929.4922f, 495.5039f},
623  {1930.2236f, 494.11084f}, {1930.9375f, 492.65625f}, {1931.6279f, 491.1665f},
624  {1932.2891f, 489.66797f}, {1932.915f, 488.187f}, {1933.5f, 486.75f},
625  {1934.0381f, 485.3833f}, {1934.5234f, 484.11328f}, {1934.9502f, 482.9663f},
626  {1935.3125f, 481.96875f}, {1935.6045f, 481.14697f}, {1935.8203f, 480.52734f},
627  {1935.9541f, 480.13623f}, {1936.0f, 480.0f}};
628  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
629 }
630 
631 /* Issue 1407, http://code.google.com/p/libgdx/issues/detail?id=1407 */
632 TEST(polyfill2d, Issue1407)
633 {
634  const float poly[][2] = {
635  {3.914329f, 1.9008259f},
636  {4.414321f, 1.903619f},
637  {4.8973203f, 1.9063174f},
638  {5.4979978f, 1.9096732f},
639  };
640  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
641 }
642 
643 /* Issue 1407, http://code.google.com/p/libgdx/issues/detail?id=1407, */
644 /* with an additional point to show what is happening. */
645 TEST(polyfill2d, Issue1407_pt)
646 {
647  const float poly[][2] = {
648  {3.914329f, 1.9008259f},
649  {4.414321f, 1.903619f},
650  {4.8973203f, 1.9063174f},
651  {5.4979978f, 1.9096732f},
652  {4, 4},
653  };
654  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
655 }
656 
657 /* Simplified from Blender bug T40777 */
658 TEST(polyfill2d, IssueT40777_colinear)
659 {
660  const float poly[][2] = {
661  {0.7, 0.37}, {0.7, 0}, {0.76, 0}, {0.76, 0.4}, {0.83, 0.4}, {0.83, 0}, {0.88, 0},
662  {0.88, 0.4}, {0.94, 0.4}, {0.94, 0}, {1, 0}, {1, 0.4}, {0.03, 0.62}, {0.03, 0.89},
663  {0.59, 0.89}, {0.03, 1}, {0, 1}, {0, 0}, {0.03, 0}, {0.03, 0.37},
664  };
665  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
666 }
667 
668 /* Blender bug T41986 */
669 TEST(polyfill2d, IssueT41986_axis_align)
670 {
671  const float poly[][2] = {
672  {-0.25, -0.07}, {-0.25, 0.27}, {-1.19, 0.14}, {-0.06, 0.73}, {0.17, 1.25},
673  {-0.25, 1.07}, {-0.38, 1.02}, {-0.25, 0.94}, {-0.40, 0.90}, {-0.41, 0.86},
674  {-0.34, 0.83}, {-0.25, 0.82}, {-0.66, 0.73}, {-0.56, 1.09}, {-0.25, 1.10},
675  {0.00, 1.31}, {-0.03, 1.47}, {-0.25, 1.53}, {0.12, 1.62}, {0.36, 1.07},
676  {0.12, 0.67}, {0.29, 0.57}, {0.44, 0.45}, {0.57, 0.29}, {0.66, 0.12},
677  {0.68, 0.06}, {0.57, -0.36}, {-0.25, -0.37}, {0.49, -0.74}, {-0.59, -1.21},
678  {-0.25, -0.15}, {-0.46, -0.52}, {-1.08, -0.83}, {-1.45, -0.33}, {-1.25, -0.04}};
679 
680  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
681 }
682 
683 /* Blender bug T52834 */
684 TEST(polyfill2d, IssueT52834_axis_align_co_linear)
685 {
686  const float poly[][2] = {
687  {40, 0}, {36, 0}, {36, 5}, {35, 5}, {35, 0}, {30, 0}, {30, 5}, {29, 5},
688  {29, 0}, {24, 0}, {24, 3}, {23, 4}, {23, 0}, {18, 0}, {18, 5}, {17, 5},
689  {17, 0}, {12, 0}, {12, 5}, {11, 5}, {11, 0}, {6, 0}, {6, 5}, {5, 5},
690  {5, 0}, {0, 0}, {0, 5}, {-1, 5}, {-1, 0}, {-6, 0}, {-9, -3}, {-6, -3},
691  {-6, -2}, {-1, -2}, {0, -2}, {5, -2}, {6, -2}, {11, -2}, {12, -2}, {17, -2},
692  {18, -2}, {23, -2}, {24, -2}, {29, -2}, {30, -2}, {35, -2}, {36, -2}, {40, -2},
693  };
694 
695  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
696 }
697 
698 /* Blender bug T67109 (version a). */
699 /* Multiple versions are offset & rotated, this fails in cases where others works. */
700 TEST(polyfill2d, IssueT67109_axis_align_co_linear_a)
701 {
702  const float poly[][2] = {
703  {3.2060661, -11.438997},
704  {2.8720665, -5.796999},
705  {-2.8659325, -5.796999},
706  {-2.8659325, -8.307999},
707  {-3.2549324, -11.438997},
708  {-2.8659325, -5.4869995},
709  {2.8720665, -5.4869995},
710  {2.8720665, -2.9759989},
711  {2.8720665, -2.6659985},
712  {2.8720665, -0.15499878},
713  };
714  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
715 }
716 
717 /* Blender bug T67109, (version b). */
718 TEST(polyfill2d, IssueT67109_axis_align_co_linear_b)
719 {
720  const float poly[][2] = {
721  {32.41416, -12.122593},
722  {28.094929, -8.477332},
723  {24.141455, -12.636018},
724  {25.96133, -14.366093},
725  {27.96254, -16.805279},
726  {23.916779, -12.422427},
727  {27.870255, -8.263744},
728  {26.050375, -6.533667},
729  {25.825695, -6.320076},
730  {24.00582, -4.5899982},
731  };
732  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
733 }
734 
735 /* Blender bug T67109 (version c). */
736 TEST(polyfill2d, IssueT67109_axis_align_co_linear_c)
737 {
738  const float poly[][2] = {
739  {-67.10034, 43.677097},
740  {-63.253956, 61.399143},
741  {-80.98382, 66.36057},
742  {-83.15499, 58.601795},
743  {-87.06422, 49.263668},
744  {-80.71576, 67.31843},
745  {-62.985912, 62.35701},
746  {-60.81475, 70.11576},
747  {-60.546703, 71.07365},
748  {-58.37554, 78.83239},
749  };
750  TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
751 }
typedef float(TangentPoint)[2]
Generic array manipulation API.
#define BLI_array_reverse(arr, arr_len)
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value)
Definition: edgehash.c:230
void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
Definition: edgehash.c:261
EdgeHashIterator * BLI_edgehashIterator_new(EdgeHash *eh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: edgehash.c:394
EdgeHash * BLI_edgehash_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: edgehash.c:225
int BLI_edgehash_len(const EdgeHash *eh) ATTR_WARN_UNUSED_RESULT
Definition: edgehash.c:368
void ** BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT
Definition: edgehash.c:301
BLI_INLINE void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
Definition: BLI_edgehash.h:153
void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
Definition: edgehash.c:408
BLI_INLINE bool BLI_edgehashIterator_isDone(const EdgeHashIterator *ehi)
Definition: BLI_edgehash.h:157
BLI_INLINE void ** BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi)
Definition: BLI_edgehash.h:173
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:202
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:182
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
float area_poly_v2(const float verts[][2], unsigned int nr)
Definition: math_geom.c:174
MINLINE void copy_v2_v2(float r[2], const float a[2])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
#define BLI_POLYFILL_ARENA_SIZE
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
Definition: polyfill_2d.c:875
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
#define TRI_ERROR_VALUE
TEST(polyfill2d, TriangleCCW)
static void test_polyfill_topology(const float[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_simple(const float[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_winding(const float poly[][2], const unsigned int, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_area(const float poly[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_template_flip_sign(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_template_main(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, unsigned int tris[][3], const unsigned int tris_num)
static void test_polyfill_template(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, unsigned int tris[][3], const unsigned int tris_num)
static void polyfill_to_obj(const char *id, const float poly[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
#define TEST_POLYFILL_TEMPLATE_STATIC(poly, is_degenerate)
static void test_polyfill_template_check(const char *id, bool is_degenerate, const float poly[][2], const unsigned int poly_num, const unsigned int tris[][3], const unsigned int tris_num)
static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int tris_num)
size_t BLI_snprintf(char *__restrict dst, size_t maxncpy, const char *__restrict format,...) ATTR_NONNULL(1
#define UNPACK2(a)
#define UNPACK3_EX(pre, a, post)
#define ELEM(...)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
SyclQueue void void size_t num_bytes void
int count
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
#define fabsf(x)
Definition: metal/compat.h:219
const btScalar eps
Definition: poly34.cpp:11
_W64 int intptr_t
Definition: stdint.h:118
Definition: BLI_heap.c:43