Compressed random-access trees for spatially coherent data
Symposium on Rendering 2007.
Efficient representation of coherent image data such as lightmaps and alpha mattes.
Adaptive multiresolution hierarchies are highly efficient at representing spatially coherent graphics data.
We introduce a framework for compressing such adaptive hierarchies using a compact randomly-accessible tree
structure. Prior schemes have explored compressed trees, but nearly all involve entropy coding of a
sequential traversal, thus preventing fine-grain random queries required by rendering algorithms. Instead,
we use fixed-rate encoding for both the tree topology and its data. Key elements include the replacement
of pointers by local offsets, a forested mipmap structure, vector quantization of inter-level residuals,
and efficient coding of partially defined data. Both the offsets and codebook indices are stored as byte
records for easy parsing by either CPU or GPU shaders. We show that continuous mipmapping over an adaptive
tree is more efficient using primal subdivision than traditional dual subdivision. Finally, we demonstrate
efficient compression of many data types including light maps, alpha mattes, distance fields, and HDR
The compressed tree structure can also be used for lossless compression,
by replacing vector quantization with simple storage of the residual vectors.
Eurographics Association Copyright Notice
Permission to make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed for profit or commercial
advantage and that copies bear this notice and the full citation on the first page. Copyrights for components
of this work owned by others than Eurographics must be honored.