mieki256's diary

Texture Atlas 用の画像を作成する際、複数の画像を、1枚の画像の中に、詰め込んで配置していく必要があるわけだけど。そのあたりを自動化するにあたって、適したアルゴリズムがあったりしないのかなと検索してみたら、実はかなり難しい問題だったようで。

• 長方形詰込み問題
• 矩形パッキング問題
• フロアプラン問題
• 2次元ビンパッキング問題
• ナップザック問題
• 組合せ最適化

色々な呼び名があるようだけど、まあ、とにかく難しい。 _NP困難 な問題、とされてるそうで。 _Sequence-pair とか、何が何だかさっぱり。

とりあえず、その手の解説ページを読んでいるところ。

以下は妄想。

_フロアプラン問題・手動配置サンプル というページで矩形を動かしているうちに思ったけれど。各画像のサイズでアタリ判定をつけて重ならないようにしてくれるCGツールがあったら、こういう時に役に立つんだろうかと妄想。手作業で配置すること前提の話だけど。

昨今は物理演算なるものがゲーム界隈で流行ってるらしいけど。それを使って詰込みできたりしないのかなと妄想したりもして。摩擦係数の少ない矩形を落としていって、箱を左右に何度か傾けると、収まるべきところに収まってくれる、みたいな。いや、そんなに上手くは行かないか…。

矩形の一つ一つが意志を持って、自分が収まるべき場所を探し続ける光景も妄想。なんだかオブジェクト指向っぽい。時々、小さい矩形がz軸を使ってジャンプして、大きな矩形を飛び越えて隙間に入ったり。

おそらく、どれも、「ソレは○○で実装されてるよ」「ソレは○○法だよ」と言われそうな予感。