commit c213ff38c1900e95dfd261bca87b2f8111d04543
parent 36625f9007d251b49309db36b22b09c5ca61cc42
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 23 Apr 2026 12:11:36 +0200
Limit allocations when creating a leaf polyline
The temporary buffers required by the function for constructing the
polyline of a leaf containing multiple lines are no longer local
variables of the function. They are now passed as input in order to
reuse, as much as possible, the memory space allocated during previous
calls.
Diffstat:
| M | src/sln_tree_build.c | | | 107 | +++++++++++++++++++++++++++++++++++++++++++++++++------------------------------ |
1 file changed, 67 insertions(+), 40 deletions(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -26,6 +26,21 @@
#include <rsys/cstr.h>
#include <rsys/math.h>
+/* Structure containing temporary variables used to create polyline on a leaf
+ * These variables are not declared locally within the function responsible for
+ * constructing this polyline in order to avoid having to allocate and
+ * deallocate them with each call to the function. Instead, they are passed as
+ * function inputs so as to share, as much as possible, the memory space
+ * allocated during previous calls to the function, thereby reducing the cost of
+ * allocation and deallocation. */
+struct build_leaf_polyline_scratch {
+ struct darray_vertex vertices; /* Polyline vertices */
+ struct darray_node nodes; /* Dummy leaf nodes */
+
+ /* Temp vertex buffer used when merging polylines into a single one */
+ struct darray_vertex vertices_tmp;
+};
+
static res_T
merge_child_polylines
(struct sln_tree* tree,
@@ -71,6 +86,27 @@ size_t_to_unsigned(const size_t sz)
return (unsigned)sz;
}
+static INLINE void
+build_leaf_polyline_scratch_init
+ (struct mem_allocator* allocator,
+ struct build_leaf_polyline_scratch* scratch)
+{
+ ASSERT(scratch);
+ darray_vertex_init(allocator, &scratch->vertices);
+ darray_vertex_init(allocator, &scratch->vertices_tmp);
+ darray_node_init(allocator, &scratch->nodes);
+}
+
+static INLINE void
+build_leaf_polyline_scratch_release
+ (struct build_leaf_polyline_scratch* scratch)
+{
+ ASSERT(scratch);
+ darray_vertex_release(&scratch->vertices);
+ darray_vertex_release(&scratch->vertices_tmp);
+ darray_node_release(&scratch->nodes);
+}
+
static INLINE res_T
build_leaf_polyline_from_1line(struct sln_tree* tree, struct sln_node* leaf)
{
@@ -120,12 +156,11 @@ error:
* Once created, the leaf’s polyline is finally copied into the tree’s vertex
* buffer */
static INLINE res_T
-build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
+build_leaf_polyline_from_Nlines
+ (struct sln_tree* tree,
+ struct sln_node* leaf,
+ struct build_leaf_polyline_scratch* scratch)
{
- struct darray_vertex scratch; /* Scratch buffer */
- struct darray_vertex vertices; /* Temporary vertex buffer */
- struct darray_node nodes; /* Temporary nodes */
-
const struct sln_vertex* src = NULL;
struct sln_vertex* dst = NULL;
size_t memsz = 0;
@@ -135,15 +170,7 @@ build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
unsigned i = 0;
res_T res = RES_OK;
- ASSERT(tree && leaf);
-
- /* Temporary dynamic arrays. If allocation and deallocation operations prove
- * too costly, make these arrays input arguments of the function to allow them
- * to be reused in subsequent calls, thereby reducing the number of dynamic
- * allocations */
- darray_vertex_init(tree->sln->allocator, &scratch);
- darray_vertex_init(tree->sln->allocator, &vertices);
- darray_node_init(tree->sln->allocator, &nodes);
+ ASSERT(tree && leaf && scratch);
/* Compute the number of lines of the leaf */
nlines = size_t_to_unsigned(leaf->range[1] - leaf->range[0] + 1/*inclusive*/);
@@ -151,14 +178,14 @@ build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
nnodes = nlines + 1/*leaf*/;
+ /* Helper macro */
+ #define NODE(Id) (darray_node_data_get(&scratch->nodes) + (Id))
+
/* Allocate the temporary list of nodes, one node per leaf to which on
* additionnal node is added for the leaf */
- res = darray_node_resize(&nodes, nnodes);
+ res = darray_node_resize(&scratch->nodes, nnodes);
if(res != RES_OK) goto error;
- memset(darray_node_data_get(&nodes), 0, sizeof(struct sln_node)*nnodes);
-
- /* Helper macro */
- #define NODE(Id) (darray_node_data_get(&nodes) + (Id))
+ memset(NODE(0), 0, sizeof(struct sln_node)*nnodes);
/* The leaf node will be the first one. Its "child" representing the node of
* each lines, will be store after it in the node list */
@@ -172,14 +199,14 @@ build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
const size_t iline = leaf->range[0] + i;
/* Mesh the line in the temporary vertex buffer */
- res = line_mesh
- (tree, iline, tree->args.nvertices_hint, &vertices, vertices_range);
+ res = line_mesh(tree, iline, tree->args.nvertices_hint, &scratch->vertices,
+ vertices_range);
if(res != RES_OK) goto error;
/* Decimate the line mesh */
- res = polyline_decimate(tree->sln, darray_vertex_data_get(&vertices),
- vertices_range, (float)tree->args.mesh_decimation_err,
- tree->args.mesh_type);
+ res = polyline_decimate(tree->sln,
+ darray_vertex_data_get(&scratch->vertices), vertices_range,
+ (float)tree->args.mesh_decimation_err, tree->args.mesh_type);
if(res != RES_OK) goto error;
NODE(ichild)->ivertex = vertices_range[0];
@@ -191,9 +218,11 @@ build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
/* Merge/collapse the polylines of each lines associated to nodes.
* These nodes are the "children" of the leaf */
if(tree->args.collapse_polylines) {
- res = collapse_child_polylines(tree, 0, nlines, &nodes, &scratch, &vertices);
+ res = collapse_child_polylines(tree, 0, nlines,
+ &scratch->nodes, &scratch->vertices_tmp, &scratch->vertices);
} else {
- res = merge_child_polylines(tree, 0, nlines, &nodes, &vertices);
+ res = merge_child_polylines(tree, 0, nlines,
+ &scratch->nodes, &scratch->vertices);
}
if(res != RES_OK) goto error;
@@ -205,7 +234,7 @@ build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
* tree */
res = darray_vertex_resize(&tree->vertices, leaf->ivertex + leaf->nvertices);
if(res != RES_OK) goto error;
- src = darray_vertex_cdata_get(&vertices) + NODE(0/*leaf*/)->ivertex;
+ src = darray_vertex_cdata_get(&scratch->vertices) + NODE(0/*leaf*/)->ivertex;
dst = darray_vertex_data_get(&tree->vertices) + leaf->ivertex;
memsz = leaf->nvertices * sizeof(*src);
memcpy(dst, src, memsz);
@@ -213,16 +242,16 @@ build_leaf_polyline_from_Nlines(struct sln_tree* tree, struct sln_node* leaf)
#undef NODE
exit:
- darray_vertex_release(&scratch);
- darray_vertex_release(&vertices);
- darray_node_release(&nodes);
return res;
error:
goto exit;
}
static INLINE res_T
-build_leaf_polyline(struct sln_tree* tree, struct sln_node* leaf)
+build_leaf_polyline
+ (struct sln_tree* tree,
+ struct sln_node* leaf,
+ struct build_leaf_polyline_scratch* scratch)
{
size_t nlines = 0; /* Number of lines in the leaf */
ASSERT(tree && leaf);
@@ -232,7 +261,7 @@ build_leaf_polyline(struct sln_tree* tree, struct sln_node* leaf)
if(nlines == 1) {
return build_leaf_polyline_from_1line(tree, leaf);
} else {
- return build_leaf_polyline_from_Nlines(tree, leaf);
+ return build_leaf_polyline_from_Nlines(tree, leaf, scratch);
}
}
@@ -681,21 +710,19 @@ 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;
int progress = 0;
/* Miscellaneous */
+ struct build_leaf_polyline_scratch scratch;
size_t inode = 0;
res_T res = RES_OK;
ASSERT(tree);
- darray_vertex_init(tree->sln->allocator, &scratch);
+ build_leaf_polyline_scratch_init(tree->sln->allocator, &scratch);
#define LOG_MSG "Meshing: %3d%%\n"
#define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
@@ -714,7 +741,7 @@ build_polylines(struct sln_tree* tree)
const size_t istack_saved = istack;
if(IS_LEAF(inode)) {
- res = build_leaf_polyline(tree, NODE(inode));
+ res = build_leaf_polyline(tree, NODE(inode), &scratch);
if(res != RES_OK) goto error;
inode = stack[--istack]; /* Pop the next node */
@@ -735,8 +762,8 @@ build_polylines(struct sln_tree* tree)
}
#endif
if(tree->args.collapse_polylines) {
- res = collapse_child_polylines
- (tree, inode, nchildren, &tree->nodes, &scratch, &tree->vertices);
+ res = collapse_child_polylines(tree, inode, nchildren, &tree->nodes,
+ &scratch.vertices_tmp, &tree->vertices);
} else {
res = merge_child_polylines
(tree, inode, nchildren, &tree->nodes, &tree->vertices);
@@ -785,7 +812,7 @@ build_polylines(struct sln_tree* tree)
#undef STACK_SIZE
exit:
- darray_vertex_release(&scratch);
+ build_leaf_polyline_scratch_release(&scratch);
return res;
error:
goto exit;
