将矩形图像数据打包为正方形纹理

Question

我有N项2D图像数据将是矩形的，我想尽可能有效地将它们打包成一个2次方的纹理。

一个简单、低效和幼稚的算法实现来打包这些rects是很容易的，但我相信人们已经想出了算法来尽可能高效地完成这项工作。我已经找到了各种关于光照贴图打包的参考资料，这与我正在寻找的相似，但是光照贴图的算法倾向于将非矩形图像考虑在内，这实际上比我需要的更复杂。

有谁有提示吗？我应该在谷歌上搜索算法或论文作者的名字？

谢谢。

Answer 1

我需要做的正是你所描述的事情。

这是我使用的Python代码，它是Python Cookbook中的一个食谱：

Recipe 442299: pack multiple images of different sizes into one image

Answer 2

你在一维中的问题叫做装箱。也许这对你的搜索是一个好的开始。

注意，你想要解决的问题真的很难(它是NP难的)。所以你不应该去寻找最优解，而应该去寻找一些聪明的启发式算法。

我认为自下而上的动态编程对于1D装箱是可能的，但对于2D情况是不可能的。

你可以通过只解决一维问题来简化你的问题，做一些限制，比如把纹理在一维上切成几个(大小可变的)切片。

另一种可能是在其上运行元启发式优化，如进化算法或粒子群优化。

Answer 3

非常好和简单的打包算法可以在这里找到：http://www.blackpawn.com/texts/lightmaps/

它的实现只需要200行C++代码，不会更多(我想您已经有了位图操作例程)。

关于背后的理论，有Jukka Jylänki的介绍(查找“打包垃圾桶的一千种方法”)。

这篇论文的作者提供了C++库，从我的角度来看，它确实很臃肿，但另一方面，它有很多选择，并且有很好的文档。