Classes | Namespaces | Typedefs | Enumerations | Enumerator | Functions | Variables

kd-tree Library
[Geometry Libraries]


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 )(void *context, Entry *entry, 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 (const char *title) const throw ()
eSort kdtree::sortPoint (const plane_t &plane,const point3d_t &point) throw ()
 say which side of a given sort plane the provided test point is on
eSort kdtree::sortRect (const plane_t &plane,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 (smart_ptr< Entry > &entry, 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 (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 (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 (eStrategy strategy, float param)
 here you tell the kd-tree to subdivide (recursively), using the given strategy.
eAction kdtree::Node::iterateStaticEntries (const rect3d_t &r, iteration_callback callback, 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_tkdtree::Node::getRect (void) const throw ()
const plane_tkdtree::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 (void *context) throw ()
void * kdtree::Node::getUserPointer (void) const throw ()
static smart_ptr< Node > kdtree::Node::create (const rect3d_t &bounds)
 when you create a kd-tree node (especially the root!) you had better know the overall boundaries.
 kdtree::Node::Node (void) throw ()
void kdtree::Node::initialize (const rect3d_t &bounds)
void kdtree::Node::subdivideInternal (eStrategy strategy, float param)

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
smart_ptr< Node > kdtree::Node::m_left
smart_ptr< Node > kdtree::Node::m_right
plane_t kdtree::Node::m_sortPlane
rect3d_t kdtree::Node::m_bounds
vec_entries_t kdtree::Node::m_entries
smart_ptr< dynamic_entry_t > kdtree::Node::m_dynamic
void * kdtree::Node::m_user

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)(void *context,Entry *entry,const rect3d_t &entry_rect)

Definition at line 141 of file kdtree.h.

typedef std::vector<entry_rec_t> kdtree::Node::vec_entries_t [inherited]

Definition at line 174 of file kdtree.h.


Enumeration Type Documentation

Enumerator:
eAxis_X 
eAxis_Y 
eAxis_Z 
eAxis_Invalid 

Definition at line 83 of file kdtree.h.

Enumerator:
eAction_Continue 
eAction_Halt 
eAction_Remove 
eAction_Invalid 

Definition at line 131 of file kdtree.h.

strategies used for space partitioning

Enumerator:
eStrategy_Naive 

simple strategy based on bounding box

eStrategy_Balance 

strategy that aims to balance nodes

eStrategy_Invalid 

Definition at line 147 of file kdtree.h.


Function Documentation

bool kdtree::plane_t::isValid ( void   )  const throw () [inline, inherited]

Definition at line 99 of file kdtree.h.

void kdtree::plane_t::dump ( const char *  title  )  const throw () [inline, inherited]

Definition at line 100 of file kdtree.h.

eSort kdtree::sortPoint ( const plane_t plane,
const point3d_t point 
) throw ()

say which side of a given sort plane the provided test point is on

eSort kdtree::sortRect ( const plane_t plane,
const rect3d_t r 
) throw ()

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 ( smart_ptr< Entry > &  entry,
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 ( 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 ( 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 ( eStrategy  strategy,
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 ( const rect3d_t r,
iteration_callback  callback,
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]

Definition at line 210 of file kdtree.h.

const Node* kdtree::Node::getRightChild ( void   )  const throw () [inline, inherited]

Definition at line 211 of file kdtree.h.

Node* kdtree::Node::getLeftChild ( void   )  throw () [inline, inherited]

Definition at line 212 of file kdtree.h.

Node* kdtree::Node::getRightChild ( void   )  throw () [inline, inherited]

Definition at line 213 of file kdtree.h.

const rect3d_t& kdtree::Node::getRect ( void   )  const throw () [inline, inherited]

Definition at line 215 of file kdtree.h.

const plane_t& kdtree::Node::getSortPlane ( void   )  const throw () [inline, inherited]

Definition at line 216 of file kdtree.h.

const vec_entries_t& kdtree::Node::getStaticEntries ( void   )  const throw () [inline, inherited]

Definition at line 218 of file kdtree.h.

vec_entries_t& kdtree::Node::getStaticEntries ( void   )  throw () [inline, inherited]

Definition at line 219 of file kdtree.h.

void kdtree::Node::setUserPointer ( void *  context  )  throw () [inline, inherited]

Definition at line 221 of file kdtree.h.

void* kdtree::Node::getUserPointer ( void   )  const throw () [inline, inherited]

Definition at line 222 of file kdtree.h.

smart_ptr< Node > kdtree::Node::create ( const rect3d_t bounds  )  [static, 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.

kdtree::Node::Node ( void   )  throw () [private, inherited]

Definition at line 516 of file kdtree.cpp.

void kdtree::Node::initialize ( const rect3d_t bounds  )  [private, inherited]

Definition at line 536 of file kdtree.cpp.

void kdtree::Node::subdivideInternal ( eStrategy  strategy,
float  param 
) [private, inherited]

Definition at line 848 of file kdtree.cpp.


Variable Documentation

eAxis kdtree::plane_t::axis [inherited]

which axis is normal to this plane

Definition at line 105 of file kdtree.h.

float kdtree::plane_t::value [inherited]

coordinate value along axis

Definition at line 106 of file kdtree.h.

Definition at line 165 of file kdtree.h.

Definition at line 170 of file kdtree.h.

smart_ptr<dynamic_entry_t> kdtree::Node::dynamic_entry_t::next [inherited]

Definition at line 171 of file kdtree.h.

smart_ptr<Node> kdtree::Node::m_left [private, inherited]

Definition at line 241 of file kdtree.h.

smart_ptr<Node> kdtree::Node::m_right [private, inherited]

Definition at line 242 of file kdtree.h.

plane_t kdtree::Node::m_sortPlane [private, inherited]

Definition at line 243 of file kdtree.h.

rect3d_t kdtree::Node::m_bounds [private, inherited]

Definition at line 244 of file kdtree.h.

vec_entries_t kdtree::Node::m_entries [private, inherited]

Definition at line 245 of file kdtree.h.

smart_ptr<dynamic_entry_t> kdtree::Node::m_dynamic [private, inherited]

Definition at line 246 of file kdtree.h.

void* kdtree::Node::m_user [private, inherited]

Definition at line 247 of file kdtree.h.