commit 6157fa54c6827b6af0b670f4880ba8a3b22e6e25
parent 0db8875deff65859fcb923ab813cdb596627856b
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 25 Aug 2016 13:24:38 +0200
Speed up the clip process
Do not clip the mesh triangles that does not intersect the clip polygon.
Diffstat:
| M | src/cpr_mesh.c | | | 160 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------- |
1 file changed, 122 insertions(+), 38 deletions(-)
diff --git a/src/cpr_mesh.c b/src/cpr_mesh.c
@@ -58,6 +58,7 @@ struct node {
struct poly {
struct darray_double coords;
+ double lower[2], upper[2];
};
struct hit {
@@ -77,6 +78,27 @@ struct cpr_mesh {
/*******************************************************************************
* Helper functions
******************************************************************************/
+static INLINE int
+aabb_is_degenerated(const double lower[2], const double upper[2])
+{
+ ASSERT(lower && upper);
+ return lower[0] >= upper[0] || lower[1] >= upper[1];
+}
+
+static int
+aabb_intersect
+ (const double lower0[2],
+ const double upper0[2],
+ const double lower1[2],
+ const double upper1[2])
+{
+ 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];
+}
+
static int
intersect_edges
(double edge0[2][2],
@@ -137,7 +159,7 @@ vertex_get_index
ASSERT(v && coords && vertices);
- /* Dirty trick. TODO comment this */
+ /* Dirty trick. TODO comment this, or better, replace this! */
key.pos[0] = (float)v->pos[0];
key.pos[1] = (float)v->pos[1];
@@ -189,15 +211,21 @@ poly_setup(struct poly* poly, const struct cpr_polygon* desc)
res = darray_double_resize(&poly->coords, desc->nvertices * 2/*#coords*/);
if(res != RES_OK) goto error;
+ d2_splat(poly->lower, DBL_MAX);
+ d2_splat(poly->upper, DBL_MIN);
FOR_EACH(ivert, 0, desc->nvertices) {
double* pos = darray_double_data_get(&poly->coords) + ivert*2;
desc->get_position(ivert, pos, desc->context);
+ d2_min(poly->lower, poly->lower, pos);
+ d2_max(poly->upper, poly->upper, pos);
}
exit:
return res;
error:
darray_double_clear(&poly->coords);
+ d2_splat(poly->lower, DBL_MAX);
+ d2_splat(poly->upper, DBL_MIN);
goto exit;
}
@@ -227,6 +255,52 @@ poly_setup_nodes(struct poly* poly, struct darray_node* nodes)
return RES_OK;
}
+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);
+}
+
+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);
+
+ FOR_EACH(i, 0, 3) {
+ struct vertex v;
+ size_t id;
+
+ CPR(mesh_get_position(mesh, triangle[i], v.pos));
+ id = vertex_get_index(&v, coords, vertices);
+ 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)
{
@@ -350,8 +424,10 @@ 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
-vertices_setup_inside_poly_flag
+preprocess_vertices
(struct darray_double* coords,
const struct darray_node* poly_nodes,
const struct darray_double* poly_coords,
@@ -682,11 +758,11 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
size_t itri, ntris, nverts;
res_T res = RES_OK;
- if(!mesh) {
- res = RES_BAD_ARG;
- goto error;
- }
+ /* 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);
@@ -697,60 +773,70 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
htable_vertex_init(mesh->allocator, &vertices);
poly_init(mesh->allocator, &poly);
- if(!poly_desc) {
- res = RES_BAD_ARG;
- goto error;
- }
-
+ /* 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 */
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;
- /* Define which mesh vertices are inside the polygon */
+ /* 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);
if(res != RES_OK) goto error;
- vertices_setup_inside_poly_flag(&mesh->coords, &poly_nodes,
- &poly.coords, darray_char_data_get(&is_inside));
+ 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;
+ }
+
+ /* 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;
+ /* Insert into the candidate and clip node lists the intersection nodes */
res = setup_intersection_nodes
(&cand_nodes, &mesh->coords, &clip_nodes, &poly.coords);
if(res != RES_OK) goto error;
#if 1
if(darray_node_size_get(&cand_nodes) == 3) { /* No intersection */
-#if 1
+ /* If the first index is not inside */
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);
+ res = triangle_register(ids, mesh, &indices, &coords, &vertices);
+ if(res != RES_OK) goto error;
darray_size_t_push_back(&indices, ids + 2);
}
-#endif
} else
#endif
{
@@ -777,17 +863,15 @@ cpr_mesh_clip(struct cpr_mesh* mesh, struct cpr_polygon* poly_desc)
if(res != RES_OK) goto error;
exit:
- 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_double_release(&coords);
- darray_size_t_release(&scratch);
- htable_vertex_release(&vertices);
- poly_release(&poly);
- }
+ 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_double_release(&coords);
+ darray_size_t_release(&scratch);
+ htable_vertex_release(&vertices);
+ poly_release(&poly);
if(polygon) POLYGON(ref_put(polygon));
return res;
