ALGORITMI ZA UKLANJANJE POLIGONA

Rezultati

Za mjerenje rezultata optimizacije sam složio virtualnu scenu u vlastitom editoru. Neke objekte sam oblikovao, a neke sam učitao iz .obj formata i uvrstio ih u scenu. Scena se sastoji od 145270 poligona. Za algoritam odbacivanja poligona po projekcijskom volumenu je vrlo bitna struktura tj. graf scene. Nastojao sam grupirati dijelove scene imajući na umu logičku i prostornu organizaciju. Na slici 10 se vidi cijela scena, bez tekstura i sa iscrtanim obujmicama svih čvorova grafa scene.

 

Slika 6. Pogled na cijelu scenu sa obujmicama.

 

 

Slika 7. Primjer pogleda u scenu.

 

Algoritam	Broj poligona poslanih na iscrtavanje	FPS
Bez algoritma	145270	173
Odbacivanje stražnjih poligona	145270	206
Odbacivanje po projekcijskom volumenu	31549	240
Odbacivanje stražnjih poligona + odbacivanje po projekcijskom volumenu	31549	304

Tablica 1. Tablica uz sliku 7.

 

Slika 8. Primjer pogleda u scenu.

 

Algoritam	Broj poligona poslanih na iscrtavanje	FPS
Bez algoritma	145270	74
Odbacivanje stražnjih poligona	145270	114
Odbacivanje po projekcijskom volumenu	118848	65
Odbacivanje stražnjih poligona + odbacivanje po projekcijskom volumenu	118848	105

Tablica 2. Tablica uz sliku 8.

 

Primjer na slici 7 je primjer pogleda u scenu kod kojeg algoritam za odbacivanje poligona daje ubrzanje iscrtavanja, a na slici 8 dolazi do usporavanja iscrtavanja jer je gotovo čitava scena vidljiva i algoritam nam je nepotreban..

 

Slika 9. Primjer pogleda u scenu.

 

Algoritam	Broj poligona poslanih na iscrtavanje	FPS
Odbacivanje po projekcijskom volumenu	123891	188
“Stani i čekaj“	17806	171
CHC++	17806	243

Tablica 3. Tablica uz sliku 9.

 

Slika 10. Pogled u scenu.

 

Algoritam	Broj poligona poslanih na iscrtavanje	FPS
Odbacivanje po projekcijskom volumenu	71942	220
“Stani i čekaj“	71942	102
CHC++	71942	212

Tablica 4. Tablica uz sliku 10.

 

Na slici 9 stoji najbolji pogled u scenu kada govorimo o algoritmima za odbacivanje zaklonjenih poligona. Gotovo čitava scena je zaklonjena i to se vidi na rezultatima. Kod “stani i čekaj“ dobivamo pad za 15-ak FPS-a unatoč puno manjem broju poslanih poligona. Dakle vrijeme koje čekamo na odgovor upita o zaklanjanju je ipak preveliko da bi dobili ikakvo ubrzanje.

Na slici 10 vidimo da najbolje performanse nudi algoritam za odbacivanje po projekcijskom volumenu, no tek nešto lošiji je CHC++. U CHC++ algoritmu svi vidljivi čvorovi se ispituju svaki deseti trenutak prikaza s time da se ne provjeravaju svi u istom trenutku prikaza. Za to je odgovoran slučajni odabir broja trenutka prikaza u kojem će se desiti prvi upit. Tako da se upiti raspodijele po različitim trenutcima prikaza i time ublaže trošak algoritma. Apsolutno najgore rezultate nudi naivna “stani i čekaj“ metoda. U svakom trenutku prikaza se iscrtavaju obujmice od svih vidljivh čvorova (ali ne na ekran), postavljaju se upiti, čekaju se odgovori na te upite i iscrtava se geometrija svih vidljivih čvorova.

 

Graf 1. Primjer prolaska kroz scenu s izmjerenim performansama.

 

Na početku grafa 1 vidimo dio gdje se CHC++ i “stani i čekaj“ algoritam odvajaju i nude puno bolje rezultate nego odbacivanje po projekcijskom volumenu. To je dio kad sam s kamerom ušao u kućicu u sceni i gotovo cijela scena je bila zaklonjena. U tom slučaju je i algoritam “stani i čekaj“ dosta dobar, malo lošiji od CHC++. To je zato što postoji samo jedan vidljiv čvor, a svi ostali se trebaju ispitati i treba pričekati njihove rezultate. Nakon toga sam s kamerom izašao iz kućice što se i očituje na grafu. CHC++ tu bilježi nagli pad FPS-a, no puno manji od naivne metode. To je otprilike onaj pogled koji sam objasnio na slici 16. Vidimo da je CHC++ lošiji od običnog odbacivanja po projekcijskom volumenu i taj pad iznosi oko 20-30 FPS-a. Do kraja prolaska su performanse svih algoritama otprilike iste jer sam krenuo prema najvećem objektu u sceni i samo je on bio vidljiv. Na samom kraju dolazim do stražnje strane modela hotela i okrećem kameru prema sceni. Vidi se da je tu CHC++ nešto bolji od ostala dva algoritma.