Skip to topic | Skip to bottom
Home
TModeling
TModeling.StreamingCompressionr1.1 - 25 Jul 2008 - 12:24 - Main.guesttopic end

Start of topic | Skip to actions

Streaming Compression

The idea of streaming meshes is to organize the data structure so that a large mesh can be accessed seamlessly by a fixed traversal while keeping only a small boundary between the visited and unvisited portions in memory at any time. More detail can be found on here http://www.cs.unc.edu/~isenburg/smc/ and throughout this wiki and Martin's pages. The seminal paper is here.

The prototype compressor sm2sm is something that we can use even for large meshes. Here is the idea, and the technical details of the representation.

Approach to streaming compression

Standard schemes for compressing polygonal meshes first construct an explicit representation of the entire mesh connectivity, then reorder it by a deterministic traversal that produces a sequence of symbols that can be encoded.

We describe a mesh compression scheme that incrementally constructs mesh connectivity as triangles are input and immediately compresses them. This compression scheme is mainly intended for meshes in streaming formats, which interleave vertices and triangles and finalize vertices that are no longer used. The availability of this scheme enables us to compress such meshes on-the-fly without ever having the entire mesh in memory and without ever having to reload parts of the mesh as required by current alternatives.

We can often significantly improve compression rates by employing a small delay buffer within which the compressor is allowed to locally reorder triangles. The memory requirements of the compressor are proportional to the width of the streaming mesh and the size of the delay buffer.

Formats

We currently use three streaming formats. SMA and SMB are uncompressed. SMC and is compressed. You can convert between using the sm2sm converter in the following manner:
sm2sm -i mesh.sma -o mesh.smc 

File type down Description
*.sma a simple OBJ-like ASCII format
*.smb a simple PLY-like uncompressed binary format
*.smc our compressed binary format

You can look at meshes in the SMA format in a text editor. This will give you a good idea what "finalization" means in practice. You will see that a streaming mesh format is just as simple as other formats. They can be just as easily generated as VRML, OBJ, PLY, and friends.

Here a quick explanation of the SMA format. First we have a look at a standard OBJ format:

# ctetra.obj 
# 
v -1.0 -1.0 -1.0 
v 1.0 1.0 -1.0 
v 1.0 -1.0 1.0 
v -1.0 1.0 1.0 
f 2 1 3 
f 4 3 1 
f 1 2 4 
f 2 3 4 

And here is our streaming SMA. This mesh is "pre-order", "vertex-compact", and "tight". Pre-order means that each vertex preceeds all triangles that use it. Vertex-compact means that vertices appear as late as possible (e.g. directly before the first triangle that uses it). And "tight" means that each vertex is finalized as early as possible (e.g. directly after the last triangle that uses it). Here we denote "finalization" of vertices by an explicit finalization command:

# ctetra.sma 
# 
# nverts 4 
# nfaces 4 
# 
v -1.0 -1.0 -1.0 
v 1.0 1.0 -1.0 
v 1.0 -1.0 1.0 
f 2 1 3 
v -1.0 1.0 1.0 
f 4 3 1 
f 1 2 4 
x 1 # finalizing vertex number 1 
f 2 3 4 
x 2 # finalizing vertex number 2 
x 3 # finalizing vertex number 3 
x 4 # finalizing vertex number 4 
the last three finalization commands are not really needed, as the end of the file implicitly finalizes all remaining vertices.

Vertex finalization with "explicit" finalization commands (i.e. the 'x' command) is supported only in the SMA format. It is mainly for educational purposes. Better practice is to finalize a vertex with the last index that references it through relative indexing. This is done in SMA and SMB formats; SMB is about a factor of 10 smaller than SMA.

# ctetra.sma
#
# nverts 4
# nfaces 4
#
v -1.0 -1.0 -1.0
v 1.0 1.0 -1.0
v 1.0 -1.0 1.0
f 2 1 3         
v -1.0 1.0 1.0
f 4 3 1
f -4 2 4      # finalizing vertex number 1 using the relative index -4
f -3 -2 -1    # finalizing vertices number 2, 3, and 4

SMC format is about a factor of 10 smaller than SMB. SMC encodes the mesh as a compact bit string that avoids the use of index offsets to vertices, typically using less than one bit per vertex to encode the mesh topology. It also quantizes the point coordinates so that they can be predicted from their neighbors as they are reconstructed. Corrections from the predictions are encoded and stored.

Finalization

Finalization is key to the efficient use of memory. Data files typically indicate when data appears; our finalization tags essentially indicate when data will no longer be needed.
to top

I Attachment sort Action Size Date Who Comment
il-sm-draftjan05.pdf manage 769.2 K 22 Feb 2005 - 23:21 JackSnoeyink draft of Martin & Peter's paper on streaming meshes in graphics (Jan 05)
streaming_mesh_tools.zip manage 9329.4 K 23 Feb 2005 - 15:42 JackSnoeyink Executables for compressing, analyzing, and displaying streaming meshes

You are here: TModeling > ProjectIdeas > StreamingCompression

to top

Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback