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

All Implemented Interfaces:

BroadPhaseStrategy
```
public class DynamicTree
extends java.lang.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.

Nested Class Summary

Nested Classes
Modifier and Type Class Description

class DynamicTree.TreeNodeStack

Field Summary

Fields
Modifier and Type	Field	Description
`private AABB`	`aabb`
`private Color3f`	`color`
`private AABB`	`combinedAABB`
`private Vec2[]`	`drawVecs`
`private int`	`m_freeList`
`private int`	`m_insertionCount`
`private int`	`m_nodeCapacity`
`private int`	`m_nodeCount`
`private DynamicTreeNode[]`	`m_nodes`
`private DynamicTreeNode`	`m_root`
`static int`	`MAX_STACK_SIZE`
`private DynamicTree.TreeNodeStack`	`nodeStack`
`static int`	`NULL_NODE`
`private Vec2`	`r`
`private RayCastInput`	`subInput`
`private Vec2`	`textVec`

Constructor Summary

Constructors
Constructor Description

DynamicTree()

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private DynamicTreeNode`	`allocateNode()`
`private DynamicTreeNode`	`balance(DynamicTreeNode iA)`
`int`	`computeHeight()`	Compute the height of the tree.
`private int`	`computeHeight(DynamicTreeNode node)`
`int`	`createProxy(AABB aabb, java.lang.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)`
`private void`	`freeNode(DynamicTreeNode node)`	returns a node to the pool
`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.
`java.lang.Object`	`getUserData(int proxyId)`
`private void`	`insertLeaf(int leaf_index)`
`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.
`private void`	`removeLeaf(DynamicTreeNode leaf)`
`void`	`validate()`	Validate this tree.
`private void`	`validateMetrics(DynamicTreeNode node)`
`private void`	`validateStructure(DynamicTreeNode node)`

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
  - m_root
```
private DynamicTreeNode m_root
```
  - m_nodes
```
private DynamicTreeNode[] m_nodes
```
  - m_nodeCount
```
private int m_nodeCount
```
  - m_nodeCapacity
```
private int m_nodeCapacity
```
  - m_freeList
```
private int m_freeList
```
  - m_insertionCount
```
private int m_insertionCount
```
  - drawVecs
```
private final Vec2[] drawVecs
```
  - nodeStack
```
private final DynamicTree.TreeNodeStack nodeStack
```
  - r
```
private final Vec2 r
```
  - aabb
```
private final AABB aabb
```
  - subInput
```
private final RayCastInput subInput
```
  - combinedAABB
```
private final AABB combinedAABB
```
  - color
```
private final Color3f color
```
  - textVec
```
private final Vec2 textVec
```
- Constructor Detail
  - DynamicTree
```
public DynamicTree()
```
- Method Detail
  - createProxy
```
public final int createProxy(AABB aabb,
                             java.lang.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 java.lang.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
  - computeHeight
```
private final int computeHeight(DynamicTreeNode node)
```
  - 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.
  - allocateNode
```
private final DynamicTreeNode allocateNode()
```
  - freeNode
```
private final void freeNode(DynamicTreeNode node)
```
    returns a node to the pool
  - getInsertionCount
```
public int getInsertionCount()
```
    Specified by:
    
    getInsertionCount in interface BroadPhaseStrategy
  - insertLeaf
```
private final void insertLeaf(int leaf_index)
```
  - removeLeaf
```
private final void removeLeaf(DynamicTreeNode leaf)
```
  - balance
```
private DynamicTreeNode balance(DynamicTreeNode iA)
```
  - validateStructure
```
private void validateStructure(DynamicTreeNode node)
```
  - validateMetrics
```
private void validateMetrics(DynamicTreeNode node)
```
  - drawTree
```
public void drawTree(DebugDraw argDraw)
```
    Specified by:
    
    drawTree in interface BroadPhaseStrategy
  - drawTree
```
public void drawTree(DebugDraw argDraw,
                     DynamicTreeNode node,
                     int spot,
                     int height)
```

Class DynamicTree

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

MAX_STACK_SIZE

NULL_NODE

m_root

m_nodes

m_nodeCount

m_nodeCapacity

m_freeList

m_insertionCount

drawVecs

nodeStack

r

aabb

subInput

combinedAABB

color

textVec

Constructor Detail

DynamicTree

Method Detail

createProxy

destroyProxy

moveProxy

getUserData

getFatAABB

query

raycast

computeHeight

computeHeight

validate

getHeight

getMaxBalance

getAreaRatio

rebuildBottomUp

allocateNode

freeNode

getInsertionCount

insertLeaf

removeLeaf

balance

validateStructure

validateMetrics

drawTree

drawTree