SIMULACIJA SUDARA KRUTIH TIJELA

3. Detekcija Sudara


Detekcija sudara uključuje algoritme za određivanje presjeka dva dana objekta. Ti algoritmi moraju odrediti točke sudara i normalu između svih parova objekata koji se sudaraju. Kod složenih objekata detekcija sudara vrlo je vremenski zahtjevna. Zato se ona obično obavlja u dvije faze. Prvo se obavljaju brzi i jednostavni testovi kojima se eliminiraju potencijalni sudari, a zatim vremenski zahtjevni.

3.1. Široka faza

Glavni cilj široke faze detekcije sudara je izbjegavanje izvođenja skupih testova za tijela koja su ionako daleko jedno od drugog. Tijela se u ovoj fazi obuhvaćaju obujmicama. Primjeri obujmica su:
• Kugla
• Kvadar paralelan s koordinatnim osima
• Općeniti kvadar
• Konveksna ljuska
Obujmice služe za aproksimaciju složenog predmeta jednostavnijim predmetom radi lakšeg ispitivanja presjeka. Što je obujmica složenija to bolje aproksimira predmet, ali raste složenost testova presjeka. Ako se obujmice ne sijeku tada očito ne moramo provjeravati ni njihov sadržaj. U ovom radu kao obujmice su korištene kugle jer je test za njih najjednostavniji. Potrebno je samo izračunati udaljenost između dva objekta. Ako je ta udaljenost veća od zbroja polumjera dvaju obujmica, tada se obujmice ne sijeku. Na slici 2.1 prikazan je primjer aproksimacije tetrahedrona i kocke sfernim obujmicama.


Slika 2.1 Jednostavni objekti aproksimirani obujmicama

Kod klasične metode detekcije sudara za svaki od n objekata u sceni provjerava se dali je u sudaru sa nekim od ostalih n-1 objekata. Ukupan broj potrebnih testova je n(n-1)/2 . Čak i kada se koriste obujmice za aproksimaciju predmeta kod većeg broja objekata u sceni ova metoda postaje neprimjenjiva za simulacije u realnom vremenu. Već kod 100 objekata u sceni potrebno je obaviti gotovo 5000 testova u svakom koraku simulacije. Kako ne bismo morali testirati sve parove objekata u sceni objekti se organiziraju u prostorne strukture podataka.

Na slici 3.2 na 2D primjeru prikazana je podjela prostora na četiri dijela. Klasičnom metodom za 9 objekata bilo bi potrebno obaviti 36 testova. Nakon podjele prostora za potencijalne parove sudara uzimaju se samo oni koji se nalaze u istom dijelu, te je sada potrebno obaviti samo 8 testova. Kada bismo donji desni dio još jednom rekurzivno podijelili, broj potencijalnih testova bio bi još manji. Ipak, kad u jednom dijelu ostane dovoljno mali broj objekata, jednostavnije je obaviti testove presjeka za sve objekte nego nastaviti dijeliti prostor.


Slika 3.2 Podijela 2D prostora

U ovom radu korišteno je oktalno stablo. Oktalno stablo rekurzivno dijeli 3D prostor na osam oktanata tj. čvorova. Svaki čvor u stablu predstavlja dio prostora, čvorovi bez djece su listovi i oni sadrže podatke o tome koji objekti se nalazi u tom dijelu prostora. Na slici 3.3 prikazan je primjer dijeljenja 3D prostora na oktane, i pripadajuće stablo. Ako neki objekt presijeca više oktanata informacija o njemu će biti spremljena u svaki od tih oktanata. Daljnji testovi presjeka vrše se samo za objekte koji se nalaze u istom oktanu, što znatno smanjuje broj potrebnih testova. Ipak prostor ne možemo dijeliti beskonačno, jer kad bi oktani postali manji od objekata, objekti bi se počeli pojavljivati u mnogo oktana, te bi zapravo počeli povećavati broj potrebnih testova. Zbog toga je potrebno ograničiti dubinu stabla.


Slika 3.3 Podijela 3D prostora

3.2. Uska faza

U uskoj fazi obavljaju se najskuplji i najprecizniji testovi, odnosno testovi presjeka za pojedine poligone objekata. Kruti objekti na računalu najčešće se prikazuju mrežom trokuta. Za svaki objekt definira se lista vrhova i lista trokuta. Pošto su obijekti sastavljeni isključivo od trokuta potrebno je obaviti testove presjeka za sve trokute objekata koji se potencijalno sudaraju. Test presjeka za trokute obavlja se pomoću sljedećeg algoritma. Trokut T1 nalazi se u ravnini pi1 a trokut T2 u ravnini pi2.

Ravnina pi2 ima sljedeću jednadžbu:

N2•X + d2 = 0

X je bilo koja točka na ravnini, a N2 i d2 se računaju po sljedećim formulama:

N2= (V21-V20)×(V22-V20)

D2= -N2•V20

Prvo se izračunava udaljenost svih vrhova T1 od ravnine pi2.

Udaljenost točke od ravnine računa se po sljedećoj formuli:

dvi= N2•V1i+d2, i=0,1,2

Ako su sve 3 udaljenosti istog predznaka, i nijedna nije jednaka nuli sigurno nema presjeka jer ravnina trokuta T2 uopće ne siječe trokut T1. Detektor javlja da nema presjeka i ne izvršava daljnje testove.

Ako trokut T1 siječe ravninu pi2 isti test ponavlja se za trokut T2 i ravninu pi1.

Nakon toga izračuna se pravac L koji je presjek ravnina pi1 i pi2.

L=O + tD

Gdje je D=N1×N2, a O jedna točka na tom pravcu.

Radi ubrzavanja proračuna pravac L projecira se na os s najvećom komponentom. Vrhovi trokuta se zatim projeciraju na pravac L. Presjeci trokuta T1 i T2 sa linijom L pronalaze se iz sličnosti trokuta.

I0=v2+(v0-v2)*dv2/(dv2-dv0)

I1=v2+(v1-v2)*dv2/(dv2-dv1)

Gdje su v0 i v1 projekcije vrhova s jedne strane pravca L, a v2 projekcija vrha sa suprotne strane. Pronalaze se intervali za oba dva trokuta, te ako se ta dva intervala preklapaju tada se dva trokuta sijeku. Na slici 3.4 prikazana su dva moguća slučaja. U prvom se intervali sijeku, a u drugom nema presjeka.


Slika 3.4 Trokuti sa pripadajućim ravninama

3.3 Točke sudara i normala

Kako bi mogli odrediti reakciju na sudar, u detekciji sudara moraju se odrediti dvije točke na objektima koje su se sudarile, te normala sudara. Zbog pojednostavljenja računa u simulaciji se zanemaruju slučajevi sudara koji su u realnim uvjetima gotovo nemogući, te se dešavaju jako rijetko ili se uopće ne dešavaju. To su slučajevi sudara dva vrha, vrha i brida, dva trokuta ili brida i trokuta. Ako se ti sudari i dogode u simulaciji će biti riješeni kao jedan od dva najčešća slučaja, a to su sudar vrha i trokuta, te sudar dva brida.


Slika 3.5 Sudar vrha jednog i trokuta drugog objekta

Na slici 3.5 prikazan je slučaj kada se vrh jednog objekta sudario sa stranicom drugog. Ovaj slučaj je detektiran kada se intervali jednog trokuta na pravcu L u potpunosti nalaze unutar intervala drugog trokuta. Kod sudara između vrha i trokuta točke sudara lako se određuju. Točka sudara na prvom tijelu je vrh koji se nalazi unutar drugog tijela, a na drugom tijelu to je točka na trokutu najbliža tom vrhu. Radi pojednostavljenja proračuna u simulaciji se za točku na trokutu uzimaju koordinate točke vrha koji probada tijelo. Normala sudara je normala tog trokuta.


Slika 3.6 Sudar bridova objekata

Kod sudara dva brida točke sudara nešto je kompliciranije odrediti. Potrebno je na 2 brida koja su se sudarila pronaći najbliže točke. To radimo pomoću sljedećeg algoritma:

Prvi brid definiran je sa dvije točke P1 i P2, a drugi sa P3 i P4, kao na slici 3.7. Točka na bridu a ima sljedeću jednadžbu:

Pa = P1 + mua (P2 - P1)

Slično tome točka na bridu b ima jednadžbu:

Pb = P3 + mub (P4 - P3)


Slika 3.7 Najbliže točke na bridovima

Vrijednosti mua i mub kreću se od minus beskonačno do beskonačno, a za segmente pravaca između točaka P1 P2 i P3 P4 imaju iznose između 0 i 1.

Pravac koji spaja dvije najbliže točke na linijama bit će okomit na oba pravca:

(Pa - Pb)•(P2 - P1) = 0

(Pa - Pb)•(P4 - P3) = 0

To proširujemo jednadžbama:

( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) )•(P2 - P1) = 0

( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) )•(P4 - P3) = 0

Računanjem skalarnog produkta dobivamo:

d1321 + mua d2121 - mub d4321 = 0

d1343 + mua d4321 - mub d4343 = 0

Gdje je:

dmnop = (Pm - Pn)•(Po - Pp)

S tim da vrijedi: dmnop = dopmn

Rješavanjem se dobiva da je:

mua = ( d1343 d4321 - d1321 d4343 ) / ( d2121 d4343 - d4321 d4321 )

mub = ( d1343 + mua d4321 ) / d4343

Točke sudara dobivamo iz početnih jednadžbi, a za normalu sudara uzima se vektorski produkt vektora smjera dva sudarena brida. Orjentacija normale uvijek je od objekta B prema objektu A.

Sudar je detektiran samo ako se dobivene točke sudara približavaju jedna drugoj. Ako je njihova relativna brzina manja od nule, znači da su se već odbile jedna od druge, te na njih ne primjenjujemo impuls sudara.