Multiple Bounding Boxes containment detection algorithm

Question

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.

Answer 1

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.

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.

Answer 2

Algebraically this problem can be expressed as a constrained satisfaction problem over the reals. The condition for a point (x,y,z) being inside a circle with center coordinates (cx,cy,cz) and radius r is:

C :=  (x-cx)^2 + (y-cy)^2 + (z-cz)^2 - r^2 <= 0

The condition for a point being inside an AABB is:

B :=  x0 <= x /\ x <= x1 /\ y0 <= x /\ y <= y1 /\ z0 <= z /\ z <= z1

where /\ means 'and' and x0, x1, ..., z1 are real numbers.

Now given a circle and several bounding boxes the question is whether the list of constraints

C /\ !(B1 \/ ... \/ Bn)

can be satisfied. If yes, there is a point inside the sphere but not inside any AABB. Since there are only three variables x,y,z and polynomials of degree of at most 2 existing algorithms/libraries can efficiently solve this problem. (e.g. Z3, see this intro).

Answer 3

Inspired by Yves idea of a recursive sweep-plane algorithm here is a more elaborate version for trying to find a point inside a sphere that is not covered by any of the given boxes.

First we have to find all values of the z-coordinate where full coverage in the corresponding plane can change when moving along the z-axis. This can happen at

• the maximal and minimal z-coordinate of the sphere (i.e. z_center +/- radius)
• the maximal and minimal z-coordinates of all boxes
• the maximal and minimal z-coordinates of all intersection circles/arcs of the sphere with all box faces

Once these z-values are collected, sorted and limited to the z-range of the sphere we have a partition of the z-range of the sphere into intervals. We choose a value inside each z-interval (e.g. the center) to check the coverage in the corresponding plane. Each 2D cutout can be solved analogously to the 3D problem - thus reducing the coverage check to a set of 1D-problems. In the 1D-case we have an interval instead of a sphere or circle and we also have intervals instead of boxes or rectangles. Thus the coverage problem of a sphere against boxes is reduced to a set of trivial coverage problems of one interval against a set of intervals.

An implementation of the main function could look like this:

# if the n-dimensional sphere is not fully covered by the boxes
# find a point inside the sphere but outside the boxes
# by a recursive sweep-plane algorithm.
# center: n-dimensional point
# radius: real value
# boxes: list of n-dimensional boxes (each box is a list of n intervals)
def getUncoveredSphereWitness(center, radius, boxes):
    sphereLimitsN = [center[-1]-radius, center[-1]+radius]
    if len(center) == 1: 
        # 1D case
        witness = getUncoveredIntervalWitness(sphereLimitsN, [box[0] for box in boxes])
        return [witness] if witness is not None else None

    boxLimitsN = sum([b[-1] for b in boxes], [])
    cutLimitsN = getCutLimitsN_boxes(center, radius, boxes)
    limitsN = list(set(sphereLimitsN + boxLimitsN + cutLimitsN))
    limitsN.sort()

    # get centers of relevant intervals
    coordNValsToCheck = []
    for b in limitsN:
        if b > sphereLimitsN[1]: break
        if b > sphereLimitsN[0]:
            coordNValsToCheck.append((bPrev+b)/2.)
        bPrev = b

    for z in coordNValsToCheck:
        # reduce to a problem of with 1 dimension less
        centerN1, radiusN1 = cutSphereN(center, radius, z)
        boxesN1 = cutBoxesN(boxes, z)
        witness = getUncoveredSphereWitness(centerN1, radiusN1, boxesN1)
        if witness is not None:
            return witness+[z] # lift witness to full dimension by appending coordinate

    return None