commit 3e141ddbc625bc5d3a0958d60d6586dbfb8f1dc6
parent 887b3e5faa0f439eb5b3eb57f15364819fb2a25a
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 4 May 2018 15:31:03 +0200
Rename the svx_octree_at function
Make it generic to the tree dimension. It is thus renamed in svx_tree_at
and can be invoked on both bintree and octree.
Diffstat:
5 files changed, 127 insertions(+), 195 deletions(-)
diff --git a/src/svx.h b/src/svx.h
@@ -253,7 +253,7 @@ svx_octree_trace_ray
struct svx_hit* hit);
SVX_API res_T
-svx_octree_at
+svx_tree_at
(struct svx_tree* octree,
const double position[3],
svx_at_filter_T filter,
diff --git a/src/svx_octree.c b/src/svx_octree.c
@@ -169,196 +169,4 @@ error:
goto exit;
}
-#if 0
-res_T
-svx_octree_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[3];
- double hsz[3]; /* Half size */
- } stack[TREE_DEPTH_MAX*8];
- int istack;
- struct svx_voxel leaf = SVX_VOXEL_NULL;
- size_t ileaf = 0;
-
- if(!oct || !func || oct->type != SVX_OCTREE) return RES_BAD_ARG;
-
- stack[0].depth = 0;
- stack[0].inode = oct->root;
- stack[0].low[0] = oct->tree_low[0];
- stack[0].low[1] = oct->tree_low[1];
- stack[0].low[2] = oct->tree_low[2];
- stack[0].hsz[0] = (oct->tree_upp[0] - oct->tree_low[0])*0.5;
- stack[0].hsz[1] = (oct->tree_upp[1] - oct->tree_low[1])*0.5;
- stack[0].hsz[2] = (oct->tree_upp[2] - oct->tree_low[2])*0.5;
- istack = 1;
-
- do {
- const struct stack_entry entry = stack[--istack];
- const size_t child_depth = entry.depth + 1;
- double child_hsz[3];
- double mid[3]; /* Middle point of the current node */
- struct buffer_xnode* node;
- int ichild;
-
- node = buffer_get_node(&oct->buffer, entry.inode);
-
- mid[0] = entry.low[0] + entry.hsz[0];
- mid[1] = entry.low[1] + entry.hsz[1];
- mid[2] = entry.low[2] + entry.hsz[2];
- child_hsz[0] = entry.hsz[0] * 0.5;
- child_hsz[1] = entry.hsz[1] * 0.5;
- child_hsz[2] = entry.hsz[2] * 0.5;
-
- FOR_EACH(ichild, 0, 8) {
- const uint8_t ichild_flag = (uint8_t)BIT(ichild);
- double low[3];
-
- if((node->is_valid & ichild_flag) == 0) continue; /* Empty node */
-
- low[0] = ichild&4 ? mid[0] : entry.low[0];
- low[1] = ichild&2 ? mid[1] : entry.low[1];
- low[2] = ichild&1 ? mid[2] : entry.low[2];
-
- if(node->is_leaf & ichild_flag) {
- struct buffer_index iattr;
-
- iattr = buffer_get_child_attr_index
- (&oct->buffer, entry.inode, ichild);
-
- d3_set(leaf.lower, low);
- d3_add(leaf.upper, low, entry.hsz);
- 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);
- d3_set(top->low, low);
- d3_set(top->hsz, child_hsz);
- top->depth = child_depth;
- ++istack;
- }
- }
- } while(istack);
-
- return RES_OK;
-}
-#endif
-
-res_T
-svx_octree_at
- (struct svx_tree* oct,
- const double position[3],
- svx_at_filter_T filter,
- void* context,
- struct svx_voxel* voxel)
-{
- struct buffer_index inode;
- struct buffer_index iattr;
- struct svx_voxel vox = SVX_VOXEL_NULL;
- double scale_exp2;
- double low[3];
- double pos[3];
- res_T res = RES_OK;
-
- if(!oct || !position || !voxel || oct->type != SVX_OCTREE) {
- res = RES_BAD_ARG;
- goto error;
- }
-
- *voxel = SVX_VOXEL_NULL;
-
- /* The position is outside the octree */
- if(position[0] > oct->upper[0] || position[0] < oct->lower[0]
- || position[1] > oct->upper[1] || position[1] < oct->lower[1]
- || position[2] > oct->upper[2] || position[2] < oct->lower[2]) {
- goto exit;
- }
-
- /* Transform the position in the normalized octree space,
- * i.e. octree lies in [0, 1]^2 */
- pos[0] = (position[0] - oct->tree_low[0]) / oct->tree_size[0];
- pos[1] = (position[1] - oct->tree_low[1]) / oct->tree_size[1];
- pos[2] = (position[2] - oct->tree_low[2]) / oct->tree_size[2];
-
- /* Initialized the lower left corner of the current node */
- low[0] = 0;
- low[1] = 0;
- low[2] = 0;
-
- /* Root voxel */
- vox.depth = 0;
- vox.is_leaf = 0;
- d3_set(vox.lower, oct->lower);
- d3_set(vox.upper, oct->upper);
- if(filter) {
- vox.data = oct->root_attr;
- vox.id = buffer_absolute_attr_index(&oct->buffer, oct->buffer.attr_head);
- if(!filter(&vox, position, context)) { *voxel = vox; goto exit; }
- }
-
- scale_exp2 = 0.5;
- inode = oct->root;
- for(;;) {
- struct buffer_xnode* node = buffer_get_node(&oct->buffer, inode);
- int ichild;
- uint8_t ichild_flag;
- double mid[3];
-
- ++vox.depth;
-
- /* Compute the middle point of the node */
- mid[0] = low[0] + scale_exp2;
- mid[1] = low[1] + scale_exp2;
- mid[2] = low[2] + scale_exp2;
-
- /* Define the child of the current node into which pos `lies' and compute
- * its lower left corner */
- ichild = 0;
- if(pos[0] > mid[0]) { ichild |= 4; low[0] = mid[0]; }
- if(pos[1] > mid[1]) { ichild |= 2; low[1] = mid[1]; }
- if(pos[2] > mid[2]) { ichild |= 1; low[2] = mid[2]; }
-
- ichild_flag = (uint8_t)BIT(ichild);
- if((node->is_valid & ichild_flag) == 0) break; /* Empty node */
-
- vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
- if(filter || vox.is_leaf) {
- iattr = buffer_get_child_attr_index(&oct->buffer, inode, ichild);
-
- /* Setup the voxel */
- vox.lower[0] = low[0] * oct->tree_size[0] + oct->tree_low[0];
- vox.lower[1] = low[1] * oct->tree_size[1] + oct->tree_low[1];
- vox.lower[2] = low[2] * oct->tree_size[2] + oct->tree_low[2];
- vox.upper[0] = vox.lower[0] + oct->tree_size[0] * scale_exp2;
- vox.upper[1] = vox.lower[1] + oct->tree_size[1] * scale_exp2;
- vox.upper[2] = vox.lower[2] + oct->tree_size[2] * scale_exp2;
- vox.data = buffer_get_attr(&oct->buffer, iattr);
- vox.id = buffer_absolute_attr_index(&oct->buffer, iattr);
- vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
-
- if(vox.is_leaf || !filter(&vox, position, context)) {
- *voxel = vox;
- break;
- }
- }
-
- inode = buffer_get_child_node_index(&oct->buffer, inode, ichild);
- scale_exp2 *= 0.5;
- }
-
-exit:
- return res;
-error:
- goto exit;
-}
diff --git a/src/svx_tree.c b/src/svx_tree.c
@@ -82,7 +82,7 @@ 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;
+ if(!tree) 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;
@@ -91,6 +91,24 @@ svx_tree_for_each_leaf(struct svx_tree* tree, svx_leaf_function_T func, void* ct
return res;
}
+res_T
+svx_tree_at
+ (struct svx_tree* tree,
+ const double pos[3],
+ svx_at_filter_T filter,
+ void* context,
+ struct svx_voxel* vox)
+{
+ res_T res = RES_OK;
+ if(!tree) return RES_BAD_ARG;
+ switch(tree->type){
+ case SVX_BINTREE: res = bintree_at(tree, pos, filter, context, vox); break;
+ case SVX_OCTREE: res = octree_at(tree, pos, filter, context, vox); 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
@@ -128,6 +128,112 @@ TREE_FUNC(for_each_leaf)
return RES_OK;
}
+static res_T
+TREE_FUNC(at)
+ (struct svx_tree* tree,
+ const double position[3],
+ svx_at_filter_T filter,
+ void* context,
+ struct svx_voxel* voxel)
+{
+ struct buffer_index inode;
+ struct buffer_index iattr;
+ struct svx_voxel vox = SVX_VOXEL_NULL;
+ double scale_exp2;
+ double low[TREE_DIMENSION];
+ double pos[TREE_DIMENSION];
+ int i;
+ res_T res = RES_OK;
+
+ if(!tree || !position || !voxel || tree->type != SVX_TREE_TYPE) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ *voxel = SVX_VOXEL_NULL;
+
+ /* The position is outside the octree */
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ if(position[tree->frame[i]] > tree->upper[tree->frame[i]]
+ || position[tree->frame[i]] < tree->lower[tree->frame[i]])
+ goto exit;
+ }
+
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ /* Transform the position in the normalized octree space,
+ * i.e. octree lies in [0, 1]^2 */
+ pos[i] = (position[tree->frame[i]] - tree->tree_low[tree->frame[i]])
+ / tree->tree_size[i];
+ /* Initialized the lower left corner of the current node */
+ low[i] = 0;
+ }
+
+ /* Root voxel */
+ vox.depth = 0;
+ vox.is_leaf = 0;
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ vox.lower[tree->frame[i]] = tree->lower[tree->frame[i]];
+ vox.upper[tree->frame[i]] = tree->upper[tree->frame[i]];
+ }
+ if(filter) {
+ vox.data = tree->root_attr;
+ vox.id = buffer_absolute_attr_index(&tree->buffer, tree->buffer.attr_head);
+ if(!filter(&vox, position, context)) { *voxel = vox; goto exit; }
+ }
+
+ scale_exp2 = 0.5;
+ inode = tree->root;
+ for(;;) {
+ struct buffer_xnode* node = buffer_get_node(&tree->buffer, inode);
+ int ichild;
+ uint8_t ichild_flag;
+ double mid[TREE_DIMENSION];
+
+ ++vox.depth;
+
+ /* Compute the middle point of the node */
+ FOR_EACH(i, 0, TREE_DIMENSION) mid[i] = low[i] + scale_exp2;
+
+ /* Define the child of the current node into which pos `lies' and compute
+ * its lower left corner */
+ ichild = 0;
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ if(pos[i] > mid[i]) { ichild |= BIT(TREE_DIMENSION-1-i); low[i] = mid[i]; }
+ }
+
+ ichild_flag = (uint8_t)BIT(ichild);
+ if((node->is_valid & ichild_flag) == 0) break; /* Empty node */
+
+ vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
+ if(filter || vox.is_leaf) {
+ iattr = buffer_get_child_attr_index(&tree->buffer, inode, ichild);
+
+ /* Setup the voxel */
+ FOR_EACH(i, 0, TREE_DIMENSION) {
+ const int iaxis = tree->frame[i];
+ vox.lower[iaxis] = low[i] * tree->tree_size[iaxis] + tree->tree_low[iaxis];
+ vox.upper[iaxis] = vox.lower[iaxis] + tree->tree_size[iaxis] * scale_exp2;
+ }
+ vox.data = buffer_get_attr(&tree->buffer, iattr);
+ vox.id = buffer_absolute_attr_index(&tree->buffer, iattr);
+ vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
+
+ if(vox.is_leaf || !filter(&vox, position, context)) {
+ *voxel = vox;
+ break;
+ }
+ }
+
+ inode = buffer_get_child_node_index(&tree->buffer, inode, ichild);
+ scale_exp2 *= 0.5;
+ }
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
#undef TREE_FUNC
#undef SVX_TREE_TYPE
#undef TREE_DIMENSION
diff --git a/src/test_svx_octree.c b/src/test_svx_octree.c
@@ -230,7 +230,7 @@ test_at_accessor(struct svx_tree* oct, const size_t nvoxels[3])
if(z*(1u<<iter) >= nvoxels[2]) break;
d3_set(ctx.position, pos);
- CHK(svx_octree_at(oct, pos, max_lod, &ctx, &vox) == RES_OK);
+ CHK(svx_tree_at(oct, pos, max_lod, &ctx, &vox) == RES_OK);
CHK(!SVX_VOXEL_NONE(&vox));
ui3[0] = (uint32_t)x * (1u << iter) + ((1u << iter) - 1);
