commit e52d051a5a3c9b5be7bb07258ce265af6e4c8dd4
parent 8d06f72773e62c5e259e5087b4ed0fb59bc94a35
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 9 Feb 2018 13:10:06 +0100
Draft of new memory layout and build algorithm of the octree
Diffstat:
4 files changed, 328 insertions(+), 211 deletions(-)
diff --git a/src/htvox_c.h b/src/htvox_c.h
@@ -44,6 +44,16 @@ morton3D_decode_u21(const uint64_t u64)
return (uint32_t)tmp;
}
+/* Count the number of bits set to 1 */
+static FINLINE int
+popcount(const uint8_t x)
+{
+ int n = x - ((x >> 1) & 0x55);
+ n = (n & 0x33) + ((n >> 2) & 0x33);
+ n = (n + (n >> 4)) & 0x0f;
+ return (n * 0x0101) >> 8;
+}
+
static INLINE uint64_t
morton_xyz_encode_u21(const uint32_t xyz[3])
{
diff --git a/src/htvox_octree_buffer.h b/src/htvox_octree_buffer.h
@@ -16,6 +16,7 @@
#ifndef HTVOX_OCTREE_BUFFER_H
#define HTVOX_OCTREE_BUFFER_H
+#include "htvox_c.h"
#include <rsys/dynamic_array.h>
/*
@@ -33,24 +34,22 @@
* aforementioned indexing procedure of the node children.
*/
-#define OCTREE_XNODE_FLAG_FAR_INDEX 0x80000000u
-#define OCTREE_XNODE_FLAG_LEAF 0x40000000u
-#define OCTREE_XNODE_FLAG_EMPTY 0x20000000u
-#define OCTREE_XNODE_MAX_CHILDREN_OFFSET (BIT(29)-1)
+#define OCTREE_XNODE_FLAG_FAR_INDEX (1u<<15)
+#define OCTREE_XNODE_MAX_CHILDREN_OFFSET (OCTREE_XNODE_FLAG_FAR_INDEX-1)
#define OCTREE_XNODE_MASK OCTREE_XNODE_MAX_CHILDREN_OFFSET
struct octree_xnode {
- /* Relative offset to retrieve the node children. If the
- * OCTREE_XNODE_FLAG_FAR_INDEX bit is not set, the node children are stored
- * `offset' nodes *before* the node. If OCTREE_XNODE_FLAG_FAR_INDEX is set,
- * the index toward the children are stored N bytes *after* the node with N
- * defined as : N = (offset & OCTREE_XNODE_MASK)*sizeof(struct octree_xnode).
- * Finally if the OCTREE_XNODE_EMPTY bit is set, then the node does not
- * contain anything and thus has no child. */
- uint32_t offset;
+ /* Relative offset to retrieve the children. If the
+ * OCTREE_XNODE_FLAG_FAR_INDEX bit is not set, the children are stored in the
+ * same page at the position `offset & OCTREE_XNODE_MASK'. If
+ * OCTREE_XNODE_FLAG_FAR_INDEX is set, `offset & OCTREE_XNODE_MASK' reference
+ * an octree_index toward the node children */
+ uint16_t node_offset;
+ uint16_t leaf_offset;
+ uint8_t is_valid; /* Mask defining if the children are valid */
+ uint8_t is_leaf; /* Mask defining if the children are leafs */
+ uint16_t dummy__; /* Ensure that the size of the node is 8 bytes */
};
-#define OCTREE_XNODE_IS_LEAF(N) (((N)->offset & OCTREE_XNODE_FLAG_LEAF)!=0)
-#define OCTREE_XNODE_IS_EMPTY(N) (((N)->offset & OCTREE_XNODE_FLAG_EMPTY)!=0)
#define OCTREE_INDEX_IPAGE_MAX UINT32_MAX
#define OCTREE_INDEX_INODE_MAX UINT16_MAX
@@ -169,22 +168,64 @@ octree_buffer_get_child_index
{
struct octree_index child_id = OCTREE_INDEX_NULL;
struct octree_xnode* node = NULL;
- uint32_t node_offset;
+ uint16_t offset;
+ const int ichild_flag = BIT(ichild);
+ int ichild_off;
+ uint8_t mask;
+
ASSERT(ichild >= 0 && ichild < 8 && buf);
node = octree_buffer_get_node(buf, id);
- if(node->offset & OCTREE_XNODE_FLAG_EMPTY) return OCTREE_INDEX_NULL;
- node_offset = (node->offset & OCTREE_XNODE_MASK);
+ mask = (uint8_t)(node->is_valid & ~node->is_leaf);
+ ASSERT(mask & ichild_flag);
+
+ /* Compute the child offset from the first child node */
+ ichild_off = popcount((uint8_t)((ichild_flag-1) & (int)mask));
- if(!(node->offset & OCTREE_XNODE_FLAG_FAR_INDEX)) {
+ offset = node->node_offset & OCTREE_XNODE_MASK;
+ if(!(node->node_offset & OCTREE_XNODE_FLAG_FAR_INDEX)) {
child_id.ipage = id.ipage;
- child_id.inode = (uint16_t)(id.inode - node_offset + (uint32_t)ichild);
+ child_id.inode = (uint16_t)(offset + ichild_off);
} else {
- child_id = *(struct octree_index*)
- ((char*)node + node_offset*sizeof(struct octree_xnode));
- child_id.inode = (uint16_t)(child_id.inode + ichild);
+ char* mem = darray_page_data_get(&buf->node_pages)[id.ipage];
+ child_id = *(struct octree_index*)(mem+offset*(sizeof(struct octree_xnode)));
+ child_id.inode = (uint16_t)(child_id.inode + ichild_off);
}
return child_id;
}
+static FINLINE struct octree_index
+octree_buffer_get_leaf_index
+ (struct octree_buffer* buf,
+ const struct octree_index id,
+ const int ileaf) /* In [0, 7] */
+{
+ struct octree_index leaf_id = OCTREE_INDEX_NULL;
+ struct octree_xnode* node = NULL;
+ uint16_t offset;
+ const int ileaf_flag = BIT(ileaf);
+ int ileaf_off;
+ uint8_t mask;
+
+ ASSERT(ileaf >= 0 && ileaf < 8 && buf);
+
+ node = octree_buffer_get_node(buf, id);
+ mask = node->is_valid & node->is_leaf;
+ ASSERT(mask & ileaf_flag);
+
+ /* Compute the leaf offset from the first leaf of the node */
+ ileaf_off = popcount((uint8_t)((ileaf_flag-1) & (int)mask));
+
+ offset = node->leaf_offset & OCTREE_XNODE_MASK;
+ if(!(node->leaf_offset & OCTREE_XNODE_FLAG_FAR_INDEX)) {
+ leaf_id.ipage = id.ipage;
+ leaf_id.inode = (uint16_t)(offset + ileaf_off);
+ } else {
+ char* mem = darray_page_data_get(&buf->node_pages)[id.ipage];
+ leaf_id = *(struct octree_index*)(mem+offset*(sizeof(struct octree_xnode)));
+ leaf_id.inode = (uint16_t)(leaf_id.inode + ileaf_off);
+ }
+ return leaf_id;
+}
+
#endif /* HTVOX_OCTREE_BUFFER_H */
diff --git a/src/htvox_scene.c b/src/htvox_scene.c
@@ -25,28 +25,32 @@
struct voxel {
uint64_t mcode; /* Morton code of the voxel */
- double data; /* Data of the voxel. -DBL_MAX == empty voxels */
+ double data; /* Data of the voxel */
};
-#define VOXEL_EMPTY_DATA -DBL_MAX
struct octree_node {
- struct octree_index ichildren; /* Index of the 1st child */
- uint8_t is_leaf; /* Define if the node is a leaf or not */
- double data; /* Data of the node */
+ struct octree_index ichild_node; /* Index of the 1st child node */
+ struct octree_index ichild_leaf; /* Index of the 1st child leaf */
+ uint8_t is_valid; /* Mask defining whether the children are valid or not */
+ uint8_t is_leaf; /* Mask defining whether the children are leaves or not */
+ double data[8]; /* Data of the leaves */
};
/* Stacked children of an octree node */
struct stack {
struct octree_node nodes[8]; /* List of registered children nodes */
- int len; /* Number of registered nodes in [0, 8[ */
+ uint8_t mask; /* Mask of valid children nodes (0 = empty) */
};
struct octree_builder {
struct stack stacks[OCTREE_DEPTH_MAX];
struct octree_buffer* buffer;
+
int (*merge)(const double min_val, const double max_val, void* ctx);
void* context; /* Client side data sent to the merge callback */
+
int octree_depth;
+
uint64_t mcode; /* Morton code of the last registered voxels */
size_t nvoxels; /* Number of voxels, i.e. leaves, */
};
@@ -59,19 +63,22 @@ static void
check_octree(struct octree_buffer* buf, const struct octree_index root)
{
const struct octree_xnode* node;
+ int ichild;
ASSERT(buf);
node = octree_buffer_get_node(buf, root);
- if(OCTREE_XNODE_IS_EMPTY(node)) {
- /* Do nothing */
- } else if(OCTREE_XNODE_IS_LEAF(node)) {
- struct octree_index ichild = octree_buffer_get_child_index(buf, root, 0);
- ASSERT(octree_buffer_get_leaf(buf, ichild) != NULL);
- } else {
- int i;
- FOR_EACH(i, 0, 8) { /* The octree is not sparse */
- struct octree_index ichild = octree_buffer_get_child_index(buf, root, i);
- check_octree(buf, ichild);
+ FOR_EACH(ichild, 0, 8) {
+ const int ichild_flag = BIT(ichild);
+ if((node->is_valid & ichild_flag) == 0) continue;
+
+ if(node->is_leaf & ichild_flag) {
+ struct octree_index leaf;
+ leaf = octree_buffer_get_leaf_index(buf, root, ichild);
+ ASSERT(octree_buffer_get_leaf(buf, leaf) != NULL);
+ } else {
+ struct octree_index child;
+ child = octree_buffer_get_child_index(buf, root, ichild);
+ check_octree(buf, child);
}
}
}
@@ -82,11 +89,16 @@ stack_clear(struct stack* stack)
{
int inode;
FOR_EACH(inode, 0, 8) {
+ int ileaf;
stack->nodes[inode].is_leaf = 0;
- stack->nodes[inode].data = 0;
- stack->nodes[inode].ichildren = OCTREE_INDEX_NULL;
+ stack->nodes[inode].is_valid = 0;
+ stack->nodes[inode].ichild_node = OCTREE_INDEX_NULL;
+ stack->nodes[inode].ichild_leaf = OCTREE_INDEX_NULL;
+ FOR_EACH(ileaf, 0, 8) {
+ stack->nodes[inode].data[ileaf] = 0;
+ }
}
- stack->len = 0;
+ stack->mask = 0;
}
/* Build a parent octree node from the registered stack nodes */
@@ -97,40 +109,40 @@ stack_setup_node
int (*merge_func)(const double min_val, const double max_val, void* ctx),
void* context)
{
- double data_min = DBL_MAX;
- double data_max =-DBL_MAX;
- int challenge_leaves_merging = 1;
int ichild;
- ASSERT(stack && node && stack->len == 8/*The octree is not sparse*/);
- ASSERT(merge_func);
+ ASSERT(stack && node && merge_func);
- node->ichildren = OCTREE_INDEX_NULL;
+ node->ichild_node = OCTREE_INDEX_NULL;
+ node->ichild_leaf = OCTREE_INDEX_NULL;
+ node->is_valid = stack->mask;
+ node->is_leaf = 0;
- /* Find the minimum and maximum of the children data */
- FOR_EACH(ichild, 0, 8) {
- if(!stack->nodes[ichild].is_leaf) { /* Could merge only leaf nodes */
- challenge_leaves_merging = 0;
- break;
- }
- data_min = MMIN(stack->nodes[ichild].data, data_min);
- data_max = MMAX(stack->nodes[ichild].data, data_max);
- }
+ if(stack->mask == 0) return; /* Empty stack */
- if(!challenge_leaves_merging) {
- node->is_leaf = 0;
- node->data = 0;
- } else {
- int merge = 0;
- if(data_min == VOXEL_EMPTY_DATA || data_max == VOXEL_EMPTY_DATA) {
- merge = data_min == data_max;
- } else {
- merge = merge_func(data_min, data_max, context);
+ /* Try to merge the child's leaves */
+ FOR_EACH(ichild, 0, 8) {
+ double data_min = DBL_MAX;
+ double data_max =-DBL_MAX;
+ struct octree_node* child = stack->nodes + ichild;
+ int ileaf;
+
+ /* Only child "full of leaves" can be merged */
+ if(child->is_leaf != 0xFF) continue;
+
+ /* Find the minimum and maximum of the leaves */
+ FOR_EACH(ileaf, 0, 8) {
+ data_min = MMIN(child->data[ileaf], data_min);
+ data_max = MMAX(child->data[ileaf], data_max);
}
- if(merge) {
- node->is_leaf = 1;
- node->data = data_max;
- /* Notify that the stacked nodes does not exist anymore: they are merged */
- stack->len = 0;
+ /* Challenge the merge function */
+ if(merge_func(data_min, data_max, context)) {
+ const uint8_t ichild_flag = (uint8_t)BIT(ichild);
+ node->data[ichild] = data_max;
+ node->is_leaf |= ichild_flag;
+
+ /* The node does not exist anymore in the stack since it became a leaf
+ * for its parent node */
+ stack->mask ^= ichild_flag;
}
}
}
@@ -143,77 +155,104 @@ stack_write
size_t* nvoxels) /* Number of written voxels */
{
struct octree_index nodes_id = OCTREE_INDEX_NULL;
+ struct octree_node* node = NULL;
size_t nvoxs = 0;
int inode;
res_T res = RES_OK;
ASSERT(stack && buffer && out_index && nvoxels);
- /* No registered nodes <=> nodes were merged in an higher level */
- if(!stack->len) goto exit;
+ /* No registered nodes, this means that the nodes were merged in an higher
+ * level */
+ if(!stack->mask) goto exit;
+
+ /* Write the leaves */
+ FOR_EACH(inode, 0, 8) {
+ size_t nleaves;
+ double* leaves;
+ size_t nvoxs_node;
+ int ileaf;
+
+ if((stack->mask & BIT(inode)) == 0) continue; /* Empty node */
- ASSERT(stack->len == 8/*legacy stack*/ || stack->len == 1/*root stack*/);
+ node = stack->nodes + inode;
+ if(!node->is_leaf) continue; /* No leaf */
+
+ nleaves = (size_t)popcount(node->is_leaf);
+
+ res = octree_buffer_alloc_leaves(buffer, nleaves, &node->ichild_leaf);
+ if(res != RES_OK) goto error;
+
+ leaves = octree_buffer_get_leaf(buffer, node->ichild_leaf);
+ nvoxs_node = 0;
+ FOR_EACH(ileaf, 0, 8) {
+ if(node->is_leaf & BIT(ileaf)) leaves[nvoxs_node++] = node->data[ileaf];
+ }
+ ASSERT(nvoxs_node == nleaves);
+ nvoxs += nleaves;
+ }
do {
struct octree_xnode* xnodes = NULL;
+ const size_t nnodes = (size_t)popcount(stack->mask);
+ size_t ixnode = 0;
/* Alloc the octree nodes */
- res = octree_buffer_alloc_nodes(buffer, (size_t)stack->len, &nodes_id);
+ res = octree_buffer_alloc_nodes(buffer, (size_t)nnodes, &nodes_id);
if(res != RES_OK) goto error;
xnodes = octree_buffer_get_node(buffer, nodes_id);
- nvoxs = 0;
- FOR_EACH(inode, 0, stack->len) {
- struct octree_node* node = stack->nodes + inode;
- size_t offset = SIZE_MAX;
-
- if(node->data == VOXEL_EMPTY_DATA) {
- xnodes[inode].offset = OCTREE_XNODE_FLAG_EMPTY;
- } else {
- if(node->is_leaf) {
- double* leaf;
-
- /* Alloc the leaf node */
- res = octree_buffer_alloc_leaves(buffer, 1, &node->ichildren);
- if(res != RES_OK) goto error;
+ FOR_EACH(inode, 0, 8) {
+ uint16_t leaf_offset = UINT16_MAX;
+ uint16_t node_offset = UINT16_MAX;
- /* Setup the leaf data */
- leaf = octree_buffer_get_leaf(buffer, node->ichildren);
- *leaf = node->data;
+ if((stack->mask & BIT(inode)) == 0) continue; /* Empty node */
+ node = stack->nodes + inode;
- nvoxs += 1;
+ /* Setup the offset toward the children */
+ if(node->is_valid & ~node->is_leaf) {
+ if(node->ichild_node.ipage == nodes_id.ipage) {
+ node_offset = node->ichild_node.inode;
}
+ /* Node offset is too high. Allocate a far index */
+ if(node_offset > OCTREE_XNODE_MAX_CHILDREN_OFFSET) {
+ struct octree_index index;
+ /* Not enough memory in the current page. The far index cannot be
+ * stored in the same page of its associated node. Stop the write
+ * process and rewrite the whole stacked nodes in a new page. */
+ res = octree_buffer_alloc_far_index(buffer, &index);
+ if(res != RES_OK) break;
- /* Define the offset toward the children of the current node */
- if(node->ichildren.ipage == nodes_id.ipage) {
- offset = (nodes_id.inode + (size_t)inode) - node->ichildren.inode;
+ *octree_buffer_get_far_index(buffer, index) = node->ichild_node;
+ node_offset = OCTREE_XNODE_FLAG_FAR_INDEX | index.inode;
}
+ }
- /* Offset is too high. Allocate a far index */
- if(offset > OCTREE_XNODE_MAX_CHILDREN_OFFSET) {
+ /* Setup the offset toward the leaves */
+ if(node->is_leaf) {
+ if(node->ichild_leaf.ipage == nodes_id.ipage) {
+ leaf_offset = node->ichild_leaf.inode;
+ }
+ /* Leaf offset is too high. Allocate a far index */
+ if(leaf_offset > OCTREE_XNODE_FLAG_FAR_INDEX) {
struct octree_index index;
- struct octree_index* far_id;
-
/* Not enough memory in the current page. The far index cannot be
- * stored relatively to its associated node. Stop the write process and
- * rewrite the whole stacked nodes in a new page. */
+ * stored in the same page of its associated node. Stop the write
+ * process and rewrite the whole stacked nodes in a new page. */
res = octree_buffer_alloc_far_index(buffer, &index);
- if(res != RES_OK) {
- break;
- }
- far_id = octree_buffer_get_far_index(buffer, index);
-
- *far_id = node->ichildren;
- offset = (index.inode - (nodes_id.inode + (size_t)inode));
- offset = offset | OCTREE_XNODE_FLAG_FAR_INDEX;
- }
+ if(res != RES_OK) break;
- if(node->is_leaf) {
- offset = offset | OCTREE_XNODE_FLAG_LEAF;
+ *octree_buffer_get_far_index(buffer, index) = node->ichild_leaf;
+ leaf_offset = OCTREE_XNODE_FLAG_FAR_INDEX | index.inode;
}
- xnodes[inode].offset = (uint32_t)offset;
}
+
+ xnodes[ixnode].node_offset = node_offset;
+ xnodes[ixnode].leaf_offset = leaf_offset;
+ xnodes[ixnode].is_valid = node->is_valid;
+ xnodes[ixnode].is_leaf = node->is_leaf;
+ ++ixnode;
}
- } while(inode < stack->len);
+ } while(inode < 8);
exit:
@@ -239,7 +278,7 @@ octree_builder_init
memset(bldr, 0, sizeof(struct octree_builder));
/* Compute the maximum depth of the octree */
- bldr->octree_depth = log2i((int)definition) + 1;
+ bldr->octree_depth = log2i((int)definition);
if(bldr->octree_depth > OCTREE_DEPTH_MAX) {
res = RES_MEM_ERR;
goto error;
@@ -268,6 +307,9 @@ octree_builder_add_voxel
const struct voxel* vox)
{
uint64_t mcode_xor;
+ int inode;
+ int ichild;
+ uint8_t ichild_flag;
res_T res = RES_OK;
ASSERT(bldr && vox && vox->mcode >= bldr->mcode);
@@ -279,46 +321,57 @@ octree_builder_add_voxel
if(mcode_xor >= 8) {
size_t ilvl;
+ inode = (bldr->mcode >> 3) & 7;
+ bldr->stacks[0].mask |= (uint8_t)BIT(inode);
+
/* Flush the stack of the octree level that does not contain the next
- * voxel. The last octree level is actually the root node. It contains all
- * the voxels and can be skipped */
- FOR_EACH(ilvl, 0, bldr->octree_depth-1/*The last level contain all voxels*/) {
+ * voxel. The last octree level is actually the level that contains the
+ * root node while the penultimate describes the root node itself. These 2
+ * levels contain all the voxels and can be skipped */
+ FOR_EACH(ilvl, 0, bldr->octree_depth-2/*The 2 last leaves contain all voxels*/) {
struct octree_node* stack_node;
size_t nvoxels;
uint64_t mcode_max_lvl;
/* Compute the maximum morton code value for the current octree level */
- mcode_max_lvl = 8lu/*#children*/ * (1lu<<(3*ilvl))/*#voxels per children*/;
+ mcode_max_lvl = 8lu/*#children*/ * (1lu<<(3*(ilvl+1)))/*#voxels per children*/;
if(mcode_xor < mcode_max_lvl) break;
- ASSERT(bldr->stacks[ilvl].len == 8); /* The octree is not sparse */
+
+ /* Retrieve the node index of the next level */
+ inode = (bldr->mcode >> (3*(ilvl+2))) & 7;
/* The next voxel is not in the ilvl^th stack. Setup the parent node of the
* nodes registered into the stack */
- stack_node = &bldr->stacks[ilvl+1].nodes[bldr->stacks[ilvl+1].len];
+ stack_node = &bldr->stacks[ilvl+1].nodes[inode];
stack_setup_node
(&bldr->stacks[ilvl], stack_node, bldr->merge, bldr->context);
- bldr->stacks[ilvl+1].len += 1;
- ASSERT(bldr->stacks[ilvl+1].len <= 8);
+ bldr->stacks[ilvl+1].mask |= (uint8_t)BIT(inode);
/* Write the nodes of the stack of the current octree level into the buf */
res = stack_write
- (&bldr->stacks[ilvl], bldr->buffer, &stack_node->ichildren, &nvoxels);
+ (&bldr->stacks[ilvl], bldr->buffer, &stack_node->ichild_node, &nvoxels);
if(res != RES_OK) goto error;
- bldr->nvoxels += nvoxels;
+ bldr->nvoxels += nvoxels; /* TODO remove this */
/* Reset the current stack */
stack_clear(&bldr->stacks[ilvl]);
}
}
+ /* Retrieve the index of the current voxel and of its parent */
+ ichild = vox->mcode & 7;
+ inode = (vox->mcode >> 3) & 7;
+ ichild_flag = (uint8_t)BIT(ichild);
+
/* Register the voxel */
+ bldr->stacks[0].nodes[inode].data[ichild] = vox->data;
+ bldr->stacks[0].nodes[inode].is_valid |= ichild_flag;
+ bldr->stacks[0].nodes[inode].is_leaf |= ichild_flag;
+
+ /* Update morton code of the last registered voxel */
bldr->mcode = vox->mcode;
- bldr->stacks[0].nodes[bldr->stacks[0].len].data = vox->data;
- bldr->stacks[0].nodes[bldr->stacks[0].len].ichildren = OCTREE_INDEX_NULL;
- bldr->stacks[0].nodes[bldr->stacks[0].len].is_leaf = 1;
- bldr->stacks[0].len += 1;
exit:
return res;
@@ -332,39 +385,43 @@ octree_builder_finalize
struct octree_index* root_id)
{
size_t nvoxels;
+ size_t inode;
int ilvl;
res_T res = RES_OK;
ASSERT(bldr);
+ inode = (bldr->mcode >> 3) & 7;
+ bldr->stacks[0].mask |= (uint8_t)BIT(inode);
+
/* Flush the stacked nodes */
FOR_EACH(ilvl, 0, bldr->octree_depth-1) {
struct octree_node* parent_node;
- ASSERT(bldr->stacks[ilvl+0].len == 8);
- ASSERT(bldr->stacks[ilvl+1].len <= 7);
- /* Fetch the parent node */
- parent_node = &bldr->stacks[ilvl+1].nodes[bldr->stacks[ilvl+1].len];
+ if(bldr->stacks[ilvl].mask == 0) continue;
+
+ /* Retrieve the node index of the next level */
+ inode = (bldr->mcode >> (3*(ilvl+2))) & 7;
/* Setup the parent node of the nodes registered into the current stack */
+ parent_node = &bldr->stacks[ilvl+1].nodes[inode]; /* Fetch the parent node */
stack_setup_node
(&bldr->stacks[ilvl], parent_node, bldr->merge, bldr->context);
- bldr->stacks[ilvl+1].len += 1;
+ bldr->stacks[ilvl+1].mask |= (uint8_t)BIT(inode);
/* Write the stacked nodes of the current level */
res = stack_write
- (&bldr->stacks[ilvl], bldr->buffer, &parent_node->ichildren, &nvoxels);
+ (&bldr->stacks[ilvl], bldr->buffer, &parent_node->ichild_node, &nvoxels);
if(res != RES_OK) goto error;
- bldr->nvoxels += nvoxels;
+ bldr->nvoxels += nvoxels; /* TODO remove this */
}
- ASSERT(bldr->stacks[bldr->octree_depth-1].len == 1);
/* Write the root node */
ilvl = bldr->octree_depth-1; /* Root level */
res = stack_write(&bldr->stacks[ilvl], bldr->buffer, root_id, &nvoxels);
if(res != RES_OK) goto error;
- bldr->nvoxels += nvoxels;
+ bldr->nvoxels += nvoxels; /* TODO remove this */
exit:
return res;
@@ -401,7 +458,6 @@ htvox_scene_create
{
struct htvox_scene* scn = NULL;
double vox_sz[3]; /* World space size of a voxel */
- double vox_sz_max; /* Max voxel size */
struct octree_builder bldr;
uint64_t mcode_max;
uint64_t mcode;
@@ -443,7 +499,7 @@ htvox_scene_create
scn->dev = dev;
/* Compute the octree definition */
- scn->definition = MMAX(nvoxels[0], 1);
+ scn->definition = MMAX(nvoxels[0], 2);
scn->definition = MMAX(nvoxels[1], scn->definition);
scn->definition = MMAX(nvoxels[2], scn->definition);
scn->definition = round_up_pow2(scn->definition);
@@ -456,6 +512,7 @@ htvox_scene_create
mcode_max = scn->definition * scn->definition * scn->definition;
FOR_EACH(mcode, 0, mcode_max) {
struct voxel vox;
+ size_t xyz[3];
uint32_t ui3[3];
morton_xyz_decode_u21(mcode, ui3);
@@ -463,16 +520,14 @@ htvox_scene_create
/* Out of bound voxels */
if(ui3[0] >= nvoxels[0]
|| ui3[1] >= nvoxels[1]
- || ui3[2] >= nvoxels[2]) {
- vox.data = VOXEL_EMPTY_DATA;
- } else {
- /* Retrieve the voxel data from the caller */
- size_t xyz[3];
- xyz[0] = (size_t)ui3[0];
- xyz[1] = (size_t)ui3[1];
- xyz[2] = (size_t)ui3[2];
- get(xyz, &vox.data, context);
- }
+ || ui3[2] >= nvoxels[2])
+ continue;
+
+ /* Retrieve the voxel data from the caller */
+ xyz[0] = (size_t)ui3[0];
+ xyz[1] = (size_t)ui3[1];
+ xyz[2] = (size_t)ui3[2];
+ get(xyz, &vox.data, context);
vox.mcode = mcode;
/* Register the voxel against the octree */
@@ -567,7 +622,6 @@ htvox_scene_for_each_voxel
double upp[3];
} stack[OCTREE_DEPTH_MAX*8];
int istack;
- size_t ivoxel = 0;
if(!scn || !func) return RES_BAD_ARG;
@@ -583,30 +637,18 @@ htvox_scene_for_each_voxel
do {
const struct stack_entry entry = stack[--istack];
struct octree_xnode* node;
+ int ichild;
node = octree_buffer_get_node(&scn->buffer, entry.inode);
- if(OCTREE_XNODE_IS_LEAF(node)) {
- double val;
- struct octree_index ileaf;
-
- ileaf = octree_buffer_get_child_index(&scn->buffer, entry.inode, 0);
- val = *octree_buffer_get_leaf(&scn->buffer, ileaf);
-
- ASSERT(entry.upp[0] <= scn->upper[0]);
- ASSERT(entry.upp[1] <= scn->upper[1]);
- ASSERT(entry.upp[2] <= scn->upper[2]);
- ASSERT(entry.low[0] >= scn->lower[0]);
- ASSERT(entry.low[1] >= scn->lower[1]);
- ASSERT(entry.low[2] >= scn->lower[2]);
-
- func(val, ivoxel, entry.low, entry.upp, ctx);
- ++ivoxel;
-
- } else if(!OCTREE_XNODE_IS_EMPTY(node)) {
+ FOR_EACH(ichild, 0, 8) {
+ const uint8_t ichild_flag = (uint8_t)BIT(ichild);
double half_sz[3]; /* Half size of the current node */
double mid[3]; /* Middle point of the current node */
- int i;
+ double upp[3];
+ double low[3];
+
+ if((node->is_valid & ichild_flag) == 0) continue; /* Empty node */
half_sz[0] = (entry.upp[0] - entry.low[0])*0.5;
half_sz[1] = (entry.upp[1] - entry.low[1])*0.5;
@@ -614,17 +656,42 @@ htvox_scene_for_each_voxel
mid[0] = entry.low[0] + half_sz[0];
mid[1] = entry.low[1] + half_sz[1];
mid[2] = entry.low[2] + half_sz[2];
-
- /* Push the children */
- FOR_EACH(i, 0, 8) {
+ 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];
+ upp[0] = low[0] + half_sz[0];
+ upp[1] = low[1] + half_sz[1];
+ upp[2] = low[2] + half_sz[2];
+
+ if(node->is_leaf & ichild_flag) {
+ struct octree_index ileaf;
+ size_t ivoxel;
+ double val;
+
+ ileaf = octree_buffer_get_leaf_index(&scn->buffer, entry.inode, ichild);
+ val = *octree_buffer_get_leaf(&scn->buffer, ileaf);
+
+ ASSERT(upp[0] <= scn->upper[0]);
+ ASSERT(upp[1] <= scn->upper[1]);
+ ASSERT(upp[2] <= scn->upper[2]);
+ ASSERT(low[0] >= scn->lower[0]);
+ ASSERT(low[1] >= scn->lower[1]);
+ ASSERT(low[2] >= scn->lower[2]);
+
+ ivoxel =
+ ileaf.ipage * scn->buffer.pagesize / sizeof(double) + ileaf.inode;
+ func(val, ivoxel, low, upp, ctx);
+ } else {
struct stack_entry* top = stack + istack;
- top->inode = octree_buffer_get_child_index(&scn->buffer, entry.inode, i);
- top->low[0] = i&4 ? mid[0] : entry.low[0];
- top->low[1] = i&2 ? mid[1] : entry.low[1];
- top->low[2] = i&1 ? mid[2] : entry.low[2];
- top->upp[0] = top->low[0] + half_sz[0];
- top->upp[1] = top->low[1] + half_sz[1];
- top->upp[2] = top->low[2] + half_sz[2];
+
+ top->inode = octree_buffer_get_child_index
+ (&scn->buffer, entry.inode, ichild);
+ top->low[0] = low[0];
+ top->low[1] = low[1];
+ top->low[2] = low[2];
+ top->upp[0] = upp[0];
+ top->upp[1] = upp[1];
+ top->upp[2] = upp[2];
++istack;
}
}
@@ -667,40 +734,39 @@ htvox_scene_at
scale_exp2 = 0.5;
inode = scn->root;
- do {
+ *voxel = HTVOX_VOXEL_NULL;
+ for(;;) {
struct octree_xnode* node = octree_buffer_get_node(&scn->buffer, inode);
-
- if(OCTREE_XNODE_IS_LEAF(node)) { /* Reach a leaf */
- const size_t page_nvoxs = scn->buffer.pagesize/sizeof(double);
- struct octree_index ileaf;
-
- ileaf = octree_buffer_get_child_index(&scn->buffer, inode, 0);
- voxel->data = *octree_buffer_get_leaf(&scn->buffer, ileaf);
- voxel->id = ileaf.ipage * page_nvoxs + ileaf.inode;
-
- } else {
- double mid[3];
- int ichild = 0;
-
- ASSERT(!OCTREE_XNODE_IS_EMPTY(node));
-
- /* 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 */
- 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]; }
-
- /* Fetch the child node */
+ int ichild;
+ uint8_t ichild_flag;
+ double mid[3];
+
+ /* 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) { /* Empty node */
+ break;
+ } else if(node->is_leaf & ichild_flag) { /* Leaf node */
+ inode = octree_buffer_get_leaf_index(&scn->buffer, inode, ichild);
+ voxel->data = *octree_buffer_get_leaf(&scn->buffer, inode);
+ voxel->id =
+ inode.ipage * scn->buffer.pagesize / sizeof(double) + inode.inode;
+ break;
+ } else { /* Child node */
inode = octree_buffer_get_child_index(&scn->buffer, inode, ichild);
scale_exp2 *= 0.5;
}
- } while(HTVOX_VOXEL_NONE(voxel));
-
+ }
return RES_OK;
}
diff --git a/src/test_htvox_scene.c b/src/test_htvox_scene.c
@@ -302,7 +302,7 @@ main(int argc, char** argv)
CHK(htvox_scene_ref_put(scn) == RES_OK);
- nvxls[0] = nvxls[1] = nvxls[2] = 8;
+ nvxls[0] = nvxls[1] = nvxls[2] = 128;
CHK(NEW_SCN(dev, low, upp, nvxls, get, merge_level0, ptr, &scn) == RES_OK);
CHK(htvox_scene_get_voxels_count(scn, &nvoxels) == RES_OK);
CHK(nvoxels == nvxls[0]*nvxls[1]*nvxls[2] / 8);
