Collision detection

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.

Overview

upright=1.3|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 distance between objects, as objects collide when the distance between them is less than or equal to zero. Negative distances indicate that one object has penetrated another. Performing collision detection requires more context than just the distance between the objects.

Accurately identifying the points of contact on both objects' surfaces is also essential for computing 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.

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.

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.

Broad phase

This phase aims at quickly finding objects or parts of objects for which it can be quickly determined that no further collision test is needed. A useful property of such approach is that it is output sensitive. In the context of collision detection this means that the time complexity of the collision detection is proportional to the number of objects that are close to each other. An early example of that is the I-COLLIDE 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 boxes, the sweep and prune algorithm

Pairwise pruning

Once a pair of physical bodies has been selected for further investigation, collisions need to be checked more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So there are two sets of triangles, <math>S={S_1,S_2,\dots,S_n}</math> and <math>T={T_1,T_2,\dots,T_n}</math> (for simplicity, each set has the same number of triangles.)

The obvious thing to do is to check all triangles <math>S_j</math> against all triangles <math>T_k</math> for collisions, but this involves <math>n^2</math> comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles that need to be checked.

The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (e.g., <math>S</math> and <math>T</math>) calculates a hierarchy of bounding volumes. Then, at each time step, when collisions need to be checked between <math>S</math> and <math>T</math>, the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, provide an example using bounding spheres, although it has been noted that spheres are undesirable in many cases.

If <math>E</math> is a set of triangles, a bounding sphere is pre-calculated. <math>B(E)</math>. There are many ways of choosing <math>B(E)</math>, <math>B(E)</math> is a sphere that completely contains <math>E</math> and is as small as possible.

Ahead of time, <math>B(S)</math> and <math>B(T)</math> can be computed. Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do <math>S</math> and <math>T</math>. This is not much better than an n-body pruning algorithm, however.

If <math>E={E_1,E_2,\dots,E_m}</math> is a set of triangles, then split it into two halves <math>L(E):={E_1,E_2,\dots,E_{m/2</math> and <math>R(E):={E_{m/2+1},\dots,E_{m-1},E_m}</math>. Apply this to <math>S</math> and <math>T</math>, and calculate (ahead of time) the bounding spheres <math>B(L(S)),B(R(S))</math> and <math>B(L(T)),B(R(T))</math>. The hope here is that these bounding spheres are much smaller than <math>B(S)</math> and <math>B(T)</math>. And, if, for instance, <math>B(S)</math> and <math>B(L(T))</math> do not intersect, then there is no sense in checking any triangle in <math>S</math> against any triangle in <math>L(T)</math>.

As a precomputation, take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node <math>N</math> represents a set of triangles, and its two children represent <math>L(N)</math> and <math>R(N)</math>. At each node in the tree, pre-compute the bounding sphere <math>B(N)</math>.

When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles.

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 boxes, 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 splines 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. 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.

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

According to the separating planes theorem, for any two disjoint convex objects, there exists a plane so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This property allows the development of efficient collision detection algorithms between convex objects. Several algorithms are available for finding the closest points on the surface of two convex polyhedral objects - and determining collision. Early work by Ming C. Lin that used a variation on the simplex algorithm from linear programming and the Gilbert-Johnson-Keerthi distance algorithm are two such examples. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, and every step is initialized from the previous collision check. In other cases, simply tiling the screen and binding each sprite into the tiles it overlaps provides sufficient pruning, and for pairwise checks, bounding rectangles or circles called hitboxes are used and deemed sufficiently accurate.

Three-dimensional games have used spatial partitioning methods for <math>n</math>-body pruning, and for a long time used one or a few spheres per actual 3D object for pairwise checks. Exact checks are very rare, except in games attempting to simulate reality closely. Even then, exact checks are not necessarily used in all cases.

Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use a posteriori collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far.

In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, binary space partitioning trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.

A robust simulator is one that will react to any input in a reasonable way. For instance, imagining a high speed racecar video game, it is conceivable that the cars would advance a substantial distance along the race track from one simulation step to the next. 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 bugs 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, 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 ====

thumb|upright|Example of hitboxes of an attacking character in a [[fighting game. The green hitbox represents character collision zone, the red hitbox represents the attack's hit zone.]]

A hitbox is an invisible shape commonly used in video games for real-time collision detection; it is a type of bounding box. It is often a rectangle (in 2D games) or cuboid (in 3D) that is attached to and follows a point on a visible object (such as a model or a sprite). Circular or spheroidial shapes are also common, though they are still most often called "boxes". It is common for animated objects to have hitboxes attached to each moving part to ensure accuracy during motion.

Hitboxes are used to detect "one-way" collisions such as a character being hit by a punch or a bullet. They are unsuitable for the detection of collisions with feedback (e.g. bumping into a wall) due to the difficulty experienced by both humans and AI in managing a hitbox's ever-changing locations; these sorts of collisions are typically handled with much simpler axis-aligned bounding boxes instead. Players may use the term "hitbox" to refer to these types of interactions regardless.

A hurtbox is a hitbox used to detect incoming sources of damage. In this context, the term hitbox is typically reserved for those which deal damage. For example, an attack may only land if the hitbox around an attacker's punch connects with one of the opponent's hurtboxes on their body, while opposing hitboxes colliding may result in the players trading or cancelling blows, and opposing hurtboxes do not interact with each other. The term is not standardized across the industry; some games reverse their definitions of hitbox and hurtbox, while others only use "hitbox" for both sides.

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