Texture Atlasの生成

Texture Atlas

1回のレンダリングで利用できるテクスチャの枚数は限られているので、複数のテクスチャを1枚のテクスチャにまとめることは非常に重要です。
この色々なテクスチャをまとめたテクスチャをTexture Atlasと呼びます。
今回はこれの作り方をいくつかメモしておきます。

Knapsack problem

入れ物に可能な限り多くのテクスチャを格納するという観点から考えるとナップサック問題として取り扱えるように思えます。
更にMulti-dimensional knapsack problemの項目を読むと2Dナップサック問題の解法としてIHS (Increasing Height Shelf) algorithmというものが存在しているらしいです。

Increasing Height Shelf

まだ論文をちらっと眺めただけですが、最大の高さのアイテムに合わせたラインにそって並べる方法のように見えます。
下記で実装されている方法がそのような挙動っぽいので下記アルゴリズムとの違いを調査したいところです。

下が揃っているラインを複数段作っていくからShelfなんですね。面白いネーミング。

Skyline Bottom-Left algorithm

https://github.com/nothings/stb/blob/master/stb_rect_pack.h
上記ではSkyline Bottom-Left algorithmを利用しているそうです。