我有 N 项 2D 图像数据，它们将是矩形的，我想尽可能有效地将它们打包成 2 的单次幂纹理。
打包这些矩形的算法的简单非高效和幼稚实现很容易启动，但我相信人们已经提出算法来尽可能有效地执行此操作。我发现了与我正在寻找的类似的光照贴图打包的各种参考，但是光照贴图的算法倾向于考虑非矩形图像，这实际上使事情变得比我需要的更复杂。
有人有提示吗？我应该用谷歌搜索算法或论文作者的名字？
谢谢。
TexturePacker
问问题
18402 次
4 回答
8
于 2008-11-05T04:09:08.097 回答
6
您的一维问题称为装箱。也许这是您搜索的良好开端。
请注意，您要解决的问题非常困难（它是 NP-hard）。所以你不应该寻找最优解，而应该寻找一些聪明的启发式算法。
我认为自下而上的动态编程对于一维装箱是可能的，但对于二维情况则不然。
您可以考虑通过仅解决一维问题来简化您的问题，例如将纹理切割成一维中的多个（可变大小）切片。
另一种可能性是对其进行元启发式优化，例如进化算法或粒子群优化。
于 2008-11-05T00:30:44.577 回答
4
非常好的和简单的打包算法可以在这里找到：http: //www.blackpawn.com/texts/lightmaps/
它的实现只需要 200 行 C++ 行，而不是更多（我想你已经有了位图操作例程）。
对于背后的理论，Jukka Jylänki 进行了介绍（查找“收拾垃圾箱的一千种方法”）。
这篇论文的作者提供的 C++ 库在我看来确实很臃肿，但另一方面，它有很多选择，并且有很好的文档记录。
于 2012-04-26T18:40:30.463 回答
1
我有一个类似的问题，但我正在打包正方形。试试这个：http ://www.mrashid.info/blog/stacking-squares-problem.php
C++ 代码不是很优雅，但至少你对如何解决这个问题有了基本的了解。
于 2012-01-15T02:21:51.887 回答