私は現在、物理エンジン（趣味のプロジェクト）用のKDTreeを書いています。
KDTreeにはポイントが含まれていません。代わりに、環境内のさまざまなオブジェクトをバインドするAxisAlignedバウンディングボックスが含まれています。
私の問題は、KDTreeノードがいっぱいになったときに分割する方法を決定することです。私は2つの方法を試しています：
方法1：ノードを常に最大軸上で正確に半分に分割します。
- これには、かなり等間隔に配置されたツリーという利点があります。
- 大きな欠点：オブジェクトがノードの小さな領域に集中している場合、冗長なサブディビジョンが作成されます。これは、すべてのボリュームが正確に半分に分割されているためです。
方法2：オブジェクトを含むノードの領域を見つけます。最大軸上でその領域を半分に分割する平面上でノードを分割します。例-すべてのオブジェクトがノードの下部に集中している場合、オブジェクトは縦方向に分割され、それによって下部が2つに分割されます。
- これにより、上記の方法の問題が解決します
- 同じ平面上に存在するもの（たとえば地形）にインデックスを付けると、長くて狭いノードが作成されます。同じ平面上にない他のオブジェクトを後で追加する場合、これらの細長いノードは非常に貧弱なインデックスを提供します。
したがって、ここで探しているのは、KDツリーノードを分割するためのより良い方法です。これが物理エンジンになることを考えると、決定はリアルタイムで行われるのに十分単純である必要があります。