はじめに本記事では、かなり前に実装したComputeShaderで格子探索を行うアルゴリズムを解説します。値の利用時に全数探索をしないことで計算速度を飛躍的に向上させるアルゴリズムのことを指します。Simulationがあります。全数探索を行っていると、すべての要素毎にすべての要素との距離を計算する必要があります。(俗に$O(n^2)$の実行時間を要すると言います)当然この方法では、最新の筋肉GPUを用いても、8万程度の要素数でFPSの頭打ちが来てしまいます。近傍探索を導入することで、64万程度の要素数でも余裕で60FPSをキープすることができるようになります。格子探索(この名称が存在するかは不明)等があります。GPUで実装する際には、単純に空間を格子状に分割する格子探索が最適とされています。(~木系は再帰的に探索するためGPU上での実装が困難です。)本記事では、この格子探索についての解説を行います。本節の解説は以下のページに基づいています。SPH法の実装(GPU実装含む)こちらに掲載されている解説をComputeShaderに置き換えます。解説に使用するリポジトリはこちらです。以下の図のような配置でパーティクルが空間に存在しているとします。はじめに、以下の構造体で構成されたComputeBufferを、全パーティクル数分の長さで確保します。パーティクルのインデックス}次に、それぞれのパーティクルが属するセルを計算し、パーティクルインデックスとペアで保存します。P_ID);}次に、これを格子のインデックスで並び替えます。ここで、パーティクルのインデックスも一緒に並び替えられることに気を付けておきましょう。これを**表(3)**としておきます。次に、以下の構造体で構成されたComputeBufferを、全格子数の長さで確保します。おわり}このとき、全要素を0xfff(値型の最大値)で初期化しておきます。0xffffff);}確保したバッファに対し、表(2)の格子インデックスが異なるものになる初めと終わりの番目を計算した結果を格納します。1;}}これを**表(5)**とします。ここまでで下準備は完了です。表(3)と表(5)を利用して、近傍探索を行います。周辺のセルに属しているパーティクルすべてを水色にする処理を施しています。_ParticlesBufferRead[id].pos;}バイトニックソート今回のソーティングの実装では、@oishihiroaki先生のリポジトリからバイトニックソートを拝借しました。注意点として、ソート対象が2のべき乗の長さでなければならない制約があります。今回の例ではパーティクル数が2のべき乗である必要があります。バイトニックソートの解説については、またの機会にできればと思っております。終わりに雑な解説となってしまいましたが、最後までお付き合いいただきありがとうございました。時間ができましたら、より詳しい解説を追記しようと思っております。お詫び何を血迷ったのか、まとまりのない実装になっている為ご容赦願います。ProgrammingUnityを用いたグラフィクスプログラミングの技術書を同僚と出版しました。ご興味があればぜひご一読ください。