commit 64f3f896e9cc64b5cba38b3eab62a74daaf3dc4f
parent 04c0417dd95581bf2ca158820db4aa277ed717f6
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Wed, 28 Feb 2018 15:14:03 +0100
Implement the LOD of attributes
Store the voxel attributes at each level of hierarchy
Diffstat:
5 files changed, 178 insertions(+), 181 deletions(-)
diff --git a/src/htvox_octree_buffer.c b/src/htvox_octree_buffer.c
@@ -35,6 +35,7 @@ ensure_allocated_nodes(struct octree_buffer* buf, const size_t nnodes)
goto exit;
nnode_pages = darray_page_size_get(&buf->node_pages);
+ if(nnode_pages > UINT32_MAX) { res = RES_MEM_ERR; goto error; }
ASSERT(nnode_pages == buf->node_head.ipage + 1);
/* Alloc and register a node page containing the node and the far indices */
@@ -43,7 +44,6 @@ ensure_allocated_nodes(struct octree_buffer* buf, const size_t nnodes)
res = darray_page_push_back(&buf->node_pages, &node_page);
if(res != RES_OK) goto error;
- ASSERT(nnode_pages <= UINT32_MAX);
buf->node_head.inode = 0;
buf->node_head.ipage = (uint32_t)nnode_pages;
@@ -56,35 +56,35 @@ error:
}
static INLINE res_T
-ensure_allocated_leaves(struct octree_buffer* buf, const size_t nleaves)
+ensure_allocated_attrs(struct octree_buffer* buf, const size_t nattrs)
{
- char* leaf_page = NULL;
- size_t nleaf_pages = 0;
+ char* attr_page = NULL;
+ size_t nattr_pages = 0;
res_T res = RES_OK;
ASSERT(buf);
- if(buf->leaf_head.ipage != OCTREE_INDEX_NULL.ipage
- && buf->leaf_head.inode + nleaves <= buf->pagesize/buf->voxsize)
+ if(buf->attr_head.ipage != OCTREE_INDEX_NULL.ipage
+ && buf->attr_head.inode + nattrs <= buf->pagesize/buf->voxsize)
goto exit;
- nleaf_pages = darray_page_size_get(&buf->leaf_pages);
- ASSERT(nleaf_pages == buf->leaf_head.ipage + 1);
+ nattr_pages = darray_page_size_get(&buf->attr_pages);
+ if(nattr_pages > UINT32_MAX) { res = RES_MEM_ERR; goto error; }
+ ASSERT(nattr_pages == buf->attr_head.ipage + 1);
- /* Alloc and register the leaf page containing the data of the leaves */
- leaf_page = MEM_ALLOC(buf->allocator, buf->pagesize);
- if(!leaf_page) { res = RES_MEM_ERR; goto error; }
- res = darray_page_push_back(&buf->leaf_pages, &leaf_page);
+ /* Alloc and register a attr page */
+ attr_page = MEM_ALLOC(buf->allocator, buf->pagesize);
+ if(!attr_page) { res = RES_MEM_ERR; goto error; }
+ res = darray_page_push_back(&buf->attr_pages, &attr_page);
if(res != RES_OK) goto error;
- ASSERT(nleaf_pages <= UINT32_MAX);
- buf->leaf_head.inode = 0;
- buf->leaf_head.ipage = (uint32_t)nleaf_pages;
+ buf->attr_head.inode = 0;
+ buf->attr_head.ipage = (uint32_t)nattr_pages;
exit:
return res;
error:
- if(leaf_page) MEM_RM(buf->allocator, leaf_page);
- CHK(darray_page_resize(&buf->leaf_pages, nleaf_pages) == RES_OK);
+ if(attr_page) MEM_RM(buf->allocator, attr_page);
+ CHK(darray_page_resize(&buf->attr_pages, nattr_pages) == RES_OK);
goto exit;
}
@@ -102,9 +102,9 @@ octree_buffer_init
buf->pagesize = (size_t)sysconf(_SC_PAGESIZE);
buf->voxsize = voxel_size;
darray_page_init(allocator, &buf->node_pages);
- darray_page_init(allocator, &buf->leaf_pages);
+ darray_page_init(allocator, &buf->attr_pages);
buf->node_head = OCTREE_INDEX_NULL;
- buf->leaf_head = OCTREE_INDEX_NULL;
+ buf->attr_head = OCTREE_INDEX_NULL;
buf->allocator = allocator;
CHK(buf->voxsize <= buf->pagesize);
}
@@ -115,7 +115,7 @@ octree_buffer_release(struct octree_buffer* buf)
ASSERT(buf);
octree_buffer_clear(buf);
darray_page_release(&buf->node_pages);
- darray_page_release(&buf->leaf_pages);
+ darray_page_release(&buf->attr_pages);
}
res_T
@@ -127,7 +127,8 @@ octree_buffer_alloc_nodes
res_T res = RES_OK;
ASSERT(buf && first_node);
- if(nnodes > buf->pagesize / sizeof(struct octree_xnode)) return RES_MEM_ERR;
+ if(nnodes > buf->pagesize / sizeof(struct octree_xnode))
+ return RES_MEM_ERR;
res = ensure_allocated_nodes(buf, nnodes);
if(res != RES_OK) return res;
@@ -135,24 +136,25 @@ octree_buffer_alloc_nodes
*first_node = buf->node_head;
buf->node_head.inode = (uint16_t)(buf->node_head.inode + nnodes);
return RES_OK;
+
}
res_T
-octree_buffer_alloc_leaves
+octree_buffer_alloc_attrs
(struct octree_buffer* buf,
- const size_t nleaves,
- struct octree_index* first_leaf)
+ const size_t nattrs,
+ struct octree_index* first_attr)
{
res_T res = RES_OK;
- ASSERT(buf && first_leaf);
+ ASSERT(buf && first_attr);
- if(nleaves >= buf->pagesize / buf->voxsize) return RES_MEM_ERR;
+ if(nattrs > buf->pagesize / buf->voxsize) return RES_MEM_ERR;
- res = ensure_allocated_leaves(buf, nleaves);
+ res = ensure_allocated_attrs(buf, nattrs);
if(res != RES_OK) return res;
- *first_leaf = buf->leaf_head;
- buf->leaf_head.inode = (uint16_t)(buf->leaf_head.inode + nleaves);
+ *first_attr = buf->attr_head;
+ buf->attr_head.inode = (uint16_t)(buf->attr_head.inode + nattrs);
return RES_OK;
}
@@ -185,12 +187,12 @@ octree_buffer_clear(struct octree_buffer* buf)
FOR_EACH(i, 0, darray_page_size_get(&buf->node_pages)) {
MEM_RM(buf->allocator, darray_page_data_get(&buf->node_pages)[i]);
}
- FOR_EACH(i, 0, darray_page_size_get(&buf->leaf_pages)) {
- MEM_RM(buf->allocator, darray_page_data_get(&buf->leaf_pages)[i]);
+ FOR_EACH(i, 0, darray_page_size_get(&buf->attr_pages)) {
+ MEM_RM(buf->allocator, darray_page_data_get(&buf->attr_pages)[i]);
}
darray_page_purge(&buf->node_pages);
- darray_page_purge(&buf->leaf_pages);
+ darray_page_purge(&buf->attr_pages);
buf->node_head = OCTREE_INDEX_NULL;
- buf->leaf_head = OCTREE_INDEX_NULL;
+ buf->attr_head = OCTREE_INDEX_NULL;
}
diff --git a/src/htvox_octree_buffer.h b/src/htvox_octree_buffer.h
@@ -30,13 +30,13 @@
* stored into the same page, that defines the absolute position of its first
* valid child into the whole list of node pages
*
- * The data of the leaves are stored in their own of memory pages. The leaves
- * of a node are stored consecutively into a page. If the page identifier of
- * the leaves is the same of the page into which their parent node lies, then
- * the node saves the index toward the first valid leaf into the page of
- * leaves. In the other case, the node references a `struct octree_index',
- * stored into the same page of the node, that defines the absolute position of
- * its first valid leaf into the buffer of leaves.
+ * The data of the nodes are stored in their own of memory pages. The attribs
+ * of the children of a node are stored consecutively into a page. If the page
+ * identifier of the attribs is the same of the page into which their parent
+ * node lies, then the node saves the index toward the first valid attrib into
+ * the page of attribs. In the other case, the node references a `struct
+ * octree_index', stored into the same page of the node, that defines the
+ * absolute position of its first valid attrib into the buffer of attribs.
*/
#define OCTREE_XNODE_FLAG_FAR_INDEX (1u<<15)
@@ -49,11 +49,13 @@ struct octree_xnode {
* & 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;
+ uint16_t attr_offset;
uint8_t is_valid; /* Mask defining if the children are valid */
uint8_t is_leaf; /* Mask defining if the children are leaves */
- uint16_t dummy__; /* Ensure that the size of the node is 8 bytes */
+ uint16_t dummy__; /* Ensure a size of 8 Bytes */
};
+STATIC_ASSERT(sizeof(struct octree_xnode) == 8,
+ Unexpected_sizeof_octree_xnode);
#define OCTREE_INDEX_IPAGE_MAX UINT32_MAX
#define OCTREE_INDEX_INODE_MAX UINT16_MAX
@@ -79,9 +81,9 @@ struct octree_buffer {
size_t voxsize; /* Memory size of a voxel in bytes */
struct darray_page node_pages; /* List of pages storing nodes */
- struct darray_page leaf_pages; /* List of pages storing leaves */
+ struct darray_page attr_pages; /* List of pages storing node attributes */
struct octree_index node_head; /* Index of the next valid node */
- struct octree_index leaf_head; /* Index of the next valid leaf */
+ struct octree_index attr_head; /* Index of the next valid attr */
struct mem_allocator* allocator;
};
@@ -103,10 +105,10 @@ octree_buffer_alloc_nodes
struct octree_index* first_node); /* Index toward the 1st allocated node */
extern LOCAL_SYM res_T
-octree_buffer_alloc_leaves
+octree_buffer_alloc_attrs
(struct octree_buffer* buf,
- const size_t nleaves,
- struct octree_index* first_leaf); /* Index toward the 1st allocated leaf */
+ const size_t nattrs,
+ struct octree_index* first_attr); /* Index toward the 1st allocated attrib */
/* Allocate an octree_index in the current buffer page. Return RES_MEM_ERR if
* the node index cannot be allocated in the current page. In this case one
@@ -140,6 +142,19 @@ octree_buffer_get_node
return (struct octree_xnode*)mem;
}
+static FINLINE void*
+octree_buffer_get_attr
+ (struct octree_buffer* buf,
+ const struct octree_index id)
+{
+ char* mem;
+ ASSERT(buf && id.inode < buf->pagesize/buf->voxsize);
+ ASSERT(id.ipage < darray_page_size_get(&buf->attr_pages));
+ mem = darray_page_data_get(&buf->attr_pages)[id.ipage];
+ mem += id.inode * buf->voxsize;
+ return mem;
+}
+
static FINLINE struct octree_index*
octree_buffer_get_far_index
(struct octree_buffer* buf,
@@ -153,21 +168,8 @@ octree_buffer_get_far_index
return (struct octree_index*)mem;
}
-static FINLINE void*
-octree_buffer_get_leaf
- (struct octree_buffer* buf,
- const struct octree_index id)
-{
- char* mem;
- ASSERT(buf && id.inode < buf->pagesize/buf->voxsize);
- ASSERT(id.ipage < darray_page_size_get(&buf->leaf_pages));
- mem = darray_page_data_get(&buf->leaf_pages)[id.ipage];
- mem += id.inode * buf->voxsize;
- return mem;
-}
-
static FINLINE struct octree_index
-octree_buffer_get_child_index
+octree_buffer_get_child_node_index
(struct octree_buffer* buf,
const struct octree_index id,
const int ichild) /* in [0, 7] */
@@ -201,37 +203,37 @@ octree_buffer_get_child_index
}
static FINLINE struct octree_index
-octree_buffer_get_leaf_index
+octree_buffer_get_child_attr_index
(struct octree_buffer* buf,
const struct octree_index id,
- const int ileaf) /* In [0, 7] */
+ const int ichild) /* In [0, 7] */
{
- struct octree_index leaf_id = OCTREE_INDEX_NULL;
+ struct octree_index child_id = OCTREE_INDEX_NULL;
struct octree_xnode* node = NULL;
uint16_t offset;
- const int ileaf_flag = BIT(ileaf);
- int ileaf_off;
+ const int ichild_flag = BIT(ichild);
+ int ichild_off;
uint8_t mask;
- ASSERT(ileaf >= 0 && ileaf < 8 && buf);
+ ASSERT(ichild >= 0 && ichild < 8 && buf);
node = octree_buffer_get_node(buf, id);
- mask = node->is_valid & node->is_leaf;
- ASSERT(mask & ileaf_flag);
+ mask = node->is_valid;
+ ASSERT(mask & ichild_flag);
- /* Compute the leaf offset from the first leaf of the node */
- ileaf_off = popcount((uint8_t)((ileaf_flag-1) & (int)mask));
+ /* Compute the attr offset from the first child node */
+ ichild_off = popcount((uint8_t)((ichild_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);
+ offset = node->attr_offset & OCTREE_XNODE_MASK;
+ if(!(node->attr_offset & OCTREE_XNODE_FLAG_FAR_INDEX)) {
+ child_id.ipage = id.ipage;
+ child_id.inode = (uint16_t)(offset + ichild_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);
+ child_id = *(struct octree_index*)(mem+offset*(sizeof(struct octree_xnode)));
+ child_id.inode = (uint16_t)(child_id.inode + ichild_off);
}
- return leaf_id;
+ return child_id;
}
#endif /* HTVOX_OCTREE_BUFFER_H */
diff --git a/src/htvox_scene.c b/src/htvox_scene.c
@@ -31,7 +31,7 @@ static const struct voxel VOXEL_NULL = {0, NULL};
struct octree_node {
struct octree_index ichild_node; /* Index of the 1st child node */
- struct octree_index ichild_leaf; /* Index of the 1st child leaf */
+ struct octree_index ichild_attr; /* Index of the 1st child attr */
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 */
ALIGN(16) char data[8][HTVOX_MAX_SIZEOF_VOXEL]; /* Data of the leaves */
@@ -48,6 +48,8 @@ struct octree_builder {
struct octree_buffer* buffer;
const struct htvox_voxel_desc* desc;
+ size_t nleaves;
+
int octree_depth;
uint64_t mcode; /* Morton code of the last registered voxels */
@@ -70,9 +72,9 @@ check_octree(struct octree_buffer* buf, const struct octree_index root)
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);
+ struct octree_index iattr;
+ iattr = octree_buffer_get_child_attr_index(buf, root, ichild);
+ ASSERT(octree_buffer_get_attr(buf, iattr) != NULL);
} else {
struct octree_index child;
child = octree_buffer_get_child_index(buf, root, ichild);
@@ -98,13 +100,13 @@ stack_clear(struct stack* stack)
{
int inode;
FOR_EACH(inode, 0, 8) {
- int ileaf;
+ int ichild;
stack->nodes[inode].is_leaf = 0;
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) {
- memset(stack->nodes[inode].data[ileaf], 0, HTVOX_MAX_SIZEOF_VOXEL);
+ stack->nodes[inode].ichild_attr = OCTREE_INDEX_NULL;
+ FOR_EACH(ichild, 0, 8) {
+ memset(stack->nodes[inode].data[ichild], 0, HTVOX_MAX_SIZEOF_VOXEL);
}
}
stack->mask = 0;
@@ -121,7 +123,7 @@ stack_setup_node
ASSERT(stack && node && check_htvox_voxel_desc(desc));
node->ichild_node = OCTREE_INDEX_NULL;
- node->ichild_leaf = OCTREE_INDEX_NULL;
+ node->ichild_attr = OCTREE_INDEX_NULL;
node->is_valid = stack->mask;
node->is_leaf = 0;
@@ -130,25 +132,20 @@ stack_setup_node
/* Try to merge the child's leaves */
FOR_EACH(ichild, 0, 8) {
const void* data[8];
+ const uint8_t ichild_flag = (uint8_t)BIT(ichild);
struct octree_node* child = stack->nodes + ichild;
- int ileaf;
-
- /* Only child "full of leaves" can be merged */
- if(child->is_leaf != 0xFF) continue;
+ int igrandchild;
- /* Find the minimum and maximum of the leaves */
- FOR_EACH(ileaf, 0, 8) {
- data[ileaf] = child->data[ileaf];
+ /* Fetch the grandchildren data */
+ FOR_EACH(igrandchild, 0, 8) {
+ data[igrandchild] = child->data[igrandchild];
}
- /* Challenge the merge function */
- if(desc->challenge_merge(data, 8, desc->context)) {
- const uint8_t ichild_flag = (uint8_t)BIT(ichild);
- desc->merge(node->data[ichild], data, 8, desc->context);
- node->is_leaf |= ichild_flag;
+ desc->merge(node->data[ichild], data, 8, desc->context);
- /* The node does not exist anymore in the stack since it became a leaf
- * for its parent node */
+ if(child->is_leaf==0xFF && desc->challenge_merge(data, 8, desc->context)) {
+ /* The node becomes a leaf : the children does not exist anymore */
+ node->is_leaf |= ichild_flag;
stack->mask ^= ichild_flag;
}
}
@@ -157,115 +154,105 @@ stack_setup_node
static res_T
stack_write
(struct stack* stack, /* Node to write */
- struct octree_buffer* buffer, /* Buffer where nodes are written */
- struct octree_index* out_index) /* Index of the first written node */
+ struct octree_buffer* buf, /* Buffer where nodes are written */
+ struct octree_index* out_index, /* Index of the first written node */
+ size_t* out_nleaves) /* #writen leaves */
{
struct octree_index nodes_id = OCTREE_INDEX_NULL;
struct octree_node* node = NULL;
+ size_t nleaves = 0;
int inode;
res_T res = RES_OK;
- ASSERT(stack && buffer && out_index);
+ ASSERT(stack && buf && out_index && out_nleaves);
/* No registered nodes, this means that the nodes were merged in an higher
* level */
if(!stack->mask) goto exit;
- /* Write the leaves */
+ /* Write the attrib of the children */
FOR_EACH(inode, 0, 8) {
- size_t nleaves;
- char* leaves;
- size_t nvoxs_node;
- int ileaf;
+ char* data = NULL;
+ size_t nattrs = 0;
+ size_t nvoxs = 0;
+ int ichild = 0;
if((stack->mask & BIT(inode)) == 0) continue; /* Empty node */
node = stack->nodes + inode;
- if(!node->is_leaf) continue; /* No leaf */
- nleaves = (size_t)popcount(node->is_leaf);
+ nattrs = (size_t)popcount(node->is_valid);
+ ASSERT(nattrs > 0);
- res = octree_buffer_alloc_leaves(buffer, nleaves, &node->ichild_leaf);
+ res = octree_buffer_alloc_attrs(buf, nattrs, &node->ichild_attr);
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)) {
- memcpy(leaves + nvoxs_node*buffer->voxsize, node->data[ileaf],
- buffer->voxsize);
- ++nvoxs_node;
- }
+ data = octree_buffer_get_attr(buf, node->ichild_attr);
+ nvoxs = 0;
+ FOR_EACH(ichild, 0, 8) {
+ if(!(node->is_valid & BIT(ichild))) continue;
+ memcpy(data + nvoxs*buf->voxsize, node->data[ichild], buf->voxsize);
+ ++nvoxs;
}
- ASSERT(nvoxs_node == nleaves);
+ ASSERT(nvoxs == nattrs);
+ nleaves += (size_t)popcount(node->is_leaf);
}
do {
+ struct octree_index index = OCTREE_INDEX_NULL;
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)nnodes, &nodes_id);
+ res = octree_buffer_alloc_nodes(buf, (size_t)nnodes, &nodes_id);
if(res != RES_OK) goto error;
- xnodes = octree_buffer_get_node(buffer, nodes_id);
+ xnodes = octree_buffer_get_node(buf, nodes_id);
FOR_EACH(inode, 0, 8) {
- uint16_t leaf_offset = UINT16_MAX;
+ uint16_t attr_offset = UINT16_MAX;
uint16_t node_offset = UINT16_MAX;
if((stack->mask & BIT(inode)) == 0) continue; /* Empty node */
node = stack->nodes + inode;
- /* 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;
-
- *octree_buffer_get_far_index(buffer, index) = node->ichild_node;
- node_offset = OCTREE_XNODE_FLAG_FAR_INDEX | index.inode;
- }
+ /* Setup the offset toward the children and children attribs */
+ if(node->ichild_node.ipage == nodes_id.ipage) {
+ node_offset = node->ichild_node.inode;
+ attr_offset = node->ichild_attr.inode;
+ }
+
+ /* The page id of the children is not the same as that of node */
+ if(node_offset > OCTREE_XNODE_MAX_CHILDREN_OFFSET) {
+ res = octree_buffer_alloc_far_index(buf, &index);
+ if(res != RES_OK) break;
+ *octree_buffer_get_far_index(buf, index) = node->ichild_node;
+ node_offset = OCTREE_XNODE_FLAG_FAR_INDEX | index.inode;
}
- /* 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;
- /* 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;
-
- *octree_buffer_get_far_index(buffer, index) = node->ichild_leaf;
- leaf_offset = OCTREE_XNODE_FLAG_FAR_INDEX | index.inode;
- }
+ /* The page id of the attribs is not tthe same as that of node */
+ if(attr_offset > OCTREE_XNODE_FLAG_FAR_INDEX) {
+ res = octree_buffer_alloc_far_index(buf, &index);
+ if(res != RES_OK) break;
+ *octree_buffer_get_far_index(buf, index) = node->ichild_attr;
+ attr_offset = OCTREE_XNODE_FLAG_FAR_INDEX | index.inode;
}
xnodes[ixnode].node_offset = node_offset;
- xnodes[ixnode].leaf_offset = leaf_offset;
+ xnodes[ixnode].attr_offset = attr_offset;
xnodes[ixnode].is_valid = node->is_valid;
xnodes[ixnode].is_leaf = node->is_leaf;
++ixnode;
}
+ /* inode < 8 <=> not enough memory in the current page. A far index could not
+ * be stored in the same page of its associated node. The write process was
+ * stoped. Rewrite the whole stacked nodes in a new page. */
} while(inode < 8);
exit:
/* Return the index toward the first writen nodes */
*out_index = nodes_id;
+ *out_nleaves = nleaves;
return res;
error:
goto exit;
@@ -296,6 +283,7 @@ octree_builder_init
}
octree_buffer_clear(buffer);
+ bldr->nleaves = 0;
bldr->desc = desc;
bldr->buffer = buffer;
@@ -335,6 +323,7 @@ octree_builder_add_voxel
FOR_EACH(ilvl, 0, bldr->octree_depth-2/*The 2 last leaves contain all voxels*/) {
struct octree_node* stack_node;
uint64_t mcode_max_lvl;
+ size_t nleaves;
/* Compute the maximum morton code value for the current octree level */
mcode_max_lvl = 8lu/*#children*/ * (1lu<<(3*(ilvl+1)))/*#voxels per children*/;
@@ -352,9 +341,11 @@ octree_builder_add_voxel
/* Write the nodes of the stack of the current octree level into the buf */
res = stack_write
- (&bldr->stacks[ilvl], bldr->buffer, &stack_node->ichild_node);
+ (&bldr->stacks[ilvl], bldr->buffer, &stack_node->ichild_node, &nleaves);
if(res != RES_OK) goto error;
+ bldr->nleaves += nleaves;
+
/* Reset the current stack */
stack_clear(&bldr->stacks[ilvl]);
}
@@ -385,6 +376,7 @@ octree_builder_finalize
struct octree_index* root_id)
{
size_t inode;
+ size_t nleaves;
int ilvl;
res_T res = RES_OK;
ASSERT(bldr);
@@ -408,14 +400,16 @@ octree_builder_finalize
/* Write the stacked nodes of the current level */
res = stack_write
- (&bldr->stacks[ilvl], bldr->buffer, &parent_node->ichild_node);
+ (&bldr->stacks[ilvl], bldr->buffer, &parent_node->ichild_node, &nleaves);
if(res != RES_OK) goto error;
+ bldr->nleaves += nleaves;
}
/* Write the root node */
ilvl = bldr->octree_depth-1; /* Root level */
- res = stack_write(&bldr->stacks[ilvl], bldr->buffer, root_id);
+ res = stack_write(&bldr->stacks[ilvl], bldr->buffer, root_id, &nleaves);
if(res != RES_OK) goto error;
+ bldr->nleaves += nleaves;
exit:
return res;
@@ -536,6 +530,8 @@ htvox_scene_create
res = octree_builder_finalize(&bldr, &scn->root);
if(res != RES_OK) goto error;
+ scn->nleaves = bldr.nleaves;
+
#ifndef NDEBUG
check_octree(&scn->buffer, scn->root);
#endif
@@ -597,13 +593,8 @@ htvox_scene_get_aabb
res_T
htvox_scene_get_voxels_count(const struct htvox_scene* scn, size_t* nvoxels)
{
- size_t nvoxs = 0;
- size_t nvoxs_per_page = 0;
if(!scn || !nvoxels) return RES_BAD_ARG;
- nvoxs_per_page = scn->buffer.pagesize / sizeof(double);
- nvoxs = scn->buffer.leaf_head.ipage * nvoxs_per_page
- + scn->buffer.leaf_head.inode;
- *nvoxels = nvoxs;
+ *nvoxels = scn->nleaves;
return RES_OK;
}
@@ -666,12 +657,13 @@ htvox_scene_for_each_voxel
upp[2] = low[2] + half_sz[2];
if(node->is_leaf & ichild_flag) {
- struct octree_index ileaf;
+ struct octree_index iattr;
size_t ivoxel;
const void* val;
- ileaf = octree_buffer_get_leaf_index(&scn->buffer, entry.inode, ichild);
- val = octree_buffer_get_leaf(&scn->buffer, ileaf);
+ iattr = octree_buffer_get_child_attr_index
+ (&scn->buffer, entry.inode, ichild);
+ val = octree_buffer_get_attr(&scn->buffer, iattr);
ASSERT(upp[0] <= scn->upper[0]);
ASSERT(upp[1] <= scn->upper[1]);
@@ -680,13 +672,13 @@ htvox_scene_for_each_voxel
ASSERT(low[1] >= scn->lower[1]);
ASSERT(low[2] >= scn->lower[2]);
- ivoxel =
- ileaf.ipage * scn->buffer.pagesize / sizeof(double) + ileaf.inode;
+ ivoxel =iattr.ipage * scn->buffer.pagesize / scn->buffer.voxsize
+ + iattr.inode;
func(val, ivoxel, low, upp, ctx);
} else {
struct stack_entry* top = stack + istack;
- top->inode = octree_buffer_get_child_index
+ top->inode = octree_buffer_get_child_node_index
(&scn->buffer, entry.inode, ichild);
top->low[0] = low[0];
top->low[1] = low[1];
@@ -759,13 +751,13 @@ htvox_scene_at
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;
+ inode = octree_buffer_get_child_attr_index(&scn->buffer, inode, ichild);
+ voxel->data = octree_buffer_get_attr(&scn->buffer, inode);
+ voxel->id = inode.ipage * scn->buffer.pagesize / scn->buffer.voxsize
+ + inode.inode;
break;
} else { /* Child node */
- inode = octree_buffer_get_child_index(&scn->buffer, inode, ichild);
+ inode = octree_buffer_get_child_node_index(&scn->buffer, inode, ichild);
scale_exp2 *= 0.5;
}
}
diff --git a/src/htvox_scene.h b/src/htvox_scene.h
@@ -27,6 +27,7 @@ struct htvox_scene {
struct octree_buffer buffer;
struct octree_index root; /* Index toward the root node of the octree */
+ size_t nleaves; /* #leaves */
struct htvox_device* dev;
ref_T ref;
diff --git a/src/test_htvox_scene.c b/src/test_htvox_scene.c
@@ -225,7 +225,7 @@ dump_data(FILE* stream, struct htvox_scene* scn)
CHK(htvox_scene_for_each_voxel(scn, write_cells, stream) == RES_OK);
fprintf(stream, "CELL_TYPES %lu\n", (unsigned long)nvxls);
- FOR_EACH(ivxl, 0, nvxls ) fprintf(stream, "11\n");
+ FOR_EACH(ivxl, 0, nvxls) fprintf(stream, "11\n");
fprintf(stream, "CELL_DATA %lu\n", (unsigned long)nvxls);
fprintf(stream, "SCALARS K float 1\n");
@@ -360,7 +360,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] = 32;
desc.challenge_merge = merge_level0;
CHK(NEW_SCN(dev, low, upp, nvxls, &desc, &scn) == RES_OK);
CHK(htvox_scene_get_voxels_count(scn, &nvoxels) == RES_OK);
