From 6592197ee64e1a1d4f1c7db3573895ddce617571 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Thu, 20 May 2010 22:16:03 -0600
Subject: Store the bounding boxes of child PR-tree nodes in the parent.

This improves cache locality and is good for about a 10% performance boost.
---
 libdimension/prtree.c | 119 ++++++++++++++++++++++++++------------------------
 libdimension/prtree.h |   8 ++--
 2 files changed, 67 insertions(+), 60 deletions(-)

(limited to 'libdimension')

diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index 53e6bdb..c9c4f9a 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -379,7 +379,17 @@ dmnsn_new_prtree_node(const dmnsn_pseudo_prleaf *leaf)
   node->bounding_box = leaf->bounding_box;
 
   for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
-    node->children[i] = leaf->children[i];
+    if (!leaf->children[i]) {
+      node->children[i] = NULL;
+    } else if (leaf->is_leaf) {
+      dmnsn_object *object = leaf->children[i];
+      node->children[i] = object;
+      node->bounding_boxes[i] = object->bounding_box;
+    } else {
+      dmnsn_prtree_node *child = leaf->children[i];
+      node->children[i] = child;
+      node->bounding_boxes[i] = child->bounding_box;
+    }
   }
 
   return node;
@@ -515,61 +525,7 @@ dmnsn_delete_prtree(dmnsn_prtree *tree)
 }
 
 /* Ray-AABB intersection test */
-static bool dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_bounding_box box,
-                                       double t);
-
-static void
-dmnsn_prtree_search_recursive(const dmnsn_prtree_node *node, dmnsn_line ray,
-                              dmnsn_intersection *intersection, double *t)
-{
-  if (dmnsn_ray_box_intersection(ray, node->bounding_box, *t)) {
-    for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
-      if (!node->children[i])
-        break;
-
-      if (node->is_leaf) {
-        dmnsn_object *object = node->children[i];
-
-        dmnsn_intersection local_intersection;
-        if (dmnsn_ray_box_intersection(ray, object->bounding_box, *t)) {
-          if ((*object->intersection_fn)(object, ray, &local_intersection)) {
-            if (*t < 0.0 || local_intersection.t < *t) {
-              *intersection = local_intersection;
-              *t = local_intersection.t;
-            }
-          }
-        }
-      } else {
-        dmnsn_prtree_search_recursive(node->children[i], ray, intersection, t);
-      }
-    }
-  }
-}
-
-bool
-dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
-                    dmnsn_intersection *intersection)
-{
-  double t = -1.0;
-
-  /* Search the unbounded objects */
-  DMNSN_ARRAY_FOREACH (dmnsn_object **, object, tree->unbounded) {
-    dmnsn_intersection local_intersection;
-    if ((*(*object)->intersection_fn)(*object, ray, &local_intersection)) {
-      if (t < 0.0 || local_intersection.t < t) {
-        *intersection = local_intersection;
-        t = local_intersection.t;
-      }
-    }
-  }
-
-  /* Search the bounded objects */
-  dmnsn_prtree_search_recursive(tree->root, ray, intersection, &t);
-
-  return t >= 0.0;
-}
-
-static bool
+static inline bool
 dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
 {
   double tmin = -INFINITY, tmax = INFINITY;
@@ -621,3 +577,54 @@ dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
 
   return t < 0.0 || tmin < t;
 }
+
+static void
+dmnsn_prtree_search_recursive(const dmnsn_prtree_node *node, dmnsn_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, 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 (*t < 0.0 || local_intersection.t < *t) {
+            *intersection = local_intersection;
+            *t = local_intersection.t;
+          }
+        }
+      } else {
+        dmnsn_prtree_search_recursive(node->children[i], ray, intersection, t);
+      }
+    }
+  }
+}
+
+bool
+dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
+                    dmnsn_intersection *intersection)
+{
+  double t = -1.0;
+
+  /* Search the unbounded objects */
+  DMNSN_ARRAY_FOREACH (dmnsn_object **, object, tree->unbounded) {
+    dmnsn_intersection local_intersection;
+    if ((*(*object)->intersection_fn)(*object, ray, &local_intersection)) {
+      if (t < 0.0 || local_intersection.t < t) {
+        *intersection = local_intersection;
+        t = local_intersection.t;
+      }
+    }
+  }
+
+  /* Search the bounded objects */
+  if (dmnsn_ray_box_intersection(ray, tree->root->bounding_box, t)) {
+    dmnsn_prtree_search_recursive(tree->root, ray, intersection, &t);
+  }
+
+  return t >= 0.0;
+}
diff --git a/libdimension/prtree.h b/libdimension/prtree.h
index 1f2dd29..eab359d 100644
--- a/libdimension/prtree.h
+++ b/libdimension/prtree.h
@@ -34,12 +34,12 @@
 #define DMNSN_PRTREE_B 6
 
 typedef struct dmnsn_prtree_node {
+  dmnsn_bounding_box bounding_box;
+
   /* Children (objects or subtrees) */
-  void *children[DMNSN_PRTREE_B];
   bool is_leaf;
-
-  /* Bounding box */
-  dmnsn_bounding_box bounding_box;
+  void *children[DMNSN_PRTREE_B];
+  dmnsn_bounding_box bounding_boxes[DMNSN_PRTREE_B];
 } dmnsn_prtree_node;
 
 typedef struct dmnsn_prtree {
-- 
cgit v1.2.3