rcrt::SAHKDtree< T > Class Template Reference

#include <SAHKDtree.hpp>

Inheritance diagram for rcrt::SAHKDtree< T >:

[legend]

Collaboration diagram for rcrt::SAHKDtree< T >:

[legend]

List of all members.

Public Types
typedef std::vector < T * >::iterator	vecTIter
typedef std::vector < TraceableEntry< T > * >::iterator	vecTEIter
typedef std::list < PlanarEvent< T > >::iterator	listPEIter
Public Member Functions
	S ()
	S (std::vector< T * > *trList, int depth=40, int lSize=2)
virtual	~SAHKDtree ()
Intersection	intersect (Ray &r) const
Intersection	intersectNode (KDNode< T > *n, Ray &r) const
const AABB &	getBoundingBox () const
const Point3D &	getCentroid () const
void	setTraceables (std::vector< T * > *trList)
void	buildTree (std::vector< T * > *trList)
KDNode< T > *	buildNode (AABB &nbox, std::vector< TraceableEntry< T > * > trList, std::list< PlanarEvent< T > > *eventList, unsigned int depth)
KDNode< T > *	buildLeaf (std::vector< TraceableEntry< T > * > trList)
void	createPlanarEvents (TraceableEntry< T > *trEntry, std::list< PlanarEvent< T > > *eventList, AABB tbbox)
void	createPlanarEvents (TraceableEntry< T > *trEntry, std::list< PlanarEvent< T > > *eventList)
float	C (float &Pl, float &Pr, int Nl, int Nr)
float	SAH (PlanarEvent< T > *p, AABB &V, int &Nl, int &Nr, int &Np)
AABB	clipBox (AABB &cbox) const
Static Public Member Functions
static bool	planarEventCompare (PlanarEvent< T > &a, PlanarEvent< T > &b)
static AABB	calcBoundingBox (std::vector< T * > *trList)
static Axis	intToAxis (int i)
Private Attributes
KDNode< T > *	root
AABB	bbox
unsigned int	maxDepth
unsigned int	leafSize

---

Detailed Description

template<class T>
class rcrt::SAHKDtree< T >

SAH KD Tree - implementation of Wald's O(n log n) building method

Definition at line 101 of file SAHKDtree.hpp.

---

Member Typedef Documentation

template<class T>

typedef std::vector< T* >::iterator rcrt::SAHKDtree< T >::vecTIter

Definition at line 123 of file SAHKDtree.hpp.

template<class T>

typedef std::vector<TraceableEntry<T>* >::iterator rcrt::SAHKDtree< T >::vecTEIter

Definition at line 124 of file SAHKDtree.hpp.

template<class T>

typedef std::list<PlanarEvent<T> >::iterator rcrt::SAHKDtree< T >::listPEIter

Definition at line 125 of file SAHKDtree.hpp.

---

Constructor & Destructor Documentation

template<class T>

virtual rcrt::SAHKDtree< T >::~SAHKDtree

(

)

[inline, virtual]

Definition at line 119 of file SAHKDtree.hpp.

---

Member Function Documentation

template<class T>

rcrt::SAHKDtree< T >::S

(

)

[inline]

template<class T>

rcrt::SAHKDtree< T >::S	(	std::vector< T * > *	trList,
		int	depth = 40,
		int	lSize = 2
	)			[inline]

template<class T>

Intersection rcrt::SAHKDtree< T >::intersect

(

Ray &

r

)

const [inline, virtual]

Intersect a given ray with the tree.

Parameters:

r

the Ray to be traced

Returns:

the intersection

Implements rcrt::Traceable.

Definition at line 133 of file SAHKDtree.hpp.

template<class T>

Intersection rcrt::SAHKDtree< T >::intersectNode	(	KDNode< T > *	n,
		Ray &	r
	)			const [inline]

Intersecta given ray with a node.

Parameters:

	n	the Node to be intersected
	r	the Ray to be traced

Returns:

the intersection

Definition at line 151 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::intersect(), and rcrt::SAHKDtree< rcrt::Triangle >::intersectNode().

template<class T>

const AABB& rcrt::SAHKDtree< T >::getBoundingBox

(

)

const [inline, virtual]

Returns:

The minimum Axis-Aligned Bounding Box of this Traceable.

Implements rcrt::Traceable.

Definition at line 201 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::clipBox().

template<class T>

const Point3D& rcrt::SAHKDtree< T >::getCentroid

(

)

const [inline, virtual]

Returns:

Some kind of central point of this object. This may just be an approximation (e.g. the central point of the AABB).

Implements rcrt::Traceable.

Definition at line 206 of file SAHKDtree.hpp.

template<class T>

void rcrt::SAHKDtree< T >::setTraceables

(

std::vector< T * > *

trList

)

[inline]

Definition at line 211 of file SAHKDtree.hpp.

template<class T>

void rcrt::SAHKDtree< T >::buildTree

(

std::vector< T * > *

trList

)

[inline]

Build SAH KD-Tree of a list of primitives.

Parameters:

trList

vector of Traceables

Definition at line 220 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::setTraceables().

template<class T>

KDNode<T>* rcrt::SAHKDtree< T >::buildNode	(	AABB &	nbox,
		std::vector< TraceableEntry< T > * >	trList,
		std::list< PlanarEvent< T > > *	eventList,
		unsigned int	depth
	)			[inline]

Build SAH KD-Node.

Parameters:

	nbox	bounding box of the node to be built
	trList	vector of Traceables
	eventList	list of split events for this node
	depth	local depth of th KD Tree

Returns:

the node

Definition at line 258 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode(), and rcrt::SAHKDtree< rcrt::Triangle >::buildTree().

template<class T>

KDNode<T>* rcrt::SAHKDtree< T >::buildLeaf

(

std::vector< TraceableEntry< T > * >

trList

)

[inline]

Build leaf node of given primitives

Parameters:

trList

vector of Traceables

Returns:

the leaf node

Definition at line 480 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode().

template<class T>

static bool rcrt::SAHKDtree< T >::planarEventCompare	(	PlanarEvent< T > &	a,
		PlanarEvent< T > &	b
	)			[inline, static]

Compares two PlanarEvents (a < b)

Parameters:

	a	event a
	b	event b return a<b

Definition at line 513 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode(), and rcrt::SAHKDtree< rcrt::Triangle >::buildTree().

template<class T>

void rcrt::SAHKDtree< T >::createPlanarEvents	(	TraceableEntry< T > *	trEntry,
		std::list< PlanarEvent< T > > *	eventList,
		AABB	tbbox
	)			[inline]

Create split events for a given primitive and bounding box

Parameters:

	trEntry	TraceableEntry that contains the primitive the events are created for
	eventList	list of events the generated events are added to
	tbbox	bounding box that defines the boundaries of the new events

Definition at line 526 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode(), rcrt::SAHKDtree< rcrt::Triangle >::buildTree(), and rcrt::SAHKDtree< rcrt::Triangle >::createPlanarEvents().

template<class T>

void rcrt::SAHKDtree< T >::createPlanarEvents	(	TraceableEntry< T > *	trEntry,
		std::list< PlanarEvent< T > > *	eventList
	)			[inline]

Definition at line 564 of file SAHKDtree.hpp.

template<class T>

float rcrt::SAHKDtree< T >::C	(	float &	Pl,
		float &	Pr,
		int	Nl,
		int	Nr
	)			[inline]

Calculate the cost of a split candidate

Parameters:

	probability	for hitting the left volume
	probability	for hitting the right volume
	number	of primitives in left volume
	number	of primitives in right volume

Returns:

cost

Definition at line 580 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::SAH().

template<class T>

float rcrt::SAHKDtree< T >::SAH	(	PlanarEvent< T > *	p,
		AABB &	V,
		int &	Nl,
		int &	Nr,
		int &	Np
	)			[inline]

Calculate the SAH for a given split candidate and determine where to put primitives lying in the split plane

Parameters:

	p	split event for split candidate
	number	of primitives left of the split plane
	number	of primitives right of the split plane
	number	of primitives in the split plane

Returns:

minimal cost of the split plane

Definition at line 597 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode().

template<class T>

static AABB rcrt::SAHKDtree< T >::calcBoundingBox

(

std::vector< T * > *

trList

)

[inline, static]

Calculate the bounding box surrounding all primitives in a given list

Parameters:

vector

of Traceables

Returns:

the bounding box

Definition at line 629 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildTree().

template<class T>

AABB rcrt::SAHKDtree< T >::clipBox

(

AABB &

cbox

)

const [inline]

Definition at line 638 of file SAHKDtree.hpp.

template<class T>

static Axis rcrt::SAHKDtree< T >::intToAxis

(

int

i

)

[inline, static]

Convert integer to axis

Parameters:

i

the int

Returns:

the axis

Definition at line 648 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode(), and rcrt::SAHKDtree< rcrt::Triangle >::createPlanarEvents().

---

Member Data Documentation

template<class T>

KDNode<T>* rcrt::SAHKDtree< T >::root [private]

Definition at line 104 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildTree(), and rcrt::SAHKDtree< rcrt::Triangle >::intersect().

template<class T>

AABB rcrt::SAHKDtree< T >::bbox [private]

Definition at line 105 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildTree(), rcrt::SAHKDtree< rcrt::Triangle >::getBoundingBox(), rcrt::SAHKDtree< rcrt::Triangle >::getCentroid(), and rcrt::SAHKDtree< rcrt::Triangle >::intersect().

template<class T>

unsigned int rcrt::SAHKDtree< T >::maxDepth [private]

Definition at line 106 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode().

template<class T>

unsigned int rcrt::SAHKDtree< T >::leafSize [private]

Definition at line 106 of file SAHKDtree.hpp.

Referenced by rcrt::SAHKDtree< rcrt::Triangle >::buildNode().

---

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

• src/rcrt/SAHKDtree.hpp

---