Grayfall: SAHKDTree Class Reference

typedef std::vector<Event> SAHKDTree::EventList [private]

Definition at line 50 of file SAHKDTree.h.

SAHKDTree::SAHKDTree	(	float	lambda = `0.8f`,
		float	kTraversal = `5.0f`,
		float	kIntersect = `1.0f`
	)			`[inline]`

Constructor. All parameters are initialized with good default values

Parameters:

	lambda	Bias factor for cost function to favor empty nodes
	kTraversal	Relative node traversal cost factor
	kIntersect	Relative primitive intersection cost factor

Definition at line 26 of file SAHKDTree.h.

SAHKDTree::~SAHKDTree ( ) [virtual]

Destructor

Definition at line 14 of file SAHKDTree.cpp.

void SAHKDTree::buildTree	(	const PrimitiveList &	list,
		const Box &	bbox
	)			`[virtual]`

Build the kd-tree from the given primitive list.

Parameters:

	list	List of all primitives
	bbox	Overall bounding box

Definition at line 24 of file SAHKDTree.cpp.

References KDTree::buildTree(), generateEvents(), LOG, and KDTree::mRootNode.

Referenced by buildTree().

void SAHKDTree::buildTree	(	Node *	node,
		const Box &	bbox,
		EventList &	events,
		unsigned int	depth
	)			const `[private]`

Recursive tree building method

Parameters:

	node	Current parent node
	bbox	Bounding box of the node
	events	Event list for the node. Should be sorted.
	depth	Current node depth

Definition at line 52 of file SAHKDTree.cpp.

References buildTree(), classifyAndSplice(), Node::clear_primitives(), SplitPlane::direction(), findBestPlane(), Node::left(), NO_AXIS, SplitPlane::position(), Node::right(), Node::setLeftRight(), Node::setSplitAxis(), Node::setSplitPlane(), and terminate().

bool SAHKDTree::terminate	(	const Node *	current,
		float	minCost,
		unsigned int	depth
	)			const `[private, virtual]`

Determine if building tree should terminate on the current node. This implementation uses tree depth and minimal primitive count constraints, as well as adaptive cost-based termination criterion.

Parameters:

	current	Current node
	minCost	Minimal traversal cost for current node
	depth	Depth of the current node

Returns:: true if current node should become leaf node

Reimplemented from KDTree.

Definition at line 114 of file SAHKDTree.cpp.

References mKIntersect, Node::primitives_count(), and KDTree::terminate().

Referenced by buildTree().

float SAHKDTree::cost	(	float	probability_left,
		float	probability_right,
		unsigned int	number_left,
		unsigned int	number_right
	)			const `[inline, private]`

Estimate cost of a node with surface area heuristic

Parameters:

	probability_left	Probability, that left node will be hit
	probability_right	Probability, that right node will be hit
	number_left	Number of primitives in the left node
	number_right	Number of primitives in the right node

Returns:: Cost factor

Definition at line 98 of file SAHKDTree.h.

References mKIntersect, mKTraversal, and mLambda.

Referenced by findBestPlane(), and SAH().

float SAHKDTree::SAH	(	Side &	side,
		const Box &	bbox,
		const SplitPlane &	plane,
		unsigned int	number_left,
		unsigned int	number_right,
		unsigned int	number_middle
	)			const `[private]`

Surface area heuristic based cost estimation.

Parameters:

	side	Output parameter. Side where to put primitives hit by split plane
	bbox	Bounding box of given node
	plane	Split plane to calculate costs for
	number_left	Number of primitives left of the plane
	number_right	Number of primitives hit by the plane
	number_middle	Number of primitives right of the plane

Returns:: Minimal cost and side where to put primitives to achieve it

Definition at line 133 of file SAHKDTree.cpp.

References Box::area(), cost(), S_LEFT, and S_RIGHT.

Referenced by findBestPlane().

SplitPlane SAHKDTree::findBestPlane	(	float &	minCost,
		const Node *	node,
		const Box &	bbox,
		const EventList &	events
	)			const `[private]`

Find best plane for the next split in O(N). Event list should be sorted before calling this method.

Parameters:

	minCost	Output parameter. Minimal cost for splitting given node
	node	Node to find the best split plane for
	bbox	Bounding box of the node
	events	Presorted event list for the node

Returns:: Best split plane and minimal cost

Definition at line 169 of file SAHKDTree.cpp.

References cost(), SplitPlane::direction(), EPSILON, ET_END, ET_PLANAR, ET_START, Box::maxVertex(), Box::minVertex(), SplitPlane::position(), Node::primitives_count(), SAH(), and SplitPlane::setSide().

Referenced by buildTree().

std::pair< Box, Box > SAHKDTree::classifyAndSplice	(	EventList &	eLeft,
		EventList &	eRight,
		Node *	node,
		const Box &	bbox,
		const EventList &	events,
		const SplitPlane &	plane
	)			const `[private]`

Classify primitives to be either left of, right of, or overlapping given plane in a single sweep over event list, then generate event lists and primitive lists for children.

Parameters:

	eLeft	Output parameter. Event list of the left child
	eRight	Output parameter. Event list of the right child
	node	Current node
	bbox	Bounding box of the current node
	events	Event list of the current node
	plane	Split plane to split with

Returns:: Bounding boxes of child nodes

Definition at line 291 of file SAHKDTree.cpp.

References Node::add(), SplitPlane::direction(), ET_END, ET_PLANAR, ET_START, generateEvents(), Node::left(), SplitPlane::position(), Node::primitive(), Node::primitives_count(), Node::right(), S_BOTH, S_LEFT, S_RIGHT, SplitPlane::side(), and Box::split().

Referenced by buildTree().

void SAHKDTree::generateEvents	(	EventList &	events,
		Primitive *	primitive,
		const Box &	bbox
	)			const `[private]`

Generate events for all dimensions and add them to the list

Parameters:

	events	Output parameter. List ov events to add new events to
	primitive	Primitive to generate events for
	bbox	Bounding box to clip primitive to

Definition at line 258 of file SAHKDTree.cpp.

References Primitive::bounds(), Box::clip(), EPSILON, ET_END, ET_PLANAR, ET_START, Box::maxVertex(), and Box::minVertex().

Referenced by buildTree(), and classifyAndSplice().

const float SAHKDTree::mLambda [private]

Lambda factor for biasing the cost function.

Definition at line 54 of file SAHKDTree.h.

Referenced by cost().

const float SAHKDTree::mKTraversal [private]

Traversal cost factor.

Definition at line 57 of file SAHKDTree.h.

Referenced by cost().

const float SAHKDTree::mKIntersect [private]

Intersection cost factor.

Definition at line 60 of file SAHKDTree.h.

Referenced by cost(), and terminate().


Public Member Functions
	SAHKDTree (float lambda=0.8f, float kTraversal=5.0f, float kIntersect=1.0f)
virtual	~SAHKDTree ()
virtual void	buildTree (const PrimitiveList &list, const Box &bbox)
Private Types
typedef std::vector< Event >	EventList
	Event list.
Private Member Functions
void	buildTree (Node *node, const Box &bbox, EventList &events, unsigned int depth) const
virtual bool	terminate (const Node *current, float minCost, unsigned int depth) const
float	cost (float probability_left, float probability_right, unsigned int number_left, unsigned int number_right) const
float	SAH (Side &side, const Box &bbox, const SplitPlane &plane, unsigned int number_left, unsigned int number_right, unsigned int number_middle) const
SplitPlane	findBestPlane (float &minCost, const Node *node, const Box &bbox, const EventList &events) const
std::pair< Box, Box >	classifyAndSplice (EventList &eLeft, EventList &eRight, Node *node, const Box &bbox, const EventList &events, const SplitPlane &plane) const
void	generateEvents (EventList &events, Primitive *primitive, const Box &bbox) const
Private Attributes
const float	mLambda
	Lambda factor for biasing the cost function.
const float	mKTraversal
	Traversal cost factor.
const float	mKIntersect
	Intersection cost factor.

SAHKDTree Class Reference

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation