Warnockův algoritmus - Warnock algorithm


The Warnockův algoritmus je algoritmus skrytého povrchu vynalezl John Warnock který se obvykle používá v oblasti počítačová grafika.[1] Řeší problém vykreslení komplikovaného obrazu rekurzivním rozdělením scény, dokud nejsou získány oblasti, které jsou triviální pro výpočet. Jinými slovy, je-li scéna dostatečně jednoduchá na to, aby se dala efektivně vypočítat, pak se vykreslí; jinak je rozdělen na menší části, které jsou rovněž testovány na jednoduchost.[2]
Tohle je algoritmus rozděl a panuj s run-time z , kde n je počet polygonů a p je počet pixelů ve výřezu.
Vstupy jsou seznam polygonů a výřez. Nejlepším případem je, že pokud je seznam mnohoúhelníků jednoduchý, nakreslete mnohoúhelníky do výřezu. Jednoduchý je definován jako jeden mnohoúhelník (poté je polygon nebo jeho část nakreslena v příslušné části výřezu) nebo výřez o velikosti jednoho pixelu (pak tento pixel získá barvu polygonu nejblíže k pozorovateli). Kontinuálním krokem je rozdělení výřezu do 4 stejně velkých kvadrantů a rekurzivní volání algoritmu pro každý kvadrant s upraveným seznamem polygonů tak, aby obsahoval pouze polygony, které jsou viditelné v tomto kvadrantu.
Reference
- ^ Warnock, Johne (1969). "Algoritmus skrytého povrchu pro počítačem generované polotónové obrázky". University of Utah.
Algoritmus byl Warnockova disertační práce.
, 32 stran
Taky: http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD753671&Location=U2&doc=GetTRDoc.pdf - ^ Daintith, John; Wright, Edmund (2009). Oxfordský slovník výpočetní techniky. Oxford University Press. ISBN 978-0-19-923400-4., 608 stran
externí odkazy
![]() | Tento programování související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |