J. Andreas Bærentzen
Data Structures for Sparse Volumetric Data
By volume data we generally understand a mapping from a cuboid region of R^3 to some value. For instance, in a medical volume, points are mapped to some physical quantity such as density. In general, we only know the mapping at a discrete set of points, and we use interpolation to fill out the volume. The simplest and by far the most used volume representation is a regular 3D grid of data points. A grid point together with its values is denoted a voxel. We are typically interested in just a fraction of the voxels for two reasons: First of all the data is usually associated with some shape (for a CT scan of a limb that would be the shape of the limb) which does not occupy the entire cuboid region of the volume. Secondly, we are often interested in voxels close to a surface, which dramatically limits what parts of the volume that are really needed. Thus, volume data is often rather sparse. In the first part of this lecture, we revisit some of the data structures which exploit this sparsity: Octrees, hierarchical grids, and run length coding. As always, the best choice depends on the application, and we shall see what trade-offs one must consider. In particular, time vs space efficiency.
In the second part, we turn to a novel volume representation currently under development where the grid is an irregular simplicial (tetrahedral) complex. Since the grid is irregular, we can exploit sparsity by locally varying the size of the simplices. However, the data structure is different from normal volume representations, since data is generally not associated with grid points but with tetrahedra which are monolithic and labelled according to their contents. I.e. the mapping from 3D to value is piecewise constant. This data structure is especially well suited to dynamic simulations which would otherwise be performed using regular voxel grids, e.g. using the level set method, but, as we shall see, the method suffers much less from numerical diffusion. Moreover. surfaces which would be represented as isosurfaces in a voxel grid are here explicitly represented as triangles shared between differently labelled simplices.