kdTreeAccel Class Reference
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...
#include <kdTreeAccel.h>
Public Types | |
| enum | SplitPlaneType { SPLIT_PLANE_MIDDLE = 0, SPLIT_PLANE_MEDIAN, SPLIT_PLANE_SAH } |
| Supported split plane generation techniques. More... | |
| enum | SplitAxisType { SPLIT_AXIS_ROUND_ROBIN = 0, SPLIT_AXIS_LONGEST_EXTENT } |
| Supported split axis selection techniques. More... | |
Public Member Functions | |
Constructors | |
| kdTreeAccel () | |
| virtual | ~kdTreeAccel () |
Initialization Routines | |
| void | setBuildParams (const BuildParams &buildParams) |
| virtual void | init () |
Main usage interface | |
| virtual real_t | getIntersection (const Ray &ray, SurfacePoint &pt) |
| virtual bool | intersects (const Ray &ray, real_t tMax=INFINITY) |
| virtual void | preview () |
Accessors | |
| const BuildParams & | getBuildParams () const |
Protected Types | |
| typedef void(kdTreeAccel::* | SplitFunction )(kdWorkBuffer *) const |
Protected Member Functions | |
| void | _buildTree (kdWorkBuffer *) |
| void | _buildTreeHelper (kdWorkBuffer *, kdNode *node, IndexedIntersectableList *primitives, const unsigned splitAxis, const real_t splitPos, const unsigned depth) |
| unsigned | _computeSplitAxis (kdWorkBuffer *) const |
| void | _postCompressTree () |
| void | _computeSplitAxisRoundRobin (kdWorkBuffer *) const |
| void | _computeSplitAxisLongestExtent (kdWorkBuffer *) const |
| void | _computeSplitPlaneMiddle (kdWorkBuffer *) const |
| void | _computeSplitPlaneMedian (kdWorkBuffer *) const |
| void | _computeSplitPlaneSAH (kdWorkBuffer *) const |
| unsigned | _computeSplitPlanesSAH (const IndexedIntersectableList &primitives, const unsigned int noPrimitives, const unsigned int splitAxis, kdSplitPlane *outPlanes) const |
| void | _computeSplitCostSAH (const kdWorkBuffer *, real_t splitPos, const unsigned splitAxis, unsigned noLeft, unsigned noPlane, unsigned noRight, kdSAHCost &outCost) const |
Protected Attributes | |
| SplitFunction | m_splitAxisFunction |
| SplitFunction | m_splitPlaneFunction |
| BuildParams | m_buildParams |
| kdNode * | m_root |
Classes | |
| struct | BuildParams |
| Parameters controlling construction of a kdTreeAccel. More... | |
Detailed Description
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.
- Date:
- Fall 2008
Definition at line 43 of file kdTreeAccel.h.
Member Typedef Documentation
typedef void(kdTreeAccel::* kdTreeAccel::SplitFunction)(kdWorkBuffer *) const [protected] |
Member Enumeration Documentation
Constructor & Destructor Documentation
| kdTreeAccel::kdTreeAccel | ( | ) | [explicit] |
Definition at line 391 of file kdTreeAccel.cpp.
| kdTreeAccel::~kdTreeAccel | ( | ) | [virtual] |
Definition at line 397 of file kdTreeAccel.cpp.
Member Function Documentation
| void kdTreeAccel::setBuildParams | ( | const BuildParams & | buildParams | ) | [inline] |
Definition at line 128 of file kdTreeAccel.h.
| void kdTreeAccel::init | ( | ) | [virtual] |
Constructs a kd-Tree with the current BuildParams
Reimplemented from SpatialAccel.
Definition at line 401 of file kdTreeAccel.cpp.
| real_t kdTreeAccel::getIntersection | ( | const Ray & | ray, | |
| SurfacePoint & | pt | |||
| ) | [virtual] |
technical note: tMin and tMax are always conservatively offset by EPSILON to reduce 99% of numerical robustness issues, the majority of which may could be due to inherent floating point arithmetic inprecision, compounded by the fact that kdNodes store their split plane positions using 32-bit floating point precision, whereas all other math in Milton uses 64-bit double floating point precision (real_t)
Each Ray has a unique "ID" stored with it to help prevent multiple intersection tests against the same Shape during traversal of an acceleration data structure (e.g., kd-Tree -- since a Shape may appear in more than one leaf node)
Implements SpatialAccel.
Definition at line 891 of file kdTreeAccel.cpp.
| void kdTreeAccel::preview | ( | ) | [virtual] |
| const BuildParams& kdTreeAccel::getBuildParams | ( | ) | const [inline] |
Definition at line 155 of file kdTreeAccel.h.
| void kdTreeAccel::_buildTree | ( | kdWorkBuffer * | workBuf | ) | [protected] |
Definition at line 531 of file kdTreeAccel.cpp.
| void kdTreeAccel::_buildTreeHelper | ( | kdWorkBuffer * | workBuf, | |
| kdNode * | node, | |||
| IndexedIntersectableList * | primitives, | |||
| const unsigned | splitAxis, | |||
| const real_t | splitPos, | |||
| const unsigned | depth | |||
| ) | [protected] |
Definition at line 630 of file kdTreeAccel.cpp.
| unsigned kdTreeAccel::_computeSplitAxis | ( | kdWorkBuffer * | ) | const [protected] |
| void kdTreeAccel::_postCompressTree | ( | ) | [protected] |
| void kdTreeAccel::_computeSplitAxisRoundRobin | ( | kdWorkBuffer * | workBuf | ) | const [protected] |
Definition at line 666 of file kdTreeAccel.cpp.
| void kdTreeAccel::_computeSplitAxisLongestExtent | ( | kdWorkBuffer * | workBuf | ) | const [protected] |
Definition at line 677 of file kdTreeAccel.cpp.
| void kdTreeAccel::_computeSplitPlaneMiddle | ( | kdWorkBuffer * | workBuf | ) | const [protected] |
Definition at line 692 of file kdTreeAccel.cpp.
| void kdTreeAccel::_computeSplitPlaneMedian | ( | kdWorkBuffer * | workBuf | ) | const [protected] |
Definition at line 703 of file kdTreeAccel.cpp.
| void kdTreeAccel::_computeSplitPlaneSAH | ( | kdWorkBuffer * | workBuf | ) | const [protected] |
Definition at line 720 of file kdTreeAccel.cpp.
| unsigned kdTreeAccel::_computeSplitPlanesSAH | ( | const IndexedIntersectableList & | primitives, | |
| const unsigned int | noPrimitives, | |||
| const unsigned int | splitAxis, | |||
| kdSplitPlane * | outPlanes | |||
| ) | const [inline, protected] |
- Returns:
- number of candidate planes (planes stored in 'outPlanes')
Definition at line 811 of file kdTreeAccel.cpp.
| void kdTreeAccel::_computeSplitCostSAH | ( | const kdWorkBuffer * | workBuf, | |
| real_t | splitPos, | |||
| const unsigned | splitAxis, | |||
| unsigned | noLeft, | |||
| unsigned | noPlane, | |||
| unsigned | noRight, | |||
| kdSAHCost & | outCost | |||
| ) | const [inline, protected] |
- Returns:
- Surface Area Heuristic (SAH) cost for given subdivision in out variable 'outCost'
Definition at line 853 of file kdTreeAccel.cpp.
Member Data Documentation
SplitFunction kdTreeAccel::m_splitAxisFunction [protected] |
Definition at line 180 of file kdTreeAccel.h.
SplitFunction kdTreeAccel::m_splitPlaneFunction [protected] |
Definition at line 181 of file kdTreeAccel.h.
BuildParams kdTreeAccel::m_buildParams [protected] |
Definition at line 210 of file kdTreeAccel.h.
kdNode* kdTreeAccel::m_root [protected] |
Definition at line 213 of file kdTreeAccel.h.
The documentation for this class was generated from the following files:
Generated on 28 Feb 2009 for Milton by
1.5.6