Classes | Typedefs | Enumerations | Functions | Variables

kdtree Namespace Reference
[kd-tree Library]

Classes

struct  plane_t
 a kdtree plane is always axis-aligned More...
class  Entry
 base class for kd-tree entries. Clients can inherit from this. More...
class  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...

Typedefs

typedef eAction(* iteration_callback )(void *context, Entry *entry, const rect3d_t &entry_rect)

Enumerations

enum  eSort {
  eSort_Left = 1,
  eSort_Right = 2,
  eSort_Straddle = 3,
  eSort_Invalid = 0
}
enum  eAxis {
  eAxis_X = 1,
  eAxis_Y = 2,
  eAxis_Z = 3,
  eAxis_Invalid = 0
}
enum  eAction {
  eAction_Continue = 0x001,
  eAction_Halt = 0x002,
  eAction_Remove = 0x010,
  eAction_Invalid = 0
}
enum  eStrategy {
  eStrategy_Naive = 1,
  eStrategy_Balance = 2,
  eStrategy_Invalid = 0
}
 

strategies used for space partitioning

More...

Functions

eSort 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 sortRect (const plane_t &plane,const rect3d_t &rect) throw ()
 say how the given rectangle sorts against the given sorting plane
static eAxis getLongAxis (const rect3d_t &r) throw ()
static void simpleSplit (const rect3d_t &r, plane_t &plane) throw ()
static void measureSplit (const plane_t &plane, const Node::vec_entries_t &vec, int &nLeft, int &nRight) throw ()
static void bestSplit (int offset, const Node::vec_entries_t &vec, plane_t &plane, int &nLeft, int &nRight)
static void balancedSplit (const rect3d_t &r, plane_t &plane, const Node::vec_entries_t &vec) throw ()
static void getLeftRightBounds (const rect3d_t &r, const plane_t &plane, rect3d_t &left, rect3d_t &right) throw ()

Variables

static const float s_eps = 1.0e-9

Enumeration Type Documentation

Enumerator:
eSort_Left 

"left" of sort plane, negative distance

eSort_Right 

"right" of sort plane, positive distance

eSort_Straddle 

in sort plane, or spans both sides

eSort_Invalid 

Definition at line 72 of file kdtree.h.


Function Documentation

static eAxis kdtree::getLongAxis ( const rect3d_t r  )  throw () [static]

Definition at line 127 of file kdtree.cpp.

static void kdtree::simpleSplit ( const rect3d_t r,
plane_t plane 
) throw () [static]

Definition at line 158 of file kdtree.cpp.

static void kdtree::measureSplit ( const plane_t plane,
const Node::vec_entries_t &  vec,
int &  nLeft,
int &  nRight 
) throw () [static]

Definition at line 187 of file kdtree.cpp.

static void kdtree::bestSplit ( int  offset,
const Node::vec_entries_t &  vec,
plane_t plane,
int &  nLeft,
int &  nRight 
) [static]

Definition at line 213 of file kdtree.cpp.

static void kdtree::balancedSplit ( const rect3d_t r,
plane_t plane,
const Node::vec_entries_t &  vec 
) throw () [static]

Definition at line 327 of file kdtree.cpp.

static void kdtree::getLeftRightBounds ( const rect3d_t r,
const plane_t plane,
rect3d_t left,
rect3d_t right 
) throw () [static]

Definition at line 479 of file kdtree.cpp.


Variable Documentation

const float kdtree::s_eps = 1.0e-9 [static]

Definition at line 43 of file kdtree.cpp.