3.6.2. Heidmannov algoritam

 

S pojavom podrške za spremnik za obilježavanje (u OpenGL-u 1.0) 1991. godine, Heidmann je objavio svoju sklopovski ubrzanu verziju Crowova originalnog algoritma. Ovaj put algoritam je zahtijevao dva prolaza. Prvo se scena iscrta samo sa ambijentnim i emisionim komponentama svjetla koristeći dubinsko testiranje za određivanje vidljivosti. Tako da cijela scena izgleda kao da je zasjenjena. Zatim se iscrtavanjem volumena sjene vrši samo obilježavanje onih dijelova sjene koji su zasjenjeni. Prednji dijelovi volumena (ulazak u volumen) iscrtavanjem povećavaju (označavaju sjenu), dok stražnji (izlazak iz volumena) smanjuju vrijednost u spremniku za označavanje (brišu sjenu). Dakle, slika ostaje ista, a u spremniku za obilježavanje imamo zapisanu informaciju o sjeni. S tim je prvi prolaz završen. U drugom prolazu ponovno iscrtavamo scenu, ovaj put sa svim komponentama svjetla i to samo na onim dijelovima koji nisu označeni u spremniku za označavanje.

            Potrebno je napomenuti da ovaj dvoprolazni pristup ima smisla samo kada se koristi jedan izvor svjetlosti. Ako koristimo više izvora svjetlosti uveden je pojednostavljeni algoritam koji samo jednom potpuno iscrta scenu, a zatim zatamnjuje zasjenjene dijelove pojedinih svjetala. Tamo gdje su preklapaju sjene različitih izvora svjetlosti scena će biti to tamnija što je više izvora svjetlosti zaklonjeno.

 

Postupak označavanja sjene možemo vidjeti na slikama 3.11. do 3.13.

 

Slika 3.11. Prednja strana volumena sjene (područje c)

 

Na slici 3.11. vidimo izgled prednje strane volumena sjene. Prilikom njena iscrtavanja povećavamo vrijednost spremnika za obilježavanje.

 

Slika 3.12. Stražnja strana volumena sjene (područje c)

 

Prilikom iscrtavanja stražnje strane volumena sjene (Slika 3.12. – područje c), smanjuju se vrijednosti u spremniku za obilježavanje.

 

Slika 3.13. Zasjenjena scena: a) izvor svjetlosti; b) trokut koji baca sjenu; c) cijena; d) objekt koji sjenimo (zid)

 

Konačni rezultat iscrtavanja prednje i stražnje strane volumena sjene vidljiv je na slici 3.13. gdje sjena nastaje samo na onim mjestima gdje se prednja strana volumena sjene prisutna, a stražnja nije (područje c). Dakle, sjena je predstavljena razlikom između prednje i stražnje strane volumena sjene.

 

NAPOMENA: Na slikama 3.11. - 3.13. područje c se zapravo ne iscrtava, ono je prikazano samo da bi se lakše shvatio postupak označavanja scene.

 

Prednje i stražnje strane volumena sjene možemo razlikovati po njihovoj orijentaciji. Tako npr., za prednju stranu volumena sjene možemo uzeti orijentaciju prema promatraču, a za stražnju obrnuto. Prednja strana volumena sjene iscrtava se tada postavljenjem vrijednosti iscrtavanja (engl. render states) na slijedeći način.

 

SRS(CULLMODE,                           CCW);                     // Iscrtajmo samo pozitivno orijentirane poligone

SRS(COLORWRITEENABLE,          0x0);                       // Ne mijenjamo boju

SRS(ZWRITEENABLE,                   FALSE);                  // Ne mijenjamo sadržaj dubinskog spremnika

SRS(ZFUNC,                                  LESSEQUAL);         // Ne crtajmo prekrivene dijelove

 SRS(STENCILENABLE,                 TRUE);                     // Omogućimo spremnik za označavanje

SRS(STENCILFUNC,                       ALWAYS);             // Usporedna funkcija uvijek uspijeva

SRS(Z-FAIL,                                   KEEP);                     // Kada z-test ne uspije, zadrži vrijednost

SRS(STENCILPASS,                      INCR);                      // Kada usporedba uspije, povećaj vrijednost

SRS(STENCILREF,                          0x0);                       // Referentna vrijednost kod testa obilježavanja

SRS(STENCILMASK,                      0xff);                       // Maska koju koristimo prilikom čitanja

SRS(STENCILWRITEMASK,           0xff);                       // Maska koju koristimo prilikom zapisivanja

NAPOMENA: SRS ekvivalentno je naredbi SetRenderState u DirectX API-ju.

 

Analogno tome, iscrtavanje stražnje strane volumena sjene postiže se promjenom slijedećih parametara iscrtavanja:

 

SRS(CULLMODE,                           CW);                        // Iscrtajmo samo negativno orijentirane poligone

SRS(STENCILPASS,                      DECR);                    // Kada usporedba uspije, smanji vrijednost

 

Pošto je volumen sjene označio zasjenjene dijelove scene, još nam samo preostaje da zatamnimo zasjenjene dijelove scene. To se postiže iscrtavanjem velikog polu prozirnog tamnog kvadrata preko cijele slike sa slijedećim parametrima iscrtavanja:

 

SRS(STENCILFUNC,                       NOTEQUAL);          // Zatamnjujemo samo zasjenjena područja

SRS(STENCILREF,                         0x0;                        // Referentna vrijednost usporedbe

SRS(STENCILPASS,                      ZERO);                    // Usput i praznimo spremnik za obilježavanje

SRS(COLORWRITEENABLE,          0xf);                        // Omogućujemo zapisivanje boje

SRS(ALPHABLENDENABLE,         TRUE);                     // Omogućujemo prozirnost

SRS(SRCBLEND,                            INVSRCALPHA);     // Postavljamo parametre prozirnosti

SRS(DESTBLEND,                          SRCALPHA);          // Postavljamo parametre prozirnosti

 

Cijeli postupak iscrtavanja scene dan je slijedećim pseudo kodom:

ClearScene();

DrawScene();

for( each light )

{

// Samo oznacavamo scenu

SRS( COLORWRITEENABLE, 0x0);

SRS( ZWRITEENABLE,            FALSE );

SRS( STENCILENABLE,           TRUE );

SRS( SHADEMODE,                 FLAT );

// Postavljamo parametre oznacavanja

SRS( STENCILREF,                  0x0000 );

SRS( STENCILMASK,              0xffff );

SRS( STENCILWRITEMASK,    0xffff );

SRS( Z-FAIL,                           KEEP );

SRS( STENCILFAIL,                 KEEP );

SRS( STENCILFUNC,               ALWAYS );

for( each object )

{

CalculateShadowVolume();

// Prednja strana volumena sjene

SRS( STENCILPASS,         INCR );

SRS( CULLMODE,             CCW );

DrawShadowVolume();

// Straznja strana volumena sjene

SRS( STENCILPASS,         DECR );

SRS( CULLMODE,             CW );

DrawShadowVolume();

}

// Sada samo trebamo zatamniti oznacene dijelove scene

SRS( STENCILFUNC,               NOTEQUAL );

SRS( STENCILPASS,               ZERO );

SRS( COLORWRITEENABLE, 0xf );

SRS( ALPHABLENDENABLE, TRUE );

SRS( SRCBLEND,                     INVSRCALPHA );

SRS( DESTBLEND,                  SRCALPHA);

DrawBigGreyTransparentSquare();

// Vratimo parametre iscrtavanja

SRS( ALPHABLENDENABLE, FALSE );

SRS( ZWRITEENABLE,            TRUE );

SRS( STENCILENABLE,           FALSE );

SRS( SHADEMODE,                 GUARD );

}

 

            Razlog zašto se kod iscrtavanja prednje i stražnje strane volumena sjene vrše operacije povećanja i smanjenja vrijednosti spremnika za obilježavanje umjesto  zapisivanja jedinice i nule ilustriran je slikom 3.14. Kada se ne bi koristile operacije povećanja i smanjenja, ne bi se mogao jednoznačno riješiti problem s preklapanjem dijelova volumena sjene konkavnih tijela. Zapisivanjem jedinice pri prednjim i nule pri stražnjim stranama volumena sjene u primjeru na slici 3.14. drugi (desni) objekt koji sjeni ne bi imao svoju sjenu jer bi je stražnja strana prvog (lijevog) objekta izbrisala. Dakle, koristeći operacije povećanja i smanjenja u spremniku za obilježavanje zapravo imamo zapisanu vrijednost dubine sjene (engl. depth count). Iz slike je lako zaključiti da ako bi se i kamera (očište) nalazila unutar volumena sjene oni dijelovi scene koji inače ne bi trebali biti zasjenji imali bi vrijednost spremnika za označavanje različitu od nule. Sjena bi bila potpuno neispravno iscrtana na onim mjestima gdje je vrijednost dubine sjene inače manja ili jednaka jedan. Naime, spremnik za obilježavanje ne razlikuje negativne vrijednosti pa stoga umanjenje nule za jedan uzrokuje da spremnik poprimi maksimalnu vrijednost.

 

Slika 3.14. Preklapanje dijelova volumena sjene.

 

            Još nismo objasnili kako se proračunava volumen sjene. Ovo je usko grlo algoritma i razlog zašto otvoreni rubovi nisu dopušteni (modeli moraju biti zatvoreni). U ovom algoritmu volumen sjene se ni u čemu ne razlikuje od drugih modela, odnosno drugih mreža (engl. mesh). Izrada volumena sjene provodi se u dva koraka. U prvom koraku pronađe se ovojnica (engl. silhouette) tijela koje baca sjenu gledano iz perspektive svijetla, a u drugom uz pomoć ovojnice i položaja svjetla stvaramo samu mrežu volumena sjene. Postoji više načina izdvajanja rubova koji tvore ovojnicu tijela. Rubovi ovojnice su oni rubovi koji sadrže jedan trokut orijentiran prema svjetlu, a drugi od svjetla. Kako je mreža zatvorena, svaki rub sadrži dva trokuta. Drugi način obuhvaća rad samo s pozitivno ili negativno orijentiranim trokutima. Svi se njihovi rubovi dodaju u listu rubova (po tri ruba za svaki trokut), a zatim se iz liste brišu oni koji se pojavljuju dva puta kao što je ilustrirano slikom 3.15. Na taj se način u listi rubova nalaze samo oni rubovi koji čine ovojnicu. Ovaj način je znatno kompliciraniji od prvog jer pri pronalaženju duplih rubova ima složenost proporcionalnu kvadratnom broju trokuta, ali troši manje memorije jer za svaki rub ne sadrži informacije o trokutima koji ga sadržavaju (dva trokuta).

 

Slika 3.15. Određivanje ovojnice sjene (oni rubovi koji se pojavljuju samo jednom bivaju zadržani).

 

            Heidmannova metoda ima i nekoliko problema. Prvi problem uzrokuje stražnja ravnina odsjecanja sjene budući da sprječava da se volumeni sjena protežu u beskonačnost. Primjer ovog problema bilo bi dobivanje sjene nekog objekta na nebu (sjena visi u zraku). Rješenje postoji u korištenju z-faill metode koja ne vrši obilježavanje u prostoru između objekta koji sjeni i objekta koji je osjenjen. Umjesto toga obilježavanje je ograničeno na prostoru unutar osjenjenog objekta gdje z-test nikada ne uspije. Da bi dobili z-faill metodu, samo moramo zamijeniti funkcije obilježavanja za STENCILPASS i Z-FAIL događaj. Tada prilikom iscrtavanja prednje strane volumena sjene koristimo slijedeće parametre iscrtavanja:

 

SRS(CULLMODE,           CCW);     // Iscrtajmo samo pozitivno orijentirane poligone

SRS(Z-FAIL,                   DECR);    // Kada z-test ne uspije, smanji vrijednost

SRS(STENCILPASS,       KEEP);     // U ostalim slucajevima zadrzi vrijednost

A prilikom iscrtavanja stražnje strane:

 

SRS(CULLMODE,           CW);        // Iscrtajmo samo pozitivno orijentirane poligone

SRS(Z-FAIL,                   INCR);      // Kada z-test ne uspije, povecaj vrijednost

 

Drugi problem događa se kada se kamera nalazi unutar nekog volumena sjene. Tada se cijela sjena iscrta naopačke. Sve što treba biti zasjenjeno ostaje osvijetljeno, a sve izloženo svjetlu biva zasjenjeno. Dakle, dodatne se provjere moraju izvršavati koje su poprilično komplicirane jer se za svaki trokut tijela mora provjeriti da li se nalazi između kamere i svjetla. Tu već pomalo ulazimo u problematiku detekcije dodira…

Da zaključimo, Heidmannova metoda veoma je procesorski zahtjevna. Uz već ionako komplicirano proračunavanje izgleda volumena sjene mora se vršiti i dodatna provjera pripadnosti kamere. Kako se u novije vrijeme grafičke kartice razvijaju znatno brže od procesora, a složenost modela postaje sve veća, procesori svojom brzinom ne mogu slijediti taj standard. Rezultat svega toga je potpuna zagušenost procesora, odnosno manji broj sličica u sekundi.