Overview
The Expanding Polytope Algorithm grows the final GJK simplex outward until it approximates the closest boundary to the origin.
SpecializedSource checked
Expanding Polytope Algorithm
Computes penetration depth and contact normal after GJK detects convex overlap.
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
- 4
- Code example
- Ready
- Visualization
- Ready
- Aliases
- EPA
Core Concepts
minkowski polytopeclosest facepenetration depthcontact normal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(iterations)
Average
O(iterations)
Worst
O(iterations)
Space
O(polytope size)
When to Use
- Use when physics simulation needs minkowski polytope.
- 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
- Computes penetration depth and contact normal after GJK detects convex overlap
- Uses minkowski polytope and closest face 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)
Closest face distance
distance = dot(facenormal, facevertex)
distance = dot(face_normal, face_vertex)Chooses the polytope face closest to the origin for expansion.
Pseudocode
- 1.Prepare the inputs and state needed for Expanding Polytope Algorithm.
- 2.Apply the minkowski polytope step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return updated state.
Canonical Example
- Input
- Expanding Polytope Algorithm input with a small representative case
- Output
- Updated state
- Explanation
- Expanding Polytope Algorithm applies minkowski polytope to produce updated state.
Implementation Notes
- Use deterministic update ordering when reproducibility matters.
- Keep the minkowski polytope 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 Expanding Polytope Algorithm 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 Expanding Polytope Algorithm.
simulation-mechanismNotes
Expanding Polytope Algorithm operates in O(iterations) time and O(polytope size) space within the Narrow Phase Collision Detection family. Key governing relation: distance = dot(face_normal, face_vertex). Often compared with GJK Collision Detection and Separating Axis Theorem.
Sources (1)
What each reference supports for this entry.
Real-Time Collision Detection
BookCollision-detection reference supporting Expanding Polytope Algorithm geometric queries, contact generation, bounding volumes, or robustness concerns.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withGJK Collision Detection
EPA commonly follows GJK to compute penetration information.
Depends onMinkowski Sum
EPA expands a polytope in Minkowski-difference space.
Tags
SimulationCollision DetectionNarrow PhaseComputational Geometry