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

enum kdtree::eSort

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.