Warnockův algoritmus - Warnock algorithm

Viditelnost polygonu v daném výřezu: a) polygon vyplní výřez, b) polygon částečně ac) zcela viditelný, d) polygon neviditelný.
Čtyři kroky rozdělení výřezu pro jednoduchou scénu

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

  1. ^ 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
  2. ^ 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