summaryrefslogtreecommitdiffstats
path: root/libdimension
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-05-20 22:16:03 -0600
committerTavian Barnes <tavianator@gmail.com>2010-05-20 22:16:03 -0600
commit6592197ee64e1a1d4f1c7db3573895ddce617571 (patch)
tree75a3f0a40ae9d48dfe499f001171fa0a31cc89dc /libdimension
parentd1e94994f75466ab207322f59847ac0f359f46b8 (diff)
downloaddimension-6592197ee64e1a1d4f1c7db3573895ddce617571.tar.xz
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.
Diffstat (limited to 'libdimension')
-rw-r--r--libdimension/prtree.c119
-rw-r--r--libdimension/prtree.h8
2 files changed, 67 insertions, 60 deletions
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 {