暗黙のkdツリー

暗黙のk -d ツリーは、直線グリッド上に暗黙的に定義されたk -d ツリーです。その分割面の位置と方向は明示的には指定されませんが、ツリーのノードに属する超長方形上に定義された再帰分割関数によって暗黙的に指定されます。各内部ノードの分割面は、基礎となるグリッドのグリッド面に配置され、ノードのグリッドを 2 つのサブグリッドに分割します。

「最小/最大k -d ツリー」と「暗黙のk -d ツリー」という用語は、混同されることがあります。これは、「暗黙のk -d ツリー」という用語を使用した最初の出版物^{[1] が}、実際には明示的な最小/最大k -d ツリーを使用していたものの、暗黙的に与えられた等値面のレイ トレーシングに使用できることを示すために、それらを「暗黙の k-d ツリー」と呼んでいたためです。ただし、この出版物では、2の累乗の辺の長さを持つ整数の超長方形上にのみ構築できるという制限がある暗黙の k-d ツリーのサブセットであるスリム k-d ツリーも使用されていました。ここで定義されている暗黙のk - dツリーは、最近導入され、コンピューター グラフィックスで使用されています。^{[2] [3]暗黙の}k -d ツリー ノードに属性を割り当てることができるため、ノードに最小値/最大値が割り当てられた暗黙のk -d ツリーを「暗黙の最小/最大k -d ツリー」と呼ぶことができます。

暗黙のk -d ツリーは、通常、明示的に構築されません。ノードにアクセスすると、ツリーを定義する特定の分割関数を使用して、その分割面の方向と位置が評価されます。分割関数が異なると、同じ基礎グリッドに対して異なるツリーが生成される場合があります。

分割関数は、特別な目的に合わせて調整できます。特別な分割関数クラスの 2 つの仕様を以下に示します。

• 非退化分割関数では、退化ノード（対応する整数超長方形の体積がゼロであるノード）の作成は許可されません。対応する暗黙のk -d ツリーは、 n 個のリーフ ノードに対してn - 1 個の内部ノードを持つ完全なバイナリ ツリーです。対応する暗黙のk -d ツリーは、非退化の暗黙のk -d ツリーです。
• 完全な分割関数は、対応する暗黙のk -d ツリーのリーフ ノードが単一のグリッド セルであり、グリッドで指定されたグリッド セルの数よりも 1 つの内部ノードが少ない、非退化分割関数です。対応する暗黙のk -d ツリーは、完全な暗黙のk -d ツリーです。

完全な分割関数の例としては、グリッド中央値分割関数があります。これは、暗黙のk次元ツリーの各ノードに属するk次元の整数ハイパー長方形hyprec[2][k]を使用して、かなりバランスの取れた暗黙のk次元ツリーを作成します。ハイパー長方形は、直線グリッドのどのグリッドセルが対応するノードに属するかを定義します。このハイパー長方形の体積が 1 に等しい場合、対応するノードは単一のグリッドセルであるため、それ以上分割されず、リーフノードとしてマークされます。それ以外の場合は、ハイパー長方形の最長範囲が方向oとして選択されます。対応する分割平面p は、その方向に沿ってハイパー長方形のグリッド中央値に最も近いグリッド平面に配置されます。

分割平面の方向o :

o = min{argmax(i = 1 ... k : (hyprec[1][i] - hyprec[0][i]))}

分割面の位置p :

p = roundDown((hyprec[0][o] + hyprec[1][o]) / 2)

暗黙のk -d ツリーの利点は、分割された平面の方向と位置を明示的に保存する必要がないことです。

しかし、一部のアプリケーションでは、分割面の方向と位置に加えて、ツリー内部ノードのさらなる属性が必要です。これらの属性は、たとえば、ノードに属するサブグリッドが対象かどうかを定義する単一のビットまたは単一のスカラー値である場合があります。完全な暗黙のk -d ツリーの場合、適切なサイズの属性配列を事前に割り当て、ツリーの各内部ノードをその割り当てられた配列内の一意の要素に割り当てることができます。

グリッド内のグリッドセルの数は、グリッドに属する整数超長方形の体積に等しくなります。完全な暗黙のk -d ツリーにはグリッドセルよりも 1 つ少ない内部ノードがあるため、格納する必要がある属性の数は事前にわかっています。関係「整数超長方形の内部ノードの体積」は、完全な分割関数とともに、割り当てられた配列内の一意の要素を各分割面に割り当てる再帰式を定義します。対応するアルゴリズムは、以下の C 疑似コードで示されています。

// 完全な暗黙の kd ツリーの内部ノードに属性を割り当てる

// 整数ヘルプのハイパー長方形 hyprec を作成します (その体積 vol(hyprec) は葉の数に等しいです) 
int hyprec [ 2 ][ k ] = { { 0 , ..., 0 }, { length_1 , ..., length_k } }; // 暗黙の kd ツリー全体の属性の配列を一度割り当てますattr * a = new attr [ volume ( hyprec ) - 1 ];              

      

attr implicitKdTreeAttributes ( int hyprec [ 2 ][ k ], attr * a ) { if ( vol ( hyprec ) > 1 ) // 現在のノードは内部ノードです{ // 基になる完全な分割関数を使用して、分割平面の方向 o と位置 p を評価しますint o , p ; completeSplittingFunction ( hyprec , & o , & p ); // 子の整数ハイパー長方形 hyprec_l と hyprec_r を評価しますint hyprec_l [ 2 ][ k ], hyprec_r [ 2 ][ k ]; hyprec_l = hyprec ; hyprec_l [ 1 ][ o ] = p ; hyprec_r = hyprec ; hyprec_r [ 0 ][ o ] = p ; // 子のメモリ位置 a_l と a_r を評価しますattr * a_l = a + 1 ; attr * a_r = a + vol ( hyprec_l ); // 子の属性 c_l と c_r を再帰的に評価しますattr c_l = implicitKdTreeAttributes ( hyprec_l , a_l ); attr c_r = implicitKdTreeAttributes ( hyprec_r , a_r ); // 子の属性を現在の属性 c にマージしますattr c = merge ( c_l , c_r ); // 現在の属性を保存して返しますa [ 0 ] = c ; return c ; } // 現在のノードはリーフ ノードです。対応するグリッドセルに属する属性を返しますreturn attribute ( hyprec ); }    

      
  
    
      
      
    
      
            
      
            
      
    
         
         
    
        
        
    
        
    
      
     
  
  
   

このアルゴリズムはすべての直線グリッドで機能することに注意してください。対応する整数超長方形の辺の長さは、必ずしも 2 の累乗である必要はありません。

暗黙的な最大k d ツリーは、レイ キャスティング 等値面/MIP (最大強度投影)に使用されます。各内部ノードに割り当てられる属性は、ノードに属するサブグリッドで指定された最大スカラー値です。スカラー値がレイに沿って検索された等値値 / 現在の最大強度よりも小さい場合、ノードはトラバースされません。暗黙的な最大k d ツリーの低いストレージ要件とレイ キャスティングの好ましい視覚化の複雑さにより、市販の PC でインタラクティブなフレーム レートで非常に大きなスカラー フィールドをレイ キャスティング (および等値面の変更) できます。同様に、暗黙的な最小/最大 k d ツリーを使用して、地形の視線などのクエリを効率的に評価できます。^[4]

n 個のグリッドセルを持つk次元グリッドにまたがる暗黙のk d ツリーが与えられます。

• ツリーのノードに属性を割り当てるには時間がかかります。${\displaystyle \mathrm {O} (kn)}$
• ノードに属性を保存するとメモリが必要になります。${\displaystyle \mathrm {O} (n)}$
• 対応する暗黙的な最大k -d ツリーを使用して、基礎となるスカラー フィールドに等値面/MIP をレイ キャストするには、およそ時間がかかります。${\displaystyle \mathrm {O} (\log(n))}$

• k -d ツリー
• 最小/最大k -d ツリー