T.TAO
Back to Blog
/16 min read/Computer Science

VCS #1 Tile-based Renderer 文書

#computer-science
VCS #1 Tile-based Renderer 文書

VCS #1 タイルベースレンダラー ドキュメント

これは CMU 15-473/673 Visual Computing System の課題1のブログ/ドキュメントです。この課題は、タイルベースレンダラーの sort-middle アルゴリズムの実装に関するものです。

データ処理

SIMD

このプロジェクトでは、Intel の SIMD（Single Instruction, Multiple Data）データ型を使用して座標を渡します。具体的には __m128 を使用します。これは Intel の SIMD 命令セットに固有のデータ型で、特に Streaming SIMD Extensions（SSE）ファミリーの命令で使用されます。4つの 32 ビット浮動小数点値を同時に格納および操作できる 128 ビットサイズのレジスタを表します。

__m128 を扱うには、基本的な算術演算を行うために特定の API を使用する必要があります。この課題では、以下の API を使用する必要があります。

Plain Text#include <xmmintrin.h> 
int main () {

    // addition
    __m128 result_addition = _mm_add_ps(1.0f, 2.0f);
    __m128i result_addition_int = _mm_add_epi32(1,2);

    // subtraction
    __m128 result_subtraction = _mm_sub_ps(1.0f, 2.0f);
    __m128i result_subtraction_int = _mm_sub_epi32(1,2);

    // multiplication
    __m128 result_mul = _mm_mul_ps(1.0f, 2.0f);
    __m128i result_mul_int = _mm_mullo_epi32(1, 2);

    // division
    __m128 result_div = _mm_div_ps(1.0f, 2.0f);

    // set to zero
    __m128 zero = _mm_setzero_ps();

    // set to value
    __m128 one = _mm_set_ps(1.0f, 2.0f, 3.0f, 4.0f);

}

SIMD 命令を使用して比較とビット演算も行えます。

Plain Text#include <xmmintrin.h> 

int main () {

    // Compare Equal
    __m128 result_equal = _mm_cmpeq_ps(1.0f, 1.0f);
    __m128i result_equal_int = _mm_cmpeq_si128(1,1);

    // Compare Less Than
    __m128 result_lessThan = _mm_cmplt_ps(1.0f, 2.0f);
    __m128i result_lessThan_int = _mm_cmplt_si128(1,2);

    // Compare Greater Than
    __m128 result_greaterThan = _mm_cmpgt_ps(1.0f, 2.0f);
    __m128i result_greaterThan_int = _mm_cmpgt_si128(1,2);

    // Bitwise And
    __m128 result_and = _mm_and_ps(1.0f, 2.0f);
    __m128i result_and_int = _mm_and_si128(1,2);

    // Bitwise Or
    __m128 result_or = _mm_or_ps(1.0f, 2.0f);
    __m128i result_or_int = _mm_or_si128(1,2);
}

N.4 フォーマット

この課題では、頂点位置は 4 ビットのサブピクセル精度を持つ固定小数点表現で格納され、これは浮動小数点値の N.4 フォーマットと呼ばれます。整数部分に n ビット、小数部分に 4 ビット。

例えば、2進表現 1001.0110 は次のように理解できます：

  • 整数部分：1001 = 9
  • 小数部分：0110 = 6/16 = 0.375

したがって、この数は 9.375 です。

N.4 フォーマットは GPU で浮動小数点計算のコストを削減するために広く使用されています。さらに、N.4 フォーマットの最も重要な操作の1つは丸めです。定義を使用すると、N.4 フォーマット浮動小数点数の2進表記 a に対して、ビットシフトを使用して floor と ceil 操作を行うことができます。

ラスタライゼーション

点-in-三角形テスト

シーンをラスタライズするとき、RasterizeTriangle() 関数を呼び出します。この関数は出力画像の領域と三角形を入力として受け取ります。その後、この画面領域内で、入力三角形によって少なくとも部分的にカバーされる可能性のあるすべての 2x2 ピクセルチャンクを識別します。

このプロセス中に、三角形が実際にこの 2x2 ピクセルブロック内のサンプルをカバーするかどうかを判断する必要があります。これを三角形カバレッジテストと呼びます。この部分は TestQuadFragment() 関数で行われます。このピクセルブロック内の4つのピクセルに対応する4つの画面点の座標を入力として受け取ります。出力は、これらの点のどれが三角形内にあるかを示すビットマスクです。以下の図に示すように。

__m128 レジスタは最大4つの整数を保存できるため、クアッド 2x2 フラグメントの4つのサンプルの x 座標と y 座標を格納するために2つのレジスタを使用します（コメントで述べたように N.4 固定小数点フォーマット）。

エッジ方程式

ピクセルが三角形にカバーされているかどうかをテストするために、エッジ方程式を使用します。三角形の i 番目の頂点を (xi, yi) とラベル付けします。クエリ点 q = (x, y) について、まず計算します。

i 番目のエッジのエッジ方程式は次で計算されます。

点 q が三角形内テストに合格する必要十分条件は

つまり、エッジ方程式は同じ符号でなければなりません。点がエッジ上に正確にある場合（Ei = 0）、エッジが現在の三角形に属しているかどうかをチェックします。isOwnerEdge[i] にアクセスすることでこれをチェックできます。isOwnerEdge[i] が true の場合、このエッジは三角形に属しているため、エッジ上のすべての点を三角形内とみなします。

これで、エッジのマスクは明確になりました。

各フラグメントのサンプルがカバーされているかどうかを示すビットマスクを返す TestQuadFrag() 関数があるので、三角形をラスタライズできます。これを RasterizeTriangle() メソッドで行います。

三角形をラスタライズする方法は、すべての候補ピクセルを見つけ、既に書いた TestQuadFrag() を使用して各ピクセルのカバレッジをテストすることに要約できます。入力として受け取るのは：

  • regionX0, regionY0：現在の作業タイルの左上隅の座標。
  • regionW, regionH：現在の作業タイルのピクセル単位の幅と高さ。
  • tri：三角形方程式を設定。三角形の角の座標を保持。
  • triSIMD：SIMD レジスタ内の tri のすべての値。
  • processQuadFragmentFunc：関数値。カバレッジを生成する可能性のあるすべてのクアッドフラグメントについて、このメソッドを呼び出す必要がある。

バウンディングボックスの検索

テストを加速し、候補を見逃さないために、まず三角形のバウンディングボックスを見つけて、どの座標を見るかを決定します。セクション 2.2 で議論した N.4 フォーマット浮動小数点数のビット演算を使用すると、これを簡単に行えます。

すべてのクアッドフラグメントを走査

for ループを単純に適用して、三角形にカバーされる可能性のあるすべてのフラグメントの走査を開始できます。見る各クアッドフラグメントについて、ピクセルの座標（左下、右下、左上、右上）をレジスタに保存します。その後、TestQuadFragment() メソッドを呼び出して、この三角形が受け入れられるかどうかを確認します。すべてのクアッドがテストに合格する必要がある trivial accept 条件を使用します。

Sort-middle タイルベースレンダラー

sort-middle タイル並列レンダラーの実装を開始します。タイルレンダラーには2つのフェーズがあります：

  • 三角形をビンに配置する。画面タイルごとに1つのビンがあり、各ビンにはビンと潜在的に重なる三角形のリストが含まれるデータ構造を構築する。
  • ビンを並列に処理し、次の未処理のビンを次の利用可能なコアに動的に配布する。

プロセスは図2に示すように表示できます。

初期化

タイルベースレンダリングでは、画面を小さなタイルに分割し、これらをビンと呼びます。各タイルは内部の三角形の処理を担当します。通常、パフォーマンスを向上させるために、三角形をカバーするタイルで分類します。このプロセスをビニングと呼びます。

ビンを追跡する直感的な方法は、各タイルが投影された三角形のベクトルであるタイルのベクトルを使用することです。これを bins と呼びます。ただし、ビニングがマルチスレッドコンテキストで処理されると、複数のスレッドが同時に三角形を処理し、対応するビンに配置する可能性があります。グローバルな bins に直接書き込むと、以下が発生する可能性があります：

  • 競合状態。複数のスレッドが同じデータ構造に書き込む。データの不一致やプログラムのクラッシュを引き起こす可能性がある。
  • パフォーマンスのボトルネック。競合状態を避けるために、スレッドセーフティを確保するためにロックを適用する必要がある。これはほぼ確実に遅くなる。並列性を低下させるため。

スレッドローカルビン

上記の問題を解決するために、threadLocalBins と呼ぶデータ構造によって維持されるスレッドローカルビンを導入します。各スレッドは独自の独立したデータ構造でビンを維持します。スレッド i がビニングするとき、独自の threadLocalBins[i] にデータを書き込みます。スレッドローカルビンを使用することで、ロックの使用も避け、同期のコストを削減します。すべてのスレッドがビニングを完了したら、全員のローカルビンをグローバルビンにマージし、ProcessBins() に渡して処理します。

ステップ

BinTriangles() で行う必要があることを以下のステップで説明します。

  1. 初期化。画面が gridWidth × gridHeight タイルに分割されていると仮定。グローバルビン。ProjectedTriangles のベクトルのベクトルで、サイズは gridWidth × gridHeight。スレッドローカルビン。ProjectedTriangles のベクトルのベクトルのベクトル。すべてのスレッドのローカルビン構造を追跡するため。つまり threadLocalBins[threadId] は threadId 番目のスレッドのローカルビンを返す。
  2. スレッドローカルビニング。各スレッドはシーン内の三角形の一部のみを処理する。三角形のカバレッジに従って threadLocalBins[threadId] に三角形を配置する。これは、threadLocalBins[threadId] 内のビンの大多数が空になることを示す。スレッドは1つまたは少数のタイルのみを処理するため。各スレッドについて、責任外のタイルは空とみなせる。図3に示すように。
  3. グローバルビンにマージ。すべてのスレッドがビニングを完了したら、threadLocalBins 内のすべてのローカルビンをグローバル bins にマージする。三角形はタイルで分類される。各タイルについて、すべてのスレッドの三角形サブリストをマージする。これらのサブリストには、このタイルに存在する三角形が含まれる。
  4. グローバルビンの処理。最後にグローバルビンを走査し、タイル内の各三角形を処理する。各タイルは独立して処理されるため、ProcessBin() を複数のスレッドで実行する。

ビニング三角形

次に行うことは、グローバルビン内のビンを処理することです。各タイルについて、ProcessBin() を呼び出してビン内のフラグメントをラスタライズします。タイルベースレンダラーでは、フラグメント間ではなくタイル間で並列性が発生することに注意してください。タイル内の処理は順次行われます。したがって、ShadeFragments() ではなく、1つのクアッドフラグメントを一度に ShadeFragment() でシェーディングします。

フレームバッファタイル

フレームバッファに直接書き込む代わりに、色と深度をフレームバッファに更新します。タイルレンダラーの利点の1つは、フレームバッファタイル全体がキャッシュに収まることです。最大のパフォーマンスのために、タイルを処理しながらタイルメジャーのフレームバッファ構造に結果を書き込み、最後にレンダラーのフレームバッファに結果をコピーし直します。

適応

ラスタライゼーションはクアッドフラグメントの粒度で行われるため、ループはタイル内の三角形で実行され、4つのフラグメントのそれぞれをループします。セクション 3.2 で書いた RasterizeTriangle() を呼び出し、領域サイズを現在のタイルのサブフレームバッファのサイズに指定します。

解決する必要があるかもしれない技術的な課題：

  • フラグメントを直接シェーディングするため（フラグメントバッファ内のフラグメントをシェーディングする代わりに）、ShadeFragments() ではなく ShadeFragment() を呼び出す。ShadeFragment() のインターフェースを見ると、処理されている三角形を処理するスレッドを知る必要がある。そうしないと、間違った頂点出力バッファまたはインデックス出力バッファを使用する。
  • タイル化されたフレームバッファに書き込むため、インデックスを慎重に扱う必要がある。
  • 特に、ShadeFragment() のインターフェースには triId パラメータがある。これは ProjectedTriangle クラスのメンバー変数ではない。これは、この三角形をビニングしたときの BinTriangles() 内のループのインデックス。

これらの問題を解決するには、これらの情報を運び伝播する必要がある。処理を容易にするために、BinnedTriangle 構造体のベクトルを維持する。この構造体はスレッド ID、ループインデックス、投影された三角形を保持する。

これでビン全体を処理できる。

完了

処理後、結果をフレームバッファに書き戻す必要がある。

このドキュメントの Markdown 形式はこちらからアクセスできます：https://hackmd.io/@Lockbrains/vcs1_tilebased_renderer。より良い読書体験のために、このリンクでブログを読むことをお勧めします。