From b45483d72dbc9c0eb8fee10df65877e5e2bfad91 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Mon, 5 Oct 2009 22:19:36 +0000
Subject: Implement insert for kD splay trees.
---
libdimension/Makefile.am | 3 ++
libdimension/kD_splay_tree.c | 115 +++++++++++++++++++++++++++++++++++++++++++
libdimension/kD_splay_tree.h | 11 +++++
3 files changed, 129 insertions(+)
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
--
cgit v1.2.3