commit a1f763b628c6b4439f8f539b50d75f1c155a3248
parent 6ab54cf71641413bb95e1f987021d0ee40d7aedd
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 2 Mar 2018 09:57:07 +0100
Add an optional filter function to the `at' accessor
Add a `is_leaf' and `depth' field to the htvox_voxel data structure.
Diffstat:
3 files changed, 68 insertions(+), 22 deletions(-)
diff --git a/src/htvox.h b/src/htvox.h
@@ -43,9 +43,11 @@
struct htvox_voxel {
const void* data; /* Data of the voxel */
size_t id; /* Indentifier of the voxel */
+ size_t depth; /* Depth of the voxel into the hierarchy */
+ int is_leaf; /* Define if the voxel is a leaf into the hierarchy */
};
-#define HTVOX_VOXEL_NULL__ { NULL, SIZE_MAX }
+#define HTVOX_VOXEL_NULL__ { NULL, SIZE_MAX, SIZE_MAX, 0 }
static const struct htvox_voxel HTVOX_VOXEL_NULL = HTVOX_VOXEL_NULL__;
#define HTVOX_VOXEL_NONE(Voxel) ((Voxel)->id == HTVOX_VOXEL_NULL.id)
@@ -93,7 +95,7 @@ struct htvox_octree_desc {
#define HTVOX_OCTREE_DESC_NULL__ \
{{DBL_MAX, DBL_MAX, DBL_MAX}, {-DBL_MAX,-DBL_MAX,-DBL_MAX}, 0, 0, 0}
-static const struct htvox_octree_desc HTVOX_OCTREE_DESC_NULL =
+static const struct htvox_octree_desc HTVOX_OCTREE_DESC_NULL =
HTVOX_OCTREE_DESC_NULL__;
struct htvox_hit {
@@ -182,6 +184,11 @@ HTVOX_API res_T
htvox_octree_at
(struct htvox_octree* octree,
const double position[3],
+ int (*filter) /* Filter function. May be NULL <=> traverse up to leaves */
+ (const struct htvox_voxel* voxel,
+ const double position[3],
+ void* ctx),
+ void* context, /* Client data sent as the last argument of the filter func */
struct htvox_voxel* voxel);
#endif /* HTVOX_H */
diff --git a/src/htvox_octree.c b/src/htvox_octree.c
@@ -85,6 +85,16 @@ check_octree(struct octree_buffer* buf, const struct octree_index root)
}
#endif
+static FINLINE size_t
+absolute_attr_index
+ (const struct octree_buffer* buf,
+ const struct octree_index index)
+{
+ ASSERT(buf);
+ return index.ipage * buf->pagesize/buf->voxsize + index.inode;
+
+}
+
static INLINE int
check_htvox_voxel_desc(const struct htvox_voxel_desc* desc)
{
@@ -545,7 +555,7 @@ htvox_octree_create
if(res != RES_OK) goto error;
oct->nleaves = bldr.nleaves;
- oct->depth = (size_t)(bldr.octree_depth - bldr.non_empty_lvl)
+ oct->depth = (size_t)(bldr.octree_depth - bldr.non_empty_lvl)
+ 1 /* leaf level */;
ASSERT(bldr.octree_depth > bldr.non_empty_lvl);
@@ -603,14 +613,11 @@ res_T
htvox_octree_get_desc
(const struct htvox_octree* oct, struct htvox_octree_desc* desc)
{
- size_t nvoxs_per_page;
if(!oct || !desc) return RES_BAD_ARG;
- nvoxs_per_page = oct->buffer.pagesize / oct->buffer.voxsize;
d3_set(desc->lower, oct->lower);
d3_set(desc->upper, oct->upper);
desc->nleaves = oct->nleaves;
- desc->nvoxels = oct->buffer.attr_head.ipage * nvoxs_per_page
- + oct->buffer.attr_head.inode
+ desc->nvoxels = absolute_attr_index(&oct->buffer, oct->buffer.attr_head)
+ 1; /* Root node */
desc->depth = oct->depth;
return RES_OK;
@@ -715,21 +722,32 @@ res_T
htvox_octree_at
(struct htvox_octree* oct,
const double position[3],
+ int (*filter) /* Filter function. May be NULL */
+ (const struct htvox_voxel* voxel,
+ const double position[3],
+ void* ctx),
+ void* context, /* Client data sent as the last argument of the filter func */
struct htvox_voxel* voxel)
{
struct octree_index inode;
+ struct htvox_voxel vox = HTVOX_VOXEL_NULL;
double scale_exp2;
double low[3];
double pos[3];
+ res_T res = RES_OK;
- if(!oct || !position || !voxel) return RES_BAD_ARG;
+ if(!oct || !position || !voxel) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
*voxel = HTVOX_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]) {
- return RES_OK;
+ goto exit;
}
/* Transform the position in the normalized octree space,
@@ -743,15 +761,25 @@ htvox_octree_at
low[1] = 0;
low[2] = 0;
+ /* Root voxel */
+ vox.depth = 0;
+ vox.is_leaf = 0;
+ if(filter) {
+ vox.data = oct->root_attr;
+ vox.id = 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;
- *voxel = HTVOX_VOXEL_NULL;
for(;;) {
struct octree_xnode* node = octree_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;
@@ -765,19 +793,28 @@ htvox_octree_at
if(pos[2] > mid[2]) { ichild |= 1; low[2] = mid[2]; }
ichild_flag = (uint8_t)BIT(ichild);
- if((node->is_valid & ichild_flag) == 0) { /* Empty node */
- break;
- } else if(node->is_leaf & ichild_flag) { /* Leaf node */
+ if((node->is_valid & ichild_flag) == 0) break; /* Empty node */
+
+ vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
+ if(filter || vox.is_leaf) {
inode = octree_buffer_get_child_attr_index(&oct->buffer, inode, ichild);
- voxel->data = octree_buffer_get_attr(&oct->buffer, inode);
- voxel->id = inode.ipage * oct->buffer.pagesize / oct->buffer.voxsize
- + inode.inode;
- break;
- } else { /* Child node */
- inode = octree_buffer_get_child_node_index(&oct->buffer, inode, ichild);
- scale_exp2 *= 0.5;
+ vox.data = octree_buffer_get_attr(&oct->buffer, inode);
+ vox.id = absolute_attr_index(&oct->buffer, inode);
+ vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
+ if(vox.is_leaf || !filter(&vox, position, context)) {
+ ++vox.depth;
+ *voxel = vox;
+ break;
+ }
}
+
+ inode = octree_buffer_get_child_node_index(&oct->buffer, inode, ichild);
+ scale_exp2 *= 0.5;
}
- return RES_OK;
+
+exit:
+ return res;
+error:
+ goto exit;
}
diff --git a/src/test_htvox_octree.c b/src/test_htvox_octree.c
@@ -347,11 +347,13 @@ main(int argc, char** argv)
ui3[1] = (uint32_t)y;
ui3[2] = (uint32_t)z;
- CHK(htvox_octree_at(oct, pos, &vox) == RES_OK);
+ CHK(htvox_octree_at(oct, pos, NULL, NULL, &vox) == RES_OK);
CHK(!HTVOX_VOXEL_NONE(&vox));
mcode = morton_xyz_encode_u21(ui3);
CHK(*((double*)vox.data) == mcode);
+ CHK(vox.is_leaf == 1);
+ CHK(vox.depth == octdesc.depth);
}
}
}
