Replace BVSTs with priority R-trees.

10 files changed, 636 insertions, 517 deletions

diff --git a/bench/libdimension/Makefile.am b/bench/libdimension/Makefile.am
index cc3d122..a384b56 100644
--- a/bench/libdimension/Makefile.am
+++ b/bench/libdimension/Makefile.am
@@ -19,18 +19,18 @@
 
 INCLUDES = -I$(top_srcdir)/libdimension
 
-EXTRA_PROGRAMS = bench-array bench-geometry bench-bvst
+EXTRA_PROGRAMS = bench-array bench-geometry bench-prtree
 
 AM_CFLAGS = $(libsandglass_CFLAGS) -fno-inline
 AM_LDFLAGS = $(libsandglass_LIBS) $(top_builddir)/libdimension/libdimension.la
 
 bench_array_SOURCES    = array.c
 bench_geometry_SOURCES = geometry.c
-bench_bvst_SOURCES     = bvst.c
+bench_prtree_SOURCES     = prtree.c
 
-bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-bvst$(EXEEXT)
+bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-prtree$(EXEEXT)
 	./bench-array$(EXEEXT)
 	./bench-geometry$(EXEEXT)
-	./bench-bvst$(EXEEXT)
+	./bench-prtree$(EXEEXT)
 
 .PHONY: bench
diff --git a/bench/libdimension/bvst.c b/bench/libdimension/prtree.c
index dd61a80..5ee32cf 100644
--- a/bench/libdimension/bvst.c
+++ b/bench/libdimension/prtree.c
@@ -66,17 +66,17 @@ dmnsn_randomize_bounding_box(dmnsn_object *object)
   }
 }
 
-dmnsn_bvst_node *
-dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node,
+dmnsn_prtree_node *
+dmnsn_prtree_deepest_recursive(dmnsn_prtree_node *node,
                                  unsigned int depth, unsigned int *deepest)
 {
-  dmnsn_bvst_node *left = NULL, *right = NULL;
+  dmnsn_prtree_node *left = NULL, *right = NULL;
 
   if (node->contains) {
-    left = dmnsn_bvst_deepest_recursive(node->contains, depth + 1, deepest);
+    left = dmnsn_prtree_deepest_recursive(node->contains, depth + 1, deepest);
   }
   if (node->container) {
-    right = dmnsn_bvst_deepest_recursive(node->container,
+    right = dmnsn_prtree_deepest_recursive(node->container,
                                              depth + 1, deepest);
   }
 
@@ -92,18 +92,18 @@ dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node,
   }
 }
 
-dmnsn_bvst_node *
-dmnsn_bvst_deepest(dmnsn_bvst *tree)
+dmnsn_prtree_node *
+dmnsn_prtree_deepest(dmnsn_prtree *tree)
 {
   unsigned int deepest = 0;
-  return dmnsn_bvst_deepest_recursive(tree->root, 0, &deepest);
+  return dmnsn_prtree_deepest_recursive(tree->root, 0, &deepest);
 }
 
 int
 main()
 {
-  dmnsn_bvst *tree;
-  dmnsn_bvst_node *node;
+  dmnsn_prtree *tree;
+  dmnsn_prtree_node *node;
   dmnsn_intersection intersection;
   dmnsn_line ray;
   const unsigned int nobjects = 128;
@@ -118,7 +118,7 @@ main()
     return EXIT_FAILURE;
   }
 
-  tree = dmnsn_new_bvst();
+  tree = dmnsn_new_prtree();
 
   for (i = 0; i < nobjects; ++i) {
     objects[i] = dmnsn_new_object();
@@ -128,40 +128,40 @@ main()
     objects[i]->intersection_fn = &dmnsn_fake_intersection_fn;
   }
 
-  /* dmnsn_bvst_insert() */
+  /* dmnsn_prtree_insert() */
 
   grains = 0;
   for (i = 0; i < nobjects; ++i) {
     sandglass_bench_noprecache(&sandglass,
-                               dmnsn_bvst_insert(tree, objects[i]));
+                               dmnsn_prtree_insert(tree, objects[i]));
     sandglass.grains += grains;
     grains = sandglass.grains;
   }
-  printf("dmnsn_bvst_insert(): %ld\n", sandglass.grains/nobjects);
+  printf("dmnsn_prtree_insert(): %ld\n", sandglass.grains/nobjects);
 
-  /* dmnsn_bvst_search() */
+  /* dmnsn_prtree_search() */
 
   ray.x0 = dmnsn_new_vector(0.0, 0.0, -2.0);
   ray.n  = dmnsn_new_vector(0.0, 0.0, 1.0);
 
   (*objects[0]->intersection_fn)(objects[0], ray, &intersection);
   sandglass_bench_noprecache(&sandglass, {
-    dmnsn_bvst_search(tree, ray, &intersection);
+    dmnsn_prtree_search(tree, ray, &intersection);
   });
-  printf("dmnsn_bvst_search(): %ld\n", sandglass.grains);
+  printf("dmnsn_prtree_search(): %ld\n", sandglass.grains);
 
-  /* dmnsn_bvst_splay() */
+  /* dmnsn_prtree_splay() */
   grains = 0;
   for (i = 0; i < nobjects; ++i) {
-    node = dmnsn_bvst_deepest(tree);
-    sandglass_bench_noprecache(&sandglass, dmnsn_bvst_splay(tree, node));
+    node = dmnsn_prtree_deepest(tree);
+    sandglass_bench_noprecache(&sandglass, dmnsn_prtree_splay(tree, node));
     sandglass.grains += grains;
     grains = sandglass.grains;
   }
-  printf("dmnsn_bvst_splay(): %ld\n", sandglass.grains/nobjects);
+  printf("dmnsn_prtree_splay(): %ld\n", sandglass.grains/nobjects);
 
   /* Cleanup */
-  dmnsn_delete_bvst(tree);
+  dmnsn_delete_prtree(tree);
   for (i = 0; i < nobjects; ++i) {
     dmnsn_delete_object(objects[i]);
   }
diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 535bd69..b5b0be1 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -49,8 +49,8 @@ lib_LTLIBRARIES = libdimension.la
 
 libdimension_la_SOURCES = $(nobase_include_HEADERS)                            \
                           ambient.c                                            \
-                          bvst.c                                               \
-                          bvst.h                                               \
+                          prtree.c                                               \
+                          prtree.h                                               \
                           camera.c                                             \
                           canvas.c                                             \
                           canvas_pigment.c                                     \
diff --git a/libdimension/bvst.c b/libdimension/bvst.c
deleted file mode 100644
index 7a57c76..0000000
--- a/libdimension/bvst.c
+++ /dev/null
@@ -1,388 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010 Tavian Barnes <tavianator@gmail.com>               *
- *                                                                       *
- * This file is part of The Dimension Library.                           *
- *                                                                       *
- * The Dimension Library is free software; you can redistribute it and/  *
- * or modify it under the terms of the GNU Lesser General Public License *
- * as published by the Free Software Foundation; either version 3 of the *
- * License, or (at your option) any later version.                       *
- *                                                                       *
- * The Dimension Library is distributed in the hope that it will be      *
- * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
- * Lesser General Public License for more details.                       *
- *                                                                       *
- * You should have received a copy of the GNU Lesser General Public      *
- * License along with this program.  If not, see                         *
- * <http://www.gnu.org/licenses/>.                                       *
- *************************************************************************/
-
-#include "dimension_impl.h"
-#include <stdlib.h>
-
-/* Return an empty tree */
-dmnsn_bvst *
-dmnsn_new_bvst()
-{
-  dmnsn_bvst *tree = dmnsn_malloc(sizeof(dmnsn_bvst));
-  tree->root = NULL;
-  return tree;
-}
-
-static dmnsn_bvst_node *
-dmnsn_new_bvst_node()
-{
-  dmnsn_bvst_node *node = dmnsn_malloc(sizeof(dmnsn_bvst_node));
-  return node;
-}
-
-/* Recursively copy the nodes of a BVST */
-static dmnsn_bvst_node *
-dmnsn_bvst_copy_recursive(dmnsn_bvst_node *root)
-{
-  dmnsn_bvst_node *node = dmnsn_new_bvst_node();
-  *node = *root;
-  if (node->contains) {
-    node->contains = dmnsn_bvst_copy_recursive(node->contains);
-    node->contains->parent = node;
-  }
-  if (node->container) {
-    node->container = dmnsn_bvst_copy_recursive(node->container);
-    node->container->parent = node;
-  }
-  return node;
-}
-
-/* Copy a BVST */
-dmnsn_bvst *
-dmnsn_copy_bvst(dmnsn_bvst *tree)
-{
-  dmnsn_bvst *copy = dmnsn_new_bvst();
-  if (tree->root)
-    copy->root = dmnsn_bvst_copy_recursive(tree->root);
-  else
-    copy->root = NULL;
-  return copy;
-}
-
-static void
-dmnsn_delete_bvst_node(dmnsn_bvst_node *node)
-{
-  free(node);
-}
-
-/* Recursively free a BVST */
-static void
-dmnsn_delete_bvst_recursive(dmnsn_bvst_node *node)
-{
-  if (node) {
-    dmnsn_delete_bvst_recursive(node->contains);
-    dmnsn_delete_bvst_recursive(node->container);
-    dmnsn_delete_bvst_node(node);
-  }
-}
-
-/* Free a BVST */
-void
-dmnsn_delete_bvst(dmnsn_bvst *tree)
-{
-  if (tree) {
-    dmnsn_delete_bvst_recursive(tree->root);
-    free(tree);
-  }
-}
-
-/* Expand node to contain the bounding box from min to max */
-static void dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
-                                    dmnsn_bounding_box box);
-
-/* Insert an object into the tree */
-void
-dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
-{
-  dmnsn_object_precompute(object);
-
-  dmnsn_bvst_node *node = dmnsn_new_bvst_node(), *parent = tree->root;
-
-  node->contains     = NULL;
-  node->container    = NULL;
-  node->parent       = NULL;
-  node->object       = object;
-  node->bounding_box = object->bounding_box;
-
-  /* Now insert the node */
-
-  while (parent) {
-    if (dmnsn_bounding_box_contains(parent->bounding_box,
-                                    node->bounding_box.min)
-        && dmnsn_bounding_box_contains(parent->bounding_box,
-                                       node->bounding_box.max))
-    {
-      /* parent fully contains node */
-      if (parent->contains) {
-        parent = parent->contains;
-      } else {
-        /* We found our parent; insert node into the tree */
-        parent->contains = node;
-        node->parent = parent;
-        break;
-      }
-    } else {
-      /* Expand node's bounding box to fully contain parent's if it doesn't
-         already */
-      dmnsn_bvst_node_swallow(node, parent->bounding_box);
-      /* node now fully contains parent */
-      if (parent->container) {
-        parent = parent->container;
-      } else {
-        /* We found our parent; insert node into the tree */
-        parent->container = node;
-        node->parent = parent;
-        break;
-      }
-    }
-  }
-
-  dmnsn_bvst_splay(tree, node);
-}
-
-/* Expand node to contain the bounding box from min to max */
-static void
-dmnsn_bvst_node_swallow(dmnsn_bvst_node *node, dmnsn_bounding_box box)
-{
-  node->bounding_box.min = dmnsn_vector_min(node->bounding_box.min, box.min);
-  node->bounding_box.max = dmnsn_vector_max(node->bounding_box.max, box.max);
-}
-
-/* Tree rotations */
-static void dmnsn_bvst_rotate(dmnsn_bvst_node *node);
-
-/* Splay a node: move it to the root via tree rotations */
-void
-dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node)
-{
-  while (node->parent) {
-    if (!node->parent->parent) {
-      /* Zig step - we are a child of the root node */
-      dmnsn_bvst_rotate(node);
-      break;
-    } else if ((node == node->parent->contains
-                && node->parent == node->parent->parent->contains)
-               || (node == node->parent->container
-                   && node->parent == node->parent->parent->container)) {
-      /* Zig-zig step - we are a child on the same side as our parent */
-      dmnsn_bvst_rotate(node->parent);
-      dmnsn_bvst_rotate(node);
-    } else {
-      /* Zig-zag step - we are a child on a different side than our parent is */
-      dmnsn_bvst_rotate(node);
-      dmnsn_bvst_rotate(node);
-    }
-  }
-  tree->root = node;
-}
-
-/* Rotate a tree on the edge connecting node and node->parent */
-static void
-dmnsn_bvst_rotate(dmnsn_bvst_node *node)
-{
-  dmnsn_bvst_node *P, *Q, *B;
-  if (node == node->parent->contains) {
-    /* We are a left child; perform a right rotation:
-     *
-     *     Q            P
-     *    / \          / \
-     *   P   C  --->  A   Q
-     *  / \              / \
-     * A   B            B   C
-     */
-    Q = node->parent;
-    P = node;
-    /* A = node->contains; */
-    B = node->container;
-    /* C = node->parent->container; */
-
-    /* First fix up the parents */
-    if (Q->parent) {
-      if (Q->parent->contains == Q)
-        Q->parent->contains = P;
-      else
-        Q->parent->container = P;
-    }
-    P->parent = Q->parent;
-    Q->parent = P;
-    if (B) B->parent = Q;
-
-    /* Then the children */
-    P->container = Q;
-    Q->contains  = B;
-  } else {
-    /* We are a right child; perform a left rotation:
-     *
-     *    P                Q
-     *   / \              / \
-     *  A   Q    --->    P   C
-     *     / \          / \
-     *    B   C        A   B
-     */
-    P = node->parent;
-    Q = node;
-    /* A = node->parent->contains; */
-    B = node->contains;
-    /* C = node->container; */
-
-    /* First fix up the parents */
-    if (P->parent) {
-      if (P->parent->contains == P)
-        P->parent->contains = Q;
-      else
-        P->parent->container = Q;
-    }
-    Q->parent = P->parent;
-    P->parent = Q;
-    if (B) B->parent = P;
-
-    /* Then the children */
-    Q->contains  = P;
-    P->container = B;
-  }
-}
-
-typedef struct {
-  dmnsn_bvst_node *node;
-  bool intersected;
-  dmnsn_intersection intersection;
-} dmnsn_bvst_search_result;
-
-static dmnsn_bvst_search_result
-dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t);
-
-bool
-dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray,
-                  dmnsn_intersection *intersection)
-{
-  dmnsn_bvst_search_result result
-    = dmnsn_bvst_search_recursive(tree->root, ray, -1.0);
-
-  if (result.intersected) {
-    dmnsn_bvst_splay(tree, result.node);
-    *intersection = result.intersection;
-  }
-
-  return result.intersected;
-}
-
-static bool dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_bounding_box box,
-                                       double t);
-
-static dmnsn_bvst_search_result
-dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
-{
-  dmnsn_bvst_search_result result_temp, result = {
-    .node = NULL,
-    .intersected = false
-  };
-
-  if (!node)
-    return result;
-
-  /* Go down the right subtree first because the closest object is more likely
-     to lie in the larger bounding boxes */
-  result_temp = dmnsn_bvst_search_recursive(node->container, ray, t);
-  if (result_temp.node && (t < 0.0 || result_temp.intersection.t < t)) {
-    result = result_temp;
-    t = result.intersection.t;
-  }
-
-  if (dmnsn_bounding_box_contains(node->bounding_box, ray.x0)
-      || dmnsn_ray_box_intersection(ray, node->bounding_box, t))
-  {
-    if (dmnsn_bounding_box_contains(node->object->bounding_box, ray.x0)
-        || dmnsn_ray_box_intersection(ray, node->object->bounding_box, t))
-    {
-      result_temp.intersected =
-        (*node->object->intersection_fn)(node->object, ray,
-                                         &result_temp.intersection);
-
-      if (result_temp.intersected
-          && (t < 0.0 || result_temp.intersection.t < t)) {
-        result.node = node;
-        result.intersected = true;
-        result.intersection = result_temp.intersection;
-        t = result.intersection.t;
-      }
-    }
-
-    /* Go down the left subtree */
-    result_temp = dmnsn_bvst_search_recursive(node->contains, ray, t);
-    if (result_temp.node && (t < 0.0 || result_temp.intersection.t < t)) {
-      result = result_temp;
-    }
-  }
-
-  return result;
-}
-
-static bool
-dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
-{
-  double t_temp;
-  dmnsn_vector p;
-
-  if (line.n.x != 0.0) {
-    /* x == box.min.x */
-    t_temp = (box.min.x - line.x0.x)/line.n.x;
-    p = dmnsn_line_point(line, t_temp);
-    if (p.y >= box.min.y && p.y <= box.max.y
-        && p.z >= box.min.z && p.z <= box.max.z
-        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return true;
-
-    /* x == box.max.x */
-    t_temp = (box.max.x - line.x0.x)/line.n.x;
-    p = dmnsn_line_point(line, t_temp);
-    if (p.y >= box.min.y && p.y <= box.max.y
-        && p.z >= box.min.z && p.z <= box.max.z
-        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return true;
-  }
-
-  if (line.n.y != 0.0) {
-    /* y == box.min.y */
-    t_temp = (box.min.y - line.x0.y)/line.n.y;
-    p = dmnsn_line_point(line, t_temp);
-    if (p.x >= box.min.x && p.x <= box.max.x
-        && p.z >= box.min.z && p.z <= box.max.z
-        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return true;
-
-    /* y == box.max.y */
-    t_temp = (box.max.y - line.x0.y)/line.n.y;
-    p = dmnsn_line_point(line, t_temp);
-    if (p.x >= box.min.x && p.x <= box.max.x
-        && p.z >= box.min.z && p.z <= box.max.z
-        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return true;
-  }
-
-  if (line.n.z != 0.0) {
-    /* z == box.min.z */
-    t_temp = (box.min.z - line.x0.z)/line.n.z;
-    p = dmnsn_line_point(line, t_temp);
-    if (p.x >= box.min.x && p.x <= box.max.x
-        && p.y >= box.min.y && p.y <= box.max.y
-        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return true;
-
-    /* z == box.max.z */
-    t_temp = (box.max.z - line.x0.z)/line.n.z;
-    p = dmnsn_line_point(line, t_temp);
-    if (p.x >= box.min.x && p.x <= box.max.x
-        && p.y >= box.min.y && p.y <= box.max.y
-        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
-      return true;
-  }
-
-  return false;
-}
diff --git a/libdimension/dimension_impl.h b/libdimension/dimension_impl.h
index 9fa2ef6..3c3283c 100644
--- a/libdimension/dimension_impl.h
+++ b/libdimension/dimension_impl.h
@@ -22,6 +22,6 @@
 #define DIMENSION_IMPL_H
 
 #include "dimension.h"
-#include "bvst.h"
+#include "prtree.h"
 
 #endif /* DIMENSION_IMPL_H */
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
new file mode 100644
index 0000000..a40100c
--- /dev/null
+++ b/libdimension/prtree.c
@@ -0,0 +1,574 @@
+/*************************************************************************
+ * Copyright (C) 2010 Tavian Barnes <tavianator@gmail.com>               *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+#include "dimension_impl.h"
+#include <stdlib.h>
+
+typedef struct dmnsn_pseudo_prtree dmnsn_pseudo_prtree;
+
+typedef struct dmnsn_pseudo_prleaf {
+  void *children[DMNSN_PRTREE_B];
+  bool is_leaf;
+  dmnsn_bounding_box bounding_box;
+} dmnsn_pseudo_prleaf;
+
+typedef struct dmnsn_pseudo_prnode {
+  dmnsn_pseudo_prtree *left, *right;
+  dmnsn_pseudo_prleaf children[6];
+} dmnsn_pseudo_prnode;
+
+struct dmnsn_pseudo_prtree {
+  bool is_leaf;
+  union {
+    dmnsn_pseudo_prleaf leaf;
+    dmnsn_pseudo_prnode node;
+  };
+};
+
+/* Expand node to contain the bounding box from min to max */
+static void
+dmnsn_pseudo_prleaf_swallow(dmnsn_pseudo_prleaf *leaf, dmnsn_bounding_box box)
+{
+  leaf->bounding_box.min = dmnsn_vector_min(leaf->bounding_box.min, box.min);
+  leaf->bounding_box.max = dmnsn_vector_max(leaf->bounding_box.max, box.max);
+}
+
+/* Comparator types */
+enum {
+  DMNSN_XMIN,
+  DMNSN_YMIN,
+  DMNSN_ZMIN,
+  DMNSN_XMAX,
+  DMNSN_YMAX,
+  DMNSN_ZMAX
+};
+
+static double
+dmnsn_priority_get(dmnsn_list_iterator *i, bool is_object, int comparator)
+{
+  dmnsn_bounding_box box;
+
+  if (is_object) {
+    dmnsn_object *object;
+    dmnsn_list_get(i, &object);
+    box = object->bounding_box;
+  } else {
+    dmnsn_prtree *prnode;
+    dmnsn_list_get(i, &prnode);
+    box = prnode->bounding_box;
+  }
+
+  switch (comparator) {
+  case DMNSN_XMIN:
+    return box.min.x;
+  case DMNSN_YMIN:
+    return box.min.y;
+  case DMNSN_ZMIN:
+    return box.min.z;
+
+  case DMNSN_XMAX:
+    return -box.max.x;
+  case DMNSN_YMAX:
+    return -box.max.y;
+  case DMNSN_ZMAX:
+    return -box.max.z;
+
+  default:
+    dmnsn_assert(false, "Invalid comparator.");
+    return 0.0;
+  }
+}
+
+/* List sorting comparators */
+
+static bool
+dmnsn_xmin_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, true, DMNSN_XMIN);
+  double rval = dmnsn_priority_get(r, true, DMNSN_XMIN);
+  return lval < rval;
+}
+
+static bool
+dmnsn_xmin_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, false, DMNSN_XMIN);
+  double rval = dmnsn_priority_get(r, false, DMNSN_XMIN);
+  return lval < rval;
+}
+
+static bool
+dmnsn_ymin_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, true, DMNSN_YMIN);
+  double rval = dmnsn_priority_get(r, true, DMNSN_YMIN);
+  return lval < rval;
+}
+
+static bool
+dmnsn_ymin_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, false, DMNSN_YMIN);
+  double rval = dmnsn_priority_get(r, false, DMNSN_YMIN);
+  return lval < rval;
+}
+
+static bool
+dmnsn_zmin_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, true, DMNSN_ZMIN);
+  double rval = dmnsn_priority_get(r, true, DMNSN_ZMIN);
+  return lval < rval;
+}
+
+static bool
+dmnsn_zmin_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, false, DMNSN_ZMIN);
+  double rval = dmnsn_priority_get(r, false, DMNSN_ZMIN);
+  return lval < rval;
+}
+
+static bool
+dmnsn_xmax_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, true, DMNSN_XMAX);
+  double rval = dmnsn_priority_get(r, true, DMNSN_XMAX);
+  return lval < rval;
+}
+
+static bool
+dmnsn_xmax_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, false, DMNSN_XMAX);
+  double rval = dmnsn_priority_get(r, false, DMNSN_XMAX);
+  return lval < rval;
+}
+
+static bool
+dmnsn_ymax_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, true, DMNSN_YMAX);
+  double rval = dmnsn_priority_get(r, true, DMNSN_YMAX);
+  return lval < rval;
+}
+
+static bool
+dmnsn_ymax_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, false, DMNSN_YMAX);
+  double rval = dmnsn_priority_get(r, false, DMNSN_YMAX);
+  return lval < rval;
+}
+
+static bool
+dmnsn_zmax_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, true, DMNSN_ZMAX);
+  double rval = dmnsn_priority_get(r, true, DMNSN_ZMAX);
+  return lval < rval;
+}
+
+static bool
+dmnsn_zmax_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+  double lval = dmnsn_priority_get(l, false, DMNSN_ZMAX);
+  double rval = dmnsn_priority_get(r, false, DMNSN_ZMAX);
+  return lval < rval;
+}
+
+static dmnsn_comparator_fn *dmnsn_object_comparators[6] = {
+  [DMNSN_XMIN] = &dmnsn_xmin_object_comp,
+  [DMNSN_YMIN] = &dmnsn_ymin_object_comp,
+  [DMNSN_ZMIN] = &dmnsn_zmin_object_comp,
+  [DMNSN_XMAX] = &dmnsn_xmax_object_comp,
+  [DMNSN_YMAX] = &dmnsn_ymax_object_comp,
+  [DMNSN_ZMAX] = &dmnsn_zmax_object_comp
+};
+
+static dmnsn_comparator_fn *dmnsn_prnode_comparators[6] = {
+  [DMNSN_XMIN] = &dmnsn_xmin_prnode_comp,
+  [DMNSN_YMIN] = &dmnsn_ymin_prnode_comp,
+  [DMNSN_ZMIN] = &dmnsn_zmin_prnode_comp,
+  [DMNSN_XMAX] = &dmnsn_xmax_prnode_comp,
+  [DMNSN_YMAX] = &dmnsn_ymax_prnode_comp,
+  [DMNSN_ZMAX] = &dmnsn_zmax_prnode_comp
+};
+
+static dmnsn_list_iterator *
+dmnsn_priority_search(dmnsn_list *leaves, bool are_objects, int comparator)
+{
+  dmnsn_list_iterator *i = dmnsn_list_first(leaves);
+  if (i) {
+    double candidate = dmnsn_priority_get(i, are_objects, comparator);
+
+    dmnsn_list_iterator *j;
+    for (j = dmnsn_list_next(i); j != NULL; j = dmnsn_list_next(j)) {
+      double new_candidate = dmnsn_priority_get(j, are_objects, comparator);
+      if (new_candidate < candidate) {
+        candidate = new_candidate;
+        i = j;
+      }
+    }
+  }
+
+  return i;
+}
+
+/* Build a pseudo PR-tree */
+static dmnsn_pseudo_prtree *
+dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator)
+{
+  dmnsn_pseudo_prtree *pseudo = dmnsn_malloc(sizeof(dmnsn_pseudo_prtree));
+
+  if (dmnsn_list_size(leaves) <= DMNSN_PRTREE_B) {
+    /* Make a leaf */
+    pseudo->is_leaf = true;
+    pseudo->leaf.bounding_box.min = dmnsn_zero;
+    pseudo->leaf.bounding_box.max = dmnsn_zero;
+
+    size_t i;
+    dmnsn_list_iterator *ii;
+    if (are_objects) {
+      pseudo->leaf.is_leaf = true;
+      for (i = 0, ii = dmnsn_list_first(leaves);
+           ii != NULL;
+           ++i, ii = dmnsn_list_next(ii))
+      {
+        dmnsn_object *object;
+        dmnsn_list_get(ii, &object);
+
+        pseudo->leaf.children[i] = object;
+        if (i == 0) {
+          pseudo->leaf.bounding_box = object->bounding_box;
+        } else {
+          dmnsn_pseudo_prleaf_swallow(&pseudo->leaf, object->bounding_box);
+        }
+      }
+    } else {
+      pseudo->leaf.is_leaf = false;
+      for (i = 0, ii = dmnsn_list_first(leaves);
+           ii != NULL;
+           ++i, ii = dmnsn_list_next(ii))
+      {
+        dmnsn_prtree *prnode;
+        dmnsn_list_get(ii, &prnode);
+
+        pseudo->leaf.children[i] = prnode;
+        if (i == 0) {
+          pseudo->leaf.bounding_box = prnode->bounding_box;
+        } else {
+          dmnsn_pseudo_prleaf_swallow(&pseudo->leaf, prnode->bounding_box);
+        }
+      }
+    }
+
+    for (; i < DMNSN_PRTREE_B; ++i) {
+      pseudo->leaf.children[i] = NULL;
+    }
+  } else {
+    /* Make an internal node */
+    pseudo->is_leaf = false;
+    size_t i;
+    for (i = 0; i < 6; ++i) {
+      pseudo->node.children[i].is_leaf = are_objects;
+    }
+
+    /* Fill the priority leaves */
+    size_t j;
+    for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+      for (j = 0; j < 6; ++j) {
+        dmnsn_list_iterator *k = dmnsn_priority_search(leaves, are_objects, j);
+        if (!k)
+          break;
+
+        if (are_objects) {
+          dmnsn_object *object;
+          dmnsn_list_get(k, &object);
+          pseudo->node.children[j].children[i] = object;
+          if (i == 0) {
+            pseudo->node.children[j].bounding_box = object->bounding_box;
+          } else {
+            dmnsn_pseudo_prleaf_swallow(&pseudo->node.children[j],
+                                        object->bounding_box);
+          }
+        } else {
+          dmnsn_prtree *prnode;
+          dmnsn_list_get(k, &prnode);
+          pseudo->node.children[j].children[i] = prnode;
+          if (i == 0) {
+            pseudo->node.children[j].bounding_box = prnode->bounding_box;
+          } else {
+            dmnsn_pseudo_prleaf_swallow(&pseudo->node.children[j],
+                                        prnode->bounding_box);
+          }
+        }
+
+        dmnsn_list_remove(leaves, k);
+      }
+
+      if (dmnsn_list_size(leaves) == 0)
+        break;
+    }
+
+    /* Set remaining space in the priority leaves to NULL */
+    for (; i < DMNSN_PRTREE_B; ++i) {
+      for (; j < 6; ++j) {
+        if (i == 0) {
+          pseudo->node.children[j].bounding_box.min = dmnsn_zero;
+          pseudo->node.children[j].bounding_box.max = dmnsn_zero;
+        }
+        pseudo->node.children[j].children[i] = NULL;
+      }
+      j = 0;
+    }
+
+    /* Recursively build the subtrees */
+    if (are_objects)
+      dmnsn_list_sort(leaves, dmnsn_object_comparators[comparator]);
+    else
+      dmnsn_list_sort(leaves, dmnsn_prnode_comparators[comparator]);
+
+    dmnsn_list *half = dmnsn_list_split(leaves);
+    pseudo->node.left
+      = dmnsn_new_pseudo_prtree(leaves, are_objects, (comparator + 1)%6);
+    pseudo->node.right
+      = dmnsn_new_pseudo_prtree(half, are_objects, (comparator + 1)%6);
+    dmnsn_delete_list(half);
+  }
+
+  return pseudo;
+}
+
+static void
+dmnsn_delete_pseudo_prtree(dmnsn_pseudo_prtree *pseudo)
+{
+  if (pseudo) {
+    if (!pseudo->is_leaf) {
+      dmnsn_delete_pseudo_prtree(pseudo->node.left);
+      dmnsn_delete_pseudo_prtree(pseudo->node.right);
+    }
+    free(pseudo);
+  }
+}
+
+/* Construct a node from a pseudo leaf */
+static dmnsn_prtree *
+dmnsn_new_prtree_node(const dmnsn_pseudo_prleaf *leaf)
+{
+  dmnsn_prtree *node = dmnsn_malloc(sizeof(dmnsn_prtree));
+  node->is_leaf      = leaf->is_leaf;
+  node->bounding_box = leaf->bounding_box;
+
+  size_t i;
+  for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+    node->children[i] = leaf->children[i];
+  }
+
+  return node;
+}
+
+static void
+dmnsn_pseudo_prtree_add_leaf(const dmnsn_pseudo_prleaf *leaf,
+                             dmnsn_list *leaves)
+{
+  /* Don't add empty leaves */
+  if (leaf->children[0]) {
+    dmnsn_prtree *prnode = dmnsn_new_prtree_node(leaf);
+    dmnsn_list_push(leaves, &prnode);
+  }
+}
+
+static void
+dmnsn_pseudo_prtree_leaves_recursive(const dmnsn_pseudo_prtree *node,
+                                     dmnsn_list *leaves)
+{
+  if (node->is_leaf) {
+    dmnsn_pseudo_prtree_add_leaf(&node->leaf, leaves);
+  } else {
+    size_t i;
+    for (i = 0; i < 6; ++i) {
+      dmnsn_pseudo_prtree_add_leaf(&node->node.children[i], leaves);
+    }
+    dmnsn_pseudo_prtree_leaves_recursive(node->node.left, leaves);
+    dmnsn_pseudo_prtree_leaves_recursive(node->node.right, leaves);
+  }
+}
+
+/* Extract the leaves of a pseudo PR-tree */
+static dmnsn_list *
+dmnsn_pseudo_prtree_leaves(const dmnsn_pseudo_prtree *pseudo)
+{
+  dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prtree *));
+  dmnsn_pseudo_prtree_leaves_recursive(pseudo, leaves);
+  return leaves;
+}
+
+/* Construct a PR-tree from a bulk of objects */
+dmnsn_prtree *
+dmnsn_new_prtree(const dmnsn_array *objects)
+{
+  size_t i;
+  for (i = 0; i < dmnsn_array_size(objects); ++i) {
+    dmnsn_object *object;
+    dmnsn_array_get(objects, i, &object);
+    dmnsn_object_precompute(object);
+  }
+
+  dmnsn_list *leaves = dmnsn_list_from_array(objects);
+  dmnsn_pseudo_prtree *pseudo = dmnsn_new_pseudo_prtree(leaves, true, 0);
+  dmnsn_delete_list(leaves);
+  leaves = dmnsn_pseudo_prtree_leaves(pseudo);
+  dmnsn_delete_pseudo_prtree(pseudo);
+
+  while (dmnsn_list_size(leaves) > 1) {
+    pseudo = dmnsn_new_pseudo_prtree(leaves, false, 0);
+    dmnsn_delete_list(leaves);
+    leaves = dmnsn_pseudo_prtree_leaves(pseudo);
+    dmnsn_delete_pseudo_prtree(pseudo);
+  }
+
+  dmnsn_prtree *root;
+  dmnsn_list_get(dmnsn_list_first(leaves), &root);
+  dmnsn_delete_list(leaves);
+  return root;
+}
+
+/* Free a PR-tree */
+void
+dmnsn_delete_prtree(dmnsn_prtree *tree)
+{
+  if (tree) {
+    if (!tree->is_leaf) {
+      size_t i;
+      for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+        dmnsn_delete_prtree(tree->children[i]);
+      }
+    }
+    free(tree);
+  }
+}
+
+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, dmnsn_line ray,
+                              dmnsn_intersection *intersection, double *t)
+{
+  if (dmnsn_ray_box_intersection(ray, node->bounding_box, *t)) {
+    size_t i;
+    for (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;
+  dmnsn_prtree_search_recursive(tree, ray, intersection, &t);
+  return t >= 0.0;
+}
+
+static bool
+dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
+{
+  if (dmnsn_bounding_box_contains(box, line.x0))
+    return true;
+
+  double t_temp;
+  dmnsn_vector p;
+
+  if (line.n.x != 0.0) {
+    /* x == box.min.x */
+    t_temp = (box.min.x - line.x0.x)/line.n.x;
+    p = dmnsn_line_point(line, t_temp);
+    if (p.y >= box.min.y && p.y <= box.max.y
+        && p.z >= box.min.z && p.z <= box.max.z
+        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+      return true;
+
+    /* x == box.max.x */
+    t_temp = (box.max.x - line.x0.x)/line.n.x;
+    p = dmnsn_line_point(line, t_temp);
+    if (p.y >= box.min.y && p.y <= box.max.y
+        && p.z >= box.min.z && p.z <= box.max.z
+        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+      return true;
+  }
+
+  if (line.n.y != 0.0) {
+    /* y == box.min.y */
+    t_temp = (box.min.y - line.x0.y)/line.n.y;
+    p = dmnsn_line_point(line, t_temp);
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.z >= box.min.z && p.z <= box.max.z
+        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+      return true;
+
+    /* y == box.max.y */
+    t_temp = (box.max.y - line.x0.y)/line.n.y;
+    p = dmnsn_line_point(line, t_temp);
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.z >= box.min.z && p.z <= box.max.z
+        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+      return true;
+  }
+
+  if (line.n.z != 0.0) {
+    /* z == box.min.z */
+    t_temp = (box.min.z - line.x0.z)/line.n.z;
+    p = dmnsn_line_point(line, t_temp);
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.y >= box.min.y && p.y <= box.max.y
+        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+      return true;
+
+    /* z == box.max.z */
+    t_temp = (box.max.z - line.x0.z)/line.n.z;
+    p = dmnsn_line_point(line, t_temp);
+    if (p.x >= box.min.x && p.x <= box.max.x
+        && p.y >= box.min.y && p.y <= box.max.y
+        && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+      return true;
+  }
+
+  return false;
+}
diff --git a/libdimension/bvst.h b/libdimension/prtree.h
index d300cf9..999bc14 100644
--- a/libdimension/bvst.h
+++ b/libdimension/prtree.h
@@ -19,48 +19,33 @@
  *************************************************************************/
 
 /*
- * Bounding Volume Splay Trees for storing object bounding boxes.
- * Each node's bounding box entirely contains the bounding boxes of the nodes
- * to its left, and is entirely contained by the bounding boxes of the nodes to
- * its right.  Splay trees are used for the implementation, to bring commonly-
- * used objects (the most recent object which a ray has hit) near the root of
- * the tree for fast access.  Object's bounding boxes are expanded as needed
- * when inserted into the tree: if they intersect an existing bounding box, they
- * are expanded to contain it.
+ * Priority R-Trees for storing bounding box hierarchies.  PR-trees are a data
+ * structure introduced by Arge, de Berg, Haverkort, and Yi, which provides
+ * asymptotically optimal worst-case lookup, while remaining efficient with real-world
+ * data.  Their structure is derived from B-trees.
  */
 
-#ifndef DIMENSION_IMPL_BVST_H
-#define DIMENSION_IMPL_BVST_H
+#ifndef DIMENSION_IMPL_PRTREE_H
+#define DIMENSION_IMPL_PRTREE_H
 
-typedef struct dmnsn_bvst dmnsn_bvst;
-typedef struct dmnsn_bvst_node dmnsn_bvst_node;
+#include <stdbool.h>
 
-struct dmnsn_bvst {
-  dmnsn_bvst_node *root;
-};
+/* Number of children per node */
+#define DMNSN_PRTREE_B 6
 
-struct dmnsn_bvst_node {
-  /* Tree children */
-  dmnsn_bvst_node *contains, *container;
-
-  /* Parent node for easy backtracking */
-  dmnsn_bvst_node *parent;
+typedef struct dmnsn_prtree {
+  /* Children (objects or subtrees) */
+  void *children[DMNSN_PRTREE_B];
+  bool is_leaf;
 
   /* Bounding box */
   dmnsn_bounding_box bounding_box;
+} dmnsn_prtree;
 
-  /* Node payload */
-  dmnsn_object *object;
-};
-
-dmnsn_bvst *dmnsn_new_bvst();
-dmnsn_bvst *dmnsn_copy_bvst(dmnsn_bvst *tree);
-void dmnsn_delete_bvst(dmnsn_bvst *tree);
-
-void dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object);
-void dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node);
+dmnsn_prtree *dmnsn_new_prtree(const dmnsn_array *objects);
+void dmnsn_delete_prtree(dmnsn_prtree *tree);
 
-bool dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray,
-                       dmnsn_intersection *intersection);
+bool dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
+                         dmnsn_intersection *intersection);
 
-#endif /* DIMENSION_IMPL_BVST_H */
+#endif /* DIMENSION_IMPL_PRTREE_H */
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index eb2f052..8946303 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -30,7 +30,7 @@
 typedef struct {
   dmnsn_progress *progress;
   dmnsn_scene *scene;
-  dmnsn_bvst *bvst;
+  dmnsn_prtree *prtree;
 
   /* For multithreading */
   unsigned int index, threads;
@@ -57,14 +57,6 @@ dmnsn_raytrace_scene_async(dmnsn_scene *scene)
     = dmnsn_malloc(sizeof(dmnsn_raytrace_payload));
   payload->progress = progress;
   payload->scene    = scene;
-  payload->bvst     = dmnsn_new_bvst();
-
-  unsigned int i;
-  for (i = 0; i < dmnsn_array_size(payload->scene->objects); ++i) {
-    dmnsn_object *object;
-    dmnsn_array_get(payload->scene->objects, i, &object);
-    dmnsn_bvst_insert(payload->bvst, object);
-  }
 
   if (pthread_create(&progress->thread, NULL, &dmnsn_raytrace_scene_thread,
                      payload) != 0)
@@ -83,7 +75,9 @@ static void *
 dmnsn_raytrace_scene_thread(void *ptr)
 {
   dmnsn_raytrace_payload *payload = ptr;
+  payload->prtree = dmnsn_new_prtree(payload->scene->objects);
   dmnsn_raytrace_scene_multithread(payload);
+  dmnsn_delete_prtree(payload->prtree);
   dmnsn_done_progress(payload->progress);
   free(payload);
 
@@ -120,9 +114,6 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
     payloads[i] = *payload;
     payloads[i].index = i;
     payloads[i].threads = nthreads;
-    if (i > 0) {
-      payloads[i].bvst = dmnsn_copy_bvst(payloads[0].bvst);
-    }
   }
 
   /* Create the threads */
@@ -140,8 +131,6 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
     if (pthread_join(threads[i], NULL)) {
       dmnsn_error(DMNSN_SEVERITY_MEDIUM,
                   "Couldn't join worker thread in raytrace engine.");
-    } else {
-      dmnsn_delete_bvst(payloads[i].bvst);
     }
   }
 
@@ -152,7 +141,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
 /* Actual raytracing implementation */
 static void dmnsn_raytrace_scene_impl(dmnsn_progress *progress,
                                       dmnsn_scene *scene,
-                                      dmnsn_bvst *bvst,
+                                      dmnsn_prtree *prtree,
                                       unsigned int index, unsigned int threads);
 
 /* Multi-threading thread callback */
@@ -161,7 +150,7 @@ dmnsn_raytrace_scene_multithread_thread(void *ptr)
 {
   dmnsn_raytrace_payload *payload = ptr;
   dmnsn_raytrace_scene_impl(payload->progress, payload->scene,
-                            payload->bvst, payload->index, payload->threads);
+                            payload->prtree, payload->index, payload->threads);
   return NULL;
 }
 
@@ -174,7 +163,7 @@ typedef struct dmnsn_raytrace_state {
 
   const dmnsn_scene *scene;
   const dmnsn_intersection *intersection;
-  dmnsn_bvst *bvst;
+  dmnsn_prtree *prtree;
   unsigned int reclevel;
 
   dmnsn_vector r;
@@ -195,13 +184,13 @@ static dmnsn_color dmnsn_raytrace_shoot(dmnsn_raytrace_state *state,
 /* Actually raytrace a scene */
 static void
 dmnsn_raytrace_scene_impl(dmnsn_progress *progress, dmnsn_scene *scene,
-                          dmnsn_bvst *bvst,
+                          dmnsn_prtree *prtree,
                           unsigned int index, unsigned int threads)
 {
   dmnsn_raytrace_state state = {
     .parent = NULL,
     .scene  = scene,
-    .bvst   = bvst,
+    .prtree   = prtree,
     .ior    = 1.0
   };
 
@@ -289,7 +278,7 @@ dmnsn_raytrace_light_ray(const dmnsn_raytrace_state *state,
   while (reclevel) {
     dmnsn_intersection shadow_caster;
     bool shadow_casted
-      = dmnsn_bvst_search(state->bvst, shadow_ray, &shadow_caster);
+      = dmnsn_prtree_search(state->prtree, shadow_ray, &shadow_caster);
 
     if (!shadow_casted || shadow_caster.t > 1.0) {
       break;
@@ -450,7 +439,7 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
   --state->reclevel;
 
   dmnsn_intersection intersection;
-  bool intersected = dmnsn_bvst_search(state->bvst, ray, &intersection);
+  bool intersected = dmnsn_prtree_search(state->prtree, ray, &intersection);
 
   dmnsn_color color = state->scene->background;
   if (intersected) {
diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am
index 6fc3dc7..f59848e 100644
--- a/tests/libdimension/Makefile.am
+++ b/tests/libdimension/Makefile.am
@@ -22,7 +22,7 @@ INCLUDES = -I$(top_srcdir)/libdimension
 check_LTLIBRARIES = libdimension-tests.la
 check_PROGRAMS    = error-test                                                 \
                     warning-test                                               \
-                    bvst-test                                                  \
+                    prtree-test                                                  \
                     png-test                                                   \
                     gl-test                                                    \
                     cxx-test
@@ -56,8 +56,8 @@ error_test_LDADD   = libdimension-tests.la
 warning_test_SOURCES = warning.c
 warning_test_LDADD   = libdimension-tests.la
 
-bvst_test_SOURCES = bvst.c
-bvst_test_LDADD   = libdimension-tests.la
+prtree_test_SOURCES = prtree.c
+prtree_test_LDADD   = libdimension-tests.la
 
 png_test_SOURCES = png.c
 png_test_LDADD   = libdimension-tests.la
diff --git a/tests/libdimension/bvst.c b/tests/libdimension/prtree.c
index 33c737b..c75d8da 100644
--- a/tests/libdimension/bvst.c
+++ b/tests/libdimension/prtree.c
@@ -18,7 +18,7 @@
  *************************************************************************/
 
 /*
- * Basic tests of our Bounding Volume Splay Tree framework
+ * Basic tests of PR-trees
  */
 
 #include "../../libdimension/dimension_impl.h"
@@ -27,46 +27,5 @@
 int
 main()
 {
-  dmnsn_bvst *tree;
-  dmnsn_object *obj1, *obj2, *obj3;
-
-  obj1 = dmnsn_new_object();
-  obj2 = dmnsn_new_object();
-  obj3 = dmnsn_new_object();
-
-  obj1->bounding_box.min = dmnsn_new_vector(0.0, 0.0, 0.0);
-  obj1->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
-
-  obj2->bounding_box.min = dmnsn_new_vector(-2.0, -2.0, -2.0);
-  obj2->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
-
-  obj3->bounding_box.min = dmnsn_new_vector(-1.0, -1.0, -1.0);
-  obj3->bounding_box.max = dmnsn_new_vector(0.0, 0.0, 0.0);
-
-  tree = dmnsn_new_bvst();
-
-  dmnsn_bvst_insert(tree, obj1);
-  if (tree->root->object != obj1) {
-    fprintf(stderr, "Wrong BVST built.\n");
-    return EXIT_FAILURE;
-  }
-
-  dmnsn_bvst_insert(tree, obj2);
-  if (tree->root->object != obj2 || tree->root->contains->object != obj1) {
-    fprintf(stderr, "Wrong BVST built.\n");
-    return EXIT_FAILURE;
-  }
-
-  dmnsn_bvst_insert(tree, obj3);
-  if (tree->root->object != obj3 || tree->root->contains->object != obj1
-      || tree->root->container->object != obj2) {
-    fprintf(stderr, "Wrong BVST built.\n");
-    return EXIT_FAILURE;
-  }
-
-  dmnsn_delete_bvst(tree);
-  dmnsn_delete_object(obj3);
-  dmnsn_delete_object(obj2);
-  dmnsn_delete_object(obj1);
   return EXIT_SUCCESS;
 }