commit 912c1e6946146693e3ecbf622a8e63573903db0c
parent e3b3bd37057cdac1e232ad86ce94d2b7e8c6a3ad
Author: Vincent Forest <vincent.forest@meso-star.com>
Date: Fri, 9 Mar 2018 10:54:05 +0100
Add the support of `challenge' and `filter' funcs to the RT
Diffstat:
4 files changed, 163 insertions(+), 79 deletions(-)
diff --git a/src/svx.h b/src/svx.h
@@ -129,6 +129,7 @@ typedef int
(const struct svx_hit* hit,
const double ray_org[3],
const double ray_dir[3],
+ const double ray_range[2],
void* context); /* User data submitted on trace ray invocation */
/* Hit filter function data type. One can define such function to discard
diff --git a/src/svx_octree.c b/src/svx_octree.c
@@ -572,10 +572,15 @@ svx_octree_create
vox_sz[2] = (upper[2] - lower[2]) / (double)nvoxels[2];
/* Compute the octree AABB in world space */
- d3_set(oct->oclow, lower);
+ oct->oclow[0] = lower[0];
+ oct->oclow[1] = lower[1];
+ oct->oclow[2] = lower[2];
oct->ocupp[0] = (double)oct->definition * vox_sz[0];
oct->ocupp[1] = (double)oct->definition * vox_sz[1];
oct->ocupp[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];
/* 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 */
diff --git a/src/svx_octree.h b/src/svx_octree.h
@@ -24,6 +24,7 @@ struct svx_octree {
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 octree_buffer buffer;
struct octree_index root; /* Index toward the children of the root */
diff --git a/src/svx_octree_trace_ray.c b/src/svx_octree_trace_ray.c
@@ -17,10 +17,22 @@
#include "svx_scene.h"
struct ray {
+ /* Ray parameters in the normalized octree space [1, 2]^3 whose ray direction
+ * is assumed to be always negative. octant_mask defines which dimension was
+ * reverted to ensure the negative ray direction: the bit 1, 2 and 3 are set if
+ * the Z, Y and X dimension was reverted, respectively. */
double org[3];
double range[2];
double ts[3]; /* 1 / -abs(dir) */
uint32_t octant_mask;
+
+ /* Ray origin and direction in world space. Note that the ray range is
+ * independent of the octree space. Let a ray `r' in world space defined as
+ * `r = O + tD'; one can transform the ray in another space by the Matrix M
+ * as `r' = M.O + t*(M.D)' without any impact on the t parameter and thus on
+ * its range. Only the norm of ray direction might be updated. */
+ double orgws[3];
+ double dirws[3];
};
/*******************************************************************************
@@ -42,52 +54,96 @@ uitof(const uint32_t ui)
return ucast.f;
}
+static FINLINE void
+setup_hit
+ (const struct svx_octree* oct,
+ const struct octree_index iattr, /* Index toward the voxel attributes */
+ const double distance, /* Hit distance */
+ const double corner[3], /* Corner of the current voxel in [1, 2]^3 space */
+ const double scale_exp2, /* Size of the voxel in [1, 2]^3] space */
+ const size_t depth, /* Depth of the voxel in the octree hierarchy */
+ const int is_leaf, /* Define if the voxel is a leaf or not */
+ const uint32_t octant_mask, /* bitmask of reverted dimensions */
+ struct svx_hit* hit)
+{
+ double low[3], upp[3];
+ ASSERT(oct && corner && voxsz && hit);
+ ASSERT(distance > 0);
+
+ hit->distance = distance;
+ hit->voxel.data = octree_buffer_get_attr(&oct->buffer, &iattr);
+ hit->voxel.depth = depth,
+ hit->voxel.id = absolute_attr_index(&oct->buffer, iattr);
+ hit->voxel.is_leaf = is_leaf;
+
+ /* Transform the voxel aabb in the [0, 1]^3 normalized space and flip it wrt
+ * to the octant mask of the ray */
+ low[0] = corner[0] - 1;
+ low[1] = corner[1] - 1;
+ low[2] = corner[2] - 1;
+ if(octant_mask & 4) low[0] = 1 - low[0] - scale_exp2;
+ if(octant_mask & 2) low[1] = 1 - low[1] - scale_exp2;
+ if(octant_mask & 1) low[2] = 1 - low[2] - scale_exp2;
+ upp[0] = low[0] + scale_exp2;
+ upp[1] = low[1] + scale_exp2;
+ 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];
+}
+
/* Return RES_BAD_OP if the ray cannot intersect the scene */
static res_T
setup_ray
- (const struct scene* scn,
- const double org[3],
+ (const struct svx_octree* oct,
+ const double org[3]
const double dir[3],
const double range[2]
struct ray* ray)
{
double rcp_ocsz[3]; /* Reciprocal size of the World space octree AABB */
- ASSERT(scn);
+ double dir_adjusted[3];
+ ASSERT(oct);
if(range[0] >= range[1]) return RES_BAD_OP; /* Disabled ray */
/* Ray paralelle to an axis and that does not intersect the scene AABB */
- if((!dir[0] && (org[0] < scn->lower[0] || org[0] > scn->upper[0]))
- || (!dir[1] && (org[1] < scn->lower[1] || org[1] > scn->upper[1]))
- || (!dir[2] && (org[2] < scn->lower[2] || org[2] > scn->upper[2]))) {
+ if((!dir[0] && (org[0] < oct->lower[0] || org[0] > oct->upper[0]))
+ || (!dir[1] && (org[1] < oct->lower[1] || org[1] > oct->upper[1]))
+ || (!dir[2] && (org[2] < oct->lower[2] || org[2] > oct->upper[2]))) {
return RES_BAD_OP;
}
/* Compute reciprocal size of the world space octree AABB */
- rcp_ocsz[0] = 1.0 / (scn->ocupp[0] - scn->oclow[0]);
- rcp_ocsz[1] = 1.0 / (scn->ocupp[1] - scn->oclow[1]);
- rcp_ocsz[2] = 1.0 / (scn->ocupp[2] - scn->oclow[2]);
+ rcp_ocsz[0] = 1.0 / oct->ocsize[0];
+ rcp_ocsz[1] = 1.0 / oct->ocsize[1];
+ rcp_ocsz[2] = 1.0 / oct->ocsize[2];
/* Transform the ray origin in the [1, 2] space */
- ray->org[0] = (org[0] - scn->oclow[0]) * rcp_ocsz[0] + 1.0;
- ray->org[1] = (org[1] - scn->oclow[1]) * rcp_ocsz[1] + 1.0;
- ray->org[2] = (org[2] - scn->oclow[2]) * rcp_ocsz[2] + 1.0;
+ 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;
- /* Transform the range in the normalized octree space */
- ray->range[0] = range[0] * rcp_ocsz[0];
- ray->range[1] = range[1] * rcp_ocsz[1];
+ /* Setup the ray range */
+ ray->range[0] = range[0];
+ ray->range[1] = range[1];
/* Transform the direction in the normalized octree space */
- ray->dir[0] = dir[0] * rcp_ocsz[0];
- ray->dir[1] = dir[1] * rcp_ocsz[1];
- ray->dir[2] = dir[2] * rcp_ocsz[2];
+ dir_adjusted[0] = dir[0] * rcp_ocsz[0];
+ dir_adjusted[1] = dir[1] * rcp_ocsz[1];
+ dir_adjusted[2] = dir[2] * rcp_ocsz[2];
/* Let a ray defines as org + t*dir and X the coordinate of an axis aligned
* plane. The ray intersects X at t = (X - org)/dir = (X - org) * ts; with ts
* = 1/dir. Note that one assume that dir is always negative. */
- ray->ts[0] = 1.0 / -abs(dir[0]);
- ray->ts[1] = 1.0 / -abs(dir[1]);
- ray->ts[2] = 1.0 / -abs(dir[2]);
+ ray->ts[0] = 1.0 / -abs(dir_adjusted[0]);
+ ray->ts[1] = 1.0 / -abs(dir_adjusted[1]);
+ ray->ts[2] = 1.0 / -abs(dir_adjusted[2]);
/* Mirror rays with position directions */
ray->octant_mask = 0;
@@ -95,11 +151,26 @@ setup_ray
if(ray_dir[1] > 0) { ray->octant_mask ^= 2; ray->org[0] = 3.0 - ray->org[1]; }
if(ray_dir[2] > 0) { ray->octant_mask ^= 1; ray->org[0] = 3.0 - ray->org[2]; }
+ /* Save the world space ray origin */
+ ray->orgws[0] = org[0];
+ ray->orgws[1] = org[1];
+ ray->orgws[2] = org[2];
+
+ /* Save the world space ray direction */
+ ray->dirws[0] = dir[0];
+ ray->dirws[1] = dir[1];
+ ray->dirws[2] = dir[2];
+
return RES_OK;
}
static res_T
-trace_ray(const struct svx_octree* oct, const struct* ray, struct svx_hit* hit)
+trace_ray
+ (const struct svx_octree* oct,
+ const svx_challenge_voxel_T challenge,
+ const svx_hit_filter_function_T filter,
+ const struct ray* ray,
+ struct svx_hit* hit)
{
#define SCALE_MAX 23 /* #mantisse bits */
struct stack_entry {
@@ -168,39 +239,62 @@ trace_ray(const struct svx_octree* oct, const struct* ray, struct svx_hit* hit)
/* Traverse the current child */
if((node->is_valid & ichild_flag)
&& t_min <= (t_max_child = MMIN(t_max, t_max_corner))) {
- double t_max_parent;
- double t_center[3];
- float scale_exp2_child;
-
- t_max_parent = t_max;
- t_max = t_max_child;
-
- if(node->is_leaf & ichild_flag) break; /* Leaf node */
- /* TODO invoke filter function if necessary */
-
- scale_exp2_child = scale_exp2 * 0.5f;
-
- /* center = corner - scale_exp2_child =>
- * t_center = ts*(corner + scale_exp2_child - org)
- * t_center = t_corner + ts*scale_exp2_child
- * Anyway we perforrm the whole computation to avoid numerical issues */
- t_center[0] = (corner[0] - ray->org[0] + scale_exp2_child) * ray->ts[0];
- t_center[1] = (corner[1] - ray->org[1] + scale_exp2_child) * ray->ts[1];
- t_center[2] = (corner[2] - ray->org[2] + scale_exp2_child) * ray->ts[2];
-
- /* Push the parent node */
- stack[scale].t_max = t_max_parent;
- stack[scale].inode = inode;
-
- /* Define the id and the lower left corner of the first child */
- ichild = 0;
- if(t_center[0] > t_min) { ichild ^= 4; corner[0] += scale_exp2_child; }
- if(t_center[1] > t_min) { ichild ^= 2; corner[1] += scale_exp2_child; }
- if(t_center[2] > t_min) { ichild ^= 1; corner[2] += scale_exp2_child; }
-
- --scale;
- scale_exp2 = scale_exp2_child;
- continue;
+ const int is_leaf = is_leaf = (node->is_leaf & ichild_flag) != 0;
+ int go_deeper = 1;
+
+ /* If the current voxel is a leaf or if a challenge function is set,
+ * check the current hit */
+ if(is_leaf || challenge) {
+ const double dst = t_min < ray->range[0] ? t_max_child : t_min;
+ const size_t depth = SCALE_MAX - scale;
+ const struct octree_index iattr = octree_buffer_get_child_attr_index
+ (&oct->buffer, &inode, ichild_adjusted);
+
+ setup_hit(oct, iattr, dst, corner, scale_exp2, depth, is_leaf,
+ ray->octant_mask, hit);
+
+ if(is_leaf || challenge(hit, context)) {
+ go_deeper = 0;
+ /* Stop the traversal if no filter is defined or if the filter
+ * function returns 0 */
+ if(!filter /* By default, i.e. with no filter, stop the traversal */
+ || !filter(hit, ray->orgws, ray->dirws, ray->range, context))
+ break;
+ }
+ }
+
+ if(go_deeper) {
+ double t_max_parent;
+ double t_center[3];
+ float scale_exp2_child;
+
+ t_max_parent = t_max;
+ t_max = t_max_child;
+
+ scale_exp2_child = scale_exp2 * 0.5f;
+
+ /* center = corner - scale_exp2_child =>
+ * t_center = ts*(corner + scale_exp2_child - org)
+ * t_center = t_corner + ts*scale_exp2_child
+ * Anyway we perforrm the whole computation to avoid numerical issues */
+ t_center[0] = (corner[0] - ray->org[0] + scale_exp2_child) * ray->ts[0];
+ t_center[1] = (corner[1] - ray->org[1] + scale_exp2_child) * ray->ts[1];
+ t_center[2] = (corner[2] - ray->org[2] + scale_exp2_child) * ray->ts[2];
+
+ /* Push the parent node */
+ stack[scale].t_max = t_max_parent;
+ stack[scale].inode = inode;
+
+ /* Define the id and the lower left corner of the first child */
+ ichild = 0;
+ if(t_center[0] > t_min) { ichild ^= 4; corner[0] += scale_exp2_child; }
+ if(t_center[1] > t_min) { ichild ^= 2; corner[1] += scale_exp2_child; }
+ if(t_center[2] > t_min) { ichild ^= 1; corner[2] += scale_exp2_child; }
+
+ --scale;
+ scale_exp2 = scale_exp2_child;
+ continue;
+ }
}
/* Define the id and the lower left corner of the next child */
@@ -270,27 +364,6 @@ trace_ray(const struct svx_octree* oct, const struct* ray, struct svx_hit* hit)
}
}
- if(scale < scale_max) {
- const uint8_t ichild_adjusted = (uint8_t)(ichild ^ ray->octant_mask);
- const struct octree_xnode* node = octree_buffer_get_node(&oct->buffer, inode);
- const struct octree_index iattr;
-
- /* Retrieve the node attribs */
- iattr = octree_buffer_get_child_attr_index(&oct->buffer, &inode, ichild_adjusted);
-
- /* Setu the hit */
- hit->distance = t_min < ray->range[0] ? t_max : t_min;
- hit->voxel.data = octree_buffer_get_attr(&oct->buffer, &iattr);
- hit->voxel.depth = SCALE_MAX - scale;
- hit->voxel.id = absolute_attr_index(&oct->buffer, iattr);
- hit->voxel.is_leaf = (node->is_leaf & ichild_adjusted) != 0;
- hit->voxel.lower[0] = corner[0];
- hit->voxel.lower[1] = corner[1];
- hit->voxel.lower[2] = corner[2];
- hit->voxel.upper[0] = corner[0] + scale_exp2;
- hit->voxel.upper[1] = corner[1] + scale_exp2;
- hit->voxel.upper[2] = corner[2] + scale_exp2;
- }
return RES_OK;
}
@@ -303,6 +376,7 @@ svx_octree_trace_ray
const double org[3],
const double dir[3],
const double range[2],
+ svx_challenge_voxel_T challenge,
svx_hit_filter_function_T filter,
void* context,
struct svx_hit* hit)
@@ -310,19 +384,22 @@ svx_octree_trace_ray
struct ray ray;
res_T res = RES_OK;
- if(!scn || !org || !range || !hit) {
+ if(!oct || !org || !range || !hit) {
res = RES_BAD_ARG;
goto error;
}
*hit = SVX_HIT_NULL;
- res = setup_ray(scn, org, dir, range, &ray);
+ res = setup_ray(oct, org, dir, range, &ray);
if(res == RES_BAD_OP) { /* The ray cannot intersect the scene. */
res = RES_OK;
goto exit;
}
+ res = trace_ray(oct, challenge, filter, ray, hit);
+ if(res != RES_OK) goto error;
+
exit:
return res;
error:
