From a868a2958dd7ea138b02543ef81cc78abf8622c7 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Fri, 15 Jan 2010 14:24:13 -0500 Subject: Rename kD splay trees to Bounding Volume Splay Trees. --- libdimension/bvst.h | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 libdimension/bvst.h (limited to 'libdimension/bvst.h') diff --git a/libdimension/bvst.h b/libdimension/bvst.h new file mode 100644 index 0000000..57b71b8 --- /dev/null +++ b/libdimension/bvst.h @@ -0,0 +1,65 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * . * + *************************************************************************/ + +/* + * 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- + * 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_BVST_H +#define DIMENSION_IMPL_BVST_H + +typedef struct dmnsn_bvst dmnsn_bvst; +typedef struct dmnsn_bvst_node dmnsn_bvst_node; + +struct dmnsn_bvst { + dmnsn_bvst_node *root; +}; + +struct dmnsn_bvst_node { + /* Tree children */ + dmnsn_bvst_node *contains, *container; + + /* Parent node for easy backtracking */ + dmnsn_bvst_node *parent; + + /* Bounding box corners */ + dmnsn_vector min, max; + + /* Node payload */ + dmnsn_object *object; +}; + +dmnsn_bvst *dmnsn_new_bvst(); +dmnsn_bvst *dmnsn_bvst_copy(dmnsn_bvst *tree); +void dmnsn_delete_bvst(dmnsn_bvst *tree); + +void dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object); +void dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node); + +dmnsn_intersection *dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray); + +#endif /* DIMENSION_IMPL_BVST_H */ -- cgit v1.2.3