algorithmgeometrycollision-detectioncomputational-geometrycontainment

Multiple Bounding Boxes containment detection algorithm

Does anyone know of Multiple Bounding Boxes containment detection algorithm (or a implementation references) with the following description:

  1. Lets have collection of Axis Aligned Bounding Boxes, some of them may intersect
  2. and a simple 3D shape, for example a sphere (or it can be another AABB).
  3. I need algorithm that can detect if the shape is fully contained in the AABB-s. In other words no parts of the sphere are outside AABB-s.

The problem is: It is easy to test for a containment in a single AABB, however there is a case where the shape may be split between multiple AABB-s and even a case where it can intersect multiple AABB-s but some parts of sphere are outside.

Solution

  • IMO, you can do that by a sweep-plane approach.

    Sort all AABB by their top and bottom "applicates" (z coordinate). Now consider an horizontal plane that moves from face to face downward, every time updating an active list (i.e. those boxes that meet the plane). A box enters the list on its top face and leaves it on its bottom face.

    The section of the scene by a plane will consist of a set of rectangles and possibly a circle. On every step, the circle needs to be wholly contained in the union of the rectangles.

    Notice that you also need to stop at the plane by the equator (which will not modify the active list), as the sphere is the "largest" there.

    Doing so, you rd the initial problem to a set of 2D containment subproblems with rectangles and circles.

    Following the same principle, you can address the latter by a sweepline technique, sorting the rectangles by ordinates of their top/bottom sides and moving an active list. On every step, the section by an iso-y line defines a set of segments, one per rectangle and possibly one for the circle, and inclusion is easily proven by sorting the bounds on x.

    enter image description here

    Said differently, by the 3D sweep process, you decompose space in prismatic slabs and build the intersections with the sphere. And by the 2D sweep process, you decompose the plane in rectangular slabs and build the intersections with the section disks.