BLIC: Bi-Level Isosurface Compression

In this paper we introduce a new and simple algorithm to compress isosurface data. This is the data extracted by isosurface algorithms from scalar functions defined on volume grids, and used to generate polygon meshes or alternative representations. In this algorithm the mesh connectivity and
a substantial proportion of the geometric information are encoded to a fraction of a bit per Marching Cubes vertex with a context based arithmetic coder closely related to the JBIG binary image compression standard. The remaining optional geometric information, in the form of one quantized scalar value per intersecting grid edge, and specifying the location of the corresponding Marching Cubes vertex more precisely, is efficiently encoded in scan-order with the same mechanism. Vertex normals can optionally be computed as normalized gradient vectors by the encoder and included in the bitstream after quantization and entropy encoding, or computed by the decoder in a postprocessing smoothing step. These choices are determined by trade-offs associated with an in-core vs. out-of-core decoder structure. The main features of our algorithm are its extreme simplicity and high compression ratios, which are 5 to 25 times better than those obtained with general purpose mesh compression schemes. Isosurface extraction algorithms construct polygon mesh approximations to level sets of scalar functions specified at the vertices of a 3D regular grid. The most popular isosurface algorithms [8] are Cuberille [1] and Marching Cubes [12]. We will refer to the polygon meshes produced by these and related algorithms as isosurface meshes. Despite the widespread use of these meshes in scientific visualization and medical applications, and their very large size, special purpose algorithms to compress them for efficient storage and fast download have not been proposed until very recently [21, 16, 33]. We compare our new algorithm with these recent approaches in section 8, after the relevant concepts are introduced. Polygon Mesh Coding A number of general purpose polygon mesh compression algorithms have been proposed in recent years. Deering [2] developed a mesh compression scheme for hardware acceleration. Taubin and Rossignac [25], Touma and Gotsman [27], Rossignac [18], and others [26], introduced methods to encode the connectivity of triangle meshes with no loss of information. King et. al. [10] developed a method to compress quadrilateral meshes.