Loading article…
最小/最大k d ツリーは、ノードに 2 つのスカラー値 (最小値と最大値) が割り当てられたk dツリーです。内部ノードの最小値/最大値は、その子ノードの最小値/最大値の最小値/最大値と等しくなります。
工事
最小/最大k d-tree は再帰的に構築できます。ルート ノードから始めて、分割面の方向と位置が評価されます。次に、子の分割面と最小/最大値が再帰的に評価されます。現在のノードの最小/最大値は、単にその子の最小値/最大値の最小値/最大値です。
プロパティ
最小/最大k dtree には、 k d-treeの特性の他に、内部ノードの最小/最大値がそれぞれいずれかの子ノードの最小/最大値と一致するという特別な特性があります。これにより、内部ノードに 2 ビットを格納し、最小/最大値を子ノードに割り当てることで、リーフ ノードでの最小/最大値の格納を破棄できます。各内部ノードの最小/最大値は事前にわかっており、ルート ノードの最小/最大値は別々に格納されます。各内部ノードには、2 つの最小/最大値のほかに、それらの最小/最大値がどの子に割り当てられるかを定義する 2 つのビットもあります (0: 左の子ノード、1: 右の子ノード)。子ノードの割り当てられていない最小/最大値は、現在のノードの既知の最小/最大値です。2 ビットは、最小/最大値の最下位ビットに格納されることもあり、そのため、それらを下方/上方に分数化して近似する必要があります。
完全なバイナリk d ツリーのリーフ ノードはツリーのノードの半分であるため、結果として生じるメモリの削減は小さくありません。
アプリケーション
最小/最大k d-tree は、等値面/MIP (最大強度投影) のレイ キャスティング に使用されます。等値面レイ キャスティングは、選択された等値が現在のノードの最小値と最大値の間にあるノードのみをトラバースします。この要件を満たさないノードは、指定された等値面を含まないため、スキップされます (空きスペース スキップ)。MIP の場合、最大値がレイに沿った現在の最大強度よりも小さい場合、ノードはトラバースされません。レイ キャスティングの好ましい視覚化の複雑さにより、市販の PC でインタラクティブなフレーム レートで非常に大きなスカラー フィールドをレイ キャスティング (および等値面の変更) できます。特に、暗黙的な最大k d-tree は、直線グリッドで定義されたスカラー フィールドを視覚化するのに最適な選択肢です ( [1] [2] [3]を参照)。同様に、暗黙的な最小/最大 kd-tree を使用して、地形の視線などのクエリを効率的に評価できます。[4]
参照
参考文献
- ^ Matthias Groß、Carsten Lojewski、Martin Bertram、Hans Hagen「高速暗黙的 KD ツリー: 大規模スカラー場の等値面レイトレーシングと最大強度投影の高速化」CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74
- ^ Ingo Wald、Heiko Friedrich、Gerd Marmitt、Philipp Slusallek、Hans-Peter Seidel「暗黙の KD ツリーを使用した等値面レイトレーシングの高速化」IEEE Transactions on Visualization and Computer Graphics (2005)
- ^ Matthias Groß (PhD, 2009) インタラクティブレイキャスティングの科学的応用に向けて
- ^ Bernardt Duvenhage「効率的な地形視線計算のための暗黙の最小/最大 KD ツリーの使用」『Proceedings of the 6th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa』、2009 年。