Rethinking AxisAlignedBoundingBox

[mattj23]

I've been working on building intersection and collision detection features for Open3D (I wrote the Line3D/Ray3D/Segment3D classes and have been working on triangle intersection and closest point code and a general purpose BVH) and I'm wondering about potentially rethinking the AxisAlignedBoundingBox class.

Axis aligned bounding boxes (AABBs) are a fundamental primitive in accelerating collision detection algorithms, and typically you end up creating a lot of them quickly. In a binary tree implementation of a Bounding Volume Hierarchy, for example, you can end up with 2 AABBs for every primitive. If you're creating a BVH for a triangle mesh that could be 2 AABBs for every face. They're worth it, though, because they can reduce the workload for collision detection by many orders of magnitude even in simple cases.

Open3D's AxisAlignedBoundingBox contains three Eigen::Vector3d (min_bound_, max_bound_, and color_) for a total of nine double values, as well as a handful of enum and a std::string inherited from Geometry through Geometry3D. This means that sizeof(AxisAlignedBoundingBox) on a 64 bit x86 architecture ends up being 96 bytes.

However, an AABB is effectively six values: a min and max scalar value for each cardinal direction, so six doubles or 48 bytes. This means that the Open3D representation is double what it needs to be for functional collision checking.

Obviously there is no point in proposing anything that will break existing user code. However, it seems to me that the core representation of AxisAlignedBoundingBox can be broken out into a separate class.

struct AABB {
  Eigen::Vector3D min_bound_;
  Eigen::Vector3D max_bound_;

  \\ core methods which operate only on min_bound_ and max_bound_
  \\ ...
}

Then AxisAlignedBoundingBox can be made to inherit from both Geometry3D and AABB. Intersection tests and other APIs that don't require non-core features can be pointed at AABB and then users will have the option to use either the very lightweight AABB or the visualizeable AxisAlignedBoundingBox, and existing users of AxisAlignedBoundingBox won't have their code broken.

The 50% size reduction is a significant payoff, otherwise this most likely wouldn't be worth the effort. But in this case the memory and cache performance implications are large and the current number of references to AxisAlignedBoundingBox in the Open3D codebase are still relatively small.

I'm willing to work on a pull request for this, but since it touches existing code the very first step would be covering AxisAlignedBoundingBox with tests (it doesn't seem to be tested currently as far as I can tell). Since that's going to be a lot of effort I'd like to know from a maintainer beforehand that it's something that might be considered before I put time into it. If it's not the direction Open3D wants to go, or if there's some technical issue I'm not aware of, that's perfectly OK too.

I would love to hear people's thoughts and opinions.

[theNded]

Thank you for the suggestions! They are very insightful, and I think it is worth refactorizing. However, Open3D is now shifting to tensor-based geometry, and it might be better to fit the new design in the new API (we don't have a tensor-based AABB now). Do you think it is reasonable to construct AABB from scratch? We can progressively adapt to this in the new API.

[mattj23]

Where would I go about learning how the tensor-based geometry primitives work? I think having a very minimal AABB construct with the new system would be useful, and I'd be willing to work on it, but I don't know anything about how the tensor based constructs are implemented.