1

プロファイラーを使用して、まだ十分に高速に実行されていないコードを調べました。次の関数にほとんどの時間がかかり、この関数の時間の半分が に費やされたことがわかりましたfloor。現在、この関数を最適化するか、1 レベル上に移動してこの関数の呼び出しを減らすという 2 つの可能性があります。最初のものが可能かどうか疑問に思います。

int Sph::gridIndex (Vector3 position) const {
    int mx = ((int)floor(position.x / _gridIntervalSize) % _gridSize);
    int my = ((int)floor(position.y / _gridIntervalSize) % _gridSize);
    int mz = ((int)floor(position.z / _gridIntervalSize) % _gridSize);

    if (mx < 0) {
        mx += _gridSize;
    }
    if (my < 0) {
        my += _gridSize;
    }
    if (mz < 0) {
        mz += _gridSize;
    }

    int x = mx * _gridSize * _gridSize;
    int y = my * _gridSize;
    int z = mz * 1;
    return x + y + z;
}

Vector33 つの float を格納し、いくつかのオーバーロードされた演算子を提供する単純なクラスです。_gridSize型intで_gridIntervalSizeあり、floatです。_gridSize ^ 3 個のバケットがあります。

この関数の目的は、ハッシュ テーブルのサポートを提供することです。すべての 3d ポイントはインデックスにマップされ、サイズ _gridIntervalSize ^ 3 の同じボクセルにあるポイントは同じバケットに着陸する必要があります。

4

3 に答える 3

2

数学が関係する場合の最適化の第 1 のルール: 除算、平方根、および三角関数を削除します。

inverse_size = 1 / _gridIntervalSize; ....that should be done only once, not once per call.

int mx = ((int)floor(position.x * inverse_size) % _gridSize);
int my = ((int)floor(position.y * inverse_size) % _gridSize);
int mz = ((int)floor(position.z * inverse_size) % _gridSize);

また、mod 操作を削除することをお勧めします。これは別の区分であるためです。グリッド サイズが 2 のべき乗である場合は、 & (gridsize-1) を使用できます。これにより、下部の条件付きコードを削除することもできます。これも大きな節約になります。

別の注意として、オーバーロードされた演算子を使用すると、問題が発生する可能性があります。これはここではデリケートなテーマなので、試してみて、自分で判断してください。

于 2010-12-08T12:10:30.003 に答える
1

floor負の値が可能であり、キャスト時のデフォルトの切り捨てによる異常が発生しないようにするために使用すると仮定しますint(値は両側からゼロに向かって丸められ、特大のボクセルが作成されます)。

_gridIntervalSizeベクトル内の各値に対して安全な最大負値を指定できる場合は、キャストの前にその (負の) 値、または最も近い のより負の倍数を減算し、 を削除できますfloor。

を使用fmodすると、安全な最も負の値を確保し、 integer を置き換えることができますが、%おそらく最適化に反するものです。それでも、簡単な変更として、チェックする価値があるかもしれません。

また、プラットフォームがベクトル命令をサポートしているかどうか、およびコンパイラーがそれらの使用を容易に奨励できるかどうかを確認してください。x86 チップには確かに整数ベクトル命令と float (最初は古い Pentium 1 MMX 命令) があり、「通常の」CPU 命令セットよりもはるかに効率的にこれを処理できる可能性があります。これは、コンパイラのベクトル命令組み込み関数のリストを掘り下げて、手作業による最適化を行う場合さえあるかもしれません。最初にコンパイラができることを確認してください。この種の最適化コンパイラがすでにどの程度のことをしてくれるかはわかりません。

マイクロ最適化のおそらく些細な部分...

return (mx * _gridSize + my) * _gridSize + mz;

1 つの整数乗算を保存します。もちろん些細なことであり、コンパイラはとにかくそれをキャッチするかもしれませんが、これは古い習慣です。

ああ、先頭のアンダースコアに注目してください。これらは予約済みの識別子です。問題が発生する可能性は低いですが、発生しても文句は言えません。

編集

を回避する別の方法floorは、正と負を別々に処理することです。グリッド セルの端にぶつかるアイテムが間違ったセルにある可能性があることを受け入れる場合 (フロートは概算と見なされるため、いずれにせよ可能性があります)。負の場合にオフセットを適用するだけで、切り捨てを補正するためにほぼ-1正確にゼロから引き離すことができます。後でビットをいじる仮数部のインクリメントを検討するかもしれませんが（期待するセルにすでに整数値を取得するため）、これはおそらく不要です。

サイズに 2 の累乗の制限を課すことができる場合、float からグリッド位置を効率的に抽出し、乗算、フロア、および%x、y、z のそれぞれの一部またはすべてを回避する、少し手間のかかる方法があるかもしれません。 、標準の浮動小数点表現を想定しています (つまり、これは移植性がありません)。ここでも、プラスとマイナスを別々に扱います。指数を抽出し、それに応じて仮数をビットシフトしてから、不要なビットをマスクします。

于 2010-12-08T11:50:26.607 に答える
0

実際の速度を向上させるには、階層の上位を調べる必要があると思います。つまり、ハッシュマップにポイントを保存することが本当に最も効率的な解決策なのでしょうか? Vector3 配列の配列があると仮定します。

Vector3 * ポイント [サイズ][サイズ][サイズ]

ここで、3D 配列の各要素は Vector3 の配列です。

使用しているアルゴリズムは、各 Vector3 配列内のポイントの均一な分布を保証していないため、問題になる可能性があります。内のポイントのクラスターは_gridIntervalSize、同じ配列にマップされます。

別の方法として、バイナリ ツリーに似ていますが、各ノードに 8 つの子ノードがあるオクト ツリーを使用する方法があります。各ノードには、ノードがカバーするボリュームを定義する最小/最大 x/y/z 値が必要です。ツリーに値を追加するには:

ポイントを含むことができる最小のノードを見つけるための再帰的な検索ツリー

ポイントをノードに追加

ノード内のポイント数 > ノード内のポイント数の上限の場合

子ノードを作成し、ポイントを子ノードに移動します

特定の軸に沿った値の変動がほとんどない場合は、四分木を使用できます。もう 1 つの方法は、BSP を使用することです。つまり、世界を 2 つに分割し、再帰的にポイントを追加するコンテナーを見つけます。繰り返しますが、これらは動的にすることができます。

float を int に変換し、分割面を整数値に配置すると、プロセスも高速化されます。

上記の用語をグーグルで検索すると、アルゴリズムのより詳細な分析につながります。

最後に、無限平面の座標に浮動小数点数 (または倍精度浮動小数点数) を使用するのは悪い考えです。(0,0,0) から遠ざかるほど、精度が低下します (値が大きくなるにつれて、浮動小数点値間のギャップが大きくなります) ）。精度を維持するには、浮動小数点値を「リセット」する必要があります。1 つの方法は、スペースを「並べて表示」し、座標を変更して整数部分と浮動小数点部分を使用することです。整数部分は「タイル」を定義し、浮動小数点部分はタイル内の位置を定義します。この方法では、はるかに単純なハッシュ方法が得られます。整数部分を使用するだけで、floor必要な呼び出しはなく、整数計算のみが必要です。もう 1 つの方法は、浮動小数点値ではなく固定小数点値を使用することですが、これでは精度が制限されます。

座標系の最上位の要件が何であるかを拡張できれば、おそらくより優れたアルゴリズムを利用できるでしょう。

于 2010-12-08T13:11:11.600 に答える