Content deleted Content added
→Overview: Updated overview. Removed discussion related to billiard and collision response and ill condition systems as these are not relevant for the page. Added discussion, supported with source to set the ground for better organized overview centered on broad phase, narrow phase collisions and related applications |
Reorganized page: Split Optimization into broad phase and narrow phase and moved these to the top - as they discuss the actual content. moved simulation to usage section. Still a lot of work is needed |
||
Line 14:
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 journal |last=Hadap |first=Sunil |last2=Eberle |first2=Dave |last3=Volino |first3=Pascal |last4=Lin |first4=Ming C. |last5=Redon |first5=Stephane |last6=Ericson |first6=Christer |date=2004-08-08 |title=Collision detection and proximity queries |url=https://dl.acm.org/doi/10.1145/1103900.1103915 |journal=SIGGRAPH ’04 Courses |language=en |publisher=ACM |pages=15 |doi=10.1145/1103900.1103915 |isbn=978-1-4503-7801-7}}</ref><ref name=":col0" />
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 journal |last=Cohen |first=Jonathan D. |last2=Lin |first2=Ming C. |last3=Manocha |first3=Dinesh |last4=Ponamgi |first4=Madhav |date=1995 |title=I-COLLIDE: an interactive and exact collision detection system for large-scale environments |url=http://portal.acm.org/citation.cfm?doid=199404.199437 |journal=I3D '95: Proceedings of the 1995 symposium on Interactive 3D graphics |language=en |publisher=ACM Press |pages=189–ff. |doi=10.1145/199404.199437 |isbn=978-0-89791-736-0}}</ref>
Due to the complexity mentioned above, collision detection is 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.
Line 22:
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.
== Broad Phase ==
This phase aims at quickly finding objects or parts of objects for which we can quickly determine that no further collision test is needed. A useful property of such algorithm 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 exact collision test 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.
=== Exploiting temporal coherence ===
Line 90 ⟶ 66:
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.
=== 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 |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> 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 |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.
=== 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 |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.
== Narrow Phase ==
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.
=== Exact pairwise collision detection ===
{{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.
Line 101 ⟶ 96:
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.
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 |year=1993 |title=Efficient Collision Detection for Animation and Robotics (thesis)
</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.
Line 114 ⟶ 109:
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 ===
Line 177 ⟶ 120:
== 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 ===
| |||