isl-org / isl-org/Open3D

Rethinking AxisAlignedBoundingBox

Open
#3,123 2 comments 1 reaction 0 assignees View on GitHub
feature request
Dominant language
C++
Stars
14k
Forks
2.6k
Avg merge
5d 18h
Merged PRs (30d)
6

Description

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.

```c++
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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.