KDTree Class Reference

#include <KDTree.h>

---

Detailed Description

The main acceleration structure.

This class is responsible for building a KDTree according to SAH (Surface Area Heuristic). The kd-Tree is a binary tree, where each interior node always has both children and where leaves of the tree sorte the primitives that overlap them.

Definition at line 22 of file KDTree.h.

Public Member Functions
bool	Intersect (Ray &ray)
void	BuildTree (const std::vector< Primitive * > &list, const Box &bbox)
	Builds the kd-tree according to SAH.
	KDTree ()
	The constructor of the tree.
	~KDTree ()
	The destructor of the tree.
Data Fields
Box	_boundingBox
	The boundingbox of the whole tree.
Private Types
enum	Axis { X_AXIS = 0, Y_AXIS = 1, Z_AXIS = 2, NO_AXIS = 3 }
	An enum that stands for the X/Y/Z Axis. More...
Private Member Functions
bool	Intersect (KDNode *node, Ray &ray, float min, float max)
void	BuildTree (KDNode *node, const Box &nodeBounds, int depth, int badRefines)
void	retrySplit (KDNode *node, Box nodeBounds, Axis &bestAxis, float &bestCost, int &bestOffset, int retries)
Private Attributes
int	_maxPrimitives
	The maximal number of primitives in one leaf node.
int	_maxDepth
	The maximal depth of the tree.
KDNode *	_root
	The root node of the tree.
int	_isectCost
int	_traversalCost
	The traversal cost used by SAH.
float	_emptyBonus
	A "bonus"-value used by SAH.
BoundEdge *	_edges [3]
	A Projection of the boundingboxes onto the x, y and z axis.
Data Structures
struct	BoundEdge
	THE projection of an boundingBox onto an axis. More...
class	KDNode
	The internal node structur of the KDTree. More...
class	KDNodeSmall

---

Member Enumeration Documentation

enum KDTree::Axis [private]

An enum that stands for the X/Y/Z Axis.

Enumerator:

X_AXIS
Y_AXIS
Z_AXIS
NO_AXIS

Definition at line 28 of file KDTree.h.

---

Constructor & Destructor Documentation

KDTree::KDTree

(

)

The constructor of the tree.

Definition at line 50 of file KDTree.cpp.

References _emptyBonus, _isectCost, _maxPrimitives, _root, and _traversalCost.

KDTree::~KDTree

(

)

The destructor of the tree.

Definition at line 59 of file KDTree.cpp.

References _root.

---

Member Function Documentation

bool KDTree::Intersect	(	KDNode *	node,
		Ray &	ray,
		float	min,
		float	max
	)			[private]

Definition at line 77 of file KDTree.cpp.

References KDTree::KDNode::distanceToSplitPlane(), KDTree::KDNode::getNearFar(), KDTree::KDNode::isLeafNode(), and KDTree::KDNode::leafIntersect().

Referenced by Object::Intersect(), Intersect(), KDTree::KDNode::leafIntersect(), and Object::Occluded().

void KDTree::BuildTree	(	KDNode *	node,
		const Box &	nodeBounds,
		int	depth,
		int	badRefines
	)			[private]

Definition at line 118 of file KDTree.cpp.

References _edges, _isectCost, KDTree::KDNode::_left, _maxDepth, KDTree::KDNode::_primitives, KDTree::KDNode::_right, KDTree::KDNode::_splitAxis, KDTree::KDNode::_splitPlane, KDTree::BoundEdge::END, Box::max, Box::min, NO_AXIS, KDTree::BoundEdge::primNum, retrySplit(), KDTree::BoundEdge::START, and KDTree::BoundEdge::t.

Referenced by Object::BuildAccelStructure(), and BuildTree().

void KDTree::retrySplit	(	KDNode *	node,
		Box	nodeBounds,
		Axis &	bestAxis,
		float &	bestCost,
		int &	bestOffset,
		int	retries
	)			[private]

Definition at line 187 of file KDTree.cpp.

References _edges, _emptyBonus, _isectCost, KDTree::KDNode::_primitives, _traversalCost, KDTree::BoundEdge::END, Box::max, Box::min, NO_AXIS, KDTree::BoundEdge::START, KDTree::BoundEdge::t, Vector3D::x(), X_AXIS, Vector3D::y(), Y_AXIS, Vector3D::z(), and Z_AXIS.

Referenced by BuildTree().

bool KDTree::Intersect

(

Ray &

ray

)

Definition at line 64 of file KDTree.cpp.

References _boundingBox, _root, Epsilon, Intersect(), and Box::Intersect().

void KDTree::BuildTree	(	const std::vector< Primitive * > &	list,
		const Box &	bbox
	)

Builds the kd-tree according to SAH.

Parameters:

	list	The list of primitives used to build the tree.
	bbox	The union of all boundingboxes of the primitive list.

Definition at line 250 of file KDTree.cpp.

References _boundingBox, _edges, _maxDepth, _maxPrimitives, KDTree::KDNode::_primitives, _root, and BuildTree().

---

Field Documentation

int KDTree::_maxPrimitives [private]

The maximal number of primitives in one leaf node.

Definition at line 282 of file KDTree.h.

Referenced by BuildTree(), and KDTree().

int KDTree::_maxDepth [private]

The maximal depth of the tree.

Definition at line 288 of file KDTree.h.

Referenced by BuildTree().

KDNode * KDTree::_root [private]

The root node of the tree.

Definition at line 294 of file KDTree.h.

Referenced by BuildTree(), Intersect(), KDTree(), and ~KDTree().

int KDTree::_isectCost [private]

Definition at line 300 of file KDTree.h.

Referenced by BuildTree(), KDTree(), and retrySplit().

int KDTree::_traversalCost [private]

The traversal cost used by SAH.

Definition at line 306 of file KDTree.h.

Referenced by KDTree(), and retrySplit().

float KDTree::_emptyBonus [private]

A "bonus"-value used by SAH.

Definition at line 312 of file KDTree.h.

Referenced by KDTree(), and retrySplit().

BoundEdge * KDTree::_edges[3] [private]

A Projection of the boundingboxes onto the x, y and z axis.

To compute the cost used by the SAH, we will sweep around these projections and keep track of which gives the lowest cost.

Definition at line 321 of file KDTree.h.

Referenced by BuildTree(), and retrySplit().

Box KDTree::_boundingBox

The boundingbox of the whole tree.

Definition at line 361 of file KDTree.h.

Referenced by BuildTree(), and Intersect().

---

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

• /Users/sw/uni/computer graphics/macsrt/librt/KDTree.h
• /Users/sw/uni/computer graphics/macsrt/librt/KDTree.cpp

---