commit ba56897138cad5caf3b0816d48d990511f665751
parent 788560648e7809168b0afa5fb4f157bca6458466
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 4 May 2018 10:09:22 +0200
Replace the <oc|bin>tree structures by a generic tree structure
Diffstat:
12 files changed, 338 insertions(+), 342 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -45,12 +45,13 @@ set(SVX_FILES_SRC
svx_buffer.c
svx_device.c
svx_octree.c
- svx_octree_trace_ray.c)
+ svx_octree_trace_ray.c
+ svx_tree.c)
set(SSOL_FILES_INC
- svx_bintree.h
svx_buffer.h
svx_device.h
- svx_octree.h)
+ svx_octree.h
+ svx_tree.h)
set(SSOL_FILES_INC_API
svx.h)
diff --git a/src/svx.h b/src/svx.h
@@ -43,7 +43,13 @@
enum svx_axis {
SVX_AXIS_X,
SVX_AXIS_Y,
- SVX_AXIS_Z
+ SVX_AXIS_Z,
+ SVX_AXIS_NONE__
+};
+
+enum svx_tree_type {
+ SVX_BINTREE,
+ SVX_OCTREE
};
/* Volume element */
@@ -97,19 +103,21 @@ struct svx_voxel_desc {
static const struct svx_voxel_desc SVX_VOXEL_DESC_NULL =
SVX_VOXEL_DESC_NULL__;
-struct svx_octree_desc {
+struct svx_tree_desc {
/* Submitted Axis Aligned Bounding Box */
double lower[3], upper[3];
size_t nleaves; /* #leaves */
size_t nvoxels; /* #voxels, i.e. #leaves + #parents */
size_t depth; /* Depth of the octree */
+
+ enum svx_tree_type type;
};
-#define SVX_OCTREE_DESC_NULL__ \
- {{DBL_MAX, DBL_MAX, DBL_MAX}, {-DBL_MAX,-DBL_MAX,-DBL_MAX}, 0, 0, 0}
-static const struct svx_octree_desc SVX_OCTREE_DESC_NULL =
- SVX_OCTREE_DESC_NULL__;
+#define SVX_TREE_DESC_NULL__ \
+ {{DBL_MAX, DBL_MAX, DBL_MAX}, {-DBL_MAX,-DBL_MAX,-DBL_MAX}, 0, 0, 0, 0}
+static const struct svx_tree_desc SVX_TREE_DESC_NULL =
+ SVX_TREE_DESC_NULL__;
struct svx_hit {
double distance; /* Distance from the ray origin to the impacted voxel */
@@ -170,8 +178,7 @@ struct mem_allocator;
/* Forward declaration of opaque data types */
struct svx_device;
-struct svx_octree;
-struct svx_bintree;
+struct svx_tree;
BEGIN_DECLS
@@ -194,7 +201,7 @@ svx_device_ref_put
(struct svx_device* svx);
/*******************************************************************************
- * Octree
+ * Tree
******************************************************************************/
SVX_API res_T
svx_octree_create
@@ -203,30 +210,40 @@ svx_octree_create
const double upper[3], /* Upper bound of the octree */
const size_t nvoxels[3], /* # voxels along the 3 axis */
const struct svx_voxel_desc* desc, /* Descriptor of a voxel */
- struct svx_octree** octree);
+ struct svx_tree** octree);
+
+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 enum svx_axis axis, /* Axis along which the binary tree is defined */
+ const struct svx_voxel_desc* desc, /* Descriptor of a voxel */
+ struct svx_tree** tree);
SVX_API res_T
-svx_octree_ref_get
- (struct svx_octree* octree);
+svx_tree_ref_get
+ (struct svx_tree* tree);
SVX_API res_T
-svx_octree_ref_put
- (struct svx_octree* octree);
+svx_tree_ref_put
+ (struct svx_tree* tree);
SVX_API res_T
-svx_octree_get_desc
- (const struct svx_octree* octree,
- struct svx_octree_desc* desc);
+svx_tree_get_desc
+ (const struct svx_tree* tree,
+ struct svx_tree_desc* desc);
SVX_API res_T
svx_octree_for_each_leaf
- (struct svx_octree* octree,
+ (struct svx_tree* tree,
svx_leaf_function_T functor,
void* context); /* Client data sent as the last argument of the functor */
SVX_API res_T
svx_octree_trace_ray
- (struct svx_octree* octree,
+ (struct svx_tree* tree,
const double ray_origin[3],
const double ray_direction[3],
const double ray_range[2],
@@ -237,32 +254,11 @@ svx_octree_trace_ray
SVX_API res_T
svx_octree_at
- (struct svx_octree* octree,
+ (struct svx_tree* octree,
const double position[3],
svx_at_filter_T filter,
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 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);
-
-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_bintree.c b/src/svx_bintree.c
@@ -16,7 +16,7 @@
#include "svx.h"
#include "svx_c.h"
#include "svx_device.h"
-#include "svx_bintree.h"
+#include "svx_tree.h"
#include "svx_tree_builder.h"
#include <rsys/mem_allocator.h>
@@ -26,21 +26,6 @@
#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
@@ -51,9 +36,9 @@ svx_bintree_create
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_tree** out_bintree)
{
- struct svx_bintree* bintree = NULL;
+ struct svx_tree* bintree = NULL;
double vox_sz; /* World space size of a voxel */
struct bintree_builder bldr;
struct voxel vox = VOXEL_NULL;
@@ -81,15 +66,8 @@ svx_bintree_create
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;
+ res = tree_create(dev, SVX_BINTREE, desc->size, &bintree);
+ if(res != RES_OK) goto error;
/* The binary tree definition that must be a power of two */
bintree->definition = round_up_pow2(nvoxels);
@@ -131,15 +109,15 @@ svx_bintree_create
bintree_check(&bintree->buffer, bintree->root);
#endif
- bintree->lower = lower;
- bintree->upper = upper;
- bintree->axis = axis;
+ bintree->lower[axis] = lower;
+ bintree->upper[axis] = upper;
+ bintree->frame[0] = 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;
+ bintree->tree_low[axis] = lower;
+ bintree->tree_upp[axis] = lower + (double)bintree->definition * vox_sz;
+ bintree->tree_size[axis] = bintree->tree_upp[axis] - bintree->tree_low[axis];
/* 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
@@ -152,25 +130,9 @@ exit:
return res;
error:
if(bintree) {
- SVX(bintree_ref_put(bintree));
+ SVX(tree_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
@@ -1,42 +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_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
@@ -16,7 +16,7 @@
#include "svx.h"
#include "svx_c.h"
#include "svx_device.h"
-#include "svx_octree.h"
+#include "svx_tree.h"
#include "svx_tree_builder.h"
#include <rsys/double3.h>
@@ -27,22 +27,6 @@
#include "svx_tree_builder.h"
/*******************************************************************************
- * Helper function
- ******************************************************************************/
-static void
-octree_release(ref_T* ref)
-{
- struct svx_octree* oct;
- struct svx_device* dev;
- ASSERT(ref);
- oct = CONTAINER_OF(ref, struct svx_octree, ref);
- buffer_release(&oct->buffer);
- dev = oct->dev;
- MEM_RM(dev->allocator, oct);
- SVX(device_ref_put(dev));
-}
-
-/*******************************************************************************
* Exported functions
******************************************************************************/
res_T
@@ -52,9 +36,9 @@ svx_octree_create
const double upper[3], /* Upper bound of the octree */
const size_t nvoxels[3], /* # voxels along the 3 axis */
const struct svx_voxel_desc* desc, /* Descriptor of a voxel */
- struct svx_octree** out_oct)
+ struct svx_tree** out_oct)
{
- struct svx_octree* oct = NULL;
+ struct svx_tree* oct = NULL;
double vox_sz[3]; /* World space size of a voxel */
struct octree_builder bldr;
struct voxel vox = VOXEL_NULL;
@@ -62,7 +46,7 @@ svx_octree_create
uint64_t mcode;
res_T res = RES_OK;
- if(!dev || !lower || !upper || !nvoxels || !check_svx_voxel_desc(desc)
+ if(!dev || !lower || !upper || !nvoxels || !check_svx_voxel_desc(desc)
|| !out_oct) {
res = RES_BAD_ARG;
goto error;
@@ -88,15 +72,9 @@ svx_octree_create
res = RES_BAD_ARG;
goto error;
}
- oct = MEM_CALLOC(dev->allocator, 1, sizeof(struct svx_octree));
- if(!oct) {
- res = RES_MEM_ERR;
- goto error;
- }
- ref_init(&oct->ref);
- SVX(device_ref_get(dev));
- buffer_init(dev->allocator, desc->size, &oct->buffer);
- oct->dev = dev;
+
+ res = tree_create(dev, SVX_OCTREE, desc->size, &oct);
+ if(res != RES_OK) goto error;
/* Compute the octree definition */
oct->definition = MMAX(nvoxels[0], 2);
@@ -150,6 +128,10 @@ svx_octree_create
#ifndef NDEBUG
octree_check(&oct->buffer, oct->root);
#endif
+ oct->frame[0] = SVX_AXIS_X;
+ oct->frame[1] = SVX_AXIS_Y;
+ oct->frame[2] = SVX_AXIS_Z;
+
/* Setup the octree AABB in world space */
d3_set(oct->lower, lower);
d3_set(oct->upper, upper);
@@ -160,15 +142,15 @@ svx_octree_create
vox_sz[2] = (upper[2] - lower[2]) / (double)nvoxels[2];
/* Compute the octree AABB in world space */
- oct->oclow[0] = lower[0];
- oct->oclow[1] = lower[1];
- oct->oclow[2] = lower[2];
- oct->ocupp[0] = oct->oclow[0] + (double)oct->definition * vox_sz[0];
- oct->ocupp[1] = oct->oclow[1] + (double)oct->definition * vox_sz[1];
- oct->ocupp[2] = oct->oclow[2] + (double)oct->definition * vox_sz[2];
- oct->ocsize[0] = oct->ocupp[0] - oct->oclow[0];
- oct->ocsize[1] = oct->ocupp[1] - oct->oclow[1];
- oct->ocsize[2] = oct->ocupp[2] - oct->oclow[2];
+ oct->tree_low[0] = lower[0];
+ oct->tree_low[1] = lower[1];
+ oct->tree_low[2] = lower[2];
+ oct->tree_upp[0] = oct->tree_low[0] + (double)oct->definition * vox_sz[0];
+ oct->tree_upp[1] = oct->tree_low[1] + (double)oct->definition * vox_sz[1];
+ oct->tree_upp[2] = oct->tree_low[2] + (double)oct->definition * vox_sz[2];
+ oct->tree_size[0] = oct->tree_upp[0] - oct->tree_low[0];
+ oct->tree_size[1] = oct->tree_upp[1] - oct->tree_low[1];
+ oct->tree_size[2] = oct->tree_upp[2] - oct->tree_low[2];
/* Adjust the octree definition with respect to the octree depth since finest
* levels might be removed during the build due to the merging process */
@@ -180,50 +162,15 @@ exit:
return res;
error:
if(oct) {
- SVX(octree_ref_put(oct));
+ SVX(tree_ref_put(oct));
oct = NULL;
}
goto exit;
}
res_T
-svx_octree_ref_get(struct svx_octree* oct)
-{
- if(!oct) return RES_BAD_ARG;
- ref_get(&oct->ref);
- return RES_OK;
-}
-
-res_T
-svx_octree_ref_put(struct svx_octree* oct)
-{
- if(!oct) return RES_BAD_ARG;
- ref_put(&oct->ref, octree_release);
- return RES_OK;
-}
-
-res_T
-svx_octree_get_desc
- (const struct svx_octree* oct, struct svx_octree_desc* desc)
-{
- if(!oct || !desc) return RES_BAD_ARG;
- d3_set(desc->lower, oct->lower);
- d3_set(desc->upper, oct->upper);
- desc->nleaves = oct->nleaves;
- desc->nvoxels = buffer_absolute_attr_index
- (&oct->buffer, oct->buffer.attr_head) + 1; /* Root node */
- desc->depth = oct->depth;
- return RES_OK;
-}
-
-res_T
svx_octree_for_each_leaf
- (struct svx_octree* oct,
- void (*func)
- (const struct svx_voxel* leaf,
- const size_t ileaf,
- void* ctx),
- void* ctx)
+ (struct svx_tree* oct, svx_leaf_function_T func, void* ctx)
{
struct stack_entry {
struct buffer_index inode;
@@ -235,16 +182,16 @@ svx_octree_for_each_leaf
struct svx_voxel leaf = SVX_VOXEL_NULL;
size_t ileaf = 0;
- if(!oct || !func) return RES_BAD_ARG;
+ if(!oct || !func || oct->type != SVX_OCTREE) return RES_BAD_ARG;
stack[0].depth = 0;
stack[0].inode = oct->root;
- stack[0].low[0] = oct->oclow[0];
- stack[0].low[1] = oct->oclow[1];
- stack[0].low[2] = oct->oclow[2];
- stack[0].hsz[0] = (oct->ocupp[0] - oct->oclow[0])*0.5;
- stack[0].hsz[1] = (oct->ocupp[1] - oct->oclow[1])*0.5;
- stack[0].hsz[2] = (oct->ocupp[2] - oct->oclow[2])*0.5;
+ stack[0].low[0] = oct->tree_low[0];
+ stack[0].low[1] = oct->tree_low[1];
+ stack[0].low[2] = oct->tree_low[2];
+ stack[0].hsz[0] = (oct->tree_upp[0] - oct->tree_low[0])*0.5;
+ stack[0].hsz[1] = (oct->tree_upp[1] - oct->tree_low[1])*0.5;
+ stack[0].hsz[2] = (oct->tree_upp[2] - oct->tree_low[2])*0.5;
istack = 1;
do {
@@ -306,7 +253,7 @@ svx_octree_for_each_leaf
res_T
svx_octree_at
- (struct svx_octree* oct,
+ (struct svx_tree* oct,
const double position[3],
svx_at_filter_T filter,
void* context,
@@ -318,10 +265,9 @@ svx_octree_at
double scale_exp2;
double low[3];
double pos[3];
- double ocsz[3]; /* Octree size along the 3 axis */
res_T res = RES_OK;
- if(!oct || !position || !voxel) {
+ if(!oct || !position || !voxel || oct->type != SVX_OCTREE) {
res = RES_BAD_ARG;
goto error;
}
@@ -335,15 +281,11 @@ svx_octree_at
goto exit;
}
- ocsz[0] = oct->ocupp[0] - oct->oclow[0];
- ocsz[1] = oct->ocupp[1] - oct->oclow[1];
- ocsz[2] = oct->ocupp[2] - oct->oclow[2];
-
/* Transform the position in the normalized octree space,
* i.e. octree lies in [0, 1]^2 */
- pos[0] = (position[0] - oct->oclow[0]) / ocsz[0];
- pos[1] = (position[1] - oct->oclow[1]) / ocsz[1];
- pos[2] = (position[2] - oct->oclow[2]) / ocsz[2];
+ pos[0] = (position[0] - oct->tree_low[0]) / oct->tree_size[0];
+ pos[1] = (position[1] - oct->tree_low[1]) / oct->tree_size[1];
+ pos[2] = (position[2] - oct->tree_low[2]) / oct->tree_size[2];
/* Initialized the lower left corner of the current node */
low[0] = 0;
@@ -391,12 +333,12 @@ svx_octree_at
iattr = buffer_get_child_attr_index(&oct->buffer, inode, ichild);
/* Setup the voxel */
- vox.lower[0] = low[0] * ocsz[0] + oct->oclow[0];
- vox.lower[1] = low[1] * ocsz[1] + oct->oclow[1];
- vox.lower[2] = low[2] * ocsz[2] + oct->oclow[2];
- 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.lower[0] = low[0] * oct->tree_size[0] + oct->tree_low[0];
+ vox.lower[1] = low[1] * oct->tree_size[1] + oct->tree_low[1];
+ vox.lower[2] = low[2] * oct->tree_size[2] + oct->tree_low[2];
+ vox.upper[0] = vox.lower[0] + oct->tree_size[0] * scale_exp2;
+ vox.upper[1] = vox.lower[1] + oct->tree_size[1] * scale_exp2;
+ vox.upper[2] = vox.lower[2] + oct->tree_size[2] * scale_exp2;
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;
diff --git a/src/svx_octree.h b/src/svx_octree.h
@@ -1,41 +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_H
-#define SVX_OCTREE_H
-
-#include "svx_buffer.h"
-#include <rsys/ref_count.h>
-
-struct svx_octree {
- size_t definition; /* #voxels along the X, Y and Z axis */
-
- double lower[3], upper[3]; /* Submitted World space AABB of the octree */
- double oclow[3], ocupp[3]; /* Adjusted World space AABB of the octree */
- double ocsize[3]; /* World space size of the octree */
-
- 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; /* Maximum depth of the octree */
-
- struct svx_device* dev;
- ref_T ref;
-};
-
-#endif /* SVX_OCTREE_H */
-
diff --git a/src/svx_octree_trace_ray.c b/src/svx_octree_trace_ray.c
@@ -14,7 +14,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include "svx.h"
-#include "svx_octree.h"
+#include "svx_tree.h"
struct ray {
/* Ray parameters in the normalized octree space [1, 2]^3 whose ray direction
@@ -56,7 +56,7 @@ uitof(const uint32_t ui)
static FINLINE void
setup_hit
- (struct svx_octree* oct,
+ (struct svx_tree* oct,
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 */
@@ -89,18 +89,18 @@ setup_hit
upp[2] = low[2] + scale_exp2;
/* Transform the voxel AABB in world space */
- hit->voxel.lower[0] = low[0] * oct->ocsize[0] + oct->oclow[0];
- hit->voxel.lower[1] = low[1] * oct->ocsize[1] + oct->oclow[1];
- hit->voxel.lower[2] = low[2] * oct->ocsize[2] + oct->oclow[2];
- hit->voxel.upper[0] = upp[0] * oct->ocsize[0] + oct->oclow[0];
- hit->voxel.upper[1] = upp[1] * oct->ocsize[1] + oct->oclow[1];
- hit->voxel.upper[2] = upp[2] * oct->ocsize[2] + oct->oclow[2];
+ hit->voxel.lower[0] = low[0] * oct->tree_size[0] + oct->tree_low[0];
+ hit->voxel.lower[1] = low[1] * oct->tree_size[1] + oct->tree_low[1];
+ hit->voxel.lower[2] = low[2] * oct->tree_size[2] + oct->tree_low[2];
+ hit->voxel.upper[0] = upp[0] * oct->tree_size[0] + oct->tree_low[0];
+ hit->voxel.upper[1] = upp[1] * oct->tree_size[1] + oct->tree_low[1];
+ hit->voxel.upper[2] = upp[2] * oct->tree_size[2] + oct->tree_low[2];
}
/* Return RES_BAD_OP if the ray cannot intersect the scene */
static res_T
setup_ray
- (const struct svx_octree* oct,
+ (const struct svx_tree* oct,
const double org[3],
const double dir[3],
const double range[2],
@@ -120,14 +120,14 @@ setup_ray
}
/* Compute reciprocal size of the world space octree AABB */
- rcp_ocsz[0] = 1.0 / oct->ocsize[0];
- rcp_ocsz[1] = 1.0 / oct->ocsize[1];
- rcp_ocsz[2] = 1.0 / oct->ocsize[2];
+ rcp_ocsz[0] = 1.0 / oct->tree_size[0];
+ rcp_ocsz[1] = 1.0 / oct->tree_size[1];
+ rcp_ocsz[2] = 1.0 / oct->tree_size[2];
/* Transform the ray origin in the [1, 2] space */
- ray->org[0] = (org[0] - oct->oclow[0]) * rcp_ocsz[0] + 1.0;
- ray->org[1] = (org[1] - oct->oclow[1]) * rcp_ocsz[1] + 1.0;
- ray->org[2] = (org[2] - oct->oclow[2]) * rcp_ocsz[2] + 1.0;
+ ray->org[0] = (org[0] - oct->tree_low[0]) * rcp_ocsz[0] + 1.0;
+ ray->org[1] = (org[1] - oct->tree_low[1]) * rcp_ocsz[1] + 1.0;
+ ray->org[2] = (org[2] - oct->tree_low[2]) * rcp_ocsz[2] + 1.0;
/* Setup the ray range */
ray->range[0] = range[0];
@@ -166,7 +166,7 @@ setup_ray
static res_T
trace_ray
- (struct svx_octree* oct,
+ (struct svx_tree* oct,
const struct ray* ray,
const svx_hit_challenge_T challenge,
const svx_hit_filter_T filter,
@@ -185,7 +185,7 @@ trace_ray
uint32_t scale_max;
uint32_t scale; /* stack index */
uint32_t ichild;
- ASSERT(oct && ray && hit);
+ ASSERT(oct && ray && hit && oct->type == SVX_OCTREE);
*hit = SVX_HIT_NULL; /* Initialise the hit to "no intersection" */
@@ -376,7 +376,7 @@ trace_ray
******************************************************************************/
res_T
svx_octree_trace_ray
- (struct svx_octree* oct,
+ (struct svx_tree* oct,
const double org[3],
const double dir[3],
const double range[2],
@@ -388,7 +388,7 @@ svx_octree_trace_ray
struct ray ray;
res_T res = RES_OK;
- if(!oct || !org || !range || !hit) {
+ if(!oct || !org || !range || !hit || oct->type != SVX_OCTREE) {
res = RES_BAD_ARG;
goto error;
}
diff --git a/src/svx_tree.c b/src/svx_tree.c
@@ -0,0 +1,118 @@
+/* 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_device.h"
+#include "svx_tree.h"
+
+#include <rsys/double3.h>
+#include <rsys/mem_allocator.h>
+
+/*******************************************************************************
+ * Helper function
+ ******************************************************************************/
+static void
+tree_release(ref_T* ref)
+{
+ struct svx_tree* tree;
+ struct svx_device* dev;
+ ASSERT(ref);
+ tree = CONTAINER_OF(ref, struct svx_tree, ref);
+ buffer_release(&tree->buffer);
+ dev = tree->dev;
+ MEM_RM(dev->allocator, tree);
+ SVX(device_ref_put(dev));
+}
+
+/*******************************************************************************
+ * Exported functions
+ ******************************************************************************/
+res_T
+svx_tree_ref_get(struct svx_tree* tree)
+{
+ if(!tree) return RES_BAD_ARG;
+ ref_get(&tree->ref);
+ return RES_OK;
+}
+
+res_T
+svx_tree_ref_put(struct svx_tree* tree)
+{
+ if(!tree) return RES_BAD_ARG;
+ ref_put(&tree->ref, tree_release);
+ return RES_OK;
+}
+
+res_T
+svx_tree_get_desc
+ (const struct svx_tree* tree, struct svx_tree_desc* desc)
+{
+ if(!tree || !desc) return RES_BAD_ARG;
+ d3_set(desc->lower, tree->lower);
+ d3_set(desc->upper, tree->upper);
+ desc->nleaves = tree->nleaves;
+ desc->nvoxels = buffer_absolute_attr_index
+ (&tree->buffer, tree->buffer.attr_head) + 1; /* Root node */
+ desc->depth = tree->depth;
+ desc->type = tree->type;
+ return RES_OK;
+}
+
+/*******************************************************************************
+ * Local functions
+ ******************************************************************************/
+res_T
+tree_create
+ (struct svx_device* dev,
+ const enum svx_tree_type type,
+ const size_t vxsz,
+ struct svx_tree** out_tree)
+{
+ struct svx_tree* tree = NULL;
+ res_T res = RES_OK;
+
+ if(!dev || !out_tree) {
+ res = RES_BAD_ARG;
+ goto error;
+ }
+
+ tree = MEM_CALLOC(dev->allocator, 1, sizeof(*tree));
+ if(!tree) {
+ res = RES_MEM_ERR;
+ goto error;
+ }
+ ref_init(&tree->ref);
+ SVX(device_ref_get(dev));
+ buffer_init(dev->allocator, vxsz, &tree->buffer);
+ tree->dev = dev;
+ d3_splat(tree->lower, DBL_MAX);
+ d3_splat(tree->upper,-DBL_MAX);
+ d3_splat(tree->tree_low, DBL_MAX);
+ d3_splat(tree->tree_upp,-DBL_MAX);
+ d3_splat(tree->tree_size, -1);
+ tree->type = type;
+ tree->frame[0] = SVX_AXIS_NONE__;
+ tree->frame[1] = SVX_AXIS_NONE__;
+ tree->frame[2] = SVX_AXIS_NONE__;
+exit:
+ if(out_tree) *out_tree = tree;
+ return res;
+error:
+ if(tree) {
+ SVX(tree_ref_put(tree));
+ tree = NULL;
+ }
+ goto exit;
+}
+
diff --git a/src/svx_tree.h b/src/svx_tree.h
@@ -0,0 +1,56 @@
+/* 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_TREE_H
+#define SVX_TREE_H
+
+#include "svx_buffer.h"
+#include <rsys/ref_count.h>
+
+struct svx_tree {
+ size_t definition; /* #voxels of the tree along its dimensions */
+
+ /* Submitted AABB */
+ double lower[3], upper[3];
+
+ /* Adjusted World space AABB of the tree. The submitted AABB is increased to
+ * encompass the whole tree voxels. The number of tree voxels might be
+ * greater than the submitted voxels count in order to ensure that definition
+ * is a power of two. */
+ double tree_low[3], tree_upp[3];
+ double tree_size[3]; /* World space size of the tree AABB */
+
+ struct buffer buffer; /* Buffer of voxel data */
+ 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; /* Maximum depth of the tree */
+
+ enum svx_axis frame[3]; /* Define the frame (i.e. basis) of the tree */
+ enum svx_tree_type type;
+ struct svx_device* dev;
+ ref_T ref;
+};
+
+extern LOCAL_SYM res_T
+tree_create
+ (struct svx_device* dev,
+ const enum svx_tree_type type,
+ const size_t vxsz,
+ struct svx_tree** out_tree);
+
+#endif /* SVX_TREE_H */
+
diff --git a/src/test_svx_octree.c b/src/test_svx_octree.c
@@ -172,9 +172,9 @@ max_lod
static void
-test_at_accessor(struct svx_octree* oct, const size_t nvoxels[3])
+test_at_accessor(struct svx_tree* oct, const size_t nvoxels[3])
{
- struct svx_octree_desc octdesc;
+ struct svx_tree_desc tree_desc;
struct at_context ctx;
size_t nvxls;
double delta[3];
@@ -182,11 +182,12 @@ test_at_accessor(struct svx_octree* oct, const size_t nvoxels[3])
size_t x, y, z;
CHK(nvoxels != NULL);
- CHK(svx_octree_get_desc(oct, &octdesc) == RES_OK);
+ CHK(svx_tree_get_desc(oct, &tree_desc) == RES_OK);
+ CHK(tree_desc.type == SVX_OCTREE);
- ocsz[0] = octdesc.upper[0] - octdesc.lower[0];
- ocsz[1] = octdesc.upper[1] - octdesc.lower[1];
- ocsz[2] = octdesc.upper[2] - octdesc.lower[2];
+ ocsz[0] = tree_desc.upper[0] - tree_desc.lower[0];
+ ocsz[1] = tree_desc.upper[1] - tree_desc.lower[1];
+ ocsz[2] = tree_desc.upper[2] - tree_desc.lower[2];
delta[0] = ocsz[0]/(double)nvoxels[0];
delta[1] = ocsz[1]/(double)nvoxels[1];
delta[2] = ocsz[2]/(double)nvoxels[2];
@@ -195,24 +196,24 @@ test_at_accessor(struct svx_octree* oct, const size_t nvoxels[3])
nvxls = MMAX(nvxls, nvoxels[1]);
nvxls = MMAX(nvxls, nvoxels[2]);
- ctx.depth = octdesc.depth;
+ ctx.depth = tree_desc.depth;
CHK(ctx.depth > 0);
while(ctx.depth-- != 0) {
- const size_t iter = octdesc.depth - ctx.depth - 1;
+ const size_t iter = tree_desc.depth - ctx.depth - 1;
double pos[3];
double low[3];
double upp[3];
FOR_EACH(x, 0, nvxls) {
- pos[0] = octdesc.lower[0] + ((double)x+1.0/(1u<<(2+iter)))*delta[0];
- low[0] = octdesc.lower[0] + (double)x * delta[0];
+ pos[0] = tree_desc.lower[0] + ((double)x+1.0/(1u<<(2+iter)))*delta[0];
+ low[0] = tree_desc.lower[0] + (double)x * delta[0];
upp[0] = low[0] + delta[0];
if(x*(1u<<iter) >= nvoxels[0]) break;
FOR_EACH(y, 0, nvxls) {
- pos[1] = octdesc.lower[1] + ((double)y+1.0/(1u<<(2+iter)))*delta[1];
- low[1] = octdesc.lower[1] + (double)y * delta[1];
+ pos[1] = tree_desc.lower[1] + ((double)y+1.0/(1u<<(2+iter)))*delta[1];
+ low[1] = tree_desc.lower[1] + (double)y * delta[1];
upp[1] = low[1] + delta[1];
if(y*(1u<<iter) >= nvoxels[1]) break;
@@ -222,8 +223,8 @@ test_at_accessor(struct svx_octree* oct, const size_t nvoxels[3])
uint32_t ui3[3];
uint64_t mcode;
- pos[2] = octdesc.lower[2] + ((double)z+1.0/(1u<<(2+iter)))*delta[2];
- low[2] = octdesc.lower[2] + (double)z * delta[2];
+ pos[2] = tree_desc.lower[2] + ((double)z+1.0/(1u<<(2+iter)))*delta[2];
+ low[2] = tree_desc.lower[2] + (double)z * delta[2];
upp[2] = low[2] + delta[2];
if(z*(1u<<iter) >= nvoxels[2]) break;
@@ -241,7 +242,7 @@ test_at_accessor(struct svx_octree* oct, const size_t nvoxels[3])
mcode = morton_xyz_encode_u21(ui3);
CHK(*((double*)vox.data) == mcode);
- CHK(vox.is_leaf == (octdesc.depth-1==ctx.depth));
+ CHK(vox.is_leaf == (tree_desc.depth-1==ctx.depth));
CHK(vox.depth == ctx.depth);
CHK(d3_eq_eps(vox.lower, low, 1.e-6));
CHK(d3_eq_eps(vox.upper, upp, 1.e-6));
@@ -261,10 +262,10 @@ int
main(int argc, char** argv)
{
struct svx_device* dev = NULL;
- struct svx_octree* oct = NULL;
+ struct svx_tree* oct = NULL;
struct mem_allocator allocator;
struct svx_voxel_desc voxdesc = SVX_VOXEL_DESC_NULL;
- struct svx_octree_desc octdesc = SVX_OCTREE_DESC_NULL;
+ struct svx_tree_desc tree_desc = SVX_TREE_DESC_NULL;
double low[3];
double upp[3];
size_t nvxls[3];
@@ -294,11 +295,11 @@ main(int argc, char** argv)
voxdesc.size = sizeof(double);
CHK(NEW_SCN(dev, low, upp, nvxls, &voxdesc, &oct) == RES_OK);
- CHK(svx_octree_ref_get(NULL) == RES_BAD_ARG);
- CHK(svx_octree_ref_get(oct) == RES_OK);
- CHK(svx_octree_ref_put(NULL) == RES_BAD_ARG);
- CHK(svx_octree_ref_put(oct) == RES_OK);
- CHK(svx_octree_ref_put(oct) == RES_OK);
+ CHK(svx_tree_ref_get(NULL) == RES_BAD_ARG);
+ CHK(svx_tree_ref_get(oct) == RES_OK);
+ CHK(svx_tree_ref_put(NULL) == RES_BAD_ARG);
+ CHK(svx_tree_ref_put(oct) == RES_OK);
+ CHK(svx_tree_ref_put(oct) == RES_OK);
upp[0] = low[0];
CHK(NEW_SCN(dev, low, upp, nvxls, &voxdesc, &oct) == RES_BAD_ARG);
@@ -338,36 +339,38 @@ main(int argc, char** argv)
CHK(svx_octree_for_each_leaf(oct, check_leaves, &ctx) == RES_OK);
- CHK(svx_octree_get_desc(NULL, &octdesc) == RES_BAD_ARG);
- CHK(svx_octree_get_desc(oct, NULL) == RES_BAD_ARG);
- CHK(svx_octree_get_desc(oct, &octdesc) == RES_OK);
- CHK(octdesc.nleaves == 5*5*5);
- CHK(octdesc.nvoxels == octdesc.nleaves + 36/*#parents*/);
- CHK(octdesc.depth == 4);
+ CHK(svx_tree_get_desc(NULL, &tree_desc) == RES_BAD_ARG);
+ CHK(svx_tree_get_desc(oct, NULL) == RES_BAD_ARG);
+ CHK(svx_tree_get_desc(oct, &tree_desc) == RES_OK);
+ CHK(tree_desc.nleaves == 5*5*5);
+ CHK(tree_desc.nvoxels == tree_desc.nleaves + 36/*#parents*/);
+ CHK(tree_desc.depth == 4);
+ CHK(tree_desc.type == SVX_OCTREE);
d3_splat(low, 0);
d3_splat(upp, 1);
- CHK(d3_eq(octdesc.lower, low));
- CHK(d3_eq(octdesc.upper, upp));
+ CHK(d3_eq(tree_desc.lower, low));
+ CHK(d3_eq(tree_desc.upper, upp));
test_at_accessor(oct, nvxls);
- CHK(svx_octree_ref_put(oct) == RES_OK);
+ CHK(svx_tree_ref_put(oct) == RES_OK);
nvxls[0] = nvxls[1] = nvxls[2] = 32;
voxdesc.challenge_merge = merge_level0;
CHK(NEW_SCN(dev, low, upp, nvxls, &voxdesc, &oct) == RES_OK);
- CHK(svx_octree_get_desc(oct, &octdesc) == RES_OK);
- CHK(octdesc.nleaves == nvxls[0]*nvxls[1]*nvxls[2] / 8);
- CHK(octdesc.nvoxels == (octdesc.nleaves*8 - 1) / 7);
- CHK(octdesc.depth == (size_t)log2i((int)(nvxls[0]/2))+1);
+ CHK(svx_tree_get_desc(oct, &tree_desc) == RES_OK);
+ CHK(tree_desc.nleaves == nvxls[0]*nvxls[1]*nvxls[2] / 8);
+ CHK(tree_desc.nvoxels == (tree_desc.nleaves*8 - 1) / 7);
+ CHK(tree_desc.depth == (size_t)log2i((int)(nvxls[0]/2))+1);
+ CHK(tree_desc.type = SVX_OCTREE);
dump_data(stdout, oct, FLOAT, 1, write_scalars);
#undef NEW_SCN
CHK(svx_device_ref_put(dev) == RES_OK);
- CHK(svx_octree_ref_put(oct) == RES_OK);
+ CHK(svx_tree_ref_put(oct) == RES_OK);
check_memory_allocator(&allocator);
mem_shutdown_proxy_allocator(&allocator);
diff --git a/src/test_svx_octree_trace_ray.c b/src/test_svx_octree_trace_ray.c
@@ -234,7 +234,7 @@ hit_challenge(const struct svx_hit* hit, void* context)
}
static void
-draw_image(FILE* stream, struct svx_octree* oct, const struct scene* scn)
+draw_image(FILE* stream, struct svx_tree* oct, const struct scene* scn)
{
struct camera cam;
unsigned char* pixels = NULL;
@@ -296,8 +296,8 @@ main(int argc, char** argv)
struct scene scn;
struct ray r;
struct svx_device* dev = NULL;
- struct svx_octree* oct = NULL;
- struct svx_octree_desc octree_desc = SVX_OCTREE_DESC_NULL;
+ struct svx_tree* oct = NULL;
+ struct svx_tree_desc tree_desc = SVX_TREE_DESC_NULL;
struct svx_voxel_desc voxel_desc = SVX_VOXEL_DESC_NULL;
struct svx_hit hit = SVX_HIT_NULL;
struct svx_hit hit2 = SVX_HIT_NULL;
@@ -352,7 +352,7 @@ main(int argc, char** argv)
CHK(*(char*)hit.voxel.data == 0);
/* Use challenge functor to intersect voxels that are not leaves */
- CHK(svx_octree_get_desc(oct, &octree_desc) == RES_OK);
+ CHK(svx_tree_get_desc(oct, &tree_desc) == RES_OK);
CHK(RT(oct, r.org, r.dir, r.range, hit_challenge, NULL, NULL, &hit2) == RES_OK);
CHK(!SVX_HIT_NONE(&hit2));
CHK(!SVX_VOXEL_EQ(&hit.voxel, &hit2.voxel));
@@ -416,7 +416,7 @@ main(int argc, char** argv)
draw_image(stdout, oct, &scn);
- CHK(svx_octree_ref_put(oct) == RES_OK);
+ CHK(svx_tree_ref_put(oct) == RES_OK);
CHK(svx_device_ref_put(dev) == RES_OK);
CHK(mem_allocated_size() == 0);
return 0;
diff --git a/src/test_svx_utils.h b/src/test_svx_utils.h
@@ -86,17 +86,17 @@ write_leaf_cells
static INLINE void
dump_data
(FILE* stream,
- struct svx_octree* oct,
+ struct svx_tree* tree,
const enum data_type type,
const size_t numcomps,
void (*write_leaf_data)
(const struct svx_voxel* leaf, const size_t ileaf, void* ctx))
{
- struct svx_octree_desc desc;
+ struct svx_tree_desc desc;
size_t ileaf;
CHK(stream != NULL);
- CHK(oct != NULL);
+ CHK(tree != NULL);
CHK(write_leaf_data);
fprintf(stream, "# vtk DataFile Version 2.0\n");
@@ -104,14 +104,15 @@ dump_data
fprintf(stream, "ASCII\n");
fprintf(stream, "DATASET UNSTRUCTURED_GRID\n");
- CHK(svx_octree_get_desc(oct, &desc) == RES_OK);
+ CHK(svx_tree_get_desc(tree, &desc) == RES_OK);
+ CHK(desc.type == SVX_OCTREE); /* FIXME currently only octree are supported */
fprintf(stream, "POINTS %lu float\n", (unsigned long)(desc.nleaves* 8));
- CHK(svx_octree_for_each_leaf(oct, write_leaf_vertices, stream) == RES_OK);
+ CHK(svx_octree_for_each_leaf(tree, write_leaf_vertices, stream) == RES_OK);
fprintf(stream, "CELLS %lu %lu\n",
(unsigned long)desc.nleaves,
(unsigned long)(desc.nleaves*(8/*#verts per leaf*/ + 1/*1st field of a cell*/)));
- CHK(svx_octree_for_each_leaf(oct, write_leaf_cells, stream) == RES_OK);
+ CHK(svx_octree_for_each_leaf(tree, write_leaf_cells, stream) == RES_OK);
fprintf(stream, "CELL_TYPES %lu\n", (unsigned long)desc.nleaves);
FOR_EACH(ileaf, 0, desc.nleaves) fprintf(stream, "11\n");
@@ -119,7 +120,7 @@ dump_data
fprintf(stream, "CELL_DATA %lu\n", (unsigned long)desc.nleaves);
fprintf(stream, "SCALARS K %s %lu\n", data_type_to_string(type), numcomps);
fprintf(stream, "LOOKUP_TABLE default\n");
- CHK(svx_octree_for_each_leaf(oct, write_leaf_data, stream) == RES_OK);
+ CHK(svx_octree_for_each_leaf(tree, write_leaf_data, stream) == RES_OK);
}
