A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt. More...

#include <DynamicTree.hpp>

Public Types
using	size_type = std::remove_const< decltype(MaxContacts)>::type

using	QueryCallback = std::function< bool(size_type)>

using	RayCastCallback = std::function< RealNum(const RayCastInput &, size_type)>

Public Member Functions
	DynamicTree (const size_type nodeCapacity=GetDefaultInitialNodeCapacity())
	Constructing the tree initializes the node pool. More...

	~DynamicTree () noexcept
	Destroys the tree, freeing the node pool. More...

	DynamicTree (const DynamicTree &copy)=delete

DynamicTree &	operator= (const DynamicTree &)=delete

size_type	CreateProxy (const AABB aabb, void *userData)
	Creates a new proxy. More...

void	DestroyProxy (const size_type index)
	Destroys a proxy. More...

bool	UpdateProxy (const size_type index, const AABB aabb, const Length2D displacement, const RealNum multiplier=1, const Length extension=Length{0})
	Updates a proxy. More...

void *	GetUserData (const size_type index) const noexcept
	Gets the user data for the node identified by the given identifier. More...

AABB	GetFatAABB (const size_type index) const noexcept
	Gets the fat AABB for a proxy. More...

void	Query (const AABB aabb, QueryCallback callback) const
	Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB. More...

void	RayCast (const RayCastInput &input, RayCastCallback callback) const
	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. More...

bool	Validate () const
	Validates this tree. More...

bool	ValidateStructure (const size_type index) const noexcept
	Validates the structure of this tree from the given index. More...

bool	ValidateMetrics (size_type index) const noexcept
	Validates the metrics of this tree from the given index. More...

size_type	GetHeight () const noexcept
	Gets the height of the binary tree. More...

size_type	GetMaxBalance () const
	Gets the maximum balance. More...

RealNum	GetAreaRatio () const noexcept
	Gets the ratio of the sum of the perimeters of nodes to the root perimeter. More...

void	RebuildBottomUp ()
	Builds an optimal tree. More...

void	ShiftOrigin (const Length2D newOrigin)
	Shifts the world origin. More...

size_type	ComputeHeight (const size_type nodeId) const noexcept
	Computes the height of the tree from a given node. More...

size_type	ComputeHeight () const noexcept
	Computes the height of the tree from its root. More...

size_type	GetNodeCapacity () const noexcept
	Gets the current node capacity of this tree. More...

size_type	GetNodeCount () const noexcept
	Gets the current node count. More...

size_type	FindLowestCostNode (const AABB leafAABB) const noexcept
	Finds the lowest cost node. More...

Static Public Member Functions
static constexpr size_type	GetDefaultInitialNodeCapacity () noexcept

Static Public Attributes
static constexpr auto	AabbMultiplier = 2

static constexpr size_type	InvalidIndex = static_cast<size_type>(-1)
	Invalid index value. More...

Detailed Description

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 AabbMultiplier 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.

Note: This data structure is 24-bytes large (on at least one 64-bit platform).

Member Typedef Documentation

◆ QueryCallback

using box2d::DynamicTree::QueryCallback = std::function<bool(size_type)>

◆ RayCastCallback

using box2d::DynamicTree::RayCastCallback = std::function<RealNum(const RayCastInput&, size_type)>

◆ size_type

using box2d::DynamicTree::size_type = std::remove_const<decltype(MaxContacts)>::type

Constructor & Destructor Documentation

◆ DynamicTree() [1/2]

DynamicTree::DynamicTree ( const size_type nodeCapacity = GetDefaultInitialNodeCapacity() )

Constructing the tree initializes the node pool.

◆ ~DynamicTree()

DynamicTree::~DynamicTree ( )

noexcept

Destroys the tree, freeing the node pool.

◆ DynamicTree() [2/2]

box2d::DynamicTree::DynamicTree ( const DynamicTree & copy )

delete

Member Function Documentation

◆ ComputeHeight() [1/2]

DynamicTree::size_type DynamicTree::ComputeHeight ( const size_type nodeId ) const

noexcept

Computes the height of the tree from a given node.

Warning: Behavior is undefined if the given index is not valid.

Parameters

nodeId ID of node to compute height from.

◆ ComputeHeight() [2/2]

DynamicTree::size_type box2d::DynamicTree::ComputeHeight ( ) const

inlinenoexcept

Computes the height of the tree from its root.

Warning: Behavior is undefined if the tree doesn't have a valid root.

◆ CreateProxy()

DynamicTree::size_type DynamicTree::CreateProxy	(	const AABB	aabb,
		void *	userData
	)

Creates a new proxy.

Creates a proxy for a tight fitting AABB and a userData pointer.

Note: The indices of proxies that have been destroyed get reused for new proxies.

Returns: Index of the created proxy.

◆ DestroyProxy()

void DynamicTree::DestroyProxy ( const size_type index )

Destroys a proxy.

Warning: Behavior is undefined if the given index is not valid.

◆ FindLowestCostNode()

DynamicTree::size_type DynamicTree::FindLowestCostNode ( const AABB leafAABB ) const

noexcept

Finds the lowest cost node.

Warning: Behavior is undefined if the tree doesn't have a valid root.

◆ GetAreaRatio()

RealNum DynamicTree::GetAreaRatio ( ) const

noexcept

Gets the ratio of the sum of the perimeters of nodes to the root perimeter.

Note: Zero is returned if no proxies exist at the time of the call.

Returns: Value of zero or more.

◆ GetDefaultInitialNodeCapacity()

constexpr DynamicTree::size_type box2d::DynamicTree::GetDefaultInitialNodeCapacity ( )

staticnoexcept

◆ GetFatAABB()

AABB box2d::DynamicTree::GetFatAABB ( const size_type index ) const

inlinenoexcept

Gets the fat AABB for a proxy.

Warning: Behavior is undefined if the given index is not valid.

Parameters

index Proxy ID. Must be a valid ID.

◆ GetHeight()

DynamicTree::size_type box2d::DynamicTree::GetHeight ( ) const

inlinenoexcept

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.

◆ GetMaxBalance()

DynamicTree::size_type DynamicTree::GetMaxBalance ( ) const

Gets the maximum balance.

This gets the maximum balance of nodes in the tree.

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

◆ GetNodeCapacity()

DynamicTree::size_type box2d::DynamicTree::GetNodeCapacity ( ) const

inlinenoexcept

Gets the current node capacity of this tree.

◆ GetNodeCount()

DynamicTree::size_type box2d::DynamicTree::GetNodeCount ( ) const

inlinenoexcept

Gets the current node count.

Returns: Count of existing proxies (count of nodes currently allocated).

◆ GetUserData()

void * box2d::DynamicTree::GetUserData ( const size_type index ) const

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.

◆ operator=()

DynamicTree& box2d::DynamicTree::operator= ( const DynamicTree & )

delete

◆ Query()

void DynamicTree::Query	(	const AABB	aabb,
		QueryCallback	callback
	)		const

Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB.

◆ RayCast()

void DynamicTree::RayCast	(	const RayCastInput &	input,
		RayCastCallback	callback
	)		const

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.

Note: Performance is roughly k * log(n), where k is the number of collisions and n is the number of proxies in the tree.

Parameters

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.

◆ RebuildBottomUp()

void DynamicTree::RebuildBottomUp ( )

Builds an optimal tree.

Note: This operation is very expensive.; Meant for testing.

◆ ShiftOrigin()

void DynamicTree::ShiftOrigin ( const Length2D 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

◆ UpdateProxy()

bool DynamicTree::UpdateProxy	(	const size_type	index,
		const AABB	aabb,
		const Length2D	displacement,
		const RealNum	multiplier = `1`,
		const Length	extension = `Length{0}`
	)

Updates a proxy.

Note: If the stored AABB of the identified proxy doesn't contain the given new AABB of the proxy, then the proxy is removed from the tree and re-inserted with a fattened and displaced version of the given new AABB.

Warning: Behavior is undefined if the given index is not valid.

Parameters

index	Proxy ID. Behavior is undefined if this is not a valid ID.
aabb	New axis aligned bounding box of the proxy.
displacement	Displacement of the proxy. Behavior undefined if not a valid value.
multiplier	Multiplier to displacement amount for new AABB. This is used to predict the future position based on the current displacement. This is a dimensionless multiplier.
extension	Extension. Amount to fatten the given AABB by if the proxy does not contain it.

Returns: true if the proxy was re-inserted, false otherwise.

◆ Validate()

bool DynamicTree::Validate ( ) const

Validates this tree.

Note: Meant for testing.

Returns: true if valid, false otherwise.

◆ ValidateMetrics()

bool DynamicTree::ValidateMetrics ( size_type index ) const

noexcept

Validates the metrics of this tree from the given index.

Note: Meant for testing.

Returns: true if valid, false otherwise.

◆ ValidateStructure()

bool DynamicTree::ValidateStructure ( const size_type index ) const

noexcept

Validates the structure of this tree from the given index.

Note: Meant for testing.

Returns: true if valid, false otherwise.

Member Data Documentation

◆ AabbMultiplier

constexpr auto box2d::DynamicTree::AabbMultiplier = 2

static

◆ InvalidIndex

constexpr size_type box2d::DynamicTree::InvalidIndex = static_cast<size_type>(-1)

static

Invalid index value.

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ QueryCallback

◆ RayCastCallback

◆ size_type

Constructor & Destructor Documentation

◆ DynamicTree() [1/2]

◆ ~DynamicTree()

◆ DynamicTree() [2/2]

Member Function Documentation

◆ ComputeHeight() [1/2]

◆ ComputeHeight() [2/2]

◆ CreateProxy()

◆ DestroyProxy()

◆ FindLowestCostNode()

◆ GetAreaRatio()

◆ GetDefaultInitialNodeCapacity()

◆ GetFatAABB()

◆ GetHeight()

◆ GetMaxBalance()

◆ GetNodeCapacity()

◆ GetNodeCount()

◆ GetUserData()

◆ operator=()

◆ Query()

◆ RayCast()

◆ RebuildBottomUp()

◆ ShiftOrigin()

◆ UpdateProxy()

◆ Validate()

◆ ValidateMetrics()

◆ ValidateStructure()

Member Data Documentation

◆ AabbMultiplier

◆ InvalidIndex