Dynamic Tree

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

Data Structures
struct	b2TreeNode
	A node in the dynamic tree. This is private data placed here for performance reasons. More...
struct	b2DynamicTree
	The dynamic tree structure. More...
union	b2TreeNode.__unnamed1__

Macros
#define	b2_defaultCategoryBits   ( 1 )
	The default category bit for a tree proxy. Used for collision filtering.
#define	b2_defaultMaskBits   ( UINT64_MAX )
	Convenience mask bits to use when you don't need collision filtering and just want all results.

Typedefs
typedef bool	b2TreeQueryCallbackFcn(int32_t proxyId, int32_t userData, void *context)
	This function receives proxies found in the AABB query.
typedef float	b2TreeRayCastCallbackFcn(const b2RayCastInput *input, int32_t proxyId, int32_t userData, void *context)
	This function receives clipped raycast input for a proxy.
typedef float	b2TreeShapeCastCallbackFcn(const b2ShapeCastInput *input, int32_t proxyId, int32_t userData, void *context)
	This function receives clipped ray-cast input for a proxy.

Functions
b2DynamicTree	b2DynamicTree_Create (void)
	Constructing the tree initializes the node pool.
void	b2DynamicTree_Destroy (b2DynamicTree *tree)
	Destroy the tree, freeing the node pool.
int32_t	b2DynamicTree_CreateProxy (b2DynamicTree *tree, b2AABB aabb, uint64_t categoryBits, int32_t userData)
	Create a proxy. Provide an AABB and a userData value.
void	b2DynamicTree_DestroyProxy (b2DynamicTree *tree, int32_t proxyId)
	Destroy a proxy. This asserts if the id is invalid.
void	b2DynamicTree_MoveProxy (b2DynamicTree *tree, int32_t proxyId, b2AABB aabb)
	Move a proxy to a new AABB by removing and reinserting into the tree.
void	b2DynamicTree_EnlargeProxy (b2DynamicTree *tree, int32_t proxyId, b2AABB aabb)
	Enlarge a proxy and enlarge ancestors as necessary.
void	b2DynamicTree_Query (const b2DynamicTree *tree, b2AABB aabb, uint64_t maskBits, b2TreeQueryCallbackFcn *callback, void *context)
	Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB.
void	b2DynamicTree_RayCast (const b2DynamicTree *tree, const b2RayCastInput *input, uint64_t maskBits, b2TreeRayCastCallbackFcn *callback, void *context)
	Ray-cast against the proxies in the tree.
void	b2DynamicTree_ShapeCast (const b2DynamicTree *tree, const b2ShapeCastInput *input, uint64_t maskBits, b2TreeShapeCastCallbackFcn *callback, void *context)
	Ray-cast against the proxies in the tree.
void	b2DynamicTree_Validate (const b2DynamicTree *tree)
	Validate this tree. For testing.
int	b2DynamicTree_GetHeight (const b2DynamicTree *tree)
	Compute the height of the binary tree in O(N) time.
int	b2DynamicTree_GetMaxBalance (const b2DynamicTree *tree)
	Get the maximum balance of the tree. The balance is the difference in height of the two children of a node.
float	b2DynamicTree_GetAreaRatio (const b2DynamicTree *tree)
	Get the ratio of the sum of the node areas to the root area.
void	b2DynamicTree_RebuildBottomUp (b2DynamicTree *tree)
	Build an optimal tree. Very expensive. For testing.
int	b2DynamicTree_GetProxyCount (const b2DynamicTree *tree)
	Get the number of proxies created.
int	b2DynamicTree_Rebuild (b2DynamicTree *tree, bool fullBuild)
	Rebuild the tree while retaining subtrees that haven't changed. Returns the number of boxes sorted.
void	b2DynamicTree_ShiftOrigin (b2DynamicTree *tree, b2Vec2 newOrigin)
	Shift the world origin.
int	b2DynamicTree_GetByteCount (const b2DynamicTree *tree)
	Get the number of bytes used by this tree.
int32_t	b2DynamicTree_GetUserData (const b2DynamicTree *tree, int32_t proxyId)
	Get proxy user data.
b2AABB	b2DynamicTree_GetAABB (const b2DynamicTree *tree, int32_t proxyId)
	Get the AABB of a proxy.

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, such as a reference to a b2Shape. 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.

Note

This is an advanced feature and normally not used by applications directly.

---

Data Structure Documentation

b2TreeNode

struct b2TreeNode

A node in the dynamic tree. This is private data placed here for performance reasons.

Collaboration diagram for b2TreeNode:

Data Fields
union b2TreeNode.__unnamed1__	__unnamed__
b2AABB	aabb	The node bounding box.
uint64_t	categoryBits	Category bits for collision filtering.
int32_t	child1	Child 1 index.
int32_t	child2	Child 2 index.
bool	enlarged	Has the AABB been enlarged?
int16_t	height	Leaf = 0, free node = -1.
char	pad[5]	Padding for clarity.
int32_t	userData	User data.

b2DynamicTree

struct b2DynamicTree

The dynamic tree structure.

This should be considered private data. It is placed here for performance reasons.

Collaboration diagram for b2DynamicTree:

Data Fields
int32_t *	binIndices	Bins for sorting during rebuild.
int32_t	freeList	Node free list.
b2AABB *	leafBoxes	Leaf bounding boxes for rebuild.
b2Vec2 *	leafCenters	Leaf bounding box centers for rebuild.
int32_t *	leafIndices	Leaf indices for rebuild.
int32_t	nodeCapacity	The allocated node space.
int32_t	nodeCount	The number of nodes.
b2TreeNode *	nodes	The tree nodes.
int32_t	proxyCount	Number of proxies created.
int32_t	rebuildCapacity	Allocated space for rebuilding.
int32_t	root	The root index.

b2TreeNode.__unnamed1__

union b2TreeNode.__unnamed1__

Data Fields
int32_t	next	The node freelist next index.
int32_t	parent	The node parent index.

Typedef Documentation

b2TreeQueryCallbackFcn

typedef bool b2TreeQueryCallbackFcn(int32_t proxyId, int32_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, int32_t proxyId, int32_t userData, void *context)

This function receives clipped raycast 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

b2TreeShapeCastCallbackFcn

typedef float b2TreeShapeCastCallbackFcn(const b2ShapeCastInput *input, int32_t proxyId, int32_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_GetHeight()

int b2DynamicTree_GetHeight

(

const b2DynamicTree *

tree

)

Compute the height of the binary tree in O(N) time.

Should not be called often.

b2DynamicTree_GetUserData()

int32_t b2DynamicTree_GetUserData	(	const b2DynamicTree *	tree,
		int32_t	proxyId )

Get proxy user data.

Returns

the proxy user data or 0 if the id is invalid

b2DynamicTree_RayCast()

void b2DynamicTree_RayCast	(	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 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. Bit-wise filtering using mask bits can greatly improve performance in some scenarios.

Parameters

tree	the dynamic tree to ray cast
input	the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1)
maskBits	filter bits: bool accept = (maskBits & node->categoryBits) != 0;
callback	a callback class that is called for each proxy that is hit by the ray
context	user context that is passed to the callback

b2DynamicTree_ShapeCast()

void b2DynamicTree_ShapeCast	(	const b2DynamicTree *	tree,
		const b2ShapeCastInput *	input,
		uint64_t	maskBits,
		b2TreeShapeCastCallbackFcn *	callback,
		void *	context )

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.

Parameters

tree	the dynamic tree to ray cast
input	the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
maskBits	filter bits: bool accept = (maskBits & node->categoryBits) != 0;
callback	a callback class that is called for each proxy that is hit by the shape
context	user context that is passed to the callback

b2DynamicTree_ShiftOrigin()

void b2DynamicTree_ShiftOrigin	(	b2DynamicTree *	tree,
		b2Vec2	newOrigin )

Shift the world origin.

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

Parameters

tree	the tree to shift
newOrigin	the new origin with respect to the old origin