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