# SGI algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/SGI_algorithm
> Markdown URL: https://mediated.wiki/source/SGI_algorithm.md
> Source: https://en.wikipedia.org/wiki/SGI_algorithm
> Source revision: 1312512194
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

The **SGI algorithm** creates [triangle strips](/source/Triangle_strip) from a set of triangles. It was published by K. Akeley, P. Haeberli, and D. Burns as a [C](/source/C_(programming_language)) program named "tomesh.c" for use with [Silicon Graphics'](/source/Silicon_Graphics_International) [IRIS GL](/source/IRIS_GL) API.[1]

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](/source/Greedy_algorithm) 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.[1]

## References

1. ^ [***a***](#cite_ref-evans_1-0) [***b***](#cite_ref-evans_1-1) Francine Evans; Steven Skiena & Amitabh Varshney (1996). [*Optimizing triangle strips for fast rendering*](http://www.cs.umd.edu/gvil/papers/av_ts.pdf) (PDF). Visualization 1996. IEEE. pp. 319–326. Retrieved 2012-08-31.

---
Adapted from the Wikipedia article [SGI algorithm](https://en.wikipedia.org/wiki/SGI_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/SGI_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.