Editing Collision detection (section)

== Narrow phase ==
Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. In this phase, the objects under consideration are relatively close to each other. Still, attempts to quickly determine if a full intersection is needed are employed first. This step is sometimes referred to as mid-phase.<ref name=":col1" /> Once these tests passed (e.g. the pair of objects may be colliding) more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and location of the intersection.

===Bounding volumes===
A quick way to potentially avoid a needless expensive computation is to check if the bounding volume enclosing the two objects intersect. If they don't, there is no need to check the actual objects. However, if the [[bounding volume|bounding volumes]] do intersect, the more expensive computation has to be performed. In order for the bounding-volume test to add value, two properties need to be balanced: a) the cost of intersecting the bounding volume needs to be low and b) the bounding volume needs to be tight enough so that the number of 'false positive' intersection will be low. A false positive intersection in this case means that the bounding volumes intersect but the actual objects do not. Different bounding volume types offer different trade-offs for these properties.

[[Minimum bounding box#Axis-aligned minimum bounding box|Axis-Align Bounding Boxes (AABB)]] and [[cuboid]]s are popular due to their simplicity and quick intersection tests.<ref>{{cite web |author=Caldwell, Douglas R. |date=2005-08-29 |title=Unlocking the Mysteries of the Bounding Box |url=http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |url-status=dead |archive-url=https://web.archive.org/web/20120728180104/http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |archive-date=2012-07-28 |access-date=2014-05-13 |publisher=US Army Engineer Research & Development Center, Topographic Engineering Center, Research Division, Information Generation and Management Branch}}</ref>  Bounding volumes such as [[Minimum bounding box#Arbitrarily oriented minimum bounding box|Oriented Bounding Boxes (OBB)]], [[Bounding volume#Common types|K-DOPs]] and Convex-hulls offer a tighter approximation of the enclosed shape at the expense of a more elaborate intersection test.

Bounding volumes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding volumes need be compared in detail.<ref>{{cite journal |author=Gan B, Dong Q |date=2022 |title=An improved optimal algorithm for collision detection of hybrid hierarchical bounding box |url=https://www.researchgate.net/publication/348937861 |journal=Evolutionary Intelligence |volume=15 |issue=4 |pages=2515–2527 |doi=10.1007/s12065-020-00559-6}}</ref> Computing collision or overlap between bounding volumes involves additional computations, therefore, in order for it to beneficial we need the bounding volume to be relatively tight and the computation overhead to due the collisions to be low.

=== Exact pairwise collision detection ===
{{how-to|section|date=January 2024}}

Objects for which pruning approaches could not rule out the possibility of a collision have to undergo an exact collision detection  computation.

==== Collision detection between convex objects ====
According to the [[Hyperplane separation theorem|separating planes theorem]], for any two disjoint [[convex set|convex]] objects, there exists a plane so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This property allows the development of efficient collision detection algorithms between convex objects. Several algorithms are available for finding the closest points on the surface of two convex polyhedral objects - and determining collision. Early work by [[Ming C. Lin]]<ref name=":1">{{cite web |author=Lin, Ming C |year=1993 |title=Efficient Collision Detection for Animation and Robotics (thesis) |url=https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf |archive-url=https://web.archive.org/web/20140728124049/https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf |archive-date=2014-07-28 |publisher=University of California, Berkeley}}
</ref> that used a variation on the [[simplex algorithm]] from [[linear programming]] and the [[Gilbert-Johnson-Keerthi distance algorithm]]<ref>{{Cite journal |last1=Gilbert |first1=E.G. |last2=Johnson |first2=D.W. |last3=Keerthi |first3=S.S. |date=1988 |title=A fast procedure for computing the distance between complex objects in three-dimensional space |url=https://graphics.stanford.edu/courses/cs448b-00-winter/papers/gilbert.pdf |journal=IEEE Journal on Robotics and Automation |volume=4 |issue=2 |pages=193–203 |doi=10.1109/56.2083}}</ref> are two such examples. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, and every step is initialized from the previous collision check.<ref name=":1" />

The result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

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

=== Triangle centroid segments ===
A [[triangle mesh]] object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh.  A triangle centroid is a center of mass location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters.  Given centroid points in both object and target it is possible to define the line segment connecting these two points.

The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian  coordinates <math>(x_1,y_1,z_1)</math>, <math>(x_2,y_2,z_2)</math> and <math>(x_3,y_3,z_3)</math> then the centroid is <math>\left(\frac{(x_1+x_2+x_3)}{3},\frac{(y_1+y_2+y_3)}{3},\frac{(z_1+z_2+z_3)}{3}\right)</math>.

Here is the function for a line segment distance between two 3D points. <math>\mathrm{distance} = \sqrt{(z_2 - z_1)^2 + (x_2 - x_1)^2 + (y_2 - y_1)^2}</math>

Here the length/distance of the segment is an adjustable "hit" criteria size of segment. As the objects approach the length decreases to the threshold value. A triangle sphere becomes the effective geometry test. A sphere centered at the centroid can be sized to encompass all the triangle's vertices.