commit 0838ad30be0c6ef32b3b849cd1dc87d78b2aafbf
parent b095cf8a3d4f96ef18902843759f789eecef5164
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 24 Aug 2016 18:01:30 +0200
Fix the clipping algorithm
Change how the vertex/index buffer of the clipped polygons are computed.
Note that the clip algorithm is still bugged when a clip edges intersect
the polygon to clip.
Diffstat:
3 files changed, 345 insertions(+), 47 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -69,9 +69,14 @@ rcmake_setup_devel(cpr CPR ${VERSION} cpr_version.h)
# Define tests
################################################################################
if(NOT NO_TEST)
+
+ if(CMAKE_COMPILER_IS_GNUCC)
+ set(MATH_LIB m)
+ endif()
+
function(new_test _name)
add_executable(${_name} ${CPR_SOURCE_DIR}/${_name}.c)
- target_link_libraries(${_name} cpr RSys)
+ target_link_libraries(${_name} cpr RSys ${MATH_LIB})
add_test(${_name} ${_name})
rcmake_set_test_runtime_dirs(${_name} _runtime_dirs)
endfunction()
diff --git a/src/cpr_mesh.c b/src/cpr_mesh.c
@@ -24,21 +24,24 @@
#include <rsys/mem_allocator.h>
#include <rsys/ref_count.h>
-struct edge {
- size_t v0;
- size_t v1;
+struct contour {
+ const struct node* nodes;
+ const double* coords;
+ size_t nnodes;
};
+struct vertex { double pos[2]; };
+
static INLINE char
-edge_eq(const struct edge* a, const struct edge* b)
+vertex_eq(const struct vertex* a, const struct vertex* b)
{
- return a->v0 == b->v0 && a->v1 == b->v1;
+ return d2_eq_eps(a->pos, b->pos, 0.e-6);
}
-#define HTABLE_NAME edge
+#define HTABLE_NAME vertex
#define HTABLE_DATA size_t /* Index of the firs node */
-#define HTABLE_KEY struct edge
-#define HTABLE_KEY_FUNCTOR_EQ edge_eq
+#define HTABLE_KEY struct vertex
+#define HTABLE_KEY_FUNCTOR_EQ vertex_eq
#include <rsys/hash_table.h>
struct node {
@@ -110,14 +113,51 @@ intersect_edges
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;
+}
- /* Ensure that the hit lie in the edge boundaries */
- return hit->t0 >= 0.0 && hit->t0 <= 1.0 && hit->t1 >= 0.0 && hit->t1 <= 1.0;
+static size_t
+vertex_get_index
+ (const struct vertex* v,
+ struct darray_double* coords,
+ struct htable_vertex* vertices)
+{
+ size_t* pivertex;
+ size_t ivertex;
+ struct vertex key;
+
+ ASSERT(v && coords && vertices);
+
+ /* Dirty trick. TODO comment 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;
}
static INLINE void
@@ -241,7 +281,7 @@ setup_intersection_nodes
struct hit hit;
double edge1[2][2];
size_t ihit_node0, ihit_node1;
- size_t ihit_pos;
+ size_t ihit_pos0, ihit_pos1;
/* Fetch the coordinates of the edge1 */
d2_set(edge1[0], POS(coords1) + NODES(nodes1)[inode1].id*2);
@@ -261,15 +301,18 @@ setup_intersection_nodes
if(res != RES_OK) goto error;
/* Register the hit position into the coords0 */
- ihit_pos = darray_double_size_get(coords0);
- res = darray_double_resize(coords0, ihit_pos + 2);
+ 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_pos, hit.pos);
- ihit_pos /= 2/* #coords per vertex */;
+ d2_set(POS(coords0) + ihit_pos0, hit.pos);
+ ihit_pos0 /= 2/* #coords per vertex */;
- /*
- * Note that the hit position is not registered in the coords1 array
- */
+ /* Register the hit position into the coords1 */
+ ihit_pos1 = darray_double_size_get(coords1);
+ res = darray_double_resize(coords1, ihit_pos1 + 2);
+ 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;
@@ -279,7 +322,7 @@ setup_intersection_nodes
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_pos;
+ 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;
@@ -292,7 +335,7 @@ setup_intersection_nodes
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_pos;
+ 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;
@@ -341,30 +384,33 @@ vertices_setup_inside_poly_flag
static res_T
clip
(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 */
+ struct contour* cand,
+ struct contour* clip,
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 */
+ 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 */
{
enum { CAND, CLIP };
- size_t icand_node, ncand_nodes;
- const struct node* node_lists[2];
+ size_t icand_node;
+
+ const struct contour* contours[2];
res_T res = RES_OK;
- ASSERT(cand_nodes && clip_nodes && is_inside && polygon && scratch && output);
+ ASSERT(mesh && cand && clip && is_inside && polygon && scratch);
+ ASSERT(indices && coords && vertices);
- 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);
+ contours[CAND] = cand;
+ contours[CLIP] = clip;
/* TODO iterate over the intersection nodes only */
- FOR_EACH(icand_node, 0, ncand_nodes) {
+ FOR_EACH(icand_node, 0, cand->nnodes) {
const size_t* scratch_data;
- size_t ilist = CAND;
+ size_t icontour = 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* 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;
@@ -377,13 +423,23 @@ clip
darray_size_t_clear(scratch);
node_start = node = n1;
do {
- res = darray_size_t_push_back(scratch, &node->id);
+ 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;
- node = node_lists[ilist] + node->next;
+ node = contours[icontour]->nodes + node->next;
if(node->link != SIZE_MAX) {
- ilist = !ilist;
- node = node_lists[ilist] + node->link;
+ icontour = !icontour;
+ node = contours[icontour]->nodes + node->link;
}
} while(node != node_start);
@@ -394,7 +450,7 @@ clip
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));
+ 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);
@@ -407,7 +463,16 @@ clip
/* Register the created triangles */
FOR_EACH(i, 0, nids) {
- res = darray_size_t_push_back(output, scratch_data + ids[i]);
+ 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;
}
}
@@ -415,7 +480,8 @@ clip
exit:
return res;
error:
- darray_size_t_clear(output);
+ darray_size_t_clear(indices);
+ darray_double_clear(coords);
goto exit;
}
@@ -589,7 +655,9 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
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;
struct poly poly;
struct polygon* polygon = NULL; /* Use to triangulate the clipped polygons */
size_t itri, ntris, nverts;
@@ -605,7 +673,9 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
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, &coords);
darray_size_t_init(mesh->allocator, &scratch);
+ htable_vertex_init(mesh->allocator, &vertices);
poly_init(mesh->allocator, &poly);
if(!poly_desc) {
@@ -630,7 +700,8 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
&poly.coords, darray_char_data_get(&is_inside));
CPR(mesh_get_triangles_count(mesh, &ntris));
- FOR_EACH(itri, 0, ntris) {
+ /*FOR_EACH(itri, 0, ntris) {*/
+ FOR_EACH(itri, 40, 41) { /* FIXME */
size_t ids[3];
CPR(mesh_get_indices(mesh, itri, ids));
@@ -641,15 +712,50 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
if(res != RES_OK) goto error;
res = setup_intersection_nodes
- (&cand_nodes, &mesh->coords, &poly_nodes, &poly.coords);
+ (&cand_nodes, &mesh->coords, &clip_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);
+#if 1
+ if(darray_node_size_get(&cand_nodes) == 3) { /* No intersection */
+#if 1
+ if(!darray_char_data_get(&is_inside)[ids[0]]) { /* FIXME */
+ struct vertex v[3];
+ CPR(mesh_get_position(mesh, ids[0], v[0].pos));
+ CPR(mesh_get_position(mesh, ids[1], v[1].pos));
+ CPR(mesh_get_position(mesh, ids[2], v[2].pos));
+
+ ids[0] = vertex_get_index(v+0, &coords, &vertices);
+ ids[1] = vertex_get_index(v+1, &coords, &vertices);
+ ids[2] = vertex_get_index(v+2, &coords, &vertices);
+
+ darray_size_t_push_back(&indices, ids + 0);
+ darray_size_t_push_back(&indices, ids + 1);
+ darray_size_t_push_back(&indices, ids + 2);
+ }
+#endif
+ } 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_release(&mesh->indices, &indices);
+ 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;
exit:
@@ -659,7 +765,9 @@ exit:
darray_node_release(&clip_nodes);
darray_char_release(&is_inside);
darray_size_t_release(&indices);
+ darray_double_release(&coords);
darray_size_t_release(&scratch);
+ htable_vertex_release(&vertices);
poly_release(&poly);
}
if(polygon) POLYGON(ref_put(polygon));
diff --git a/src/test_cpr_clip.c b/src/test_cpr_clip.c
@@ -0,0 +1,185 @@
+/* Copyright (C) 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 "cpr.h"
+#include "test_cpr_utils.h"
+
+#include <rsys/math.h>
+#include <rsys/stretchy_array.h>
+
+static void
+get_clip_pos(const size_t ivert, double pos[2], void* ctx)
+{
+ const double* coords = ctx;
+ NCHECK(pos, NULL);
+ NCHECK(ctx, NULL);
+ pos[0] = coords[ivert*2+0];
+ pos[1] = coords[ivert*2+1];
+}
+
+static void
+dump_obj(FILE* stream, const struct cpr_mesh* mesh)
+{
+ size_t i, n;
+
+ NCHECK(stream, NULL);
+ NCHECK(mesh, NULL);
+
+ CHECK(cpr_mesh_get_vertices_count(mesh, &n), RES_OK);
+ FOR_EACH(i, 0, n) {
+ double pos[2];
+ CHECK(cpr_mesh_get_position(mesh, i, pos), RES_OK);
+ fprintf(stream, "v %g %g 0\n", SPLIT2(pos));
+ }
+
+ CHECK(cpr_mesh_get_triangles_count(mesh, &n), RES_OK);
+ FOR_EACH(i, 0, n) {
+ size_t ids[3];
+ CHECK(cpr_mesh_get_indices(mesh, i, ids), RES_OK);
+ fprintf(stream, "f %lu %lu %lu\n",
+ (unsigned long)(ids[0] + 1),
+ (unsigned long)(ids[1] + 1),
+ (unsigned long)(ids[2] + 1));
+ }
+}
+
+static void
+test_triangle(struct cpr_mesh* mesh)
+{
+ const double triangle_pos[] = { 0.0, 0.0, 0.0, 1.0, 1.0, 0.0 };
+ const size_t triangle_ids[] = { 0, 1, 2 };
+ const double clip_pos[] = { -1.0, 0.25, 1.0, 0.25, 1, 0.75 };
+ struct cpr_polygon poly;
+ struct mesh_context ctx;
+ size_t ntris;
+
+ ctx.coords = triangle_pos;
+ ctx.nverts = 3;
+ ctx.indices = triangle_ids;
+ ctx.ntris = 1;
+ CHECK(cpr_mesh_setup_indexed_vertices
+ (mesh, ctx.ntris, get_ids, 3, get_pos, &ctx), RES_OK);
+
+ poly.get_position = get_clip_pos;
+ poly.nvertices = 3;
+ poly.context = (void*)clip_pos;
+ CHECK(cpr_mesh_clip(NULL, NULL), RES_BAD_ARG);
+ CHECK(cpr_mesh_clip(mesh, NULL), RES_BAD_ARG);
+ CHECK(cpr_mesh_clip(NULL, &poly), RES_BAD_ARG);
+ CHECK(cpr_mesh_clip(mesh, &poly), RES_OK);
+
+ CHECK(cpr_mesh_get_triangles_count(mesh, &ntris), RES_OK);
+ CHECK(ntris, 3);
+
+ dump_obj(stdout, mesh);
+}
+
+static void
+test_disk(struct cpr_mesh* mesh)
+{
+ const double clip[] = { -1.75, -1.75, 1.75, -1.75, 1.75, 1.75, -1.75, 1.75 };
+ const size_t ninternal_disks = 10;
+ const double radius = 2.5;
+ const double internal_disk_step = radius / (double)ninternal_disks;
+ const size_t nslices = 4;
+ struct mesh_context ctx;
+ struct cpr_polygon poly;
+ double* pos = NULL;
+ size_t* ids = NULL;
+ size_t i, j;
+
+ FOR_EACH(i, 0, ninternal_disks) {
+ const double r = (double)(i+1)*internal_disk_step;
+ FOR_EACH(j, 0, nslices) {
+ const double theta = (double)j / (double)nslices * 2 * PI;
+ const double x = r * cos(theta);
+ const double y = r * sin(theta);
+ sa_push(pos, x);
+ sa_push(pos, y);
+ }
+ }
+
+ /* Center point */
+ sa_push(pos, 0.0);
+ sa_push(pos, 0.0);
+
+ FOR_EACH(i, 0, ninternal_disks-1) {
+ const size_t offset = (i+1) * nslices;
+ FOR_EACH(j, 0, nslices) {
+ const size_t id0 = j + offset;
+ const size_t id1 = ((j + 1) % nslices) + offset;
+ const size_t id2 = id0 - nslices;
+ const size_t id3 = id1 - nslices;
+
+ sa_push(ids, id0);
+ sa_push(ids, id2);
+ sa_push(ids, id1);
+
+ sa_push(ids, id1);
+ sa_push(ids, id2);
+ sa_push(ids, id3);
+ }
+ }
+
+ /* Center triangles */
+ FOR_EACH(j, 0, nslices) {
+ const size_t id0 = j;
+ const size_t id1 = (j + 1) % nslices;
+ const size_t id2 = sa_size(pos)/2 - 1;
+
+ sa_push(ids, id0);
+ sa_push(ids, id2);
+ sa_push(ids, id1);
+ }
+
+ ctx.coords = pos;
+ ctx.nverts = sa_size(pos)/2;
+ ctx.indices = ids;
+ ctx.ntris = sa_size(ids)/3;
+ CHECK(cpr_mesh_setup_indexed_vertices
+ (mesh, ctx.ntris, get_ids, ctx.nverts, get_pos, &ctx), RES_OK);
+
+ poly.get_position = get_clip_pos;
+ poly.nvertices = sizeof(clip)/sizeof(double[2]);
+ poly.context = (void*)clip;
+ CHECK(cpr_mesh_clip(mesh, &poly), RES_OK);
+
+ dump_obj(stdout, mesh);
+
+ sa_release(pos);
+ sa_release(ids);
+}
+
+int
+main(int argc, char** argv)
+{
+ struct mem_allocator allocator;
+ struct cpr_mesh* mesh;
+ (void)argc, (void)argv;
+
+ mem_init_proxy_allocator(&allocator, &mem_default_allocator);
+
+ CHECK(cpr_mesh_create(&allocator, &mesh), RES_OK);
+
+ /*test_triangle(mesh);*/
+ test_disk(mesh);
+
+ CHECK(cpr_mesh_ref_put(mesh), RES_OK);
+
+ check_memory_allocator(&allocator);
+ mem_shutdown_proxy_allocator(&allocator);
+ CHECK(mem_allocated_size(), 0);
+ return 0;
+}
