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

Definition at line 127 of file kdtree.cpp.

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

Definition at line 158 of file kdtree.cpp.

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

Definition at line 187 of file kdtree.cpp.

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

Definition at line 213 of file kdtree.cpp.

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

Definition at line 327 of file kdtree.cpp.

static void kdtree::getLeftRightBounds ( IN const rect3d_t r,
IN const plane_t plane,
OUT rect3d_t left,
OUT 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.