Implement insert for kD splay trees.

1 files changed, 11 insertions, 0 deletions

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