Content deleted Content added
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 |
m v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation - Punctuation in link) |
||
Line 5:
{{tone|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|video games
== 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>
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 journal |last=Andrews |first=Sheldon |last2=Erleben |first2=Kenny |last3=Ferguson |first3=Zachary |date=2022-08-02 |title=Contact and friction simulation for computer graphics |url=https://dl.acm.org/doi/10.1145/3532720.3535640 |journal=SIGGRAPH ’22 Courses |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 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" />
Line 18:
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.
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 |last=Akenine-Möller |first=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>
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.
| |||