Download paper (a 1.75 MB PDF file).
Download software (a 1.0 MB ZIP file containing Windows executables).
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
Input: A model in VRML 2.0 format *
Output: A model in VRML 2.0
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
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:
MLARENDSEQ <input_mesh_file> <arrangement_file> <output_mesh_file>
$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
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.
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
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"
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
Send mail to to Alex