Embedded Files
Iterationを利用したMarching Cubes
前回の予告通り、今回はMarching CubesをIterationを用いることで高速化した手法を紹介します。
多分こうやるんだろう、という感じで適当に作った物なので、より高速な手法がある可能性が十分にあります。
ただ、基本的な処理の流れは変わらないと思いますので、参考にしていただけたら幸いです。
ちなみに、前回のように全てのCubeを最大分割数分だけ3Dテクスチャで用意する手法を用いると、分割数256で一桁FPSになりました(RadeonHD 5870環境)。
しかし、上の画面では分割数512で50FPS以上出ています。
サンプルではIterate Numを2にすればIterateなしの64分割と同じ分割数になるので、その差を見るだけでも高速になることがわかるかと思います。
まあ、環境依存はすると思うので、速度が低下する環境がないとは言い切れませんのでご了承ください。
さて、どのように処理をしているかというのを言葉で説明するのが難しいので、図を用意しました。
この図はCompute Shaderで行っている処理をフローチャートっぽい物におこした物です。
青の四角はCompute ShaderでのDispatch処理で、各関数名が書かれています。
赤の四角はバッファに出力される情報です。
黒の矢印が処理の流れを示し、緑の矢印がバッファへの出力を示し、紫の矢印がCompute Shaderへの入力を示します。
では、それぞれの処理を説明します。
最初に実行されるのはDispatchFirst関数です。
これは空間全体を8*8*8の3D分割します。これによって8*8*8=512個のCubeが生成されます。
それぞれのCubeと、Marching Cubesを作成したいパーティクル群との衝突判定を取ります。
衝突していない場合、そのCubeは棄却されます。
衝突している場合、DispacthIndirect用バッファのx値を1加算し、Cube情報バッファにそのCubeの基準座標と1辺の長さを格納します。
なお、パーティクルとCubeの衝突判定ですが、パーティクルがCubeを完全に内包する場合も衝突なしとして棄却します。
Marching Cubeではパーティクルに内包されたCubeにおいてはポリゴンの生成が行われません(ただし、この表現は正確ではない点に注意)。
ですので棄却しても問題ないということになります。
次に行われるDispatchIter関数は基本的な処理はDispatchFirst関数と変わりません。
違いは、空間全体を分割するか、与えられたCube群を分割するかの違いです。
もちろん、この2つの関数は1つにまとめてしまうことも可能ですが、今回はそれぞれ別々に分けました。深い意味は無いです。
このDispatchIter関数は何度も呼び出すことが可能です。
速度に余裕があるのであれば、何度も呼び出してより分割数を増やしていくことが可能となっています。
ただし、分割数を増やせば必要なバッファサイズも大きくなりますし、処理も重くなります。ご注意ください。
最後にDispatchFinal関数です。
ここではこれまでに分割されたCubeをまたもや8*8*8に分割します。
しかし、ここでは衝突判定は行わず、通常のMarching Cubes処理を行います。
つまり、各Cubeの値を求め、隣接Cubeの値との関係からポリゴン生成を行うCubeを選定します。
その情報を隣接Cubeの値とともに出力し、Geometry Shaderでポリゴン生成が必要なCubeのみ処理を行うわけです。
なお、この段階でポリゴンを生成することも可能なはずです。
もしかしたらGeometry Shaderを利用するより高速かもしれませんが試してみないと正確なところは言えません。
Geometry Shaderを使用した理由にも深い意味は無いです。
Marching Cubesは分割数が増えれば増えるほど、ポリゴンを生成する必要の無いCubeが増えていきます。
これらを真面目にGeometry Shaderに流すのは無駄に重いので、Octreeのような形で枝打ちをしていこうというのが今回の手法です。
この手法はSparse Voxel Octreeと近い考え方の技術と言えます。
ちなみに、DispatchFirstとDispatchIterではCubeとパーティクルの衝突判定を取っています。
ここでMarching Cubesの計算を行ってもいいのではと考える方がいると思いますが、これでは正しく描画されません。
例えば、Cubeがパーティクルを内包してしまった場合を考えてください。
この場合、Cubeの各頂点においてパーティクルからは値が得られず、0となってしまいます。
すると、このCubeはポリゴンが生成されないCubeと扱われて棄却されてしまうのです。
しかし実際にはCubeをより細かく分割すればそこにポリゴンが生成される可能性が出てきます。
この問題はMarching Cubes自体の欠点とも言えますが、それを出来るだけ軽減するために当たり判定を取るようにしています。
では、サンプルのダウンロードは以下から行ってください。
Download：Sample125.zip
Twitterでも少し書きましたが、環境によっては正常に描画されない可能性があります。
自宅のRadeonHD 5870はCatalystの12.8を使用していますが、これだとパーティクル移動中にポリゴンの一部が剥がれることがあります。
移動を止めている場合は問題なく描画されています。
また、Iterationの回数を4以上にすると問答無用で描画されなくなります。
ですので、サンプルでは2回か3回しか選択出来ないようにしています。
Indirect用バッファのクリア方法もクリア用のCompute Shaderを起動することで行っていますが、この処理を行う場所によっても描画が正常に行われたり行われなかったりします。
Stagingバッファを使用してデフォルトデータをコピーする方法だと全く描画されなくなります。
Iterationの回数は試していませんが、NVIDIAのGPUだとこのような問題は発生しませんでした。
NVIDIAでも発生するようであればドライバを更新していただければ正常動作するかもしれません。
さて、今回のサンプルではパーティクルが2つだけでしたので全てのCubeで全パーティクルの衝突判定を取っていました。
しかし粒子系の物理計算を行ってそれらについてMarching Cubesで描画したい場合はパーティクルの計算量が増えてしまいます。
これを回避する方法としては、衝突判定が取られたパーティクルをリスト化して保持しておく方法があるかと思います。
ただ、これによって高速化出来るかどうかは難しいところかもしれません。
まず、そのリストを保持しなければいけないのでメモリ量が増えますし、メモリアクセスも増えます。
また、衝突判定が1つでも取られればCubeを有効として扱うことが出来るので、実際に全てのパーティクルと衝突判定を取る必要は(DispatchFinal以外では)ないのです。
とはいえ、棄却されるCubeはすべてのパーティクルと衝突判定をチェックする必要があります。
棄却されるCubeが多い場合は衝突判定回数を減らせる可能性が高いので、それなりの高速化は期待出来るかもしれません。
この辺もやはり試してみないと何とも言えないですね。
次回は現状では予定無し。
なにか考えておきます。
Page updated
Google Sites
Report abuse