commit be5cf33acb117cb1af85bbb3a02b55c80f79d61c
parent 6157fa54c6827b6af0b670f4880ba8a3b22e6e25
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 26 Aug 2016 12:25:57 +0200
Use the clipper library to perform clip operations
Replace the internal Weiler & Atherton clipping algorithm by the clipper
library.
Diffstat:
4 files changed, 198 insertions(+), 549 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -14,10 +14,9 @@
# along with this program. If not, see <http://www.gnu.org/licenses/>.
cmake_minimum_required(VERSION 2.8)
-project(cpr C)
+project(cpr C CXX)
enable_testing()
-option(BUILD_STATIC "Build library as static rather than shared" ON)
option(NO_TEST "Do not compile the test pograms" OFF)
set(CPR_SOURCE_DIR ${PROJECT_SOURCE_DIR}/../src)
@@ -28,7 +27,14 @@ set(CPR_SOURCE_DIR ${PROJECT_SOURCE_DIR}/../src)
find_package(RCMake REQUIRED)
find_package(RSys 0.4 REQUIRED)
find_package(Polygon 0.0.5 REQUIRED)
-include_directories(${RSys_INCLUDE_DIR} ${Polygon_INCLUDE_DIR})
+find_package(PkgConfig REQUIRED)
+pkg_check_modules(Clipper REQUIRED polyclipping)
+
+link_directories(${Clipper_LIBRARY_DIRS})
+include_directories(
+ ${Clipper_INCLUDE_DIRS}
+ ${Polygon_INCLUDE_DIR}
+ ${RSys_INCLUDE_DIR})
set(CMAKE_MODULE_PATH ${RCMAKE_SOURCE_DIR})
include(rcmake)
@@ -50,18 +56,18 @@ set(CPR_FILES_DOC COPYING README.md)
rcmake_prepend_path(CPR_FILES_SRC ${CPR_SOURCE_DIR})
rcmake_prepend_path(CPR_FILES_INC ${CPR_SOURCE_DIR})
rcmake_prepend_path(CPR_FILES_DOC ${PROJECT_SOURCE_DIR}/../)
+set_source_files_properties(${CPR_FILES_SRC} PROPERTIES LANGUAGE CXX)
+
+add_library(cpr SHARED ${CPR_FILES_SRC} ${CPR_FILES_INC})
+set_target_properties(cpr PROPERTIES
+ DEFINE_SYMBOL CPR_SHARED_BUILD
+ VERSION ${VERSION}
+ SOVERSION ${VERSION_MAJOR})
+target_link_libraries(cpr RSys Polygon ${Clipper_LIBRARIES})
-if(BUILD_STATIC)
- add_library(cpr STATIC ${CPR_FILES_SRC} ${CPR_FILES_INC})
- set_target_properties(cpr PROPERTIES DEFINE_SYMBOL CPR_STATIC_BUILD)
-else()
- add_library(cpr SHARED ${CPR_FILES_SRC} ${CPR_FILES_INC})
- set_target_properties(cpr PROPERTIES
- DEFINE_SYMBOL CPR_SHARED_BUILD
- VERSION ${VERSION}
- SOVERSION ${VERSION_MAJOR})
+if(CMAKE_COMPILER_IS_GNUCXX)
+ set_target_properties(cpr PROPERTIES COMPILE_FLAGS "-Wno-long-long")
endif()
-target_link_libraries(cpr RSys Polygon)
rcmake_setup_devel(cpr CPR ${VERSION} cpr_version.h)
@@ -70,7 +76,7 @@ rcmake_setup_devel(cpr CPR ${VERSION} cpr_version.h)
################################################################################
if(NOT NO_TEST)
- if(CMAKE_COMPILER_IS_GNUCC)
+ if(CMAKE_COMPILER_IS_GNUCXX OR CMAKE_COMPILER_IS_GNUCC)
set(MATH_LIB m)
endif()
diff --git a/src/cpr.h b/src/cpr.h
@@ -104,5 +104,7 @@ cpr_mesh_get_position
const size_t ivert,
double position[2]);
+END_DECLS
+
#endif /* CPR_H */
diff --git a/src/cpr_mesh.c b/src/cpr_mesh.c
@@ -15,8 +15,6 @@
#include "cpr.h"
-#include <polygon.h>
-
#include <rsys/double2.h>
#include <rsys/dynamic_array_double.h>
#include <rsys/dynamic_array_size_t.h>
@@ -24,47 +22,26 @@
#include <rsys/mem_allocator.h>
#include <rsys/ref_count.h>
-struct contour {
- const struct node* nodes;
- const double* coords;
- size_t nnodes;
-};
+#include <polygon.h>
+#include <clipper.hpp>
+STATIC_ASSERT(sizeof(ClipperLib::cInt) == sizeof(double), Unexpected_Type_Size);
struct vertex { double pos[2]; };
-static INLINE char
+static FINLINE int
vertex_eq(const struct vertex* a, const struct vertex* b)
-{
- return d2_eq_eps(a->pos, b->pos, 0.e-6);
-}
+{ return d2_eq(a->pos, b->pos); }
#define HTABLE_NAME vertex
-#define HTABLE_DATA size_t /* Index of the firs node */
+#define HTABLE_DATA size_t
#define HTABLE_KEY struct vertex
#define HTABLE_KEY_FUNCTOR_EQ vertex_eq
#include <rsys/hash_table.h>
-struct node {
- size_t next;
- size_t prev;
- size_t link;
- size_t id;
- double t;
-};
-
-#define DARRAY_NAME node
-#define DARRAY_DATA struct node
-#include <rsys/dynamic_array.h>
-
struct poly {
struct darray_double coords;
- double lower[2], upper[2];
-};
-
-struct hit {
- double pos[2];
- double t0; /* Parametric intersection on 1st edge */
- double t1; /* Parametric intersection on 2nd edge */
+ double lower[2];
+ double upper[2];
};
struct cpr_mesh {
@@ -78,108 +55,36 @@ struct cpr_mesh {
/*******************************************************************************
* Helper functions
******************************************************************************/
-static INLINE int
-aabb_is_degenerated(const double lower[2], const double upper[2])
+static FINLINE ClipperLib::cInt
+double_to_cInt(const double d, const double scale)
{
- ASSERT(lower && upper);
- return lower[0] >= upper[0] || lower[1] >= upper[1];
+ double dbl = d;
+ union { int64_t i; double d; } ucast;
+ ClipperLib::cInt i;
+ ASSERT(scale > 0);
+
+ ucast.d = 1 + fabs(d / scale);
+ i = (ucast.i & 0x000FFFFFFFFFFFFF) >> 1;
+ return dbl < 0 ? -i : i;
}
-static int
-aabb_intersect
- (const double lower0[2],
- const double upper0[2],
- const double lower1[2],
- const double upper1[2])
+static FINLINE double
+cInt_to_double(const ClipperLib::cInt i, const double scale)
{
- ASSERT(lower0 && upper0 && lower1 && upper1);
- ASSERT(!aabb_is_degenerated(lower0, upper0));
- ASSERT(!aabb_is_degenerated(lower1, upper1));
- return lower0[0] < upper1[0] && lower0[1] < upper1[1]
- && lower1[0] < upper0[0] && lower1[1] < upper0[1];
-}
+ double dbl;
+ union { int64_t i; double d; } ucast;
+ assert(scale > 0);
-static int
-intersect_edges
- (double edge0[2][2],
- double edge1[2][2],
- struct hit* hit)
-{
- double org0[2], org1[2];
- double dir0[2], dir1[2];
- double tmp[2];
- double a, b;
- int i;
-
- /* Express the edges as org<0|1> + t<0|1>*dir<0|1> */
- d2_set(org0, edge0[0]);
- d2_set(org1, edge1[0]);
- d2_sub(dir0, edge0[1], edge0[0]);
- d2_sub(dir1, edge1[1], edge1[0]);
-
- /* Solve org0 + t0*dir0 = org1 + t1*dir1
- * (org0 + t0*dir0) x dir1 = (org1 + t1*dir1) x dir1
- * org0 x dir1 + t0*(dir0 x dir1) = org1 x dir1
- * t0 = (org1 - org0) x dir1 / (dir0 x dir1) */
- d2_sub(tmp, org1, org0);
- b = d2_cross(dir0, dir1);
- if(b == 0) return 0; /* Edges are colinear => i.e. no intersection */
- a = d2_cross(tmp, dir1);
- hit->t0 = a / b;
-
- /* Compute the hit position */
- d2_muld(hit->pos, dir0, hit->t0);
- d2_add(hit->pos, org0, hit->pos);
-
- /* Compute the paremtric hit coordinate on the edge1 */
- i = dir1[0] != 0 ? 0 : 1;
- hit->t1 = (hit->pos[i] - org1[i]) / dir1[i];
-
- /* Ensure that the hit lie in the edge boundaries */
- if(hit->t0 < 0.0 || hit->t0 > 1.0 || hit->t1 < 0.0 || hit->t1 > 1.0)
- return 0;
-
-#ifndef NDEBUG
- d2_muld(tmp, dir1, hit->t1);
- d2_add(tmp, org1, tmp);
- ASSERT(d2_eq_eps(hit->pos, tmp, 1.e-6));
-#endif
- return 1;
+ ucast.i = 0x3FF0000000000000 | (llabs(i) << 1);
+ dbl = (ucast.d - 1) * scale;
+ return i < 0 ? -dbl : dbl;
}
-static size_t
-vertex_get_index
- (const struct vertex* v,
- struct darray_double* coords,
- struct htable_vertex* vertices)
+static INLINE int
+aabb_is_degenerated(const double lower[2], const double upper[2])
{
- size_t* pivertex;
- size_t ivertex;
- struct vertex key;
-
- ASSERT(v && coords && vertices);
-
- /* Dirty trick. TODO comment this, or better, replace this! */
- key.pos[0] = (float)v->pos[0];
- key.pos[1] = (float)v->pos[1];
-
- /* Retrieve the index of this vertex into the vertex buffer */
- pivertex = htable_vertex_find(vertices, v);
- if(pivertex) {
- ivertex = *pivertex;
- } else {
-
- res_T res = RES_OK;
- ivertex = darray_double_size_get(coords);
- res = darray_double_resize(coords, ivertex + 2/*#coords per vertex*/);
- if(res != RES_OK) FATAL("Not enough memory\n");
- d2_set(darray_double_data_get(coords) + ivertex, v->pos);
-
- ivertex /= 2/*#coords per vertex*/;
- res = htable_vertex_set(vertices, &key, &ivertex);
- if(res != RES_OK) FATAL("Not enough memory\n");
- }
- return ivertex;
+ ASSERT(lower && upper);
+ return lower[0] >= upper[0] || lower[1] >= upper[1];
}
static INLINE void
@@ -230,354 +135,130 @@ error:
}
static res_T
-poly_setup_nodes(struct poly* poly, struct darray_node* nodes)
+register_vertex
+ (const double pos[2],
+ struct darray_double* coords,
+ struct darray_size_t* indices,
+ struct htable_vertex* vertices)
{
- size_t nverts;
- size_t ivert;
+ struct vertex v;
+ size_t* pid, id;
res_T res = RES_OK;
- ASSERT(poly && nodes);
-
- darray_node_clear(nodes);
- nverts = darray_double_size_get(&poly->coords)/2/*#coords*/;
+ ASSERT(pos && coords && indices && vertices);
- res = darray_node_resize(nodes, nverts);
- if(res != RES_OK) return res;
-
- FOR_EACH(ivert, 0, nverts) {
- struct node* node = darray_node_data_get(nodes) + ivert;
- node->next = (ivert == nverts - 1) ? 0 : ivert + 1;
- node->prev = (ivert == 0) ? nverts - 1 : ivert - 1;
- node->link = SIZE_MAX;
- node->id = ivert;
- node->t = -1.0;
- }
+ d2_set(v.pos, pos);
- return RES_OK;
-}
+ /* FIXME dirty hack */
+ v.pos[0] = (float)v.pos[0];
+ v.pos[1] = (float)v.pos[1];
-static void
-triangle_compute_aabb
- (const size_t triangle[3],
- const struct cpr_mesh* mesh,
- double lower[2],
- double upper[2])
-{
- double pos[2];
- ASSERT(triangle && mesh && lower && upper);
- CPR(mesh_get_position(mesh, triangle[0], pos));
- d2_set(lower, pos), d2_set(upper, pos);
- CPR(mesh_get_position(mesh, triangle[1], pos));
- d2_min(lower, lower, pos), d2_max(upper, upper, pos);
- CPR(mesh_get_position(mesh, triangle[2], pos));
- d2_min(lower, lower, pos), d2_max(upper, upper, pos);
-}
+ pid = htable_vertex_find(vertices, &v);
-static res_T
-triangle_register
- (const size_t triangle[3],
- const struct cpr_mesh* mesh,
- struct darray_size_t* indices,
- struct darray_double* coords,
- struct htable_vertex* vertices)
-{
- int i;
- res_T res = RES_OK;
- ASSERT(triangle && mesh && indices && coords && vertices);
+ if(pid) {
+ id = *pid;
+ } else {
+ const size_t ivert = darray_double_size_get(coords);
- FOR_EACH(i, 0, 3) {
- struct vertex v;
- size_t id;
+ res = darray_double_resize(coords, ivert+2/*#coords*/);
+ if(res != RES_OK) goto error;
+ d2_set(darray_double_data_get(coords)+ivert, pos);
- CPR(mesh_get_position(mesh, triangle[i], v.pos));
- id = vertex_get_index(&v, coords, vertices);
- res = darray_size_t_push_back(indices, &id);
+ id = ivert / 2;
+ res = htable_vertex_set(vertices, &v, &id);
if(res != RES_OK) goto error;
}
+
+ res = darray_size_t_push_back(indices, &id);
+ if(res != RES_OK) goto error;
+
exit:
return res;
error:
- /* Pop the already registered indices */
- darray_size_t_resize(indices, darray_size_t_size_get(indices) - (size_t)i);
goto exit;
}
static res_T
-triangle_setup_nodes(const size_t triangle[3], struct darray_node* nodes)
+register_paths
+ (const ClipperLib::Paths& paths,
+ struct darray_double* coords, /* Vertex buffer */
+ struct darray_size_t* indices, /* Index buffer */
+ struct htable_vertex* vertices, /* Map a vertex to its index */
+ const double extend[2], /* Scale to apply to the cInt coordinates */
+ struct polygon* polygon, /* Use to triangulate the clipped polygons */
+ struct darray_double* scratch) /* Temporary container */
{
size_t ivert;
+ size_t ipath;
res_T res = RES_OK;
- ASSERT(triangle && nodes);
-
- darray_node_clear(nodes);
-
- res = darray_node_resize(nodes, 3);
- if(res != RES_OK) return res;
-
- FOR_EACH(ivert, 0, 3) {
- struct node* node = darray_node_data_get(nodes) + ivert;
- node->next = ivert + 1;
- node->prev = ivert - 1;
- node->link = SIZE_MAX;
- node->id = triangle[ivert];
- node->t = -1.0;
- }
- darray_node_data_get(nodes)[0].prev = 2;
- darray_node_data_get(nodes)[2].next = 0;
- return RES_OK;
-}
-
-static res_T
-setup_intersection_nodes
- (struct darray_node* nodes0,
- struct darray_double* coords0,
- struct darray_node* nodes1,
- struct darray_double* coords1)
-{
- size_t inode0, nnodes0;
- size_t inode1, nnodes1;
- res_T res = RES_OK;
- ASSERT(nodes0 && coords0 && nodes1 && coords1);
-
- nnodes0 = darray_node_size_get(nodes0);
- nnodes1 = darray_node_size_get(nodes1);
-
- #define POS(Array) darray_double_data_get(Array)
- #define NODES(Array) darray_node_data_get(Array)
- FOR_EACH(inode0, 0, nnodes0) {
- double edge0[2][2];
-
- /* Fetch the coordinates of the edge0 */
- d2_set(edge0[0], POS(coords0) + NODES(nodes0)[inode0].id*2);
- d2_set(edge0[1], POS(coords0) + NODES(nodes0)[(inode0+1)%nnodes0].id*2);
-
- FOR_EACH(inode1, 0, nnodes1) {
- struct node* node;
- struct hit hit;
- double edge1[2][2];
- size_t ihit_node0, ihit_node1;
- size_t ihit_pos0, ihit_pos1;
-
- /* Fetch the coordinates of the edge1 */
- d2_set(edge1[0], POS(coords1) + NODES(nodes1)[inode1].id*2);
- d2_set(edge1[1], POS(coords1) + NODES(nodes1)[(inode1+1)%nnodes1].id*2);
-
- /* Find the edge intersection */
- if(!intersect_edges(edge0, edge1, &hit)) continue;
-
- /* Allocate the hit node into the node list 0 */
- ihit_node0 = darray_node_size_get(nodes0);
- res = darray_node_resize(nodes0, ihit_node0 + 1);
- if(res != RES_OK) goto error;
-
- /* Allocate the hit node into the node list 1 */
- ihit_node1 = darray_node_size_get(nodes1);
- res = darray_node_resize(nodes1, ihit_node1 + 1);
- if(res != RES_OK) goto error;
-
- /* Register the hit position into the coords0 */
- ihit_pos0 = darray_double_size_get(coords0);
- res = darray_double_resize(coords0, ihit_pos0 + 2);
- if(res != RES_OK) goto error;
- d2_set(POS(coords0) + ihit_pos0, hit.pos);
- ihit_pos0 /= 2/* #coords per vertex */;
-
- /* Register the hit position into the coords1 */
- ihit_pos1 = darray_double_size_get(coords1);
- res = darray_double_resize(coords1, ihit_pos1 + 2);
+ ASSERT(coords && indices && vertices && scratch);
+
+ FOR_EACH(ipath, 0, paths.size()) {
+ if(paths[ipath].size() == 3) {
+ FOR_EACH(ivert, 0, 3) {
+ double pos[2];
+ pos[0] = cInt_to_double(paths[ipath][ivert].X, extend[0]);
+ pos[1] = cInt_to_double(paths[ipath][ivert].Y, extend[1]);
+ res = register_vertex(pos, coords, indices, vertices);
+ if(res != RES_OK) goto error;
+ }
+ } else {
+ /* Triangulate the clipped primitive */
+ const uint32_t* ids;
+ uint32_t nids;
+
+ /* Define the contour of the polygon to triangulate */
+ POLYGON(clear(polygon));
+ darray_double_clear(scratch);
+ FOR_EACH(ivert, 0, paths[ipath].size()) {
+ float fpos[3] = {0.f, 0.f, 0.f};
+ double pos[2];
+
+ pos[0] = cInt_to_double(paths[ipath][ivert].X, extend[0]);
+ pos[1] = cInt_to_double(paths[ipath][ivert].Y, extend[1]);
+
+ fpos[0] = (float)pos[0], fpos[1] = (float)pos[1];
+ res = polygon_vertex_add(polygon, fpos);
+ if(res != RES_OK) goto error;
+ }
+ res = polygon_triangulate(polygon, &ids, &nids);
if(res != RES_OK) goto error;
- d2_set(POS(coords1) + ihit_pos1, hit.pos);
- ihit_pos1 /= 2/* #coords per vertex */;
- /* Insert the hit node into the node list 0 */
- node = NODES(nodes0) + NODES(nodes0)[inode0].next;
- while(node->link != SIZE_MAX && node->t < hit.t0) {
- node = NODES(nodes0) + node->next;
- }
- NODES(nodes0)[ihit_node0].next = (size_t)(node - NODES(nodes0));
- NODES(nodes0)[ihit_node0].prev = node->prev;
- NODES(nodes0)[ihit_node0].link = ihit_node1;
- NODES(nodes0)[ihit_node0].id = ihit_pos0;
- NODES(nodes0)[ihit_node0].t = hit.t0;
- NODES(nodes0)[node->prev].next = ihit_node0;
- node->prev = ihit_node0;
-
- /* Inser the hit node into the node list 1 */
- node = NODES(nodes1) + NODES(nodes1)[inode1].next;
- while(node->link != SIZE_MAX && node->t < hit.t1) {
- node = NODES(nodes1) + node->next;
+ FOR_EACH(ivert, 0, nids) {
+ float fpos[3];
+ double pos[2];
+ POLYGON(vertex_get(polygon, ids[ivert], fpos));
+ pos[0] = (float)fpos[0];
+ pos[1] = (float)fpos[1];
+ res = register_vertex(pos, coords, indices, vertices);
+ if(res != RES_OK) goto error;
}
- NODES(nodes1)[ihit_node1].next = (size_t)(node - NODES(nodes1));
- NODES(nodes1)[ihit_node1].prev = node->prev;
- NODES(nodes1)[ihit_node1].link = ihit_node0;
- NODES(nodes1)[ihit_node1].id = ihit_pos1;
- NODES(nodes1)[ihit_node1].t = hit.t1;
- NODES(nodes1)[node->prev].next = ihit_node1;
- node->prev = ihit_node1;
}
}
- #undef POS
- #undef NODES
-
exit:
return res;
error:
goto exit;
}
-/* Define if the vertices are inside the polygon and slightly move them if they
- * roughly lie onto a polygon edge */
static void
-preprocess_vertices
- (struct darray_double* coords,
- const struct darray_node* poly_nodes,
- const struct darray_double* poly_coords,
- char* is_inside)
-{
- size_t ivert, nverts;
- size_t iedge, nedges;
- ASSERT(coords && poly_nodes && poly_coords && is_inside);
-
- nverts = darray_double_size_get(coords) / 2/*#coords per vertex*/;
- nedges = darray_node_size_get(poly_nodes);
-
- FOR_EACH(ivert, 0, nverts) {
- double* v = darray_double_data_get(coords) + ivert*2;
- char inside = 1;
- for(iedge = 0; inside && iedge < nedges; ++iedge) {
- const struct node* node0 = darray_node_cdata_get(poly_nodes) + iedge;
- const struct node* node1 = darray_node_cdata_get(poly_nodes) + node0->next;
- const double* c0 = darray_double_cdata_get(poly_coords) + node0->id*2;
- const double* c1 = darray_double_cdata_get(poly_coords) + node1->id*2;
- double e0[2], e1[2];
- double area2;
- d2_sub(e0, c0, v);
- d2_sub(e1, c1, v);
- area2 = d2_cross(e1, e0);
-
- /* The area of the c0, c1, v triangle is roughly null => v is near of the
- * c0, c1 edge. Slightly move the v vertex to avoid the intersection
- * between the clip edge and the candidate vertex */
- if(eq_eps(area2, 0, 2.e-6)) {
- const double dx = c1[0] - c0[0];
- const double dy = c1[1] - c0[1];
- double N[2];
- N[0] = -dy, N[1] = dx;
- d2_normalize(N, N);
-
- d2_add(v, v, d2_muld(N, N, 1.e-6));
- d2_sub(e0, c0, v);
- d2_sub(e1, c1, v);
- area2 = d2_cross(e1, e0);
- ASSERT(!eq_eps(area2, 0, 2.e-6));
- }
- inside = inside && (area2 < 0);
- }
- is_inside[ivert] = inside;
- }
-}
-
-static res_T
-clip
- (const struct cpr_mesh* mesh,
- struct contour* cand, /* Contour of the candidate polygon */
- struct contour* clip, /* Contour of the clip polygon */
- const char* is_inside, /* Define if candidate vertex is inside the clip polygon */
- struct polygon* polygon, /* Use to triangulate the clipped polygons */
- struct darray_size_t* scratch, /* Temporary buffer */
- struct darray_size_t* indices, /* Index buffer of the clipped polygons */
- struct darray_double* coords, /* Vertex buffer of the clipped polygons */
- struct htable_vertex* vertices) /* Map a vertex pos to its index */
+mesh_compute_aabb(const struct cpr_mesh* mesh, double lower[2], double upper[2])
{
- enum { CAND, CLIP };
- size_t icand_node;
+ size_t itri, ntris;
- const struct contour* contours[2];
- res_T res = RES_OK;
- ASSERT(mesh && cand && clip && is_inside && polygon && scratch);
- ASSERT(indices && coords && vertices);
-
- contours[CAND] = cand;
- contours[CLIP] = clip;
-
- /* TODO iterate over the intersection nodes only */
- FOR_EACH(icand_node, 0, cand->nnodes) {
- const size_t* scratch_data;
- size_t icontour = CAND;
- size_t i, n;
- const struct node* n0 = contours[CAND]->nodes + icand_node;
- const struct node* n1 = contours[CAND]->nodes + n0->next;
- const struct node* node_start;
- const struct node* node;
- const uint32_t* ids;
- uint32_t nids;
-
- if(n0->link == SIZE_MAX || n1->link != SIZE_MAX || is_inside[n1->id])
- continue;
-
- /* Clip the candidate polygon */
- darray_size_t_clear(scratch);
- node_start = node = n1;
- do {
- struct vertex v;
- size_t ivertex;
-
- /* Fetch the node position */
- d2_set(v.pos, contours[icontour]->coords + node->id*2);
-
- /* Retrieve the index of this vertex into the vertex buffer */
- ivertex = vertex_get_index(&v, coords, vertices);
-
- /* Add the vertex index to the clipped polygon contour */
- res = darray_size_t_push_back(scratch, &ivertex);
- if(res != RES_OK) goto error;
+ CPR(mesh_get_triangles_count(mesh, &ntris));
+ d2_splat(lower, DBL_MAX);
+ d2_splat(upper, DBL_MIN);
- node = contours[icontour]->nodes + node->next;
- if(node->link != SIZE_MAX) {
- icontour = !icontour;
- node = contours[icontour]->nodes + node->link;
- }
- } while(node != node_start);
-
- /* Setup the clipped polygon to triangulate */
- n = darray_size_t_size_get(scratch);
- scratch_data = darray_size_t_cdata_get(scratch);
- POLYGON(clear(polygon));
- FOR_EACH(i, 0, n) {
- float posf[3] = { 0.f, 0.f, 0.f };
+ FOR_EACH(itri, 0, ntris) {
+ size_t ids[3], ivert;
+ CPR(mesh_get_indices(mesh, itri, ids));
+ FOR_EACH(ivert, 0, 3) {
double pos[2];
- d2_set(pos, darray_double_data_get(coords) + scratch_data[i]*2);
-
- posf[0] = (float)pos[0], posf[1] = (float)pos[1];
- res = polygon_vertex_add(polygon, posf);
- if(res != RES_OK) goto error;
- }
-
- /* Triangulate the polygon */
- res = polygon_triangulate(polygon, &ids, &nids);
- if(res != RES_OK) goto error;
-
- /* Register the created triangles */
- FOR_EACH(i, 0, nids) {
- float posf[3];
- struct vertex v;
- size_t* pivertex;
- size_t ivertex;
- POLYGON(vertex_get(polygon, ids[i], posf));
- v.pos[0] = posf[0], v.pos[1] = posf[1];
-
- pivertex = htable_vertex_find(vertices, &v);
- ivertex = *pivertex;
- res = darray_size_t_push_back(indices, &ivertex);
- if(res != RES_OK) goto error;
+ CPR(mesh_get_position(mesh, ids[ivert], pos));
+ d2_min(lower, lower, pos);
+ d2_max(upper, upper, pos);
}
}
-
-exit:
- return res;
-error:
- darray_size_t_clear(indices);
- darray_double_clear(coords);
- goto exit;
}
static void
@@ -607,7 +288,8 @@ cpr_mesh_create(struct mem_allocator* mem_allocator, struct cpr_mesh** out_mesh)
}
allocator = mem_allocator ? mem_allocator : &mem_default_allocator;
- mesh = MEM_CALLOC(allocator, 1, sizeof(struct cpr_mesh));
+ mesh = (struct cpr_mesh*)
+ MEM_CALLOC(allocator, 1, sizeof(struct cpr_mesh));
if(!mesh) {
res = RES_MEM_ERR;
goto error;
@@ -745,136 +427,97 @@ cpr_mesh_get_position
res_T
cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
{
- struct darray_node poly_nodes;
- struct darray_node cand_nodes; /* Candidate */
- struct darray_node clip_nodes;
- struct darray_char is_inside;
- struct darray_size_t indices;
- struct darray_double coords;
- struct darray_size_t scratch;
- struct htable_vertex vertices;
+ double lower[2], upper[2], extend[2];
struct poly poly;
- struct polygon* polygon = NULL; /* Use to triangulate the clipped polygons */
- size_t itri, ntris, nverts;
+ struct polygon* polygon = NULL; /* Use to triangulate clipped polygons */
+ struct darray_double polycoords; /* Clipped polygon to triangulate */
+ struct darray_double coords; /* Coordinates of the clipped mesh */
+ struct darray_size_t indices; /* Indices of the clipped mesh */
+ struct htable_vertex vertices; /* Map a coordinate to its index */
+ ClipperLib::Clipper clipper;
+ ClipperLib::Paths output;
+ ClipperLib::Path cand_path;
+ ClipperLib::Path clip_path;
+ size_t ivert, nverts;
+ size_t itri, ntris;
+
res_T res = RES_OK;
- /* Directly return an error since the temporary data structures are still not
- * initialized and thus could not be released by the exit block. */
if(!mesh || !poly_desc) return RES_BAD_ARG;
- /* Initialised the temporary data structures */
- darray_node_init(mesh->allocator, &poly_nodes);
- darray_node_init(mesh->allocator, &cand_nodes);
- darray_node_init(mesh->allocator, &clip_nodes);
- darray_char_init(mesh->allocator, &is_inside);
- darray_size_t_init(mesh->allocator, &indices);
+ darray_double_init(mesh->allocator, &polycoords);
darray_double_init(mesh->allocator, &coords);
- darray_size_t_init(mesh->allocator, &scratch);
+ darray_size_t_init(mesh->allocator, &indices);
htable_vertex_init(mesh->allocator, &vertices);
- poly_init(mesh->allocator, &poly);
- /* Create the polygon object used to triangulated the clipped primitives */
- res = polygon_create(NULL, &polygon);
- if(res != RES_OK) goto error;
-
- /* Setup the clip polygon */
+ poly_init(mesh->allocator, &poly);
res = poly_setup(&poly, poly_desc);
if(res != RES_OK) goto error;
-
- /* Degenerated polygon => nothing to clip.
- * TODO For CW polygon all the triangles must be clipped */
if(aabb_is_degenerated(poly.lower, poly.upper)) goto exit;
- /* Build the polygon node list */
- res = poly_setup_nodes(&poly, &poly_nodes);
- if(res != RES_OK) goto error;
+ mesh_compute_aabb(mesh, lower, upper);
+ if(aabb_is_degenerated(lower, upper)) goto exit;
- /* Preprocess the mesh vertices, i.e. define which mesh vertices are inside
- * the polygon and avoid that a mesh vertex lies onto a polygon edge */
- CPR(mesh_get_vertices_count(mesh, &nverts));
- res = darray_char_resize(&is_inside, nverts);
+ /* Compute the overall aabb of the candidate and the clip polygon */
+ d2_min(lower, lower, poly.lower);
+ d2_max(upper, upper, poly.upper);
+ d2_sub(extend, upper, lower);
+
+ /* Setup the clip path */
+ nverts = darray_double_size_get(&poly.coords) / 2/*#coords per vertex*/;
+ FOR_EACH(ivert, 0, nverts) {
+ const double* v = darray_double_cdata_get(&poly.coords) + ivert*2;
+ ClipperLib::IntPoint pt;
+ pt.X = double_to_cInt(v[0], extend[0]);
+ pt.Y = double_to_cInt(v[1], extend[1]);
+ clip_path.push_back(pt);
+ }
+
+ /* Create the polygon structure used to triangulate the clipped polygons */
+ res = polygon_create(mesh->allocator, &polygon);
if(res != RES_OK) goto error;
- preprocess_vertices(&mesh->coords, &poly_nodes, &poly.coords,
- darray_char_data_get(&is_inside));
CPR(mesh_get_triangles_count(mesh, &ntris));
FOR_EACH(itri, 0, ntris) {
- double lower[2], upper[2];
size_t ids[3];
- /* Fetch the current triangle */
CPR(mesh_get_indices(mesh, itri, ids));
- triangle_compute_aabb(ids, mesh, lower, upper);
- if(aabb_is_degenerated(lower, upper)) continue; /* Skip degenerated prim */
- if(!aabb_intersect(lower, upper, poly.lower, poly.upper)) {
- /* TODO Discard the triangle if the clip polygon is CW oredered */
- res = triangle_register(ids, mesh, &indices, &coords, &vertices);
- if(res != RES_OK) goto error;
- continue;
+ /* Setup the candidate path */
+ cand_path.clear();
+ FOR_EACH(ivert, 0, 3) {
+ double pos[2];
+ ClipperLib::IntPoint pt;
+ CPR(mesh_get_position(mesh, ids[ivert], pos));
+ pt.X = double_to_cInt(pos[0], extend[0]);
+ pt.Y = double_to_cInt(pos[1], extend[1]);
+ cand_path.push_back(pt);
}
- /* Build the node list of the mesh triangle */
- res = triangle_setup_nodes(ids, &cand_nodes);
- if(res != RES_OK) goto error;
-
- /* Make a copy of the polygon node list. This is necessary since the node
- * list is going to be updated with respect to the candidate/polygon
- * intersections */
- res = darray_node_copy(&clip_nodes, &poly_nodes);
- if(res != RES_OK) goto error;
+ /* Clip the polygon */
+ clipper.Clear();
+ clipper.AddPath(cand_path, ClipperLib::ptSubject, 1);
+ clipper.AddPath(clip_path, ClipperLib::ptClip, 1);
+ clipper.Execute(ClipperLib::ctDifference, output);
- /* Insert into the candidate and clip node lists the intersection nodes */
- res = setup_intersection_nodes
- (&cand_nodes, &mesh->coords, &clip_nodes, &poly.coords);
+ /* Register the polygons */
+ res = register_paths
+ (output, &coords, &indices, &vertices, extend, polygon, &polycoords);
if(res != RES_OK) goto error;
-
-#if 1
- if(darray_node_size_get(&cand_nodes) == 3) { /* No intersection */
- /* If the first index is not inside */
- if(!darray_char_data_get(&is_inside)[ids[0]]) { /* FIXME */
- res = triangle_register(ids, mesh, &indices, &coords, &vertices);
- if(res != RES_OK) goto error;
- darray_size_t_push_back(&indices, ids + 2);
- }
- } else
-#endif
- {
- struct contour cand_contour;
- struct contour clip_contour;
-
- cand_contour.nodes = darray_node_cdata_get(&cand_nodes);
- cand_contour.coords = darray_double_cdata_get(&mesh->coords);
- cand_contour.nnodes = darray_node_size_get(&cand_nodes);
-
- clip_contour.nodes = darray_node_cdata_get(&clip_nodes);
- clip_contour.coords = darray_double_cdata_get(&poly.coords);
- clip_contour.nnodes = darray_node_size_get(&clip_nodes);
-
- clip(mesh, &cand_contour, &clip_contour,
- darray_char_cdata_get(&is_inside), polygon, &scratch, &indices,
- &coords, &vertices);
- }
}
- res = darray_size_t_copy_and_clear(&mesh->indices, &indices);
- if(res != RES_OK) goto error;
res = darray_double_copy_and_clear(&mesh->coords, &coords);
- if(res != RES_OK) goto error;
+ if(res != RES_OK) FATAL("Unexpected error.\n");
+ res = darray_size_t_copy_and_clear(&mesh->indices, &indices);
+ if(res != RES_OK) FATAL("Unexpected error.\n");
exit:
- darray_node_release(&poly_nodes);
- darray_node_release(&cand_nodes);
- darray_node_release(&clip_nodes);
- darray_char_release(&is_inside);
- darray_size_t_release(&indices);
+ if(polygon) POLYGON(ref_put(polygon));
darray_double_release(&coords);
- darray_size_t_release(&scratch);
+ darray_size_t_release(&indices);
htable_vertex_release(&vertices);
poly_release(&poly);
- if(polygon) POLYGON(ref_put(polygon));
return res;
-
error:
goto exit;
}
diff --git a/src/test_cpr_clip.c b/src/test_cpr_clip.c
@@ -82,8 +82,6 @@ test_triangle(struct cpr_mesh* mesh)
CHECK(cpr_mesh_get_triangles_count(mesh, &ntris), RES_OK);
CHECK(ntris, 3);
-
- dump_obj(stdout, mesh);
}
static void
@@ -173,7 +171,7 @@ main(int argc, char** argv)
CHECK(cpr_mesh_create(&allocator, &mesh), RES_OK);
- /*test_triangle(mesh);*/
+ test_triangle(mesh);
test_disk(mesh);
CHECK(cpr_mesh_ref_put(mesh), RES_OK);
