1

私は現在、ポイントクラウドを多く扱っており、特定の最大距離でポイントをセグメントにクラスター化するセグメンテーションアルゴリズムを実装しました。

それを最適化するために、各セグメントに軸に沿ったバウンディング ボックスを与え、指定されたポイントがセグメントに一致する可能性があるかどうかを確認してから、ポイントを詳しく調べて反復し、距離を計算します (実際には octree を使用しますこれにより、ポイントの大部分を取り除くことができます。)

私は gnuprof を介してプログラムを実行しました。結果は次のとおりです。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 52.42      5.14     5.14 208995661     0.00     0.00  otree_node_out_of_bounds
 19.60      7.06     1.92 189594292     0.00     0.00  otree_has_point_in_range
 11.33      8.17     1.11   405834     0.00     0.00  otree_node_has_point_in_range
  9.29      9.08     0.91   352273     0.00     0.00  find_matching_segments
 [...]

ご覧のとおり、計算時間の大部分はotree_node_out_of_bounds次のように実装されて費やされます。

int otree_node_out_of_bounds(struct otree_node *t, void *p)
{
    vec3 *_p = p;
    return (_p->x < t->_llf[0] - SEGMENTATION_DIST 
        || _p->x > t->_urb[0] + SEGMENTATION_DIST
        || _p->y < t->_llf[1] - SEGMENTATION_DIST 
        || _p->y > t->_urb[1] + SEGMENTATION_DIST
        || _p->z < t->_llf[2] - SEGMENTATION_DIST 
        || _p->z > t->_urb[2] + SEGMENTATION_DIST);
}

ここでSEGMENTATION DISTはコンパイル時定数で、gcc が一定の折り畳みを行えるようにします。_llfおよび_urbは型float[3]であり、octree の境界ボックスを表します。

したがって、私の質問は基本的に、この関数でいくつかの卑劣な最適化を行うことは可能ですか、またはより一般的に言えば、AABB で境界チェックを行うより効率的な方法があるか、または別の言い方をすれば、高速化できますか? C/gcc マジックを使ってどうにかして比較？

この質問に答えるためにさらに情報が必要な場合は、お知らせください:)

ありがとう、アンディ。

4

2 に答える 2

2

これは、膨大な回数呼び出される小さなリーフ関数です。呼び出しを測定するオーバーヘッドは、関数自体のコストに比べて大きいため、プロファイリング結果は常にこれらの関数のコストを過大評価します。通常の最適化では、(最終的にこのテストを呼び出す外側のループのレベルでの) 操作全体のコストは、実行時間全体の割合が低くなります。これは、プロファイリングを有効にして関数をインライン化することで確認できる場合があります (例: を使用__attribute__((__always_inline__)))。

あなたの関数は書かれているようにうまく見えます。そのような個々のテストをあなたが持っている以上に最適化できるとは思えません (もしできたとしても、それは劇的ではありません)。操作全体を最適化したい場合は、より高いレベルで行う必要があります。

  • 別の構造 (octree の代わりに kd-tree など) を試すか、データのパターンを利用するまったく新しいアルゴリズムを試すことができます。
  • ループを「各ポイント チェック otrees」から「各 otree チェック ポイント」に反転させると、境界データを何度も再利用できます。
  • 最も効率的な方法でデータ (おそらくポイント) にアクセスしていることを確認できます (つまり、ランダムにジャンプするのではなく、シーケンシャルに)。
  • 再構築されたループを使用すると、SSE を使用して単一の命令で複数の境界テストを実行できます (分岐なしで!)。
于 2013-02-04T07:34:01.087 に答える
-1

私には良さそうです。私が考えることができる唯一のマイクロ最適化は、 *_p を static として宣言することです

于 2013-01-29T09:26:29.933 に答える