commit e6178416a6dc623d78d0e4371034aff39fd736cd
parent 1a4496eef4c5ad30a2e289ac89377c50746caad7
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 17 Apr 2026 15:58:43 +0200
A leaf node can contain multiple lines
Add a new input argument when creating the tree to specify the maximum
number of lines a leaf node can have.
Internally, its polyline is constructed as if it were an internal node
onto which its N children (i.e., its lines) are merged. Thus, the line
meshing procedure is reused with all its beneficial properties
(symmetric, monotonic on its half), as are the merge/grouping functions
originally designed for internal nodes.
Certain internal functions, originally designed to process only tree
data, have been updated to handle a vertex buffer and a list of nodes
not belonging to the tree. They can thus be used on temporary data, as
is necessary for the aforementioned function that constructs the
polyline from a list of lines.
The -L option has been added to the sln-build tool to allow the user to
set the maximum number of lines per leaf, which defaults to 1.
The sln-slab tool has also been slightly modified, as the acceleration
structure now samples one leaf per instance, rather than one line,
since a leaf can have multiple lines. The algorithm remains strictly
the same, however; only certain variable names have been updated to
clarify that a leaf can contain more than one line.
Finally, the tree-building tests have been expanded to verify the
construction of trees whose leaves contain more than one line.
As expected, increasing the number of lines per leaf significantly
reduces the memory footprint of the resulting tree, since the most
memory-intensive part are the line meshes. In initial tests, this memory
usage was reduced up to an order of magnitude. This is because merging
lines and simplifying the resulting polylines results in the removal of
several vertices located on their common flat segments, such as the
vertices of overlapping line wings. On the other hand, having multiple
lines per leaf increases the evaluation of each leaf’s contribution, and
thus the computational cost of algorithms that use this evluation, as is
the case with the sln-slab program.
Diffstat:
11 files changed, 320 insertions(+), 117 deletions(-)
diff --git a/doc/sln-build.1 b/doc/sln-build.1
@@ -15,7 +15,7 @@
.\"
.\" You should have received a copy of the GNU General Public License
.\" along with this program. If not, see <http://www.gnu.org/licenses/>.
-.Dd April 15, 2026
+.Dd April 17, 2026
.Dt SLN-BUILD 1
.Os
.\""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
@@ -28,6 +28,7 @@
.Op Fl chsv
.Op Fl a Ar arity
.Op Fl e Ar polyline_opt Ns Op : Ns Ar polyline_opt No ...
+.Op Fl L Ar leaf_nlines
.Op Fl l Ar line_profile
.Op Fl o Ar accel_struct
.Fl P Ar pressure
@@ -102,6 +103,10 @@ The default value is 16.
.It Fl h
Display short help and exit.
.\""""""""""""""""""""""""""""""""""
+.It Fl L Ar leaf_nlines
+Maximum number of lines per tree leaf.
+The default value is 1.
+.\""""""""""""""""""""""""""""""""""
.It Fl l Ar line_profile
Defines the line profile.
Currently,
diff --git a/src/sln.h b/src/sln.h
@@ -45,6 +45,7 @@
#define SLN_TREE_DEPTH_MAX 64 /* Maximum depth of a tree */
#define SLN_TREE_ARITY_MAX 256 /* Maximum arity of a tree */
+#define SLN_LEAF_NLINES_MAX 1024 /* Maximum number of lines per leaf */
/* Forward declaration of external data structures */
struct logger;
@@ -112,6 +113,9 @@ struct sln_tree_create_args {
/* Maximum number of children per node */
unsigned arity;
+ /* Maximum number of lines per leaf */
+ unsigned leaf_nlines;
+
/* 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
@@ -136,6 +140,7 @@ struct sln_tree_create_args {
0.01f, /* Mesh decimation error */ \
SLN_MESH_UPPER, /* Mesh type */ \
2, /* Arity */ \
+ 1, /* Number of lines per leaf */ \
0 /* Collapse polylines */ \
}
static const struct sln_tree_create_args SLN_TREE_CREATE_ARGS_DEFAULT =
@@ -171,7 +176,6 @@ static const struct sln_tree_write_args SLN_TREE_WRITE_ARGS_NULL =
SLN_TREE_WRITE_ARGS_NULL__;
struct sln_tree_desc {
- size_t max_nlines_per_leaf;
double mesh_decimation_err;
enum sln_mesh_type mesh_type;
enum sln_line_profile line_profile;
@@ -184,9 +188,10 @@ struct sln_tree_desc {
size_t nvertices;
size_t nnodes;
unsigned arity;
+ unsigned leaf_nlines;
};
#define SLN_TREE_DESC_NULL__ { \
- 0, 0, SLN_MESH_TYPES_COUNT__, SLN_LINE_PROFILES_COUNT__, 0, 0, 0, 0, 0, 0, 0 \
+ 0,SLN_MESH_TYPES_COUNT__,SLN_LINE_PROFILES_COUNT__,0,0,0,0,0,0,0,0 \
}
static const struct sln_tree_desc SLN_TREE_DESC_NULL = SLN_TREE_DESC_NULL__;
diff --git a/src/sln_build.c b/src/sln_build.c
@@ -57,6 +57,7 @@ struct args {
int quit;
int verbose;
unsigned arity; /* tree arity */
+ unsigned leaf_nlines; /* Maximum number of lines per leaf */
enum line_list_format line_format;
};
#define ARGS_DEFAULT__ { \
@@ -82,6 +83,7 @@ struct args {
0, /* Quit */ \
0, /* Verbose */ \
2, /* Tree arity */ \
+ 1, /* Number of lines per leaf */ \
LINE_LIST_HITRAN /* lines_format */ \
}
static const struct args ARGS_DEFAULT = ARGS_DEFAULT__;
@@ -108,8 +110,8 @@ usage(FILE* stream)
{
fprintf(stream,
"usage: sln-build [-chsv] [-a arity] [-e polyline_opt[:polyline_opt ...]]\n"
-" [-l line_profile] [-o accel_struct] -P pressure -T temperature\n"
-" -m molparams -x mixture [lines]\n");
+" [-L leaf_nlines] [-l line_profile] [-o accel_struct]\n"
+" -P pressure -T temperature -m molparams -x mixture [lines]\n");
}
static res_T
@@ -227,7 +229,7 @@ args_init(struct args* args, int argc, char** argv)
*args = ARGS_DEFAULT;
- while((opt = getopt(argc, argv, "a:ce:hl:o:P:sT:m:vx:")) != -1) {
+ while((opt = getopt(argc, argv, "a:ce:hL:l:o:P:sT:m:vx:")) != -1) {
switch(opt) {
case 'a':
res = cstr_to_uint(optarg, &args->arity);
@@ -241,6 +243,10 @@ args_init(struct args* args, int argc, char** argv)
usage(stdout);
args->quit = 1;
goto exit;
+ case 'L':
+ res = cstr_to_uint(optarg, &args->leaf_nlines);
+ if(res == RES_OK && args->leaf_nlines < 1) res = RES_BAD_ARG;
+ break;
case 'l':
res = parse_line_profile(optarg, &args->line_profile);
break;
@@ -452,6 +458,7 @@ cmd_run(struct cmd* cmd)
tree_args.mesh_decimation_err = cmd->args.mesh_decimation_err;
tree_args.mesh_type = cmd->args.mesh_type;
tree_args.arity = cmd->args.arity;
+ tree_args.leaf_nlines = cmd->args.leaf_nlines;
tree_args.collapse_polylines = cmd->args.collapse_polylines;
if(cmd->args.output) {
diff --git a/src/sln_get.c b/src/sln_get.c
@@ -481,7 +481,7 @@ print_tree_descriptor(const struct cmd* cmd)
printf("type: %s\n", sln_mesh_type_cstr(desc.mesh_type));
printf("decimation error: %.4e\n", desc.mesh_decimation_err);
printf("line profile: %s\n", sln_line_profile_cstr(desc.line_profile));
- printf("#lines per leaf: %lu\n", (unsigned long)desc.max_nlines_per_leaf);
+ printf("#lines per leaf: %lu\n", (unsigned long)desc.leaf_nlines);
printf("arity: %u\n", desc.arity);
exit:
diff --git a/src/sln_line.c b/src/sln_line.c
@@ -349,6 +349,7 @@ save_line_mesh
const struct line* line,
const struct darray_double* wavenumbers,
const struct darray_double* values,
+ struct darray_vertex* vertices, /* buffer in which vertices are added */
size_t vertices_range[2]) /* Range into which the line vertices are saved */
{
const double* wnums = NULL;
@@ -360,10 +361,10 @@ save_line_mesh
size_t i = 0;
res_T res = RES_OK;
- ASSERT(tree && line && wavenumbers && values && vertices_range);
+ ASSERT(tree && line && wavenumbers && values && vertices && vertices_range);
ASSERT(darray_double_size_get(wavenumbers) == darray_double_size_get(values));
- nvertices = darray_vertex_size_get(&tree->vertices);
+ nvertices = darray_vertex_size_get(vertices);
nwavenumbers = darray_double_size_get(wavenumbers);
/* Compute the overall number of vertices of the line */
@@ -372,7 +373,7 @@ save_line_mesh
- 1;/* Do not duplicate the line center */
/* Allocate the list of line vertices */
- res = darray_vertex_resize(&tree->vertices, nvertices + line_nvertices);
+ res = darray_vertex_resize(vertices, nvertices + line_nvertices);
if(res != RES_OK) goto error;
wnums = darray_double_cdata_get(wavenumbers);
@@ -384,7 +385,7 @@ save_line_mesh
/* Copy the vertices of the line for its lower half */
FOR_EACH_REVERSE(ivertex, nwavenumbers-1, 0) {
- struct sln_vertex* vtx = darray_vertex_data_get(&tree->vertices) + i++;
+ struct sln_vertex* vtx = darray_vertex_data_get(vertices) + i++;
const double nu = MIRROR(wnums[ivertex]);
const double ha = vals[ivertex];
@@ -394,7 +395,7 @@ save_line_mesh
/* Copy the vertices of the line for its upper half */
FOR_EACH(ivertex, 0, nwavenumbers) {
- struct sln_vertex* vtx = darray_vertex_data_get(&tree->vertices) + i++;
+ struct sln_vertex* vtx = darray_vertex_data_get(vertices) + i++;
const double nu = wnums[ivertex];
const double ha = vals[ivertex];
@@ -413,7 +414,7 @@ save_line_mesh
exit:
return res;
error:
- darray_vertex_resize(&tree->vertices, nvertices);
+ darray_vertex_resize(vertices, nvertices);
ERROR(tree->sln, "Error while recording line vertices -- %s.\n",
res_to_cstr(res));
goto exit;
@@ -498,6 +499,7 @@ line_mesh
(struct sln_tree* tree,
const size_t iline,
const size_t nvertices_hint,
+ struct darray_vertex* vertices, /* buffer in which vertices are added */
size_t vertices_range[2]) /* out. Bounds are inclusive */
{
/* The line */
@@ -512,7 +514,7 @@ line_mesh
res_T res = RES_OK;
/* Pre-conditions */
- ASSERT(tree && nvertices_hint);
+ ASSERT(tree && vertices && nvertices_hint);
darray_double_init(tree->sln->allocator, &values);
darray_double_init(tree->sln->allocator, &wavenumbers);
@@ -545,7 +547,8 @@ line_mesh
default: FATAL("Unreachable code.\n"); break;
}
- res = save_line_mesh(tree, &line, &wavenumbers, &values, vertices_range);
+ res = save_line_mesh
+ (tree, &line, &wavenumbers, &values, vertices, vertices_range);
if(res != RES_OK) goto error;
exit:
diff --git a/src/sln_line.h b/src/sln_line.h
@@ -66,6 +66,8 @@ line_mesh
(struct sln_tree* tree,
const size_t iline,
const size_t nvertices_hint,
+ /* Vertex buffer in which line vertices are added */
+ struct darray_vertex* vertices, /* out */
/* Range of generated line vertices. Bounds are inclusive */
size_t vertices_range[2]); /* out */
diff --git a/src/sln_slab.c b/src/sln_slab.c
@@ -368,7 +368,7 @@ error:
}
static const struct sln_node* /* NULL <=> an error occurs */
-sample_line
+sample_leaf
(const struct cmd* cmd,
struct ssp_rng* rng,
const double nu/*[cm^-1]*/,
@@ -420,26 +420,6 @@ error:
goto exit;
}
-static INLINE res_T
-check_sampled_node(const struct cmd* cmd, const struct sln_node* node)
-{
- ASSERT(cmd);
- (void) cmd;
-
- if(!node) return RES_BAD_ARG;
-
-#ifndef NDEBUG
- {
- /* Verify that the sampled node corresponds to a single line */
- struct sln_node_desc desc = SLN_NODE_DESC_NULL;
- SLN(node_get_desc(cmd->tree, node, &desc));
- ASSERT(desc.nlines == 1);
- }
-#endif
-
- return RES_OK;
-}
-
/* Check that the probability is valid */
static INLINE res_T
check_proba(const struct cmd* cmd, const double proba)
@@ -521,8 +501,8 @@ realisation
for(ncollisions=0; ; ++ncollisions) {
double dst = 0; /* Sampled distance */
double proba_abs = 0; /* Probability of absorption */
- double line_proba = 0; /* Probability of sampling the line */
- double line_ha = 0; /* Value of the line */
+ double leaf_proba = 0; /* Probability of sampling the line */
+ double leaf_ka = 0; /* Value of the line */
double r = 0; /* Random number */
dst = ssp_ran_exp(rng, ka_max); /* Sample a traversal distance */
@@ -534,13 +514,12 @@ realisation
}
/* Importance sampling of a line */
- node = sample_line(cmd, rng, nu, &line_proba);
- if((res = check_sampled_node(cmd, node)) != RES_OK) goto error;
+ node = sample_leaf(cmd, rng, nu, &leaf_proba);
/* Evaluate the value of the line and compute the probability of being
* absorbed by it */
- line_ha = sln_node_eval(cmd->tree, node, nu);
- proba_abs = line_ha / (line_proba*ka_max);
+ leaf_ka = sln_node_eval(cmd->tree, node, nu);
+ proba_abs = leaf_ka / (leaf_proba*ka_max);
if((res = check_proba(cmd, proba_abs)) != RES_OK) goto error;
r = ssp_rng_canonical(rng);
diff --git a/src/sln_tree.c b/src/sln_tree.c
@@ -229,6 +229,12 @@ check_sln_tree_create_args
return RES_BAD_ARG;
}
+ if(args->leaf_nlines < 1 || args->leaf_nlines > SLN_LEAF_NLINES_MAX) {
+ ERROR(sln, "%s: invalid number of lines per leaf %u. It must be in [1, %d]\n",
+ caller, args->leaf_nlines, SLN_LEAF_NLINES_MAX);
+ return RES_BAD_ARG;
+ }
+
res = check_molecules(sln, caller, args);
if(res != RES_OK) return res;
@@ -388,32 +394,29 @@ release_tree(ref_T* ref)
******************************************************************************/
unsigned
node_child_count
- (const struct sln_tree* tree,
- const size_t inode,
+ (const struct sln_node* node,
+ const unsigned tree_arity,
size_t* out_nlines_per_child) /* Max #lines per child. May be NULL */
{
- const struct sln_node* node = NULL;
size_t nlines = 0; /* #lines in the node */
size_t nlines_per_child = 0; /* Max #lines in a child */
size_t nchildren = 0;
/* Pre-conditions */
- ASSERT(tree && inode < darray_node_size_get(&tree->nodes));
- ASSERT(MAX_NLINES_PER_LEAF == 1); /* Assume one line per leaf */
+ ASSERT(node && tree_arity >= 2);
/* Retrieve the node data and compute the #lines it partitions */
- node = darray_node_cdata_get(&tree->nodes) + inode;
nlines = node->range[1] - node->range[0] + 1;
ASSERT(nlines);
/* Based on the arity of the tree, calculate how the lines of the node are
* distributed among its children. The policy below prioritizes an equal
- * distribution of rows among the children over maintaining the tree's arity.
+ * distribution of lines among the children over maintaining the tree's arity.
* Thus, if a smaller number of children results in a more equitable
* distribution, this option is preferred over ensuring a number of children
* equal to the tree's arity. In other words, the tree's balance is
* prioritized. */
- nlines_per_child = (nlines + tree->args.arity-1/*ceil*/)/tree->args.arity;
+ nlines_per_child = (nlines + tree_arity-1/*ceil*/)/tree_arity;
/* From the previous line repartition, compute the number of children */
nchildren = (nlines + nlines_per_child-1/*ceil*/)/nlines_per_child;
@@ -554,6 +557,7 @@ sln_tree_read
READ(&tree->args.mesh_decimation_err, 1);
READ(&tree->args.mesh_type, 1);
READ(&tree->args.arity, 1);
+ READ(&tree->args.leaf_nlines, 1);
#undef READ
exit:
@@ -589,7 +593,6 @@ sln_tree_get_desc(const struct sln_tree* tree, struct sln_tree_desc* desc)
if(!tree || !desc) return RES_BAD_ARG;
- desc->max_nlines_per_leaf = 1;
desc->mesh_decimation_err = tree->args.mesh_decimation_err;
desc->mesh_type = tree->args.mesh_type;
desc->line_profile = tree->args.line_profile;
@@ -598,6 +601,7 @@ sln_tree_get_desc(const struct sln_tree* tree, struct sln_tree_desc* desc)
desc->pressure = tree->args.pressure; /* [atm] */
desc->temperature = tree->args.temperature; /* [K] */
desc->arity = tree->args.arity;
+ desc->leaf_nlines = tree->args.leaf_nlines;
SHTR(line_list_get_size(tree->args.lines, &desc->nlines));
@@ -638,11 +642,8 @@ sln_node_get_child_count
if(sln_node_is_leaf(node)) {
return 0; /* No child */
-
} else {
- const size_t inode = (size_t)(node - darray_node_cdata_get(&tree->nodes));
- ASSERT(inode < darray_node_size_get(&tree->nodes));
- return node_child_count(tree, inode, NULL);
+ return node_child_count(node, tree->args.arity, NULL);
}
}
@@ -820,6 +821,7 @@ sln_tree_write
WRITE(&tree->args.mesh_decimation_err, 1);
WRITE(&tree->args.mesh_type, 1);
WRITE(&tree->args.arity, 1);
+ WRITE(&tree->args.leaf_nlines, 1);
#undef WRITE
exit:
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -26,6 +26,23 @@
#include <rsys/cstr.h>
#include <rsys/math.h>
+static res_T
+merge_child_polylines
+ (struct sln_tree* tree,
+ const size_t inode, /* Node at which child polylines are merged */
+ const unsigned nchildren, /* #children to merge */
+ struct darray_node* nodes, /* List of nodes */
+ struct darray_vertex* vertices); /* List of polyline vertices */
+
+static res_T
+collapse_child_polylines
+ (struct sln_tree* tree,
+ const size_t inode, /* Node at which child polylines are merged */
+ const unsigned nchildren, /* #children to collapse */
+ struct darray_node* nodes, /* List of nodes */
+ struct darray_vertex* scratch, /* Temporary buffer of vertices */
+ struct darray_vertex* vertices); /* List of polyline vertices */
+
/*******************************************************************************
* Helper functions
******************************************************************************/
@@ -37,17 +54,27 @@ ui64_to_ui32(const uint64_t ui64)
return (uint32_t)ui64;
}
+static FINLINE unsigned
+size_t_to_unsigned(const size_t sz)
+{
+ if(sz > UINT_MAX)
+ VFATAL("%s: overflow %lu.\n", ARG2(FUNC_NAME, ((unsigned long)sz)));
+ return (unsigned)sz;
+}
+
static INLINE res_T
-build_leaf_polyline(struct sln_tree* tree, struct sln_node* leaf)
+build_leaf_polyline_from_1line(struct sln_tree* tree, struct sln_node* leaf)
{
size_t vertices_range[2];
res_T res = RES_OK;
- /* Currently assume that we have only one line per leaf */
+ /* Assume that there is only one line per leaf */
ASSERT(leaf->range[0] == leaf->range[1]);
/* Line meshing */
- res = line_mesh(tree, leaf->range[0], tree->args.nvertices_hint, vertices_range);
+ res = line_mesh
+ (/* in */ tree, leaf->range[0], tree->args.nvertices_hint,
+ /* out */ &tree->vertices, vertices_range);
if(res != RES_OK) goto error;
/* Decimate the line mesh */
@@ -68,55 +95,190 @@ error:
goto exit;
}
+/* Build the polyline of a leaf node containing more than one line.
+ *
+ * Each line is drawn as if it were the only one on the leaf. This allows the
+ * line meshing routine to be used, and consequently the algorithm that relies
+ * on the properties of the lines (symmetry, monotonicity on one half). Next,
+ * this set of polylines is merged/collapsed into a single polyline, which is
+ * the leaf polyline.
+ *
+ * To reuse the merging/collapsing designed for internal nodes, the function
+ * treats a leaf as if it were an internal node. A list of temporary nodes is
+ * thus created, containing not only the leaf node but also its “children”
+ * i.e., its lines.
+ *
+ * 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)
+{
+ 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;
+
+ size_t nnodes = 0;
+ unsigned nlines = 0; /* Number of lines in the 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);
+
+ /* Compute the number of lines of the leaf */
+ nlines = size_t_to_unsigned(leaf->range[1] - leaf->range[0] + 1/*inclusive*/);
+ ASSERT(nlines > 1); /* Assume there is more than one line per leaf */
+
+ nnodes = nlines + 1/*leaf*/;
+
+ /* 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);
+ 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))
+
+ /* 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 */
+ NODE(0)->offset = 1;
+ NODE(0)->range[0] = leaf->range[0];
+ NODE(0)->range[1] = leaf->range[1];
+
+ FOR_EACH(i, 0, nlines) {
+ size_t vertices_range[2] = {0, 0}; /* Range in the vertex buffer */
+ const size_t ichild = NODE(0)->offset + i; /* Index of the child */
+ 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);
+ 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);
+ if(res != RES_OK) goto error;
+
+ NODE(ichild)->ivertex = vertices_range[0];
+ NODE(ichild)->nvertices = ui64_to_ui32(vertices_range[1] - vertices_range[0] + 1);
+ NODE(ichild)->range[0] = iline;
+ NODE(ichild)->range[1] = iline;
+ }
+
+ /* 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);
+ } else {
+ res = merge_child_polylines(tree, 0, nlines, &nodes, &vertices);
+ }
+ if(res != RES_OK) goto error;
+
+ /* Setup the leaf */
+ leaf->ivertex = darray_vertex_size_get(&tree->vertices);
+ leaf->nvertices = NODE(0/*leaf*/)->nvertices;
+
+ /* Copy the leaf vertices from temporary buffer to the vertex buffer of the
+ * 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;
+ dst = darray_vertex_data_get(&tree->vertices) + leaf->ivertex;
+ memsz = leaf->nvertices * sizeof(*src);
+ memcpy(dst, src, memsz);
+
+ #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)
+{
+ size_t nlines = 0; /* Number of lines in the leaf */
+ ASSERT(tree && leaf);
+
+ nlines = leaf->range[1] - leaf->range[0] + 1;
+
+ if(nlines == 1) {
+ return build_leaf_polyline_from_1line(tree, leaf);
+ } else {
+ return build_leaf_polyline_from_Nlines(tree, leaf);
+ }
+}
+
static INLINE double
eval_ka
- (const struct sln_tree* tree,
- const struct sln_node* node,
+ (const struct sln_node* node,
+ const struct sln_vertex* vertices,
const double wavenumber)
{
struct sln_mesh mesh = SLN_MESH_NULL;
double ka = 0;
- ASSERT(tree && node);
+ ASSERT(node && vertices);
/* Whether the mesh to be constructed corresponds to the spectrum or its upper
* limit, use the node mesh to calculate the value of ka at a given wave
* number. Calculating the value from the node lines would take far too long*/
- SLN(node_get_mesh(tree, node, &mesh));
+ mesh.vertices = vertices + node->ivertex;
+ mesh.nvertices = node->nvertices;
ka = sln_mesh_eval(&mesh, wavenumber);
-
return ka;
}
/* Merge all child polylines in a single step. The polylines are merged before
* being decimated */
-static res_T
+res_T
merge_child_polylines
(struct sln_tree* tree,
- const size_t inode)
+ const size_t inode,
+ const unsigned nchildren,
+ struct darray_node* nodes,
+ struct darray_vertex* vertex_list)
{
/* Helper constant */
static const size_t NO_MORE_VERTEX = SIZE_MAX;
/* Polyline vertices */
- size_t children_ivtx[SLN_TREE_ARITY_MAX] = {0};
+ #define NCHILDREN_MAX \
+ ( SLN_TREE_ARITY_MAX > SLN_LEAF_NLINES_MAX \
+ ? SLN_TREE_ARITY_MAX : SLN_LEAF_NLINES_MAX)
+ size_t children_ivtx[NCHILDREN_MAX] = {0};
+
size_t vertices_range[2] = {0,0};
struct sln_vertex* vertices = NULL;
size_t ivtx = 0;
size_t nvertices = 0;
/* Miscellaneous */
- size_t nchildren = 0;
unsigned i = 0;
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))
+ ASSERT(tree && inode < darray_node_size_get(nodes));
+ ASSERT(nchildren >= 2 && nchildren <= NCHILDREN_MAX);
- nchildren = node_child_count(tree, inode, NULL);
+ #define NODE(Id) (darray_node_data_get(nodes) + (Id))
/* Compute the number of vertices to be merged,
* i.e., the sum of vertices of the children */
@@ -127,16 +289,16 @@ merge_child_polylines
}
/* Define the vertices range of the merged polyline */
- vertices_range[0] = darray_vertex_size_get(&tree->vertices);
+ vertices_range[0] = darray_vertex_size_get(vertex_list);
vertices_range[1] = vertices_range[0] + nvertices - 1/*inclusive bound*/;
/* Allocate the memory space to store the new polyline */
- res = darray_vertex_resize(&tree->vertices, vertices_range[1]+1);
+ res = darray_vertex_resize(vertex_list, vertices_range[1]+1);
if(res != RES_OK) {
ERROR(tree->sln, "Error in merging polylines -- %s.\n", res_to_cstr(res));
goto error;
}
- vertices = darray_vertex_data_get(&tree->vertices);
+ vertices = darray_vertex_data_get(vertex_list);
/* Initialize the vertex index list. For each child, the initial value
* corresponds to the index of its first vertex. This index will be
@@ -176,7 +338,7 @@ merge_child_polylines
/* The wave number does not correspond to a vertex in the current
* child's mesh. Therefore, its contribution to the parent node's ka is
* computed */
- ka += eval_ka(tree, child, nu);
+ ka += eval_ka(child, vertices, nu);
} else {
/* The wave number is the one for which the child node stores a ka
@@ -206,7 +368,7 @@ merge_child_polylines
}
/* Decimate the resulting polyline */
- res = polyline_decimate(tree->sln, darray_vertex_data_get(&tree->vertices),
+ res = polyline_decimate(tree->sln, darray_vertex_data_get(vertex_list),
vertices_range, (float)tree->args.mesh_decimation_err, tree->args.mesh_type);
if(res != RES_OK) goto error;
@@ -230,9 +392,10 @@ merge_child_polylines
}
/* Shrink the size of the vertices */
- darray_vertex_resize(&tree->vertices, vertices_range[1] + 1);
+ darray_vertex_resize(vertex_list, vertices_range[1] + 1);
#undef NODE
+ #undef NCHILDREN_MAX
exit:
return res;
@@ -246,11 +409,17 @@ error:
static res_T
collapse_child_polylines
(struct sln_tree* tree,
+ const size_t inode,
+ const unsigned nchildren,
+ struct darray_node* nodes,
struct darray_vertex* scratch,
- const size_t inode)
+ struct darray_vertex* vertex_list)
{
/* Polylines to be collapsed, i.e., the ids of their first and last vertices */
- size_t poly_parts[SLN_TREE_ARITY_MAX][2] = {0};
+ #define NCHILDREN_MAX \
+ ( SLN_TREE_ARITY_MAX > SLN_LEAF_NLINES_MAX \
+ ? SLN_TREE_ARITY_MAX : SLN_LEAF_NLINES_MAX)
+ size_t poly_parts[NCHILDREN_MAX][2] = {0};
size_t nparts;
/* Indices of the first and last vertices of the resulting polyline.
@@ -265,20 +434,16 @@ collapse_child_polylines
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))
+ ASSERT(tree && inode < darray_node_size_get(nodes));
+ ASSERT(nchildren >= 2 && nchildren <= NCHILDREN_MAX);
- nchildren = node_child_count(tree, inode, NULL);
+ #define NODE(Id) (darray_node_data_get(nodes) + (Id))
/* Compute the number of vertices to be merged,
* i.e., the sum of vertices of the children */
@@ -289,7 +454,7 @@ collapse_child_polylines
}
/* Define the vertices range of the merged polyline */
- vertices_range[0] = darray_vertex_size_get(&tree->vertices);
+ vertices_range[0] = darray_vertex_size_get(vertex_list);
vertices_range[1] = vertices_range[0] + nvertices - 1/*inclusive bound*/;
/* Allocate the memory space required to store the new polyline and the
@@ -297,14 +462,14 @@ collapse_child_polylines
* 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
+ if((res = darray_vertex_resize(vertex_list, 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);
+ vertices = darray_vertex_data_get(vertex_list);
/* Recover the memory space to be used in the Redux process.
*
@@ -489,8 +654,9 @@ collapse_child_polylines
}
/* Shrink the size of the vertices */
- darray_vertex_resize(&tree->vertices, vertices_range[1] + 1);
+ darray_vertex_resize(vertex_list, vertices_range[1] + 1);
+ #undef NCHILDREN
#undef NODE
exit:
@@ -546,7 +712,8 @@ build_polylines(struct sln_tree* tree)
} else {
const size_t ichild0 = inode + NODE(inode)->offset + 0;
- const size_t nchildren = node_child_count(tree, inode, NULL);
+ const struct sln_node* node = darray_node_cdata_get(&tree->nodes)+inode;
+ const unsigned nchildren = node_child_count(node, tree->args.arity, NULL);
size_t i = 0;
/* Child nodes have their polyline created */
@@ -558,11 +725,12 @@ build_polylines(struct sln_tree* tree)
ASSERT(NODE(ichild)->nvertices != 0);
}
#endif
-
if(tree->args.collapse_polylines) {
- res = collapse_child_polylines(tree, &scratch, inode);
+ res = collapse_child_polylines
+ (tree, inode, nchildren, &tree->nodes, &scratch, &tree->vertices);
} else {
- res = merge_child_polylines(tree, inode);
+ res = merge_child_polylines
+ (tree, inode, nchildren, &tree->nodes, &tree->vertices);
}
if(res != RES_OK) goto error;
@@ -665,7 +833,7 @@ partition_lines(struct sln_tree* tree)
nlines = NODE(inode)->range[1] - NODE(inode)->range[0] + 1;
/* Make a leaf */
- if(nlines <= MAX_NLINES_PER_LEAF) {
+ if(nlines <= tree->args.leaf_nlines) {
int pcent = 0;
NODE(inode)->offset = 0;
@@ -688,13 +856,14 @@ partition_lines(struct sln_tree* tree)
size_t nchildren = 0;
size_t i = 0;
- /* Compute how the lines of a node are distributed among its children,
- * as well as the number of children that node has */
- nchildren = node_child_count(tree, inode, &nlines_per_child);
-
/* Calculate the index of the first child */
size_t ichildren = darray_node_size_get(&tree->nodes);
+ /* Compute how the lines of a node are distributed among its children,
+ * as well as the number of children that node has */
+ nchildren = node_child_count(darray_node_cdata_get(&tree->nodes)+inode,
+ tree->args.arity, &nlines_per_child);
+
ASSERT(nchildren <= tree->args.arity);
ASSERT(ichildren > inode);
diff --git a/src/sln_tree_c.h b/src/sln_tree_c.h
@@ -25,9 +25,6 @@
#include <rsys/dynamic_array.h>
#include <rsys/ref_count.h>
-/* Maximum number of lines per leaf */
-#define MAX_NLINES_PER_LEAF 1
-
/* Current version of the serialized tree data. One should increment it and
* perform a version management onto serialized tree when these data are
* updated. */
@@ -76,8 +73,8 @@ tree_build
/* Assume that the node is an internal node */
extern LOCAL_SYM unsigned
node_child_count
- (const struct sln_tree* tree,
- const size_t inode,
+ (const struct sln_node* node,
+ const unsigned tree_arity,
size_t* out_nlines_per_child); /* Max #lines per child. May be NULL */
#endif /* SLN_TREE_C_H */
diff --git a/src/test_sln_tree.c b/src/test_sln_tree.c
@@ -105,7 +105,7 @@ check_tree_lines
unsigned i = 0;
unsigned n = sln_node_get_child_count(tree, node);
- CHK(sln_node_get_line_count(node) > desc.max_nlines_per_leaf);
+ CHK(sln_node_get_line_count(node) > desc.leaf_nlines);
FOR_EACH(i, 1, n) {
stack[istack++] = sln_node_get_child(tree, node, i);
@@ -116,7 +116,7 @@ check_tree_lines
size_t iline, nlines;
nlines = sln_node_get_line_count(node);
- CHK(nlines <= desc.max_nlines_per_leaf);
+ CHK(nlines <= desc.leaf_nlines);
FOR_EACH(iline, 0, nlines) {
struct shtr_line line = SHTR_LINE_NULL;
size_t found_iline = 0;
@@ -203,7 +203,7 @@ check_tree_equality
CHK(sln_tree_get_desc(tree1, &desc1) == RES_OK);
CHK(sln_tree_get_desc(tree2, &desc2) == RES_OK);
- CHK(desc1.max_nlines_per_leaf == desc2.max_nlines_per_leaf);
+ CHK(desc1.leaf_nlines == desc2.leaf_nlines);
CHK(desc1.mesh_decimation_err == desc2.mesh_decimation_err);
CHK(desc1.mesh_type == desc2.mesh_type);
CHK(desc1.line_profile == desc2.line_profile);
@@ -258,6 +258,8 @@ test_tree
const struct sln_node* node = NULL;
struct shtr_line line = SHTR_LINE_NULL;
size_t nlines = 0;
+ size_t nleaf = 0;
+ unsigned depth = 0;
CHK(sln && tree_args_in && line_list);
tree_args = *tree_args_in;
@@ -273,15 +275,18 @@ test_tree
CHK(sln_tree_get_desc(tree, NULL) == RES_BAD_ARG);
CHK(sln_tree_get_desc(tree, &desc) == RES_OK);
- CHK(desc.max_nlines_per_leaf >= 1);
+ CHK(desc.leaf_nlines >= 1);
CHK(desc.mesh_decimation_err == tree_args.mesh_decimation_err);
CHK(desc.mesh_type == tree_args.mesh_type);
CHK(desc.line_profile == tree_args.line_profile);
CHK(desc.nlines == nlines);
CHK(desc.nvertices >= 1);
CHK(desc.nnodes >= 1);
- CHK(desc.depth
- == (unsigned)ceil(log((double)desc.nlines)/log((double)desc.arity)));
+
+ nleaf = (desc.nlines + desc.leaf_nlines-1/*ceil*/)/ desc.leaf_nlines;
+ depth = (unsigned)ceil(log((double)nleaf)/log((double)desc.arity));
+ CHK(desc.depth == depth);
+
CHK(desc.pressure == tree_args.pressure);
CHK(desc.temperature == tree_args.temperature);
CHK(desc.arity == tree_args.arity);
@@ -320,10 +325,10 @@ test_tree
}
CHK(sln_node_get_child_count(tree, node) == 0);
- CHK(sln_node_get_line_count(node) <= desc.max_nlines_per_leaf);
+ CHK(sln_node_get_line_count(node) <= desc.leaf_nlines);
CHK(sln_node_get_line(NULL, node, 0, &line) == RES_BAD_ARG);
CHK(sln_node_get_line(tree, NULL, 0, &line) == RES_BAD_ARG);
- CHK(sln_node_get_line(tree, node, desc.max_nlines_per_leaf+1, &line)
+ CHK(sln_node_get_line(tree, node, desc.leaf_nlines+1, &line)
== RES_BAD_ARG);
CHK(sln_node_get_line(tree, node, 0, NULL) == RES_BAD_ARG);
CHK(sln_node_get_line(tree, node, 0, &line) == RES_OK);
@@ -345,16 +350,28 @@ test_tree
tree_args.mesh_decimation_err = -1;
CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.mesh_decimation_err = SLN_TREE_CREATE_ARGS_DEFAULT.mesh_decimation_err;
- tree_args.mesh_decimation_err = 1e-1f;
tree_args.mesh_type = SLN_MESH_TYPES_COUNT__;
CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.mesh_type = SLN_TREE_CREATE_ARGS_DEFAULT.mesh_type;
- tree_args.mesh_type = SLN_MESH_FIT;
tree_args.line_profile = SLN_LINE_PROFILES_COUNT__;
CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.line_profile = SLN_TREE_CREATE_ARGS_DEFAULT.line_profile;
+
+ tree_args.arity = 1;
+ CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.arity = SLN_TREE_ARITY_MAX + 1;
+ CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.arity = SLN_TREE_CREATE_ARGS_DEFAULT.arity;
+
+ tree_args.leaf_nlines = 0;
+ CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.leaf_nlines = SLN_LEAF_NLINES_MAX + 1;
+ CHK(sln_tree_create(sln, &tree_args, &tree) == RES_BAD_ARG);
+ tree_args.leaf_nlines = SLN_TREE_CREATE_ARGS_DEFAULT.leaf_nlines;
- tree_args.line_profile = SLN_LINE_PROFILE_VOIGT;
CHK(sln_tree_create(sln, &tree_args, &tree) == RES_OK);
if(tree_args.arity == 2 && tree_args.collapse_polylines == 0) {
@@ -513,6 +530,23 @@ main(int argc, char** argv)
test_tree(sln, &tree_args, line_list);
test_tree_serialization(sln, &tree_args);
+ /* Test a tree where the number of rows per leaf is greater than 1 */
+ tree_args.arity = 4;
+ tree_args.leaf_nlines = 3;
+ tree_args.collapse_polylines = 0;
+ test_tree(sln, &tree_args, line_list);
+ test_tree_serialization(sln, &tree_args);
+
+ /* Test a tree in which the number of lines per leaf is greater than 1. The
+ * polylines for the leaves and internal nodes are created by reducing,
+ * respectively, the polyline of the leaf lines or those of the internal
+ * nodes' children */
+ tree_args.arity = 3;
+ tree_args.leaf_nlines = 6;
+ 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);
