computational-geometry - kd ツリーは三角形を維持するのに適していますか、それとも従来の kd ツリー構築アルゴリズムを変更する必要がありますか?

Question

wiki で kd ツリーの説明を読んだことがあります。wiki によると、kd ツリーはポイントを保持します。私は三角形のメッシュを持っており、円柱との効果的な計算の交差と点への距離のクエリのための構造が必要です。私が理解しているように、メッシュを平面で分割すると、多くの三角形がその平面と交差する可能性があります。それで、私は何をすべきですか？三角形のコピーを左右の子ボックスに入れるか、交差する三角形を分割しますか?

Answer 1

交差する三角形を分割する必要があります。これを行う方法については、KD ツリーを使用するオープンソースのレイ トレーシング アルゴリズムを参照するか、Google Scholar で学術論文を検索してください。

分割面を選択する良い方法については、Surface Area Heuristic を参照してください。これは一般的にレイ トレーシングで使用されますが、状況によっては適用できる場合もあります。