Package org.jbox2d.collision.broadphase
Class DynamicTree
java.lang.Object
org.jbox2d.collision.broadphase.DynamicTree
- All Implemented Interfaces:
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 -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final AABB
private final Color3f
private final AABB
private final Vec2[]
private int
private int
private int
private int
private DynamicTreeNode[]
private DynamicTreeNode
static final int
private final DynamicTree.TreeNodeStack
static final int
private final Vec2
private final RayCastInput
private final Vec2
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate final DynamicTreeNode
private DynamicTreeNode
final int
Compute the height of the tree.private final int
computeHeight
(DynamicTreeNode node) final int
createProxy
(AABB aabb, java.lang.Object userData) Create a proxy.final void
destroyProxy
(int proxyId) Destroy a proxyvoid
void
drawTree
(DebugDraw argDraw, DynamicTreeNode node, int spot, int height) private final void
freeNode
(DynamicTreeNode node) returns a node to the poolfloat
Get the ratio of the sum of the node areas to the root area.final AABB
getFatAABB
(int proxyId) int
Compute the height of the binary tree in O(N) time.int
int
Get the maximum balance of an node in the tree.final java.lang.Object
getUserData
(int proxyId) private final void
insertLeaf
(int leaf_index) final boolean
Move a proxy with a swepted AABB.final 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
Build an optimal tree.private final void
removeLeaf
(DynamicTreeNode leaf) void
validate()
Validate this tree.private void
private void
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Field Details
-
MAX_STACK_SIZE
public static final int MAX_STACK_SIZE- See Also:
-
NULL_NODE
public static final int NULL_NODE- See Also:
-
m_root
-
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
-
nodeStack
-
r
-
aabb
-
subInput
-
combinedAABB
-
color
-
textVec
-
-
Constructor Details
-
DynamicTree
public DynamicTree()
-
-
Method Details
-
createProxy
Description copied from interface:BroadPhaseStrategy
Create a proxy. Provide a tight fitting AABB and a userData pointer.- Specified by:
createProxy
in interfaceBroadPhaseStrategy
- Parameters:
aabb
-userData
-- Returns:
-
destroyProxy
public final void destroyProxy(int proxyId) Description copied from interface:BroadPhaseStrategy
Destroy a proxy- Specified by:
destroyProxy
in interfaceBroadPhaseStrategy
- Parameters:
proxyId
-
-
moveProxy
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
- Specified by:
getFatAABB
in interfaceBroadPhaseStrategy
-
query
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
- Parameters:
callback
-
-
raycast
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
-
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
-
freeNode
returns a node to the pool -
getInsertionCount
public int getInsertionCount()- Specified by:
getInsertionCount
in interfaceBroadPhaseStrategy
-
insertLeaf
private final void insertLeaf(int leaf_index) -
removeLeaf
-
balance
-
validateStructure
-
validateMetrics
-
drawTree
- Specified by:
drawTree
in interfaceBroadPhaseStrategy
-
drawTree
-