Collision detection: Difference between revisions

Revision as of 03:12, 7 November 2024

Latest revision as of 11:07, 23 July 2025

(28 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Term in computer science}}

{{About|collision detection in computational geometry|collision detection in computer networks|Carrier-sense multiple access with collision detection}}

{{redirect|Hitbox}}{{Multiple issues|

{{UnreferencedMultiple issues|{{Technical|section|date=JulyMarch 20242020}}

{{TechnicalTone|section|date=MarchAugust 20202014}}}}

{{Tone|section|{{subst:March 2020}}|date=January 2024}}

{{tone|date=August 2014}}

}}

'''Collision detection''' is the [[computational problem]] of detecting an [[intersectionIntersection (geometry)|intersection]] of two or more [[Space|spatial]]objects objectsin virtual space. More precisely, commonlyit computerdeals graphicswith the questions of ''if'', ''when'' and ''where'' two or more objects intersect. ItCollision hasdetection applicationsis ina variousclassic computingproblem fields,of primarily[[computational geometry]] with applications in [[computer graphics]], [[computerphysical gamesimulation]]s, [[computervideo simulationgame]]s, [[robotics]] (including [[autonomous driving]]) and [[computational physics]]. Collision detection is a classic problem of [[computational geometry]]. Collision detection [[algorithm]]s can be divided into operating on 2D or 3D spatial objects.<ref>{{cite journal|url=https://hal.inria.fr/inria-00394479/document|title=Collision Detection for Deformable Objects|year=2005|doi=10.1111/j.1467-8659.2005.00829.x|last1=Teschner|first1=M.|last2=Kimmerle|first2=S.|last3=Heidelberger|first3=B.|last4=Zachmann|first4=G.|last5=Raghupathi|first5=L.|last6=Fuhrmann|first6=A.|last7=Cani|first7=M.-P.|last8=Faure|first8=F.|last9=Magnenat-Thalmann|first9=N.|last10=Strasser|first10=W.|last11=Volino|first11=P.|journal=Computer Graphics Forum|volume=24|pages=61–81|s2cid=1359430|citeseerx=10.1.1.58.2505}}</ref>

== Overview ==

[[Image:Billiards balls.jpg|right|200px|thumb|Billiards balls hitting each other in a virtual space are a classic example where collision detection computations are needed.]]Collision detection is closely linked to calculating the [[Euclidean distance|distance]] between objects, as two objects (or more) intersect when the distance between them reaches zero or even becomes negative.<ref>{{Cite book |url=https://www.csun.edu/~ctoth/Handbook/HDCG3.html |title=Handbook of discrete and computational geometry |date=2018 |publisher=CRC Press, Taylor & Francis Group, a Chapman & Hall book |isbn=978-1-4987-1139-5 |editor-last=Goodman |editor-first=Jacob E. |edition=3rd |series=Discrete mathematics and its applications |___location=Boca Raton London New York |chapter=39 |editor-last2=O'Rourke |editor-first2=Joseph |editor-last3=Tóth |editor-first3=Csaba D.}}</ref> Negative distance indicates that one object has penetrated another. Performing collision detection requires more context than just the distance between the objects.

[[Image:Billiards balls.jpg|right|200px|thumb|Billiards balls hitting each other are a classic example applicable within the science of collision detection.]]

In physical simulation, experiments such as playing [[billiards]] are conducted.<ref>{{Cite web |title=myPhysicsLab Billiards |url=https://www.myphysicslab.com/engine2D/billiards-en.html |access-date=2024-07-08 |website=www.myphysicslab.com}}</ref> The [[physics]] of bouncing billiard balls are understood under the umbrella of [[rigid body motion]] and [[elastic collision]]s.<ref>Pool Table Simulation (calpoly.edu)

Accurately identifying the points of contact on both objects' surfaces is also essential for the computation of a physically accurate [[collision response]]. The complexity of this task increases with the level of detail in the objects' representations: the more intricate the model, the greater the computational cost.<ref name=":col0">{{Cite book |last1=Andrews |first1=Sheldon |last2=Erleben |first2=Kenny |last3=Ferguson |first3=Zachary |chapter=Contact and friction simulation for computer graphics |date=2022-08-02 |title=ACM SIGGRAPH 2022 Courses |chapter-url=https://dl.acm.org/doi/10.1145/3532720.3535640 |language=en |publisher=ACM |pages=1–172 |doi=10.1145/3532720.3535640 |isbn=978-1-4503-9362-1}}</ref>

<nowiki>https://users.csc.calpoly.edu/~zwood/teaching/csc471/finalW19/jpietrok/index.html</nowiki></ref> An initial description of the situation would be given, with a very precise physical description of the billiard table and balls, as well as initial positions of all the balls.<ref><nowiki>https://www.cs.rpi.edu/~cutler/classes/advancedgraphics/S09/final_projects/anderson.pdf</nowiki></ref> Based on a force applied to the cue ball, the [[computer program]] would calculate the trajectories, precise motion and eventual resting places of all the balls. A program to simulate this game would consist of several portions, one of which would be responsible for calculating the precise impacts between the billiard balls. This particular example also turns out to be [[condition number|ill conditioned]]: as a small error in any calculation will cause drastic changes in the final position of the billiard balls.

Collision detection frequently involves dynamic objects, adding a temporal dimension to distance calculations. Instead of simply measuring distance between static objects, collision detection algorithms often aim to determine whether the objects’ motion will bring them to a point in time when their distance is zero—an operation that adds significant computational overhead.<ref name=":col1">{{Cite book |last1=Hadap |first1=Sunil |last2=Eberle |first2=Dave |last3=Volino |first3=Pascal |last4=Lin |first4=Ming C. |last5=Redon |first5=Stephane |last6=Ericson |first6=Christer |chapter=Collision detection and proximity queries |date=2004-08-08 |title=ACM SIGGRAPH 2004 Course Notes |chapter-url=https://dl.acm.org/doi/10.1145/1103900.1103915 |language=en |publisher=ACM |pages=15 |doi=10.1145/1103900.1103915 |isbn=978-1-4503-7801-7}}</ref><ref name=":col0" />

Video games have similar requirements, with some crucial differences. While some computer simulations need to simulate real-world physics as precisely as possible, computer games need to simulate real-world physics in an ''acceptable'' way, in [[Real-time computing|real time]] and robustly. Compromises are allowed, so long as the resulting simulation is satisfying to the game players.

In collision detection involving multiple objects, a naive approach would require detecting collisions for all pairwise combinations of objects. As the number of objects increases, the number of required comparisons grows rapidly: for <math>n</math> objects, <math display="">{n(n-1)}/{2}</math> intersection tests are needed with a naive approach. This quadratic growth makes such an approach computationally expensive as <math>n</math> increases.<ref name=":col1" /><ref name=":0">{{Cite book |last1=Cohen |first1=Jonathan D. |last2=Lin |first2=Ming C. |last3=Manocha |first3=Dinesh |last4=Ponamgi |first4=Madhav |chapter=I-COLLIDE: An interactive and exact collision detection system for large-scale environments |date=1995 |title=Proceedings of the 1995 symposium on Interactive 3D graphics - SI3D '95 |chapter-url=http://portal.acm.org/citation.cfm?doid=199404.199437 |language=en |publisher=ACM Press |pages=189–ff |doi=10.1145/199404.199437 |isbn=978-0-89791-736-0}}</ref>

== Collision detection in computer simulation ==

{{unreferenced-section|date=January 2024}}

Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. This is very CPU intensive for low softness materials. Some simulators estimate the time of collision by [[linear interpolation]], [[Rollback (data management)|roll back]] the simulation, and calculate the collision by the more abstract methods of [[conservation laws]].

Due to the complexity mentioned above, collision detection is a computationally intensive process. Nevertheless, it is essential for interactive applications like video games, robotics, and real-time physics engines. To manage these computational demands, extensive efforts have gone into optimizing collision detection algorithms.

Some iterate the linear interpolation ([[Newton's method]]) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in [[air traffic control]].

A commonly used approach towards accelerating the required computations is to divide the process into two phases: the '''broad phase''' and the '''narrow phase'''.<ref name=":col1" /><ref>{{Cite book |last1=Akenine-Möller |first1=Tomas |url=https://www.realtimerendering.com |title=Real-time rendering |last2=Haines |first2=Eric |last3=Hoffman |first3=Naty |last4=Pesce |first4=Angelo |last5=Iwanicki |first5=Michał |last6=Hillaire |first6=Sébastien |date=2018 |publisher=CRC Press, Taylor & Francis Group |isbn=978-1-138-62700-0 |edition=4th |series=An A K Peters book |___location=Boca Raton London New York}}</ref> The broad phase aims to answer the question of whether objects might collide, using a conservative but efficient approach to rule out pairs that clearly do not intersect, thus avoiding unnecessary calculations.

After an inelastic collision, special states of sliding and resting can occur and, for example, the [[Open Dynamics Engine]] uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a [[scene graph]] avoids drift.

Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. Here, 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.

In other words, physical simulators usually function one of two ways: where the collision is detected ''[[Empirical evidence|a posteriori]]'' (after the collision occurs) or ''[[A priori and a posteriori|a priori]]'' (before the collision occurs). In addition to the ''a posteriori'' and ''a priori'' distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than ''a posteriori'' and ''a priori''.

== Broad phase ==

=== ''A posteriori'' (discrete) versus ''a priori'' (continuous) ===

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.

{{Unreferenced section|date=August 2022}}

In the ''a posteriori'' case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called ''a posteriori'' because it typically misses the actual instant of collision, and only catches the collision after it has actually happened.

=== Spatial partitioning ===

In the ''a priori'' methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called ''a priori'' because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies.

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

The main benefits of the ''a posteriori'' methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the ''a posteriori'' algorithms are in effect one dimension simpler than the ''a priori'' algorithms. An ''a priori'' algorithm must deal with the time variable, which is absent from the ''a posteriori'' problem.

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

On the other hand, ''a posteriori'' algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small.

</ref> The same approach works for pair wise collision and self-collisions.

The benefits of the ''a priori'' algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical [[Root-finding algorithm|root finder]] is usually involved.

Some objects are in ''resting contact'', that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (''a posteriori'') or slide (''a priori'') and their relative motion is below a threshold, friction becomes [[stiction]] and both objects are arranged in the same branch of the [[scene graph]].

== Optimization ==

The obvious approaches to collision detection for multiple objects are very slow. [[Triangular number|Checking every object against every other object]] will, of course, work, but is too inefficient to be used when the number of objects is at all large. Checking objects with complex geometry against each other in the obvious way, by checking each face against each other face, is itself quite slow. Thus, considerable research has been applied to speed up the problem.

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

{{Multiple issues|{{Technical|section|date=March 2020}}

{{Tone|section|{{subst:March 2020}}|date=January 2024}}

{{Unreferenced section|date=July 2024}}|section=y}}

In many applications, the configuration of physical bodies from one time step to the next changes very little. Many of the objects may not move at all. Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster completion of the calculation.

At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect. Those pairs will require further analysis. An early high performance algorithm for this was developed by [[Ming C. Lin]] at the [[University of California, Berkeley]] [http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html], who suggested using [[axis-aligned bounding box]]es for all ''n'' bodies in the scene.

Each box is represented by the product of three intervals (i.e., a box would be <math>I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]</math>). A common algorithm for collision detection of bounding boxes is [[sweep and prune]]. Observe that two such boxes, <math>I_1 \times I_2 \times I_3</math> and <math>J_1 \times J_2 \times J_3</math> intersect [[If and only if|if, and only if]], <math>I_1</math> intersects <math>J_1</math>, <math>I_2</math> intersects <math>J_2</math> and <math>I_3</math> intersects <math>J_3</math>. It is supposed that, from one time step to the next, if <math>I_k</math> and <math>J_k</math> intersect, then it is very likely that at the next time step they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to.

So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length <math>n</math>, the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an <math>n \times n</math> [[matrix (math)|matrix]] <math>M=(m_{ij})</math> of zeroes and ones: <math>m_{ij}</math> is 1 if intervals <math>i</math> and <math>j</math> intersect, and 0 if they do not intersect.

By our assumption, the matrix <math>M</math> associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we [[sorting algorithm|sort]] the list by coordinates, and update the matrix <math>M</math> as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next.

In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an ''n''-body pruning algorithm is the best that can be done.

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>

If an upper bound can be placed on the velocity of the physical bodies in a scene, then pairs of objects can be pruned based on their initial distance and the size of the time step.

=== Pairwise pruning ===

{{Multiple issues|{{Technical|section|date=March 2020}}

{{Tone|section|{{subst:March 2020}}|date=January 2024}}

{{Unreferenced section|date=July 2024}}|section=y}}

Line 87 ⟶ 61:

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.

== Narrow phase ==

=== Exact pairwise collision detection ===

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.

{{manual|section|date=January 2024}}

Once we're done pruning, we are left with a number of candidate pairs to check for exact collision detection.

===Bounding volumes===

A basic observation is that for any two [[convex set|convex]] objects which are disjoint, one can find a plane in space 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 allows the development of very fast collision detection algorithms for convex objects.

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.

Early work in this area involved "[[Separating axis theorem|separating plane]]" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are <math>{v_1,v_2,v_3}</math> and <math>{v_4,v_5,v_6}</math> where each <math>v_j</math> is a vector in <math>\mathbb R^3</math>, then we can take three vertices, <math>v_i,v_j,v_k</math>, find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.

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.

If the triangles are coplanar, this test is not entirely successful. One can add some extra planes, for instance, planes that are [[normal (geometry)|normal]] to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.

==== Collision detection between convex objects ====

Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by [[Ming C. Lin]]<ref>{{cite web |author=Lin, Ming C|title=Efficient Collision Detection for Animation and Robotics (thesis)|year=1993|publisher=University of California, Berkeley|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}}

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> used a variation on the [[simplex algorithm]] from [[linear programming]]. The [[Gilbert-Johnson-Keerthi distance algorithm]] has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.

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

Line 110 ⟶ 90:

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

=== Spatial partitioning ===

Alternative algorithms are grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s, [[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. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above.

===Bounding volumes===

In order to accelerate collision detection calculation, [[Bounding volume]]s may be used. A bounding volume is a shape that encloses the object of interest but is simpler to compute collisions for.

[[Minimum bounding box#Axis-aligned minimum bounding box|Axis-Align Bounding Boxes (AABB)]] and [[cuboid]]s are popular due to their simplicity. <ref>{{cite web |

url=http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |

title=Unlocking the Mysteries of the Bounding Box |

date=2005-08-29 |

author=Caldwell, Douglas R. |

publisher=US Army Engineer Research & Development Center, Topographic Engineering Center, Research Division, Information Generation and Management Branch |

access-date=2014-05-13 |

archive-url=https://web.archive.org/web/20120728180104/http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm |

archive-date=2012-07-28 |

url-status=dead }}</ref> A bounding box in a video game is sometimes called a [[#Hitbox|Hitbox]]. Other bounding volumes commonly used for collision detection include [[Convex hull]] and [[Minimum bounding box#Arbitrarily oriented minimum bounding box| Oriented Bounding Boxes (OBB)]].

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

| title= An improved optimal algorithm for collision detection of hybrid hierarchical bounding box

| date= 2022

| journal = Evolutionary Intelligence

| volume= 15

| issue= 4

| pages= 2515–2527

| doi= 10.1007/s12065-020-00559-6

| url= https://www.researchgate.net/publication/348937861 }}</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.

=== Bounding Volume Hierarchy ===

When the space of the objects we are computing collision for is complex, a single bounding volume may not provide tight enough approximation to considerably reduce the number of exact collision detections we have to perform. In such cases [[Bounding volume hierarchy| Bounding Volume Hierarchy]] (BVH) may be used. A BVH is a tree structure over a set of bounding volumes. 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

| title = Efficient collision detection using bounding volume hierarchies of k-DOPs

| journal = IEEE Transactions on Visualization and Computer Graphics

| volume = 4

| issue = 1

| pages = 21–36

| publisher = IEEE

| date = 1998

| doi = 10.1109/2945.675649

}}

</ref> The same approach works for pair wise collision and self-collisions.

=== Triangle centroid segments ===

Line 173 ⟶ 101:

== Usage ==

=== Collision detection in computer simulation ===

{{unreferenced section|date=January 2024}}

Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. This is very CPU intensive for low softness materials. Some simulators estimate the time of collision by [[linear interpolation]], [[Rollback (data management)|roll back]] the simulation, and calculate the collision by the more abstract methods of [[conservation laws]].

Some iterate the linear interpolation ([[Newton's method]]) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in [[air traffic control]].

After an inelastic collision, special states of sliding and resting can occur and, for example, the [[Open Dynamics Engine]] uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a [[scene graph]] avoids drift.

In other words, physical simulators usually function one of two ways: where the collision is detected ''[[Empirical evidence|a posteriori]]'' (after the collision occurs) or ''[[A priori and a posteriori|a priori]]'' (before the collision occurs). In addition to the ''a posteriori'' and ''a priori'' distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than ''a posteriori'' and ''a priori''.

==== ''A posteriori'' (discrete) versus ''a priori'' (continuous) ====

{{Unreferenced section|date=August 2022}}

In the ''a posteriori'' case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called ''a posteriori'' because it typically misses the actual instant of collision, and only catches the collision after it has actually happened.

In the ''a priori'' methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called ''a priori'' because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies.

The main benefits of the ''a posteriori'' methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the ''a posteriori'' algorithms are in effect one dimension simpler than the ''a priori'' algorithms. An ''a priori'' algorithm must deal with the time variable, which is absent from the ''a posteriori'' problem.

On the other hand, ''a posteriori'' algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small.

The benefits of the ''a priori'' algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical [[Root-finding algorithm|root finder]] is usually involved.

Some objects are in ''resting contact'', that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (''a posteriori'') or slide (''a priori'') and their relative motion is below a threshold, friction becomes [[stiction]] and both objects are arranged in the same branch of the [[scene graph]].

=== Video games ===

Line 185 ⟶ 137:

In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, [[binary space partitioning]] trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.

A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed [[Racing game|racecar video game]], from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track from one simulation step to the next. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in [[software bug|bug]]s that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly [[bottomless pit (video gaming)|bottomless pit]], sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. ''[[Big Rigs: Over the Road Racing]]'' is an infamous example of a game with a failing or possibly missing collision detection system.

==== Hitbox ====<!-- Deleted image removed: [[File:GearheadsCollisionBoxSize.png|thumb|A [[Debug menu|debug]] dialogue box in ''[[Gearheads (video game)|Gearheads]]'' controlling an object's hitbox {{Deletable file-caption|Tuesday, 9 July 2024|F7}}]] -->

Line 198 ⟶ 150:

==See also==

{{div col}}

* [[Chazelle polyhedron]]

* [[Collision response]]

* [[Hit-testing]]

Line 213 ⟶ 166:

==External links==

* [https://css-tricks.com/worlds-collide-keyframe-collision-detection-using-style-queries/ Collision detection in CSS animations]

* [http://gamma.cs.unc.edu/research/collision/ University of North Carolina at Chapel Hill collision detection research website]

* [http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances/ Prof. Steven Cameron (Oxford University) web site on collision detection]

* [http://demonstrations.wolfram.com/HowToAvoidACollision/ How to Avoid a Collision] by George Beck, [[Wolfram Demonstrations Project]].

* {{usurped|1=[https://web.archive.org/web/20130108211242/http://geomalgorithms.com/a08-_containers.html Bounding boxes and their usage]}}

* [http://programmerart.weebly.com/separating-axis-theorem.html Separating Axis Theorem]

* [https://docs.unity3d.com/ScriptReference/Collision.html Unity 3D Collision]

Line 227 ⟶ 182:

[[Category:Computer graphics]]

[[Category:Video game development]]

[[Category:Robotics]]

[[Category:Computer physics engines]]

[[Category:Robotics engineering]]