Az SGI-algoritmus háromszögek halmazából hivatott háromszögsávokat előállítani. C nyelven publikálta K. Akeley, P. Haeberli és D. Burns az IEEE Visualization ’96 Proceedings című kiadványának 319–326. oldalán 1996-ban. Programjuk neve "tomesh.c" volt, és Silicon Graphics IRIS GL API-t használt.Francine Evans, Steven Skiena, and Amitabh Varshney. Optimizing triangle strips for fast rendering. Visualization ’96 Proceedings, IEEE, pages 319–326, 1996.
Az algoritmus háromszögek egy halmazán dolgozik, mely halmaz elemei még nem szerepelnek egy háromszögsávban sem; kezdetben ez a teljes bemeneti halmazt jelenti. A háromszögeket mohó módon adja hozzá háromszögsávokhoz mindaddig, míg már nem talál olyan háromszöget, melyet az aktuális sávhoz fűzhetne. Ez esetben új sávot kezd. Kezdéskor, illetve egy más meglévő sáv folytatásánál a következő háromszög kiválasztása a háromszög fokszáma (azaz a vele szomszédos háromszögek száma) alapján történik; az algoritmus a kisebb fokszámú háromszöget részesíti előnyben.
Amennyiben az új sávok indításakor a kezdő háromszög kiválasztását prioritási sor segíti, az algoritmus lineáris időben fut.
Jegyzetek
Fordítás
Kategória:Számítógépes grafikai algoritmusok Kategória:1990 számítástechnikai újdonságai