Template Class HierarchyTree

Defined in File hierarchy_tree.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(std::vector<Node*> &leaves, int level = 0): Initialize the tree by a set of leaves using algorithm with a given level.

Node *insert(const BV &bv, void *data): Insest a node.

void remove(Node *leaf): Remove a leaf node.

void clear(): Clear the tree.

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

void update(Node *leaf, int lookahead_level = -1): Updates a leaf node. A use case is when the bounding volume of an object changes. Ensure every parent node has its bounding volume expand or shrink to fit the bounding volumes of its children.

Note

Strangely the structure of the tree may change even if the bounding volume of the leaf node does not change. It is just another valid tree of the same set of objects. This is because update() works by first removing leaf and then inserting leaf back. The structural change could be as simple as switching the order of two leaves if the sibling of the leaf is also a leaf. Or it could be more complicated if the sibling is an internal node.

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

bool update(Node *leaf, const BV &bv, const Vec3s &vel, CoalScalar margin): update one leaf’s bounding volume, with prediction

bool update(Node *leaf, const BV &bv, const Vec3s &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(const Node *root, std::vector<Node*> &leaves) const: extract all the leaves of the tree

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

Node *getRoot() const: get the root of the tree

Node *&getRoot()

void print(Node *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

Protected Attributes

Node *root_node

size_t n_leaves

unsigned int opath

Node *free_node: This is a one Node cache, the reason is that we need to remove a node and then add it again frequently.

int max_lookahead_level