Min/max kd-tree

Min/max kd-tree

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 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 are the children's splitting planes and min/max values 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 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 "k"d-trees are an optimal choice for visualizing scalar fields defined on rectilinear grids (see also [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] , [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)] ).

ee also

* "k"d-tree
* implicit "k"d-tree

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • 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. Contents 1 Construction 2 Properties 3… …   Wikipedia

  • Min-max heap — A min max heap is a double ended priority queue implemented as a modified version of a binary heap. Like a binary heap, a min max heap is represented as a complete binary tree. Unlike a binary heap, though, the nodes in this tree do not obey the… …   Wikipedia

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Implicit kd-tree — An implicit k d tree is a k d tree defined implicitly above a rectilinear grid. Its splitting planes positions and orientations are not given explicitly but implicitly by some recursive splitting function defined on the hyperrectangles belonging… …   Wikipedia

  • Kd-tree — In computer science, a k d tree (short for k dimensional tree ) is a space partitioning data structure for organizing points in a k dimensional space. k d trees are a useful data structure for several applications, such as searches involving a… …   Wikipedia

  • Steiner Tree — Das Steinerbaumproblem (oft mit STEINER TREE notiert), ein nach dem Schweizer Mathematiker Jakob Steiner benanntes Problem der Graphentheorie, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Beim Steinerbaumproblem sucht man in… …   Deutsch Wikipedia

  • Expectiminimax tree — An expectiminimax tree is a specialized variation of a minimax tree for use in artificial intelligence systems which play games of chance. In addition to min and max nodes of the traditional minimax tree, this variant has chance nodes, which take …   Wikipedia

  • Leftist tree — A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s value which is the distance to the nearest leaf. In contrast to a binary heap , a leftist tree attempts to be very unbalanced. In… …   Wikipedia

  • Metric tree — This article is about the data structure. For the type of metric space, see Real tree. A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle… …   Wikipedia

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”