Nori
|
Optimized KD-tree acceleration data structure for n-dimensional (n<=4) shapes and various queries on them. More...
#include <gkdtree.h>
Classes | |
struct | BuildContext |
Per-thread context used to manage memory allocations, also records some useful statistics. More... | |
struct | BuildInterface |
Communication data structure used to pass jobs to kd-tree builder threads. More... | |
struct | EdgeEvent |
Describes the beginning or end of a primitive when projected onto a certain dimension. More... | |
struct | EdgeEventOrdering |
Edge event comparison functor. More... | |
struct | MinMaxBins |
Min-max binning as described in "Highly Parallel Fast KD-tree Construction for Interactive
Ray Tracing of Dynamic Scenes" by M. Shevtsov, A. Soupikov and A. Kapustin. More... | |
struct | SplitCandidate |
Data type for split candidates computed by the O(n log n) greedy optimization method. More... | |
class | TreeBuilder |
kd-tree builder thread More... | |
Public Types | |
typedef KDTreeBase < BoundingBoxType > | Parent |
typedef Parent::SizeType | SizeType |
Size number format. | |
typedef Parent::IndexType | IndexType |
Index number format (max 2^32 prims) | |
typedef Parent::KDNode | KDNode |
typedef BoundingBoxType::Scalar | Scalar |
typedef BoundingBoxType::PointType | PointType |
typedef BoundingBoxType::VectorType | VectorType |
Public Member Functions | |
GenericKDTree () | |
Create a new kd-tree instance initialized with the default parameters. | |
virtual | ~GenericKDTree () |
Release all memory. | |
void | setTraversalCost (float traversalCost) |
Set the traversal cost used by the tree construction heuristic. | |
float | getTraversalCost () const |
Return the traversal cost used by the tree construction heuristic. | |
void | setQueryCost (float queryCost) |
Set the query cost used by the tree construction heuristic (This is the average cost for testing a contained shape against a kd-tree search query) | |
float | getQueryCost () const |
Return the query cost used by the tree construction heuristic (This is the average cost for testing a contained shape against a kd-tree search query) | |
void | setEmptySpaceBonus (float emptySpaceBonus) |
Set the bonus factor for empty space used by the tree construction heuristic. | |
float | getEmptySpaceBonus () const |
Return the bonus factor for empty space used by the tree construction heuristic. | |
void | setMaxDepth (SizeType maxDepth) |
Set the maximum tree depth (0 = use heuristic) | |
void | setMinMaxBins (SizeType minMaxBins) |
Set the number of bins used for Min-Max binning. | |
SizeType | getMinMaxBins () const |
Return the number of bins used for Min-Max binning. | |
SizeType | getMaxDepth () const |
Return maximum tree depth (0 = use heuristic) | |
void | setClip (bool clip) |
Specify whether or not to use primitive clipping will be used in the tree construction. | |
bool | getClip () const |
Return whether or not to use primitive clipping will be used in the tree construction. | |
void | setRetract (bool retract) |
Specify whether or not bad splits can be "retracted". | |
bool | getRetract () const |
Return whether or not bad splits can be "retracted". | |
void | setMaxBadRefines (SizeType maxBadRefines) |
Set the number of bad refines allowed to happen in succession before a leaf node will be created. | |
SizeType | getMaxBadRefines () const |
Return the number of bad refines allowed to happen in succession before a leaf node will be created. | |
void | setStopPrims (SizeType stopPrims) |
Set the number of primitives, at which recursion will stop when building the tree. | |
SizeType | getStopPrims () const |
Return the number of primitives, at which recursion will stop when building the tree. | |
void | setParallelBuild (bool parallel) |
Specify whether or not tree construction should run in parallel. | |
bool | getParallelBuild () const |
Return whether or not tree construction will run in parallel. | |
void | setExactPrimitiveThreshold (SizeType exactPrimThreshold) |
Specify the number of primitives, at which the builder will switch from (approximate) Min-Max binning to the accurate O(n log n) optimization method. | |
SizeType | getExactPrimitiveThreshold () const |
Return the number of primitives, at which the builder will switch from (approximate) Min-Max binning to the accurate O(n log n) optimization method. | |
Protected Types | |
enum | EClassificationResult { EBothSides = 0, ELeftSide = 1, ERightSide = 2, EBothSidesProcessed = 3 } |
Primitive classification during tree-construction. More... | |
Protected Member Functions | |
void | buildInternal () |
Build a KD-tree over the supplied geometry. | |
BOOST_STATIC_ASSERT (sizeof(EdgeEvent)==12) | |
Derived * | cast () |
Cast to the derived class. | |
const Derived * | cast () const |
Cast to the derived class (const version) | |
boost::tuple< EdgeEvent *, EdgeEvent *, SizeType > | createEventList (OrderedChunkAllocator &alloc, const BoundingBoxType &nodeBoundingBox, IndexType *prims, SizeType primCount) |
Create an edge event list for a given list of primitives. | |
void | createLeaf (BuildContext &ctx, KDNode *node, EdgeEvent *eventStart, EdgeEvent *eventEnd, SizeType primCount) |
Leaf node creation helper function. | |
void | createLeaf (BuildContext &ctx, KDNode *node, SizeType *indices, SizeType primCount) |
Leaf node creation helper function. | |
void | createLeafAfterRetraction (BuildContext &ctx, KDNode *node, SizeType start) |
Leaf node creation helper function. | |
float | transitionToNLogN (BuildContext &ctx, unsigned int depth, KDNode *node, const BoundingBoxType &nodeBoundingBox, IndexType *indices, SizeType primCount, bool isLeftChild, SizeType badRefines) |
Implements the transition from min-max-binning to the O(n log n) optimization. | |
float | buildTreeMinMax (BuildContext &ctx, unsigned int depth, KDNode *node, const BoundingBoxType &nodeBoundingBox, const BoundingBoxType &tightBBox, IndexType *indices, SizeType primCount, bool isLeftChild, SizeType badRefines) |
Build helper function (min-max binning) | |
float | buildTree (BuildContext &ctx, unsigned int depth, KDNode *node, const BoundingBoxType &nodeBoundingBox, EdgeEvent *eventStart, EdgeEvent *eventEnd, SizeType primCount, bool isLeftChild, SizeType badRefines) |
Protected Attributes | |
IndexType * | m_indices |
float | m_traversalCost |
float | m_queryCost |
float | m_emptySpaceBonus |
bool | m_clip |
bool | m_retract |
bool | m_parallelBuild |
SizeType | m_maxDepth |
SizeType | m_stopPrims |
SizeType | m_maxBadRefines |
SizeType | m_exactPrimThreshold |
SizeType | m_minMaxBins |
SizeType | m_nodeCount |
SizeType | m_indexCount |
std::vector< TreeBuilder * > | m_builders |
std::vector< KDNode * > | m_indirections |
QMutex | m_indirectionLock |
BuildInterface | m_interface |
Optimized KD-tree acceleration data structure for n-dimensional (n<=4) shapes and various queries on them.
Note that this class mainly concerns itself with data that cover a region of space. For point data, other implementations will be more suitable. The most important application in Mitsuba is the fast construction of high-quality trees for ray tracing. See the class SAHKDTree for this specialization.
The code in this class is a fully generic kd-tree implementation, which can theoretically support any kind of shape. However, subclasses still need to provide the following signatures for a functional implementation:
/// Return the total number of primitives inline SizeType getPrimitiveCount() const; /// Return the axis-aligned bounding box of a certain primitive inline BoundingBoxType getBoundingBox(IndexType primIdx) const; /// Return the bounding box of a primitive when clipped to another box inline BoundingBoxType getClippedBoundingBox(IndexType primIdx, const BoundingBoxType &bbox) const;
This class follows the "Curiously recurring template" design pattern so that the above functions can be inlined (in particular, no virtual calls will be necessary!).
When the kd-tree is initially built, this class optimizes a cost heuristic every time a split plane has to be chosen. For ray tracing, the heuristic is usually the surface area heuristic (SAH), but other choices are possible as well. The tree construction heuristic must be passed as a template argument, which can use a supplied bounding box and split candidate to compute approximate probabilities of recursing into the left and right subrees during a typical kd-tree query operation. See SurfaceAreaHeuristic for an example of the interface that must be implemented.
The kd-tree construction algorithm creates 'perfect split' trees as outlined in the paper "On Building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)" by Ingo Wald and Vlastimil Havran. This works even when the tree is not meant to be used for ray tracing. For polygonal meshes, the involved Sutherland-Hodgman iterations can be quite expensive in terms of the overall construction time. The setClip method can be used to deactivate perfect splits at the cost of a lower-quality tree.
Because the O(N log N) construction algorithm tends to cause many incoherent memory accesses, a fast approximate technique (Min-max binning) is used near the top of the tree, which significantly reduces cache misses. Once the input data has been narrowed down to a reasonable amount, the implementation switches over to the O(N log N) builder. When multiple processors are available, the build process runs in parallel.
typedef Parent::IndexType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::IndexType |
Index number format (max 2^32 prims)
Reimplemented from KDTreeBase< BoundingBoxType >.
Reimplemented in KDTree.
typedef Parent::KDNode GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::KDNode |
typedef KDTreeBase<BoundingBoxType> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::Parent |
typedef BoundingBoxType::PointType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::PointType |
typedef BoundingBoxType::Scalar GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::Scalar |
typedef Parent::SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::SizeType |
typedef BoundingBoxType::VectorType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::VectorType |
enum GenericKDTree::EClassificationResult [protected] |
Primitive classification during tree-construction.
GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::GenericKDTree | ( | ) | [inline] |
virtual GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::~GenericKDTree | ( | ) | [inline, virtual] |
GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::BOOST_STATIC_ASSERT | ( | sizeof(EdgeEvent) | = =12 | ) | [protected] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::buildInternal | ( | ) | [inline, protected] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::buildTree | ( | BuildContext & | ctx, |
unsigned int | depth, | ||
KDNode * | node, | ||
const BoundingBoxType & | nodeBoundingBox, | ||
EdgeEvent * | eventStart, | ||
EdgeEvent * | eventEnd, | ||
SizeType | primCount, | ||
bool | isLeftChild, | ||
SizeType | badRefines | ||
) | [inline, protected] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::buildTreeMinMax | ( | BuildContext & | ctx, |
unsigned int | depth, | ||
KDNode * | node, | ||
const BoundingBoxType & | nodeBoundingBox, | ||
const BoundingBoxType & | tightBBox, | ||
IndexType * | indices, | ||
SizeType | primCount, | ||
bool | isLeftChild, | ||
SizeType | badRefines | ||
) | [inline, protected] |
Build helper function (min-max binning)
ctx | Thread-specific build context containing allocators etc. |
depth | Current tree depth (1 == root node) |
node | KD-tree node entry to be filled |
nodeBoundingBox | Axis-aligned bounding box of the current node |
tightBBox | Tight bounding box of the contained geometry (for min-max binning) |
indices | Index list of all triangles in the current node (for min-max binning) |
primCount | Total primitive count for the current node |
isLeftChild | Is this node the left child of its parent? This is important for memory management using the OrderedChunkAllocator. |
badRefines | Number of "probable bad refines" further up the tree. This makes it possible to split along an initially bad-looking candidate in the hope that the cost was significantly overestimated. The counter makes sure that only a limited number of such splits can happen in succession. |
Derived* GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::cast | ( | ) | [inline, protected] |
const Derived* GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::cast | ( | ) | const [inline, protected] |
boost::tuple<EdgeEvent *, EdgeEvent *, SizeType> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createEventList | ( | OrderedChunkAllocator & | alloc, |
const BoundingBoxType & | nodeBoundingBox, | ||
IndexType * | prims, | ||
SizeType | primCount | ||
) | [inline, protected] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createLeaf | ( | BuildContext & | ctx, |
KDNode * | node, | ||
EdgeEvent * | eventStart, | ||
EdgeEvent * | eventEnd, | ||
SizeType | primCount | ||
) | [inline, protected] |
Leaf node creation helper function.
ctx | Thread-specific build context containing allocators etc. |
node | KD-tree node entry to be filled |
eventStart | Start pointer of an edge event list |
eventEnd | End pointer of an edge event list |
primCount | Total primitive count for the current node |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createLeaf | ( | BuildContext & | ctx, |
KDNode * | node, | ||
SizeType * | indices, | ||
SizeType | primCount | ||
) | [inline, protected] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createLeafAfterRetraction | ( | BuildContext & | ctx, |
KDNode * | node, | ||
SizeType | start | ||
) | [inline, protected] |
bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getClip | ( | ) | const [inline] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getEmptySpaceBonus | ( | ) | const [inline] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getExactPrimitiveThreshold | ( | ) | const [inline] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getMaxBadRefines | ( | ) | const [inline] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getMaxDepth | ( | ) | const [inline] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getMinMaxBins | ( | ) | const [inline] |
bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getParallelBuild | ( | ) | const [inline] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getQueryCost | ( | ) | const [inline] |
bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getRetract | ( | ) | const [inline] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getStopPrims | ( | ) | const [inline] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getTraversalCost | ( | ) | const [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setClip | ( | bool | clip | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setEmptySpaceBonus | ( | float | emptySpaceBonus | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setExactPrimitiveThreshold | ( | SizeType | exactPrimThreshold | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setMaxBadRefines | ( | SizeType | maxBadRefines | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setMaxDepth | ( | SizeType | maxDepth | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setMinMaxBins | ( | SizeType | minMaxBins | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setParallelBuild | ( | bool | parallel | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setQueryCost | ( | float | queryCost | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setRetract | ( | bool | retract | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setStopPrims | ( | SizeType | stopPrims | ) | [inline] |
void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setTraversalCost | ( | float | traversalCost | ) | [inline] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::transitionToNLogN | ( | BuildContext & | ctx, |
unsigned int | depth, | ||
KDNode * | node, | ||
const BoundingBoxType & | nodeBoundingBox, | ||
IndexType * | indices, | ||
SizeType | primCount, | ||
bool | isLeftChild, | ||
SizeType | badRefines | ||
) | [inline, protected] |
Implements the transition from min-max-binning to the O(n log n) optimization.
ctx | Thread-specific build context containing allocators etc. |
depth | Current tree depth (1 == root node) |
node | KD-tree node entry to be filled |
nodeBoundingBox | Axis-aligned bounding box of the current node |
indices | Index list of all triangles in the current node (for min-max binning) |
primCount | Total primitive count for the current node |
isLeftChild | Is this node the left child of its parent? This is important for memory management using the OrderedChunkAllocator. |
badRefines | Number of "probable bad refines" further up the tree. This makes it possible to split along an initially bad-looking candidate in the hope that the cost was significantly overestimated. The counter makes sure that only a limited number of such splits can happen in succession. |
std::vector<TreeBuilder *> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_builders [protected] |
bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_clip [protected] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_emptySpaceBonus [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_exactPrimThreshold [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indexCount [protected] |
IndexType* GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indices [protected] |
QMutex GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indirectionLock [protected] |
std::vector<KDNode *> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indirections [protected] |
BuildInterface GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_interface [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_maxBadRefines [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_maxDepth [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_minMaxBins [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_nodeCount [protected] |
bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_parallelBuild [protected] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_queryCost [protected] |
bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_retract [protected] |
SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_stopPrims [protected] |
float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_traversalCost [protected] |