Collision detection

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Collision detection is the computational problem of detecting an 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 games, robotics (including autonomous driving), and computational physics. Collision detection algorithms can be divided into operating on 2D or 3D spatial objects.

Collision detection is the computational problem of detecting an 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 games, robotics (including autonomous driving), and computational physics. Collision detection algorithms can be divided into operating on 2D or 3D spatial objects.

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 n objects, {n(n-1)}/{2} intersection tests are needed with a naive approach. This quadratic growth makes such an approach computationally expensive as n increases. 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.

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.

Bounding volume hierarchy

A bounding volume hierarchy (BVH) is a tree structure in which each node is associated with a bounding volume enclosing the geometric primitives represented by its subtree. During collision detection, the tree is traversed from the root towards the leaves. If a node's bounding volume does not intersect the object or bounding volume being tested, its entire subtree can be discarded. Otherwise, the traversal continues to its child nodes.

Hence, all the primitives associated with the discarded branches can be excluded without testing each primitive individually. To test two complex objects for collision, their BVHs can be traversed together, beginning with the root nodes. Pairs of branches whose bounding volumes do not intersect are discarded, while overlapping pairs are examined recursively. Exact intersection tests between the enclosed geometric primitives, often triangles and their components (vertices and edges), are required only for primitives contained in overlapping leaf nodes.

The same approach can be used for self-collision detection. BVHs can organize the geometric primitives of a single object, the components of an articulated body, or multiple objects in a scene. They can be used with rigid and deformable objects, although a hierarchy over deformable geometry must be updated as the geometry changes.

Because exact intersection tests are deferred to the leaves, BVHs can also accelerate collision detection between objects represented by different types of geometric primitives, provided suitable leaf-level intersection tests are available.

Bounding volumes

Since checking whether two objects intersect can be a relatively expensive operation, one quick way to potentially avoid the computation is to check whether the bounding volumes enclosing the two objects intersect. Bounding volumes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping volumes need be compared in detail. If they don't overlap, there is no need to check the actual objects.

Computing overlap or collision between bounding volumes involves additional computations, so in order for the bounding-volume test to add value: 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' intersections will be low. A false positive intersection in this case means that the bounding volumes intersect but the actual objects do not. Different bounding volume types offer different trade-offs for these properties.

Axis-Align Bounding Boxes (AABB) and cuboids are popular due to their simplicity and quick intersection tests. Bounding volumes such as Oriented Bounding Boxes (OBB), K-DOPs and Convex-hulls offer a tighter approximation of the enclosed shape at the expense of a more elaborate intersection test.

See also

Chazelle polyhedron Collision response Hit-testing Bounding volume Game physics Gilbert–Johnson–Keerthi distance algorithm Minkowski Portal Refinement Physics engine Lubachevsky–Stillinger algorithm Ragdoll physics Sprite

References

External links

Collision detection in CSS animations University of North Carolina at Chapel Hill collision detection research website Prof. Steven Cameron (Oxford University) web site on collision detection How to Avoid a Collision by George Beck, Wolfram Demonstrations Project. Separating Axis Theorem Unity 3D Collision Godot Physics Collision

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378598094 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

14 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.