Fakultät Informatik

DuoDecim - A Structure for Point Scan Compression and Rendering

 Jens Krüger,  Jens Schneider, Rüdiger Westermann

Computer Graphics and Visualization Group, Technical University Munich, Germany


In this work we present a compression scheme for large point scans including per-point normals. For the encoding of such scans we introduce a particular type of closest sphere packing grids, the hexagonal close packing (HCP). HCP grids provide a structure for an optimal packing of 3D space, and for a given sampling error they result in a minimal number of cells if geometry is sampled into these grids. To compress the data, we extract linear sequences (runs) of filled cells in HCP grids. The problem of determining optimal runs is turned into a graph theoretical one. Point positions and normals in these runs are incrementally encoded. At a grid spacing close to the point sampling distance, the compression scheme only requires slightly more than 3 bits per point position. Incrementally encoded per-point normals are quantized at high fidelity using only 5 bits per normal. The compressed data stream can be decoded in the graphics processing unit (GPU). Decoded point positions are saved in graphics memory, and they are then used on the GPU again to render point primitives. In this way we render gigantic point scans from their compressed representation in local GPU memory at interactive frame rates.


The images above show the three largest datasets from the  digital michelangelo project. The scan of the  david statue was compressed from about 1.1 GB down to 21 MB while the  St. Matthew statue was roughly 7.3 GB before compression and only 180 MB after. The largest scan of the  unfinished Atlas statue was almost 10 GB in size before and is now only 230 MB after compression. while still almost no difference can be seen. Click on the first image to get a high-res picture and try to find out which version is the compressed (for an answer check the paper). One of the key features of our technique is that it allows for very effecient rendering of these highly compressed datasets without the need to decompress them. To see how fast we can render these and other statues altogether on a commodity PC check out the video below.

Associated publications

DuoDecim - A Structure for Point Scan Compression and Rendering
J. Krüger, J. Schneider, R. Westermann, Point-Based Graphics 2005 [Bibtex]
Selected for journal publication of outstanding papers.


Accompanying video of the paper [35 MB WMV]



Matthias Niessner, our new Professor from Stanford University, offers a number of interesting topics for  master theses.


A new PhD/PostDoc position on  Computational Fabrication and 3D Printing is available at the Computer Graphics & Visualization group.


A new PhD position is available at the games engineering group.  Check it out here.