min/max kd-tree

A min/max kd-tree is a kd-tree with two scalar values - a minimum and a maximum - assigned to its nodes. The minimum/maximum of an inner node is equal the minimum/maximum of its children's minima/maxima.

Construction

Min/max kd-trees may be constructed recursively. Starting with the root node, the splitting plane orientation and position is evaluated. Then the children's splitting planes and min/max values are evaluated recursively. The min/max value of the current node is simply the minimum/maximum of its children's minima/maxima.

Properties

The min/max kdtree has - besides the properties of an kd-tree - the special property that an inner node's min/max values coincide each with a min/max value of either one child. This allows to discard the storage of min/max values at the leaf nodes by storing two bits at inner nodes, assigning min/max values to the children: Each inner node's min/max values will be known in advance, where the root node's min/max values are stored separately. Each inner node has besides two min/max values also two bits given, defining to which child those min/max values are assigned (0: to the left child 1: to the right child). The non-assigned min/max values of the children are the from the current node already known min/max values. The two bits may also be stored in the least significant bits of the min/max values which have therefore to be approximated by fractioning them down/up.

The resulting memory reduction is not minor, as the leaf nodes of full binary kd-trees are one half of the tree's nodes.

Applications

Min/max kd-trees are used for ray casting isosurfaces/MIP (maximum intensity projection). Isosurface ray casting only traverses nodes for which the chosen isovalue lies in between the min/max value of the current node. Nodes that do not fulfill that requirement do not contain an isosurface to the given isovalue and are therefore skipped (empty space skipping). For MIP are nodes not traversed if their maximum is smaller than the current maximum intensity along the ray. The favorible visualization complexity of ray casting allows to ray cast (and even change the isosurface for) very large scalar fields at interactive framerates on commodity PCs. Especial implicit max kd-trees are an optimal choice for visualizing scalar fields defined on rectilinear grids (see also^[1],^[2],^[3]). Similarly an implicit min/max kd-tree may be used to efficiently evaluate queries such as terrain line of sight^[4].

See also

• kd-tree
• implicit kd-tree

References

1. ^ Matthias Groß, Carsten Lojewski, Martin Bertram and Hans Hagen "Fast Implicit KD-Trees: Accelerated Isosurface Ray Tracing and Maximum Intensity Projection for Large Scalar Fields" CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74
2. ^ Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek and Hans-Peter Seidel "Faster Isosurface Ray Tracing using Implicit KD-Trees" IEEE Transactions on Visualization and Computer Graphics (2005)
3. ^ Matthias Groß (PhD, 2009) Towards Scientific Applications for Interactive Ray Casting
4. ^ Bernardt Duvenhage "Using An Implicit Min/Max KD-Tree for Doing Efficient Terrain Line of Sight Calculations" in "Proceedings of the 6th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa", 2009.