commit ef5c91a352e199f4f54ea8fbf5c8330a5f4df7a7
parent d96b3066b4662949c00d23152352ce3b232f6a10
Author: vaplv <vaplv@free.fr>
Date: Mon, 22 Sep 2014 16:27:12 +0200
Test and fix the polygon triangulation
Diffstat:
| M | src/polygon.c | | | 40 | ++++++++++++++++++++++------------------ |
| M | src/test_polygon.c | | | 135 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- |
2 files changed, 150 insertions(+), 25 deletions(-)
diff --git a/src/polygon.c b/src/polygon.c
@@ -140,10 +140,13 @@ node_is_an_ear
float T[3], u;
const uint32_t inode_concave = *htable_u32_iterator_key_get(&it);
htable_u32_iterator_next(&it);
+ if(inode_concave == nodes[inode].next
+ || inode_concave == nodes[inode].prev)
+ continue;
/* Project the concave vertex position onto the {prev, curr, next} triangle
* plane and test if it lies into it */
f3_sub(T, nodes[inode_concave].pos, nodes[inode].pos);
- u = f3_dot(T, E1) / det;
+ u = f3_dot(T, P) / det;
if(u >= 0.f && u <= 1.f) {
float Q[3], v;
f3_cross(Q, T, E1);
@@ -336,10 +339,8 @@ polygon_triangulate
htable_u32_clear(&poly->vertices_concave);
darray_u32_clear(&poly->triangle_ids);
- if(poly->nvertices < 3) { /* Point or line */
- res = POLYGON_BAD_ARGUMENT;
- goto error;
- }
+ if(poly->nvertices < 3) /* Point or line */
+ goto exit;
if(poly->nvertices == 3) { /* Already a triangle */
FOR_EACH(ivert, 0, 3) {
@@ -354,7 +355,7 @@ polygon_triangulate
nodes = darray_vertex_node_data_get(&poly->pool);
inode = poly->vertices;
- FOR_EACH(ivert, 0, poly->nvertices) { /* Find the list of concave vertices */
+ FOR_EACH(inode, 0, poly->nvertices) { /* Find the list of concave vertices */
node_normal_compute(poly, inode, normal);
if(f3_dot(normal_convex, normal) <= 0.f) {
const char dummy = 1;
@@ -363,10 +364,11 @@ polygon_triangulate
}
}
- /* "The Graham Scan Triangulates Simple Polygons */
+ /* Implementation of the ear cutting algorithm "The Graham Scan Triangulates
+ * Simple Polygons */
inode = nodes[nodes[poly->vertices].next].next;
while(inode != poly->vertices) {
- if(!node_is_an_ear(poly, &poly->vertices_concave, inode)) {
+ if(!node_is_an_ear(poly, &poly->vertices_concave, nodes[inode].prev)) {
inode = nodes[inode].next;
} else { /* `Prev' is an ear */
const uint32_t iv0 = nodes[nodes[inode].prev].prev;
@@ -401,16 +403,18 @@ polygon_triangulate
}
exit:
- if(indices && nindices) {
- *nindices = (uint32_t)darray_u32_size_get(&poly->triangle_ids);
- *indices = *nindices ? darray_u32_cdata_get(&poly->triangle_ids) : NULL;
- }
- if(poly && poly->nvertices) { /* Restore the linked list */
- poly->vertices = 0;
- nodes = darray_vertex_node_data_get(&poly->pool);
- FOR_EACH(inode, 1, poly->nvertices) {
- nodes[inode].prev = inode == 0 ? poly->nvertices - 1 : inode - 1;
- nodes[inode].next = inode == poly->nvertices - 1 ? 0 : inode + 1;
+ if(poly) {
+ if(indices && nindices && poly) {
+ *nindices = (uint32_t)darray_u32_size_get(&poly->triangle_ids);
+ *indices = *nindices ? darray_u32_cdata_get(&poly->triangle_ids) : NULL;
+ }
+ if(poly->nvertices) { /* Restore the linked list */
+ poly->vertices = 0;
+ nodes = darray_vertex_node_data_get(&poly->pool);
+ FOR_EACH(inode, 0, poly->nvertices) {
+ nodes[inode].prev = inode == 0 ? poly->nvertices - 1 : inode - 1;
+ nodes[inode].next = inode == poly->nvertices - 1 ? 0 : inode + 1;
+ }
}
}
return res;
diff --git a/src/test_polygon.c b/src/test_polygon.c
@@ -14,32 +14,98 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include "polygon.h"
+
#include <rsys/float3.h>
#include <rsys/mem_allocator.h>
+#include <string.h>
+
#define BARG POLYGON_BAD_ARGUMENT
#define OK POLYGON_OK
+static float /* Return the area of the triangulated polygon */
+check_triangulation
+ (struct polygon* poly,
+ const uint32_t* indices,
+ const uint32_t nindices,
+ const uint32_t nedges_contour)
+{
+ float area = 0.f;
+ uint32_t i;
+ /* List the counter edges retrieved after the polygon triangulation. This
+ * array must be indexed by the smallest index of the edge */
+ char* contour;
+ ASSERT(poly && indices && nindices && nedges_contour);
+
+ contour = mem_calloc(nedges_contour, sizeof(char));
+ NCHECK(contour, NULL);
+
+ memset(contour, 0, sizeof(contour));
+ CHECK(nindices % 3, 0);
+ FOR_EACH(i, 0, nindices/3) {
+ const uint32_t* tri = indices + (i*3);
+ float e0[3], e1[3], N[3];
+ float v0[3], v1[3], v2[3];
+ float len;
+ CHECK(polygon_vertex_get(poly, tri[0], v0), OK);
+ CHECK(polygon_vertex_get(poly, tri[1], v1), OK);
+ CHECK(polygon_vertex_get(poly, tri[2], v2), OK);
+ /* Compute the triangle area and add it to the overall polygon area */
+ f3_sub(e0, v1, v0);
+ f3_sub(e1, v2, v0);
+ len = f3_normalize(N, f3_cross(N, e0, e1));
+ CHECK(eq_eps(len, 0.f, 1.e-6f), 0);
+ area += len * 0.5f;
+ /* Update the contour edge flag */
+ if(tri[1] == (tri[0] + 1) % nedges_contour) {
+ CHECK(contour[tri[0]], 0);
+ contour[tri[0]] = 1;
+ }
+ if(tri[2] == (tri[1] + 1) % nedges_contour) {
+ CHECK(contour[tri[1]], 0);
+ contour[tri[1]] = 1;
+ }
+ if(tri[0] == (tri[2] + 1) % nedges_contour) {
+ CHECK(contour[tri[2]], 0);
+ contour[tri[2]] = 1;
+ }
+ }
+ FOR_EACH(i, 0, nedges_contour) /* All the contour edges may be found */
+ CHECK(contour[i], 1);
+
+ mem_free(contour);
+ return area;
+}
+
int
main(int argc, char** argv)
{
+ /* Input polygon contour :
+ * 1-------------2 5---6
+ * | | | |
+ * | 10----9 | | |
+ * | | | 3-----4 |
+ * | | | |
+ * 0---11 8-------------7 */
const float vertices[] = {
0.f, 0.f, 0.f,
0.f, 1.f, 0.f,
- 1.25f, 1.f, 0.f,
- 1.25f, 0.25f, 0.f,
- 1.75f, 0.25f, 0.f,
+ 1.f, 1.f, 0.f,
+ 1.f, 0.25f, 0.f,
+ 1.5f, 0.25f, 0.f,
+ 1.5f, 1.f, 0.f,
1.75f, 1.f, 0.f,
- 2.f, 1.f, 0.f,
- 2.f, 0.f, 0.f,
- 1.f, 0.f, 0.f,
- 1.f, 0.75f, 0.f,
+ 1.75f, 0.f, 0.f,
+ 0.75f, 0.f, 0.f,
+ 0.75f, 0.75f, 0.f,
0.25f, 0.75f, 0.f,
0.25f, 0.f, 0.f
};
struct mem_allocator allocator_proxy;
struct polygon* poly;
+ const uint32_t* indices;
float pos[3];
+ uint32_t nindices;
uint32_t ivertex, nvertices;
(void)argc, (void)argv;
@@ -118,6 +184,60 @@ main(int argc, char** argv)
CHECK(f3_eq_eps(pos, vertices + ivertex*3, 1.e-6f), 1);
}
+ CHECK(polygon_triangulate(NULL, NULL, NULL), BARG);
+ CHECK(polygon_triangulate(poly, NULL, NULL), BARG);
+ CHECK(polygon_triangulate(NULL, &indices, NULL), BARG);
+ CHECK(polygon_triangulate(poly, &indices, NULL), BARG);
+ CHECK(polygon_triangulate(NULL, NULL, &nindices), BARG);
+ CHECK(polygon_triangulate(poly, NULL, &nindices), BARG);
+ CHECK(polygon_triangulate(NULL, &indices, &nindices), BARG);
+
+ /* Check full triangulation */
+ CHECK(polygon_triangulate(poly, &indices, &nindices), OK);
+ CHECK(nindices, 30);
+ CHECK(eq_eps(check_triangulation
+ (poly, indices, nindices, 12), 1.f, 1.e-6f), 1);
+
+ /* After the triangulation the input polygon may be unchanged */
+ CHECK(polygon_vertices_count_get(poly, &nvertices), OK);
+ CHECK(nvertices, sizeof(vertices)/sizeof(float[3]));
+ FOR_EACH(ivertex, 0, sizeof(vertices)/sizeof(float[3])) {
+ CHECK(polygon_vertex_get(poly, ivertex, pos), OK);
+ CHECK(f3_eq_eps(pos, vertices + ivertex*3, 1.e-6f), 1);
+ }
+
+ /* Check that the input polygon can be retriangulated */
+ CHECK(polygon_triangulate(poly, &indices, &nindices), OK);
+ CHECK(nindices, 30);
+ CHECK(eq_eps(check_triangulation
+ (poly, indices, nindices, 12), 1.f, 1.e-6f), 1);
+
+ /* One can triangulate empty polygon */
+ CHECK(polygon_clear(poly), OK);
+ CHECK(polygon_triangulate(poly, &indices, &nindices), OK);
+ CHECK(nindices, 0);
+
+ /* Check the triangulation of an updated polygon */
+ CHECK(polygon_vertex_add(poly, vertices + 0), OK);
+ CHECK(polygon_vertex_add(poly, vertices + 3), OK);
+ CHECK(polygon_triangulate(poly, &indices, &nindices), OK);
+ CHECK(nindices, 0);
+ CHECK(polygon_vertex_add(poly, vertices + 6), OK);
+ CHECK(polygon_triangulate(poly, &indices, &nindices), OK);
+ CHECK(nindices, 3);
+ CHECK(eq_eps(check_triangulation
+ (poly, indices, nindices, 3), 0.5f, 1.e-6f), 1);
+ CHECK(polygon_vertex_add(poly, vertices + 9), OK);
+ CHECK(polygon_vertex_add(poly, vertices + 12), OK);
+ CHECK(polygon_vertex_add(poly, vertices + 15), OK);
+ CHECK(polygon_vertex_add(poly, vertices + 18), OK);
+ CHECK(polygon_vertex_add(poly, vertices + 21), OK);
+ CHECK(polygon_vertex_add(poly, vertices + 21), OK);
+ CHECK(polygon_triangulate(poly, &indices, &nindices), OK);
+ CHECK(nindices, 18);
+ CHECK(eq_eps(check_triangulation
+ (poly, indices, nindices, 8), 1.375f, 1.e-6f), 1);
+
CHECK(polygon_ref_put(poly), OK);
if(MEM_ALLOCATED_SIZE(&allocator_proxy)) {
char dump[512];
@@ -129,3 +249,4 @@ main(int argc, char** argv)
CHECK(mem_allocated_size(), 0);
return 0;
}
+
