Jazz2::Collisions::DynamicTree class

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. In the tree we expand the proxy AABB by AabbExtension 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.

Constructors, destructors, conversion operators

DynamicTree()
Constructing the tree initializes the node pool.
~DynamicTree()
Destroys the tree, freeing the node pool.

Public functions

auto CreateProxy(const AABBf& aabb, void* userData) -> std::int32_t
Creates a proxy.
void DestroyProxy(std::int32_t proxyId)
Destroys a proxy.
auto MoveProxy(std::int32_t proxyId, const AABBf& aabb1, Vector2f displacement) -> bool
Moves a proxy with a swepted AABB.
auto GetUserData(std::int32_t proxyId) const -> void*
Returns proxy user data.
auto WasMoved(std::int32_t proxyId) const -> bool
Returns true if a proxy was moved.
void ClearMoved(std::int32_t proxyId)
Clears moved status of a proxy.
auto GetFatAABB(std::int32_t proxyId) const -> const AABBf&
Returns the fat AABB for a proxy.
template<typename T>
void Query(T* callback, const AABBf& aabb) const
Queries an AABB for overlapping proxies, the callback is called for each proxy that overlaps the supplied AABB.
void Validate() const
Ray-cast against the proxies in the tree.
auto GetHeight() const -> std::int32_t
Computes the height of the binary tree in $ \mathcal{O}(n) $ time, should not be called often.
auto GetMaxBalance() const -> std::int32_t
Returns the maximum balance of an node in the tree.
auto GetAreaRatio() const -> float
Returns the ratio of the sum of the node areas to the root area.
void RebuildBottomUp()
Build an optimal tree, very expensive — for testing only.
void ShiftOrigin(Vector2f newOrigin)
Shifts the world origin.

Function documentation

bool Jazz2::Collisions::DynamicTree::MoveProxy(std::int32_t proxyId, const AABBf& aabb1, Vector2f displacement)

Moves a proxy with a swepted AABB.

Returns true if the proxy was re-inserted.

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.

void* Jazz2::Collisions::DynamicTree::GetUserData(std::int32_t proxyId) const

Returns proxy user data.

Returns the proxy user data or 0 if the id is invalid.

void Jazz2::Collisions::DynamicTree::Validate() const

Ray-cast against the proxies in the tree.

  • Validates this tree — for testing only

std::int32_t Jazz2::Collisions::DynamicTree::GetMaxBalance() const

Returns the maximum balance of an node in the tree.

The balance is the difference in height of the two children of a node.

void Jazz2::Collisions::DynamicTree::ShiftOrigin(Vector2f newOrigin)

Shifts the world origin.

Parameters
newOrigin the new origin with respect to the old origin

Useful for large worlds. The shift formula is: position -= newOrigin