ラスタライズ

目次

やぁおかえり。今回は三角形が実際にラスタライズされる様子を見ていく──やっとだ！ しかしラスタライズを始める前に、まず三角形セットアップが必要になる。そして三角形セットアップを議論する前に、まず何をセットアップするのかを説明しなければならない。というわけで、まずはハードウェアに優しいラスタライズアルゴリズムについて話そう。

三角形を描画する下手な方法

まず、この村に長くいて最適化されたソフトウェアテクスチャマッパーを自分で書いたことがある人に向けて少し注意事項がある。そういった人はおそらく三角形のラスタライズを様々な処理を一度に行う巨大な処理と捉えることに慣れているだろう: 三角形の形状のトレース、\(u\), \(v\) の補間 (透視的に正しくするなら \(u/z\), \(v/z\), \(1/z\) の補間)、Z バッファテスト (透視的に正しいマッピングでは代わりに \(1/z\) バッファを使ったテスト)、そして実際のテクスチャリングおよびシェーディング、こういった処理を全て細心の注意を払ってスケジュールした一つの大きなループで、おそらくは利用可能なレジスタを全て使って実行したはずだ。私の言っていることが分かるだろう？ だが、今はそれを忘れてほしい。これはハードウェアだ。ハードウェアでは設計とテストを個別に行えるよう機能を小さくて小奇麗なモジュールにパッケージ化する。ハードウェアにおける「三角形ラスタライザ」は三角形が被覆する (サブ) ピクセルを伝えるブロックである。場合によっては三角形に含まれるピクセルの座標を重心座標系で返したりもするが、それで終わりだ。\(u\) や \(v\) は出てこない──\(1/z\) も、テクスチャやシェーディングも存在しない。最後の二つに関しては専用のテクスチャユニットとシェーダーユニットが存在するので、驚くことでもないだろう。

次に、もし "昔に" 三角形マッパーを自分で書いたことがあるなら、Chris Hecker の透視テクスチャマッピングに関するシリーズで説明されるようなインクリメンタルなスキャンラインラスタライザを使ったはずだ。これは SIMD ユニットを持たないプロセッサでは高速だが、高速な SIMD ユニットを持つ現代的なプロセッサとは相性が悪く、ハードウェアとはさらに悪い──誰も試さなくなったというわけではないが。具体的に言うと、そこの角に立って平静を保とうと大変な努力をしている、とある古いゲームコンソールは、スクリーンの下と右の辺に対するガードバンドクリッピングは非常に高速だが、上と左の辺に対してはそうでもなかった (これは、友よ、"テル癖" というやつである)。なに、言ってみただけだ。

ではスキャンラインアルゴリズムの何がハードウェアにとって不都合なのか？ まず、ラスタライズが厳密にスキャンラインごとに行われる点がある。ピクセルシェーダーを説明するときすぐに明らかになる理由により、ラスタライザは 2x2 のピクセルをまとめて出力するのが望ましい (この 2x2 のピクセルは「クアッド (quad)」と呼ばれる──パイプラインのこのステージで三角形の組に分解される「クアッド」プリミティブと混同しないように注意)。しかし、この要件はスキャンラインアルゴリズムと全く噛み合わない。このアルゴリズムの "インスタンス" を二つ並列に実行しなければならないだけではなく、二つのインスタンスからの出力はそれぞれのスキャンラインがプリミティブと接触する最初の点から始まるので、遠く離れている可能性もあり、望まれる 2x2 のクアッドが次々と生成されることはない。またスキャンラインアルゴリズムは x 方向と y 方向に対称でないので、効率的に並列化するのも難しい──幅が 8 ピクセルで高さが 100 ピクセルの三角形と幅が 100 ピクセルで高さが 8 ピクセルの三角形では、負荷がかかるラスタライザの部分が大きく異なる。このときボトルネックを避けるには "x" と "y" が "ループ" を同じ速度で進まなくてはならないが、実際の処理があるのは "y" のステップだけで、"x" のループには自明な処理しかない！ 言った通り、厄介だ。

より優れた方法

三角形をラスタライズするこれよりずっと単純な (そしてハードウェアにもより優しい) 方法は 1988 年に Pineda による論文で発表された。一般的なアプローチは二つの文で説明できる: 点から直線への符号付き距離は二次元の内積 (と加算) で計算できる──点から平面への距離が三次元の内積 (と加算) で計算できるのと同様だ。すると三角形の内部は、三つの辺の全てに対して正しい側にある点の集合として定義できる。つまり...判定したいピクセルをループして、それぞれが三角形の内部にあるかどうかを判定すればよい。それだけだ。これが基本的なアルゴリズムである。

ピクセルを (例えば) 右に移動するとき、\(X\) には \(1\) が加算され、\(Y\) はそのままとなる。また辺と直線の符号付き距離を表す方程式は \(E(X,Y) = aX + bY + c\) という形をしている (\(a\), \(b\), \(c\) は辺ごとに定まる定数)。言い換えると、適当なピクセルでこの方程式の値を計算すれば、隣接するピクセルに対する値は数回の加算で計算できる。このアルゴリズムが完全に自明な形で並列化できる点にも注目してほしい: 例えば 8x8 = 64 ピクセルを同時にラスタライズしたいとしよう。これは AMD のハードウェアが好きな値だ (Real-Time Rendering によると、少なくとも Xbox 360 はこの値を使っている)。このとき、まず三角形の辺それぞれに対して \(ia + jb\) (\(0 \leq i, j \leq 7\)) を計算し、レジスタに保存する。すると 8x8 のピクセルブロックをラスタライズするときは、左上の角のピクセルに対する三つの辺の式を計算し、先ほど計算してレジスタに保存した定数の加算を 8x8 で並列に行い、最終的な結果の符号ビットを見れば 8x8 の各ピクセルが辺の外側か内側かを判定できる。この判定を三つの辺に対して行えば、なんと、8x8 のピクセルブロックのラスタライズを全くあきれるほど並列な形で行うことができ、その複雑さは整数加算が何度かある程度となる！ ところで、前章で頂点座標を固定小数点の格子にスナップした理由はここにある──ここで整数算術を使うためだ。整数加算器は浮動小数点数値計算ユニットより格段に、はるかに単純である。それから当然、整数加算器の幅は考えているビューポートサイズをちょうどサポートするよう調整できる。このときは十分なサブピクセル精度を確保し、さらに適切なサイズのガードバンドを得るためにそれを 2 倍から 4 倍にした幅が選ばれる。

余談になるが、ここにはもう一つ面倒な問題がある: 塗りつぶし規則 (fill rule) である。辺を共有して隣接する二つの三角形があるとき、共有される辺の周りのピクセルが飛ばされたり二度ラスタライズされたりしないことを保証するために引き分けを処理する規則が必要になる。D3D と OpenGL はどちらも「top-left」と呼ばれる塗りつぶし規則を使う: 詳細はそれぞれのマニュアルで説明されている。この規則についてここで詳しくは話さないが、一点、今説明した整数ラスタライザでは、最終的に三角形セットアップで特定の辺の方程式に含まれる定数から 1 を引くだけで塗りつぶし規則が処理できることは記しておく。これは隙間が生じないことが保証された処置であり、非常に簡単に行える──Chris が自身の記事で引き分け処理を正しく実装するために必要とした複雑な処理と比較してみてほしい！ 問題が美しく解決されることもときにはあるようだ。

しかし問題はまだある: 判定を行う 8x8 のピクセルブロックはどのように選ぶべきだろうか？ Pineda は二つの戦略に言及している: 単純に三角形のバウンディングボックス全体をスキャンする方法と、三角形内部のサンプルにヒットしないことが分かった段階でその行の処理を止めて "折り返す" 賢い方法である。ただ、二つ目の方法はピクセルを一つずつ判定するときにしか使えない。今は 8x8 のピクセルブロックを使っているのだった！ かといって、64 個の並列加算を行って最終的にピクセルが一つたりともヒットしないというのは無駄が大きい。では...どうにかしなければ！

もっと階層が必要だ

ここまでに説明したのは "細かい" (実際のサンプルが被覆されているかどうかを出力する) ラスタライザの動作である。続いて、ピクセルレベルで無駄な仕事が生まれるのを避けるために、三角形をピクセルではなく "タイル" にラスタライズする別のラスタライザがこの前に追加される (McCormack と McNamara による Tiled Polygon Traversal Using Half-Plane Edge Functions や Greene による Hierarchical Polygon Tiling with Coverage Masks に詳細がある。後者ではこのアイデアを使って論理的な結論を得ている)。辺の方程式を使って三角形を被覆されるタイルにラスタライズする処理は、被覆されるピクセルにラスタライズする処理と非常によく似ている。何をするかと言うと、タイル全体に渡る辺の方程式の最大値と最小値を計算するのである。辺の方程式は線形だから、極値はタイルの境界で起こる──実は四つの角をループするだけで十分であり、方程式の \(a\) と \(b\) の符号を見ればどの角で極値となるかが分かる。要するに、コストは先ほど議論した手法と同程度となる。さらにボーナスとして、ここでタイルのいずれかの角における辺の方程式の値を評価するのだから、その値を細かいラスタライザに渡すこともできるかもしれない。それぞれの 8x8 ブロックでは一つの参照値が必要だったのを覚えているだろうか？ 素晴らしい。

つまり "粗い" ラスタライザを最初に実行して、三角形が被覆するタイルがどれかを調べるということだ。このラスタライザは小さくでき (このレベルで 8x8 はやり過ぎに思える！)、8x8 のブロックにつき一度だけ実行されるのでそれほど速い必要もない。言い換えれば、このレベルで空のブロックを見つけるコストはそれだけ小さい。

このアイデアをさらに進めれば、先述した Green の論文や Mike Abrash の Rasterization on Larrabee で説明される完全に階層的なラスタライザとなる。しかしハードウェアラスタライザでここまでする意味はほとんどない: 実を言えば、こうすると小さい三角形に対しては処理の量が増加してしまう (階層をいくつか飛ばせばいいのだが、ハードウェアのデータフローはそのように設計できない！)。加えて、ラスタライズに時間がかかるほど大きな三角形があったとしても、ここで説明したアーキテクチャがあればシェーダーユニットが消費するよりも速くピクセル位置を生成できる。

実はそもそも、ここで本当に問題となるのは大きな三角形ではない: 大きな三角形を効率的に処理するのは大部分のアルゴリズム (もちろんスキャンラインラスタライザも含まれる) にとって難しくない。問題は小さな三角形なのである！ ゼロ個あるいは一個の可視ピクセルを生成するような小さな三角形が大量にある場合でも三角形セットアップ (いまだに説明できていないが、あともう少しだ) は行わなければならず、加えて一度の粗いラスタライズと 8x8 ブロックに対する少なくとも一度の細かいラスタライズも必要になる。小さな三角形がたくさんあると、三角形セットアップや粗いラスタライズがすぐに律速となる。

一つ記しておくと、この種のアルゴリズムではスライバー (長くて非常に薄い三角形) が非常に悪いニュースになる──タイルを山ほど走査しなければならず、それぞれのタイルには被覆されるピクセルがほとんど存在しない。だから、まぁ、スライバーは遅い。可能なら避けることだ。

三角形セットアップは何をするのか？

さて、これでラスタライズのアルゴリズムがどんなものかが説明できたので、後はこれまで使ってきた辺ごとの定数を見ていく必要がある。実は、これこそが三角形セットアップでセットアップする値である。

私たちが考えてきたケースでは、セットアップされる値のリストは次のようになる:

...以上が三角形セットアップで計算される値である。突き詰めれば辺の方程式とその初期値を求める何回かの大きな整数乗算とステップ値を求める数回のそれより小さい乗算であり、残りはコストの低い組み合わせ論理で行える。

ラスタライザに関するその他の話題とピクセル出力

ここまで言及してこなかった話題にシザーレクトがある。これはスクリーンと平行な辺を持つ長方形レクトであり、ピクセルをマスクする: ラスタライザはこの長方形の外側にあるピクセルを生成しない。これはとても簡単に実装できる──粗いラスタライザはタイルとシザーレクトが全く重ならないとき、そのタイルをその時点で破棄できる。また細かいラスタライザは全ての生成されたカバレッジマスクと "ラスタライズされた" シザーレクトの AND を取ることができる (ここでの "ラスタライズ" は行および列ごとに一度の比較と、何度かのビット AND で済む)。簡単な話だ。次に進もう。

もう一つの話題がマルチサンプルアンチエイリアシング (MSAA) である。これを使ったときに何が変わるかというと、ピクセルごとに判定すべきサンプルが増える──DX11 では最低でも 8x MSAA をサポートすることがハードウェアに求められる。それぞれのピクセル内部におけるサンプル位置は構造格子ではなく、優れた結果が得られる辺の傾きの範囲が大きくなるようサンプルは分散して配置される。この非構造的なサンプル位置はスキャンラインラスタライザで扱うのが非常に難しい (使うべきでない理由がまた一つ増えた！) が、Pineda スタイルのアルゴリズムだと非常に簡単にサポートできる: 三角形セットアップで辺ごとのオフセットを追加でいくつか計算し、ピクセルごとに加算と符号テストを (一回ではなく) 複数回行えばよい。

例えば 4x MSAA を 8x8 のラスタライザで使う場合のやり方は二つある: 一つは各サンプルを個別の "サンプル" として扱う方法で、このとき実効的なタイルサイズは MSAA リゾルブ後の実際のピクセル換算で 4x4 となり、細かいラスタライザにおける 2x2 個の位置からなるブロックがリゾルブ後のピクセル一つに対応することになる。もう一つは実際の 8x8 ピクセルをそのまま扱い、ラスタライザを四度実行するというものだ。8x8 は少し大きいように思えるので、AMD は前者を使っているのだと私は考えている。他の MSAA レベルについても同様に動作する。

話をまとめよう。以上で細かいラスタライザが実行され、そこから各 8x8 ブロックの位置とカバレッジマスクが得られる。素晴らしい。しかしこれは、話の半分でしかない──いまどきのハードウェアは (可能なら) Z テストと階層的 Z テストもピクセルシェーダーを実行する前の早い段階で行い、ラスタライズの一部にZ プロセッシングを組み込んでいる。ただ話題が多くなり過ぎてしまうので、ここで章を分けた方がよさそうだ。次章では様々な種類の Z プロセッシング、Z 圧縮、そしてさらに別の三角形セットアップについて話をする──本章ではラスタライズのためのセットアップを触れただけだが、他にも Z 処理やピクセルシェーディングのために補間されるべき値が存在するので、これらもセットアップされなければならない！ それではまた。

注意

ラスタライズの様々なアプローチを代表すると私が考えたアルゴリズムに対するリンクを示した (たまたま全てウェブにあった) が、これ以外にもアルゴリズムは多くある。この話題に関する完全な入門さえ書こうとはしなかった。それだけで一つの真面目な (長い！) 記事になるはずだ──ただあまり面白くはならないのではないかと、私は恐れている。

本章が暗黙に仮定していることがもう一つある (以前に何度か触れたが、ここでも言及するべきだろう): これはハイエンドの PC ハードウェアでの話である。「タイルレンダラ」と呼ばれる、スクリーンをタイルに分割してタイルごとに別々にレンダリングを行う手法を採用するハードウェアも (特にモバイル/組み込みで) 多くある。これは、本章で説明した 8x8 のタイルを使ったラスタライズと同じではない。タイルレンダラには "超粗い" ラスタライズステージが追加で少なくとも一つ必要になる。通常「ビニング (binning)」と呼ばれるこのステージは、どの (大きな) タイルが各三角形によって被覆されるかを判定するために早い段階で使われる。私がここで説明した「sort-last」のレンダラ (これは正式名称である) と比べると、タイルレンダラは異なる動作と設計パラメータを持つ。D3D11 パイプラインが終わったら (まだまだ遠い！) タイルレンダラに関する記事も一つか二つ書くかもしれないが、今は触れないことにする。そのため、例えばスマートフォンの多くに搭載されている PowerVR のチップでは処理が異なるのだと知っておいてほしい。

8x8 のブロックでラスタライズを行う手法は、一定の大きさより小さい三角形や極端なアスペクト比を持つ三角形に対するラスタライズで直感に反する量の処理を行うことになり、ハードウェアを上手く活用できないことを意味する (他のブロックサイズを使っても問題は変わらない)。簡単に並列化できてなおかつスライバーも簡単に扱える魔法のアルゴリズムがあればよいのだが、仮にあったとしても私は知らない。またハードウェアベンダーはいまだに「スライバーでは性能が悪くなるぞ」と定期的に注意喚起を行っているので、彼らも知らないようである。そのため当面は、これがハードウェアラスタライズで避けられない事実であるようだ。もしかしたら、いずれ誰かが優れた解決法を思いつくかもしれない。

粗いラスタライザの話題で説明した「辺の方程式の最小値/最大値を求める」処理は問題なく動作するが、特定のケースで偽陽性 (ピクセルを一つも被覆しないブロックが細かいラスタライザに渡される状況) が発生する。これを避けるトリックも存在するが、しかしここでも、稀にしか起きないケースの検出には複雑な処理が必要であり、どのピクセルも灯らないブロックをたまにラスタライズするよりもコストが多くかかってしまう。ここにもトレードオフがある。

最後に、ラスタライズで使われるタイルはスクリーンを等分割した格子にスナップされることが多い (こうすべき理由は次章で明らかになる)。この場合、わずか二ピクセル分の大きさしかない三角形であっても、二つのタイルにまたがっていれば 8x8 ブロックを二つラスタライズすることになる。効率はさらに落ちる。

要点はこれだ: ラスタライズはなるほど非常に単純で美しいが、完璧ではない。実際の三角形に対する実際のラスタライズの速度はラスタライズ性能の理論的ピーク (細かいブロックが常に全て埋まっていると仮定した値) から程遠い。この点は忘れてはいけない。

広告
このページの文章はテキストゆれないくんを使って校正されました。