kdTreeAccel.h File Reference

#include "accel/SpatialAccel.h"

Go to the source code of this file.

Classes

class kdTreeAccel

An N-dimensional kd-Tree is an axis-aligned binary spatial partitioning data structure. Each internal node is split along one of the N principle axes, where the split plane is typically chosen at each node based on some sort of heuristic. This kd-Tree implementation supports several common split plane generation methods, namely: spatial midpoint, median of geometry, and surface area heuristic (SAH). Note that a kd-Tree constructed by choosing the spatial midpoint along the current split axis as the next split plane is equivalent to an Octree. Also note that though the SAH produces the best quality tree overall with respect to visibility tests, it can take a long time to build and is thus mainly suitable for static scenes (whereas other acceleration data structures may be more appropriate for dynamic geometry & animations). The SAH kd-Tree may be tweaked with several parameters. See kdTreeAccelParams for more info. The O(nlog n) SAH construction has been implemented as opposed to the O(n) or O(n^2) alternatives (using std::sort for internal sorting). This choice was made because the O(n) solutions which exist both have large constants (which diminish their utility in practice), and are nowhere near as readable or easy to understand as the relatively straightforward O(nlog n) alternative. More...

struct kdTreeAccel::BuildParams

Parameters controlling construction of a kdTreeAccel. More...

Defines

#define KD_MAX_DEPTH (24)

Functions

DECLARE_STL_TYPEDEF (std::vector< unsigned >, IndexedIntersectableList)

Define Documentation

#define KD_MAX_DEPTH (24)

Definition at line 34 of file kdTreeAccel.h.

Function Documentation

DECLARE_STL_TYPEDEF	(	std::vector< unsigned >	,
		IndexedIntersectableList
	)


Classes
class	kdTreeAccel
	An N-dimensional kd-Tree is an axis-aligned binary spatial partitioning data structure. Each internal node is split along one of the N principle axes, where the split plane is typically chosen at each node based on some sort of heuristic. This kd-Tree implementation supports several common split plane generation methods, namely: spatial midpoint, median of geometry, and surface area heuristic (SAH). Note that a kd-Tree constructed by choosing the spatial midpoint along the current split axis as the next split plane is equivalent to an Octree. Also note that though the SAH produces the best quality tree overall with respect to visibility tests, it can take a long time to build and is thus mainly suitable for static scenes (whereas other acceleration data structures may be more appropriate for dynamic geometry & animations). The SAH kd-Tree may be tweaked with several parameters. See kdTreeAccelParams for more info. The O(nlog n) SAH construction has been implemented as opposed to the O(n) or O(n^2) alternatives (using std::sort for internal sorting). This choice was made because the O(n) solutions which exist both have large constants (which diminish their utility in practice), and are nowhere near as readable or easy to understand as the relatively straightforward O(nlog n) alternative. More...
struct	kdTreeAccel::BuildParams
	Parameters controlling construction of a kdTreeAccel. More...
Defines
#define	KD_MAX_DEPTH (24)
Functions
	DECLARE_STL_TYPEDEF (std::vector< unsigned >, IndexedIntersectableList)