[Bf-blender-cvs] [503484c] master: GTest: polyfill2d
Campbell Barton
noreply at git.blender.org
Sun Sep 28 13:44:17 CEST 2014
Commit: 503484c9784d1fa19fd4bb8a68747d31008acce6
Author: Campbell Barton
Date: Sun Sep 28 21:25:14 2014 +1000
Branches: master
https://developer.blender.org/rB503484c9784d1fa19fd4bb8a68747d31008acce6
GTest: polyfill2d
Collection of test cases from libGDX and our own tracker
Tests:
- combine triangle area matches polygon area.
- tris have same winding.
- tris don't have duplicates.
- correct number of internal & boundary edges.
- degenerate polys still give topologically correct output.
also checks all possible start-vert offsets, forwards and backwards.
optional OBJ output, for debugging.
===================================================================
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..7852747
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_polyfill2d_test.cc
@@ -0,0 +1,492 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+/* Use to write out OBJ files, handy for checking output */
+// #define USE_OBJ_PREVIEW
+
+/* test every possible offset and reverse */
+#define USE_COMBINATIONS_ALL
+
+extern "C" {
+#include "BLI_array.h"
+#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
+}
+
+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);
+
+/* -------------------------------------------------------------------- */
+/* 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);
+}
+
+
+/* -------------------------------------------------------------------- */
+/* Macro and helpers to manage checking */
+/**
+ * Main template for polyfill testing.
+ */
+static void test_polyfill_template_check(
+ const char *id, bool is_degenerate,
+ const float poly[][2], const unsigned int poly_tot,
+ const unsigned int tris[][3], const unsigned int tris_tot)
+{
+ test_polyfill_simple(poly, poly_tot, tris, tris_tot);
+ test_polyfill_topology(poly, poly_tot, tris, tris_tot);
+ if (!is_degenerate) {
+ test_polyfill_winding(poly, poly_tot, tris, tris_tot);
+
+ test_polyfill_area(poly, poly_tot, tris, tris_tot);
+ }
+ polyfill_to_obj(id, poly, poly_tot, tris, tris_tot);
+}
+
+static void test_polyfill_template(
+ const char *id, bool is_degenerate,
+ const float poly[][2], const unsigned int poly_tot,
+ unsigned int tris[][3], const unsigned int tris_tot)
+{
+ test_valid_polyfill_prepare(tris, tris_tot);
+ BLI_polyfill_calc(poly, poly_tot, 0, tris);
+
+ /* check all went well */
+ test_polyfill_template_check(id, is_degenerate, poly, poly_tot, tris, tris_tot);
+}
+
+#ifdef USE_COMBINATIONS_ALL
+static void test_polyfill_template_main(
+ const char *id, bool is_degenerate,
+ const float poly[][2], const unsigned int poly_tot,
+ unsigned int tris[][3], const unsigned int tris_tot)
+{
+ /* overkill? - try at _every_ offset & reverse */
+ unsigned int poly_reverse;
+ float (*poly_copy)[2] = (float (*)[2])MEM_mallocN(sizeof(float[2]) * poly_tot, id);
+ float tmp[2];
+
+ memcpy(poly_copy, poly, sizeof(float[2]) * poly_tot);
+
+ for (poly_reverse = 0; poly_reverse < 2; poly_reverse++) {
+ unsigned int poly_cycle;
+
+ if (poly_reverse) {
+ BLI_array_reverse(poly_copy, poly_tot);
+ }
+
+ for (poly_cycle = 0; poly_cycle < poly_tot; poly_cycle++) {
+ // printf("polytest %s ofs=%d, reverse=%d\n", id, poly_cycle, poly_reverse);
+ test_polyfill_template(id, is_degenerate, poly, poly_tot, tris, tris_tot);
+
+ /* cycle */
+ copy_v2_v2(tmp, poly_copy[0]);
+ memmove(&poly_copy[0], &poly_copy[1], (poly_tot - 1) * sizeof(float[2]));
+ copy_v2_v2(poly_copy[poly_tot - 1], tmp);
+ }
+ }
+
+ MEM_freeN(poly_copy);
+}
+#else /* USE_COMBINATIONS_ALL */
+static void test_polyfill_template_main(
+ const char *id, bool is_degenerate,
+ const float poly[][2], const unsigned int poly_tot,
+ unsigned int tris[][3], const unsigned int tris_tot)
+{
+ test_polyfill_template(id, is_degenerate, poly, poly_tot, tris, tris_tot);
+}
+#endif /* USE_COMBINATIONS_ALL */
+
+#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); \
+ const char *id = typeid(*this).name(); \
+ \
+ test_polyfill_template_main(id, is_degenerate, poly, poly_tot, 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", UNPACK3_EX(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)
+
+
+/* A counterclockwise triangle */
+TEST(polyfill2d, TriangleCCW)
+{
+ const float poly[][2] = {{0, 0}, {0, 1}, {1, 0}};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* A counterclockwise square */
+TEST(polyfill2d, SquareCCW)
+{
+ const float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* A clockwise square */
+TEST(polyfill2d, SquareCW)
+{
+ const float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Starfleet insigna */
+TEST(polyfill2d, Starfleet)
+{
+ const 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)
+{
+ const 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)
+{
+ const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Four collinear points */
+TEST(polyfill2d, 4Colinear)
+{
+ const float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Non-consecutive collinear points */
+TEST(polyfill2d, UnorderedColinear)
+{
+ const float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0}};
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
+}
+
+/* Plus shape */
+TEST(polyfill2d, PlusShape)
+{
+ const 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,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list