Intersection Detection

Intersection Detection
References

Notes based on
Tomas Moller and Eric Haines, Real-Time Rendering, A K Peters,
2nd edition, 2002. Chapter 9.
Franco Preparata and Michael Shamos, Computational Geometry:
An Introduction, Springer Verlag, 1990. Chapter 2.

Intersection Detection
Introduction

Intersection detection is the problem of detecting whether two

objects intersect — overlap in space. Intersection detection is
carried out by performing intersection tests.

Intersection detection is a problem which occurs in computer

graphics in many forms, including: clipping, view-volume culling,
ray-tracing, picking and collision detection.
Intersection detection lies at the heart of collision detection.
Collision detection is intersection detection amongst a set of
moving objects.

Intersection Detection
Three Possibilities

There are three spatial relationships between two objects:

◮ no intersection, (disjoint, exclusion),
◮ partial intersection (overlap) and
◮ containment (inclusion).

It is important to keep all these possibilities in mind when

performing intersection detection.

Intersection Detection
Bounding Volumes

The classic computer graphics technique of bounding volumes is

applied in intersection detection.

Instead of performing expensive intersection tests amongst

complex objects (relatively) simpler tests using bounding volumes
can be performed.
These tests allow quick (“trivially”) determination of exclusion and
inclusion cases, where no further work needs be done, and
potential overlap cases where further work does need to be done in
order to get a correct answer.

Intersection Detection
Types of Bounding Volumes
Common bounding volumes (BVs) are:
1. Axis-aligned bounding boxes (AABBs).
2. Oriented bounding boxes (OBBs).
3. Discrete oriented polytopes (k-DOPs).
4. Spheres.
There is an obvious trade-off: tightness of fit versus complexity
and cost of test.

One quantitive measure used in relation to BVs is void volume: the

difference between the bounding volume and the object volume.
Intersection Detection
Convex Hulls

The tightest fitting bounding volume is the convex hull, although

it is only strictly defined for polygonal objects or sets of points.

Intersection Detection
Axis-Aligned Bounding Boxes (AABBs)

An axis-aligned bounding box (also called an extent or a

rectangular box).

An axis-aligned bounding box is defined by two extreme points.

For example an AABB called A is defined by amin and amax , where
aimin ≤ aimax , ∀i ∈ x, y , z .

Intersection Detection
Oriented Bounding Boxes (OBBs)
An oriented bounding box is a box which may be arbitrarily
oriented (rotated). It is still a box; its faces have normals which
are pairwise orthogonal.

An OBB B can be described by the center point of the box bc ,

and three normalised positively oriented vectors which describe the
side directions of the box.
The vectors are bu , bv and bw and their half lengths are huB , hvB
and hwB.

Intersection Detection
Discrete Oriented Polytopes (k-DOPs)
A k-DOP is the intersection of a set of pairs of parallel planes,
where each pair of parallel planes is called a slab.

A k-DOP is defined by k/2 (k even) normalised normals, ni ,

1 ≤ i ≤ k/2 each with two associated scalar values dimin and dimax
where dimin < dimax .
Each triple (ni , dim in, dim ax) defines a slab Si which is the volume
betwen two planes πimin : ni .(x) + dimin = 0 and
πimax : ni .(x) + dimax = 0.
The k-DOP volume is then the intersection of all slabs ∩1≤l≤k/2 Sl .
Intersection Detection
Hierarchical Bounding Volumes

Bounding volumes can be placed inside other bounding volumes,

recursively, thereby building bounding volume hierarchies.

Bounding volume hierarchies are one approach to improving

collision detection performance amongst many objects or between
complex objects.
Bounding volume hierarchies may reduce collision detection from
an O(n2 ) algorithm to O(nlg (n)) or even O(n).

Intersection Detection
Intersection Detection Principles or “Rules of Thumb”

◮ Perform calculations which allow trivial acceptance or trivial

rejection.
◮ If possible, use results from above tests, even if they fail.
◮ Try re-ordering rejection and acceptance tests for better
performance.
◮ Postpone expensive calculations.
◮ Consider reducing dimensionality of problem.
◮ If many objects are being tested against one object,
pre-calculate values if possible.
◮ Perform timing tests and profiling to investigate performance.
◮ Make code robust (80% of work!).

Intersection Detection
Point-Point Intersection Testing

Two points p1 (x1 , y1 , z1 ) and p2 (x2 , y2 , z2 ) intersect if they are

coincident:
x1 = x2 , y1 = y2 , z 1 = z 2

Intersection Detection
Interval-Interval Intersection Testing

Two intervals [amin , amax ] and [b min , b max ] are disjoint (do not
intersect) if either amin > b max or b min > amax .

interval intersect(A, B)
returns (OVERLAP,DISJOINT)
1: if (amin > b max or b min > amax )
2: return (DISJOINT);
3 else
4: return (OVERLAP);

Figure: Interval Intersection Test

Intersection Detection
AABB-AABB Intersection Testing

Two axis-aligned bounding boxes (AABBs) intersect if they overlap

in x or y or z. The AABB intersection test is essentially three
interval intersection tests, with short-circuiting.

AABB intersect(A, B)
returns (OVERLAP,DISJOINT)
1: for each i ∈ x, y , z
2: if (aimin > bimax or bimin > aimax )
3: return (DISJOINT);
5: else
4: return (OVERLAP);

Figure: AABB Intersection Test

Intersection Detection
Sphere-Sphere Intersection Testing
Two spheres intersect if the distance between their centres c1 and
c2 is less than the sum of their radii r1 + r2 .

sphere intersect(A, B)
returns (OVERLAP,DISJOINT)
1: l = c2 − c1
2: d 2 = l.l
3: if (d 2 < (r1 + r2 )2 )
4: return (OVERLAP);
5: else
6: return (DISJOINT);

Figure: Sphere-Sphere Intersection Test

Using distance squared rather than distance avoids a square root

calculation. Square roots used to be very expensive c.f. other
operations, and are still somewhat expensive c.f. other operations.
Intersection Detection
Sphere-AABB Intersection Testing
The sphere-AABB test also uses a distance test. The distance
(squared) from the sphere centre to the box is accumlated in each
dimension, then a distance test is applied.
sphere AABB intersect(c,r ,A)
returns (OVERLAP,DISJOINT)
1: d 2 = 0
2: for each i ∈ x, y , z
3: if (ci < aimin )
4: d 2 = d 2 + (ci − aimin )2
5: else if (ci > aimax )
6: d 2 = d 2 + (ci − aimax )2
7: if (d 2 < r 2 )
8: return (OVERLAP)
9: else
10: return (DISJOINT)

Figure: Sphere-AABB Intersection Test

Intersection Detection
Rays

Rays are directed lines. They may be finite, semi-infinite or infinite.

r(t)=o+td

d
o

Rays are an important geometric object (“shape”) used in

intersection detection, (and, of course, ray tracing!). Rays are
useful in intersection detection because:
1. They are sometimes good models of paths taken by moving
objects, e.g., high speed bullets over short distances.
2. They can be used as a computationally efficient (“cheap”)
way to perform approximate intersection detection

Intersection Detection
Representing Rays

A ray is represented parametrically using a combination of a point

(origin) o and a vector (direction) d.

r = o + td

If (xo , yo , zo ) is the ray origin and (u, v , w ) is the ray direction

then a point on the ray is given by

x = xo + tu
y = yo + tv
z = zo + tw

Intersection Detection
A ray may also be specified by giving two points p1 and p2 in
which case the equations become:

x = x1 + t(x2 − x1 )
y = y1 + t(y2 − y1 )
z = z1 + t(z2 − z1 )

It is often advantageous to normalise the ray direction. This saves

repeatedly taking the magnitude (involving a sqrt operation) in
dot products where vector projections are being calculated.

Intersection Detection
Ray-Sphere Intersection Testing
A sphere may be represented by the equation

(x − a)2 + (y − b)2 + (z − c)2 = r 2

The ray-sphere intersection is found by substituting the equations
for the x, y and z coordinates of the ray into the sphere equation

(xo + tu − a)2 + (yo + tv − b)2 + (zo + tw − c)2 = r 2

Rearrangement then gives

(u 2 + v 2 + w 2 )t 2 +
2(u(xo − a) + v (yo − b) + w (zo − c))t +
(xo − a)2 + (yo − b)2 + (zo − c)2 − r 2 = 0

i.e. a quadratic in t. If the quadratic has real roots then the ray
intersects the sphere, otherwise it does not.
Intersection Detection
So we have

A = (u 2 + v 2 + w 2 )t 2
B = 2(u(x0 − a) + v (y0 − b) + w (z0 − c))t
C = (x0 − a)2 + (y0 − b)2 + (z0 − c)2 − r 2

Solving for t we get

√
−B ± B 2 − 4AC
t=
2A
where the smallest positive root is the first intersection.

t2
t 1= t 2

t1
d d
d

o o o

Intersection Detection
Minor Optimisation

A small optimisation can be achieved by noting that a factor of

two cancels, giving

B = u(x0 − a) + v (y0 − b) + w (z0 − c)t

and √
−B ± B 2 − AC
t=
A
These kinds of optimisations tend to be of decreasing value with
increasing floating point performance. They are also potential
source for introducting bugs and creating obscurity.

Intersection Detection
Optimised Solution
Haines optimised version of the ray-sphere intersection detection
algorithm allows earlier short-circuiting.
ray sphere intersect(o,d,c,r)
returns (REJECT,INTERSECT,t,p)
1: l=c - o
2: d = l.d
3: l 2 = l.l
4: if (d < 0 and l 2 > r 2 ) return (REJECT,0,O);
5: m2 = l 2 − d 2
2 2
6: if (m√ > r ) return (REJECT,0,O);
7: q = r − m2 2

8: if (l 2 > r 2 ) t = d − q else t = d + q
9: return (INTERSECT,t,o + td);

Figure: Optimised Algorithm

Intersection Detection
Ray-Polygon Intersection Detection
To find the intersection point between a ray and a polygon:
1. Find the intersection point of the ray and the plane containing
the polygon. If it does not exist then finished.
2. Determine if the ray-plane intersection point is inside the
polgon, i.e., perform a point-polygon intersection
(containment) test.

Intersection Detection
Ray-Polygon Intersection Point
The equation of a plane is

Ax + By + Cz + D = 0

The equation of a ray is

x = xo + tu
y = yo + tv
z = zo + tw

Substituting into the plane equation we get

A(xo + tu) + B(yo + tv ) + C (zo + tw ) + D = 0

Rearrangement gives
(Axo + Byo + Czo + D)
t=−
Au + Bv + Cw
Intersection Detection
Polygon Containment Test
The polygon containment test is performed by projecting the
polygon and the intersection point onto one of the coordinate
planes along one of the three principal axis directions and then
performing a 2D point in polygon test.
Which axis do we project along?

Intersection Detection
Point in Polygon: Crossings Test
One O(n) approach is to count the number of crossings or
intersections between a semi-infinite line or ray and edges of the
polygon.
P

Count the number of intersections of P with R. If the number of

intersections (crossings) of is odd then z is inside, otherwise it is
outside. This is a result of the Jordon curve thereom.
Special cases, e.g., vertices on the ray, need to be handled.
How can this be done?
Intersection Detection
Convex Polygons
In the case of a convex polygon an O(lg (n)) point-in-polygon (or
containment) algorithm is possible.

p3

p4 C
p2

p5
p1

The point q can be any internal point, e.g., the centroid of the
triangle determined by any three vertices of P.
Using polar coordinates, a binary search can be performed to find
the wedge which contains z. Then z can be compared against the
wedge edge.
How much preprocessing is required?
Intersection Detection
Concave Polygons

Can point containment for concave polygons be performed in

O(lg (n)) time?
If so, how much preprocessing is required?

Intersection Detection
Brute Force Collision Detection
A brute force approach to collision detection uses intersection tests
of all object pairs — or pairwise testing — at discrete points in
time where all objects are assumed to be stationary
1: for i = 1 to n − 1
2: for j = i to n
3: intersect(object(i), object(j))

Figure: Brute-force collision detection

There are n(n−1)

2 pairs amonst n objects, and this is the number of
object-object intersection tests the brute-force algorithm performs
at each point in time.
Using the big O notation, the brute-force algorithm uses O(n2 )
object-object intersection tests. If each intersection test can be
performed in O(1) time, i.e., constant time, then the algorithm is
O(n2 ) time.
Intersection Detection