Bounding volumes for primitive shapes

[Jondolf]

What problem does this solve or what need does it fill?

Bounding volumes such as Axis-Aligned Bounding Boxes (AABBs) and bounding spheres are commonly used to speed up broad phase collision detection, spatial queries, and even rendering, and they are also used in Bounding Volume Hierarchies (BVHs). They are very lightweight primitives that can be used for quickly computing intersections.

Primitive shapes were just added in #10466, and it would be very useful to be able to compute bounding volumes for them. This would facilitate the usage of primitive shapes for a lot more things and help unify the engine's APIs.

What solution would you like?

Note: This is just my rough proposal for the API. Details can and should be changed for the final implementation.

Add Aabb2d and Aabb3d primitives:

#[derive(Clone, Copy, Debug)]
pub struct Aabb2d {
    mins: Vec2,
    maxs: Vec2,
}

#[derive(Clone, Copy, Debug)]
pub struct Aabb3d {
    mins: Vec3,
    maxs: Vec3,
}

There could also be bounding spheres/circles:

#[derive(Clone, Copy, Debug)]
pub struct BoundingCircle {
    center: Vec2,
    circle: Circle,
}

#[derive(Clone, Copy, Debug)]
pub struct BoundingSphere {
    center: Vec3,
    sphere: Sphere,
}

(Oriented Bounding Boxes, or OBBs, could also be added, but they are less common)

Notice how these store the actual coordinates too. They will be required pretty much everywhere where bounding volumes are used (e.g. BVHs), so I think it's sensible to include. Feel free to correct me!

There could be a BoundingVolume trait shared by them:

pub trait BoundingVolume {
    type Position: Clone + Copy + PartialEq;

    /// Returns the center of the bounding volume.
    fn center(&self) -> Self::Position;

    /// Computes the surface area of the bounding volume.
    fn area(&self) -> f32;

    /// Checks if this bounding volume intersects another one.
    fn intersects(&self, other: &Self) -> bool;

    /// Checks if this bounding volume contains another one.
    fn contains(&self, other: &Self) -> bool;

    /// Computes the smallest bounding volume that contains both `self` and `other`.
    fn merged(&self, other: &Self) -> Self;

    /// Increases the size of this bounding volume by the given amount.
    fn padded(&self, amount: &Self) -> Self;

    // Note: Not a good name, we should come up with a better one
    /// Decreases the size of this bounding volume by the given amount.
    fn shrunk(&self, amount: &Self) -> Self;
}

Now, each shape primitive should have methods for computing the bounding volumes:

let capsule = Capsule::new(2.0, 0.6);
// AABB from capsule at origin with no rotation
let aabb = capsule.aabb_2d(Vec2::ZERO, 0.0);

These methods could be in traits like Bounded2d and Bounded3d:

pub trait Bounded2d {
    fn aabb_2d(&self, translation: Vec2, rotation: f32) -> Aabb2d;
    fn bounding_circle(&self, translation: Vec2) -> BoundingCircle;
}

pub trait Bounded3d {
    fn aabb_3d(&self, translation: Vec3, rotation: Quat) -> Aabb3d;
    fn bounding_sphere(&self, translation: Vec3) -> BoundingSphere;
}

Potential use cases

These bounding volumes could be used for a wide variety of things:

• Bounding volume hierarchies
• Collision detection (broad phase)
• Raycasting and other spatial queries
• Rendering optimization
• Mesh AABBs
• Probably a lot more

While these are already possible, it is very useful to have a unified set of bounding volumes that can be used for all of them and can be computed from the existing set of primitive shapes.

[NiseVoid]

I've seen people get confused about the name "aabb2d" before because bounding rectangle is the more reasonable term, but I also like the consistent naming between the 2d and 3d variant.

Working with actual coordinates and including the rotation on the aabb function seems like the right call, I'm actually not sure how bevy currently handles that with the aabbs for meshes (maybe @superdump can give us some insights)

I think we might need to split the trait up into two parts:

• A trait to check for intersections
  • This trait would need to take a bounding volume as argument, but allows us to support frustums and raycasting
• A trait to generalize over bounding volumes
  • Useful for spatial datastructures where you want to get the bounding volume that contains both bounding volumes

As for the proposed trait:

• Not a fan of the names expanded/shrinked (especially since the latter sounds wrong)
• We should be able to expand an aabb non-uniformly
• I'm not sure what shrink would be used for
• We need a method to get the area (and maybe volume)
• We need a merge method that gives a bounding volume that contains the two you pass in as arguments
• origin should probably be called center, since the actual origin of the shape could be anywhere

A reference for the methods I use on my bvh's Aabb trait:

    fn center(&self) -> Self::Pos; // Like the proposed origin
    fn area(&self) -> f32;
    fn merge(&self, other: &Self) -> Self; // Gives a volume that contains both aabbs
    fn padded(&self, padding: &Self) -> Self; // Like the proposed expand, but not uniform

and two methods to get intersections with a ray or other aabbs (which should probably be in the other trait)

[Jondolf]

Not a fan of the names expanded/shrinked (especially since the latter sounds wrong)

Yeah I agree, they were just placeholder names. I mainly wanted to avoid Parry's loosened and tightened since I find them to be even more confusing. Padded is quite nice, updated my proposal to use that.

If there is an expansion method, then I feel like it just logically makes sense that there would also be a size reduction method, just not sure what it should be called. For now, I fixed shrinked to shrunk, but using an irregular verb like that is a horrible idea 😂

We should be able to expand an aabb non-uniformly

This should be possible with the trait I proposed, since the associated Sizing type (again, name not ideal) could be a vector. I think I like your approach more though, so I updated my proposal to use that for now.

We need a method to get the area (and maybe volume)

Yep, agreed. This could be on the AABB types themselves though since 2D AABBs don't have volume. Or maybe separate BoundingVolume traits for 2D and 3D?

We need a merge method that gives a bounding volume that contains the two you pass in as arguments

Yup

origin should probably be called center, since the actual origin of the shape could be anywhere

Yup

I updated my rough proposal to match most of the feedback.

[NiseVoid]

Published my BVH, since it might be an interesting reference: https://github.com/NiseVoid/ploc-bvh.

It has this Aabb trait here, I think it's fairly similar to what was proposed, but the proposal here would much more general.

If we do it well data structures like a BVH, and many other things, could just take a generic argument of type BoundingVolume, and some kind of intersection test for traversal like this one. That way we can make things independant of the type of bounding volume (and even dimension) and could easily support additional intersection tests from plugins, and they would work on anything working with this BoundingVolume trait.