From 772c252a6b279b8a841f83816e8b170f06636f32 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Thu, 15 Jul 2010 18:42:14 -0600
Subject: Clean up optimized ray-AABB intersection code a bit.

---
 libdimension/prtree.c | 50 +++++++++++++++++++++++++++++---------------------
 1 file changed, 29 insertions(+), 21 deletions(-)

(limited to 'libdimension/prtree.c')

diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index 6fa2d10..b1ae2fa 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -523,9 +523,14 @@ dmnsn_delete_prtree(dmnsn_prtree *tree)
   }
 }
 
+typedef struct dmnsn_inverted_line {
+  dmnsn_line line;
+  dmnsn_vector n_inv;
+} dmnsn_optimized_line;
+
 /* Ray-AABB intersection test */
 static inline bool
-dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_vector inv,
+dmnsn_ray_box_intersection(dmnsn_optimized_line optline,
                            dmnsn_bounding_box box, double t)
 {
   double tmin = -INFINITY, tmax = INFINITY;
@@ -534,43 +539,43 @@ dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_vector inv,
   if (box.min.x >= box.max.x)
     return false;
 
-  if (line.n.x != 0.0) {
+  if (optline.line.n.x != 0.0) {
     /* inv.x == 1.0/line.n.x */
-    double tx1 = (box.min.x - line.x0.x)*inv.x;
-    double tx2 = (box.max.x - line.x0.x)*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));
 
     if (tmin > tmax)
       return false;
-  } else if (line.x0.x < box.min.x || line.x0.x > box.max.x) {
+  } else if (optline.line.x0.x < box.min.x || optline.line.x0.x > box.max.x) {
     return false;
   }
 
-  if (line.n.y != 0.0) {
-    double ty1 = (box.min.y - line.x0.y)*inv.y;
-    double ty2 = (box.max.y - line.x0.y)*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));
 
     if (tmin > tmax)
       return false;
-  } else if (line.x0.y < box.min.y || line.x0.y > box.max.y) {
+  } else if (optline.line.x0.y < box.min.y || optline.line.x0.y > box.max.y) {
     return false;
   }
 
-  if (line.n.z != 0.0) {
-    double tz1 = (box.min.z - line.x0.z)*inv.z;
-    double tz2 = (box.max.z - line.x0.z)*inv.z;
+  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 (line.x0.z < box.min.z || line.x0.z > box.max.z) {
+  } else if (optline.line.x0.z < box.min.z || optline.line.x0.z > box.max.z) {
     return false;
   }
 
@@ -579,27 +584,28 @@ dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_vector inv,
 
 static void
 dmnsn_prtree_intersection_recursive(const dmnsn_prtree_node *node,
-                                    dmnsn_line ray, dmnsn_vector inv,
+                                    dmnsn_optimized_line ray,
                                     dmnsn_intersection *intersection, double *t)
 {
   for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
     if (!node->children[i])
       break;
 
-    if (dmnsn_ray_box_intersection(ray, inv, node->bounding_boxes[i], *t)) {
+    if (dmnsn_ray_box_intersection(ray, node->bounding_boxes[i], *t)) {
       if (node->is_leaf) {
         dmnsn_object *object = node->children[i];
 
         dmnsn_intersection local_intersection;
-        if ((*object->intersection_fn)(object, ray, &local_intersection)) {
+        if ((*object->intersection_fn)(object, ray.line, &local_intersection)) {
           if (local_intersection.t < *t) {
             *intersection = local_intersection;
             *t = local_intersection.t;
           }
         }
       } else {
-        dmnsn_prtree_intersection_recursive(node->children[i], ray, inv,
-                                            intersection, t);
+        dmnsn_prtree_intersection_recursive(
+          node->children[i], ray, intersection, t
+        );
       }
     }
   }
@@ -623,11 +629,13 @@ 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_vector inv = dmnsn_new_vector(1.0/ray.n.x, 1.0/ray.n.y, 1.0/ray.n.z);
+  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);
 
   /* Search the bounded objects */
-  if (dmnsn_ray_box_intersection(ray, inv, tree->root->bounding_box, t)) {
-    dmnsn_prtree_intersection_recursive(tree->root, ray, inv, intersection, &t);
+  if (dmnsn_ray_box_intersection(optline, tree->root->bounding_box, t)) {
+    dmnsn_prtree_intersection_recursive(tree->root, optline, intersection, &t);
   }
 
   return !isinf(t);
-- 
cgit v1.2.3