多角形の塗りつぶし

(3) その他の手法

与えられた多角形の描画処理の説明は前回までの内容で全て完了していますので、ここでは、まだ紹介していないその他の手法について説明をしたいと思います。


1) 三角形の描画

任意の多角形を描画するためには、クリッピングや辺の定義、スキャンラインの決定などにおいて細かく注意しながら処理する必要があり、プログラムも複雑なものになりました。しかし、描画する形状を三角形に限定すると、処理を単純にすることが可能になります。任意の多角形は三角形に分割することができるので、三角形に分割する手法があれば、三角形の描画処理を組み合わせて多角形を描画することもできるようになります。立体形状のモデリングでは、通常は三角形や四角形を組み合わせて行われるので、任意の多角形を描画するルーチンは三次元コンピュータグラフィックス (3DCG) ではほとんど利用されないようです。面を組み合わせた立体の表現だけを考慮するのであれば、三角形の描画ができれば充分ということになります。

三角形を描画する場合、辺が交差することがないので、図形の内側に閉じた領域が発生することもありません。スキャンラインと交差する辺も高々二つまでであり、その位置関係も変化しないので、辺のソートを行うことも不要です。水平な辺が存在しなければ、三角形には上向きと下向きの頂点が必ず一つずつあり、残り一つの頂点は左か右のいずれかを向いています。Y 座標方向のクリッピングは上または下向きの頂点を持つ二つの辺だけ行うことになり、X 座標方向のクリッピングは任意の多角形の場合と同様に描画直前で行います。


それでは早速、三角形描画用のサンプル・プログラムを以下に示します。

/*
  TriFill_XDraw : 三角形描画スキャンライン描画

  DrawingArea_IF& draw : 描画領域
  GPixelOp& pset : 点描画に使う関数オブジェクト
  pair<double, double> &l, &r : スキャンラインの両端座標の X 成分と増分の pair
  int& sy : 描画開始 Y 座標(描画終了時に次の Y 座標を返す)
  int ey : 描画終了 Y 座標
*/
void TriFill_XDraw( DrawingArea_IF& draw, GPixelOp& pset, pair<double, double>& l, pair<double,double>& r, int& sy, int ey )
{
  for ( ; sy < ey ; ++sy ) {
    int sx = RoundHalfUp( l.first ); // 描画開始 X 座標
    int ex = RoundHalfUp( r.first ); // 描画終了 X 座標

    // X 座標のクリッピング
    if ( sx < 0 ) sx = 0;
    if ( ex >= draw.size().x ) ex = draw.size().x - 1;

    // スキャンライン描画
    for ( ; sx <= ex ; ++sx )
      pset( draw, Coord<int>( sx, sy ) );

    // X 座標の更新
    l.first += l.second;
    r.first += r.second;
  }
}

/*
  TriFill_Main : 三角形描画用 メイン・ルーチン

  DrawingArea_IF& draw : 描画領域
  GPixelOp& pset : 点描画に使う関数オブジェクト
  Coord<int> &top, &middle, &bottom : 三角形の頂角の座標(上側・中央・下側の順)
*/
void TriFill_Main( DrawingArea_IF& draw, GPixelOp& pset, const Coord<int>& top, const Coord<int>& middle, const Coord<int>& bottom )
{
  // 上側の頂点からの描画開始 X 座標(頂角が描画領域外の場合、異なる座標になる)
  double top_mid_x = top.x; // top - middle
  double top_btm_x = top.x; // top - bottom

  // 上側に水平な辺がある場合は中央の頂点で初期化する
  if ( top.y == middle.y )
    top_mid_x = middle.x;

  int sy = top.y;    // 描画開始 Y 座標
  int my = middle.y; // 中央の頂点の Y 座標
  int ey = bottom.y; // 描画終了 Y 座標

  // クリッピング

  // 上側の頂点が領域外の場合
  if ( top.y < 0 ) {
    sy = 0;
    // 上側から中央への辺をクリッピング
    if ( middle.y >= 0 ) {
      if ( top.y != middle.y )
        top_mid_x = (double)( middle.x - top.x ) * (double)middle.y / (double)( top.y - middle.y ) + (double)middle.x;
    } else {
      if ( middle.y != bottom.y )
        top_mid_x = (double)( bottom.x - middle.x ) * (double)bottom.y / (double)( middle.y - bottom.y ) + (double)bottom.x;
    }
    // 上側から下側への辺をクリッピング
    if ( top.y != bottom.y )
      top_btm_x = (double)( bottom.x - top.x ) * (double)bottom.y / (double)( top.y - bottom.y ) + (double)bottom.x;
  }

  // 下側の頂点が領域外の場合は描画終了 Y 座標を描画領域内にする
  if ( bottom.y >= draw.size().y )
    ey = draw.size().y - 1;

  // X 座標に対する増分
  double top_mid_a = ( middle.y != top.y ) ?
    (double)( middle.x - top.x ) / (double)( middle.y - top.y ) : 0;       // top - middle
  double mid_btm_a = ( middle.y != bottom.y ) ?
    (double)( middle.x - bottom.x ) / (double)( middle.y - bottom.y ) : 0; // middle - bottom
  double top_btm_a = ( top.y != bottom.y ) ?
    (double)( top.x - bottom.x ) / (double)( top.y - bottom.y ) : 0;       // top - bottom

  // 描画開始 X 座標とその増分の pair
  pair<double, double> top_mid( top_mid_x, top_mid_a ); // top - middle
  pair<double, double> top_btm( top_btm_x, top_btm_a ); // top - bottom

  // 中央の頂点が右向きか左向きかを判定して、各辺が左側・右側ののいずれかを決定する
  // 中央の頂点を通る水平線が、上側・下側を通る直線と交わる点の X 座標
  int splitLine_x = ( top.y != bottom.y ) ?
    ( top.x - bottom.x ) * ( middle.y - top.y ) / ( top.y - bottom.y ) + top.x :
    bottom.x; // 中央・下側の Y 座標が等しい場合、下側の X 座標
  pair<double, double>& l = ( middle.x < splitLine_x ) ? top_mid : top_btm; // 左側
  pair<double, double>& r = ( middle.x < splitLine_x ) ? top_btm : top_mid; // 右側

  // 描画開始
  TriFill_XDraw( draw, pset, l, r, sy, my );
  top_mid.second = mid_btm_a;
  TriFill_XDraw( draw, pset, l, r, sy, ey + 1 );
}

/*
  TriFill : 三角形描画用ルーチン 前処理

  DrawingArea_IF& draw : 描画領域
  GPixelOp& pset : 点描画に使う関数オブジェクト
  Coord<int> c1, c2, c3 : 三角形の頂点
*/
void TriFill( DrawingArea_IF& draw, GPixelOp& pset, Coord<int> c1, Coord<int> c2, Coord<int> c3 )
{
  if ( &draw == 0 || &pset == 0 ) return;

  // Y 座標で昇順にソート
  if ( c1.y > c2.y ) std::swap( c1, c2 );
  if ( c1.y > c3.y ) std::swap( c1, c3 );
  if ( c2.y > c3.y ) std::swap( c2, c3 );

  // ポリゴンが描画領域外なら処理しない
  if ( c1.y >= draw.size().y ) return;
  if ( c3.y < 0 ) return;

  // 描画ルーチン メインへ
  TriFill_Main( draw, pset, c1, c2, c3 );
}

TriFill が最初に呼び出される関数で、ここでは描画前の前処理を行なっています。与えられた頂点を Y 座標により並べ替え、描画対象が描画領域内にあることを確認した上でメイン・ルーチンの TriFill_Main を呼び出します。
TriFill_Main では、top, middle, bottom の三つの頂点が与えられていますが、これらがそれぞれ上向き・左右向き・下向きの頂点を表し、Y 座標はこの順で大きくなります。最初に描画を開始する座標値を求め、top, bottom の Y 座標が描画領域外にあればクリッピングを行っています。描画開始する位置は、二辺とも同じ座標 (top) で初期化することになりますが、上側に水平な辺がある場合は描画開始位置は水平な辺の両端 (topmiddle) とする必要があります。

描画開始位置
図 1-1. 描画開始位置の初期化

また、top, bottom だけではなく、middle も描画領域外にある場合もあります。middle が描画領域より上側ならば、領域との交点を求める辺は top - middle ではなく middle - bottom になるので、middle の Y 座標を使って場合分けをしています。なお、描画開始位置は最初の二辺 (top - middle, top - bottom) だけで充分です。スキャンラインが middle の位置まで達した時点で、middle - bottom の描画開始位置は決まるので、増分を切り替えるだけで対応することができます。

クリッピングの位置
図 1-2. クリッピングの位置

描画開始位置と増分は Standard Template Library(STL) の pair 型を使って一つにまとめています。実際の描画は TriFill_XDraw で行いますが、呼び出し時の引数が少なくて済むためです。このとき、bottom が左右のどちらを向いているかによって top - middle - bottomtop - bottom の二つの経路の位置関係が変わるので、それがわかるような形で l, r に参照を代入しています。これをしておかないと、描画時に X 座標の大小関係をチェックして、逆転していれば交換する作業が必要になります。
TriFill_XDraw は、受け取った描画開始座標を元にスキャンライン上の線分を描画して、X 座標を増分だけ更新する処理を繰り返すだけの簡単な処理です。


2) 巻き数 (Winding Number)

スキャンラインによる描画範囲の決定には、多角形の輪郭との交点が使われていました。交点は二つ以上存在する場合もあるので、座標の X 座標を使って並べ替え、二つずつペアとなる交点を取得してその間を描画するというのが前回紹介した方法です。このとき、ペアとなる二点の間は描画されますが、その外側の領域は描画されないので、結果として、内側にできる閉じた領域は描画されないことになります。内側の閉じた領域は、多角形が折りたたまれたような状態になるときに発生しますが、交点のペアが二つ以上あったとき、その間の領域が閉じているのか、開いているのかを判断するためには、全方向に対してスキャンラインとの交点を走査する必要があり、現実的ではありません。

この手法は「Crossing Number Algorithm」または「Even-odd Rule Algorithm」と呼ばれる手法で、日本語に訳せば「交点数アルゴリズム」「偶奇則アルゴリズム」となると思いますが、正式な名称はわかりませんでした。これに対し、「Winding Number」と呼ばれる値を利用する手法もあり、こちらは「Winding Number Algorithm」と呼ばれています。「Winding Number」は「巻き数」と訳されるので、このアルゴリズムは日本語では「巻き数アルゴリズム」となるでしょうか。以降の文章では、英語表記そのままで表していきたいと思います。

Winding Number」がどのようなものかを理解するために簡単な例を紹介します。例えば、陸上競技場のトラックを走っている選手をビデオカメラで撮影するとき、トラックの内部と外部でその挙動は変化します。トラックの内部で撮影する場合、選手の動きを追ってカメラの向く方向を変化させていくと、選手がトラックを一周したときカメラも一回転することになります。ところが、トラックの外部から撮影すると、左右どちらかにカメラの向きをいったん移動させた後、今度は逆方向に向きを移動させ、元の位置に選手が近づくと、また最初と同じ方向へ移動するので、カメラは回転することなく選手を撮影することができます。サーキットのコースのように複雑なパスである場合でも、コースどうしの交差がなくコースが閉じている(スタートとゴールが同じ位置になる)限りはこの状態は成り立ちます。このように、ある点から閉曲線をたどり最初の位置まで戻った時に、その視点が回転した回数を「Winding Number」といい、この値は必ず整数値となります。但し、時計回りに回転する方向を正、逆時計回りの場合を負とするため、「Winding Number」は正負のいずれの値もとる場合があります。先ほどの結果から、交差のない閉曲線の場合、その内部では ±1、外部ではゼロになることがわかります。

単純な円形の軌跡
図 2-1. 単純な円形のコースの場合

コース同士の交差がある場合はどうでしょうか。例えば 8 の字のコースを考えてみます。わかりやすくするため交差した地点からスタートするとして、まずは 8 の字になった二つの円のいずれかの中から視点を動かす場合を考えると、自分を取り囲んでいる円上を見ているときは一回転しますが、もう一方は円を外部から見ている場合と同じ状態になるため回転はしません。よって、この場合は Winding Number は ±1 になります。8 の字コースの外部で観察した場合、円周の時と全く同じ状況なので値はゼロです。

8 の字の軌跡
図 2-2. 8 の字コースの場合

次に、輪ゴムを何重にも棒に巻きつけたような状態を考えます。N 回巻きつけていれば円周は N 個できるので、その中心付近から軌跡をたどっていくと Winding Number は ±N になることが容易に想像できます。それでは、それぞれの円どうしのすき間から軌跡をたどった場合はどうでしょうか。その点よりも中心よりにある円は外側になるので一周してもカウントはされず、そのような円の個数分だけ Winding Number の絶対値は小さくなります。中心付近の領域では、N 個の円が重ねられた状態であると見ることも可能で、Winding Number の絶対値はその重なった数と等しくなります。
例えば、先ほどの 8 の字コースの二つの円のうち小さい方を、大きい側の円の中に収まるように折りたたんだ状態を想像すると、どちらの円も移動する方向は等しいはずなので(輪ゴムをねじって折りたたむことは考えないとします)、その小さい円の中では Winding Number は ±2 であり、それはちょうど二つの円が重なった領域でもあります。大きな円と小さな円の間の領域は、小さな円が外側にあるためカウントされず、Winding Number は ±1 になりますが、その領域は大きな円だけが占める領域になります。もし、小さい方の円が実際には細長く、大きな円と交差する部分ができたとすると、大きな円からはみ出た領域では大きな円が外側にあることになり、やはり Winding Number は ±1 です。このことからも、面の重なった数と Winding Number の絶対値は等しいことが理解できると思います。

二重円の軌跡(回転の向きが同じ)
図 2-3. 二重の円周コースの場合(回転の向きが同じ)

しかし、二つの円を通る方向が逆転していると、それぞれの周回に対する Winding Number の正負は互いに異なることになるので、小さな円の内部の Winding Number はゼロになります。これは、交差しているように見える箇所が実際には交差せず、もう一方の円に移動するとき U ターンしている状況を想定すると、小さな円の内部は実際にはコースの外側になると考えれば納得できます。実際、8 の字にした輪ゴムを折りたたむのでなく平面上でひねって二重にすると、交差していたところが外れて小さな円の内部は閉じた領域ではなくなります。

二重円の軌跡(回転の向きが異なる)
図 2-4. 二重の円周コースの場合(回転の向きが異なる)

回転方向の逆転した二重の円に対し、内側の円を傾けて外側のコースに交差させても、二つの円が重なった部分は Winding Number がゼロで、内側の円のはみ出た部分の Winding Number は ±1 になります。コースを交点で分割してそれぞれの回転角を求めたとき、その総和が Winding Number を表していることを考えると、コースをどのように進んでも、方向が正しく、二回以上同じコースをたどることがない限り Winding Number の値は変化しないので、二つの円を回る ( 下図 A → B → C → D の順 ) のではなく、円が重なっていない二つの領域の周囲それぞれを回る ( 下図 A → D → C → B の順 ) ようにすると、円が重なった部分は領域の外と考えることができます。ここで、二つの円の回転する方向がどちらも時計回りであれば、A → D → C → B ではなく A → C → D → B ( または A → B → D → C ) の順にたどることになり、Winding Number は 2 になります。

二重円の軌跡(回転の向きが異なる場合 2)
図 2-5. 内側の円が外側と交差した場合

コースが複雑になっても、各領域ごとにたどる時の始点やその道筋を変えることで比較的簡単に Winding Number を求めることができます。交差している点がある場合はそれを始点としてたどり、同じ点に戻ってくるまでの道筋の中側に位置していれば、Winding Number は 1 だけ加算または減算されます。これを、全ての道筋に対して行うことで目的の値を求めることができます。
下図の場合、閉じた領域を輪の形にして重ねたような形状をしています。Winding Number は、領域が重なったところで 2 となり、それ以外の領域は 1 となっています。輪の中の部分はコースの外側なので、Winding Number はゼロになります。

複雑なコース (1)
図 2-6. 複雑な図形の Winding Number (1)

コースにねじれがあると、進行方向が逆転して Winding Number の正負が変わる場合があります。そうすると、下図のように領域の内部に Winding Number がゼロとなる部分が発生しますが、たどり方を工夫すれば、ゼロの部分が領域の外側になるようにすることができるのは前に説明したとおりです。実際、下図でもそのような軌跡を決めることができるので、一度試してみてください。

複雑なコース (2)
図 2-7. 複雑な図形の Winding Number (2)

今までの結果から、Winding Number が非ゼロの領域を描画するようにすれば、領域どうしが交差したときに描画できない領域が発生する問題を回避することができます。本当に領域の外側にあれば Winding Number はゼロになるので、周囲をコースで囲まれていたとしても描画されることはありません。しかし、次は Winding Number をどうやって求めるかという問題があります。実際に領域の周囲を移動した時の回転数を求めることは現実的なやり方ではないので、もっと簡単な方法を考える必要があります。

Winding Number を求めたい点を通る任意の直線を一本固定すると、直線と閉領域の辺との交点が存在すれば、その交点が閉領域に接しているのでない限り、必ずペアとなるものが存在します。この考え方は、スキャンラインとの交点を使って描画するときにも利用されています。ある交点から辺をたどって別の交点に達した時、このペアは、片側が上向き( Y 方向の移動がなければ右向き)であれば、もう片側は必ず下向き(または左向き)になるはずです。直線が閉領域内を通過しているのであれば、この領域は直線によって二つに分断され、例えば最初の交点が上向きであれば直線の上側にある部分を進むことになるので、やがて次の交点に達した時には下側の領域に移るはずで、このときは下向きに進んでいなければなりません。直線上を、X 座標値が増加する方向に進んだ時、ある辺との交点に達した段階である閉領域内に入ったことになり、その交点とペアになる点に達した時にその閉領域から出たことになります。閉領域が重なる領域では、それらが同じ進行方向であれば Winding Number の絶対値は大きくなり、異なる方向の場合は打ち消し合ってゼロになる場合もあります。Winding Number がゼロになる領域は、たどり方を変えることで閉領域が重なっているのではなく外側であると判断することが可能であることは前に説明したとおりです。例えば、先ほど紹介した「複雑な図形」のように、閉領域を使って輪を作った時、中央にできる穴の部分はゼロになります。しかし、輪を作った時に発生する重なった部分は、ペアどうしで線を結ぶ「Crossing Number Algorithm」では描画されないのに対し、Winding Number が非ゼロの領域を描画するようにすれば塗りつぶされるようになります。

図 2-8. Crossing Number AlgorithmWinding Number Algorithm の描画の違い
Crossing Number AlgorithmWinding Number Algorithm
Crossing Number Winding Number

直線は任意でいいので、スキャンライン上の交点に対して Winding Number を求め、ゼロになるまでの線分を描画すれば実現ができることになります。辺が上向きと下向きのどちらかを保持しておけばペアとなる交点に対しては必ず逆方向になるので、Winding Number が非ゼロであればその交点を無視する処理を追加するだけで非常に簡単に対応できます。なお、水平な辺では上向き・下向きの判断ができなくなりますが、水平な線分は最初から無視されているため影響はありません。


Winding Number による領域判定処理を組み込んだ描画処理のサンプル・プログラムを以下に示します。

/* 辺の定義 */
struct Edge {
  double x;        // 交点のX座標(初期値は始点のX座標)
  int    y0;       // 始点のY座標
  int    y1;       // 終点のY座標(必ずy0<y1)
  bool   downward; // 始点から終点の方向(下向きのときtrue)
  double a;        // 傾き dX/dY
};

// 辺定義ベクタの型
typedef vector<Edge> VecEdge;

// vector<Edge> 用イテレータの型
typedef VecEdge::iterator itEdge;
typedef VecEdge::const_iterator citEdge;

/*
  DrawLine型 : スキャンラインの描画用関数の型
*/
typedef void (*DrawLineType)( DrawingArea_IF&, GPixelOp&, vector<itEdge>::iterator, vector<itEdge>::iterator, int );

/*
  GenerateEdgeList : 辺リストの生成

  const VecCoord& vertex : 頂点座標
  VecEdge& edgeList : 生成する辺リスト
*/
void GenerateEdgeList( const VecCoord& vertex, VecEdge& edgeList )
{
  edgeList.clear();
  if ( vertex.empty() ) return;
  unsigned int vertexCnt = vertex.size(); // 頂点の個数

  for ( unsigned int i = 0 ; i < vertexCnt ; ++i ) {
    const Coord<int>& c0 = vertex[i]; // 始点
    Coord<int> c1 = vertex[( i + 1 ) % vertexCnt]; // 終点
    if ( c0.y == c1.y ) continue;

    const Coord<int>& c2 = vertex[( i + 2 ) % vertexCnt]; // 終点の次の点

    Edge edge; // 辺データ用バッファ

    edge.downward = c0.y < c1.y;
    edge.x = ( edge.downward ) ? c0.x : c1.x;
    edge.a = (double)( c1.x - c0.x ) / (double)( c1.y - c0.y );

    // 終点が左右向きの場合、終点のY座標をひとつずらす
    if ( ( c1.y - c0.y ) * ( c1.y - c2.y ) < 0 ) {
      if ( edge.downward ) {
        --( c1.y ); // 終点が辺の下側なら上側にずらす
      } else {
        ++( c1.y ); // 終点が辺の上側なら下側にずらす
        edge.x += edge.a; // X座標の初期値を補正する
      }
    }

    edge.y0 = ( edge.downward ) ? c0.y : c1.y;
    edge.y1 = ( edge.downward ) ? c1.y : c0.y;
    edgeList.push_back( edge );
  }
}

/*
  Poly_CN_DrawLine : クリッピング・エリア外の交点をチェックしながらライン描画

  描画領域判定は Crossing Number (Even-Odd) Test を利用

  DrawingArea_IF& draw : 描画領域
  GPixelOp& pset : 点描画に使う関数オブジェクト
  vector<itEdge>::iterator s, e : アクティブな辺リストの開始位置・終了の次の位置
  int y : 描画ラインの Y 座標
*/
void Poly_CN_DrawLine( DrawingArea_IF& draw, GPixelOp& pset, vector<itEdge>::iterator s, vector<itEdge>::iterator e, int y )
{
  for ( vector<itEdge>::iterator i = s + 1 ; i < e ; i += 2 ) {
    int x0 = RoundHalfUp( ( *( i - 1 ) )->x ); // 左端の点の X 座標
    int x1 = RoundHalfUp( ( *i )->x );         // 右端の点の X 座標

      // X座標の更新
      ( *( i - 1 ) )->x += ( *( i - 1 ) )->a;
      ( *i )->x += ( *i )->a;

      // X座標のクリッピング
      if ( x1 < 0 || x0 > draw.size().x - 1 ) continue;
      if ( x0 < 0 ) x0 = 0;
      if ( x1 > draw.size().x - 1 ) x1 = draw.size().x - 1;

      // 直線の描画
      for ( int x = x0 ; x <= x1 ; x++ )
        pset( draw, Coord<int>( x, y ) );
    }
}

/*
  Poly_WN_DrawLine : クリッピング・エリア外の交点をチェックしながらライン描画

  描画領域判定は Winding Number を利用

  DrawingArea_IF& draw : 描画領域
  GPixelOp& pset : 点描画に使う関数オブジェクト
  vector<itEdge>::iterator s, e : アクティブな辺リストの開始位置・終了の次の位置
  int y : 描画ラインの Y 座標
*/
void Poly_WN_DrawLine( DrawingArea_IF& draw, GPixelOp& pset, vector<itEdge>::iterator s, vector<itEdge>::iterator e, int y )
{
  for ( vector<itEdge>::iterator i = s ; i < e ; ) {
    vector<itEdge>::iterator e0 = i; // 描画領域の左端
    unsigned int wn = ( ( *e0 )->downward ) ? 1 : -1;
    for ( ++i ; i < e ; ++i ) {
      wn += ( ( *i )->downward ) ? 1 : -1;
      if ( wn == 0 ) break;
    }
    if ( i == e ) break; // 終端位置が見つからない場合はデータがおかしい

    vector<itEdge>::iterator e1 = i++; // 描画領域の右端
    int x0 = RoundHalfUp( ( *e0 )->x ); // 左端の点の X 座標
    int x1 = RoundHalfUp( ( *e1 )->x ); // 右端の点の X 座標

    // X座標の更新
    for ( vector<itEdge>::iterator j = e0 ; j <= e1 ; ++ j )
      ( *j )->x += ( *j )->a;

    // X座標のクリッピング
    if ( x1 < 0 || x0 > draw.size().x - 1 ) continue;
    if ( x0 < 0 ) x0 = 0;
    if ( x1 > draw.size().x - 1 ) x1 = draw.size().x - 1;

    // 直線の描画
    for ( int x = x0 ; x <= x1 ; x++ )
      pset( draw, Coord<int>( x, y ) );
  }
}

/*
  PolyFill_Group : 多角形描画(「アクティブ」「非アクティブ」の群に分ける方法)

  DrawingArea_IF& draw : 描画領域
  GPixelOp& pset : 点描画に使う関数オブジェクト
  VecEdge& edgeList : 生成する辺リスト
  DrawLine func : スキャンラインの描画用関数
*/
void PolyFill_Group( DrawingArea_IF& draw, GPixelOp& pset, VecEdge& edgeList, DrawLineType func )
{
  if ( &draw == 0 || &pset == 0 ) return;

  vector<VecEdge::iterator> edgeItList( edgeList.size() );
  for ( unsigned int i = 0 ; i < edgeList.size() ; ++i )
    edgeItList[i] = edgeList.begin() + i;

  // activeIndexStart は「非アクティブ」な辺の末尾の次の位置も表す
  unsigned int activeIndexEnd = edgeItList.size(); // 「アクティブ」な辺の末尾の次の位置
  unsigned int activeIndexStart = activeIndexEnd;  // 「アクティブ」な辺の開始位置

  for ( int y = 0 ; y < draw.size().y ; ++y ) {
    // yと始点が一致した「未アクティブ」な辺を「アクティブ」にする
    for ( unsigned int i = activeIndexStart ; i > 0 ; --i ) {
      if ( edgeItList[i - 1]->y0 == y ) {
        itEdge edgeIt = edgeItList[i - 1];
        edgeItList[i - 1] = edgeItList[--activeIndexStart];
        edgeItList[activeIndexStart] = edgeIt;
      }
    }

    // yより点が小さくなった「アクティブ」な辺を削除する
    for ( unsigned int i = activeIndexEnd ; i > activeIndexStart ; --i )
      if ( edgeItList[i - 1]->y1 < y )
        edgeItList[i - 1] = edgeItList[--activeIndexEnd];

    // 交点のソート
    InsertionSort( edgeItList.begin() + activeIndexStart, edgeItList.begin() + activeIndexEnd, CmpByX() );

    // クリッピング・エリア外の交点をチェックしながらライン描画
    (*func)( draw, pset, edgeItList.begin() + activeIndexStart, edgeItList.begin() + activeIndexEnd, y );
  }
}

描画範囲の決め方は、Crossing NumberWinding Number のいずれかを選択できたほうが便利なので、この判定・描画処理を別の関数にして切り替えができるようにします。この関数には、描画領域 draw と描画用関数オブジェクト pset、辺リストの開始・終了位置、Y 座標を渡せばよく、

void (*func)( DrawingArea_IF&, GPixelOp&, vector<itEdge>::iterator, vector<itEdge>::iterator, int )

型の関数ポインタを通して呼び出すようにします。PolyFill_Group は前回紹介したものとほとんど同じ内容ですが、描画範囲を決めて描画する部分は関数を呼び出す形に変更し、その関数ポインタを引数 func で渡すようにしています。

前回同様に、ペアを決めて描画する Crossing Number Algorithm を利用した関数は Poly_CN_DrawLine です。処理内容は全く同じですが、前回は添字を使って交点の要素へアクセスしていたのに対し、今回はイテレータを使って処理しているところが異なります。Winding Number Algorithm を利用した関数は Poly_WN_DrawLine で、辺が上向きか下向きかを、構造体 Edge のメンバ変数 downward で判断しながら Winding Number を更新し、ゼロになったところを終点としています。downward は新たに追加されたメンバ変数なので、辺リストの生成処理用関数 GenerateEdgeList も前回から少しだけ変更をしています。

下図は、先に示した「複雑な図形」を多角形で表して、サンプル・プログラムを使って描画した結果を示しています。領域の重なった部分が、Poly_CN_DrawLine では描画されていないのに対し、Poly_WN_DrawLine では描画されています。重なった部分で表現された形は後者の場合全く見えなくなるので、前述のように、両者の比較方法は場合によって使い分けられた方が便利だと思います。

図 2-9. Poly_CN_DrawLinePoly_WN_DrawLine での描画結果
Poly_CN_DrawLinePoly_WN_DrawLine
Crossing Number Winding Number

<参考文献>
  1. B.Sc.IT - bsc it mumbai university - Myitweb」 - 「Computer Graphics」 - 「solid_area_scan-conversion.pdf
  2. Wikipedia

[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system