commit 7fa5a5eb80eb280cb6d33ebf5da6d7f0d9aec4f4
parent 114cc20211fdf9ae828f36a2c400d0abc7ddc2d6
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Thu, 13 Sep 2018 16:30:02 +0200
Test the svx_bintree_trace_ray function
Diffstat:
2 files changed, 401 insertions(+), 0 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -99,6 +99,7 @@ if(NOT NO_TEST)
new_test(test_svx_device)
new_test(test_svx_octree)
new_test(test_svx_octree_trace_ray ${MATH_LIB})
+ new_test(test_svx_bintree_trace_ray ${MATH_LIB})
endif()
rcmake_copy_runtime_libraries(test_svx_octree_trace_ray)
diff --git a/src/test_svx_bintree_trace_ray.c b/src/test_svx_bintree_trace_ray.c
@@ -0,0 +1,400 @@
+/* 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.r.org/licenses/>. */
+
+#include "svx.h"
+#include "test_svx_utils.h"
+
+#include <rsys/double2.h>
+#include <rsys/double3.h>
+#include <rsys/math.h>
+
+#include <math.h>
+
+struct ray {
+ double org[3];
+ double dir[3];
+ double range[2];
+};
+
+struct scene {
+ enum svx_axis axis;
+ double origin;
+ double vxsz;
+ double range_center;
+ double range_half_len;
+};
+
+static double
+rand_canonic(void)
+{
+ return (double)rand() / (double)((size_t)RAND_MAX + 1);
+}
+
+static void
+voxel_get(const size_t xyz[3], void* dst, void* ctx)
+{
+ const struct scene* scn = ctx;
+ char* val = dst;
+ double low;
+ double upp;
+ double dst1, dst2;
+ double min_dst, max_dst;
+ CHK(xyz != NULL);
+ CHK(dst != NULL);
+ CHK(ctx != NULL);
+
+ /* Compute the range of the voxel */
+ low = (double)xyz[scn->axis] * scn->vxsz + scn->origin;
+ upp = low + scn->vxsz;
+
+ /* Compute the distance from the voxel boundary to the range_center */
+ dst1 = fabs(scn->range_center - low);
+ dst2 = fabs(scn->range_center - upp);
+ min_dst = MMIN(dst1, dst2);
+ max_dst = MMAX(dst1, dst2);
+
+ /* Define if the voxel intersects a range boundary */
+ *val = min_dst <= scn->range_half_len
+ && max_dst >= scn->range_half_len;
+}
+
+static void
+voxels_merge(void* dst, const void* voxels[], const size_t nvoxels, void* ctx)
+{
+ size_t ivoxel;
+ char tmp = 0;
+ char* val = dst;
+
+ CHK(dst && voxels && nvoxels && ctx);
+
+ for(ivoxel=0; !tmp && ivoxel<nvoxels; ++ivoxel) {
+ const char* voxel_data = voxels[ivoxel];
+ tmp = *voxel_data;
+ }
+ *val = tmp;
+}
+
+static int
+voxels_challenge_merge(const void* voxels[], const size_t nvoxels, void* ctx)
+{
+ size_t ivoxel;
+ int merge = 1;
+ char ref;
+
+ CHK(voxels && nvoxels && ctx);
+
+ ref = *(char*)(voxels[0]);
+
+ for(ivoxel=1; merge && ivoxel<nvoxels; ++ivoxel) {
+ const char* voxel_data = voxels[ivoxel];
+ merge = (ref == *voxel_data);
+ }
+ return merge;
+}
+
+static int
+hit_challenge(const struct svx_hit* hit, void* context)
+{
+ (void)context;
+ CHK(hit);
+ CHK(!SVX_HIT_NONE(hit));
+ return 1;
+}
+
+static int
+hit_filter
+ (const struct svx_hit* hit,
+ const double ray_org[3],
+ const double ray_dir[3],
+ const double ray_range[3],
+ void* context)
+{
+ const struct ray* ray = context;
+ CHK(hit && ray_org && ray_dir && ray_range && context);
+ CHK(d3_eq(ray->org, ray_org));
+ CHK(d3_eq(ray->dir, ray_dir));
+ CHK(d2_eq(ray->range, ray_range));
+ CHK(!SVX_HIT_NONE(hit));
+ return *((char*)hit->voxel.data) == 0;
+}
+
+static int
+hit_filter2
+ (const struct svx_hit* hit,
+ const double ray_org[3],
+ const double ray_dir[3],
+ const double ray_range[3],
+ void* context)
+{
+ const struct svx_voxel* voxel = context;
+ CHK(hit && ray_org && ray_dir && ray_range && context);
+ CHK(!SVX_HIT_NONE(hit));
+ return SVX_VOXEL_EQ(&hit->voxel, voxel)
+ || *((char*)hit->voxel.data) == 0;
+}
+
+static int
+hit_filter3
+ (const struct svx_hit* hit,
+ const double ray_org[3],
+ const double ray_dir[3],
+ const double ray_range[3],
+ void* context)
+{
+ int* accum = context;
+ CHK(hit && ray_org && ray_dir && ray_range && context);
+ CHK(!SVX_HIT_NONE(hit));
+ *accum += *(char*)hit->voxel.data;
+ return 1;
+}
+
+int
+main(int argc, char** argv)
+{
+ struct svx_device* dev = NULL;
+ struct svx_tree* btree = NULL;
+ struct svx_voxel_desc voxel_desc = SVX_VOXEL_DESC_NULL;
+ struct svx_voxel voxel = SVX_VOXEL_NULL;
+ struct svx_hit hit;
+ struct svx_hit hit2;
+ struct scene scn;
+ const double lower = -1;
+ const double upper = 1;
+ const size_t definition = 32;
+ const double scnsz = upper - lower;
+ struct ray r;
+ int accum;
+ (void)argc, (void)argv;
+
+ scn.origin = lower;
+ scn.vxsz = scnsz / (double)definition;
+ scn.range_center = lower + scnsz*0.5;
+ scn.range_half_len = scnsz*0.25;
+ scn.axis = SVX_AXIS_X;
+
+ CHK(svx_device_create(NULL, NULL, 1, &dev) == RES_OK);
+ voxel_desc.get = voxel_get;
+ voxel_desc.merge = voxels_merge;
+ voxel_desc.challenge_merge = voxels_challenge_merge;
+ voxel_desc.context = &scn;
+ voxel_desc.size = sizeof(char);
+
+ CHK(svx_bintree_create(dev, lower, upper, definition, scn.axis,
+ &voxel_desc, &btree) == RES_OK);
+
+ d3(r.org, -1.01, 0, 0);
+ d3(r.dir, -1, 0, 0);
+ d2(r.range, 0, DBL_MAX);
+
+ #define RT svx_bintree_trace_ray
+ CHK(RT(NULL, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_BAD_ARG);
+ CHK(RT(btree, NULL, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_BAD_ARG);
+ CHK(RT(btree, r.org, NULL, r.range, NULL, NULL, NULL, &hit) == RES_BAD_ARG);
+ CHK(RT(btree, r.org, r.dir, NULL, NULL, NULL, NULL, &hit) == RES_BAD_ARG);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, NULL) == RES_BAD_ARG);
+
+ /* Check failed hits */
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+ d3(r.org, 1.01, 0, 0);
+ d3(r.dir, 1, 0, 0);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+ d3(r.dir, 0, 1, 0);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+ d3(r.dir, 0, 0, -1);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+
+ /* Check first hit */
+ d3(r.org, -1.01, 0, 0);
+ d3(r.dir, 1, 0, 0);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+ CHK(eq_eps(hit.distance[0], 0.01, 1.e-6));
+ CHK(eq_eps(hit.distance[0], hit.voxel.lower[0] - r.org[0], 1.e-6));
+ CHK(eq_eps(hit.distance[1], hit.voxel.upper[0] - r.org[0], 1.e-6));
+ CHK(hit.voxel.is_leaf);
+ CHK(hit.voxel.depth == 3);
+ CHK(*(char*)hit.voxel.data == 0);
+ CHK(IS_INF(hit.voxel.lower[1]));
+ CHK(IS_INF(hit.voxel.lower[2]));
+ CHK(IS_INF(hit.voxel.upper[1]));
+ CHK(IS_INF(hit.voxel.upper[2]));
+
+ /* Check first hit with negative ray */
+ d3(r.org, 1.01, 1234, 10);
+ d3(r.dir, -1, 0, 0);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit2) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit2));
+ CHK(eq_eps(hit2.distance[0], 0.01, 1.e-6));
+ CHK(eq_eps(hit2.distance[0], r.org[0] - hit2.voxel.upper[0], 1.e-6));
+ CHK(eq_eps(hit2.distance[1], r.org[0] - hit2.voxel.lower[0], 1.e-6));
+ CHK(hit2.voxel.is_leaf);
+ CHK(*(char*)hit2.voxel.data == 0);
+ CHK(eq_eps(hit2.distance[0], hit2.distance[0], 1.e-6));
+ CHK(eq_eps(hit2.distance[1], hit2.distance[1], 1.e-6));
+
+ /* Check first hit with negative ray and and a non orthognal r.dir */
+ d3_normalize(r.dir, d3(r.dir, -1, -1, -1));
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+ CHK(SVX_VOXEL_EQ(&hit.voxel, &hit2.voxel));
+ CHK(eq_eps(hit.distance[0], (hit.voxel.upper[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit.distance[1], (hit.voxel.lower[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit.voxel.upper[0], 1, 1.e-6));
+ CHK(eq_eps(hit.voxel.lower[0], 1-2*(1/(double)(1<<hit.voxel.depth)), 1.e-6));
+ CHK(hit.voxel.is_leaf);
+ CHK(hit.voxel.depth == 3);
+ CHK(*(char*)hit.voxel.data == 0);
+
+ /* Use challenge functor to intersect voxels that are note leaves */
+ d3(r.org, 2, 1, 0);
+ d3(r.dir, -rand_canonic(), rand_canonic()*2-1, rand_canonic()*2-1);
+ d3_normalize(r.dir, r.dir);
+ CHK(RT(btree, r.org, r.dir, r.range, hit_challenge, NULL, NULL, &hit)==RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+ CHK(!SVX_VOXEL_EQ(&hit.voxel, &hit2.voxel));
+ CHK(hit.voxel.is_leaf == 0);
+ CHK(hit.voxel.depth < 3);
+ CHK(*(char*)hit.voxel.data == 1);
+ CHK(eq_eps(hit.distance[0], (hit.voxel.upper[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit.distance[1], (hit.voxel.lower[0]-r.org[0])/r.dir[0], 1.e-6));
+
+ /* Use filter function to discard leaves with a value == 0 */
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter, &r, &hit) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+ CHK(hit.voxel.is_leaf == 1);
+ CHK(hit.voxel.depth == 5);
+ CHK(*(char*)hit.voxel.data == 1);
+ CHK(eq_eps(hit.distance[0], (hit.voxel.upper[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit.distance[1], (hit.voxel.lower[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit.voxel.lower[0], 0.5, 1.e-6));
+ CHK(eq_eps(hit.voxel.upper[0], 0.5+2.0/32.0, 1.e-6));
+
+ /* Use the ray range to avoid the intersection with the closest voxel */
+ r.range[1] = hit.distance[0] - 1.e-6;
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter, &r, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+ r.range[1] = INF;
+
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter, &r, &hit) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+
+ /* Use the ray range to discard the closest voxel */
+ r.range[0] = hit.distance[1] + 1.e-6;
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter, &r, &hit2) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit2));
+ CHK(!SVX_VOXEL_EQ(&hit.voxel, &hit2.voxel));
+ CHK(hit2.voxel.is_leaf == 1);
+ CHK(hit2.voxel.depth == 5);
+ CHK(*(char*)hit2.voxel.data == 1);
+ CHK(eq_eps(hit2.distance[0], (hit2.voxel.upper[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit2.distance[1], (hit2.voxel.lower[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit2.voxel.lower[0], 0.5-2.0/32.0, 1.e-6));
+ CHK(eq_eps(hit2.voxel.upper[0], 0.5, 1.e-6));
+
+ /* Adjust the ray range to intersect the interior of the closest voxel */
+ r.range[0] = hit.distance[0] + 1.e-6;
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter, &r, &hit2) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit2));
+ CHK(SVX_VOXEL_EQ(&hit.voxel, &hit2.voxel));
+ CHK(eq_eps(hit2.distance[0], r.range[0], 1.e-6));
+ CHK(eq_eps(hit2.distance[1], hit.distance[1], 1.e-6));
+
+ /* Discard the closest voxel != 0 with the filter function */
+ d2(r.range, 0, INF);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter2, &hit.voxel, &hit2) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit2));
+ CHK(!SVX_VOXEL_EQ(&hit.voxel, &hit2.voxel));
+ CHK(eq_eps(hit2.distance[0], (hit2.voxel.upper[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit2.distance[1], (hit2.voxel.lower[0]-r.org[0])/r.dir[0], 1.e-6));
+ CHK(eq_eps(hit2.voxel.lower[0], 0.5-2.0/32.0, 1.e-6));
+ CHK(eq_eps(hit2.voxel.upper[0], 0.5, 1.e-6));
+
+ /* Use the filter functor to accumulate the leaves */
+ accum = 0;
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter3, &accum, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+ CHK(accum == 4);
+
+ /* Check ray with null dir along the btree axis */
+ d2(r.range, 0, INF);
+ d3(r.org, -0.875, 123, 456);
+ d3(r.dir, 0, rand_canonic()*2-1, rand_canonic()*2-1);
+ d3_normalize(r.dir, r.dir);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+ CHK(eq_eps(hit.distance[0], r.range[0], 1.e-6));
+ CHK(IS_INF(hit.distance[1]));
+ CHK(hit.voxel.is_leaf == 1);
+ CHK(hit.voxel.depth == 3);
+ CHK(svx_tree_at(btree, r.org, NULL, NULL, &voxel) == RES_OK);
+ CHK(SVX_VOXEL_EQ(&voxel, &hit.voxel));
+ CHK(*(char*)hit.voxel.data == 0);
+
+ /* Use hit filter to discard the hit */
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter, &r, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+
+ /* Check ray with null dir along the btree axis */
+ d3(r.org, -0.625, 456, 789);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(!SVX_HIT_NONE(&hit));
+ CHK(eq_eps(hit.distance[0], r.range[0], 1.e-6));
+ CHK(IS_INF(hit.distance[1]));
+ CHK(hit.voxel.is_leaf == 1);
+ CHK(svx_tree_at(btree, r.org, NULL, NULL, &voxel) == RES_OK);
+ CHK(SVX_VOXEL_EQ(&voxel, &hit.voxel));
+ CHK(*(char*)hit.voxel.data == 0);
+
+ /* Use hit chalenge to intersect a non leaf node */
+ CHK(RT(btree, r.org, r.dir, r.range, hit_challenge, NULL, NULL, &hit2) == RES_OK);
+ CHK(eq_eps(hit.distance[0], r.range[0], 1.e-6));
+ CHK(IS_INF(hit.distance[1]));
+ CHK(!SVX_HIT_NONE(&hit2));
+ CHK(!SVX_VOXEL_EQ(&hit2.voxel, &hit.voxel));
+ CHK(*(char*)hit2.voxel.data == 1);
+ CHK(hit2.voxel.depth < 3);
+
+ /* Stil lcheck a ray with null dir along the tree axis */
+ d3(r.org, -0.51, 31, 41);
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, NULL, NULL, &hit) == RES_OK);
+ CHK(eq_eps(hit.distance[0], r.range[0], 1.e-6));
+ CHK(IS_INF(hit.distance[1]));
+ CHK(hit.voxel.is_leaf == 1);
+ CHK(svx_tree_at(btree, r.org, NULL, NULL, &voxel) == RES_OK);
+ CHK(SVX_VOXEL_EQ(&voxel, &hit.voxel));
+ CHK(*(char*)hit.voxel.data == 1);
+ CHK(eq_eps(hit.voxel.lower[0], -0.5-2.0/32.0, 1.e-6));
+ CHK(eq_eps(hit.voxel.upper[0], -0.5, 1.e-6));
+ CHK(IS_INF(hit.voxel.lower[1]));
+ CHK(IS_INF(hit.voxel.lower[2]));
+ CHK(IS_INF(hit.voxel.upper[1]));
+ CHK(IS_INF(hit.voxel.upper[2]));
+
+ /* Use hit filter to accum data along the ray */
+ accum = 0;
+ CHK(RT(btree, r.org, r.dir, r.range, NULL, hit_filter3, &accum, &hit) == RES_OK);
+ CHK(SVX_HIT_NONE(&hit));
+ CHK(accum == 1);
+
+ CHK(svx_tree_ref_put(btree) == RES_OK);
+ CHK(svx_device_ref_put(dev) == RES_OK);
+ CHK(mem_allocated_size() == 0);
+ return 0;
+}
+
