A min/max ''k''d-tree is a
''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
Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a came ...
isosurface
An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value (e.g. pressure, temperature, velocity, density) within a volume of space; in other words, it is a level set of a continuous fu ...
s/MIP (
maximum intensity projection
In scientific visualization, a maximum intensity projection (MIP) is a method for 3D data that projects in the visualization plane the voxels with maximum intensity that fall in the way of parallel rays traced from the viewpoint to the plane of p ...
). 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 max ''k''d-trees are an optimal choice for visualizing scalar fields defined on rectilinear grids (see ). Similarly an
implicit
Implicit may refer to:
Mathematics
* Implicit function
* Implicit function theorem
* Implicit curve
* Implicit surface
* Implicit differential equation
Other uses
* Implicit assumption, in logic
* Implicit-association test, in social psychology
...
min/max kd-tree may be used to efficiently evaluate queries such as terrain
line of sight
The line of sight, also known as visual axis or sightline (also sight line), is an imaginary line between a viewer/observer/spectator's eye(s) and a subject of interest, or their relative direction. The subject may be any definable object taken ...
.
[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.]
See also
*
''k''-d tree
*
implicit ''k''d-tree
References
{{DEFAULTSORT:Min max kd-tree
Computer graphics data structures
Trees (data structures)