star-line

commit bb6e02fe7c1f0a6a36056e9ae41081e588bdac32
parent c0f8186e7e68037158390e0a9c9cde9b317f488f
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Tue, 20 Sep 2022 11:28:45 +0200

Update the algorithm for decimating upper meshes

Diffstat:
M
src/sln_polyline.c
 | 
33
++++++++++++---------------------

1 file changed, 12 insertions(+), 21 deletions(-)
diff --git a/src/sln_polyline.c b/src/sln_polyline.c
@@ -24,8 +24,6 @@
 #include <rsys/float2.h>
 #include <rsys/math.h>
 
-#include <stdlib.h> /* rand */
-
 /*******************************************************************************
  * Helper function
  ******************************************************************************/
@@ -46,10 +44,10 @@ find_falsest_vertex
   float p0[2], p1[2]; /* 1st and last point of the submitted range */
   float N[2], C; /* edge equation N.p + C  = 0 */
   float len;
-
   size_t ivertex;
   size_t imax; /* Index toward the falsest vertex */
   float err_max;
+  int has_vertices_above = 0;
   ASSERT(vertices && range && range[0] < range[1]-1 && out_ivertex && out_err);
   ASSERT((unsigned)mesh_type < SLN_MESH_TYPES_COUNT__);
   (void)len;
@@ -81,23 +79,8 @@ find_falsest_vertex
 
     FETCH_VERTEX(p, ivertex);
 
-    /* To ensure an upper mesh, we cannot delete a vertex above the candidate
-     * edge used to simplify the mesh. We therefore compel ourselves to keep
-     * such vertices by defining their error at infinity. It would therefore be
-     * useless to look for a more false vertex and the research could be
-     * stopped. But we don't always stop the research since any of these
-     * vertices is a candidate to be a polyline vertex. Instead, we randomly
-     * stop the search and thus avoid always keeping the first/last vertex in
-     * the ascending/descending parts, respectively. */
-    if(mesh_type == SLN_MESH_UPPER /* Ensure an upper mesh */
-    && N[0]*p[0] + N[1]*p[1] + C < 0) { /* The vertex is above the edge */
-      imax = ivertex;
-      err_max = FLT_MAX;
-      if(rand() > RAND_MAX / 2) {
-        break;
-      } else {
-        continue;
-      }
+    if(N[0]*p[0] + N[1]*p[1] + C < 0) { /* The vertex is above the edge */
+      has_vertices_above = 1;
     }
 
     /* Compute the linear approximation of p */
@@ -113,7 +96,15 @@ find_falsest_vertex
   #undef FETCH_VERTEX
 
   *out_ivertex = imax;
-  *out_err = err_max;
+  /* To ensure an upper mesh, we cannot delete a vertex above the candidate
+   * edge used to simplify the mesh. We therefore compel ourselves not to
+   * simplify the polyline when such vertices are detected by returning an
+   * infinite error */
+  if(mesh_type == SLN_MESH_UPPER && has_vertices_above) {
+    *out_err = (float)INF;
+  } else {
+    *out_err = err_max;
+  }
 }
 
 static INLINE void