Package 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 Murphy

  • Field Details

  • Constructor Details

    • DynamicTree

      public DynamicTree()

  • Method Details

    • 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
      Parameters:
      aabb - The axis-aligned bounding box.

    • 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 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
      aabb - The axis-aligned bounding box.
      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
      aabb - The axis-aligned bounding box.

    • 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 an exact ray-cast in the case were the proxy contains a shape. The callback also performs 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

    • getMaxBalance

      public int getMaxBalance()
      Description copied from interface: BroadPhaseStrategy
      Get the maximum balance of a node in the tree. The balance is the difference in height of the two children of a node.
      Specified by:
      getMaxBalance in interface BroadPhaseStrategy

    • 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

    • rebuildBottomUp

      public void rebuildBottomUp()
      Build an optimal tree. Very expensive. For testing.

    • drawTree

      public void drawTree(DebugDraw argDraw)
      Specified by:
      drawTree in interface BroadPhaseStrategy

    • drawTree

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