Rename kD splay trees to Bounding Volume Splay Trees.

9 files changed, 138 insertions, 144 deletions

diff --git a/bench/libdimension/Makefile.am b/bench/libdimension/Makefile.am
index 8b124bc..2e23fde 100644
--- a/bench/libdimension/Makefile.am
+++ b/bench/libdimension/Makefile.am
@@ -19,7 +19,7 @@
 
 INCLUDES = -I$(top_srcdir)/libdimension
 
-EXTRA_PROGRAMS = bench-array bench-geometry bench-kD_splay_tree
+EXTRA_PROGRAMS = bench-array bench-geometry bench-bvst
 
 bench_array_SOURCES = array.c
 bench_array_LDADD   = -lsandglass $(top_builddir)/libdimension/libdimension.la
@@ -27,12 +27,12 @@ bench_array_LDADD   = -lsandglass $(top_builddir)/libdimension/libdimension.la
 bench_geometry_SOURCES = geometry.c
 bench_geometry_LDADD   = -lsandglass $(top_builddir)/libdimension/libdimension.la
 
-bench_kD_splay_tree_SOURCES = kD_splay_tree.c
-bench_kD_splay_tree_LDADD   = -lsandglass $(top_builddir)/libdimension/libdimension.la
+bench_bvst_SOURCES = bvst.c
+bench_bvst_LDADD   = -lsandglass $(top_builddir)/libdimension/libdimension.la
 
-bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-kD_splay_tree$(EXEEXT)
+bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-bvst$(EXEEXT)
 	./bench-array$(EXEEXT)
 	./bench-geometry$(EXEEXT)
-	./bench-kD_splay_tree$(EXEEXT)
+	./bench-bvst$(EXEEXT)
 
 .PHONY: bench
diff --git a/bench/libdimension/kD_splay_tree.c b/bench/libdimension/bvst.c
index fffab69..3d363ca 100644
--- a/bench/libdimension/kD_splay_tree.c
+++ b/bench/libdimension/bvst.c
@@ -66,17 +66,17 @@ dmnsn_randomize_bounding_box(dmnsn_object *object)
   }
 }
 
-dmnsn_kD_splay_node *
-dmnsn_kD_splay_deepest_recursive(dmnsn_kD_splay_node *node,
+dmnsn_bvst_node *
+dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node,
                                  unsigned int depth, unsigned int *deepest)
 {
-  dmnsn_kD_splay_node *left = NULL, *right = NULL;
+  dmnsn_bvst_node *left = NULL, *right = NULL;
 
   if (node->contains) {
-    left = dmnsn_kD_splay_deepest_recursive(node->contains, depth + 1, deepest);
+    left = dmnsn_bvst_deepest_recursive(node->contains, depth + 1, deepest);
   }
   if (node->container) {
-    right = dmnsn_kD_splay_deepest_recursive(node->container,
+    right = dmnsn_bvst_deepest_recursive(node->container,
                                              depth + 1, deepest);
   }
 
@@ -92,18 +92,18 @@ dmnsn_kD_splay_deepest_recursive(dmnsn_kD_splay_node *node,
   }
 }
 
-dmnsn_kD_splay_node *
-dmnsn_kD_splay_deepest(dmnsn_kD_splay_tree *tree)
+dmnsn_bvst_node *
+dmnsn_bvst_deepest(dmnsn_bvst *tree)
 {
   unsigned int deepest = 0;
-  return dmnsn_kD_splay_deepest_recursive(tree->root, 0, &deepest);
+  return dmnsn_bvst_deepest_recursive(tree->root, 0, &deepest);
 }
 
 int
 main()
 {
-  dmnsn_kD_splay_tree *tree;
-  dmnsn_kD_splay_node *node;
+  dmnsn_bvst *tree;
+  dmnsn_bvst_node *node;
   dmnsn_intersection *intersection;
   dmnsn_line ray;
   const unsigned int nobjects = 128;
@@ -119,7 +119,7 @@ main()
     return EXIT_FAILURE;
   }
 
-  tree = dmnsn_new_kD_splay_tree();
+  tree = dmnsn_new_bvst();
 
   for (i = 0; i < nobjects; ++i) {
     objects[i] = dmnsn_new_object();
@@ -133,41 +133,41 @@ main()
     objects[i]->intersection_fn = &dmnsn_fake_intersection_fn;
   }
 
-  /* dmnsn_kD_splay_insert() */
+  /* dmnsn_bvst_insert() */
 
   grains = 0;
   for (i = 0; i < nobjects; ++i) {
     sandglass_bench_noprecache(&sandglass,
-                               dmnsn_kD_splay_insert(tree, objects[i]));
+                               dmnsn_bvst_insert(tree, objects[i]));
     sandglass.grains += grains;
     grains = sandglass.grains;
   }
-  printf("dmnsn_kD_splay_insert(): %ld\n", sandglass.grains/nobjects);
+  printf("dmnsn_bvst_insert(): %ld\n", sandglass.grains/nobjects);
 
-  /* dmnsn_kD_splay_search() */
+  /* dmnsn_bvst_search() */
 
   ray.x0 = dmnsn_new_vector(0.0, 0.0, -2.0);
   ray.n  = dmnsn_new_vector(0.0, 0.0, 1.0);
 
   dmnsn_delete_intersection((*objects[0]->intersection_fn)(objects[0], ray));
   sandglass_bench_noprecache(&sandglass, {
-    intersection = dmnsn_kD_splay_search(tree, ray);
+    intersection = dmnsn_bvst_search(tree, ray);
   });
   dmnsn_delete_intersection(intersection);
-  printf("dmnsn_kD_splay_search(): %ld\n", sandglass.grains);
+  printf("dmnsn_bvst_search(): %ld\n", sandglass.grains);
 
-  /* dmnsn_kD_splay() */
+  /* dmnsn_bvst_splay() */
   grains = 0;
   for (i = 0; i < nobjects; ++i) {
-    node = dmnsn_kD_splay_deepest(tree);
-    sandglass_bench_noprecache(&sandglass, dmnsn_kD_splay(tree, node));
+    node = dmnsn_bvst_deepest(tree);
+    sandglass_bench_noprecache(&sandglass, dmnsn_bvst_splay(tree, node));
     sandglass.grains += grains;
     grains = sandglass.grains;
   }
-  printf("dmnsn_kD_splay(): %ld\n", sandglass.grains/nobjects);
+  printf("dmnsn_bvst_splay(): %ld\n", sandglass.grains/nobjects);
 
   /* Cleanup */
-  dmnsn_delete_kD_splay_tree(tree);
+  dmnsn_delete_bvst(tree);
   for (i = 0; i < nobjects; ++i) {
     dmnsn_delete_object(objects[i]);
   }
diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 0efa05c..b3f6813 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -42,6 +42,8 @@ lib_LTLIBRARIES = libdimension.la
 
 libdimension_la_SOURCES = $(nobase_include_HEADERS)                            \
                           ambient.c                                            \
+                          bvst.c                                               \
+                          bvst.h                                               \
                           camera.c                                             \
                           canvas.c                                             \
                           color.c                                              \
@@ -53,8 +55,6 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS)                            \
                           geometry.c                                           \
                           gl.c                                                 \
                           inlines.c                                            \
-                          kD_splay_tree.c                                      \
-                          kD_splay_tree.h                                      \
                           light.c                                              \
                           object.c                                             \
                           perspective.c                                        \
diff --git a/libdimension/kD_splay_tree.c b/libdimension/bvst.c
index b6be801..a73b4b2 100644
--- a/libdimension/kD_splay_tree.c
+++ b/libdimension/bvst.c
@@ -21,14 +21,14 @@
 #include "dimension_impl.h"
 #include <stdlib.h>
 
-static dmnsn_kD_splay_node *dmnsn_new_kD_splay_node();
-static void dmnsn_delete_kD_splay_node(dmnsn_kD_splay_node *node);
+static dmnsn_bvst_node *dmnsn_new_bvst_node();
+static void dmnsn_delete_bvst_node(dmnsn_bvst_node *node);
 
 /* Return an empty tree */
-dmnsn_kD_splay_tree *
-dmnsn_new_kD_splay_tree()
+dmnsn_bvst *
+dmnsn_new_bvst()
 {
-  dmnsn_kD_splay_tree *tree = malloc(sizeof(dmnsn_kD_splay_tree));
+  dmnsn_bvst *tree = malloc(sizeof(dmnsn_bvst));
   if (tree) {
     tree->root = NULL;
   } else {
@@ -38,29 +38,29 @@ dmnsn_new_kD_splay_tree()
 }
 
 /* Recursively copy the nodes of a kD splay tree */
-static dmnsn_kD_splay_node *
-dmnsn_kD_splay_copy_recursive(dmnsn_kD_splay_node *root)
+static dmnsn_bvst_node *
+dmnsn_bvst_copy_recursive(dmnsn_bvst_node *root)
 {
-  dmnsn_kD_splay_node *node = dmnsn_new_kD_splay_node();
+  dmnsn_bvst_node *node = dmnsn_new_bvst_node();
   *node = *root;
   if (node->contains) {
-    node->contains = dmnsn_kD_splay_copy_recursive(node->contains);
+    node->contains = dmnsn_bvst_copy_recursive(node->contains);
     node->contains->parent = node;
   }
   if (node->container) {
-    node->container = dmnsn_kD_splay_copy_recursive(node->container);
+    node->container = dmnsn_bvst_copy_recursive(node->container);
     node->container->parent = node;
   }
   return node;
 }
 
 /* Copy a kD splay tree */
-dmnsn_kD_splay_tree *
-dmnsn_kD_splay_copy(dmnsn_kD_splay_tree *tree)
+dmnsn_bvst *
+dmnsn_bvst_copy(dmnsn_bvst *tree)
 {
-  dmnsn_kD_splay_tree *copy = dmnsn_new_kD_splay_tree();
+  dmnsn_bvst *copy = dmnsn_new_bvst();
   if (tree->root)
-    copy->root = dmnsn_kD_splay_copy_recursive(tree->root);
+    copy->root = dmnsn_bvst_copy_recursive(tree->root);
   else
     copy->root = NULL;
   return copy;
@@ -68,21 +68,21 @@ dmnsn_kD_splay_copy(dmnsn_kD_splay_tree *tree)
 
 /* Recursively free a kD splay tree */
 void
-dmnsn_delete_kD_splay_tree_recursive(dmnsn_kD_splay_node *node)
+dmnsn_delete_bvst_recursive(dmnsn_bvst_node *node)
 {
   if (node) {
-    dmnsn_delete_kD_splay_tree_recursive(node->contains);
-    dmnsn_delete_kD_splay_tree_recursive(node->container);
-    dmnsn_delete_kD_splay_node(node);
+    dmnsn_delete_bvst_recursive(node->contains);
+    dmnsn_delete_bvst_recursive(node->container);
+    dmnsn_delete_bvst_node(node);
   }
 }
 
 /* Free a kD splay tree */
 void
-dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_tree *tree)
+dmnsn_delete_bvst(dmnsn_bvst *tree)
 {
   if (tree) {
-    dmnsn_delete_kD_splay_tree_recursive(tree->root);
+    dmnsn_delete_bvst_recursive(tree->root);
     free(tree);
   }
 }
@@ -91,14 +91,14 @@ dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_tree *tree)
 static int dmnsn_box_contains(dmnsn_vector p,
                               dmnsn_vector min, dmnsn_vector max);
 /* Expand node to contain the bounding box from min to max */
-static void dmnsn_kD_splay_node_swallow(dmnsn_kD_splay_node *node,
-                                        dmnsn_vector min, dmnsn_vector max);
+static void dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
+                                    dmnsn_vector min, dmnsn_vector max);
 
 /* Insert an object into the tree */
 void
-dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
+dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
 {
-  dmnsn_kD_splay_node *node = dmnsn_new_kD_splay_node(), *parent = tree->root;
+  dmnsn_bvst_node *node = dmnsn_new_bvst_node(), *parent = tree->root;
 
   /* Store the inverse of the transformation matrix */
   object->trans_inv = dmnsn_matrix_inverse(object->trans);
@@ -117,31 +117,31 @@ dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
   dmnsn_vector corner;
   corner = dmnsn_new_vector(object->min.x, object->min.y, object->max.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   corner = dmnsn_new_vector(object->min.x, object->max.y, object->min.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   corner = dmnsn_new_vector(object->min.x, object->max.y, object->max.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   corner = dmnsn_new_vector(object->max.x, object->min.y, object->min.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   corner = dmnsn_new_vector(object->max.x, object->min.y, object->max.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   corner = dmnsn_new_vector(object->max.x, object->max.y, object->min.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   corner = dmnsn_new_vector(object->max.x, object->max.y, object->max.z);
   corner = dmnsn_matrix_vector_mul(object->trans, corner);
-  dmnsn_kD_splay_node_swallow(node, corner, corner);
+  dmnsn_bvst_node_swallow(node, corner, corner);
 
   /* Now insert the node */
 
@@ -160,7 +160,7 @@ dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
     } else {
       /* Expand node's bounding box to fully contain parent's if it doesn't
          already */
-      dmnsn_kD_splay_node_swallow(node, parent->min, parent->max);
+      dmnsn_bvst_node_swallow(node, parent->min, parent->max);
       /* node now fully contains parent */
       if (parent->container)
         parent = parent->container;
@@ -173,7 +173,7 @@ dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
     }
   }
 
-  dmnsn_kD_splay(tree, node);
+  dmnsn_bvst_splay(tree, node);
 }
 
 /* Return whether p is within the axis-aligned box with corners min and max */
@@ -186,8 +186,8 @@ dmnsn_box_contains(dmnsn_vector p, dmnsn_vector min, dmnsn_vector max)
 
 /* Expand node to contain the bounding box from min to max */
 static void
-dmnsn_kD_splay_node_swallow(dmnsn_kD_splay_node *node,
-                            dmnsn_vector min, dmnsn_vector max)
+dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
+                        dmnsn_vector min, dmnsn_vector max)
 {
   if (node->min.x > min.x) node->min.x = min.x;
   if (node->min.y > min.y) node->min.y = min.y;
@@ -199,28 +199,28 @@ dmnsn_kD_splay_node_swallow(dmnsn_kD_splay_node *node,
 }
 
 /* Tree rotations */
-static void dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node);
+static void dmnsn_bvst_rotate(dmnsn_bvst_node *node);
 
 /* Splay a node: move it to the root via tree rotations */
 void
-dmnsn_kD_splay(dmnsn_kD_splay_tree *tree, dmnsn_kD_splay_node *node)
+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_kD_splay_rotate(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_kD_splay_rotate(node->parent);
-      dmnsn_kD_splay_rotate(node);
+      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_kD_splay_rotate(node);
-      dmnsn_kD_splay_rotate(node);
+      dmnsn_bvst_rotate(node);
+      dmnsn_bvst_rotate(node);
     }
   }
   tree->root = node;
@@ -228,9 +228,9 @@ dmnsn_kD_splay(dmnsn_kD_splay_tree *tree, dmnsn_kD_splay_node *node)
 
 /* Rotate a tree on the edge connecting node and node->parent */
 static void
-dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node)
+dmnsn_bvst_rotate(dmnsn_bvst_node *node)
 {
-  dmnsn_kD_splay_node *P, *Q, *B;
+  dmnsn_bvst_node *P, *Q, *B;
   if (node == node->parent->contains) {
     /* We are a left child; perform a right rotation:
      *
@@ -293,22 +293,21 @@ dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node)
 }
 
 typedef struct {
-  dmnsn_kD_splay_node *node;
+  dmnsn_bvst_node *node;
   dmnsn_intersection  *intersection;
-} dmnsn_kD_splay_search_result;
+} dmnsn_bvst_search_result;
 
-static dmnsn_kD_splay_search_result
-dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
-                                double t);
+static dmnsn_bvst_search_result
+dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t);
 
 dmnsn_intersection *
-dmnsn_kD_splay_search(dmnsn_kD_splay_tree *tree, dmnsn_line ray)
+dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray)
 {
-  dmnsn_kD_splay_search_result result
-    = dmnsn_kD_splay_search_recursive(tree->root, ray, -1.0);
+  dmnsn_bvst_search_result result
+    = dmnsn_bvst_search_recursive(tree->root, ray, -1.0);
 
   if (result.node)
-    dmnsn_kD_splay(tree, result.node);
+    dmnsn_bvst_splay(tree, result.node);
 
   return result.intersection;
 }
@@ -316,19 +315,18 @@ dmnsn_kD_splay_search(dmnsn_kD_splay_tree *tree, dmnsn_line ray)
 static int dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_vector min,
                                       dmnsn_vector max, double t);
 
-static dmnsn_kD_splay_search_result
-dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
-                                double t)
+static dmnsn_bvst_search_result
+dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
 {
   dmnsn_line ray_trans;
-  dmnsn_kD_splay_search_result result = { NULL, NULL }, result_temp;
+  dmnsn_bvst_search_result result = { NULL, NULL }, result_temp;
 
   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_kD_splay_search_recursive(node->container, ray, t);
+  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;
@@ -376,7 +374,7 @@ dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
     }
 
     /* Go down the left subtree */
-    result_temp = dmnsn_kD_splay_search_recursive(node->contains, ray, t);
+    result_temp = dmnsn_bvst_search_recursive(node->contains, ray, t);
     if (result_temp.node && (t < 0.0 || result_temp.intersection->t < t)) {
       dmnsn_delete_intersection(result.intersection);
       result = result_temp;
@@ -447,10 +445,10 @@ dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_vector min, dmnsn_vector max,
   return 0;
 }
 
-static dmnsn_kD_splay_node *
-dmnsn_new_kD_splay_node()
+static dmnsn_bvst_node *
+dmnsn_new_bvst_node()
 {
-  dmnsn_kD_splay_node *node = malloc(sizeof(dmnsn_kD_splay_node));
+  dmnsn_bvst_node *node = malloc(sizeof(dmnsn_bvst_node));
   if (!node) {
     dmnsn_error(DMNSN_SEVERITY_HIGH, "kD splay tree node allocation failed.");
   }
@@ -458,7 +456,7 @@ dmnsn_new_kD_splay_node()
 }
 
 static void
-dmnsn_delete_kD_splay_node(dmnsn_kD_splay_node *node)
+dmnsn_delete_bvst_node(dmnsn_bvst_node *node)
 {
   free(node);
 }
diff --git a/libdimension/kD_splay_tree.h b/libdimension/bvst.h
index eac47d8..57b71b8 100644
--- a/libdimension/kD_splay_tree.h
+++ b/libdimension/bvst.h
@@ -19,7 +19,7 @@
  *************************************************************************/
 
 /*
- * k-dimensional (in this case, k == 3) trees for storing object bounding boxes.
+ * 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-
@@ -29,22 +29,22 @@
  * are expanded to contain it.
  */
 
-#ifndef DIMENSION_IMPL_KD_SPLAY_TREE_H
-#define DIMENSION_IMPL_KD_SPLAY_TREE_H
+#ifndef DIMENSION_IMPL_BVST_H
+#define DIMENSION_IMPL_BVST_H
 
-typedef struct dmnsn_kD_splay_tree dmnsn_kD_splay_tree;
-typedef struct dmnsn_kD_splay_node dmnsn_kD_splay_node;
+typedef struct dmnsn_bvst dmnsn_bvst;
+typedef struct dmnsn_bvst_node dmnsn_bvst_node;
 
-struct dmnsn_kD_splay_tree {
-  dmnsn_kD_splay_node *root;
+struct dmnsn_bvst {
+  dmnsn_bvst_node *root;
 };
 
-struct dmnsn_kD_splay_node {
+struct dmnsn_bvst_node {
   /* Tree children */
-  dmnsn_kD_splay_node *contains, *container;
+  dmnsn_bvst_node *contains, *container;
 
   /* Parent node for easy backtracking */
-  dmnsn_kD_splay_node *parent;
+  dmnsn_bvst_node *parent;
 
   /* Bounding box corners */
   dmnsn_vector min, max;
@@ -53,14 +53,13 @@ struct dmnsn_kD_splay_node {
   dmnsn_object *object;
 };
 
-dmnsn_kD_splay_tree *dmnsn_new_kD_splay_tree();
-dmnsn_kD_splay_tree *dmnsn_kD_splay_copy(dmnsn_kD_splay_tree *tree);
-void dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_tree *tree);
+dmnsn_bvst *dmnsn_new_bvst();
+dmnsn_bvst *dmnsn_bvst_copy(dmnsn_bvst *tree);
+void dmnsn_delete_bvst(dmnsn_bvst *tree);
 
-void dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object);
-void dmnsn_kD_splay(dmnsn_kD_splay_tree *tree, dmnsn_kD_splay_node *node);
+void dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object);
+void dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node);
 
-dmnsn_intersection *dmnsn_kD_splay_search(dmnsn_kD_splay_tree *tree,
-                                          dmnsn_line ray);
+dmnsn_intersection *dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray);
 
-#endif /* DIMENSION_IMPL_KD_SPLAY_TREE_H */
+#endif /* DIMENSION_IMPL_BVST_H */
diff --git a/libdimension/dimension_impl.h b/libdimension/dimension_impl.h
index 216302a..880aee7 100644
--- a/libdimension/dimension_impl.h
+++ b/libdimension/dimension_impl.h
@@ -22,6 +22,6 @@
 #define DIMENSION_IMPL_H
 
 #include "dimension.h"
-#include "kD_splay_tree.h"
+#include "bvst.h"
 
 #endif /* DIMENSION_IMPL_H */
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index a76a2f5..1e03b91 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -30,7 +30,7 @@
 typedef struct {
   dmnsn_progress *progress;
   dmnsn_scene *scene;
-  dmnsn_kD_splay_tree *kD_splay_tree;
+  dmnsn_bvst *bvst;
 
   /* For multithreading */
   unsigned int index, threads;
@@ -63,19 +63,19 @@ dmnsn_raytrace_scene_async(dmnsn_scene *scene)
       return NULL;
     }
 
-    payload->progress      = progress;
-    payload->scene         = scene;
-    payload->kD_splay_tree = dmnsn_new_kD_splay_tree();
+    payload->progress = progress;
+    payload->scene    = scene;
+    payload->bvst     = dmnsn_new_bvst();
 
     for (i = 0; i < dmnsn_array_size(payload->scene->objects); ++i) {
       dmnsn_array_get(payload->scene->objects, i, &object);
-      dmnsn_kD_splay_insert(payload->kD_splay_tree, object);
+      dmnsn_bvst_insert(payload->bvst, object);
     }
 
     if (pthread_create(&progress->thread, NULL, &dmnsn_raytrace_scene_thread,
                        payload) != 0)
     {
-      dmnsn_delete_kD_splay_tree(payload->kD_splay_tree);
+      dmnsn_delete_bvst(payload->bvst);
       free(payload);
       dmnsn_delete_progress(progress);
       return NULL;
@@ -145,8 +145,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
     payloads[i].index = i;
     payloads[i].threads = nthreads;
     if (i > 0) {
-      payloads[i].kD_splay_tree =
-        dmnsn_kD_splay_copy(payloads[0].kD_splay_tree);
+      payloads[i].bvst = dmnsn_bvst_copy(payloads[0].bvst);
     }
   }
 
@@ -164,7 +163,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
         } else {
           /* Only free on a successful join - otherwise we might free a pointer
              out from under a running thread */
-          dmnsn_delete_kD_splay_tree(payloads[j].kD_splay_tree);
+          dmnsn_delete_bvst(payloads[j].bvst);
           free(ptr);
         }
       }
@@ -182,7 +181,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
       if (retval == 0) {
         retval = *(int *)ptr;
       }
-      dmnsn_delete_kD_splay_tree(payloads[i].kD_splay_tree);
+      dmnsn_delete_bvst(payloads[i].bvst);
       free(ptr);
     }
   }
@@ -195,7 +194,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
 /* Actual raytracing implementation */
 static int dmnsn_raytrace_scene_impl(dmnsn_progress *progress,
                                      dmnsn_scene *scene,
-                                     dmnsn_kD_splay_tree *kD_splay_tree,
+                                     dmnsn_bvst *bvst,
                                      unsigned int index, unsigned int threads);
 
 /* Multi-threading thread callback */
@@ -206,7 +205,7 @@ dmnsn_raytrace_scene_multithread_thread(void *ptr)
   int *retval = malloc(sizeof(int));
   if (retval) {
     *retval = dmnsn_raytrace_scene_impl(payload->progress, payload->scene,
-                                        payload->kD_splay_tree,
+                                        payload->bvst,
                                         payload->index, payload->threads);
   }
   return retval;
@@ -219,7 +218,7 @@ dmnsn_raytrace_scene_multithread_thread(void *ptr)
 typedef struct dmnsn_raytrace_state {
   const dmnsn_scene *scene;
   const dmnsn_intersection *intersection;
-  dmnsn_kD_splay_tree *kD_splay_tree;
+  dmnsn_bvst *bvst;
   unsigned int level;
 
   dmnsn_vector r;
@@ -238,12 +237,12 @@ static dmnsn_color dmnsn_raytrace_shoot(dmnsn_raytrace_state *state,
 /* Actually raytrace a scene */
 static int
 dmnsn_raytrace_scene_impl(dmnsn_progress *progress, dmnsn_scene *scene,
-                          dmnsn_kD_splay_tree *kD_splay_tree,
+                          dmnsn_bvst *bvst,
                           unsigned int index, unsigned int threads)
 {
   dmnsn_raytrace_state state = {
     .scene = scene,
-    .kD_splay_tree = kD_splay_tree
+    .bvst = bvst
   };
 
   unsigned int width  = scene->canvas->x;
@@ -339,10 +338,8 @@ dmnsn_raytrace_light_ray(const dmnsn_raytrace_state *state,
 
   unsigned int level = state->level;
   while (level) {
-    dmnsn_intersection *shadow_caster = dmnsn_kD_splay_search(
-      state->kD_splay_tree,
-      shadow_ray
-    );
+    dmnsn_intersection *shadow_caster
+      = dmnsn_bvst_search(state->bvst, shadow_ray);
 
     if (!shadow_caster || shadow_caster->t > 1.0) {
       dmnsn_delete_intersection(shadow_caster);
@@ -468,7 +465,7 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
   --state->level;
 
   dmnsn_intersection *intersection
-    = dmnsn_kD_splay_search(state->kD_splay_tree, ray);
+    = dmnsn_bvst_search(state->bvst, ray);
 
   dmnsn_color color = state->scene->background;
   if (intersection) {
diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am
index 7b238da..886eb42 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                                               \
-                    kD_splay_tree-test                                         \
+                    bvst-test                                                  \
                     png-test                                                   \
                     gl-test
 TESTS             = $(check_PROGRAMS)
@@ -45,8 +45,8 @@ error_test_LDADD   = libdimension-tests.la
 warning_test_SOURCES = warning.c
 warning_test_LDADD   = libdimension-tests.la
 
-kD_splay_tree_test_SOURCES = kD_splay_tree.c
-kD_splay_tree_test_LDADD   = libdimension-tests.la
+bvst_test_SOURCES = bvst.c
+bvst_test_LDADD   = libdimension-tests.la
 
 png_test_SOURCES = png.c
 png_test_LDADD   = libdimension-tests.la
diff --git a/tests/libdimension/kD_splay_tree.c b/tests/libdimension/bvst.c
index ea53550..36dce04 100644
--- a/tests/libdimension/kD_splay_tree.c
+++ b/tests/libdimension/bvst.c
@@ -18,7 +18,7 @@
  *************************************************************************/
 
 /*
- * Basic tests of our fancy k-D splay tree framework
+ * Basic tests of our Bounding Volume Splay Tree framework
  */
 
 #include "../../libdimension/dimension_impl.h"
@@ -27,7 +27,7 @@
 int
 main()
 {
-  dmnsn_kD_splay_tree *tree;
+  dmnsn_bvst *tree;
   dmnsn_object *obj1, *obj2, *obj3;
 
   obj1 = dmnsn_new_object();
@@ -43,28 +43,28 @@ main()
   obj3->min = dmnsn_new_vector(-1.0, -1.0, -1.0);
   obj3->max = dmnsn_new_vector(0.0, 0.0, 0.0);
 
-  tree = dmnsn_new_kD_splay_tree();
+  tree = dmnsn_new_bvst();
 
-  dmnsn_kD_splay_insert(tree, obj1);
+  dmnsn_bvst_insert(tree, obj1);
   if (tree->root->object != obj1) {
-    fprintf(stderr, "Wrong kD splay tree built.\n");
+    fprintf(stderr, "Wrong BVST built.\n");
     return EXIT_FAILURE;
   }
 
-  dmnsn_kD_splay_insert(tree, obj2);
+  dmnsn_bvst_insert(tree, obj2);
   if (tree->root->object != obj2 || tree->root->contains->object != obj1) {
-    fprintf(stderr, "Wrong kD splay tree built.\n");
+    fprintf(stderr, "Wrong BVST built.\n");
     return EXIT_FAILURE;
   }
 
-  dmnsn_kD_splay_insert(tree, obj3);
+  dmnsn_bvst_insert(tree, obj3);
   if (tree->root->object != obj3 || tree->root->contains->object != obj1
       || tree->root->container->object != obj2) {
-    fprintf(stderr, "Wrong kD splay tree built.\n");
+    fprintf(stderr, "Wrong BVST built.\n");
     return EXIT_FAILURE;
   }
 
-  dmnsn_delete_kD_splay_tree(tree);
+  dmnsn_delete_bvst(tree);
   dmnsn_delete_object(obj3);
   dmnsn_delete_object(obj2);
   dmnsn_delete_object(obj1);