多角形の塗りつぶし

(1) ソリッド・エリア・スキャン・コンバージョン (Solid Area Scan Conversion)

この章からはまた図形描画に関するアルゴリズムへ戻り、多角形の塗りつぶしについて紹介します。「塗りつぶし」といっても以前紹介したペイント・ルーチンではなくて、「中身の詰まった多角形を描く」アルゴリズムであるソリッド・エリア・スキャン・コンバージョンを使います。


1) ソリッド・エリア・スキャン・コンバージョンのアルゴリズム

「ソリッド・エリア・スキャン・コンバージョン (Solid Area Scan Conversion)」のアルゴリズムは、図形の輪郭とスキャン・ライン (走査線 ; 画面の横一ライン) の交点を求め、求めた各点の間を水平線分で結ぶ処理を、各スキャン・ラインについて繰り返すことで実現できます (図 1)。あるスキャン・ラインに対して交点がいくつも存在する場合は、x 座標の小さいものから順に二点ずつペアを作り、その二点間を結んでいきます。このため、図形の内側にできる閉じた領域は塗りつぶされません(図 2)。

スキャン・エリア・ライン・コンバージョン
図 1. スキャン・エリア・ライン・コンバージョンのアルゴリズム

塗りつぶされない領域の例(星型)
図 2. 内側にできる閉じた領域の例

このアルゴリズム自体は円のような曲線からなる図形の塗り潰しにも利用することが可能ですが、今回は輪郭が直線だけからなる多角形のみを扱うことにします。この場合、多角形とスキャンラインの交点は、全ての辺とスキャンラインの交点を求めることによって得られます。求めた交点は必ずしも x 座標の小さい順に並んでいるわけではないので、いったんバッファ領域にためておいて、全部そろってからソートする必要があります。

アルゴリズムの大筋は以上のようにシンプルなものですが、実現するにあたっていくつか注意しなければならないことがあります。
まず、輪郭が閉じていない図形では得られる交点の数が奇数になる場所が発生するため、対にならない点が発生して描画結果がおかしくなります。このような場合は最初の点と最後の点をつないで辺を補ってやれば解決します。
しかし、交点の数が奇数になる場合は他にもあります。各辺に対して個別にスキャン・ラインとの交点を求めると、多角形の頂点では多角形がスキャン・ラインと二度交わることになります。下に示した図 3 のような状態では、頂点 A の場合は辺 AB と辺 CA、頂点 B の場合は辺 AB と辺 BC の二辺がスキャン・ラインと交わるため、結果として交点の数は偶数になり問題なく描画できるのに対し、頂点 C を通るときは三辺全てがスキャン・ラインと交わることになり、交点の数は奇数になってしまいます。

交点が奇数になる例
図 3. 交点が奇数になる例

これを回避するには、上下方向に向いていない頂点を交点一つとする必要があります。頂点の方向は、着目している頂点の隣にある頂点との関係から判定することができます。具体的には、今注目している頂点の Y 座標 (仮に Y0 とします) とその隣にある頂点の Y 座標 (これを Y1, Y-1 とします) を比較して、Y0 > Y1 かつ Y0 > Y-1、または Y0 < Y1 かつ Y0 < Y-1 の場合はその頂点は上向きか下向き、そうでなければ左向きか右向きと判定することができます (等しい場合は無視することができます。これについては後述します)。
また、多少不正確になってもよいのであれば、もっと簡単な方法があります。辺の長さを一ピクセル分短く見積もって、片側の端点ではスキャン・ラインと交わらないようにすることで、右向き、左向きの頂点における交点の数は一つとなり、交点の数が奇数になる現象を回避することができます。但し、この方法を使った場合、辺の上側にある端点を省いた場合は上向きの、また辺の下側にある端点を省いた場合は下向きの頂点が欠けてしまいます。

頂点の数以外では水平な線分の扱いにも注意が必要です。
水平な線分はスキャン・ラインと重なってしまうため、他の辺と同じように交点を求めるということはできません。ではどう処理すれば正しいかというと、無視すればいいのです。水平線分は前処理の段階で削ってしまいます。削除してもその辺を挟む辺同士が水平線分で結ばれるため、描画結果には全く影響しません。

水平線分の処理
図 4. 水平線分の扱い

2) 多角形のクリッピング

多角形描画の場合もクリッピング処理は必要です。各辺のクリッピングには、「ライン・ルーチン」で説明した「(2) 線分のクリッピング」と同じ手法が利用できますが、多角形の場合は、クリッピング後の各頂点の前後関係 (どの頂点とどの頂点が辺で結ばれているか) に注意する必要があります。
与えられた頂点が多角形の各辺を形成できるよう順番に並んでいる場合 (例えば辺 AB、辺 BC、辺 CAからなる三角形 ABC において、各頂点が A, B, C の順で並んでいる場合)、並べられた順序でクリッピングを行えば頂点を結ぶ順序が乱れることはありません。下図のように、三角形 ABC を辺 AB, BC, CA の順にクリッピングすると頂点 A, a, b, C が得られ、結果として辺 ab を含む四角形 AabC になります。

クリッピング成功例
図 5. 通常のクリッピング結果

ところが、これだけではうまくいかない場合もあります。
例えば、下図の左側にあるような、クリッピング・エリアの頂点が内部にある三角形 ABC をクリッピングすると、頂点は A, a, b しか得られないため、描画結果は三角形 Aab となり、意図した結果 (クリッピング・エリアの頂点を含む四角形) になりません。さらに、下図右側のような、クリッピングによって多角形 DEFGH が二つ以上に分割される場合は、分割された図形をつなぐ辺 (下図では辺 ab と辺 cd ) が生成されてしまうことになります。

クリッピング失敗例
図 6. クリッピングがうまくできない例

この問題は、クリッピングを二段階に分けることで対処することができます。前処理段階では Y 座標成分についてのみクリッピングを行い、X 座標のクリッピングはスキャン・ラインと多角形との交点を求めてから行うことにより、クリッピング・エリアの頂点が内部にある三角形の場合はきちんとクリッピングされ、二つ以上に分割された場合に生じる意図しない垂直線分も発生しなくなります。水平線分の方はまだ残りますが、前に述べた通り、水平線分は削除されてしまうため問題にはなりません。


以下に、頂点の座標を格納したリストを受け取って、クリッピング処理を行うサンプル・プログラムを示します。

/*****************************************************
 Coord : 座標定義用構造体
*****************************************************/
template<class T> struct Coord
{
  T x;
  T y;

  // コンストラクタ
  Coord( T _x = 0, T _y = 0 ) : x( _x ), y ( _y ) {}

  // 演算子の多重定義
  bool operator==( const Coord& c ) const { return( x == c.x && y == c.y ); }
  bool operator!=( const Coord& c ) const { return( x != c.x || y != c.y ); }
};

typedef vector< Coord<int> > VecCoord; // 座標の配列の型定義

/*
  LineClip : 線分のクリッピング(Y座標のみ)

  const Coord<int> &ip1, &ip2 : クリッピング対象の線分座標
  VecCoord& op : クリッピング後の座標を格納する配列のリファレンス
  const Coord<int>& drawMin : 描画領域の左上座標(最小値)
  const Coord<int>& drawMax : 描画領域の右下座標(最大値)

  ip2 は必ず描画領域の外側になることを想定している
*/
void LineClip( const Coord<int>& ip1, const Coord<int>& ip2, VecCoord& op, const Coord<int>& drawMin, const Coord<int>& drawMax )
{
  // 描画領域と端点との Y 方向の距離を求める
  int dy = ( ip2.y < drawMin.y ) ? drawMin.y - ip1.y : drawMax.y - ip1.y;
  // X 方向の距離に変換した上で、描画領域の端と線分の交点の X 座標を求める
  int x = ( ip2.x - ip1.x ) * dy / ( ip2.y - ip1.y ) + ip1.x;
  // 描画領域の端と線分の交点の Y 座標
  int y = ( ip2.y < drawMin.y ) ? drawMin.y : drawMax.y;

  op.push_back( Coord<int>( x, y ) );
}

/*
  Clipping : クリッピング・ルーチン

  const VecCoord& vertex : クリッピング対象の頂点座標
  VecCoord& clippedVertex : クリッピング後の頂点座標
  const Coord<int>& drawMin : 描画領域の左上座標(最小値)
  const Coord<int>& drawMax : 描画領域の右下座標(最大値)
*/
void Clipping( const VecCoord& vertex, VecCoord& clippedVertex, const Coord<int>& drawMin, const Coord<int>& drawMax )
{
  clippedVertex.clear();
  unsigned int vertexCnt = vertex.size(); // 頂点の数

  for ( unsigned int i = 1 ; i <= vertexCnt ; ++i ) {
    const Coord<int>& c0 = vertex[i-1];           // 始点
    const Coord<int>& c1 = vertex[i % vertexCnt]; // 終点
    if ( c0 == c1 ) continue;
    // 始点がエリア外
    if ( ( c0.y < drawMin.y ) || ( c0.y > drawMax.y ) ) {
      // 終点はエリア内
      if ( ( c1.y >= drawMin.y ) && ( c1.y <= drawMax.y ) ) {
        LineClip( c1, c0, clippedVertex, drawMin, drawMax );
      // 終点もエリア外(クリッピング・エリアの上下境界をまたぐ)
      } else if ( ( ( c0.y < drawMin.y ) && ( c1.y > drawMax.y ) ) ||
                  ( ( c1.y < drawMin.y ) && ( c0.y > drawMax.y ) ) ) {
        LineClip( c1, c0, clippedVertex, drawMin, drawMax );
        LineClip( c0, c1, clippedVertex, drawMin, drawMax );
      }
    // 始点がエリア内
    } else {
      clippedVertex.push_back( c0 );
      // 終点がエリア外ならクリッピングして頂点を追加
      if ( ( c1.y < drawMin.y ) || ( c1.y > drawMax.y ) )
        LineClip( c0, c1, clippedVertex, drawMin, drawMax );
    }
  }
}

Coord は任意の型 T で表現された座標を保持する構造体で x, y をメンバ変数として持ち、その配列 vector< Coord<int> > の型を VecCoord としています。関数 Clipping がクリッピング処理のメイン・ルーチンで、ループ処理の中で、配列 vertex から始点と終点を順番に取得して、その値によって場合分けを行い、関数 LineClip を使ってクリッピングした結果を配列 clippedVertex に登録します。LineClip では、二番目の引数 ip2 がエリア外にあると想定して計算を行っています。従って、始点と終点のどちらもエリア外にある場合は、LineClip を二回呼び出して処理しています。

始点がエリア外の場合、終点がエリア内ならば、クリッピング・エリアの境界と辺との交点は一つのみであり、LineClip を使ってその点だけを登録します。終点もエリア外の場合、始点と終点が両方ともクリッピング・エリアより上側、または下側ならば、それらの頂点を含む辺そのものがエリア外なので無視することができます。しかし、上下の境界をまたぐような場合、辺との交点は二つ発生するため、LineClip を二回呼び出してそれらの交点を登録します。
始点がエリア内ならば、その点を登録した上で、終点がエリア外の時だけクリッピング・エリアの境界と辺との交点を LineClip を使って登録します。終点がエリア内なら、次の処理で登録されることになるので、始点がエリア内外のいずれの場合も終点がエリア内なら登録は不要になります。また、描画する対象が閉曲面となるように、ループの最後の処理で、終点が配列 vertex の先頭の要素になることに注意してください。


<参考文献>
  1. 「X68000マシン語プログラミング <グラフィックス編>」 村田敏幸 著 (ソフトバンク)

◆◇◆更新履歴◆◇◆

◎ サンプルソースにバグがあり、修正を兼ねてかなりの見直しを行いました。結果として、以前のものよりもシンプルな作りとなりました(2012-07-15)。

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