An implicit k-d tree is a k-d tree defined implicitly above a rectilinear grid. Its split planes' positions and orientations are not given explicitly but implicitly by some recursive splitting-function defined on the hyperrectangles belonging to the tree's nodes. Each inner node's split plane is positioned on a grid plane of the underlying grid, partitioning the node's grid into two subgrids.
The terms "min/max k-d tree" and "implicit k-d tree" are sometimes mixed up. This is because the first publication using the term "implicit k-d tree" [1] did actually use explicit min/max k-d trees but referred to them as "implicit k-d trees" to indicate that they may be used to ray trace implicitly given iso surfaces. Nevertheless, this publication used also slim k-d trees which are a subset of the implicit k-d trees with the restriction that they can only be built over integer hyperrectangles with sidelengths that are powers of two. Implicit k-d trees as defined here have recently been introduced, with applications in computer graphics. [2] [3] As it is possible to assign attributes to implicit k-d tree nodes, one may refer to an implicit k-d tree which has min/max values assigned to its nodes as an "implicit min/max k-d tree".
Implicit k-d trees are generally not constructed explicitly. When accessing a node, its split plane orientation and position are evaluated using the specific splitting-function defining the tree. Different splitting-functions may result in different trees for the same underlying grid.
Splitting-functions may be adapted to special purposes. Underneath two specifications of special splitting-function classes.
A complete splitting function is for example the grid median splitting-function. It creates fairly balanced implicit k-d trees by using k-dimensional integer hyperrectangles hyprec[2][k] belonging to each node of the implicit k-d tree. The hyperrectangles define which gridcells of the rectilinear grid belong to their corresponding node. If the volume of this hyperrectangle equals one, the corresponding node is a single grid cell and is therefore not further subdivided and marked as leaf node. Otherwise the hyperrectangle's longest extent is chosen as orientation o. The corresponding split plane p is positioned onto the grid plane that is closest to the hyperrectangle's grid median along that orientation.
Split plane orientation o:
o = min{argmax(i = 1 ... k: (hyprec[1][i] - hyprec[0][i]))}Split plane position p:
p = roundDown((hyprec[0][o] + hyprec[1][o]) / 2)
An advantage of implicit k-d trees is that their split plane's orientations and positions need not to be stored explicitly.
But some applications require besides the split plane's orientations and positions further attributes at the inner tree nodes. These attributes may be for example single bits or single scalar values, defining if the subgrids belonging to the nodes are of interest or not. For complete implicit k-d trees it is possible to pre-allocate a correctly sized array of attributes and to assign each inner node of the tree to a unique element in that allocated array.
The amount of gridcells in the grid is equal the volume of the integer hyperrectangle belonging to the grid. As a complete implicit k-d tree has one inner node less than grid cells, it is known in advance how many attributes need to be stored. The relation "Volume of integer hyperrectangle to inner nodes" defines together with the complete splitting-function a recursive formula assigning to each split plane a unique element in the allocated array. The corresponding algorithm is given in C-pseudo code underneath.
// Assigning attributes to inner nodes of a complete implicit k-d tree// create an integer help hyperrectangle hyprec (its volume vol(hyprec) is equal the amount of leaves)inthyprec[2][k]={{0,...,0},{length_1,...,length_k}};// allocate once the array of attributes for the entire implicit k-d treeattr*a=newattr[volume(hyprec)-1];attrimplicitKdTreeAttributes(inthyprec[2][k],attr*a){if(vol(hyprec)>1)// the current node is an inner node{// evaluate the split plane's orientation o and its position p using the underlying complete split-functioninto,p;completeSplittingFunction(hyprec,&o,&p);// evaluate the children's integer hyperrectangles hyprec_l and hyprec_r inthyprec_l[2][k],hyprec_r[2][k];hyprec_l=hyprec;hyprec_l[1][o]=p;hyprec_r=hyprec;hyprec_r[0][o]=p;// evaluate the children's memory location a_l and a_r attr*a_l=a+1;attr*a_r=a+vol(hyprec_l);// evaluate recursively the children's attributes c_l and c_r attrc_l=implicitKdTreeAttributes(hyprec_l,a_l);attrc_r=implicitKdTreeAttributes(hyprec_r,a_r);// merge the children's attributes to the current attribute c attrc=merge(c_l,c_r);// store the current attribute and return ita[0]=c;returnc;}// The current node is a leaf node. Return the attribute belonging to the corresponding gridcellreturnattribute(hyprec);}It is worth mentioning that this algorithm works for all rectilinear grids. The corresponding integer hyperrectangle does not necessarily have to have sidelengths that are powers of two.
Implicit max-k-d trees are used for ray casting isosurfaces/MIP (maximum intensity projection). The attribute assigned to each inner node is the maximal scalar value given in the subgrid belonging to the node. Nodes are not traversed if their scalar values are smaller than the searched iso-value/current maximum intensity along the ray. The low storage requirements of the implicit max kd-tree and the favorable visualization complexity of ray casting allow to ray cast (and even change the isosurface for) very large scalar fields at interactive framerates on commodity PCs. Similarly an implicit min/max kd-tree may be used to efficiently evaluate queries such as terrain line of sight. [4]
Given an implicit k-d tree spanned over a k-dimensional grid with n gridcells.
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.
Vector calculus, or vector analysis, is a type of advanced mathematics that has practical applications in physics and engineering. It is concerned with differentiation and integration of vector fields, primarily in 3-dimensional Euclidean space The term vector calculus is sometimes used as a synonym for the broader subject of multivariable calculus, which spans vector calculus as well as partial differentiation and multiple integration. Vector calculus plays an important role in differential geometry and in the study of partial differential equations. It is used extensively in physics and engineering, especially in the description of electromagnetic fields, gravitational fields, and fluid flow.
A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The word is derived from oct + tree. Octrees are often used in 3D graphics and 3D game engines.
Miller indices form a notation system in crystallography for lattice planes in crystal (Bravais) lattices.
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. K-dimensional is that which concerns exactly k orthogonal axes or a space of any number of dimensions. k-d trees are a useful data structure for several applications, such as:
This is an overview of Fortran 95 language features. Included are the additional features of TR-15581:Enhanced Data Type Facilities, which have been universally implemented. Old features that have been superseded by new ones are not described – few of those historic features are used in modern programs although most have been retained in the language to maintain backward compatibility. The current standard is Fortran 2023; many of its new features are still being implemented in compilers. The additional features of Fortran 2003, Fortran 2008, Fortran 2018 and Fortran 2023 are described by Metcalf, Reid, Cohen and Bader.
A bounding interval hierarchy (BIH) is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance ray tracing and may be especially useful for dynamic scenes.
Function Representation is used in solid modeling, volume modeling and computer graphics. FRep was introduced in "Function representation in geometric modeling: concepts, implementation and applications" as a uniform representation of multidimensional geometric objects (shapes). An object as a point set in multidimensional space is defined by a single continuous real-valued function of point coordinates which is evaluated at the given point by a procedure traversing a tree structure with primitives in the leaves and operations in the nodes of the tree. The points with belong to the object, and the points with are outside of the object. The point set with is called an isosurface.
A min/max kd-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.
A Fenwick tree or binary indexed tree(BIT) is a data structure that can efficiently update values and calculate prefix sums in an array of values.
In computer science, M-trees are tree data structures that are similar to R-trees and B-trees. It is constructed using a metric and relies on the triangle inequality for efficient range and k-nearest neighbor (k-NN) queries. While M-trees can perform well in many conditions, the tree can also have large overlap and there is no clear strategy on how to best avoid overlap. In addition, it can only be used for distance functions that satisfy the triangle inequality, while many advanced dissimilarity functions used in information retrieval do not satisfy this.
In computer science, a min-max heap is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it. This makes the min-max heap a very useful data structure to implement a double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time. Min-max heaps are often represented implicitly in an array; hence it's referred to as an implicit data structure.
In computer science, a ball tree, balltree or metric tree, is a space partitioning data structure for organizing points in a multi-dimensional space. A ball tree partitions data points into a nested set of balls. The resulting data structure has characteristics that make it useful for a number of applications, most notably nearest neighbor search.
In computational geometry, a well-separated pair decomposition (WSPD) of a set of points , is a sequence of pairs of sets , such that each pair is well-separated, and for each two distinct points , there exists precisely one pair which separates the two.
In computer science, a K-D-B-tree (k-dimensional B-tree) is a tree data structure for subdividing a k-dimensional search space. The aim of the K-D-B-tree is to provide the search efficiency of a balanced k-d tree, while providing the block-oriented storage of a B-tree for optimizing external memory accesses.
A relaxed K-d tree or relaxed K-dimensional tree is a data structure which is a variant of K-d trees. Like K-dimensional trees, a relaxed K-dimensional tree stores a set of n-multidimensional records, each one having a unique K-dimensional key x=(x0,... ,xK−1). Unlike K-d trees, in a relaxed K-d tree, the discriminants in each node are arbitrary. Relaxed K-d trees were introduced in 1998.
The PH-tree is a tree data structure used for spatial indexing of multi-dimensional data (keys) such as geographical coordinates, points, feature vectors, rectangles or bounding boxes. The PH-tree is space partitioning index with a structure similar to that of a quadtree or octree. However, unlike quadtrees, it uses a splitting policy based on tries and similar to Crit bit trees that is based on the bit-representation of the keys. The bit-based splitting policy, when combined with the use of different internal representations for nodes, provides scalability with high-dimensional data. The bit-representation splitting policy also imposes a maximum depth, thus avoiding degenerated trees and the need for rebalancing.
