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

Question

我有许多对象需要渲染到 HTML5 Canvas 上。我的输入是轴对齐边界框的有序列表。这些盒子经常重叠，但也经常在它们之间留下大面积的空白空间。

我想尽量减少我必须创建的 Canvas 表面区域的数量，以便以正确的顺序呈现所有这些项目，同时不必在多个 Canvas 上呈现单个对象的部分(从而防止简单的解决方案只需创建适合所有占用空间的 Canvas 即可)。

所以基本上，我希望紧密的对象组全部呈现在同一 Canvas 上，而不重叠的对象应该呈现在单独的 Canvas 上。但并不是所有重叠的对象都应该在单个 Canvas 上渲染——例如，一个非常高和非常宽的对象稍微重叠形成一个 L 仍然应该在两个单独的 Canvas 上渲染，因为将它们组合会导致大量浪费的 Canvas 空间在 L 的开放部分。

维护 Z 顺序也会导致一些困难的情况。例如，下图表示一种可能的排列方式:

在这种情况下，您可能希望将蓝色和绿色层组合到一个 Canvas 中，但是如果不包括红色层，您将无法以这种方式产生正确的分层，并且最终会出现很多死角空间。

但是您也不能只将组合层限制为 Z 顺序中连续的项目。 Z 顺序可能与上图相同，但红色项目可能恰好不与其他项目重叠，在这种情况下，您确实想要组合蓝色和绿色图层。

我正在努力为这个问题想出一个好的算法。有人愿意插话吗？

Answer 1

此问题在 3D 中众所周知，用于在光线追踪或碰撞检测中构建高性能 AABB 层次结构。尝试在谷歌上搜索“BVH”、“表面积启发式”和/或“SAH”。以下论文的第3.1节有一个很好的启发式算法；这应该很容易适应您的 2D 案例:http://graphics.stanford.edu/~boulos/papers/togbvh.pdf