SGI-algoritmus

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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.[1]

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.[1]

Jegyzetek[szerkesztés]

  1. a b Francine Evans, Steven Skiena, and Amitabh Varshney. Optimizing triangle strips for fast rendering. Visualization ’96 Proceedings, IEEE, pages 319–326, 1996.

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a SGI algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.