Mitsuba Renderer  0.5.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
mitsuba::SAHKDTree2D< Derived > Class Template Reference

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

#include <mitsuba/render/sahkdtree2.h>

+ Inheritance diagram for mitsuba::SAHKDTree2D< Derived >:

Classes

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

Public Types

typedef GenericKDTree< AABB2,
SurfaceAreaHeuristic2, Derived > 
Parent
 
typedef KDTreeBase< AABB2 >
::SizeType 
SizeType
 
typedef KDTreeBase< AABB2 >
::IndexType 
IndexType
 
typedef KDTreeBase< AABB2 >::KDNode KDNode
 
- Public Types inherited from mitsuba::GenericKDTree< AABB2, SurfaceAreaHeuristic2, Derived >
typedef KDTreeBase< AABB2Parent
 
typedef Parent::SizeType SizeType
 
typedef Parent::IndexType IndexType
 
typedef Parent::KDNode KDNode
 
typedef AABB2::Scalar Scalar
 
typedef AABB2::PointType PointType
 
typedef AABB2::VectorType VectorType
 
- Public Types inherited from mitsuba::KDTreeBase< AABB2 >
typedef uint32_t IndexType
 Index number format (max 2^32 prims) More...
 
typedef uint32_t SizeType
 Size number format. 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...
 
FINLINE bool rayIntersectHavran (const Ray2 &ray, Float mint, Float maxt, Float &t, void *temp) const
 Ray tracing kd-tree traversal loop (Havran variant) More...
 
- Protected Member Functions inherited from mitsuba::GenericKDTree< AABB2, SurfaceAreaHeuristic2, 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 AABB2 &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 AABB2 &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 AABB2 &nodeAABB, const AABB2 &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 AABB2 &nodeAABB, EdgeEvent *eventStart, EdgeEvent *eventEnd, SizeType primCount, bool isLeftChild, SizeType badRefines)
 
- Protected Member Functions inherited from mitsuba::KDTreeBase< AABB2 >
virtual ~KDTreeBase ()
 
- Protected Member Functions inherited from Object
virtual ~Object ()
 Virtual private deconstructor. (Will only be called by ref) More...
 

Additional Inherited Members

- Public Member Functions inherited from mitsuba::GenericKDTree< AABB2, SurfaceAreaHeuristic2, 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...
 
IndexTypegetIndices () 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< AABB2 >
 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 AABB2getAABB () const
 Return a (slightly enlarged) axis-aligned bounding box containing all primitives. More...
 
const AABB2getTightAABB () const
 Return a tight axis-aligned bounding box containing all primitives. More...
 
virtual const ClassgetClass () 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...
 
- 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< AABB2 >
static Classm_theClass
 
- Static Public Attributes inherited from Object
static Classm_theClass
 Pointer to the object's class descriptor. More...
 
- Protected Types inherited from mitsuba::GenericKDTree< AABB2, SurfaceAreaHeuristic2, Derived >
enum  EClassificationResult
 Primitive classification during tree-construction. More...
 
- Protected Attributes inherited from mitsuba::GenericKDTree< AABB2, SurfaceAreaHeuristic2, Derived >
IndexTypem_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< Mutexm_indirectionLock
 
BuildInterface m_interface
 
- Protected Attributes inherited from mitsuba::KDTreeBase< AABB2 >
KDNode * m_nodes
 
ELogLevel m_logLevel
 
AABB2 m_aabb
 
AABB2 m_tightAABB
 

Detailed Description

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

Specializes GenericKDTree to a two-dimensional tree to be used for flatland 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 Ray2 &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<AABB2>::IndexType mitsuba::SAHKDTree2D< Derived >::IndexType
template<typename Derived >
typedef KDTreeBase<AABB2>::KDNode mitsuba::SAHKDTree2D< Derived >::KDNode
template<typename Derived >
typedef GenericKDTree<AABB2, SurfaceAreaHeuristic2, Derived> mitsuba::SAHKDTree2D< Derived >::Parent
template<typename Derived >
typedef KDTreeBase<AABB2>::SizeType mitsuba::SAHKDTree2D< Derived >::SizeType

Member Function Documentation

template<typename Derived >
void mitsuba::SAHKDTree2D< Derived >::buildInternal ( )
inlineprotected
template<typename Derived >
Derived* mitsuba::SAHKDTree2D< Derived >::cast ( )
inlineprotected

Cast to the derived class.

template<typename Derived >
const Derived* mitsuba::SAHKDTree2D< Derived >::cast ( ) const
inlineprotected

Cast to the derived class (const version)

template<typename Derived >
FINLINE bool mitsuba::SAHKDTree2D< Derived >::rayIntersectHavran ( const Ray2 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.


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