Share
en begränsning är en begränsning av ett fysiskt modellerat objekt inom en simulering. I allmänhet börjar ett objekt med sex grader av frihet, representerar sin förmåga att röra sig och rotera inom den simulerade världen; Genom att begränsa dessa frihetsgrader på olika sätt kan vi uppnå många intressanta och tilltalande effekter.
När processorn av moderna datorer blir mer och mer kraftfull kan beräkningar sättas mot modellering och lösa många intressanta fysiska scenarier. Begränsningar är ett generaliserat och matematiskt backat sätt att producera sådana scenarier. Vi kan alla tacka Erin Catto för sitt första papper om detta ämne: Iterativ dynamik med Temporal Coherence. Jag kommer att använda det här papperet som en referens vid skrivandet av det här inlägget, så jag föreslår att du åtminstone tar en titt innan du läser vidare, även om det bara är av respekt för Erins arbete (och hans listade resurs fungerar och speciellt tack från var och en av sina bidragsgivare ).
Det finns några olika termer som ofta används när man pratar om fysikmotorer. För tydligheten är här en kort ordlista som kan användas som referens när du läser det här inlägget:
Några förutsättningar krävs för att dra full nytta av denna artikel. Den allmänna läsaren kan dock fortfarande njuta av mycket materialet, men det är bäst att ha en grundläggande förståelse för:
Eftersom en begränsning begränsar grader av frihet, låt oss kolla vad en stel kropp gör när man använder sex på en gång:
Ovanstående styva kropp använder tre grader av frihet för att översätta sig genom världen. De tre sista används för att ständigt ändra orienteringen av alla tre rotationsaxlarna.
Låt oss nu titta på några olika exempel på vilka begränsningar faktiskt är. Den mest kända begränsningen skulle vara en som förhindrar att två styva kroppar penetrerar. Denna typ av begränsning är endast aktiv när två kroppar tränger in i varandra och driver de två kropparna från varandra. När denna interpenetrationsbegränsning är aktiv är det lätt att se att de styva kropparnas frihetsgrader blir begränsade och påverkade på ett sådant sätt att de ger ett intressant resultat (det intressanta resultatet är att de två föremålen kan kollidera med varandra ):
Hallå världen av begränsningar skulle vara distansbegränsning, där två punkter på två styva kroppar är begränsade till att vara ett exakt avstånd från varandra. Man kan föreställa sig en masslös stång som förbinder två punkter ihop, där stången inte kan sträckas eller komprimeras:
Många typer av hinder finns för alla slags intressanta beteenden, inklusive: friktion, prismatisk, revolute, svetsning, vinkel och mer.
I allmänhet är en begränsning en skalär ekvation som är lika med något värde (vanligtvis noll).
\ Begin equation
C (l_1, a_1, l_2, a_2) = 0
\ Label EQ1
\ End equation
\ (L \) och \ (a \) termerna i \ eqref eq1 är min egen notation: \ (l \) avser linjär medan \ (a \) refererar till vinkel-. Tecknen 1 och 2 avser de två objekten inom begränsningen. Som du kan se finns det linjära och vinkliga ingångar till en begränsningsekvation, och varje måste vara ett skalärvärde.
Låt oss ta ett steg tillbaka för att titta på distansbegränsningen. Avståndsbestämmelsen vill köra avståndet mellan två ankarpunkter på två kroppar för att vara lika med ett skalarvärde:
\ Begin equation
C (l_1, a_1, l_2, a_2) = \ frac 1 2 [(P_2 - P_1) ^ 2 - L ^ 2] = 0
\ Label eq2
\ End equation
\ (L \) är stångens längd som förbinder båda kropparna; \ (P_1 \) och \ (P_2 \) är de två kropparnas positioner.
I sin nuvarande form är denna begränsning en positioneringsposition. Denna typ av positionsekvation är icke-linjär, vilket gör att det är mycket svårt att lösa det. En metod att lösa denna ekvation kan vara att istället härleda positionsbegränsningen (med avseende på tiden) och använda en hastighetsbegränsning. Resulterande hastighetsekvationer är linjära, vilket gör dem lösliga. Lösningar kan sedan integreras med någon form av integrator tillbaka i positionsform.
I allmänhet är en hastighetsbegränsning av formen:
\ Begin equation
\ dot C (l_1, a_1, l_2, a_2) = 0
\ Label EQ3
\ End equation
Under derivatet visas en ny term \ (J \) via kedjeregeln:
\ Begin equation
\ dot C (l_1, a_1, l_2, a_2) = JV = 0
\ Label EQ4
\ End equation
Tidderivatet av \ (C \) skapar en hastighetsvektor och en Jacobian. Jacobianen är en 1x6-matris som innehåller skalärvärden som motsvarar varje grad av frihet. I en parvis begränsning innehåller en Jacobian typiskt 12 element (tillräckligt för att innehålla \ (l \) och \ (a \) termerna för både kroppar \ (A \) och \ (B \).
Ett system av begränsningar kan bilda en gemensam. En gemensam kan innehålla många begränsningar som begränsar graden av frihet på olika sätt. I detta fall kommer Jacobian att vara en matris där antalet rader är lika med antalet begränsningar som är aktiva i systemet.
Jacobianen är härledd offline, för hand. När en Jacobian har förvärvats, kodar för att beräkna och använda Jacobian kan skapas. Som du kan se från \ eqref eq4, omvandlas hastigheten \ (V \) från kartesiska rymden till att begränsa rymden. Detta är viktigt eftersom ursprung i känt utrymme är känt. Faktum är att varje mål kan vara känt. Detta innebär att eventuella hinder kan härledas för att ge en Jacobian som kan förvandla krafter från kartesiska rymden för att begränsa rymden.
I begränsningsutrymmet, med en målskalär, kan ekvationen flytta antingen mot eller bort från målet. Lösningar kan enkelt erhållas i begränsningsutrymme för att flytta det aktuella tillståndet av en styv kropp mot ett målläge. Dessa lösningar kan sedan omvandlas ur begränsningsutrymme tillbaka till kartesiska rymden som så:
\ Begin equation
F = \ lambda J ^ T
\ Label EQ5
\ End equation
\ (F \) är en kraft i kartesiskt utrymme, där \ (J ^ T \) är den inverse (transponerade) Jacobianen. \ (\ lambda \) (lambda) är en skalär multiplikator.
Tänk på Jacobian som en hastighetsvektor, där varje rad är en vektor i sig (av två skalärvärden i 2D och tre skalärvärden i 3D):
\ Begin equation
J = \ start bmatrix
l_1 \\
a_1 \\
l_2 \\
a_2 \\
\ End bmatrix
\ Label EQ6
\ End equation
Att multiplicera \ (V \) av \ (J \) matematiskt skulle involvera matrismultiplicering. De flesta element är dock noll, och det är därför vi behandlar Jacobian som en vektor. Detta gör det möjligt för oss att definiera vår egen operation för beräkning \ (JV \), som i \ eqref eq4.
\ Begin equation
JV = \ start bmatrix
l_1 & a_1 & l_2 & a_2
\ End bmatrix
\ Begin bmatrix
v_1 \\
ω_1 \\
v_2 \\
ω_2 \\
\ End bmatrix
\ Label EQ7
\ End equation
Här representerar \ (v \) linjär hastighet, och \ (ω \) (omega) representerar vinkelhastighet. \ eqref eq7 kan skrivas ner som några prickprodukter och multiplikationer för att ge en effektivare beräkning jämfört med fullmatrismatrisering:
\ Begin equation
JV = l_1 \ cdot v_1 + a_1 \ cdot ω_1 + l_2 \ cdot v_2 + a_2 \ cdot ω_2
\ Label EQ8
\ End equation
Jacobianen kan betraktas som en riktningsvektor i begränsningsutrymme. Denna riktning pekar alltid mot målet i den riktning som kräver det minsta arbetet att göra. Eftersom denna "riktning" Jacobian är härledd offline, är allt som behöver lösas för kraftens storlek som ska tillämpas för att upprätthålla begränsningen. Denna storlek kallas \ (\ lambda \). \ (\ lambda \) kan kallas Lagrange Multiplikatorn. Jag har inte formellt studerat Lagrangian Mechanics, men en studie av Lagrangian Mechanics är inte nödvändig för att helt enkelt genomföra begränsningar. (Jag är bevis på det!) \ (\ Lambda \) kan lösas med hjälp av a begränsningslösare (mer om detta senare).
I Erin Cattos papper finns det en enkel skiss för handledande Jacobians. Stegen är:
Den enda svåra delen är att beräkna derivatet, och detta kan komma med övning. I allmänhet är handledningsbegränsningar svåra, men blir lättare med tiden.
Låt oss härleda en giltig Jacobian för användning vid lösning av distansbegränsning. Vi kan börja i steg 1 med \ eqref eq2. Här är några detaljer för steg 2:
\ Begin equation
\ dot C = (P_2 - P_1) (\ punkt P _2 - \ punkt P _1)
\ Label eq9
\ End equation
\ Begin equation
\ dot C = (P_2 - P_1) ((v_2 + ω_2 \ gånger r_2) - (v_1 + ω_1 \ tider r_1))
\ Label EQ10
\ End equation
\ (r_1 \) och \ (r_2 \) är vektorer från massans centrum till ankarpunkten, för respektive kropps 1 respektive 2.
Nästa steg är att isolera hastighetsvillkoren. För att göra detta ska vi utnyttja den skalära trippelproduktidentiteten:
\ Begin equation
(P_2 - P_1) = d
\ Label EQ11
\ End equation
\ Begin equation
\ dot C = (d \ cdot v_2 + d \ cdot ω_2 \ gånger r_2) - (d \ cdot v_1 + d \ cdot ω_1 \ tider r_1)
\ Label eq12
\ End equation
\ Begin equation
\ dot C = (d \ cdot v_2 + ω_2 \ cdot r_2 \ gånger d) - (d \ cdot v_1 + ω_1 \ cdot r_1 \ gånger d)
\ Label eq13
\ End equation
Det sista steget är att identifiera Jacobianen genom inspektion. För att göra detta kommer alla koefficienterna för alla hastighetsvillkor (\ (V \) och \ (ω \)) att användas som Jacobian-elementen. Därför:
\ Begin equation
J = \ start bmatrix -d & -r_1 \ gånger d & d & r_2 \ times d \ end bmatrix
\ Label eq14
\ End equation
Kontaktbegränsning (interpenetrationsbegränsning), där \ (n \) är kontaktnormal:
\ Begin equation
J = \ start bmatrix -n & -r_1 \ times n & n & r_2 \ times n \ end bmatrix
\ Label eq15
\ End equation
Friktionsbegränsning (aktiv vid penetration), där \ (t \) är en friktionsaxel (2D har en axel, 3D har två):
\ Begin equation
J = \ start bmatrix -t & -r_1 \ gånger t & t & r_2 \ times t \ end bmatrix
\ Label eq16
\ End equation
Nu när vi har förståelse för vad en begränsning är, kan vi prata om hur man löser dem. Som sagt tidigare, när en Jacobian är hand-härledd, behöver vi bara lösa för \ (\ lambda \). Att lösa ett enda hinder i isolering är lätt, men att lösa många hinder samtidigt är svårt och mycket ineffektivt (beräkningsmässigt). Detta utgör ett problem, eftersom spel och simuleringar sannolikt vill ha många begränsningar aktiva samtidigt.
En alternativ metod för att lösa alla hinder samtidigt (globalt lösa) skulle vara att lösa begränsningarna iterativt. Genom att lösa för approximationer av lösningen och matning i tidigare lösningar till ekvationerna kan vi konvergera på lösningen.
En sådan iterativ lösare är känd som sekventiella impulser, som dubblats av Erin Catto. Sekventiella impulser liknar mycket Projicerad Gauss Seidel. Tanken är att lösa alla begränsningar, en i taget, flera gånger. Lösningarna kommer att ogiltiggöra varandra, men över många iterationer kommer varje enskild begränsning att konvergeras och en global lösning kan uppnås. Det här är bra! Iterativa lösningsmedel är snabba.
När en lösning uppnåtts kan en impuls appliceras på båda kropparna i begränsningen för att upprätthålla begränsningen.
För att lösa en enda begränsning kan vi använda följande ekvation:
\ Begin equation
\ lambda = \ frac - (JV + b) JM ^ - 1 J ^ T
\ Label eq17
\ End equation
\ (M ^ - 1 \) är massan av begränsningen; \ (b \) är bias (mer om detta senare).
Detta är en matris som innehåller inversmassan och invers inerti hos båda styva kroppen i begränsningen. Följande är massan av begränsningen; notera att \ (m ^ - 1 \) är den inversa massan av en kropp, medan \ (I ^ - 1 \) är en invers inerti:
\ begin ekvation M ^ - 1 =
\ Begin bmatrix
m_1 ^ - 1 & 0 & 0 & 0 \\
0 & I_1 ^ - 1 & 0 & 0 \\
0 & 0 & m_2 ^ - 1 & 0 \\
0 & 0 & 0 & I_2 ^ - 1
\ End bmatrix
\ Label eq18
\ End equation
Även om \ (M ^ - 1 \) är teoretiskt en matris, var vänlig modellera den inte som sådan (det mesta är nollor!). Istället var smart om vilken typ av beräkningar du gör.
\ (JM ^ - 1 J ^ T \) är känd som begränsningsmassa. Denna term beräknas en gång och används för att lösa för \ (\ lambda \). Vi beräknar det för ett system som så:
\ Begin equation
JM ^ - 1 J ^ T = (l_1 \ cdot l_1) * m_1 ^ - 1 + (l_2 \ cdot l_2) * m_2 ^ - 1 + a_1 * (I_1 ^ - 1 a_1) + a_2 * (I_2 ^ - 1 a_2)
\ Label eq19
\ End equation
Observera att du måste invertera \ eqref eq19 för att beräkna \ eqref eq17.
Ovanstående information är allt som behövs för att lösa en begränsning! En kraft i kartesisk rymd kan lösas för och används för att uppdatera hastigheten hos ett objekt, för att upprätthålla en begränsning. Vänligen återkalla \ eqref eq5:
\ Begin equation
F = \ lambda J ^ T \\
V_ final = V_ initial + m ^ - 1 * F \\
∴ \\
\ Begin bmatrix
v_1 \\
ω_1 \\
v_2 \\
ω_2 \\
\ end bmatrix + = \ start bmatrix
m_1 ^ - 1 & 0 & 0 & 0 \\
0 & I_1 ^ - 1 & 0 & 0 \\
0 & 0 & m_2 ^ - 1 & 0 \\
0 & 0 & 0 & I_2 ^ - 1
\ End bmatrix \ begin bmatrix
\ lambda * l_1 \\
\ lambda * a_1 \\
\ lambda * l_2 \\
\ lambda * a_2 \\
\ End bmatrix
\ Label EQ20
\ End equation
På grund av linjärisering av de icke-linjära positionekvationerna förloras viss information. Detta resulterar i lösningar som inte helt uppfyller den ursprungliga positionsekvationen, men uppfyller hastighetsekvationerna. Detta fel är känt som begränsningsdrift. Man kan tänka på detta fel som ett resultat av en tangentlinje approximation.
Det finns några olika sätt att lösa sådana fel, som alla approximerar felet och tillämpar någon form av korrigering. Den enklaste är känd som Baumgarte.
Baumgarte är ett litet tillskott av energi i begränsningsutrymmet och står för \ (b \) termen i de tidigare ekvationerna. För att ta hänsyn till förskjutning, här är en modifierad version av \ eqref eq4:
\ Begin equation
\ dot C = JV + b = 0
\ Label eq21
\ End equation
För att beräkna en Baumgarte term och tillämpa den som en bias måste vi inspektera den ursprungliga begränsningsekvationen och identifiera en lämplig metod för beräkning av fel. Baumgarte finns i formen:
\ Begin equation
JV = - \ beta C
\ Label eq22
\ End equation
\ (\ beta \) (Baumgarte termen) är en avstämningsbar, unit-less, simuleringsberoende faktor. Det är vanligtvis mellan 0,1 och 0,3.
För att beräkna bias termen, låt oss titta på ekvationen för icke-penetreringsbegränsningen \ eqref eq15 innan den härledas med avseende på tiden, där \ (n \) är kontaktnormalen:
\ Begin equation
C = \ start bmatrix -x_1 & -r_1 & x_2 & r_2 \ end bmatrix \ cdot \ vec n
\ Label eq23
\ End equation
Ovannämnda ekvation säger att scalarfelet av \ (C \) är interpenetrationsdjupet mellan två styva kroppar.
Tack vare Erin Catto och hans papper om begränsningslösning har vi ett sätt att lösa positionsbegränsningar i form av hastighet. Många intressanta beteenden kan uppstå ur begränsningar, och förhoppningsvis kommer artikeln att vara till nytta för många människor. Som alltid är du välkommen att ställa frågor eller ge kommentarer nedan.
Vänligen se Box2D Lite för en resurs för att lösa olika typer av 2D-begränsningar, samt inblick i många implementeringsspecifikationer som inte omfattas här.
Accentsconagua