A dynamic AABB tree broad-phase. More...
#include <DynamicTree.hpp>
Classes | |
struct | BranchData |
Branch data of a tree node. More... | |
struct | LeafData |
Leaf data of a tree node. More... | |
class | TreeNode |
A node in the dynamic tree. More... | |
struct | UnusedData |
Unused data of a tree node. More... | |
union | VariantData |
Variant data. More... | |
Public Types | |
using | Size = ContactCounter |
Size type. More... | |
using | Height = ContactCounter |
Type for heights. More... | |
Public Member Functions | |
DynamicTree () noexcept | |
Default constructor. More... | |
DynamicTree (Size nodeCapacity) | |
Size initializing constructor. More... | |
~DynamicTree () noexcept | |
Destroys the tree, freeing the node pool. More... | |
DynamicTree (const DynamicTree &other) | |
Copy constructor. More... | |
DynamicTree (DynamicTree &&other) noexcept | |
Move constructor. More... | |
DynamicTree & | operator= (DynamicTree other) noexcept |
Unifying assignment operator. More... | |
Size | CreateLeaf (const AABB &aabb, const LeafData &data) |
Creates a new leaf node. More... | |
void | DestroyLeaf (Size index) noexcept |
Destroys a leaf node. More... | |
void | UpdateLeaf (Size index, const AABB &aabb) |
Updates a leaf node with a new AABB value. More... | |
LeafData | GetLeafData (Size index) const noexcept |
Gets the user data for the node identified by the given identifier. More... | |
void | SetLeafData (Size index, LeafData value) noexcept |
Sets the leaf data for the element at the given index to the given value. More... | |
AABB | GetAABB (Size index) const noexcept |
Gets the AABB for a leaf or branch (a non-unused node). More... | |
Height | GetHeight (Size index) const noexcept |
Gets the height value for the identified node. More... | |
Size | GetOther (Size index) const noexcept |
Gets the "other" index for the node at the given index. More... | |
BranchData | GetBranchData (Size index) const noexcept |
Gets the branch data for the identified node. More... | |
Size | GetRootIndex () const noexcept |
Gets the index of the "root" node if this tree has one. More... | |
Size | GetFreeIndex () const noexcept |
Gets the free index. More... | |
void | RebuildBottomUp () |
Builds an optimal tree. More... | |
void | ShiftOrigin (Length2 newOrigin) |
Shifts the world origin. More... | |
Size | GetNodeCapacity () const noexcept |
Gets the current node capacity of this tree. More... | |
Size | GetNodeCount () const noexcept |
Gets the current count of allocated nodes. More... | |
Size | GetLeafCount () const noexcept |
Gets the current leaf node count. More... | |
Size | FindReference (Size index) const noexcept |
Finds first node which references the given index. More... | |
Static Public Member Functions | |
static PLAYRHO_CONSTEXPR Size | GetInvalidSize () noexcept |
Gets the invalid size value. More... | |
static PLAYRHO_CONSTEXPR Height | GetInvalidHeight () noexcept |
Gets the invalid height value. More... | |
static PLAYRHO_CONSTEXPR bool | IsUnused (Height value) noexcept |
Gets whether the given height is the height for an "unused" node. More... | |
static PLAYRHO_CONSTEXPR bool | IsLeaf (Height value) noexcept |
Gets whether the given height is the height for a "leaf" node. More... | |
static PLAYRHO_CONSTEXPR bool | IsBranch (Height value) noexcept |
Gets whether the given height is a height for a "branch" node. More... | |
static PLAYRHO_CONSTEXPR Size | GetDefaultInitialNodeCapacity () noexcept |
Gets the default initial node capacity. More... | |
Static Public Attributes | |
static const PLAYRHO_CONSTEXPR auto | InvalidHeight = static_cast<Height>(-1) |
Invalid height constant value. More... | |
Friends | |
void | swap (DynamicTree &lhs, DynamicTree &rhs) noexcept |
Customized swap function for DynamicTree objects. More... | |
Related Functions | |
(Note that these are not member functions.) | |
DynamicTree::Height | GetHeight (const DynamicTree &tree) noexcept |
Gets the height of the binary tree. More... | |
AABB | GetAABB (const DynamicTree &tree) noexcept |
Gets the AABB for the given dynamic tree. More... | |
bool | TestOverlap (const DynamicTree &tree, DynamicTree::Size leafIdA, DynamicTree::Size leafIdB) noexcept |
Tests for overlap of the elements identified in the given dynamic tree. More... | |
Detailed Description
A dynamic AABB tree broad-phase.
A dynamic tree arranges data in a binary tree to accelerate queries such as volume queries and ray casts. Leafs are proxies with an AABB.
- Invariant
- A dynamic tree with a capacity of N nodes will always have N minus M "free" nodes and M "allocated" nodes where M is never more than N.
- Freed nodes' "other" nodes are valid "next" older freed nodes, or they have the invalid size value indicating that they are the oldest freed node.
- Allocated nodes' "other" nodes are valid "parent" nodes, or they have the invalid size value indicating that they are parentless.
- The root node's index is either the index to the node at the root of the tree or it's the invalid size value indicating that this tree is empty.
- The root node's "other" index will be the invalid size value.
- Allocated nodes can only be "branch" or "leaf" nodes.
- Branch nodes always have two valid "child" nodes.
- Branch nodes always have a "height" of 1 plus the maximum height of its children.
- Branch nodes' AABBs are always the AABB which minimally encloses its children.
- Leaf nodes always have a "height" of zero.
- Freed nodes always have a "height" of the maximum value of the height type.
- Note
- This code was inspired by Nathanael Presson's
btDbvt
. - Nodes are pooled and relocatable, so we use node indices rather than pointers.
- This data structure is 32-bytes large (on at least one 64-bit platform).
- See also
- http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/
- http://www.cs.utah.edu/~thiago/papers/rotations.pdf ("Fast, Effective BVH Updates for Animated Scenes")
Definition at line 71 of file DynamicTree.hpp.
Member Typedef Documentation
◆ Size
Size type.
Definition at line 75 of file DynamicTree.hpp.
◆ Height
Type for heights.
- Note
- The maximum height of a tree can never exceed half of the max value of the
Size
type due to the binary nature of this tree structure.
Definition at line 92 of file DynamicTree.hpp.
Constructor & Destructor Documentation
◆ DynamicTree() [1/4]
|
defaultnoexcept |
Default constructor.
◆ DynamicTree() [2/4]
|
explicit |
Size initializing constructor.
Definition at line 381 of file DynamicTree.cpp.
◆ ~DynamicTree()
|
noexcept |
Destroys the tree, freeing the node pool.
Definition at line 423 of file DynamicTree.cpp.
◆ DynamicTree() [3/4]
playrho::d2::DynamicTree::DynamicTree | ( | const DynamicTree & | other | ) |
Copy constructor.
Definition at line 398 of file DynamicTree.cpp.
◆ DynamicTree() [4/4]
|
noexcept |
Move constructor.
Definition at line 409 of file DynamicTree.cpp.
Member Function Documentation
◆ GetInvalidSize()
|
inlinestaticnoexcept |
Gets the invalid size value.
Definition at line 84 of file DynamicTree.hpp.
◆ GetInvalidHeight()
|
inlinestaticnoexcept |
Gets the invalid height value.
Definition at line 98 of file DynamicTree.hpp.
◆ IsUnused()
|
inlinestaticnoexcept |
Gets whether the given height is the height for an "unused" node.
Definition at line 104 of file DynamicTree.hpp.
◆ IsLeaf()
|
inlinestaticnoexcept |
Gets whether the given height is the height for a "leaf" node.
Definition at line 110 of file DynamicTree.hpp.
◆ IsBranch()
|
inlinestaticnoexcept |
Gets whether the given height is a height for a "branch" node.
Definition at line 116 of file DynamicTree.hpp.
◆ GetDefaultInitialNodeCapacity()
|
inlinestaticnoexcept |
Gets the default initial node capacity.
Definition at line 538 of file DynamicTree.hpp.
◆ operator=()
|
noexcept |
Unifying assignment operator.
- Note
- This intentionally takes the argument by-value. Along with the move constructor, this assignment method effectively doubles up as both copy assignment and move assignment support.
- See also
- https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap
- https://stackoverflow.com/a/3279550/7410358
Definition at line 415 of file DynamicTree.cpp.
◆ CreateLeaf()
DynamicTree::Size playrho::d2::DynamicTree::CreateLeaf | ( | const AABB & | aabb, |
const LeafData & | data | ||
) |
Creates a new leaf node.
Creates a leaf node for a tight fitting AABB and the given data.
- Note
- The indices of leaf nodes that have been destroyed get reused for new nodes.
- Postcondition
- If the root index had been the
GetInvalidSize()
, then it will be set to the index returned from this method. - The leaf count will be incremented by one.
- Returns
- The index of the created leaf node.
Definition at line 516 of file DynamicTree.cpp.
◆ DestroyLeaf()
|
noexcept |
Destroys a leaf node.
- Postcondition
- The leaf count will be decremented by one.
- Warning
- Behavior is undefined if the given index is not valid.
Definition at line 533 of file DynamicTree.cpp.
◆ UpdateLeaf()
Updates a leaf node with a new AABB value.
- Warning
- Behavior is undefined if the given index is not valid.
- Parameters
-
index Leaf node's ID. Behavior is undefined if this is not a valid ID. aabb New axis aligned bounding box for the leaf node.
Definition at line 566 of file DynamicTree.cpp.
◆ GetLeafData()
|
inlinenoexcept |
Gets the user data for the node identified by the given identifier.
- Warning
- Behavior is undefined if the given index is not valid.
- Parameters
-
index Identifier of node to get the user data for.
- Returns
- User data for the specified node.
Definition at line 602 of file DynamicTree.hpp.
◆ SetLeafData()
Sets the leaf data for the element at the given index to the given value.
Definition at line 610 of file DynamicTree.hpp.
◆ GetAABB()
Gets the AABB for a leaf or branch (a non-unused node).
- Warning
- Behavior is undefined if the given index is not valid.
- Parameters
-
index Leaf or branch node's ID. Must be a valid ID.
Definition at line 586 of file DynamicTree.hpp.
◆ GetHeight()
|
inlinenoexcept |
Gets the height value for the identified node.
- Warning
- Behavior is undefined if the given index is not valid.
Definition at line 572 of file DynamicTree.hpp.
◆ GetOther()
|
inlinenoexcept |
Gets the "other" index for the node at the given index.
- Note
- For unused nodes, this is the index to the "next" unused node.
- For used nodes (leaf or branch nodes), this is the index to the "parent" node.
- Warning
- Behavior is undefined if the given index is not valid.
- Precondition
- This tree has a node capacity greater than the given index.
- Returns
- The invalid index value or a value less than the node capacity.
Definition at line 579 of file DynamicTree.hpp.
◆ GetBranchData()
|
inlinenoexcept |
Gets the branch data for the identified node.
- Warning
- Behavior is undefined if the given index in not a valid branch node.
Definition at line 594 of file DynamicTree.hpp.
◆ GetRootIndex()
|
inlinenoexcept |
Gets the index of the "root" node if this tree has one.
- Note
- If the tree has a root node, then the "other" property of this node will be the invalid size.
- Returns
GetInvalidSize()
if this tree is "empty", else index to "root" node.
Definition at line 543 of file DynamicTree.hpp.
◆ GetFreeIndex()
|
inlinenoexcept |
Gets the free index.
Definition at line 550 of file DynamicTree.hpp.
◆ RebuildBottomUp()
void playrho::d2::DynamicTree::RebuildBottomUp | ( | ) |
Builds an optimal tree.
- Note
- This operation is very expensive.
- Meant for testing.
Definition at line 583 of file DynamicTree.cpp.
◆ ShiftOrigin()
void playrho::d2::DynamicTree::ShiftOrigin | ( | Length2 | newOrigin | ) |
Shifts the world origin.
- Note
- Useful for large worlds.
-
The shift formula is:
position -= newOrigin
.
- Parameters
-
newOrigin the new origin with respect to the old origin.
Definition at line 652 of file DynamicTree.cpp.
◆ GetNodeCapacity()
|
inlinenoexcept |
Gets the current node capacity of this tree.
Definition at line 555 of file DynamicTree.hpp.
◆ GetNodeCount()
|
inlinenoexcept |
Gets the current count of allocated nodes.
- Returns
- Count of existing proxies (count of nodes currently allocated).
Definition at line 560 of file DynamicTree.hpp.
◆ GetLeafCount()
|
inlinenoexcept |
Gets the current leaf node count.
Gets the current leaf node count.
- Examples
- World.cpp.
Definition at line 565 of file DynamicTree.hpp.
◆ FindReference()
|
noexcept |
Finds first node which references the given index.
- Note
- Primarily intended for unit testing and/or debugging.
- Returns
- Index of node referencing the given index, or the value of
GetInvalidSize()
.
Definition at line 496 of file DynamicTree.cpp.
Friends And Related Function Documentation
◆ swap
|
friend |
Customized swap function for DynamicTree
objects.
- Note
- This satisfies the
Swappable
concept.
Definition at line 666 of file DynamicTree.cpp.
◆ GetHeight()
|
related |
Gets the height of the binary tree.
- Returns
- Height of the tree (as stored in the root node) or 0 if the root node is not valid.
Definition at line 673 of file DynamicTree.hpp.
◆ GetAABB()
|
related |
Gets the AABB for the given dynamic tree.
Gets the AABB that encloses all other AABB instances that are within the given dynamic tree.
- Returns
- Enclosing AABB or the "unset" AABB.
Definition at line 684 of file DynamicTree.hpp.
◆ TestOverlap()
|
related |
Tests for overlap of the elements identified in the given dynamic tree.
Definition at line 692 of file DynamicTree.hpp.
Member Data Documentation
◆ InvalidHeight
|
static |
Invalid height constant value.
Definition at line 95 of file DynamicTree.hpp.
The documentation for this class was generated from the following files:
- Collision/DynamicTree.hpp
- Collision/DynamicTree.cpp