SAH KD-tree acceleration data structure for fast ray-triangle intersections. More...

#include <mitsuba/render/skdtree.h>

Inheritance diagram for mitsuba::ShapeKDTree:

Classes
struct	IntersectionCache
	Temporarily holds some intersection information. More...

Public Member Functions
virtual const Class *	getClass () const
	Retrieve this object's class. More...

Initialization and tree construction
	ShapeKDTree ()
	Create an empty kd-tree. More...

void	addShape (const Shape *shape)
	Add a shape to the kd-tree. More...

const std::vector< const Shape * > &	getShapes () const
	Return the list of stored shapes. More...

SizeType	getPrimitiveCount () const
	Return the total number of low-level primitives (triangles and other low-level primitives) More...

const AABB &	getAABB () const
	Return an axis-aligned bounding box containing all primitives. More...

void	build ()
	Build the kd-tree (needs to be called before tracing any rays) More...

Ray tracing routines
bool	rayIntersect (const Ray &ray, Intersection &its) const
	Intersect a ray against all primitives stored in the kd-tree and return detailed intersection information. More...

bool	rayIntersect (const Ray &ray, Float &t, ConstShapePtr &shape, Normal &n, Point2 &uv) const
	Intersect a ray against all primitives stored in the kd-tree and return the traveled distance and intersected shape. More...

bool	rayIntersect (const Ray &ray) const
	Test a ray for occlusion with respect to all primitives stored in the kd-tree. More...

Public Member Functions inherited from mitsuba::SAHKDTree3D< Derived >
void	findCosts (Float &traversalCost, Float &intersectionCost)
	Empirically find the best traversal and intersection cost values. More...

Public Member Functions inherited from mitsuba::GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived >
	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< AABB >
	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 AABB &	getAABB () const
	Return a (slightly enlarged) axis-aligned bounding box containing all primitives. More...

const AABB &	getTightAABB () const
	Return a tight axis-aligned bounding box containing all primitives. 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...

Static Public Attributes
static Class *	m_theClass

Static Public Attributes inherited from mitsuba::KDTreeBase< AABB >
static Class *	m_theClass

Static Public Attributes inherited from Object
static Class *	m_theClass
	Pointer to the object's class descriptor. More...

Protected Member Functions
FINLINE IndexType	findShape (IndexType &idx) const
	Return the shape index corresponding to a primitive index seen by the generic kd-tree implementation. More...

FINLINE AABB	getAABB (IndexType idx) const
	Return the axis-aligned bounding box of a certain primitive. More...

FINLINE AABB	getClippedAABB (IndexType idx, const AABB &aabb) const
	Return the AABB of a primitive when clipped to another AABB. More...

FINLINE bool	intersect (const Ray &ray, IndexType idx, Float mint, Float maxt, Float &t, void *temp) const

FINLINE bool	intersect (const Ray &ray, IndexType idx, Float mint, Float maxt) const

template<bool BarycentricPos>
FINLINE void	fillIntersectionRecord (const Ray &ray, const void *temp, Intersection &its) const
	After having found a unique intersection, fill a proper record using the temporary information collected in intersect() More...

bool	rayIntersect (const Ray &ray, Float _mint, Float _maxt) const
	Plain shadow ray query (used by the 'instance' plugin) More...

bool	rayIntersect (const Ray &ray, Float _mint, Float _maxt, Float &t, void *temp) const
	Plain intersection query (used by the 'instance' plugin) More...

virtual	~ShapeKDTree ()
	Virtual destructor. More...

Protected Member Functions inherited from mitsuba::SAHKDTree3D< Derived >
void	buildInternal ()

Derived *	cast ()
	Cast to the derived class. More...

const Derived *	cast () const
	Cast to the derived class (const version) More...

template<bool shadowRay>
FINLINE bool	rayIntersectHavran (const Ray &ray, Float mint, Float maxt, Float &t, void *temp) const
	Ray tracing kd-tree traversal loop (Havran variant) More...

FINLINE RayStatistics	rayIntersectHavranCollectStatistics (const Ray &ray, Float mint, Float maxt, Float &t, void *temp) const
	Internal kd-tree traversal implementation (Havran variant) More...

template<bool shadowRay>
FINLINE bool	rayIntersectPBRT (const Ray &ray, Float mint_, Float maxt_, Float &t, void *temp) const
	Ray tracing kd-tree traversal loop (PBRT variant) More...

Protected Member Functions inherited from mitsuba::GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived >
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 AABB &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 AABB &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 AABB &nodeAABB, const AABB &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 AABB &nodeAABB, EdgeEvent eventStart, EdgeEvent *eventEnd, SizeType primCount, bool isLeftChild, SizeType badRefines)

Protected Member Functions inherited from mitsuba::KDTreeBase< AABB >
virtual	~KDTreeBase ()

Protected Member Functions inherited from Object
virtual	~Object ()
	Virtual private deconstructor. (Will only be called by ref) More...

Friends
class	GenericKDTree< AABB, SurfaceAreaHeuristic3, ShapeKDTree >

class	SAHKDTree3D< ShapeKDTree >

class	Instance

class	AnimatedInstance

class	SingleScatter

Additional Inherited Members
Public Types inherited from mitsuba::SAHKDTree3D< Derived >
typedef GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived >	Parent

typedef KDTreeBase< AABB > ::SizeType	SizeType

typedef KDTreeBase< AABB > ::IndexType	IndexType

typedef KDTreeBase< AABB >::KDNode	KDNode

Public Types inherited from mitsuba::GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived >
typedef KDTreeBase< AABB >	Parent

typedef Parent::SizeType	SizeType

typedef Parent::IndexType	IndexType

typedef Parent::KDNode	KDNode

typedef AABB::Scalar	Scalar

typedef AABB::PointType	PointType

typedef AABB::VectorType	VectorType

Public Types inherited from mitsuba::KDTreeBase< AABB >
typedef uint32_t	IndexType
	Index number format (max 2^32 prims) More...

typedef uint32_t	SizeType
	Size number format. More...

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

Protected Types inherited from mitsuba::GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived >
enum	EClassificationResult
	Primitive classification during tree-construction. More...

Protected Attributes inherited from mitsuba::GenericKDTree< AABB, SurfaceAreaHeuristic3, Derived >
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< AABB >
KDNode *	m_nodes

ELogLevel	m_logLevel

AABB	m_aabb

AABB	m_tightAABB

Detailed Description

SAH KD-tree acceleration data structure for fast ray-triangle intersections.

Implements the construction algorithm for 'perfect split' trees as outlined in the paper "On Bulding fast kd-Trees for Ray Tracing, and on doing that in O(N log N)" by Ingo Wald and Vlastimil Havran. Non-triangle shapes are supported, but most optimizations here target large triangle meshes. For more details regarding the construction algorithm, please refer to the class GenericKDTree.

This class offers a choice of two different triangle intersection algorithms: By default, intersections are computed using the "TriAccel" projection with pre-computation method from Ingo Wald's PhD thesis "Realtime Ray Tracing and Interactive Global Illumination". This adds an overhead of 48 bytes per triangle.

When compiled with MTS_KD_CONSERVE_MEMORY, the Moeller-Trumbore intersection test is used instead, which doesn't need any extra storage. However, it also tends to be quite a bit slower.

See Also: GenericKDTree

Constructor & Destructor Documentation

mitsuba::ShapeKDTree::ShapeKDTree ( )

Create an empty kd-tree.

virtual mitsuba::ShapeKDTree::~ShapeKDTree ( )

protectedvirtual

Virtual destructor.

Member Function Documentation

void mitsuba::ShapeKDTree::addShape ( const Shape * shape )

Add a shape to the kd-tree.

void mitsuba::ShapeKDTree::build ( )

Build the kd-tree (needs to be called before tracing any rays)

template<bool BarycentricPos>

FINLINE void mitsuba::ShapeKDTree::fillIntersectionRecord	(	const Ray &	ray,
		const void *	temp,
		Intersection &	its
	)		const

inlineprotected

After having found a unique intersection, fill a proper record using the temporary information collected in intersect()

FINLINE IndexType mitsuba::ShapeKDTree::findShape ( IndexType & idx ) const

inlineprotected

Return the shape index corresponding to a primitive index seen by the generic kd-tree implementation.

When this is a triangle mesh, the idx parameter is updated to the triangle index within the mesh.

const AABB& mitsuba::ShapeKDTree::getAABB ( ) const

inline

Return an axis-aligned bounding box containing all primitives.

FINLINE AABB mitsuba::ShapeKDTree::getAABB ( IndexType idx ) const

inlineprotected

Return the axis-aligned bounding box of a certain primitive.

virtual const Class* mitsuba::ShapeKDTree::getClass ( ) const

virtual

Retrieve this object's class.

Reimplemented from mitsuba::KDTreeBase< AABB >.

FINLINE AABB mitsuba::ShapeKDTree::getClippedAABB	(	IndexType	idx,
		const AABB &	aabb
	)		const

inlineprotected

Return the AABB of a primitive when clipped to another AABB.

SizeType mitsuba::ShapeKDTree::getPrimitiveCount ( ) const

inline

Return the total number of low-level primitives (triangles and other low-level primitives)

const std::vector<const Shape *>& mitsuba::ShapeKDTree::getShapes ( ) const

inline

Return the list of stored shapes.

FINLINE bool mitsuba::ShapeKDTree::intersect	(	const Ray &	ray,
		IndexType	idx,
		Float	mint,
		Float	maxt,
		Float &	t,
		void *	temp
	)		const

inlineprotected

Check whether a primitive is intersected by the given ray. Some temporary space is supplied to store data that can later be used to create a detailed intersection record.

FINLINE bool mitsuba::ShapeKDTree::intersect	(	const Ray &	ray,
		IndexType	idx,
		Float	mint,
		Float	maxt
	)		const

inlineprotected

Check whether a primitive is intersected by the given ray. This version is used for shadow rays, hence no temporary space is supplied.

bool mitsuba::ShapeKDTree::rayIntersect	(	const Ray &	ray,
		Intersection &	its
	)		const

Intersect a ray against all primitives stored in the kd-tree and return detailed intersection information.

Parameters

ray	A 3-dimensional ray data structure with minimum/maximum extent information, as well as a time (which applies when the shapes are animated)
its	A detailed intersection record, which will be filled by the intersection query

Returns: true if an intersection was found

bool mitsuba::ShapeKDTree::rayIntersect	(	const Ray &	ray,
		Float &	t,
		ConstShapePtr &	shape,
		Normal &	n,
		Point2 &	uv
	)		const

Intersect a ray against all primitives stored in the kd-tree and return the traveled distance and intersected shape.

This function represents a performance compromise when the intersected shape must be known, but there is no need for a detailed intersection record.

Parameters

ray	A 3-dimensional ray data structure with minimum/maximum extent information, as well as a time (which applies when the shapes are animated)
t	The traveled ray distance will be stored in this parameter
shape	A pointer to the intersected shape will be stored in this parameter
n	The geometric surface normal will be stored in this parameter
uv	The UV coordinates associated with the intersection will be stored here.

Returns: true if an intersection was found

bool mitsuba::ShapeKDTree::rayIntersect ( const Ray & ray ) const

Test a ray for occlusion with respect to all primitives stored in the kd-tree.

This function does not compute a detailed intersection record, and it never determines the closest intersection, which makes it quite a bit faster than the other two rayIntersect() methods. However, for this reason, it can only be used to check whether there is any occlusion along a ray or ray segment.

Parameters

ray	A 3-dimensional ray data structure with minimum/maximum extent information, as well as a time (which applies when the shapes are animated)

Returns: true if there is occlusion

bool mitsuba::ShapeKDTree::rayIntersect	(	const Ray &	ray,
		Float	_mint,
		Float	_maxt
	)		const

inlineprotected

Plain shadow ray query (used by the 'instance' plugin)

bool mitsuba::ShapeKDTree::rayIntersect	(	const Ray &	ray,
		Float	_mint,
		Float	_maxt,
		Float &	t,
		void *	temp
	)		const

inlineprotected

Plain intersection query (used by the 'instance' plugin)

Friends And Related Function Documentation

friend class AnimatedInstance

friend

friend class GenericKDTree< AABB, SurfaceAreaHeuristic3, ShapeKDTree >

friend

friend class Instance

friend

friend class SAHKDTree3D< ShapeKDTree >

friend

friend class SingleScatter

friend

Member Data Documentation

Class* mitsuba::ShapeKDTree::m_theClass

static

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

include/mitsuba/render/skdtree.h

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation