Implement insert for kD splay trees.

3 files changed, 129 insertions, 0 deletions

diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 2333baf..f11f119 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -38,6 +38,7 @@ nobase_include_HEADERS = dimension.h                                           \
 lib_LTLIBRARIES = libdimension.la
 
 libdimension_la_SOURCES = $(nobase_include_HEADERS)                            \
+                          dimension_impl.h                                     \
                           camera.c                                             \
                           cameras.c                                            \
                           canvas.c                                             \
@@ -46,6 +47,8 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS)                            \
                           geometry.c                                           \
                           gl.c                                                 \
                           inlines.c                                            \
+                          kD_splay_tree.c                                      \
+                          kD_splay_tree.h                                      \
                           object.c                                             \
                           objects.c                                            \
                           pigments.c                                           \
diff --git a/libdimension/kD_splay_tree.c b/libdimension/kD_splay_tree.c
index 043be8a..ce27b47 100644
--- a/libdimension/kD_splay_tree.c
+++ b/libdimension/kD_splay_tree.c
@@ -59,6 +59,7 @@ dmnsn_kD_splay_node *dmnsn_kD_splay_copy(dmnsn_kD_splay_node *root)
   return node;
 }
 
+/* Recursively free a kD splay tree */
 void
 dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_node *root)
 {
@@ -69,9 +70,122 @@ dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_node *root)
   }
 }
 
+/* Return whether node1 contains node2 */
+static int dmnsn_kD_splay_contains(const dmnsn_kD_splay_node *node1,
+                                   const dmnsn_kD_splay_node *node2);
+/* Expand node to contain the bounding box from min to max */
+static void dmnsn_kD_splay_swallow(dmnsn_kD_splay_node *node,
+                                   dmnsn_vector min, dmnsn_vector max);
+
+/* Insert an object into the tree.  Returns the new tree root. */
+dmnsn_kD_splay_node *
+dmnsn_kD_splay_insert(dmnsn_kD_splay_node *root, dmnsn_object *object)
+{
+  dmnsn_vector corner;
+  dmnsn_kD_splay_node *node = dmnsn_new_kD_splay_node();
+
+  node->left = NULL;
+  node->right = NULL;
+  node->parent = NULL;
+  node->object = object;
+
+  /* Calculate the new bounding box by finding the minimum coordinate of the
+     transformed corners of the object's original bounding box */
+
+  node->min = dmnsn_matrix_vector_mul(object->trans, object->min);
+  node->max = node->min;
+
+  corner = dmnsn_vector_construct(object->min.x, object->min.y, object->max.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  corner = dmnsn_vector_construct(object->min.x, object->max.y, object->min.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  corner = dmnsn_vector_construct(object->min.x, object->max.y, object->max.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  corner = dmnsn_vector_construct(object->max.x, object->min.y, object->min.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  corner = dmnsn_vector_construct(object->max.x, object->min.y, object->max.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  corner = dmnsn_vector_construct(object->max.x, object->max.y, object->min.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  corner = dmnsn_vector_construct(object->max.x, object->max.y, object->max.z);
+  corner = dmnsn_matrix_vector_mul(object->trans, corner);
+  dmnsn_kD_splay_swallow(node, corner, corner);
+
+  /* Now insert the node */
+
+  while (root) {
+    if (dmnsn_kD_splay_contains(root, node)) {
+      /* node < root */
+      if (root->left)
+        root = root->left;
+      else {
+        /* We found our parent; insert and splay */
+        root->left = node;
+        node->parent = root;
+        dmnsn_kD_splay(node);
+        break;
+      }
+    } else {
+      /* Expand the bounding box to fully contain root if it doesn't
+          already */
+      dmnsn_kD_splay_swallow(node, root->min, root->max);
+      /* node >= root */
+      if (root->right)
+        root = root->right;
+      else {
+        /* We found our parent; insert and splay */
+        root->right = node;
+        node->parent = root;
+        dmnsn_kD_splay(node);
+        break;
+      }
+    }
+  }
+
+  return node;
+}
+
+/* Return whether node1 contains node2 */
+static int
+dmnsn_kD_splay_contains(const dmnsn_kD_splay_node *node1,
+                        const dmnsn_kD_splay_node *node2)
+{
+  return (node1->min.x <= node2->min.x && node1->min.y <= node2->min.y
+          && node1->min.z <= node2->min.z)
+         && (node1->max.x >= node2->max.x && node1->max.y >= node2->max.y
+             && node1->max.z >= node2->max.z);
+}
+
+/* Expand node to contain the bounding box from min to max */
+static void
+dmnsn_kD_splay_swallow(dmnsn_kD_splay_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.z;
+  if (node->min.z > min.z) node->min.z = min.y;
+
+  if (node->max.x < max.x) node->max.x = max.x;
+  if (node->max.y < max.y) node->max.y = max.z;
+  if (node->max.z < max.z) node->max.z = max.y;
+}
+
 /* Tree rotations */
 static void dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node);
 
+/* Splay a node: move it to the root via tree rotations */
 void
 dmnsn_kD_splay(dmnsn_kD_splay_node *node)
 {
@@ -95,6 +209,7 @@ dmnsn_kD_splay(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)
 {
diff --git a/libdimension/kD_splay_tree.h b/libdimension/kD_splay_tree.h
index 7d00b8c..61c1944 100644
--- a/libdimension/kD_splay_tree.h
+++ b/libdimension/kD_splay_tree.h
@@ -18,6 +18,17 @@
  * <http://www.gnu.org/licenses/>.                                       *
  *************************************************************************/
 
+/*
+ * k-dimensional (in this case, k == 3) 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.
+ */
+
 #ifndef DIMENSION_IMPL_KD_SPLAY_TREE_H
 #define DIMENSION_IMPL_KD_SPLAY_TREE_H