From b45483d72dbc9c0eb8fee10df65877e5e2bfad91 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Mon, 5 Oct 2009 22:19:36 +0000 Subject: Implement insert for kD splay trees. --- libdimension/kD_splay_tree.h | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'libdimension/kD_splay_tree.h') 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 @@ * . * *************************************************************************/ +/* + * 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