Public Member Functions | Protected Member Functions | Protected Attributes

KDTreeGPU Class Reference

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

#include <KDTreeGPU.h>

Inheritance diagram for KDTreeGPU:
KDTreePoint KDTreeTri

List of all members.

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.
KDTreeDataGetData ()
 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

KDNodeListm_pListActive
 Currently active nodes list.
KDNodeListm_pListNext
 Node list for next pass of algorithm.
KDChunkListm_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:
numInputElemsNumber of elements to store within the kd-tree. Note that this removes or at least restricts the ability to dynamically update the tree.
numElementPointsNumber 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.
rootAABBMinRoot node AABB minimum vertex.
rootAABBMaxRoot 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]pListNode 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]pListThe 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]pListParentThe list of parent nodes. This is usually the active list.
[in,out]pListChildThe 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:
bitNoNumber of the custom bit to manipulate. This can be either 0 or 1, but nothing else.
[in]d_valuesValues 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:
ratioThe 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:
radiusThe 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:
maximumThe 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:
MNRT Source Code Documentation (Version 1.0) - Copyright © Mathias Neumann 2010