Collision detection: Difference between revisions

Revision as of 05:49, 7 November 2024

Revision as of 06:59, 8 November 2024

Line 8:

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

[[Image:Billiards balls.jpg|right|200px|thumb|Billiards balls hitting each other are a classic example applicable within the science of collision detection.]]

In physical simulation, experiments such as playing [[billiards]] are conducted.<ref>{{Cite web |title=myPhysicsLab Billiards |url=https://www.myphysicslab.com/engine2D/billiards-en.html |access-date=2024-07-08 |website=www.myphysicslab.com}}</ref> The [[physics]] of bouncing billiard balls are understood under the umbrella of [[rigid body motion]] and [[elastic collision]]s.<ref>Pool Table Simulation (calpoly.edu)

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

<nowiki>https://users.csc.calpoly.edu/~zwood/teaching/csc471/finalW19/jpietrok/index.html</nowiki></ref> An initial description of the situation would be given, with a very precise physical description of the billiard table and balls, as well as initial positions of all the balls.<ref><nowiki>https://www.cs.rpi.edu/~cutler/classes/advancedgraphics/S09/final_projects/anderson.pdf</nowiki></ref> Based on a force applied to the cue ball, the [[computer program]] would calculate the trajectories, precise motion and eventual resting places of all the balls. A program to simulate this game would consist of several portions, one of which would be responsible for calculating the precise impacts between the billiard balls. This particular example also turns out to be [[condition number|ill conditioned]]: as a small error in any calculation will cause drastic changes in the final position of the billiard balls.

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

Video games have similar requirements, with some crucial differences. While some computer simulations need to simulate real-world physics as precisely as possible, computer games need to simulate real-world physics in an ''acceptable'' way, in [[Real-time computing|real time]] and robustly. Compromises are allowed, so long as the resulting simulation is satisfying to the game players.

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

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

== Collision detection in computer simulation ==