Overview
GJK iteratively builds a simplex toward the origin in Minkowski-difference space to decide whether two convex shapes intersect.
SpecializedSource checked
GJK Collision Detection
Tests convex shapes for intersection using support points of their Minkowski difference.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Simulation
- Difficulty
- Advanced
- Family
- Narrow Phase Collision Detection
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 7
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Gilbert-Johnson-Keerthi
Core Concepts
support mappingminkowski differencesimplexorigin containment
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(iterations)
Average
O(iterations)
Worst
O(iterations)
Space
O(1)
When to Use
- Use when physics simulation needs support mapping.
- Use when the input matches the assumptions behind narrow Phase Collision Detection.
When Not to Use
- Avoid when the time step, forces, or constraints make the system unstable for the chosen method.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Tests convex shapes for intersection using support points of their Minkowski difference
- Uses support mapping and minkowski difference to guide the work.
- Produces updated state.
Use Cases
- Physics simulation
- Animation
- Interactive systems
Inputs
- Current state
- Forces or constraints
- Time step
Outputs
- Updated state
- Constraint corrections
- Collision results
Key Formulas (1)
Support difference
support(A − B, d) = support(A, d) − support(B, −d)
support(A - B, d) = support(A, d) - support(B, -d)Finds an extreme point in the Minkowski difference along a direction.
Pseudocode
- 1.Prepare the inputs and state needed for GJK Collision Detection.
- 2.Apply the support mapping step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return updated state.
Canonical Example
- Input
- GJK Collision Detection input with a small representative case
- Output
- Updated state
- Explanation
- GJK Collision Detection applies support mapping to produce updated state.
Implementation Notes
- Use deterministic update ordering when reproducibility matters.
- Keep the support mapping step separate enough to test independently.
Common Pitfalls
- Changing the time step without retuning stiffness or damping can destabilize the simulation.
- Forgetting to check edge cases can make GJK Collision Detection look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow state updates, constraints, and error correction over simulation steps.
Step 1 of 4: Prepare the inputs and state needed for GJK Collision Detection.
simulation-mechanismNotes
GJK Collision Detection operates in O(iterations) time and O(1) space within the Narrow Phase Collision Detection family. Key governing relation: support(A - B, d) = support(A, d) - support(B, -d). Often compared with Separating Axis Theorem and Expanding Polytope Algorithm.
Sources (1)
What each reference supports for this entry.
Van den Bergen 1999
PaperReference implementation paper for robust GJK collision detection on convex objects.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byNarrow Phase Collision Detection
Simulation · Core
GJK is commonly used for precise convex narrow-phase collision tests.
Compare with thisOften paired withExpanding Polytope Algorithm
Simulation · Specialized
EPA can compute penetration depth after GJK detects overlap.
Compare with thisRelationships
View full relationship pageOften paired withExpanding Polytope Algorithm
EPA can compute penetration depth after GJK detects overlap.
Depends onMinkowski Sum
GJK relies on support points of the Minkowski difference.
GJK is commonly used for precise convex narrow-phase collision tests.
Related Algorithms
Tags
SimulationCollision DetectionNarrow PhaseComputational Geometry