The SGI algorithm creates
triangle strip
In computer graphics, a triangle strip is a subset of triangles in a triangle mesh with shared vertices, and is a more memory-efficient method of storing information about the mesh. They are more efficient than un-indexed lists of triangles, bu ...
s from a set of triangles. It was published by K. Akeley, P. Haeberli, and D. Burns as a
C program named "tomesh.c" for use with
Silicon Graphics' IRIS GL
IRIS GL (Integrated Raster Imaging System Graphics Library) is a proprietary graphics API created by Silicon Graphics (SGI) in the early 1980s for producing 2D and 3D computer graphics on their IRIX-based IRIS graphical workstations. Later SGI re ...
API.
[{{cite conference , author1=Francine Evans , author2=Steven Skiena , author3=Amitabh Varshney , name-list-style=amp , title = Optimizing triangle strips for fast rendering , conference = Visualization 1996 , publisher = IEEE , pages = 319–326 , year = 1996 , url = http://www.cs.umd.edu/gvil/papers/av_ts.pdf , accessdate = 2012-08-31 ]
The algorithm operates on the set of triangles that have not yet been added to a triangle strip, starting with the entire set of input triangles. Triangles are
greedily added to a strip until no triangle is available that can be appended to the strip; a new strip will be started in this case. When choosing a triangle for starting or continuing a triangle strip, the selection is based on a triangle's degree (i.e. the number of triangles adjacent to it), with smaller degrees being preferred.
If implemented using a priority queue to quickly identify triangles that can start a new strip, the algorithm runs in linear time.
[
]
References
Computer graphics algorithms
SGI graphics