org.jbox2d.collision.broadphase
Class DynamicTree

java.lang.Object
  org.jbox2d.collision.broadphase.DynamicTree

All Implemented Interfaces:

BroadPhaseStrategy

public class DynamicTree
extends Object
implements BroadPhaseStrategy

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

Author:

daniel

Nested Class Summary

class

DynamicTree.TreeNodeStack

Field Summary

static int	MAX_STACK_SIZE
static int	NULL_NODE

Constructor Summary

DynamicTree()

Method Summary

int	computeHeight() Compute the height of the tree.
int	createProxy(AABB aabb, Object userData) Create a proxy.
void	destroyProxy(int proxyId) Destroy a proxy
void	drawTree(DebugDraw argDraw)
void	drawTree(DebugDraw argDraw, DynamicTreeNode node, int spot, int height)
float	getAreaRatio() Get the ratio of the sum of the node areas to the root area.
AABB	getFatAABB(int proxyId)
int	getHeight() Compute the height of the binary tree in O(N) time.
int	getInsertionCount()
int	getMaxBalance() Get the maximum balance of an node in the tree.
Object	getUserData(int proxyId)
boolean	moveProxy(int proxyId, AABB aabb, Vec2 displacement) Move a proxy with a swepted AABB.
void	query(TreeCallback callback, AABB aabb) Query an AABB for overlapping proxies.
void	raycast(TreeRayCastCallback callback, RayCastInput input) Ray-cast against the proxies in the tree.
void	rebuildBottomUp() Build an optimal tree.
void	validate() Validate this tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

MAX_STACK_SIZE

public static final int MAX_STACK_SIZE

See Also:

Constant Field Values

NULL_NODE

public static final int NULL_NODE

See Also:

Constant Field Values

Constructor Detail

DynamicTree

public DynamicTree()

Method Detail

createProxy

public final int createProxy(AABB aabb,
                             Object userData)

Description copied from interface: BroadPhaseStrategy

Create a proxy. Provide a tight fitting AABB and a userData pointer.

Specified by:

createProxy in interface BroadPhaseStrategy

Returns:

destroyProxy

public final void destroyProxy(int proxyId)

Description copied from interface: BroadPhaseStrategy

Destroy a proxy

Specified by:

destroyProxy in interface BroadPhaseStrategy

moveProxy

public final boolean moveProxy(int proxyId,
                               AABB aabb,
                               Vec2 displacement)

Description copied from interface: BroadPhaseStrategy

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.

Specified by:

moveProxy in interface BroadPhaseStrategy

Returns:

true if the proxy was re-inserted.

getUserData

public final Object getUserData(int proxyId)

Specified by:

getUserData in interface BroadPhaseStrategy

getFatAABB

public final AABB getFatAABB(int proxyId)

Specified by:

getFatAABB in interface BroadPhaseStrategy

query

public final void query(TreeCallback callback,
                        AABB aabb)

Description copied from interface: BroadPhaseStrategy

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

Specified by:

query in interface BroadPhaseStrategy

raycast

public void raycast(TreeRayCastCallback callback,
                    RayCastInput input)

Description copied from interface: BroadPhaseStrategy

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.

Specified by:

raycast in interface BroadPhaseStrategy

Parameters:

callback - a callback class that is called for each proxy that is hit by the ray.

input - the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).

computeHeight

public final int computeHeight()

Description copied from interface: BroadPhaseStrategy

Compute the height of the tree.

Specified by:

computeHeight in interface BroadPhaseStrategy

validate

public void validate()

Validate this tree. For testing.

getHeight

public int getHeight()

Description copied from interface: BroadPhaseStrategy

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

Specified by:

getHeight in interface BroadPhaseStrategy

Returns:

getMaxBalance

public int getMaxBalance()

Description copied from interface: BroadPhaseStrategy

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

Specified by:

getMaxBalance in interface BroadPhaseStrategy

Returns:

getAreaRatio

public float getAreaRatio()

Description copied from interface: BroadPhaseStrategy

Get the ratio of the sum of the node areas to the root area.

Specified by:

getAreaRatio in interface BroadPhaseStrategy

Returns:

rebuildBottomUp

public void rebuildBottomUp()

Build an optimal tree. Very expensive. For testing.

getInsertionCount

public int getInsertionCount()

Specified by:

getInsertionCount in interface BroadPhaseStrategy

drawTree

public void drawTree(DebugDraw argDraw)

Specified by:

drawTree in interface BroadPhaseStrategy

drawTree

public void drawTree(DebugDraw argDraw,
                     DynamicTreeNode node,
                     int spot,
                     int height)