为了提供一些背景信息，我有几个 3D 场景中不同对象的光照贴图，我想将它们打包到一个纹理中。光照贴图是方形的并且具有不同的大小，不一定是 2 的幂(尽管如果可以提供更好的解决方案，则可以包括此限制)。生成的纹理的大小是任意的，但应尽可能方形。我必须保持像素完美，不能使用旋转。速度不是问题，这不用于时间紧迫的应用程序。
我找到的基本算法over at GameDev.SE会像这样工作:
- 按区域对光照贴图进行排序，从大开始
- 以光栅扫描顺序浏览输出纹理[固定宽度或根据需要增加]
- 将光照贴图放在第一个可能的位置
- 重复下一个光照贴图直到完成
虽然这听起来合理且易于实现，但我想知道该算法是否适合我的目的，或者是否有更简单的解决方案。特别是，我对以下内容感兴趣:
- 我能否以某种方式利用只有方形的纹理？
- 有没有办法预先计算输出的最佳平方维度？
- 我能否充分利用只有“二次幂”的纹理？
最佳答案
按高度排序的启发式方法仍然有效。即使是这个稍微简单一点的版本也可以工作:按高度排序，从左到右放在相同的 y 上，每次到达右侧时，您都会将 y 增加最大的纹理在这条线上。这样你甚至不必找到一个位置，你已经知道你会把它放在哪里。如果高度变化不大，这种方法效果很好，但可能会很糟糕。
据我所知，没有办法预先计算大小。但是，尝试这样做无论如何都会导致非二次方大小。猜测一个大小(sqrt(总面积)可能四舍五入为 2 的幂)，如果不是所有东西都适合，则将其增加 2 应该可以快速找到最佳大小。
如果您打包的所有东西都是二次方大小，那么您可以做一些更简单的事情。将所有东西都放在堆中，然后尝试将大小相同的 4 个一组放在一起，形成下一个大小的 block 。不会总是有 4 个，这意味着更大的 block 中有一些空白空间。
如果它们不是 2 的幂，这里有一个替代方案可能比按高度排序的技巧更好一些。它要慢得多，而且只打包很多小元素不值得，但我发现当元素的尺寸完全不同时它很有用。它基于区域划分，在这方面它让人想起 KD 树，但事实并非如此(因为这里是关于区域的，没有“点”)。无论如何，你使用一棵树，其中每个内部节点代表一个 split ，奇数级在一个轴上 split ，偶数级在另一个轴上 split 。放置元素时，递归地找到第一个适合它的地方。
这是最基本的事情。我发现首先尝试将它“很好地”安装在某个地方很有用(这样它会创建少于 2 个拆分，因此它在宽度或高度或两者上完全适合某个区域)并且只有在没有这样的地方时，才安顿下来首先，它确实适合。我还发现在节点中存储每个节点“具有”的空闲区域及其“实际矩形”很有用。可以在递归期间计算尺寸和位置，并且区域根本不是必需的，但是将实际的矩形放在那里很方便，并且可以提前跳过太满的空闲区域节点。先按区域反向排序有助于减少被分割一次就永远无法使用的区域(而将小项目放在大项目之后应该没问题)，但它仍然几乎不是最佳选择。
关于image - 将任意正方形包装成矩形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28541498/