Commit: 8eee31eef42c642445a1ab0a9755c0002002d946
Author: Campbell Barton
Date: Tue Jun 24 19:31:00 2014 +1000
https://developer.blender.org/rB8eee31eef42c642445a1ab0a9755c0002002d946
Add polyfill2d WIP test
Create branch for preparing tests
===================================================================
A tests/gtests/blenlib/BLI_polyfill2d_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/tests/gtests/blenlib/BLI_polyfill2d_test.cc
b/tests/gtests/blenlib/BLI_polyfill2d_test.cc
new file mode 100644
index 0000000..59a5c4e
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_polyfill2d_test.cc
@@ -0,0 +1,413 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+/* Use to write out OBJ files, handy for checking output */
+// #define USE_OBJ_PREVIEW
+
+extern "C" {
+#include "BLI_polyfill2d.h"
+#include "BLI_math.h"
+#include "BLI_edgehash.h"
+#include "MEM_guardedalloc.h"
+
+#ifdef USE_OBJ_PREVIEW
+# include "BLI_string.h"
+#endif
+}
+
+/* -------------------------------------------------------------------- */
+/* test utility functions */
+
+#define TRI_ERROR_VALUE (unsigned int)-1
+
+static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int
tris_tot)
+{
+ unsigned int i;
+ for (i = 0; i < tris_tot; i++) {
+ unsigned int j;
+ for (j = 0; j < 3; j++) {
+ tris[i][j] = TRI_ERROR_VALUE;
+ }
+ }
+}
+
+/**
+ * Basic check for face index values:
+ *
+ * - no duplicates.
+ * - all tris set.
+ * - all verts used at least once.
+ */
+static void test_polyfill_simple(
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ unsigned int i;
+ int *tot_used = (int *)MEM_callocN(poly_tot * sizeof(int), __func__);
+ for (i = 0; i < tris_tot; i++) {
+ unsigned int j;
+ for (j = 0; j < 3; j++) {
+ EXPECT_NE(TRI_ERROR_VALUE, tris[i][j]);
+ tot_used[tris[i][j]] += 1;
+ }
+ EXPECT_NE(tris[i][0], tris[i][1]);
+ EXPECT_NE(tris[i][1], tris[i][2]);
+ EXPECT_NE(tris[i][2], tris[i][0]);
+ }
+ for (i = 0; i < poly_tot; i++) {
+ EXPECT_NE(0, tot_used[i]);
+ }
+ MEM_freeN(tot_used);
+}
+
+static void test_polyfill_topology(
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ EdgeHash *edgehash = BLI_edgehash_new(__func__);
+ EdgeHashIterator *ehi;
+ unsigned int i;
+ for (i = 0; i < tris_tot; i++) {
+ unsigned int j;
+ for (j = 0; j < 3; j++) {
+ const unsigned int v1 = tris[i][j];
+ const unsigned int v2 = tris[i][(j + 1) % 3];
+ void **p = BLI_edgehash_lookup_p(edgehash, v1, v2);
+ if (p) {
+ *p = (void *)((intptr_t)*p + (intptr_t)1);
+ }
+ else {
+ BLI_edgehash_insert(edgehash, v1, v2, (void
*)(intptr_t)1);
+ }
+ }
+ }
+ EXPECT_EQ(poly_tot + (poly_tot - 3), BLI_edgehash_size(edgehash));
+
+ for (i = 0; i < poly_tot; i++) {
+ const unsigned int v1 = i;
+ const unsigned int v2 = (i + 1) % poly_tot;
+ void **p = BLI_edgehash_lookup_p(edgehash, v1, v2);
+ EXPECT_EQ(1, (void *)p != NULL);
+ EXPECT_EQ(1, (intptr_t)*p);
+ }
+
+ for (ehi = BLI_edgehashIterator_new(edgehash), i = 0;
+ BLI_edgehashIterator_isDone(ehi) == false;
+ BLI_edgehashIterator_step(ehi), i++)
+ {
+ void **p = BLI_edgehashIterator_getValue_p(ehi);
+ EXPECT_EQ(true, ELEM((intptr_t)*p, 1, 2));
+ }
+
+ BLI_edgehash_free(edgehash, NULL);
+}
+
+/**
+ * Check all faces are flipped the same way
+ */
+static void test_polyfill_winding(
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ unsigned int i;
+ unsigned int count[2] = {0, 0};
+ for (i = 0; i < tris_tot; i++) {
+ float winding_test = cross_tri_v2(poly[tris[i][0]],
poly[tris[i][1]], poly[tris[i][2]]);
+ if (fabsf(winding_test) > FLT_EPSILON) {
+ count[winding_test < 0.0f] += 1;
+ }
+ }
+ EXPECT_EQ(true, ELEM(0, count[0], count[1]));
+}
+
+/**
+ * Check the accumulated triangle area is close to the original area.
+ */
+static void test_polyfill_area(
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ unsigned int i;
+ const float area_tot = area_poly_v2(poly, poly_tot);
+ float area_tot_tris = 0.0f;
+ const float eps_abs = 0.00001f;
+ const float eps = area_tot > 1.0f ? (area_tot * eps_abs) : eps_abs;
+ for (i = 0; i < tris_tot; i++) {
+ area_tot_tris += area_tri_v2(poly[tris[i][0]],
poly[tris[i][1]], poly[tris[i][2]]);
+ }
+ EXPECT_NEAR(area_tot, area_tot_tris, eps);
+}
+
+/**
+ * Main template for polyfill testing.
+ */
+#define TEST_POLYFILL_TEMPLATE_STATIC(poly, is_degenerate) \
+{ \
+ unsigned int tris[POLY_TRI_COUNT(ARRAY_SIZE(poly))][3]; \
+ const unsigned int poly_tot = ARRAY_SIZE(poly); \
+ const unsigned int tris_tot = ARRAY_SIZE(tris); \
+ test_valid_polyfill_prepare(tris, tris_tot); \
+ \
+ BLI_polyfill_calc(poly, poly_tot, 0, tris); \
+ \
+ test_polyfill_simple(poly, poly_tot, (const unsigned int (*)[3])tris,
tris_tot); \
+ test_polyfill_topology(poly, poly_tot, (const unsigned int (*)[3])tris,
tris_tot); \
+ if (!is_degenerate) { \
+ test_polyfill_winding(poly, poly_tot, (const unsigned int
(*)[3])tris, tris_tot); \
+ \
+ test_polyfill_area(poly, poly_tot, (const unsigned int
(*)[3])tris, tris_tot); \
+ } \
+ polyfill_to_obj(typeid(*this).name(), poly, poly_tot, (const unsigned
int (*)[3])tris, tris_tot); \
+} (void)0
+
+/* -------------------------------------------------------------------- */
+/* visualisation functions (not needed for testing) */
+
+#ifdef USE_OBJ_PREVIEW
+static void polyfill_to_obj(
+ const char *id,
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ char path[1024];
+ FILE *f;
+ unsigned int i;
+
+ BLI_snprintf(path, sizeof(path), "%s.obj", id);
+
+ f = fopen(path, "w");
+ if (!f) {
+ return;
+ }
+
+ for (i = 0; i < poly_tot; i++) {
+ fprintf(f, "v %f %f 0.0\n", UNPACK2(poly[i]));
+ }
+
+ for (i = 0; i < tris_tot; i++) {
+ fprintf(f, "f %u %u %u\n", UNPACK3OP(1 +, tris[i]));
+ }
+
+ fclose(f);
+}
+#else
+static void polyfill_to_obj(
+ const char *id,
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ (void)id;
+ (void)poly, (void)poly_tot;
+ (void)tris, (void)tris_tot;
+}
+#endif /* USE_OBJ_PREVIEW */
+
+
+/* -------------------------------------------------------------------- */
+/* tests */
+
+#define POLY_TRI_COUNT(len) ((len) - 2)
+
+#if 0
+/* BLI_cleanup_path */
+TEST(polyfill2d, Empty)
+{
+ BLI_polyfill_calc(NULL, 0, 0, NULL);
+}
+#endif
+
+// @Override
+// public void create () {
+// // An empty "polygon"
+// testCases.add(new TestCase(new float[] {}, true));
+//
+// // A point
+// testCases.add(new TestCase(new float[] {0, 0}, true));
+//
+// // A line segment
+// testCases.add(new TestCase(new float[] {0, 0, 1, 1}, true));
+
+/* A counterclockwise triangle */
+TEST(polyfill2d, TriangleCCW)
+{
+ float poly[][2] = {{0, 0}, {0, 1}, {1, 0},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* A counterclockwise square */
+TEST(polyfill2d, SquareCCW)
+{
+ float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* A clockwise square */
+TEST(polyfill2d, SquareCW)
+{
+ float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Starfleet insigna */
+TEST(polyfill2d, Starfleet)
+{
+ float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Starfleet insigna with repeated point */
+TEST(polyfill2d, StarfleetDegenerate)
+{
+ float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {0.6f, 0.4f}, {1, 0}, {0.5f,
1},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Three collinear points */
+TEST(polyfill2d, 3Colinear)
+{
+ float poly[][2] = {{0, 0}, {1, 0}, {2, 0},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Four collinear points */
+TEST(polyfill2d, 4Colinear)
+{
+ float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Non-consecutive collinear points */
+TEST(polyfill2d, UnorderedColinear)
+{
+ float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Plus shape */
+TEST(polyfill2d, PlusShape)
+{
+ float poly[][2] = {
+ {1, 0}, {2, 0}, {2, 1}, {3, 1}, {3, 2}, {2, 2}, {2, 3}, {1, 3}, {1,
2}, {0, 2}, {0, 1}, {1, 1},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Star shape */
+TEST(polyfill2d, StarShape)
+{
+ float poly[][2] = {
+ {4, 0}, {5, 3}, {8, 4}, {5, 5}, {4, 8}, {3, 5}, {0, 4}, {3, 3},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* U shape */
+TEST(polyfill2d, UShape)
+{
+ float poly[][2] = {
+ {1, 0}, {2, 0}, {3, 1}, {3, 3}, {2, 3}, {2, 1}, {1, 1}, {1, 3}, {0,
3}, {0, 1},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Spiral */
+TEST(polyfill2d, Spiral)
+{
+ float poly[][2] = {
+ {1, 0}, {4, 0}, {5, 1}, {5, 4}, {4, 5}, {1, 5}, {0, 4}, {0, 3},
+ {1, 2}, {2, 2}, {3, 3}, {1, 3}, {1, 4}, {4, 4}, {4, 1}, {0, 1},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Test case from http:#
www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml */
+TEST(polyfill2d, TestFlipCode)
+{
+ float poly[][2] = {
+ {0, 6}, {0, 0}, {3, 0}, {4, 1}, {6, 1}, {8, 0}, {12, 0}, {13, 2},
+ {8, 2}, {8, 4}, {11, 4}, {11, 6}, {6, 6}, {4, 3}, {2, 6},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Self-intersection */
+TEST(polyfill2d, SelfIntersect)
+{
+ float poly[][2] = {{0, 0}, {1, 1}, {2, -1}, {3, 1}, {4, 0},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
+}
+
+/* Self-touching */
+TEST(polyfill2d, SelfTouch)
+{
+ float poly[][2] = {
+ {0, 0}, {4, 0}, {4, 4}, {2, 4}, {2, 3}, {3, 3}, {3, 1}, {1, 1}, {1,
3}, {2, 3}, {2, 4}, {0, 4},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Self-overlapping */
+TEST(polyfill2d, SelfOverlap)
+{
+ float poly[][2] = {
+ {0, 0}, {4, 0}, {4, 4}, {1, 4}, {1, 3}, {3, 3}, {3, 1}, {1, 1}, {1,
3}, {3, 3}, {3, 4}, {0, 4},};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
+}
+
+/* Test case from http:# www.davdata.nl/math/polygons.html */
+TEST(polyfill2d, TestDavData)
+{
+ float poly[][2] = {
+ {190, 480}, {140, 180}, {310, 100}, {330, 390}, {290, 390}, {280,
260}, {220, 260}, {220, 430}, {370, 430},
+ {350, 30}, {50, 30}, {160, 560}, {730, 510}, {710, 20}, {410, 30},
{470, 440}, {640, 410}, {630, 140},
+ {590, 140},
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
