ペイント・ルーチン (2)アルゴリズムの高速化

前章で紹介したサンプル・プログラムは非常にシンプルな実装である反面、無駄な処理が多いため、実行するのにかなりの時間が必要になります。そこでこの章では、無駄な処理を省くことでアルゴリズムの最適化・高速化を行います。

まず、上の図でシードＰから閉領域を塗り潰すとします。シードＰから左右方向に境界を探すとまずは線分 ABが得られます。線分 ABを塗り潰したら、その上下にある CD, EF二つのラインから領域色の部分を探します。線分 CDはそのまま領域色で、線分 EFはその中にある GHの部分が領域色なので、それぞれの代表として右端のシードＤとＨをキューに追加します。これで１ライン分の処理が済んだので、キューから新たなシードを取り出します。ここではシードＤが取り出されたとします。
シードＤから左右方向に境界を検索するとき、左方向はＤからＩまで、右方向はＤからＪまでの範囲を走査することになります。しかし、線分 CD間はすでに走査済みで、領域色であることがすでにわかっているため、この部分の再走査はまるごと無駄になります。よって左方向の走査を左端のＣから行うようにすれば、この無駄を省くことができます。但し、そのためには、上下のラインを走査したときに領域色が連続した部分が見つかったら、右端だけでなく左端もバッファに記憶する必要があります。
走査の結果、線分 IJ間を塗り潰してから、上下のラインの走査を行うところにも同様の無駄があります。初期シードを除けば、上下どちらかのラインは「今のシードをバッファに登録したときの親ライン」が必ずあり、それはすでに「走査済み」であるため再走査の必要はなくなります。今の例では、線分 IJの下側にある捜査範囲 KLのうち、線分 CDの真下にあたる部分 ABの走査が省略できます。但し、ここで捜査範囲 KLは二分されてしまうことに注意する必要があります。また、親が上にあるか下にあるかについての情報も必要になるため、シードをバッファに登録する際に親ラインの Y座標も付け加える必要があります。

実際にどれほどの効果があるかを、例によって試験してみました。1024 X 1024サイズの領域の画像を中央から 100回塗り潰すのに要する時間を、

の三つのパターンで計測したところ、以下のような結果が得られました。計測はそれぞれ、下図のようなテスト用パターンを持つ場合(テストA)とベタの場合(テストB)に分けて行っています(CPU : Intel Pentium4 3.00GHz)。なお、テスト用パターンは、シードを登録するバッファを非常に多く消費します。

パターン	テストA	テストB
1	22.482 (1.00)	14.777 (1.00)
2	20.266 (0.90)	10.989 (0.74)
3	19.828 (0.88)	7.277 (0.49)

ベタの塗り潰しでは、パターン3が最も早いという予想通りの結果になったものの、テスト用パターンを持つ場合は、アルゴリズムの複雑さが災いしてそれほど大きな差はありませんでした。しかし、テスト用パターンはかなり特殊な場合で、通常は、塗り潰しを行う閉領域はほとんどベタの状態であり、全体的に見れば最適化を行ったほうが圧倒的に早くなります。

最適化を行った場合のサンプル・プログラムを以下に示します。

#define MAXSIZE	1024 /* バッファサイズ */

/* 画面サイズは 1024 X 1024 とする */
#define MINX 0
#define MINY 0
#define MAXX 1023
#define MAXY 1023

struct BufStr {
  int lx; /* 領域右端のX座標 */
  int rx; /* 領域右端のX座標 */
  int y;  /* 領域のY座標 */
  int oy; /* 親ラインのY座標 */
};
struct BufStr buff[MAXSIZE]; /* シード登録用バッファ */
struct BufStr *sIdx, *eIdx;  /* buffの先頭・末尾ポインタ */

/*
  scanLine : 線分からシードを探索してバッファに登録する

  int lx, rx : 線分のX座標の範囲
  int y : 線分のY座標
  int oy : 親ラインのY座標
  unsigned int col : 領域色
*/
void scanLine( int lx, int rx, int y, int oy, unsigned int col )
{
  while ( lx <= rx ) {

    /* 非領域色を飛ばす */
    for ( ; lx < rx ; lx++ )
      if ( point( lx, y ) == col ) break;
    if ( point( lx, y ) != col ) break;

    eIdx->lx = lx;

    /* 領域色を飛ばす */
    for ( ; lx <= rx ; lx++ )
      if ( point( lx, y ) != col ) break;

    eIdx->rx = lx - 1;
    eIdx->y = y;
    eIdx->oy = oy;

    if ( ++eIdx == &buff[MAXSIZE] )
      eIdx = buff;
  }
}

/*
  paint : 塗り潰し処理(高速版)

  int x, y : 開始座標
  unsigned int paintCol : 塗り潰す時の色(描画色)
*/
void paint( int x, int y, unsigned int paintCol )
{
  int lx, rx; /* 塗り潰す線分の両端のX座標 */
  int ly;     /* 塗り潰す線分のY座標 */
  int oy;     /* 親ラインのY座標 */
  int i;
  unsigned int col = point( x, y ); /* 閉領域の色(領域色) */
  if ( col == paintCol ) return;    /* 領域色と描画色が等しければ処理不要 */

  sIdx = buff;
  eIdx = buff + 1;
  sIdx->lx = sIdx->rx = x;
  sIdx->y = sIdx->oy = y;

  do {
    lx = sIdx->lx;
    rx = sIdx->rx;
    ly = sIdx->y;
    oy = sIdx->oy;

    int lxsav = lx - 1;
    int rxsav = rx + 1;

    if ( ++sIdx == &buff[MAXSIZE] ) sIdx = buff;

    /* 処理済のシードなら無視 */
    if ( point( lx, ly ) != col )
      continue;

    /* 右方向の境界を探す */
    while ( rx < MAXX ) {
      if ( point( rx + 1, ly ) != col ) break;
      rx++;
    }
    /* 左方向の境界を探す */
    while ( lx > MINX ) {
      if ( point( lx - 1, ly ) != col ) break;
      lx--;
    }
    /* lx-rxの線分を描画 */
    for ( i = lx; i <= rx; i++ ) pset( i, ly, paintCol );

    /* 真上のスキャンラインを走査する */
    if ( ly - 1 >= MINY ) {
      if ( ly - 1 == oy ) {
        scanLine( lx, lxsav, ly - 1, ly, col );
        scanLine( rxsav, rx, ly - 1, ly, col );
      } else {
        scanLine( lx, rx, ly - 1, ly, col );
      }
    }

    /* 真下のスキャンラインを走査する */
    if ( ly + 1 <= MAXY ) {
      if ( ly + 1 == oy ) {
        scanLine( lx, lxsav, ly + 1, ly, col );
        scanLine( rxsav, rx, ly + 1, ly, col );
      } else {
        scanLine( lx, rx, ly + 1, ly, col );
      }
    }

  } while ( sIdx != eIdx );
}