7

私をお勧めできますか...

  • AABB ツリーの実証済みの軽量 C / C++ 実装ですか?
  • または、代わりに、別の効率的なデータ構造に加えて、軽量の C / C++ 実装を使用して、多数の三角形と多数の光線が交差する問題を解決しますか?

「大きい数」とは、光線、三角形ともに数百万という意味です。

AABB ツリーが CGAL ライブラリの一部であり、おそらく Bullet のようなゲーム物理ライブラリの一部であることは承知しています。ただし、プロジェクトに膨大な追加ライブラリのオーバーヘッドは必要ありません。理想的には、小さな float 型のテンプレート化されたヘッダーのみの実装を使用したいと思います。また、プロジェクトに簡単に統合できる限り、CPP ファイルの束を使用することもできます。への依存boostは問題ありません。

はい、グーグルで検索しましたが、成功しませんでした。

私のアプリケーション コンテキストはメッシュ処理であり、レンダリングではありません。簡単に言うと、参照メッシュのトポロジーを 3D スキャンからメッシュのジオメトリに変換しています。頂点から、参照メッシュの法線に沿って 3D スキャンに向かって光線を発射しています。これらの光線とスキャンとの交差を回復する必要があります。

編集

いくつかの回答/コメントは、最近傍データ構造を指していました。最近隣法を使用してレイ メッシュの交差にアプローチするときに発生する問題について、小さな図を作成しました。最近隣法は、多くの場合に機能するヒューリスティックとして使用できますが、AABB ツリーのように実際に問題を体系的に解決できるとは確信していません。

ここに画像の説明を入力

4

3 に答える 3

2

このコードは少し古く、3DS Max SDK を使用していますが、C++ でのオブジェクト間の衝突変形のためのかなり優れたツリー システムを提供します。クワッドツリーなのか、AABB ツリーなのか、OBB ツリーなのか、一見しただけではわかりません (コメントも少し控えめです)。

http://www.max3dstuff.com/max4/objectDeform/help.html

Max から独自のシステムへの変換が必要になりますが、努力する価値があるかもしれません。

于 2013-03-03T23:03:18.333 に答える
1

ANN ライブラリを試してください: http://www.cs.umd.edu/~mount/ANN/

それは「おおよその最近傍」です。少し違うものを探していると思いますが、これを使用してデータ処理を高速化する方法は次のとおりです。

  1. ポイントを ANN にフィードします。
  2. レイキャストする各頂点の周囲のユーザーが選択可能な (これを「メッシュごとのノブ」と考えてください) 半径を照会し、範囲内にあるメッシュ頂点を見つけます。
  3. その範囲内にある三角形のみを選択し、法線に沿ってレイ トレースして目的の三角形を見つけます。

検索範囲を慎重に選択することで、精度を損なうことなく大幅な高速化を確実に実現できます。

于 2013-02-19T13:05:30.183 に答える
1

リアルタイムの要件がない場合は、まず力ずくで試してみます。

1M * 1M ray->triangle テストは、(CPU で) 実行するのに数分以上かかることはありません。

それが問題である場合、次に行う最善の方法は、ターゲット メッシュ内の三角形/ポリゴン間の隣接グラフ/関係を計算することにより、検索領域を制限することです。最初の推測が失敗した後、隣接する三角形を試すことができます。もちろん、これはセルフ オクルージョンの欠如/複数のヒット ポイントに依存しています。（これは、「可視性はこの問題には当てはまりません」の1つの解釈だと思います）。

また、トポロジーがどの程度病的であるかにもよりますが、ターゲット メッシュをユニット キューブにマッピングする環境を試し (各ピクセルは、それに投影された三角形のリストで構成されます)、最初の候補を 1 つの ray->aabb テスト + ルックアップでテストすることもできます。 .

フィードバックを考慮して、考慮すべきもう 1 つの簡単なオプションがあります。単純な 3D グリッドへの空間分割です。各次元は、x/y/z 位置のヒストグラムによって、または定期的に細分化できます。

  • 100x100x100 グリッドは、1e6 エントリの非常に扱いやすいサイズです
  • 訪問する立方体の最大数は直径に比例します (最大 300)

  • 最大 60000 個の極端なセルがあり、セルごとに 10 個の三角形の順序を示唆しています

  • 警告: 三角形は、占有するすべてのセルに配置する必要があります。保守的なアルゴリズムでは、三角形が属していないセルに配置されます。大きな三角形は、おそらくクリッピングと再構築が必要になります。

于 2013-02-15T15:37:07.610 に答える