Rezultati

U ovom radu je prezentiran GJK algoritam za detekciju sudara dvaju objekata prezentiranih njihovim konveksnim omotačem. Zanima nas kako se GJK algoritam nosi sa primitivnom metodom detekcije sudara dvaju objekata prezentiranih njihovim mrežama poligona. Također nas zanima usporedba GJK algoritma sa korištenjem obujmica.

Primitivnu metodu detekcije sudara u ovom će testu zastupati test za detekciju sudara dvaju trokuta. Od mnogobrojnih metoda koje koriste obujmice, koristiti ćemo jednostavnu metodu obujmica u obliku sfere. Zanima nas kako će se svaki od ova tri načina detekcije sudara nositi sa povećanjem broja poligona kojima su predstavljeni objekti čije sudare provjeravamo.

Gornji graf prikazuje eksponencijalnu složenost testa sudara dvaju trokuta. To ga čini potpuno neprihvatljivim za korištenje kao jedinog algoritma u interaktivnim simulacijama. Algoritam koji detektira sudare dviju obujmica u obliku sfere te tek tada poziva primitivni trokut-trokut test je dao bolje rezultate. No, i kod njega se vidi gotovo eksponencijalna složenost. Razlog tomu je što sfera ne prianja u potpunosti na zadani objekt te imamo zamjetan broj lažnih sudara. To jest sudara dviju obujmica kada ne postoji sudar dvaju objekata. GJK algoritam je polučio najbolje rezultate. Ovaj algoritam posjeduje linearnu složenost. Razlog tomu je u korištenju konveksnog omotača koji je najbolje prianjajuća obujmica. Zbog toga je broj lažnih sudara kod GJK algoritma sveden na minimum. GJK algoritam također u potpunosti iskorištava veliku sličnost između dvaju vremenskih odsječaka korištenjem svjedoka što mu u slučaju kada nema sudara između dva čvrsta tijela omogućuje konstantnu složenost.

Rezultati mjerenja su pokazali da kombinacija konveksnog omotača, kao odlično prianjajuće obujmice, i GJK algoritma, kao metode koja koristi svjedoke, po brzini izvođenja daleko nadmašuje korištenje obujmica u obliku sfere i primitivne metode detekcije sudara dvaju trokuta.