Editing Collision detection (section)

=== 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.