A Software Tool To Produce Efficient Triangle Strips
Department of Computer Science
State University of New York at Stony Brook
Stony Brook, NY 11794-4400
Almost all scientific visualization involving surfaces is currently done via triangles. The speed at which such triangulated surfaces can be displayed is crucial to interactive visualization and is bounded by the rate at which triangulated data can be sent to the graphics subsystem for rendering. Partitioning polygonal models into triangle strips can significantly reduce rendering times over transmitting each triangle individually. We present software for constructing triangle strips from partially triangulated models, and experimental results showing these strips are 10-30% better than those from previous codes.
The speed of high-performance rendering engines on triangular meshes in computer graphics can be bounded by the rate at which triangulation data is sent into the machine. Obviously, each triangle can be specified by three vertices, but to maximize the use of the available data bandwidth, it is desirable to order the triangles so that consecutive triangles share an edge. Using such an ordering, only the incremental change of one vertex per triangle need be specified, potentially reducing the rendering time by a factor of three by avoiding redundant clipping and transformation computations.
Consider the triangulation in Figure 1. Without using triangle strips, we would have to specify the five triangles with three vertices each. By using triangle strips, as supported by the OpenGL graphics library, we can describe the triangulation using the strip (1,2,3,4,5,6,7,8), and assuming the convention that the ith triangle is described by the ith, (i+1)st, and (i+2)nd vertices of the sequential strip.
In this paper, we consider the problem of constructing good triangle strips from polygonal models. Often such models are not fully triangulated, and contain quadrilaterals and other non-triangular faces, which must be triangulated prior to rendering. Our software exploits the freedom to triangulate these faces to produce strips that are 10 - 30% better than those of previous codes.
To allow greater freedom in the creation of triangle strips, a "swap" command permits one to alter the FIFO queuing discipline in a triangle strip. A swap command swaps the order of the two latest vertices in the buffer so that the instead of vertex i replacing the vertex (i-2) in a buffer of size 2, vertex i replaces the vertex (i-1). Although the swap command is supported in the GL graphics library, keeping portability considerations in mind it was decided to not support it in OpenGL. With OpenGL gaining rapid acceptance in the graphics software community, the one-bit-per-vertex cost model that was appropriate for a swap command in GL is now outdated. In this paper, we evaluate our software for only the OpenGL cost models.
Constructing Triangle Strips
The best previous code for constructing triangle strips which we are aware of is code developed at SGI, implementing what we will call the SGI algorithm. The SGI algorithm seeks to create strips that tend to minimize leaving isolated triangles, by always choosing as the next triangle in a strip the triangle that is adjacent to the least number of neighbors (it only works on triangulated models). After starting from an arbitrary lowest degree triangle, it extends its strips in both directions, so that each strip is as long as possible. There is no reluctance to generate swaps, and understandably so, since this algorithm was aimed at generating triangle strips for Iris GL.
In our algorithm, we perform a global analysis of the structure of a polygonal model using a technique we call patchification. In typical polyhedral models, there are many quadrilateral faces, often arranged in large connected regions. We attempt to find large "patches", rectangular regions consisting only of quadrilaterals. Each patch larger than a specified cutoff size is converted into one strip, at a cost of 3 swaps per turn. Further, every such strip is extended backwards from the starting quadrilateral and forwards from the ending quadrilateral of the patch to the extent possible. To extend, we use an algorithm similar to the SGI algorithm. However, we triangulate our faces "on the fly", which gives us considerably more freedom in producing triangle strips.
We have exhaustively tested our software on several datsets and compared them with the best known triangle strip code. Table 1 shows the results of comparison against the SGI algorithm. The cost columns show the total number of vertices required to represent the dataset in a generalized triangle strip representation under the OpenGL cost model (where each swap costs one vertex). We can observe that our results are close to the theoretical lower bound of the number of triangles + 2, so there is limited potential for better algorithms.
Conclusions and Future Work
As can be seen from the results of Table 1, we are able to outperform the SGI algorithm significantly. Further, our cost averages just 10% more than the theoretical minimum of using one sequential strip with no swaps. We have found that using global algorithms for detecting large strips of quads proves very effective for reducing swaps. This has proved to be quite useful for generating efficient triangle strips for the OpenGL cost model where every swap costs one vertex.
Our algorithm runs in linear time. Although the SGI algorithm does have a slightly better running time, we do not believe this to be a serious drawback of our approach since the triangle-strip generation phase is typically done off-line before interactive visualization. Keeping this in mind we have not yet done any serious performance tuning of our code and there is some scope for further improving our run-times.
We would like to acknowledge several valuable discussions we have had on triangle strips with Joe Mitchell, Martin Held, Estie Arkin, Jarek Rossignac, Josh Mittleman, and Jim Helman. The datasets that we have used have been provided to us by Viewpoint DataLabs. Francine Evans is supported in part by a NSF Graduate Fellowship and a Northrop Grumman Fellowship. Steven Skiena is supported by ONR award 400x116yip01. Amitabh Varshney is supported in part by NSF Career Award CCR-9502239.
 K. Akeley, P. Haeberli, and D. Burns. tomesh.c : C Program on SGI Developer's Toolbox CD, 1990.
 J. Helman. Personal Communication.
 Open GL Architecture Review Board. OpenGL Reference Manual. Addison-Wesley Publishing Company, Reading, MA, 1993.
 Open GL Architecture Review Board, J. Neider, T. Davis and M. Woo. OpenGL rogramming Guide. Addison-Wesley Publishing Company, Reading, MA, 1993.
 Silicon Graphics, Inc. Graphics Library Programming Guide, 1991.