1mod primitive_impls;
2
3use super::{BoundingVolume, IntersectsVolume};
4use crate::{
5 ops,
6 prelude::{Mat2, Rot2, Vec2},
7 FloatPow, Isometry2d,
8};
9
10#[cfg(feature = "bevy_reflect")]
11use bevy_reflect::Reflect;
12#[cfg(all(feature = "bevy_reflect", feature = "serialize"))]
13use bevy_reflect::{ReflectDeserialize, ReflectSerialize};
14#[cfg(feature = "serialize")]
15use serde::{Deserialize, Serialize};
16
17#[inline(always)]
19fn point_cloud_2d_center(points: &[Vec2]) -> Vec2 {
20 assert!(
21 !points.is_empty(),
22 "cannot compute the center of an empty set of points"
23 );
24
25 let denom = 1.0 / points.len() as f32;
26 points.iter().fold(Vec2::ZERO, |acc, point| acc + *point) * denom
27}
28
29pub trait Bounded2d {
31 fn aabb_2d(&self, isometry: impl Into<Isometry2d>) -> Aabb2d;
33 fn bounding_circle(&self, isometry: impl Into<Isometry2d>) -> BoundingCircle;
35}
36
37#[doc(alias = "BoundingRectangle")]
39#[derive(Clone, Copy, Debug, PartialEq)]
40#[cfg_attr(
41 feature = "bevy_reflect",
42 derive(Reflect),
43 reflect(Debug, PartialEq, Clone)
44)]
45#[cfg_attr(feature = "serialize", derive(Serialize), derive(Deserialize))]
46#[cfg_attr(
47 all(feature = "serialize", feature = "bevy_reflect"),
48 reflect(Serialize, Deserialize)
49)]
50pub struct Aabb2d {
51 pub min: Vec2,
53 pub max: Vec2,
55}
56
57impl Aabb2d {
58 #[inline(always)]
60 pub fn new(center: Vec2, half_size: Vec2) -> Self {
61 debug_assert!(half_size.x >= 0.0 && half_size.y >= 0.0);
62 Self {
63 min: center - half_size,
64 max: center + half_size,
65 }
66 }
67
68 #[inline(always)]
75 pub fn from_point_cloud(isometry: impl Into<Isometry2d>, points: &[Vec2]) -> Aabb2d {
76 let isometry = isometry.into();
77
78 let mut iter = points.iter().map(|point| isometry.rotation * *point);
80
81 let first = iter
82 .next()
83 .expect("point cloud must contain at least one point for Aabb2d construction");
84
85 let (min, max) = iter.fold((first, first), |(prev_min, prev_max), point| {
86 (point.min(prev_min), point.max(prev_max))
87 });
88
89 Aabb2d {
90 min: min + isometry.translation,
91 max: max + isometry.translation,
92 }
93 }
94
95 #[inline(always)]
97 pub fn bounding_circle(&self) -> BoundingCircle {
98 let radius = self.min.distance(self.max) / 2.0;
99 BoundingCircle::new(self.center(), radius)
100 }
101
102 #[inline(always)]
107 pub fn closest_point(&self, point: Vec2) -> Vec2 {
108 point.clamp(self.min, self.max)
110 }
111}
112
113impl BoundingVolume for Aabb2d {
114 type Translation = Vec2;
115 type Rotation = Rot2;
116 type HalfSize = Vec2;
117
118 #[inline(always)]
119 fn center(&self) -> Self::Translation {
120 (self.min + self.max) / 2.
121 }
122
123 #[inline(always)]
124 fn half_size(&self) -> Self::HalfSize {
125 (self.max - self.min) / 2.
126 }
127
128 #[inline(always)]
129 fn visible_area(&self) -> f32 {
130 let b = self.max - self.min;
131 b.x * b.y
132 }
133
134 #[inline(always)]
135 fn contains(&self, other: &Self) -> bool {
136 other.min.x >= self.min.x
137 && other.min.y >= self.min.y
138 && other.max.x <= self.max.x
139 && other.max.y <= self.max.y
140 }
141
142 #[inline(always)]
143 fn merge(&self, other: &Self) -> Self {
144 Self {
145 min: self.min.min(other.min),
146 max: self.max.max(other.max),
147 }
148 }
149
150 #[inline(always)]
151 fn grow(&self, amount: impl Into<Self::HalfSize>) -> Self {
152 let amount = amount.into();
153 let b = Self {
154 min: self.min - amount,
155 max: self.max + amount,
156 };
157 debug_assert!(b.min.x <= b.max.x && b.min.y <= b.max.y);
158 b
159 }
160
161 #[inline(always)]
162 fn shrink(&self, amount: impl Into<Self::HalfSize>) -> Self {
163 let amount = amount.into();
164 let b = Self {
165 min: self.min + amount,
166 max: self.max - amount,
167 };
168 debug_assert!(b.min.x <= b.max.x && b.min.y <= b.max.y);
169 b
170 }
171
172 #[inline(always)]
173 fn scale_around_center(&self, scale: impl Into<Self::HalfSize>) -> Self {
174 let scale = scale.into();
175 let b = Self {
176 min: self.center() - (self.half_size() * scale),
177 max: self.center() + (self.half_size() * scale),
178 };
179 debug_assert!(b.min.x <= b.max.x && b.min.y <= b.max.y);
180 b
181 }
182
183 #[inline(always)]
191 fn transformed_by(
192 mut self,
193 translation: impl Into<Self::Translation>,
194 rotation: impl Into<Self::Rotation>,
195 ) -> Self {
196 self.transform_by(translation, rotation);
197 self
198 }
199
200 #[inline(always)]
208 fn transform_by(
209 &mut self,
210 translation: impl Into<Self::Translation>,
211 rotation: impl Into<Self::Rotation>,
212 ) {
213 self.rotate_by(rotation);
214 self.translate_by(translation);
215 }
216
217 #[inline(always)]
218 fn translate_by(&mut self, translation: impl Into<Self::Translation>) {
219 let translation = translation.into();
220 self.min += translation;
221 self.max += translation;
222 }
223
224 #[inline(always)]
232 fn rotated_by(mut self, rotation: impl Into<Self::Rotation>) -> Self {
233 self.rotate_by(rotation);
234 self
235 }
236
237 #[inline(always)]
245 fn rotate_by(&mut self, rotation: impl Into<Self::Rotation>) {
246 let rot_mat = Mat2::from(rotation.into());
247 let half_size = rot_mat.abs() * self.half_size();
248 *self = Self::new(rot_mat * self.center(), half_size);
249 }
250}
251
252impl IntersectsVolume<Self> for Aabb2d {
253 #[inline(always)]
254 fn intersects(&self, other: &Self) -> bool {
255 let x_overlaps = self.min.x <= other.max.x && self.max.x >= other.min.x;
256 let y_overlaps = self.min.y <= other.max.y && self.max.y >= other.min.y;
257 x_overlaps && y_overlaps
258 }
259}
260
261impl IntersectsVolume<BoundingCircle> for Aabb2d {
262 #[inline(always)]
263 fn intersects(&self, circle: &BoundingCircle) -> bool {
264 let closest_point = self.closest_point(circle.center);
265 let distance_squared = circle.center.distance_squared(closest_point);
266 let radius_squared = circle.radius().squared();
267 distance_squared <= radius_squared
268 }
269}
270
271#[cfg(test)]
272mod aabb2d_tests {
273 use approx::assert_relative_eq;
274
275 use super::Aabb2d;
276 use crate::{
277 bounding::{BoundingCircle, BoundingVolume, IntersectsVolume},
278 ops, Vec2,
279 };
280
281 #[test]
282 fn center() {
283 let aabb = Aabb2d {
284 min: Vec2::new(-0.5, -1.),
285 max: Vec2::new(1., 1.),
286 };
287 assert!((aabb.center() - Vec2::new(0.25, 0.)).length() < f32::EPSILON);
288 let aabb = Aabb2d {
289 min: Vec2::new(5., -10.),
290 max: Vec2::new(10., -5.),
291 };
292 assert!((aabb.center() - Vec2::new(7.5, -7.5)).length() < f32::EPSILON);
293 }
294
295 #[test]
296 fn half_size() {
297 let aabb = Aabb2d {
298 min: Vec2::new(-0.5, -1.),
299 max: Vec2::new(1., 1.),
300 };
301 let half_size = aabb.half_size();
302 assert!((half_size - Vec2::new(0.75, 1.)).length() < f32::EPSILON);
303 }
304
305 #[test]
306 fn area() {
307 let aabb = Aabb2d {
308 min: Vec2::new(-1., -1.),
309 max: Vec2::new(1., 1.),
310 };
311 assert!(ops::abs(aabb.visible_area() - 4.) < f32::EPSILON);
312 let aabb = Aabb2d {
313 min: Vec2::new(0., 0.),
314 max: Vec2::new(1., 0.5),
315 };
316 assert!(ops::abs(aabb.visible_area() - 0.5) < f32::EPSILON);
317 }
318
319 #[test]
320 fn contains() {
321 let a = Aabb2d {
322 min: Vec2::new(-1., -1.),
323 max: Vec2::new(1., 1.),
324 };
325 let b = Aabb2d {
326 min: Vec2::new(-2., -1.),
327 max: Vec2::new(1., 1.),
328 };
329 assert!(!a.contains(&b));
330 let b = Aabb2d {
331 min: Vec2::new(-0.25, -0.8),
332 max: Vec2::new(1., 1.),
333 };
334 assert!(a.contains(&b));
335 }
336
337 #[test]
338 fn merge() {
339 let a = Aabb2d {
340 min: Vec2::new(-1., -1.),
341 max: Vec2::new(1., 0.5),
342 };
343 let b = Aabb2d {
344 min: Vec2::new(-2., -0.5),
345 max: Vec2::new(0.75, 1.),
346 };
347 let merged = a.merge(&b);
348 assert!((merged.min - Vec2::new(-2., -1.)).length() < f32::EPSILON);
349 assert!((merged.max - Vec2::new(1., 1.)).length() < f32::EPSILON);
350 assert!(merged.contains(&a));
351 assert!(merged.contains(&b));
352 assert!(!a.contains(&merged));
353 assert!(!b.contains(&merged));
354 }
355
356 #[test]
357 fn grow() {
358 let a = Aabb2d {
359 min: Vec2::new(-1., -1.),
360 max: Vec2::new(1., 1.),
361 };
362 let padded = a.grow(Vec2::ONE);
363 assert!((padded.min - Vec2::new(-2., -2.)).length() < f32::EPSILON);
364 assert!((padded.max - Vec2::new(2., 2.)).length() < f32::EPSILON);
365 assert!(padded.contains(&a));
366 assert!(!a.contains(&padded));
367 }
368
369 #[test]
370 fn shrink() {
371 let a = Aabb2d {
372 min: Vec2::new(-2., -2.),
373 max: Vec2::new(2., 2.),
374 };
375 let shrunk = a.shrink(Vec2::ONE);
376 assert!((shrunk.min - Vec2::new(-1., -1.)).length() < f32::EPSILON);
377 assert!((shrunk.max - Vec2::new(1., 1.)).length() < f32::EPSILON);
378 assert!(a.contains(&shrunk));
379 assert!(!shrunk.contains(&a));
380 }
381
382 #[test]
383 fn scale_around_center() {
384 let a = Aabb2d {
385 min: Vec2::NEG_ONE,
386 max: Vec2::ONE,
387 };
388 let scaled = a.scale_around_center(Vec2::splat(2.));
389 assert!((scaled.min - Vec2::splat(-2.)).length() < f32::EPSILON);
390 assert!((scaled.max - Vec2::splat(2.)).length() < f32::EPSILON);
391 assert!(!a.contains(&scaled));
392 assert!(scaled.contains(&a));
393 }
394
395 #[test]
396 fn rotate() {
397 let a = Aabb2d {
398 min: Vec2::new(-2.0, -2.0),
399 max: Vec2::new(2.0, 2.0),
400 };
401 let rotated = a.rotated_by(core::f32::consts::PI);
402 assert_relative_eq!(rotated.min, a.min);
403 assert_relative_eq!(rotated.max, a.max);
404 }
405
406 #[test]
407 fn transform() {
408 let a = Aabb2d {
409 min: Vec2::new(-2.0, -2.0),
410 max: Vec2::new(2.0, 2.0),
411 };
412 let transformed = a.transformed_by(Vec2::new(2.0, -2.0), core::f32::consts::FRAC_PI_4);
413 let half_length = ops::hypot(2.0, 2.0);
414 assert_eq!(
415 transformed.min,
416 Vec2::new(2.0 - half_length, -half_length - 2.0)
417 );
418 assert_eq!(
419 transformed.max,
420 Vec2::new(2.0 + half_length, half_length - 2.0)
421 );
422 }
423
424 #[test]
425 fn closest_point() {
426 let aabb = Aabb2d {
427 min: Vec2::NEG_ONE,
428 max: Vec2::ONE,
429 };
430 assert_eq!(aabb.closest_point(Vec2::X * 10.0), Vec2::X);
431 assert_eq!(aabb.closest_point(Vec2::NEG_ONE * 10.0), Vec2::NEG_ONE);
432 assert_eq!(
433 aabb.closest_point(Vec2::new(0.25, 0.1)),
434 Vec2::new(0.25, 0.1)
435 );
436 }
437
438 #[test]
439 fn intersect_aabb() {
440 let aabb = Aabb2d {
441 min: Vec2::NEG_ONE,
442 max: Vec2::ONE,
443 };
444 assert!(aabb.intersects(&aabb));
445 assert!(aabb.intersects(&Aabb2d {
446 min: Vec2::new(0.5, 0.5),
447 max: Vec2::new(2.0, 2.0),
448 }));
449 assert!(aabb.intersects(&Aabb2d {
450 min: Vec2::new(-2.0, -2.0),
451 max: Vec2::new(-0.5, -0.5),
452 }));
453 assert!(!aabb.intersects(&Aabb2d {
454 min: Vec2::new(1.1, 0.0),
455 max: Vec2::new(2.0, 0.5),
456 }));
457 }
458
459 #[test]
460 fn intersect_bounding_circle() {
461 let aabb = Aabb2d {
462 min: Vec2::NEG_ONE,
463 max: Vec2::ONE,
464 };
465 assert!(aabb.intersects(&BoundingCircle::new(Vec2::ZERO, 1.0)));
466 assert!(aabb.intersects(&BoundingCircle::new(Vec2::ONE * 1.5, 1.0)));
467 assert!(aabb.intersects(&BoundingCircle::new(Vec2::NEG_ONE * 1.5, 1.0)));
468 assert!(!aabb.intersects(&BoundingCircle::new(Vec2::ONE * 1.75, 1.0)));
469 }
470}
471
472use crate::primitives::Circle;
473
474#[derive(Clone, Copy, Debug, PartialEq)]
476#[cfg_attr(
477 feature = "bevy_reflect",
478 derive(Reflect),
479 reflect(Debug, PartialEq, Clone)
480)]
481#[cfg_attr(feature = "serialize", derive(Serialize), derive(Deserialize))]
482#[cfg_attr(
483 all(feature = "serialize", feature = "bevy_reflect"),
484 reflect(Serialize, Deserialize)
485)]
486pub struct BoundingCircle {
487 pub center: Vec2,
489 pub circle: Circle,
491}
492
493impl BoundingCircle {
494 #[inline(always)]
496 pub fn new(center: Vec2, radius: f32) -> Self {
497 debug_assert!(radius >= 0.);
498 Self {
499 center,
500 circle: Circle { radius },
501 }
502 }
503
504 #[inline(always)]
509 pub fn from_point_cloud(isometry: impl Into<Isometry2d>, points: &[Vec2]) -> BoundingCircle {
510 let isometry = isometry.into();
511
512 let center = point_cloud_2d_center(points);
513 let mut radius_squared = 0.0;
514
515 for point in points {
516 let distance_squared = point.distance_squared(center);
518 if distance_squared > radius_squared {
519 radius_squared = distance_squared;
520 }
521 }
522
523 BoundingCircle::new(isometry * center, ops::sqrt(radius_squared))
524 }
525
526 #[inline(always)]
528 pub fn radius(&self) -> f32 {
529 self.circle.radius
530 }
531
532 #[inline(always)]
534 pub fn aabb_2d(&self) -> Aabb2d {
535 Aabb2d {
536 min: self.center - Vec2::splat(self.radius()),
537 max: self.center + Vec2::splat(self.radius()),
538 }
539 }
540
541 #[inline(always)]
546 pub fn closest_point(&self, point: Vec2) -> Vec2 {
547 self.circle.closest_point(point - self.center) + self.center
548 }
549}
550
551impl BoundingVolume for BoundingCircle {
552 type Translation = Vec2;
553 type Rotation = Rot2;
554 type HalfSize = f32;
555
556 #[inline(always)]
557 fn center(&self) -> Self::Translation {
558 self.center
559 }
560
561 #[inline(always)]
562 fn half_size(&self) -> Self::HalfSize {
563 self.radius()
564 }
565
566 #[inline(always)]
567 fn visible_area(&self) -> f32 {
568 core::f32::consts::PI * self.radius() * self.radius()
569 }
570
571 #[inline(always)]
572 fn contains(&self, other: &Self) -> bool {
573 let diff = self.radius() - other.radius();
574 self.center.distance_squared(other.center) <= ops::copysign(diff.squared(), diff)
575 }
576
577 #[inline(always)]
578 fn merge(&self, other: &Self) -> Self {
579 let diff = other.center - self.center;
580 let length = diff.length();
581 if self.radius() >= length + other.radius() {
582 return *self;
583 }
584 if other.radius() >= length + self.radius() {
585 return *other;
586 }
587 let dir = diff / length;
588 Self::new(
589 (self.center + other.center) / 2. + dir * ((other.radius() - self.radius()) / 2.),
590 (length + self.radius() + other.radius()) / 2.,
591 )
592 }
593
594 #[inline(always)]
595 fn grow(&self, amount: impl Into<Self::HalfSize>) -> Self {
596 let amount = amount.into();
597 debug_assert!(amount >= 0.);
598 Self::new(self.center, self.radius() + amount)
599 }
600
601 #[inline(always)]
602 fn shrink(&self, amount: impl Into<Self::HalfSize>) -> Self {
603 let amount = amount.into();
604 debug_assert!(amount >= 0.);
605 debug_assert!(self.radius() >= amount);
606 Self::new(self.center, self.radius() - amount)
607 }
608
609 #[inline(always)]
610 fn scale_around_center(&self, scale: impl Into<Self::HalfSize>) -> Self {
611 let scale = scale.into();
612 debug_assert!(scale >= 0.);
613 Self::new(self.center, self.radius() * scale)
614 }
615
616 #[inline(always)]
617 fn translate_by(&mut self, translation: impl Into<Self::Translation>) {
618 self.center += translation.into();
619 }
620
621 #[inline(always)]
622 fn rotate_by(&mut self, rotation: impl Into<Self::Rotation>) {
623 let rotation: Rot2 = rotation.into();
624 self.center = rotation * self.center;
625 }
626}
627
628impl IntersectsVolume<Self> for BoundingCircle {
629 #[inline(always)]
630 fn intersects(&self, other: &Self) -> bool {
631 let center_distance_squared = self.center.distance_squared(other.center);
632 let radius_sum_squared = (self.radius() + other.radius()).squared();
633 center_distance_squared <= radius_sum_squared
634 }
635}
636
637impl IntersectsVolume<Aabb2d> for BoundingCircle {
638 #[inline(always)]
639 fn intersects(&self, aabb: &Aabb2d) -> bool {
640 aabb.intersects(self)
641 }
642}
643
644#[cfg(test)]
645mod bounding_circle_tests {
646 use super::BoundingCircle;
647 use crate::{
648 bounding::{BoundingVolume, IntersectsVolume},
649 ops, Vec2,
650 };
651
652 #[test]
653 fn area() {
654 let circle = BoundingCircle::new(Vec2::ONE, 5.);
655 assert!(ops::abs(circle.visible_area() - 78.5398) < 0.001);
657 }
658
659 #[test]
660 fn contains() {
661 let a = BoundingCircle::new(Vec2::ONE, 5.);
662 let b = BoundingCircle::new(Vec2::new(5.5, 1.), 1.);
663 assert!(!a.contains(&b));
664 let b = BoundingCircle::new(Vec2::new(1., -3.5), 0.5);
665 assert!(a.contains(&b));
666 }
667
668 #[test]
669 fn contains_identical() {
670 let a = BoundingCircle::new(Vec2::ONE, 5.);
671 assert!(a.contains(&a));
672 }
673
674 #[test]
675 fn merge() {
676 let a = BoundingCircle::new(Vec2::ONE, 5.);
679 let b = BoundingCircle::new(Vec2::new(1., -4.), 1.);
680 let merged = a.merge(&b);
681 assert!((merged.center - Vec2::new(1., 0.5)).length() < f32::EPSILON);
682 assert!(ops::abs(merged.radius() - 5.5) < f32::EPSILON);
683 assert!(merged.contains(&a));
684 assert!(merged.contains(&b));
685 assert!(!a.contains(&merged));
686 assert!(!b.contains(&merged));
687
688 let b = BoundingCircle::new(Vec2::ZERO, 3.);
690 assert!(a.contains(&b));
691 let merged = a.merge(&b);
692 assert_eq!(merged.center, a.center);
693 assert_eq!(merged.radius(), a.radius());
694
695 let b = BoundingCircle::new(Vec2::ONE, 6.);
697 let merged = a.merge(&b);
698 assert_eq!(merged.center, a.center);
699 assert_eq!(merged.radius(), b.radius());
700 }
701
702 #[test]
703 fn merge_identical() {
704 let a = BoundingCircle::new(Vec2::ONE, 5.);
705 let merged = a.merge(&a);
706 assert_eq!(merged.center, a.center);
707 assert_eq!(merged.radius(), a.radius());
708 }
709
710 #[test]
711 fn grow() {
712 let a = BoundingCircle::new(Vec2::ONE, 5.);
713 let padded = a.grow(1.25);
714 assert!(ops::abs(padded.radius() - 6.25) < f32::EPSILON);
715 assert!(padded.contains(&a));
716 assert!(!a.contains(&padded));
717 }
718
719 #[test]
720 fn shrink() {
721 let a = BoundingCircle::new(Vec2::ONE, 5.);
722 let shrunk = a.shrink(0.5);
723 assert!(ops::abs(shrunk.radius() - 4.5) < f32::EPSILON);
724 assert!(a.contains(&shrunk));
725 assert!(!shrunk.contains(&a));
726 }
727
728 #[test]
729 fn scale_around_center() {
730 let a = BoundingCircle::new(Vec2::ONE, 5.);
731 let scaled = a.scale_around_center(2.);
732 assert!(ops::abs(scaled.radius() - 10.) < f32::EPSILON);
733 assert!(!a.contains(&scaled));
734 assert!(scaled.contains(&a));
735 }
736
737 #[test]
738 fn transform() {
739 let a = BoundingCircle::new(Vec2::ONE, 5.0);
740 let transformed = a.transformed_by(Vec2::new(2.0, -2.0), core::f32::consts::FRAC_PI_4);
741 assert_eq!(
742 transformed.center,
743 Vec2::new(2.0, core::f32::consts::SQRT_2 - 2.0)
744 );
745 assert_eq!(transformed.radius(), 5.0);
746 }
747
748 #[test]
749 fn closest_point() {
750 let circle = BoundingCircle::new(Vec2::ZERO, 1.0);
751 assert_eq!(circle.closest_point(Vec2::X * 10.0), Vec2::X);
752 assert_eq!(
753 circle.closest_point(Vec2::NEG_ONE * 10.0),
754 Vec2::NEG_ONE.normalize()
755 );
756 assert_eq!(
757 circle.closest_point(Vec2::new(0.25, 0.1)),
758 Vec2::new(0.25, 0.1)
759 );
760 }
761
762 #[test]
763 fn intersect_bounding_circle() {
764 let circle = BoundingCircle::new(Vec2::ZERO, 1.0);
765 assert!(circle.intersects(&BoundingCircle::new(Vec2::ZERO, 1.0)));
766 assert!(circle.intersects(&BoundingCircle::new(Vec2::ONE * 1.25, 1.0)));
767 assert!(circle.intersects(&BoundingCircle::new(Vec2::NEG_ONE * 1.25, 1.0)));
768 assert!(!circle.intersects(&BoundingCircle::new(Vec2::ONE * 1.5, 1.0)));
769 }
770}