Implicit k-d tree

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.

Implicit k-d trees as defined here have recently been introduced, with applications in computer graphics.

When accessing a node, its split plane orientation and position are evaluated using the specific splitting-function defining the tree.

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.

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.

Construction and storage of a 2D implicit max k d-tree using the grid median splitting-function. Each cell of the rectilinear grid has one scalar value from low (bright blue) to high (bright red) assigned to it. The grid's memory footprint is indicated in the lower line. The implicit max k d-tree's predefined memory footprint needs one scalar value less than that. The storing of the node's max values is indicated in the upper line.