Editing Collision detection (section)

== Broad phase ==
This phase aims at quickly finding objects or parts of objects for which it can be quickly determined that no further collision test is needed. A useful property of such approach is that it is [[Output-sensitive algorithm|output sensitive]]. In the context of collision detection this means that the time complexity of the collision detection is proportional to the number of objects that are close to each other. An early example of that is the I-COLLIDE<ref name=":0" /> where the number of required narrow phase collision tests was <math>O(n + m)</math> where <math>n</math> is the number of objects and <math>m</math> is the number of objects at close proximity. This is a significant improvement over the quadratic complexity of the naive approach.

=== Spatial partitioning ===
Several approaches can be grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s (for 3D), [[quadtree]]s (for 2D), [[binary space partitioning]] (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Dynamic scenes and deformable objects require updating the partitioning which can add overhead.

===Bounding volume hierarchy===
[[Bounding volume hierarchy|Bounding Volume Hierarchy]] (BVH) is a tree structure over a set of [[#Bounding volumes|bounding volumes]]. Collision is determined by doing a tree traversal starting from the root. If the bounding volume of the root doesn't intersect with the object of interest, the traversal can be stopped. If, however there is an intersection, the traversal proceeds and checks the branches for each there is an intersection. Branches for which there is no intersection with the bounding volume can be culled from further intersection test. Therefore, multiple objects can be determined to not intersect at once. BVH can be used with deformable objects such as cloth or soft-bodies but the volume hierarchy has to be adjusted as the shape deforms. For deformable objects we need to be concerned about self-collisions or self intersections. BVH can be used for that end as well.  Collision between two objects is computed by computing intersection between the bounding volumes of the root of the tree as there are collision we dive into the sub-trees that intersect. Exact collisions between the actual objects, or its parts (often triangles of a [[triangle mesh]]) need to be computed only between intersecting leaves.<ref>
{{cite journal |last1=Klosowski |first1=James T |last2=Held |first2=Martin |last3=Mitchell |first3=Joseph S.B. |last4=Sowizral |first4=Henry |last5=Zikan |first5=Karel |date=1998 |title=Efficient collision detection using bounding volume hierarchies of k-DOPs |journal=IEEE Transactions on Visualization and Computer Graphics |publisher=IEEE |volume=4 |issue=1 |pages=21–36 |doi=10.1109/2945.675649}}
</ref> The same approach works for pair wise collision and self-collisions.

=== Exploiting temporal coherence ===
During the broad-phase, when the objects in the world move or deform, the data-structures used to cull collisions have to be updated. In cases where the changes between two frames or time-steps are small and the objects can be approximated well with [[axis-aligned bounding box]]es, the [[sweep and prune]] algorithm<ref name=":0" /> can be a suitable approach.

Several key observation make the implementation efficient: Two bounding-boxes intersect [[If and only if|if, and only if]], there is overlap along all three axes; overlap can be determined, for each axis separately, by sorting the intervals for all the boxes; and lastly, between two frames updates are typically small (making sorting algorithms optimized for almost-sorted lists suitable for this application). The algorithm keeps track of currently intersecting boxes, and as objects move, re-sorting the intervals helps keep track of the status.<ref>{{Cite book |last=Ericson |first=Christer |url=https://realtimecollisiondetection.net/books/rtcd/ |title=Real-time collision detection |date= 22 December 2004|publisher=Elsevier |isbn=978-1-55860-732-3 |edition=Nachdr. |series=Morgan Kaufmann series in interactive 3D technology |location=Amsterdam Heidelberg |pages=329–338}}</ref>

=== Pairwise pruning ===
{{Multiple issues|{{Technical|section|date=March 2020}}
{{Tone|section|{{subst:March 2020}}|date=January 2024}}
{{Unreferenced section|date=July 2024}}|section=y}}

Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, <math>S={S_1,S_2,\dots,S_n}</math> and <math>T={T_1,T_2,\dots,T_n}</math> (for simplicity, we will assume that each set has the same number of triangles.)

The obvious thing to do is to check all triangles <math>S_j</math> against all triangles <math>T_k</math> for collisions, but this involves <math>n^2</math> comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check.

The most widely used family of algorithms is known as the ''hierarchical bounding volumes'' method. As a preprocessing step, for each object (in our example, <math>S</math> and <math>T</math>) we will calculate a [[bounding volume hierarchy|hierarchy of bounding volumes]]. Then, at each time step, when we need to check for collisions between <math>S</math> and <math>T</math>, the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases.{{Citation needed|date=June 2008}}

If <math>E</math> is a set of triangles, we can pre-calculate a bounding sphere <math>B(E)</math>. There are many ways of choosing <math>B(E)</math>, we only assume that <math>B(E)</math> is a sphere that completely contains <math>E</math> and is as small as possible.

Ahead of time, we can compute <math>B(S)</math> and <math>B(T)</math>. Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do <math>S</math> and <math>T</math>. This is not much better than an ''n''-body pruning algorithm, however.

If <math>E={E_1,E_2,\dots,E_m}</math> is a set of triangles, then we can split it into two halves <math>L(E):={E_1,E_2,\dots,E_{m/2}}</math> and <math>R(E):={E_{m/2+1},\dots,E_{m-1},E_m}</math>. We can do this to <math>S</math> and <math>T</math>, and we can calculate (ahead of time) the bounding spheres <math>B(L(S)),B(R(S))</math> and <math>B(L(T)),B(R(T))</math>. The hope here is that these bounding spheres are much smaller than <math>B(S)</math> and <math>B(T)</math>. And, if, for instance, <math>B(S)</math> and <math>B(L(T))</math> do not intersect, then there is no sense in checking any triangle in <math>S</math> against any triangle in <math>L(T)</math>.

As a [[precomputation]], we can take each physical body (represented by a set of triangles) and recursively decompose it into a [[binary tree]], where each node <math>N</math> represents a set of triangles, and its two children represent <math>L(N)</math> and <math>R(N)</math>. At each node in the tree, we can pre-compute the bounding sphere <math>B(N)</math>.

When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles.

Many variants of the algorithms are obtained by choosing something other than a sphere for <math>B(T)</math>. If one chooses [[axis-aligned bounding box]]es, one gets AABBTrees. [[Oriented bounding box]] trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as [[Spline (mathematics)|spline]]s instead of simple triangles.