PolygonとScan Line Conversion

スキャンラインコンバージョン

Polygonの塗りつぶし、fillPolygonを作る必要があって勉強した。アルゴリズムは Scan Line Conversion と言うのが定番らしい。
下記サイトがソース付きで参考になる。

Cによる。アルゴリズム解説が大変勉強になる。
http://www2.starcat.ne.jp/~fussy/algo/algo6-1.htm
http://www2.starcat.ne.jp/~fussy/algo/algo6-2.htm
http://www2.starcat.ne.jp/~fussy/algo/algo6-3.htm

Javaによる。Appletですぐに動かせる。
http://nis-lab.is.s.u-tokyo.ac.jp/~koiso/applet/ScanConv/index.html

両サイトのコードともアルゴリズムの基本は同じであるが、データ構造の作り方に差がある。
また、どちらのコードにも一点欠陥があると思われる。

Fussy氏のコードでは頂点で検出した交差辺が奇数になることを防ぐため、交差辺検出の終端を1pixel短く見るようにしている。http://www2.starcat.ne.jp/~fussy/algo/algo6-3.htm の冒頭に氏による説明がある。
ところが、こうすると、ポリゴンの下端がY軸方向に1pixel短く描画されてしまう。X軸と平行な下辺を持つポリゴンを描画すると分かりやすい。

Koiso氏のコードは、X軸と平行な辺に対する対処が不足している為、そのような辺を持つデータを与えると描画がされない。

Fussy氏のコードの場合、GenerateEdgeList 及び PolyFill関数中の下記コードの (a) (A) (B) (C) を、後掲のコードで変更することで、厳密な描画を行うよう修正できる。

(オリジナル抜粋 GenerateEdgeList 関数)

    if ( y != 0 ) {
      Edge->X = ( y > 0 ) ? * ( ApexList - 2 ) << 16 : *ApexList << 16; // (a) を挿入

(オリジナル抜粋 PolyFill 関数)

    /* ｙと終点が一致した「アクティブ」な辺を削除する */
    for ( epp = NonActiveEdgePointer + 1 ; epp <= ActiveEdgePointer ; ) {
      if ( ( *epp )->Y1 == y ) {          // (A) に変更
        *epp = *ActiveEdgePointer;
		*ActiveEdgePointer-- = &eof;
      } else epp++;
    }

    /* 交点のソート */
    InsertSort( NonActiveEdgePointer + 1 , ActiveEdgePointer );
    /* クリッピング・エリア外の交点をチェックしながらライン描画 */
    for ( epp = NonActiveEdgePointer + 1 ; epp < ActiveEdgePointer ; epp += 2 )  	{
      x0 = ((*epp)->X) >> 16;             // (B) に変更
      x1 = ((*(epp+1))->X) >> 16;         // 
      if ( x1 < MINX || x0 > MAXX ) continue;
      if ( x0 < MINX ) x0 = MINX;
      if ( x1 > MAXX ) x1 = MAXX;
      for ( x = x0 ; x <= x1 ; x++ ) pset(x,y,Col);
      /* X座標の更新 */
      (*epp)->X += (*epp)->a;             // (C) に変更
      (*(epp+1))->X += (*(epp+1))->a;     //
    }

(struct EDGBUF)

  short X1;   // メンバを追加

(a)

      Edge->X1 = y > 0 ? *ApexList : *(ApexList - 2);

(PolyFill関数先頭)

    struct EDGBUF* pre = &eof;
    short preX = -1;

(A)

      if ( ( *epp )->Y1 < y ) {

(B)

      struct EDGBUF* e0;
      struct EDGBUF* e1;
      if ((*epp)->X >> 16 == (*(epp + 1))->X >> 16 && (*epp)->Y0 == (*(epp + 1))->Y1){
      	// 交差辺が奇数になる場合、描画済みの辺を外す
      	e0 = (*epp);               //  @ epp+1
      	e1 = (*(epp + 2));         // @ <--
      	epp++;                     //  @ epp 
      }else if (preX == (*epp)->X >> 16 && pre->Y0 == (*epp)->Y1){
      	// 交差辺が奇数になる場合、描画済みの辺を外す
      	epp++;                     //  @ epp
      	e0 = (*epp);               // @ <--
      	e1 = (*(epp + 1));         //  @ pre
      }else if ((*epp)->Y0 == y && (*(epp + 1))->Y0 < y && (*(epp + 1))->Y1 == y){
      	// 閉じた区間が連続する場合、今の区間と次の閉区間を繋げる
      	e0 = (*epp);               // epp+1>@  @   　     epp+1>@
      	e1 = (*(epp + 1));         // --> @O@  @       ->  @O   @
      	e1->X = (*(epp + 2))->X;   // epp>@    @ epp+2     @    @ epp+2
      }else{
      	e0 = (*epp);
      	e1 = (*(epp + 1));
      }
      x0 = (short)((e0->X) >> 16);
      x1 = (short)((e1->X) >> 16);
      pre = e1;
      preX = x1;

(C)

      if (e0->Y1 == y + 1){
      	e0->X = e0->X1 << 16;
      }else{
      	e0->X += e0->a;
      }
      if (e1->Y1 == y + 1){
      	e1->X = e1->X1 << 16;
      }else{
      	e1->X += e1->a;
      }

いずれにせよ、大変有意義な記事とコードを公開して下さっている両氏に感謝したい。

スキャン ライン コンバージョン

スキャンラインコンバージョン