Draft article not currently submitted for review. This is a draft Articles for creation (AfC) submission. It is not currently pending review. While there are no deadlines, abandoned drafts may be deleted after six months. To edit or make changes to this draft, simply click on the "Edit" tab at the top of the window. To be accepted, a draft should: Show the subject qualifies for a Wikipedia article by using multiple sources that meet four criteria. The sources should be (1) reliable (2) secondary (3) independent of the subject (4) talk about the subject in some depth. For some topics, there are alternative criteria. Be written from a neutral point of view Respect copyright and do not plagiarize. Do not copy-paste. It is strongly discouraged to write about either yourself or your business or employer. If you do so, you must declare it. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Last edited by Vkazemi (talk | contribs) 3 months ago. (Update) Submit the draft for review!

The Expanding Polytope Algorithm (EPA) is a computational geometry algorithm used primarily in physics engines and computer graphics to determine the penetration depth and contact manifold of two intersecting convex shapes (polytopes). ^[1]

EPA is almost exclusively used in conjunction with the Gilbert-Johnson-Keerthi (GJK) algorithm. While GJK is highly efficient at determining boolean collision (whether two objects intersect), it cannot calculate the depth of the intersection once the objects overlap. EPA takes the geometric data generated by a terminating GJK algorithm and expands it to find the minimum translation vector (MTV) required to separate the objects.

To understand EPA, one must first understand the Minkowski difference, defined for two point sets ${\displaystyle A}$ and ${\displaystyle B}$ as:

${\displaystyle A\ominus B=\{{\vec {a}}-{\vec {b}}\mid {\vec {a}}\in A,{\vec {b}}\in B\}}$

Two shapes intersect if and only if their Minkowski difference contains the origin ${\displaystyle (0,0,0)}$.

The GJK algorithm searches for the origin within the Minkowski difference. If it finds the origin, it terminates and outputs a simplex (a triangle in 2D, or a tetrahedron in 3D) whose vertices lie on the boundary of the Minkowski difference and which wholly encloses the origin.

Once a collision is detected, physics engines need to push the objects apart to resolve the collision. The shortest distance to move them out of collision corresponds to the shortest distance from the origin to the boundary of the Minkowski difference. EPA's function is to "expand" the GJK simplex until it finds this closest boundary point.

The EPA algorithm operates iteratively, expanding the initial polytope outwards toward the boundary of the Minkowski difference.

1. Initialization: Begin with the simplex provided by the GJK algorithm (a tetrahedron in 3D) that contains the origin.
2. Find closest face: Calculate the perpendicular distance from the origin to each face of the current polytope. Identify the face closest to the origin.
3. Calculate support point: Use a support function to find the furthest point on the Minkowski difference in the direction of the closest face's normal vector, ${\displaystyle {\vec {n}}}$. $${\displaystyle P_{support}=Support_{A}({\vec {n}})-Support_{B}(-{\vec {n}})}$$
4. Termination check: Check the distance from the origin to the new support point. If this distance is equal to (or within a predefined tolerance of) the distance to the face, the algorithm terminates. The current face lies on the boundary of the Minkowski difference, and the penetration vector is the vector from the origin to this face.
5. Expansion: If the support point is further out, the polytope must be expanded. The closest face (and any adjacent faces visible from the support point) are removed, leaving a "hole" (or horizon) in the polytope.
6. Reconstruction: Create new triangular faces connecting the edges of the horizon to the new support point, thereby expanding the polytope.
7. Iteration: Return to Step 2.

In the worst-case scenario, EPA has a time complexity of ${\displaystyle O(n)}$, where ${\displaystyle n}$ is the number of vertices defining the Minkowski difference. However, because it is an iterative algorithm utilizing support functions, its practical performance depends heavily on the complexity of the intersecting shapes and the depth of penetration.

Limitations and challenges:

• Floating-point errors: Because EPA involves creating increasingly smaller and flatter triangles near the boundary of the Minkowski difference, it is highly susceptible to floating-point precision errors. Degenerate faces can cause infinite loops or crashes if not handled with robust numerical tolerance checks.
• Non-convex shapes: Like GJK, EPA strictly requires convex polytopes. Concave shapes must be decomposed into a hierarchy of convex sub-shapes (convex decomposition) before EPA can be applied.

EPA is a standard algorithm in real-time collision detection systems. It is implemented in nearly all major 3D physics engines, including:

• Bullet Physics: Widely used in films, games, and robotics simulations.
• Box2D: A ubiquitous 2D physics engine that uses a 2D equivalent called the Expanding Polygon Algorithm.
• Havok: An industry-standard game physics engine.

By providing the exact penetration vector and contact points, EPA allows physics engines to apply accurate impulse forces, preventing objects in video games or simulations from sinking into one another.