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