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.

  • 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

      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 Details

    • DynamicTree

      public DynamicTree()

  • Method Details

    • 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
      Parameters:
      aabb -
      userData -
      Returns:

    • destroyProxy

      public final void destroyProxy(int proxyId)
      Description copied from interface: BroadPhaseStrategy
      Destroy a proxy
      Specified by:
      destroyProxy in interface BroadPhaseStrategy
      Parameters:
      proxyId -

    • 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
      Parameters:
      callback -

    • 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)