Cleanup: add trailing commas to avoid right shift
[blender.git] / tests / gtests / blenlib / BLI_polyfill_2d_test.cc
1 /* Apache License, Version 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 extern "C" {
13 #include "BLI_utildefines.h"
14 #include "BLI_array_utils.h"
15 #include "BLI_polyfill_2d.h"
16 #include "BLI_edgehash.h"
17 #include "BLI_math.h"
18 #include "MEM_guardedalloc.h"
19
20 #ifdef USE_OBJ_PREVIEW
21 #  include "BLI_string.h"
22 #endif
23
24 #ifdef USE_BEAUTIFY
25 #  include "BLI_polyfill_2d_beautify.h"
26 #  include "BLI_memarena.h"
27 #  include "BLI_heap.h"
28 #endif
29 }
30
31 #include "stubs/bf_intern_eigen_stubs.h"
32
33 static void polyfill_to_obj(const char *id,
34                             const float poly[][2],
35                             const unsigned int poly_tot,
36                             const unsigned int tris[][3],
37                             const unsigned int tris_tot);
38
39 /* -------------------------------------------------------------------- */
40 /* test utility functions */
41
42 #define TRI_ERROR_VALUE (unsigned int)-1
43
44 static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int tris_tot)
45 {
46   unsigned int i;
47   for (i = 0; i < tris_tot; i++) {
48     unsigned int j;
49     for (j = 0; j < 3; j++) {
50       tris[i][j] = TRI_ERROR_VALUE;
51     }
52   }
53 }
54
55 /**
56  * Basic check for face index values:
57  *
58  * - no duplicates.
59  * - all tris set.
60  * - all verts used at least once.
61  */
62 static void test_polyfill_simple(const float poly[][2],
63                                  const unsigned int poly_tot,
64                                  const unsigned int tris[][3],
65                                  const unsigned int tris_tot)
66 {
67   unsigned int i;
68   int *tot_used = (int *)MEM_callocN(poly_tot * sizeof(int), __func__);
69   for (i = 0; i < tris_tot; i++) {
70     unsigned int j;
71     for (j = 0; j < 3; j++) {
72       EXPECT_NE(TRI_ERROR_VALUE, tris[i][j]);
73       tot_used[tris[i][j]] += 1;
74     }
75     EXPECT_NE(tris[i][0], tris[i][1]);
76     EXPECT_NE(tris[i][1], tris[i][2]);
77     EXPECT_NE(tris[i][2], tris[i][0]);
78   }
79   for (i = 0; i < poly_tot; i++) {
80     EXPECT_NE(0, tot_used[i]);
81   }
82   MEM_freeN(tot_used);
83 }
84
85 static void test_polyfill_topology(const float poly[][2],
86                                    const unsigned int poly_tot,
87                                    const unsigned int tris[][3],
88                                    const unsigned int tris_tot)
89 {
90   EdgeHash *edgehash = BLI_edgehash_new(__func__);
91   EdgeHashIterator *ehi;
92   unsigned int i;
93   for (i = 0; i < tris_tot; i++) {
94     unsigned int j;
95     for (j = 0; j < 3; j++) {
96       const unsigned int v1 = tris[i][j];
97       const unsigned int v2 = tris[i][(j + 1) % 3];
98       void **p = BLI_edgehash_lookup_p(edgehash, v1, v2);
99       if (p) {
100         *p = (void *)((intptr_t)*p + (intptr_t)1);
101       }
102       else {
103         BLI_edgehash_insert(edgehash, v1, v2, (void *)(intptr_t)1);
104       }
105     }
106   }
107   EXPECT_EQ(BLI_edgehash_len(edgehash), poly_tot + (poly_tot - 3));
108
109   for (i = 0; i < poly_tot; i++) {
110     const unsigned int v1 = i;
111     const unsigned int v2 = (i + 1) % poly_tot;
112     void **p = BLI_edgehash_lookup_p(edgehash, v1, v2);
113     EXPECT_EQ((void *)p != NULL, 1);
114     EXPECT_EQ((intptr_t)*p, 1);
115   }
116
117   for (ehi = BLI_edgehashIterator_new(edgehash), i = 0; BLI_edgehashIterator_isDone(ehi) == false;
118        BLI_edgehashIterator_step(ehi), i++) {
119     void **p = BLI_edgehashIterator_getValue_p(ehi);
120     EXPECT_TRUE(ELEM((intptr_t)*p, 1, 2));
121   }
122
123   BLI_edgehashIterator_free(ehi);
124   BLI_edgehash_free(edgehash, NULL);
125 }
126
127 /**
128  * Check all faces are flipped the same way
129  */
130 static void test_polyfill_winding(const float poly[][2],
131                                   const unsigned int poly_tot,
132                                   const unsigned int tris[][3],
133                                   const unsigned int tris_tot)
134 {
135   unsigned int i;
136   unsigned int count[2] = {0, 0};
137   for (i = 0; i < tris_tot; i++) {
138     float winding_test = cross_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
139     if (fabsf(winding_test) > FLT_EPSILON) {
140       count[winding_test < 0.0f] += 1;
141     }
142   }
143   EXPECT_TRUE(ELEM(0, count[0], count[1]));
144 }
145
146 /**
147  * Check the accumulated triangle area is close to the original area.
148  */
149 static void test_polyfill_area(const float poly[][2],
150                                const unsigned int poly_tot,
151                                const unsigned int tris[][3],
152                                const unsigned int tris_tot)
153 {
154   unsigned int i;
155   const float area_tot = area_poly_v2(poly, poly_tot);
156   float area_tot_tris = 0.0f;
157   const float eps_abs = 0.00001f;
158   const float eps = area_tot > 1.0f ? (area_tot * eps_abs) : eps_abs;
159   for (i = 0; i < tris_tot; i++) {
160     area_tot_tris += area_tri_v2(poly[tris[i][0]], poly[tris[i][1]], poly[tris[i][2]]);
161   }
162   EXPECT_NEAR(area_tot, area_tot_tris, eps);
163 }
164
165 /* -------------------------------------------------------------------- */
166 /* Macro and helpers to manage checking */
167 /**
168  * Main template for polyfill testing.
169  */
170 static void test_polyfill_template_check(const char *id,
171                                          bool is_degenerate,
172                                          const float poly[][2],
173                                          const unsigned int poly_tot,
174                                          const unsigned int tris[][3],
175                                          const unsigned int tris_tot)
176 {
177   test_polyfill_simple(poly, poly_tot, tris, tris_tot);
178   test_polyfill_topology(poly, poly_tot, tris, tris_tot);
179   if (!is_degenerate) {
180     test_polyfill_winding(poly, poly_tot, tris, tris_tot);
181
182     test_polyfill_area(poly, poly_tot, tris, tris_tot);
183   }
184   polyfill_to_obj(id, poly, poly_tot, tris, tris_tot);
185 }
186
187 static void test_polyfill_template(const char *id,
188                                    bool is_degenerate,
189                                    const float poly[][2],
190                                    const unsigned int poly_tot,
191                                    unsigned int tris[][3],
192                                    const unsigned int tris_tot)
193 {
194   test_valid_polyfill_prepare(tris, tris_tot);
195   BLI_polyfill_calc(poly, poly_tot, 0, tris);
196
197   /* check all went well */
198   test_polyfill_template_check(id, is_degenerate, poly, poly_tot, tris, tris_tot);
199
200 #ifdef USE_BEAUTIFY
201   /* check beautify gives good results too */
202   {
203     MemArena *pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
204     Heap *pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
205
206     BLI_polyfill_beautify(poly, poly_tot, tris, pf_arena, pf_heap);
207
208     test_polyfill_template_check(id, is_degenerate, poly, poly_tot, tris, tris_tot);
209
210     BLI_memarena_free(pf_arena);
211     BLI_heap_free(pf_heap, NULL);
212   }
213 #endif
214 }
215
216 static void test_polyfill_template_flip_sign(const char *id,
217                                              bool is_degenerate,
218                                              const float poly[][2],
219                                              const unsigned int poly_tot,
220                                              unsigned int tris[][3],
221                                              const unsigned int tris_tot)
222 {
223   float(*poly_copy)[2] = (float(*)[2])MEM_mallocN(sizeof(float[2]) * poly_tot, id);
224   for (int flip_x = 0; flip_x < 2; flip_x++) {
225     for (int flip_y = 0; flip_y < 2; flip_y++) {
226       float sign_x = flip_x ? -1.0f : 1.0f;
227       float sign_y = flip_y ? -1.0f : 1.0f;
228       for (int i = 0; i < poly_tot; i++) {
229         poly_copy[i][0] = poly[i][0] * sign_x;
230         poly_copy[i][1] = poly[i][1] * sign_y;
231       }
232       test_polyfill_template(id, is_degenerate, poly_copy, poly_tot, tris, tris_tot);
233     }
234   }
235   MEM_freeN(poly_copy);
236 }
237
238 #ifdef USE_COMBINATIONS_ALL
239 static void test_polyfill_template_main(const char *id,
240                                         bool is_degenerate,
241                                         const float poly[][2],
242                                         const unsigned int poly_tot,
243                                         unsigned int tris[][3],
244                                         const unsigned int tris_tot)
245 {
246   /* overkill? - try at _every_ offset & reverse */
247   unsigned int poly_reverse;
248   float(*poly_copy)[2] = (float(*)[2])MEM_mallocN(sizeof(float[2]) * poly_tot, id);
249   float tmp[2];
250
251   memcpy(poly_copy, poly, sizeof(float[2]) * poly_tot);
252
253   for (poly_reverse = 0; poly_reverse < 2; poly_reverse++) {
254     unsigned int poly_cycle;
255
256     if (poly_reverse) {
257       BLI_array_reverse(poly_copy, poly_tot);
258     }
259
260     for (poly_cycle = 0; poly_cycle < poly_tot; poly_cycle++) {
261       // printf("polytest %s ofs=%d, reverse=%d\n", id, poly_cycle, poly_reverse);
262       test_polyfill_template_flip_sign(id, is_degenerate, poly, poly_tot, tris, tris_tot);
263
264       /* cycle */
265       copy_v2_v2(tmp, poly_copy[0]);
266       memmove(&poly_copy[0], &poly_copy[1], (poly_tot - 1) * sizeof(float[2]));
267       copy_v2_v2(poly_copy[poly_tot - 1], tmp);
268     }
269   }
270
271   MEM_freeN(poly_copy);
272 }
273 #else  /* USE_COMBINATIONS_ALL */
274 static void test_polyfill_template_main(const char *id,
275                                         bool is_degenerate,
276                                         const float poly[][2],
277                                         const unsigned int poly_tot,
278                                         unsigned int tris[][3],
279                                         const unsigned int tris_tot)
280 {
281   test_polyfill_template_flip_sign(id, is_degenerate, poly, poly_tot, tris, tris_tot);
282 }
283 #endif /* USE_COMBINATIONS_ALL */
284
285 #define TEST_POLYFILL_TEMPLATE_STATIC(poly, is_degenerate) \
286   { \
287     unsigned int tris[POLY_TRI_COUNT(ARRAY_SIZE(poly))][3]; \
288     const unsigned int poly_tot = ARRAY_SIZE(poly); \
289     const unsigned int tris_tot = ARRAY_SIZE(tris); \
290     const char *id = typeid(*this).name(); \
291 \
292     test_polyfill_template_main(id, is_degenerate, poly, poly_tot, tris, tris_tot); \
293   } \
294   (void)0
295
296 /* -------------------------------------------------------------------- */
297 /* visualisation functions (not needed for testing) */
298
299 #ifdef USE_OBJ_PREVIEW
300 static void polyfill_to_obj(const char *id,
301                             const float poly[][2],
302                             const unsigned int poly_tot,
303                             const unsigned int tris[][3],
304                             const unsigned int tris_tot)
305 {
306   char path[1024];
307   FILE *f;
308   unsigned int i;
309
310   BLI_snprintf(path, sizeof(path), "%s.obj", id);
311
312   f = fopen(path, "w");
313   if (!f) {
314     return;
315   }
316
317   for (i = 0; i < poly_tot; i++) {
318     fprintf(f, "v %f %f 0.0\n", UNPACK2(poly[i]));
319   }
320
321   for (i = 0; i < tris_tot; i++) {
322     fprintf(f, "f %u %u %u\n", UNPACK3_EX(1 +, tris[i], ));
323   }
324
325   fclose(f);
326 }
327 #else
328 static void polyfill_to_obj(const char *id,
329                             const float poly[][2],
330                             const unsigned int poly_tot,
331                             const unsigned int tris[][3],
332                             const unsigned int tris_tot)
333 {
334   (void)id;
335   (void)poly, (void)poly_tot;
336   (void)tris, (void)tris_tot;
337 }
338 #endif /* USE_OBJ_PREVIEW */
339
340 /* -------------------------------------------------------------------- */
341 /* tests */
342
343 /**
344  * Script to generate the data below:
345  *
346  * \code{.py}
347  * # This example assumes we have a mesh object in edit-mode
348  *
349  * import bpy
350  * import bmesh
351  *
352  * obj = bpy.context.edit_object
353  * me = obj.data
354  * bm = bmesh.from_edit_mesh(me)
355  *
356  * def clean_float(num):
357  *     if int(num) == num:
358  *         return str(int(num))
359  *     prec = 1
360  *     while True:
361  *         text = f"{num:.{prec}f}"
362  *         if float(text) == num:
363  *             return text
364  *         prec += 1
365  *
366  * for f in bm.faces:
367  *     if f.select:
368  *         print(f"\t// data for face: {f.index}")
369  *         print("\tconst float poly[][2] = {", end="")
370  *         coords = [[clean_float(num) for num in l.vert.co[0:2]] for l in f.loops]
371  *         print("\t    ", end="")
372  *         for i, (x, y) in enumerate(coords):
373  *             if (i % 2) == 0:
374  *                 print("\n\t    ", end="")
375  *             print(f"{{{x}, {y}}}", end=",")
376  *         print("\n\t};")
377  * \endcode
378  */
379
380 #define POLY_TRI_COUNT(len) ((len)-2)
381
382 /* A counterclockwise triangle */
383 TEST(polyfill2d, TriangleCCW)
384 {
385   const float poly[][2] = {{0, 0}, {0, 1}, {1, 0}};
386   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
387 }
388
389 /* A counterclockwise square */
390 TEST(polyfill2d, SquareCCW)
391 {
392   const float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
393   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
394 }
395
396 /* A clockwise square */
397 TEST(polyfill2d, SquareCW)
398 {
399   const float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
400   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
401 }
402
403 /* Starfleet insigna */
404 TEST(polyfill2d, Starfleet)
405 {
406   const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
407   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
408 }
409
410 /* Starfleet insigna with repeated point */
411 TEST(polyfill2d, StarfleetDegenerate)
412 {
413   const float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1}};
414   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
415 }
416
417 /* Three collinear points */
418 TEST(polyfill2d, 3Colinear)
419 {
420   const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}};
421   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
422 }
423
424 /* Four collinear points */
425 TEST(polyfill2d, 4Colinear)
426 {
427   const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
428   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
429 }
430
431 /* Non-consecutive collinear points */
432 TEST(polyfill2d, UnorderedColinear)
433 {
434   const float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0}};
435   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
436 }
437
438 /* Plus shape */
439 TEST(polyfill2d, PlusShape)
440 {
441   const float poly[][2] = {
442       {1, 0},
443       {2, 0},
444       {2, 1},
445       {3, 1},
446       {3, 2},
447       {2, 2},
448       {2, 3},
449       {1, 3},
450       {1, 2},
451       {0, 2},
452       {0, 1},
453       {1, 1},
454   };
455   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
456 }
457
458 /* Star shape */
459 TEST(polyfill2d, StarShape)
460 {
461   const float poly[][2] = {{4, 0}, {5, 3}, {8, 4}, {5, 5}, {4, 8}, {3, 5}, {0, 4}, {3, 3}};
462   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
463 }
464
465 /* U shape */
466 TEST(polyfill2d, UShape)
467 {
468   const float poly[][2] = {
469       {1, 0}, {2, 0}, {3, 1}, {3, 3}, {2, 3}, {2, 1}, {1, 1}, {1, 3}, {0, 3}, {0, 1}};
470   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
471 }
472
473 /* Spiral */
474 TEST(polyfill2d, Spiral)
475 {
476   const float poly[][2] = {
477       {1, 0},
478       {4, 0},
479       {5, 1},
480       {5, 4},
481       {4, 5},
482       {1, 5},
483       {0, 4},
484       {0, 3},
485       {1, 2},
486       {2, 2},
487       {3, 3},
488       {1, 3},
489       {1, 4},
490       {4, 4},
491       {4, 1},
492       {0, 1},
493   };
494   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
495 }
496
497 /* Test case from http:# www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml */
498 TEST(polyfill2d, TestFlipCode)
499 {
500   const float poly[][2] = {
501       {0, 6},
502       {0, 0},
503       {3, 0},
504       {4, 1},
505       {6, 1},
506       {8, 0},
507       {12, 0},
508       {13, 2},
509       {8, 2},
510       {8, 4},
511       {11, 4},
512       {11, 6},
513       {6, 6},
514       {4, 3},
515       {2, 6},
516   };
517   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
518 }
519
520 /* Self-intersection */
521 TEST(polyfill2d, SelfIntersect)
522 {
523   const float poly[][2] = {{0, 0}, {1, 1}, {2, -1}, {3, 1}, {4, 0}};
524   TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
525 }
526
527 /* Self-touching */
528 TEST(polyfill2d, SelfTouch)
529 {
530   const float poly[][2] = {
531       {0, 0},
532       {4, 0},
533       {4, 4},
534       {2, 4},
535       {2, 3},
536       {3, 3},
537       {3, 1},
538       {1, 1},
539       {1, 3},
540       {2, 3},
541       {2, 4},
542       {0, 4},
543   };
544   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
545 }
546
547 /* Self-overlapping */
548 TEST(polyfill2d, SelfOverlap)
549 {
550   const float poly[][2] = {
551       {0, 0},
552       {4, 0},
553       {4, 4},
554       {1, 4},
555       {1, 3},
556       {3, 3},
557       {3, 1},
558       {1, 1},
559       {1, 3},
560       {3, 3},
561       {3, 4},
562       {0, 4},
563   };
564   TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
565 }
566
567 /* Test case from http:# www.davdata.nl/math/polygons.html */
568 TEST(polyfill2d, TestDavData)
569 {
570   const float poly[][2] = {
571       {190, 480}, {140, 180}, {310, 100}, {330, 390}, {290, 390}, {280, 260}, {220, 260},
572       {220, 430}, {370, 430}, {350, 30},  {50, 30},   {160, 560}, {730, 510}, {710, 20},
573       {410, 30},  {470, 440}, {640, 410}, {630, 140}, {590, 140}, {580, 360}, {510, 370},
574       {510, 60},  {650, 70},  {660, 450}, {190, 480},
575   };
576   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
577 }
578
579 /* Issue 815, http:# code.google.com/p/libgdx/issues/detail?id=815 */
580 TEST(polyfill2d, Issue815)
581 {
582   const float poly[][2] = {
583       {-2.0f, 0.0f},
584       {-2.0f, 0.5f},
585       {0.0f, 1.0f},
586       {0.5f, 2.875f},
587       {1.0f, 0.5f},
588       {1.5f, 1.0f},
589       {2.0f, 1.0f},
590       {2.0f, 0.0f},
591   };
592   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
593 }
594
595 /* Issue 207, comment #1, http:# code.google.com/p/libgdx/issues/detail?id=207#c1 */
596 TEST(polyfill2d, Issue207_1)
597 {
598   const float poly[][2] = {
599       {72.42465f, 197.07095f},
600       {78.485535f, 189.92776f},
601       {86.12059f, 180.92929f},
602       {99.68253f, 164.94557f},
603       {105.24325f, 165.79604f},
604       {107.21862f, 166.09814f},
605       {112.41958f, 162.78253f},
606       {113.73238f, 161.94562f},
607       {123.29477f, 167.93805f},
608       {126.70667f, 170.07617f},
609       {73.22717f, 199.51062f},
610   };
611   TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
612 }
613
614 /* Issue 207, comment #11, http:# code.google.com/p/libgdx/issues/detail?id=207#c11 */
615 /* Also on issue 1081, http:# code.google.com/p/libgdx/issues/detail?id=1081 */
616 TEST(polyfill2d, Issue207_11)
617 {
618   const float poly[][2] = {
619       {2400.0f, 480.0f},        {2400.0f, 176.0f},        {1920.0f, 480.0f},
620       {1920.0459f, 484.22314f}, {1920.1797f, 487.91016f}, {1920.3955f, 491.0874f},
621       {1920.6875f, 493.78125f}, {1921.0498f, 496.01807f}, {1921.4766f, 497.82422f},
622       {1921.9619f, 499.22607f}, {1922.5f, 500.25f},       {1923.085f, 500.92236f},
623       {1923.7109f, 501.26953f}, {1924.3721f, 501.31787f}, {1925.0625f, 501.09375f},
624       {1925.7764f, 500.62354f}, {1926.5078f, 499.9336f},  {1927.251f, 499.0503f},
625       {1928.0f, 498.0f},        {1928.749f, 496.80908f},  {1929.4922f, 495.5039f},
626       {1930.2236f, 494.11084f}, {1930.9375f, 492.65625f}, {1931.6279f, 491.1665f},
627       {1932.2891f, 489.66797f}, {1932.915f, 488.187f},    {1933.5f, 486.75f},
628       {1934.0381f, 485.3833f},  {1934.5234f, 484.11328f}, {1934.9502f, 482.9663f},
629       {1935.3125f, 481.96875f}, {1935.6045f, 481.14697f}, {1935.8203f, 480.52734f},
630       {1935.9541f, 480.13623f}, {1936.0f, 480.0f}};
631   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
632 }
633
634 /* Issue 1407, http:# code.google.com/p/libgdx/issues/detail?id=1407 */
635 TEST(polyfill2d, Issue1407)
636 {
637   const float poly[][2] = {
638       {3.914329f, 1.9008259f},
639       {4.414321f, 1.903619f},
640       {4.8973203f, 1.9063174f},
641       {5.4979978f, 1.9096732f},
642   };
643   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
644 }
645
646 /* Issue 1407, http:# code.google.com/p/libgdx/issues/detail?id=1407, */
647 /* with an additional point to show what is happening. */
648 TEST(polyfill2d, Issue1407_pt)
649 {
650   const float poly[][2] = {
651       {3.914329f, 1.9008259f},
652       {4.414321f, 1.903619f},
653       {4.8973203f, 1.9063174f},
654       {5.4979978f, 1.9096732f},
655       {4, 4},
656   };
657   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
658 }
659
660 /* Simplified from Blender bug T40777 */
661 TEST(polyfill2d, IssueT40777_colinear)
662 {
663   const float poly[][2] = {
664       {0.7, 0.37},  {0.7, 0},    {0.76, 0}, {0.76, 0.4}, {0.83, 0.4}, {0.83, 0},    {0.88, 0},
665       {0.88, 0.4},  {0.94, 0.4}, {0.94, 0}, {1, 0},      {1, 0.4},    {0.03, 0.62}, {0.03, 0.89},
666       {0.59, 0.89}, {0.03, 1},   {0, 1},    {0, 0},      {0.03, 0},   {0.03, 0.37},
667   };
668   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
669 }
670
671 /* Blender bug T41986 */
672 TEST(polyfill2d, IssueT41986_axis_align)
673 {
674   const float poly[][2] = {
675       {-0.25, -0.07}, {-0.25, 0.27},  {-1.19, 0.14},  {-0.06, 0.73},  {0.17, 1.25},
676       {-0.25, 1.07},  {-0.38, 1.02},  {-0.25, 0.94},  {-0.40, 0.90},  {-0.41, 0.86},
677       {-0.34, 0.83},  {-0.25, 0.82},  {-0.66, 0.73},  {-0.56, 1.09},  {-0.25, 1.10},
678       {0.00, 1.31},   {-0.03, 1.47},  {-0.25, 1.53},  {0.12, 1.62},   {0.36, 1.07},
679       {0.12, 0.67},   {0.29, 0.57},   {0.44, 0.45},   {0.57, 0.29},   {0.66, 0.12},
680       {0.68, 0.06},   {0.57, -0.36},  {-0.25, -0.37}, {0.49, -0.74},  {-0.59, -1.21},
681       {-0.25, -0.15}, {-0.46, -0.52}, {-1.08, -0.83}, {-1.45, -0.33}, {-1.25, -0.04}};
682
683   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
684 }
685
686 /* Blender bug T52834 */
687 TEST(polyfill2d, IssueT52834_axis_align_co_linear)
688 {
689   const float poly[][2] = {
690       {40, 0},  {36, 0},  {36, 5},  {35, 5},  {35, 0},  {30, 0},  {30, 5},  {29, 5},
691       {29, 0},  {24, 0},  {24, 3},  {23, 4},  {23, 0},  {18, 0},  {18, 5},  {17, 5},
692       {17, 0},  {12, 0},  {12, 5},  {11, 5},  {11, 0},  {6, 0},   {6, 5},   {5, 5},
693       {5, 0},   {0, 0},   {0, 5},   {-1, 5},  {-1, 0},  {-6, 0},  {-9, -3}, {-6, -3},
694       {-6, -2}, {-1, -2}, {0, -2},  {5, -2},  {6, -2},  {11, -2}, {12, -2}, {17, -2},
695       {18, -2}, {23, -2}, {24, -2}, {29, -2}, {30, -2}, {35, -2}, {36, -2}, {40, -2},
696   };
697
698   TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
699 }