commit 887b3e5faa0f439eb5b3eb57f15364819fb2a25a
parent 885b0d3698d20224bd88a1bbbea9658265c5f57f
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 4 May 2018 15:08:29 +0200
Rename the svx_octree_for_each_leaf function
Make it generic to the tree dimension. Its name is thus
svx_tree_for_each_leaf and can be invoke on both octree and binary tree.
Diffstat:
8 files changed, 174 insertions(+), 6 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -51,7 +51,9 @@ set(SSOL_FILES_INC
svx_buffer.h
svx_device.h
svx_octree.h
- svx_tree.h)
+ svx_tree.h
+ svx_tree_builder.h
+ svx_tree_generic_func.h)
set(SSOL_FILES_INC_API
svx.h)
diff --git a/src/svx.h b/src/svx.h
@@ -236,7 +236,7 @@ svx_tree_get_desc
struct svx_tree_desc* desc);
SVX_API res_T
-svx_octree_for_each_leaf
+svx_tree_for_each_leaf
(struct svx_tree* tree,
svx_leaf_function_T functor,
void* context); /* Client data sent as the last argument of the functor */
diff --git a/src/svx_bintree.c b/src/svx_bintree.c
@@ -135,3 +135,4 @@ error:
goto exit;
}
+
diff --git a/src/svx_octree.c b/src/svx_octree.c
@@ -18,6 +18,7 @@
#include "svx_device.h"
#include "svx_tree.h"
#include "svx_tree_builder.h"
+#include "svx_tree_generic_func.h"
#include <rsys/double3.h>
#include <rsys/mem_allocator.h>
@@ -168,6 +169,7 @@ error:
goto exit;
}
+#if 0
res_T
svx_octree_for_each_leaf
(struct svx_tree* oct, svx_leaf_function_T func, void* ctx)
@@ -250,6 +252,7 @@ svx_octree_for_each_leaf
return RES_OK;
}
+#endif
res_T
svx_octree_at
diff --git a/src/svx_tree.c b/src/svx_tree.c
@@ -15,10 +15,19 @@
#include "svx_device.h"
#include "svx_tree.h"
+#include "svx_tree_generic_func.h"
#include <rsys/double3.h>
#include <rsys/mem_allocator.h>
+/* Generate the generic binary functions */
+#define TREE_DIMENSION 1
+#include "svx_tree_generic_func.h"
+
+/* Generate the generic octree functions */
+#define TREE_DIMENSION 3
+#include "svx_tree_generic_func.h"
+
/*******************************************************************************
* Helper function
******************************************************************************/
@@ -69,6 +78,19 @@ svx_tree_get_desc
return RES_OK;
}
+res_T
+svx_tree_for_each_leaf(struct svx_tree* tree, svx_leaf_function_T func, void* ctx)
+{
+ res_T res = RES_OK;
+ if(!tree || !func) return RES_BAD_ARG;
+ switch(tree->type) {
+ case SVX_BINTREE: res = bintree_for_each_leaf(tree, func, ctx); break;
+ case SVX_OCTREE: res = octree_for_each_leaf(tree, func, ctx); break;
+ default: FATAL("Unreachable code.\n"); break;
+ }
+ return res;
+}
+
/*******************************************************************************
* Local functions
******************************************************************************/
diff --git a/src/svx_tree_generic_func.h b/src/svx_tree_generic_func.h
@@ -0,0 +1,140 @@
+/* Copyright (C) 2018 Université Paul Sabatier, |Meso|Star>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef TREE_DIMENSION
+
+#ifndef SVX_TREE_GENERIC_FUNC_H
+#define SVX_TREE_GENERIC_FUNC_H
+
+#include "svx.h"
+#include "svx_tree.h"
+#include "svx_tree_builder.h" /* For the TREE_DEPTH_MAX constant */
+
+#endif /* SVX_TREE_GENERIC_FUNC_H */
+#else /*!TREE_DIMENSION */
+
+#ifdef COMPILER_GCC
+ #pragma GCC push_options
+ #pragma GCC optimize("unroll-loops")
+#endif
+
+#if TREE_DIMENSION == 1
+ #define TREE_FUNC(Func) CONCAT(bintree_, Func)
+ #define SVX_TREE_TYPE SVX_BINTREE
+#elif TREE_DIMENSION == 3
+ #define TREE_FUNC(Func) CONCAT(octree_, Func)
+ #define SVX_TREE_TYPE SVX_OCTREE
+#else
+ #error "Invalid TREE_DIMENSION value"
+#endif
+
+#define NCHILDREN BIT(TREE_DIMENSION)
+
+static res_T
+TREE_FUNC(for_each_leaf)
+ (struct svx_tree* oct, svx_leaf_function_T func, void* ctx)
+{
+ struct stack_entry {
+ struct buffer_index inode;
+ size_t depth;
+ double low[TREE_DIMENSION];
+ double hsz[TREE_DIMENSION]; /* Half size */
+ } stack[TREE_DEPTH_MAX*NCHILDREN];
+ int istack;
+ struct svx_voxel leaf = SVX_VOXEL_NULL;
+ size_t ileaf = 0;
+ int i;
+
+ if(!oct || !func || oct->type != SVX_TREE_TYPE) return RES_BAD_ARG;
+
+ stack[0].depth = 0;
+ stack[0].inode = oct->root;
+
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ stack[0].low[i] = oct->tree_low[oct->frame[i]];
+ stack[0].hsz[i] =
+ (oct->tree_upp[oct->frame[i]] - oct->tree_low[oct->frame[i]])*0.5;
+ }
+ istack = 1;
+
+ do {
+ const struct stack_entry entry = stack[--istack];
+ const size_t child_depth = entry.depth + 1;
+ double child_hsz[TREE_DIMENSION];
+ double mid[TREE_DIMENSION]; /* Middle point of the current node */
+ struct buffer_xnode* node;
+ int ichild;
+
+ node = buffer_get_node(&oct->buffer, entry.inode);
+
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ mid[i] = entry.low[i] + entry.hsz[i];
+ child_hsz[i] = entry.hsz[i] * 0.5;
+ }
+
+ FOR_EACH(ichild, 0, NCHILDREN) {
+ const uint8_t ichild_flag = (uint8_t)BIT(ichild);
+ double low[TREE_DIMENSION];
+
+ if((node->is_valid & ichild_flag) == 0) continue; /* Empty node */
+
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ low[i] = ichild & BIT(TREE_DIMENSION-1-i) ? mid[i] : entry.low[i];
+ }
+
+ if(node->is_leaf & ichild_flag) {
+ struct buffer_index iattr;
+
+ iattr = buffer_get_child_attr_index
+ (&oct->buffer, entry.inode, ichild);
+
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ leaf.lower[oct->frame[i]] = low[i];
+ leaf.upper[oct->frame[i]] = low[i] + entry.hsz[i];
+ }
+ leaf.data = buffer_get_attr(&oct->buffer, iattr);
+ leaf.id = buffer_absolute_attr_index(&oct->buffer, iattr);
+ leaf.depth = child_depth;
+ leaf.is_leaf = 1;
+
+ func(&leaf, ileaf++, ctx);
+ } else {
+ struct stack_entry* top = stack + istack;
+
+ top->inode = buffer_get_child_node_index
+ (&oct->buffer, entry.inode, ichild);
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ top->low[i] = low[i];
+ top->hsz[i] = child_hsz[i];
+ }
+ top->depth = child_depth;
+ ++istack;
+ }
+ }
+ } while(istack);
+
+ return RES_OK;
+}
+
+#undef TREE_FUNC
+#undef SVX_TREE_TYPE
+#undef TREE_DIMENSION
+#undef NCHILDREN
+
+#ifdef COMPILER_GCC
+ #pragma GCC pop_options
+#endif
+
+#endif /* !TREE_DIMENSION */
diff --git a/src/test_svx_octree.c b/src/test_svx_octree.c
@@ -337,7 +337,7 @@ main(int argc, char** argv)
CHK(NEW_SCN(dev, low, upp, nvxls, &voxdesc, &oct) == RES_OK);
- CHK(svx_octree_for_each_leaf(oct, check_leaves, &ctx) == RES_OK);
+ CHK(svx_tree_for_each_leaf(oct, check_leaves, &ctx) == RES_OK);
CHK(svx_tree_get_desc(NULL, &tree_desc) == RES_BAD_ARG);
CHK(svx_tree_get_desc(oct, NULL) == RES_BAD_ARG);
diff --git a/src/test_svx_utils.h b/src/test_svx_utils.h
@@ -107,12 +107,12 @@ dump_data
CHK(svx_tree_get_desc(tree, &desc) == RES_OK);
CHK(desc.type == SVX_OCTREE); /* FIXME currently only octree are supported */
fprintf(stream, "POINTS %lu float\n", (unsigned long)(desc.nleaves* 8));
- CHK(svx_octree_for_each_leaf(tree, write_leaf_vertices, stream) == RES_OK);
+ CHK(svx_tree_for_each_leaf(tree, write_leaf_vertices, stream) == RES_OK);
fprintf(stream, "CELLS %lu %lu\n",
(unsigned long)desc.nleaves,
(unsigned long)(desc.nleaves*(8/*#verts per leaf*/ + 1/*1st field of a cell*/)));
- CHK(svx_octree_for_each_leaf(tree, write_leaf_cells, stream) == RES_OK);
+ CHK(svx_tree_for_each_leaf(tree, write_leaf_cells, stream) == RES_OK);
fprintf(stream, "CELL_TYPES %lu\n", (unsigned long)desc.nleaves);
FOR_EACH(ileaf, 0, desc.nleaves) fprintf(stream, "11\n");
@@ -120,7 +120,7 @@ dump_data
fprintf(stream, "CELL_DATA %lu\n", (unsigned long)desc.nleaves);
fprintf(stream, "SCALARS K %s %lu\n", data_type_to_string(type), numcomps);
fprintf(stream, "LOOKUP_TABLE default\n");
- CHK(svx_octree_for_each_leaf(tree, write_leaf_data, stream) == RES_OK);
+ CHK(svx_tree_for_each_leaf(tree, write_leaf_data, stream) == RES_OK);
}
