axiolid_collide/
lib.rs

1// SPDX-License-Identifier: MPL-2.0
2#![forbid(unsafe_code)]
3#![warn(missing_docs)]
4
5//! Convex collision queries via the separating axis theorem.
6//!
7//! # What this answers, and what it deliberately does not
8//!
9//! Two convex shapes are disjoint if and only if some axis exists on which
10//! their projections do not overlap. This crate finds such an axis, or proves
11//! none exists.
12//!
13//! When the shapes are apart it also reports **how far** apart, because that
14//! is the question a rule check asks: not "do these collide" but "is there
15//! enough clearance". The `axiolid-inspect` crate's mesh clearance answers
16//! the same
17//! question for triangle soups; this answers it for convex shapes without
18//! building an index.
19//!
20//! It does **not** report penetration depth. That is a deliberate refusal,
21//! consistent with `axiolid-measure`: a contact area and an interpenetration
22//! depth are different measurements, and collapsing them behind one number
23//! is how a caller ends up using the wrong one. Callers needing penetration
24//! depth for physics want EPA, which belongs in a physics engine rather than
25//! a certified geometry kernel.
26//!
27//! # Why SAT rather than GJK
28//!
29//! For the shapes a model-checking rule actually has -- boxes, extruded
30//! profiles, hulls with tens of vertices -- SAT is direct, has no iteration
31//! count to tune, and its failure mode is a clean answer rather than a
32//! tolerance-dependent one. GJK wins on high vertex counts and on a generic
33//! support function; neither is the common case here, and published
34//! commercial model-checking geometry APIs ship convex hull and SAT-style
35//! tests without GJK/EPA at all.
36//!
37//! # Robustness
38//!
39//! Projections are compared with an explicit tolerance rather than exactly.
40//! An axis derived from a cross product of two nearly parallel edges is
41//! numerically meaningless, so such axes are skipped instead of being
42//! allowed to report a spurious separation of ~1e-17.
43
44use axiolid_core::{Box3, Point3, Scalar, Vec3};
45
46mod sat;
47mod shape;
48
49pub use sat::{separation, Contact, SeparationResult};
50pub use shape::ConvexShape;
51
52/// Shortest distance between two convex shapes, or zero if they overlap.
53///
54/// Convenience over [`separation`] for callers that only need the number.
55#[must_use]
56pub fn distance(a: &ConvexShape, b: &ConvexShape, tolerance: Scalar) -> Scalar {
57    match separation(a, b, tolerance) {
58        SeparationResult::Apart { distance, .. } => distance,
59        SeparationResult::Overlapping => 0.0,
60    }
61}
62
63/// Whether two convex shapes share any point.
64#[must_use]
65pub fn intersects(a: &ConvexShape, b: &ConvexShape, tolerance: Scalar) -> bool {
66    matches!(separation(a, b, tolerance), SeparationResult::Overlapping)
67}
68
69/// Whether two oriented boxes overlap.
70///
71/// The case `Box3` could not answer before: it carried an orientation but had
72/// no intersection test, so a caller had to fall back to an axis-aligned
73/// bound and lose the tightness the orientation was for.
74#[must_use]
75pub fn boxes_intersect(a: &Box3, b: &Box3, tolerance: Scalar) -> bool {
76    intersects(
77        &ConvexShape::from_points(&a.corners()),
78        &ConvexShape::from_points(&b.corners()),
79        tolerance,
80    )
81}
82
83/// Whether a point lies inside or on a convex shape.
84#[must_use]
85pub fn contains_point(shape: &ConvexShape, point: Point3, tolerance: Scalar) -> bool {
86    intersects(shape, &ConvexShape::from_points(&[point]), tolerance)
87}
88
89/// Axis-aligned extent of a shape along a direction.
90pub(crate) fn project(points: &[Point3], axis: Vec3) -> (Scalar, Scalar) {
91    let mut min = Scalar::INFINITY;
92    let mut max = Scalar::NEG_INFINITY;
93    for point in points {
94        let value = point.dot(axis);
95        min = min.min(value);
96        max = max.max(value);
97    }
98    (min, max)
99}
axiolid_collide/lib.rs

axiolid_collide/
lib.rs
