fey_math/
shape.rs

1use crate::{Circle, Float, Line, Projection, Ray, RayHit, Rect, Vec2, line, rect};
2
3/// A type that represents a convex 2D shape.
4pub trait Shape<T> {
5    /// Centroid of the shape.
6    fn centroid(&self) -> Vec2<T>;
7
8    /// If the point is contained within the shape.
9    fn contains(&self, p: Vec2<T>) -> bool;
10
11    /// Rectangular bounds of the shape.
12    fn bounds(&self) -> Rect<T>;
13
14    /// Project the shape onto the axis.
15    fn project_onto_axis(&self, axis: Vec2<T>) -> Projection<T>;
16
17    /// Project a point onto the outside surface of the shape.
18    fn project_point(&self, p: Vec2<T>) -> Vec2<T>;
19
20    /// Check if a ray intersects this shape.
21    fn rayhit(&self, ray: &Ray<T>) -> bool;
22
23    /// Raycast against the shape.
24    fn raycast(&self, ray: &Ray<T>) -> Option<RayHit<T>>;
25
26    /// If this shape overlaps the rectangle.
27    fn overlaps_rect(&self, rect: &Rect<T>) -> bool;
28
29    /// If this shape overlaps the circle.
30    fn overlaps_circ(&self, circ: &Circle<T>) -> bool;
31
32    /// If this shape overlaps the polygon.
33    fn overlaps_poly<P: Polygonal<T>>(&self, poly: &P) -> bool;
34
35    /// If this shape and the circle overlap, return a push-out
36    /// vector that can be used to extract them from each other.
37    fn extract_from_circ(&self, circ: &Circle<T>) -> Option<Vec2<T>>;
38
39    /// If this shape and the polygon overlap, return a push-out
40    /// vector that can be used to extract them from each other.
41    fn extract_from_poly<P: Polygonal<T>>(&self, poly: &P) -> Option<Vec2<T>>;
42
43    /// If this shape is convex.
44    fn is_convex(&self) -> bool;
45}
46
47/// A type that represents a convex 2D polygonal shape.
48pub trait Polygonal<T>: Shape<T> {
49    /// Get the nearest point on this polygon to the source point.
50    fn nearest_vertex(&self, source: Vec2<T>) -> Vec2<T>;
51
52    /// Iterate all polygonal edges of the shape, returning true if
53    /// any of them satisfy the conditional function provided.
54    fn all_edges<F: FnMut(Line<T>) -> bool>(&self, cond: F) -> bool;
55
56    /// Iterate all edge normals of the shape, returning true if
57    /// any of them satisfy the conditional function provided.
58    fn all_normals<F: FnMut(Vec2<T>) -> bool>(&self, cond: F) -> bool;
59
60    /// Walk through every edge of the polygon.
61    #[inline]
62    fn visit_edges<F: FnMut(Line<T>)>(&self, mut plot: F) {
63        self.all_edges(|edge| {
64            plot(edge);
65            true
66        });
67    }
68
69    /// Walk through every normal of the polygon.
70    fn visit_normals<F: FnMut(Vec2<T>)>(&self, plot: F);
71}
72
73/// Check if two shapes overlap on the provided axis.
74#[inline]
75pub(crate) fn overlaps_on<T: Float, A: Shape<T>, B: Shape<T>>(a: &A, b: &B, axis: Vec2<T>) -> bool {
76    let a = a.project_onto_axis(axis);
77    let b = b.project_onto_axis(axis);
78    a.overlaps(b)
79}
80
81/// If the two shapes overlap on the provided axis. This will assign the
82/// push-out distance and direction if the calculated push-out is shorter.
83#[inline]
84pub(crate) fn extract_on<T: Float, A: Shape<T>, B: Shape<T>>(
85    a: &A,
86    b: &B,
87    axis: Vec2<T>,
88    push_dist: &mut T,
89    push_dir: &mut Vec2<T>,
90) -> bool {
91    let a = a.project_onto_axis(axis);
92    let b = b.project_onto_axis(axis);
93    if a.min < b.max && a.max > b.min {
94        let dist = if T::abs(b.max - a.min) < T::abs(a.max - b.min) {
95            b.max - a.min
96        } else {
97            b.min - a.max
98        };
99        if T::abs(dist) < T::abs(*push_dist) {
100            *push_dist = dist;
101            *push_dir = axis;
102        }
103        true
104    } else {
105        false
106    }
107}
108
109impl<T: Float, S: AsRef<[Vec2<T>]>> Shape<T> for S {
110    fn centroid(&self) -> Vec2<T> {
111        let arr = self.as_ref();
112        let mut centroid = Vec2::ZERO;
113        let mut signed_area = T::ZERO;
114        for i in 0..arr.len() {
115            let a = arr[i];
116            let b = arr[(i + 1) % arr.len()];
117            let area = a.x * b.y - b.x * a.y;
118            centroid += (a + b) * area;
119            signed_area += area;
120        }
121        centroid / (signed_area * T::THREE)
122    }
123
124    fn contains(&self, p: Vec2<T>) -> bool {
125        let arr = self.as_ref();
126        for i in 0..arr.len() {
127            let a = arr[i];
128            let b = arr[(i + 1) % arr.len()];
129            if (b - a).cross(p - a) <= T::ZERO {
130                return false;
131            }
132        }
133        true
134    }
135
136    fn bounds(&self) -> Rect<T> {
137        let arr = self.as_ref();
138        let mut min = Vec2::splat(T::MAX);
139        let mut max = Vec2::splat(T::MIN);
140        for p in arr {
141            min = p.min(min);
142            max = p.max(max);
143        }
144        rect(min.x, min.y, max.x - min.x, max.y - min.y)
145    }
146
147    fn project_onto_axis(&self, axis: Vec2<T>) -> Projection<T> {
148        let arr = self.as_ref();
149        let mut min = T::MAX;
150        let mut max = T::MIN;
151        for p in arr {
152            let dot = p.dot(axis);
153            min = T::min(min, dot);
154            max = T::max(max, dot);
155        }
156        Projection { min, max }
157    }
158
159    fn project_point(&self, p: Vec2<T>) -> Vec2<T> {
160        let arr = self.as_ref();
161        let mut min_dist = T::MAX;
162        let mut min_proj = Vec2::ZERO;
163        for i in 0..arr.len() {
164            let edge = line(arr[i], arr[(i + 1) % arr.len()]);
165            let proj = edge.project_point(p);
166            let dist = proj.sqr_dist(p);
167            if dist < min_dist {
168                min_dist = dist;
169                min_proj = proj;
170            }
171        }
172        min_proj
173    }
174
175    fn rayhit(&self, ray: &Ray<T>) -> bool {
176        let arr = self.as_ref();
177        for i in 0..arr.len() {
178            let edge = line(arr[i], arr[(i + 1) % arr.len()]);
179            if edge.raycast(ray).is_some() {
180                return true;
181            }
182        }
183        false
184    }
185
186    fn raycast(&self, ray: &Ray<T>) -> Option<RayHit<T>> {
187        let arr = self.as_ref();
188        let mut distance = T::MAX;
189        let mut crossings = 0;
190        let mut normal = Vec2::ZERO;
191        for i in 0..arr.len() {
192            let edge = line(arr[i], arr[(i + 1) % arr.len()]);
193            if let Some(d) = edge.raycast(ray) {
194                crossings += 1;
195                if d < distance {
196                    distance = d;
197                    normal = edge.vector();
198                }
199            }
200        }
201        (crossings > 0 && (crossings % 2) == 0)
202            .then(|| RayHit::new(normal.norm().turn_left(), distance))
203    }
204
205    #[inline]
206    fn overlaps_rect(&self, rect: &Rect<T>) -> bool {
207        rect.overlaps_poly(self)
208    }
209
210    #[inline]
211    fn overlaps_circ(&self, circ: &Circle<T>) -> bool {
212        circ.overlaps_poly(self)
213    }
214
215    #[inline]
216    fn overlaps_poly<P: Polygonal<T>>(&self, poly: &P) -> bool {
217        self.all_normals(|axis| overlaps_on(self, poly, axis))
218            && poly.all_normals(|axis| overlaps_on(self, poly, axis))
219    }
220
221    #[inline]
222    fn extract_from_circ(&self, circ: &Circle<T>) -> Option<Vec2<T>> {
223        circ.extract_from_poly(self).map(|p| -p)
224    }
225
226    fn extract_from_poly<P: Polygonal<T>>(&self, poly: &P) -> Option<Vec2<T>> {
227        let mut dist = T::MAX;
228        let mut dir = Vec2::ZERO;
229        (self.all_normals(|axis| extract_on(self, poly, axis, &mut dist, &mut dir))
230            && poly.all_normals(|axis| extract_on(self, poly, axis, &mut dist, &mut dir)))
231        .then(|| dir * dist)
232    }
233
234    fn is_convex(&self) -> bool {
235        let p = self.as_ref();
236        for i in 0..p.len() {
237            let a = p[i];
238            let b = p[(i + 1) % p.len()];
239            let c = p[(i + 2) % p.len()];
240            if (b - a).cross(c - b) < T::ZERO {
241                return false;
242            }
243        }
244        true
245    }
246}
247
248impl<T: Float, S: AsRef<[Vec2<T>]>> Polygonal<T> for S {
249    fn nearest_vertex(&self, source: Vec2<T>) -> Vec2<T> {
250        let arr = self.as_ref();
251        let mut min_dist = arr[0].dist(source);
252        let mut min_i = 0;
253        for i in 1..arr.len() {
254            let dist = arr[i].dist(source);
255            if dist < min_dist {
256                min_dist = dist;
257                min_i = i;
258            }
259        }
260        arr[min_i]
261    }
262
263    #[inline]
264    fn all_edges<F: FnMut(Line<T>) -> bool>(&self, mut cond: F) -> bool {
265        let arr = self.as_ref();
266        (0..arr.len()).all(|i| cond(line(arr[i], arr[(i + 1) % arr.len()])))
267    }
268
269    #[inline]
270    fn all_normals<F: FnMut(Vec2<T>) -> bool>(&self, mut cond: F) -> bool {
271        self.all_edges(|edge| cond(edge.left_norm()))
272    }
273
274    #[inline]
275    fn visit_normals<F: FnMut(Vec2<T>)>(&self, mut plot: F) {
276        self.all_edges(|edge| {
277            plot(edge.left_norm());
278            true
279        });
280    }
281}
fey_math/shape.rs

fey_math/
shape.rs
