ラスタライザを作る人の古文書集ラスタライザを作る人の古文書集SmallWorld3Dを作る際に集めた、ジオメトリエンジン+ラスタライザについての資料をここにまとめておきます。一応ジオメトリエンジンとラスタライザについての説明をしておくと、図1のように頂点の座標変換を行うものがジオメトリエンジン(Geometry Engine)、ベクタグラフィックスを画素の集合（ラスタグラフィックス）に変換するものがラスタライザです。3D対応を謳うビデオカードは、これらをハードウェアで実装しています。
James H. Clark, 1982
ラスタライザの前段のジオメトリエンジンに関する論文です。とはいえハードウェアの話なので、これを見なくても頂点変換のルーチンは書けます。ただ、GPUの開祖として外せないので紹介しておきます。あと、筆者のJim ClarkはこのGeometry Engineのアイデアを実現するためにSillicon Graphicsを起業してそこからOpenGLが生まれWebGLにつながるという点で、Webプログラマーにも多少縁があります。
ClarkのGeometry Engineのユニークな点は、ピック（モデリングソフトでよくあるような、画面上のオブジェクトを選択する機能）をハードウェアでサポートしていることで、CGの描画が高速になるとインタラクティブに使えるようになるんだよ、というアピールをしています。
Juan Pineda, 1988
ラスタライザの実装に関する知識が簡潔にまとまっている資料です。この中で必須となる知識はEdge Functionと呼ばれる関数についてで、これは平面上のある点が三角形の内部にあるかどうかを判定する関数です。
完全な Edge Function の計算方法は
三角形の辺Eが(X, Y)から(X+dx, Y+dy)を結ぶとき E(x, y) = (x - X) * dy - (y - Y) * dx として、 全ての辺について E(x, y) <= 0 なら(x, y)は三角形の内部にある（y軸が下向き、辺が時計回りの場合）ですが、一度どこかの点についてE(x, y)を計算してしまえば
E(x+1, y) = E(x, y) + dy E(x, y+1) = E(x, y) - dx
という計算量の少ない式で、周辺の点についての値を次々と求めて行くことができます。単純な実装例を挙げると、まず三角形を囲むバウンディングボックス（図2の赤枠）の左上で完全なEdge Functionを計算して、後は差分の式を使って右下に向かって走査するというアルゴリズムで三角形の内部を塗り潰すことができます。
SmallWorld3Dでは今のところこのような単純な実装にしていますが、走査点が余白を走らないように工夫する事でさらに最適化が可能です。また、実装によってはEdge Functionを複数箇所で同時に計算して並列処理が可能です。
ポリゴンを描画するとき、頂点の属性（典型的には色、UV座標）を滑らかに変化させながら各ピクセルを描きます。このとき、頂点の属性を頂点間を結ぶ辺上で内挿したもの（属性値の"坂"）はSlopeと呼ばれます。 さらに、2本のSlopeの間にSpan（橋）を架け、この両端の値を内挿することにより、三角形内部の全ての点で内挿値を得ることができます。（図3、図4）
このSlope/Spanの実装を入れればグーローシェーディング付き・テクスチャ無しの描画を行えますが、テクスチャを貼るためにはもう一捻り必要です。テクスチャを貼る時にはテクスチャ座標が必要であり、このテクスチャ座標もSlope/Spanにより生成しますが、貼り付け対象のポリゴンが奥行きを持っている場合、テクスチャ座標に単純な線形補間をすると図5のようにおかしな結果になります。
これを補正する処理はパースペクティブコレクトと呼ばれますが、このパースペクティブコレクトについての資料は意外と少なく、見つけたと思ったらどこかの大学の講義資料で紹介するには気が引ける、という具合でしたが、書籍の形をした資料がありましたのでここに紹介しました。
パースペクティブコレクトの具体的な方法ですが、テクスチャ座標(u, v)をそのまま補間するのではなく、透視変換で出てくる斉次のwを使い
(u/w, v/w, 1/w)
という値を頂点毎に作り、これでSlope/Spanの処理を行います。補間結果を
{ (u/w)' , (v/w)' , (1/w)' }
としたら、(u/w)' および (v/w)' を (1/w)' で割ります（つまり、補間前にwの逆数をとり、補間後にもう一度wをひっくり返します）
cairo等の2D用ラスタライザとDirect3D, OpenGL等の3D用ラスタライザの決定的な違いは、レンダリング時にこの w を受け取るか否かにあります。
図6は、パースペクティブコレクトを適用した描画結果です。
古文書を読まなくても、海外のフォーラムにまとまった情報がありました。 → ラスタライズスレ - uimac実装メモ
とはいえ、ネット上の情報というのは突然消えてしまいます。上のフォーラムも、このページも然りです。もしこのページを気に入っていただけたら、すぐに手元のHDDに保存しましょう。