Collision detection

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 where the number of required narrow phase collision tests was ${\displaystyle O(n+m)}$ where ${\displaystyle n}$ is the number of objects and ${\displaystyle m}$ is the number of objects at close proximity. This is a significant improvement over the quadratic complexity of the naive approach.

Spatial partitioning

Several approaches can be grouped under the spatial partitioning umbrella, which includes octrees (for 3D), quadtrees (for 2D), binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Dynamic scenes and deformable objects require updating the partitioning which can add overhead.

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.

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 can be a suitable approach.

Several key observation make the implementation efficient: Two bounding-boxes intersect 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 move, re-sorting the intervals helps keep track of the status.

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

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.

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.

The result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

Precomputed pruning

Many video game levels contain static geometry that is created once and reused whenever the game is played. It is therefore advantageous to precompute data structures that accelerate in-game collision detection. Such precomputation may include constructing bounding volumes and bounding-volume hierarchies, building spatial partitions, and defining explicit collision masks or exclusion tables for object pairs that need not be tested.

Continuous collision detection

Continuous collision detection (CCD) determines whether moving objects intersect during a time interval and may also determine or bound the time of impact. The methods used depend on the objects' geometric representations and include algorithms based on root finding and conservative advancement.

For triangle meshes whose vertices follow linear trajectories over a time step, triangle–triangle CCD can be decomposed into vertex–face and edge–edge queries. These queries are often performed in two stages: identifying candidate times at which the primitives are coplanar, and then determining whether they are in contact at those times. Coplanarity is a necessary but not sufficient condition for collision, and candidate times can be found by computing the roots of a cubic polynomial. Numerical and interval-based root-finding methods are often used in this context, with robustness near degenerate configurations being an important consideration.

Usage

Collision detection in computer simulation

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, roll back the simulation, and calculate the collision by the more abstract methods of conservation laws.

Some iterate the linear interpolation (Newton's method) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in air traffic control.

After an inelastic collision, special states of sliding and resting can occur and, for example, the Open Dynamics Engine uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a scene graph avoids drift.

In other words, physical simulators usually function one of two ways: where the collision is detected a posteriori (after the collision occurs) or a priori (before the collision occurs). In addition to the a posteriori and a priori distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than a posteriori and a priori.

A posteriori (discrete) versus a priori (continuous)

In the a posteriori case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called a posteriori because it typically misses the actual instant of collision, and only catches the collision after it has actually happened.

In the a priori methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called a priori because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies.

The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. An a priori algorithm must deal with the time variable, which is absent from the a posteriori problem.

On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small.

The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical root finder is usually involved.

Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph.

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.

For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two-dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between sprites on the screen. 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 ${\displaystyle n}$-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

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.