Gradiva nauk.si zahtevajo za pravilen prikaz sodoben brskalnik. Preverjeno delujejo
z brskalniki Mozilla Firefox 3.5+, Google Chrome 4.0+, Safari 4.0+, Internet Explorer 8.0+ ali Opera 10.50+.
V primeru, da uporabljate Internet Explorer 8, preverite, če imate vklopljen združljivostni način
(Compatibility view), ki ga lahko izklopite s klikom na ikono, ki jo vidite na spodnji sliki.
Iz varnostnih razlogov je mogoče celozaslonski način
vključiti samo s pritiskom na gumb F11 na tipkovnici.
Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.
Algoritmi za zaznavo trkov
Avtor: Daniel Jevremović
Hvala za ogled gradiva!
Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.
Uvod
Ko govorimo o zaznavi trkov, mislimo proces zaznavanja kdaj bosta dva objekta trčila oziroma kdaj sta trčila. Torej nas zanima, če sta dva objekta v nekem trenutku na istem mestu. Te algoritme v večini uporabljamo pri video igrah in simulacijah, vendar imajo veliko uporabnost tudi v robotiki. Zanima nas kaj se zgodi, ko je trk zaznan, in kako reagirati, da ne bo nastalo težav. Za reševanje problemov trkov je potrebno široko znanje linearne algebre in računalniške geometrije.
Glavni problem zaznave trkov je število potrebnih testov, da ugotovimo kakšno je stanje objektov, kar pa hitro zasiči procesor. Da se število testov omeji, želimo kodo zaznavanja trkov kar se da hitro zapustiti. Težavnost tega problema želimo zmanjšati, kako to storiti pa si bomo pogledali v nadaljevanju.
Motivacija
Da bi bolje razumeli željo oziroma celo nujo po algoritmih za zaznavo trkov, si poglejmo primer simulacije. V fizičnih simulacijah želimo opravljati eksperimente.
Tipičen primer je simulacija igre biljarda, katere fiziko odbijajočih se krogel dobro poznamo s pomočjo znanja o togih telesih in prožnih trkih. Cilj igre je, da s palico odbijemo belo kroglo v druge krogle na mizi in jih spravimo v eno izmed šestih lukenj. Ko simuliramo igro biljarda se v nobenem trenutku ne sme zgoditi, da imamo dve krogli na istem mestu, saj bi bilo to v nasprotju z zakoni fizike. Da zagotovimo, da nikoli ne pridemo v tako situacijo, moramo dobro definirati kaj se zgodi v trenutku, ko dve krogli trčita.
Ko dve krogli trčita, moramo poznati hitrost in smer bele krogle, da lahko nato izračunamo v katero smer in s kakšno hitrostjo se bo vsaka od opazovanih krogel odkotalila.
Simulacija biljarda je sicer enostavna za razumeti, vendar ni stabilna. Še tako majhna napaka v izračunu lahko povzroči ogromne spremembe v končnem stanju krogel.
Video igre imajo podobne zahtevke, vendar z nekaterimi ključnimi razlikami. Medtem ko mora fizična simulacija simulirati realni svet kakor se da natančno, lahko video igre simulirajo fiziko realnega sveta le do mere, ki je sprejemljiva.
Algoritmi
Algoritmov za zaznavo trkov je veliko in se med seboj razlikujejo glede na dimenzijo (premica, ravnina, prostor), koncept časa (zvezen, diskreten), strukture objektov, prožnost trkov, ... vendar jih lahko kljub temu razvrstimo v dve večji kategoriji zaznavanja trkov. Pri poljubnem algoritmu nas v resnici zanima le kako se algoritem odzove na trk. Ti dve kategoriji sta metodi posteriori in priori.
Metoda posteriori
V primeru posteriori metode premikamo simulacijo naprej v majhnih časovnih intervalih, šele nato pa preverimo, če se katerikoli objekti sekajo, oziroma so tako blizu eden drugega, da jih smatramo, kot da se sekajo. Ta metoda trk dopusti, nato pa šele preveri, če je stanje obeh objektov v nasprotju s pravili simulacije. Posteriori metoda uporablja diskreten koncept časa.
V vsakem trenutku nas zanima kateri objekti se sekajo in kje, ne vemo pa točno kdaj se je trk zgodil.
Slabost posteriori metode je ta, da če so časovni intervali predolgi, lahko po nesreči izpustimo primer, ko dva objekta trčita.
Prednost te metode je to, da je potrebno hraniti le stanja objektov, nas pa ne zanimajo fizikalni problemi, ki lahko v simulaciji nastanejo.
Dober primer posteriori metode je video igra Bomberman. Zanima nas kako se dinamični objekt (lik Bomberman) premika v okolju polno škatel.
Lik se lahko premika le za 33 enot (kar pa je ravno širina ene škatle). Iz kode je razvidno, da na vsakem ukazu premika dovolimo, da se lik premakne za 33 enot, šele nato pa preverimo kje ta lik je. Če se lik dotika vijolične ali sive barve, pomeni, da lik stoji na eni izmed škatel ali na zidu. Ker pa je to v nasprotju s pravili, postavimo lik nazaj na prešnjo stanje.
Metoda priori
V primeru priori metod pa se uporabljajo algoritmi za zaznavo trkov, ki lahko predvidijo trk preden se zgodi. Vsak korak je izračunan zelo natančno in tako tudi preprečimo, da bi se katerakoli dva objekta sekala. Priori metoda skrbi, da do trka še ne pride, nato preveri, če se trk sme zgoditi in šele nato dopusti trk.
Ker je treba predvideti trke med objekti je tu potrebno poznati trajektorije in hitrost objektov.
Za razliko s posteriori metodo, se tu koraki izračunajo vnaprej, kar sicer prinese večjo stabilnost problema, ampak na račun več operacij (preveč računanja).
Sedaj pa je na vrsti vprašanje.
Katero metodo bi bilo bolje uporabiti pri omenjenih igrah?
Čeprav lahko za vsako izmed naštetih iger uporabimo katerokoli metodo na levi, so trenutno izbrane metode najbolj uporabne za rešitev.
Napačno
Čeprav lahko za vsako izmed naštetih iger uporabimo katerokoli metodo na levi, obstaja boljši način uporabe.
Optimizacija
Bolj natančni želimo biti, bolj zahtevni morajo biti algoritmi, saj je potrebno upoštevati več faktorjev.
V primeru, kjer imamo na voljo predmetov, moramo opraviti primerjav med objekti, da ugotovimo kateri se sekajo. V večini primerov smo časovno omejeni in si ne smemo privoščiti predolgega računanja. Zato je bolje, da probleme omejimo in rešujemo lokalno.
Vsak primer ima svojo kompleksnost, zahtevke in pričakovanja, vendar kljub temu lahko celoten primer posplošimo, saj je koncept podoben. Objekti v simulaciji imajo lahko povsem različne lastnosti in jih zaradi teh lastnosti lahko ločimo med seboj in obravnavamo posebej.
Poznamo dinamične in statične objekte – torej objekte, ki so vedno pri miru ali se gibljejo. Objektom, ki so pri miru, ne rabimo vedno znova pripisati pozicijo, saj se nikoli ne bodo premaknili. Tistim, ki pa se premikajo, pa lahko pripišemo bližino. Objekti, ki niso blizu eden drugega ne bodo trčili. Torej se opazuje le objekte, ki so glede na pozicijo »blizu« -- kaj pomeni blizu je pa seveda odvisno od simulacije. Obstajajo pa tudi nekateri objekti, ki se dotikajo drugih objektov, zato lahko skupek objektov smatramo kot en sam objekt, ki se kasneje obravnava kot skupek manjših objektov. Zopet odvisno od simulacije, se nekateri objekti lahko gibljejo le znotraj nekega prostora, katerega nikoli ne zapustijo.
Če natančno vemo kateri objekti so statični in kateri dinamični, potem je dovolj, da opazujemo le dinamične objekte.
Primer: Računalniška igra nogometa
Pri igri nogometa lahko stvari precej optimiziramo. Ker ne gre za fizično simulacijo, nas gledalci kot posamezni objekti ne zanimajo, zato jih lahko obravnavamo kot celoto, ki ne bo nikoli blizu ostalim objektom znotraj igre. Prav tako to velja za vse fizične objekte zunaj igrišča.
Vsi objekti razen sodnikov, igralcev, golmanov in žoge so statični. Torej opazujemo le dinamične objekte.
Poleg tega nas igralci in golmani zunaj igrišča ne zanimajo, saj ne pridejo v stik s trenutnimi igralci.
Če dobro premislimo nas sodniki tudi ne zanimajo, saj se gibljejo zunaj igrišča. Za sodnika na igrišču pa lahko rečemo, da nikoli ne pride v stik z igralci, da zgled posplošimo.
Torej smo sedaj problem omejili le na igralce in golmane na igrišču ter žogo.
Ko pa primerjamo objekte med seboj pa lahko rečemo, da sta golmana nasprotnih ekip »daleč« eden od drugega, in zatu ju ni treba vedno primerjati med seboj.
Edini pomembni statični objekt bi bil gol. Poleg gola nas pa tudi zanima rob igrišča, saj nas zanima tudi kaj se zgodi, ko žoga zapusti igrišče.
Katere objekte bi opazovali pri računalniški igri biljarda?
Tako je. Igralec, nasprotnik, miza in palica so povsem nepomembni objekti, ki predstavljajo okolico.
Napačno
Dobro premislite kateri objekti so nepomembni (del okolice).
Razdalja med objekti
Vse do sedaj omenjene situacije, ki zmanjšujejo število potrebnih operacij za izračun trkov so sicer ugodne, ampak kljub vsem tem optimizacijam se izkaže, da je tako računanje še zmeraj precej dolgo. Zato je potreben drugačen pristop.
Če hranimo le podatke o poziciji objektov, potem vemo kateri objekti so dovolj blizu eden drugega. Zato, ker se stanja nekaterih objektov med dvema časovnima intervaloma zelo malo spremenijo, lahko podatke stanj teh objektov prenesemo v podatke novih stanj. Ko imamo podatke o poziciji objektov, potem nas zanima le kaj pomeni biti »blizu«.
Največji problem je računanje razdalje med objektoma. Pomembno se je vprašati kako izmeriti razdaljo med dvema objektoma? Če želimo izvedeti kako oddaljena sta objekta drevo in človek, se moramo odločiti od kje do kje meriti razdaljo.
Merimo od dna objekta?
Torej če nas zanima razdalja med stolpnico in človekom, ki stoji na stolpnici, je potem razdalja kar višina stopnice? To ni prav.
Mogoče od vrha objekta?
Zakaj ta način ni dober lahko sklepamo podobno iz prejšnjega primera.
Kaj pa če kar od sredine objekta?
Tudi tu lahko naletimo na problem, ko je en objekt precej večji od drugega.
Torej moramo meriti od njune najbližje točke.
Če se človek sedaj premakne bližje drevesu, je najbližja točka seveda povsem druga.
Seveda pa ne želimo hraniti koordinate vsakega lista, dela debla, korenin, človekovih prstov na roki, ... samo zato, da bi ugotovili razdaljo med dvema objektoma.
Torej potrebujemo strukturo, ki bo na enostaven način beležila pozicije objektov in nam omogočila lažje računanje razdalj med objekti.
Omejujoče škatle
To storimo tako, da vsakemu objektu pripišemo najmanjšo škatlo z najmanjšimi merami znotraj katere ležijo vse točke objekta. Tem škatlam rečemo omejujoče škatle, ki pa so glede na dimenzijo tudi drugače predstavljene. V 1-dimenzionalnem svetu je to daljica, v 2-dimenzionalnem pravokotnik in v 3-dimenzionalnem kvader. Torej objekte postavimo v škatle, ki imajo to lastnost, da če škatlo na kateri koli stranici zmanjšamo, potem objekt ni več znotraj škatle v celoti. Škatle poravnamo glede na koordinatne osi (torej so stranice omejujočih škatel vzporedne s koordinatnimi osmi).
Nekaj zgledov
Čajnica v 3D prostoru omejena v kvadru iz različnih zornih kotov.
Sedaj omejujoče škatle predstavljajo objekte. Namesto, da računamo razdaljo med drevesom in človekom, jo računamo med njunimi škatlami.
Računanje razdalje med škatlami (med daljicami, pravokotniki ali kvadri) je sedaj precej bolj enostavno. Pozicije objektov predstavljajo koordinate škatel.
Ne glede na dimenzijo, če želimo vedeti kje in kako velika je omejujoča škatla nekega objekta, potrebujemo le informacijo o dveh točkah, ki to škatlo predstavljata.
Za daljico potrebujemo le dve točki, ki ju daljica povezuje.
Za pravokotnik potrebujemo le dve točki (levo spodnjo in desno zgornjo), da ga definiramo. Torej le točki, ki ju diagonala pravokotnika določa.
Prav tako za kvader potrebujemo le točki, ki ponazarjata diagonalo kvadra.
Če poznamo dani točki, potem lahko hitro izračunamo še preostale.
Napačno
Prva koordinata predstavlja x os, druga y os.
Omejujoče škatle - sekanje
Iz danih dveh točk lahko hitro izračunamo tudi preostale. Tako poznamo dolžino/ploščino/prostornino škatle in tudi kje se nahaja.
Pravokotnik na prejšnji strani torej predstavljata intervala [1, 4] na x osi ter [3, 5] na y osi.
Kako pa vemo, če ta pravokotnik seka kateri drugi pravokotnik?
To se zgodi natanko takrat, ko obstaja še kakšen pravokotnik, ki je vsaj deloma znotraj intervalov [1, 4] na x osi in [3, 5] na y osi.
Recimo, da imamo pravokotnika A in B, ki sta predstavljena vsak z dvema točkama. Pravokotnik A leži na intervalu [Axmin, Axmax] na x osi, pravokotnik B pa na intervalu [Bxmin, Bxmax] na x osi. Kako lahko računsko preverimo, če se pravokotnika sekata (Trenutno zanemarimo y os. Lahko se odločimo, da se na y osi pravokotnika že sekata)?
Če preverimo neenačbi in , potem vemo, če se pravokotnika sekata.
Podobno preverimo za intervale y osi, in tako vemo, če se pravokotnika zares sekata.
Podobno velja tudi za kvadre, le da imamo tu še tretji interval, za katerega moramo preveriti prekrivanje.
Sedaj je koncept trka že precej bolj jasen. Ko sta dve omejujoči škatli glede na pozicijo v simulaciji blizu, preverimo, če se omejujoči škatli sekata. Če se ne, se ne zgodi nič, če pa se, pa gremo na naslednji korak. Kaj pomeni pojem »blizu« pa je odvisno od simulacije (na primer pri video igri nogometa bi lahko pojem »blizu« predstavljal 1 meter razdalje, saj lahko zaradi hitrosti žoge nastanejo hitre spremembe v njeni okolici).
Omejujoči škatli se sekata
Ko naletimo na primer, da se dva omejujoče škatle sekata, nas zanima kaj to pomeni. Ali to pomeni, da sta objekta trčila? Ni nujno.
Poglejmo si par primerov.
Drugi objekt se dotika škatle prvega, vendar se ne dotika prvega objekta.
Dva plovila sta blizu eden drugega. Njuni omejujoči škatli se sekata, vendar objekta še nista trčila niti se ne dotikata.
Na sliki je več različnih objektov in njihove omejujoče škatle. Tu vidimo primer, kjer sta dva objekta dovolj blizu, da se njuni omejujoči škatli sekata, sama objekta pa ne. Vidimo pa tudi primer, kjer se objekta sekata.
Ko vemo, da se omejujoče škatle sekajo, še ne pomeni, da se objekta sekata. Objekti so znotraj škatel, niso pa celotna škatla.
Pomembno je razumeti, da se omejujoče škatle uporabljajo le zato, da lažje računamo razdalje med objekti in njihovo pozicijo.
Podane imamo dvakrat po dve točki. Oba para točk predstavljata neko omejujočo škatlo, kot je narisano na sliki. Ti omejujoči škatli predstavljata vsaka svoj lik (lika na sliki sta tu le za lažjo predstavo). Kaj lahko zagotovo razberemo iz danih informacij? Ali se omejujoči škatli teh dveh objektov sekata? Se morda objekta sekata?
Kot smo rekli, informacija, da se omejujoči škatli sekata nam pove le to, da sta objekta dovolj blizu, da nas zanima, če se sekata.
Napačno
Slika je tu le za predstavo. Informacijo imate le o omejujočih škatlah.
Algoritem »počisti in obreži«
Povedali smo, da vse objekte postavimo v svoje omejujoče škatle. Koordinate škatel poznamo in jih nekje hranimo. Podatke običajno hranimo v dveh seznamih. En seznam hrani x-koordinate omejujočih škatel, drugi seznam pa y-koordinate omejujočih škatel. Tako ima vsak izmed seznamov elementov ( je število omejujočih škatel, vsaka omejujoča škatla pa je predstavljena z dvema x koordinatama in dvema y koordinatama).
Zapomnimo si kateri elementi seznama predstavljajo kateri objekt, nato pa sezname uredimo po velikosti.
Indeks elementov predstavlja objekt, črke 'a' in 'b' pa predstavljajo min in max koordinato osi x (torej xmin in xmax), črke 'c' in 'd' pa predstavljajo min in max koordinato osi y (torej ymin in ymax).
Če pogledamo zgornjo sliko in opazujemo objekt 6 (rdeče obarvan) lahko marsikaj ugotovimo. Ker so elementi urejeni po velikosti, pomeni, da sta na x osi možna le dva objekta, ki sekata interval objekta 6. To preverimo tako, da pogledamo kateri indeksi elementov se nahajajo med vrednostima a in b (xmin in xmax) objekta 6. Iz seznama seznam_x vidimo, da sta to elementa b9 in b8 (torej objekta 9 in 8). Sedaj pa pogledamo v seznam seznam_y in vse kar nas zanima je, če je kateri od objektov 8 ali 9 v temu seznamu med elementoma c6 in d6. To je res zato, ker smo prej spoznali, da se dva objekta sekata, če se vsi njuni intervali, ki objekt določajo, med seboj sekajo. Torej, ker se v seznamu seznam_x z objektom 6 sekata le intervala objektov 8 in 9, potem sta to tudi edina objekta, ki lahko sekata objekt 6. V seznamu seznam_y vidimo, da se nahaja element d8, kar takoj pomeni, da se objekta 6 in 8 sekata.
Ko algoritem za iskanje parov objektov, ki se sekajo, najde tak par, potem to situacijo pogledamo bližje.
Torej imamo dva objekta, katerih omejujoči škatli se sekata. V tem trenutku mi še ne vemo, če se objekta dotikata ali celo sekata. Sedaj pa naredimo naslednji korak.
Vsakega izmed objektov razdelimo na manjše dele, in tem delom priredimo omejujoče škatle.
Kako objekte razdelimo na manjše dele je odvisno od posameznika.
Kot vidimo iz zgleda, je lik sedaj sestavljen iz štirih omejujočih škatel, ki pa skupaj zasedejo manj prostora kot prej in se bolj prilegajo objektu.
Sedaj, ko imamo lik razdeljen na manjše dele, pa lahko primerjamo škatle enega objekta s škatlami drugega objekta in iščemo, če se sedaj kateri izmed delov seka.
Postopek od tu naprej se ponavlja.
Če najdemo omejujoči škatli delov objekta, ki se sekata, ta dva dela razdelimo na še manjše dele in jih postavimo v omejujoče škatle. Koliko korakov deljenja objektov bomo opravili je odvisno od uporabnikov kako natančno simulacijo ali video igro želijo imeti.
Stare igre so ponavadi imele le eno omejujočo škatlo in sekanje omejujočih škatel je pomenilo kar sekanje objektov. Ker so igralci postali zahtevnejši, so želeli boljšo natančnost, in takrat so morali začeti uporabljati natančnejše algoritme. Seveda pa, večkrat je bil ta postopek izveden, več računanja je bilo potrebnega. Zato je rast iger naraščala vzporedno z zmogljivostjo računalnikov, ki so jih imeli igralci. Sedanje igre imajo natančnost trkov že zelo dobro definirano in je zaradi tega vse manj nezadovoljstva glede teh problemov.
V seznamu seznam_x sta na intervalu 2. objekta intervala objektov 4 in 1, v seznamu seznam_y pa na intervalu 2. objekta intervala objektov 4 in 3. Ker se interval 4. objekta pojavi v obeh seznamih na intervalu 2. objekta, se potem objekta 4 in 2 sekata. Preostalih možnosti ni.
Napačno
Preveriti je treba oba seznama.
Vprašanje - deljenje objekta na manjše dele
Premislite, če je pri video igri biljarda potrebno deljenje objektov na manjše dele.
Krogle imajo to značilnost, da ne glede na koliko delov kroglo razdelimo, je tisti del, ki leži na sredini (največji polmer) vedno enako širok. Ker pa pri igri biljarda opazujemo le če so krogle tik ena ob drugi, ne bo krogla nikoli uspela priti bližje kot že v prvotnem primeru.
Napačno
Krogle imajo to značilnost, da ne glede na koliko delov kroglo razdelimo, je tisti del, ki leži na sredini (največji polmer) vedno enako širok. Ker pa pri igri biljarda opazujemo le če so krogle tik ena ob drugi, ne bo krogla nikoli uspela priti bližje kot že v prvotnem primeru. Je pa primer malce »za lase privlečen«, saj brez omembe vnaprej niste mogli vedeti, da pri video igrah biljarda krogle nikoli ne »odskočijo« v zrak (ne zapustijo tal).
Drugačni liki
Do sedaj smo vedno omenjali omejujoče škatle. Obstajajo pa tudi drugi liki, ki lahko objekte omejijo.
Taki liki so lahko trikotniki/piramide, elipse/sfere, ipd ... Važno je le, da so ti liki konveksni in da je računanje razdalje med njimi enostavno. Konveksni liki imajo to lastnost, da če poljubni točki znotraj lika povežemo med seboj z ravno črto, lika ne bomo nikoli zapustili.
Video algoritma počisti in obreži
Spodaj je enostaven zgled kako poteka algoritem počisti in obreži. Prikazane so le omejujoče škatle nekih objektov, ki se premikajo. Algoritem na vsakem koraku zabeleži, katere omejujoče škatle se sekajo in si zapomni pare teh objektov.
Kot smo že prej omenili, če na tem koraku končamo je odvisno od uporabnikov. Če je sekanje omejujočih škatel objekta dovolj, potem ta algoritem vrne le pare objektov, ki se sekajo. Sicer pa algoritem pošlje podatke (pare objektov, ki se sekajo) naprej naslednjemu algoritmu, ki problem rešuje lokalno. Seveda pa lahko naslednji algoritem tudi sledi načelu počisti in obreži.
Zgled uporabe
Poglejmo si še celoten postopek na zgledu.
Zaključna misel
V večini primerov so algoritmi za zaznavo trkov nuja, saj v trenutku, ko želimo povedati, da se en objekt dotika drugega, nastane potreba po teh algoritmih. Razumeti osnovno idejo teh algoritmov je enostavno, vendar je tu še veliko prostora za izboljšavo.
