Specializes GenericKDTree to a three-dimensional tree to be used for ray tracing. More...

#include <mitsuba/render/sahkdtree3.h>

Inheritance diagram for mitsuba::SAHKDTree3D< Derived >:

Classes
struct	HashedMailbox
	Hashed mailbox implementation. More...

struct	KDStackEntry
	Ray traversal stack entry for Wald-style incoherent ray tracing. More...

struct	KDStackEntryHavran
	Ray traversal stack entry for Havran-style incoherent ray tracing. More...

struct	RayStatistics

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

Public Member Functions
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...

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

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< AABB >
static Class *	m_theClass

Static Public Attributes inherited from Object
static Class *	m_theClass
	Pointer to the object's class descriptor. 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

template<typename Derived>
class mitsuba::SAHKDTree3D< Derived >

Specializes GenericKDTree to a three-dimensional tree to be used for ray tracing.

One additional function call must be implemented by subclasses:

/// Check whether a primitive is intersected by the given ray.
/// Some temporary space is supplied, which can be used to cache
/// information about the intersection
bool intersect(const Ray &ray, IndexType idx,
    Float mint, Float maxt, Float &t, void *tmp);

This class implements an epsilon-free version of the optimized ray traversal algorithm (TA^B_{rec}), which is explained in Vlastimil Havran's PhD thesis "Heuristic Ray Shooting Algorithms".

Author: Wenzel Jakob

Member Typedef Documentation

template<typename Derived>

typedef KDTreeBase<AABB>::IndexType mitsuba::SAHKDTree3D< Derived >::IndexType

template<typename Derived>

typedef KDTreeBase<AABB>::KDNode mitsuba::SAHKDTree3D< Derived >::KDNode

template<typename Derived>

typedef GenericKDTree<AABB, SurfaceAreaHeuristic3, Derived> mitsuba::SAHKDTree3D< Derived >::Parent

template<typename Derived>

typedef KDTreeBase<AABB>::SizeType mitsuba::SAHKDTree3D< Derived >::SizeType

Member Function Documentation

template<typename Derived>

void mitsuba::SAHKDTree3D< Derived >::buildInternal ( )

inlineprotected

template<typename Derived>

Derived* mitsuba::SAHKDTree3D< Derived >::cast ( )

inlineprotected

Cast to the derived class.

template<typename Derived>

const Derived* mitsuba::SAHKDTree3D< Derived >::cast ( ) const

inlineprotected

Cast to the derived class (const version)

template<typename Derived>

void mitsuba::SAHKDTree3D< Derived >::findCosts	(	Float &	traversalCost,
		Float &	intersectionCost
	)

inline

Empirically find the best traversal and intersection cost values.

This is done by running the traversal code on random rays and fitting the SAH cost model to the collected statistics.

template<typename Derived>

template<bool shadowRay>

FINLINE bool mitsuba::SAHKDTree3D< Derived >::rayIntersectHavran	(	const Ray &	ray,
		Float	mint,
		Float	maxt,
		Float &	t,
		void *	temp
	)		const

inlineprotected

Ray tracing kd-tree traversal loop (Havran variant)

This is generally the most robust and fastest traversal routine of the methods implemented in this class.

template<typename Derived>

FINLINE RayStatistics mitsuba::SAHKDTree3D< Derived >::rayIntersectHavranCollectStatistics	(	const Ray &	ray,
		Float	mint,
		Float	maxt,
		Float &	t,
		void *	temp
	)		const

inlineprotected

Internal kd-tree traversal implementation (Havran variant)

This method is almost identical to rayIntersectHavran, except that it additionally returns statistics on the number of traversed nodes, intersected shapes, as well as the time taken to do this (measured using rtdsc).

template<typename Derived>

template<bool shadowRay>

FINLINE bool mitsuba::SAHKDTree3D< Derived >::rayIntersectPBRT	(	const Ray &	ray,
		Float	mint_,
		Float	maxt_,
		Float &	t,
		void *	temp
	)		const

inlineprotected

Ray tracing kd-tree traversal loop (PBRT variant)

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

include/mitsuba/render/sahkdtree3.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

template<typename Derived> class mitsuba::SAHKDTree3D< Derived >

Member Typedef Documentation

Member Function Documentation

template<typename Derived>
class mitsuba::SAHKDTree3D< Derived >