Editing Collision detection (section)

=== A priori pruning ===
Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.

Pruning is also desirable here, both ''n''-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration.

When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical [[root-finding algorithm]] to compute the instant of impact.

As an example, consider two triangles moving in time <math>{v_1(t),v_2(t),v_3(t)}</math> and <math>{v_4(t),v_5(t),v_6(t)}</math>. At any point in time, the two triangles can be checked for intersection using the twenty planes previously mentioned. However, we can do better, since these twenty planes can all be tracked in time. If <math>P(u,v,w)</math> is the plane going through points <math>u,v,w</math> in <math>\mathbb R^3</math> then there are twenty planes <math>P(v_i(t),v_j(t),v_k(t))</math> to track. Each plane needs to be tracked against three vertices, this gives sixty values to track. Using a root finder on these sixty functions produces the exact collision times for the two given triangles and the two given trajectory. We note here that if the trajectories of the vertices are assumed to be linear polynomials in <math>t</math> then the final sixty functions are in fact cubic polynomials, and in this exceptional case, it is possible to locate the exact collision time using the formula for the roots of the cubic. Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials.{{Citation needed|date=June 2008}}