3.6.1. Povijesni pregled

Iz škole Leonarda da Vincija

Ideja o korištenju volumena sjene kao sredstva za ostvarivanje računalnih sjena prvi put je predstavljena 1977. godine kada je Frank Crow objavio svoj algoritam utemeljen na praćenju zrake. Za svaki slikovni element (engl. pixel) na slici, povučena je zraka s početkom u ishodištu kamere i završetkom u nekoj čvrstoj točci predstavljenom tim slikovnim elementom. Zraka bi se presijecala granicama volumena sjene, a broj tih presijecanja, odnosno ulazaka i izlazaka iz volumena sjene bi se sumirao. Crow je zapazio da presijecanje zrake prednjim, odnosno stražnjim stranama granicama volumena predstavlja ulazak, odnosno izlazak zrake iz volumena sjene. Ako bi se svi poligoni volumena sjene postavili tako da gledaju prema van, ulazak zrake u volumen sjene bio bi karakteriziran presijecanjem zrake s pozitivno orijentiranim poligonom (usmjerenim prema promatraču), dok bi izlazak iz volumena bio predstavljen presijecanjem s negativno orijentiranim poligonom volumena sjene. Promatrani slikovni element bio bi zasjenjen kada je broj ulazaka veći ili jednak broju izlazaka iz volumena sjene. Crow je također zamijetio da se mora dodatno provjeravati pripadnost kamere unutar volumena sjene jer se tada ne može na jednoznačan način odrediti da li sjenčati slikovni element ili ne. Korištenje ovog algoritma zahtijevalo je proračunavanje granica volumena sjena za svako tijelo (objekt) na sceni, a kako se objekti i izvori svjetlosti na sceni pomiču, novo proračunavanje obavijalo se pri svakom pomaku.

1984. godine Brotman i Badler proširili su Crowov pristup sa podrškom za meke sjene korištenjem više zamjenskih izvora svjetlosti od koji svaki «baca» svoju sjenu.

Pixel-Planes metoda predstavljena je 1984. godine. Za razliku od Crowova pristupa, ovdje se za svaki trokut proračunava volumen sjene i svaki se slikovni elementi testira na pripadnost tom volumenu. Testiranje pojedinog slikovnog elementa s volumenom sjene poprilično je jednostavno – slikovni element mora se nalaziti ispod svake ravnine koje tvore volumen sjene trenutnog trokuta. Samo testiranje slikovnih elemenata vršio je prototip pixel-plane memorijskog čipa koji je bio integriran u sklopovlje za 3D grafiku. Na slikama 3.9. i 3.10. možemo vidjeti poprilično impresivne rezultate za ono vrijeme.

Slika 3.9. Model kapelice od 357 poligona. Vrijeme generiranje slike (uz 10 MHz procesor) iznosi 9ms.

Slika 3.10. Model kapelice sa sjenom. Generiranja slike trajalo je 13.8ms.

Lako je zaključiti da bi programska verzija ovog algoritma bila poprilično procesorski skupa. Za scenu koja sadrži 10000 poligona, razlučljivosti 640*480 slikovnih elemenata pri 20 slika u sekundi, trebalo bi se analizirati 10000*640*480*20 = 61 440 000 000 slikovnih elemenata u sekundi.

Drugo proširenje Crowova algoritma uveo je Bergeron kada je u svom članku 1986. godine objasnio važnost korištena zatvorenih modela objekata i kako ispravno raditi s onima koji su otvoreni.

Fournier i Fussell su 1988. godine objavili novi pristup koji je za svaki slikovni element zapisivao i dubinu (standardni z-spremnik) i broj dubine sjene. Taj pristup služio je kao teorijska osnova za sve kasnije sklopovski ubrzane algoritme za ostvarivanje sjena korištenjem metode volumena sjena.

Algoritam koji se još i danas gotovo nepromijenjen koristi objavio je Heidmann 1991. godine. Zasnovan je na korištenju spremnika za obilježavanje (engl. stencil buffer) da bi odredili koji dijelovi bivaju osjenjeni, a koji ne. U slijedećem poglavlju biti će detaljnije objašnjen ovaj algoritam.