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. 1 2 Francine Evans, Steven Skiena, and Amitabh Varshney (1996). Optimizing triangle strips for fast rendering (PDF). Visualization 1996. IEEE. pp. 319–326. Retrieved 2012-08-31.
This article is issued from Wikipedia - version of the Thursday, March 21, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.