1 Fundamentals

Collision detection is the computational task of determining whether two or more objects intersect, overlap, or come into contact. In practice, it may also estimate where contact occurs, when an impact will happen, and how close objects are to one another. The field is a core part of interactive systems that need to react quickly to moving shapes, from animated simulations to autonomous machines.

1.1 Definition and purpose

The main purpose of collision detection is to identify geometric interactions before they cause incorrect behavior in a program or simulation. In a game, it prevents a character from walking through walls; in robotics, it helps avoid obstacles; in engineering software, it can reveal whether components fit together. The same basic problem can be solved at different levels of precision depending on the application.

1.2 Geometric primitives

Many systems simplify complex objects into geometric primitives such as points, line segments, triangles, boxes, spheres, and convex polyhedra. These shapes are easier to test for overlap than detailed meshes. More elaborate models may be represented by collections of primitives, allowing the system to balance speed and accuracy.

1.3 Broad-phase and narrow-phase detection

Collision detection is often divided into broad-phase and narrow-phase stages. The broad phase quickly excludes pairs that are far apart, reducing the number of detailed tests. The narrow phase then performs exact or near-exact checks on the remaining candidates. This two-stage structure is common because full pairwise testing becomes expensive as the number of objects grows.

1.4 Static and dynamic collision detection

Static collision detection considers objects at a fixed instant, asking whether they overlap at that moment. Dynamic collision detection examines motion over time and can detect whether moving bodies will meet during an interval. The dynamic case is more demanding, since fast motion may cause an object to pass through another between frames if only snapshots are used.

1.5 Discrete and continuous methods

Discrete methods test objects at separated time steps, usually once per frame or simulation step. Continuous methods analyze the path of motion between steps and can detect the exact moment of first contact. Discrete approaches are simpler and faster, while continuous approaches are more reliable for high-speed movement and thin objects.

2 Algorithms and techniques

A wide variety of algorithms are used to make collision detection efficient. Some methods organize objects in space so that only nearby candidates are compared, while others rely on mathematical tests for intersection or distance. The choice of technique depends on object shape, motion pattern, and performance requirements.

2.1 Bounding volumes

Bounding volumes enclose more detailed geometry inside a simpler shape. They are useful because overlap tests for these enclosing shapes are generally faster than tests against the original object. If the bounding volumes do not intersect, the enclosed objects cannot intersect either.

2.1.1 Axis-aligned bounding boxes

Axis-aligned bounding boxes are rectangular boxes whose faces remain aligned with the coordinate axes. They are inexpensive to compute and test, which makes them common in broad-phase systems. Their limitation is that they may fit rotated objects poorly, leaving extra empty space inside the box.

2.1.2 Oriented bounding boxes

Oriented bounding boxes can rotate with the object they enclose, producing a tighter fit than axis-aligned boxes. This can reduce unnecessary candidate pairs, especially for elongated or tilted shapes. The overlap test is more complex, however, because the box orientation must be taken into account.

2.1.3 Bounding spheres

Bounding spheres enclose objects within a radius from a center point. They are especially simple to compare, since two spheres intersect when the distance between their centers is less than the sum of their radii. Spheres are rotationally invariant, though they can be inefficient for long or irregular shapes.

2.2 Spatial partitioning

Spatial partitioning divides space into regions so that objects need to be compared mainly with others in the same or neighboring regions. This can greatly reduce the number of candidate interactions in large scenes. Such methods are often used together with bounding volumes.

2.2.1 Uniform grids

Uniform grids partition space into equal-sized cells. Each object is associated with one or more cells, and only objects sharing a cell are tested against one another. This method is straightforward and works well when objects are evenly distributed, but performance can decline if many objects cluster in a small area.

2.2.2 Quadtrees and octrees

Quadtrees subdivide two-dimensional space into smaller regions, while octrees do the same in three dimensions. Regions are recursively split when they contain too much detail or too many objects. These structures adapt well to scenes with uneven density, making them useful for large environments and hierarchical searches.

2.2.3 BSP trees

Binary space partitioning trees divide space using recursive cutting planes. Each node separates geometry into front and back portions, allowing efficient organization of complex scenes. BSP trees can support fast visibility and collision queries, although building and updating them may be expensive in dynamic worlds.

2.3 Intersection tests

Intersection tests answer whether two geometric entities meet under a specified condition. They are the building blocks of narrow-phase detection and often rely on vector mathematics, plane equations, and distance calculations. Different tests are optimized for different pairs of shapes.

2.3.1 Point-in-shape tests

Point-in-shape tests determine whether a point lies inside a region such as a circle, polygon, sphere, or polyhedron. These checks are useful for containment queries, selection tools, and inclusion tests in simulation. For polygons and solids, the method may use ray casting, winding rules, or half-space comparisons.

2.3.2 Line and ray intersection

Line and ray intersection tests determine whether a segment or infinite ray crosses a shape. They are commonly used in visibility checks, shooting mechanics, sensor simulation, and picking interfaces. The result may include the intersection point, the distance along the ray, or the first object hit.

2.3.3 Polygon and mesh intersection

Polygon and mesh intersection methods compare more complex boundaries made from edges and faces. They may test for edge crossings, face overlap, or penetration between triangle sets. Because meshes can contain many elements, these tests are often combined with bounding volumes or hierarchical acceleration structures.

2.4 Swept-volume methods

Swept-volume methods account for the space occupied by a moving object over time. Instead of checking only the start and end positions, they consider the full path of motion. This helps detect collisions that would otherwise be missed between discrete updates.

2.4.1 Time of impact calculation

Time of impact calculation estimates when two moving objects first touch. It is important for preventing tunneling, where fast objects pass through others without registering contact. The computed time can be used to stop motion precisely at the moment of first collision or to trigger a response at that instant.

2.4.2 Continuous collision checking

Continuous collision checking examines motion continuously rather than at isolated frames. It is frequently used when movement is rapid, objects are small, or safety is critical. The method is more computationally demanding than discrete checks, but it offers better accuracy in many dynamic systems.

2.5 Minkowski sum and support-mapping methods

Minkowski sum and support-mapping methods reformulate collision detection into operations on convex shapes. These techniques are powerful for convex objects and can be extended, with additional processing, to more elaborate models. They are especially useful in computational geometry and physics simulation.

2.5.1 Gilbert–Johnson–Keerthi algorithm

The Gilbert–Johnson–Keerthi algorithm is a well-known method for determining whether two convex shapes intersect. It works by searching the Minkowski difference of the shapes and checking whether the origin lies inside it. The algorithm is widely used because it is efficient and can also support distance queries.

2.5.2 Expanding polytope algorithm

The expanding polytope algorithm is often used after a collision is detected to compute penetration depth and contact information. Starting from a simplex, it expands a polytope toward the boundary of the Minkowski difference. This makes it valuable for obtaining detailed contact data rather than a simple yes-or-no answer.

3 Applications

Collision detection appears in many digital systems that model movement, interaction, or physical contact. Its role ranges from visual realism to operational safety. In some fields it is central to simulation quality; in others it supports responsiveness and user experience.

3.1 Video games

In video games, collision detection governs how characters, projectiles, and environments interact. It helps preserve the illusion of a consistent world by preventing impossible overlaps and by triggering gameplay events. Real-time performance is especially important because these checks must be performed repeatedly during play.

3.1.1 Character movement

Character movement often depends on collision detection to keep avatars from passing through floors, walls, or obstacles. The system may adjust position, slide along surfaces, or stop motion altogether. Smooth movement usually requires careful tuning so that contact feels natural rather than abrupt.

3.1.2 Projectile handling

Projectile handling uses collision tests to determine whether a moving object hits a target or environment feature. Fast projectiles may require continuous checks to avoid missing thin obstacles. The result may trigger damage, an explosion, or another in-game event.

3.1.3 Environmental interaction

Environmental interaction includes doors, platforms, trigger zones, and destructible elements. Collision detection can determine whether a player activates a region or whether an object should respond to contact. This allows the environment to behave in ways that are visually and mechanically coherent.

3.2 Robotics

Robotics uses collision detection to support safe and efficient movement. A robot must know whether its body, arm, or tools are likely to intersect obstacles in the workspace. These computations are closely tied to planning, control, and sensor interpretation.

3.2.1 Motion planning

Motion planning seeks paths that avoid collisions while moving from one configuration to another. Collision detection is used repeatedly during path search to evaluate candidate trajectories. Efficient geometric checks are essential because the planner may explore many possible motions.

3.2.2 Obstacle avoidance

Obstacle avoidance relies on detecting imminent contact and adjusting motion before impact occurs. Robots may use internal models, sensor data, or both to estimate clearance. The approach is common in mobile robots, manipulators, and autonomous systems that operate in crowded spaces.

3.3 Computer-aided design

Computer-aided design software uses collision detection to verify whether parts overlap or assemble correctly. This is useful during product development, where designers need to confirm shape compatibility before manufacturing. The analysis can also reveal situations where tolerances are too tight for reliable assembly.

3.3.1 Assembly checking

Assembly checking tests whether components fit together without unwanted interference. It helps identify clashes between mechanical parts and can support early correction of design errors. The process is especially valuable in complex products with many moving or nested parts.

3.3.2 Tolerance analysis

Tolerance analysis studies how permitted variation in dimensions affects fit and clearance. Collision detection can be applied to worst-case or probabilistic models to determine whether parts still avoid overlap. This helps engineers understand how manufacturing variation influences function.

3.4 Simulation and virtual reality

Simulation and virtual reality use collision detection to create plausible interaction between objects and users. The method contributes to realism in physical models and to immersion in interactive environments. It also supports training systems where contact behavior must be believable.

3.4.1 Physics engines

Physics engines use collision detection as a first step before computing forces, constraints, and motion responses. Once contact is identified, the engine may calculate impulses or constraints to prevent interpenetration. Accurate detection is important for stable and believable physical behavior.

3.4.2 Haptic systems

Haptic systems provide touch feedback by responding to detected collisions between a virtual tool and simulated objects. The computation must often be fast enough to maintain a steady tactile sensation. This makes both precision and low latency important design goals.

4 Implementation considerations

Practical collision detection is shaped by computational limits, numerical behavior, and the timing demands of interactive software. Designers must decide how much precision to use, which data structures to employ, and how to keep updates fast enough for real-time operation.

4.1 Performance optimization

Performance optimization reduces the cost of repeated collision queries. Since many systems check large numbers of objects every frame, small efficiency gains can have a significant effect. Common strategies include hierarchical filtering, simplified geometry, and reuse of intermediate results.

4.1.1 Cache-friendly data structures

Cache-friendly data structures arrange data so that the processor can access nearby memory locations efficiently. This can improve throughput when many objects are tested in sequence. Arrays, compact records, and carefully ordered scene data are often preferred over scattered pointer-based layouts.

4.1.2 Parallel processing

Parallel processing distributes collision work across multiple cores or processing units. Independent broad-phase checks and many narrow-phase tests can often be run concurrently. The approach can increase speed substantially, though it may require careful synchronization and task scheduling.

4.2 Numerical robustness

Numerical robustness concerns the reliability of collision results in the presence of rounding error and finite precision arithmetic. Even small numerical mistakes can cause missed contacts, incorrect intersections, or unstable responses. Robust methods reduce these risks through careful formulation and guard conditions.

4.2.1 Floating-point precision

Floating-point precision limits how accurately positions, distances, and angles can be represented. Near-touching objects may be especially sensitive to small errors. Algorithms often use tolerances, exact predicates, or fallback logic to handle borderline cases consistently.

4.2.2 Degenerate cases

Degenerate cases occur when shapes or configurations fall into special conditions such as zero area, collinearity, or coincident boundaries. These situations can confuse standard intersection formulas. Robust implementations include explicit handling for such cases to avoid failures or unstable results.

4.3 Approximation trade-offs

Approximation trade-offs arise because no single method is both perfectly accurate and maximally fast for every situation. A system may deliberately simplify geometry or accept limited error to meet performance goals. The best compromise depends on whether speed, precision, or stability matters most.

4.3.1 Accuracy versus speed

Accuracy versus speed is a central design choice in collision detection. Highly detailed methods can produce better results but cost more computation, while coarse methods are faster but less exact. Many practical systems combine several layers of approximation to achieve a balanced outcome.

4.3.2 False positives and false negatives

False positives occur when an algorithm reports a collision that does not really exist, while false negatives miss a genuine contact. False positives may lead to unnecessary responses, and false negatives can allow objects to interpenetrate. Good system design aims to minimize both while keeping computation manageable.

4.4 Real-time constraints

Real-time constraints require collision detection to finish within strict time limits. Interactive applications often need updates every frame, which means algorithms must be predictable as well as efficient. Systems that miss deadlines can produce lag, stutter, or unstable motion.

4.4.1 Frame updates

Frame updates are the regular cycles in which simulation and rendering are advanced. Collision detection must fit within these cycles so that object motion appears continuous and responsive. Techniques that scale well with object count are especially important in this setting.

4.4.2 Latency management

Latency management reduces the delay between an object’s motion and the system’s reaction to it. Lower latency improves responsiveness in games, robotics, and haptic interfaces. To achieve this, implementations may use incremental updates, simplified checks, or predictive methods.

Collision detection is closely connected to several other computational topics. These include the algorithms that determine how objects react after contact, methods for measuring separation, and planning techniques that avoid contact altogether. Together, these areas support realistic and efficient spatial reasoning.

5.1 Collision response

Collision response describes what happens after a collision has been detected. A system may change velocity, reposition objects, apply constraints, or trigger events. Detection and response are separate steps, but they are usually designed together.

5.1.1 Impulse resolution

Impulse resolution computes instantaneous changes in momentum at the contact point. It is commonly used to simulate bouncing, sliding, and stacking behavior. The method aims to separate objects and produce a plausible post-collision motion.

5.1.2 Friction and restitution

Friction and restitution are material properties that influence how objects move after contact. Friction resists sliding motion, while restitution controls how much energy is preserved in a bounce. These values help shape the realism of physical interaction.

5.2 Distance computation

Distance computation measures the separation between objects rather than only whether they intersect. It can be used to find closest points, estimate clearance, or prepare a future collision test. This information is useful in both motion planning and geometric analysis.

5.3 Contact mechanics

Contact mechanics studies the forces and deformations that arise when bodies touch. In computational systems, simplified contact models are often used instead of full physical analysis. The subject connects geometry, physics, and numerical methods.

5.4 Motion planning and pathfinding

Motion planning and pathfinding both aim to find feasible routes through space, often while avoiding obstacles. Collision detection provides the tests needed to reject unsafe paths. While pathfinding is usually associated with discrete maps, motion planning often deals with continuous geometry and more detailed constraints.