0

为了提供一些上下文，我有几个光照贴图，用于 3D 场景中的不同对象，我想将它们打包到一个纹理中。光照贴图是正方形的，并且具有不同的大小，不一定是 2 的幂（尽管可以包括这个限制，如果它可以提供更好的解决方案）。生成的纹理的大小是任意的，但应尽可能为方形。我必须保持像素完美，不能使用旋转。速度不是问题，这不用于对时间要求严格的应用程序。

我在 GameDev.SE找到的基本算法是这样工作的：

  1. 按区域对光照贴图进行排序，从大开始
  2. 以光栅扫描顺序遍历输出纹理[固定宽度或根据需要增加]
  3. 将光照贴图放置在第一个可能的位置
  4. 重复下一个光照贴图，直到完成

虽然这听起来合理且易于实现，但我想知道该算法是否适合我的目的，或者是否有更简单的解决方案。特别是，我对以下内容感兴趣：

  • 我可以以某种方式利用只有方形纹理吗？
  • 有没有办法预先计算输出的最佳方形尺寸？
  • 我可以充分利用只有“二的力量”纹理吗？
4

1 回答 1

1

按高度启发式排序仍然有效。即使是这个稍微简单的版本也可以：按高度排序，从左到右放置在同一个位置y，每次到达右侧时，都会增加y这条线上最大的纹理。这样你甚至不必找一个位置，你已经知道你会把它放在哪里。如果高度变化不大，这很有效，但它可能很糟糕。

据我所知，没有办法事先计算大小。但是，无论如何，尝试这样做会导致非二次方大小。猜测尺寸（sqrt（总面积）可能四舍五入到 2 的幂）并将其增加 2 倍，如果不是所有东西都可以安装的话，应该很快找到最佳尺寸。

如果您要打包的所有东西都是二次方大小，那么您可以做一些更简单的事情。把所有东西都放在一个堆里，并尝试把 4 个大小相等的组放在一起，形成下一个大小的块。不会总是有 4 个，这意味着更大的块中有一些空白空间。

如果它们不是 2 的幂，这里有一个替代方案，它可能比按高度排序的技巧更好。它的速度要慢得多，而且不值得只打包很多小物品，但我发现当物品的尺寸完全不同时它很有用。它基于区域分割，在这方面它让人想起 KD 树，但事实并非如此（因为这里是关于区域的，没有“点”）。无论如何，您使用一棵树，其中每个内部节点都表示一个拆分，奇数层在一个轴上拆分，偶数层在另一个轴上拆分。放置项目时，递归地找到它可以放置的第一个位置。

这是基本的事情。我发现首先尝试将其“很好地”安装在某个地方很有用（这样它会创建少于 2 个拆分，因此它完全适合某个区域的宽度或高度或两者兼而有之），并且只有在没有这样的地方时，才解决首先它确实适合。此外，我发现在节点中存储每个节点“拥有”的空闲区域及其“实际矩形”很有用。可以在递归期间计算尺寸和位置，并且该区域根本不是必需的，但是在此处拥有实际的矩形很方便，并且可以提前跳过太满的空闲区域节点。首先按区域反向排序可以帮助减少被分割一次然后永远不能使用的区域（而将小物品放在大物品之后应该没问题），

于 2015-02-16T15:31:31.487 回答