Collision detection: Difference between revisions

Revision as of 06:09, 3 March 2025

Latest revision as of 11:07, 23 July 2025

(6 intermediate revisions by 6 users not shown)

Line 3:

{{redirect|Hitbox}}

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

{{Tone|section|{{subst:March 2020}}|date=August 2014}}}}

'''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]], [[video game]]s, [[robotics]] (including [[autonomous driving]]) and [[computational physics]]. 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>

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), [[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===

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

Line 40:

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

==See also==

{{div col}}

* [[Chazelle polyhedron]]

* [[Collision response]]

* [[Hit-testing]]

Line 165 ⟶ 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]