Package com.ardor3d.bounding

Class CollisionTree

java.lang.Object
com.ardor3d.bounding.CollisionTree
All Implemented Interfaces:
Serializable
public class CollisionTree extends Object implements Serializable
CollisionTree defines a well balanced red black tree used for triangle accurate collision detection. The CollisionTree supports three types: Oriented Bounding Box, Axis-Aligned Bounding Box and Sphere. The tree is composed of a hierarchy of nodes, all but leaf nodes have two children, a left and a right, where the children contain half of the triangles of the parent. This "half split" is executed down the tree until the node is maintaining a set maximum of triangles. This node is called the leaf node. Intersection checks are handled as follows:
1. The bounds of the node is checked for intersection. If no intersection occurs here, no further processing is needed, the children (nodes or triangles) do not intersect.
2a. If an intersection occurs and we have children left/right nodes, pass the intersection information to the children.
2b. If an intersection occurs and we are a leaf node, pass each triangle individually for intersection checking.

Optionally, during creation of the collision tree, sorting can be applied. Sorting will attempt to optimize the order of the triangles in such a way as to best split for left and right sub-trees. This function can lead to faster intersection tests, but increases the creation time for the tree. The number of triangles a leaf node is responsible for is defined in CollisionTreeManager. It is actually recommended to allow CollisionTreeManager to maintain the collision trees for a scene.
See Also:

  • Field Details

    • _type

      protected CollisionTree.Type _type

    • _left

      protected CollisionTree _left

    • _right

      protected CollisionTree _right

    • _bounds

      protected BoundingVolume _bounds

    • _worldBounds

      protected BoundingVolume _worldBounds

    • _primitiveIndices

      protected int[] _primitiveIndices
      the list of primitives indices that compose the tree. This list contains all the triangles of the mesh and is shared between all nodes of this tree. Stored here to allow for sorting.

    • _start

      protected int _start

    • _end

      protected int _end

    • _mesh

      protected transient WeakReference<Mesh> _mesh

    • _section

      protected int _section

    • _comparator

      protected final transient TreeComparator _comparator

  • Constructor Details

    • CollisionTree

      public CollisionTree(CollisionTree.Type type)
      Constructor creates a new instance of CollisionTree.
      Parameters:
      type - the type of collision tree to make
      See Also:

  • Method Details

    • construct

      public void construct(int childIndex, int section, Node parent, boolean doSort)
      Recreate this Collision Tree for the given Node and child index.
      Parameters:
      childIndex - the index of the child to generate the tree for.
      section - the section
      parent - The Node that this tree should represent.
      doSort - true to sort primitives during creation, false otherwise

    • construct

      public void construct(Mesh mesh, boolean doSort)
      Recreate this Collision Tree for the given mesh.
      Parameters:
      mesh - The mesh that this tree should represent.
      doSort - true to sort primitives during creation, false otherwise

    • splitMesh

      protected void splitMesh(Mesh mesh, int sectionStart, int sectionEnd, boolean doSort)

    • createTree

      public void createTree(int section, int start, int end, boolean doSort)
      Creates a Collision Tree by recursively creating children nodes, splitting the primitives this node is responsible for in half until the desired primitive count is reached.
      Parameters:
      section - the section
      start - The start index of the primitivesArray, inclusive.
      end - The end index of the primitivesArray, exclusive.
      doSort - True if the primitives should be sorted at each level, false otherwise.

    • intersectsBounding

      public boolean intersectsBounding(BoundingVolume volume)
      Tests if the world bounds of the node at this level intersects a provided bounding volume. If an intersection occurs, true is returned, otherwise false is returned. If the provided volume is invalid, false is returned.
      Parameters:
      volume - the volume to intersect with.
      Returns:
      true if there is an intersect, false otherwise.

    • intersect

      public boolean intersect(CollisionTree collisionTree)
      Determines if this Collision Tree intersects the given CollisionTree. If a collision occurs, true is returned, otherwise false is returned. If the provided collisionTree is invalid, false is returned.
      Parameters:
      collisionTree - The Tree to test.
      Returns:
      True if they intersect, false otherwise.

    • intersect

      public boolean intersect(CollisionTree collisionTree, List<PrimitiveKey> aList, List<PrimitiveKey> bList)
      Determines if this Collision Tree intersects the given CollisionTree. If a collision occurs, true is returned, otherwise false is returned. If the provided collisionTree is invalid, false is returned. All collisions that occur are stored in lists as an integer index into the mesh's triangle buffer. where aList is the primitives for this mesh and bList is the primitives for the test tree.
      Parameters:
      collisionTree - The Tree to test.
      aList - a list to contain the colliding primitives of this mesh.
      bList - a list to contain the colliding primitives of the testing mesh.
      Returns:
      True if they intersect, false otherwise.

    • intersect

      public List<PrimitiveKey> intersect(Ray3 ray, List<PrimitiveKey> store)
      intersect checks for collisions between this collision tree and a provided Ray. Any collisions are stored in a provided list as primitive index values. The ray is assumed to have a normalized direction for accurate calculations.
      Parameters:
      ray - the ray to test for intersections.
      store - a list to fill with the index values of the primitive hit. if null, a new List is created.
      Returns:
      the list.

    • getBounds

      public BoundingVolume getBounds()
      Returns the bounding volume for this tree node in local space.
      Returns:
      the bounding volume for this tree node in local space.

    • getWorldBounds

      public BoundingVolume getWorldBounds()
      Returns the bounding volume for this tree node in world space.
      Returns:
      the bounding volume for this tree node in world space.

    • sortPrimitives

      public void sortPrimitives()
      sortPrimitives attempts to optimize the ordering of the subsection of the array of primitives this node is responsible for. The sorting is based on the most efficient method along an axis. Using the TreeComparator and quick sort, the subsection of the array is sorted.