An Improved Adjacency Data Structure for Fast Triangle Stripping

Patrick Reuter
LaBRI - CNRS - INRIA Futurs, University of Bordeaux 1

Johannes Behr
Computer Graphics Center Darmstadt

Marc Alexa
Darmstadt University of Technology

This paper appears in issue Volume 10, Number 2.
Purchase this issue from the akpeters.com web site.

Abstract

To speed up the rendering of polygonal meshes, triangle strips are used to reduce the number of vertices sent to the graphics subsystem by exploiting the fact that adjacent triangles share an edge. In this paper, we present an improved adjacency data structure for fast triangle stripping algorithms. There are three major contributions: first, the data structure can be created quickly and robustly from any indexed face set; second, its cache-friendly layout is specifically designed to efficiently answer common stripping queries, such as neighbor finding and least-degree triangle finding, in constant time; third, the stripping algorithm operates in-place, since strips are created by simply relinking pointers. An implementation of a stripping algorithm shows a significant speed-up compared to other implementations.

Author Information

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

Johannes Behr, Computer Graphics Center Darmstadt, Department of Computer Science Darmstadt, Germany jbehr@zgdv.de

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

Source Code

Downloadable C++ source code implements the fast stripping algorithmin described in the paper: TriangleAdjacencyGraph.h, TriangleAdjacencyGraph.cpp.

Simple Demo

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

Results

Comparison of stripping 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 Stripping
		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

BibTeX Entry

@article{ReuterEtAl05,
  author = "Patrick Reuter and Johannes Behr and Marc Alexa",
  title = "An Improved Adjacency Data Structure for Fast Triangle Stripping",
  journal = "journal of graphics tools",
  volume = "10",
  number = "2",
  pages = "41-50",
  year = "2005",
}