See on meie kolmeosalise videomängude füüsika sarja III osa. Vaadake selle sarja ülejäänud osa:

I osa: Sissejuhatus jäikusse kehadünaamikasse
II osa: tahkete objektide kokkupõrke tuvastamine

---

Selle sarja I osas nägime, kuidas saab simuleerida jäikade kehade vaba liikumist. II osas nägime, kuidas kokkupõrke- ja läheduskatsete abil keha teadvustada. Siiani pole me aga veel näinud, kuidas panna esemeid üksteisega tõeliselt suhtlema. Näiteks, kuigi me teame, kuidas avastada kokkupõrkeid ja määrata nende kohta palju kasulikku teavet, ei tea me ikkagi, mida teha tegema selle teabega.

Teisisõnu oleme ainult kirjeldanud piiranguteta simulatsioonid . Realistlike ja kindlate objektide simuleerimise viimane etapp on rakendamine piirangud , määratledes jäikade kehade liikumise piirangud. Mõned näited piirangutest on liigesed (näiteks kuulliigendid ja hingede liigendid) ja mittetungimispiirangud . See viimane tüüp on see, millega on harjunud lahendada kokkupõrkeid , jõudes käitumisele, mis takistab kehade läbitungimist ja paneb need hoopis teineteisest realistlikult tagasi põrkama.

Selles artiklis käsitleme videomängude füüsika võrdõiguslikkuse ja ebavõrdsuse piiranguid. Kirjeldame neid kõigepealt jõupõhise lähenemisviisi abil, kus korrigeerivad jõud arvutatakse, ja seejärel impulssipõhise lähenemisviisi abil, kus selle asemel arvutatakse paranduskiirused. Lõpuks vaatame läbi mõned nutikad trikid tarbetu töö välistamiseks ja arvutamise kiirendamiseks.

See osamakse hõlmab rohkem rasket matemaatikat kui I või II osa, nii et hoiatage. Kui peate oma hambakivi hoogustama, minge siin Khani akadeemias . Lineaaralgebra põhialuste ülevaatamiseks võite viidata lisa I osas ja keerukama lineaarse algebra, näiteks maatriksi korrutamine, Khani akadeemia jälle toimetab . Vikipeedias on ka suurepäraseid artikleid kalk ja Lineaaralgebra .

Mis on piirangud?

Piirangud on põhimõtteliselt reeglid, mis peavad simulatsiooni ajal olema täidetud, näiteks 'Nende kahe osakese vaheline kaugus ei tohiks olla suurem kui 2' või 'Need kaks jäiga kehapaari punkti peaksid kogu aeg kokku langema' . Teisisõnu, piirang eemaldub vabadusastmed jäigast kehast. Simulatsiooni igal etapil saame arvutada parandusjõud või impulsid, mis kehadele rakendatuna tõmbavad need kokku või lükkavad üksteisest lahti, nii et nende liikumine on piiratud ja piirangute kehtestatud reeglid jäävad rahuldatuks.

Praktikas määratletakse piirang a-ga käitumisfunktsioon või piirangu funktsioon C , mis võtab parameetritena kehapaari oleku (nt asukoht ja suund) ning väljastab skalaararvu. Kui selle funktsiooni väärtus on vastuvõetavas vahemikus, on piirang täidetud. Seega peame simulatsiooni igas etapis rakendama jäikadele kehadele jõude või impulsse, et proovida hoida C lubatud vahemikus.

Näide: võrdõiguslikkuse piirangud

Levinud piirangute klass on tuntud kui võrdõiguslikkuse piirang . Võrdõiguslikkuse piirang on see, kus ainsana aktsepteeritav väärtus C on null. Seega tahame simulatsiooni igas etapis säilitada C võimalikult nullilähedane. Teisisõnu, me tahame minimeerida C . Võrdsuse piiranguid kasutatakse siis, kui mõne osakese või punkti asukoht peab alati täpselt vastama mõnele etteantud tingimusele. Hea näide on kuulliigend, kus vuugi asukohas peavad alati olema ühendatud kaks jäika keha.

Vaatame lihtsat näidet. Vaatleme osakest kahemõõtmelises asendis lk ( t ) = ( lkx ( t ), lkY ( t )), mis on aja funktsioon, mis annab osakese asukoha korraga t . Aja tuletiste väljendamiseks kasutame punktmärkimist, seega ṗ on tuletis esimest korda lk aja suhtes, mis on osakese kiirus v ( t )ja p̈ on selle teine ​​kordne tuletis ehk kiirendus.

Määratleme piirang. Lase C olema järgmine käitumisfunktsioon:

See funktsioon võtab osakese positsiooni parameetrina ja väljastab selle kauguse alguspunktist miinus l . See on null, kui osakese ja algpunkti vaheline kaugus on l . Seega on selle piirangu tagajärjel osakest fikseeritud kaugusel l päritolust, nagu päritolu külge kinnitatud pendel. Väärtused lk mis rahuldavad C ( lk ) = 0on juriidilised seisukohad osakese.

Selles näites C on ainult kahe muutuja funktsioon, mis väljastab skalaari, nii et saame selle hõlpsalt koostada ja uurida selle mõningaid omadusi. Kui seame piirangu kauguseks 2 (st l = 2), siis graafik C näeb välja selline:

See on tagurpidi koonus. Sinine rõngas sisaldab punkte, kus C = 0, mis on juured C . Seda punktide kogumit tuntakse kui piirang ülipind ja see sisaldab kõiki meie osakese õiguslikke seisukohti. Piirangu ülipind ons-mõõtmeline pind, kusson muutujate arv C .

Rohelised nooled näitavad kalded kohta C , mida hinnatakse hüperpinna ümber, ja näitab juhiseid ebaseaduslikud ametikohad meie osakese kohta, kus C ≠ 0. Kui osake liigub mingil viisil mööda neid jooni, kas positiivses suunas (algusest eemale) või negatiivses suunas (alguse suunas), murrab see piirangu. Seega on jõud, mille me tekitame osakese seaduslikesse asenditesse surumiseks, nende joonte paralleelsed.

Kuigi sellel lihtsal näitel on ainult kaks muutujat, on enamikul piirangufunktsioonidel rohkem ja see muudab nende välimuse kujutamise raskeks. Kuid põhimõte jääb samaks. Igal sammul peame genereerima piirjõud, mis on paralleelsed gradiendiga C hüperpinnal.

Piirangujõudude arvutamine

Tore oleks lihtsalt sättida lk selline, et C on alati täpselt null. Praktikas toob see kaasa ebareaalse käitumise, kuna meie osake hüppab ja väriseb hüperpinna ümber. Hoidma C võimalikult nullilähedane, säilitades samas realistliku käitumise, tuleb kasutada intuitiivset lähenemist jõupõhine dünaamika ja arvutage osakese rakendamiseks vajalik jõud, et see rahuldaks piiranguid Newtoni liikumisseadusi rikkumata.

Piirangujõu arvutamiseks peame mõistma osakese lubatavaid kiirendusi ja kiirusi. Selleks peame hankima tuletised C aja suhtes.

Tahame tagada, et väärtus C jääb nulliga võrdseks ja kogu simulatsiooni vältel muutumatuks. See tähendab, et esimest korda C. , peab olema ka null.

Samamoodi selleks C. jääda fikseeritud nulli, teine ​​tuletis, C̈ , peab olema ka null.

Me ei pea piirama ühtegi täiendavat tuletist C , sest teine ​​tuletis on see, kus rakendatakse meie piirangujõude.

Määratleme need tuletised. Meie praegune mõiste C on ruutjuur ja see muudab eristamise natuke keeruliseks. Saame ümber kirjutada C kasutades ruudukujulisi vahemaid:

See ei muuda seda omadust C on null, kui osakese ja algpunkti vaheline kaugus on l . Sellest saame esimese tuletise C austusega t :

Arvestades lk , kõik kiirused ṗ mis rahuldavad C. ( lk ) = 0on legaalsed kiirused. Selles näites peaksid need olema ainult need kiirused, mis on ülaltoodud pildi hüperpinna suhtes tangentsiaalsed.

Teine tuletis C austusega t on:

Võrdselt, arvestades seaduslikku positsiooni ja kiirust, on kõik kiirendused p̈ mis rahuldavad C̈ ( lk ) = 0on õiguslikud kiirendused. Selles näites peaksid need olema ainult need kiirendused, mis on otseselt päritolu suunas või sellest eemal.

Newtoni teise liikumisseaduse abil saame kiirendust väljendada jõu kujul. Võime arvestada, et osakestel on kaks jõudu: kõigi väliste jõudude kombinatsioon f ext , nagu gravitatsioon, tuul, kasutaja rakendatavad jõud ja piirangujõud f C. Viimane on see, mille tahame kindlaks määrata. Eeldades, et osakesel on mass m , selle kiirendus on:

Asendades selle C̈ = 0saame:

Mida saab ümber korraldada:

Meil on üks võrrand ja kaks tundmatut (kaks koordinaati f C), seega ei saa seda lahendada. Peame kasutusele võtma ühe täiendava tingimuse.

Intuitiivselt teame, et piirangule tuleb rakendada jõudu vastu soovitud suunas ära hoida osakest sisse liikumast. Selles näites osutavad piirangujõud alati raadiusega ringjoone suhtes risti asetsevale suunale l , kuna osakesel pole lubatud sellest ringist väljapoole liikuda. Need perpendikulaarsed jõud suruvad osakese alati ringjoonele, kui ta üritab sellest lahkuda, ja see põhjustab nendes suundades osutava kiiruskomponendi nulli. Seega peavad piiramisjõud olema osakese kiirusega alati risti.

Seetõttu:

Meie piirangu esimese tuletise võrrand ütleb seda lk · ṗ = 0. Kuna f C· ṗ = 0, meil on mõlemad f Cja lk on risti ṗ , ja nii f Cja lk on paralleelsed. Seega võime ühe kirjutada teise korrutisena

Oleme peaaegu kohal! Skalaar λ tähistab rakendatava piirangu jõu suurus süsteemi viimiseks kehtivasse olekusse. Mida kaugemale meie süsteem kehtivatest olekutest eemaldub, seda suurem λ on selleks, et lükata see tagasi kehtivasse olekusse. Sel hetkel λ on meie ainus tundmatu. Asendades ülaltoodu meie eelmisse võrrandisse, saame:

Nüüd saame arvutada λ otse ja hankige f Ckorrutades sellega lk . Siis me lihtsalt kandideerime f Cosakesele ja laske I osas kirjeldatud simulatsioonil teha kõik ülejäänud!

λ on tuntud ka kui Lagrange'i kordaja . Mis tahes piirangu korral hõlmab arvutus jõuvektori suuna ja selle suuruse määramist, λ .

Millal rakendada piirangujõude

Selle näite põhjal näeme, et piirangujõudude arvutamiseks on vaja kõiki teisi jõude f ext on juba teada. Ja loomulikult peame enne saadud liikumise simuleerimist rakendama piirangujõude. Seega näeb iga simulatsioonietapi üldine järjestus välja selline:

1. Arvutage kõik välised jõud f ext .
2. Arvutage piirangujõud f C.
3. Rakendage kõik jõud ja simuleerige liikumist, nagu on kirjeldatud I osas.

Piirangute süsteemid

See oli suhteliselt lihtne näide päris põhipiirangust, mis hõlmas ühte üksust. Tegelikult tahame, et simulatsioonis oleks palju piiranguid ja palju objekte. Piiranguid ei saa käsitleda eraldi, kuna ühe piirangu rakendatavad jõud võivad mõjutada teise piirangu poolt rakendatavaid jõude. See on selgelt nähtav pöörlevate liigenditega ühendatud jäikade kehade ahela näites. Sel põhjusel tuleb piirangud lahendada tervikuna võrrandisüsteemis.

Seadistan

Töötame nüüd vektorite ja maatriksitega, mis sisaldavad meie simulatsioonis kõigi üksuste olekut, ja kasutame neid oma globaalsete võrrandite arendamiseks sarnaselt sellele, mida tegime ühe osakese näite puhul. Arendagem need võrrandid jäikade kehade jaoks kahes mõõtmes.

Riigivektor

Ütle, et meil on n jäigad kehad, mida me simuleerime. Lase mida olema a olekuvektor millel on kõik jäigade kehade asukohad ja nurgad:

kus lk i on kahemõõtmeline vektor, mis tähistab i - jäik kere ja a i on selle nurk, mis on skalaar. Seega mida on3nelemendid.

Dünaamika: Newtoni teine ​​seadus

Lase M olla järgmine3nkõrval3ndiagonaalmaatriks:

kus m i on massi mass i - jäik kere ja Mina i on selle inertsimoment.

Lase F olla globaalne jõuvektor, mis sisaldab igale kehale mõjuvaid jõude ja pöördemomente. See on väliste ja piiravate jõudude summa:

ja:

F on ka 3n elemente, kuna igaüks neist f i on kahemõõtmeline vektor.

Nüüd võime kirjutada Newtoni teise liikumisseaduse kogu kehade komplektile ühe väljendiga:

Piirangud

Lõpuks seadistame oma käitumisfunktsioonid. Ütle, et neid on m piirangud, millest igaüks esindab jäikade kehade ahela lüli. Rühmitame kõik oma käitumisfunktsioonid ühte funktsiooni C ( mida ):

C ( mida )võtab3n-mõõtmeline vektor mida sisendina ja väljundina an m -mõõtmeline vektor. Soovime hoida seda väljundit võimalikult nullvektori lähedal, kasutades sarnast protsessi, mida me tegime eespool.

Me ei hakka siin iga käitumisfunktsiooni määratlema, kuna see pole vajalik, kuid veebis on suurepäraseid õpetusi pöörlevad liigesepiirangud .

Tuletised C Üle aja

Nagu varem, tahame ka esimese ja teise korra tuletisi C olla nullvektorid. Arendame neid võrrandeid.

Tuletis C aja suhtes võib anda järgmiselt:

Pange tähele keti reegli kasutamist. Saame seda võrrandit edasi arendada, määratledes J kui:

See on Jakobi maatriks või Jakobi päritolu C . Jaakobi keel on gradienti üldistus, mis ise on nõlva üldistus. Samuti on huvitav märkida, et iga rida on iga käitumisfunktsiooni gradient. Jaakoblane räägib meile, kuidas iga käitumisfunktsioon reageerib muutustele iga olekumuutuja suhtes.

Meie ahela puhul on see hõre maatriks, sest iga piirang hõlmab ainult kahte jäika keha, mis on selle piiranguga seotud. Kõigi teiste organite seisundil ei ole sellele seosele otsest mõju.

Nüüd saame väljendada aja tuletist C kui:

Ilus.

Teine tuletis C saab:

kus:

Asendades Newtoni teise seaduse väljendit, on meil:

Piirangujõu vektori arvutamine

Me tahame teist tuletist C väärtuseks null, seega seadkem see nulli ja korraldage ümber:

See võrrand on analoogne sellele, mille oleme varem välja töötanud ühe piirangu jaoks:

Jällegi on tundmatute arv suurem kui võrrandite arv ja jällegi võime lahenduse leidmiseks kasutada asjaolu, et piirangujõud on kiiruste suhtes ristkülikud:

Soovime ka esimest tuletist C olla null. Alates C. = 0meil on see:

ja seetõttu saame kirjutada piirangujõu vektori F C kui mitmekordne J :

Vektor λ on m skalaarkomponendid ja selles maatriksi-vektori korrutises iga komponent λ i korrutab rea J (mis on i -th piirangu funktsioon) ja võtab need kokku. See on

F C on seega a lineaarne kombinatsioon rida J , mis on piirangufunktsioonide gradientideks. Ehkki see süsteem on liiga keeruline, et oleks võimalik hüperpinda hõlpsalt visualiseerida, nagu me näitasime osakese näitel, käitub see täpselt samamoodi nagu see näide: gradiendid on piirangute hüperpindade suhtes ortogonaalsed ja suunad, milles süsteem ei tohi liikuda. Seega on see lineaarne kombinatsioon vektoritest, mis osutavad keelatud suundadesse, mis tähendab, et piirangujõud piirduvad nende suundadega ja need suruvad kehad piirangute kehtestatud kehtivate olekute suunas.

Ainus asi, mille lahendamiseks on jäänud, on λ vektor, mis määrab piirangujõudude suurused. Naaseme oma peamise võrrandi juurde ja asendame seal oleva viimase avaldise:

See on lineaarvõrrandite süsteem kus ainult λ ei ole teada. Tuntud on palju meetodid sellise lineaarse süsteemi tõhusaks lahendamiseks. Kui see on lahendatud ja meil on λ , saame arvutada F C , rakendage tulemused jäikadele kehadele ja simuleerige saadud liikumist, nagu on näidatud I osas.

Nende võrrandite üksikasjaliku tuletamise saamiseks vaadake Andrew Witkini raamatut Piiratud dünaamika , osa Füüsiliselt modelleerimine: põhimõtted ja praktika kursus Carnegie Melloni ülikoolis.

Ebavõrdsuse piirangud

Siiani oleme eeldanud, et piirangute täitmiseks peavad meie käitumisfunktsioonid olema kogu aeg võrdsed nulliga. Siiski on teatud tüüpi piiranguid, mis nõuavad teatud paindlikkust, kus parandusjõude ei rakendata suurema väärtuste vahemiku korral C kui lihtsalt null. Näide ühest sellisest piirangust on mittetungimispiirang , mis on jäikade kehasimulatsioonide puhul sageli kõige olulisem piirangutüüp, sest selle eest vastutab kokkupõrke lahendus , tagades, et kaks keha ei tungi kunagi ebareaalselt ja annab neile loomuliku kindla käitumise.

Nagu me kirjeldasime II osas, tuvastab kokkupõrge pärast kokkupõrget GJK algoritm , on kontaktpunktid mõlemal kehal ja kontaktpunktis normaalne pind. Pidage meeles, et GJK on nii kokkupõrkekatse kui ka läheduskatse ning kaht keha võib pidada „põrkumiseks“, isegi kui nad tegelikult ei puutu, kuid nende vaheline kaugus on väga väike. Sel juhul loetakse kahe keha kontaktpunktid punktideks, kus nad asuvad üksteisele kõige lähemal.

Mittetungimispiirang püüab hoida kehasid lahus, rakendades korrigeerivaid jõude, mis suruvad kehad lahku, kuid ainult siis, kui surnukehad põrkuvad .

Vaatleme paari kahemõõtmelist keha TO ja B mis põrkuvad. Kontakti hetkel TO omab positsiooni lk TO ja nurk a TO ja B omab positsiooni lk B ja nurk a B . Helistame r TO vektor, mis läheb keskpunktist TO kontaktpunkti TO ja määratleme ka r B sarnaselt. Lase n olla kontaktnormaalne, mis osutab TO kuni B .

Võtame standardse 2D pöörlemismaatriksi R ( θ )mis pöörleb vektoreid antud nurga all θ :

Me saame seda kasutada vektorite pööramiseks r TO ja r B nurkade järgi a TO ja a B vastavalt. See võimaldab meil määratleda käitumisfunktsiooni, C , nagu:

See käitumisfunktsioon tundub hirmutav, kuid see on lihtne. Kontaktpunkti vahel kulub vektor TO ja kontaktpunkt sisse B , projitseerib selle tavalisele vektorile n ja väljastab selle projektsioonivektori pikkuse. Teisisõnu määrab see läbitungimissügavuse normaalse suunas. Kui C on nullist suurem või sellega võrdne, ei tohiks jõudu rakendada, kuna kehad ei tungi läbi. Seega peame rakendama ebavõrdsus C ≥ 0.

Kui võrrandeid analüüsime, leiame, et peame ainult piirama väärtust λ iga piirangu jaoks. Eelmiste näidete võrdõiguslikkuse piirangutes λ võib võtta mis tahes väärtuse, see tähendab, et piirangujõud võivad olla käitumise gradiendides positiivses või negatiivses suunas). Sellise ebavõrdsuse piirangu korral nagu sissetungimata jätmise piirang on λ peab olema suurem või võrdne nulliga, mis tähistab piirangujõude, mis saavad ainult suruda ära põrkuvad kehad ära üksteiselt.

See muutus muudab meie olemasolevate lineaarvõrrandite süsteemi millekski hoopis teistsuguseks (ja keerulisemaks), mida nimetatakse a-ks Segatud lineaarse vastastikuse täiendavuse probleem või MLCP. Seal on mõned toredad algoritmid, mis suudavad selle probleemi otseselt lahendada, näiteks Lemke algoritm . Kuid jätame siinkohal üksikasjad vahele ja arutame veel üht lähenemist piirangutele, mis on mängufüüsikas väga populaarne.

Impulssipõhine dünaamika

Siiani oleme uurinud jõupõhine lähenemisviis piirangute jõustamisele. Arvutame piirangujõud, rakendame neid jõude kehadele koos väliste jõududega ja integreerime need, kasutades I osas kirjeldatud meetodeid, et simuleerida saadud liikumisi. Siiski on veel üks mängufüüsika mootorite seas väga populaarne tehnika, mis võtab impulssipõhine lähenemine, toimides kehade kiirusel, mitte jõul või kiirendusel. See tähendab, et piirangu lahendaja arvutab ja rakendab kehade lineaarse ja nurkkiiruse otsest muutust, selle asemel, et arvutada ja rakendada parandusjõude ning tugineda kiiruste muutmiseks integreerumisele.

Impulsspõhise dünaamika abil on eesmärk leida impulsid, mille tulemuseks on piirangud lahendavad kiirused. See on mõnevõrra analoogne jõupõhise eesmärgiga leida jõud, mis toovad kaasa kiirendused, mis lahendavad piirangud. Töötame siiski väiksema suurusjärguga ja seetõttu on matemaatika vähem keeruline.

Impulsipõhist lähenemist populariseeris Brian Mirtich aastal tema doktoritöö aastast 1996 , mis on endiselt üks olulisemaid viiteid sellel teemal. Jan Bender jt. juures. on avaldanud ka rea olulised dokumendid sellel teemal .

Impulssipõhist dünaamikat kasutava simulatsioonietapi üldine järjestus erineb mõnevõrra jõupõhiste mootorite omast:

1. Arvutage kõik välised jõud.
2. Rakendage jõud ja määrake saadud kiirused, kasutades I osa tehnikaid.
3. Arvutage piirangu kiirused käitumisfunktsioonide põhjal.
4. Rakendage piirangukiirused ja simuleerige saadud liikumist.

Võib-olla on impulsipõhise dünaamika suurim eelis jõupõhise lähenemise ja teiste ees algoritmide suhteline lihtsus. Samuti on seda intuitiivselt lihtsam mõista. Enamikul juhtudel on see ka arvutuslikult tõhusam, mis muudab selle mängude jaoks atraktiivsemaks, kus reaalajas jõudlus on sageli prioriteet. Siiski on puudusi, mida tuleb arvestada, sealhulgas raskused stabiilsete kontaktide realistlikul käsitsemisel (näiteks puhkepakendis) ja keerukus kontaktide hõõrdumise modelleerimisel. Sellegipoolest saame need probleemid lahendada mitmel viisil, nagu näeme allpool.

Füüsika kõnepruugis an impulss on jõu lahutamatu osa aja suhtes. See on:

See on võrdne muutus sisse hoog selle aja jooksul.

Kui pidev jõud F rakendatakse teatud aja jooksul h , siis on impulss lihtsalt:

Kui kaks jäika objekti kokku põrkavad, püsivad nad kontaktis väga lühikese aja jooksul, mille jooksul nad deformeeruvad ja rakendavad üksteisele võrdseid ja vastupidiseid jõude. Pärast seda lühikest suhtlust võivad nende kiirused olla drastiliselt muutunud ja seetõttu võivad muutuda ka nende hoogud. Kui objektid on täiesti jäigad kehad, on kontaktisoleku aeg lõpmatult nullilähedane ja nende kiirused muutuvad kohe pärast kokkupõrget. Täiuslikult jäigad kehad päriselus ei eksisteeri, kuid lihtsustuse abil saab väga jäikade objektide käitumist realistlikult simuleerida.

Järjestikused impulsid

Meie eesmärk on leida impulsid, mis lahendavad simulatsiooni praeguse ajasammu piirangud. Järjestikused impulsid on tehnika, mille abil saame neid impulsse leida. Selle populariseeris raamatu autor Erin Catto Kast2D füüsika mootor . See on iteratiivne algoritm, kus idee on piiramise kiiruse lihvimine, rakendades impulsse jäikadele kehadele igal iteratsioonil, ja korrata, kuni sellest tulenev kiiruse viga on väga väike või teisisõnu kuni C. on väga nullilähedane.

Järjestikuste impulsside korral ei loo me ühte monoliitset võrrandite ja ebavõrdsuste süsteemi nagu varem. Me tegelikult modelleerime ja lahendame iga piirangut individuaalselt, umbes nii, nagu tegime ühe osakese esimeses näites. Algoritm taandub nendele kolmele etapile:

1. Integreerige rakendatud jõud, kasutades poolimplitsiitset Eulerit nagu I osas, andes esialgsed kiirused. Need kiirused võivad rikkuda piiranguid ja neid tuleb enne rakendamist parandada.

2. Kiiruse vigade parandamiseks rakendage impulsse järjestikku kõigi piirangute jaoks. Korrake mitu kordust, kuni impulsid muutuvad väikeseks või pärast korduste maksimaalse arvu saavutamist.

3. Kasutage uusi kiirusi liikumise simuleerimiseks, positsioonide värskendamiseks, jälle poolimplitsiitse Euleri abil.

Pange tähele, et need etapid vastavad ülalkirjeldatud impulsipõhiste ajaetappide üldise järjestuse etappidele 2 kuni 4.

Kiiruste arvutamine

Uurime võrrandeid. Lase q̇ üks= q̇ ( t i - üks)ja q̇ 2= q̇ ( t i ). See on, q̇ üksja q̇ 2on vastavalt eelmise aja sammu kiirus ja praeguse aja sammu kiirus (mida me tahame määrata). Kasutades poolimplitsiitset Euleri integreerimisskeemi, on esialgne, piiranguteta praeguse etapi kiirus (tähega tähistatud) on:

See kiirus võib rikkuda piiranguid ja sel juhul tuleb seda korrigeerida impulsiga.

Lase P C olla piirangu impulss. Jagades selle massi järgi, saame kiiruse muutuse ja rakendame seda esialgse kiiruse jaoks, et saada soovitud kiirus, mis vastab piirangutele:

Kuidas siis kindlaks teha P C ? Kui mõistame, et impulssi rakendatakse samas suunas kui seda tekitavat hetkelist jõudu, võime jällegi kasutada tõsiasja, et piirangujõud peavad olema paralleelsed käitumisfunktsiooni gradiendiga, täpselt nagu tegime jõu- põhinevad piirangud. Seega võime kirjutada:

kus λ on jällegi suurusjärkude vektor.

Impulssipõhine lähenemine tähistab otseteed, mis möödub Newtoni teisest seadusest. Jättes jõudude arvutamise ja sellest tuleneva kiirenduse vahele, võib see tekitada märgatavaid, hetkelisi kiiruse muutusi, mis võivad simulatsiooni soovimatult närvi ajada. Nende mõjude leevendamiseks on tavaline lisada a eelarvamus kiiruse piirangutele mõjurite pehmendamiseks:

Jälgige seda J q̇ 2+ b = 0aastast q̇ 2peab olema kehtiv kiirus. Seejärel saame kehtiva kiirusvõrrandi asendamise ja ümberkorraldamise abil

Pärast selle võrrandi lahendamist λ saame arvutada piiranguimpulsi kasutades P C = J T λ ja värskendage lõpuks kiirust.

Me peame lahendama kõik piirangud individuaalselt ja rakendama impulsse, ajakohastades kehade kiirusi ja korrates seda sammu mitu korda, kuni on saavutatud lähenemine või maksimaalne korduste arv. See tähendab, et me ise koguneda impulsid, kui me kordame. Ajasammu lõpetamiseks peame lihtsalt asukohti värskendama lõplike kiiruste abil:

Ebavõrdsuse piirangud

Ebavõrdsuse piiramiseks peame impulsid siduma ja hoidma neid kogunemisel lubatud väärtustes, nii et piirangud ei rakendaks impulsse soovimatutes suundades või tugevustes. See piiramisprotseduur pole nii lihtne kui lihtsalt min / max rakendamine funktsiooni, sest me tahame siduda ainult lõpliku kogunenud impulsi, kuid mitte akumuleerimisel tekkivad vahepealsed impulsid. Kontrollige Erin Catto GDC 2009 esitlus üksikasjadeks.

Soe alustamine

Nimetatakse ühte väikest tehnikat, mis parandab oluliselt algoritmi täpsust soe algus . Algoritm algab algse oletusega λ ja töötab sealt ülespoole. Arvestades, et füüsikasimulatsioonil on palju ajalist ja ruumilist sidusust, on loomulik mõelda selle kasutamisele λ leiti eelmises etapis lähtepunktina ja see on soe algus. Kehad ei liigu sageli samm-sammult palju, seega on väga tõenäoline, et impulsid, mille me eelmises etapis arvutasime, on praeguses etapis peaaegu samad. Alustades meie algoritmi sealt, saab see kiiremini täpsema lahenduse poole. See parandab simulatsiooni stabiilsust, eriti selliste piirangute puhul nagu liigesed ja püsiv kontakt kehade vahel.

Prognoositud Gauss-Seidel

Teine impulsipõhiste piirangute lahendamise tehnika tuleb sellest, et seda saab modelleerida ka MLCP-na. Prognoositud Gauss-Seidel (PGS) on iteratiivne algoritm MLCP-de lahendamiseks, mis töötab hästi impulssipõhise dünaamika jaoks. See lahendab sisuliselt lineaarse süsteemi TO x = b , piiridega x . PGS on programmi laiendus Gaussi-Seideli meetod , kus seome väärtuse x igal iteratsioonil, et hoida seda soovitud vahemikus.

Kuna töötame kiiruse kallal, saame kiirenduse kõrvaldada, kirjutades selle ligikaudse arvu kui kiiruse muutuse ja deltaaja suhet praeguse ajaetapi jaoks. Lase q̇ üks= q̇ ( t i - üks)ja q̇ 2= q̇ ( t i ), siis:

kus jälle q̇ ükson eelmises etapis arvutatud kiirus ja q̇ 2on kiirus, mida soovime praeguse sammu jaoks leida. Newtoni teisest seadusest on meil:

Asendades meie lähendust ja F C = J T λ , saame:

Kuna C. = 0, meil on see olemas J q̇ 2= 0 , sest q̇ 2on seaduslik kiirus pärast selle lahendamist. Ümberkorraldamine ja korrutamine J mõlemalt poolt saame:

See MLCP erineb mõnevõrra sellest, mis meil on jõupõhise lähenemise puhul, kuna see kasutab ligikaudset kiirendust. Kui oleme selle PGS-i abil lahendanud, saame hakkama λ , ja siis q̇ 2saab arvutada eelmise võrrandi abil:

Uuendatud positsioonid ja orientatsioonid tulenevad poolimplitsiitsest Euleri skeemist hõlpsalt:

Huvitav on see, et lähedane uurimine näitab, et PGS on samaväärne järjestikuste impulssidega! Me teeme siin sisuliselt sama asja. Sooja algust saab jälle kasutada, võttes λ arvutatakse eelmises etapis lähtepunktina. Erinevus seisneb selles, et järjestikuste impulsside sõnastus on intuitiivsem, kuid PGS-i formulatsioon on üldisem ja võimaldab paindlikumat koodi. Näiteks võime MLCP lahendamiseks katsetada muid tööriistu.

Lisateavet PGS-i kasutamise kohta impulsipõhises simulatsioonis vaadake Erin Catto 2005. aasta GDC ettekanne ja referaat .

Hõõrdumise simuleerimine impulsside abil

The Coulombi hõõrdemudel on lihtne ja töötab kenasti. See määratleb kaks erinevat juhtumit, kui kaks tahket pinda on üksteisega kontaktis:

• Staatiline hõõrdumine : Vastupanu tangentsiaalsele liikumisele, kui pinnad ei liigu üksteise suhtes, sest hõõrdumisest ülesaamiseks pole piisavalt jõudu. Hõõrdejõud osutab netopuutuja jõu vastupidises suunas ja on sellega suurusjärgus võrdne.
• Kineetiline hõõrdumine : Vastupidavus tangentsiaalsele liikumisele, kui pinnad libisevad. Hõõrdejõud osutab liikumise vastassuunas ja on väiksem kui puutuja netojõud.

Hõõrdejõud on proportsionaalne normaaljõuga, mis on netojõu komponent kontaktpinna normaalvektori suunas. Teisisõnu, hõõrdejõud on proportsionaalne jõuga, mis surub kaks objekti üksteise suunas. Seda saab väljendada:

kus F f on hõõrdejõud, F n on normaalne jõud ja μ on hõõrdetegur (mis võib staatilise ja kineetilise hõõrdumise korral olla erinev).

Hõõrdumise simuleerimiseks piirangumudeli abil peame kirjutama kiirusepiirangu otse:

Kus v lk on suhteline kiirusvektor kontaktpunktis lk ja t on pindade puutuja ühikvektor. Tahame viia tangentsiaalkiiruse nulli.

Hõõrdevõrrandi järgi peame piirama hõõrdejõu impulssi väärtuse normaalse impulssi ja hõõrdeteguri korrutisega. See tähendab, et peame hoidma oma λ vahel- μ λ nja μ λ n, kus λ non normaalimpulsi suurus.

Seega on hõõrdumine veel üks näide ebavõrdsuse piiramisest.

Kolmes dimensioonis lähevad asjad natuke keerulisemaks. Tema oma 2005 GDC ettekanne , Erin Catto esitab lähenemisviisi, mis kasutab kahte puutuja vektorit ja paari piirangut. Kuid hõõrdejõu impulssi piiramine normaalimpulssi mitmekordsega ühendab sel juhul need kaks piirangut ja muudab asja raskesti lahendatavaks. Ta töötab selle ümber, piirates seda keha massi ja raskuskiirendusega proportsionaalse konstantse väärtusega.

Optimeerimised

Oleme kirjeldanud mitmeid meetodeid, et määrata kindlaks meie jäikadele kehadele rakendatavad jõud või impulsid, et oma piiranguid jõustada. Mõlemal juhul hõlmavad arvutused parajalt jalatööd. Vaatame nüüd mõnda nutikat optimeerimisstrateegiat, et osa sellest tööst välja lõigata, kui see pole vajalik.

Saared

Piiratud füüsikasimulatsioonis võib täheldada, et mõned objektid mõjutavad teiste liikumist, mõned aga mitte.

Ülaltoodud pildil kast B on staatiline objekt, mis ei liigu. See on põrand. Vasakul asuvad esemed on virnastatud, üksteisega kontaktis. Kui mõni neist üldse liigub, liiguvad potentsiaalselt ka teised, sest nende vahel on kontaktpiirangud. Mis tahes nendele kehadele rakendatav jõud või impulss võib levida teistes kehades. Keskel asuv kolmnurk istub aga lihtsalt üksinda fikseeritud kasti peal B . Vasakul virnastatud objektidele rakendatud jõud ei mõjuta kunagi kolmnurga liikumist, kuna virnastatud objektide ja kolmnurga vahel puudub seos. Sama võib öelda paremal asuva kastiketi kohta. Neid kõiki ühendavad pöörlevad liigesed ja nii võib igaühe liikumine tekitada reaktsiooni mööda piiranguid, mõjutades kõigi teiste keti osaks olevate kastide liikumist. Kuid need ei mõjuta kunagi kolmnurga olekut ega vasakul asuvaid virnastatud objekte, välja arvatud juhul, kui nende vahel luuakse uus piirang, näiteks nende liikumise tõttu tekkiv kontakti / mitte-tungimise piirang, mis põhjustab nende põrkumist teisega objektid.

Selle lihtsa vaatluse põhjal saame need objektid rühmitada sellesse, mida me nimetame saartel , mis on iseseisvad keharühmad, mis võivad piiravate jõudude / impulsside kaudu mõjutada üksteise liikumist rühmas, kuid ei mõjuta ühegi teise saare objektide liikumist.

See eraldamine võimaldab meil lahendada väiksemaid piirangute gruppe, luues kogu füüsikamaailma jaoks ühe suure süsteemi asemel väiksemaid süsteeme. See välistab potentsiaalselt tohutu hulga kasutu töö, mida arvuti peab tegema.

Kui vaatame maailma graafina, kus kehad on sõlmed ja piirangud on servad, saame saared ehitada esimene otsing sellel graafikul. Graafiteoorias on meie saared tuntud kui ühendatud komponendid .

Kast2D teeb seda oma b2World::Solve meetod, mis vastutab kõigi piirangute lahendamise eest samm . See ehitab saared üles ja siis helistab b2Island::Solve igaühel neist. See meetod lahendab selle saare piirangud järjestikuste impulsside abil.

Magamine

Kui keha simulatsiooni ajal puhkama jääb, jääb tema asend loomulikult muutumatuks kõigi simulatsiooni järgnevate etappide jooksul, kuni mingi väline jõud paneb ta uuesti liikuma. See kutsub meie tähelepanu veel ühele võimalikule optimeerimisele: võime peatada antud saare simuleerimise, kui kõigi selle kehade lineaarne ja nurkkiirus jäävad väikese aja jooksul etteantud tolerantsi alla. Seda seisundit nimetatakse magamine .

Pärast saare magama panemist jäetakse selle keha simulatsiooni kõikidest etappidest välja, välja arvatud kokkupõrke tuvastamine. Kui väljaspool saart paiknev keha põrkub selle saare mõne kehaga, „ärkab“ saar üles ja läheb uuesti simulatsiooni. Kui selle kehale rakendatakse mõnda muud välist jõudu või impulssi, siis see ka ärkab.

See on üsna lihtne tehnika, mis võib paljusid objekte sisaldavate simulatsioonide toimimist oluliselt parandada.

Järeldus - videomängude füüsika ja piiratud keha jäik simulatsioon

See lõpetab meie kolmeosalise seeria edasi videomäng Füüsika. Oleme näinud, kuidas füüsikat saab mängudes simuleerida, keskendudes jäigale kehasimulatsioonile, mis on füüsika simulatsiooni alushulk, millest sageli piisab mängude dünaamiliseks ja lõbusaks muutmiseks. Nägime, kuidas saab simuleerida jäikade kehade liikumist, kuidas nende vahelisi kokkupõrkeid tuvastada ja lahendada ning kuidas saab modelleerida muid nendevahelisi interaktsioone.

Nähtud tehnikaid kasutatakse sellistes populaarsetes mängufüüsika mootorites nagu Kast2D , Burundi füüsika ja Kuulifüüsika . Neid meetodeid saab kasutada realistliku ja dünaamilise käitumisega mängude valmistamiseks, kusjuures objektid liiguvad ringi ja põrkuvad kokku. Samuti võimaldavad objektid mitut tüüpi liigeste kaudu üksteisega erineval viisil ühenduda. Võib olla huvitav märkida, et need samad meetodid leiavad rakendusi isegi teistes mänguvälistes valdkondades, näiteks robootika.

Nagu tavaliselt, võivad asjad olla teoreetiliselt ilusad, kuid praktikas osutuvad hoopis teiseks jutuks. Stabiilse ja tõhusa rakenduse saamiseks on vaja palju nutikaid lihtsustusi, eriti piiratud dünaamika osas. Viimase paari aasta jooksul on tehtud palju suuri arenguid kokkupõrgete tuvastamise, löögi arvutamise aja, MLCP eraldusvõime jms osas, kuid siiski on veel palju asju, mida saab parandada. The Kuulifüüsika foorum on hea koht, kus end mängu ja jäiga kehafüüsika simulatsioonimaailmas toimuvaga kursis hoida, eriti Teadus- ja arendusarutelu kokkupõrgete tuvastamise ja füüsikasimulatsiooni teemadel sektsioon, kus liikmed arutavad igasuguseid tänapäevaseid füüsika simulatsioonitehnikaid.