star-vx

commit e4ad9db9319afbb0daf978dc1db1d3bb4f1b6abd
parent bacbd47c8ce43b6e178009f78f4666c831da14c5
Author: Vincent Forest <vincent.forest@meso-star.com>
Date:   Tue, 15 Oct 2024 12:28:31 +0200

Fix a ray-tracing bug in a binary tree

If the traced ray has a direction approximately aligned with the
infinite dimension, the caller could still cross the voxel boundary
whereas it was assumed that this could not happen. This is because even
with an approximately zero direction along the 1D axis, a ray can cross
the boundaries of the voxel in which it is located if the crossing
distance is long enough. This commit corrects this problem by forcing
the alignment of such a ray with the infinite dimension as soon as it is
detected as such.

Diffstat:
M
src/svx_bintree_trace_ray.c
 | 
32
++++++++++++++++++++++----------

1 file changed, 22 insertions(+), 10 deletions(-)
diff --git a/src/svx_bintree_trace_ray.c b/src/svx_bintree_trace_ray.c
@@ -87,6 +87,7 @@ bintree_trace_ray
   struct buffer_index inode;
   size_t istack; /* Top of the stack */
   size_t iaxis; /* Id in [0, 2] of the axis along which the tree is defined */
+  double rdir[3]; /* Ray direction adjusted wrt numerical problems */
   double pos_min, pos_max; /* Min/Max pos along the ray in [0,1] +dir 1D space */
   double org; /* Ray origin in the [0,1] +dir 1D space */
   double dir; /* Ray direction in the [0,1] +dir 1D space */
@@ -113,17 +114,29 @@ bintree_trace_ray
   rcp_btreesz = 1.0 / (double)btree->tree_size[iaxis];
   ASSERT(rcp_btreesz > 0);
 
+  d3_set(rdir, ray_dir);
+
+ /* Define whether the direction of the 1D ray is approximately aligned with the
+  * infinite dimension. If it is, make sure it's really aligned so that the
+  * caller can't have a ray that escapes the voxel from which the ray starts.
+  * Indeed, even with an approximately zero direction along the 1D axis, the ray
+  * can still cross the boundary of a voxel if the caller decides to make it
+  * travel long distances. */
+  null_dir = eq_eps(ray_dir[iaxis], 0, 1.e-6);
+  if(null_dir) {
+    rdir[iaxis] = 0;
+    d3_normalize(rdir, rdir);
+  }
+
   /* Transform the ray origin in [0, 1] space  */
   org = (ray_org[iaxis] - btree->tree_low[iaxis]) * rcp_btreesz;
   /* Transform the direction in the normalized bintree space */
-  dir = (ray_dir[iaxis] * rcp_btreesz);
-  /* Define if the 1D ray direction is roughly null */
-  null_dir = eq_eps(ray_dir[iaxis], 0, 1.e-6);
+  dir = (rdir[iaxis] * rcp_btreesz);
 
   /* The ray starts outside the binary tree and point outward the bin tree: it
    * cannot intersect the binary tree */
-  if((org > 1 && (dir > 0 || null_dir))
-  || (org < 0 && (dir < 0 || null_dir)))
+  if((org > 1 && dir >= 0)
+  || (org < 0 && dir <= 0))
     return RES_OK;
 
   /* Mirror rays with negative direction */
@@ -161,9 +174,9 @@ bintree_trace_ray
       0/*depth*/, 0/*is_leaf*/, flip, &hit_root);
     hit_root.voxel.data = btree->root_attr;
 
-    if(challenge(&hit_root, ray_org, ray_dir, ray_range, context)) {
+    if(challenge(&hit_root, ray_org, rdir, ray_range, context)) {
       if(!filter /* By default, i.e. with no filter, stop the traversal */
-      || !filter(&hit_root, ray_org, ray_dir, ray_range, context)) {
+      || !filter(&hit_root, ray_org, rdir, ray_range, context)) {
         *hit = hit_root;
         return RES_OK; /* Do not traverse the binary tree */
       }
@@ -211,12 +224,12 @@ bintree_trace_ray
           flip, &hit_tmp);
 
         if(is_leaf
-        || challenge(&hit_tmp, ray_org, ray_dir, ray_range, context)) {
+        || challenge(&hit_tmp, ray_org, rdir, ray_range, 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_tmp, ray_org, ray_dir, ray_range, context)) {
+          || !filter(&hit_tmp, ray_org, rdir, ray_range, context)) {
             *hit = hit_tmp;
             break;
           }
@@ -275,4 +288,3 @@ bintree_trace_ray
   }
   return RES_OK;
 }
-