Kd アルゴリズムは、2 つのサブツリーの作成に使用される 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 ツリーの実装にすぎないため)。
更新: 切断点に従って間隔の配列 [t0,t1] を 2 つの間隔の配列に分割できるアルゴリズムまたはヒューリスティックを検索しました。左の配列には、切断点の左側の間隔と、切断点を含む間隔が含まれます。右側の配列についても同様です。両方の配列の間隔の数はほぼ同じでなければならず、重複する間隔の数はできるだけ少なくする必要があります。このアルゴリズムの複雑さは O(n^2) ではない場合があります。