Struct EPA

pub struct EPA { /* private fields */ }

The Expanding Polytope Algorithm in 3D.

This structure computes the penetration depth between two shapes when they are overlapping. It’s used after GJK (Gilbert-Johnson-Keerthi) determines that two shapes are penetrating.

What does EPA do?

EPA finds:

• The penetration depth: How far the shapes are overlapping
• The contact normal: The direction to separate the shapes
• The contact points: Where the shapes are touching on each surface

How it works in 3D

In 3D, EPA maintains a convex polyhedron (made of triangular faces) in the Minkowski difference space (CSO - Configuration Space Obstacle) that encloses the origin. It iteratively:

1. Finds the triangular face closest to the origin
2. Expands the polyhedron by adding a new support point in the direction of that face’s normal
3. Removes faces that can be “seen” from the new point (they’re now inside)
4. Creates new faces connecting the boundary edges (silhouette) to the new point
5. Repeats until the polyhedron cannot expand further (convergence)

The final closest face provides the penetration depth (distance to origin) and contact normal.

Example

use parry3d::query::epa::EPA;
use parry3d::query::gjk::VoronoiSimplex;
use parry3d::shape::Ball;
use parry3d::na::Isometry3;

let ball1 = Ball::new(1.0);
let ball2 = Ball::new(1.0);
let pos12 = Isometry3::translation(1.5, 0.0, 0.0); // Overlapping spheres

// After GJK determines penetration and fills a simplex:
let mut epa = EPA::new();
let simplex = VoronoiSimplex::new(); // Would be filled by GJK

// EPA computes the contact details
// if let Some((pt1, pt2, normal)) = epa.closest_points(&pos12, &ball1, &ball2, &simplex) {
//     println!("Penetration depth: {}", (pt2 - pt1).norm());
//     println!("Contact normal: {}", normal);
// }

Reusability

The EPA structure can be reused across multiple queries to avoid allocations. Internal buffers are cleared and reused in each call to closest_points.

Convergence and Failure Cases

EPA may return None in these situations:

• The shapes are not actually penetrating (GJK should be used instead)
• Degenerate or nearly-degenerate geometry causes numerical instability
• The initial simplex from GJK is invalid
• The algorithm fails to converge after 100 iterations
• Silhouette extraction fails (topology issues)

When None is returned, the shapes may be touching at a single point, edge, or face, or there may be numerical precision issues with the input geometry.

Complexity

The 3D EPA implementation is more complex than 2D because:

• It maintains a 3D mesh topology with face adjacency information
• It needs to compute silhouettes (visible edges from a point)
• It handles more degenerate cases (coplanar faces, edge cases)

Implementations

impl EPA

pub fn new() -> Self

Creates a new instance of the 3D Expanding Polytope Algorithm.

This allocates internal data structures (vertices, faces, silhouette buffer, and a priority heap). The same EPA instance can be reused for multiple queries to avoid repeated allocations.

Example

use parry3d::query::epa::EPA;

let mut epa = EPA::new();
// Use epa for multiple queries...

pub fn project_origin<G: ?Sized + SupportMap>( &mut self, m: &Isometry<f32>, g: &G, simplex: &VoronoiSimplex, ) -> Option<Point<f32>>

Projects the origin onto the boundary of the given shape.

This is a specialized version of closest_points for projecting a point (the origin) onto a single shape’s surface.

Parameters

• m: The position and orientation of the shape in world space
• g: The shape to project onto (must implement SupportMap)
• simplex: A Voronoi simplex from GJK that encloses the origin (indicating the origin is inside the shape)

Returns

• Some(point): The closest point on the shape’s boundary to the origin, in the local space of g
• None: If the origin is not inside the shape, or if EPA failed to converge

Prerequisites

The origin must be inside the shape. If it’s outside, use GJK instead. Typically, you would:

1. Run GJK to detect if a point is inside a shape
2. If inside, use this method to find the closest boundary point

Example

use parry3d::query::epa::EPA;
use parry3d::query::gjk::VoronoiSimplex;
use parry3d::shape::Ball;
use parry3d::na::Isometry3;

let ball = Ball::new(2.0);
let pos = Isometry3::<f32>::identity();

// Assume GJK determined the origin is inside and filled simplex
let simplex = VoronoiSimplex::new();
let mut epa = EPA::new();

// Find the closest point on the ball's surface to the origin
// if let Some(surface_point) = epa.project_origin(&pos, &ball, &simplex) {
//     println!("Closest surface point: {:?}", surface_point);
// }

pub fn closest_points<G1, G2>( &mut self, pos12: &Isometry<f32>, g1: &G1, g2: &G2, simplex: &VoronoiSimplex, ) -> Option<(Point<f32>, Point<f32>, Unit<Vector<f32>>)>

where G1: ?Sized + SupportMap, G2: ?Sized + SupportMap,

Computes the closest points between two penetrating shapes and their contact normal.

This is the main EPA method that computes detailed contact information for overlapping shapes. It should be called after GJK determines that two shapes are penetrating.

Parameters

• pos12: The relative position/orientation from g2’s frame to g1’s frame (typically computed as pos1.inverse() * pos2)
• g1: The first shape (must implement SupportMap)
• g2: The second shape (must implement SupportMap)
• simplex: A Voronoi simplex from GJK that encloses the origin, indicating penetration

Returns

Returns Some((point1, point2, normal)) where:

• point1: Contact point on shape g1 in g1’s local frame
• point2: Contact point on shape g2 in g2’s local frame
• normal: Contact normal pointing from g2 toward g1, normalized

The penetration depth can be computed as (point1 - point2).norm() after transforming both points to the same coordinate frame.

Returns None if:

• The shapes are not actually penetrating
• EPA fails to converge (degenerate geometry, numerical issues)
• The simplex is invalid or empty
• The algorithm reaches the maximum iteration limit (100 iterations)
• Silhouette extraction fails (indicates topology corruption)

Prerequisites

The shapes must be penetrating. The typical workflow is:

1. Run GJK to check if shapes intersect
2. If GJK detects penetration and returns a simplex enclosing the origin
3. Use EPA with that simplex to compute detailed contact information

Example

use parry3d::query::epa::EPA;
use parry3d::query::gjk::{GJKResult, VoronoiSimplex};
use parry3d::shape::Ball;
use parry3d::na::Isometry3;

let ball1 = Ball::new(1.0);
let ball2 = Ball::new(1.0);

let pos1 = Isometry3::identity();
let pos2 = Isometry3::translation(1.5, 0.0, 0.0); // Overlapping
let pos12 = pos1.inverse() * pos2;

// After GJK detects penetration:
let mut simplex = VoronoiSimplex::new();
// ... simplex would be filled by GJK ...

let mut epa = EPA::new();
// if let Some((pt1, pt2, normal)) = epa.closest_points(&pos12, &ball1, &ball2, &simplex) {
//     println!("Contact on shape 1: {:?}", pt1);
//     println!("Contact on shape 2: {:?}", pt2);
//     println!("Contact normal: {}", normal);
//     println!("Penetration depth: ~0.5");
// }

Technical Details

The algorithm works in the Minkowski difference space (also called the Configuration Space Obstacle or CSO), where the difference between support points of the two shapes forms a new shape. When shapes penetrate, this CSO contains the origin.

EPA iteratively expands a convex polyhedron (in 3D) that surrounds the origin. At each iteration:

1. It finds the triangular face closest to the origin
2. Computes a support point in that face’s normal direction
3. Determines which existing faces are visible from the new point (the silhouette)
4. Removes visible faces and creates new ones connecting the silhouette boundary to the new point

This process maintains a valid convex hull that progressively tightens around the origin until convergence, at which point the closest face defines the penetration depth and contact normal.

Trait Implementations

impl Default for EPA

fn default() -> EPA

Returns the “default value” for a type.