给定一些AABB,找到包含它们的最小总表面积AABB？

Question

我有许多需要渲染到HTML5画布上的物体.我的输入是轴对齐边界框的有序列表.这些盒子经常重叠,但也常常在它们之间留下大面积的空白区域.

我想最小化我必须创建的画布表面区域的数量,以便以正确的顺序渲染所有这些项目,同时不必在多个画布上渲染单个对象的部分(从而防止仅仅创建画布的简单解决方案)紧紧地适合所有占用的空间).

所以基本上,我希望在同一个画布上渲染紧密的对象组,而非重叠的对象应该在单独的画布上渲染.但并非所有重叠的对象都应该在单个画布上渲染 - 例如,一个非常高且非常宽的对象略微重叠以形成L仍然应该在两个单独的画布上渲染,因为组合它们会导致大量浪费的画布空间在L的开放部分

维持Z顺序也会导致一些困难的情况.例如,下图代表一种可能的安排:

在这种情况下,您可能希望将蓝色和绿色图层组合到一个画布中,但是如果不包括红色图层,则无法以这种方式生成正确的分层,并且最终会产生大量死区.

但是,您也不能将图层组合限制为Z顺序中连续的项目.Z顺序可能与上面的图像相同,但红色项目可能不会与其他项目重叠,在这种情况下,您想要组合蓝色和绿色图层.

我正在努力为这个问题提出一个好的算法.有人关心进来吗？

Answer 1

这是一个简单的建议，可能无法解决某些极端情况，但至少可以部分解决它，并希望提出更好的解决方案：

a = <a z-ordered list of the objects> ;
b = [];
bounds = null;
objects = [];
while ( a.length > 0) {
    c = a.pop();
    if( <c overlaps bounds> && <area of combined canvases> < <area of seperate canvases> || bounds === null) {
         objects.push(c);
         bounds = <union of bounds and c, or bounds of c if bounds is null>;
     } else {
          b.push(c);
     }
     if( a.length === 0) {
          a = b;
          b = [];
          <do something with the current bounds and objects list>
          bounds = null;
          objects = [];
     }
}

在哪里

 < area of combined canvases> = sum( < area of each canvas> ) - sum( <interesections> )
 < area of seperate conavases> = sum( < area of each canvas> )

这不会捕获两个不相交的对象都与一个公共对象相交的情况，但可能可以通过在每次迭代时回顾所有较低 z 顺序的对象来改进这一点。