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.[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 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.0 1.1 Francine Evans; Steven Skiena; Amitabh Varshney (1996). "Optimizing triangle strips for fast rendering". Visualization 1996. IEEE. pp. 319–326. http://www.cs.umd.edu/gvil/papers/av_ts.pdf. Retrieved 2012-08-31.
 |  |
