Patrick Reuter, Johannes Behr, and Marc Alexa. An Improved Adjacency Data Structure for Fast Triangle Stripping. Accepted for publication in Journal of Graphics Tools.


An Improved Adjacency Data Structure for Fast Triangle Stripping


Patrick Reuter
LaBRI - CNRS - INRIA Futurs
University Bordeaux 1
France
preuter@labri.fr

Johannes Behr
Department of Visual Computing
Computer Graphics Center Darmstadt
Germany
jbehr@zgdv.de

Marc Alexa
Department of Computer Science
Darmstadt University of Technology
Germany
alexa@gris.informatik.tu-darmstadt.de


Abstract:
Data structures for striping algorithms are presented. The data structures are specifically designed to answer common queries during striping such as neighbor finding and least-degree triangle finding in constant time. They can be generated quickly and robustly from any indexed face set. An implementation of a striping algorithm shows a significant speed-up compared to other implementations.
Paper:
The final version of the paper will be available soon.

Source code:
Downloadable C++ source code implements the fast striping algorithm described in this paper TriangleAdjacencyGraph.cpp, and its header, TriangleAdjacencyGraph.h.

Simple fstripDemo:
fstripDemo.tar.gz C++ Source Code for a simple striper reading ASCII ply files (e.g. bunny.ply.gz), just to see how simple the fast striping algorithm can be used in your own programs (tested on Linux and IRIX).

Results:
Comparison of striping time and quality (number of vertices to be send to the graphics subsystem) on a 1.7GHz Pentium with 512 MB of RAM.

Model Triangles STRIPE FTSG GameGems Fast Striping
    sec. vertices sec. vert sec. vert sec. vertices
bunny 69,451 1.8 82,182 0.33 81412 6.50 88,330 0.12 81,674
dragon 871,414 19.5 1,140,991 4.60 1,121,151 1384 1,233,809 1.45 1,136,528
buddha 1,087,716 24.2 1,423,102 5.92 1,398,464 2096 1,538,041 1.80 1,420,126



Images:
Bunny (model by the
Stanford 3D Scanning Repository)
Dragon (model by the
Stanford 3D Scanning Repository)
Buddha (model by the
Stanford 3D Scanning Repository)