12

大きな静的サイズの長方形を小さな長方形に分割するアルゴリズムが必要です。私にとって完璧な実装は次のようになります。

struct RECT
{
  int l,t,r,b;
};

class BigRect
{
public:
  // width and height of big rect
  BigRect( unsigned width, unsigned height );

  // returns -1 if rect cannot be allocated, otherwise returns id of found rect
  int GetRect( unsigned width, unsigned height, RECT &out );

  // returns allocated rect to big rectangle
  void FreeRect( int id );
};

void test()
{
  BigRect r( 10, 10 );

  RECT out;
  r.GetRect( 4, 4, out ); // rect found ({0,0,4,4} for example), returns 1
  r.GetRect( 5, 5, out ); // rect found ({4,0,9,5} for example), returns 2

  r.GetRect( 6, 6, out ); // no place found for rect, returns -1
  r.FreeRect( 2 );        // add {4,0,9,5} back to rect

  r.GetRect( 6, 6, out ); // rect found (4,0,10,6)
}

GetRectしたがって、FreeRectメソッドのアルゴリズムが必要です。アイデアやリンクをいただければ幸いです。

4

1 に答える 1

7

あなたがしようとしているのは、オンライン 2D ビン パッキングです。大きな絵に詰め込もうとする前に、すべての小さな絵を手元に持っていないため、オンラインです。さらに、いくつかの小さな画像が「割り当て解除」され、それらのスペースが解放されます。一方、オフライン アルゴリズムを使用すると、小さな写真をパックする前に、大きいものから小さいものへと並べ替えることができます。

これは、2D パッキングの最新技術を調査した記事です: 2 次元パッキングに関する調査. かなり理論的です。

この記事A New Upper Bound on 2D Online Bin Packing では、オンライン 2D パッキング アルゴリズムについて説明している他の記事を引用しています。

ゲームの世界の人々は、あなたと同じような問題を抱えています。彼らはそれをテクスチャ パッキングまたはテクスチャ アトラスと呼んでいます。ただし、オフライン アルゴリズムを使用します。

John Ratcliff が、テクスチャ パッキングに関するブログ記事を投稿しました。

gamedev に関するこの関連する質問も参照してください: https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm

于 2011-05-23T15:52:46.053 に答える