One of several possible scenarios of distribution in client/server visualization environments  is a setup where the server calculates the visualization and produces geometry data, which is then transmitted over a network and rendered at the client. As typical visualization applications like iso-surface extraction from volumetric data produce large amounts of geometry, efficient transmission of the data is crucial for smooth and efficient work. Applying various compression techniques to the geometry data to speed up the transmission is just one of several alternatives.
 
 

Various Level of Detail (LOD)  approaches allow to first transmit a rough approximation of the geometry and to successively update and refine the representation as more data arrives (See talk of Markus Hadwiger). Several LOD encoders/decoders are available even as source code and only few changes have to be done to existing visualization setups to include LOD transmission. The most severe disadvantage of this approach is the slow LOD generation process: the fastest approaches can eliminate just about 5000 vertices/second. Compressing an  isosurface produced by the marching cubes on a 256³ data set (about 300K-3M triangles) on the fly would require an inacceptably long time.

Before being passed to the network , the geometry is compressed to reduce redundancy and the overall size of the data. While general-purpose compression techniques like LZW compression can be applied to geometry data, better compression ratios can be achieved if more specialized compression techniques are employed. Similar to the usage of LOD techniques, almost no modifications to existing visualization code are required. Up to 100kTri/s can be decompressed in software (~1.5mbit/s data stream) [2], compression is slower, but significantly faster than the generation of LODs. As compressing a large geometry data set is still not interactive, the accuracy of the visualization and thus the amount of geometry data should be controllable by the user.

The most effective approach which also requires most effort to implement is to adapt the way the visualization generates geometry to the needs of the network transmission. For example, output could be produced in a "progressive", LOD-like way, compressed and transmitted to the client. This can allow to reuse data transmitted for coarser levels of representation for building up more detailed levels and offers most flexibility.

• A single vertex (Position: 3 x float, Normal vector: 3 x float, RGB Color coefficients: 3 x float, Texture coordinates : 2 x float): 11 x float, 44 bytes.
• Triangle: 3 x vertex, 132 bytes
• Iso-surface from medical data-set: 1.5MTri: 66MB!

• Indexed face set: All the vertices of an object are stored in a single array. An index array is used to identify which vertices out of the vertex array to use to form a triangle. Requires the storage of 3 x int indices per triangle.
• Triangle Strips: Frequently used, for example by OpenGL. By subsequently appending vertices to a queue, a triangle is formed by three subsequent vertices. Requires (n+2)/n vertices/triangle for n triangles in a strip. Usually every vertex is specified twice in a mesh (two neighbouring strips).

• Statistically, there are approximately twice as many triangles a vertices in a mesh: optimizations: Generalized TriangleMesh, ...

• encoding of the connectivity information: which vertex belongs to which triangles?
• encoding of vertex positions and attributes.

• optimize the mesh: preprocess the geometry data to produce a representation most suited for compression, for example as long triangle strips as possible.
• transform vertex and attribute data to encode them with fewer bits/less accuracy.
• encode connectivity information/ vertex information
• perform huffman encoding of data.

Generalized triangle mesh: Three basic operations are available for building up triangles from a sequence of vertices. At each step three vertices are available to form a triangle: the one which is being currently added, the previous one (called middle) and the one before previous (oldest).

• restart [V] : start a new mesh with V as the first vertex
• replace oldest[V]: the default operation performed to build up a triangle strip: the middle vertex becomes the oldest, the newest one becomest middle and the currently added one becomes newest. a triangle between oldest, middle and newest is produced.
• replace middle[V]: keep oldest untouched, move newest to middle and the current one to newest. this allows to break the "left-right-left-right-..." construction order of triangle strips.
• In addition, a buffer for 16 vertices can be used to explicitely push vertices for later reuse without the need for respecification of attributes. Vertices from the buffer can be used for any of the mesh construction operations.
• Any of the vertex attributes like color or normal can be bundled with a vertex definition or referenced from a "current" normal /color.

---

• Normalize the object to fit into the unit cube.
• Transform coordinates to integers (up to 16 bit). This accuracy is usually sufficient.
• As successive vertices of a triangle mesh are usually spatially correlated, use delta encoding:

V_n+1=V_n+(dX,dY,dZ)
Store differences in coordinate positions instead of absolute coordinates. This requires less bits than absolute values.
• Huffmann encode the d-values with variable length.
• A similar but less accurate procedure is applied to Color values.

Exploit the symmetry of octants: use the 3 sign-bits of the normal to identify octant. Exploit the symmetry of sextants within an octant: use 3 bits to identify the sextant. use 2*6 bit to encode the u/v angles within a sextant instead of a single index to make delta encoding more efficient 18 bit/normal, use delta encoding..

• overall compression factor of the Java3D compression: 5-10

Construct a vertex spanning tree with a minimum number of runs. (A vertex sp. tree contains all vertices of the object exactly once) Predict vertex positions for delta encoding by using the positions of 1-4 of it's ancestors in the tree. Store tree: depth first traversal storage of vertex data, length of run + 2 bit for topology per node.
Cut mesh along vertex spanning tree (for objects not topologically equivalent to a sphere: vst with few additional edges). The result is the triangle spanning tree, a simply connected polygon. which can be represented as a binary tree of triangle runs. Encoding of tree topology: length of run+1 bit indicating branch/leaf per node.
Create a vertex index table of the closed boundary of the triangle spanning tree Encode triangles of a run: Store indices of the start vertices on the left and right side of the triangle run. Store "marching pattern": 1 bit to add next vertex on the left or right side The "Y-Vertex" of split-triangles is stored implicitely (preprocessing step) Maximize triangle strips generated at decoding: depth first to the first leaf node produces a single strip.

This compression method gains a factor of 20-100 depending of the accuracy of vertex position and attributes.

Progressive Iso-Surface Extraction from Hierarchical 3D Meshes
Roberto Grosso, Thomas Ertl
in Proceedings EUROGRAPHICS'98, pp. C125-C135

Java 3D APi Specification: 3D Geometry Compression
http://www.javasoft.com/products/java-media/3D/forDevelopers/j3dguide/AppendixCompress.doc.html
 

VRML Compressed Binary Format
http://www.vrml.org/WorkingGroups/vrml-cbf/cbfwg.html
http://www.research.ibm.com/vrml/binary/pdfs/ibm20340.pdf