Module sat

Application of the Separating Axis Theorem (SAT) for collision detection.

What is the Separating Axis Theorem?

The Separating Axis Theorem (SAT) is a fundamental geometric principle used in collision detection. It states that two convex shapes do not intersect if and only if there exists an axis (a line) onto which the projections of the two shapes do not overlap.

In simpler terms: if you can find a direction where, when you “shine a light” from that direction and look at the shadows cast by both shapes, those shadows don’t overlap, then the shapes are not colliding.

How Does SAT Work?

SAT works by testing a finite set of candidate axes to find a separating axis:

1. Select candidate axes: For polygons/polyhedra, these are typically:

   • Face normals (perpendicular to each face)
   • Edge cross products (perpendicular to pairs of edges from each shape, in 3D)

2. Project both shapes onto each axis: Find the extent (min and max) of each shape along the axis by computing support points (the furthest points in that direction).

3. Check for overlap: If the projections don’t overlap on any axis, the shapes don’t collide. If all axes show overlap, the shapes are intersecting.

4. Find minimum separation: The axis with the smallest overlap (or largest separation) is the “best” separating axis, useful for computing penetration depth and contact normals.

When is SAT Used?

SAT is particularly effective for:

• Convex polygonal shapes: Cuboids (boxes), triangles, convex polygons/polyhedra
• Accurate contact information: SAT can provide exact penetration depth and contact normals
• Shallow penetrations: Works best when shapes are just touching or slightly overlapping
• Edge-edge contacts: In 3D, SAT naturally handles edge-edge collisions between polyhedra

Parry uses SAT alongside other algorithms:

• GJK: For general convex shapes (faster for distance queries, but less accurate for contacts)
• EPA: For penetration depth when GJK detects overlap (but SAT is often more accurate)
• Specialized algorithms: For specific shape pairs (sphere-sphere, etc.)

Example: Cuboid-Cuboid Collision

use parry3d::shape::Cuboid;
use parry3d::query::sat::*;
use parry3d::na::{Isometry3, Vector3};

// Create two boxes
let box1 = Cuboid::new(Vector3::new(1.0, 1.0, 1.0));
let box2 = Cuboid::new(Vector3::new(0.5, 0.5, 0.5));

// Position them close together
let pos12 = Isometry3::translation(1.5, 0.0, 0.0);

// Test face normals from box1
let (separation, _normal) = cuboid_cuboid_find_local_separating_normal_oneway(
    &box1, &box2, &pos12
);

if separation > 0.0 {
    println!("Boxes are separated by {}", separation);
} else {
    println!("Boxes are overlapping by {}", -separation);
}

Module Organization

This module provides SAT implementations for common shape pairs:

• Cuboid-Cuboid: Box vs box collision (2D and 3D)
• Cuboid-Triangle: Box vs triangle (2D and 3D)
• Cuboid-Segment: Box vs line segment (2D and 3D)
• Cuboid-SupportMap: Box vs any convex shape
• Triangle-Segment: Triangle vs line segment (3D only)
• SupportMap-SupportMap: Generic convex shape vs convex shape

Each module provides functions to:

• Find the best separating normal (testing face normals)
• Find the best separating edge (testing edge cross products, 3D only)
• Compute separation distance along a given axis

Functions

cuboid_cuboid_find_local_separating_normal_oneway

Finds the best separating axis by testing the face normals of the first cuboid.

cuboid_support_map_find_local_separating_normal_oneway

Finds the best separating axis by testing the face normals of a cuboid against a support map shape.

point_cuboid_find_local_separating_normal_oneway

Computes the separation distance between a point and a cuboid along a specified normal direction.

segment_cuboid_find_local_separating_normal_oneway

Finds the best separating axis by testing a segment’s normal against a cuboid (2D only).

support_map_support_map_compute_separation

Computes the separation distance between two convex shapes along a given direction.

triangle_cuboid_find_local_separating_normal_oneway

Finds the best separating axis by testing a triangle’s normals against a cuboid (2D only).

triangle_support_map_find_local_separating_normal_oneway

Finds the best separating axis by testing the edge normals of a triangle against a support map shape (2D only).