commit b095cf8a3d4f96ef18902843759f789eecef5164
parent d85b80b8c7564388486a732caef0e16c93f36ea6
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 24 Aug 2016 11:36:09 +0200
Finalise the 1st version of the clip function
Diffstat:
5 files changed, 123 insertions(+), 57 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -69,10 +69,14 @@ rcmake_setup_devel(cpr CPR ${VERSION} cpr_version.h)
# Define tests
################################################################################
if(NOT NO_TEST)
- add_executable(test_cpr_mesh ${CPR_SOURCE_DIR}/test_cpr_mesh.c)
- target_link_libraries(test_cpr_mesh cpr)
- add_test(test_cpr_mesh test_cpr_mesh)
- rcmake_set_test_runtime_dirs(test_cpr_mesh _runtime_dirs)
+ function(new_test _name)
+ add_executable(${_name} ${CPR_SOURCE_DIR}/${_name}.c)
+ target_link_libraries(${_name} cpr RSys)
+ add_test(${_name} ${_name})
+ rcmake_set_test_runtime_dirs(${_name} _runtime_dirs)
+ endfunction()
+ new_test(test_cpr_clip)
+ new_test(test_cpr_mesh)
endif()
################################################################################
diff --git a/src/cpr.h b/src/cpr.h
@@ -41,6 +41,9 @@ struct cpr_polygon {
void* context;
};
+#define CPR_POLYGON_NULL__ { NULL, 0, NULL }
+static const struct cpr_polygon CPR_POLYGON_NULL = CPR_POLYGON_NULL__;
+
/* Opaque 2 dimensionnal mesh data type */
struct cpr_mesh;
diff --git a/src/cpr_mesh.c b/src/cpr_mesh.c
@@ -15,6 +15,8 @@
#include "cpr.h"
+#include <polygon.h>
+
#include <rsys/double2.h>
#include <rsys/dynamic_array_double.h>
#include <rsys/dynamic_array_size_t.h>
@@ -265,7 +267,7 @@ setup_intersection_nodes
d2_set(POS(coords0) + ihit_pos, hit.pos);
ihit_pos /= 2/* #coords per vertex */;
- /*
+ /*
* Note that the hit position is not registered in the coords1 array
*/
@@ -338,36 +340,44 @@ vertices_setup_inside_poly_flag
static res_T
clip
- (const struct darray_node* cand_nodes,
- const struct darray_node* clip_nodes,
- const char* is_inside,
- struct darray_size_t* output)
+ (const struct cpr_mesh* mesh,
+ const struct darray_node* cand_nodes, /* Candidate polygon node list */
+ const struct darray_node* clip_nodes, /* Clipping polygon node list */
+ 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* output) /* Index of the triangulated vertices */
{
enum { CAND, CLIP };
size_t icand_node, ncand_nodes;
const struct node* node_lists[2];
res_T res = RES_OK;
- ASSERT(cand_nodes && clip_nodes && is_inside && output);
+ ASSERT(cand_nodes && clip_nodes && is_inside && polygon && scratch && output);
ncand_nodes = darray_node_size_get(cand_nodes);
node_lists[CAND] = darray_node_cdata_get(cand_nodes);
node_lists[CLIP] = darray_node_cdata_get(clip_nodes);
+ /* TODO iterate over the intersection nodes only */
FOR_EACH(icand_node, 0, ncand_nodes) {
+ const size_t* scratch_data;
size_t ilist = CAND;
+ size_t i, n;
const struct node* n0 = node_lists[CAND] + icand_node;
const struct node* n1 = node_lists[CAND] + node_lists[CAND][icand_node].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])
+ if(n0->link == SIZE_MAX || n1->link != SIZE_MAX || is_inside[n1->id])
continue;
- darray_size_t_clear(output);
+ /* Clip the candidate polygon */
+ darray_size_t_clear(scratch);
node_start = node = n1;
-
do {
- res = darray_size_t_push_back(output, &node->id);
+ res = darray_size_t_push_back(scratch, &node->id);
if(res != RES_OK) goto error;
node = node_lists[ilist] + node->next;
@@ -376,6 +386,30 @@ clip
node = node_lists[ilist] + 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 };
+ double pos[2];
+ CPR(mesh_get_position(mesh, scratch_data[i], pos));
+
+ 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) {
+ res = darray_size_t_push_back(output, scratch_data + ids[i]);
+ if(res != RES_OK) goto error;
+ }
}
exit:
@@ -548,29 +582,42 @@ cpr_mesh_get_position
}
res_T
-cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* polygon)
+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_node clip_nodes;
struct darray_char is_inside;
+ struct darray_size_t indices;
+ struct darray_size_t scratch;
struct poly poly;
+ struct polygon* polygon = NULL; /* Use to triangulate the clipped polygons */
size_t itri, ntris, nverts;
res_T res = RES_OK;
+ if(!mesh) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
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_size_t_init(mesh->allocator, &scratch);
poly_init(mesh->allocator, &poly);
- if(!mesh || !polygon) {
+ if(!poly_desc) {
res = RES_BAD_ARG;
goto error;
}
- /* Setup the polygon */
- res = poly_setup(&poly, polygon);
+ res = polygon_create(NULL, &polygon);
+ if(res != RES_OK) goto error;
+
+ /* Setup the clip polygon */
+ res = poly_setup(&poly, poly_desc);
if(res != RES_OK) goto error;
res = poly_setup_nodes(&poly, &poly_nodes);
if(res != RES_OK) goto error;
@@ -596,14 +643,26 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* polygon)
res = setup_intersection_nodes
(&cand_nodes, &mesh->coords, &poly_nodes, &poly.coords);
if(res != RES_OK) goto error;
+
+ darray_size_t_clear(&indices);
+ clip(mesh, &cand_nodes, &poly_nodes, darray_char_cdata_get(&is_inside),
+ polygon, &scratch, &indices);
}
+ res = darray_size_t_copy_and_release(&mesh->indices, &indices);
+ if(res != RES_OK) goto error;
+
exit:
- darray_node_release(&poly_nodes);
- darray_node_release(&cand_nodes);
- darray_node_release(&clip_nodes);
- darray_char_release(&is_inside);
- poly_release(&poly);
+ if(mesh) {
+ 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);
+ darray_size_t_release(&scratch);
+ poly_release(&poly);
+ }
+ if(polygon) POLYGON(ref_put(polygon));
return res;
error:
diff --git a/src/test_cpr_mesh.c b/src/test_cpr_mesh.c
@@ -16,38 +16,6 @@
#include "cpr.h"
#include "test_cpr_utils.h"
-struct context {
- const double* coords;
- size_t nverts;
- const size_t* indices;
- size_t ntris;
-};
-
-static void
-get_pos(const size_t ivert, double pos[2], void* context)
-{
- const struct context* ctx = context;
- NCHECK(pos, NULL);
- NCHECK(context, NULL);
- NCHECK(ctx->coords, NULL);
- CHECK(ivert < ctx->nverts, 1);
- pos[0] = ctx->coords[ivert*2 + 0];
- pos[1] = ctx->coords[ivert*2 + 1];
-}
-
-static void
-get_ids(const size_t itri, size_t ids[3], void* context)
-{
- const struct context* ctx = context;
- NCHECK(ids, NULL);
- NCHECK(context, NULL);
- NCHECK(ctx->indices, NULL);
- CHECK(itri < ctx->ntris, 1);
- ids[0] = ctx->indices[itri*3 + 0];
- ids[1] = ctx->indices[itri*3 + 1];
- ids[2] = ctx->indices[itri*3 + 2];
-}
-
int
main(int argc, char** argv)
{
@@ -79,7 +47,7 @@ main(int argc, char** argv)
double pos[2];
size_t i, n;
struct mem_allocator allocator;
- struct context ctx;
+ struct mesh_context ctx;
struct cpr_mesh* mesh;
(void)argc, (void)argv;
diff --git a/src/test_cpr_utils.h b/src/test_cpr_utils.h
@@ -19,6 +19,38 @@
#include <rsys/mem_allocator.h>
#include <stdio.h>
+struct mesh_context {
+ const double* coords;
+ size_t nverts;
+ const size_t* indices;
+ size_t ntris;
+};
+
+static void
+get_pos(const size_t ivert, double pos[2], void* context)
+{
+ const struct mesh_context* ctx = context;
+ NCHECK(pos, NULL);
+ NCHECK(context, NULL);
+ NCHECK(ctx->coords, NULL);
+ CHECK(ivert < ctx->nverts, 1);
+ pos[0] = ctx->coords[ivert*2 + 0];
+ pos[1] = ctx->coords[ivert*2 + 1];
+}
+
+static void
+get_ids(const size_t itri, size_t ids[3], void* context)
+{
+ const struct mesh_context* ctx = context;
+ NCHECK(ids, NULL);
+ NCHECK(context, NULL);
+ NCHECK(ctx->indices, NULL);
+ CHECK(itri < ctx->ntris, 1);
+ ids[0] = ctx->indices[itri*3 + 0];
+ ids[1] = ctx->indices[itri*3 + 1];
+ ids[2] = ctx->indices[itri*3 + 2];
+}
+
static void
check_memory_allocator(struct mem_allocator* allocator)
{
