From d543caf4ad629ec5313463f6e78e5931c406a353 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Thu, 15 Jul 2010 19:15:19 -0600
Subject: Remove some unneeded tests from ray-AABB intersection tests.

---
 libdimension/prtree.c | 71 ++++++++++++++++++++-------------------------------
 1 file changed, 28 insertions(+), 43 deletions(-)

(limited to 'libdimension/prtree.c')

diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index b1ae2fa..43400a3 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -523,63 +523,50 @@ dmnsn_delete_prtree(dmnsn_prtree *tree)
   }
 }
 
-typedef struct dmnsn_inverted_line {
+typedef struct dmnsn_optimized_line {
   dmnsn_line line;
   dmnsn_vector n_inv;
 } dmnsn_optimized_line;
 
-/* Ray-AABB intersection test */
+/* Precompute inverses for faster ray-box intersection tests */
+static inline dmnsn_optimized_line
+dmnsn_optimize_line(dmnsn_line line)
+{
+  dmnsn_optimized_line optline = {
+    .line  = line,
+    .n_inv = dmnsn_new_vector(1.0/line.n.x, 1.0/line.n.y, 1.0/line.n.z)
+  };
+  return optline;
+}
+
+/* Ray-AABB intersection test, by the slab method */
 static inline bool
 dmnsn_ray_box_intersection(dmnsn_optimized_line optline,
                            dmnsn_bounding_box box, double t)
 {
-  double tmin = -INFINITY, tmax = INFINITY;
-
-  /* Detenerate box test */
+  /* Degenerate box test */
   if (box.min.x >= box.max.x)
     return false;
 
-  if (optline.line.n.x != 0.0) {
-    /* inv.x == 1.0/line.n.x */
-    double tx1 = (box.min.x - optline.line.x0.x)*optline.n_inv.x;
-    double tx2 = (box.max.x - optline.line.x0.x)*optline.n_inv.x;
+  double tx1 = (box.min.x - optline.line.x0.x)*optline.n_inv.x;
+  double tx2 = (box.max.x - optline.line.x0.x)*optline.n_inv.x;
 
-    tmin = dmnsn_max(tmin, dmnsn_min(tx1, tx2));
-    tmax = dmnsn_min(tmax, dmnsn_max(tx1, tx2));
+  double tmin = dmnsn_min(tx1, tx2);
+  double tmax = dmnsn_max(tx1, tx2);
 
-    if (tmin > tmax)
-      return false;
-  } else if (optline.line.x0.x < box.min.x || optline.line.x0.x > box.max.x) {
-    return false;
-  }
+  double ty1 = (box.min.y - optline.line.x0.y)*optline.n_inv.y;
+  double ty2 = (box.max.y - optline.line.x0.y)*optline.n_inv.y;
 
-  if (optline.line.n.y != 0.0) {
-    double ty1 = (box.min.y - optline.line.x0.y)*optline.n_inv.y;
-    double ty2 = (box.max.y - optline.line.x0.y)*optline.n_inv.y;
+  tmin = dmnsn_max(tmin, dmnsn_min(ty1, ty2));
+  tmax = dmnsn_min(tmax, dmnsn_max(ty1, ty2));
 
-    tmin = dmnsn_max(tmin, dmnsn_min(ty1, ty2));
-    tmax = dmnsn_min(tmax, dmnsn_max(ty1, ty2));
+  double tz1 = (box.min.z - optline.line.x0.z)*optline.n_inv.z;
+  double tz2 = (box.max.z - optline.line.x0.z)*optline.n_inv.z;
 
-    if (tmin > tmax)
-      return false;
-  } else if (optline.line.x0.y < box.min.y || optline.line.x0.y > box.max.y) {
-    return false;
-  }
-
-  if (optline.line.n.z != 0.0) {
-    double tz1 = (box.min.z - optline.line.x0.z)*optline.n_inv.z;
-    double tz2 = (box.max.z - optline.line.x0.z)*optline.n_inv.z;
-
-    tmin = dmnsn_max(tmin, dmnsn_min(tz1, tz2));
-    tmax = dmnsn_min(tmax, dmnsn_max(tz1, tz2));
-
-    if (tmin > tmax)
-      return false;
-  } else if (optline.line.x0.z < box.min.z || optline.line.x0.z > box.max.z) {
-    return false;
-  }
+  tmin = dmnsn_max(tmin, dmnsn_min(tz1, tz2));
+  tmax = dmnsn_min(tmax, dmnsn_max(tz1, tz2));
 
-  return tmax >= 0.0 && tmin < t;
+  return tmax >= 0.0 && tmax >= tmin && tmin < t;
 }
 
 static void
@@ -629,9 +616,7 @@ dmnsn_prtree_intersection(const dmnsn_prtree *tree, dmnsn_line ray,
   }
 
   /* Precalculate 1.0/ray.n.{x,y,z} to save time in intersection tests */
-  dmnsn_optimized_line optline;
-  optline.line = ray;
-  optline.n_inv = dmnsn_new_vector(1.0/ray.n.x, 1.0/ray.n.y, 1.0/ray.n.z);
+  dmnsn_optimized_line optline = dmnsn_optimize_line(ray);
 
   /* Search the bounded objects */
   if (dmnsn_ray_box_intersection(optline, tree->root->bounding_box, t)) {
-- 
cgit v1.2.3