1use crate::Matrix4Ext;
22use nalgebra::{Matrix4, Vector2, Vector3, Vector4};
23use rectutils::{OptionRect, Rect};
24
25#[derive(Copy, Clone, Debug)]
26pub struct AxisAlignedBoundingBox {
27 pub min: Vector3<f32>,
28 pub max: Vector3<f32>,
29}
30
31impl Default for AxisAlignedBoundingBox {
32 #[inline]
33 fn default() -> Self {
34 Self {
35 min: Vector3::new(f32::MAX, f32::MAX, f32::MAX),
36 max: Vector3::new(-f32::MAX, -f32::MAX, -f32::MAX),
37 }
38 }
39}
40
41impl AxisAlignedBoundingBox {
42 #[inline]
43 pub const fn unit() -> Self {
44 Self::from_min_max(Vector3::new(-0.5, -0.5, -0.5), Vector3::new(0.5, 0.5, 0.5))
45 }
46
47 #[inline]
48 pub const fn collapsed() -> Self {
49 Self {
50 min: Vector3::new(0.0, 0.0, 0.0),
51 max: Vector3::new(0.0, 0.0, 0.0),
52 }
53 }
54
55 #[inline]
56 pub fn from_radius(radius: f32) -> Self {
57 Self {
58 min: Vector3::new(-radius, -radius, -radius),
59 max: Vector3::new(radius, radius, radius),
60 }
61 }
62
63 #[inline]
64 pub const fn from_min_max(min: Vector3<f32>, max: Vector3<f32>) -> Self {
65 Self { min, max }
66 }
67
68 #[inline]
69 pub fn from_point(point: Vector3<f32>) -> Self {
70 Self {
71 min: point,
72 max: point,
73 }
74 }
75
76 #[inline]
77 pub fn from_points(points: &[Vector3<f32>]) -> Self {
78 let mut aabb = AxisAlignedBoundingBox::default();
79 for pt in points {
80 aabb.add_point(*pt);
81 }
82 aabb
83 }
84
85 #[inline]
86 pub fn add_point(&mut self, a: Vector3<f32>) {
87 if a.x < self.min.x {
88 self.min.x = a.x;
89 }
90 if a.y < self.min.y {
91 self.min.y = a.y;
92 }
93 if a.z < self.min.z {
94 self.min.z = a.z;
95 }
96
97 if a.x > self.max.x {
98 self.max.x = a.x;
99 }
100 if a.y > self.max.y {
101 self.max.y = a.y;
102 }
103 if a.z > self.max.z {
104 self.max.z = a.z;
105 }
106 }
107
108 #[inline]
109 pub fn inflate(&mut self, delta: Vector3<f32>) {
110 self.min -= delta.scale(0.5);
111 self.max += delta.scale(0.5);
112 }
113
114 #[inline]
115 pub fn scale(&mut self, scale: f32) {
116 let center = self.center();
117 self.min = (self.min - center) * scale + center;
118 self.max = (self.max - center) * scale + center;
119 }
120
121 #[inline]
122 pub fn add_box(&mut self, other: Self) {
123 self.add_point(other.min);
124 self.add_point(other.max);
125 }
126
127 #[inline]
128 pub fn corners(&self) -> [Vector3<f32>; 8] {
129 [
130 Vector3::new(self.min.x, self.min.y, self.min.z),
131 Vector3::new(self.min.x, self.min.y, self.max.z),
132 Vector3::new(self.max.x, self.min.y, self.max.z),
133 Vector3::new(self.max.x, self.min.y, self.min.z),
134 Vector3::new(self.min.x, self.max.y, self.min.z),
135 Vector3::new(self.min.x, self.max.y, self.max.z),
136 Vector3::new(self.max.x, self.max.y, self.max.z),
137 Vector3::new(self.max.x, self.max.y, self.min.z),
138 ]
139 }
140
141 #[inline]
142 pub fn volume(&self) -> f32 {
143 let size = self.max - self.min;
144 size.x * size.y * size.z
145 }
146
147 #[inline]
148 pub fn offset(&mut self, v: Vector3<f32>) {
149 self.min += v;
150 self.max += v;
151 }
152
153 #[inline]
154 pub fn center(&self) -> Vector3<f32> {
155 (self.max + self.min).scale(0.5)
156 }
157
158 #[inline]
159 pub fn half_extents(&self) -> Vector3<f32> {
160 (self.max - self.min).scale(0.5)
161 }
162
163 #[inline]
164 pub fn invalidate(&mut self) {
165 *self = Default::default();
166 }
167
168 #[inline]
169 pub fn is_valid(&self) -> bool {
170 #[inline(always)]
171 fn is_nan_or_inf(x: &Vector3<f32>) -> bool {
172 x.iter().all(|e| e.is_nan() || e.is_infinite())
173 }
174
175 self.max.x >= self.min.x
176 && self.max.y >= self.min.y
177 && self.max.z >= self.min.z
178 && !is_nan_or_inf(&self.min)
179 && !is_nan_or_inf(&self.max)
180 }
181
182 #[inline]
183 pub fn is_degenerate(&self) -> bool {
184 self.max == self.min
185 }
186
187 #[inline]
188 pub fn is_invalid_or_degenerate(&self) -> bool {
189 !self.is_valid() || self.is_degenerate()
190 }
191
192 #[inline]
193 pub fn is_contains_point(&self, point: Vector3<f32>) -> bool {
194 point.x >= self.min.x
195 && point.x <= self.max.x
196 && point.y >= self.min.y
197 && point.y <= self.max.y
198 && point.z >= self.min.z
199 && point.z <= self.max.z
200 }
201
202 #[inline]
203 pub fn is_intersects_sphere(&self, position: Vector3<f32>, radius: f32) -> bool {
204 let r2 = radius.powi(2);
205 let mut dmin = 0.0;
206
207 if position.x < self.min.x {
208 dmin += (position.x - self.min.x).powi(2);
209 } else if position.x > self.max.x {
210 dmin += (position.x - self.max.x).powi(2);
211 }
212
213 if position.y < self.min.y {
214 dmin += (position.y - self.min.y).powi(2);
215 } else if position.y > self.max.y {
216 dmin += (position.y - self.max.y).powi(2);
217 }
218
219 if position.z < self.min.z {
220 dmin += (position.z - self.min.z).powi(2);
221 } else if position.z > self.max.z {
222 dmin += (position.z - self.max.z).powi(2);
223 }
224
225 dmin <= r2
226 || ((position.x >= self.min.x)
227 && (position.x <= self.max.x)
228 && (position.y >= self.min.y)
229 && (position.y <= self.max.y)
230 && (position.z >= self.min.z)
231 && (position.z <= self.max.z))
232 }
233
234 #[inline]
235 pub fn is_intersects_aabb(&self, other: &Self) -> bool {
236 let self_center = self.center();
237 let self_half_extents = self.half_extents();
238
239 let other_half_extents = other.half_extents();
240 let other_center = other.center();
241
242 if (self_center.x - other_center.x).abs() > (self_half_extents.x + other_half_extents.x) {
243 return false;
244 }
245
246 if (self_center.y - other_center.y).abs() > (self_half_extents.y + other_half_extents.y) {
247 return false;
248 }
249
250 if (self_center.z - other_center.z).abs() > (self_half_extents.z + other_half_extents.z) {
251 return false;
252 }
253
254 true
255 }
256
257 #[inline]
263 #[must_use]
264 pub fn transform(&self, m: &Matrix4<f32>) -> AxisAlignedBoundingBox {
265 let basis = m.basis();
266
267 let mut transformed = Self {
268 min: m.position(),
269 max: m.position(),
270 };
271
272 for i in 0..3 {
273 for j in 0..3 {
274 let a = basis[(i, j)] * self.min[j];
275 let b = basis[(i, j)] * self.max[j];
276 if a < b {
277 transformed.min[i] += a;
278 transformed.max[i] += b;
279 } else {
280 transformed.min[i] += b;
281 transformed.max[i] += a;
282 }
283 }
284 }
285
286 transformed
287 }
288
289 #[inline]
290 pub fn split(&self) -> [AxisAlignedBoundingBox; 8] {
291 let center = self.center();
292 let min = &self.min;
293 let max = &self.max;
294 [
295 AxisAlignedBoundingBox::from_min_max(
296 Vector3::new(min.x, min.y, min.z),
297 Vector3::new(center.x, center.y, center.z),
298 ),
299 AxisAlignedBoundingBox::from_min_max(
300 Vector3::new(center.x, min.y, min.z),
301 Vector3::new(max.x, center.y, center.z),
302 ),
303 AxisAlignedBoundingBox::from_min_max(
304 Vector3::new(min.x, min.y, center.z),
305 Vector3::new(center.x, center.y, max.z),
306 ),
307 AxisAlignedBoundingBox::from_min_max(
308 Vector3::new(center.x, min.y, center.z),
309 Vector3::new(max.x, center.y, max.z),
310 ),
311 AxisAlignedBoundingBox::from_min_max(
312 Vector3::new(min.x, center.y, min.z),
313 Vector3::new(center.x, max.y, center.z),
314 ),
315 AxisAlignedBoundingBox::from_min_max(
316 Vector3::new(center.x, center.y, min.z),
317 Vector3::new(max.x, max.y, center.z),
318 ),
319 AxisAlignedBoundingBox::from_min_max(
320 Vector3::new(min.x, center.y, center.z),
321 Vector3::new(center.x, max.y, max.z),
322 ),
323 AxisAlignedBoundingBox::from_min_max(
324 Vector3::new(center.x, center.y, center.z),
325 Vector3::new(max.x, max.y, max.z),
326 ),
327 ]
328 }
329
330 #[inline]
331 pub fn project(&self, view_projection: &Matrix4<f32>, viewport: &Rect<i32>) -> Rect<f32> {
332 let mut rect_builder = OptionRect::default();
333 for corner in self.corners() {
334 let clip_space = view_projection * Vector4::new(corner.x, corner.y, corner.z, 1.0);
335 let ndc_space = clip_space.xyz() / clip_space.w.abs();
336 let mut normalized_screen_space =
337 Vector2::new((ndc_space.x + 1.0) / 2.0, (1.0 - ndc_space.y) / 2.0);
338 normalized_screen_space.x = normalized_screen_space.x.clamp(0.0, 1.0);
339 normalized_screen_space.y = normalized_screen_space.y.clamp(0.0, 1.0);
340 let screen_space_corner = Vector2::new(
341 (normalized_screen_space.x * viewport.size.x as f32) + viewport.position.x as f32,
342 (normalized_screen_space.y * viewport.size.y as f32) + viewport.position.y as f32,
343 );
344
345 rect_builder.push(screen_space_corner);
346 }
347 rect_builder.unwrap()
348 }
349}
350
351#[cfg(test)]
352mod test {
353 use crate::aabb::AxisAlignedBoundingBox;
354 use nalgebra::{Matrix4, Point3, Vector2, Vector3};
355 use rectutils::Rect;
356
357 #[test]
358 fn test_aabb_transform() {
359 let aabb = AxisAlignedBoundingBox {
360 min: Vector3::new(0.0, 0.0, 0.0),
361 max: Vector3::new(1.0, 1.0, 1.0),
362 };
363
364 let transform = Matrix4::new_translation(&Vector3::new(1.0, 1.0, 1.0))
365 * Matrix4::new_nonuniform_scaling(&Vector3::new(2.0, 2.0, 2.0));
366
367 let transformed_aabb = aabb.transform(&transform);
368
369 assert_eq!(transformed_aabb.min, Vector3::new(1.0, 1.0, 1.0));
370 assert_eq!(transformed_aabb.max, Vector3::new(3.0, 3.0, 3.0));
371 }
372
373 #[test]
374 fn test_aabb_default() {
375 let _box = AxisAlignedBoundingBox::default();
376 assert_eq!(_box.min, Vector3::new(f32::MAX, f32::MAX, f32::MAX));
377 assert_eq!(_box.max, Vector3::new(-f32::MAX, -f32::MAX, -f32::MAX));
378 }
379
380 #[test]
381 fn test_aabb_unit() {
382 let _box = AxisAlignedBoundingBox::unit();
383 assert_eq!(_box.min, Vector3::new(-0.5, -0.5, -0.5));
384 assert_eq!(_box.max, Vector3::new(0.5, 0.5, 0.5));
385 }
386
387 #[test]
388 fn test_aabb_collapsed() {
389 let _box = AxisAlignedBoundingBox::collapsed();
390 assert_eq!(_box.min, Vector3::new(0.0, 0.0, 0.0));
391 assert_eq!(_box.max, Vector3::new(0.0, 0.0, 0.0));
392 }
393
394 #[test]
395 fn test_aabb_from_radius() {
396 let _box = AxisAlignedBoundingBox::from_radius(1.0);
397 assert_eq!(_box.min, Vector3::new(-1.0, -1.0, -1.0));
398 assert_eq!(_box.max, Vector3::new(1.0, 1.0, 1.0));
399 }
400
401 #[test]
402 fn test_aabb_from_point() {
403 let _box = AxisAlignedBoundingBox::from_point(Vector3::new(0.0, 0.0, 0.0));
404 assert_eq!(_box.min, Vector3::new(0.0, 0.0, 0.0));
405 assert_eq!(_box.max, Vector3::new(0.0, 0.0, 0.0));
406 }
407
408 #[test]
409 fn test_aabb_from_points() {
410 let _box = AxisAlignedBoundingBox::from_points(
411 vec![
412 Vector3::new(-1.0, -1.0, -1.0),
413 Vector3::new(0.0, 0.0, 0.0),
414 Vector3::new(1.0, 1.0, 1.0),
415 ]
416 .as_ref(),
417 );
418 assert_eq!(_box.min, Vector3::new(-1.0, -1.0, -1.0));
419 assert_eq!(_box.max, Vector3::new(1.0, 1.0, 1.0));
420 }
421
422 #[test]
423 fn test_aabb_add_point() {
424 let mut _box = AxisAlignedBoundingBox::default();
425 _box.add_point(Vector3::new(-1.0, -1.0, -1.0));
426 _box.add_point(Vector3::new(1.0, 1.0, 1.0));
427 assert_eq!(_box.min, Vector3::new(-1.0, -1.0, -1.0));
428 assert_eq!(_box.max, Vector3::new(1.0, 1.0, 1.0));
429 }
430
431 #[test]
432 fn test_aabb_inflate() {
433 let mut _box = AxisAlignedBoundingBox::from_radius(1.0);
434 _box.inflate(Vector3::new(5.0, 5.0, 5.0));
435 assert_eq!(_box.min, Vector3::new(-3.5, -3.5, -3.5));
436 assert_eq!(_box.max, Vector3::new(3.5, 3.5, 3.5));
437 }
438
439 #[test]
440 fn test_aabb_add_box() {
441 let mut _box = AxisAlignedBoundingBox::collapsed();
442 let _box2 = AxisAlignedBoundingBox::from_radius(1.0);
443 _box.add_box(_box2);
444 assert_eq!(_box.min, Vector3::new(-1.0, -1.0, -1.0));
445 assert_eq!(_box.max, Vector3::new(1.0, 1.0, 1.0));
446 }
447
448 #[test]
449 fn test_aabb_corners() {
450 let _box = AxisAlignedBoundingBox::from_radius(1.0);
451 assert_eq!(
452 _box.corners(),
453 [
454 Vector3::new(-1.0, -1.0, -1.0),
455 Vector3::new(-1.0, -1.0, 1.0),
456 Vector3::new(1.0, -1.0, 1.0),
457 Vector3::new(1.0, -1.0, -1.0),
458 Vector3::new(-1.0, 1.0, -1.0),
459 Vector3::new(-1.0, 1.0, 1.0),
460 Vector3::new(1.0, 1.0, 1.0),
461 Vector3::new(1.0, 1.0, -1.0),
462 ]
463 );
464 assert_eq!(_box.volume(), 8.0);
465 assert_eq!(_box.center(), Vector3::new(0.0, 0.0, 0.0));
466 assert_eq!(_box.half_extents(), Vector3::new(1.0, 1.0, 1.0));
467 }
468
469 #[test]
470 fn test_aabb_offset() {
471 let mut _box = AxisAlignedBoundingBox::unit();
472 _box.offset(Vector3::new(1.0, 1.0, 1.0));
473 assert_eq!(_box.min, Vector3::new(0.5, 0.5, 0.5));
474 assert_eq!(_box.max, Vector3::new(1.5, 1.5, 1.5));
475 }
476
477 #[test]
478 fn test_aabb_invalidate() {
479 let mut _box = AxisAlignedBoundingBox::collapsed();
480 _box.invalidate();
481 assert_eq!(_box.min, Vector3::new(f32::MAX, f32::MAX, f32::MAX));
482 assert_eq!(_box.max, Vector3::new(-f32::MAX, -f32::MAX, -f32::MAX));
483 }
484
485 #[test]
486 fn test_aabb_is_valid() {
487 let mut _box = AxisAlignedBoundingBox::default();
488 assert!(!_box.is_valid());
489
490 _box.add_point(Vector3::new(1.0, 1.0, 1.0));
491 assert!(_box.is_valid());
492
493 _box.add_point(Vector3::new(-1.0, -1.0, -1.0));
494 assert!(_box.is_valid());
495 }
496
497 #[test]
498 fn test_aabb_is_degenerate() {
499 let _box = AxisAlignedBoundingBox::unit();
500 assert!(!_box.is_degenerate());
501
502 let _box = AxisAlignedBoundingBox::collapsed();
503 assert!(_box.is_degenerate());
504 }
505
506 #[test]
507 fn test_aabb_is_invalid_or_degenerate() {
508 let mut _box = AxisAlignedBoundingBox::collapsed();
509 assert!(_box.is_invalid_or_degenerate());
510
511 _box.invalidate();
512 assert!(_box.is_invalid_or_degenerate());
513 }
514
515 #[test]
516 fn test_aabb_is_contains_point() {
517 let _box = AxisAlignedBoundingBox::unit();
518 assert!(_box.is_contains_point(Vector3::new(0.0, 0.0, 0.0)));
519
520 for point in _box.corners() {
521 assert!(_box.is_contains_point(point));
522 }
523 }
524
525 #[test]
526 fn test_aabb_is_intersects_sphere() {
527 let _box = AxisAlignedBoundingBox::unit();
528 assert!(_box.is_intersects_sphere(Vector3::new(0.0, 0.0, 0.0), 1.0));
529 assert!(_box.is_intersects_sphere(Vector3::new(0.0, 0.0, 0.0), 0.5));
530 assert!(_box.is_intersects_sphere(Vector3::new(0.0, 0.0, 0.0), 1.5));
531 assert!(_box.is_intersects_sphere(Vector3::new(0.5, 0.5, 0.5), 1.0));
532 assert!(_box.is_intersects_sphere(Vector3::new(0.25, 0.25, 0.25), 1.0));
533
534 assert!(!_box.is_intersects_sphere(Vector3::new(10.0, 10.0, 10.0), 1.0));
535 assert!(!_box.is_intersects_sphere(Vector3::new(-10.0, -10.0, -10.0), 1.0));
536 }
537
538 #[test]
539 fn test_aabb_is_intersects_aabb() {
540 let _box = AxisAlignedBoundingBox::unit();
541 let mut _box2 = _box;
542 assert!(_box.is_intersects_aabb(&_box2));
543
544 _box2.offset(Vector3::new(0.5, 0.0, 0.0));
545 assert!(_box.is_intersects_aabb(&_box2));
546 _box2.offset(Vector3::new(1.0, 0.0, 0.0));
547 assert!(!_box.is_intersects_aabb(&_box2));
548
549 let mut _box2 = _box;
550 _box2.offset(Vector3::new(0.0, 0.5, 0.0));
551 assert!(_box.is_intersects_aabb(&_box2));
552 _box2.offset(Vector3::new(0.0, 1.0, 0.0));
553 assert!(!_box.is_intersects_aabb(&_box2));
554
555 let mut _box2 = _box;
556 _box2.offset(Vector3::new(0.0, 0.0, 0.5));
557 assert!(_box.is_intersects_aabb(&_box2));
558 _box2.offset(Vector3::new(0.0, 0.0, 1.0));
559 assert!(!_box.is_intersects_aabb(&_box2));
560 }
561
562 #[test]
563 fn test_aabb_split() {
564 let _box = AxisAlignedBoundingBox::from_radius(1.0);
565 let _boxes = _box.split();
566
567 assert_eq!(_boxes[0].min, Vector3::new(-1.0, -1.0, -1.0));
568 assert_eq!(_boxes[0].max, Vector3::new(0.0, 0.0, 0.0));
569
570 assert_eq!(_boxes[1].min, Vector3::new(0.0, -1.0, -1.0));
571 assert_eq!(_boxes[1].max, Vector3::new(1.0, 0.0, 0.0));
572
573 assert_eq!(_boxes[2].min, Vector3::new(-1.0, -1.0, 0.0));
574 assert_eq!(_boxes[2].max, Vector3::new(0.0, 0.0, 1.0));
575
576 assert_eq!(_boxes[3].min, Vector3::new(0.0, -1.0, 0.0));
577 assert_eq!(_boxes[3].max, Vector3::new(1.0, 0.0, 1.0));
578
579 assert_eq!(_boxes[4].min, Vector3::new(-1.0, 0.0, -1.0));
580 assert_eq!(_boxes[4].max, Vector3::new(0.0, 1.0, 0.0));
581
582 assert_eq!(_boxes[5].min, Vector3::new(0.0, 0.0, -1.0));
583 assert_eq!(_boxes[5].max, Vector3::new(1.0, 1.0, 0.0));
584
585 assert_eq!(_boxes[6].min, Vector3::new(-1.0, 0.0, 0.0));
586 assert_eq!(_boxes[6].max, Vector3::new(0.0, 1.0, 1.0));
587
588 assert_eq!(_boxes[7].min, Vector3::new(0.0, 0.0, 0.0));
589 assert_eq!(_boxes[7].max, Vector3::new(1.0, 1.0, 1.0));
590 }
591
592 #[test]
593 fn test_aabb_projection() {
594 let viewport = Rect::new(0, 0, 1000, 1000);
595 let view_projection = Matrix4::new_perspective(1.0, 90.0f32.to_radians(), 0.025, 1000.0)
596 * Matrix4::look_at_rh(
597 &Default::default(),
598 &Point3::new(0.0, 0.0, 1.0),
599 &Vector3::y_axis(),
600 );
601
602 let aabb = AxisAlignedBoundingBox::unit();
603 let rect = aabb.project(&view_projection, &viewport);
604 assert_eq!(rect.position, Vector2::new(0.0, 0.0));
605 assert_eq!(rect.size, Vector2::new(1000.0, 1000.0));
606
607 let aabb = AxisAlignedBoundingBox::from_min_max(
608 Vector3::new(-0.5, 0.0, -0.5),
609 Vector3::new(0.5, 0.5, 0.5),
610 );
611 let rect = aabb.project(&view_projection, &viewport);
612 assert_eq!(rect.position, Vector2::new(0.0, 0.0));
613 assert_eq!(rect.size, Vector2::new(1000.0, 500.0));
614
615 let aabb = AxisAlignedBoundingBox::from_min_max(
616 Vector3::new(-0.5, 0.25, -0.5),
617 Vector3::new(0.5, 0.5, 0.5),
618 );
619 let rect = aabb.project(&view_projection, &viewport);
620 assert_eq!(rect.position, Vector2::new(0.0, 0.0));
621 assert_eq!(rect.size, Vector2::new(1000.0, 250.0));
622
623 let aabb = AxisAlignedBoundingBox::from_min_max(
624 Vector3::new(-10.0, -10.0, -20.0),
625 Vector3::new(10.0, 10.0, 10.0),
626 );
627 let rect = aabb.project(&view_projection, &viewport);
628 assert_eq!(rect.position, Vector2::new(0.0, 0.0));
629 assert_eq!(rect.size, Vector2::new(1000.0, 1000.0));
630 }
631}