Universal Rendering Sequences for Transparent Vertex Caching of Progressive Meshes

Alexander Bogomjakov    Craig Gotsman

Computer Science Department
Technion - Israel Institute of Technology


Download paper (a 1.75 MB PDF file).
Download software (a 1.0 MB ZIP file containing Windows executables).

Programs:

VSimplify.exe        Simplification program
cachesim.exe         FIFO vertex cache simulation program
dfsrendseq.exe      Rendering sequence generator (with the recursive cut algorithm)
mlarendseq.exe     A program to convert a linear arrangement into a rendering sequence
mla.exe                 A program for finding a minimum linear arrangement of a hypergraph
vrml2hgraph.exe    VRML 2.0 mesh to hypergraph converter
 

Generating Rendering Sequences

Recursive Cut Algorithm

Program: DFSRENDSEQ.EXE
Input: A model in VRML 2.0 format *
Output: A model in VRML 2.0
Usage:
DFSRENDSEQ <input_file> <output_file>

Description: The program uses the recursive cut algorithm in order to compute a rendering sequence of the input model. The output model is the same as the input model except that its faces are arranged according to the computed rendering sequence.
 

Minimum Linear Arrangement (MLA) Algorithm

Programs: MLARENDSEQ.EXE, MLA.EXE, VRML2HGRAPH.EXE
The MLA program was written by Jon Feldman of LCS, MIT.
Description: In order to obtain a mesh with faces arranged according to a rendering sequence based on the MLA method, perform the following 3 steps:

  1. Use the VRML2HGRAPH utility to convert your mesh (described in VRML 2.0*) into a hypergraph.
  2. Use the hypergraph as an input to the MLA program. It will compute an arrangement.
  3. Use the original mesh and the computed arrangement as an input to the MLARENDSEQ program in order to obtain a mesh with reordered faces (according to the arrangement).
Usage:
VRML2HGRAPH <input_mesh_file> <output_hypergraph_file>

MLARENDSEQ <input_mesh_file> <arrangement_file> <output_mesh_file>

MLA <parameters>
Parameters:
    $1: Hypergraph File
    $2: UB Factor - an integer in the range [1..29]
    $3: Number of trials of the main algorithm
    $4: Local Improvement UB Factor (like $2)
    $5: Number of Local Improvement trials
    $6: Upper Bound on OT size (-1 - no bound)
    $7: (1)=Keep Hyperedge Projections
    $8: Output Filename for Layout

A hypergraph file is obtained by running the VRML2HGRAPH utility program on a mesh described in VRML 2.0. The MLA program is based on the hMETIS hypergraph partitioning library, UB Factor parameters are passed to hMETIS. Experiments have shown a quality / running time trade-off as a function of the UB Factor - the higher the UB Factor is the better is the solution, but the program takes more time to run.
Number of trials - the main part of the algorithm runs given number of times, and then takes the best one for further local improvements.
Number of local improvement trials - number of iterations of the local improvement algorithm.
Set $6 and $7 to -1 and 0 respectively.

Example:

vrml2hgraph regular64.wrl regular64.hgraph
mla.exe regular64.hgraph 1 1 29 30 -1 0 regular64.mla
mlarendseq regular64.wrl regular64.mla regular64_seq.wrl
 
 

Cache Simulation Program

CACHESIM is a FIFO vertex cache simulation program with a user-friendly interface. The functionality of most of the menu and toolbar items is more or less obvious.
The user can load a VRML2.0 model and simulate on it the work of a FIFO vertex cache of a given size. The resulting image shows the model with colored triangle corners. Each color denotes different number of cache misses for the corresponding vertex. Suppose that vertex v participates in triangle T.  If v's corner is colored gray, this means that v caused no cache miss when T was rendered; if it is green - than this is the first cache miss for this vertex; blue - second miss; red - third or more. Of course, for each vertex, exactly one of its triangles will have a green corner, as it will cause at least one cache miss when loading the vertex for the first time. The goal of the whole problem is to maximize the number of the gray corners and minimize the number of the blue and the red ones.

Selecting the Options / Draw Path menu item will cause the program to draw the rendering sequence path instead of colored triangles. The path between adjacent triangles is shown by white lines; jumps (between non-adjacent triangles) is shown in red.

The Simulation / Simulate... menu item opens a dialog which allows to run the simulation in a bach mode for different cache sizes and at different mesh resolutions. Note that in the interactive simulation mode you may also change the cache size and mesh resolution.

The resolution of a given mesh can be changed only if at the loading time of the model there was a history file present in the same directory as the model. The history file must have the same name as the model but with the ".history" extension.
 
 

Simplification History

A simplification history is generated by VSIMPLIFY. It is a GUI based program, developed by Virtue Ltd.. Just load the mesh you want to simplify, make sure that the percentage of retained triangles is what you really want, and press the "Simplify" button.
VSIMPLIFY generate two things as output. One is the simplified version of the mesh; it is not used by any program here. Second, it will create a file named "history.txt" in the directory where  VSIMPLIFY was run. This is the simplification history. Rename it to your_mesh_name.history and move it to the same directory where your_mesh_name.wrl is.

ATTENTION: since the programs that generate rendering sequences assign new indices, a simplification history should be generated for each mesh separately.
For example, if you had a mesh called model.wrl, and ran it through, say, DFSRENDSEQ to obtain model_seq.wrl, then you will have to generate a simplification history specifically for model_seq.wrl and call the history file model_seq.history
 
 

Questions ?

Send mail to to Alex Bogomjakov.
 


* All the programs here that work with the VRML 2.0 format assume that the model is described by a single Shape node with geometry of type IndexedFaceSet  without any other features (e.g. normals, color, material, texture, etc.). The mesh described by the IndexedFaceSet is assumed to be connected, triangular and manifold, although it may have a boundary.