長方形になる N 個の 2D 画像データがあり、それらをできるだけ効率的に 2 のべき乗テクスチャにパックしたいと考えています。
これらの四角形をパックするためのアルゴリズムの単純で非効率的で単純な実装は簡単に作成できますが、人々はこれを可能な限り効率的に行うアルゴリズムを考え出したと確信しています。私が探しているものに似たライトマップ パッキングへのさまざまな参照を見つけましたが、ライト マップのアルゴリズムは非四角形の画像を考慮に入れる傾向があり、実際には必要以上に複雑になっています。
誰にもヒントがありますか？Google で調べるべきアルゴリズムや論文の著者の名前は?
ありがとう。
私はあなたが説明したまさにこのことをする必要がありました。
これは私が使用した Python コードです。Python クックブックのレシピです。
1D の問題は、ビン パッキングと呼ばれます。おそらく、それはあなたの検索の良いスタートです。
解決したい問題は本当に難しいことに注意してください (それは NP 困難です)。したがって、最適解を探すのではなく、巧妙な発見的アルゴリズムを探す必要があります。
ボトムアップの動的計画法は、1D ビン パッキングでは可能ですが、2D ケースでは可能ではないと思います。
テクスチャを 1 次元の複数の (可変サイズの) スライスにカットするなどの制限を設けて、1D 問題のみを解決することで問題を単純化することを考えることができます。
別の可能性は、進化的アルゴリズムや粒子群最適化などのメタヒューリスティック最適化を実行することです。
非常に優れたシンプルなパッキング アルゴリズムがここにあります: http://www.blackpawn.com/texts/lightmaps/
その実装には 200 行の C++ 行しか必要ありません (ビットマップ操作ルーチンは既にあると思います)。
背後にある理論については、Jukka Jylänki による紹介があります (「A Thousand Ways to Pack the Bin」を探してください)。
この論文の著者は C++ ライブラリを提供していますが、これは私の観点からは非常に肥大化していますが、一方で、多くのオプションがあり、非常によく文書化されています。
私も同様の問題を抱えていましたが、正方形を詰めていました。これを試してください：http ：//www.mrashid.info/blog/stacking-squares-problem.php
C ++コードはあまり洗練されていませんが、少なくともこの問題に取り組む方法についての基本的な考え方は理解できます。