Content deleted Content added
Update for clarity |
|||
| (11 intermediate revisions by 10 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|{{Technical|section|date=March 2020}} {{Tone|section|
'''Collision detection''' is the [[computational problem]] of detecting an [[Intersection (geometry)|intersection]] of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detection is a classic problem of [[computational geometry]] with applications in [[computer graphics]], [[physical simulation]], [[
== 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.
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>
Line 16:
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>
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.
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.
Line 26:
=== Spatial partitioning ===
Several approaches can be grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s (for 3D), [[
===Bounding volume hierarchy===
[[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}}
</ref> The same approach works for pair wise collision and self-collisions.
=== 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.
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
=== Pairwise pruning ===
{{Multiple issues|{{Technical|section|date=March 2020}}
{{Tone|section
{{Unreferenced section|date=July 2024}}|section=y}}
Line 59 ⟶ 60:
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 ==
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
[[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.
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 ===
{{
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 ====
Line 104 ⟶ 103:
=== Collision detection in computer simulation ===
{{unreferenced
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]].
Line 138 ⟶ 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]]
==== 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 151 ⟶ 150:
==See also==
{{div col}}
* [[Chazelle polyhedron]]
* [[Collision response]]
* [[Hit-testing]]
Line 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]
| |||