The Central Idea
Two objects collide when their occupied regions have a nonempty intersection.
If objects occupy regions \(A\) and \(B\), then collision means
\[ \boxed{ A\cap B\ne\varnothing }. \]Computationally, however, testing this intersection directly may be expensive. Efficient systems therefore organize collision detection into stages.
Broad Phase and Narrow Phase
Collision detection is commonly divided into two major stages.
- Broad phase: quickly reject pairs that cannot collide.
- Narrow phase: apply a more exact geometric test to the remaining candidate pairs.
This structure avoids spending expensive computation on obviously separated objects.
Why the Broad Phase Matters
Suppose a simulation contains
\[ n \]objects.
Testing every unordered pair directly would require
\[ \boxed{ \frac{n(n-1)}{2} } \]pair checks.
For large \(n\), this quadratic growth becomes expensive.
Bounding Volumes
A bounding volume is a simpler region that contains a more complicated object.
Common examples include:
- axis-aligned bounding boxes;
- oriented bounding boxes;
- bounding circles or spheres;
- capsules;
- convex hulls.
If two bounding volumes are disjoint, the underlying objects are also disjoint.
Bounding-Volume Rejection
Let
\[ A\subseteq B_A \qquad\text{and}\qquad B\subseteq B_B, \]where \(B_A\) and \(B_B\) are bounding volumes.
Then
\[ B_A\cap B_B=\varnothing \]implies
\[ \boxed{ A\cap B=\varnothing }. \]This makes bounding-volume tests excellent early rejection tools.
Bounding-Volume Overlap Does Not Prove Collision
Two bounding boxes can overlap even when the objects inside them do not.
Therefore,
\[ B_A\cap B_B\ne\varnothing \]does not necessarily imply
\[ A\cap B\ne\varnothing. \]Broad-phase overlap produces a candidate pair, not a final answer.
Axis-Aligned Bounding Boxes
In two dimensions, an axis-aligned bounding box, or AABB, can be represented by
\[ [x_{\min},x_{\max}] \times [y_{\min},y_{\max}]. \]Two AABBs overlap when their intervals overlap on both coordinate axes.
One-Dimensional Interval Overlap
Two closed intervals
\[ [a_{\min},a_{\max}] \]and
\[ [b_{\min},b_{\max}] \]overlap when
\[ \boxed{ a_{\max}\ge b_{\min} \quad\text{and}\quad b_{\max}\ge a_{\min} }. \]AABB Collision Test
Two closed AABBs overlap when
\[ x_{A,\max}\ge x_{B,\min}, \] \[ x_{B,\max}\ge x_{A,\min}, \] \[ y_{A,\max}\ge y_{B,\min}, \]and
\[ y_{B,\max}\ge y_{A,\min}. \]Failure on even one axis proves separation.
Separating Axes
The AABB test illustrates a broader principle: if two objects are separated along even one projection axis, they cannot overlap in full space.
This idea leads to the separating axis theorem.
The Separating Axis Theorem
For two convex polygons, they are disjoint if and only if there exists a line direction onto which their projected intervals do not overlap.
Such a direction is called a separating axis.
\[ \boxed{ \text{one separating axis} \Rightarrow \text{no collision} }. \]Candidate Axes for Convex Polygons
In two dimensions, it is sufficient to test axes perpendicular to the edges of both polygons.
If no such axis separates the projected intervals, the convex polygons overlap or touch.
Projecting a Point onto an Axis
Let \(\mathbf{a}\) be a chosen axis direction.
A vertex \(P\) can be projected using the dot product:
\[ \boxed{ s=P\cdot\mathbf{a} }. \]The polygon's projection interval is found from the minimum and maximum values of \(s\) over all its vertices.
Projection Intervals
For polygon \(A\), compute
\[ I_A= [s_{A,\min},s_{A,\max}]. \]For polygon \(B\), compute
\[ I_B= [s_{B,\min},s_{B,\max}]. \]If the intervals are disjoint on any candidate axis, the polygons are separated.
Touching versus Penetrating
Boundary policy affects the interval comparison.
If touching counts as collision, then intervals that meet at one endpoint are considered overlapping.
If only positive-area penetration counts, strict interval overlap may be required.
Circle-Circle Collision
Let two circles have centers
\[ C_1,\qquad C_2 \]and radii
\[ r_1,\qquad r_2. \]They overlap or touch when
\[ \boxed{ \|C_2-C_1\|\le r_1+r_2 }. \]Squared Circle-Circle Test
The square root is unnecessary.
Instead test
\[ \boxed{ \|C_2-C_1\|^2 \le (r_1+r_2)^2 }. \]This is usually faster and numerically simpler.
Circle-Point Collision
A point \(P\) lies inside or on a circle centered at \(C\) with radius \(r\) when
\[ \boxed{ \|P-C\|^2\le r^2 }. \]This is the same point-in-circle predicate used in point-in-region testing.
Circle-Segment Collision
A circle intersects a segment when the minimum distance from the circle center to the segment is at most the radius.
Therefore, the key construction is the closest point on the segment.
Closest Point on a Segment
Let segment \(AB\) be parameterized as
\[ S(t)=A+t(B-A), \qquad 0\le t\le1. \]The unconstrained projection parameter of point \(P\) is
\[ t_0= \frac{(P-A)\cdot(B-A)} {(B-A)\cdot(B-A)}. \]Clamping the Projection
The closest point on the finite segment uses
\[ \boxed{ t= \operatorname{clamp}(t_0,0,1) }. \]Then
\[ Q=A+t(B-A) \]is the closest point on the segment to \(P\).
Completing the Circle-Segment Test
Let \(C\) be the circle center and \(Q\) the closest point on segment \(AB\).
Collision occurs when
\[ \boxed{ \|C-Q\|^2\le r^2 }. \]Segment-Segment Collision
Segment collision can use the orientation predicates developed earlier.
For segments \(AB\) and \(CD\), compute
\[ o_1=\operatorname{orient}(A,B,C), \] \[ o_2=\operatorname{orient}(A,B,D), \] \[ o_3=\operatorname{orient}(C,D,A), \] \[ o_4=\operatorname{orient}(C,D,B). \]Proper Segment Crossing
When no orientation value is zero, the segments properly cross when
\[ \boxed{ o_1o_2<0 \quad\text{and}\quad o_3o_4<0 }. \]Endpoint contact and collinear overlap must be handled separately.
Polygon Collision
Collision between general polygons can involve:
- edge-edge intersections;
- one polygon lying inside another;
- shared boundary portions;
- touching at vertices or edges.
A complete test must account for all of these possibilities.
Convex Polygon Collision
For convex polygons, the separating axis theorem provides an elegant complete test.
Test projection overlap on axes normal to every edge of both polygons.
If all intervals overlap, the polygons intersect or touch.
Concave Polygon Collision
The standard separating axis theorem does not directly reduce concave polygon collision to only edge-normal projections.
Common strategies include:
- triangulating or convexly decomposing the polygons;
- testing boundary intersections plus containment;
- using hierarchical bounding structures.
Convex Decomposition
A concave object can be divided into several convex pieces.
Collision detection then reduces to testing pairs of convex components.
This shifts complexity from the narrow-phase predicate into preprocessing.
Bounding Circles and Spheres
Circles and spheres are rotation-invariant bounding volumes.
Their overlap test depends only on center distance and radius sum.
This makes them computationally inexpensive, although they may fit elongated objects poorly.
Oriented Bounding Boxes
An oriented bounding box, or OBB, may rotate with the object.
It can fit a rotated or elongated shape more tightly than an AABB.
The tradeoff is a more expensive overlap test.
Tightness versus Test Cost
Bounding volumes involve a design tradeoff:
\[ \boxed{ \text{tighter fit} \quad\longleftrightarrow\quad \text{more expensive test} }. \]A sphere may be cheap but loose.
A convex hull may be tight but require a more sophisticated narrow-phase test.
Bounding-Volume Hierarchies
A complex object can be organized into a tree of bounding volumes.
The root encloses the whole object.
Child nodes enclose smaller parts.
Leaves contain individual primitives or small groups of them.
Hierarchy Traversal
To test two objects:
- compare their root bounding volumes;
- if separated, stop;
- if overlapping, compare child regions;
- continue only where overlap persists;
- apply primitive tests near the leaves.
This focuses work on geometrically relevant regions.
Spatial Grids for Collision Detection
A domain can be partitioned into grid cells.
Each object is assigned to the cells it occupies.
Only objects sharing one or more cells need to become candidate collision pairs.
Spatial Hashing
A spatial hash maps grid coordinates to storage locations using a hash function.
This provides grid-like spatial organization without allocating every possible cell in advance.
It is especially useful in large sparse domains.
Quadtrees and Octrees
Quadtrees partition two-dimensional space hierarchically.
Octrees provide the analogous idea in three dimensions.
Dense regions can be subdivided more deeply than sparse regions, making these structures useful for adaptive broad-phase collision detection.
Sweep and Prune
Sweep and prune projects object bounds onto one or more coordinate axes.
Objects whose intervals do not overlap on an axis cannot collide.
Maintaining sorted interval endpoints can make repeated broad-phase updates efficient when objects move gradually.
Static versus Dynamic Collision Detection
Static collision detection asks whether objects overlap at a particular instant.
Dynamic or continuous collision detection asks whether they collide at any time during a motion interval.
Why Discrete Time Steps Can Miss Collisions
Suppose an object is on one side of a thin wall at time \(t_0\) and on the other side at time \(t_1\).
If collision is tested only at the endpoints, the object may appear nonintersecting at both times even though it passed through the wall.
This failure is often called tunneling.
Continuous Collision Detection
Continuous collision detection incorporates motion into the geometric test.
Instead of asking only
\[ A(t_0)\cap B(t_0)\ne\varnothing, \]it asks whether there exists
\[ t\in[t_0,t_1] \]such that
\[ \boxed{ A(t)\cap B(t)\ne\varnothing }. \]Time of Impact
A continuous collision solver may seek the earliest
\[ t^* \]satisfying the collision condition.
This value is called the time of impact.
After finding \(t^*\), a physical simulation can resolve the collision and continue from that event.
Moving Circle against Moving Circle
Suppose two circle centers move linearly:
\[ C_1(t)=C_{1,0}+tV_1 \]and
\[ C_2(t)=C_{2,0}+tV_2. \]Collision occurs when
\[ \|C_2(t)-C_1(t)\|^2 = (r_1+r_2)^2. \]Relative Motion Simplifies the Problem
Define relative position
\[ P=C_{2,0}-C_{1,0} \]and relative velocity
\[ V=V_2-V_1. \]Then the moving-circle collision equation becomes
\[ \boxed{ \|P+tV\|^2 = (r_1+r_2)^2 }. \]This is a quadratic equation in \(t\).
Contact Normal
Once a collision point or time is known, a system may need a contact normal.
For two circles with distinct centers, a natural normal is
\[ \boxed{ \mathbf{n} = \frac{C_2-C_1} {\|C_2-C_1\|} }. \]The normal points from one object toward the other.
Penetration Depth
For overlapping circles, the center distance is
\[ d=\|C_2-C_1\|. \]The penetration depth is
\[ \boxed{ \delta= r_1+r_2-d }. \]A positive \(\delta\) measures how far the circles overlap along the center direction.
Collision Detection versus Collision Response
Collision detection answers questions such as:
- Did contact occur?
- Where did it occur?
- When did it occur?
- What is the contact normal?
- How deep is the overlap?
Collision response determines what happens afterward.
The two tasks are related but distinct.
Meshes and Collision Detection
A triangular mesh represents a complex object as many simple primitives.
Collision can then be reduced to:
- bounding-volume tests between mesh regions;
- triangle-triangle tests near candidate contacts;
- edge and vertex feature tests.
Hierarchies prevent every triangle from being tested against every other triangle.
Point-Triangle Collision
In two dimensions, point-triangle collision is a point-in-region test.
In three dimensions, the point must first lie on the triangle's plane and then inside the triangular boundary.
Barycentric coordinates are often useful for the second step.
Triangle-Triangle Collision
In two dimensions, triangle collision can be tested with:
- the separating axis theorem;
- edge intersection plus containment;
- other convex-polygon predicates.
In three dimensions, additional plane and feature relationships must be considered.
Degenerate Objects
Collision systems must define behavior for:
- zero-length segments;
- zero-radius circles;
- zero-area triangles;
- duplicate vertices;
- coincident surfaces;
- objects already interpenetrating at the start of a time step.
Contact Classification
A useful collision routine may distinguish:
\[ \boxed{ \{\text{separated},\text{touching},\text{penetrating}\} }. \]Some systems also need to classify overlapping boundaries or coincident geometric features.
Numerical Robustness
Collision detection frequently operates near boundaries where quantities should theoretically be zero.
Examples include:
\[ d-(r_1+r_2)=0 \]or
\[ \operatorname{orient}(A,B,C)=0. \]Floating-point error can change a touching case into an apparent gap or penetration.
Collision Tolerances
A practical system may use a tolerance
\[ \varepsilon>0 \]and treat sufficiently small separation values as contact.
The tolerance should reflect scale and application requirements rather than being chosen arbitrarily.
Temporal Tolerances
Continuous collision detection can also require tolerances in time.
A computed impact parameter near
\[ t=0 \]or
\[ t=1 \]may need careful clamping or classification so that contacts are not lost because of tiny numerical drift.
False Positives and False Negatives
A false positive reports collision when the objects are actually separated.
A false negative misses a real collision.
In many safety-critical or physical applications, false negatives are especially dangerous.
Conservative Collision Tests
A conservative broad-phase test may intentionally produce some false positives.
That is acceptable if the narrow phase later removes them.
What the broad phase must avoid is incorrectly rejecting a pair that truly collides.
Common Error: Treating Bounding-Box Overlap as Exact Collision
Bounding boxes may overlap while the actual objects remain separated.
Broad-phase overlap means only:
\[ \boxed{ \text{perform a more detailed test} }. \]Common Error: Testing Only Object Positions at Frame Boundaries
Fast-moving objects can pass completely through thin obstacles between two sampled times.
Continuous collision detection or sufficiently conservative swept tests are needed when tunneling matters.
Common Error: Using the Separating Axis Theorem Directly on Concave Polygons
The standard edge-normal SAT test is complete for convex polygons.
Concave polygons generally require decomposition or another strategy.
Common Error: Forgetting Collinear Segment Cases
The proper-crossing orientation test does not by itself detect:
- shared endpoints;
- collinear overlap;
- one endpoint lying on the other segment.
These cases must be handled explicitly.
Common Error: Normalizing a Zero Contact Direction
If two circle centers coincide, then
\[ C_2-C_1=\mathbf{0}. \]The ordinary center-to-center contact normal cannot be normalized.
A fallback rule is required.
Common Error: Ignoring Collision Policy
A system must define whether:
- touching counts as collision;
- shared boundaries count;
- initial overlap is allowed;
- small gaps within tolerance count as contact.
Different policies produce different valid predicates.
A Reliable Procedure for AABB Broad-Phase Testing
- Compute or update the AABB of each object.
- Compare the \(x\)-intervals.
- If they are disjoint, reject the pair.
- Compare the \(y\)-intervals.
- If they are disjoint, reject the pair.
- Otherwise, pass the pair to the narrow phase.
A Reliable Procedure for Circle-Circle Collision
- Compute the center displacement \(D=C_2-C_1\).
- Compute \(d^2=D\cdot D\).
- Compute \(R=r_1+r_2\).
- Compare \(d^2\) with \(R^2\).
- Classify separated, touching, or penetrating according to policy.
- If needed, compute contact normal and penetration depth.
A Reliable Procedure for Convex Polygon Collision
- Collect edge-normal axes from both polygons.
- Project both polygons onto the first axis.
- If the intervals are disjoint, return separated.
- Repeat for every candidate axis.
- If no separating axis exists, classify the polygons as overlapping or touching.
- Apply the chosen boundary policy for exact contact.
A Reliable Procedure for a General Collision Pipeline
- Choose appropriate bounding volumes.
- Use a spatial structure to reduce candidate pairs.
- Apply broad-phase overlap tests.
- Send surviving pairs to geometry-specific narrow-phase tests.
- Classify contact type.
- Compute contact location, normal, depth, or time of impact when required.
- Handle degeneracies and tolerances consistently.
- Verify against representative edge cases.
Practice 1: Pair Count
How many unordered object pairs are possible when
\[ n=10? \]Practice 2: Interval Overlap
Do the intervals
\[ [2,7] \]and
\[ [6,10] \]overlap?
Practice 3: AABB Rejection
Two AABBs overlap on the \(x\)-axis but are disjoint on the \(y\)-axis. Can the boxes collide?
Practice 4: Circle-Circle Test
Two circles have radii
\[ r_1=3, \qquad r_2=2 \]and their centers are \(4\) units apart. Do they overlap or touch?
Practice 5: Circle Separation
Two circles have radii \(2\) and \(1\), and their centers are \(5\) units apart. Are they separated?
Practice 6: Separating Axis
If the projections of two convex polygons are disjoint on one tested axis, what can you conclude?
Practice 7: Broad Phase
What is the purpose of the broad phase?
Practice 8: Tunneling
What collision-detection problem occurs when a fast object passes through a thin obstacle between discrete time samples?
Practice 9: Penetration Depth
Two circles have radii \(4\) and \(3\), and their centers are \(5\) units apart. What is their penetration depth?
Practice 10: Bounding-Volume Hierarchy
Why is a hierarchy useful when testing collisions between highly detailed mesh objects?
Practice Answers
Practice 1
\[ \frac{10(10-1)}{2} = \frac{90}{2} = \boxed{45}. \]Practice 2
The intervals share the range from \(6\) through \(7\), so
\[ \boxed{\text{yes}}. \]Practice 3
No. Separation on one axis is enough to prove the AABBs are disjoint.
\[ \boxed{\text{No collision}.} \]Practice 4
The radius sum is
\[ 3+2=5. \]Since
\[ 4<5, \]the circles
\[ \boxed{\text{overlap}}. \]Practice 5
The radius sum is
\[ 2+1=3. \]Since
\[ 5>3, \]the circles are
\[ \boxed{\text{separated}}. \]Practice 6
A separating axis has been found, so
\[ \boxed{\text{the convex polygons do not collide}.} \]Practice 7
The broad phase quickly eliminates object pairs that cannot collide so that expensive exact tests are applied only to plausible candidates.
Practice 8
The problem is called
\[ \boxed{\text{tunneling}}. \]Practice 9
\[ \delta= 4+3-5 = \boxed{2}. \]Practice 10
The hierarchy rejects large separated regions early, so only nearby subregions and primitive triangles require detailed collision tests.
What to Remember
Collision detection combines fast rejection with exact geometric testing.
- collision means the occupied regions have nonempty intersection;
- broad-phase tests reduce the number of candidate pairs;
- bounding volumes provide conservative rejection tests;
- AABB overlap reduces to interval overlap on each coordinate axis;
- circle collision uses center distance and radius sums;
- segment tests rely on orientation and boundary cases;
- the separating axis theorem provides a complete convex-polygon test;
- concave objects can be decomposed into convex pieces;
- spatial grids, trees, sweep methods, and hierarchies accelerate broad-phase testing;
- continuous collision detection prevents tunneling between sampled times;
- numerical tolerances and contact policy are part of the algorithm design.
The larger computational principle is that difficult spatial interactions become manageable when simple conservative tests eliminate impossible cases before more expensive exact geometry is applied.
Where We Go Next
Collision detection works with computational representations of geometry. The next lesson examines two of the most important ways geometric information itself is encoded.
Raster and Vector Representation compares grid-based and coordinate-based models of spatial information and explains how each representation supports different algorithms, resolutions, and geometric operations.