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