|
Mitsuba Renderer
0.5.0
|
|
|
Mitsuba Renderer
0.5.0
|
|
Optimized KD-tree acceleration data structure for n-dimensional (n<=4) shapes and various queries on them. More...
#include <mitsuba/render/gkdtree.h>
Inheritance diagram for mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >: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 | EventList |
| 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 | RewriteItem |
| Once the tree has been constructed, it is rewritten into a more convenient binary storage format. 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< AABBType > | Parent |
| typedef Parent::SizeType | SizeType |
| typedef Parent::IndexType | IndexType |
| typedef Parent::KDNode | KDNode |
| typedef AABBType::Scalar | Scalar |
| typedef AABBType::PointType | PointType |
| typedef AABBType::VectorType | VectorType |
| Public Types inherited from mitsuba::KDTreeBase< AABBType > | |
| typedef uint32_t | IndexType |
| Index number format (max 2^32 prims) More... | |
| typedef uint32_t | SizeType |
| Size number format. More... | |
Public Member Functions | |
| GenericKDTree () | |
| Create a new kd-tree instance initialized with the default parameters. More... | |
| virtual | ~GenericKDTree () |
| Release all memory. More... | |
| void | setTraversalCost (Float traversalCost) |
| Set the traversal cost used by the tree construction heuristic. More... | |
| IndexType * | getIndices () const |
| Returns the underlying kd-tree index buffer. More... | |
| Float | getTraversalCost () const |
| Return the traversal cost used by the tree construction heuristic. More... | |
| 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) More... | |
| 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) More... | |
| void | setEmptySpaceBonus (Float emptySpaceBonus) |
| Set the bonus factor for empty space used by the tree construction heuristic. More... | |
| Float | getEmptySpaceBonus () const |
| Return the bonus factor for empty space used by the tree construction heuristic. More... | |
| void | setMaxDepth (SizeType maxDepth) |
| Set the maximum tree depth (0 = use heuristic) More... | |
| void | setMinMaxBins (SizeType minMaxBins) |
| Set the number of bins used for Min-Max binning. More... | |
| SizeType | getMinMaxBins () const |
| Return the number of bins used for Min-Max binning. More... | |
| SizeType | getMaxDepth () const |
| Return maximum tree depth (0 = use heuristic) More... | |
| void | setClip (bool clip) |
| Specify whether or not to use primitive clipping will be used in the tree construction. More... | |
| bool | getClip () const |
| Return whether or not to use primitive clipping will be used in the tree construction. More... | |
| void | setRetract (bool retract) |
| Specify whether or not bad splits can be "retracted". More... | |
| bool | getRetract () const |
| Return whether or not bad splits can be "retracted". More... | |
| void | setMaxBadRefines (SizeType maxBadRefines) |
| Set the number of bad refines allowed to happen in succession before a leaf node will be created. More... | |
| SizeType | getMaxBadRefines () const |
| Return the number of bad refines allowed to happen in succession before a leaf node will be created. More... | |
| void | setStopPrims (SizeType stopPrims) |
| Set the number of primitives, at which recursion will stop when building the tree. More... | |
| SizeType | getStopPrims () const |
| Return the number of primitives, at which recursion will stop when building the tree. More... | |
| void | setParallelBuild (bool parallel) |
| Specify whether or not tree construction should run in parallel. More... | |
| bool | getParallelBuild () const |
| Return whether or not tree construction will run in parallel. More... | |
| 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. More... | |
| 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. More... | |
| Public Member Functions inherited from mitsuba::KDTreeBase< AABBType > | |
| BOOST_STATIC_ASSERT (sizeof(KDNode)==8) | |
| ELogLevel | getLogLevel () const |
| Return the log level of kd-tree status messages. More... | |
| void | setLogLevel (ELogLevel level) |
| Return the log level of kd-tree status messages. More... | |
| const KDNode * | getRoot () const |
| Return the root node of the kd-tree. More... | |
| bool | isBuilt () const |
| Return whether or not the kd-tree has been built. More... | |
| const AABBType & | getAABB () const |
| Return a (slightly enlarged) axis-aligned bounding box containing all primitives. More... | |
| const AABBType & | getTightAABB () const |
| Return a tight axis-aligned bounding box containing all primitives. More... | |
| virtual const Class * | getClass () const |
| Retrieve this object's class. More... | |
| Public Member Functions inherited from Object | |
| Object () | |
| Construct a new object. More... | |
| int | getRefCount () const |
| Return the current reference count. More... | |
| void | incRef () const |
| Increase the reference count of the object by one. More... | |
| void | decRef (bool autoDeallocate=true) const |
| Decrease the reference count of the object and possibly deallocate it. More... | |
| virtual std::string | toString () const |
| Return a human-readable string representation of the object's contents. More... | |
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. More... | |
| BOOST_STATIC_ASSERT (sizeof(EdgeEvent)==12) | |
| Derived * | cast () |
| Cast to the derived class. More... | |
| const Derived * | cast () const |
| Cast to the derived class (const version) More... | |
| EventList | createEventList (OrderedChunkAllocator &alloc, const AABBType &nodeAABB, IndexType *prims, SizeType primCount) |
| Create an edge event list for a given list of primitives. More... | |
| void | createLeaf (BuildContext &ctx, KDNode *node, EdgeEvent *eventStart, EdgeEvent *eventEnd, SizeType primCount) |
| Leaf node creation helper function. More... | |
| void | createLeaf (BuildContext &ctx, KDNode *node, SizeType *indices, SizeType primCount) |
| Leaf node creation helper function. More... | |
| void | createLeafAfterRetraction (BuildContext &ctx, KDNode *node, SizeType start) |
| Leaf node creation helper function. More... | |
| Float | transitionToNLogN (BuildContext &ctx, unsigned int depth, KDNode *node, const AABBType &nodeAABB, IndexType *indices, SizeType primCount, bool isLeftChild, SizeType badRefines) |
| Implements the transition from min-max-binning to the O(n log n) optimization. More... | |
| Float | buildTreeMinMax (BuildContext &ctx, unsigned int depth, KDNode *node, const AABBType &nodeAABB, const AABBType &tightAABB, IndexType *indices, SizeType primCount, bool isLeftChild, SizeType badRefines) |
| Build helper function (min-max binning) More... | |
| Float | buildTree (BuildContext &ctx, unsigned int depth, KDNode *node, const AABBType &nodeAABB, EdgeEvent *eventStart, EdgeEvent *eventEnd, SizeType primCount, bool isLeftChild, SizeType badRefines) |
| Protected Member Functions inherited from mitsuba::KDTreeBase< AABBType > | |
| virtual | ~KDTreeBase () |
| Protected Member Functions inherited from Object | |
| virtual | ~Object () |
| Virtual private deconstructor. (Will only be called by ref) More... | |
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 |
| ref< Mutex > | m_indirectionLock |
| BuildInterface | m_interface |
| Protected Attributes inherited from mitsuba::KDTreeBase< AABBType > | |
| KDNode * | m_nodes |
| ELogLevel | m_logLevel |
| AABBType | m_aabb |
| AABBType | m_tightAABB |
Additional Inherited Members | |
| Static Public Member Functions inherited from Object | |
| static void | staticInitialization () |
| Initializes the built-in reference count debugger (if enabled) More... | |
| static void | staticShutdown () |
| Free the memory taken by staticInitialization() More... | |
| Static Public Attributes inherited from mitsuba::KDTreeBase< AABBType > | |
| static Class * | m_theClass = new Class("KDTreeBase", true, "Object") |
| Static Public Attributes inherited from Object | |
| static Class * | m_theClass |
| Pointer to the object's class descriptor. More... | |
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:
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 AABB 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 mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::IndexType |
| typedef Parent::KDNode mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::KDNode |
| typedef KDTreeBase<AABBType> mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::Parent |
| typedef AABBType::PointType mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::PointType |
| typedef AABBType::Scalar mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::Scalar |
| typedef Parent::SizeType mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::SizeType |
| typedef AABBType::VectorType mitsuba::GenericKDTree< AABBType, TreeConstructionHeuristic, Derived >::VectorType |
|
protected |
Primitive classification during tree-construction.
|
inline |
Create a new kd-tree instance initialized with the default parameters.
|
inlinevirtual |
Release all memory.
|
protected |
|
inlineprotected |
Build a KD-tree over the supplied geometry.
To be called by the subclass.
Clean up event lists and print statistics
|
inlineprotected |
|
inlineprotected |
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 |
| nodeAABB | Axis-aligned bounding box of the current node |
| tightAABB | 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. |
|
inlineprotected |
Cast to the derived class.
|
inlineprotected |
Cast to the derived class (const version)
|
inlineprotected |
Create an edge event list for a given list of primitives.
This is necessary when passing from Min-Max binning to the more accurate O(n log n) optimizier.
|
inlineprotected |
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 |
|
inlineprotected |
Leaf node creation helper function.
| ctx | Thread-specific build context containing allocators etc. |
| node | KD-tree node entry to be filled |
| indices | Start pointer of an index list |
| primCount | Total primitive count for the current node |
|
inlineprotected |
Leaf node creation helper function.
Creates a unique index list by collapsing a subtree with a bad cost.
| ctx | Thread-specific build context containing allocators etc. |
| node | KD-tree node entry to be filled |
| start | Start pointer of the subtree indices |
|
inline |
Return whether or not to use primitive clipping will be used in the tree construction.
|
inline |
Return the bonus factor for empty space used by the tree construction heuristic.
|
inline |
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.
|
inline |
Returns the underlying kd-tree index buffer.
|
inline |
Return the number of bad refines allowed to happen in succession before a leaf node will be created.
|
inline |
Return maximum tree depth (0 = use heuristic)
|
inline |
Return the number of bins used for Min-Max binning.
|
inline |
Return whether or not tree construction will run in parallel.
|
inline |
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)
|
inline |
Return whether or not bad splits can be "retracted".
|
inline |
Return the number of primitives, at which recursion will stop when building the tree.
|
inline |
Return the traversal cost used by the tree construction heuristic.
|
inline |
Specify whether or not to use primitive clipping will be used in the tree construction.
|
inline |
Set the bonus factor for empty space used by the tree construction heuristic.
|
inline |
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.
|
inline |
Set the number of bad refines allowed to happen in succession before a leaf node will be created.
|
inline |
Set the maximum tree depth (0 = use heuristic)
|
inline |
Set the number of bins used for Min-Max binning.
|
inline |
Specify whether or not tree construction should run in parallel.
|
inline |
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)
|
inline |
Specify whether or not bad splits can be "retracted".
|
inline |
Set the number of primitives, at which recursion will stop when building the tree.
|
inline |
Set the traversal cost used by the tree construction heuristic.
|
inlineprotected |
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 |
| nodeAABB | 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. |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
1.8.5 