Given some AABBs, find minimum total surface area AABBs that contain them all?

Question

I have a number of objects that need to be rendered onto HTML5 canvases. My input is an ordered list of axis-aligned bounding boxes. These boxes often overlap, but also often leave large areas of empty space between them.

I'd like to minimize the amount of canvas surface area I have to create to render all these items in the correct order, while not ever having to render parts of a single object on multiple canvases (thus preventing the easy solution of just creating canvases that tightly fit all of the occupied space).

So basically, I want tight groups of objects to all be rendered on the same canvas, while non-overlapping objects should be rendered on a separate canvas. But not all overlapping objects should be rendered on single canvases--for example, a very tall and very wide object that overlap slightly to form an L should still be rendered on two separate canvases, since combining them results in a lot of wasted canvas space in the open part of the L.

Maintaining Z order also results in some difficult cases. For example, the following image represents one potential arrangement:

In this case, you might want to combine the blue and green layers into a single canvas, but you can't produce correct layering that way without also including the red layer, and you'll end up with a lot of dead space.

But you also can't just limit combining layers to items that are consecutive in the Z order. The Z order might be the same as the above image, but the red item could happen to NOT overlap with the others, and in that case you DO want to combine the blue and green layers.

I'm struggling to come up with a good algorithm for this problem. Anyone care to chime in?

Answer 1

This problem is well known in 3D for building high-performance AABB hierarchies in ray-tracing or collision detection. Try to google for "BVH", "surface area heuristic" and/or "SAH". Section 3.1 of the following paper has a good heuristic algorithm; which should be easy to adapt to your 2D case: http://graphics.stanford.edu/~boulos/papers/togbvh.pdf