三角メッシュのためのKDツリーが遅くなりました

Question

KDアルゴリズムは、2つの新しい配列（左右のプリミティブ）を作成するために、プリミティブの配列をパーティション化することで、ルートBSPノードの作成から始まります。サブツリー

左右のプリミティブは、所与のプリミティブアレイを2つのアレイに分割することによって計算されます。分割面位置は、各三角形の間隔の中央値（所与の軸（x、y、z）に投影された）の中央値を取ることによって計算される。

X座標を持つ三角形：1,2,3は、ミドルポイント1=（3-1）/ 2（X軸に沿って）を有する。 X座標の三角形：2,3,8は、ミドルポイント3=（8-2）/ 2（X軸に沿って）を有する。 X座標を持つ三角形：4,3,8は、ミドルポイント2.5=（8-3）/ 2（X軸に沿って） これら3つの三角形を含むプリミティブアレイは、yz平面に平行なx= 2.5（中央値）を介して平面によって分割される。結果として得られた左のプリミティブアレイは3つの三角形を含み、結果として得られる右プリミティブアレイは3つの三角形を含みます。

左右のプリミティブを持つ2つのアレイを使用して、KDノードの左右のサブツリーを作成します（プリミティブはリーフノードでのみ保存されます）。

左サブツリーの場合：

If (the left primitives are empty) then the left subtree points to NULL
else if (the number of left primitives is smaller than the minimal number || the depth == 1) then the left subtree is a leaf node
else the left subtree is another tree.

create the left subtree with the left primitives along the axis (++axis % 3) with --depth as depth and the same minimal number.

.

右のサブツリーに類似しています。

アルゴリズムは機能していますが、ツリーがあまりパーティション化されていないため、非常に遅いです。 5500の三角形のバニーをレイトリングすると、1つの三角形の葉ノードがたくさんあり、最後のリーフノードは762の三角形を含んでいます。

は、より良い分割アルゴリズムがあります（鉱山は表面に変換された単一のポイントのためのKDツリーの実装です）。

更新：私は、切断点に従って、間隔の配列を2つの間隔に分割することができるアルゴリズムまたはヒューリスティックを検索しました。左側の配列は、切断点の左側の間隔と、切断点を含むものを含みます。右アレイに似ています。両方のアレイはほぼ同じ数の間隔を持たなければならず、重複した間隔の数は少なくともできるだけ少なくて済む必要があります。このアルゴリズムは複雑さのO（n ^ 2）ではないかもしれません。

Answer 1

ミドルポイントの計算は間違って見えます。X座標2,3,8を持つ三角形の場合、ミドルポイントは2 +（8-2）/ 2= 5にする必要があります。X座標1,2,3の三角形には、ミドルポイント1 +（3-1）/ 2があるはずです。= 2.不平衡葉を説明することができます。

Answer 2

最適な分割を見つけるために表面積の発見的（SAH）を使用することをお勧めします。

サブツリーとの光線の交差確率は、そのサブツリーの境界箱の表面積に比例します。

しかし、葉サブツリーにたくさんの三角形が含まれている場合 - それはそれらすべてを横断する必要があることを意味します。

だから、SAHの主な考え方は両方を最小限に抑えることです：サブツリーの表面積とそれらの内部の多角形の数。

小さい2Dの例を見てみましょう：

また、SAHの使用 - KDツリーの建物中の終了条件を決定するのに役立ちます。

1）kd-treeの各ステップで、サブツリーの分割前に - あなたは現在のサブツリーのSAHを計算しなければなりません

SAH_initial = number_of_polygons * area_of_subtree

.

2）最適な現在のサブツリーの分割のSAHを見つけなければならないことをAFTRE

SAH_optimal = min(S_left * N_left + S_right * N_right)

.

3）比較しなければならないAFTRE：

define some split_cost
...

if( SAH_optimal + split_cost < SAH_initial ) { 
   it would be optimal to split that subtree
} else {
   you don't have to split current subtree
}

.

これは別の Shahの審判を含みます。