2次元のパッキング問題を近似的に解く

上手い方法を紹介してるページを見つけた&自分で実装してみたので紹介

パッキング問題(2次元)とは

先人の記事
「大きな四角形の中に, いかに効率よく小さな四角形を敷き詰められるか?」を考える問題です.

レンダリングの分野では, テクスチャ一つ一つごとに描画命令を実行していると処理負荷が高くなることがあります.
しかしあらかじめ大きなテクスチャの中に小さなテクスチャを複数書き込んでおけば, 描画命令の実行コストを下げる事ができます.

ソースと実行結果

実行結果はこんな感じになります.

ソースはこちら
理論はいいから実装見せろという人向け.
ランダムに生成した長さの四角形を, 大きな四角形の中に敷き詰めていきます.
画像処理にはCImgを使いました.

アルゴリズム

ここに紹介されている方法を実装しました.
ちょっと長いですが, お付き合いください.
アイデアは「大きな四角形を二分木のようなNodeTreeに分割」することです

ノードは以下のような特徴をもっています.

• 自分の子供へのポインタを2つもつ
• 四角形の領域をもつ
• 使用済かのフラグをもつ

初期化処理

• ルートのノードを一つだけ作成
• ルートのノードの四角形を大きな形状で初期化する

画像を挿入する処理は, 以下のようになります.

1. ルートノードから探索開始
2. ノードのもつ四角形の大きさと, 挿入する画像の大きさを比較する. 不足している場合は探索を終了し, 完全に一致している場合は探索終了. 余っている場合, より挿入画像にフィッティングするように, ノードのもつ四角形を2つに分割し, 新たな子ノードに割り当てる
3. 2で子ノードを作成した場合, 子ノードに移動し, 2と同様の処理をおこなう.

具体例

正直文章だと分かりにくいので, 図で説明します.
初期段階は, ルートノード:Aと大きな四角形のみが与えられていて, ここにオレンジ色の四角形を挿入してみましょう.

挿入画像は現在のノード:Aの四角形領域より小さいですから, よりフィッティングするように四角形を分割しましょう.

分割した2つの四角形にAの子ノード:BとCを割り当てます.

次に, 挿入画像によりフィットする四角形領域をもつノード:Bに移り, 再び四角形の領域を比較しましょう.

しかし, まだノード:Bの四角形の方が挿入画像より大きいので, Bの四角形領域をさらに分割します.

同様に子ノード:DとEを追加しましょう.

ここまで来たら, 分かりますね?
挿入画像によりフィットする四角形領域をもつノード:Dに移動して, 四角形の大きさを比べてみましょう.
今度は挿入画像とノード:Dのもつ四角形領域の大きさが完全に一致したので, この部分に画像を書きこんで, ノード:Dの使用済みフラグをたてておきます.

実際には, 上記探索処理で, 四角形の大きさと使用済みフラグもチェックします.

コード

以上を踏まえた, 疑似コードライクなCPPコードです.
「完全に大きさが合致する四角形」を求めるように, 四角形を二つに分割していくのがミソです.
詳しくはGitHubのコードをご覧ください

class Node
{
  bool mUsed;
  Rect mRect;
  Node* mChildren[2];
}

Node* Node::insert(const Image& img)
{
	if (!isLeaf())
	{
		Node* newNodePtr;
		if (mChildNode[0] != nullptr)
			newNodePtr = mChildNode[0]->insert(img);

		if (newNodePtr != nullptr)
			return newNodePtr;

		return mChildNode[1]->insert(img);
	}
	else
	{
        // 既に使われているNode
		if (mUsed)
			return nullptr;

        // 自分のRectよりサイズが大きい画像は登録できない
		if (!contain(img, mRect))
			return nullptr;
                
        // 自分のRectとサイズが完全に一致したらNodeに登録する
		if (fitPerfect(img, mRect))
		{
			mUsed = true;
			return this;
		}

		mChildNode[0] = new Node();
		mChildNode[1] = new Node();

		const auto dw = mRect.getWidth() - img.width();
		const auto dh = mRect.getHeight() - img.height();
                
        // より小さな四角形に分割する
		if (dw > dh)
		{
			mChildNode[0]->mRect = Rect(mRect.l, mRect.t, mRect.l + img.width() - 1, mRect.b);
			mChildNode[1]->mRect = Rect(mRect.l + img.width(), mRect.t, mRect.r, mRect.b);
		}
		else
		{
			mChildNode[0]->mRect = Rect(mRect.l, mRect.t, mRect.r, mRect.t + img.height() - 1);
			mChildNode[1]->mRect = Rect(mRect.l, mRect.t + img.height(), mRect.r, mRect.b);
		}

		return mChildNode[0]->insert(img);
	}

	return nullptr;
}

課題

一度つめこむ「だけ」なら良いのですが, 使わなくなったノードを「削除」していくと, 使用領域フラグメント化(所々がスカスカ)されていきます.

その場合, 全ての子ノードを削除し, 画像を再挿入するしか無さそうです...