public

Inheritance Graph

graph BT
	ABTree
	ABTree --> kDTree
	click ABTree "classMinSG_1_1TriangleTrees_1_1ABTree"
	click kDTree "classMinSG_1_1TriangleTrees_1_1kDTree"

Description

Adaptive binary tree as presented in Game Programming Gems 6, Chapter 5.2: Spatial Partitioning Using an Adaptive Binary Tree.

Author: Benjamin Eikel

Date: 2009-07-07

Protected Attributes

   
   
unsigned char splitDimension

Public Functions

   
   
  ABTree( Rendering::Mesh * mesh, uint32_t trianglesPerNode, float allowedBBEnlargement)
   
  ~ABTree()
Does nothing.
   
unsigned char getSplitDimension() const

Protected Functions

   
   
  ABTree(const Geometry::Box & childBound, const kDTree & parent)
   
ABTree * createChild(const Geometry::Box & childBound, const kDTree & parent) const
Return a child node. Needed for polymorphism.
   
void calculateSplittingPlane(uint32_t & numFirstChild, uint32_t & numSecondChild)

Documentation

variable
MinSG::TriangleTrees::ABTree::splitDimension

protected
 
 
unsigned char splitDimension

In this tree the split dimension does not depend on the level of the node as it does in the kDTree . Therefore the split dimension has to be stored here.

Defined in MinSG/Ext/TriangleTrees/ABTree.h:75

function
MinSG::TriangleTrees::ABTree::ABTree

public explicit
     
     
ABTree( Rendering::Mesh * mesh,
  uint32_t trianglesPerNode,
  float allowedBBEnlargement
)    

Create a new kDTree node with the given triangles. This creates a root node which creates a copy of the triangles. Furthermore it builds a axis-aligned bounding box around the triangles.

Parameters

triangles
List of triangles.
trianglesPerNode
Maximum number of triangles to store inside a node. Bigger nodes will be split.
allowedBBEnlargement
Maximum increase of the size of the bounding box when triangles are inserted. If a triangle fits into the at most increased bounding box it will not be cut. This parameter is the fraction of the original bounding box size that is used for increase. For example if the value is0.1fthen a maximum increase of 10% is allowed.

Defined in MinSG/Ext/TriangleTrees/ABTree.h:52

function
MinSG::TriangleTrees::ABTree::~ABTree

public virtual
   
   
~ABTree( )

Does nothing.

Defined in MinSG/Ext/TriangleTrees/ABTree.h:57

function
MinSG::TriangleTrees::ABTree::getSplitDimension

public const inline virtual
   
   
unsigned char getSplitDimension( ) const

Return the dimension which is orthogonal to the splitting plane.

Returns

Dimension X = 0, Y = 1, Z = 2

Defined in MinSG/Ext/TriangleTrees/ABTree.h:65

function
MinSG::TriangleTrees::ABTree::ABTree

protected explicit
     
     
ABTree( const Geometry::Box & childBound,
  const kDTree & parent
)    

Create a new kDTree node. This is used to create child nodes. The creating node has to assign the triangles to the node.

Parameters

childBound
Axis-aligned bounding box for the child.
parent
Parent node which is used to copy the parameters from.

Defined in MinSG/Ext/TriangleTrees/ABTree.h:86

function
MinSG::TriangleTrees::ABTree::createChild

protected const inline virtual
     
     
ABTree * createChild( const Geometry::Box & childBound,
  const kDTree & parent
) const    

Return a child node. Needed for polymorphism.

Defined in MinSG/Ext/TriangleTrees/ABTree.h:89

function
MinSG::TriangleTrees::ABTree::calculateSplittingPlane

protected virtual
     
     
void calculateSplittingPlane( uint32_t & numFirstChild,
  uint32_t & numSecondChild
)    

Calculate the value of the splitting value and the splitting dimension by sampling multiple candidate planes.

Parameters

numFirstChild
Number of triangles that will be assigned to the first child. This value has to be reliable.
numSecondChild
Number of triangles that will be assigned to the second child. This value has to be reliable. assigned to the first child. This value has to be reliable.

Note: It has the side effect that thesplitValuewill be set to the calculated value.

Defined in MinSG/Ext/TriangleTrees/ABTree.h:106