Implementacija
U svojoj implementaciji koristim malo izmijenjen kod koji nude na internetskoj stranici http://www.lighthouse3d.com/opengl/viewfrustum/ kao primjer učenja algoritma. Tu postoji razred Frustum koji predstavlja krnju piramidu tj. projekcijski volumen koji se sastoji od 6 ravnina. Za svaku ravninu se izračunaju normale. Ja sam izmijenio funkciju pointInFrustum koja ispituje gdje se nalazi točka u odnosu na površinu kojoj je orijentacija određena normalom. Za svaku površinu ispitujem svih osam točaka obujmice čvora. Ako se svih osam nalazi na krivoj strani jedne površine, onda je čvor izvan projekcijskog volumena. Ako se svih osam točaka nalazi na unutrašnjoj strani svih šest ravnina, onda je čvor unutar projekcijskog volumena. Za sve ostalo funkcija vraća vrijednost presijecanja projekcijskog volumena. [5]
U ovom radu proučavam detaljnije algoritme za odbacivanje zaklonjenih poligona pomoću sklopovskih upita o zaklanjanju. Temelj ovih algoritama su upiti upućeni grafičkoj kartici, no veliki problem čini već spomenuta asinkrona priroda rada ovih upita. Da bih to bolje razumio prvo sam implementirao naivnu “stani i čekaj“ (engl. stop and wait) metodu.
Hijerarhijska “stani i čekaj“ metoda
Ova metoda je dosta jednostavna, a funkcionira tako da, za svaki čvor u hijerarhiji, postavi upit da li je, objekt koji želimo iscrtati, zaklonjen ili ne. Ako je zaklonjen, preskačemo taj čvor. Ako nije zaklonjen, djecu toga čvora stavljamo u red uređen po udaljenosti od kamere (od naprijed prema natrag, engl. front-to-back order). Ako je čvor list, onda ga iscrtamo. Dakle CPU pošalje upit i čeka rezultat upita i pritom ne radi ništa. Odmah se može pretpostaviti koja je loša strana ovog algoritma. Tek kad je velika večina scene zaklonjena, ovaj algoritam postaje koristan, no i onda kaska za naprednijim riješenjima. Treba napomenuti da se za potrebe upita iscrtavaju obujmice objekata, a ne sami objekti.
Ispis 1. Pseudokod "stani i čekaj" algoritma.
CHC++ algoritam
Oliver Mattausch, Jiri Bittner i Michael Wimmer osmislili su CHC++ algoritam. Za potrebe ovog rada, stupio sam u kontakt sa Jiri Bittnerom koji mi je posalo izvorni kod. Ja sam ga onda modificirao da radi sa mojim grafom scene. Algoritam riješava mnoge probleme vezane uz ovaj način odbacivanja zaklonjenih poligona.
Ovaj algoritam smanjuje broj promjena stanja i upita. Naišao sam na podatak da je oko 200 promjena stanja, u jednom trenutku prikaza, prihvatljivo za današnje sklopovlje. Kod ovakvih algoritama to se može premašiti za više puta. CHC++ uspijeva napraviti redukciju tako da radi jedan upit za više čvorova, a ne samo za jedan čvor. Također smanjuje i čekanje glavnog procesora. Dok se čekaju odgovori na upite postavljene grafičkoj kartici, ovaj algoritam šalje upite za čvorove koji su bili vidljivi u prošlom trenutku prikaza i dalje prolazi kroz hijerarhiju scene.
U CHC++ algoritmu se isto koristi red uređen po udaljenosti od kamere, no također se bilježe i podatci o pojedinim čvorovima. Za svaki čvor se zna koliko je puta do sada bio nevidljiv, u kojem trenutku prikaza je zadnji put bio ispitan i, ako je vidljiv, koliko se još očekuje da ostane vidljiv.
Slika 5. Grafički prikaz raspodjele čvorova po redovima [15].
Vidljivi listovi se odmah iscrtavaju i stavljaju se u red vidljivih čvorova za upit o zaklanjanju, no odgovor na taj upit se koristi tek u idućem trenutku prikaza.
Nevidljivi čvorovi se stavljaju u red za upit nevidljivih čvorova. Kada broj čvorova, u tom redu, dosegne određenu vrijednost, pošalje se jedan upit za više čvorova (engl. multiquery). Odluka o tome koji čvorovi će biti grupirani za jedan upit ovisi o odnosu broja čvorova u potencijalnom upitu i očekivanog troška upita:
Gdje je B broj upita, a C funkcija očekivanog troška.
Ispis 2. Pseudokod CHC++ algoritma.