View source for Min/max kd-tree

{{lowercase|title=min/max kd-tree}}
A '''min/max ''k''d-tree''' is a [[K-d tree|''k''-d tree]] with two scalar values - a minimum and a maximum - assigned to its nodes. The minimum/maximum of an inner node is equal to the minimum/maximum of its children's minima/maxima.
==Construction==
Min/max ''k''d-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 ''k''dtree has - besides the properties of an ''k''d-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 ''k''d-trees are one half of the tree's nodes.
==Applications==
Min/max ''k''d-trees are used for [[ray casting]] [[isosurface]]s/MIP ([[maximum intensity projection]]). Isosurface ray casting only traverses nodes for which the chosen isovalue lies between the min/max values of the current node. Nodes that do not fulfill this requirement do not contain an isosurface to the given isovalue and are therefore skipped (empty space skipping). For MIP, nodes are not traversed if their maximum is smaller than the current maximum intensity along the ray. The favorable 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. Especially [[implicit kd tree|implicit max ''k''d-trees]] are an optimal choice for visualizing scalar fields defined on rectilinear grids (see <ref>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</ref><ref>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)</ref><ref>Matthias Groß (PhD, 2009) [http://kluedo.ub.uni-kl.de/volltexte/2009/2361/ Towards Scientific Applications for Interactive Ray Casting]</ref>). Similarly an [[implicit kd tree|implicit]] min/max kd-tree may be used to efficiently evaluate queries such as terrain [[Line of sight (gaming)|line of sight]].<ref>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.</ref>
==See also==
* [[K-d tree|''k''-d tree]]
* [[implicit kd tree|implicit ''k''d-tree]]
==References==
<references/>
{{DEFAULTSORT:Min max kd-tree}}
[[Category:Computer graphics data structures]]
[[Category:Trees (data structures)]]