Dynamic Tree

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

Data Structures
struct	b2DynamicTree
	The dynamic tree structure. More...
struct	b2TreeStats
	These are performance results returned by dynamic tree queries. More...

Typedefs
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	b2TreeShapeCastCallbackFcn(const b2ShapeCastInput *input, int proxyId, uint64_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.
int	b2DynamicTree_CreateProxy (b2DynamicTree *tree, b2AABB aabb, uint64_t categoryBits, uint64_t userData)
	Create a proxy. Provide an AABB and a userData value.
void	b2DynamicTree_DestroyProxy (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_EnlargeProxy (b2DynamicTree *tree, int proxyId, b2AABB aabb)
	Enlarge a proxy and enlarge ancestors as necessary.
void	b2DynamicTree_SetCategoryBits (b2DynamicTree *tree, int proxyId, uint64_t categoryBits)
	Modify the category bits on a proxy. This is an expensive operation.
uint64_t	b2DynamicTree_GetCategoryBits (b2DynamicTree *tree, int proxyId)
	Get the category bits on a proxy.
b2TreeStats	b2DynamicTree_Query (const b2DynamicTree *tree, b2AABB aabb, uint64_t maskBits, b2TreeQueryCallbackFcn *callback, void *context)
	Query an AABB for overlapping proxies.
b2TreeStats	b2DynamicTree_RayCast (const b2DynamicTree *tree, const b2RayCastInput *input, uint64_t maskBits, b2TreeRayCastCallbackFcn *callback, void *context)
	Ray cast against the proxies in the tree.
b2TreeStats	b2DynamicTree_ShapeCast (const b2DynamicTree *tree, const b2ShapeCastInput *input, uint64_t maskBits, b2TreeShapeCastCallbackFcn *callback, void *context)
	Ray cast against the proxies in 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 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.
int	b2DynamicTree_Rebuild (b2DynamicTree *tree, bool fullBuild)
	Rebuild the tree while retaining subtrees that haven't changed. Returns the number of boxes sorted.
int	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_GetAABB (const b2DynamicTree *tree, int proxyId)
	Get the AABB of a proxy.
void	b2DynamicTree_Validate (const b2DynamicTree *tree)
	Validate this tree. For testing.
void	b2DynamicTree_ValidateNoEnlarged (const b2DynamicTree *tree)
	Validate this tree has no enlarged AABBs. For testing.

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

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
int *	binIndices	Bins for sorting during rebuild.
int	freeList	Node free list.
b2AABB *	leafBoxes	Leaf bounding boxes for rebuild.
b2Vec2 *	leafCenters	Leaf bounding box centers for rebuild.
int *	leafIndices	Leaf indices for rebuild.
int	nodeCapacity	The allocated node space.
int	nodeCount	The number of nodes.
struct b2TreeNode *	nodes	The tree nodes.
int	proxyCount	Number of proxies created.
int	rebuildCapacity	Allocated space for rebuilding.
int	root	The root index.

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.

Typedef Documentation

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

b2TreeShapeCastCallbackFcn

typedef float b2TreeShapeCastCallbackFcn(const b2ShapeCastInput *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_Query()

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

Returns

performance data

b2DynamicTree_RayCast()

b2TreeStats 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. 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. The ray extends from p1 to p1 + maxFraction * (p2 - p1)
maskBits	mask bit hint: 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

Returns

performance data

b2DynamicTree_ShapeCast()

b2TreeStats 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

Returns

performance data