All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Member Functions | Public Attributes | Protected Attributes | Private Types | Private Member Functions | Static Private Member Functions
fcl::HierarchyTree< BV > Class Template Reference

Class for hierarchy tree structure. More...

#include <hierarchy_tree.h>

List of all members.

Classes

struct  SortByMorton

Public Member Functions

void balanceBottomup ()
 balance the tree from bottom
void balanceIncremental (int iterations)
 balance the tree in an incremental way
void balanceTopdown ()
 balance the tree from top
void clear ()
 Clear the tree.
bool empty () const
 Whether the tree is empty.
void extractLeaves (const NodeType *root, std::vector< NodeType * > &leaves) const
 extract all the leaves of the tree
size_t getMaxDepth () const
 get the max depth of the tree
size_t getMaxHeight () const
 get the max height of the tree
NodeType * getRoot () const
 get the root of the tree
NodeType *& getRoot ()
 HierarchyTree (int bu_threshold_=16, int topdown_level_=0)
 Create hierarchy tree with suitable setting. bu_threshold decides the height of tree node to start bottom-up construction / optimization; topdown_level decides different methods to construct tree in topdown manner. lower level method constructs tree with better quality but is slower.
void init (std::vector< NodeType * > &leaves, int level=0)
 Initialize the tree by a set of leaves using algorithm with a given level.
NodeType * insert (const BV &bv, void *data)
 Insest a node.
void print (NodeType *root, int depth)
 print the tree in a recursive way
void refit ()
 refit the tree, i.e., when the leaf nodes' bounding volumes change, update the entire tree in a bottom-up manner
void remove (NodeType *leaf)
 Remove a leaf node.
size_t size () const
 number of leaves in the tree
template<>
bool update (NodeBase< AABB > *leaf, const AABB &bv_, const Vec3f &vel, FCL_REAL margin)
template<>
bool update (NodeBase< AABB > *leaf, const AABB &bv_, const Vec3f &vel)
void update (NodeType *leaf, int lookahead_level=-1)
 update one leaf node
bool update (NodeType *leaf, const BV &bv)
 update the tree when the bounding volume of a given leaf has changed
bool update (NodeType *leaf, const BV &bv, const Vec3f &vel, FCL_REAL margin)
 update one leaf's bounding volume, with prediction
bool update (NodeType *leaf, const BV &bv, const Vec3f &vel)
 update one leaf's bounding volume, with prediction
template<>
bool update (NodeBase< AABB > *leaf, const AABB &bv_, const Vec3f &vel, FCL_REAL margin)
template<>
bool update (NodeBase< AABB > *leaf, const AABB &bv_, const Vec3f &vel)
 ~HierarchyTree ()

Public Attributes

int bu_threshold
 decide the depth to use expensive bottom-up algorithm
int topdown_level
 decide which topdown algorithm to use

Protected Attributes

NodeType * free_node
 This is a one NodeType cache, the reason is that we need to remove a node and then add it again frequently.
int max_lookahead_level
size_t n_leaves
unsigned int opath
NodeType * root_node

Private Types

typedef NodeBase< BV > NodeType
typedef std::vector< NodeBase
< BV > * >::const_iterator 		NodeVecConstIterator
typedef std::vector< NodeBase
< BV > * >::iterator 		NodeVecIterator

Private Member Functions

void bottomup (const NodeVecIterator lbeg, const NodeVecIterator lend)
 construct a tree for a set of leaves from bottom -- very heavy way
NodeType * createNode (NodeType *parent, const BV &bv, void *data)
 create one node (leaf or internal)
NodeType * createNode (NodeType *parent, const BV &bv1, const BV &bv2, void *data)
NodeType * createNode (NodeType *parent, void *data)
void deleteNode (NodeType *node)
void fetchLeaves (NodeType *root, std::vector< NodeType * > &leaves, int depth=-1)
 Delete all internal nodes and return all leaves nodes with given depth from root.
void getMaxDepth (NodeType *node, size_t depth, size_t &max_depth) const
 compute the maximum depth of a subtree rooted from a given node
size_t getMaxHeight (NodeType *node) const
 compute the maximum height of a subtree rooted from a given node
void init_0 (std::vector< NodeType * > &leaves)
 init tree from leaves in the topdown manner (topdown_0 or topdown_1)
void init_1 (std::vector< NodeType * > &leaves)
 init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we use bottomup method to construct the subtree, which is slow but can construct tree with high quality.
void init_2 (std::vector< NodeType * > &leaves)
 init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we split the leaves into two parts with the same size simply using the node index.
void init_3 (std::vector< NodeType * > &leaves)
 init tree from leaves using morton code. It uses morton_2, i.e., for all nodes, we simply divide the leaves into parts with the same size simply using the node index.
void insertLeaf (NodeType *root, NodeType *leaf)
 Insert a leaf node and also update its ancestors.
NodeType * mortonRecurse_0 (const NodeVecIterator lbeg, const NodeVecIterator lend, const FCL_UINT32 &split, int bits)
NodeType * mortonRecurse_1 (const NodeVecIterator lbeg, const NodeVecIterator lend, const FCL_UINT32 &split, int bits)
NodeType * mortonRecurse_2 (const NodeVecIterator lbeg, const NodeVecIterator lend)
void recurseDeleteNode (NodeType *node)
void recurseRefit (NodeType *node)
NodeType * removeLeaf (NodeType *leaf)
 Remove a leaf. The leaf node itself is not deleted yet, but all the unnecessary internal nodes are deleted. return the node with the smallest depth and is influenced by the remove operation.
NodeType * sort (NodeType *n, NodeType *&r)
 sort node n and its parent according to their memory position
NodeType * topdown (const NodeVecIterator lbeg, const NodeVecIterator lend)
 construct a tree for a set of leaves from top
NodeType * topdown_0 (const NodeVecIterator lbeg, const NodeVecIterator lend)
 construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split axis as the axis along with the longest AABB edge. Then compute the median of all nodes' center projection onto the axis and using it as the split threshold.
NodeType * topdown_1 (const NodeVecIterator lbeg, const NodeVecIterator lend)
 construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split thresholds for different axes as the average of all nodes' center. Then choose the split axis as the axis whose threshold can divide the nodes into two parts with almost similar size. This construction is more expensive then topdown_0, but also can provide tree with better quality.
void update_ (NodeType *leaf, const BV &bv)
 update one leaf node's bounding volume

Static Private Member Functions

static BV bounds (const std::vector< NodeType * > &leaves)
static BV bounds (const NodeVecIterator lbeg, const NodeVecIterator lend)
static size_t indexOf (NodeType *node)

Detailed Description

template<typename BV>
class fcl::HierarchyTree< BV >

Class for hierarchy tree structure.

Definition at line 116 of file hierarchy_tree.h.

Member Typedef Documentation

template<typename BV>
typedef NodeBase<BV> fcl::HierarchyTree< BV >::NodeType [private]

Definition at line 118 of file hierarchy_tree.h.

template<typename BV>
typedef std::vector<NodeBase<BV>* >::const_iterator fcl::HierarchyTree< BV >::NodeVecConstIterator [private]

Definition at line 120 of file hierarchy_tree.h.

template<typename BV>
typedef std::vector<NodeBase<BV>* >::iterator fcl::HierarchyTree< BV >::NodeVecIterator [private]

Definition at line 119 of file hierarchy_tree.h.

Constructor & Destructor Documentation

template<typename BV>
fcl::HierarchyTree< BV >::HierarchyTree ( int  bu_threshold_ = 16,
int  topdown_level_ = 0 
)

Create hierarchy tree with suitable setting. bu_threshold decides the height of tree node to start bottom-up construction / optimization; topdown_level decides different methods to construct tree in topdown manner. lower level method constructs tree with better quality but is slower.

template<typename BV>
fcl::HierarchyTree< BV >::~HierarchyTree ( )

Member Function Documentation

template<typename BV>
void fcl::HierarchyTree< BV >::balanceBottomup ( )

balance the tree from bottom

template<typename BV>
void fcl::HierarchyTree< BV >::balanceIncremental ( int  iterations)

balance the tree in an incremental way

template<typename BV>
void fcl::HierarchyTree< BV >::balanceTopdown ( )

balance the tree from top

template<typename BV>
void fcl::HierarchyTree< BV >::bottomup ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
) [private]

construct a tree for a set of leaves from bottom -- very heavy way

template<typename BV>
static BV fcl::HierarchyTree< BV >::bounds ( const std::vector< NodeType * > &  leaves) [static, private]
template<typename BV>
static BV fcl::HierarchyTree< BV >::bounds ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
) [static, private]
template<typename BV>
void fcl::HierarchyTree< BV >::clear ( )

Clear the tree.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::createNode ( NodeType *  parent,
const BV &  bv,
void *  data 
) [private]

create one node (leaf or internal)

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::createNode ( NodeType *  parent,
const BV &  bv1,
const BV &  bv2,
void *  data 
) [private]
template<typename BV>
NodeType* fcl::HierarchyTree< BV >::createNode ( NodeType *  parent,
void *  data 
) [private]
template<typename BV>
void fcl::HierarchyTree< BV >::deleteNode ( NodeType *  node) [private]
template<typename BV>
bool fcl::HierarchyTree< BV >::empty ( ) const

Whether the tree is empty.

template<typename BV>
void fcl::HierarchyTree< BV >::extractLeaves ( const NodeType *  root,
std::vector< NodeType * > &  leaves 
) const

extract all the leaves of the tree

template<typename BV>
void fcl::HierarchyTree< BV >::fetchLeaves ( NodeType *  root,
std::vector< NodeType * > &  leaves,
int  depth = -1 
) [private]

Delete all internal nodes and return all leaves nodes with given depth from root.

template<typename BV>
size_t fcl::HierarchyTree< BV >::getMaxDepth ( ) const

get the max depth of the tree

template<typename BV>
void fcl::HierarchyTree< BV >::getMaxDepth ( NodeType *  node,
size_t  depth,
size_t &  max_depth 
) const [private]

compute the maximum depth of a subtree rooted from a given node

template<typename BV>
size_t fcl::HierarchyTree< BV >::getMaxHeight ( ) const

get the max height of the tree

template<typename BV>
size_t fcl::HierarchyTree< BV >::getMaxHeight ( NodeType *  node) const [private]

compute the maximum height of a subtree rooted from a given node

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::getRoot ( ) const

get the root of the tree

template<typename BV>
NodeType*& fcl::HierarchyTree< BV >::getRoot ( )
template<typename BV>
static size_t fcl::HierarchyTree< BV >::indexOf ( NodeType *  node) [static, private]
template<typename BV>
void fcl::HierarchyTree< BV >::init ( std::vector< NodeType * > &  leaves,
int  level = 0 
)

Initialize the tree by a set of leaves using algorithm with a given level.

template<typename BV>
void fcl::HierarchyTree< BV >::init_0 ( std::vector< NodeType * > &  leaves) [private]

init tree from leaves in the topdown manner (topdown_0 or topdown_1)

template<typename BV>
void fcl::HierarchyTree< BV >::init_1 ( std::vector< NodeType * > &  leaves) [private]

init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we use bottomup method to construct the subtree, which is slow but can construct tree with high quality.

template<typename BV>
void fcl::HierarchyTree< BV >::init_2 ( std::vector< NodeType * > &  leaves) [private]

init tree from leaves using morton code. It uses morton_0, i.e., for nodes which is of depth more than the maximum bits of the morton code, we split the leaves into two parts with the same size simply using the node index.

template<typename BV>
void fcl::HierarchyTree< BV >::init_3 ( std::vector< NodeType * > &  leaves) [private]

init tree from leaves using morton code. It uses morton_2, i.e., for all nodes, we simply divide the leaves into parts with the same size simply using the node index.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::insert ( const BV &  bv,
void *  data 
)

Insest a node.

template<typename BV>
void fcl::HierarchyTree< BV >::insertLeaf ( NodeType *  root,
NodeType *  leaf 
) [private]

Insert a leaf node and also update its ancestors.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::mortonRecurse_0 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend,
const FCL_UINT32 &  split,
int  bits 
) [private]
template<typename BV>
NodeType* fcl::HierarchyTree< BV >::mortonRecurse_1 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend,
const FCL_UINT32 &  split,
int  bits 
) [private]
template<typename BV>
NodeType* fcl::HierarchyTree< BV >::mortonRecurse_2 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
) [private]
template<typename BV>
void fcl::HierarchyTree< BV >::print ( NodeType *  root,
int  depth 
)

print the tree in a recursive way

template<typename BV>
void fcl::HierarchyTree< BV >::recurseDeleteNode ( NodeType *  node) [private]
template<typename BV>
void fcl::HierarchyTree< BV >::recurseRefit ( NodeType *  node) [private]
template<typename BV>
void fcl::HierarchyTree< BV >::refit ( )

refit the tree, i.e., when the leaf nodes' bounding volumes change, update the entire tree in a bottom-up manner

template<typename BV>
void fcl::HierarchyTree< BV >::remove ( NodeType *  leaf)

Remove a leaf node.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::removeLeaf ( NodeType *  leaf) [private]

Remove a leaf. The leaf node itself is not deleted yet, but all the unnecessary internal nodes are deleted. return the node with the smallest depth and is influenced by the remove operation.

template<typename BV>
size_t fcl::HierarchyTree< BV >::size ( ) const

number of leaves in the tree

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::sort ( NodeType *  n,
NodeType *&  r 
) [private]

sort node n and its parent according to their memory position

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::topdown ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
) [private]

construct a tree for a set of leaves from top

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::topdown_0 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
) [private]

construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split axis as the axis along with the longest AABB edge. Then compute the median of all nodes' center projection onto the axis and using it as the split threshold.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::topdown_1 ( const NodeVecIterator  lbeg,
const NodeVecIterator  lend 
) [private]

construct a tree from a list of nodes stored in [lbeg, lend) in a topdown manner. During construction, first compute the best split thresholds for different axes as the average of all nodes' center. Then choose the split axis as the axis whose threshold can divide the nodes into two parts with almost similar size. This construction is more expensive then topdown_0, but also can provide tree with better quality.

template<>
bool fcl::HierarchyTree< AABB >::update ( NodeBase< AABB > *  leaf,
const AABB &  bv_,
const Vec3f &  vel,
FCL_REAL  margin 
)

Definition at line 71 of file hierarchy_tree.cpp.

template<>
bool fcl::HierarchyTree< AABB >::update ( NodeBase< AABB > *  leaf,
const AABB &  bv_,
const Vec3f &  vel 
)

Definition at line 89 of file hierarchy_tree.cpp.

template<typename BV>
void fcl::HierarchyTree< BV >::update ( NodeType *  leaf,
int  lookahead_level = -1 
)

update one leaf node

template<typename BV>
bool fcl::HierarchyTree< BV >::update ( NodeType *  leaf,
const BV &  bv 
)

update the tree when the bounding volume of a given leaf has changed

template<typename BV>
bool fcl::HierarchyTree< BV >::update ( NodeType *  leaf,
const BV &  bv,
const Vec3f &  vel,
FCL_REAL  margin 
)

update one leaf's bounding volume, with prediction

template<typename BV>
bool fcl::HierarchyTree< BV >::update ( NodeType *  leaf,
const BV &  bv,
const Vec3f &  vel 
)

update one leaf's bounding volume, with prediction

template<>
bool fcl::HierarchyTree< AABB >::update ( NodeBase< AABB > *  leaf,
const AABB &  bv_,
const Vec3f &  vel,
FCL_REAL  margin 
)
template<>
bool fcl::HierarchyTree< AABB >::update ( NodeBase< AABB > *  leaf,
const AABB &  bv_,
const Vec3f &  vel 
)
template<typename BV>
void fcl::HierarchyTree< BV >::update_ ( NodeType *  leaf,
const BV &  bv 
) [private]

update one leaf node's bounding volume

Member Data Documentation

template<typename BV>
int fcl::HierarchyTree< BV >::bu_threshold

decide the depth to use expensive bottom-up algorithm

Definition at line 302 of file hierarchy_tree.h.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::free_node [protected]

This is a one NodeType cache, the reason is that we need to remove a node and then add it again frequently.

Definition at line 293 of file hierarchy_tree.h.

template<typename BV>
int fcl::HierarchyTree< BV >::max_lookahead_level [protected]

Definition at line 295 of file hierarchy_tree.h.

template<typename BV>
size_t fcl::HierarchyTree< BV >::n_leaves [protected]

Definition at line 288 of file hierarchy_tree.h.

template<typename BV>
unsigned int fcl::HierarchyTree< BV >::opath [protected]

Definition at line 290 of file hierarchy_tree.h.

template<typename BV>
NodeType* fcl::HierarchyTree< BV >::root_node [protected]

Definition at line 286 of file hierarchy_tree.h.

template<typename BV>
int fcl::HierarchyTree< BV >::topdown_level

decide which topdown algorithm to use

Definition at line 299 of file hierarchy_tree.h.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

fcl
Author(s): Jia Pan
autogenerated on Tue Jan 15 2013 16:05:31