b2DynamicTree Class Reference

#include <b2_dynamic_tree.h>

Public Member Functions
	b2DynamicTree ()
	Constructing the tree initializes the node pool.
	~b2DynamicTree ()
	Destroy the tree, freeing the node pool.
int32	CreateProxy (const b2AABB &aabb, void *userData)
	Create a proxy. Provide a tight fitting AABB and a userData pointer.
void	DestroyProxy (int32 proxyId)
	Destroy a proxy. This asserts if the id is invalid.
bool	MoveProxy (int32 proxyId, const b2AABB &aabb1, const b2Vec2 &displacement)
void *	GetUserData (int32 proxyId) const
bool	WasMoved (int32 proxyId) const
void	ClearMoved (int32 proxyId)
const b2AABB &	GetFatAABB (int32 proxyId) const
	Get the fat AABB for a proxy.
template<typename T >
void	Query (T *callback, const b2AABB &aabb) const
template<typename T >
void	RayCast (T *callback, const b2RayCastInput &input) const
void	Validate () const
	Validate this tree. For testing.
int32	GetHeight () const
int32	GetMaxBalance () const
float	GetAreaRatio () const
	Get the ratio of the sum of the node areas to the root area.
void	RebuildBottomUp ()
	Build an optimal tree. Very expensive. For testing.
void	ShiftOrigin (const b2Vec2 &newOrigin)

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

Member Function Documentation

GetHeight()

int32 b2DynamicTree::GetHeight

(

)

const

Compute the height of the binary tree in O(N) time. Should not be called often.

GetMaxBalance()

int32 b2DynamicTree::GetMaxBalance

(

)

const

Get the maximum balance of an node in the tree. The balance is the difference in height of the two children of a node.

GetUserData()

void * b2DynamicTree::GetUserData ( int32  proxyId ) const

inline

Get proxy user data.

Returns

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

MoveProxy()

bool b2DynamicTree::MoveProxy	(	int32	proxyId,
		const b2AABB &	aabb1,
		const b2Vec2 &	displacement
	)

Move a proxy with a swepted AABB. 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.

Returns

true if the proxy was re-inserted.

Query()

template<typename T >

void b2DynamicTree::Query ( T *  callback, const b2AABB &  aabb  ) const

inline

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

RayCast()

template<typename T >

void b2DynamicTree::RayCast ( T *  callback, const b2RayCastInput &  input  ) const

inline

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

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.

ShiftOrigin()

void b2DynamicTree::ShiftOrigin

(

const b2Vec2 &

newOrigin

)

Shift the world origin. Useful for large worlds. The shift formula is: position -= newOrigin

Parameters

newOrigin

the new origin with respect to the old origin

---

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

• include/box2d/b2_dynamic_tree.h