#include <b2DynamicTree.h>
Public Member Functions | |
b2DynamicTree () | |
Constructing the tree initializes the node pool. | |
int32 | CreateProxy (const b2AABB &aabb, void *userData) |
Create a proxy. Provide a tight fitting AABB and a userData pointer. | |
void | DestroyProxy (int32 proxyId) |
Destroy a proxy. This asserts if the id is invalid. | |
float32 | GetAreaRatio () const |
Get the ratio of the sum of the node areas to the root area. | |
const b2AABB & | GetFatAABB (int32 proxyId) const |
Get the fat AABB for a proxy. | |
int32 | GetHeight () const |
int32 | GetMaxBalance () const |
void * | GetUserData (int32 proxyId) const |
bool | MoveProxy (int32 proxyId, const b2AABB &aabb1, const b2Vec2 &displacement) |
template<typename T > | |
void | Query (T *callback, const b2AABB &aabb) const |
template<typename T > | |
void | RayCast (T *callback, const b2RayCastInput &input) const |
void | RebuildBottomUp () |
Build an optimal tree. Very expensive. For testing. | |
void | ShiftOrigin (const b2Vec2 &newOrigin) |
void | Validate () const |
Validate this tree. For testing. | |
~b2DynamicTree () | |
Destroy the tree, freeing the node pool. | |
Private Member Functions | |
int32 | AllocateNode () |
int32 | Balance (int32 index) |
int32 | ComputeHeight () const |
int32 | ComputeHeight (int32 nodeId) const |
void | FreeNode (int32 node) |
void | InsertLeaf (int32 node) |
void | RemoveLeaf (int32 node) |
void | ValidateMetrics (int32 index) const |
void | ValidateStructure (int32 index) const |
Private Attributes | |
int32 | m_freeList |
int32 | m_insertionCount |
int32 | m_nodeCapacity |
int32 | m_nodeCount |
b2TreeNode * | m_nodes |
uint32 | m_path |
This is used to incrementally traverse the tree for re-balancing. | |
int32 | m_root |
A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt. 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. In the tree we expand the proxy AABB by b2_fatAABBFactor so that the proxy AABB is bigger than the client object. This allows the client object to move by small amounts without triggering a tree update.
Nodes are pooled and relocatable, so we use node indices rather than pointers.
Definition at line 61 of file b2DynamicTree.h.
Constructing the tree initializes the node pool.
Definition at line 22 of file b2DynamicTree.cpp.
Destroy the tree, freeing the node pool.
Definition at line 46 of file b2DynamicTree.cpp.
int32 b2DynamicTree::AllocateNode | ( | ) | [private] |
Definition at line 53 of file b2DynamicTree.cpp.
int32 b2DynamicTree::Balance | ( | int32 | index | ) | [private] |
Definition at line 377 of file b2DynamicTree.cpp.
int32 b2DynamicTree::ComputeHeight | ( | ) | const [private] |
Definition at line 573 of file b2DynamicTree.cpp.
int32 b2DynamicTree::ComputeHeight | ( | int32 | nodeId | ) | const [private] |
Definition at line 558 of file b2DynamicTree.cpp.
int32 b2DynamicTree::CreateProxy | ( | const b2AABB & | aabb, |
void * | userData | ||
) |
Create a proxy. Provide a tight fitting AABB and a userData pointer.
Definition at line 105 of file b2DynamicTree.cpp.
void b2DynamicTree::DestroyProxy | ( | int32 | proxyId | ) |
Destroy a proxy. This asserts if the id is invalid.
Definition at line 121 of file b2DynamicTree.cpp.
void b2DynamicTree::FreeNode | ( | int32 | node | ) | [private] |
Definition at line 92 of file b2DynamicTree.cpp.
float32 b2DynamicTree::GetAreaRatio | ( | ) | const |
Get the ratio of the sum of the node areas to the root area.
Definition at line 531 of file b2DynamicTree.cpp.
const b2AABB & b2DynamicTree::GetFatAABB | ( | int32 | proxyId | ) | const [inline] |
Get the fat AABB for a proxy.
Definition at line 162 of file b2DynamicTree.h.
int32 b2DynamicTree::GetHeight | ( | ) | const |
Compute the height of the binary tree in O(N) time. Should not be called often.
Definition at line 520 of file b2DynamicTree.cpp.
int32 b2DynamicTree::GetMaxBalance | ( | ) | const |
Get the maximum balance of an node in the tree. The balance is the difference in height of the two children of a node.
Definition at line 672 of file b2DynamicTree.cpp.
void * b2DynamicTree::GetUserData | ( | int32 | proxyId | ) | const [inline] |
Get proxy user data.
Definition at line 156 of file b2DynamicTree.h.
void b2DynamicTree::InsertLeaf | ( | int32 | node | ) | [private] |
Definition at line 176 of file b2DynamicTree.cpp.
bool b2DynamicTree::MoveProxy | ( | int32 | proxyId, |
const b2AABB & | aabb1, | ||
const b2Vec2 & | displacement | ||
) |
Move a proxy with a swepted AABB. If the proxy has moved outside of its fattened AABB, then the proxy is removed from the tree and re-inserted. Otherwise the function returns immediately.
Definition at line 130 of file b2DynamicTree.cpp.
void b2DynamicTree::Query | ( | T * | callback, |
const b2AABB & | aabb | ||
) | const [inline] |
Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB.
Definition at line 169 of file b2DynamicTree.h.
void b2DynamicTree::RayCast | ( | T * | callback, |
const b2RayCastInput & | input | ||
) | const [inline] |
Ray-cast against the proxies in the tree. This relies on the callback to perform a exact ray-cast in the case were the proxy contains a shape. The callback also performs the any collision filtering. This has performance roughly equal to k * log(n), where k is the number of collisions and n is the number of proxies in the tree.
input | the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1). |
callback | a callback class that is called for each proxy that is hit by the ray. |
Definition at line 204 of file b2DynamicTree.h.
void b2DynamicTree::RebuildBottomUp | ( | ) |
Build an optimal tree. Very expensive. For testing.
Definition at line 694 of file b2DynamicTree.cpp.
void b2DynamicTree::RemoveLeaf | ( | int32 | node | ) | [private] |
Definition at line 316 of file b2DynamicTree.cpp.
void b2DynamicTree::ShiftOrigin | ( | const b2Vec2 & | newOrigin | ) |
Shift the world origin. Useful for large worlds. The shift formula is: position -= newOrigin
newOrigin | the new origin with respect to the old origin |
Definition at line 770 of file b2DynamicTree.cpp.
void b2DynamicTree::Validate | ( | ) | const |
Validate this tree. For testing.
Definition at line 653 of file b2DynamicTree.cpp.
void b2DynamicTree::ValidateMetrics | ( | int32 | index | ) | const [private] |
Definition at line 614 of file b2DynamicTree.cpp.
void b2DynamicTree::ValidateStructure | ( | int32 | index | ) | const [private] |
Definition at line 579 of file b2DynamicTree.cpp.
int32 b2DynamicTree::m_freeList [private] |
Definition at line 148 of file b2DynamicTree.h.
int32 b2DynamicTree::m_insertionCount [private] |
Definition at line 153 of file b2DynamicTree.h.
int32 b2DynamicTree::m_nodeCapacity [private] |
Definition at line 146 of file b2DynamicTree.h.
int32 b2DynamicTree::m_nodeCount [private] |
Definition at line 145 of file b2DynamicTree.h.
b2TreeNode* b2DynamicTree::m_nodes [private] |
Definition at line 144 of file b2DynamicTree.h.
uint32 b2DynamicTree::m_path [private] |
This is used to incrementally traverse the tree for re-balancing.
Definition at line 151 of file b2DynamicTree.h.
int32 b2DynamicTree::m_root [private] |
Definition at line 142 of file b2DynamicTree.h.