commit 3f35162be574b177c08e80cd84a60a1dbab61e87
parent 11ec17f63b6767b537803e80f6011a18e9895403
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 13 Feb 2026 11:07:45 +0100
Fix an issue with polyline decimation
An assertion was thrown when calculating the maximum decimation error on
a polyline whose vertices were (approximately) coincident. This commit
first checks whether the polyline is degenerate. If so, it does not
record its vertices, except for the first one.
Note that this additional step uses a numerical parameter, namely the
epsilon used to compare vertex attributes and determine whether one
vertex is approximately the same as another. The coarser this parameter
is, the greater the number of vertices considered equivalent will be. In
any case, merging a polyline into a point does not guarantee that the
final mesh will be an upper limit of the spectrum, which may be what the
caller expects. To try to limit this effect, the same epsilon is added
to the ka of the recorded vertex, although in any case, this new vertex,
connected to the next one, may still generate a segment that intersects
the initial spectrum.
This is an effect to keep in mind, but it should be appreciated given
the conditions under which it is possible. The upper bound meshes are
merged and simplified successively while attempting to ensure the upper
bound criterion. The result is an upper bound that is likely to be well
above the numerical approximation linked to the aforementioned epsilon
which must nevertheless remain small.
Diffstat:
| M | src/sln_polyline.c | | | 87 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------- |
1 file changed, 75 insertions(+), 12 deletions(-)
diff --git a/src/sln_polyline.c b/src/sln_polyline.c
@@ -27,6 +27,39 @@
/*******************************************************************************
* Helper function
******************************************************************************/
+static INLINE int
+vtx_eq_eps
+ (const struct sln_vertex* v0,
+ const struct sln_vertex* v1,
+ const float eps)
+{
+ ASSERT(v0 && v1);
+
+ return eq_eps(v0->wavenumber, v1->wavenumber, eps)
+ && eq_eps(v0->ka, v1->ka, eps);
+}
+
+/* Defines whether a polyline is degenerate, i.e., whether it is actually a
+ * point */
+static int
+is_polyline_degenerate
+ (const struct sln_vertex* vertices,
+ const size_t range[2], /* Bounds are inclusive */
+ const float epsilon)
+{
+ size_t i = 0;
+ ASSERT(range[0] < range[1] && epsilon >= 0);
+
+ /* Find the first peak that is not (approximately) equal to the first one */
+ FOR_EACH(i, range[0]+1, range[1]+1/*Inclusive bound*/) {
+ if(!vtx_eq_eps(vertices+range[0], vertices + i, epsilon)) break;
+ }
+
+ /* If all vertices are verified without interruption, then all vertices are
+ * (approximately) equal. The polyline is therefore degenerate. */
+ return i > range[1];
+}
+
/* Given a set of points in [range[0], range[1]], find the point in
* [range[0]+1, range[0]-1] whose maximize the error regarding its linear
* approximation by the line (range[0], range[1]). Let K the real value of the point
@@ -176,24 +209,54 @@ polyline_decimate
PUSH(stack, range[1]);
while(range[0] != vertices_range[1]) {
+ /* Epsilon below which vertex attributes are considered equal */
+ const float vtx_eps = 1.e-6f;
+
size_t imax;
float err_max = -1;
- if(range[1] - range[0] > 1) {
- find_falsest_vertex(vertices, range, mesh_type, &imax, &err_max);
- }
+ if(is_polyline_degenerate(vertices, range, vtx_eps)) {
+ /* All the vertices of the polyline are merged. Delete all vertices from
+ * the polyline, i.e., do not save any vertices. Then, move to the next
+ * vertex range */
+ range[0] = range[1];
+ POP(stack, range[1]);
+
+ /* Note that this simplification removes vertices (even if they are very
+ * close), and the resulting mesh may therefore not correspond to the
+ * upper limit of the spectrum required by the caller. To try to mitigate
+ * this effect, update the retained vertex by adding the epsilon used to
+ * detect that one vertex is equal to another.
+ *
+ * However, there is no strict guarantee that the mesh constitutes an
+ * upper limit. This should be kept in mind, but it should be assessed in
+ * light of the conditions under which an upward default is possible. The
+ * processed mesh is likely to be superior to the spectrum well beyond the
+ * numerical approximation related to the aforementioned epsilon, which
+ * must nevertheless remain tiny */
+ if(mesh_type == SLN_MESH_UPPER) {
+ ASSERT(ivtx > 0);
+ vertices[ivtx-1].ka += vtx_eps;
+ }
- if(err_max > err) {
- /* Try to simplify a smaller polyline interval in [range[0], imax] */
- PUSH(stack, range[1]);
- range[1] = imax;
} else {
- /* Remove all vertices in [range[0]+1, range[1]-1]] */
- vertices[ivtx++] = vertices[range[1]];
+ if(range[1] - range[0] > 1) {
+ find_falsest_vertex(vertices, range, mesh_type, &imax, &err_max);
+ }
- /* Setup the next range */
- range[0] = range[1];
- POP(stack, range[1]);
+ if(err_max > err) {
+ /* Try to simplify a smaller polyline interval in [range[0], imax] */
+ PUSH(stack, range[1]);
+ range[1] = imax;
+ } else {
+ /* Remove all vertices in [range[0]+1, range[1]-1]] */
+ vertices[ivtx] = vertices[range[1]];
+ ++ivtx;
+
+ /* Setup the next range */
+ range[0] = range[1];
+ POP(stack, range[1]);
+ }
}
}
#undef PUSH
