GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived > Class Template Reference

Optimized KD-tree acceleration data structure for n-dimensional (n<=4) shapes and various queries on them. More...

#include <gkdtree.h>

Inheritance diagram for GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >:

List of all members.

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

---

Detailed Description

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>
class GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >

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.

Author:

Wenzel Jakob

Definition at line 629 of file gkdtree.h.

---

Member Typedef Documentation

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef Parent::IndexType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::IndexType

Index number format (max 2^32 prims)

Reimplemented from KDTreeBase< BoundingBoxType >.

Reimplemented in KDTree.

Definition at line 639 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef Parent::KDNode GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::KDNode

Reimplemented in KDTree.

Definition at line 640 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef KDTreeBase<BoundingBoxType> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::Parent

Reimplemented in KDTree.

Definition at line 634 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef BoundingBoxType::PointType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::PointType

Definition at line 642 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef BoundingBoxType::Scalar GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::Scalar

Definition at line 641 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef Parent::SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::SizeType

Size number format.

Reimplemented from KDTreeBase< BoundingBoxType >.

Reimplemented in KDTree.

Definition at line 638 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

typedef BoundingBoxType::VectorType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::VectorType

Definition at line 643 of file gkdtree.h.

---

Member Enumeration Documentation

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

enum GenericKDTree::EClassificationResult [protected]

Primitive classification during tree-construction.

Enumerator:

EBothSides	Straddling primitive.
ELeftSide	Primitive is entirely on the left side of the split.
ERightSide	Primitive is entirely on the right side of the split.
EBothSidesProcessed	Edge events have been generated for the straddling primitive.

Definition at line 1104 of file gkdtree.h.

---

Constructor & Destructor Documentation

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::GenericKDTree

(

)

[inline]

Create a new kd-tree instance initialized with the default parameters.

Definition at line 654 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

virtual GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::~GenericKDTree

(

)

[inline, virtual]

Release all memory.

Definition at line 672 of file gkdtree.h.

---

Member Function Documentation

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::BOOST_STATIC_ASSERT

(

sizeof(EdgeEvent)

= =12

)

[protected]

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::buildInternal

(

)

[inline, protected]

Build a KD-tree over the supplied geometry.

To be called by the subclass.

Clean up event lists and print statistics

Definition at line 856 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

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]

Definition at line 1719 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

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)

Parameters:

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.

Returns:

Final cost of the node

Definition at line 1559 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

Derived* GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::cast

(

)

[inline, protected]

Cast to the derived class.

Definition at line 1302 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

const Derived* GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::cast

(

)

const [inline, protected]

Cast to the derived class (const version)

Definition at line 1307 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

boost::tuple<EdgeEvent *, EdgeEvent *, SizeType> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createEventList	(	OrderedChunkAllocator &	alloc,
		const BoundingBoxType &	nodeBoundingBox,
		IndexType *	prims,
		SizeType	primCount
	)		[inline, protected]

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.

Definition at line 1317 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createLeaf	(	BuildContext &	ctx,
		KDNode *	node,
		EdgeEvent *	eventStart,
		EdgeEvent *	eventEnd,
		SizeType	primCount
	)		[inline, protected]

Leaf node creation helper function.

Parameters:

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

Definition at line 1372 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createLeaf	(	BuildContext &	ctx,
		KDNode *	node,
		SizeType *	indices,
		SizeType	primCount
	)		[inline, protected]

Leaf node creation helper function.

Parameters:

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

Definition at line 1404 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::createLeafAfterRetraction	(	BuildContext &	ctx,
		KDNode *	node,
		SizeType	start
	)		[inline, protected]

Leaf node creation helper function.

Creates a unique index list by collapsing a subtree with a bad cost.

Parameters:

ctx	Thread-specific build context containing allocators etc.
node	KD-tree node entry to be filled
start	Start pointer of the subtree indices

Definition at line 1429 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getClip

(

)

const [inline]

Return whether or not to use primitive clipping will be used in the tree construction.

Definition at line 767 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getEmptySpaceBonus

(

)

const [inline]

Return the bonus factor for empty space used by the tree construction heuristic.

Definition at line 723 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getExactPrimitiveThreshold

(

)

const [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.

Definition at line 847 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getMaxBadRefines

(

)

const [inline]

Return the number of bad refines allowed to happen in succession before a leaf node will be created.

Definition at line 797 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getMaxDepth

(

)

const [inline]

Return maximum tree depth (0 = use heuristic)

Definition at line 751 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getMinMaxBins

(

)

const [inline]

Return the number of bins used for Min-Max binning.

Definition at line 744 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getParallelBuild

(

)

const [inline]

Return whether or not tree construction will run in parallel.

Definition at line 829 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getQueryCost

(

)

const [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)

Definition at line 707 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getRetract

(

)

const [inline]

Return whether or not bad splits can be "retracted".

Definition at line 781 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getStopPrims

(

)

const [inline]

Return the number of primitives, at which recursion will stop when building the tree.

Definition at line 813 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::getTraversalCost

(

)

const [inline]

Return the traversal cost used by the tree construction heuristic.

Definition at line 689 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setClip

(

bool

clip

)

[inline]

Specify whether or not to use primitive clipping will be used in the tree construction.

Definition at line 759 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setEmptySpaceBonus

(

float

emptySpaceBonus

)

[inline]

Set the bonus factor for empty space used by the tree construction heuristic.

Definition at line 715 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setExactPrimitiveThreshold

(

SizeType

exactPrimThreshold

)

[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.

Definition at line 838 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setMaxBadRefines

(

SizeType

maxBadRefines

)

[inline]

Set the number of bad refines allowed to happen in succession before a leaf node will be created.

Definition at line 789 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setMaxDepth

(

SizeType

maxDepth

)

[inline]

Set the maximum tree depth (0 = use heuristic)

Definition at line 730 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setMinMaxBins

(

SizeType

minMaxBins

)

[inline]

Set the number of bins used for Min-Max binning.

Definition at line 737 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setParallelBuild

(

bool

parallel

)

[inline]

Specify whether or not tree construction should run in parallel.

Definition at line 821 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setQueryCost

(

float

queryCost

)

[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)

Definition at line 698 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setRetract

(

bool

retract

)

[inline]

Specify whether or not bad splits can be "retracted".

Definition at line 774 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setStopPrims

(

SizeType

stopPrims

)

[inline]

Set the number of primitives, at which recursion will stop when building the tree.

Definition at line 805 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

void GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::setTraversalCost

(

float

traversalCost

)

[inline]

Set the traversal cost used by the tree construction heuristic.

Definition at line 682 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

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.

Parameters:

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.

Returns:

Final cost of the node

Definition at line 1492 of file gkdtree.h.

---

Member Data Documentation

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

std::vector<TreeBuilder *> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_builders [protected]

Definition at line 2411 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_clip [protected]

Definition at line 2403 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_emptySpaceBonus [protected]

Definition at line 2402 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_exactPrimThreshold [protected]

Definition at line 2407 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indexCount [protected]

Definition at line 2410 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

IndexType* GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indices [protected]

Definition at line 2399 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

QMutex GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indirectionLock [protected]

Definition at line 2413 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

std::vector<KDNode *> GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_indirections [protected]

Definition at line 2412 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

BuildInterface GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_interface [protected]

Definition at line 2414 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_maxBadRefines [protected]

Definition at line 2406 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_maxDepth [protected]

Definition at line 2404 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_minMaxBins [protected]

Definition at line 2408 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_nodeCount [protected]

Definition at line 2409 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_parallelBuild [protected]

Definition at line 2403 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_queryCost [protected]

Definition at line 2401 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

bool GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_retract [protected]

Definition at line 2403 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

SizeType GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_stopPrims [protected]

Definition at line 2405 of file gkdtree.h.

template<typename BoundingBoxType, typename TreeConstructionHeuristic, typename Derived>

float GenericKDTree< BoundingBoxType, TreeConstructionHeuristic, Derived >::m_traversalCost [protected]

Definition at line 2400 of file gkdtree.h.

---

The documentation for this class was generated from the following file:

• include/nori/gkdtree.h