How to subdivide set of overlapping AABB into non-overlapping set of AABBs?

Question

I have a set of AABBs in 3D. Each AABB keeps track of an index in another array. I would like to find and subdivide these AABBs into smaller AABBs wherever they intersect. Each new AABB created needs to keep track of the union of indices between the different split AABBs. See the 2D image example below:

I would like the 3 overlapping AABBs on the left to become the 9 non-overlapping AABBs on the right.

How would I go about achieving this?

Undersheriff

Do you need to minimize the number of AABBs? (Possible, but on the complicated side.) – Ocker

The easy way is to draw a grid with all x and y coordinates of the boxes, but in this example, you get an extra vertical division for the larger residual AABBs of A and B. – Ocker

Answer 1

Part 1 - Subdividing Intervals

When you restrict the number of dimensions to 1, a box is just an interval. Consider a datastructure called "check_point":

struct check_point {
float value;
bool start; // true if this is the start of an interval, false otherwise.
int id; // The id of the interval that is starting or ending at this value.
}

First convert the start and end points of the 1d interval by their values in an array. Iterate through this array, and every 2 consecutive checkpoints create a new interval. You maintain a set of currently open interval ids while iterating through the check points. Whenever you encounter a 'start' check point, you add the id to the set, and whenever you encounter a 'end' check point, you remove the id from the set. Everytime you create a new interval, you assign the current id-set to the created interval. This looks like the picture below.

Part 2 - Subdividing Boxes

Now let's take the logic from part-1 and adapt it for higher dimensions. First decompose the boxes into x, y and z intervals (just x and y in 2d). If you start with n boxes, you should end up with n each of x-intervals, y-intervals and z-intervals. Apply the algorithm from Part 1 separately for the set of x, y and z intervals, which should give you 3 sets of output intervals.

Now we have to convert these 1d intervals back into boxes.

For a given combination of x,y and z output intervals, you should create a box only if the intersection of the index-sets of all 3 intervals (x, y and z) is not an empty set. You ignore the xyz interval combinations that don't have indices in common. This gives you a set of subdivided boxes.

The picture below demonstrates an example in 2d. The dotted lines show all poossible combinations of x and y intervals. The combinations that are marked with 'x' are ignored because they don't have any indices in common. The combinations that get converted into boxes have a check mark in them. The same logic should also work in 3 or more dimensions.

Note: This algorithm gives you more boxes (smaller in size) than those in your example. But this is more deterministic, without following arbitrary conventions for subdividing boxes. You can always modify the algorithm to create fewer boxes depending on your exact needs. For example, you can walk the grid shown in the second image to merge boxes either along x or y or both.

Pudgy

Answer 2

You can use a sweepline method.

Sort all corner ordinates increasingly. Then consider all pairs of consecutive ordinates, which delimit a slab across the plane. Now in every slab you have a 1D problem, which you solve by sorting the abscissas.

You implement this efficiently using an active list, where the boxes enter and leave. You can keep it sorted by exiting ordinate, and also by left+right abscissas, using binary trees. Then scanning from left to right with an "overlap counter" will tell you when to generate rectangles.

Reclamation

Answer 3

Sort all the corners of rectangles by their y (then x to break ties) coordinates. Process each corner in one iteration.

1. If it's a top-left corner, add the new rectangle into the list and update overlapping status.
2. If it's a top-right corner, remove the current rectangle from the list and update the status.
3. If it's a bottom-left corner, add it to the list.
4. Remove the current rectangle from the list if it's a bottom-right corner.

During the process, you need to maintain the overlapping status of all rectangles in the list.

Dental

Does this work in the 3D case as well? The 2D image was just for illustration. – Visa

Sure, It's a little more complex in 3D case. You need to consider the x, y, and z coordinates. For each cube, there are 8 corners being considered, so there are 8 different cases totally. – Dental