[Bf-blender-cvs] [d19f7e6] gtest-testing: Polyfill test: added winding and area tests
Campbell Barton
noreply at git.blender.org
Tue May 20 18:06:56 CEST 2014
Commit: d19f7e6b7dea40c7c5eaa64953e18af581d23b2a
Author: Campbell Barton
Date: Wed May 21 01:35:15 2014 +1000
https://developer.blender.org/rBd19f7e6b7dea40c7c5eaa64953e18af581d23b2a
Polyfill test: added winding and area tests
also cleanup naming
===================================================================
M source/tests/blenlib_tests/CMakeLists.txt
M source/tests/blenlib_tests/polyfill2d_test.cc
===================================================================
diff --git a/source/tests/blenlib_tests/CMakeLists.txt b/source/tests/blenlib_tests/CMakeLists.txt
index c0fd59d..bb03a1f 100644
--- a/source/tests/blenlib_tests/CMakeLists.txt
+++ b/source/tests/blenlib_tests/CMakeLists.txt
@@ -25,6 +25,7 @@ set(INC
.
../
../../blender/blenlib
+ ../../../intern/guardedalloc
)
include_directories(${INC})
diff --git a/source/tests/blenlib_tests/polyfill2d_test.cc b/source/tests/blenlib_tests/polyfill2d_test.cc
index d95652d..cf210e69 100644
--- a/source/tests/blenlib_tests/polyfill2d_test.cc
+++ b/source/tests/blenlib_tests/polyfill2d_test.cc
@@ -3,6 +3,7 @@
extern "C" {
#include "BLI_polyfill2d.h"
#include "BLI_math.h"
+#include "MEM_guardedalloc.h"
}
/* -------------------------------------------------------------------- */
@@ -10,11 +11,8 @@ extern "C" {
/*
* TODO:
- * - check faces are flipped the same way.
* - check all edges along the polygon have one face user, all others 2.
* - all indicies are used in a triangle least once.
- * - the area of the triangles combine adds up to the area of the polygon (with some error margin)...
- * ... note, this needs to be skipped for intentionally self-overlapping tests.
*/
#define TRI_ERROR_VALUE (unsigned int)-1
@@ -30,21 +28,69 @@ static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int tri
}
}
-#define TEST_VALID_POLYFILL(tri, tri_tot) \
- { \
- unsigned int i; \
- for (i = 0; i < tri_tot; i++) { \
- unsigned int j; \
- for (j = 0; j < 3; j++) { \
- EXPECT_NE(TRI_ERROR_VALUE, tri[i][j]); \
- } \
- EXPECT_NE(tri[i][0], tri[i][1]); \
- EXPECT_NE(tri[i][1], tri[i][2]); \
- EXPECT_NE(tri[i][2], tri[i][0]); \
+/**
+ * Basic check for face index values:
+ *
+ * - no duplicates.
+ * - all tris set.
+ * - all verts used at least once.
+ */
+#define TEST_POLYFILL_SIMPLE(poly, poly_tot, tri, tri_tot) \
+{ \
+ unsigned int i; \
+ int *tot_used = (int *)MEM_callocN(poly_tot * sizeof(int), __func__); \
+ for (i = 0; i < tri_tot; i++) { \
+ unsigned int j; \
+ for (j = 0; j < 3; j++) { \
+ EXPECT_NE(TRI_ERROR_VALUE, tri[i][j]); \
+ tot_used[tri[i][j]] += 1; \
} \
- } (void)0
+ EXPECT_NE(tri[i][0], tri[i][1]); \
+ EXPECT_NE(tri[i][1], tri[i][2]); \
+ EXPECT_NE(tri[i][2], tri[i][0]); \
+ } \
+ for (i = 0; i < poly_tot; i++) { \
+ EXPECT_NE(0, tot_used[i]); \
+ } \
+ MEM_freeN(tot_used); \
+} (void)0
-#define TEST_POLYFILL_TEMPLATE_STATIC(poly) \
+/**
+ * Check all faces are flipped the same way
+ */
+#define TEST_POLYFILL_WINDING(poly, poly_tot, tri, tri_tot) \
+{ \
+ unsigned int i; \
+ unsigned int count[2] = {0, 0}; \
+ for (i = 0; i < tri_tot; i++) { \
+ float winding_test = cross_tri_v2(poly[tri[i][0]], poly[tri[i][1]], poly[tri[i][2]]); \
+ if (fabsf(winding_test) > FLT_EPSILON) { \
+ count[winding_test < 0.0f] += 1; \
+ } \
+ } \
+ EXPECT_EQ(true, ELEM(0, count[0], count[1])); \
+} (void)0
+
+/**
+ * Check the accumulated triangle area is close to the original area.
+ */
+#define TEST_POLYFILL_AREA(poly, poly_tot, tri, tri_tot) \
+{ \
+ unsigned int i; \
+ const float area_tot = area_poly_v2(poly, poly_tot); \
+ float area_tot_tri = 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 < tri_tot; i++) { \
+ area_tot_tri += area_tri_v2(poly[tri[i][0]], poly[tri[i][1]], poly[tri[i][2]]); \
+ } \
+ EXPECT_NEAR(area_tot, area_tot_tri, eps); \
+} (void)0
+
+/**
+ * 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); \
@@ -52,13 +98,18 @@ static void test_valid_polyfill_prepare(unsigned int tris[][3], unsigned int tri
\
BLI_polyfill_calc(poly, poly_tot, tris); \
\
- TEST_VALID_POLYFILL(tris, ARRAY_SIZE(tris)); \
+ TEST_POLYFILL_SIMPLE(poly, ARRAY_SIZE(poly), tris, ARRAY_SIZE(tris)); \
+ if (!is_degenerate) { \
+ TEST_POLYFILL_WINDING(poly, ARRAY_SIZE(poly), tris, ARRAY_SIZE(tris)); \
+ \
+ TEST_POLYFILL_AREA(poly, ARRAY_SIZE(poly), tris, ARRAY_SIZE(tris)); \
+ } \
} (void)0
#define POLY_TRI_COUNT(len) ((len) - 2)
/* BLI_cleanup_path */
-TEST(pathutils, PolyFill2D_Empty)
+TEST(polyfill2d, Empty)
{
BLI_polyfill_calc(NULL, 0, NULL);
}
@@ -75,158 +126,158 @@ TEST(pathutils, PolyFill2D_Empty)
// testCases.add(new TestCase(new float[] {0, 0, 1, 1}, true));
/* A counterclockwise triangle */
-TEST(pathutils, PolyFill2D_TriangleCCW)
+TEST(polyfill2d, TriangleCCW)
{
float poly[][2] = {{0, 0}, {0, 1}, {1, 0},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* A counterclockwise square */
-TEST(pathutils, PolyFill2D_SquareCCW)
+TEST(polyfill2d, SquareCCW)
{
float poly[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* A clockwise square */
-TEST(pathutils, PolyFill2D_SquareCW)
+TEST(polyfill2d, SquareCW)
{
float poly[][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Starfleet insigna */
-TEST(pathutils, PolyFill2D_Starfleet)
+TEST(polyfill2d, Starfleet)
{
float poly[][2] = {{0, 0}, {0.6f, 0.4f}, {1, 0}, {0.5f, 1},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Starfleet insigna with repeated point */
-TEST(pathutils, PolyFill2D_StarfleetDegenerate)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Three collinear points */
-TEST(pathutils, PolyFill2D_3Colinear)
+TEST(polyfill2d, 3Colinear)
{
float poly[][2] = {{0, 0}, {1, 0}, {2, 0},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Four collinear points */
-TEST(pathutils, PolyFill2D_4Colinear)
+TEST(polyfill2d, 4Colinear)
{
float poly[][2] = {{0, 0}, {1, 0}, {2, 0}, {3, 0},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Non-consecutive collinear points */
-TEST(pathutils, PolyFill2D_UnorderedColinear)
+TEST(polyfill2d, UnorderedColinear)
{
float poly[][2] = {{0, 0}, {1, 1}, {2, 0}, {3, 1}, {4, 0},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Plus shape */
-TEST(pathutils, PolyFill2D_PlusShape)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Star shape */
-TEST(pathutils, PolyFill2D_StarShape)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* U shape */
-TEST(pathutils, PolyFill2D_UShape)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Spiral */
-TEST(pathutils, PolyFill2D_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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Test case from http:# www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml */
-TEST(pathutils, PolyFill2D_TestFlipCode)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Self-intersection */
-TEST(pathutils, PolyFill2D_SelfIntersect)
+TEST(polyfill2d, SelfIntersect)
{
float poly[][2] = {{0, 0}, {1, 1}, {2, -1}, {3, 1}, {4, 0},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
}
/* Self-touching */
-TEST(pathutils, PolyFill2D_SelfTouch)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Self-overlapping */
-TEST(pathutils, PolyFill2D_SelfOverlap)
+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);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, true);
}
/* Test case from http:# www.davdata.nl/math/polygons.html */
-TEST(pathutils, PolyFill2D_TestDavData)
+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}, {580, 360}, {510, 370}, {510, 60}, {650, 70}, {660, 450}, {190, 480},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Issue 815, http:# code.google.com/p/libgdx/issues/detail?id=815 */
-TEST(pathutils, PolyFill2D_TestIssue815)
+TEST(polyfill2d, TestIssue815)
{
float poly[][2] = {
{-2.0f, 0.0f}, {-2.0f, 0.5f}, {0.0f, 1.0f}, {0.5f, 2.875f},
{1.0f, 0.5f}, {1.5f, 1.0f}, {2.0f, 1.0f}, {2.0f, 0.0f},};
- TEST_POLYFILL_TEMPLATE_STATIC(poly);
+ TEST_POLYFILL_TEMPLATE_STATIC(poly, false);
}
/* Issue 207, comment #1, http:# code.google.com/p/libgdx/issues/detail?id=207#c1 */
-TEST(pathutils, PolyFill2D_TestIssue207_1)
+TEST(polyfill2d, TestIssue207_1)
{
float poly[][2] = {
{72.42465f, 197.07095f}, {78.485535f, 189.92776f}, {86.12059f, 180.92929f}, {99.68253f, 16
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list