See on meie videomängude füüsikat käsitleva kolmeosalise sarja II osa. Vaadake selle sarja ülejäänud osa:

I osa: Sissejuhatus jäikusse kehadünaamikasse
III osa: piiratud jäiga keha simulatsioon

---

Selle sarja I osas uurisime jäikaid kehasid ja nende liikumisi. Selles arutelus ei olnud objektid aga omavahel seotud. Ilma lisatööta võivad simuleeritud jäigad kehad üksteisest läbi minna ehk „läbistada”, mis on enamikul juhtudel ebasoovitav.

Tahkete objektide käitumise realistlikumaks simuleerimiseks peame kontrollima, kas nad põrkuvad üksteisega iga kord, kui nad liiguvad, ja kui nad seda teevad, peame sellega midagi ette võtma, näiteks rakendama nende kiirusi muutvaid jõude, nii et et nad liiguvad vastassuunas. Siin on kokkupõrkefüüsika mõistmine eriti oluline mängude arendajad .

II osas käsitleme kokkupõrke tuvastamise etappi, mis seisneb kehapaaride leidmises, mis põrkavad kokku võimaliku hulga kehade vahel, mis on hajutatud 2D või 3D maailmas. Järgmises ja viimases osas räägime lähemalt nende kokkupõrgete „lahendamisest“ läbitungimiste kõrvaldamiseks.

Selles artiklis viidatud lineaarse algebra mõistete ülevaatamiseks võite viidata I osa lineaaralgebra krahhikursus .

kuidas saada twitteri andmeid

Kokkupõrkefüüsika videomängudes

Jäikade kehasimulatsioonide kontekstis toimub kokkupõrge, kui kahe jäiga keha kuju ristuvad või kui nende kuju vaheline kaugus langeb alla väikese tolerantsi.

Kui meil on n meie simulatsioonis on paaris testidega kokkupõrgete tuvastamise arvutuslik keerukus VÕI ( n 2), arv, mis paneb arvutiteadlasi kripeldama. Paarikatsete arv suureneb kehade arvuga kvadratuurselt ning määrata, kas kaks suvalises asendis ja suunas asuvat kuju kokku põrkavad, pole juba odav. Kokkupõrke tuvastamise protsessi optimeerimiseks jagame selle tavaliselt kahte faasi: lai faas ja kitsas faas .

Lai faas vastutab jäikade kehapaaride leidmise eest potentsiaalselt kokkupõrge ja välistatakse paarid, mis kindlasti ei põrka, kogu simulatsioonis olevate kehade hulgast. See samm peab olema võimeline tõeliselt hästi mõõtma jäikade kehade arvuga, et veenduda, et püsime hästi all VÕI ( n 2)aja keerukus. Selle saavutamiseks kasutatakse tavaliselt selles faasis ruumi jaotamine koos siduvad mahud mis määravad kokkupõrke ülemise piiri.

Kitsas faas töötab jäikade kehapaaride korral, mille on leidnud laia faasi kokkupõrge. See on täpsustamisetapp, kus tehakse kindlaks, kas kokkupõrked tegelikult toimuvad, ja iga leitud kokkupõrke korral arvutame välja kontaktpunktid, mida hiljem kokkupõrgete lahendamiseks kasutatakse.

Järgmistes jaotistes räägime mõnest algoritmist, mida saab kasutada laia faasi ja kitsa faasi korral.

Lai faas

Videomängude kokkupõrkefüüsika laias faasis peame tuvastama, millised jäikade kehade paarid võib põrkuma. Nendel kehadel võib olla keeruline kuju, näiteks hulktahukad ja hulktahukad, ja mida saame selle kiirendamiseks teha, on kasutada objekti hõlbustamiseks lihtsamat kuju. Kui need siduvad mahud ei ristu, siis ei ristu ka tegelikud kujundid. Kui need ristuvad, siis tegelikud kujundid võib ristuvad.

Mõned populaarsed piiravate köidete tüübid on orienteeritud sidumiskastid (OBB), ringid 2D-s ja sfäärid 3D-s. Vaatame ühte kõige lihtsamat köidet: teljega joondatud piirikastid (AABB) .

AABB-d saavad füüsika programmeerijatelt palju armastust, kuna need on lihtsad ja pakuvad häid kompromisse. Kahemõõtmelist AABB-d võib C-keeles esitada sellise struktuuriga:

typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

min väli tähistab kasti vasaku alumise nurga ja max asukohta väli tähistab paremat ülanurka.

Kahe AABB ristumise testimiseks peame välja selgitama ainult selle, kas nende projektsioonid ristuvad kõigil koordinaattelgedel:

BOOL TestAABBOverlap(AABB* a, AABB* b) d2y > 0.0f) return FALSE; return TRUE;

Sellel koodil on sama loogika kui b2TestOverlap funktsioon alates Kast2D mootor (versioon 2.3.0). See arvutab erinevuse min vahel ja max mõlema AABB mõlema telje mõlemas järjekorras. Kui mõni neist väärtustest on suurem kui null, siis AABB-d ei ristu.

Kuigi AABB kattuv test on odav, pole sellest palju abi, kui teeme ikkagi iga võimaliku paari jaoks paarikaupa teste, kuna meil on endiselt soovimatuid teste VÕI ( n 2)aja keerukus. AABB kattuvate testide arvu minimeerimiseks võime kasutada mingisuguseid ruumi jaotamine , mis töötab samadel põhimõtetel nagu andmebaasi indeksid mis kiirendab päringuid. (Geograafilised andmebaasid, nt PostGIS , kasutavad oma ruumiliste indeksite jaoks tegelikult sarnaseid andmestruktuure ja algoritme.) Sel juhul aga liiguvad AABB-d pidevalt ringi, nii et üldiselt peame pärast simulatsiooni iga sammu uuesti indeksid looma.

Selleks on palju ruumi jagamise algoritme ja andmestruktuure, näiteks ühtlased võred , nelipuud 2D-s, kaheksandikud 3D-vormingus ja ruumiline räsimine . Vaatame lähemalt kahte populaarset ruumilise jaotuse algoritmi: sorteerimise ja pühkimise ning piiravate helihierarhiate (BVH).

Sortimis- ja pühkimisalgoritm

The sorteeri ja pühi meetod (alternatiivina tuntud kui pühkima ja kärpima ) on füüsika programmeerijate seas üks lemmikvalikuid, mida kasutatakse jäikus keha simulatsioonis. The Kuulifüüsika Näiteks on mootoril seda meetodit rakendatud btAxisSweep3 klass.

Ühe AABB projektsioon ühele koordinaatteljele on põhimõtteliselt intervall[ b , on ](see tähendab algus ja lõpp). Meie simulatsioonis on meil palju jäiku keha ja seega palju AABB-sid ning see tähendab palju intervalle. Tahame teada saada, millised intervallid ristuvad.

Sorteerimise ja pühkimise algoritmis sisestame kõik b ja on väärtused ühes loendis ja sortida see skalaarsete väärtuste järgi kasvavas järjestuses. Siis meie pühkima või loendis liikuda. Alati kui b väärtusega, salvestatakse selle vastav intervall eraldi loendis aktiivsed intervallid ja alati on väärtus, eemaldatakse selle vastav intervall aktiivsete intervallide loendist. Igal hetkel lõikuvad kõik aktiivsed intervallid. (Kontrollige David Baraffi doktoritöö , lk. 52 üksikasjad. Soovitan kasutada see veebitööriist postskripti faili kuvamiseks.) Intervallide loendit saab simulatsiooni igas etapis uuesti kasutada, kus saame selle loendi tõhusalt ümber sortida sisestamise sort , mis sobib peaaegu sorditud loendite sorteerimiseks.

Kahes ja kolmes mõõtmes vähendab sortimise ja pühkimise juhtimine, nagu eespool kirjeldatud, üle ühe koordinaattelje ühe AABB otseste ristumiskatsete arvu, mis tuleb läbi viia, kuid tasuvus võib olla parem kui ühe koordinaattelje üle teise. Seetõttu rakendatakse sorteerimise ja pühkimise algoritmi keerukamaid variatsioone. Oma raamatus Reaalajas kokkupõrke tuvastamine (lehekülg 336) esitab Christer Ericson tõhusa variatsiooni, kus ta salvestab kõik AABB-d ühte massiivi ning iga sorteerimise ja pühkimise katse jaoks valitakse üks koordinaattelg ja massiiv sorteeritakse min valitud telje AABBde väärtus, kasutades kiirsort . Seejärel läbitakse massiiv ja tehakse AABB kattuvuse testid. Järgmise sorteerimise jaoks kasutatava telje määramiseks dispersioon arvutatakse AABB-de keskpunkt ja järgmiseks etapiks valitakse suurema varieeruvusega telg.

Dünaamilised piiravad mahupuud

Teine kasulik ruumilise jaotamise meetod on dünaamiline piirava mahu puu , tuntud ka kui Dbvt . See on teatud tüüpi piirava mahu hierarhia .

Dbvt on binaarne puu, milles igal sõlmel on AABB, mis piirab kõiki oma laste AABB-sid. Jäikade kehade AABB-d asuvad lehesõlmedes. Tavaliselt 'küsitakse' Dbvt-d, andes AABB-le, mille jaoks me tahaksime ristmikke tuvastada. See toiming on tõhus, kuna nende sõlmede lapsi, kes ei ristle päringutega AABB, ei ole vaja kattuvust testida. Sellisena algab AABB kokkupõrke päring juurist ja jätkub rekursiivselt läbi puu ainult nende AABB sõlmede puhul, mis lõikuvad päringu AABB-ga. Puu saab läbi tasakaalustada puude pöörlemised , nagu ka AVL puu .

Box2D-l on Dbvt keerukas juurutamine b2DynamicTree klass . The b2BroadPhase klass vastutab laia faasi teostamise eest ja kasutab eksemplari b2DynamicTree AABB päringute täitmiseks.

Kitsas faas

Pärast videomängude kokkupõrkefüüsika laia faasi on meil olemas paar jäiku keha paari potentsiaalselt kokkupõrge. Seega peame iga paari jaoks, arvestades mõlema keha kuju, asukohta ja suunda, välja selgitama, kas nad tegelikult põrkuvad; kui nad ristuvad või kui nende vahemaa langeb väikese tolerantsi väärtuse alla. Samuti peame teadma kokkupõrkekehade kokkupuutepunkte, kuna seda on vaja kokkupõrgete hilisemaks lahendamiseks.

Kumerad ja nõgusad kujundid

Videomängu füüsika üldreeglina pole triviaalne kindlaks teha, kas kaks suvalist kuju ristuvad, ega arvutada nende vahelist kaugust. Üks omadus, millel on kriitilise tähtsusega raskuse kindlaksmääramisel, on kumerus kuju. Kujud võivad olla mõlemad kumer või nõgus ja nõgusate kujunditega on raskem töötada, seetõttu vajame nende lahendamiseks mõnda strateegiat.

Kumer kuju langeb joonelõigu suvalise kahe punkti vahel alati täielikult kuju sisse. Nõgusa (või mitte-kumera) kuju puhul ei kehti sama kõigi kuju punktide ühendamise võimalike joonelõikude kohta. Kui leiate vähemalt ühe joonelõigu, mis jääb kujust üldse välja, siis on kuju nõgus.

Arvutuslikult on soovitav, et kõik kujundid oleksid simulatsioonis kumerad, kuna meil on palju võimsaid kauguse ja ristumiskatse algoritme, mis töötavad kumerate kujunditega. Kõik objektid ei ole siiski kumerad ja tavaliselt töötame nende ümber kahel viisil: kumer kere ja kumer lagunemine.

The kumer kere kuju on väikseim kumer kuju, mis seda täielikult sisaldab. Kahemõõtmelise nõgusa hulknurga jaoks oleks see sama, kui haamrida nael igale tipule ja mähkida kummipael kõigi küünte ümber. Polügooni või hulktahuka või üldisemalt punktide hulga kumera kere arvutamiseks on hea algoritm kasutada järgmist: kiirkorpus algoritm, mille keskmine ajaline keerukus on VÕI ( n logi n ).

Ilmselgelt, kui kasutame nõgusa eseme kujutamiseks kumerat kere, kaotavad see nõgusad omadused. Võib ilmneda soovimatu käitumine, näiteks kokkupõrked kummitusega, kuna objektil on endiselt nõgus graafiline esitus. Näiteks on autol tavaliselt nõgus kuju ja kui kasutame selle füüsiliseks kujutamiseks kumerat kere ja paneme siis kasti, võib kasti näida hõljuvat ülal asuvas ruumis.

c # android visuaalne stuudio

Üldiselt on kumerad kered nõgusate objektide esindamiseks sageli piisavalt head kas seetõttu, et ebareaalsed kokkupõrked pole eriti märgatavad või pole nende nõgusad omadused simuleeritava jaoks olulised. Mõnel juhul võime siiski soovida, et nõgus objekt käituks füüsiliselt nõgusa kujuna. Näiteks kui kasutame kausi füüsiliseks kujutamiseks kumerat kere, ei saa me sinna midagi panna. Objektid hõljuvad selle peal lihtsalt. Sellisel juhul võime kasutada a kumer lagunemine nõgusa kujuga.

Kumerad lagunemisalgoritmid saavad nõgusa kuju ja tagastavad kumerate kujundite hulga, mille liit on identne algse nõgusa kujuga. Mõningaid nõgusaid kujundeid saab kujutada ainult suure hulga kumerate kujunditega ning nende arvutamine ja kasutamine võib osutuda ülemäära kulukaks. Lähenemine on aga sageli piisavalt hea ja nii, näiteks sellised algoritmid V-HACD toota nõgusast hulktahust väike kumerate hulktaimede komplekt.

Paljudel kollisioonifüüsikalistel juhtudel võib kumerat lagunemist käsitsi teha kunstnik. See välistab vajaduse maksustada tulemuslikkust lagunemisalgoritmidega. Kuna jõudlus on reaalajas toimuvate simulatsioonide üks olulisemaid aspekte, on üldjuhul hea mõte luua keeruliste graafiliste objektide jaoks väga lihtsad füüsilised esitused. Alloleval pildil on 2D auto üks võimalik kumer lagunemine, kasutades üheksat kumerat kuju.

Ristmike testimine - eraldava telje teoreem

The eraldava telje teoreem (SAT) väidab, et kaks kumerat kuju ei ristu siis ja ainult siis, kui on olemas vähemalt üks telg, kus sellel teljel olevate kujundite ristkülikud ei ristu.

Tavaliselt on visuaalselt intuitiivsem leida 2D-st joon või 3D-tasapind, mis eraldab kahte kuju, mis on tegelikult sama põhimõte. 2D sirgele ristkülikukujulist vektorit või 3D tasapinna normaalvektorit 3D-s saab kasutada eraldusteljena.

Mängufüüsikamootoritel on arvukalt erinevaid klassikujundeid, näiteks ringid (3D-sfääris olevad sfäärid), servad (ühe rea segment) ja kumerad hulknurgad (3D-kujulised hulktahukad). Iga kuju tüübi paari jaoks on neil kindel kokkupõrke tuvastamise algoritm. Lihtsaim neist on tõenäoliselt ringi-ringi algoritm:

typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Kuigi SAT kehtib ringide kohta, on palju lihtsam kontrollida, kas nende keskpunktide vaheline kaugus on väiksem kui nende raadiuste summa. Sel põhjusel kasutatakse SAT-i kokkupõrke tuvastamise algoritmis konkreetsete kujundiklasside paaride jaoks, näiteks kumer hulknurk kumera hulknurga (või 3D-kujuliste hulktahukate) vastu.

Mis tahes kujundipaari jaoks on lõpmatu arv telgi, mida saame eraldamiseks testida. Seega on SAT-i tõhusa rakendamise jaoks ülioluline määrata, millist telge testida. Õnneks saame kumerate hulknurkade paari kokkupõrke testimisel potentsiaalsete eraldustelgedena kasutada servanormaale. Normaalne vektor n servast on risti servavektoriga ja osutab väljaspool hulknurka. Iga hulknurga iga serva jaoks peame lihtsalt välja selgitama, kas teise hulknurga kõik tipud on ees servast.

Kui mõni test läbib - see tähendab, et kui mõne serva puhul on teise polügooni kõik tipud ees sellest - siis polügoonid ei ristu. Lineaaralgebra annab selle testi jaoks lihtsa valemi: antud tippudega esimese kuju serv kuni ja b ja tipp v teiselt kujult, kui( v - kuni ) n on suurem kui null, siis on tipp serva ees.

Polüheedrite puhul võime kasutada näo normaalsusi ja ka kõigi servade kombinatsioonide risttoodet igast kujust. See kõlab nagu paljud asjad, mida testida; asjade kiirendamiseks võime siiski viimase kasutatud eraldustelje vahemällu salvestada ja proovida seda simulatsiooni järgmistes etappides uuesti kasutada. Kui vahemällu salvestatud eraldustelg ei eralda enam kujundeid, võime otsida uut telge, alustades eelmise näo või servaga külgnevatest külgedest või servadest. See töötab, sest kehad ei liigu sageli sammude vahel ega pöörle palju.

Box2D kasutab SAT-i, et testida, kas tema polügoon-hulknurk kokkupõrke tuvastamise algoritmis lõikuvad kaks kumerat polügooni b2CollidePolygon.cpp .

Arvutuskaugus - Gilbert-Johnson-Keerthi algoritm

Paljudel kokkupõrkefüüsikalistel juhtudel tahame objekte pidada kokkupõrkeks mitte ainult siis, kui need tegelikult ristuvad, vaid ka siis, kui nad on üksteisele väga lähedal, mis nõuab, et me teaksime nende vahelist kaugust. The Gilbert-Johnson-Keerthi (GJK) algoritm arvutab kahe kumera kuju ja nende lähimate punktide vahelise kauguse. See on elegantne algoritm, mis töötab kumerate kujundite kaudse esitamisega tugifunktsioonide, Minkowski summade ja simplexide kaudu, nagu allpool selgitatud.

Tugifunktsioonid

TO tugifunktsioon s TO( d )tagastab punkti kuju piirilTOmillel on vektoril suurim projektsioon d . Matemaatiliselt on sellel kõrgeima punktiga toode d . Seda nimetatakse a tugipunkt ja seda toimingut tuntakse ka kui toetada kaardistamist . Geomeetriliselt on see punkt kuju suunas kõige kaugem punkt d .

Tugipunkti leidmine polügoonil on suhteliselt lihtne. Vektori tugipunkti jaoks d , peate lihtsalt sirvima selle tipud ja leidma selle, millel on kõige kõrgema punktiga toode d , nagu nii:

Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i highest) { highest = dot; support = v; } } return support; }

Tugifunktsiooni tegelik jõud on aga see, mis hõlbustab töötamist muu hulgas näiteks koonuste, silindrite ja ellipsidega. Selliste kujundite vahekaugust on üsna raske otseselt arvutada ja ilma sellise algoritmita nagu GJK peate asjade lihtsustamiseks tavaliselt diskretiseerima hulknurkseks või hulktahukateks. See võib aga kaasa tuua täiendavaid probleeme, kuna hulktahuka pind ei ole nii sile kui näiteks sfääri pind, välja arvatud juhul, kui hulktahukas on väga detailne, mis võib kokkupõrke tuvastamisel põhjustada halba jõudlust. Samuti võivad ilmneda muud soovimatud kõrvaltoimed; näiteks ei pruugi polühedraalne kera sujuvalt veereda.

Päritolule keskendunud sfääri tugipunkti saamiseks peame lihtsalt normaliseeruma d (see tähendab arvutage d / || d ||, mis on vektor, mille pikkus on 1 (pikkuse ühik) ja mis osutab endiselt d ) ja korrutame selle siis sfääri raadiusega.

Kontrollima Gino van den Bergeni paber leida muude kujundite hulgas veel silindrite ja koonuste tugifunktsioonide näiteid.

Muidugi nihutatakse meie objekte simulatsiooniruumis lähtepunktist ja neid pööratakse, nii et me peame suutma arvutada teisendatud kuju tugipunktid. Kasutame afiini transformatsioon T ( x ) = R x + c meie objekte nihutada ja pöörata, kuhu c on nihkevektor ja R on pöörlemismaatriks . See teisendus pöörab esmalt objekti alguse ümber ja seejärel tõlgib selle. Teisendatud kuju tugifunktsioonTOon:

Minkowski summad

The Minkowski summa kahest kujustTOjaBon määratletud kui:

c # üksuse testimise õpetus

See tähendab, et arvutame kõigi selles sisalduvate punktide summaTOjaB. Tulemus on selline täispuhutav TOkoosB.

Samamoodi määratleme Minkowski erinevus kui:

mille võime kirjutada ka Minkowski summanaTOkoos-B:

KumeraksTOjaB,A⊕Bon ka kumer.

Minkowski erinevuse üks kasulik omadus on see, et kui see sisaldab ruumi päritolu, siis lõikuvad kujundid, nagu on näha eelmisest pildist. Miks nii? Sest kui kaks kuju ristuvad, on neil vähemalt üks ühine punkt, mis asub ruumis samas kohas ja nende erinevus on nullvektor, mis on tegelikult alguspunkt.

Minkowski erinevuse teine ​​tore omadus on see, et kui see ei sisalda päritolu, on minimaalne kaugus päritolu ja Minkowski erinevuse vahel kujundite vaheline kaugus.

Kahe kuju vaheline kaugus on määratletud järgmiselt:

Teisisõnu, vahemaaTOjaBon lühima vektori pikkus, millest lähtutakseTOkuniB. See vektor sisaldubA⊖Bja see on väikseima pikkusega, mis on järelikult lähim päritolule.

Üldiselt ei ole lihtne kahe kuju Minkowski summa selgesõnaliselt üles ehitada. Õnneks saame ka siin toetuse kaardistamist kasutada, kuna:

Simplexid

GJK algoritm otsib iteratiivselt Minkowski erinevuse punkti, mis on lähim algpunktile. Ta teeb seda, ehitades rea lihtsad mis on lähemal lähtekohale igas iteratsioonis. Simplex - või täpsemalt, a k-simplex täisarvu jaokskuni- on kumer kerek + 1 täiesti sõltumatu punktid k-mõõtmelises ruumis. See tähendab, et kui kahe punkti puhul ei tohi need kokku langeda, siis kolme punkti korral ei tohi nad lisaks asuda samal sirgel ja kui meil on neli punkti, ei tohi nad samuti asuda samal tasapinnal. Seega on 0-simplex punkt, 1-simplex on sirglõik, 2-simplex on kolmnurk ja 3-simplex on tetraeeder. Kui eemaldame ühe punkti hulgast punkti, vähendame selle mõõtmeid ühe võrra ja kui lisame punkti, siis suurendame selle mõõtmeid ühe võrra.

GJK tegevuses

Paneme selle kõik kokku, et näha, kuidas GJK töötab. Kahe kuju vahelise kauguse määramiseksTOjaB, alustame nende Minkowski erinevuse võtmisestA⊖B. Saadud kujust otsime lähimast punktist lähtekohta, kuna kaugus selle punktini on kahe algkuju vaheline kaugus. Valime mingi punkti v aastalA⊖B, mis on meie kauguse ligikaudne väärtus. Samuti määratleme tühja punktide hulgaIN, mis sisaldab punkte praeguses lihtsustatud testis.

Siis sisestame silmuse. Alustame tugipunkti saamisest aastal = sA⊖B(- v ), punkt edasiA⊖Bkelle projektsioon peale v on päritolule kõige lähemal.

Kui|| aastal ||ei erine palju|| v ||ja nende vaheline nurk ei muutunud palju (vastavalt mõnele ettemääratud tolerantsile), see tähendab, et algoritm on lähenenud ja saame tagasi pöörduda|| v ||kui kaugus.

Muidu lisame aastal kuniIN. Kui kumer kereIN(see tähendab, et simplex) sisaldab päritolu, kujundid lõikuvad ja see tähendab ka, et oleme valmis. Vastasel juhul leiame algpunktile lähima punkti simplexist ja lähtestame siis v olla see uus lähim lähendus. Lõpuks eemaldame kõik punktidINmis ei aita kaasa lähima punkti arvutamisele. (Näiteks kui meil on kolmnurk ja lähim punkt alguspunktile asub selle ühes servas, võime punkti eemaldadaINsee ei ole selle serva tipp.) Seejärel kordame samu samme, kuni algoritm läheneb.

Järgmine pilt näitab GJK algoritmi nelja iteratsiooni näidet. Sinine objekt tähistab Minkowski erinevustA⊖Bja roheline vektor on v . Siit näete, kuidas v lihvib päritolule lähimasse punkti.

GJK algoritmi üksikasjaliku ja põhjaliku selgituse saamiseks vaadake paberit Kiire ja kindel GJK juurutus kumerate objektide kokkupõrke tuvastamiseks , autor Gino van den Bergen. Ajaveeb dyn4j füüsikamootoril on ka a suurepärane postitus GJK-s .

Box2D-l on GJK algoritmi juurutamine aastal b2Distance.cpp , Et b2Distance funktsioon. Ta kasutab oma algoritmis pideva kokkupõrke tuvastamiseks löögi arvutamise ajal GJK-d (teema, mida arutame allpool).

Chimpunki füüsikamootor kasutab kogu kokkupõrke tuvastamiseks GJK-d ja selle rakendamine on sisse lülitatud cpCollision.c , Et GJK funktsioon. Kui GJK algoritm teatab ristumiskohast, peab ta ikkagi teadma, millised on kontaktpunktid koos läbitungimissügavusega. Selleks kasutab ta laieneva polütoobi algoritmi, mida uurime järgmisena.

Tungimissügavuse määramine - laienev polütoobi algoritm

Nagu eespool öeldud, kui kujundidTOjaBristuvad, genereerib GJK simplexiINmis sisaldab päritolu Minkowski erinevuse seesA⊖B. Selles etapis teame ainult, et kujundid ristuvad, kuid paljude kokkupõrketuvastussüsteemide kujundamisel on soovitav osata arvutada, kui palju ristmikke meil on ja milliseid punkte saame kasutada kokkupuutepunktidena, nii et lahendame kokkupõrke realistlikult. The Polütoobi algoritmi laiendamine (EPA) võimaldab meil selle teabe hankida, alustades sealt, kus GJK pooleli jäi: päritolu sisaldava lihtsusega.

The läbitungimissügavus on pikkus minimaalne translatsioonivektor (MTV), mis on väikseim vektor, mida mööda saame ristuva kuju teisendada, et see teisest kujust eraldada.

Kui kaks kuju ristuvad, sisaldab nende Minkowski erinevus alguspunkti ja Minkowski erinevuse piiril olev punkt, mis on lähim lähtekohale, on MTV. EPA algoritm leiab selle punkti, laiendades GJK poolt meile antud kompleksi polügooniks; selle servade järjestikune jagamine uute tippudega.

Kõigepealt leiame algpunktile lähima simplexi serva ja arvutame tugipunkti Minkowski erinevuses suunas, mis on selle servaga normaalne (st sellega risti ja osutab väljaspool hulknurka). Seejärel jagasime selle serva, lisades sellele selle tugipunkti. Kordame neid samme, kuni vektori pikkus ja suund ei muutu palju. Kui algoritm on lähenenud, on meil olemas MTV ja läbitungimissügavus.

Kasutades GJK-d koos EPA-ga, saame kokkupõrke üksikasjaliku kirjelduse, olenemata sellest, kas objektid juba ristuvad, või lihtsalt piisavalt lähedal, et neid kokkupõrkeks pidada.

EPA algoritmi on kirjeldatud artiklis 3D-mänguobjektide läheduspäringud ja läbitungimissügavuse arvutamine , kirjutanud ka Gino van den Bergen. Dyn4j blogil on ka a postitus EPA kohta .

Pidev kokkupõrke tuvastamine

Siiani esitatud videomängu füüsika tehnikad võimaldavad simulatsiooni staatilise hetkepildi jaoks kokkupõrke tuvastamist. Seda nimetatakse diskreetne kokkupõrke tuvastamine ja see ignoreerib eelmise ja praeguse sammu vahel toimuvat. Sel põhjusel ei pruugi mõnda kokkupõrget tuvastada, eriti kiiresti liikuvate objektide puhul. Seda küsimust tuntakse kui tunnelite rajamine .

Pidevat kokkupõrke tuvastamise tehnikat püütakse leida millal simulatsiooni eelmise ja praeguse etapi vahel põrkasid kokku kaks keha. Nad arvutavad mõju aeg , et saaksime siis ajas tagasi minna ja kokkupõrget sel hetkel töödelda.

Mõju aeg (või kokkupuute aeg) t c on ajahetk, kui kahe keha vaheline kaugus on null. Kui suudame kirjutada funktsiooni kahe keha vaheliseks kauguseks pikema aja jooksul, on see, mida me soovime leida, kõige väiksem juur selle funktsiooni. Seega on löögi arvutamise aeg a juurte leidmise probleem .

Mõju arvutamise ajal arvestame keha olekut (asendit ja suunda) eelmises etapis korraga t i - üksja praeguses etapis t i . Asjade lihtsustamiseks eeldame sammude vahel lineaarset liikumist.

Lihtsustame probleemi eeldades, et kujundid on ringid. Kahe ringi jaoks C üksja C 2, raadiusega r üksja r 2, kus nende massikeskus x üksja x 2langevad kokku nende tsentroidiga (st nad pöörlevad loomulikult oma massikeskme ümber), võime kauguse funktsiooni kirjutada järgmiselt:

Arvestades lineaarset liikumist sammude vahel, võime positsiooni jaoks kirjutada järgmise funktsiooni C üksalates t i - ükskuni t i

meediumipäring reageeriva kujunduse jaoks

See on lineaarne interpolatsioon alates x üks( t i - üks)kuni x üks( t i ). Sama saab teha ka x 2. Selle intervalli jaoks võime kirjutada veel ühe kauguse funktsiooni:

Pange see avaldis võrdseks nulliga ja saate a ruutvõrrand peal t . Juured võib leida otse ruutvalem . Kui ringid ei ristu, pole ruutvalemil lahendust. Kui nad seda teevad, võib see põhjustada ühe või kaks juurt. Kui sellel on ainult üks juur, on see väärtus mõju aeg. Kui sellel on kaks juurt, on väikseim neist kokkupõrke aeg ja teine ​​aeg, mil ringid eralduvad. Pange tähele, et löögi aeg on siin arv vahemikus 0 kuni 1. See pole aeg sekundites; see on vaid arv, mille abil saame interpoleerida kehade seisundi kokkupõrke täpsesse kohta.

Pidev kokkupõrke tuvastamine mitte-ringide jaoks

Kaugusfunktsiooni kirjutamine muud tüüpi kujundite jaoks on keeruline peamiselt seetõttu, et nende kaugus sõltub nende orientatsioonist. Sel põhjusel kasutame üldjuhul iteratiivseid algoritme, mis liigutavad objekte igal iteratsioonil aina lähemale piisavalt lähedal pidada kokkupõrkeks.

The konservatiivne edasiminek algoritm liigutab kehasid iteratiivselt edasi (ja pöörab neid). Igas iteratsioonis arvutab see nihke ülemise piiri. Algne algoritm on esitatud Brian Mirtichi doktoritöö (punkt 2.3.2), mis võtab arvesse kehade ballistilist liikumist. See paber Erwin Coumans (Bullet Physics Enginei autor) esitab lihtsama versiooni, mis kasutab konstantseid lineaarseid ja nurkkiireid.

Algoritm arvutab kujundite vahel lähimad punktidTOjaB, joonistab vektori ühest punktist teise ja projitseerib selle vektoril liikumise ülemise piiri arvutamiseks kiiruse. See tagab, et ükski keha punkt ei liigu sellest projektsioonist kaugemale. Seejärel viib see kehad selle summa võrra edasi ja kordub, kuni kaugus langeb väikese tolerantsi väärtuse alla.

Mõnel juhul võib kuluda liiga palju kordusi, näiteks kui ühe keha nurkkiirus on liiga suur.

Kokkupõrgete lahendamine

Kui kokkupõrge on avastatud, on vaja kokkupõrkavate objektide liikumisi realistlikult muuta, näiteks panna nad üksteisest põrkama. Selle teooria järgmises ja viimases osas käsitleme mõningaid populaarseid meetodeid videomängude kokkupõrgete lahendamiseks.

Viited

Kui olete huvitatud kokkupõrkefüüsika, näiteks kokkupõrke tuvastamise algoritmide ja tehnikate, sügavama mõistmise omandamisest, Reaalajas kokkupõrke tuvastamine , autor Christer Ericson, on must-have.

Kuna kokkupõrgete tuvastamine tugineb suuresti geomeetriale, on ApeeScape'i artikkel Arvutusgeomeetria Pythonis: teooriast rakenduseks on suurepärane sissejuhatus teemasse.

Seotud: Sissejuhatav robotite programmeerimise õpetus