commit da20b8fccea4de3285fade7986b79cb119c76ced
parent 3467e2d3dda84ea28cd0d10ac16c1759d7c09fb3
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 3 May 2018 15:24:52 +0200
Make the build process generic to the tree dimension
Diffstat:
11 files changed, 979 insertions(+), 894 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -41,14 +41,14 @@ set(VERSION_PATCH 0)
set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(SVX_FILES_SRC
+ svx_buffer.c
svx_device.c
svx_octree.c
- svx_octree_buffer.c
svx_octree_trace_ray.c)
set(SSOL_FILES_INC
+ svx_buffer.h
svx_device.h
- svx_octree.h
- svx_octree_buffer.h)
+ svx_octree.h)
set(SSOL_FILES_INC_API
svx.h)
diff --git a/src/svx.h b/src/svx.h
@@ -165,6 +165,7 @@ struct mem_allocator;
/* Forward declaration of opaque data types */
struct svx_device;
struct svx_octree;
+struct svx_bintree;
BEGIN_DECLS
@@ -236,5 +237,25 @@ svx_octree_at
void* context, /* Client data sent as the last argument of the filter func */
struct svx_voxel* voxel);
+/*******************************************************************************
+ * Binary tree
+ ******************************************************************************/
+SVX_API res_T
+svx_bintree_create
+ (struct svx_device* dev,
+ const double lower, /* Lower bound of the bintree */
+ const double upper, /* Upper bound of the bintree */
+ const size_t nvoxels, /* # voxels along the range */
+ const struct svx_voxel_desc* desc, /* Descriptor of a voxel */
+ struct svx_bintree** bintree);
+
+SVX_API res_T
+svx_bintree_ref_get
+ (struct svx_bintree* bintree);
+
+SVX_API res_T
+svx_bintree_ref_put
+ (struct svx_bintree* bintree);
+
#endif /* SVX_H */
diff --git a/src/svx_buffer.c b/src/svx_buffer.c
@@ -0,0 +1,198 @@
+/* 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/>. */
+
+#include "svx_buffer.h"
+
+#include <rsys/mem_allocator.h>
+
+#include <unistd.h>
+
+/*******************************************************************************
+ * Helper functions
+ ******************************************************************************/
+static INLINE res_T
+ensure_allocated_nodes(struct buffer* buf, const size_t nnodes)
+{
+ char* node_page = NULL;
+ size_t nnode_pages = 0;
+ res_T res = RES_OK;
+ ASSERT(buf);
+
+ if(buf->node_head.ipage != BUFFER_INDEX_NULL.ipage
+ && buf->node_head.inode + nnodes <= buf->pagesize/sizeof(struct buffer_xnode))
+ 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 */
+ node_page = MEM_ALLOC(buf->allocator, buf->pagesize);
+ if(!node_page) { res = RES_MEM_ERR; goto error; }
+ res = darray_page_push_back(&buf->node_pages, &node_page);
+ if(res != RES_OK) goto error;
+
+ buf->node_head.inode = 0;
+ buf->node_head.ipage = (uint32_t)nnode_pages;
+
+exit:
+ return res;
+error:
+ if(node_page) MEM_RM(buf->allocator, node_page);
+ CHK(darray_page_resize(&buf->node_pages, nnode_pages) == RES_OK);
+ goto exit;
+}
+
+static INLINE res_T
+ensure_allocated_attrs(struct buffer* buf, const size_t nattrs)
+{
+ char* attr_page = NULL;
+ size_t nattr_pages = 0;
+ res_T res = RES_OK;
+ ASSERT(buf);
+
+ if(buf->attr_head.ipage != BUFFER_INDEX_NULL.ipage
+ && buf->attr_head.inode + nattrs <= buf->pagesize/buf->voxsize)
+ goto exit;
+
+ 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 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;
+
+ buf->attr_head.inode = 0;
+ buf->attr_head.ipage = (uint32_t)nattr_pages;
+
+exit:
+ return res;
+error:
+ if(attr_page) MEM_RM(buf->allocator, attr_page);
+ CHK(darray_page_resize(&buf->attr_pages, nattr_pages) == RES_OK);
+ goto exit;
+}
+
+/*******************************************************************************
+ * Local functions
+ ******************************************************************************/
+void
+buffer_init
+ (struct mem_allocator* allocator,
+ const size_t voxel_size,
+ struct buffer* buf)
+{
+ ASSERT(buf && allocator);
+ memset(buf, 0, sizeof(struct buffer));
+ buf->pagesize = (size_t)sysconf(_SC_PAGESIZE);
+ buf->voxsize = voxel_size;
+ darray_page_init(allocator, &buf->node_pages);
+ darray_page_init(allocator, &buf->attr_pages);
+ buf->node_head = BUFFER_INDEX_NULL;
+ buf->attr_head = BUFFER_INDEX_NULL;
+ buf->allocator = allocator;
+ CHK(buf->voxsize <= buf->pagesize);
+}
+
+void
+buffer_release(struct buffer* buf)
+{
+ ASSERT(buf);
+ buffer_clear(buf);
+ darray_page_release(&buf->node_pages);
+ darray_page_release(&buf->attr_pages);
+}
+
+res_T
+buffer_alloc_nodes
+ (struct buffer* buf,
+ const size_t nnodes,
+ struct buffer_index* first_node)
+{
+ res_T res = RES_OK;
+ ASSERT(buf && first_node);
+
+ if(nnodes > buf->pagesize / sizeof(struct buffer_xnode))
+ return RES_MEM_ERR;
+
+ res = ensure_allocated_nodes(buf, nnodes);
+ if(res != RES_OK) return res;
+
+ *first_node = buf->node_head;
+ buf->node_head.inode = (uint16_t)(buf->node_head.inode + nnodes);
+ return RES_OK;
+
+}
+
+res_T
+buffer_alloc_attrs
+ (struct buffer* buf,
+ const size_t nattrs,
+ struct buffer_index* first_attr)
+{
+ res_T res = RES_OK;
+ ASSERT(buf && first_attr);
+
+ if(nattrs > buf->pagesize / buf->voxsize) return RES_MEM_ERR;
+
+ res = ensure_allocated_attrs(buf, nattrs);
+ if(res != RES_OK) return res;
+
+ *first_attr = buf->attr_head;
+ buf->attr_head.inode = (uint16_t)(buf->attr_head.inode + nattrs);
+ return RES_OK;
+}
+
+res_T
+buffer_alloc_far_index
+ (struct buffer* buf,
+ struct buffer_index* id)
+{
+ size_t remaining_size;
+ size_t skipped_nnodes;
+ STATIC_ASSERT(sizeof(struct buffer_index) >= sizeof(struct buffer_xnode),
+ Unexpected_type_size);
+
+ remaining_size = buf->pagesize - buf->node_head.inode*sizeof(struct buffer_xnode);
+
+ /* Not enough memory in the current page */
+ if(sizeof(struct buffer_index) > remaining_size) return RES_MEM_ERR;
+
+ *id = buf->node_head;
+ skipped_nnodes = sizeof(struct buffer_index) / sizeof(struct buffer_xnode);
+ buf->node_head.inode = (uint16_t)(buf->node_head.inode + skipped_nnodes);
+ return RES_OK;
+}
+
+void
+buffer_clear(struct buffer* buf)
+{
+ size_t i;
+ ASSERT(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->attr_pages)) {
+ MEM_RM(buf->allocator, darray_page_data_get(&buf->attr_pages)[i]);
+ }
+ darray_page_purge(&buf->node_pages);
+ darray_page_purge(&buf->attr_pages);
+ buf->node_head = BUFFER_INDEX_NULL;
+ buf->attr_head = BUFFER_INDEX_NULL;
+}
+
diff --git a/src/svx_buffer.h b/src/svx_buffer.h
@@ -0,0 +1,248 @@
+/* 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 SVX_BUFFER_H
+#define SVX_BUFFER_H
+
+#include "svx_c.h"
+#include <rsys/dynamic_array.h>
+
+/*
+ * Buffer containing the data of a tree. These data are partitioned in fixed
+ * size memory pages whose capacity is defined on buffer initialisation with
+ * respect to the page size of the system.
+ *
+ * The children of a node are stored consecutively into a page. The parent node
+ * directly references its first valid children excepted if they lie in a
+ * different page. In this case, the node references a `struct buffer_index',
+ * 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 nodes are stored in their own 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
+ * buffer_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 BUFFER_XNODE_FLAG_FAR_INDEX (1u<<15)
+#define BUFFER_XNODE_MAX_CHILDREN_OFFSET (BUFFER_XNODE_FLAG_FAR_INDEX-1)
+#define BUFFER_XNODE_MASK BUFFER_XNODE_MAX_CHILDREN_OFFSET
+
+struct buffer_xnode {
+ /* Offset to retrieve the children. If the BUFFER_XNODE_FLAG_FAR_INDEX bit is
+ * not set, the children are stored in the same page at the position `offset
+ * & BUFFER_XNODE_MASK'. If BUFFER_XNODE_FLAG_FAR_INDEX is set, `offset &
+ * BUFFER_XNODE_MASK' reference an buffer_index toward the node children */
+ uint16_t node_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 a size of 8 Bytes */
+};
+STATIC_ASSERT(sizeof(struct buffer_xnode) == 8,
+ Unexpected_sizeof_buffer_xnode);
+
+#define BUFFER_INDEX_IPAGE_MAX UINT32_MAX
+#define BUFFER_INDEX_INODE_MAX UINT16_MAX
+
+struct buffer_index {
+ uint32_t ipage; /* Identifier of the page */
+ uint16_t inode; /* Identifier of the node in the page */
+ uint16_t dummy__; /* Padding to ensure the tree index is 8 bytes lenght */
+};
+STATIC_ASSERT(sizeof(struct buffer_index) == 8,
+ Unexpected_sizeof_buffer_index);
+#define BUFFER_INDEX_NULL__ {UINT32_MAX, UINT16_MAX, UINT16_MAX}
+static const struct buffer_index BUFFER_INDEX_NULL = BUFFER_INDEX_NULL__;
+#define BUFFER_INDEX_EQ(A, B) ((A)->inode==(B)->inode && (A)->ipage==(B)->ipage)
+
+/* Define the dynamic array of pages */
+#define DARRAY_NAME page
+#define DARRAY_DATA char*
+#include <rsys/dynamic_array.h>
+
+struct buffer {
+ size_t pagesize; /* Memory page size in bytes */
+ size_t voxsize; /* Memory size of a voxel in bytes */
+
+ struct darray_page node_pages; /* List of pages storing nodes */
+ struct darray_page attr_pages; /* List of pages storing node attributes */
+ struct buffer_index node_head; /* Index of the next valid node */
+ struct buffer_index attr_head; /* Index of the next valid attr */
+
+ struct mem_allocator* allocator;
+};
+
+extern LOCAL_SYM void
+buffer_init
+ (struct mem_allocator* allocator,
+ const size_t sizeof_voxel, /* Size in bytes of a voxel */
+ struct buffer* buf);
+
+extern LOCAL_SYM void
+buffer_release
+ (struct buffer* buf);
+
+extern LOCAL_SYM res_T
+buffer_alloc_nodes
+ (struct buffer* buf,
+ const size_t nnodes,
+ struct buffer_index* first_node); /* Index toward the 1st allocated node */
+
+extern LOCAL_SYM res_T
+buffer_alloc_attrs
+ (struct buffer* buf,
+ const size_t nattrs,
+ struct buffer_index* first_attr); /* Index toward the 1st allocated attrib */
+
+/* Allocate an buffer_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
+ * have to alloc new nodes */
+extern LOCAL_SYM res_T
+buffer_alloc_far_index
+ (struct buffer* buf,
+ struct buffer_index* id); /* Index toward the allocated far index */
+
+extern LOCAL_SYM void
+buffer_clear
+ (struct buffer* buf);
+
+static FINLINE int
+buffer_is_empty(const struct buffer* buf)
+{
+ ASSERT(buf);
+ return darray_page_size_get(&buf->node_pages) == 0;
+}
+
+static FINLINE struct buffer_xnode*
+buffer_get_node
+ (struct buffer* buf,
+ const struct buffer_index id)
+{
+ char* mem;
+ ASSERT(buf && id.inode < buf->pagesize/sizeof(struct buffer_xnode));
+ ASSERT(id.ipage < darray_page_size_get(&buf->node_pages));
+ mem = darray_page_data_get(&buf->node_pages)[id.ipage];
+ mem += id.inode * sizeof(struct buffer_xnode);
+ return (struct buffer_xnode*)mem;
+}
+
+static FINLINE void*
+buffer_get_attr
+ (struct buffer* buf,
+ const struct buffer_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 buffer_index*
+buffer_get_far_index
+ (struct buffer* buf,
+ const struct buffer_index id)
+{
+ char* mem;
+ ASSERT(buf && id.inode < buf->pagesize/sizeof(struct buffer_xnode));
+ ASSERT(id.ipage < darray_page_size_get(&buf->node_pages));
+ mem = darray_page_data_get(&buf->node_pages)[id.ipage];
+ mem += id.inode * sizeof(struct buffer_xnode);
+ return (struct buffer_index*)mem;
+}
+
+static FINLINE struct buffer_index
+buffer_get_child_node_index
+ (struct buffer* buf,
+ const struct buffer_index id,
+ const int ichild) /* in [0, 7] */
+{
+ struct buffer_index child_id = BUFFER_INDEX_NULL;
+ struct buffer_xnode* node = NULL;
+ uint16_t offset;
+ const int ichild_flag = BIT(ichild);
+ int ichild_off;
+ uint8_t mask;
+
+ ASSERT(ichild >= 0 && ichild < 8 && buf);
+
+ node = buffer_get_node(buf, id);
+ 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));
+
+ offset = node->node_offset & BUFFER_XNODE_MASK;
+ if(!(node->node_offset & BUFFER_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];
+ child_id = *(struct buffer_index*)(mem+offset*(sizeof(struct buffer_xnode)));
+ child_id.inode = (uint16_t)(child_id.inode + ichild_off);
+ }
+ return child_id;
+}
+
+static FINLINE struct buffer_index
+buffer_get_child_attr_index
+ (struct buffer* buf,
+ const struct buffer_index id,
+ const int ichild) /* In [0, 7] */
+{
+ struct buffer_index child_id = BUFFER_INDEX_NULL;
+ struct buffer_xnode* node = NULL;
+ uint16_t offset;
+ const int ichild_flag = BIT(ichild);
+ int ichild_off;
+ uint8_t mask;
+
+ ASSERT(ichild >= 0 && ichild < 8 && buf);
+
+ node = buffer_get_node(buf, id);
+ mask = node->is_valid;
+ ASSERT(mask & ichild_flag);
+
+ /* Compute the attr offset from the first child node */
+ ichild_off = popcount((uint8_t)((ichild_flag-1) & (int)mask));
+
+ offset = node->attr_offset & BUFFER_XNODE_MASK;
+ if(!(node->attr_offset & BUFFER_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];
+ child_id = *(struct buffer_index*)(mem+offset*(sizeof(struct buffer_xnode)));
+ child_id.inode = (uint16_t)(child_id.inode + ichild_off);
+ }
+ return child_id;
+}
+
+static FINLINE size_t
+buffer_absolute_attr_index
+ (const struct buffer* buf,
+ const struct buffer_index index)
+{
+ ASSERT(buf);
+ return index.ipage * buf->pagesize/buf->voxsize + index.inode;
+}
+
+#endif /* SVX_BUFFER_H */
diff --git a/src/svx_c.h b/src/svx_c.h
@@ -16,6 +16,7 @@
#ifndef SVX_C_H
#define SVX_C_H
+#include "svx.h"
#include <rsys/rsys.h>
static INLINE uint64_t
@@ -71,5 +72,16 @@ morton_xyz_decode_u21(const uint64_t code, uint32_t xyz[3])
xyz[2] = (uint32_t)morton3D_decode_u21(code >> 0);
}
+static INLINE int
+check_svx_voxel_desc(const struct svx_voxel_desc* desc)
+{
+ return desc
+ && desc->get
+ && desc->merge
+ && desc->challenge_merge
+ && desc->size > 0
+ && desc->size <= SVX_MAX_SIZEOF_VOXEL;
+}
+
#endif /* SVX_C_H */
diff --git a/src/svx_octree.c b/src/svx_octree.c
@@ -18,422 +18,18 @@
#include "svx_device.h"
#include "svx_octree.h"
+#include "svx_tree_builder.h"
+
#include <rsys/double3.h>
#include <rsys/mem_allocator.h>
-#define OCTREE_DEPTH_MAX 16 /* Maximum depth of an octree */
-
-struct voxel {
- uint64_t mcode; /* Morton code of the voxel */
- void* data; /* Data of the voxel */
-};
-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_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][SVX_MAX_SIZEOF_VOXEL]; /* Data of the leaves */
-};
-
-/* Stacked children of an octree node */
-struct stack {
- struct octree_node nodes[8]; /* List of registered children nodes */
- uint8_t mask; /* Mask of valid children nodes (0 = empty) */
-};
-
-struct octree_builder {
- struct stack stacks[OCTREE_DEPTH_MAX];
- struct octree_buffer* buffer;
-
- const struct svx_voxel_desc* desc;
- size_t nleaves; /* Number of emitted leaves */
-
- int octree_depth; /* Maximum octree depth */
- int non_empty_lvl; /* Index of the 1st non empty level */
-
- uint64_t mcode; /* Morton code of the last registered voxels */
-};
+/* Generate the tree_builder_3d data structure */
+#define TREE_DIMENSION 3
+#include "svx_tree_builder.h"
/*******************************************************************************
* Helper function
******************************************************************************/
-#ifndef NDEBUG
-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);
- 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 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_node_index(buf, root, ichild);
- check_octree(buf, child);
- }
- }
-}
-#endif
-
-static INLINE int
-check_svx_voxel_desc(const struct svx_voxel_desc* desc)
-{
- return desc
- && desc->get
- && desc->merge
- && desc->challenge_merge
- && desc->size > 0
- && desc->size <= SVX_MAX_SIZEOF_VOXEL;
-}
-
-static INLINE void
-stack_clear(struct stack* stack)
-{
- int inode;
- FOR_EACH(inode, 0, 8) {
- 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_attr = OCTREE_INDEX_NULL;
- FOR_EACH(ichild, 0, 8) {
- memset(stack->nodes[inode].data[ichild], 0, SVX_MAX_SIZEOF_VOXEL);
- }
- }
- stack->mask = 0;
-}
-
-/* Build a parent octree node from the registered stack nodes */
-static INLINE void
-stack_setup_node
- (struct stack* stack,
- struct octree_node* node,
- const struct svx_voxel_desc* desc)
-{
- int ichild;
- ASSERT(stack && node && check_svx_voxel_desc(desc));
-
- node->ichild_node = OCTREE_INDEX_NULL;
- node->ichild_attr = OCTREE_INDEX_NULL;
- node->is_valid = stack->mask;
- node->is_leaf = 0;
-
- if(stack->mask == 0) return; /* Empty stack */
-
- /* 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 igrandchild;
-
- /* Fetch the grandchildren data */
- FOR_EACH(igrandchild, 0, 8) {
- data[igrandchild] = child->data[igrandchild];
- }
-
- desc->merge(node->data[ichild], data, 8, desc->context);
-
- 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;
- }
- }
-}
-
-static res_T
-stack_write
- (struct stack* stack, /* Node to write */
- 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 && 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 attrib of the children */
- FOR_EACH(inode, 0, 8) {
- 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;
-
- nattrs = (size_t)popcount(node->is_valid);
- ASSERT(nattrs > 0);
-
- res = octree_buffer_alloc_attrs(buf, nattrs, &node->ichild_attr);
- if(res != RES_OK) goto error;
-
- 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 == 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(buf, (size_t)nnodes, &nodes_id);
- if(res != RES_OK) goto error;
- xnodes = octree_buffer_get_node(buf, nodes_id);
-
- FOR_EACH(inode, 0, 8) {
- 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 and children attribs */
- if(node->ichild_node.ipage == nodes_id.ipage) {
- node_offset = node->ichild_node.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 children attribs */
- if(node->ichild_attr.ipage == nodes_id.ipage) {
- attr_offset = node->ichild_attr.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].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;
-}
-
-static res_T
-octree_builder_init
- (struct octree_builder* bldr,
- const size_t definition,
- const struct svx_voxel_desc* desc,
- struct octree_buffer* buffer)
-{
- int ilvl;
- res_T res = RES_OK;
- ASSERT(bldr && IS_POW2(definition) && check_svx_voxel_desc(desc));
- memset(bldr, 0, sizeof(struct octree_builder));
-
- /* Compute the maximum depth of the octree */
- bldr->octree_depth = log2i((int)definition);
- if(bldr->octree_depth > OCTREE_DEPTH_MAX) {
- res = RES_MEM_ERR;
- goto error;
- }
-
- /* Init the per octree level stack */
- FOR_EACH(ilvl, 0, bldr->octree_depth) {
- stack_clear(&bldr->stacks[ilvl]);
- }
-
- octree_buffer_clear(buffer);
- bldr->nleaves = 0;
- bldr->desc = desc;
- bldr->buffer = buffer;
- bldr->non_empty_lvl = bldr->octree_depth - 1;
-
-exit:
- return res;
-error:
- goto exit;
-}
-
-static res_T
-octree_builder_add_voxel
- (struct octree_builder* bldr,
- 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);
-
- /* Define if the bits in [4 .. 63] of the previous and the next Morton
- * codes are the same */
- mcode_xor = bldr->mcode ^ vox->mcode;
-
- /* The next voxel is not in the current node */
- 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 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;
- 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*/;
-
- if(mcode_xor < mcode_max_lvl) break;
-
- /* 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[inode];
- stack_setup_node(&bldr->stacks[ilvl], stack_node, bldr->desc);
- 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->ichild_node, &nleaves);
- if(res != RES_OK) goto error;
-
- bldr->nleaves += nleaves;
- if(nleaves) bldr->non_empty_lvl = MMIN(bldr->non_empty_lvl, (int)ilvl);
-
- /* 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 */
- memcpy(bldr->stacks[0].nodes[inode].data[ichild], vox->data, bldr->desc->size);
- 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;
-
-exit:
- return res;
-error:
- goto exit;
-}
-
-static INLINE res_T
-octree_builder_finalize
- (struct octree_builder* bldr,
- struct octree_index* root_id,
- void* root_data)
-{
- const void* data[8];
- size_t inode;
- size_t nleaves;
- int ilvl;
- int ichild;
- 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;
-
- 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->desc);
- 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->ichild_node, &nleaves);
- if(res != RES_OK) goto error;
- bldr->nleaves += nleaves;
- }
-
- ilvl = bldr->octree_depth-1; /* Root level */
-
- /* Write the root node */
- res = stack_write(&bldr->stacks[ilvl], bldr->buffer, root_id, &nleaves);
- if(res != RES_OK) goto error;
- bldr->nleaves += nleaves;
-
- /* Setup the root attribs */
- ASSERT(bldr->stacks[ilvl].mask == 1); /* Only the root node is active */
- FOR_EACH(ichild, 0, 8) {
- data[ichild] = bldr->stacks[ilvl].nodes[0].data[ichild];
- }
- bldr->desc->merge(root_data, data, 8, bldr->desc->context);
-
-exit:
- return res;
-error:
- goto exit;
-}
-
static void
octree_release(ref_T* ref)
{
@@ -441,7 +37,7 @@ octree_release(ref_T* ref)
struct svx_device* dev;
ASSERT(ref);
oct = CONTAINER_OF(ref, struct svx_octree, ref);
- octree_buffer_release(&oct->buffer);
+ buffer_release(&oct->buffer);
dev = oct->dev;
MEM_RM(dev->allocator, oct);
SVX(device_ref_put(dev));
@@ -467,8 +63,8 @@ svx_octree_create
uint64_t mcode;
res_T res = RES_OK;
- if(!dev || !lower || !upper || !nvoxels
- || !check_svx_voxel_desc(desc) || !out_oct) {
+ if(!dev || !lower || !upper || !nvoxels || !check_svx_voxel_desc(desc)
+ || !out_oct) {
res = RES_BAD_ARG;
goto error;
}
@@ -500,7 +96,7 @@ svx_octree_create
}
ref_init(&oct->ref);
SVX(device_ref_get(dev));
- octree_buffer_init(dev->allocator, desc->size, &oct->buffer);
+ buffer_init(dev->allocator, desc->size, &oct->buffer);
oct->dev = dev;
/* Compute the octree definition */
@@ -548,12 +144,12 @@ svx_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.tree_depth - bldr.non_empty_lvl)
+ 1 /* leaf level */;
- ASSERT(bldr.octree_depth > bldr.non_empty_lvl);
+ ASSERT(bldr.tree_depth > bldr.non_empty_lvl);
#ifndef NDEBUG
- check_octree(&oct->buffer, oct->root);
+ octree_check(&oct->buffer, oct->root);
#endif
/* Setup the octree AABB in world space */
d3_set(oct->lower, lower);
@@ -615,7 +211,7 @@ svx_octree_get_desc
d3_set(desc->lower, oct->lower);
d3_set(desc->upper, oct->upper);
desc->nleaves = oct->nleaves;
- desc->nvoxels = octree_buffer_absolute_attr_index
+ desc->nvoxels = buffer_absolute_attr_index
(&oct->buffer, oct->buffer.attr_head) + 1; /* Root node */
desc->depth = oct->depth;
return RES_OK;
@@ -631,11 +227,11 @@ svx_octree_for_each_leaf
void* ctx)
{
struct stack_entry {
- struct octree_index inode;
+ struct buffer_index inode;
size_t depth;
double low[3];
double hsz[3]; /* Half size */
- } stack[OCTREE_DEPTH_MAX*8];
+ } stack[TREE_DEPTH_MAX*8];
int istack;
struct svx_voxel leaf = SVX_VOXEL_NULL;
size_t ileaf = 0;
@@ -657,10 +253,10 @@ svx_octree_for_each_leaf
const size_t child_depth = entry.depth + 1;
double child_hsz[3];
double mid[3]; /* Middle point of the current node */
- struct octree_xnode* node;
+ struct buffer_xnode* node;
int ichild;
- node = octree_buffer_get_node(&oct->buffer, entry.inode);
+ node = buffer_get_node(&oct->buffer, entry.inode);
mid[0] = entry.low[0] + entry.hsz[0];
mid[1] = entry.low[1] + entry.hsz[1];
@@ -680,15 +276,15 @@ svx_octree_for_each_leaf
low[2] = ichild&1 ? mid[2] : entry.low[2];
if(node->is_leaf & ichild_flag) {
- struct octree_index iattr;
+ struct buffer_index iattr;
- iattr = octree_buffer_get_child_attr_index
+ 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 = octree_buffer_get_attr(&oct->buffer, iattr);
- leaf.id = octree_buffer_absolute_attr_index(&oct->buffer, iattr);
+ 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;
@@ -696,7 +292,7 @@ svx_octree_for_each_leaf
} else {
struct stack_entry* top = stack + istack;
- top->inode = octree_buffer_get_child_node_index
+ top->inode = buffer_get_child_node_index
(&oct->buffer, entry.inode, ichild);
d3_set(top->low, low);
d3_set(top->hsz, child_hsz);
@@ -717,8 +313,8 @@ svx_octree_at
void* context,
struct svx_voxel* voxel)
{
- struct octree_index inode;
- struct octree_index iattr;
+ struct buffer_index inode;
+ struct buffer_index iattr;
struct svx_voxel vox = SVX_VOXEL_NULL;
double scale_exp2;
double low[3];
@@ -762,14 +358,14 @@ svx_octree_at
d3_set(vox.upper, oct->upper);
if(filter) {
vox.data = oct->root_attr;
- vox.id = octree_buffer_absolute_attr_index(&oct->buffer, oct->buffer.attr_head);
+ 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 octree_xnode* node = octree_buffer_get_node(&oct->buffer, inode);
+ struct buffer_xnode* node = buffer_get_node(&oct->buffer, inode);
int ichild;
uint8_t ichild_flag;
double mid[3];
@@ -793,7 +389,7 @@ svx_octree_at
vox.is_leaf = (node->is_leaf & ichild_flag) != 0;
if(filter || vox.is_leaf) {
- iattr = octree_buffer_get_child_attr_index(&oct->buffer, inode, ichild);
+ iattr = buffer_get_child_attr_index(&oct->buffer, inode, ichild);
/* Setup the voxel */
vox.lower[0] = low[0] * ocsz[0] + oct->oclow[0];
@@ -802,8 +398,8 @@ svx_octree_at
vox.upper[0] = vox.lower[0] + ocsz[0] * scale_exp2;
vox.upper[1] = vox.lower[1] + ocsz[1] * scale_exp2;
vox.upper[2] = vox.lower[2] + ocsz[2] * scale_exp2;
- vox.data = octree_buffer_get_attr(&oct->buffer, iattr);
- vox.id = octree_buffer_absolute_attr_index(&oct->buffer, iattr);
+ 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)) {
@@ -812,7 +408,7 @@ svx_octree_at
}
}
- inode = octree_buffer_get_child_node_index(&oct->buffer, inode, ichild);
+ inode = buffer_get_child_node_index(&oct->buffer, inode, ichild);
scale_exp2 *= 0.5;
}
diff --git a/src/svx_octree.h b/src/svx_octree.h
@@ -16,7 +16,7 @@
#ifndef SVX_OCTREE_H
#define SVX_OCTREE_H
-#include "svx_octree_buffer.h"
+#include "svx_buffer.h"
#include <rsys/ref_count.h>
struct svx_octree {
@@ -26,8 +26,8 @@ struct svx_octree {
double oclow[3], ocupp[3]; /* Adjusted World space AABB of the octree */
double ocsize[3]; /* World space size of the octree */
- struct octree_buffer buffer;
- struct octree_index root; /* Index toward the children of the root */
+ struct buffer buffer;
+ struct buffer_index root; /* Index toward the children of the root */
ALIGN(16) char root_attr[SVX_MAX_SIZEOF_VOXEL]; /* Attribute of the root */
size_t nleaves; /* #leaves */
diff --git a/src/svx_octree_buffer.c b/src/svx_octree_buffer.c
@@ -1,198 +0,0 @@
-/* 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/>. */
-
-#include "svx_octree_buffer.h"
-
-#include <rsys/mem_allocator.h>
-
-#include <unistd.h>
-
-/*******************************************************************************
- * Helper functions
- ******************************************************************************/
-static INLINE res_T
-ensure_allocated_nodes(struct octree_buffer* buf, const size_t nnodes)
-{
- char* node_page = NULL;
- size_t nnode_pages = 0;
- res_T res = RES_OK;
- ASSERT(buf);
-
- if(buf->node_head.ipage != OCTREE_INDEX_NULL.ipage
- && buf->node_head.inode + nnodes <= buf->pagesize/sizeof(struct octree_xnode))
- 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 */
- node_page = MEM_ALLOC(buf->allocator, buf->pagesize);
- if(!node_page) { res = RES_MEM_ERR; goto error; }
- res = darray_page_push_back(&buf->node_pages, &node_page);
- if(res != RES_OK) goto error;
-
- buf->node_head.inode = 0;
- buf->node_head.ipage = (uint32_t)nnode_pages;
-
-exit:
- return res;
-error:
- if(node_page) MEM_RM(buf->allocator, node_page);
- CHK(darray_page_resize(&buf->node_pages, nnode_pages) == RES_OK);
- goto exit;
-}
-
-static INLINE res_T
-ensure_allocated_attrs(struct octree_buffer* buf, const size_t nattrs)
-{
- char* attr_page = NULL;
- size_t nattr_pages = 0;
- res_T res = RES_OK;
- ASSERT(buf);
-
- if(buf->attr_head.ipage != OCTREE_INDEX_NULL.ipage
- && buf->attr_head.inode + nattrs <= buf->pagesize/buf->voxsize)
- goto exit;
-
- 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 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;
-
- buf->attr_head.inode = 0;
- buf->attr_head.ipage = (uint32_t)nattr_pages;
-
-exit:
- return res;
-error:
- if(attr_page) MEM_RM(buf->allocator, attr_page);
- CHK(darray_page_resize(&buf->attr_pages, nattr_pages) == RES_OK);
- goto exit;
-}
-
-/*******************************************************************************
- * Local functions
- ******************************************************************************/
-void
-octree_buffer_init
- (struct mem_allocator* allocator,
- const size_t voxel_size,
- struct octree_buffer* buf)
-{
- ASSERT(buf && allocator);
- memset(buf, 0, sizeof(struct octree_buffer));
- buf->pagesize = (size_t)sysconf(_SC_PAGESIZE);
- buf->voxsize = voxel_size;
- darray_page_init(allocator, &buf->node_pages);
- darray_page_init(allocator, &buf->attr_pages);
- buf->node_head = OCTREE_INDEX_NULL;
- buf->attr_head = OCTREE_INDEX_NULL;
- buf->allocator = allocator;
- CHK(buf->voxsize <= buf->pagesize);
-}
-
-void
-octree_buffer_release(struct octree_buffer* buf)
-{
- ASSERT(buf);
- octree_buffer_clear(buf);
- darray_page_release(&buf->node_pages);
- darray_page_release(&buf->attr_pages);
-}
-
-res_T
-octree_buffer_alloc_nodes
- (struct octree_buffer* buf,
- const size_t nnodes,
- struct octree_index* first_node)
-{
- res_T res = RES_OK;
- ASSERT(buf && first_node);
-
- if(nnodes > buf->pagesize / sizeof(struct octree_xnode))
- return RES_MEM_ERR;
-
- res = ensure_allocated_nodes(buf, nnodes);
- if(res != RES_OK) return res;
-
- *first_node = buf->node_head;
- buf->node_head.inode = (uint16_t)(buf->node_head.inode + nnodes);
- return RES_OK;
-
-}
-
-res_T
-octree_buffer_alloc_attrs
- (struct octree_buffer* buf,
- const size_t nattrs,
- struct octree_index* first_attr)
-{
- res_T res = RES_OK;
- ASSERT(buf && first_attr);
-
- if(nattrs > buf->pagesize / buf->voxsize) return RES_MEM_ERR;
-
- res = ensure_allocated_attrs(buf, nattrs);
- if(res != RES_OK) return res;
-
- *first_attr = buf->attr_head;
- buf->attr_head.inode = (uint16_t)(buf->attr_head.inode + nattrs);
- return RES_OK;
-}
-
-res_T
-octree_buffer_alloc_far_index
- (struct octree_buffer* buf,
- struct octree_index* id)
-{
- size_t remaining_size;
- size_t skipped_nnodes;
- STATIC_ASSERT(sizeof(struct octree_index) >= sizeof(struct octree_xnode),
- Unexpected_type_size);
-
- remaining_size = buf->pagesize - buf->node_head.inode*sizeof(struct octree_xnode);
-
- /* Not enough memory in the current page */
- if(sizeof(struct octree_index) > remaining_size) return RES_MEM_ERR;
-
- *id = buf->node_head;
- skipped_nnodes = sizeof(struct octree_index) / sizeof(struct octree_xnode);
- buf->node_head.inode = (uint16_t)(buf->node_head.inode + skipped_nnodes);
- return RES_OK;
-}
-
-void
-octree_buffer_clear(struct octree_buffer* buf)
-{
- size_t i;
- ASSERT(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->attr_pages)) {
- MEM_RM(buf->allocator, darray_page_data_get(&buf->attr_pages)[i]);
- }
- darray_page_purge(&buf->node_pages);
- darray_page_purge(&buf->attr_pages);
- buf->node_head = OCTREE_INDEX_NULL;
- buf->attr_head = OCTREE_INDEX_NULL;
-}
-
diff --git a/src/svx_octree_buffer.h b/src/svx_octree_buffer.h
@@ -1,248 +0,0 @@
-/* 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 SVX_OCTREE_BUFFER_H
-#define SVX_OCTREE_BUFFER_H
-
-#include "svx_c.h"
-#include <rsys/dynamic_array.h>
-
-/*
- * Buffer containing the data of an octree. These data are partitioned in fixed
- * size memory pages whose capacity is defined on buffer initialisation with
- * respect to the page size of the system.
- *
- * The children of a node are stored consecutively into a page. The parent node
- * directly references its first valid children excepted if they lie in a
- * different page. In this case, the node references a `struct octree_index',
- * 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 nodes are stored in their own 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)
-#define OCTREE_XNODE_MAX_CHILDREN_OFFSET (OCTREE_XNODE_FLAG_FAR_INDEX-1)
-#define OCTREE_XNODE_MASK OCTREE_XNODE_MAX_CHILDREN_OFFSET
-
-struct octree_xnode {
- /* 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 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 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
-
-struct octree_index {
- uint32_t ipage; /* Identifier of the page */
- uint16_t inode; /* Identifier of the node in the page */
- uint16_t dummy__; /* Padding to ensure the octree index is 8 bytes lenght */
-};
-STATIC_ASSERT(sizeof(struct octree_index) == 8,
- Unexpected_sizeof_octree_index);
-#define OCTREE_INDEX_NULL__ {UINT32_MAX, UINT16_MAX, UINT16_MAX}
-static const struct octree_index OCTREE_INDEX_NULL = OCTREE_INDEX_NULL__;
-#define OCTREE_INDEX_EQ(A, B) ((A)->inode==(B)->inode && (A)->ipage==(B)->ipage)
-
-/* Define the dynamic array of pages */
-#define DARRAY_NAME page
-#define DARRAY_DATA char*
-#include <rsys/dynamic_array.h>
-
-struct octree_buffer {
- size_t pagesize; /* Memory page size in bytes */
- size_t voxsize; /* Memory size of a voxel in bytes */
-
- struct darray_page node_pages; /* List of pages storing nodes */
- 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 attr_head; /* Index of the next valid attr */
-
- struct mem_allocator* allocator;
-};
-
-extern LOCAL_SYM void
-octree_buffer_init
- (struct mem_allocator* allocator,
- const size_t sizeof_voxel, /* Size in bytes of a voxel */
- struct octree_buffer* buf);
-
-extern LOCAL_SYM void
-octree_buffer_release
- (struct octree_buffer* buf);
-
-extern LOCAL_SYM res_T
-octree_buffer_alloc_nodes
- (struct octree_buffer* buf,
- const size_t nnodes,
- struct octree_index* first_node); /* Index toward the 1st allocated node */
-
-extern LOCAL_SYM res_T
-octree_buffer_alloc_attrs
- (struct octree_buffer* buf,
- 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
- * have to alloc new nodes */
-extern LOCAL_SYM res_T
-octree_buffer_alloc_far_index
- (struct octree_buffer* buf,
- struct octree_index* id); /* Index toward the allocated far index */
-
-extern LOCAL_SYM void
-octree_buffer_clear
- (struct octree_buffer* buf);
-
-static FINLINE int
-octree_buffer_is_empty(const struct octree_buffer* buf)
-{
- ASSERT(buf);
- return darray_page_size_get(&buf->node_pages) == 0;
-}
-
-static FINLINE struct octree_xnode*
-octree_buffer_get_node
- (struct octree_buffer* buf,
- const struct octree_index id)
-{
- char* mem;
- ASSERT(buf && id.inode < buf->pagesize/sizeof(struct octree_xnode));
- ASSERT(id.ipage < darray_page_size_get(&buf->node_pages));
- mem = darray_page_data_get(&buf->node_pages)[id.ipage];
- mem += id.inode * sizeof(struct octree_xnode);
- 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,
- const struct octree_index id)
-{
- char* mem;
- ASSERT(buf && id.inode < buf->pagesize/sizeof(struct octree_xnode));
- ASSERT(id.ipage < darray_page_size_get(&buf->node_pages));
- mem = darray_page_data_get(&buf->node_pages)[id.ipage];
- mem += id.inode * sizeof(struct octree_xnode);
- return (struct octree_index*)mem;
-}
-
-static FINLINE struct octree_index
-octree_buffer_get_child_node_index
- (struct octree_buffer* buf,
- const struct octree_index id,
- const int ichild) /* in [0, 7] */
-{
- struct octree_index child_id = OCTREE_INDEX_NULL;
- struct octree_xnode* node = NULL;
- 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);
- 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));
-
- 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)(offset + ichild_off);
- } else {
- 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_child_attr_index
- (struct octree_buffer* buf,
- const struct octree_index id,
- const int ichild) /* In [0, 7] */
-{
- struct octree_index child_id = OCTREE_INDEX_NULL;
- struct octree_xnode* node = NULL;
- 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);
- mask = node->is_valid;
- ASSERT(mask & ichild_flag);
-
- /* Compute the attr offset from the first child node */
- ichild_off = popcount((uint8_t)((ichild_flag-1) & (int)mask));
-
- 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];
- 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 size_t
-octree_buffer_absolute_attr_index
- (const struct octree_buffer* buf,
- const struct octree_index index)
-{
- ASSERT(buf);
- return index.ipage * buf->pagesize/buf->voxsize + index.inode;
-}
-
-#endif /* SVX_OCTREE_BUFFER_H */
diff --git a/src/svx_octree_trace_ray.c b/src/svx_octree_trace_ray.c
@@ -57,7 +57,7 @@ uitof(const uint32_t ui)
static FINLINE void
setup_hit
(struct svx_octree* oct,
- const struct octree_index iattr, /* Index toward the voxel attributes */
+ const struct buffer_index iattr, /* Index toward the voxel attributes */
const double distance, /* Hit distance */
const float corner[3], /* Corner of the current voxel in [1, 2]^3 space */
const double scale_exp2, /* Size of the voxel in [1, 2]^3] space */
@@ -71,9 +71,9 @@ setup_hit
ASSERT(distance > 0);
hit->distance = distance;
- hit->voxel.data = octree_buffer_get_attr(&oct->buffer, iattr);
+ hit->voxel.data = buffer_get_attr(&oct->buffer, iattr);
hit->voxel.depth = depth,
- hit->voxel.id = octree_buffer_absolute_attr_index(&oct->buffer, iattr);
+ hit->voxel.id = buffer_absolute_attr_index(&oct->buffer, iattr);
hit->voxel.is_leaf = is_leaf;
/* Transform the voxel aabb in the [0, 1]^3 normalized space and flip it wrt
@@ -175,10 +175,10 @@ trace_ray
{
#define SCALE_MAX 23 /* #mantisse bits */
struct stack_entry {
- struct octree_index inode;
+ struct buffer_index inode;
double t_max;
} stack[SCALE_MAX + 1/*Dummy entry use to avoid invalid read*/];
- struct octree_index inode;
+ struct buffer_index inode;
double t_min, t_max;
float corner[3];
float scale_exp2;
@@ -219,7 +219,7 @@ trace_ray
/* Octree traversal */
scale_max = scale + 1;
while(scale < scale_max && t_min < t_max) {
- const struct octree_xnode* node = octree_buffer_get_node(&oct->buffer, inode);
+ const struct buffer_xnode* node = buffer_get_node(&oct->buffer, inode);
double t_corner[3];
double t_max_corner;
double t_max_child;
@@ -245,7 +245,7 @@ trace_ray
struct svx_hit hit_tmp;
const double dst = t_min <= ray->range[0] ? t_max_child : t_min;
const size_t depth = SCALE_MAX - scale;
- const struct octree_index iattr = octree_buffer_get_child_attr_index
+ const struct buffer_index iattr = buffer_get_child_attr_index
(&oct->buffer, inode, (int)ichild_adjusted);
setup_hit(oct, iattr, dst, corner, scale_exp2, depth, is_leaf,
@@ -286,7 +286,7 @@ trace_ray
stack[scale].inode = inode;
/* Get the node index of the traversed child */
- inode = octree_buffer_get_child_node_index
+ inode = buffer_get_child_node_index
(&oct->buffer, inode, (int)ichild_adjusted);
/* Define the id and the lower left corner of the first grand child */
diff --git a/src/svx_tree_builder.h b/src/svx_tree_builder.h
@@ -0,0 +1,456 @@
+/* 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_BUILDER_H
+#define SVX_TREE_BUILDER_H
+
+#include "svx_buffer.h"
+
+#define TREE_DEPTH_MAX 16 /* Maximum depth of a tree */
+
+struct voxel {
+ uint64_t mcode; /* Morton code of the voxel */
+ void* data; /* Data of the voxel */
+};
+static const struct voxel VOXEL_NULL = {0, NULL};
+
+#endif /* SVX_TREE_BUILDER_H */
+#else /* TREE_DIMENSION */
+
+#if (TREE_DIMENSION<=0) || (TREE_DIMENSION>3)
+ #error "Invalid TREE_DIMENSION value"
+#endif
+
+#if TREE_DIMENSION == 1
+ #define XD(Name) CONCAT(bintree_, Name)
+#elif TREE_DIMENSION == 2
+ #define XD(Name) CONCAT(quadtree_, Name)
+#elif TREE_DIMENSION == 3
+ #define XD(Name) CONCAT(octree_, Name)
+#else
+ #error "Invalid TREE_DIMENSION value"
+#endif
+
+#define NCHILDREN BIT(TREE_DIMENSION)
+
+struct XD(node) {
+ struct buffer_index ichild_node; /* Index of the 1st child node */
+ struct buffer_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[NCHILDREN][SVX_MAX_SIZEOF_VOXEL]; /* Data of the leaves */
+};
+
+/* Stacked children of an tree node */
+struct XD(stack) {
+ struct XD(node) nodes[NCHILDREN]; /* List of registered children */
+ uint8_t mask; /* Mask of valid children nodes (0 = empty) */
+};
+
+struct XD(builder) {
+ struct XD(stack) stacks[TREE_DEPTH_MAX];
+ struct buffer* buffer;
+
+ const struct svx_voxel_desc* desc;
+ size_t nleaves; /* Number of emitted leaves */
+
+ int tree_depth; /* Maximum tree desc */
+ int non_empty_lvl; /* Index of the 1st non empty level */
+
+ uint64_t mcode; /* Morton code of the voxel */
+};
+
+/*******************************************************************************
+ * Stack functions
+ ******************************************************************************/
+#ifndef NDEBUG
+static void
+XD(check)(struct buffer* buf, const struct buffer_index root)
+{
+ const struct buffer_xnode* node;
+ int ichild;
+ ASSERT(buf);
+
+ node = buffer_get_node(buf, root);
+ FOR_EACH(ichild, 0, NCHILDREN) {
+ const int ichild_flag = BIT(ichild);
+ if((node->is_valid & ichild_flag) == 0) continue;
+
+ if(node->is_leaf & ichild_flag) {
+ struct buffer_index iattr;
+ iattr = buffer_get_child_attr_index(buf, root, ichild);
+ ASSERT(buffer_get_attr(buf, iattr) != NULL);
+ } else {
+ struct buffer_index child;
+ child = buffer_get_child_node_index(buf, root, ichild);
+ XD(check)(buf, child);
+ }
+ }
+}
+#endif
+
+static INLINE void
+XD(stack_clear)(struct XD(stack)* stack)
+{
+ int inode;
+ FOR_EACH(inode, 0, NCHILDREN) {
+ int ichild;
+ stack->nodes[inode].is_leaf = 0;
+ stack->nodes[inode].is_valid = 0;
+ stack->nodes[inode].ichild_node = BUFFER_INDEX_NULL;
+ stack->nodes[inode].ichild_attr = BUFFER_INDEX_NULL;
+ FOR_EACH(ichild, 0, NCHILDREN) {
+ memset(stack->nodes[inode].data[ichild], 0, SVX_MAX_SIZEOF_VOXEL);
+ }
+ }
+ stack->mask = 0;
+}
+
+/* Build a parent tree node from the registered stack nodes */
+static INLINE void
+XD(stack_setup_node)
+ (struct XD(stack)* stack,
+ struct XD(node)* node,
+ const struct svx_voxel_desc* desc)
+{
+ int ichild;
+ ASSERT(stack && node && check_svx_voxel_desc(desc));
+
+ node->ichild_node = BUFFER_INDEX_NULL;
+ node->ichild_attr = BUFFER_INDEX_NULL;
+ node->is_valid = stack->mask;
+ node->is_leaf = 0;
+
+ if(stack->mask == 0) return; /* Empty stack */
+
+ /* Try to merge the child's leaves */
+ FOR_EACH(ichild, 0, NCHILDREN) {
+ const void* data[NCHILDREN];
+ const uint8_t ichild_flag = (uint8_t)BIT(ichild);
+ struct XD(node)* child = stack->nodes + ichild;
+ int igrandchild;
+
+ /* Fetch the grandchildren data */
+ FOR_EACH(igrandchild, 0, NCHILDREN) {
+ data[igrandchild] = child->data[igrandchild];
+ }
+
+ desc->merge(node->data[ichild], data, NCHILDREN, desc->context);
+
+ if(child->is_leaf == (BIT(NCHILDREN)-1)/*all active bitmask*/
+ && desc->challenge_merge(data, NCHILDREN, desc->context)) {
+ /* The node becomes a leaf : the children does not exist anymore */
+ node->is_leaf |= ichild_flag;
+ stack->mask ^= ichild_flag;
+ }
+ }
+}
+
+static res_T
+XD(stack_write)
+ (struct XD(stack)* stack, /* Node to write */
+ struct buffer* buf, /* Buffer where nodes are written */
+ struct buffer_index* out_index, /* Index of the first written node */
+ size_t* out_nleaves) /* #writen leaves */
+{
+ struct buffer_index nodes_id = BUFFER_INDEX_NULL;
+ struct XD(node)* node = NULL;
+ size_t nleaves = 0;
+ int inode;
+ res_T res = RES_OK;
+ 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 attrib of the children */
+ FOR_EACH(inode, 0, NCHILDREN) {
+ 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;
+
+ nattrs = (size_t)popcount(node->is_valid);
+ ASSERT(nattrs > 0);
+
+ res = buffer_alloc_attrs(buf, nattrs, &node->ichild_attr);
+ if(res != RES_OK) goto error;
+
+ data = buffer_get_attr(buf, node->ichild_attr);
+ nvoxs = 0;
+ FOR_EACH(ichild, 0, NCHILDREN) {
+ if(!(node->is_valid & BIT(ichild))) continue;
+ memcpy(data + nvoxs*buf->voxsize, node->data[ichild], buf->voxsize);
+ ++nvoxs;
+ }
+ ASSERT(nvoxs == nattrs);
+ nleaves += (size_t)popcount(node->is_leaf);
+ }
+
+ do {
+ struct buffer_index index = BUFFER_INDEX_NULL;
+ struct buffer_xnode* xnodes = NULL;
+ const size_t nnodes = (size_t)popcount(stack->mask);
+ size_t ixnode = 0;
+
+ /* Alloc the tree nodes */
+ res = buffer_alloc_nodes(buf, (size_t)nnodes, &nodes_id);
+ if(res != RES_OK) goto error;
+ xnodes = buffer_get_node(buf, nodes_id);
+
+ FOR_EACH(inode, 0, NCHILDREN) {
+ 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 and children attribs */
+ if(node->ichild_node.ipage == nodes_id.ipage) {
+ node_offset = node->ichild_node.inode;
+ }
+ /* The page id of the children is not the same as that of node */
+ if(node_offset > BUFFER_XNODE_MAX_CHILDREN_OFFSET) {
+ res = buffer_alloc_far_index(buf, &index);
+ if(res != RES_OK) break;
+ *buffer_get_far_index(buf, index) = node->ichild_node;
+ node_offset = BUFFER_XNODE_FLAG_FAR_INDEX | index.inode;
+ }
+
+ /* Setup the offset toward the children attribs */
+ if(node->ichild_attr.ipage == nodes_id.ipage) {
+ attr_offset = node->ichild_attr.inode;
+ }
+
+ /* The page id of the attribs is not tthe same as that of node */
+ if(attr_offset > BUFFER_XNODE_FLAG_FAR_INDEX) {
+ res = buffer_alloc_far_index(buf, &index);
+ if(res != RES_OK) break;
+ *buffer_get_far_index(buf, index) = node->ichild_attr;
+ attr_offset = BUFFER_XNODE_FLAG_FAR_INDEX | index.inode;
+ }
+
+ xnodes[ixnode].node_offset = node_offset;
+ xnodes[ixnode].attr_offset = attr_offset;
+ xnodes[ixnode].is_valid = node->is_valid;
+ xnodes[ixnode].is_leaf = node->is_leaf;
+ ++ixnode;
+ }
+ /* inode < NCHILDREN <=> 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 < NCHILDREN);
+
+
+exit:
+ /* Return the index toward the first writen nodes */
+ *out_index = nodes_id;
+ *out_nleaves = nleaves;
+ return res;
+error:
+ goto exit;
+}
+
+
+/*******************************************************************************
+ * Builder functions
+ ******************************************************************************/
+static res_T
+XD(builder_init)
+ (struct XD(builder)* bldr,
+ const size_t definition,
+ const struct svx_voxel_desc* desc,
+ struct buffer* buffer)
+{
+ int ilvl;
+ res_T res = RES_OK;
+ ASSERT(bldr && IS_POW2(definition) && check_svx_voxel_desc(desc));
+ memset(bldr, 0, sizeof(struct XD(builder)));
+
+ /* Compute the maximum depth of the tree */
+ bldr->tree_depth = log2i((int)definition);
+ if(bldr->tree_depth > TREE_DEPTH_MAX) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+
+ /* Init the per tree level stack */
+ FOR_EACH(ilvl, 0, bldr->tree_depth) {
+ XD(stack_clear)(&bldr->stacks[ilvl]);
+ }
+
+ buffer_clear(buffer);
+ bldr->nleaves = 0;
+ bldr->desc = desc;
+ bldr->buffer = buffer;
+ bldr->non_empty_lvl = bldr->tree_depth - 1;
+
+exit:
+ return res;
+error:
+ goto exit;
+
+}
+
+static res_T
+XD(builder_add_voxel)
+ (struct XD(builder)* bldr,
+ 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);
+
+ /* Define if the bits in [4 .. 63] of the previous and the next Morton
+ * codes are the same */
+ mcode_xor = bldr->mcode ^ vox->mcode;
+
+ /* The next voxel is not in the current node */
+ if(mcode_xor >= 8) {
+ size_t ilvl;
+
+ inode = (bldr->mcode >> TREE_DIMENSION) & (NCHILDREN-1);
+ bldr->stacks[0].mask |= (uint8_t)BIT(inode);
+
+ /* Flush the stack of the tree level that does not contain the next voxel.
+ * The last tree 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->tree_depth-2/*The 2 last voxels contain all voxels*/) {
+ struct XD(node)* stack_node;
+ uint64_t mcode_max_lvl;
+ size_t nleaves;
+
+ /* Compute the maximum morton code value for the current tree level */
+ mcode_max_lvl =
+ NCHILDREN/*#children*/
+ * (1lu<<(TREE_DIMENSION*(ilvl+1)))/*#voxels per children*/;
+
+ if(mcode_xor < mcode_max_lvl) break;
+
+ /* Retrieve the node index of the next level */
+ inode = (bldr->mcode >> (TREE_DIMENSION*(ilvl+2))) & (NCHILDREN-1);
+
+ /* 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[inode];
+ XD(stack_setup_node)(&bldr->stacks[ilvl], stack_node, bldr->desc);
+ bldr->stacks[ilvl+1].mask |= (uint8_t)BIT(inode);
+
+ /* Write the nodes of the stack of the current tree level into the buf */
+ res = XD(stack_write)
+ (&bldr->stacks[ilvl], bldr->buffer, &stack_node->ichild_node, &nleaves);
+ if(res != RES_OK) goto error;
+
+ bldr->nleaves += nleaves;
+ if(nleaves) bldr->non_empty_lvl = MMIN(bldr->non_empty_lvl, (int)ilvl);
+
+ /* Reset the current stack */
+ XD(stack_clear)(&bldr->stacks[ilvl]);
+ }
+ }
+
+ /* Retrieve the index of the current voxel and of its parent */
+ ichild = vox->mcode & (NCHILDREN-1);
+ inode = (vox->mcode >> TREE_DIMENSION) & (NCHILDREN-1);
+ ichild_flag = (uint8_t)BIT(ichild);
+
+ /* Register the voxel */
+ memcpy(bldr->stacks[0].nodes[inode].data[ichild], vox->data, bldr->desc->size);
+ 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;
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+static INLINE res_T
+XD(builder_finalize)
+ (struct XD(builder)* bldr,
+ struct buffer_index* root_id,
+ void* root_data)
+{
+ const void* data[8];
+ size_t inode;
+ size_t nleaves;
+ int ilvl;
+ int ichild;
+ res_T res = RES_OK;
+ ASSERT(bldr);
+
+ inode = (bldr->mcode >> TREE_DIMENSION) & (NCHILDREN-1);
+ bldr->stacks[0].mask |= (uint8_t)BIT(inode);
+
+ /* Flush the stacked nodes */
+ FOR_EACH(ilvl, 0, bldr->tree_depth-1) {
+ struct XD(node)* parent_node;
+
+ if(bldr->stacks[ilvl].mask == 0) continue;
+
+ /* Retrieve the node index of the next level */
+ inode = (bldr->mcode >> (TREE_DIMENSION*(ilvl+2))) & (NCHILDREN-1);
+
+ /* Setup the parent node of the nodes registered into the current stack */
+ parent_node = &bldr->stacks[ilvl+1].nodes[inode]; /* Fetch the parent node */
+ XD(stack_setup_node)(&bldr->stacks[ilvl], parent_node, bldr->desc);
+ bldr->stacks[ilvl+1].mask |= (uint8_t)BIT(inode);
+
+ /* Write the stacked nodes of the current level */
+ res = XD(stack_write)
+ (&bldr->stacks[ilvl], bldr->buffer, &parent_node->ichild_node, &nleaves);
+ if(res != RES_OK) goto error;
+ bldr->nleaves += nleaves;
+ }
+
+ ilvl = bldr->tree_depth-1; /* Root level */
+
+ /* Write the root node */
+ res = XD(stack_write)(&bldr->stacks[ilvl], bldr->buffer, root_id, &nleaves);
+ if(res != RES_OK) goto error;
+ bldr->nleaves += nleaves;
+
+ /* Setup the root attribs */
+ ASSERT(bldr->stacks[ilvl].mask == 1); /* Only the root node is active */
+ FOR_EACH(ichild, 0, NCHILDREN) {
+ data[ichild] = bldr->stacks[ilvl].nodes[0].data[ichild];
+ }
+ bldr->desc->merge(root_data, data, NCHILDREN, bldr->desc->context);
+
+exit:
+ return res;
+error:
+ goto exit;
+}
+
+#undef TREE_DIMENSION
+#undef NCHILDREN
+#undef XD
+
+#endif /* !TREE_DIMENSION */
