star-line

commit 1a4807e87740ee85ec096eb4569cace30e734bed
parent 2d7da76a223794081c173e8e234400d0aa8bacb4
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Mon, 30 May 2022 16:15:35 +0200

Ensures the upper mesh property in the decimation algorithm

Diffstat:
M
src/sln_polyline.c
 | 
30
+++++++++++++++++++++++++++---
M
src/sln_polyline.h
 | 
3
++-
M
src/sln_tree_build.c
 | 
5
+++--

3 files changed, 32 insertions(+), 6 deletions(-)
diff --git a/src/sln_polyline.c b/src/sln_polyline.c
@@ -24,6 +24,8 @@
 #include <rsys/float2.h>
 #include <rsys/math.h>
 
+#include <stdlib.h> /* rand */
+
 /*******************************************************************************
  * Helper function
  ******************************************************************************/
@@ -32,11 +34,12 @@
  * approximation by the line (range[0], range[1]). Let K the real value of the point
  * and Kl its linear approximation, the error is computed as:
  *
- *    err = |K-K|/min(K, Kl) */
+ *    err = |K-Kl|/(K, Kl) */
 static void
 find_falsest_vertex
   (const struct sln_vertex* vertices,
    const size_t range[2],
+   const enum sln_mesh_type mesh_type,
    size_t* out_ivertex, /* Index of the falsest vertex */
    float* out_err) /* Error of the falsest vertex */
 {
@@ -48,6 +51,7 @@ find_falsest_vertex
   size_t imax; /* Index toward the falsest vertex */
   float err_max;
   ASSERT(vertices && range && range[0] < range[1]-1 && out_ivertex && out_err);
+  ASSERT((unsigned)mesh_type < SLN_MESH_TYPES_COUNT__);
   (void)len;
 
   #define FETCH_VERTEX(Dst, Id) {                                              \
@@ -76,6 +80,25 @@ 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;
+      }
+    }
+
     /* Compute the linear approximation of p */
     val = -(N[0]*p[0] + C)/N[1];
 
@@ -124,7 +147,8 @@ polyline_decimate
   (struct sln_device* sln,
    struct sln_vertex* vertices,
    size_t vertices_range[2],
-   const float err) /* Max relative error */
+   const float err, /* Max relative error */
+   const enum sln_mesh_type mesh_type)
 {
   struct darray_size_t stack;
   size_t range[2] = {0, 0};
@@ -164,7 +188,7 @@ polyline_decimate
     float err_max = -1;
 
     if(range[1] - range[0] > 1) {
-      find_falsest_vertex(vertices, range, &imax, &err_max);
+      find_falsest_vertex(vertices, range, mesh_type, &imax, &err_max);
     }
 
     if(err_max > err) {
diff --git a/src/sln_polyline.h b/src/sln_polyline.h
@@ -33,6 +33,7 @@ polyline_decimate
   (struct sln_device* sln,
    struct sln_vertex* vertices,
    size_t vertices_range[2],
-   const float err); /* Relative error */
+   const float err, /* Relative error */
+   const enum sln_mesh_type mesh_type);
 
 #endif /* SLN_POLYLINE_H */
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -61,7 +61,7 @@ build_leaf_polyline
   /* Decimate the line mesh */
   res = polyline_decimate
     (tree->mixture->sln, darray_vertex_data_get(&tree->vertices),
-     vertices_range, args->mesh_decimation_err);
+     vertices_range, args->mesh_decimation_err, tree->mesh_type);
   if(res != RES_OK) {
     log_err(tree->mixture->sln, "Error while decimating the line mesh -- %s.\n",
       res_to_cstr(res));
@@ -172,7 +172,8 @@ merge_node_polylines
     (tree->mixture->sln,
      darray_vertex_data_get(&tree->vertices),
      vertices_range,
-     args->mesh_decimation_err);
+     args->mesh_decimation_err,
+     tree->mesh_type);
   if(res != RES_OK) {
     log_err(tree->mixture->sln, "Error while decimating the line mesh -- %s.\n",
       res_to_cstr(res));