本記事では、空間分割アルゴリズムを利用して、計算負荷を大幅に軽減する方法をリサーチしています。空間分割アルゴリズムには、さまざまな方法がありますが、本記事では実装が比較的簡単なグリッド法についての実装方法です。

実装にはProcessingを利用します。
サンプルコードが必要な場合は、下記 Patreon にてダウンロードできます。

Research / Grid-Based Partitioning for Processing: Optimizing Performance in Large Simulations

空間分割とは？

空間分割（Spatial Partitioning）とは、オブジェクトを特定の領域に分類し、計算コストを削減する手法です。代表的なアルゴリズムには、以下のようなものがあります。

  • グリッド法（Grid-based Partitioning）：空間をグリッド状に分割し、各セルにオブジェクトを割り当てる
  • クワッドツリー（Quadtree）：2D空間を再帰的に4分割するデータ構造
  • オクツリー（Octree）：3D空間を再帰的に8分割するデータ構造

空間分割のグリッド法とは？（Grid-based Partitioning）

空間分割のグリッド法では、シミュレーション対象の領域を、指定したサイズのセルに分割します。各セル内に存在するパーティクルをリストで管理し、パーティクル間の相互作用を計算する際に、対象のセルとその近隣のセルに存在するパーティクルのみを計算対象とします。これにより、全パーティクルに対して計算を行うのではなく、近くにいるパーティクルのみを対象にするため、計算量を大幅に削減できます。

1. セルのサイズ（cellSize）の決定

セルのサイズ cellSize を決めることは、空間分割法において最も重要な要素の1つです。セルサイズが大きすぎると、計算範囲が広すぎて計算効率が悪くなり、逆に小さすぎると、セルの数が増えすぎて管理にかかるオーバーヘッドが増加します。

セルサイズは MAX_DISTANCE（パーティクル間の最大距離）に基づいて決定します。適切な cellSize の目安は次の式で求めることができます：

int range = ceil(float(MAX_DISTANCE) / cellSize);
MAX_DISTANCEcellSizeMAX_DISTANCE / cellSizerange の理想値
100502.0ceil(2.0) = 2
1001001.0ceil(1.0) = 1
1002000.5ceil(0.5) = 1
150503.0ceil(3.0) = 3

2. グリッドの構造

グリッドは2次元の配列として実装されることが一般的です。配列のサイズは、シミュレーション空間の幅と高さをそれぞれ cellSize で割った値で決まります。各セル内には、対応する範囲に存在するパーティクルをリストとして格納します。


// グリッドの作成
cols = width / cellSize;
rows = height / cellSize;
grid = new ArrayList[rows][cols];

// セル内のパーティクルを追加
for (int i = 0; i < MAX_PARTICLES; i++) {
    Particle p = new Particle();
    grid[int(p.pos.y / cellSize)][int(p.pos.x / cellSize)].add(p);
}

3. 近傍探索

パーティクル間の相互作用を計算する際に、空間分割のメリットが発揮されます。各パーティクルは、自分がいるセルとその周囲のセルのみを探索対象とします。探索範囲は、事前に設定した range に基づいて決定します。 range が１であれば、パーティクルは自分のセルとその周囲８セルを調べます。


// 近傍セルの探索
int range = ceil(float(MAX_DISTANCE) / cellSize);
for (int dy = -range; dy <= range; dy++) {
    for (int dx = -range; dx <= range; dx++) {
        int gridC = (c + dx + cols) % cols; // X方向の近傍セル
        int gridR = (r + dy + rows) % rows; // Y方向の近傍セル

        for (Particle p : grid[gridR][gridC]) {
            if (this != p) {
                float d = pos.dist(p.pos);
                if (d < MAX_DISTANCE) {
                    // 相互作用の処理
                }
            }
        }
    }
}

上記のコードでは、range によって自分のセルとその近隣のセルを探索し、近距離のパーティクルのみを相互作用させます。

4. メリットとデメリット

メリット

  • 計算量の削減：全てのパーティクルを比較する代わりに、近くのセルに存在するパーティクルのみを探索対象とするため、計算量を大幅に削減できる。
  • スケーラビリティ：パーティクル数が増えても、計算負荷が急激に増加しない。
  • 効率的なメモリ管理：セルごとにパーティクルを管理することで、メモリの利用効率が向上。

デメリット

  • セル管理のオーバーヘッド：セルの管理に一定のオーバーヘッドがかかる。特に、セルサイズが小さい場合やシミュレーション空間が広い場合に顕著。
  • 空間分割のバランス：セルサイズの設定が不適切だと、効率的に動作しなくなる場合がある。

5. 最適化のポイント

  • セルサイズの最適化： cellSize を MAX_DISTANCE に基づいて適切に設定することで、計算の負荷を最小化できる。
  • 探索範囲の調整：range の値を調整することで、計算するセルの数をコントロールし、計算負荷をさらに減らせる。
  • 並列化の検討：パーティクル間の相互作用の計算は独立しているため、並列処理（例えばGPUを活用）を利用することで、さらに高速化が可能。

比較

下記は、空間分割なしとありの比較、パーティクル数 10,000 にて実行した場合のFramerate数。

【 なし ／空間分割（Spatial Partitioning）】

【 あり ／空間分割（Spatial Partitioning）】

まとめ

空間分割のグリッド法は、大量のパーティクルが関わるシミュレーションにおいて非常に有効な手法です。セルのサイズと探索範囲を適切に調整することで、計算量を劇的に削減でき、パフォーマンスを向上させることができます。

Recommended Book / barbe_generative_library

Grid-Systems-Raster-Systeme

Grid systems in graphic design – Josef Müller-Brockmann

グリッドシステムとは。

グリッドシステムとは、連続した行と列に基づいてテキストやイメージを配置しデザインの整合性と視認性を高めるレイアウト手法です。元々は印刷レイアウトのために考えられたものですが、現在ではWebデザインなど、あらゆるデザイン設計において利用され、ProcessingやP5jsなど２Dでグラフィックを制作する場合にも、このグリッドシステムから学べる事は多い。

ーーーーー
► 『Grid systems in graphic design 』（Josef Müller-Brockmann）

1981年に刊行された完全日本語訳版。
初版／ 2019.11.9
ページ数／184ページ
出版社／ボーンデジタル
言語／日本語

BGD_SOUNDS on bandcamp

BGD_SOUNDSでは、bandcamp上にて、安価で利用できる膨大な著作権フリーのサウンドライブラリーを目指して日々様々な音源ライブラリーを増やしています。音源のほとんどは、192kHzの32bitの高音質にて録音。音楽制作や映像制作など用途に合わせて利用可能です。また、Sound visualization Penplot artも定期的に販売しています。

BGD_CLUB（月額サブスクリプション）も低価格から始めており、すべてのライブラリーにアクセスし自由にダウンロードすることも可能です。

Link / BGD_SOUNDS on bandcamp