Collision detection: Difference between revisions

Revision as of 04:03, 1 November 2024

Revision as of 03:12, 7 November 2024

Line 8:

}}

'''Collision detection''' is the [[computational problem]] of detecting an [[intersection (geometry)|intersection]] of two or more [[Space|spatial]] objects, commonly computer graphics objects. It has applications in various computing fields, primarily in [[computer graphics]], [[computer game]]s, [[computer simulation]]s, [[robotics]] (including [[autonomous driving]]) and [[computational physics]]. Collision detection is a classic problem of [[computational geometry]]. 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>

== Overview ==

Line 43:

== Optimization ==

The obvious approaches to collision detection for multiple objects are very slow. [[Triangular number|Checking every object against every other object]] will, of course, work, but is too inefficient to be used when the number of objects is at all large. Checking objects with complex geometry against each other in the obvious way, by checking each face against each other face, is itself quite slow. Thus, considerable research has been applied to speed up the problem.

The obvious approaches to collision detection for multiple objects are very slow.

[[Triangular number|Checking every object against every other object]] will, of course, work, but is too inefficient to be used when the number of objects is at all large. Checking objects with complex geometry against each other in the obvious way, by checking each face against each other face, is itself quite slow. Thus, considerable research has been applied to speed up the problem.

=== Exploiting temporal coherence ===

Line 51 ⟶ 50:

{{Unreferenced section|date=July 2024}}|section=y}}

In many applications, the configuration of physical bodies from one time step to the next changes very little. Many of the objects may not move at all. Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster completion of the calculation.

Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster completion of the calculation.

At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect. Those pairs will require further analysis. An early high performance algorithm for this was developed by [[Ming C. Lin]] at the [[University of California, Berkeley]] [http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html], who suggested using [[axis-aligned bounding box]]es for all ''n'' bodies in the scene.

Line 174 ⟶ 172:

Here the length/distance of the segment is an adjustable "hit" criteria size of segment. As the objects approach the length decreases to the threshold value. A triangle sphere becomes the effective geometry test. A sphere centered at the centroid can be sized to encompass all the triangle's vertices.

== Video gamesUsage ==

=== Video games ===

Video games have to split their very limited computing time between several tasks. Despite this resource limit, and the use of relatively primitive collision detection algorithms, programmers have been able to create believable, if inexact, systems for use in games.{{Citation needed|date=August 2014}}

Line 187:

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

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

<!-- Deleted image removed: [[File:GearheadsCollisionBox.png|thumb|The hitbox of a ''[[Gearheads (video game)|Gearheads]]'' toy, controlled by the above screen {{Deletable file-caption|Tuesday, 9 July 2024|F7}}]] -->