The dynamic tree is a binary AABB tree to organize and query large numbers of geometric objects. More...

Data Structures
struct	b2TreeStats
	These are performance results returned by dynamic tree queries. More...
struct	b2BoxCastInput
	Input for casting an AABB through a dynamic tree. More...

Typedefs
typedef struct b2DynamicTree	b2DynamicTree
	Opaque dynamic tree. Details are internal.
typedef bool	b2TreeQueryCallbackFcn(int proxyId, uint64_t userData, void *context)
	This function receives proxies found in the AABB query.
typedef float	b2TreeRayCastCallbackFcn(const b2RayCastInput input, int proxyId, uint64_t userData, void context)
	This function receives clipped ray cast input for a proxy.
typedef float	b2TreeBoxCastCallbackFcn(const b2BoxCastInput input, int proxyId, uint64_t userData, void context)
	This function receives clipped AABB cast input for a proxy.

Functions
b2DynamicTree *	b2CreateDynamicTree (int proxyCapacity)
	Constructing the tree initializes the node pool.
void	b2DestroyDynamicTree (b2DynamicTree *tree)
	Destroy the tree, freeing the node pool.
int	b2CreateTreeProxy (b2DynamicTree *tree, b2AABB aabb, uint64_t categoryBits, uint64_t userData)
	Create a proxy. Provide an AABB and a userData value.
void	b2DestroyTreeProxy (b2DynamicTree *tree, int proxyId)
	Destroy a proxy. This asserts if the id is invalid.
void	b2DynamicTree_MoveProxy (b2DynamicTree *tree, int proxyId, b2AABB aabb)
	Move a proxy to a new AABB by removing and reinserting into the tree.
void	b2DynamicTree_SetCategoryBits (b2DynamicTree *tree, int proxyId, uint64_t categoryBits)
	Modify the category bits on a proxy.
uint64_t	b2DynamicTree_GetCategoryBits (b2DynamicTree *tree, int proxyId)
	Get the category bits on a proxy.
b2TreeStats	b2DynamicTree_OverlapAABB (const b2DynamicTree tree, b2AABB aabb, uint64_t maskBits, b2TreeQueryCallbackFcn callback, void *context)
	Query an AABB for overlapping proxies.
b2TreeStats	b2DynamicTree_OverlapAABBAll (const b2DynamicTree tree, b2AABB aabb, b2TreeQueryCallbackFcn callback, void *context)
	Query an AABB for overlapping proxies.
b2TreeStats	b2DynamicTree_CastRay (const b2DynamicTree tree, const b2RayCastInput input, uint64_t maskBits, b2TreeRayCastCallbackFcn callback, void context)
	Ray cast against the proxies in the tree.
b2TreeStats	b2DynamicTree_CastBox (const b2DynamicTree tree, const b2BoxCastInput input, uint64_t maskBits, b2TreeBoxCastCallbackFcn callback, void context)
	Cast a swept AABB through the tree.
int	b2DynamicTree_GetHeight (const b2DynamicTree *tree)
	Get the height of the binary tree.
float	b2DynamicTree_GetAreaRatio (const b2DynamicTree *tree)
	Get the ratio of the sum of the internal node areas to the root area.
b2AABB	b2DynamicTree_GetRootBounds (const b2DynamicTree *tree)
	Get the bounding box that contains the entire tree.
int	b2DynamicTree_GetProxyCount (const b2DynamicTree *tree)
	Get the number of proxies created.
size_t	b2DynamicTree_GetByteCount (const b2DynamicTree *tree)
	Get the number of bytes used by this tree.
uint64_t	b2DynamicTree_GetUserData (const b2DynamicTree *tree, int proxyId)
	Get proxy user data.
b2AABB	b2DynamicTree_GetProxyBounds (const b2DynamicTree *tree, int proxyId)
	Get the AABB of a proxy.
void	b2DynamicTree_Validate (const b2DynamicTree *tree)
	Validate the tree.

Detailed Description

The dynamic tree is a binary AABB tree to organize and query large numbers of geometric objects.

Box2D uses the dynamic tree internally to sort collision shapes into a binary bounding volume hierarchy. This data structure may have uses in games for organizing other geometry data and may be used independently of Box2D rigid body simulation.

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 AABB queries and ray casts. Leaf nodes are proxies with an AABB. These are used to hold a user collision object. Nodes are pooled and relocatable, so I use node indices rather than pointers. The dynamic tree is made available for advanced users that would like to use it to organize spatial game data besides rigid bodies.

Data Structure Documentation

◆ b2TreeStats

struct b2TreeStats

These are performance results returned by dynamic tree queries.

Data Fields
int	leafVisits	Number of leaf nodes visited during the query.
int	nodeVisits	Number of internal nodes visited during the query.

◆ b2BoxCastInput

struct b2BoxCastInput

Input for casting an AABB through a dynamic tree.

Data Fields
b2AABB	box	The AABB to cast, in the tree's frame.
float	maxFraction	The maximum fraction of the translation to consider, typically 1.
b2Vec2	translation	The sweep translation.

Typedef Documentation

◆ b2TreeBoxCastCallbackFcn

typedef float b2TreeBoxCastCallbackFcn(const b2BoxCastInput *input, int proxyId, uint64_t userData, void *context)

This function receives clipped AABB cast input for a proxy.

The function returns the new cast fraction.

return a value of 0 to terminate the cast
return a value less than input->maxFraction to clip the cast
return a value of input->maxFraction to continue the cast without clipping

◆ b2TreeQueryCallbackFcn

typedef bool b2TreeQueryCallbackFcn(int proxyId, uint64_t userData, void *context)

This function receives proxies found in the AABB query.

Returns: true if the query should continue

◆ b2TreeRayCastCallbackFcn

typedef float b2TreeRayCastCallbackFcn(const b2RayCastInput *input, int proxyId, uint64_t userData, void *context)

This function receives clipped ray cast input for a proxy.

The function returns the new ray fraction.

return a value of 0 to terminate the ray cast
return a value less than input->maxFraction to clip the ray
return a value of input->maxFraction to continue the ray cast without clipping

Function Documentation

◆ b2DynamicTree_CastBox()

b2TreeStats b2DynamicTree_CastBox	(	const b2DynamicTree *	tree,
		const b2BoxCastInput *	input,
		uint64_t	maskBits,
		b2TreeBoxCastCallbackFcn *	callback,
		void *	context )

Cast a swept AABB through the tree.

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.

Parameters

tree	the dynamic tree to cast through
input	the AABB cast input. The box sweeps from its origin to origin + maxFraction * translation.
maskBits	filter bits: bool accept = (maskBits & proxy->categoryBits) != 0;
callback	a callback that is called for each proxy the swept box may hit
context	user context that is passed to the callback

Returns: performance data

◆ b2DynamicTree_CastRay()

b2TreeStats b2DynamicTree_CastRay	(	const b2DynamicTree *	tree,
		const b2RayCastInput *	input,
		uint64_t	maskBits,
		b2TreeRayCastCallbackFcn *	callback,
		void *	context )

Ray cast against the proxies in the tree.

This relies on the callback to perform an exact ray cast in the case where the proxy contains a shape. The callback also performs 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. Bit-wise filtering using mask bits can improve performance in some scenarios. However, this filtering may be approximate, so the user should still apply filtering to results.

Parameters

tree	the dynamic tree to ray cast
input	the ray cast input data.
maskBits	mask bits used to filter proxies.
callback	a callback that is called for each proxy that is hit by the ray
context	user context that is passed to the callback

Returns: performance data

◆ b2DynamicTree_OverlapAABB()

b2TreeStats b2DynamicTree_OverlapAABB	(	const b2DynamicTree *	tree,
		b2AABB	aabb,
		uint64_t	maskBits,
		b2TreeQueryCallbackFcn *	callback,
		void *	context )

Query an AABB for overlapping proxies.

The callback is called for each proxy that overlaps the supplied AABB.

Returns: performance data

◆ b2DynamicTree_OverlapAABBAll()

b2TreeStats b2DynamicTree_OverlapAABBAll	(	const b2DynamicTree *	tree,
		b2AABB	aabb,
		b2TreeQueryCallbackFcn *	callback,
		void *	context )