Package org.jbox2d.collision.broadphase
Class DynamicTree
- 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 proxyvoid
drawTree(DebugDraw argDraw)
void
drawTree(DebugDraw argDraw, DynamicTreeNode node, int spot, int height)
private void
freeNode(DynamicTreeNode node)
returns a node to the poolfloat
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)
-
-
-
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
-
-
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 interfaceBroadPhaseStrategy
- Returns:
-
destroyProxy
public final void destroyProxy(int proxyId)
Description copied from interface:BroadPhaseStrategy
Destroy a proxy- Specified by:
destroyProxy
in interfaceBroadPhaseStrategy
-
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 interfaceBroadPhaseStrategy
- Returns:
- true if the proxy was re-inserted.
-
getUserData
public final java.lang.Object getUserData(int proxyId)
- Specified by:
getUserData
in interfaceBroadPhaseStrategy
-
getFatAABB
public final AABB getFatAABB(int proxyId)
- Specified by:
getFatAABB
in interfaceBroadPhaseStrategy
-
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 interfaceBroadPhaseStrategy
-
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 interfaceBroadPhaseStrategy
- 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 interfaceBroadPhaseStrategy
-
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 interfaceBroadPhaseStrategy
- 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 interfaceBroadPhaseStrategy
- 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 interfaceBroadPhaseStrategy
- 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 interfaceBroadPhaseStrategy
-
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 interfaceBroadPhaseStrategy
-
drawTree
public void drawTree(DebugDraw argDraw, DynamicTreeNode node, int spot, int height)
-
-