Editing Collision detection (section)

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

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

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.

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.