~下のムービーは、512x512=262144個をソートする様子です(2MB)。背景が赤くなると、ソートは完了しています。■はじめにもういい加減、順序を気にしなくてよい半透明表示をハードウェアで実装してもらいたいところですが、なかなかそんなものは実現していません。よるソートが必要不可欠です。ソートは、異なる位置のピクセルを入れ替えるという作業で、現在のGPUでは行いにくい方法の1つです。Hardwareが公開されました。この論文は、フォトンマップをGPUで実装するという野心的な論文です。いうソート法があります(ここの説明が詳しいです)。O((logN)2)パス数でソートを実行するソート法です。要素に対して、210パス(ポリゴンを描画するだけなので、最近のGPUによる実行速度1000FPSを考えれば、0.2秒で終了します)。DirectX9で実装をしてみます(元の論文にCg版が乗っているので、ほとんど何もやっていないのですが...)。受け入れることにしました。今回のプログラムは、次のものです。フィルタ:DirectX9(ピクセルシェーダ2.0)まぁ、いつものように適当にファイルが入っています。出力されるフレームワークのファイルは紹介を省かせていただきます。アプリケーションのソースあと、実行ファイル、プロジェクトファイルが入っています。最初に隣り合った2つのデータをソートします。次に、ソートされた2つのブロック(4つのデータ)をソートします。あとは、ソートする塊をゆきだるま式に大きくして、すべてのデータをソートするまで続けます。ここで、矢印は、ソートする2つのデータを指し示します。下を向いた赤い矢印は、小さな値のデータを上に、上を向いた青い矢印は、小さな値のデータを下に動かします。赤いブロックは上のデータほど値が小さくなるようなソートで、青いブロックは下のデータの値が小さくなるような逆順のソートです。特徴として、途中のソートでは、正順と逆順を交互に繰り返す方法であるということがあげられます。して、1つおきに並び替えのデータをかえるのでしょうか?上のデータを正順、下のデータを逆順に並べておくと次のステップでの並び替えがスムーズに行われます。4つの正順のデータと4つの逆順のデータを組み合わせてソートする時を考えます。上の図で、小さな値1~4は白い色で、大きな値5~8は灰色にしました。ここで、4個おきにデータを比較、ソートしてみると、小さな値のデータは全て上に、大きな値のデータは全て下に移動してしまいました。ソートした後も、2個づつデータはソートされるので、(特に上の4つに注目すれば、2つづつ正順、逆順が並んだ全く同じ構造になっています。同じステップをあと2回続ければ、データは完全にソートされます。2n-2個おきの比較をします。最後にとなりのデータの比較までたどり着いたところでソートが完了します。1つのブロックをソートするのに、n回のレンダリングパスが必要になります。パスで完了することになります。■プログラムということで、今回のプログラムを紹介してきましょう。データをソートするので、使えるバッファはテクスチャです。そのインデックスに関して、ソートをします。1次元から2次元への変換は、次のようになります。テクスチャの幅と高さです。1の範囲で、2次元のテクスチャ座標の値dstは、0~1の範囲を返します。ちなみに、この逆に2次元の座標からインデックスへの変換は、次のようになります。1次元のインデックスになります。らによるシェーダのHLSL版は、次のようになります。次に、比較対照のデータの位置に必要な参照するデータの向きcsignを計算します。csignが1なら、自分より後ろのインデックスのデータと比較して、-1なら、自分よりも前のインデックスのデータと比較します。位置が比較するデータになります。次に、ソートする向きcdirを計算します。今までに出てきた図の赤い部分は1、青い部分は-1になります。らのシェーダでは、この部分は等号で比較していましたが、HLSLではきちんと動かなかったので、不等号を使って、cdirを計算しました。あとは、それぞれのデータを読み込んで、小さなデータcminと大きいデータcmaxを計算し、ソートの向きとピクセルに格納するデータの位置からどちらのデータを出力するか決定します。HLSL内でグローバル変数(定数レジスタ)として扱います。それぞれのパスでのパラメータの値は、次のようになります。アプリケーション側からパラメータを計算する部分は、次のようになります。計算しておき、そこからパラメータの動きをよく考えて各パラメータを作りました。2*offset;■最後にいや、これすげーよ。1048576個のデータをソートするなら個人的には、これぐらいは全然許容範囲内だと思います。紹介されていたけど、「あれじゃ全然わかんねぇよ!!」と思ったのは、私だけですか...(この説明もわかりやすいかどうか疑問ですが)もどるimagire@gmail.com。