GPU-based kd-tree implementation abstract base class. More...

#include <KDTreeGPU.h>

Inheritance diagram for KDTreeGPU:

Public Member Functions
	KDTreeGPU (size_t numInputElems, uint numElementPoints, float3 rootAABBMin, float3 rootAABBMax)
	Initializes this object. To build the tree, call BuildTree().
virtual	~KDTreeGPU (void)
	Destructs this object. Calls Destroy().
bool	BuildTree ()
	Constructs the kd-tree for the elements supplied by subclasses.
virtual void	Destroy ()
	Destroys the kd-tree by releasing both auxiliary structures and final kd-tree data.
KDTreeData *	GetData ()
	Gets final kd-tree data after construction.
void	SetCustomBits (uint bitNo, uint *d_values)
	Sets custom bits within final kd-tree data.
void	SetEmptySpaceRatio (float ratio)
	Sets the empty space ratio ratio used for construction.
float	GetEmptySpaceRatio () const
	Returns the current empty space ratio.
void	SetSmallNodeMax (uint maximum)
	Sets the maximum of elements for small nodes.
uint	GetSmallNodeMax () const
	Returns the current small node element maximum.
void	SetMaxQueryRadius (float radius)
	Sets the maximum query radius.
float	GetMaxQueryRadius () const
	Returns the current maximum query radius.
void	AddListener (KDTreeListener *pListener)
	Registers kd-tree listener.
void	RemoveListener (KDTreeListener *pListener)
	Removes given kd-tree listener from the list of registered listeners.
Protected Member Functions
virtual void	AddRootNode (KDNodeList *pList)=0
	Adds the root node to the given node list.
virtual void	PerformSplitClipping (KDNodeList pListParent, KDNodeList pListChild)
	Performs split clipping for large nodes.
void	CreateChunkList (KDNodeList *pList)
	Fills chunk list m_pChunkList with chunks for the given node list.
virtual void	PreBuild ()
	Initializes auxiliary structures and data.
virtual void	PostBuild ()
	Cleans up auxiliary data after building.
Protected Attributes
KDNodeList *	m_pListActive
	Currently active nodes list.
KDNodeList *	m_pListNext
	Node list for next pass of algorithm.
KDChunkList *	m_pChunkList
	Chunk list used for node AABB calculation and element counting.
float3	m_rootAABBMin
	Root node bounding box minimum supplied by constructor. Not neccessarily tight.
float3	m_rootAABBMax
	Root node bounding box maximum supplied by constructor. Not neccessarily tight.

Detailed Description

GPU-based kd-tree implementation abstract base class.

This class provides a GPU-based kd-tree construction algorithm that can be adapted for different types of kd-trees (e.g. points or triangles as objects) within subclasses. However, this extension possibility is somewhat limited due to problems with the parallel implementation and might need some reworking to allow more types of primitives.

The implementation is based on the work of [Zhou et al. 2008].

This class uses pointers to the concrete elements to store in the kd-tree. These pointers are indices for the array of elements. Within the construction algorithm, the elements are in most cases hidden behind their AABBs. But at some places, e.g. for splitting the nodes, there has to be special treatment depending on the primitive type. Opposed to [Zhou et al. 2008] I limit this special treatment quite a bit to allow both point kd-trees and triangle kd-trees to be a subclass of this class. This was done by introducing the number of element points, which can be 1 or 2, depending on the primitive type. It is used for construction puropses only.

If the number of element points is 1, only one at most four-dimensional point can be used per element. This is enough for a point kd-tree, where each element is just a three-dimensional point. Similarly two four-dimensional points can be stored per element, when the number of element points is set to 2. This is enough for triangle kd-trees as the construction process mainly requires the AABB of the triangles. Special handling like split clipping can be sourced out to the corresponding subclass. This might be extended to other primtive objects as long as they can be represented with at most two element points.

Author:: Mathias Neumann

Date:: 06.02.2010

See also:: KDTreePoint, KDTreeTri

Constructor & Destructor Documentation

KDTreeGPU::KDTreeGPU	(	size_t	numInputElems,
		uint	numElementPoints,
		float3	rootAABBMin,
		float3	rootAABBMax
	)

Initializes this object. To build the tree, call BuildTree().

Root AABB vertices are in most cases available before calling this method. To avoid internal computation, they have to be passed as parameters. The corresponding AABB may be less tight than possible. This can however decrease the performance.

Author:: Mathias Neumann

Date:: 06.02.2010

Parameters:

numInputElems	Number of elements to store within the kd-tree. Note that this removes or at least restricts the ability to dynamically update the tree.
numElementPoints	Number of element points that can be stored for each element of the kd-tree. Only relevant for construction of the tree. Has to be either 1 or 2.
rootAABBMin	Root node AABB minimum vertex.
rootAABBMax	Root node AABB maximum vertex.

KDTreeGPU::~KDTreeGPU ( void ) [virtual]

Destructs this object. Calls Destroy().

Author:: Mathias Neumann

Date:: 06.02.2010

Member Function Documentation

void KDTreeGPU::AddRootNode ( KDNodeList * pList ) [protected, pure virtual]

Adds the root node to the given node list.

This method has to be specified by subclasses. It's responsible for creating and adding the kd-tree root node to the given node list. The concrete implementation has to copy all required data (see KDNodeList) for the root node into the first node list entry. This is usually a host to device copy operation.

Regarding AABBs: It is assumed that the subclass will only initialize the inherited root node bounds. Furthermore the subclass is responsible for calculating and initializing the element points for all root node elements.

Author:: Mathias Neumann

Date:: 02.04.2010

Parameters:

[in,out] pList Node list where the root node should be added. It is assumed that this list is empty.

Implemented in KDTreePoint, and KDTreeTri.

bool KDTreeGPU::BuildTree ( )

Constructs the kd-tree for the elements supplied by subclasses.

The process starts by requesting auxiliary structures (in most cases lists of nodes). After that, the root node is created using AddRootNode(). This step has to be defined by subclasses. Hence the concrete elements have to be supplied by the subclasses. Subsequently, large nodes are processed within the large node stage until no more large nodes are available. Then, within the small node stage, all small nodes are processed.

In both stages, all final nodes are added to a final node list that represents the final kd-tree information. As node ordering in this final node list is somewhat chaotic, a final step is added to layout the tree in a new, more cache friendly way. This is done using a two tree traversals. To avoid high memory consumption, all auxiliary structures used for construction, e.g. lists of intermediate nodes or the chunk list, are destroyed before this method returns.

Author:: Mathias Neumann

Date:: 06.02.2010

Returns:: true if it succeeds, false if it fails.

void KDTreeGPU::CreateChunkList ( KDNodeList * pList ) [protected]

Fills chunk list m_pChunkList with chunks for the given node list.

The creation is only performed when the current chunk list m_pChunkList is not created for the given node list pList. Structurally it might be better to source this out into the KDChunkList type and to allow multiple chunk lists. However, I opted to use a single chunk list as I wanted to reduce memory and time requirements.

Author:: Mathias Neumann

Date:: February 2010

Parameters:

[in] pList The node list for which the current chunk list should be created. May not be NULL.

void KDTreeGPU::Destroy ( void ) [virtual]

Destroys the kd-tree by releasing both auxiliary structures and final kd-tree data.

Subclasses should overwrite this to destroy their own data. In this case, do not forget to call this base class method.

Author:: Mathias Neumann

Date:: 06.02.2010

Reimplemented in KDTreePoint.

KDTreeData * KDTreeGPU::GetData ( ) [inline]

Gets final kd-tree data after construction.

Author:: Mathias Neumann

Date:: February 2010

Returns:: Returns final kd-tree data.

void KDTreeGPU::PerformSplitClipping	(	KDNodeList *	pListParent,
		KDNodeList *	pListChild
	)		`[inline, protected, virtual]`

Performs split clipping for large nodes.

The default implementation does nothing. This is enough for point kd-trees as points have a degenerated AABB that cannot be reduced by clipping the point to a child nodes AABB. But for other element types, e.g. triangles, split clipping can help improving kd-tree quality. Here the element is clipped to the child node bounds and a new element AABB is generated.

Author:: Mathias Neumann.

Date:: April 2010.

Parameters:

[in]	pListParent	The list of parent nodes. This is usually the active list.
[in,out]	pListChild	The list of child nodes that should be updated.

Reimplemented in KDTreeTri.

void KDTreeGPU::PostBuild ( ) [protected, virtual]

Cleans up auxiliary data after building.

This method is called right before BuildTree() returns. It's default implementation is important and subclasses should not forget to call it.

Author:: Mathias Neumann.

Date:: July 2010.

Reimplemented in KDTreePoint.

void KDTreeGPU::PreBuild ( ) [protected, virtual]

Initializes auxiliary structures and data.

This method is called right before BuildTree() performs the actual construction. It's default implementation is important and subclasses should not forget to call it.

Author:: Mathias Neumann

Date:: July 2010

void KDTreeGPU::SetCustomBits	(	uint	bitNo,
		uint *	d_values
	)

Sets custom bits within final kd-tree data.

The final kd-tree's parent information in KDTreeData::d_preorderTree contains two free bits that can be used for custom purposes. I introduced this to mark inner kd-tree nodes without adding a new array. This avoids adding another memory read or texture fetch, e.g. within GPU based traversal algorithms.

Warning:: As this method requires the final kd-tree layout, only call it after building the kd-tree with BuildTree().

Author:: Mathias Neumann.

Date:: September 2010.

Parameters:

	bitNo	Number of the custom bit to manipulate. This can be either 0 or 1, but nothing else.
[in]	d_values	Values for the given custom bit. Has to be an binary array of KDTreeData::numNodes elements, that is only 0 or 1 are allowed as values. Note that the bits for leafs are ignored as leafs have no custom bits!

void KDTreeGPU::SetEmptySpaceRatio ( float ratio ) [inline]

Sets the empty space ratio ratio used for construction.

If at one side of a node's bounding box are at least ratio times the AABB extent at the corresponding axis of free space, the space is cut off in form of an empty node.

Parameters:

ratio The ratio. Has to be a value within [0.0f, 1.0f].

void KDTreeGPU::SetMaxQueryRadius ( float radius ) [inline]

Sets the maximum query radius.

The maximum query radius is required for split cost evaluation, e.g. for the VVH cost evaluation. It's somewhat misplaced here and would better fit into the corresponding subclass.

Parameters:

radius The maximum query radius.

void KDTreeGPU::SetSmallNodeMax ( uint maximum )

Sets the maximum of elements for small nodes.

For performance reasons, larger kd-tree nodes are handled in a different way compared to small nodes, hence there is a large node stage and a small node stage. This property draws the line between small and large nodes.

Parameters:

maximum The maximum number of elements a small node can contain. All larger nodes are considered as large nodes.

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

kd-tree/KDTreeGPU.h
kd-tree/KDTreeGPU.cpp

KDTreeGPU Class Reference

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation