Skip to main content

three_rs/math/
box3.rs

1//! Port of `three.js/src/math/Box3.js`.
2
3use crate::core::{BufferAttribute, ObjectRef};
4
5use super::math_utils::{js_max, js_min};
6use super::{Matrix4, Plane, Sphere, Triangle, Vector3};
7
8/// Port of `three.js/src/math/Box3.js`'s `Box3` class: an axis-aligned
9/// bounding box (AABB) in 3D space.
10#[derive(Clone, Copy, Debug, PartialEq)]
11pub struct Box3 {
12    /// The lower boundary of the box.
13    pub min: Vector3,
14    /// The upper boundary of the box.
15    pub max: Vector3,
16}
17
18impl Default for Box3 {
19    /// `new Box3()` — min `(+Infinity, +Infinity, +Infinity)`,
20    /// max `(-Infinity, -Infinity, -Infinity)`.
21    fn default() -> Self {
22        Self {
23            min: Vector3::new(f64::INFINITY, f64::INFINITY, f64::INFINITY),
24            max: Vector3::new(f64::NEG_INFINITY, f64::NEG_INFINITY, f64::NEG_INFINITY),
25        }
26    }
27}
28
29impl Box3 {
30    /// `Box3.isBox3`.
31    pub const IS_BOX3: bool = true;
32
33    /// `new Box3()`.
34    pub const fn new(min: Vector3, max: Vector3) -> Self {
35        Self { min, max }
36    }
37
38    /// `Box3.set()`.
39    pub fn set(&mut self, min: &Vector3, max: &Vector3) -> &mut Self {
40        self.min.copy(min);
41        self.max.copy(max);
42
43        self
44    }
45
46    /// `Box3.setFromArray()`.
47    pub fn set_from_array(&mut self, array: &[f64]) -> &mut Self {
48        self.make_empty();
49
50        let mut vector = Vector3::default();
51
52        let il = array.len();
53        let mut i = 0;
54        while i < il {
55            let point = *vector.from_array(array, i);
56            self.expand_by_point(&point);
57            i += 3;
58        }
59
60        self
61    }
62
63    /// `Box3.setFromBufferAttribute()`.
64    pub fn set_from_buffer_attribute(&mut self, attribute: &BufferAttribute) -> &mut Self {
65        self.make_empty();
66
67        for i in 0..attribute.count() {
68            let point = attribute.get_vector3(i);
69            self.expand_by_point(&point);
70        }
71
72        self
73    }
74
75    /// `Box3.setFromPoints()`.
76    pub fn set_from_points(&mut self, points: &[Vector3]) -> &mut Self {
77        self.make_empty();
78
79        for point in points {
80            self.expand_by_point(point);
81        }
82
83        self
84    }
85
86    /// `Box3.setFromCenterAndSize()`.
87    pub fn set_from_center_and_size(&mut self, center: &Vector3, size: &Vector3) -> &mut Self {
88        let mut vector = Vector3::default();
89        let half_size = *vector.copy(size).multiply_scalar(0.5);
90
91        self.min.copy(center).sub(&half_size);
92        self.max.copy(center).add(&half_size);
93
94        self
95    }
96
97    /// `Box3.setFromObject( object, precise )`: the world-axis-aligned box of a
98    /// scene-graph subtree.
99    ///
100    /// `precise` puts every vertex of every geometry through its node's
101    /// `matrix_world`; the default walks each geometry's own bounding box
102    /// through the same matrix, which is cheaper and can be larger than
103    /// strictly necessary.
104    pub fn set_from_object(&mut self, object: &ObjectRef, precise: bool) -> &mut Self {
105        self.make_empty();
106
107        self.expand_by_object(object, precise)
108    }
109
110    /// `Box3.expandByObject( object, precise )`.
111    ///
112    /// Two divergences from three.js, both because the port has no
113    /// `Object3D.getVertexPosition()` yet: the precise path reads the position
114    /// attribute directly, so it does not apply morph targets or skinning (the
115    /// non-precise path does get morphs, through
116    /// `BufferGeometry::compute_bounding_box()`), and there is no object-level
117    /// `boundingBox` to prefer over the geometry's, since only `SkinnedMesh`
118    /// has one here and it is not a [`Payload`](crate::objects::Payload)
119    /// variant. An `InstancedMesh` takes the conservative path in three.js too.
120    pub fn expand_by_object(&mut self, object: &ObjectRef, precise: bool) -> &mut Self {
121        // Computes the world-axis-aligned bounding box of an object (including
122        // its children), accounting for both the object's, and children's,
123        // world transforms.
124        object.update_world_matrix(false, false);
125
126        // Cloned out of the borrow: the `Rc` is cheap, and the recursion below
127        // must not hold a borrow on the node.
128        let geometry = {
129            let object = object.borrow();
130            object.payload.geometry().cloned()
131        };
132
133        if let Some(geometry) = geometry {
134            let (matrix_world, is_instanced_mesh) = {
135                let object = object.borrow();
136                (object.matrix_world, object.payload.is_instanced_mesh())
137            };
138
139            // precise AABB computation based on vertex data requires at least a
140            // position attribute. instancing isn't supported so far and uses the
141            // normal (conservative) code path.
142            let position = geometry.get_attribute("position");
143
144            match position {
145                Some(position) if precise && !is_instanced_mesh => {
146                    for i in 0..position.count() {
147                        let mut vector = position.get_vector3(i);
148                        vector.apply_matrix4(&matrix_world);
149                        self.expand_by_point(&vector);
150                    }
151                }
152                _ => {
153                    // geometry-level bounding box, computed on demand: the port's
154                    // geometries do not cache one.
155                    if let Some(bounding_box) = geometry.compute_bounding_box() {
156                        let mut box_ = Self::new(bounding_box.min, bounding_box.max);
157                        box_.apply_matrix4(&matrix_world);
158
159                        self.union(&box_);
160                    }
161                }
162            }
163        }
164
165        for child in object.children() {
166            self.expand_by_object(&child, precise);
167        }
168
169        self
170    }
171
172    /// `Box3.copy()`.
173    pub fn copy(&mut self, box_: &Self) -> &mut Self {
174        self.min.copy(&box_.min);
175        self.max.copy(&box_.max);
176
177        self
178    }
179
180    /// `Box3.makeEmpty()`.
181    pub fn make_empty(&mut self) -> &mut Self {
182        self.min.x = f64::INFINITY;
183        self.min.y = f64::INFINITY;
184        self.min.z = f64::INFINITY;
185        self.max.x = f64::NEG_INFINITY;
186        self.max.y = f64::NEG_INFINITY;
187        self.max.z = f64::NEG_INFINITY;
188
189        self
190    }
191
192    /// `Box3.isEmpty()`.
193    pub fn is_empty(&self) -> bool {
194        // this is a more robust check for empty than ( volume <= 0 ) because volume can get positive with two negative axes
195
196        (self.max.x < self.min.x) || (self.max.y < self.min.y) || (self.max.z < self.min.z)
197    }
198
199    /// `Box3.getCenter()`.
200    pub fn get_center(&self) -> Vector3 {
201        let mut target = Vector3::default();
202        if self.is_empty() {
203            *target.set(0.0, 0.0, 0.0)
204        } else {
205            *target
206                .add_vectors(&self.min, &self.max)
207                .multiply_scalar(0.5)
208        }
209    }
210
211    /// `Box3.getSize()`.
212    pub fn get_size(&self) -> Vector3 {
213        let mut target = Vector3::default();
214        if self.is_empty() {
215            *target.set(0.0, 0.0, 0.0)
216        } else {
217            *target.sub_vectors(&self.max, &self.min)
218        }
219    }
220
221    /// `Box3.expandByPoint()`.
222    pub fn expand_by_point(&mut self, point: &Vector3) -> &mut Self {
223        self.min.min(point);
224        self.max.max(point);
225
226        self
227    }
228
229    /// `Box3.expandByVector()`.
230    pub fn expand_by_vector(&mut self, vector: &Vector3) -> &mut Self {
231        self.min.sub(vector);
232        self.max.add(vector);
233
234        self
235    }
236
237    /// `Box3.expandByScalar()`.
238    pub fn expand_by_scalar(&mut self, scalar: f64) -> &mut Self {
239        self.min.add_scalar(-scalar);
240        self.max.add_scalar(scalar);
241
242        self
243    }
244
245    /// `Box3.containsPoint()`.
246    pub fn contains_point(&self, point: &Vector3) -> bool {
247        point.x >= self.min.x
248            && point.x <= self.max.x
249            && point.y >= self.min.y
250            && point.y <= self.max.y
251            && point.z >= self.min.z
252            && point.z <= self.max.z
253    }
254
255    /// `Box3.containsBox()`.
256    pub fn contains_box(&self, box_: &Self) -> bool {
257        self.min.x <= box_.min.x
258            && box_.max.x <= self.max.x
259            && self.min.y <= box_.min.y
260            && box_.max.y <= self.max.y
261            && self.min.z <= box_.min.z
262            && box_.max.z <= self.max.z
263    }
264
265    /// `Box3.getParameter()`.
266    pub fn get_parameter(&self, point: &Vector3) -> Vector3 {
267        // This can potentially have a divide by zero if the box
268        // has a size dimension of 0.
269
270        let mut target = Vector3::default();
271        *target.set(
272            (point.x - self.min.x) / (self.max.x - self.min.x),
273            (point.y - self.min.y) / (self.max.y - self.min.y),
274            (point.z - self.min.z) / (self.max.z - self.min.z),
275        )
276    }
277
278    /// `Box3.intersectsBox()`.
279    pub fn intersects_box(&self, box_: &Self) -> bool {
280        // using 6 splitting planes to rule out intersections.
281        box_.max.x >= self.min.x
282            && box_.min.x <= self.max.x
283            && box_.max.y >= self.min.y
284            && box_.min.y <= self.max.y
285            && box_.max.z >= self.min.z
286            && box_.min.z <= self.max.z
287    }
288
289    /// `Box3.intersectsSphere()`.
290    pub fn intersects_sphere(&self, sphere: &Sphere) -> bool {
291        // Find the point on the AABB closest to the sphere center.
292        let vector = self.clamp_point(&sphere.center);
293
294        // If that point is inside the sphere, the AABB and sphere intersect.
295        vector.distance_to_squared(&sphere.center) <= (sphere.radius * sphere.radius)
296    }
297
298    /// `Box3.intersectsPlane()`.
299    pub fn intersects_plane(&self, plane: &Plane) -> bool {
300        // We compute the minimum and maximum dot product values. If those values
301        // are on the same side (back or front) of the plane, then there is no intersection.
302
303        let mut min;
304        let mut max;
305
306        if plane.normal.x > 0.0 {
307            min = plane.normal.x * self.min.x;
308            max = plane.normal.x * self.max.x;
309        } else {
310            min = plane.normal.x * self.max.x;
311            max = plane.normal.x * self.min.x;
312        }
313
314        if plane.normal.y > 0.0 {
315            min += plane.normal.y * self.min.y;
316            max += plane.normal.y * self.max.y;
317        } else {
318            min += plane.normal.y * self.max.y;
319            max += plane.normal.y * self.min.y;
320        }
321
322        if plane.normal.z > 0.0 {
323            min += plane.normal.z * self.min.z;
324            max += plane.normal.z * self.max.z;
325        } else {
326            min += plane.normal.z * self.max.z;
327            max += plane.normal.z * self.min.z;
328        }
329
330        (min <= -plane.constant) && (max >= -plane.constant)
331    }
332
333    /// `Box3.intersectsTriangle()`.
334    pub fn intersects_triangle(&self, triangle: &Triangle) -> bool {
335        if self.is_empty() {
336            return false;
337        }
338
339        // compute box center and extents
340        let center = self.get_center();
341        let mut extents = Vector3::default();
342        extents.sub_vectors(&self.max, &center);
343
344        // translate triangle to aabb origin
345        let mut v0 = Vector3::default();
346        let mut v1 = Vector3::default();
347        let mut v2 = Vector3::default();
348        v0.sub_vectors(&triangle.a, &center);
349        v1.sub_vectors(&triangle.b, &center);
350        v2.sub_vectors(&triangle.c, &center);
351
352        // compute edge vectors for triangle
353        let mut f0 = Vector3::default();
354        let mut f1 = Vector3::default();
355        let mut f2 = Vector3::default();
356        f0.sub_vectors(&v1, &v0);
357        f1.sub_vectors(&v2, &v1);
358        f2.sub_vectors(&v0, &v2);
359
360        // test against axes that are given by cross product combinations of the edges of the triangle and the edges of the aabb
361        // make an axis testing of each of the 3 sides of the aabb against each of the 3 sides of the triangle = 9 axis of separation
362        // axis_ij = u_i x f_j (u0, u1, u2 = face normals of aabb = x,y,z axes vectors since aabb is axis aligned)
363        let axes = [
364            0.0, -f0.z, f0.y, 0.0, -f1.z, f1.y, 0.0, -f2.z, f2.y, f0.z, 0.0, -f0.x, f1.z, 0.0,
365            -f1.x, f2.z, 0.0, -f2.x, -f0.y, f0.x, 0.0, -f1.y, f1.x, 0.0, -f2.y, f2.x, 0.0,
366        ];
367        if !sat_for_axes(&axes, &v0, &v1, &v2, &extents) {
368            return false;
369        }
370
371        // test 3 face normals from the aabb
372        let axes = [1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0];
373        if !sat_for_axes(&axes, &v0, &v1, &v2, &extents) {
374            return false;
375        }
376
377        // finally testing the face normal of the triangle
378        // use already existing triangle edge vectors here
379        let mut triangle_normal = Vector3::default();
380        triangle_normal.cross_vectors(&f0, &f1);
381        let axes = [triangle_normal.x, triangle_normal.y, triangle_normal.z];
382
383        sat_for_axes(&axes, &v0, &v1, &v2, &extents)
384    }
385
386    /// `Box3.clampPoint()`.
387    pub fn clamp_point(&self, point: &Vector3) -> Vector3 {
388        let mut target = Vector3::default();
389        *target.copy(point).clamp(&self.min, &self.max)
390    }
391
392    /// `Box3.distanceToPoint()`.
393    pub fn distance_to_point(&self, point: &Vector3) -> f64 {
394        self.clamp_point(point).distance_to(point)
395    }
396
397    /// `Box3.getBoundingSphere()`.
398    pub fn get_bounding_sphere(&self) -> Sphere {
399        let mut target = Sphere::default();
400
401        if self.is_empty() {
402            target.make_empty();
403        } else {
404            target.center = self.get_center();
405
406            target.radius = self.get_size().length() * 0.5;
407        }
408
409        target
410    }
411
412    /// `Box3.intersect()`.
413    pub fn intersect(&mut self, box_: &Self) -> &mut Self {
414        self.min.max(&box_.min);
415        self.max.min(&box_.max);
416
417        // ensure that if there is no overlap, the result is fully empty, not slightly empty with non-inf/+inf values that will cause subsequence intersects to erroneously return valid values.
418        if self.is_empty() {
419            self.make_empty();
420        }
421
422        self
423    }
424
425    /// `Box3.union()`.
426    pub fn union(&mut self, box_: &Self) -> &mut Self {
427        self.min.min(&box_.min);
428        self.max.max(&box_.max);
429
430        self
431    }
432
433    /// `Box3.applyMatrix4()`.
434    pub fn apply_matrix4(&mut self, matrix: &Matrix4) -> &mut Self {
435        // transform of empty box is an empty box.
436        if self.is_empty() {
437            return self;
438        }
439
440        let mut points = [Vector3::default(); 8];
441
442        // NOTE: I am using a binary pattern to specify all 2^3 combinations below
443        points[0]
444            .set(self.min.x, self.min.y, self.min.z)
445            .apply_matrix4(matrix); // 000
446        points[1]
447            .set(self.min.x, self.min.y, self.max.z)
448            .apply_matrix4(matrix); // 001
449        points[2]
450            .set(self.min.x, self.max.y, self.min.z)
451            .apply_matrix4(matrix); // 010
452        points[3]
453            .set(self.min.x, self.max.y, self.max.z)
454            .apply_matrix4(matrix); // 011
455        points[4]
456            .set(self.max.x, self.min.y, self.min.z)
457            .apply_matrix4(matrix); // 100
458        points[5]
459            .set(self.max.x, self.min.y, self.max.z)
460            .apply_matrix4(matrix); // 101
461        points[6]
462            .set(self.max.x, self.max.y, self.min.z)
463            .apply_matrix4(matrix); // 110
464        points[7]
465            .set(self.max.x, self.max.y, self.max.z)
466            .apply_matrix4(matrix); // 111
467
468        self.set_from_points(&points);
469
470        self
471    }
472
473    /// `Box3.translate()`.
474    pub fn translate(&mut self, offset: &Vector3) -> &mut Self {
475        self.min.add(offset);
476        self.max.add(offset);
477
478        self
479    }
480
481    /// `Box3.equals()`.
482    pub fn equals(&self, box_: &Self) -> bool {
483        box_.min.equals(&self.min) && box_.max.equals(&self.max)
484    }
485}
486
487/// `Box3.js` module-private `satForAxes()`.
488fn sat_for_axes(axes: &[f64], v0: &Vector3, v1: &Vector3, v2: &Vector3, extents: &Vector3) -> bool {
489    let mut test_axis = Vector3::default();
490
491    let j = axes.len() - 3;
492    let mut i = 0;
493    while i <= j {
494        test_axis.from_array(axes, i);
495        // project the aabb onto the separating axis
496        let r = extents.x * test_axis.x.abs()
497            + extents.y * test_axis.y.abs()
498            + extents.z * test_axis.z.abs();
499        // project all 3 vertices of the triangle onto the separating axis
500        let p0 = v0.dot(&test_axis);
501        let p1 = v1.dot(&test_axis);
502        let p2 = v2.dot(&test_axis);
503        // actual test, basically see if either of the most extreme of the triangle points intersects r
504        if js_max(-js_max(p0, js_max(p1, p2)), js_min(p0, js_min(p1, p2))) > r {
505            // points of the projected triangle are outside the projected half-length of the aabb
506            // the axis is separating and we can exit
507            return false;
508        }
509
510        i += 3;
511    }
512
513    true
514}