Template Class HierarchyTree

Defined in File hierarchy_tree_array.h

Nested Relationships

Nested Types

Struct HierarchyTree::SortByMorton

Class Documentation

template<typename BV> class HierarchyTree

Class for hierarchy tree structure.

Public Types

typedef NodeBase<BV> Node

Public Functions

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.

~HierarchyTree()

void init(Node *leaves, int n_leaves_, int level = 0): Initialize the tree by a set of leaves using algorithm with a given level.

size_t insert(const BV &bv, void *data): Initialize the tree by a set of leaves using algorithm with a given level.

void remove(size_t leaf): Remove a leaf node.

void clear(): Clear the tree.

bool empty() const: Whether the tree is empty.

void update(size_t leaf, int lookahead_level = -1): update one leaf node

bool update(size_t leaf, const BV &bv): update the tree when the bounding volume of a given leaf has changed

bool update(size_t leaf, const BV &bv, const Vec3f &vel, FCL_REAL margin): update one leaf’s bounding volume, with prediction

bool update(size_t leaf, const BV &bv, const Vec3f &vel): update one leaf’s bounding volume, with prediction

size_t getMaxHeight() const: get the max height of the tree

size_t getMaxDepth() const: get the max depth of the tree

void balanceBottomup(): balance the tree from bottom

void balanceTopdown(): balance the tree from top

void balanceIncremental(int iterations): balance the tree in an incremental 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 extractLeaves(size_t root, Node *&leaves) const: extract all the leaves of the tree

size_t size() const: number of leaves in the tree

size_t getRoot() const: get the root of the tree

Node *getNodes() const: get the pointer to the nodes array

void print(size_t root, int depth): print the tree in a recursive way

Public Members

int topdown_level: decide which topdown algorithm to use

int bu_threshold: decide the depth to use expensive bottom-up algorithm

Public Static Attributes

static const size_t NULL_NODE = std::numeric_limits<size_t>::max()

Protected Attributes

size_t root_node

Node *nodes

size_t n_nodes

size_t n_nodes_alloc

size_t n_leaves

size_t freelist

unsigned int opath

int max_lookahead_level