The Gilbert-Johnson-Keerthi (GJK) Algorithm

Talk outline

What is the GJK algorithm
Terminology
“Simplified” version of the algorithm
One object

GJK solves proximity queries

Given two convex polyhedra
Computes distance d
Can also return

GJK solves proximity queries

Generalized for arbitrary convex objects
As long as they

Terminology 1(3)

Supporting (or extreme) point

for direction

returned by support mapping function

Terminology 2(3)

0-simplex

1-simplex

2-simplex

3-simplex

simplex

Terminology 3(3)

Point set C

Convex hull, CH(C)

The GJK algorithm

Initialize the simplex set Q with up to d+1

GJK example 1(10)

INPUT: Convex polyhedron C given as the convex hull

Initialize the simplex set Q with up to d+1 points from

GJK example 3(10)

Compute point P of minimum norm in CH(Q)

GJK example 4(10)

If P is the origin, exit; return 0
Reduce Q

GJK example 5(10)

Let V=SC(–P) be a supporting point in direction –P

GJK example 6(10)

If V no more extreme in direction –P than

GJK example 7(10)

Compute point P of minimum norm in CH(Q)

GJK example 8(10)

If P is the origin, exit; return 0
Reduce Q

GJK example 9(10)

Let V=SC(–P) be a supporting point in direction –P

GJK example 10(10)

DONE!

If V no more extreme in direction –P than

Distance subalgorithm 1(2)

Approach #1: Solve algebraically
Used in original GJK paper
Johnson’s distance

Distance subalgorithm 2(2)

Approach #2: Solve geometrically
Mathematically equivalent
But more intuitive
Therefore easier to

Closest point on triangle

ClosestPointOnTriangleToPoint()
Finds point on triangle closest to a given

Closest point on triangle

Separate cases based on which feature Voronoi region

Closest point on triangle

Closest point on triangle

GJK for two objects

What about two polyhedra, A and B?
Reduce problem

Minkowski sum & difference

Minkowski sum
The sweeping of one convex object with

Minkowski sum & difference

Minkowski difference, defined as:
Can write distance between two

The generalization

A and B intersecting iff A–B contains the origin!
Distance between

GJK for moving objects

Transform the problem…

…into moving vs stationary

Alt #1: Point duplication

Let object A additionally include the points

…effectively forming

Alt #2: Support mapping

Modify support mapping to consider only points

when

Alt #2: Support mapping

…and to consider only points

when

GJK for moving objects

Presented solution
Gives only Boolean interference detection result
Interval halving