API for creating kd trees.
More...
Collaboration diagram for kd-tree Library:
|
Classes | |
| struct | kdtree::plane_t |
| a kdtree plane is always axis-aligned More... | |
| class | kdtree::Entry |
| base class for kd-tree entries. Clients can inherit from this. More... | |
| class | kdtree::Node |
| root (and node!) of a kd-tree This class is expected to be used as the core object for rendering and other CPU-intensive tasks, so it therefore has no virtual methods. More... | |
| struct | kdtree::Node::dynamic_entry_t |
Namespaces | |
| namespace | kdtree |
Typedefs | |
| typedef eAction(* | kdtree::iteration_callback )(IN void *context, IN Entry *entry, IN const rect3d_t &entry_rect) |
| typedef std::vector< entry_rec_t > | kdtree::Node::vec_entries_t |
Enumerations | |
| enum | kdtree::eAxis { kdtree::eAxis_X = 1, kdtree::eAxis_Y = 2, kdtree::eAxis_Z = 3, kdtree::eAxis_Invalid = 0 } |
| enum | kdtree::eAction { kdtree::eAction_Continue = 0x001, kdtree::eAction_Halt = 0x002, kdtree::eAction_Remove = 0x010, kdtree::eAction_Invalid = 0 } |
| enum | kdtree::eStrategy { kdtree::eStrategy_Naive = 1, kdtree::eStrategy_Balance = 2, kdtree::eStrategy_Invalid = 0 } |
strategies used for space partitioning More... | |
Functions | |
| bool | kdtree::plane_t::isValid (void) const throw () |
| void | kdtree::plane_t::dump (IN const char *title) const throw () |
| eSort | kdtree::sortPoint (IN const plane_t &plane, IN const point3d_t &point) throw () |
| say which side of a given sort plane the provided test point is on | |
| eSort | kdtree::sortRect (IN const plane_t &plane, IN const rect3d_t &rect) throw () |
| say how the given rectangle sorts against the given sorting plane | |
| kdtree::Node::~Node (void) throw () | |
| void | kdtree::Node::addStaticEntry (IN smart_ptr< Entry > &entry, IN const rect3d_t &r) |
| static entries are expensive to add and remove--do so rarely (such as when constructing the tree). | |
| void | kdtree::Node::addDynamicEntry (IN smart_ptr< dynamic_entry_t > &de) |
| dynamic entries are fast to add and remove, but are not used for partitioning and are not affected by subdividing. | |
| bool | kdtree::Node::removeStaticEntry (IN Entry *entry) throw () |
| smart_ptr< dynamic_entry_t > | kdtree::Node::popDynamicEntry (void) throw () |
| int | kdtree::Node::getTreeDepth (void) const throw () |
| int | kdtree::Node::getNodeCount (void) const throw () |
| int | kdtree::Node::getStaticEntryCount (void) const throw () |
| void | kdtree::Node::subdivide (IN eStrategy strategy, IN float param) |
| here you tell the kd-tree to subdivide (recursively), using the given strategy. | |
| eAction | kdtree::Node::iterateStaticEntries (IN const rect3d_t &r, IN iteration_callback callback, IN void *context) |
| client can iterate over all entries in the given rect | |
| const Node * | kdtree::Node::getLeftChild (void) const throw () |
| const Node * | kdtree::Node::getRightChild (void) const throw () |
| Node * | kdtree::Node::getLeftChild (void) throw () |
| Node * | kdtree::Node::getRightChild (void) throw () |
| const rect3d_t & | kdtree::Node::getRect (void) const throw () |
| const plane_t & | kdtree::Node::getSortPlane (void) const throw () |
| const vec_entries_t & | kdtree::Node::getStaticEntries (void) const throw () |
| vec_entries_t & | kdtree::Node::getStaticEntries (void) throw () |
| void | kdtree::Node::setUserPointer (IN void *context) throw () |
| void * | kdtree::Node::getUserPointer (void) const throw () |
| static smart_ptr< Node > | kdtree::Node::create (IN const rect3d_t &bounds) |
| when you create a kd-tree node (especially the root!) you had better know the overall boundaries. | |
Variables | |
| eAxis | kdtree::plane_t::axis |
| which axis is normal to this plane | |
| float | kdtree::plane_t::value |
| coordinate value along axis | |
| rect3d_t | kdtree::Node::entry_rec_t::rect |
| rect3d_t | kdtree::Node::dynamic_entry_t::rect |
| smart_ptr< dynamic_entry_t > | kdtree::Node::dynamic_entry_t::next |
Detailed Description
API for creating kd trees.
Only supports 3D for now. See http://en.wikipedia.org/wiki/Kd-tree
This library is optimized for use caess where a lot of objects are added and only a few are removed. In particular, the tree isn't rebalanced nor are empty nodes removed.
WARNING: This API is not threadsafe.
Typedef Documentation
| typedef eAction(* kdtree::iteration_callback)(IN void *context, IN Entry *entry, IN const rect3d_t &entry_rect) |
typedef std::vector<entry_rec_t> kdtree::Node::vec_entries_t [inherited] |
Enumeration Type Documentation
| enum kdtree::eAxis |
| enum kdtree::eAction |
| enum kdtree::eStrategy |
Function Documentation
| bool kdtree::plane_t::isValid | ( | void | ) | const throw () [inline, inherited] |
| void kdtree::plane_t::dump | ( | IN const char * | title | ) | const throw () [inline, inherited] |
say which side of a given sort plane the provided test point is on
say how the given rectangle sorts against the given sorting plane
| kdtree::Node::~Node | ( | void | ) | throw () [inherited] |
Definition at line 527 of file kdtree.cpp.
| void kdtree::Node::addStaticEntry | ( | IN smart_ptr< Entry > & | entry, | |
| IN const rect3d_t & | r | |||
| ) | [inherited] |
static entries are expensive to add and remove--do so rarely (such as when constructing the tree).
Definition at line 603 of file kdtree.cpp.
| void kdtree::Node::addDynamicEntry | ( | IN smart_ptr< dynamic_entry_t > & | de | ) | [inherited] |
dynamic entries are fast to add and remove, but are not used for partitioning and are not affected by subdividing.
Definition at line 646 of file kdtree.cpp.
| bool kdtree::Node::removeStaticEntry | ( | IN Entry * | entry | ) | throw () [inherited] |
Definition at line 679 of file kdtree.cpp.
| smart_ptr< Node::dynamic_entry_t > kdtree::Node::popDynamicEntry | ( | void | ) | throw () [inherited] |
Definition at line 705 of file kdtree.cpp.
| int kdtree::Node::getTreeDepth | ( | void | ) | const throw () [inherited] |
Definition at line 547 of file kdtree.cpp.
| int kdtree::Node::getNodeCount | ( | void | ) | const throw () [inherited] |
Definition at line 567 of file kdtree.cpp.
| int kdtree::Node::getStaticEntryCount | ( | void | ) | const throw () [inherited] |
Definition at line 582 of file kdtree.cpp.
| void kdtree::Node::subdivide | ( | IN eStrategy | strategy, | |
| IN float | param | |||
| ) | [inherited] |
here you tell the kd-tree to subdivide (recursively), using the given strategy.
The param use depends on the strategy.
- For the naive strategy, the param is the max number of nodes per entity.
Definition at line 786 of file kdtree.cpp.
| eAction kdtree::Node::iterateStaticEntries | ( | IN const rect3d_t & | r, | |
| IN iteration_callback | callback, | |||
| IN void * | context | |||
| ) | [inherited] |
client can iterate over all entries in the given rect
Definition at line 722 of file kdtree.cpp.
| const Node* kdtree::Node::getLeftChild | ( | void | ) | const throw () [inline, inherited] |
| const Node* kdtree::Node::getRightChild | ( | void | ) | const throw () [inline, inherited] |
| Node* kdtree::Node::getLeftChild | ( | void | ) | throw () [inline, inherited] |
| Node* kdtree::Node::getRightChild | ( | void | ) | throw () [inline, inherited] |
| const rect3d_t& kdtree::Node::getRect | ( | void | ) | const throw () [inline, inherited] |
| const plane_t& kdtree::Node::getSortPlane | ( | void | ) | const throw () [inline, inherited] |
| const vec_entries_t& kdtree::Node::getStaticEntries | ( | void | ) | const throw () [inline, inherited] |
| vec_entries_t& kdtree::Node::getStaticEntries | ( | void | ) | throw () [inline, inherited] |
| void kdtree::Node::setUserPointer | ( | IN void * | context | ) | throw () [inline, inherited] |
| void* kdtree::Node::getUserPointer | ( | void | ) | const throw () [inline, inherited] |
when you create a kd-tree node (especially the root!) you had better know the overall boundaries.
Anything you add to the node must be contained by these bounds.
Definition at line 895 of file kdtree.cpp.
Variable Documentation
eAxis kdtree::plane_t::axis [inherited] |
float kdtree::plane_t::value [inherited] |
rect3d_t kdtree::Node::entry_rec_t::rect [inherited] |
rect3d_t kdtree::Node::dynamic_entry_t::rect [inherited] |
smart_ptr<dynamic_entry_t> kdtree::Node::dynamic_entry_t::next [inherited] |
