public

Inheritance Graph

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

Description

One object of this class represents a node in a k-D-tree. To be exact this class does not work with k dimensions but with exactly three dimensions.

Author: Benjamin Eikel

Date: 2009-06-30

Protected Attributes

   
   
std::vector< TriangleAccessor > * triangleStorage
   
std::vector< uint32_t > sorted
   
float splitValue
   
std::unique_ptr< kDTree > firstChild
First child of this node ornullptrif leaf.
   
std::unique_ptr< kDTree > secondChild
Second child of this node ornullptrif leaf.
   
const uint32_t maxTrianglesPerNode
   
const float maxBoundingBoxEnlargement
Fraction of allowed bounding box increase.

Public Functions

   
   
  kDTree( Rendering::Mesh * mesh, uint32_t trianglesPerNode, float allowedBBEnlargement)
   
  ~kDTree()
Clean up memory for possible children.
   
bool isLeaf() const
   
std::vector< const TriangleTree * > getChildren() const
   
uint8_t getSplitDimension() const
   
float getSplitValue() const
   
const TriangleAccessor & getTriangle(uint32_t index) const
   
uint32_t getTriangleCount() const
   
bool shouldSplit() const
   
void split()
   
bool contains(const TriangleAccessor & triangle) const
   
void fetchAttributes( Util::AttributeProvider * container) const

Protected Functions

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

Protected Static Functions

   
   
bool needCut(const TriangleAccessor & triangle, uint8_t splitDimension, float splitValue, float & minPos, float & maxPos)

Documentation

variable
MinSG::TriangleTrees::kDTree::triangleStorage

protected
 
 
std::vector< TriangleAccessor > * triangleStorage

Internal storage of the triangles inside the nodes. The root node allocates this storage and hands the pointer to the children.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:165

variable
MinSG::TriangleTrees::kDTree::sorted

protected
 
 
std::vector< uint32_t > sorted

These array of vectors contains the indices of the triangles insidetriangleStorage. The three vectors are sorted by each of the three coordinates of the center of the triangles. The vectors are only used during the construction of the tree and freed afterwards.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:174

variable
MinSG::TriangleTrees::kDTree::splitValue

protected
 
 
float splitValue

Coordinate value of the splitting plane in the splitting dimension.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:180

variable
MinSG::TriangleTrees::kDTree::firstChild

protected
 
 
std::unique_ptr< kDTree > firstChild

First child of this node ornullptrif leaf.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:183

variable
MinSG::TriangleTrees::kDTree::secondChild

protected
 
 
std::unique_ptr< kDTree > secondChild

Second child of this node ornullptrif leaf.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:186

variable
MinSG::TriangleTrees::kDTree::maxTrianglesPerNode

protected
 
 
const uint32_t maxTrianglesPerNode

Maximum number of triangles stored in a node. If the actual number is bigger, the node will be split.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:192

variable
MinSG::TriangleTrees::kDTree::maxBoundingBoxEnlargement

protected
 
 
const float maxBoundingBoxEnlargement

Fraction of allowed bounding box increase.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:195

function
MinSG::TriangleTrees::kDTree::kDTree

public explicit
     
     
kDTree( 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

mesh
Mesh containing the 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/kDTree.h:60

function
MinSG::TriangleTrees::kDTree::~kDTree

public virtual
   
   
~kDTree( )

Clean up memory for possible children.

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

function
MinSG::TriangleTrees::kDTree::isLeaf

public const inline virtual
   
   
bool isLeaf( ) const

Tell if the node is a leaf node.

Returns

trueif the node is a leaf andfalseif it is an inner node.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:73

function
MinSG::TriangleTrees::kDTree::getChildren

public const inline virtual
   
   
std::vector< const TriangleTree * > getChildren( ) const

Retrieve the two child nodes.

Returns

Pointers to children.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:82

function
MinSG::TriangleTrees::kDTree::getSplitDimension

public const inline virtual
   
   
uint8_t 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/kDTree.h:95

function
MinSG::TriangleTrees::kDTree::getSplitValue

public const inline
   
   
float getSplitValue( ) const

Return the coordinate value of the splitting plane.

Returns

Coordinate in split dimension

Defined in MinSG/Ext/TriangleTrees/kDTree.h:105

function
MinSG::TriangleTrees::kDTree::getTriangle

public const virtual
     
     
const TriangleAccessor & getTriangle( uint32_t index ) const

Return one triangle.

Parameters

index
Index of triangle stored in this node.

Returns

Indices stored in this node.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:115

function
MinSG::TriangleTrees::kDTree::getTriangleCount

public const inline virtual
   
   
uint32_t getTriangleCount( ) const

Return the number of triangles that are stored in this tree node.

Returns

Triangle count

Defined in MinSG/Ext/TriangleTrees/kDTree.h:122

function
MinSG::TriangleTrees::kDTree::shouldSplit

public const inline
   
   
bool shouldSplit( ) const

Check if this node should be split.

Returns

trueif this node should be split.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:131

function
MinSG::TriangleTrees::kDTree::split

public
   
   
void split( )

Split this node if it is a leaf. It creates two children and converts this node into an inner node.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:140

function
MinSG::TriangleTrees::kDTree::contains

public const virtual
     
     
bool contains( const TriangleAccessor & triangle ) const

Check if the triangle fits into the bounding box of the tree node.

Parameters

triangle
Triangle to check.

Returns

trueif the triangle is inside or at most touching the bounds.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:150

function
MinSG::TriangleTrees::kDTree::fetchAttributes

public const virtual
     
     
void fetchAttributes( Util::AttributeProvider * container ) const

Add attributes specific to this object to the given container.

Parameters

container
Container for attributes.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:157

function
MinSG::TriangleTrees::kDTree::kDTree

protected explicit
     
     
kDTree( 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/kDTree.h:206

function
MinSG::TriangleTrees::kDTree::createChild

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

Return a child node. Needed for polymorphism.

Defined in MinSG/Ext/TriangleTrees/kDTree.h:209

function
MinSG::TriangleTrees::kDTree::calculateSplittingPlane

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

Calculate the value of the splitting plane in the current splitting dimension.

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/kDTree.h:225

function
MinSG::TriangleTrees::kDTree::needCut

protected static
     
     
bool needCut( const TriangleAccessor & triangle,
  uint8_t splitDimension,
  float splitValue,
  float & minPos,
  float & maxPos
)    

Check if the triangle given by itsindexlies on both sides of the splitting plane given bysplitValuein thesplitDimension.

Parameters

triangle
Triangle to check
splitDimension
Dimension orthogonal to the splitting plane
splitValue
Coordinate value of the splitting plane
minPos
Minimum coordinate of the vertices of the triangle
maxPos
Maximum coordinate of the vertices of the triangle

Defined in MinSG/Ext/TriangleTrees/kDTree.h:243