Content deleted Content added
NotAG on AWB (talk | contribs) replace {{manual}} with {{how-to}} per TfD, typo(s) fixed: Therefore → Therefore,, e.g → e.g. |
|||
Line 1:
{{Short description|Term in computer science}}
{{About|collision detection in computational geometry|collision detection in computer networks|Carrier-sense multiple access with collision detection}}
{{redirect|Hitbox}}
{{Multiple issues|{{Technical|section|date=March 2020}} {{Tone|section|{{subst:March 2020}}|date=
'''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]], [[
== Overview ==
Line 26:
=== Spatial partitioning ===
Several approaches can grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s (for 3D), [[
===Bounding volume hierarchy===
[[Bounding volume hierarchy|Bounding Volume Hierarchy]] (BVH) 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.
=== Exploiting temporal coherence ===
During the broad-phase, when the objects in the world move or deform, the data-structures used to cull collisions have to be updated. In cases where the changes between two frames or time-steps are small and the objects can be approximated well with [[axis-aligned bounding box]]es, the [[sweep and prune]] algorithm<ref name=":0" /> can be a suitable approach.
Several key observation make the implementation efficient: Two bounding-boxes intersect [[If and only if|if, and only if]], there is overlap along all three axes; overlap can be determined, for each axis separately, by sorting the intervals for all the boxes; and lastly, between two frames updates are typically small (making sorting algorithms optimized for almost-sorted lists suitable for this application). The algorithm keeps track of currently intersecting boxes, and as objects moves, re-sorting the intervals helps keep track of the status.<ref>{{Cite book |last=Ericson |first=Christer |url=https://realtimecollisiondetection.net/books/rtcd/ |title=Real-time collision detection |date= 22 December 2004|publisher=Elsevier |isbn=978-1-55860-732-3 |edition=Nachdr. |series=Morgan Kaufmann series in interactive 3D technology |___location=Amsterdam Heidelberg |pages=329–338}}</ref>
Line 59 ⟶ 60:
Many variants of the algorithms are obtained by choosing something other than a sphere for <math>B(T)</math>. If one chooses [[axis-aligned bounding box]]es, one gets AABBTrees. [[Oriented bounding box]] trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as [[Spline (mathematics)|spline]]s instead of simple triangles.
== Narrow phase ==
Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. In this phase, the objects under consideration are relatively close to each other. Still, attempts to quickly determine if a full intersection is needed are employed first. This step is sometimes referred to as mid-phase.<ref name=":col1" /> Once these tests passed (e.g. the pair of objects may be colliding) 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.
===Bounding volumes===
A quick way to potentially avoid a needless expensive computation is to check if the bounding volume enclosing the two objects intersect. If they don't, there is not need to check the actual objects. However, if the [[bounding volume]] intersect, the more expensive computation has to be performed. In order for the bounding-volume test to add value, two properties need to be balanced: a) the cost of intersecting the bounding volume needs to be low and b) the bounding volume needs to be tight enough so that the number of 'false positive' intersection will be low. A false positive intersection in this case means that the bounding volume intersect but the actual objects do not. Different bounding volume types offer different trade-offs for these properties.
[[Minimum bounding box#Axis-aligned minimum bounding box|Axis-Align Bounding Boxes (AABB)]] and [[cuboid]]s are popular due to their simplicity and quick intersection tests.
Bounding volumes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding volumes need be compared in detail.<ref>{{cite journal |author=Gan B, Dong Q |date=2022 |title=An improved optimal algorithm for collision detection of hybrid hierarchical bounding box |url=https://www.researchgate.net/publication/348937861 |journal=Evolutionary Intelligence |volume=15 |issue=4 |pages=2515–2527 |doi=10.1007/s12065-020-00559-6}}</ref> Computing collision or overlap between bounding volumes involves additional computations, therefore, in order for it to beneficial we need the bounding volume to be relatively tight and the computation overhead to due the collisions to be low.
=== Exact pairwise collision detection ===
{{
Objects for which pruning approaches could not rule out the possibility of a collision have to undergo an exact collision detection computation.
==== Collision detection between convex objects ====
Line 104 ⟶ 103:
=== Collision detection in computer simulation ===
{{unreferenced
Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. This is very CPU intensive for low softness materials. Some simulators estimate the time of collision by [[linear interpolation]], [[Rollback (data management)|roll back]] the simulation, and calculate the collision by the more abstract methods of [[conservation laws]].
| |||