commit cd191ce1786ba49ad76e6d06b1368229b4751390
parent 0f5885ea280d8eca5f2533aaaa0d2712da246c1e
Author: vaplv <vaplv@free.fr>
Date: Wed, 26 Apr 2017 11:45:08 +0200
Fix the triangulation algorithm
The triangulation might fail if the first and the last vertex of the
polygon was the same. Priorly to the triangulation process, the last
vertices are now removed if they are at the same position of the first
one.
Diffstat:
5 files changed, 141 insertions(+), 16 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -13,9 +13,8 @@
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
-cmake_minimum_required(VERSION 2.6)
+cmake_minimum_required(VERSION 2.8)
project(polygon C)
-cmake_policy(SET CMP0011 NEW)
enable_testing()
option(BUILD_STATIC "Build library as static rather than shared" OFF)
@@ -53,12 +52,12 @@ rcmake_prepend_path(POLYGON_FILES_DOC ${PROJECT_SOURCE_DIR}/../)
if(CMAKE_COMPILER_IS_GNUCC)
set(MATH_LIB m)
-endif(CMAKE_COMPILER_IS_GNUCC)
+endif()
if(BUILD_STATIC)
add_library(polygon STATIC ${POLYGON_FILES_SRC} ${POLYGON_FILES_INC})
set_target_properties(polygon PROPERTIES DEFINE_SYMBOL POLYGON_STATIC_BUILD)
-else(BUILD_STATIC)
+else()
add_library(polygon SHARED ${POLYGON_FILES_SRC} ${POLYGON_FILES_INC})
set_target_properties(polygon PROPERTIES
@@ -66,7 +65,7 @@ else(BUILD_STATIC)
VERSION ${VERSION}
SOVERSION ${VERSION_MAJOR})
target_link_libraries(polygon ${MATH_LIB})
-endif(BUILD_STATIC)
+endif()
target_link_libraries(polygon RSys)
rcmake_setup_devel(polygon Polygon ${VERSION} polygon_version.h)
@@ -75,11 +74,19 @@ rcmake_setup_devel(polygon Polygon ${VERSION} polygon_version.h)
# Define tests
################################################################################
if(NOT NO_TEST)
- add_executable(test_polygon ${POLYGON_SOURCE_DIR}/test_polygon.c)
- target_link_libraries(test_polygon polygon ${MATH_LIB})
- add_test(test_polygon test_polygon)
- rcmake_set_test_runtime_dirs(test_polygon _runtime_dirs)
-endif(NOT NO_TEST)
+ function(new_test _name)
+ add_executable(${_name}
+ ${POLYGON_SOURCE_DIR}/${_name}.c
+ ${POLYGON_SOURCE_DIR}/test_polygon_utils.h)
+ target_link_libraries(${_name} polygon ${MATH_LIB})
+ add_test(${_name} ${_name})
+
+ rcmake_set_test_runtime_dirs(${_name} _runtime_dirs)
+ endfunction()
+
+ new_test(test_polygon)
+ new_test(test_polygon1)
+endif()
################################################################################
# Install directories
diff --git a/src/polygon.c b/src/polygon.c
@@ -52,6 +52,32 @@ struct polygon {
/*******************************************************************************
* Helper functions
******************************************************************************/
+/* Remove the last vertices if they are the same of the first one */
+static void
+cleanup_polygon(struct polygon* poly)
+{
+ struct vertex_node* first;
+ struct vertex_node* last;
+ struct vertex_node* nodes;
+ ASSERT(poly);
+
+ if(poly->nvertices <= 1) return;
+
+ nodes = darray_vertex_node_data_get(&poly->pool);
+ first = nodes + poly->vertices;
+
+ for(;;) {
+ last = nodes + first->prev;
+ if(!f3_eq_eps(first->pos, last->pos, 1.e-6f) || first == last)
+ break;
+
+ nodes[last->prev].next = last->next;
+ nodes[last->next].prev = last->prev;
+ --poly->nvertices;
+ }
+}
+
+
static void
node_normal_compute
(const struct polygon* poly,
@@ -338,6 +364,8 @@ polygon_triangulate
goto error;
}
+ cleanup_polygon(poly);
+
htable_u32_clear(&poly->vertices_concave);
darray_u32_clear(&poly->triangle_ids);
diff --git a/src/test_polygon.c b/src/test_polygon.c
@@ -14,6 +14,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include "polygon.h"
+#include "test_polygon_utils.h"
#include <rsys/float3.h>
#include <rsys/mem_allocator.h>
@@ -236,12 +237,8 @@ main(int argc, char** argv)
(poly, indices, nindices, 8), 1.375f, 1.e-6f), 1);
CHECK(polygon_ref_put(poly), RES_OK);
- if(MEM_ALLOCATED_SIZE(&allocator_proxy)) {
- char dump[512];
- MEM_DUMP(&allocator_proxy, dump, sizeof(dump)/sizeof(char));
- fprintf(stderr, "%s\n", dump);
- FATAL("Memory leaks\n");
- }
+
+ check_memory_allocator(&allocator_proxy);
mem_shutdown_proxy_allocator(&allocator_proxy);
CHECK(mem_allocated_size(), 0);
return 0;
diff --git a/src/test_polygon1.c b/src/test_polygon1.c
@@ -0,0 +1,59 @@
+/* Copyright (C) 2014-2016 Vincent Forest (vaplv@free.fr)
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "polygon.h"
+#include "test_polygon_utils.h"
+#include <rsys/mem_allocator.h>
+
+int
+main(int argc, char** argv)
+{
+ struct mem_allocator allocator_proxy;
+ struct polygon* poly;
+ union { uint32_t i; float f; } ucast;
+ float pos[3] = {0, 0, 0};
+ const uint32_t* ids;
+ uint32_t nids;
+ (void)argc, (void)argv;
+
+ CHECK(mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator), RES_OK);
+
+ CHECK(polygon_create(&allocator_proxy, &poly), RES_OK);
+
+ pos[0] = (ucast.i = 0xbeb504f3, ucast.f);
+ pos[1] = (ucast.i = 0x3eb504f3, ucast.f);
+ CHECK(polygon_vertex_add(poly, pos), RES_OK);
+ pos[0] = (ucast.i = 0xbe977d76, ucast.f);
+ pos[1] = (ucast.i = 0x3ec14031, ucast.f);
+ CHECK(polygon_vertex_add(poly, pos), RES_OK);
+ pos[0] = (ucast.i = 0xbe5dab96, ucast.f);
+ pos[1] = (ucast.i = 0x3f05ca33, ucast.f);
+ CHECK(polygon_vertex_add(poly, pos), RES_OK);
+ pos[0] = (ucast.i = 0xbecccbef, ucast.f);
+ pos[1] = (ucast.i = 0x3ecccbef, ucast.f);
+ CHECK(polygon_vertex_add(poly, pos), RES_OK);
+ pos[0] = (ucast.i = 0xbeb504f3, ucast.f);
+ pos[1] = (ucast.i = 0x3eb504f3, ucast.f);
+ CHECK(polygon_vertex_add(poly, pos), RES_OK);
+
+ CHECK(polygon_triangulate(poly, &ids, &nids), RES_OK);
+ CHECK(nids, 6);
+ CHECK(polygon_ref_put(poly), RES_OK);
+
+ check_memory_allocator(&allocator_proxy);
+ mem_shutdown_proxy_allocator(&allocator_proxy);
+ CHECK(mem_allocated_size(), 0);
+ return 0;
+}
diff --git a/src/test_polygon_utils.h b/src/test_polygon_utils.h
@@ -0,0 +1,34 @@
+/* Copyright (C) 2014-2016 Vincent Forest (vaplv@free.fr)
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef TEST_POLYGON_UTILS_H
+#define TEST_POLYGON_UTILS_H
+
+#include <rsys/mem_allocator.h>
+#include <stdio.h>
+
+static void
+check_memory_allocator(struct mem_allocator* allocator)
+{
+ if(MEM_ALLOCATED_SIZE(allocator)) {
+ char dump[512];
+ MEM_DUMP(allocator, dump, sizeof(dump)/sizeof(char));
+ fprintf(stderr, "%s\n", dump);
+ FATAL("Memory leaks\n");
+ }
+}
+
+#endif /* TEST_POLYGON_UTILS_H */
+
