commit 4a690c54da17f66fa7712bac502df49f06674a4e
parent 3b65704cf1fbe70c12d97960e559c895832bae65
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 15 Apr 2026 11:52:07 +0200
Add a new algorithm for building the polylines of internal nodes
These polylines can now be constructed by recursively reducing the
polylines of their child nodes until a single polyline is obtained. In
other words, the polylines are merged and simplified in pairs.
This algorithm is provided for testing purposes. For non-binary trees,
the construction time and the quality of the resulting data structure
should depend on the algorithm used. The same applies to memory usage.
Initial tests seem to indicate that reducing polylines is more efficient
in terms of construction time. The memory space used is also slightly
lower (by a few percent) than that occupied by a tree constructed by
merging all child polylines in a single step. This reduced memory usage
could be a sign of coarser polylines, i.e., ones that represent the
node's spectrum in a more approximate manner. Sampling a line by
importance might then prove less efficient. However, this hypothesis has
not yet been verified.
A boolean variable has been added to the list of arguments for creating
a tree to allow the user to enable this new procedure (which is disabled
by default). This option is not yet available as an option in the
sln-build tool.
Finally, the tree-building tests have been expanded to include tests on
tree construction using this new algorithm.
Diffstat:
3 files changed, 297 insertions(+), 3 deletions(-)
diff --git a/src/sln.h b/src/sln.h
@@ -111,6 +111,19 @@ struct sln_tree_create_args {
/* Maximum number of children per node */
unsigned arity;
+
+ /* When this option is enabled, the polylines of internal nodes are
+ * constructed by merging their children's polylines in pairs (and then
+ * simplifying the result), and repeating the process until only a single
+ * polyline remains, which becomes the internal node's polyline.
+ *
+ * If this option is disabled, all child polylines are merged in a single step
+ * before being simplified.
+ *
+ * Enabling this option only makes sense for trees with an arity greater than
+ * two. For a binary tree, both methods should produce exactly the same tree,
+ * down to the bit */
+ int collapse_polylines;
};
#define SLN_TREE_CREATE_ARGS_DEFAULT__ { \
NULL, /* metadata */ \
@@ -122,7 +135,8 @@ struct sln_tree_create_args {
16, /* #vertices hint */ \
0.01f, /* Mesh decimation error */ \
SLN_MESH_UPPER, /* Mesh type */ \
- 2 /* Arity */ \
+ 2, /* Arity */ \
+ 0 /* Collapse polylines */ \
}
static const struct sln_tree_create_args SLN_TREE_CREATE_ARGS_DEFAULT =
SLN_TREE_CREATE_ARGS_DEFAULT__;
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -24,6 +24,7 @@
#include <star/shtr.h>
#include <rsys/cstr.h>
+#include <rsys/math.h>
/*******************************************************************************
* Helper functions
@@ -86,8 +87,10 @@ eval_ka
return ka;
}
+/* Merge all child polylines in a single step. The polylines are merged before
+ * being decimated */
static res_T
-merge_children_polylines
+merge_child_polylines
(struct sln_tree* tree,
const size_t inode)
{
@@ -237,6 +240,264 @@ error:
goto exit;
}
+/* Merge child polylines by combining them in pairs (the resulting polyline is
+ * then simplified), and repeat this process until only a single polyline
+ * remains. This polyline becomes the node's polyline */
+static res_T
+collapse_child_polylines
+ (struct sln_tree* tree,
+ struct darray_vertex* scratch,
+ const size_t inode)
+{
+ /* Polylines to be collapsed, i.e., the ids of their first and last vertices */
+ size_t poly_parts[SLN_TREE_ARITY_MAX][2] = {0};
+ size_t nparts;
+
+ /* Indices of the first and last vertices of the resulting polyline.
+ * These indices are absolute to the tree's vertex list */
+ size_t vertices_range[2] = {0,0};
+
+ /* Redux double buffering */
+ struct sln_vertex* buf[2] = {NULL, NULL};
+ int r, w; /* Index of the buffer in read/write */
+
+ /* Miscellaneous */
+ struct sln_vertex* vertices = NULL; /* Pointer to the tree's vertex buffer */
+ size_t range_merge[2] = {0,0}; /* vertex range of a merged polyline */
+ size_t nvertices = 0; /* #vertices of the resulting polyline */
+ size_t nchildren = 0;
+ size_t ivtx = 0;
+ unsigned i = 0;
+ int ncollapses = 0; /* Number of collapse steps */
+ res_T res = RES_OK;
+
+ /* Pre-conditions */
+ ASSERT(tree && inode < darray_node_size_get(&tree->nodes));
+ ASSERT(tree->args.arity >= 2);
+ ASSERT(tree->args.arity <= SLN_TREE_ARITY_MAX);
+
+ #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
+
+ nchildren = node_child_count(tree, inode, NULL);
+
+ /* Compute the number of vertices to be merged,
+ * i.e., the sum of vertices of the children */
+ nvertices = 0;
+ FOR_EACH(i, 0, nchildren) {
+ const size_t ichild = inode + NODE(inode)->offset + i;
+ nvertices += NODE(ichild)->nvertices;
+ }
+
+ /* Define the vertices range of the merged polyline */
+ vertices_range[0] = darray_vertex_size_get(&tree->vertices);
+ vertices_range[1] = vertices_range[0] + nvertices - 1/*inclusive bound*/;
+
+ /* Allocate the memory space required to store the new polyline and the
+ * temporary buffer. This is the memory space in which the collapse
+ * procedure's double buffering will take place. Each buffer will be used
+ * alternately as a read/write buffer when reducing the polylines of the
+ * child nodes */
+ if((res = darray_vertex_resize(&tree->vertices, vertices_range[1]+1)) != RES_OK
+ || (res = darray_vertex_resize(scratch, nvertices)) != RES_OK) {
+ ERROR(tree->sln, "Error in merging polylines -- %s.\n", res_to_cstr(res));
+ goto error;
+ }
+
+ /* Recover the memory space of the tree's vertices */
+ vertices = darray_vertex_data_get(&tree->vertices);
+
+ /* Recover the memory space to be used in the Redux process.
+ *
+ * In the vertex buffer, this refers to the newly allocated memory space used
+ * during the collapse. The beginning of the buffer contains the vertices of
+ * the registered nodes and must therefore not be modified. At the end of the
+ * collapse, this space will contain the vertices of the polylines resulting
+ * from the collapse of the child nodes' polylines.
+ *
+ * The scratch buffer is used as-is, since its sole purpose is to temporarily
+ * store the vertices of the polylines to be merged. */
+ buf[0] = vertices + vertices_range[0];
+ buf[1] = darray_vertex_data_get(scratch);
+
+ /* Initially, the number of partitions to be reduced is equal to the number of
+ * children */
+ nparts = nchildren;
+
+ /* Calculate the number of reduction steps, i.e., the logarithm of the power
+ * of 2 that is greater than or equal to the number of polylines to be
+ * reduced, to which one is added to obtain the number of steps, not the index
+ * of the last step */
+ ncollapses = log2i((int)round_up_pow2(nparts)) + 1;
+
+ /* Set the index of the write buffer so that, once the collapse process is
+ * complete, the last write buffer is the one whose memory space is allocated
+ * in the tree's vertex buffer. This way, no additional copies will be needed
+ * to store the result of the reduction */
+ w = ncollapses % 2 ? 0 : 1;
+
+ /* Initialize the polylines to be reduced, i.e., copy the child vertices into
+ * a collapse buffer and record their index ranges */
+ ivtx = 0;
+ for(i = 0; i < nchildren; ++i) {
+ const size_t ichild = inode + NODE(inode)->offset + i;
+ const struct sln_node* child = NODE(ichild);
+ const size_t memsz = child->nvertices * sizeof(struct sln_vertex);
+ const struct sln_vertex* src = vertices + child->ivertex;
+ struct sln_vertex* dst = buf[w] + ivtx;
+
+ memcpy(dst, src, memsz);
+ poly_parts[i][0] = ivtx;
+ poly_parts[i][1] = ivtx + child->nvertices - 1/*inclusive bound*/;
+
+ ivtx += child->nvertices;
+ }
+
+ r = w; /* Index of the buffer from which to read the data */
+ w =!r; /* Index of the buffer into which to write the data */
+
+
+ /* As long as the number of segments is not equal to one, there are still
+ * polylines to be merged in pairs */
+ while(nparts > 1) {
+ size_t ipart = 0;
+
+ for(ipart=0; ipart < nparts-1; ipart+=2) {
+ struct sln_mesh mesh0 = SLN_MESH_NULL;
+ struct sln_mesh mesh1 = SLN_MESH_NULL;
+
+ /* Retrieve the two polylines to be merged */
+ const size_t* part0 = poly_parts[ipart+0];
+ const size_t* part1 = poly_parts[ipart+1];
+
+ /* Calculate the partition index of the merged polyline, that is, the index
+ * that will contain the information for the polyline resulting from the
+ * merge: the first and last indices of its in the vertex array currently
+ * being written */
+ const size_t ipart_merge = ipart/2;
+
+ /* Compute the number of vertices of the merged polyline */
+ const size_t nvtx =
+ ((part0[1] - part0[0]) + 1/*inclusive bound*/)
+ + ((part1[1] - part1[0]) + 1/*inclusive bound*/);
+
+ /* For each child, initialized its vertex index to its first vertex. This
+ * index will be incremented as vertices are merged into the merged
+ * polyline */
+ size_t ivtx0 = part0[0];
+ size_t ivtx1 = part1[0];
+
+ /* Set the vertex index range for the merged polyline in the write buffer */
+ range_merge[0] = part0[0];
+ range_merge[1] = range_merge[0] + nvtx-1/*inclusive bound*/;
+
+ /* Setup the mesh of the two polylines to be merged */
+ mesh0.vertices = buf[r] + part0[0]; mesh0.nvertices = part0[1]-part0[0]+1;
+ mesh1.vertices = buf[r] + part1[0]; mesh1.nvertices = part1[1]-part1[0]+1;
+
+ /* Merge the polylines */
+ FOR_EACH(ivtx, range_merge[0], range_merge[1]+1/*inclusive bound*/) {
+ const double nu0 = ivtx0 <= part0[1] ? buf[r][ivtx0].wavenumber : INF;
+ const double nu1 = ivtx1 <= part1[1] ? buf[r][ivtx1].wavenumber : INF;
+ double ka = 0;
+ double nu = 0;
+
+ /* Find the minimum wave number among the vertices of the child vertices
+ * that are candidates for merging */
+ if(nu0 < nu1) { /* The vertex comes from the child0 */
+ nu = buf[r][ivtx0].wavenumber;
+ ka = buf[r][ivtx0].ka + sln_mesh_eval(&mesh1, nu);
+ ++ivtx0;
+
+ } else if(nu0 > nu1) { /* The vertex comes from the child1 */
+ nu = buf[r][ivtx1].wavenumber;
+ ka = buf[r][ivtx1].ka + sln_mesh_eval(&mesh0, nu);
+ ++ivtx1;
+
+ } else { /* The vertex is shared by node0 and node1 */
+ nu = buf[r][ivtx0].wavenumber;
+ ka = buf[r][ivtx0].ka + buf[r][ivtx1].ka;
+ --range_merge[1]; /* Remove duplicate */
+ ++ivtx0;
+ ++ivtx1;
+ }
+ buf[w][ivtx].wavenumber = (float)nu;
+ buf[w][ivtx].ka = (float)ka;
+ }
+
+ /* Decimate the resulting polyline */
+ res = polyline_decimate(tree->sln, buf[w], range_merge,
+ (float)tree->args.mesh_decimation_err, tree->args.mesh_type);
+ if(res != RES_OK) goto error;
+
+ /* Setup the partition of the merge polyline */
+ poly_parts[ipart_merge][0] = range_merge[0];
+ poly_parts[ipart_merge][1] = range_merge[1];
+ }
+
+ /* If there is a polyline that has not been merged, copy its vertices to the
+ * write buffer so that it can be processed in the next reduction step */
+ if(nparts % 2) {
+ const size_t* remain_part = poly_parts[nparts-1];
+ const size_t nvtx = remain_part[1] - remain_part[0] + 1/*inclusive*/;
+ const size_t memsz = nvtx * sizeof(struct sln_vertex);
+ const struct sln_vertex* src = buf[r] + remain_part[0];
+ struct sln_vertex* dst = buf[w] + remain_part[0];
+
+ memcpy(dst, src, memsz);
+ poly_parts[nparts/2][0] = remain_part[0];
+ poly_parts[nparts/2][1] = remain_part[1];
+ }
+
+#ifndef NDEBUG
+ FOR_EACH(i, 1, (nparts+1/*ceil*/)/2) {
+ ASSERT(poly_parts[i][0] > poly_parts[i-1][1]);
+ }
+#endif
+
+ /* Update the number of partitions to be reduced */
+ nparts = (nparts + 1/*ceil*/)/2;
+
+ /* Swap read/write buffers */
+ r = !r;
+ w = !w;
+ }
+
+ nvertices = (range_merge[1] - range_merge[0]) + 1/*inclusive bound*/;
+ vertices_range[1] = vertices_range[0] + nvertices - 1/*inclusive bound*/;
+
+ /* Assumed that double buffering was configured to ensure that the resulting
+ * polyline is stored in the tree vertex buffer */
+ ASSERT(buf[r] != darray_vertex_cdata_get(scratch));
+
+ /* Setup the node */
+ NODE(inode)->ivertex = vertices_range[0];
+ NODE(inode)->nvertices = ui64_to_ui32(nvertices);
+
+ /* It is necessary to ensure that the recorded vertices define a polyline
+ * along which any value (calculated by linear interpolation) is well above
+ * the sum of the corresponding values of the polylines to be merged. However,
+ * although this is guaranteed by definition for the vertices of the polyline,
+ * numerical uncertainty may nevertheless introduce errors that violate this
+ * criterion. Hence the following adjustment, which slightly increases the ka
+ * of the mesh so as to guarantee this constraint between the mesh of a node
+ * and that of its children */
+ if(tree->args.mesh_type == SLN_MESH_UPPER) {
+ FOR_EACH(ivtx, vertices_range[0], vertices_range[1]+1/*inclusive bound*/) {
+ const double ka = vertices[ivtx].ka;
+ vertices[ivtx].ka = (float)(ka + MMAX(ka*1e-2, 1e-6));
+ }
+ }
+
+ /* Shrink the size of the vertices */
+ darray_vertex_resize(&tree->vertices, vertices_range[1] + 1);
+
+ #undef NODE
+
+exit:
+ return res;
+error:
+ goto exit;
+}
static res_T
build_polylines(struct sln_tree* tree)
{
@@ -245,6 +506,9 @@ build_polylines(struct sln_tree* tree)
size_t stack[STACK_SIZE];
size_t istack = 0;
+ /* Temporary buffer of polyline vertices */
+ struct darray_vertex scratch;
+
/* Progress */
size_t nnodes_total = 0;
size_t nnodes_processed = 0;
@@ -256,6 +520,8 @@ build_polylines(struct sln_tree* tree)
ASSERT(tree);
+ darray_vertex_init(tree->sln->allocator, &scratch);
+
#define LOG_MSG "Meshing: %3d%%\n"
#define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
#define IS_LEAF(Id) (NODE(Id)->offset == 0)
@@ -292,8 +558,14 @@ build_polylines(struct sln_tree* tree)
ASSERT(NODE(ichild)->nvertices != 0);
}
#endif
- res = merge_children_polylines(tree, inode);
+
+ if(tree->args.collapse_polylines) {
+ res = collapse_child_polylines(tree, &scratch, inode);
+ } else {
+ res = merge_child_polylines(tree, inode);
+ }
if(res != RES_OK) goto error;
+
inode = stack[--istack]; /* Pop the next node */
/* Child nodes have NOT their polyline created */
@@ -336,6 +608,7 @@ build_polylines(struct sln_tree* tree)
#undef STACK_SIZE
exit:
+ darray_vertex_release(&scratch);
return res;
error:
goto exit;
diff --git a/src/test_sln_tree.c b/src/test_sln_tree.c
@@ -490,6 +490,13 @@ main(int argc, char** argv)
test_tree(sln, &tree_args, line_list);
test_tree_serialization(sln, &tree_args);
+ /* Test a tree with a non-standard arity, where the polylines of the internal
+ * nodes are created by collapsing the polylines of their child nodes */
+ tree_args.arity = 5;
+ tree_args.collapse_polylines = 1;
+ test_tree(sln, &tree_args, line_list);
+ test_tree_serialization(sln, &tree_args);
+
CHK(sln_device_ref_put(sln) == RES_OK);
CHK(shtr_ref_put(shtr) == RES_OK);
CHK(shtr_line_list_ref_put(line_list) == RES_OK);
