前回は、与えられた多角形をクリッピング処理して新たな頂点列を得るところまでを説明しました。この章では、頂点列から辺リストを作成し、スキャン・ラインと辺との交点を算出しながら描画を行う部分について解説します。
辺とスキャン・ラインの交点は、いくつかのやり方で算出することができます。
最も単純で高速化が期待できるのは 3 番目のやり方ですが、このとき増分 a' = dX / dY は必ずしも整数ではないことに注意する必要があります。しかし、現在のプロセッサは浮動少数点演算が非常に遅いなどということはないので、増分の加算を整数演算で行う必要は通常はありません。もし、整数演算を使う場合は x 座標の初期値と増分 a' の両方に同じ定数を掛けて(ゲタ履き)、整数値で計算した後に同じ定数で割って元に戻すといった手法が一般的です(固定小数点演算)。
例えば、 a' = 0.5 ; x 座標の初期値(x0) = 3 のとき、これらのパラメータに定数値 10000 を掛けると、値はそれぞれ 5000, 30000 になります。よって Y が 1 増加したとき、x 座標は a' = 5000ずつ増加すると考えると、x 座標の計算結果は下表のようになります。
Y | 0 | 1 | 2 | 3 | ... |
---|---|---|---|---|---|
X(ゲタ履き) | 30000 | 35000 | 40000 | 45000 | ... |
X(真の値) | 3 | 3 | 4 | 4 | ... |
定数値を乗除する部分は、実際に乗除算をする以外にもビットシフトなどを利用するなどの手段があります(*1-1)。
ところで、全ての辺が常にスキャン・ラインと交わっているわけではないので、交点算出処理は「スキャン・ラインと交差している辺」に対してのみ行う必要があります。スキャン・ラインと交差しているかを各辺に対して処理前に毎回チェックして、交差した辺だけを対象に交点を算出するというのが最も簡単な方法ですが、各辺を「スキャン・ラインと交差した辺(アクティブ)」と「スキャン・ラインと交差していない辺(未アクティブ)」に分類して処理する方法も考えられます。
描画時は、各スキャン・ラインとの交点の X 座標を昇順に並べ替えた上で描画する範囲を決定する必要があります。X 座標の大小関係は各辺が交差しない限り変化しないので、「アクティブ」な辺に対して一度ソートをしておけば、並べ替えの度に発生する要素交換の頻度を下げることができます。描画時に並べ替えが必要な要素数はそれほど多くないので、単純なソート法で、ソート済みの配列に対して処理が早い「挿入ソート(Insertion Sort)」などを使用すれば効果は大きいことが期待できます。
*1-1) 昔のホビー用 PC は浮動小数点演算プロセッサがないものが多く、ソフトウェアでエミュレートする方式を取るものが多かったので、浮動小数点演算 = 遅いという図式が定着してました。そのため、整数の下位ビットを小数部に見立てて計算する手法がよく利用されました。余談ですが、68000 プロセッサには swap という命令があって、指定したデータ・レジスタの上位・下位 16 ビット分 (68000 プロセッサではワードといいます) を交換するのに用いられます。よって、swap を行った後に下位ワードだけを取り出せば、65536( = 216 ) で割った時の商と同じ意味になり、65536 を掛けて整数演算処理後、swap 命令で解を取り出すテクニックがよく使われていました。この時は上位ワードが整数部、下位ワードが小数部の固定小数点演算を行っているということになります。
描画時には複数の辺に対して交点を求めながら処理を行うため、交点算出に必要な各パラメータは処理のあいだ各辺ごとに保持しておく必要があります。このパラメータは以下のような構造体にまとめることにします。
/* 辺の定義 */ struct Edge { double x; // 交点のX座標(初期値は始点のX座標) int y0; // 始点のY座標 int y1; // 終点のY座標(必ずy0<y1) double a; // 傾き dX/dY };
始点と終点の関係は、必ず始点の方が終点より上側 ( すなわち y0 < y1 ) となるようにします。また、x と a は浮動小数点数型 (double) としており、ここでは浮動小数点演算による「増分の加算」を使ってスキャン・ラインと辺の交点を算出することを想定しています。
辺リスト作成ルーチンのコーディング例を以下に示します。
typedef vector< Coord<int> > VecCoord; // 座標の配列の型定義 typedef vector<Edge> VecEdge; // 辺リストの型定義 /* GenerateEdgeList : 辺リストの生成 const VecCoord& clippedVertex : クリッピング後の頂点座標 VecEdge& edgeList : 生成する辺リスト */ void GenerateEdgeList( const VecCoord& clippedVertex, VecEdge& edgeList ) { edgeList.clear(); if ( clippedVertex.empty() ) return; unsigned int vertexCnt = clippedVertex.size(); // 頂点の個数 for ( unsigned int i = 0 ; i < vertexCnt ; ++i ) { const Coord<int>& c0 = clippedVertex[i]; // 始点 Coord<int> c1 = clippedVertex[( i + 1 ) % vertexCnt]; // 終点 if ( c0.y == c1.y ) continue; const Coord<int>& c2 = clippedVertex[( i + 2 ) % vertexCnt]; // 終点の次の点 Edge edge; // 辺データ用バッファ edge.x = ( c1.y > c0.y ) ? 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 ( c1.y > c0.y ) { --( c1.y ); // 終点が辺の下側なら上側にずらす } else { ++( c1.y ); // 終点が辺の上側なら下側にずらす edge.x += edge.a; // X座標の初期値を補正する } } edge.y0 = ( c1.y > c0.y ) ? c0.y : c1.y; edge.y1 = ( c1.y > c0.y ) ? c1.y : c0.y; edgeList.push_back( edge ); } }
「多角形の塗りつぶし (1)ソリッド・エリア・スキャン・コンバージョン (Solid Area Scan Conversion)」の中でも説明したように、頂点が左右を向いている場合、描画領域範囲の端点としてカウントすると、あるスキャン・ライン上の全交点数が奇数となってしまい、正確に描画領域を決めることができなくなります。これを回避するため、終点が左右向きの場合は座標を Y 座標を一つずらす処理を行っています。このとき、終点が辺の上側と下側の場合でシフトする方向が異なることに注意してください。終点が辺の上側ならば Y 座標に 1 を加え、逆に終点が辺の下側なら Y 座標から 1 を引きます。Y 座標を変更するのは必ず終点とすることを原則とするため、このような処理となっています。なお、辺リスト作成前にはまず水平線分かどうかをチェックして、水平線分であった場合は処理をスキップさせています。
まずは、多角形描画のサンプル・プログラムを先に示しておきます。
/* CmpByX : 辺の X 座標による比較関数オブジェクト */ class CmpByX { public: int operator()( VecEdge::const_iterator e0, VecEdge::const_iterator e1 ) const { return( e0->x < e1->x ); } }; /* double型のデータを小数点以下四捨五入してint型として返す double d : 対象データ */ int roundHalfUp( double d ) { if ( d > 0 ) d += 0.5; else d -= 0.5; return( (int)d ); } /* PolyFill_Flag : 多角形描画(アクティブ・非アクティブの判断をフラグで行う) DrawingArea_IF& draw : 描画領域 GPixelOp& pset : 点描画に使う関数オブジェクト VecEdge& edgeList : 生成した辺リスト */ void PolyFill_Flag( DrawingArea_IF& draw, GPixelOp& pset, VecEdge& edgeList ) { unsigned int edgeSize = edgeList.size(); // 辺リストのサイズ vector<int> vec_x( edgeSize ); // X 座標のリスト for ( int y = 0 ; y < draw.size().y ; ++y ) { vector<int>::iterator ep = vec_x.begin(); // 抽出した X 座標の末尾(開始位置で初期化) for ( unsigned int i = 0 ; i < edgeSize ; ++i ) { // アクティブな辺の X 座標を抽出 if ( edgeList[i].y0 <= y && y <= edgeList[i].y1 ) { *ep++ = edgeList[i].x; edgeList[i].x += edgeList[i].a; // X座標の更新 } } // 交点のソート std::sort( vec_x.begin(), ep ); // クリッピング・エリア外の交点をチェックしながらライン描画 for ( vector<int>::iterator sp = vec_x.begin() + 1 ; sp < ep ; sp += 2 ) { int x0 = roundHalfUp( *( sp - 1 ) ); // 左端の点のX座標 int x1 = roundHalfUp( *sp ); // 右端の点のX座標 // 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 : 生成する辺リスト */ void PolyFill_Group( DrawingArea_IF& draw, GPixelOp& pset, VecEdge& edgeList ) { 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 ) { VecEdge::iterator 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]; // 交点のソート std::sort( edgeItList.begin() + activeIndexStart, edgeItList.begin() + activeIndexEnd, CmpByX() ); // クリッピング・エリア外の交点をチェックしながらライン描画 for ( unsigned int i = activeIndexStart + 1 ; i < activeIndexEnd ; i += 2 ) { int x0 = roundHalfUp( edgeItList[i - 1]->x ); // 左端の点のX座標 int x1 = roundHalfUp( edgeItList[i]->x ); // 右端の点のX座標 // X座標の更新 edgeItList[i - 1]->x += edgeItList[i - 1]->a; edgeItList[i]->x += edgeItList[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 ) ); } } }
関数 PolyFill_Flag は、スキャン・ラインと交差したかどうかを各辺ごとに毎回チェックする方式の多角形描画関数です。スキャン・ラインと辺が交差しているかを、現在のスキャン・ラインの Y 座標と辺の端点の Y 座標を比較することで判定し、交差していたら、そのときの交点の X 座標を抽出した上で、次のスキャン・ラインでの X 座標に更新する処理を行います。
PolyFill_Groupは、辺リストを「アクティブ」な群と「未アクティブ」な群に分けて処理する方式を使っています。それぞれの群の間で要素の交換が発生するので、できるだけ交換時の処理時間を短くするために、辺リストの反復子(Iterator)を要素とする新たな可変長配列 edgeItList を用意して、反復子を使って交換処理を行うようにしています。edgeItList には「アクティブ」な群と「非アクティブ」な群が混在し、先頭側に「非アクティブ」な群、末尾側に「アクティブ」な群が並ぶようにします。「アクティブ」な群の先頭の位置は activeIndexStart、末尾の次の位置は activeIndexEnd が保持するので、activeIndexStart は「非アクティブ」な群の末尾の次の位置を表していることにもなります。activeIndexStart, activeIndexEnd はどちらも配列 edgeItList の末尾の要素の次を表すように初期化され、処理前はすべてが「非アクティブ」な状態です。「未アクティブ」な群から「アクティブ」な群へ要素を移す場合は、対象の反復子と activeIndexStart の位置の反復子を交換してから activeIndexStart を一つ前にずらし、「アクティブ」な群から反復子を削除する場合は activeIndexEnd を一つ前にずらしてからその要素を削除対象の場所に上書きします。言葉での説明ではわかりづらいので、下の図を参考にしてください。
交点の X 座標のソート処理には Standard Template Library(STL) の sort アルゴリズムを利用しています。ソートが完了したら、最後にラインを描画するルーチンが残っていますが、描画前に、まだやり残していた X 座標のクリッピングをここで行っています。
描画処理には、点描画を行うための GPixelOp 型関数オブジェクト pset を利用すると想定しています。draw は描画を行う領域 (DrawingArea_IF) を表し、そのメンバ関数 size は領域の大きさを返します。また、pset オブジェクトはメンバ関数 operator() を持ち、これを使って任意の描画領域に対して描画することができます。その引数は
で、描画領域 draw を第一引数で指定し、第二引数の座標 c が点の位置を表しています。
二つの多角形描画ルーチンを使って、頂点数を変化させながら描画速度を計測した結果を以下に示します。計測に利用した PC は CPU が Intel Core i7-2600 3.40GHz (1P/4C) で、Windows7 (64bit) 上で VirtualBox を使って Vine Linux 6 (64bit) を動作させ、その上で実施しています。なお、Vine Linux 上での CPU 数は 1 としています。絶対的な速度は環境によって大きく変化すると思いますので、あくまで参考値程度に考えてください。計測は一つの条件に対して 100 回繰り返し、その平均・最大・最小値・標準偏差を示しています。多角形の描画領域は 512 x 512 の矩形とし、「クリッピングなし」 は描画領域内に必ず収まるように頂点を決め、「クリッピングあり」の場合は描画領域の大きさの半分だけ上下左右に頂点がはみ出すことを許容しているため、( -256, -256 ) - ( 767, 767 ) の範囲に頂点がセットされます。
上に示したグラフは多角形の頂点数に対する描画時間で、左側は頂点数が 1000 まで、右側はさらに 10000 まで増やしたときの様子を表しています。予想に反して、頂点の数が多くなると毎回スキャン・ラインと交差したかをチェックする方が処理時間は短くなるという結果になりました。「アクティブ」「非アクティブ」にグループ化すると、ソート済みの配列に対しては処理時間が短くなるという想定が、std::sort では成り立たない可能性があります。そこで、std::sort の代わりに挿入ソートを実装してみます。挿入ソートは以下のようなコーディングになります。
/* InsertionSort : 挿入ソート・ルーチン Ran first, last : ランダム・アクセス反復子(ソート開始と終了) Less less : 比較用関数オブジェクト */ template<class Ran, class Less> void InsertionSort( Ran first, Ran last, Less less ) { typedef typename Ran::value_type value_type; for ( Ran e = first + 1 ; e < last ; ++e ) { value_type v = *e; // 未ソート列の先頭の要素を取得 bool inserted = false; // v が挿入されたか for ( Ran s = e - 1 ; s >= first ; --s ) { if ( less( v, *s ) ) { *(s + 1) = *s; } else { *(s + 1) = v; inserted = true; break; } } // v が未挿入の場合は先頭に要素を代入 if ( ! inserted ) *first = v; } } template void InsertionSort( vector<VecEdge::iterator>::iterator first, vector<VecEdge::iterator>::iterator last, CmpByX cmpByX ); template void InsertionSort( vector<int>::iterator first, vector<int>::iterator last, std::less<int> less );
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
PolyFill_Group は、ソート方法を変更したことによって描画時間が短くなり、逆に PolyFill_Flag は極端に遅くなってしまいました。挿入ソートは、通常の配列をソートする場合は「遅いソート」の部類に入り、処理時間はデータ量の二乗に比例しますが、ほとんどソート済みの状態である場合は処理時間は極端に短くなります。PolyFill_Group では配列がほとんど「ソート済み」の状態となることから、挿入ソートを利用することは非常に有効なのに対し、PolyFill_Flag に利用するのはかえって逆効果であることがこの結果からもよくわかります。
今度は、PolyFill_Flag に対して処理時間を短縮できないか検討してみます。Standard Template Library(STL) にあるコンテナ・クラスの multiset は、要素をソートされた状態で挿入するので、ソート処理を行う必要がなくなります。multiset を利用した場合のコーディング例を以下に示します。
/* PolyFill_MultiSet : 多角形描画(multisetを利用した場合) DrawingArea_IF& draw : 描画領域 GPixelOp& pset : 点描画に使う関数オブジェクト VecEdge& edgeList : 生成する辺リスト */ void PolyFill_MultiSet( DrawingArea_IF& draw, GPixelOp& pset, VecEdge& edgeList ) { unsigned int edgeSize = edgeList.size(); // 辺リストのサイズ for ( int y = 0 ; y < draw.size().y ; ++y ) { multiset<int> multiset_x; // X 座標のリスト for ( unsigned int i = 0 ; i < edgeSize ; ++i ) { // アクティブな辺の X 座標を抽出 if ( edgeList[i].y0 <= y && y <= edgeList[i].y1 ) { multiset_x.insert( edgeList[i].x ); edgeList[i].x += edgeList[i].a; // X座標の更新 } } // クリッピング・エリア外の交点をチェックしながらライン描画 multiset<int>::iterator sp = multiset_x.begin(); while ( sp != multiset_x.end() ) { int x0 = roundHalfUp( *sp++ ); // 左端の点のX座標 if ( sp == multiset_x.end() ) break; int x1 = roundHalfUp( *sp++ ); // 右端の点のX座標 // 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 ) ); } } }
以下に、multiset を利用した場合の処理時間を示します。グラフの中の比較対象(PolyFill)は、最初に示したプログラム(スキャン・ラインとの交差を毎回チェックし、ソートには std::sort を利用) です。結論としては、std::sort を使って毎回ソートした方が速いという結果になりました。multiset の要素の挿入にはそれなりに時間がかかるということでしょうか。
|
|
なお、multiset は「アクティブ」「非アクティブ」にグループ化する場合には利用できません。要素がソートされるように並べ替えるのは要素を挿入するときのみで、その後に各要素の値が変化しても multiset が自動的に並べ替えてくれるわけではありません。スキャン・ラインとの交点の X 座標は描画時に更新されるので、もし multiset を使うのであれば更新した要素をもう一度挿入しなおすような処理が必要になります。
頂点数の多い多角形に対しても処理時間の増加を抑えることのできるような処理にすることができましたが、通常、描画を行う場合は数百程度もあれば充分だと思います。特に、グラフィック・エディタなどに実装する場合、マウスなどで頂点を指定して多角形を描画することを考えれば数十点程度を指定する程度になるでしょう。また、ゲームなどで利用されるポリゴン描画は三角形を組み合わせて行うのが通常のようです。この場合は立体を画面上に表現する必要があるので、面を三角形の組み合わせで表現する方が処理は単純になります。したがって、今回は、あくまでも任意の多角形を平面上に描画するためということになり、いわゆる 3D 表現には不向きです。
次回は、三角形などの特定の多角形を描画するプログラムや、多角形の内点かどうかを判定する他の手法などを紹介したいと思います。
前に戻る | タイトルに戻る |