c - C の計算効率の高い 3 次元配列

Question

3 次元の一連の偏微分方程式を数値的に解こうとしています。各方程式で、ポイントの未知数の次の値は、最も近いポイントの各未知数の現在の値に依存します。

効率的なコードを作成するには、各値がメモリから 1 回だけ呼び出されるように、3 次元のポイントを (1 次元の) メモリ空間の近くに保つ必要があります。

八分木の使用を考えていましたが、誰かがより良い方法を知っているかどうか疑問に思っていました。

Answer 1

ツリー方式の 1 つの代替方法: Morton-Order を使用してデータをエンコードします。

3 次元では、次のようになります。座標コンポーネントを取得し、各ビットに 2 つのゼロ ビットをインターリーブします。ここではバイナリで表示されます: 11111b は 1001001001b になります

これを行う C 関数は次のようになります (わかりやすくするために 11 ビットのみを示しています)。

int morton3 (int a)
{
  int result = 0;
  int i;
  for (i=0; i<11; i++)
  {
     // check if the i'th bit is set.
     int bit = a&(1<<i);
     if (bit)
     {
       // if so set the 3*i'th bit in the result:
       result |= 1<<(i*3);
     }
  }
  return result;
}

この関数を使用して、次のようにポジションを組み合わせることができます。

index = morton3 (position.x) + 
        morton3 (position.y)*2 +
        morton3 (position.z)*4;

これにより、3 次元のインデックスが 1 次元のインデックスに変わります。最良の部分: 3D 空間で近い値は、1D 空間でも近いです。互いに近い値に頻繁にアクセスする場合は、キャッシュの局所性に関してモートン順序エンコーディングが最適であるため、非常に高速になります。

morton3 の場合は、上記のコードを使用しない方がよいでしょう。小さなテーブルを使用して、一度に 4 ビットまたは 8 ビットを検索し、それらを結合します。

お役に立てば幸いです、ニルス

Answer 2

Octtreesは行く方法です。配列を 8 つのオクタントに分割します。

1 2
3 4

---

5 6
7 8

そして、上記のように、1、2、3、4、5、6、7、8 の順にメモリに配置します。これを各オクタント内で再帰的に繰り返して、ベース サイズ (おそらく約 128 バイト程度) になるまで (これは単なる推測です。最適なカットオフ ポイントを決定するには、必ずプロファイルを作成してください)。これは、単純なレイアウトよりもはるかに優れたキャッシュの一貫性と参照の局所性を備えています。

Answer 3

『 Foundations of Multidimensional and Metric Data Structures』という本は、どのデータ構造が範囲クエリで最も高速かを判断するのに役立ちます: octrees、kd-trees、R-trees ... また、ポイントをメモリ内に保持するためのデータ レイアウトについても説明しています。