SGI algorithm

The SGI algorithm creates triangle strips 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 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.