Teknologia
Videopelifysiikan opetusohjelma - Osa III: Rajoitettu jäykkä kehon simulointi
Tämä on kolmiosaisen videopelifysiikan sarjan III osa. Katso loput tästä sarjasta:
Osa I: Johdanto jäykkään kehodynamiikkaan
Osa II: Törmäystunnistus kiinteille esineille
Tämän sarjan osassa I näimme kuinka jäykkien kappaleiden vapaata liikettä voidaan simuloida. Osassa II näimme kuinka saada kehot tietoisiksi toisistaan törmäys- ja läheisyystesteillä. Tähän asti emme kuitenkaan ole vielä nähneet, kuinka saada esineet todella vuorovaikutuksessa toistensa kanssa. Vaikka esimerkiksi tiedämme, kuinka törmäykset havaitaan ja määritetään paljon hyödyllistä tietoa niistä, emme silti tiedä mitä tehdä näiden tietojen kanssa.
Toisin sanoen olemme vain kuvanneet rajoittamattomat simulaatiot . Viimeinen askel realististen, kiinteiden esineiden simulointiin on soveltaa rajoituksia , määrittelemällä jäykkien kappaleiden liikkumista koskevat rajoitukset. Joitakin esimerkkejä rajoituksista ovat Liitokset (kuten pallonivelet ja sarananivelet) ja tunkeutumattomuusrajoitukset . Tämä viimeinen tyyppi on tottunut ratkaista törmäyksiä , pakottamalla käyttäytymistä, joka estää ruumiita tunkeutumasta ja saa ne sen sijaan toipumaan toisistaan realistisella tavalla.
Tässä artikkelissa käsitellään videopelifysiikan tasa-arvo- ja eriarvoisuusrajoituksia. Kuvailemme niitä ensin voimaan perustuvalla lähestymistavalla, jossa korjaavat voimat lasketaan, ja sitten impulssipohjaisella lähestymistavalla, jossa korjaavat nopeudet lasketaan sen sijaan. Lopuksi käymme läpi älykkäitä temppuja tarpeettoman työn poistamiseksi ja nopeuttamaan laskentaa.
Tämä erä sisältää enemmän raskaita matematiikoita kuin osa I tai II, joten varoitetaan. Jos sinun on tehostettava kiveäsi, mene täällä Khan-akatemiassa . Voit tarkastella lineaarisen algebran perusteita viittaamalla siihen I osan liite ja monimutkaisemmalle lineaariselle algebralle, kuten matriisikertoimelle, Khan Academy jälleen toimittaa . Wikipediassa on myös upeita artikkeleita kalkki ja lineaarialgebra .
Mitä rajoitteet ovat?
Rajoitukset ovat lähinnä sääntöjä, jotka on täytettävä simulaation aikana, kuten 'Näiden kahden hiukkasen välinen etäisyys ei saa olla suurempi kuin 2' tai 'Näiden kahden jäykän runkoparin pisteiden tulisi olla koko ajan yhtäpitäviä' . Toisin sanoen rajoitus poistuu vapauden asteet jäykästä rungosta. Simulaation jokaisessa vaiheessa voimme laskea korjaavat voimat tai impulssit, jotka kohdistettuina runkoihin vetävät ne yhteen tai työntävät ne erilleen, joten niiden liikkumista rajoitetaan ja rajoitusten asettamat säännöt pysyvät tyydyttävinä.
Käytännössä rajoitus määritellään a: lla käyttäytymistoiminto tai rajoitustoiminto C , joka ottaa runkoparin tilan parametreiksi (esim. sijainti ja suunta) ja antaa skalaariluvun. Kun tämän toiminnon arvo on hyväksyttävällä alueella, rajoitus täyttyy. Täten jokaisessa simulaation vaiheessa meidän on kohdistettava voimia tai impulsseja jäykkiin kappaleisiin yrittääkseen pitää C sallitulla alueella.
Esimerkki: Tasa-arvorajoitukset
Yhteinen rajoitusluokka tunnetaan nimellä tasa-arvoa koskeva rajoitus . Tasa-arvorajoitus on sellainen, jossa ainoa hyväksyttävä arvo C on nolla. Siksi haluamme pitää simulaation jokaisen vaiheen aikana C mahdollisimman lähellä nollaa. Toisin sanoen haluamme minimoida C . Yhtälöllisyysrajoituksia käytetään, kun jonkin hiukkasen tai pisteen sijainnin on aina oltava täsmälleen jonkin ennalta määritellyn ehdon mukainen. Hyvä esimerkki on pallonivel, jossa kahden jäykän rungon on aina oltava kytketty liitoksen kohtaan.
Katsotaanpa yksinkertaista esimerkkiä. Tarkastellaan hiukkasia kahdessa ulottuvuudessa asennon kanssa s ( t ) = ( sx ( t ), sY ( t )), joka on ajan funktio, joka antaa hiukkasen sijainnin kerrallaan t . Käytämme pistemerkintöjä aikajohdannaisten ilmaisemiseen, ṗ on ensimmäisen kerran johdannainen s ajan suhteen, joka on hiukkasen nopeus v ( t )ja p̈ on toisen kerran johdannainen tai kiihtyvyys.
Määritellään rajoitus. Päästää C olla seuraava käyttäytymistoiminto:
Tämä toiminto ottaa hiukkasen sijainnin parametrina ja antaa sen etäisyyden alkuperästä miinus l . Se on nolla aina, kun hiukkasen ja alkuperän välinen etäisyys on l . Siten tämän rajoituksen vaikutuksena on pitää hiukkanen kiinteällä etäisyydellä l alkuperästä, kuten alkuperään kiinnitetty heiluri. Arvot s jotka tyydyttävät C ( s ) = 0ovat oikeudelliset asemat hiukkasesta.
Tässä esimerkissä C on vain kahden muuttujan funktio, joka tuottaa skalaarin, joten voimme piirtää sen helposti ja tutkia joitain sen ominaisuuksia. Jos asetamme rajoitusetäisyydeksi 2 (eli l = 2), sitten kaavio C näyttää tältä:
Se on ylösalaisin kartio. Sininen rengas sisältää kohdat, joissa C = 0, jotka ovat juuret C . Tämä pistejoukko tunnetaan nimellä rajoite ylipinta , ja se sisältää kaikki hiukkasemme oikeudelliset kannat. Rajoituksen hyperpinta ons-mittainen pinta, missäson muuttujien lukumäärä C .
Vihreät nuolet osoittavat kaltevuudet / C , arvioitu hyperpinnan ympärille ja osoittaa suuntaan laiton asema hiukkasemme, missä C ≠ 0. Jos hiukkanen liikkuu näitä linjoja pitkin millään tavalla joko positiiviseen suuntaan (poispäin alkuperästä) tai negatiiviseen suuntaan (kohti alkuperää), se rikkoo rajoituksen. Siten voimat, jotka synnymme työntämään hiukkasen laillisiin paikkoihin, ovat yhdensuuntaiset näiden viivojen kanssa.
Vaikka tässä yksinkertaisessa esimerkissä on vain kaksi muuttujaa, useimmilla rajoitustoiminnoilla on enemmän, mikä tekee siitä vaikea kuvitella miltä ne näyttävät. Mutta periaate pysyy samana. Jokaisessa vaiheessa meidän on tuotava rajoitusvoimat, jotka ovat yhdensuuntaiset gradientin kanssa C hyperpinnalla.
Laskennalliset rajoitusvoimat
Olisi mukavaa yksinkertaisesti asettaa s sellainen C on aina tarkalleen nolla. Käytännössä tämä johtaa epärealistiseen käyttäytymiseen, koska hiukkasemme hyppää ja tärisee hyperpinnan ympäri. Pitää C mahdollisimman lähellä nollaa säilyttäen realistinen käyttäytyminen, on käytettävä intuitiivista lähestymistapaa voimaan perustuva dynamiikka ja laske tarvittava voima hiukkaseen kohdistamiseksi, jotta se tyydyttää rajoitukset rikkomatta Newtonin liikelakeja.
Rajoitusvoiman laskemiseksi meidän on ymmärrettävä hiukkasen sallitut kiihdytykset ja nopeudet. Tätä varten meidän on hankittava johdannaiset C ajan suhteen.
Haluamme varmistaa, että arvo C pysyy yhtä suurena kuin nolla ja pysyy muuttumattomana koko simulaation ajan. Tämä tarkoittaa, että ensimmäistä kertaa johdannainen, C. , on oltava myös nolla.
Samoin, jotta C. pysyä kiinteänä nollassa, toinen johdannainen, C̈ , on myös oltava nolla.
Meidän ei tarvitse rajoittaa muita johdannaisia C , koska toinen johdannainen on paikka, jossa rajoitusvoimiamme käytetään.
Määritetään nämä johdannaiset. Nykyinen määritelmämme C siinä on neliöjuuri, ja se tekee erottamisen hieman vaikeaksi. Voimme kirjoittaa uudelleen C kuitenkin käyttämällä neliömatkoja:
Tämä ei muuta omaisuutta, joka C on nolla, kun hiukkasen ja origon välinen etäisyys on l . Tästä voimme saada ensimmäisen johdannaisen C kunnioittaen t :
Ottaen huomioon s , kaikki nopeudet ṗ jotka tyydyttävät C. ( s ) = 0ovat laillisia nopeuksia. Tässä esimerkissä näiden tulisi olla vain ne nopeudet, jotka ovat tangentiaalisia yllä olevan kuvan hyperpinnalle.
Toinen johdannainen C kunnioittaen t On:
Vastaavasti kaikki kiihdytykset, kun otetaan huomioon oikeudellinen sijainti ja nopeus p̈ jotka tyydyttävät C̈ ( s ) = 0ovat oikeudellisia kiihdytyksiä. Tässä esimerkissä näiden tulisi olla vain sellaisia kiihtyvyyksiä, jotka ovat suoraan kohti alkuperää tai poissa siitä.
Newtonin toisen liikelain avulla voimme ilmaista kiihtyvyyden voimana. Voimme ajatella, että hiukkaselle vaikuttaa kaksi voimaa: kaikkien ulkoisten voimien yhdistelmä f alanumero , kuten painovoima, tuuli, käyttäjän käyttämät voimat ja rajoitusvoima f C. Jälkimmäisen haluamme määrittää. Olettaen, että hiukkasella on massa m , sen kiihtyvyys on:
Korvaa tämä C̈ = 0saamme:
Joka voidaan järjestää uudelleen:
Meillä on yksi yhtälö ja kaksi tuntematonta (kaksi koordinaattia f C), joten sitä ei voida ratkaista. Meidän on esitettävä yksi lisäehto.
Intuitiivisesti tiedämme, että rajoitusvoimaa on sovellettava vastustaa haluamaamme suuntaan estää hiukkasen liikkumasta sisään. Tässä esimerkissä rajoitusvoimat osoittavat aina suuntaan, joka on kohtisuorassa säteen ympyrään nähden. l , koska hiukkasen ei saa liikkua tämän ympyrän ulkopuolella. Nämä kohtisuorat voimat työntävät hiukkasen takaisin pyöreälle polulle aina, kun se yrittää poistua siitä, ja tämä saa näihin suuntiin osoittavan nopeuskomponentin olemaan nolla. Siten rajoitusvoimat ovat aina kohtisuorassa hiukkasen nopeuteen nähden.
Siksi:
Rajoituksen ensimmäisen johdannan yhtälö sanoo sen s · ṗ = 0. Siitä asti kun f C· ṗ = 0, meillä on molemmat f Cja s ovat kohtisuorassa ṗ , ja niin f Cja s ovat yhdensuuntaisia. Täten voimme kirjoittaa yhden toisen kerrannaisina
Olemme melkein siellä! Skalaari λ edustaa sovellettavan rajoitusvoiman suuruus järjestelmän saattamiseksi kelvolliseen tilaan. Mitä pidemmälle järjestelmämme siirtyy pois voimassa olevista tiloista, sitä suurempi λ palauttaa sen kelvolliseen tilaan. Tässä tilanteessa λ on ainoa tuntematon. Korvaamalla yllä oleva edelliseen yhtälöömme saadaan:
Nyt voimme laskea λ suoraan ja hanki f Ckertomalla se s . Sitten yksinkertaisesti haemme f Cja anna osassa I kuvatun simulaation tehdä loput!
λ tunnetaan myös nimellä Lagrange-kerroin . Kaikille rajoituksille laskelma sisältää voimavektorin suunnan ja sen suuruuden määrittämisen, λ .
Milloin rajoitusvoimia käytetään
Tästä esimerkistä voimme nähdä, että rajoitusvoimien laskeminen edellyttää, että kaikki muut voimat f alanumero ovat jo tunnettuja. Ja tietysti meidän on sovellettava rajoitusvoimia ennen kuin tuloksena olevaa liikettä simuloidaan. Siten jokaisen simulointivaiheen yleinen sekvenssi näyttää tältä:
- Laske kaikki ulkoiset voimat f alanumero .
- Laske rajoitusvoimat f C.
- Käytä kaikkia voimia ja simuloi liikettä osassa I kuvatulla tavalla.
Rajoitusten järjestelmät
Se oli suhteellisen yksinkertainen esimerkki melko yksinkertaisesta perusrajoituksesta. Haluamme todella, että simulaatiossamme voi olla monia rajoituksia ja monia esineitä. Rajoituksia ei voida käsitellä erikseen, koska yhden rajoituksen käyttämät voimat voivat vaikuttaa toisen rajoituksen käyttämiin voimiin. Tämä on selvästi nähtävissä esimerkissä jäykkien kappaleiden ketjusta, jotka on yhdistetty pyöröliitoksilla. Tästä syystä rajoitukset on ratkaistava kokonaisuutena yhtälöjärjestelmässä.
Asettaa
Työskentelemme nyt vektorien ja matriisien kanssa, jotka sisältävät simulaatiossamme kaikkien entiteettien tilan, ja käytämme niitä kehittäessämme globaaleja yhtälöitä samalla tavalla kuin mitä teimme yhden hiukkasesimerkin yhteydessä. Kehitetään nämä yhtälöt jäykille kappaleille kahdessa ulottuvuudessa.
Valtion vektori
Sano että meillä on n jäykät kappaleet, joita simuloimme. Päästää mitä olla a tilavektori jolla on kaikki jäykät kappaleiden asennot ja kulmat:
missä s i on kaksiulotteinen vektori, joka edustaa i - jäykkä runko ja a i on sen kulma, joka on skalaari. Täten, mitä on3nelementtejä.
Dynamiikka: Newtonin toinen laki
Päästää M olla seuraava3nmennessä3nlävistäjämatriisi:
missä m i on massan paino i - jäykkä runko ja Minä i on sen hitausmomentti.
Päästää F olla globaali voimavektori, joka sisältää kuhunkin kehoon vaikuttavat voimat ja momentit. Se on ulkoisten ja pakottavien voimien summa:
ja:
F on myös 3n elementtejä, koska kukin f i on kahden ulottuvuuden vektori.
Nyt voimme kirjoittaa Newtonin toisen liikelain kaikille kappaleille yhdellä lausekkeella:
Rajoitukset
Lopuksi määritetään käyttäytymistoimintomme. Sano, että niitä on m rajoitukset, joista kukin edustaa linkkiä jäykkien kappaleiden ketjussa. Aiomme ryhmitellä kaikki toimintatapamme yhteen toimintoon C ( mitä ):
C ( mitä )vie3n-dimensioinen vektori mitä tulona ja lähdöt an m -dimensioinen vektori. Haluamme pitää tämän lähdön mahdollisimman lähellä nollavektoria käyttäen samanlaista prosessia kuin mitä teimme yllä.
Emme aio määritellä kutakin käyttäytymistoimintoa täällä, koska se ei ole välttämätöntä, mutta verkossa on upeita opetusohjelmia pyörivät nivelrajoitukset .
Johdannaiset C Ajan myötä
Kuten aiemmin, haluamme myös ensimmäisen ja toisen kerran johdannaiset C olemaan nollavektoreita. Kehitetään nämä yhtälöt.
Johdannainen C ajan suhteen voidaan antaa seuraavasti:
Huomaa ketjusäännön käyttö. Voimme kehittää tätä yhtälöä edelleen määrittelemällä J kuten:
Tämä on Jakobialainen matriisi , tai Jacobian C . Jaakobin kieli on gradientin yleistys, joka itsessään on kaltevuuden yleistys. On myös mielenkiintoista huomata, että jokainen rivi on kunkin käyttäytymistoiminnon kaltevuus. Jakobilainen kertoo meille, kuinka jokainen käyttäytymistoiminto reagoi muutoksiin jokaisen tilamuuttujan suhteen.
Ketjumme tapauksessa se on harvinainen matriisi, koska jokainen rajoitus koskee vain kahta jäykää runkoa, jotka tämä rajoitus yhdistää. Kaikkien muiden elinten tilalla ei ole suoraa vaikutusta tähän linkkiin.
Voimme nyt ilmaista ajan derivaatin C kuten:
Kaunis.
Toinen johdannainen C tulee olemaan:
missä:
Korvaamalla Newtonin toisen lain ilmaisumme meillä on:
Rajoitusvoimavektorin laskeminen
Haluamme toisen johdannaisen C nollaksi, joten asetetaan se nollaksi ja järjestetään uudelleen:
Tämä yhtälö on analoginen sen kanssa, jonka kehitimme aiemmin yhdelle rajoitukselle:
Jälleen tuntemattomien lukumäärä on suurempi kuin yhtälöiden lukumäärä, ja voimme jälleen käyttää ratkaisun löytämiseen sitä tosiseikkaa, että rajoitusvoimat ovat kohtisuorassa nopeuksiin nähden:
Haluamme myös ensimmäisen johdannaisen C olla nolla. Alkaen C. = 0meillä on se:
ja siksi voimme kirjoittaa rajoitusvoiman vektorin F C moninkertaisena J :
Vektori λ on m skalaarikomponentit, ja tässä matriisi-vektorikertomuksessa kukin komponentti λ i kertoo rivin J (joka on i rajoitusfunktio) ja summataan ne yhteen. Tuo on
F C on siten a lineaarinen yhdistelmä rivistä J , jotka ovat rajoitetoimintojen gradientteja. Vaikka tämä järjestelmä on liian monimutkainen, jotta hyperpintaa voidaan helposti visualisoida, kuten teimme hiukkasesimerkissä, se käyttäytyy samalla tavalla kuin tämä esimerkki: kaltevuudet ovat kohtisuorassa rajoitusten hyperpintoihin nähden ja ne ovat suunnat, joihin järjestelmä ei saa liikkua. Tämä on siis lineaarinen yhdistelmä vektoreita, jotka osoittavat kiellettyihin suuntiin, mikä tarkoittaa, että rajoitusvoimat rajoitetaan näihin suuntiin ja ne työntävät kappaleita kohti rajoitusten asettamia kelvollisia tiloja.
Ainoa asia, joka on jäljellä ratkaistavaksi, on λ vektori, joka määrittää rajoitusvoimien suuruudet. Palataan takaisin pääyhtälöömme ja korvataan siellä oleva viimeinen lauseke:
Tämä on lineaaristen yhtälöiden järjestelmä missä vain λ ei tiedetä. On paljon tunnettuja menetelmiä ratkaista tällainen lineaarinen järjestelmä tehokkaasti. Kun se on ratkaistu ja meillä on λ , voimme laskea F C , käytä tuloksia jäykkiin kappaleisiin ja simuloi tuloksena olevaa liikettä osassa I esitetyllä tavalla.
Katso yksityiskohtainen johdanto näistä yhtälöistä tutustumalla Andrew Witkiniin Rajoitettu dynamiikka , osa Fyysisesti perustuva mallinnus: periaatteet ja käytäntö kurssi Carnegie Mellonin yliopistossa.
Eriarvoisuusrajoitukset
Tähän mennessä olemme olettaneet, että käyttäytymistoimintojemme on oltava aina nollia, jotta rajoitukset voidaan täyttää. On kuitenkin erityyppisiä rajoituksia, jotka vaativat jonkin verran joustavuutta, jolloin korjaavia voimia ei sovelleta laajemmalle C kuin vain nolla. Esimerkki tällaisesta rajoituksesta on tunkeutumattomuutta koskeva rajoitus , joka on usein jäykkien kehon simulaatioiden tärkein rajoitustyyppi, koska se on vastuussa törmäystarkkuus , varmistamalla, että kaksi elintä ei koskaan tunkeudu epärealistisesti, ja antaa heille luonnollisen vankan käyttäytymisen.
Kuten kuvailimme osassa II, törmäys havaitaan törmäyksen jälkeen GJK-algoritmi , meillä on kosketuspisteet molemmissa kappaleissa sekä pinnan normaali kosketuspisteessä. Muista, että GJK on sekä törmäystesti että läheisyystesti ja että kahta kehoa voidaan pitää ”törmäyksinä”, vaikka ne eivät itse asiassa koskettaisikaan, mutta niiden välinen etäisyys on hyvin pieni. Tällöin kahden rungon yhteyspisteitä pidetään pisteinä, joissa ne ovat lähinnä toisiaan.
Tunkeutumattomuutta koskeva rajoite pyrkii pitämään ruumiin erillään soveltamalla korjaavia voimia, jotka työntävät kappaleet toisistaan, mutta vain jos ruumiit törmäävät .
Tarkastellaan 2-ulotteisen kappaleen paria TO ja B jotka törmäävät. Yhteydenoton hetkellä TO on asema s TO ja kulma a TO ja B on asema s B ja kulma a B . Soitetaan r TO vektori, joka kulkee keskuksen TO yhteysviranomaiselle TO ja määritellään myös r B samoin. Päästää n olla kontakti normaali, joka osoittaa TO että B .
Otetaan tavallinen 2D-kiertomatriisi R ( θ )joka kiertää vektoreita tietyllä kulmalla θ :
Voimme käyttää sitä vektorien kiertämiseen r TO ja r B kulmien mukaan a TO ja a B vastaavasti. Tämän avulla voimme määritellä käyttäytymistoiminnon, C , kuten:
Tämä käyttäytymistoiminto näyttää pelottavalta, mutta toiminto on yksinkertaista. Se vie vektorin yhteyspisteen välillä TO ja yhteyspiste päällä B , heijastaa sen normaaliin vektoriin n ja tuottaa tämän projektiovektorin pituuden. Toisin sanoen se määrittää tunkeutumissyvyyden normaalin suuntaan. Jos C on suurempi tai yhtä suuri kuin nolla, voimaa ei tule käyttää, koska kappaleet eivät tunkeudu. Siksi meidän on pantava täytäntöön epätasa-arvo C ≥ 0.
Jos analysoimme yhtälöitä, huomaamme, että meidän on vain rajoitettava yhtälön arvoa λ jokaiselle rajoitukselle. Edellisten esimerkkien tasa-arvorajoituksissa λ voi olla mikä tahansa arvo, mikä tarkoittaa, että rajoitusvoimat voivat olla joko positiivisessa tai negatiivisessa suunnassa käyttäytymisgradienteilla). Eriarvoisuusrajoituksessa, kuten tunkeutumattomuusrajoituksessa, kuitenkin λ on oltava suurempi tai yhtä suuri kuin nolla, mikä edustaa rajoitusvoimia, jotka voivat vain työntää pois törmäävät elimet pois toisiltaan.
Tämä muutos muuttaa meillä olevan lineaaristen yhtälöiden järjestelmän joksikin aivan erilaiseksi (ja monimutkaisemmaksi), jota kutsutaan a: ksi Sekoitettu lineaarinen täydentävyysongelma tai MLCP. On olemassa muutamia hienoja algoritmeja, jotka voivat ratkaista tämän ongelman suoraan, kuten Lemken algoritmi . Ohitamme kuitenkin yksityiskohdat tässä ja keskustelemme toisesta lähestymistavasta rajoitteisiin, joka on erittäin suosittu pelifysiikassa.
Impulssipohjainen dynamiikka
Toistaiseksi olemme tutkineet voimaan perustuva lähestymistapa rajoitusten täytäntöönpanoon. Laskemme rajoitusvoimat, kohdistamme nämä voimat kappaleisiin yhdessä ulkoisten voimien kanssa ja integroimme ne osassa I kuvattujen menetelmien avulla simuloimaan tuloksena olevia liikkeitä. On kuitenkin olemassa toinen tekniikka, joka on erittäin suosittu pelifysiikkamoottoreiden keskuudessa, ja siihen tarvitaan impulssipohjainen lähestymistapa, joka toimii kappaleiden nopeudella eikä voimalla tai kiihtyvyydellä. Tämä tarkoittaa sitä, että rajoitusratkaisija laskee ja soveltaa suoraa muutosta kappaleiden lineaarisessa ja kulmanopeudessa sen sijaan, että laskisi ja käyttäisi korjaavia voimia ja luottaisi integraatioon nopeuksien muuttamiseksi.
Impulssipohjaisen dynamiikan avulla tavoitteena on löytää impulssit, jotka johtavat nopeuksiin, jotka ratkaisevat rajoitukset. Tämä on jonkin verran analogista voimaan perustuvan tavoitteen kanssa löytää voimat, jotka johtavat kiihtymyksiin, jotka ratkaisevat rajoitteet. Työskentelemme kuitenkin pienemmällä suuruusluokalla, minkä seurauksena matematiikka on vähemmän monimutkaista.
Impulssipohjaista lähestymistapaa suositteli Brian Mirtich vuonna väitöskirja vuodelta 1996 , joka on edelleen yksi tärkeimmistä viitteistä aiheesta. Jan Bender et. . ovat myös julkaisseet sarjan tärkeät asiaa koskevat asiakirjat .
Impulssipohjaista dynamiikkaa käyttävän simulointivaiheen yleinen järjestys on jonkin verran erilainen kuin voimapohjaisilla moottoreilla:
- Laske kaikki ulkoiset voimat.
- Käytä voimia ja määritä tuloksena olevat nopeudet osan I tekniikoilla.
- Laske rajoitusnopeudet käyttäytymistoimintojen perusteella.
- Käytä rajoitusnopeuksia ja simuloi tuloksena olevaa liikettä.
Ehkä suurin impulssipohjaisen dynamiikan etu voimaan perustuvaan lähestymistapaan ja muihin verrattuna on algoritmien suhteellinen yksinkertaisuus. Se on myös helpompi ymmärtää intuitiivisesti. Useimmissa tapauksissa se on myös laskennallisesti tehokkaampi, mikä tekee siitä houkuttelevamman peleille, joissa reaaliaikainen suorituskyky on usein etusijalla. Huomioon otettavia haittoja ovat kuitenkin vaikeudet vakaiden koskettimien realistisessa käsittelyssä (kuten lepäävässä laatikkopinossa) ja monimutkaisuus kontaktikitkan mallinnuksessa. Voimme kuitenkin kiertää nämä ongelmat muutamalla tavalla, kuten näemme jäljempänä.
Fysiikan kielellä an impulssi on voiman integraali ajan suhteen. Tuo on:
Tämä on yhtä suuri kuin muutos vauhtia tuona aikana.
Jos jatkuva voima F käytetään tietyn ajan h , impulssi on yksinkertaisesti:
Kun kaksi jäykää esinettä törmäävät, ne pysyvät kosketuksessa hyvin lyhyen ajan, jonka aikana ne muuttuvat ja kohdistavat toisiinsa yhtä suuria ja vastakkaisia voimia. Tämän lyhyen vuorovaikutuksen jälkeen heidän nopeutensa ovat saattaneet muuttua dramaattisesti, ja siten myös heidän liikemääränsä. Jos esineet ovat täysin jäykkiä kappaleita, aika, jonka ne pysyvät kosketuksessa, on äärettömän lähellä nollaa, ja niiden nopeudet muuttuvat heti törmäyksen jälkeen. Täysin jäykkiä kappaleita ei ole todellisessa elämässä, mutta yksinkertaistamista voidaan käyttää realistisesti simuloimaan hyvin jäykkien esineiden käyttäytymistä.
Peräkkäiset impulssit
Tavoitteenamme on löytää impulssit, jotka ratkaisevat rajoitukset simulaation nykyiselle aikavaiheelle. Peräkkäiset impulssit on tekniikka, jota voimme käyttää näiden impulssien löytämiseen. Sen suositteli Erin Catto, Box2D fysiikan moottori . Se on iteratiivinen algoritmi, jossa ajatuksena on hioa rajoitusnopeutta soveltamalla impulsseja jäykkiin kappaleisiin jokaisella iteraatiolla, ja toistaa, kunnes tuloksena oleva nopeusvirhe on hyvin pieni tai toisin sanoen, kunnes C. on hyvin lähellä nollaa.
Peräkkäisissä impulsseissa emme luo yhtä monoliittista yhtälö- ja eriarvoisuusjärjestelmää kuin aiemmin. Me itse asiassa mallinnamme ja ratkaisemme jokaisen rajoitteen erikseen, melkein kuten teimme ensimmäisessä esimerkissä yhdelle hiukkaselle. Algoritmi jakautuu näihin kolmeen vaiheeseen:
-
Integroi käytetyt voimat käyttämällä osittain implisiittistä Euleria kuten osassa I, jolloin saadaan alustavat nopeudet. Nämä nopeudet voivat rikkoa rajoituksia ja ne on korjattava ennen käyttöä.
-
Käytä impulsseja peräkkäin kaikille rajoituksille nopeusvirheiden korjaamiseksi. Toista useita kertoja, kunnes impulssit pienenevät tai kun enimmäismäärä iteraatioita on saavutettu.
-
Käytä uusia nopeuksia simuloimaan liikettä, päivittämällä sijainteja taas käyttämällä puoliimplisiittistä Euleria.
Huomaa, että nämä vaiheet vastaavat yllä kuvatun impulssipohjaisten aikavaiheiden yleisen jakson vaiheita 2-4.
Nopeuksien laskeminen
Tutkitaan yhtälöitä. Päästää q̇ yksi= q̇ ( t i -yksi)ja q̇ 2= q̇ ( t i ). Tuo on, q̇ yksija q̇ 2ovat edellisen aikavaiheen nopeus ja kulloisen aikavaiheen nopeus (jonka haluamme määrittää). Käyttämällä osittain implisiittistä Euler-integraatiojärjestelmää alustava, rajoittamaton nykyisen vaiheen nopeus (merkitty tähdellä) on:
Tämä nopeus voi rikkoa rajoituksia, jolloin se on korjattava impulssilla.
Päästää P C olla rajoitusimpulssi. Jakamalla se massalla saadaan nopeuden muutos ja sovellamme sitä alustavaan nopeuteen saadaksesi halutun nopeuden, joka täyttää rajoitukset:
Joten miten voimme määrittää P C ? Jos tunnistamme, että impulssi kohdistetaan samaan suuntaan kuin sitä tuottava hetkellinen voima, voimme jälleen käyttää sitä tosiasiaa, että rajoitusvoimien on oltava yhdensuuntaiset käyttäytymisfunktion gradientin kanssa, aivan kuten teimme voiman kanssa - perustuvat rajoitteet. Siten voimme kirjoittaa:
missä λ on jälleen suuruusluokan vektori.
Impulssipohjainen lähestymistapa edustaa pikakuvaketta, joka ohittaa Newtonin toisen lain. Ohittamalla voimien ja niistä johtuvien kiihtyvyyksien laskenta voi tuottaa havaittavia, hetkellisiä nopeuden muutoksia, jotka voivat saada simulaation värisemään epätoivottavasti. Näiden vaikutusten lieventämiseksi on tavallista lisätä a puolueellisuus tekijä nopeusrajoituksiin pehmentääkseen vaikutuksia:
Noudata sitä J q̇ 2+ b = 0, siitä asti kun q̇ 2on oltava kelvollinen nopeus. Sitten korvaamalla ja järjestämällä voimassa oleva nopeusyhtälö saadaan
Kun tämä yhtälö on ratkaistu λ voimme laskea rajoitusimpulssin käyttämällä P C = J T λ ja päivitä lopuksi nopeus.
Meidän on ratkaistava jokainen rajoitus erikseen ja sovellettava impulsseja, päivittämällä kehojen nopeudet, ja toistettava sitten tämä vaihe useita kertoja, kunnes konvergenssi saavutetaan tai enimmäismäärä iteraatioita saavutetaan. Se tarkoittaa meitä kerääntyä impulssit iteroimalla. Aikavaiheen loppuun saattamiseksi meidän on vain päivitettävä sijainnit lopullisilla nopeuksilla:
Eriarvoisuusrajoitukset
Eriarvoisuusrajoitusten vuoksi meidän on sidottava impulssit ja pidettävä ne sallituissa arvoissa, kun niitä kerätään, jotta rajoitukset eivät sovella impulsseja ei-toivottuihin suuntiin tai vahvuuksiin. Tämä rajoitusprosessi ei ole niin yksinkertainen kuin vain min / max -sovelluksen käyttäminen toiminto, koska haluamme sitoa vain lopullisen kertyneen impulssin, mutta ei kertymisen aikana syntyvät välipulssit. Tarkista Erin Catton GDC 2009 esitys yksityiskohtia varten.
Lämmin käynnistys
Yksi pieni tekniikka, joka parantaa algoritmin tarkkuutta huomattavasti, kutsutaan lämmin käynnistys . Algoritmi alkaa alkuperäisellä arvailulla λ ja toimii tiensä ylöspäin sieltä. Ottaen huomioon, että fysiikan simulaatiossa on paljon ajallista ja spatiaalista johdonmukaisuutta, on luonnollista ajatella λ löytyi edellisessä vaiheessa lähtökohtana, ja juuri siitä on kyse lämpimästä alkamisesta. Kehot eivät useinkaan liiku paljon askeleelta toiselle, joten on hyvin todennäköistä, että edellisessä vaiheessa laskemamme impulssit ovat melkein samat nykyisessä vaiheessa. Aloittamalla algoritmimme sieltä se lähentyy tarkempaan ratkaisuun nopeammin. Tämä parantaa simulaation vakautta erityisesti rajoitteiden, kuten nivelten ja jatkuvan kosketuksen kappaleiden välillä, suhteen.
Heijastettu Gauss-Seidel
Toinen tekniikka impulssipohjaisten rajoitusten ratkaisemiseksi tulee siitä, että se voidaan mallintaa myös MLCP: nä. Heijastettu Gauss-Seidel (PGS) on iteratiivinen algoritmi MLCP: n ratkaisemiseksi, joka toimii hyvin impulssipohjaiseen dynamiikkaan. Se ratkaisee olennaisesti lineaarisen järjestelmän TO x = b , rajoilla x . PGS on laajennus Gauss-Seidel-menetelmä , johon sidottiin arvon x jokaisella iteraatiolla pitämään se halutulla alueella.
Koska työskentelemme nopeuden suhteen, voimme eliminoida kiihtyvyyden kirjoittamalla likiarvon siitä nopeuden muutoksen ja delta-ajan väliseksi suhteeksi nykyiselle ajanjaksolle. Päästää q̇ yksi= q̇ ( t i -yksi)ja q̇ 2= q̇ ( t i ), sitten:
missä taas q̇ yksion edellisessä vaiheessa laskettu nopeus ja q̇ 2on nopeus, jonka haluamme löytää nykyiselle vaiheelle. Newtonin toisesta laista meillä on:
Korvaa likiarvomme ja F C = J T λ , saamme:
Siitä asti kun C. = 0, meillä on se J q̇ 2= 0 , koska q̇ 2on laillinen nopeus, kun tämä on ratkaistu. Järjestäminen ja kertominen J molemmilta puolilta saamme:
Tämä MLCP on hieman erilainen kuin meillä on voimapohjainen lähestymistapa, koska se käyttää likimääräistä kiihtyvyyttä. Kun olemme ratkaissut sen PGS: n avulla, meillä on λ , ja sitten q̇ 2voidaan laskea käyttämällä edellistä yhtälöä:
Päivitetyt sijainnit ja suuntaukset seuraavat helposti puoliksi implisiittistä Euler-mallia:
Mielenkiintoista on, että tarkka tutkimus paljastaa, että PGS vastaa peräkkäisiä impulsseja! Teemme täällä olennaisesti samaa. Lämmin käynnistys voidaan jälleen käyttää λ lasketaan edellisessä vaiheessa lähtökohtana. Erona on, että peräkkäisten impulssien muotoilu on intuitiivisempaa, mutta PGS-formulaatio on yleisempi ja mahdollistaa joustavamman koodin. Voimme esimerkiksi kokeilla muita työkaluja MLCP: n ratkaisemiseksi.
Katso lisätietoja PGS: n käytöstä impulssipohjaisessa simulaatiossa Erin Catton vuoden 2005 GDC-esitys ja paperi .
Kitkan simulointi impulssien avulla
Coulomb-kitkamalli on yksinkertainen ja toimii hienosti. Se määrittelee kaksi erilaista tapausta, kun kaksi kiinteää pintaa on kosketuksessa toistensa kanssa:
- Staattinen kitka : Vastus tangentiaaliselle liikkeelle, kun pinnat eivät liiku toistensa suhteen, koska kitkaa ei ole riittävästi voiman voittamiseksi. Kitkavoima osoittaa nettotangenttivoiman vastakkaiseen suuntaan ja on yhtä suuri sen suuruuden mukaan.
- Kineettinen kitka : Vastus tangentiaaliselle liikkeelle, kun pinnat liukuvat. Kitkavoima osoittaa vastakkaiseen liikesuuntaan ja on pienempi kuin tangentin nettovoimat.
Kitkavoima on verrannollinen normaalivoimaan, joka on nettovoimakomponentti kosketuspinnan normaalivektorin suunnassa. Toisin sanoen kitkavoima on verrannollinen voimaan, joka työntää kahta kohdetta toisiinsa. Se voidaan ilmaista seuraavasti:
missä F f on kitkavoima, F n on normaali voima ja μ on kitkakerroin (joka voi olla erilainen staattisen ja kineettisen kitkan suhteen).
Kitkan simuloimiseksi rajoitusmallilla joudumme kirjoittamaan nopeusrajoituksen suoraan:
Missä v s on suhteellinen nopeusvektori kosketuspisteessä s ja t on pintojen tangenttiyksikköyksikkö. Haluamme tuoda tangentiaalisen nopeuden nollaan.
Kitkayhtälön mukaan meidän on rajoitettava kitka-impulssin arvo normaaliin impulssiin kertaa kitkakerroin. Tämä tarkoittaa, että meidän on pidettävä omaa λ välillä- μ λ nja μ λ n, missä λ non normaalin impulssin suuruus.
Siten kitka on toinen esimerkki eriarvoisuuden rajoituksesta.
Kolme ulottuvuutta asiat muuttuvat hieman monimutkaisemmiksi. Hänen 2005 GDC-esitys , Erin Catto esittelee lähestymistavan, joka käyttää kahta tangenttivektoria ja paria rajoituksia. Kitkapulssin rajoittaminen normaalin impulssin moninkertaisuudella kuitenkin yhdistää nämä kaksi rajoitusta ja tekee asioista vaikeasti ratkaistavissa. Hän kiertää sen rajoittamalla sen sijaan vakioarvolla, joka on verrannollinen ruumiin massaan ja painovoiman kiihtyvyyteen.
Optimoinnit
Olemme kuvanneet useita menetelmiä jäykkiin kehoihimme kohdistuvien voimien tai impulssien määrittämiseksi rajoitteidemme toteuttamiseksi. Kummassakin tapauksessa laskelmat sisältävät hyvän määrän jalkatyötä. Tarkastellaan nyt älykkäitä optimointistrategioita leikkaamaan osa tästä työstä, kun se ei ole välttämätöntä.
Saaret
Rajoitetussa fysiikan simulaatiossa voidaan havaita, että jotkut esineet vaikuttavat toisten liikkeisiin, kun taas toiset eivät.
Yllä olevassa kuvassa ruutu B on staattinen esine, joka ei liiku. Se on lattia. Vasemmalla olevat esineet on pinottu, kosketuksissa toistensa kanssa. Jos joku heistä liikkuu ollenkaan, mahdollisesti muutkin liikkuvat, koska niiden välillä on kontaktirajoituksia. Mikä tahansa näistä kappaleista kohdistuva voima tai impulssi voi levitä muihin elimiin. Keskellä oleva kolmio istuu kuitenkin yksin yksin kiinteällä laatikolla B . Vasemmalla oleviin pinottuihin esineisiin kohdistetut voimat eivät koskaan vaikuta kolmion liikkeeseen, koska pinottujen esineiden ja kolmion välillä ei ole yhteyttä. Sama voidaan sanoa oikealla olevasta laatikkoketjusta. Ne kaikki on yhdistetty pyörivillä liitoksilla, joten minkä tahansa heistä liike voi tuottaa reaktion rajoituksia pitkin, mikä vaikuttaa kaikkien muiden ketjuun kuuluvien laatikoiden liikkeeseen. Mutta ne eivät koskaan vaikuta kolmion tilaan eikä vasemmalla oleviin pinottuihin esineisiin, ellei niiden välille luoda uutta rajoitusta, kuten kosketuksen / tunkeutumattomuuden rajoitus, joka johtuu niiden liikkeestä, joka saa heidät törmäämään muihin esineitä.
Tämän yksinkertaisen havainnon perusteella voimme ryhmitellä nämä objektit siihen, mitä kutsumme saarilla , jotka ovat itsenäisiä ruumiiryhmiä, jotka voivat vaikuttaa ryhmän toistensa liikkeisiin pakottavien voimien / impulssien avulla, mutta eivät vaikuta mihinkään muuhun saareen kuuluvien esineiden liikkumiseen.
Tämän erottelun avulla voimme ratkaista pienempiä rajoitteiden ryhmiä luomalla pienempiä järjestelmiä yhden suuren järjestelmän sijaan koko fysiikan maailmaan. Tämä eliminoi mahdollisesti valtavan määrän hyödytöntä työtä, joka tietokoneen on tehtävä.
Jos katsomme maailmaa graafina, jossa elimet ovat solmuja ja rajoitteet ovat reunoja, voimme rakentaa saaret käyttämällä syvyyshaku tässä kaaviossa. Graafiteoriassa saartemme tunnetaan nimellä liitetyt komponentit .
Box2D tekee tämän omassa b2World::Solve menetelmä, joka on vastuussa kaikkien rajoitusten ratkaisemisesta kussakin askel . Se rakentaa saaret ja soittaa sitten b2Island::Solve jokaisella heistä. Tämä menetelmä ratkaisee saaren rajoitteet peräkkäisten impulssien avulla.
Nukkumassa
Kun ruumis lepää simulaation aikana, sen sijainti pysyy luonnollisesti muuttumattomana kaikissa simulaation seuraavissa vaiheissa, kunnes jokin ulkoinen voima saa sen liikkumaan uudelleen. Tämä herättää huomiomme toiseen mahdolliseen optimointiin: voimme lopettaa tietyn saaren simuloinnin, kun kaikkien sen kappaleiden lineaariset ja kulmanopeudet pysyvät tietyn toleranssin alapuolella pienen ajan. Tätä tilaa kutsutaan nukkumassa .
Kun saari on nukkunut, sen rungot suljetaan pois kaikista simulaation vaiheista paitsi törmäystunnistuksesta. Jos saaren ulkopuolella oleva elin törmää mihin tahansa tämän saaren kehoon, saari “herää” ja palaa takaisin simulaatioon. Jos johonkin sen kehoon kohdistuu muuta ulkoista voimaa tai impulssia, se myös herää.
Tämä on melko yksinkertainen tekniikka, joka voi parantaa huomattavasti monia esineitä sisältävien simulaatioiden suorituskykyä.
Johtopäätös - Videopelifysiikka ja rajoitettu jäykkä kehon simulointi
Tämä päättää kolmiosaisen sarjamme videopeli fysiikka. Olemme nähneet, kuinka fysiikkaa voidaan simuloida peleissä keskittyen jäykkään kehon simulointiin, joka on fysiikan simulaation perustaso, joka riittää usein tekemään peleistä dynaamisia ja hauskoja. Näimme, kuinka jäykkien kappaleiden liikettä voidaan simuloida, kuinka niiden väliset törmäykset voidaan havaita ja ratkaista ja miten muita niiden välisiä vuorovaikutuksia voidaan mallintaa.
Tekniikoita, joita olemme nähneet, käytetään esimerkiksi suosituissa pelifysiikkamoottoreissa Box2D , Maaoravat fysiikka ja Luodin fysiikka . Näitä menetelmiä voidaan käyttää realistisen, dynaamisen käyttäytymisen omaavien esineiden liikkumisessa ja törmäämisessä. Niiden avulla esineitä voidaan myös yhdistää toisiinsa monin eri tavoin monen tyyppisten nivelten kautta. Voi olla mielenkiintoista huomata, että nämä samat menetelmät löytävät sovelluksia jopa muusta pelaamisen ulkopuolisesta ulottuvuudesta, kuten robotiikasta.
Kuten tavallista, asiat saattavat olla teoriassa kauniita, mutta käytännössä osoittautuvat toisiksi tarinoiksi. Vakaa ja tehokas toteutus vaatii monia älykkäitä yksinkertaistuksia etenkin rajoitetun dynamiikan suhteen. Viime vuosina on tapahtunut paljon suurta kehitystä törmäystunnistuksessa, iskujen laskennassa, MLCP-tarkkuudessa ja niin edelleen, ja silti monia asioita voidaan vielä parantaa. Luodifysiikan foorumi on hyvä paikka pysyä ajan tasalla pelin ja jäykän kehofysiikan simulointimaailman tapahtumista, erityisesti Tutkimus- ja kehityskeskustelu törmäystunnistuksesta ja fysiikan simulaatiosta -osio, jossa jäsenet keskustelevat kaikenlaisista nykyaikaisista fysiikan simulointitekniikoista.
