KDTree分割

Question

現在、物理エンジン（Hobbyプロジェクト）用のKDTreeを作成しています。

KDTreeにはポイントが含まれていません。 代わりに、環境内のさまざまなオブジェクトをバインドするAxis Alignedバウンディングボックスが含まれています。

私の問題は、KDTreeノードがフルになったときに分割する方法を決めることです。 私は2つの方法を試しています：

方法1：ノードを常に最大軸の半分に分割します。

• これは、かなり均等に間隔を置いたツリーの利点があります。
• 大きな欠点：オブジェクトがノードの小さな領域に集中していると、冗長なサブディビジョンが作成されます。これは、すべてのボリュームが正確に半分に分割されているためです。

方法2：オブジェクトを含むノードの領域を見つけます。その領域を半分に分割する平面上のノードを、その最大軸上で分割します。例 - すべてのオブジェクトがノードの底に集中している場合、長さ方向に分割して底を2つに分割します。

• これは、それが細長いノードを作成
• 同じ平面（例えば地形）上に存在するものをインデックス上記の方法で問題を解決します。同じ平面上にない他のオブジェクトを後で追加する場合、これらの細長いノードはインデックス作成が非常に貧弱です。

私がここで探しているのは、私のKD-Treeノードを分割するより良い方法です。 これが物理エンジンになることを考慮すると、決定はリアルタイムで作成するのに十分シンプルである必要があります。

Answer 1

"表面領域ヒューリスティック"（SAH）は、少なくともレイトレーシングコミュニティ内で、kd木を構築するための最良の分割方法と考えられています。アイデアは、各子のオブジェクトの数で重み付けされた2つの子空間の表面積が等しくなるように平面を追加することです。

この資料の参考資料はIngo Wald's thesisです。特に7.3章「高品質のBSP構築」を参照してください。これは、SAHの可能性をよりよく説明しています。

私は現時点では良いリンクを見つけることができませんが、実際のSAHに近似していますが、はるかに速い「ビニングされた」SAHに関する論文を見てください。

これらのことは、最近、kd木よりもはるかに普及しているように思われる（BVH）a.k.a.ここでも、Ingo Wald's publication pageは良い出発点です。おそらく、「SAHベースのバウンディング・ボリューム階層の高速構築」の記事を読んでからしばらくありましたが、

OMPF forumsもこの種のことについて話し合うのに適しています。

希望に役立ちます。がんばろう！

Answer 2

前提が動きの多いジオメトリである物理エンジンの場合は確かに、bvhはおそらくより良い選択ですが、それらは非常に速くトラバースされませんが、構築がはるかに高速で、再構成/すべてのフレーム（一連のフレームにわたって並行して実行することができ、その間に再構成されたbvhで十分です。waldを参照してください）。

パーティクルや光子などのボリュームを持たないエンティティを扱う場合は例外ですが、境界を解決する必要がないという事実によってkdツリーの構築が単純化されます個々のプリミティブのそれは本当にアプリケーションに依存します。優れた物理エンジンは、空間加速構造のバランスの取れた組み合わせを使用する必要があります。一般的に、浅いオクトリーと呼ばれる広範な位相分割を解決し、葉ノードをあなたがしていることの性質に適した別のスキームで拡張することです。静的なジオメトリ、特に2dで、構造が変化していないときは、できるだけ多くの異なるスキームや構造を試して、いつ、どのようにしてうまく動作するかを感じることが最善です。