star-line

commit 51c5fbcab8cc14f428751617bf78b7e5f8801762
parent 25fde8e4d6c6fa72c4981c96fc435d49d875c1e0
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Tue,  7 Apr 2026 14:28:58 +0200

Addition of a tree arity-agnostic polylines building

The new function creates a polyline from a node regardless of the number
of its children, unlike the previous function, which assumed that a node
must have exactly two children.

Since the tree's arity cannot differ from 2, using this function results
in the same acceleration structure - down to the bit - as the one built
using the previous function. This serves as an initial validation of
this function, confirmed by the regression tests, which continue to
function as expected.

Note that the previous function is retained to simplify future testing
when the caller will be able to define an arity other than 2.

Diffstat:
M
src/sln_tree_build.c
 | 
98
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

1 file changed, 97 insertions(+), 1 deletion(-)
diff --git a/src/sln_tree_build.c b/src/sln_tree_build.c
@@ -465,6 +465,102 @@ error:
 }
 
 static res_T
+build_polylines2(struct sln_tree* tree)
+{
+  size_t stack[STACK_SIZE*2];
+  size_t istack = 0;
+  size_t inode = 0;
+  size_t nnodes_total = 0;
+  size_t nnodes_processed = 0;
+  int progress = 0;
+  res_T res = RES_OK;
+  ASSERT(tree);
+
+  #define LOG_MSG "Meshing: %3d%%\n"
+  #define NODE(Id) (darray_node_data_get(&tree->nodes) + (Id))
+  #define IS_LEAF(Id) (NODE(Id)->offset == 0)
+
+  nnodes_total = darray_node_size_get(&tree->nodes);
+
+  /* Print that nothing has been done yet */
+  INFO(tree->sln, LOG_MSG, progress);
+
+  /* Push back SIZE_MAX which, once pop up, will mark the end of recursion */
+  stack[istack++] = SIZE_MAX;
+
+  inode = 0; /* Root node */
+  while(inode != SIZE_MAX) {
+    const size_t istack_saved = istack;
+
+    if(IS_LEAF(inode)) {
+      res = build_leaf_polyline(tree, NODE(inode));
+      if(res != RES_OK) goto error;
+
+      inode = stack[--istack]; /* Pop the next node */
+
+    } else {
+      const size_t ichild0 = inode + NODE(inode)->offset + 0;
+      const size_t nchildren = node_child_count(tree, inode);
+      size_t i = 0;
+
+      /* Child nodes have their polyline created */
+      if(NODE(ichild0)->nvertices) {
+#ifndef NDEBUG
+        /* Check that all children have their polylines created */
+        FOR_EACH(i, 1, nchildren) {
+          const size_t ichild = inode + NODE(inode)->offset + i;
+          ASSERT(NODE(ichild)->nvertices != 0);
+        }
+#endif
+        res = merge_children_polylines(tree, inode);
+        if(res != RES_OK) goto error;
+        inode = stack[--istack]; /* Pop the next node */
+
+      /* Child nodes have NOT their polyline created */
+      } else {
+        ASSERT(istack < STACK_SIZE - (nchildren - 1/*ichild0*/ + 1/*inode*/));
+        stack[istack++] = inode; /* Push the current node */
+
+        /* Push the children except the 1st one */
+        FOR_EACH(i, 1, nchildren) {
+          const size_t ichild = inode + NODE(inode)->offset + i;
+          ASSERT(NODE(ichild)->nvertices == 0);
+          stack[istack++] = ichild;
+        }
+
+        /* Recursively build the polyline of the 1st child */
+        inode = ichild0;
+      }
+    }
+
+    /* Handle progression bar */
+    if(istack < istack_saved) {
+      int pcent = 0;
+
+      nnodes_processed += istack_saved - istack;
+      ASSERT(nnodes_processed <= nnodes_total);
+
+      /* Print progress update */
+      pcent = (int)((double)nnodes_processed*100.0/(double)nnodes_total+0.5);
+      if(pcent/10 > progress/10) {
+        progress = pcent;
+        INFO(tree->sln, LOG_MSG, progress);
+      }
+    }
+  }
+  ASSERT(nnodes_processed == nnodes_total);
+
+  #undef NODE
+  #undef IS_LEAF
+  #undef LOG_MSG
+
+exit:
+  return res;
+error:
+  goto exit;
+}
+
+static res_T
 partition_lines(struct sln_tree* tree)
 {
   size_t stack[STACK_SIZE];
@@ -702,7 +798,7 @@ tree_build(struct sln_tree* tree)
   res_T res = RES_OK;
 
   if((res = partition_lines2(tree)) != RES_OK) goto error;
-  if((res = build_polylines(tree)) != RES_OK) goto error;
+  if((res = build_polylines2(tree)) != RES_OK) goto error;
 
 exit:
   return res;