star-cpr

commit 0db8875deff65859fcb923ab813cdb596627856b
parent 0838ad30be0c6ef32b3b849cd1dc87d78b2aafbf
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Thu, 25 Aug 2016 10:11:44 +0200

Add a trick to avoid the clip edge/candidate vertex intersection issue

If a clip edge intersects a candidate vertex, the Weiler & Atherton
clipping algorithm may fail. To avoid this, candidate vertices that
roughly lie onto the clip edge are slightly move away along the clip
edge normal.

Diffstat:
M
src/cpr_mesh.c
 | 
32
+++++++++++++++++++++++++-------
M
src/test_cpr_clip.c
 | 
2
+-

2 files changed, 26 insertions(+), 8 deletions(-)
diff --git a/src/cpr_mesh.c b/src/cpr_mesh.c
@@ -352,7 +352,7 @@ error:
 
 static void
 vertices_setup_inside_poly_flag
-  (const struct darray_double* coords,
+  (struct darray_double* coords,
    const struct darray_node* poly_nodes,
    const struct darray_double* poly_coords,
    char* is_inside)
@@ -365,7 +365,7 @@ vertices_setup_inside_poly_flag
   nedges = darray_node_size_get(poly_nodes);
 
   FOR_EACH(ivert, 0, nverts) {
-    const double* v = darray_double_cdata_get(coords) + ivert*2;
+    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;
@@ -373,9 +373,28 @@ vertices_setup_inside_poly_flag
       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);
-      inside = d2_cross(e1, e0) < 0;
+      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;
   }
@@ -384,8 +403,8 @@ vertices_setup_inside_poly_flag
 static res_T
 clip
   (const struct cpr_mesh* mesh,
-   struct contour* cand,
-   struct contour* clip,
+   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 */
@@ -700,8 +719,7 @@ 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, 40, 41) { /* FIXME */
+  FOR_EACH(itri, 0, ntris) {
     size_t ids[3];
 
     CPR(mesh_get_indices(mesh, itri, ids));
diff --git a/src/test_cpr_clip.c b/src/test_cpr_clip.c
@@ -93,7 +93,7 @@ test_disk(struct cpr_mesh* mesh)
   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;
+  const size_t nslices = 64;
   struct mesh_context ctx;
   struct cpr_polygon poly;
   double* pos = NULL;