2011-08-14

Kieto kūno(rigid-body) fizikos pagrindai


  Didžioji dalis šiandienos žaidimų ir įvairių simuliatorių neapsieina be fizikos „efektų“. Kai dar 1998m. pasirodė Half-life pirmoji dalis, Quake 3 ir kiti gerai žinomi kultiniai žaidimai apie pilnavertę fizikos simuliaciją galima buvo tik pasvajoti. Tuomet fizikos skaičiavimai buvo naudojami tik būtiniausiose žaidimų vietose – žaidėjų-scenos kolizijų aptikimui-atsakui(collision detection & response), protagonistų judėjimui ir dalelių sistemų simuliacijai(particle physics). Procesorių CPU ir GPU pajėgumams padidėjus su trenksmu ir tam tikra egzotika tokie kūrėjai kaip Havok, Ageia Novodex(dabartinė Nvidia PhysX) pradėjo plėtoti pilnavertes simuliacijos sistemas ir siūlyti savo programinės įrangos plėtotės įrankius(software development kit – SDK) fizikinių sistemų integracijai į kitas programas. Viena iš pirmųjų Havok fizikos sistema sėkmingai buvo panaudota Valve žaidime „Half-life 2” ir padėjo žaidimui pasiekti aukštumas. Iš mėgėjams skirtų priemonių gerai buvo žinoma Tokamak, ODE bei Newton projektai – vis dar naudojami šiandien ir populiarūs. Taip pat atsirado atviro kodo galingų sistemų tokių kaip: Bullet Physics, kuri naudojama žaidimų, filmų pramonėje(pvz. kuriant filmą „2012”), Blender bei kituose modeliavimo ir komerciniuose paketuose kaip Softimage XSI, Cinema 4D. Dviejų dimensijų analogas - Box2D ir kt.


               Šiandien kiekviename žaidime galime pamatyti jau „de facto“ tapusius fizikos simuliacijos efektus – sprogimai, dūžtantys daiktai, vandens, spyruoklių(virvės, laidai), realistiška minkštų kūnų(žėlė, drabužiai) simuliacijas. Kai kurie žaidimai pagrįsti vien tik fizika (pvz: Phun 2D) ir pačios žaidimo taisyklės kyla iš jos dėsnių. Populiariajam išmaniųjų telefonų žaidimui „Angry Birds“ interaktyvumo priduoda būtent ne kas kita kaip 2D fizika. 
                Šiame straipsnelyje nesiimsime toliau gilintis į detales, o pradėsime nagrinėti paprastų fizikos sistemų realizaciją ir kaip ji įgyvendinama kasdieniuose projektuose. Teks prisiminti šiek tiek ir mokyklos fizikos kurso. Bendru atveju, dažnai skiriama ir nagrinėjama tik kieto ir minkšto kūno (rigid-body & soft-body physics) bei dalelių(particle) fizika. Be to, kūnai gali būti tiek statiniai(nejudantys – labai didelė masė ar kt.), tiek dinaminiai. Realizuojant paprastą sistemą – dinaminių veikėjų, mašinų ar kitų objektų judėjimą prireiks ir paprogramuot bei prisiminti vektorinę algebrą – jei primiršot, tai siūlau pakartoti prieš pradedant.

II. Bendroji kūnų judėjimo lygtis - Oilerio integratorius(Euler integrator)

                Fizikoje visi objektai charakterizuojami tam tikrais parametrais(charakteristikomis). Šiuo atveju mus domina - objekto masė, pagreitis, greitis, jėga, kuria objektas yra veikiamas bei koordinatė(pozicija erdvėje/plokštumoje). Visą šią informacija patogu laikyti objekto apibrėžime(struktūroje ar klasėje) vektorių-skaliarų pavidalu, nes parametrų kryptys taip pat svarbios! Taigi objekto apibrėžimas pseudokodu:


struct RigidBody{
                vec position;
                vec velocity;
                vec acceleration;
                vec force;
                float mass;
}


Iš fizikos kurso žinome, kad kūno pozicija vienos koordinatės atžvilgiu kinta pagal tokias lygtis:
čia v(t) – objekto greitis po laiko t, v0 – pradinis objekto greitis, a – objekto pagreitis, x0 – pradinė objekto koordinatė, x(t) – objekto koordinatė po laiko t. Tas pats ir su y bei z koordinate – lygtys tos pačios, tik koordinatė skiriasi. Jei viską išreikšime vektoriškai, tai gausime:
                 Ši universali išraiška tinka bet kokiu atveju – tiek 1D, 2D ar 3D. Žinant pradinius parametrus visada galime rasti objekto parametrus po bet kokio laiko t. Dažnai kvadratinis at2/2 narys yra tiesiog atmetamas, kai simuliuojama su mažu laiko tarpu(žingsniu) t<0.001 ir pan., kadangi jo kvadratas daro ypač mažą įtaką pozicijos pokyčiui. Norint didesnio tikslumo – galima jį įskaityti, toliau mes jį taip pat atmesime. Simuliatoriuje mes norime fizikos procesus vykdyti maždaug taip(pseudokodas):

for every frame do
                physics.update(timeElapsed)
                drawScene()



                t.y. simuliuoti kiekvieną kadrą - atnaujinti fizikos efektus per praėjusi laiką nuo paskutinio atnaujinimo - Dt ir piešti vaizdą į ekraną, po to vėl kartoti tą patį. Galbūt pastebėjote - šis pažingsninis fizikos atnaujinimo būdas yra ne kas kita, kaip – integravimas! Dažniausiai Dt yra pasirenkamas fiksuotas, pvz.: Dt = 1/30s, t.y. 30fps (kadrų per sekundę) greitis ar net 60 fps dėl gaunamo didesnio stabilumo. Kuo žingsnisn mažesnis, tuo stabilumas geresnis – mažesnės paklaidos. Dar geriau, jei fizikos simuliacija “sukasi” atskiroje gijoje(multithreading) fiksuotu dažniu ir nepriklauso nuo kitų programos vykdymo niuansų.
                Simuliuojant natūralius procesus, t.y. Žemėje, vietoj pagreičio a imamas: g = 9,81m/s2, o jei tarkime mėnulyje tai 6 kartus mažiau – tik g = 1.64m/s2, priklausomai nuo kūną veikiančios gravitacijos. Žinoma, jos gali ir nebūti (g = 0) – jei bandoma realizuoti nesvarumo būsena arba tiesiog galima parinkti savo nuožiūra, jei nepasiekiamas norimas efektas.

III. Antras Niutono dėsnis – tiesinis judėjimas (linear motion)

                Galbūt dar prisimenate II Niutono dėsnį, jei ne – ne problema. Dabar kaip tik pakartosime! Taigi II Niutono dėsnis teigia: kūno pagreitis yra tiesiog proporcingas kūną veikiančių jėgų atstojamajai ir atvirkščiai proporcingas jo masei. Štai vektorinė šio dėsnio išraiška:
                Iš šios išraiškos išplaukia, kad pirmiausia kūną turi veikti jėgos(pvz. gravitacija), kad jis įgytų pagreitį. Šiuo dėsniu remiantis mes pagaliau pajudėsime į priekį simuliacijoje! Taigi grįžtant prie fizikos simuliatoriaus update() metodo pseudokodas atrodytu maždaug taip:

for every object do
                object.applyForces()
                object.integrate(elapsedTime)

                Realizuokime objekto jėgų nustatymo metodą applyForces(). Šiame metode visos esamu momentu kūną veikiančios(gravitacija, kiti veikiantys laukai ir pan.) jėgos sudedamos vektoriškai(prieš tai būtina išvalyti). Šiuo atveju imsime, kad kūną veikia tik gravitacinis laukas. Gravitacijos vektoriumi imant vec(0,-9.81,0) pseudokodu gauname:

gravity = vec(0, -9.81, 0)
object.forces = vec(0, 0, 0)
object.forces += gravity * object.mass

Gravitacijos vektorius nukreiptas žemyn(kūnas krenta – priklausomai nuo atskaitos sistemos), todėl atsiranda minusas y koordinatėje. Dabar realizuosime integrate() metodą pseudokodu:

object.acceleration = object.forces / object.mass
object.velocity += object.acceleration * dt
object.position += object.velocity * dt


object.velocity = object.velocity * dampingFactor

                čia dt – integravimo žingsnis(laikas praėjęs nuo paskutinio fizikos atnaujinimo) papildomai turi būti naudojamas slopinimo koeficientas(dampingFactor = 0.99f), kuris simuliuoja sistemoje energijos praradimą, be jo – objektas judėtų nesustodamas.
              Na štai, realizavus šias idėjas gausime paprastą fizikinę sistemą su judančiais dinaminiais objektais. Jei norėsime integruoti didesnį laiko tarpą, tai teks praėjusį laiką išskaidyti į mažesnius laiko tarpus ir integravimą pakartoti n = T/dt kartų, kur T -  praėjęs didelis laiko tarpas, dt – fiksuotas integravimo žingsnio laikas. Taip pat reiktų atkreipti dėmesį, kad jei laiko tarpas labai didelis, o žingsnis labai mažas, tai gali net tekti ilgai laukti, kad to nebūtų – galima pasirinkti maksimalią dar integruojamo laiko ribą, o didesnius laiko už ją intervalus tiesiog atmesti.
                Keletas žodžių apie šį Oilerio integratorių – tai vienas paprastesnių integravimo metodų, kadangi esant dideliems integravimo žingsniams dt gaunama tikrai didelė paklaida ir ji vis didėja. Jei nėra kompensuojama, sistema išsiderina ir nėra stabili. Net staigus greičių pakitimas gali išmušti visą sistemą iš „vėžių“ – objektai gali įgauti didelius greičius ir išsilakstyti(pvz.: simuliuojant spyruokles). Ne dažnai taip pasitaiko, tačiau paprastoms sistemoms, žaidimams puikiai tinka ir yra naudojama labai plačiai, todėl nereikia dėl to labai rūpintis, kol nereikalaujama didelio tikslumo. Apie tikslumą ir kaip jį pagerinti – straipsnelyje ateityje.

IV. Paprastas kolizijų aptikimas ir atsakas (simple collision detection & response)

                Aptikti judančių kūnų kolizijas ir į jas reaguoti – skaičiavimų ir laiko reikalaujantis procesas. Plačiausiai paplitę ir lengviausiai realizuojami objektų tipai: apskritimas(ar sfera), dėžė, cilindras, kapsulė ir plokštuma, tiesė bei jų tarpusavio susidūrimo nustatymo metodai.

                Sudėtingesni modeliai, kaip 3D geometrija yra arba apgaubiami vienu iš minėtų labiausiai tinkančių(priglundančių) objektų(ar jų grupe) arba nagrinėjamos kolizijos su trikampiais. 2D atveju šiek tiek paprasčiau, nes viena ašimi yra mažiau, o visi objektai yra Z=0 plokštumoje. Taigi norint reaguoti į kolizijas fizikos simuliatoriaus update() metodą reiktų papildyti taip(pseudokodas):

for every object do
                object.applyForces()
                object.integrate(elapsedTime)
for every object-other_object pair do
                object.resolveCollision(other_object)

                Toks kolizijų tikrinimo-nustatymo metodas nėra efektyvus O(n2), nes reiktų patikrinti kiekvieną objektą su kiekvienu kitu objektu vieną kartą, tačiau paprastoms ir nesudėtingoms sistemoms su mažai objektų tai tinka. Galimų kolizijų skaičius C nuo fizikinėje sistemoje esančių objektų skaičiaus n auga kvadratu: C = n(n-1)/2. Esant 100 objektų, kiekvieną patikrinti su kiekvienu(bruteforce metodu) reikės 50*99 tikrinimų – išties daug. Tikrinimų skaičiui sumažinti naudojamos spartinimo ir erdvės dalinimo struktūros bei metodai – bet apie jas plačiau kada nors kitą kartą.
Kolizijos aptikimo skaičiavimas(x - atstumas iki tiesės, dR - atstatymo poslinkis, v1 - greičio atspindys)
                Pabaigai pasinaudosime kol kas tuo neefektyviu kolizijų nustatymo metodu paprastam 2D apskritimo ir y=D tiesės susikirtimui rasti bei atsakui. Taigi jei fizikinis kūnas atitinka apskritimo modelį(žinome spindulį R) ir žinome horizontalios tiesės lygtį y=D, tai pirmiausia patikrinsime, ar apskritimas nekerta duotos tiesės(collision detection fazė), jei kerta – atliksime du veiksmus(collision response fazė):

1. Atstatymą - atstatysime apskritimo objektą į neutralią padėtį (kai linijos dar nekirto)
2. Atsaką – atliksime greičio vektoriaus atspindį (paprastesniu invertavimo metodu)
Kolizijos aptikimas, atstatymas(x=R) bei atspindys
Taigi resolveCollision() metodą galime realizuoti pseudokodu taip:

if typeOf(object) is „Circle“ and typeOf(other_object) is „Line“ then
x = other_object.D  - object.position.y
if x < R then // kolizija yra
                dR = R - x
                object.position.y -= dR // atstatymas, kai buvo x
=R
                object.velocity = -object.velocity // v
1 = -v0 atspindys
endif
endif

                Įgyvendinus visa tai kamuoliukas gali šokinėti nuo tiesės remiantis paprastos fizikos žiniomis. Šis atspindžio metodas nėra tikslus ir pats teisingiausias būdas realizuoti kolizijos atsaką(response), bet puikiai tinka nesudėtingiems objektams ir yra lengvai realizuojamas. Apie „tikresnius“ metodus manau bus dar laiko pakalbėti vėliau, o šiam kartui kol kas tiek.

Šokinėjantis kamuoliukas  realizuotame projekte.


Realizuotą projektą su Java Processing galite parsisiųsti iš čia.

Daugiau informacijos:
  1. Ian Millington, Game physics engine development
  2. Grant Palmer, Physics for game developers
  3. David Conger, Physics modelling for game developers

Komentarų nėra:

Rašyti komentarą