ペイント・ルーチン (1)シード・フィルアルゴリズム

ここでは、シード・フィル(seed fill)による閉領域の塗り潰し、いわゆるペイント・ルーチンについて取り上げたいと思います。

シード・フィルアルゴリズムは、以下のような流れになります。

2のステップで見つかるシードの候補は一点だけとは限らないので、見つけたシードの候補は全てどこかに記憶しておく必要があります。そのあたりを考慮してアルゴリズムを練り直すと次のようになります。

新たなシードを決める際には、バッファ中のどのピクセルを選んでもよいのですが、新しい順か、古い順かのどちらかに統一するのが普通でしょう。バッファをスタック構造にすれば新しい順、キューにすれば古い順に自然に決まります。
また、同じピクセルがバッファに二重に格納される場合があり、バッファに格納した段階では未処理のピクセルであったものが、取り出したときにはすでに処理済になっている(塗り潰されている)可能性があるため、バッファから取り出したピクセルは無条件にシードとせずに、今一度シードとしての資格審査にかける必要があります。

さて、上記アルゴリズムはピクセル単位で処理しているためバッファに大量のメモリを必要とします。また、同じピクセルを重複してバッファに格納する確率が高く、その重複分が更にバッファを食い潰して効率を低下させます。
そこで、現実のペイント・ルーチンでは、もっとまとまった単位である水平線分単位で処理するのが一般的です。塗り潰すべきピクセルが横方向に並んでいたらそれらをひとまとめにして、バッファには代表のピクセル一つだけを登録するようにします。この改良版アルゴリズムはスキャンライン・シード・フィルアルゴリズム(Scanline Seed Fill Algorithm)と呼ばれています。

スキャンライン・シード・フィルアルゴリズムの手順を以下に示します。

以下に、スキャンライン・シード・フィルアルゴリズムを使った塗り潰し処理のサンプル・プログラムを示します。

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

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

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

/* 点描画用関数 */
void pset( int x, int y, unsigned int col )
{
  :
}

/* 色コードの取得 */
unsigned int point( int x, int y )
{
  :
}

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

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

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

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

    eIdx->sx = lx - 1;
    eIdx->sy = y;
    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 i;
  unsigned int col = point( x, y ); /* 閉領域の色(領域色) */
  if ( col == paintCol ) return;    /* 領域色と描画色が等しければ処理不要 */

  sIdx = buff;
  eIdx = buff + 1;
  sIdx->sx = x;
  sIdx->sy = y;

  do {
    lx = rx = sIdx->sx;
    ly = sIdx->sy;
    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 )
      scanLine( lx, rx, ly - 1, col );

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

  } while ( sIdx != eIdx );
}

サンプル・プログラムの中で「領域色」と記述された色コードが、塗り潰そうとしている領域の色を表し、変数名 colで表されています。塗り潰すときの色コードは、変数名が paintColとしてあります。
シードの上下にあるラインから次のシードをさがす処理は scanLineで行っています。シード位置(線分の左端)から右方向へラインを走査して、領域色と同じラインが見つかったら、その右端の位置を新たなシードとして登録する処理を繰り返しています。メイン・ルーチンとなる paintでは、シード上にあるラインの描画を行っていますが、描画すべき範囲をチェックする前に、シード位置の色が領域色と等しいかを確認して、そうでなければ処理をスキップしていることに注意してください。領域色と等しくなければ、シード登録後にその位置は処理されたことになるため、処理する必要がなくなります。

1) シード(X,Y)から左右に塗り潰しの境界を探す	2) 線分(X_L,Y)-(X_R,Y)を塗り潰す

3) 線分(X_L,Y-1)-(X_R,Y-1)中の塗り潰すべき範囲を走査してその右端をバッファに登録	4) 線分(X_L,Y+1)-(X_R,Y+1)中の塗り潰すべき範囲を走査してその右端をバッファに登録

5) バッファから*1を取り出し、新たなシードとして処理を繰り返す	6) バッファから*2を取り出し、新たなシードとして処理を繰り返す

7) バッファから*3を取り出し、新たなシードとして処理を繰り返す	8) バッファから*4を取り出し、新たなシードとして処理を繰り返す

ペイント・ルーチン

(1)シード・フィル アルゴリズム

(1)シード・フィルアルゴリズム