多分2018年最後の記事。（思ったほど効果がなかったので温めずに公開）
UE4のマテリアルBPでバイトニックソートを作ってみました。
RG32fテクスチャを「R=キー, G=値」の配列に見立ててテクセルを並べ替えます。
GPUパーティクル等でテクスチャに格納した情報をソートする場合に、
GPUからCPUへデータをフィードバックしてCPUでソート、
再びGPUに戻すよりも全部GPUでやったほうが速いだろうということで。
バイトニックソート自体はDirect Computeのサンプルなどがわかりやすいです。
ComputeShaderSort11 サンプル
今回のマテリアルBPを利用した方法はほぼピクセルシェーダ実装なのでt-pot様も参考になると思います。
t-pot『Bitonic sort』
バイトニックソートの大まかな流れは
- ステップ1
- サブステップ 2要素毎に1個隣と入れ替え
- ステップ2
- サブステップ 4要素毎に2個隣と入れ替え
- サブステップ 2要素毎に1個隣と入れ替え
- ステップ3
- サブステップ 8要素毎に4個隣と入れ替え
- サブステップ 4要素毎に2個隣と入れ替え
- サブステップ 2要素毎に1個隣と入れ替え
- ステップi
- 同様に最大要素の半分の要素毎のステップまで続ける
という感じです。要素数が 2^n の場合は合計で n*(n+1)/2 のサブステップによってソートが完了します。
65536=2^16 なら 136サブステップです。
実際には昇順降順を入れ違いにするので詳細は先に挙げたページを参考にしてください。
また、バイトニックソートの制限として要素数が2のべき乗でないとダメなのでそのあたりはBPで調整してます。
実装詳細はサンプルプロジェクトを見ていただくとして概要は以下のようになります。
- BP
- BP_BitonicSortTest
- ソート用のマテリアルを使ってソートを実行するアクター
- 必要なテクスチャやマテリアルを保持
- 初期化マテリアル及びバイトニックソートマテリアルをDrawMaterialToRenderTargetで実行する
- 初期化マテリアルでRにノイズ、Gに適当な値を書き込み
- バイトニックソートマテリアルに適切なパラメータを設定しつつ必要な数だけDrawMaterialToRenderTargetを実行している
- Drawで実行する関係でテクスチャを二枚用意し交互に入出力を切り替えている
- M_RandInitRGKeyVal
- 指定されたテクスチャのRにノイズ, Gに適当な値を書き込み
- M_BitonicSortRG32fKeyVal
- バイトニックソートの1サブステップ分の処理をするマテリアル
- テクスチャのテクセル一つを配列の1要素に見立て、Rの値の大小比較で入れ替えをする
- ステップ番号とサブステップ番号、1サブステップ前の結果のテクスチャをパラメータに指定してDrawするとターゲットに1サブステップ分の要素入れ替えをした結果を書き込む
- M_TextureDraw
- ソート結果のテクスチャを可視化するためだけのマテリアル
- BP_BitonicSortTest
ソートの結果がこの記事の最初に貼ったノイズのようなテクスチャの色がｳﾈｳﾈしている動画です。
毎フレームでテクスチャのRの値にノイズ(乱数)を書き込み、Rの値でソートしてメッシュに貼り付けています。
ソートの結果左上のテクセルが先頭、右下が末尾になるように並び替えられるので、上のほうがRが小さく(緑)、下のほうがRが大きい(赤)ようになっているはずです。
ちなみにソートマテリアルを実行しない場合は以下のような感じです。
youtu.be
要素数はアクターの ArgMaxElement で変更できます。
実際にはここに設定した数値より大きい最小の2のべき乗数が自動で計算されて利用されます。
結果としてはマテリアルBPでソートはできましたが、速度はそんなに速くなりませんでした。遅いです。
原因はDrawMaterialToRenderTargetの回数が多すぎることによるCPU負荷と思われます。
サブステップ1回につきDrawMaterialToRenderTargetが1回必要なので、65536要素の場合は136回のDrawMaterialToRenderTargetが実行されてます。
ComputeShaderで実装する場合は共有メモリを利用することで1ステップをDispatch1回で処理できるので相当速くできると思います。いつかやりたい。
以上、マテリアルBPで無理やりバイトニックソートをやってみた、でした。
