Class 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.
    • 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:
      • 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.
      • 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

        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:
      • rebuildBottomUp

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

        private final void freeNode​(DynamicTreeNode node)
        returns a node to the pool
      • insertLeaf

        private final void insertLeaf​(int leaf_index)
      • validateStructure

        private void validateStructure​(DynamicTreeNode node)