commit 9a2da88754a9b5042ec8ef8d501912ec209b4542
parent c9547d0f09ee927cd75266ed4be104fa9de5f4f9
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Mon, 5 Feb 2018 09:23:08 +0100
Finalize the draft of the octree build
Implement the "octree buffer" and make the source code compilable.
Diffstat:
7 files changed, 500 insertions(+), 292 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -42,9 +42,11 @@ set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(HTVOX_FILES_SRC
htvox_device.c
+ htvox_octree_buffer.c
htvox_scene.c)
set(SSOL_FILES_INC
htvox_device.h
+ htvox_octree_buffer.h
htvox_scene.h)
set(SSOL_FILES_INC_API
htvox.h)
diff --git a/src/htvox.h b/src/htvox.h
@@ -84,6 +84,7 @@ htvox_scene_create
const double upper[3], /* Upper bound of the scene */
const size_t nvoxels[3], /* # voxels along the 3 axis */
void (*get)(const size_t xyz[3], double* value, void* ctx),
+ int (*merge)(const double min_val, const double max_val),
void* context, /* Client data send as the last param of the `get' callback */
struct htvox_scene** scn);
diff --git a/src/htvox_octree.h b/src/htvox_octree.h
@@ -1,183 +0,0 @@
-/* Copyright (C) CNRS 2018
- *
- * 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 HTVOX_OCTREE_H
-#define HTVOX_OCTREE_H
-
-#include <rsys/dynamic_array.h>
-
-/*
- * Incore buffer of octree data partitioned in fixed sized memory pages.
- *
- * The nodes are stored in pages whose memory size is defined at the init of
- * the buffer. The node children are indexed relatively to their parent node
- * excepted if the relative offset is too high regarding the encoding precision
- * of the offset, or if the children are stored in another page. In such cases,
- * the node relatively references an 'octree_index', allocated in the same
- * page, that defines the absolute position of the children in the buffer.
- *
- * Leaf attributes are stored in a separate buffer and are indexed either
- * relatively, or absolutely by the leaf node storing, following the same
- * aforementioned indexing procedure of the node children.
- */
-#define OCTREE_XNODE_FLAG_FAR_INDEX_FLAG BIT(31)
-#define OCTREE_XNODE_FLAG_LEAF_FLAG BIT(30)
-#define OCTREE_XNODE_MAX_CHILDREN_OFFSET (BIT(30)-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) */
- uint32_t offset;
-};
-
-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 */
-
- /* Number of per page nodes. */
- size_t page_nnodes;
-
- struct darray_page node_pages; /* List of pages storing nodes */
- struct darray_page leaf_pages; /* List of pages storing leaves */
- struct octree_index node_head; /* Index of the next valid node */
- struct octree_index leaf_head; /* Index of the next valid leaf */
-
- struct mem_allocator* allocator;
-};
-
-extern LOCAL_SYM void
-octree_buffer_init
- (struct mem_allocator* allocator,
- 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_leaves
- (struct octree_buffer* buf,
- const size_t nleaves,
- struct octree_index* first_leaf); /* Index toward the 1st allocated leaf */
-
-/* Allocate a 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_node));
- 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 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_node));
- ASSERT(id.ipage < darray_page_size_get(&buf->node_pages));
- mem = darray_node_page_data_get(&buf->node_pages)[id.ipage];
- mem += id.inode * sizeof(struct octree_xnode);
- return (struct octree_index*)mem;
-}
-
-static FINLINE double*
-octree_buffer_get_leaf
- (struct octree_buffer* buf,
- const struct octree_index id)
-{
- char* mem;
- ASSERT(buf && id.inode < buf->pagesize/sizeof(double));
- ASSERT(id.ipage < darray_page_size_get(&buf->leaf_pages));
- mem = darray_page_data_get(&buf->leaf_pages)[id.ipage];
- mem += id.inode * sizeof(double);
- return (double*)mem;
-}
-
-static FINLINE struct octree_index
-octree_byffer_get_child_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;
- uint32_t node_offset;
- ASSERT(ichild >= 0 && ichild < 8 && buf);
-
- node = octree_buffer_get_node(buf, id);
- node_offset = (node->offset & OCTREE_XNODE_MASK);
-
- if(!(node->offset & OCTREE_XNODE_FLAG_FAR_INDEX)) {
- child_id.ipage = id.ipage;
- child_id.inode = id.inode - node_offset + ichild;
- } else {
- child_id = *(struct octree_index*)
- ((char*)node + node_offset*sizeof(struct octree_index));
- child_id.inode = child_id.node_offset + ichild;
- }
- return child_id;
-}
-
-#endif /* HTVOX_OCTREE_H */
diff --git a/src/htvox_octree_buffer.c b/src/htvox_octree_buffer.c
@@ -0,0 +1,191 @@
+/* Copyright (C) CNRS 2018
+ *
+ * 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 "htvox_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);
+ 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;
+
+ ASSERT(nnode_pages <= UINT32_MAX);
+ 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_leaves(struct octree_buffer* buf, const size_t nleaves)
+{
+ char* leaf_page = NULL;
+ size_t nleaf_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/sizeof(double))
+ goto exit;
+
+ nleaf_pages = darray_page_size_get(&buf->leaf_pages);
+ ASSERT(nleaf_pages == buf->leaf_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);
+ if(res != RES_OK) goto error;
+
+ ASSERT(nleaf_pages <= UINT32_MAX);
+ buf->leaf_head.inode = 0;
+ buf->leaf_head.ipage = (uint32_t)nleaf_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);
+ goto exit;
+}
+
+/*******************************************************************************
+ * Local functions
+ ******************************************************************************/
+void
+octree_buffer_init(struct mem_allocator* allocator, struct octree_buffer* buf)
+{
+ ASSERT(buf && allocator);
+ memset(buf, 0, sizeof(struct octree_buffer));
+ buf->pagesize = (size_t)sysconf(_SC_PAGESIZE);
+ darray_page_init(allocator, &buf->node_pages);
+ darray_page_init(allocator, &buf->leaf_pages);
+ buf->node_head = OCTREE_INDEX_NULL;
+ buf->leaf_head = OCTREE_INDEX_NULL;
+ buf->allocator = allocator;
+}
+
+void
+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);
+}
+
+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_leaves
+ (struct octree_buffer* buf,
+ const size_t nleaves,
+ struct octree_index* first_leaf)
+{
+ res_T res = RES_OK;
+ ASSERT(buf && first_leaf);
+
+ if(nleaves >= buf->pagesize / sizeof(double)) return RES_MEM_ERR;
+
+ res = ensure_allocated_leaves(buf, nleaves);
+ if(res != RES_OK) return res;
+
+ *first_leaf = buf->leaf_head;
+ buf->leaf_head.inode = (uint16_t)(buf->leaf_head.inode + nleaves);
+ 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->leaf_pages)) {
+ MEM_RM(buf->allocator, darray_page_data_get(&buf->leaf_pages)[i]);
+ }
+ darray_page_purge(&buf->node_pages);
+ darray_page_purge(&buf->leaf_pages);
+ buf->node_head = OCTREE_INDEX_NULL;
+ buf->leaf_head = OCTREE_INDEX_NULL;
+}
+
diff --git a/src/htvox_octree_buffer.h b/src/htvox_octree_buffer.h
@@ -0,0 +1,188 @@
+/* Copyright (C) CNRS 2018
+ *
+ * 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 HTVOX_OCTREE_BUFFER_H
+#define HTVOX_OCTREE_BUFFER_H
+
+#include <rsys/dynamic_array.h>
+
+/*
+ * Buffer of octree data partitioned in fixed sized memory pages.
+ *
+ * The nodes are stored in pages whose memory size is defined at the init of
+ * the buffer. The node children are indexed relatively to their parent node
+ * excepted if the relative offset is too high regarding the encoding precision
+ * of the offset, or if the children are stored in another page. In such cases,
+ * the node relatively references an 'octree_index', allocated in the same
+ * page, that defines the absolute position of the children in the buffer.
+ *
+ * Leaf attributes are stored in a separate buffer and are indexed either
+ * relatively, or absolutely by the leaf node storing, following the same
+ * aforementioned indexing procedure of the node children.
+ */
+
+#define OCTREE_XNODE_FLAG_FAR_INDEX 0x80000000u
+#define OCTREE_XNODE_FLAG_LEAF 0x40000000u
+#define OCTREE_XNODE_EMPTY 0xC0000000u
+#define OCTREE_XNODE_MAX_CHILDREN_OFFSET (BIT(30)-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 offset is equal to OCTREE_XNODE_EMPTY, then the node does not
+ * contain anything and thus has no child. */
+ uint32_t offset;
+};
+
+#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 */
+
+ struct darray_page node_pages; /* List of pages storing nodes */
+ struct darray_page leaf_pages; /* List of pages storing leaves */
+ struct octree_index node_head; /* Index of the next valid node */
+ struct octree_index leaf_head; /* Index of the next valid leaf */
+
+ struct mem_allocator* allocator;
+};
+
+extern LOCAL_SYM void
+octree_buffer_init
+ (struct mem_allocator* allocator,
+ 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_leaves
+ (struct octree_buffer* buf,
+ const size_t nleaves,
+ struct octree_index* first_leaf); /* Index toward the 1st allocated leaf */
+
+/* Allocate a 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 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 double*
+octree_buffer_get_leaf
+ (struct octree_buffer* buf,
+ const struct octree_index id)
+{
+ char* mem;
+ ASSERT(buf && id.inode < buf->pagesize/sizeof(double));
+ ASSERT(id.ipage < darray_page_size_get(&buf->leaf_pages));
+ mem = darray_page_data_get(&buf->leaf_pages)[id.ipage];
+ mem += id.inode * sizeof(double);
+ return (double*)mem;
+}
+
+static FINLINE struct octree_index
+octree_buffer_get_child_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;
+ uint32_t node_offset;
+ ASSERT(ichild >= 0 && ichild < 8 && buf);
+
+ node = octree_buffer_get_node(buf, id);
+ if(node->offset == OCTREE_XNODE_EMPTY) return OCTREE_INDEX_NULL;
+ node_offset = (node->offset & OCTREE_XNODE_MASK);
+
+ if(!(node->offset & OCTREE_XNODE_FLAG_FAR_INDEX)) {
+ child_id.ipage = id.ipage;
+ child_id.inode = (uint16_t)(id.inode - node_offset + (uint32_t)ichild);
+ } else {
+ child_id = *(struct octree_index*)
+ ((char*)node + node_offset*sizeof(struct octree_index));
+ child_id.inode = (uint16_t)(child_id.inode + ichild);
+ }
+ return child_id;
+}
+
+#endif /* HTVOX_OCTREE_BUFFER_H */
diff --git a/src/htvox_scene.c b/src/htvox_scene.c
@@ -24,30 +24,9 @@
struct voxel {
uint64_t mcode; /* Morton code of the voxel */
- double data; /* Data of the voxel */
-};
-
-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 OCTREE_XNODE_FLAG_FAR_INDEX_FLAG BIT(31)
-#define OCTREE_XNODE_FLAG_LEAF_FLAG BIT(30)
-#define OCTREE_XNODE_MAX_CHILDREN_OFFSET (BIT(30)-1)
-#define OCTREE_XNODE_MASK OCTREE_XNODE_MAX_CHILDREN_OFFSET
-
-struct octree_xnode {
- uint32_t offset;
+ double data; /* Data of the voxel. -DBL_MAX == empty voxels */
};
+#define VOXEL_EMPTY_DATA -DBL_MAX
struct octree_node {
struct octree_index ichildren; /* Index of the 1st child */
@@ -63,6 +42,8 @@ struct stack {
struct octree_builder {
struct stack stacks[OCTREE_DEPTH_MAX];
+ struct octree_buffer* buffer;
+ int (*merge)(const double min_val, const double max_val);
int octree_depth;
uint64_t mcode; /* Morton code of the last registered voxels */
};
@@ -77,26 +58,30 @@ stack_clear(struct stack* stack)
FOR_EACH(inode, 0, 8) {
stack->nodes[inode].is_leaf = 0;
stack->nodes[inode].data = 0;
- stack->ichildren = OCTREE_INDEX_NULL;
+ stack->nodes[inode].ichildren = OCTREE_INDEX_NULL;
}
stack->len = 0;
}
/* Build a parent octree node from the registered stack nodes */
static INLINE void
-stack_setup_node(struct stack* stack, struct octree_node* node)
+stack_setup_node
+ (struct stack* stack,
+ struct octree_node* node,
+ int (*merge_func)(const double min_val, const double max_val))
{
double data_min = DBL_MAX;
double data_max =-DBL_MAX;
int challenge_leaves_merging = 1;
int ichild;
- ASSERT(stack && stack->mask != 0 && node);
+ ASSERT(stack && node && stack->len == 8/*The octree is not sparse*/);
+ ASSERT(merge_func);
node->ichildren = OCTREE_INDEX_NULL;
- /* Find the minimum and maximum data of the children */
+ /* Find the minimum and maximum of the children data */
FOR_EACH(ichild, 0, 8) {
- if(!stach->nodes[ichild].is_leaf) { /* Could merge only leaf nodes */
+ if(!stack->nodes[ichild].is_leaf) { /* Could merge only leaf nodes */
challenge_leaves_merging = 0;
break;
}
@@ -104,14 +89,22 @@ stack_setup_node(struct stack* stack, struct octree_node* node)
data_max = MMAX(stack->nodes[ichild].data, data_max);
}
- if(challenge_leaves_merging && merge(data_min, data_max)) {
- node->is_leaf = 1;
- node->data = data_max;
- /* Notify that the stacked nodes does not exist anymore: they are merged */
- stack->len = 0;
- } else {
+ 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);
+ }
+ 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;
+ }
}
}
@@ -129,57 +122,63 @@ stack_write
/* No registered nodes <=> nodes were merged in an higher level */
if(!stack->len) goto exit;
+ ASSERT(stack->len == 8/*legacy stack*/ || stack->len == 1/*root stack*/);
+
do {
struct octree_xnode* xnodes = NULL;
- /* Alloc the 8 octree nodes */
- res = octree_buffer_alloc_nodes(buffer, 8, &nodes_id);
+ /* Alloc the octree nodes */
+ res = octree_buffer_alloc_nodes(buffer, (size_t)stack->len, &nodes_id);
if(res != RES_OK) goto error;
xnodes = octree_buffer_get_node(buffer, nodes_id);
FOR_EACH(inode, 0, stack->len) {
- const struct octree_node* node = stack->nodes + inode;
+ struct octree_node* node = stack->nodes + inode;
size_t offset = SIZE_MAX;
- if(node->is_leaf) {
- double* leaf;
-
- /* Alloc the leaf node */
- ASSERT(OCTREE_INDEX_EQ(node->ichildren, OCTREE_INDEX_NULL));
- res = octree_buffer_alloc_leaf(buffer, 1, &node->ichildren);
- if(res != RES_OK) goto error;
-
- /* Setup the leaf data */
- leaf = octree_buffer_get_leaf(buffer, &node->ichildren);
- *leaf = node->data;
+ if(node->data == VOXEL_EMPTY_DATA) {
+ xnodes[inode].offset = OCTREE_XNODE_EMPTY;
+ } else {
+ if(node->is_leaf) {
+ double* leaf;
+
+ /* Alloc the leaf node */
+ ASSERT(OCTREE_INDEX_EQ(&node->ichildren, &OCTREE_INDEX_NULL));
+ res = octree_buffer_alloc_leaves(buffer, 1, &node->ichildren);
+ if(res != RES_OK) goto error;
+
+ /* Setup the leaf data */
+ leaf = octree_buffer_get_leaf(buffer, node->ichildren);
+ *leaf = node->data;
+ }
+
+ /* 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;
+ }
+
+ /* Offset is too high. Allocate a far index */
+ if(offset > OCTREE_XNODE_MAX_CHILDREN_OFFSET) {
+ 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. */
+ 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(node->is_leaf) {
+ offset = offset | OCTREE_XNODE_FLAG_LEAF;
+ }
+ xnodes[inode].offset = (uint32_t)offset;
}
-
- /* Define the offset toward the children of the current node */
- if(node->ichildren.page == nodes_id.page) {
- offset = (node_id.inode + (size_t)inode) - node->ichildren.inode;
- }
-
- /* Offset is too high. Allocate a far index */
- if(offset > OCTREE_XNODE_MAX_CHILDREN_OFFSET) {
- 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. */
- 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 - (node_id.inode + (size_t)inode));
- offset = offset | OCTREE_XNODE_FLAG_FAR_INDEX;
- }
-
- if(node->is_leaf) {
- offset |= OCTREE_XNODE_FLAG_LEAF;
- }
- xnodes[inode].offset = offset;
}
} while(inode < stack->len);
@@ -192,16 +191,16 @@ error:
goto exit;
}
-static INLINE
-
static res_T
octree_builder_init
(struct octree_builder* bldr,
- const size_t definition)
+ const size_t definition,
+ int (*merge)(const double min_val, const double max_val),
+ struct octree_buffer* buffer)
{
int ilvl;
res_T res = RES_OK;
- ASSERT(bldr && IS_POW2(definition));
+ ASSERT(bldr && IS_POW2(definition) && merge);
memset(bldr, 0, sizeof(struct octree_builder));
/* Compute the maximum depth of the octree */
@@ -216,6 +215,10 @@ octree_builder_init
stack_clear(&bldr->stacks[ilvl]);
}
+ octree_buffer_clear(buffer);
+ bldr->merge = merge;
+ bldr->buffer = buffer;
+
exit:
return res;
error:
@@ -226,6 +229,7 @@ static res_T
octree_builder_add_voxel(struct octree_builder* bldr, const struct voxel* vox)
{
uint64_t mcode_xor;
+ 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
@@ -234,6 +238,8 @@ octree_builder_add_voxel(struct octree_builder* bldr, const struct voxel* vox)
/* The next voxel is not in the current node */
if(mcode_xor >= 8) {
+ size_t ilvl;
+
/* 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 */
@@ -249,12 +255,12 @@ octree_builder_add_voxel(struct octree_builder* bldr, const struct voxel* vox)
/* 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_setup_node(&bldr->stacks[ilvl], stack_node);
+ stack_setup_node(&bldr->stacks[ilvl], stack_node, bldr->merge);
bldr->stacks[ilvl+1].len += 1;
ASSERT(bldr->stacks[ilvl+1].len <= 8);
- /* Write the nodes of the stack of the current octree level into the octree */
- ASSERT(stacks[ilvl].len == 8); /* The octree is not sparse */
+ /* Write the nodes of the stack of the current octree level into the buf */
+ ASSERT(bldr->stacks[ilvl].len == 8); /* The octree is not sparse */
res = stack_write(&bldr->stacks[ilvl], bldr->buffer, &stack_node->ichildren);
if(res != RES_OK) goto error;
@@ -265,10 +271,10 @@ octree_builder_add_voxel(struct octree_builder* bldr, const struct voxel* vox)
/* Register the voxel */
bldr->mcode = vox->mcode;
- bldr->stack[0].nodes[bldr->stack[0].len].data = vox->data;
- bldr->stack[0].nodes[bldr->stack[0].len].children = OCTREE_INDEX_NULL;
- bldr->stack[0].nodes[bldr->stack[0].len].is_leaf = 1;
- bldr->stack[0].len += 1;
+ 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;
@@ -317,21 +323,19 @@ htvox_scene_create
const double upper[3], /* Upper bound of the scene */
const size_t nvoxels[3], /* # voxels along the 3 axis */
void (*get)(const size_t xyz[3], double* value, void* ctx),
+ int (*merge)(const double min_val, const double max_val),
void* context, /* Client data send as the last param of the `get' callback */
struct htvox_scene** out_scn)
{
struct htvox_scene* scn = NULL;
- double sz[3]; /* Size of the scene AABB */
- double vox_sz; /* World space size of a voxel */
+ double vox_sz[3]; /* World space size of a voxel */
double vox_sz_max; /* Max voxel size */
- double vox_scale[3]; /* Scale factor of the voxel size */
- struct stack stacks[OCTREE_DEPTH_MAX];
+ struct octree_builder bldr;
uint64_t mcode_max;
- uint64_t imcode;
- int octree_depth;
+ uint64_t mcode;
res_T res = RES_OK;
- if(!dev || !lower || !upper || !nvoxels || !get || !out_scn) {
+ if(!dev || !lower || !upper || !nvoxels || !get || !merge || !out_scn) {
res = RES_BAD_ARG;
goto error;
}
@@ -363,6 +367,7 @@ htvox_scene_create
}
ref_init(&scn->ref);
HTVOX(device_ref_get(dev));
+ octree_buffer_init(dev->allocator, &scn->buffer);
scn->dev = dev;
/* Compute the voxel size in world space */
@@ -380,33 +385,35 @@ htvox_scene_create
if(vox_sz[2] != vox_sz_max) scn->vox_scale[2] = vox_sz_max / vox_sz[2];
/* Compute the octree definition */
- scn->definition = MAX(nvoxels[0], 1);
- scn->definition = MAX(nvoxels[1], scn->definition);
- scn->definition = MAX(nvoxels[2], scn->definition);
+ scn->definition = MMAX(nvoxels[0], 1);
+ scn->definition = MMAX(nvoxels[1], scn->definition);
+ scn->definition = MMAX(nvoxels[2], scn->definition);
scn->definition = round_up_pow2(scn->definition);
/* Intialize the octree builder */
- res = octree_builder_init(&bldr, scn->definition);
+ res = octree_builder_init(&bldr, scn->definition, merge, &scn->buffer);
if(res != RES_OK) goto error;
mcode_max = scn->definition * scn->definition * scn->definition;
FOR_EACH(mcode, 0, mcode_max) {
- struct voxel vox:
+ struct voxel vox;
uint32_t ui3[3];
- const size_t xyz[3];
morton_xyz_decode_u21(mcode, ui3);
/* Out of bound voxels */
- if(ui3[0] > nvoxels[0]) continue;
- if(ui3[1] > nvoxels[1]) continue;
- if(ui3[2] > nvoxels[2]) continue;
- xyz[0] = (size_t)ui3[0];
- xyz[1] = (size_t)ui3[1];
- xyz[2] = (size_t)ui3[2];
-
- /* Retrieve the voxel data from the caller */
- get(xyz, &vox.data, context);
+ 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);
+ }
vox.mcode = mcode;
/* Register the voxel against the octree */
diff --git a/src/htvox_scene.h b/src/htvox_scene.h
@@ -16,12 +16,14 @@
#ifndef HTVOX_SCENE_H
#define HTVOX_SCENE_H
+#include "htvox_octree_buffer.h"
#include <rsys/ref_count.h>
struct htvox_scene {
double vox_scale[3]; /* Scale factor of the octree */
- double definition; /* Definition of the octree */
+ size_t definition; /* Definition of the octree */
+ struct octree_buffer buffer;
struct octree_index root; /* Index toward the root node of the octree */
struct htvox_device* dev;
