Module org.dyn4j

Class LazyAABBTree<E extends Collidable<T>,​T extends Fixture>

  • Type Parameters:
    E - the Collidable type
    T - the Fixture type
    All Implemented Interfaces:
    BatchBroadphaseDetector<E,​T>, BroadphaseDetector<E,​T>, Shiftable

    public class LazyAABBTree<E extends Collidable<T>,​T extends Fixture>
    extends AbstractBroadphaseDetector<E,​T>
    implements BatchBroadphaseDetector<E,​T>
    Implementation of a self-balancing axis-aligned bounding box tree broad-phase collision detection algorithm.

    This class implements a aabb tree broad-phase detector that is based on ideas from DynamicAABBTree but with some very critical improvements. This data structure is lazy in the sense that it will build the actual tree as late as possible (hence the name). Performance is optimized for fast detection of collisions, as required by the World class. Raycasting and other functionalities should see no big improvements. Insertion is O(1), update is O(logn) but batch update (update of all bodies) is O(n), remove is O(logn) average but O(n) worse.

    The class will rebuild the whole tree at each detection and will detect the collisions at the same time in an efficient manner.

    This structure keeps the bodies sorted by the radius of their fixtures and rebuilds the tree each time in order to construct better trees.

    Manolis Tsamis
    • Field Detail

      • sorted

        boolean sorted
        Whether there's new data to sort
      • pendingRemoves

        boolean pendingRemoves
        Whether there are leafs waiting to be batch-removed
      • pendingInserts

        boolean pendingInserts
        Whether there are leafs waiting to be batch-inserted
    • Constructor Detail

      • LazyAABBTree

        public LazyAABBTree()
        Default constructor.
      • LazyAABBTree

        public LazyAABBTree​(int initialCapacity)
        Optional constructor.

        Allows fine tuning of the initial capacity of local storage for faster running times.

        initialCapacity - the initial capacity of local storage
        java.lang.IllegalArgumentException - if initialCapacity is less than zero
    • Method Detail

      • batchRebuild

        void batchRebuild()
        Destroys the existing tree in O(n) time and prepares for batch-detection, but does not update the AABBs of elements.
      • batchUpdate

        public void batchUpdate()
        Destroys the existing tree in O(n) time and prepares for batch-detection while also updating all AABBs. Called by World in each step before detection.
        Specified by:
        batchUpdate in interface BatchBroadphaseDetector<E extends Collidable<T>,​T extends Fixture>
      • remove

        public boolean remove​(E collidable,
                              T fixture)
        Description copied from interface: BroadphaseDetector
        Removes the given Fixture for the given Collidable from the broad-phase and returns true if it was found.
        Specified by:
        remove in interface BroadphaseDetector<E extends Collidable<T>,​T extends Fixture>
        collidable - the collidable
        fixture - the fixture to remove
        boolean true if the fixture was found and removed
      • remove

        void remove​(LazyAABBTreeLeaf<E,​T> leaf)
        Internal method to remove a leaf from the tree. Assumes the root is not null.
        leaf - the leaf to remove
      • doPendingRemoves

        void doPendingRemoves()
        Internal method to actually remove all leafs marked for removal. If there are any (see pendingRemoves) performs all deletions in O(n) time, else no work is done. This mechanism is used to solve the O(n) time for removing an element from the elements ArrayList. Although worst case is the same, in various scenarios this will perform better. Assumes all leafs marked for removal are not on the tree.
      • ensureSorted

        void ensureSorted()
        Internal method that sorts the elements if needed. Note that the sorting routines in array list are optimized for partially sorted data and we can expect the sorting to happen very fast if just a few changes did happen from the last sorting.
      • ensureOnTree

        void ensureOnTree()
        Internal method to ensure that all nodes are on the tree.
      • build

        void build()
        Internal method that ensures the whole tree is built. This just creates the tree and performs no detection. This is used to support raycasting and single AABB queries.
      • buildAndDetect

        void buildAndDetect​(BroadphaseFilter<E,​T> filter,
                            java.util.List<BroadphasePair<E,​T>> pairs)
        The heart of the LazyAABBTree batch detection. Assumes no tree exists and in performs all the broad-phase detection while building the tree from scratch.
        filter - the broadphase filter
        pairs - List a list containing the results
      • descendCost

        double descendCost​(LazyAABBTreeNode node,
                           AABB itemAABB)
        Cost function for descending to a particular node. The cost equals the enlargement caused in the AABB of the node. More specifically, descendCost(node, aabb) = (perimeter(union(node.aabb, aabb)) - perimeter(node.aabb)) / 2
        node - the node to descend
        itemAABB - the AABB of the item being inserted
        the cost of descending to node
      • insert

        void insert​(LazyAABBTreeLeaf<E,​T> item)
        Internal method to insert a leaf in the tree
        item - the leaf to insert
      • insertAndDetect

        void insertAndDetect​(LazyAABBTreeLeaf<E,​T> item,
                             BroadphaseFilter<E,​T> filter,
                             java.util.List<BroadphasePair<E,​T>> pairs)
        Internal method to insert a leaf in the tree and also perform all the collision detection required for that tree
        item - the leaf to insert
        filter - the broadphase filter
        pairs - a list containing the results
      • insert

        void insert​(LazyAABBTreeLeaf<E,​T> item,
                    boolean detect,
                    BroadphaseFilter<E,​T> filter,
                    java.util.List<BroadphasePair<E,​T>> pairs)
        The implementation routine for the tree. In order to avoid code duplication this method performs either insertion with detection or just insertion, as requested by the 'detect' parameter. The actual insertion algorithm is the same with that in DynamicAABBTree but with a variety of optimizations and clean-ups.
        item - The leaf to insert
        detect - Whether to also perform collision detection
        filter - the broadphase filter
        pairs - List a list containing the results
      • shift

        public void shift​(Vector2 shift)
        Description copied from interface: Shiftable
        Translates the object to match the given coordinate shift.
        Specified by:
        shift in interface Shiftable
        shift - the amount to shift along the x and y axes
      • balanceAll

        void balanceAll​(LazyAABBTreeNode node)
        Balances the tree starting from node and going up to the root
        node - The starting node
      • balance

        void balance​(LazyAABBTreeNode a)
        Balances the subtree using node as the root. Note that this is the exact same balancing routine as in DynamicAABBTree but greatly reduced in size and optimized
        a - the root node of the subtree to balance