axiolid_collide/
shape.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! The convex shape a query runs against.
4
5use axiolid_core::{Point3, Vec3};
6
7/// A convex shape as its vertices and face normals.
8///
9/// Storing normals alongside points is what keeps SAT honest: the candidate
10/// axes for two polyhedra are their face normals plus the cross products of
11/// their edge pairs. Deriving normals from a point cloud every call would
12/// repeat work the caller usually already has.
13///
14/// A shape with no normals still works -- a point cloud's hull is implied by
15/// the edge-pair axes -- but supplying them makes the test exact for
16/// polyhedra rather than conservative.
17#[derive(Debug, Clone, PartialEq)]
18pub struct ConvexShape {
19    pub(crate) points: Vec<Point3>,
20    pub(crate) normals: Vec<Vec3>,
21    pub(crate) edges: Vec<Vec3>,
22}
23
24impl ConvexShape {
25    /// A shape from its vertices alone.
26    ///
27    /// Face normals are not inferred: computing a hull here would make a
28    /// cheap constructor expensive and would silently discard the caller's
29    /// own topology. Use [`ConvexShape::with_faces`] when face normals are
30    /// available.
31    #[must_use]
32    pub fn from_points(points: &[Point3]) -> Self {
33        let edges = derive_edges(points);
34        Self {
35            points: points.to_vec(),
36            normals: Vec::new(),
37            edges,
38        }
39    }
40
41    /// A shape with known face normals and edge directions.
42    #[must_use]
43    pub fn with_faces(points: &[Point3], normals: &[Vec3]) -> Self {
44        let edges = derive_edges(points);
45        Self {
46            points: points.to_vec(),
47            normals: normals.to_vec(),
48            edges,
49        }
50    }
51
52    /// An axis-aligned box as a convex shape.
53    #[must_use]
54    pub fn from_aabb(min: Point3, max: Point3) -> Self {
55        let corners = [
56            Point3::new(min.x, min.y, min.z),
57            Point3::new(max.x, min.y, min.z),
58            Point3::new(max.x, max.y, min.z),
59            Point3::new(min.x, max.y, min.z),
60            Point3::new(min.x, min.y, max.z),
61            Point3::new(max.x, min.y, max.z),
62            Point3::new(max.x, max.y, max.z),
63            Point3::new(min.x, max.y, max.z),
64        ];
65        Self::with_faces(
66            &corners,
67            &[
68                Vec3::new(1.0, 0.0, 0.0),
69                Vec3::new(0.0, 1.0, 0.0),
70                Vec3::new(0.0, 0.0, 1.0),
71            ],
72        )
73    }
74
75    /// The shape's vertices.
76    #[must_use]
77    pub fn points(&self) -> &[Point3] {
78        &self.points
79    }
80
81    /// Whether the shape has no vertices.
82    #[must_use]
83    pub fn is_empty(&self) -> bool {
84        self.points.is_empty()
85    }
86}
87
88/// Edge directions between consecutive and diagonal vertex pairs.
89///
90/// Capped deliberately. The full O(n^2) edge set makes SAT O(n^4) against
91/// another shape, which is the wrong trade past a few dozen vertices; for the
92/// box and prism cases this crate targets, the cap is never reached.
93fn derive_edges(points: &[Point3]) -> Vec<Vec3> {
94    const MAX_POINTS_FOR_FULL_EDGES: usize = 16;
95    let mut edges = Vec::new();
96    if points.len() <= MAX_POINTS_FOR_FULL_EDGES {
97        for i in 0..points.len() {
98            for j in (i + 1)..points.len() {
99                let direction = points[j] - points[i];
100                if direction.length_squared() > 0.0 {
101                    edges.push(direction);
102                }
103            }
104        }
105    } else {
106        for window in points.windows(2) {
107            let direction = window[1] - window[0];
108            if direction.length_squared() > 0.0 {
109                edges.push(direction);
110            }
111        }
112    }
113    edges
114}
axiolid_collide/shape.rs

axiolid_collide/
shape.rs
