Classes | Typedefs | Enumerations | Functions | Variables

kdtree Namespace Reference
[kd-tree Library]


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...


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


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



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 ()


static const float s_eps = 1.0e-9

Enumeration Type Documentation


"left" of sort plane, negative distance


"right" of sort plane, positive distance


in sort plane, or spans both sides


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.