Implicit kd tree

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" 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. 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 in general 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 extend 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.

...
Wikipedia