Tämä on videopelifysiikan kolmiosaisen sarjan osa II. Katso loput tästä sarjasta:

Osa I: Johdanto jäykkään kehodynamiikkaan
Osa III: Rajoitettu jäykkä kehon simulointi

---

Tämän sarjan osassa I tutkittiin jäykkiä kappaleita ja niiden liikkeitä. Tuossa keskustelussa esineet eivät kuitenkaan olleet vuorovaikutuksessa toistensa kanssa. Ilman lisätyötä simuloidut jäykät kappaleet voivat kulkea suoraan toistensa läpi tai 'tunkeutua', mikä ei ole toivottavaa useimmissa tapauksissa.

Kiinteiden esineiden käyttäytymisen realistisemmaksi simuloimiseksi meidän on tarkistettava törmäävätkö ne toistensa kanssa joka kerta, kun liikkuvat, ja jos näin tapahtuu, meidän on tehtävä asialle jotain, esimerkiksi kohdistamalla voimia, jotka muuttavat niiden nopeuksia, joten että ne liikkuvat vastakkaiseen suuntaan. Tällöin törmäysfysiikan ymmärtäminen on erityisen tärkeää pelikehittäjät .

Osassa II käsitellään törmäystunnistusvaihetta, joka koostuu kehoparien löytämisestä, jotka törmäävät mahdollisesti suuren määrän 2D- tai 3D-maailmaan hajallaan olevien kappaleiden kesken. Seuraavassa viimeisessä erässä puhumme lisää näiden törmäysten 'ratkaisemisesta' läpäisyn poistamiseksi.

Tässä artikkelissa tarkoitettujen lineaaristen algebrakäsitteiden tarkistamiseksi voit viitata lineaarinen algebran törmäyskurssi osassa I .

Törmäysfysiikka videopeleissä

Jäykkien runkosimulaatioiden yhteydessä törmäys tapahtuu, kun kahden jäykän rungon muodot leikkaavat tai kun näiden muotojen välinen etäisyys laskee pienen toleranssin alapuolelle.

Jos meillä on n simulaatiossamme, pareittain tapahtuvien törmäysten havaitseminen on laskennallisesti monimutkaista TAI ( n 2), luku, joka saa tietojenkäsittelijät raivostumaan. Pariskohtaisten testien määrä kasvaa neliöllisesti kappaleiden lukumäärän mukaan, eikä kahden mielivaltaisen asennon ja suunnan törmäämisen määrittäminen jo ole halpaa. Törmäysten havaitsemisen optimoimiseksi jaamme sen yleensä kahteen vaiheeseen: laaja vaihe ja kapea vaihe .

Laaja vaihe on vastuussa jäykkien runkoparien löytämisestä mahdollisesti törmäävät ja sulkemalla pois parit, jotka eivät todellakaan törmää, kaikkien simulaatiossa olevien kappaleiden joukosta. Tämän vaiheen on voitava skaalata todella hyvin jäykkien kappaleiden määrällä, jotta voimme varmistaa, että pysymme hyvin TAI ( n 2)ajan monimutkaisuus. Tämän saavuttamiseksi tässä vaiheessa käytetään yleensä avaruusosiointi yhdistettynä sitovat määrät jotka muodostavat ylärajan törmäykselle.

Kapea vaihe toimii niiden jäykkien kappaleiden parilla, jotka leveä vaihe löytää ja jotka saattavat törmätä. Se on tarkennusvaihe, jossa määritetään, tapahtuvatko törmäykset, ja jokaiselle löydetylle törmäykselle laskemme yhteyspisteet, joita käytetään törmäysten ratkaisemiseen myöhemmin.

Seuraavissa osioissa puhumme joistakin algoritmeista, joita voidaan käyttää laaja- ja kapea-vaiheisina.

Laaja vaihe

Videopelien törmäysfysiikan laajessa vaiheessa meidän on tunnistettava jäykkien kappaleiden parit voi törmätä. Näillä kappaleilla voi olla monimutkaisia ​​muotoja, kuten monikulmioita ja monikulmioita, ja mitä voimme tehdä tämän kiihdyttämiseksi, on käyttää yksinkertaisempaa muotoa kohteen sisällyttämiseen. Jos nämä sitovat määrät eivät leikkaa, niin myös todelliset muodot eivät leikkaa. Jos ne leikkaavat, todelliset muodot voi leikkaa.

Jotkut suositut sidontatyyppityypit ovat suuntautuneet rajoittavat laatikot (OBB), ympyrät 2D-muodossa ja pallot 3D-muodossa. Katsotaanpa yhtä yksinkertaisimmista sidontavolyymeistä: akselin suuntaiset rajoittavat laatikot (AABB) .

AABB: t saavat paljon rakkautta fysiikan ohjelmoijilta, koska ne ovat yksinkertaisia ​​ja tarjoavat hyviä kompromisseja. 2-ulotteinen AABB voidaan esittää tällaisella rakenteella C-kielellä:

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

min -kenttä edustaa laatikon vasemman alakulman ja max -kohdan sijaintia kenttä edustaa oikeaa yläkulmaa.

Jotta voimme testata kahden AABB: n leikkaamista, meidän on vain selvitettävä, leikkaavatko niiden projektiot kaikki koordinaattiakselit:

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

Tällä koodilla on sama logiikka kuin b2TestOverlap toiminto Box2D moottori (versio 2.3.0). Se laskee min: n välisen eron ja max molempien AABB: n molemmissa akseleissa molemmissa tilauksissa. Jos jokin näistä arvoista on suurempi kuin nolla, AABB: t eivät leikkaa.

Vaikka AABB-päällekkäisyystesti on halpa, se ei auta paljoakaan, jos teemme edelleen pareittain testit jokaiselle mahdolliselle parille, koska meillä on edelleen ei-toivottuja TAI ( n 2)ajan monimutkaisuus. AABB-päällekkäisyystestien määrän minimoimiseksi voimme käyttää jonkinlaisia avaruusosiointi , joka toimii samoilla periaatteilla kuin tietokannan indeksit mikä nopeuttaa kyselyjä. (Maantieteelliset tietokannat, kuten PostGIS , käyttävät tosiasiallisesti samanlaisia ​​tietorakenteita ja algoritmeja spatiaalisiin indekseihinsä.) Tässä tapauksessa AABB: t kuitenkin liikkuvat jatkuvasti, joten yleensä meidän on luotava indeksit uudelleen simulaation jokaisen vaiheen jälkeen.

Tähän voidaan käyttää runsaasti tilaa jakavia algoritmeja ja tietorakenteita, kuten yhtenäiset ristikot , quadtrees 2D-muodossa, kahdeksankymmentä 3D-muodossa ja spatiaalinen hajautus . Katsotaanpa tarkemmin kahta suosittua spatiaalisen osioinnin algoritmia: lajittelu ja pyyhkäisy sekä rajoittavat äänenvoimakkuushierarkiat (BVH).

Lajittelu- ja pyyhkäisyalgoritmi

lajittele ja lakaise menetelmä (vaihtoehtoisesti tunnetaan nimellä lakaista ja karsia ) on yksi fysiikan ohjelmoijien suosikkivalinnoista jäykkään kehon simulointiin. Luodin fysiikka Esimerkiksi moottorilla on tämän menetelmän toteutus btAxisSweep3 luokassa.

Yhden AABB: n projektio yhdelle koordinaattiakselille on olennaisesti väli[ b , On ](eli alku ja loppu). Simulaatiossamme meillä on paljon jäykkiä runkoja ja siten monia AABB: itä, mikä tarkoittaa monia välejä. Haluamme selvittää, mitkä välit leikkaavat.

Lajittelu- ja pyyhkäisyalgoritmiin lisätään kaikki b ja On arvot yhdessä luettelossa ja lajittele se nousevasti niiden skalaariarvojen mukaan. Sitten me lakaista tai kiertää luetteloa. Aina a b arvo havaitaan, sen vastaava aikaväli tallennetaan erilliseen luetteloon aktiiviset välit ja aina On arvo havaitaan, sitä vastaava väli poistetaan aktiivisten aikavälien luettelosta. Milloin tahansa, kaikki aktiiviset aikavälit leikkaavat. (Tarkista David Baraffin väitöskirja , s. 52 lisätietoja. Ehdotan käyttää tämä online-työkalu PostScript-tiedoston tarkastelemiseksi.) Aikaväliluetteloa voidaan käyttää uudelleen jokaisessa simulaation vaiheessa, jossa voimme lajitella tämän luettelon tehokkaasti uudelleen lisäyslaji , joka on hyvä lajittelemaan melkein lajiteltuja luetteloita.

Kahdessa ja kolmessa ulottuvuudessa lajittelun ja pyyhkäisyn suorittaminen, kuten edellä on kuvattu, yhden koordinaattiakselin yli vähentää suorien AABB-leikkaustestien lukumäärää, mutta suoritus voi olla parempi yhden koordinaattiakselin yli kuin toinen. Siksi lajittelu- ja pyyhkäisyalgoritmin kehittyneempiä muunnelmia toteutetaan. Hänen kirjassaan Reaaliaikainen törmäystunnistus (sivu 336), Christer Ericson esittelee tehokkaan muunnelman, jossa hän tallentaa kaikki AABB: t yhteen ryhmään, ja jokaiselle lajittelu- ja pyyhkäisyajolle valitaan yksi koordinaatti-akseli ja taulukko lajitellaan min AABB: n arvo valitulla akselilla käyttäen pikalajitelma . Sitten taulukko kulkee ja tehdään AABB-päällekkäisyystestit. Seuraavan lajittelussa käytettävän akselin määrittämiseksi, varianssi AABB: n keskipiste lasketaan ja seuraavaan vaiheeseen valitaan akseli, jolla on suurempi varianssi.

Dynaamiset rajaavat puita

Toinen hyödyllinen alueellinen osiointimenetelmä on dynaaminen rajoittava tilavuuspuu , tunnetaan myös Dbvt . Tämä on eräänlainen rajoittavan äänenvoimakkuuden hierarkia .

Dbvt on binääripuu, jossa jokaisella solmulla on AABB, joka rajoittaa kaikkien lastensa AABB: t. Itse jäykkien kappaleiden AABB: t sijaitsevat lehtisolmuissa. Tyypillisesti Dbvt: tä 'kysytään' antamalla AABB: lle, jolle haluaisimme havaita risteykset. Tämä toiminto on tehokas, koska solmujen lapsia, jotka eivät leikkaa kysyttyä AABB: tä, ei tarvitse testata päällekkäisyyksien varalta. Sellaisena AABB-törmäyskysely alkaa juuresta ja jatkuu rekursiivisesti puun läpi vain AABB-solmuille, jotka leikkaavat kysytyn AABB: n kanssa. Puu voidaan tasapainottaa läpi puiden kierrot , kuten AVL-puu .

Box2D: llä on hienostunut Dbvt: n toteutus b2DynamicTree luokassa . b2BroadPhase luokassa on vastuussa laajan vaiheen suorittamisesta ja käyttää b2DynamicTree -esiintymää suorittaa AABB-kyselyitä.

Kapea vaihe

Videopelien törmäysfysiikan laajan vaiheen jälkeen meillä on joukko jäykkiä kappaleita mahdollisesti törmää. Siksi meidän on selvitettävä jokaiselle parille, kun otetaan huomioon molempien kappaleiden muoto, sijainti ja suuntaus, törmääkö ne itse asiassa; jos ne ovat leikkaavia tai jos niiden etäisyys on pienen toleranssiarvon alapuolella. Meidän on myös tiedettävä, mitkä yhteyspisteet ovat törmäävien elinten välillä, koska sitä tarvitaan törmäysten ratkaisemiseksi myöhemmin.

Kuparit ja koverat muodot

Videopelifysiikan yleissääntönä ei ole triviaali määrittää, leikkaavatko kaksi mielivaltaista muotoa, tai laskea niiden välinen etäisyys. Yksi ominaisuus, jolla on kuitenkin ratkaiseva merkitys sen kovuuden määrittämisessä, on kuperuus muodon. Muotoja voi olla joko kupera tai kovera ja koverien muotojen kanssa on vaikea työskennellä, joten tarvitsemme joitain strategioita niiden käsittelemiseksi.

Kuparissa muodossa viivan segmentti muodon kahden pisteen välillä putoaa aina kokonaan muodon sisään. Koveran (tai 'ei-kuperan') muodon kohdalla sama ei kuitenkaan päde kaikkiin mahdollisiin viivan segmentteihin, jotka yhdistävät muodon pisteet. Jos löydät ainakin yhden viivasegmentin, joka putoaa muodon ulkopuolelle, muoto on kovera.

Laskennallisesti on toivottavaa, että kaikki muodot ovat kuperia simulaatiossa, koska meillä on paljon tehokkaita etäisyyden ja leikkauksen testialgoritmeja, jotka toimivat kuperien muotojen kanssa. Kaikki esineet eivät kuitenkaan ole kuperia, ja yleensä kiertämme niitä kahdella tavalla: kupera runko ja kupera hajoaminen.

kupera runko muodon muoto on pienin kupera muoto, joka sisältää sen kokonaan. Koveran monikulmion ollessa kaksiulotteinen, se olisi kuin lyödä kynsi kumpaankin kärkeen ja kääriä kuminauha kaikkien kynsien ympärille. Laskettaessa kupera runko polygonille tai polyhedrolle tai yleisemmin pistejoukolle, hyvä algoritmi on nopea runko algoritmi, jonka keskimääräinen aikakompleksi on TAI ( n Hirsi n ).

On selvää, että jos käytämme kuperaa runkoa koveran esineen edustamiseen, se menettää koverat ominaisuudet. Ei-toivottu käyttäytyminen, kuten ”haamutörmäykset”, voi ilmetä, koska esineellä on edelleen kovera graafinen esitys. Esimerkiksi autolla on yleensä kovera muoto, ja jos käytämme kuperaa runkoa edustamaan sitä fyysisesti ja laitamme sitten laatikon siihen, laatikko saattaa näyttää kelluvan yllä olevassa tilassa.

Yleensä kuperat rungot ovat usein riittävän hyviä edustamaan koveria esineitä joko siksi, että epärealistiset törmäykset eivät ole kovin havaittavia, tai niiden koverat ominaisuudet eivät ole välttämättömiä simuloidulle. Joissakin tapauksissa saatamme kuitenkin haluta, että kovera esine käyttäytyy kuin kovera muoto fyysisesti. Esimerkiksi, jos käytämme kuperaa runkoa edustamaan kulhoa fyysisesti, emme voi laittaa mitään sen sisälle. Esineet kelluvat vain sen päällä. Tässä tapauksessa voimme käyttää a kupera hajoaminen koveran muodon.

Kuperat hajoamisalgoritmit saavat koveran muodon ja palauttavat joukon kuperia muotoja, joiden liitos on identtinen alkuperäisen koveran muodon kanssa. Joitakin koveria muotoja voi edustaa vain suuri määrä kuperia muotoja, ja niiden laskeminen ja käyttö voi tulla kohtuuttoman kallista. Lähentäminen on kuitenkin usein tarpeeksi hyvä, ja niin, kuten V-HACD tuottaa pieni joukko kuperia polyhedroja koverasta polyhedronista.

Monissa collisons-fysiikan tapauksissa kupera hajoaminen voidaan tehdä taiteilijan käsin. Tämä eliminoi tarpeen verottaa suorituskykyä hajoamisalgoritmeilla. Koska suorituskyky on yksi tärkeimmistä näkökohdista reaaliaikaisissa simulaatioissa, on yleensä hyvä idea luoda hyvin yksinkertaisia ​​fyysisiä esityksiä monimutkaisille graafisille kohteille. Alla olevassa kuvassa näkyy 2D-auton yksi mahdollinen kupera hajoaminen yhdeksällä kuperalla muodolla.

Risteysten testaaminen - erottavan akselin lause

erottava akselilause (SAT) toteaa, että kaksi kuperaa muotoa eivät leikkaa toisinaan ja vain, jos on olemassa ainakin yksi akseli, jossa tällä akselilla olevien muotojen kohtisuorat projektiot eivät leikkaa.

Yleensä on visuaalisesti intuitiivisempaa löytää viiva 2D-muodossa tai taso 3D-muodossa, joka erottaa nämä kaksi muotoa, mikä on käytännössä sama periaate. 2D-linjaa vastaan ​​kohtisuoraa vektoria tai kolmiulotteisen tason normaalivektoria voidaan käyttää ”erotusakselina”.

Pelifysiikkamoottoreilla on useita erilaisia ​​muotoluokkia, kuten ympyrät (pallot 3D: ssä), reunat (yksi linjainen segmentti) ja kuperat polygonit (polyhedrit 3D: ssä). Jokaiselle muototyyppiparille heillä on oma törmäystunnistuksen algoritmi. Yksinkertaisin niistä on todennäköisesti ympyrä-ympyrä-algoritmi:

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; }

Vaikka SAT koskee ympyröitä, on paljon yksinkertaisempaa vain tarkistaa, onko niiden keskipisteiden välinen etäisyys pienempi kuin niiden säteiden summa. Tästä syystä SAT: ta käytetään törmäystunnistusalgoritmissa tietyille muotoluokkapareille, kuten kupera polygoni kuperaa polygonia (tai polyhedronia 3D: ssä) vastaan.

Kaikille muotopareille on ääretön määrä akseleita, joita voimme testata erottamiseksi. Siten testattavan akselin määrittäminen on ensiarvoisen tärkeää tehokkaan SAT-toteutuksen kannalta. Onneksi testattaessa kuperien polygoniparien törmäystä voimme käyttää reunanormaaleja potentiaalisina erotusakseleina. Normaali vektori n on kohtisuorassa reunavektoriin nähden ja osoittaa polygonin ulkopuolelle. Jokaisen polygonin kullekin reunalle meidän on vain selvitettävä, ovatko toisen polygonin kaikki pisteet edessä reunan reunasta.

Jos jokin testi läpäisee - eli jos jommankumman reunan kohdalla toisen polygonin kaikki kärjet ovat edessä monikulmioita ei leikata. Lineaarinen algebra tarjoaa helpon kaavan tälle testille: annetaan ensimmäiselle muodolle reuna, jossa on kärjet että ja b ja kärki v toisella muodolla, jos( v - että ) n on suurempi kuin nolla, sitten kärki on reunan edessä.

Monikulmioissa voimme käyttää kasvojen normaaaleja ja myös kaikkien reunayhdistelmien ristituotetta kustakin muodosta. Se kuulostaa paljon testattavilta asioilta; Nopeuttamiseksi voimme kuitenkin tallentaa välimuistiin viimeisen käyttämämme erotusakselin ja yrittää käyttää sitä uudelleen simulaation seuraavissa vaiheissa. Jos välimuistissa oleva erotusakseli ei enää erota muotoja, voimme etsiä uutta akselia alkaen edellisen pinnan tai reunan viereisistä pinnoista. Se toimii, koska kehot eivät useinkaan liiku tai pyöri paljon vaiheiden välillä.

Box2D testaa SAT: n avulla, leikkaavatko kaksi kuperaa polygonia polygoni-polygoni-törmäystunnistusalgoritmissaan b2CollidePolygon.cpp .

Laskennan etäisyys - Gilbert-Johnson-Keerthi-algoritmi

Monissa törmäysfysiikan tapauksissa haluamme pitää esineitä törmäyksinä paitsi silloin, kun ne todella leikkaavat, myös silloin, kun ne ovat hyvin lähellä toisiaan, mikä vaatii meitä tuntemaan niiden välisen etäisyyden. Gilbert-Johnson-Keerthi (GJK) -algoritmi laskee kahden kuperan muodon ja niiden lähimpien pisteiden välisen etäisyyden. Se on tyylikäs algoritmi, joka toimii kuperien muotojen implisiittisen esityksen kanssa tukitoimintojen, Minkowski-summien ja yksinkertaisuuksien avulla, kuten alla selitetään.

Tukitoiminnot

TO tukitoiminto s TO( d )palauttaa pisteen muodon rajalleTOjolla on suurin projektio vektorissa d . Matemaattisesti sillä on korkein pistetulo d . Tätä kutsutaan a tukipiste , ja tämä toiminto tunnetaan myös nimellä tukea kartoitusta . Geometrisesti tämä piste on muodon pisin piste suuntaan d .

Tukipisteen löytäminen monikulmiosta on suhteellisen helppoa. Vektorin tukipiste d , sinun tarvitsee vain käydä läpi sen kärjet ja löytää se, jolla on korkein pistetuote d , kuten tämä:

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; }

Tukitoiminnon todellinen voima on kuitenkin se, että on helppoa työskennellä muun muassa kartioiden, sylinterien ja ellipsien kanssa. Tällaisten muotojen välistä etäisyyttä on melko vaikea laskea suoraan, ja ilman GJK: n kaltaista algoritmia sinun on yleensä diskretisoitava ne monikulmioon tai monikulmioon, jotta asiat olisivat yksinkertaisempia. Tämä saattaa kuitenkin johtaa uusiin ongelmiin, koska monikulmion pinta ei ole yhtä sileä kuin esimerkiksi pallon pinta, ellei monikulmio ole hyvin yksityiskohtainen, mikä voi johtaa huonoon suorituskykyyn törmäystunnistuksen aikana. Myös muut ei-toivotut sivuvaikutukset voivat ilmetä; esimerkiksi 'monikulmioinen' pallo ei ehkä pyöri sujuvasti.

Jotta saisimme tukipisteen alkuperälle keskitetylle pallolle, meidän on vain normalisoitava d (eli laskea d / || d ||, joka on vektori, jonka pituus on 1 (yksikön pituus) ja joka osoittaa edelleen samaan suuntaan d ) ja kerrotaan sitten pallon säteellä.

Tarkistaa Gino van den Bergenin paperi löytää lisää esimerkkejä sylinterien ja kartioiden tukitoiminnoista muiden muotojen joukossa.

Kohteemme tietysti siirtyvät ja kiertyvät lähtöpaikasta simulaatiotilassa, joten meidän on pystyttävä laskemaan tukipisteet muunnetulle muodolle. Käytämme affinien muutos T ( x ) = R x + c siirtää ja kiertää esineitämme missä c on siirtovektori ja R on kiertomatriisi . Tämä muunnos kiertää ensin kohdetta alkuperän ympäri ja sitten kääntää sen. Muunnetun muodon tukitoimintoTOOn:

Minkowski-summat

Minkowskin summa kahdesta muodostaTOjaBon määritelty seuraavasti:

Tämä tarkoittaa sitä, että laskemme summan kaikille pisteessä oleville pisteilleTOjaB. Tulos on kuin paisuva TOkanssaB.

Samoin määritellään Minkowskin ero kuten:

jonka voimme kirjoittaa myös Minkowskin summanaTOkanssa-B:

KuperaTOjaB,A⊕Bon myös kupera.

Yksi hyödyllinen ominaisuus Minkowski-erossa on, että jos muodot sisältävät tilan alkuperän, muodot leikkaavat, kuten edellisestä kuvasta näkyy. Miksi niin? Koska jos kaksi muotoa leikkaa, niillä on ainakin yksi yhteinen piste, joka sijaitsee samassa paikassa avaruudessa, ja niiden ero on nollavektori, joka on itse asiassa alkuperä.

Toinen mukava piirre Minkowski-erossa on, että jos se ei sisällä alkuperää, alkuperäisen ja Minkowski-erotuksen vähimmäisetäisyys on muotojen välinen etäisyys.

Kahden muodon välinen etäisyys määritellään seuraavasti:

Toisin sanoen etäisyysTOjaBon lyhimmän vektorin pituus, josta lähteeTOettäB. Tämä vektori sisältyyA⊖Bja sen pituus on pienin, mikä on lähinnä alkuperää.

Yleensä ei ole helppoa rakentaa nimenomaisesti kahden muodon Minkowski-summa. Onneksi voimme käyttää tukikartoitusta myös tässä, koska:

Yksinkertaisuudet

GJK-algoritmi etsii iteratiivisesti Minkowski-erotuksen pistettä, joka on lähinnä alkuperää. Se tekee niin rakentamalla sarjan yksinkertaisuudet jotka ovat lähempänä kunkin iteraation alkuperää. Yksinkertainen - tai tarkemmin sanottuna, a k-yksinkertainen kokonaisluvulleettä- on kupera runkok + 1 täysin itsenäinen pistettä k-ulotteisessa tilassa. Toisin sanoen, jos kahden pisteen kohdalla ne eivät saa olla yhteneviä, kolmen pisteen kohdalla niiden ei myöskään saa olla samalla linjalla, ja jos meillä on neljä pistettä, niiden ei myöskään saa olla samassa tasossa. Täten 0-simplex on piste, 1-simplex on viivasegmentti, 2-simplex on kolmio ja 3-simplex on tetraedri. Jos poistamme pisteen yksinkertaisuudesta, vähennämme sen ulottuvuutta yhdellä, ja jos lisäämme pisteen yksinkertaiselle, kasvatamme sen ulottuvuutta yhdellä.

GJK toiminnassa

Laitetaan tämä kaikki yhteen, jotta voimme nähdä, miten GJK toimii. Kahden muodon välisen etäisyyden määrittäminenTOjaB, aloitamme ottamalla heidän Minkowski-eronA⊖B. Etsimme tuloksesta saadusta muodosta lähintä pistettä alkuperälle, koska etäisyys tähän pisteeseen on kahden alkuperäisen muodon välinen etäisyys. Valitsemme jonkin pisteen v sisäänA⊖B, mikä on etäisyyksien arvio. Määritämme myös tyhjän pistejoukonSISÄÄN, joka sisältää nykyisen testin yksinkertaisuuden pisteet.

Sitten syötämme silmukan. Aloitamme hankkimalla tukipisteen sisään = sA⊖B(- v ), kohta päälläA⊖Bjonka projektio v on lähinnä alkuperää.

Jos|| sisään ||ei ole paljon erilainen kuin|| v ||ja niiden välinen kulma ei muuttunut paljoakaan (joidenkin ennalta määritettyjen toleranssien mukaan), se tarkoittaa, että algoritmi on lähentynyt ja voimme palata|| v ||etäisyydeksi.

Muuten lisäämme sisään ettäSISÄÄN. Jos kupera runkoSISÄÄN(eli yksinkertaisuus) sisältää alkuperän, muodot leikkaavat, ja tämä tarkoittaa myös, että olemme valmiit. Muussa tapauksessa löydämme pinnan yksinkertaisuudesta, joka on lähinnä alkuperää, ja sitten nollataan v olla tämä uusi lähin arvio. Lopuksi poistamme kaikki kohdatSISÄÄNjotka eivät edistä lähimmän pisteen laskemista. (Esimerkiksi, jos meillä on kolmio ja lähin kohta alkuperää on sen yhdestä reunasta, voimme poistaa pisteenSISÄÄNse ei ole tämän reunan kärki.) Toistamme sitten nämä samat vaiheet, kunnes algoritmi yhtyy.

Seuraava kuva näyttää esimerkin neljästä GJK-algoritmin iteraatiosta. Sininen esine edustaa Minkowskin eroaA⊖Bja vihreä vektori on v . Näet täältä miten v hioa lähimpään kohtaan alkuperää.

Katso yksityiskohtainen ja perusteellinen kuvaus GJK-algoritmista tutustumalla artikkeliin Nopea ja kestävä GJK-toteutus kuperien objektien törmäystunnistukseen , kirjoittanut Gino van den Bergen. Blogi dyn4j fysiikan moottorilla on myös a loistava viesti GJK: ssa .

Box2D: ssä on GJK-algoritmin toteutus b2Distance.cpp , b2Distance toiminto. Se käyttää GJK: ta vain iskujen laskennan aikana algoritmissaan jatkuvan törmäyksen havaitsemiseen (aiheesta keskustelemme jäljempänä).

Chimpunk-fysiikkamoottori käyttää GJK: ta kaikkeen törmäystunnistukseen, ja sen toteutus on käynnissä cpCollision.c , GJK toiminto. Jos GJK-algoritmi raportoi leikkauspisteen, sen on silti tiedettävä kontaktikohdat ja tunkeutumissyvyys. Tätä varten se käyttää laajenevan polytoopin algoritmia, jota tutkimme seuraavaksi.

Tunkeutumissyvyyden määrittäminen - laajeneva polytooppialgoritmi

Kuten edellä todettiin, jos muodotTOjaBovat leikkaavia, GJK luo yksinkertaisenSISÄÄNjoka sisältää alkuperän Minkowski-eron sisälläA⊖B. Tässä vaiheessa tiedämme vain, että muodot leikkaavat, mutta monien törmäyksenilmaisujärjestelmien suunnittelussa on toivottavaa pystyä laskemaan, kuinka paljon risteyksiä meillä on ja mitä pisteitä voimme käyttää kosketuspisteinä, jotta käsittelemme törmäystä realistisella tavalla. Polytooppialgoritmin laajentaminen (EPA) antaa meille mahdollisuuden saada kyseiset tiedot alkaen siitä, mihin GJK jäi: yksinkertaisella, joka sisältää alkuperän.

tunkeutumissyvyys on pituus pienin käännösvektori (MTV), joka on pienin vektori, jota pitkin voimme kääntää leikkaavan muodon erottaaksemme sen toisesta muodosta.

Kun kaksi muotoa leikkaa toisiaan, niiden Minkowski-ero sisältää alkuperän, ja Minkowski-eron rajalla oleva kohta, joka on lähinnä alkuperää, on MTV. EPA-algoritmi löytää tämän pisteen laajentamalla GJK: n antaman yksinkertaisuuden polygoniksi; jakamalla sen reunat peräkkäin uusilla kärjillä.

Ensinnäkin löydämme yksinkertaista reunaa lähinnä alkuperää ja laskemme tukipisteen Minkowski-erossa suuntaan, joka on normaali reunaan nähden (ts. Kohtisuorassa sitä kohtaan ja osoittaa polygonin ulkopuolelle). Sitten jaetaan tämä reuna lisäämällä tämä tukipiste siihen. Toistamme nämä vaiheet, kunnes vektorin pituus ja suunta eivät muutu paljon. Kun algoritmi on lähentynyt, meillä on MTV ja tunkeutumissyvyys.

Käyttämällä GJK: ta yhdessä EPA: n kanssa saamme yksityiskohtaisen kuvauksen törmäyksestä riippumatta siitä, ovatko kohteet jo leikkaavia vai vain riittävän lähellä, jotta niitä voidaan pitää törmäyksinä.

EPA-algoritmi on kuvattu artikkelissa 3D-peliobjektien läheisyyskyselyt ja tunkeutumissyvyyden laskenta , kirjoittanut myös Gino van den Bergen. Dyn4j-blogissa on myös a viesti EPA: sta .

Jatkuva törmäystunnistus

Tähän mennessä esitetyt videopelifysiikan tekniikat suorittavat törmäystunnistuksen simulaation staattisesta otoksesta. Tätä kutsutaan erillinen törmäystunnistus , ja se jättää huomiotta edellisen ja nykyisen vaiheen välisen tapahtuman. Tästä syystä joitain törmäyksiä ei ehkä havaita, etenkin nopeasti liikkuvien kohteiden kohdalla. Tämä asia tunnetaan nimellä tunnelointi .

Jatkuva törmäystunnistustekniikka yrittää löytää kun kaksi runkoa törmäsi simulaation edellisen ja nykyisen vaiheen välillä. He laskevat vaikutusaika , jotta voimme sitten palata ajassa taaksepäin ja käsitellä törmäystä siinä vaiheessa.

Vaikutusaika (tai kosketusaika) t c on ajanhetki, jolloin kahden ruumiin välinen etäisyys on nolla. Jos voimme kirjoittaa funktion kahden kehon väliselle etäisyydelle pitkin aikaa, haluamme löytää pienimmän juuri tämän toiminnon. Siksi vaikutusten laskennan aika on a juurihakuongelma .

Iskulaskennan ajankohtana tarkastellaan kehon tilaa (asento ja suunta) edellisessä vaiheessa kerrallaan t i -yksija nykyisessä vaiheessa kerrallaan t i . Asioiden yksinkertaistamiseksi oletamme lineaarisen liikkeen vaiheiden välillä.

Yksinkertaistetaan ongelmaa olettaen, että muodot ovat ympyröitä. Kahdelle ympyrälle C yksija C 2, säteellä r yksija r 2, missä niiden massakeskus x yksija x 2samaan aikaan niiden sentroidin kanssa (ts. ne kiertävät luonnollisesti massakeskipisteensä ympäri), voimme kirjoittaa etäisyysfunktion seuraavasti:

Kun otetaan huomioon lineaarinen liike vaiheiden välillä, voimme kirjoittaa seuraavan funktion asemaan C yksialkaen t i -yksiettä t i

Se on lineaarinen interpolointi x yksi( t i -yksi)että x yksi( t i ). Sama voidaan tehdä x 2. Tälle aikavälille voimme kirjoittaa toisen etäisyysfunktion:

Aseta tämä lauseke nollaksi ja saat a asteen yhtälö päällä t . Juuret löytyvät suoraan asteen kaava . Jos ympyrät eivät leikkaa toisiaan, neliöllisellä kaavalla ei ole ratkaisua. Jos he tekevät, se voi johtaa yhteen tai kahteen juureen. Jos sillä on vain yksi juuri, kyseinen arvo on vaikutuksen aika. Jos sillä on kaksi juurta, pienin on vaikutusaika ja toinen on aika, jolloin ympyrät eroavat toisistaan. Huomaa, että iskun aika on luku välillä 0–1. Se ei ole aika sekunneissa; se on vain luku, jolla voimme interpoloida kappaleiden tilan tarkkaan paikkaan, jossa törmäys tapahtui.

Jatkuva törmäystunnistus piireille

Etäisyysfunktion kirjoittaminen muun tyyppisille muodoille on vaikeaa lähinnä siksi, että niiden etäisyys riippuu niiden suunnasta. Tästä syystä käytämme yleensä iteratiivisia algoritmeja, jotka liikuttavat objekteja lähemmäksi ja lähemmäksi kutakin iteraatiota, kunnes ne ovat tarpeeksi lähellä on katsottava törmäykseksi.

konservatiivinen edistyminen algoritmi siirtää kappaleita eteenpäin (ja kiertää niitä) iteratiivisesti. Jokaisessa iteraatiossa se laskee siirtymän ylärajan. Alkuperäinen algoritmi on esitetty Brian Mirtichin väitöskirja (kohta 2.3.2), jossa tarkastellaan kappaleiden ballistista liikettä. Tämä paperi Erwin Coumans (Bullet Physics Engine -lehden kirjoittaja) esittelee yksinkertaisemman version, joka käyttää tasaisia ​​lineaarisia ja kulmanopeuksia.

Algoritmi laskee lähimmät pisteet muotojen välilläTOjaB, piirtää vektorin yhdestä pisteestä toiseen ja projisoi nopeuden tälle vektorille laskemaan ylemmän liikkeen rajat. Se takaa, että yksikään kehon piste ei pääse tämän ulkoneman ulkopuolelle. Sitten se siirtää kehoja eteenpäin tällä määrällä ja toistaa, kunnes etäisyys putoaa pieneen toleranssiarvoon.

Joissakin tapauksissa voi kulua liian monta iteraatiota, esimerkiksi kun toisen kappaleen kulmanopeus on liian suuri.

Törmäysten ratkaiseminen

Kun törmäys on havaittu, on välttämätöntä muuttaa törmäävien esineiden liikkeet realistisella tavalla, esimerkiksi saada ne toipumaan toisistaan. Tämän teorian seuraavassa ja viimeisessä erässä keskustelemme suosituimmista menetelmistä videopelien törmäysten ratkaisemiseksi.

Viitteet

Jos haluat saada syvällisemmän käsityksen törmäysfysiikasta, kuten törmäystunnistuksen algoritmeista ja tekniikoista, kirja Reaaliaikainen törmäystunnistus , on kirjoittanut Christer Ericson.

Koska törmäystunnistus perustuu suurelta osin geometriaan, ApeeScapen artikkeli Laskennallinen geometria Pythonissa: teoriasta sovellukseen on erinomainen johdatus aiheeseen.

Liittyvät: Johdanto robottiohjelmointiin