commit 788560648e7809168b0afa5fb4f157bca6458466
parent da20b8fccea4de3285fade7986b79cb119c76ced
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 4 May 2018 09:09:38 +0200
Begin the implementation of the binary tree
Diffstat:
5 files changed, 229 insertions(+), 3 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -41,11 +41,13 @@ set(VERSION_PATCH 0)
set(VERSION ${VERSION_MAJOR}.${VERSION_MINOR}.${VERSION_PATCH})
set(SVX_FILES_SRC
+ svx_bintree.c
svx_buffer.c
svx_device.c
svx_octree.c
svx_octree_trace_ray.c)
set(SSOL_FILES_INC
+ svx_bintree.h
svx_buffer.h
svx_device.h
svx_octree.h)
diff --git a/src/svx.h b/src/svx.h
@@ -40,6 +40,12 @@
/* Maximum memory size of a voxel */
#define SVX_MAX_SIZEOF_VOXEL (sizeof(double)*16)
+enum svx_axis {
+ SVX_AXIS_X,
+ SVX_AXIS_Y,
+ SVX_AXIS_Z
+};
+
/* Volume element */
struct svx_voxel {
double lower[3], upper[3]; /* AABB of the voxel */
@@ -246,6 +252,7 @@ svx_bintree_create
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 enum svx_axis axis, /* Axis along which the binary tree is defined */
const struct svx_voxel_desc* desc, /* Descriptor of a voxel */
struct svx_bintree** bintree);
diff --git a/src/svx_bintree.c b/src/svx_bintree.c
@@ -0,0 +1,176 @@
+/* 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.h"
+#include "svx_c.h"
+#include "svx_device.h"
+#include "svx_bintree.h"
+#include "svx_tree_builder.h"
+
+#include <rsys/mem_allocator.h>
+
+/* Generate the bintree_builder API */
+#define TREE_DIMENSION 1
+#include "svx_tree_builder.h"
+
+/*******************************************************************************
+ * Helper functions
+ ******************************************************************************/
+static void
+bintree_release(ref_T* ref)
+{
+ struct svx_bintree* bintree;
+ struct svx_device* dev;
+ ASSERT(ref);
+ bintree = CONTAINER_OF(ref, struct svx_bintree, ref);
+ dev = bintree->dev;
+ MEM_RM(dev->allocator, bintree);
+ SVX(device_ref_put(dev));
+}
+
+/*******************************************************************************
+ * Exported functions
+ ******************************************************************************/
+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 enum svx_axis axis, /* Axis along which the binary tree is defined */
+ const struct svx_voxel_desc* desc, /* Descriptor of a voxel */
+ struct svx_bintree** out_bintree)
+{
+ struct svx_bintree* bintree = NULL;
+ double vox_sz; /* World space size of a voxel */
+ struct bintree_builder bldr;
+ struct voxel vox = VOXEL_NULL;
+ size_t ivox;
+ res_T res = RES_OK;
+
+ if(!dev || !lower || !upper || !nvoxels || !check_svx_voxel_desc(desc)
+ || !bintree || axis < 0 || axis > 2) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ if(lower >= upper) {
+ log_err(dev,
+ "%s: the submitted range is degenrated\n"
+ "\tlower = %g, upper = %g\n", FUNC_NAME, lower, upper);
+ res = RES_BAD_ARG;
+ goto error;
+ }
+ if(!nvoxels) {
+ log_err(dev,
+ "%s: the number of voxels along cannot be null.\n"
+ "\t#voxels = %lu.\n",
+ FUNC_NAME, (unsigned long)nvoxels);
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ bintree = MEM_CALLOC(dev->allocator, 1, sizeof(*bintree));
+ if(!bintree) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+ ref_init(&bintree->ref);
+ SVX(device_ref_get(dev));
+ buffer_init(dev->allocator, desc->size, &bintree->buffer);
+ bintree->dev = dev;
+
+ /* The binary tree definition that must be a power of two */
+ bintree->definition = round_up_pow2(nvoxels);
+
+ /* Initialize the bintree builder */
+ res = bintree_builder_init(&bldr, bintree->definition, desc, &bintree->buffer);
+ if(res != RES_OK) goto error;
+
+ /* Allocate the memory space of a temporary voxel */
+ vox.data = MEM_CALLOC(dev->allocator, 1, desc->size);
+ if(!vox.data) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+
+ FOR_EACH(ivox, 0, bintree->definition) {
+ size_t xyz[3] = {0, 0, 0};
+ if(ivox > nvoxels) continue; /* Out of bound voxels */
+
+ /* Retrieve the voxel data from the caller */
+ xyz[axis] = ivox;
+ desc->get(xyz, vox.data, desc->context);
+ vox.mcode = ivox;
+
+ /* Register the voxel against the bintree */
+ res = bintree_builder_add_voxel(&bldr, &vox);
+ if(res != RES_OK) goto error;
+ }
+
+ res = bintree_builder_finalize(&bldr, &bintree->root, bintree->root_attr);
+ if(res != RES_OK) goto error;
+
+ bintree->nleaves = bldr.nleaves;
+ bintree->depth = (size_t)(bldr.tree_depth - bldr.non_empty_lvl)
+ + 1 /* leaf level */;
+ ASSERT(bldr.tree_depth > bldr.non_empty_lvl);
+
+#ifndef NDEBUG
+ bintree_check(&bintree->buffer, bintree->root);
+#endif
+
+ bintree->lower = lower;
+ bintree->upper = upper;
+ bintree->axis = axis;
+
+ /* Compute the world space range of the binary tree */
+ vox_sz = (upper - lower) / (double)nvoxels;
+ bintree->tree_low = lower;
+ bintree->tree_upp = bintree->tree_low + (double)bintree->definition * vox_sz;
+ bintree->tree_sz = bintree->tree_upp - bintree->tree_low;
+
+ /* Adjuste the binary tree definition with respect to the binary tree depth
+ * since finest levels might be removed during the build due to the merging
+ * process */
+ bintree->definition = bintree->definition / (1u<<bldr.non_empty_lvl);
+
+exit:
+ if(vox.data) MEM_RM(dev->allocator, vox.data);
+ if(out_bintree) *out_bintree = bintree;
+ return res;
+error:
+ if(bintree) {
+ SVX(bintree_ref_put(bintree));
+ bintree = NULL;
+ }
+ goto exit;
+}
+
+res_T
+svx_bintree_ref_get(struct svx_bintree* bintree)
+{
+ if(!bintree) return RES_BAD_ARG;
+ ref_get(&bintree->ref);
+ return RES_OK;
+}
+
+res_T
+svx_bintree_ref_put(struct svx_bintree* bintree)
+{
+ if(!bintree) return RES_BAD_ARG;
+ ref_put(&bintree->ref, bintree_release);
+ return RES_OK;
+}
+
diff --git a/src/svx_bintree.h b/src/svx_bintree.h
@@ -0,0 +1,42 @@
+/* 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_BINTREE_H
+#define SVX_BINTREE_H
+
+#include "svx_buffer.h"
+#include <rsys/ref_count.h>
+
+struct svx_bintree {
+ size_t definition;
+
+ double lower, upper; /* Submitted World space AABB of the bintree */
+ double tree_low, tree_upp; /* Adjusted World space AABB of the bintree */
+ double tree_sz; /* World space size of the bintree */
+ enum svx_axis axis; /* Axis along wich the binary tree is defined */
+
+ 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 */
+ size_t depth;
+
+ struct svx_device* dev;
+ ref_T ref;
+};
+
+#endif /* SVX_BINTREE_H */
+
diff --git a/src/svx_octree.c b/src/svx_octree.c
@@ -17,13 +17,12 @@
#include "svx_c.h"
#include "svx_device.h"
#include "svx_octree.h"
-
#include "svx_tree_builder.h"
#include <rsys/double3.h>
#include <rsys/mem_allocator.h>
-/* Generate the tree_builder_3d data structure */
+/* Generate the octree_builder API */
#define TREE_DIMENSION 3
#include "svx_tree_builder.h"
@@ -172,7 +171,7 @@ svx_octree_create
oct->ocsize[2] = oct->ocupp[2] - oct->oclow[2];
/* Adjust the octree definition with respect to the octree depth since finest
- * levels might be removed by the build process due to the merging process */
+ * levels might be removed during the build due to the merging process */
oct->definition = oct->definition / (1u << bldr.non_empty_lvl);
exit:
