Share
EEN beperking is een beperking op een fysiek gemodelleerd object binnen een simulatie. Over het algemeen begint een object met zes graden van vrijheid, het vertegenwoordigen van zijn vermogen om rond te bewegen en te roteren binnen de gesimuleerde wereld; door deze vrijheidsgraden op verschillende manieren te beperken, kunnen we veel interessante en aansprekende effecten bereiken.
Naarmate de CPU van moderne computers steeds krachtiger wordt, kunnen er berekeningen worden gemaakt voor het modelleren en oplossen van vele interessante fysieke scenario's. Beperkingen zijn een gegeneraliseerde en wiskundig gesteunde manier om dergelijke scenario's te produceren. We kunnen allemaal Erin Catto bedanken voor zijn eerste paper over dit onderwerp: Iteratieve Dynamica met Temporele Coherentie. Ik zal dit artikel als referentie gebruiken bij het schrijven van dit bericht, dus ik stel voor dat je op zijn minst een kijkje neemt voordat je verder leest, al was het maar uit respect voor Erin's werk (en zijn vermelde bron werkt en speciale dank door elk van hun bijdragers) ).
Er zijn een paar verschillende termen die vaak worden gebruikt bij het praten over physics engines. Voor de duidelijkheid, hier is een korte verklarende woordenlijst om als referentie te gebruiken bij het lezen van dit bericht:
Een paar vereisten zijn vereist om ten volle te kunnen profiteren van dit artikel. De algemene lezer kan echter nog steeds veel van het materiaal genieten, hoewel het het beste is om een basiskennis te hebben van:
Omdat een beperking de vrijheidsgraden beperkt, laten we eens kijken wat een onbuigzaam lichaam doet wanneer zes tegelijk worden gebruikt:
Het bovengenoemde stijve lichaam gebruikt drie vrijheidsgraden om zich door de wereld te vertalen. De laatste drie worden gebruikt om de oriëntatie van alle drie de rotatie-assen constant te veranderen.
Laten we nu een paar verschillende voorbeelden bekijken van wat beperkingen eigenlijk zijn. De bekendste beperking is er een die voorkomt dat twee stijve lichamen binnendringen. Dit type beperking is alleen actief als twee lichamen elkaar binnendringen en de twee lichamen uit elkaar drijven. Zodra deze interpenetratiebeperking actief is, is het gemakkelijk te zien dat de vrijheidsgraden van de starre lichamen worden beperkt en zodanig worden beïnvloed dat ze een interessant resultaat opleveren (het interessante resultaat is dat de twee objecten tegen elkaar kunnen botsen) ):
De Hallo wereld van beperkingen zou de afstandsbeperking, waarbij twee punten op twee onbuigzame lichamen beperkt zijn tot een exacte afstand van elkaar. Je kunt je een massaloze staaf voorstellen die twee punten met elkaar verbindt, waarbij deze staaf niet kan worden uitgerekt of samengedrukt:
Er zijn veel soorten beperkingen voor allerlei interessante gedragingen, waaronder: wrijving, prismatisch, revolute, las, hoek en meer.
In algemene vorm is een beperking een scalaire vergelijking die gelijk is aan een bepaalde waarde (meestal nul).
\ Begin equation
C (l_1, a_1, l_2, a_2) = 0
\ Label EQ1
\ End equation
De \ (l \) en \ (a \) termen in \ eqref eq1 zijn mijn eigen notatie: \ (l \) verwijst naar lineair while \ (a \) verwijst naar hoekig. De subscripten 1 en 2 verwijzen naar de twee objecten binnen de beperking. Zoals je kunt zien, bestaan er lineaire en hoekige inputs voor een constraint-vergelijking, en elk moet een scalaire waarde zijn.
Laten we een stap terug doen om de afstandsbeperking te bekijken. De afstandsbeperking wil de afstand tussen twee ankerpunten op twee lichamen gelijk maken aan een of andere scalaire waarde:
\ 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 \) is de lengte van de staaf die beide lichamen verbindt; \ (P_1 \) en \ (P_2 \) zijn de posities van de twee lichamen.
In de huidige vorm is deze beperking een vergelijking van positie. Dit soort positievergelijking is niet-lineair, waardoor het heel moeilijk wordt opgelost. Een methode om deze vergelijking op te lossen kan zijn om in plaats daarvan de positiebeperking af te leiden (met betrekking tot de tijd) en een snelheidsbeperking te gebruiken. Resulterende snelheidsvergelijkingen zijn lineair, waardoor ze oplosbaar zijn. Oplossingen kunnen vervolgens worden geïntegreerd met een soort integrator terug in positie.
In de algemene vorm is een snelheidsbeperking van de vorm:
\ Begin equation
\ punt C (l_1, a_1, l_2, a_2) = 0
\ Label EQ3
\ End equation
Tijdens de afgeleide verschijnt een nieuwe term \ (J \) via een kettingregel:
\ Begin equation
\ punt C (l_1, a_1, l_2, a_2) = JV = 0
\ Label EQ4
\ End equation
De tijdafgeleide van \ (C \) creëert een snelheidsvector en een Jacobiaan. De Jacobiaan is een 1x6 matrix die scalaire waarden bevat die overeenkomen met elke vrijheidsgraad. In een paarsgewijze beperking bevat een Jacobiaan meestal 12 elementen (voldoende om de \ (l \) en \ (a \) termen voor beide lichamen te bevatten \ (A \) en \ (B \).
Een systeem van beperkingen kan een vorm aannemen gewricht. Een verbinding kan vele beperkingen bevatten die de vrijheidsgraden op verschillende manieren beperken. In dit geval zal de Jacobiaan een matrix zijn waarbij het aantal rijen gelijk is aan het aantal beperkingen dat actief is in het systeem.
De Jacobiaan is offline met de hand afgeleid. Zodra een Jacobiaan is verkregen, kan de code voor het berekenen en gebruiken van de Jacobiaan worden gemaakt. Zoals je kunt zien vanaf \ eqref eq4, wordt de snelheid \ (V \) getransformeerd van de cartesiaanse ruimte naar de beperkingsruimte. Dit is belangrijk omdat in de beperkingsruimte de oorsprong bekend is. In feite kan elk doelwit bekend zijn. Dit betekent dat elke beperking kan worden afgeleid om een Jacobiaan voort te brengen die krachten kan transformeren van de Cartesiaanse ruimte naar beperkte ruimte.
In de beperkingsruimte, gegeven een scalaire doelstelling, kan de vergelijking naar of van het doelwit worden verplaatst. Oplossingen kunnen eenvoudig worden verkregen in een beperkte ruimte om de huidige staat van een star lichaam naar een doeltoestand te verplaatsen. Deze oplossingen kunnen vervolgens vanuit beperkende ruimte terug worden omgezet in de cartesiaanse ruimte, zoals:
\ Begin equation
F = \ lambda J ^ T
\ Label EQ5
\ End equation
\ (F \) is een kracht in de Cartesiaanse ruimte, waar \ (J ^ T \) de omgekeerde (getransponeerde) Jacobiaan is. \ (\ lambda \) (lambda) is een scalaire multiplier.
Zie de Jacobiaan als een snelheidsvector, waarbij elke rij een vector zelf is (van twee scalaire waarden in 2D en drie scalaire waarden in 3D):
\ Begin equation
J = \ begin bmatrix
l_1 \\
a_1 \\
l_2 \\
a_2 \\
\ End bmatrix
\ Label EQ6
\ End equation
Om \ (V \) met \ (J \) te vermenigvuldigen, zou wiskundig matrix vermenigvuldiging inhouden. De meeste elementen zijn echter nul en daarom behandelen we de Jacobiaan als een vector. Dit stelt ons in staat om onze eigen bewerking voor computer \ (JV \) te definiëren, zoals in \ eqref eq4.
\ Begin equation
JV = \ begin 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
Hier staat \ (v \) voor lineaire snelheid en \ (ω \) (omega) staat voor de hoeksnelheid. \ eqref eq7 kan worden genoteerd als een paar puntproducten en vermenigvuldigingen om een efficiëntere berekening te bieden in vergelijking met volledige matrixvermenigvuldiging:
\ 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
De Jacobiaan kan worden gezien als een richtingsvector in beperkingsruimte. Deze richting wijst altijd naar het doel in de richting die het minste werk vereist. Aangezien deze "richting" Jacobiaan offline is afgeleid, hoeft er alleen nog maar de kracht op te worden genomen om de beperking te handhaven. Deze grootte wordt \ (\ lambda \) genoemd. \ (\ lambda \) kan de Lagrange-multiplier worden genoemd. Zelf heb ik Lagrangian Mechanics niet formeel gestudeerd, maar een studie van Lagrangian Mechanics is niet nodig om eenvoudig beperkingen te implementeren. (Ik ben het bewijs daarvan!) \ (\ Lambda \) kan worden opgelost met behulp van een constraint solver (meer hierover later).
In de krant van Erin Catto bestaat een eenvoudige schets voor Jakiansen die hand geven. De stappen zijn:
Het enige harde deel is het berekenen van het derivaat, en dit kan komen met oefenen. Over het algemeen zijn handafhankelijke beperkingen moeilijk, maar met de tijd gemakkelijker.
Laten we een geldige Jacobiaan afleiden voor gebruik bij het oplossen van een afstandsbeperking. We kunnen beginnen bij Stap 1 met \ eqref eq2. Hier zijn enkele details voor stap 2:
\ Begin equation
\ punt C = (P_2 - P_1) (\ punt P _2 - \ punt P _1)
\ Label eq9
\ End equation
\ Begin equation
\ punt C = (P_2 - P_1) ((v_2 + ω_2 \ tijden r_2) - (v_1 + ω_1 \ tijden r_1))
\ Label EQ10
\ End equation
\ (r_1 \) en \ (r_2 \) zijn vectoren van het zwaartepunt naar het ankerpunt, voor respectievelijk lichamen 1 en 2.
De volgende stap is het isoleren van de snelheidsvoorwaarden. Om dit te doen, zullen we gebruik maken van de scalaire drievoudige productidentiteit:
\ Begin equation
(P_2 - P_1) = d
\ Label eq11
\ End equation
\ Begin equation
\ punt C = (d \ cdot v_2 + d \ cdot ω_2 \ keer r_2) - (d \ cdot v_1 + d \ cdot ω_1 \ keer r_1)
\ Label eq12
\ End equation
\ Begin equation
\ punt C = (d \ cdot v_2 + ω_2 \ cdot r_2 \ maal d) - (d \ cdot v_1 + ω_1 \ cdot r_1 \ maal d)
\ Label eq13
\ End equation
De laatste stap is om de Jacobiaan te identificeren door middel van inspectie. Om dit te doen, zullen alle coëfficiënten van alle snelheidstermen (\ (V \) en \ (ω \)) worden gebruikt als de Jacobiaanse elementen. daarom:
\ Begin equation
J = \ begin bmatrix -d & -r_1 \ keer d & d & r_2 \ keer d \ end bmatrix
\ Label eq14
\ End equation
Contactbeperking (interpenetratiebeperking), waarbij \ (n \) het contact normaal is:
\ Begin equation
J = \ begin bmatrix -n & -r_1 \ keer n & n & r_2 \ keer n \ end bmatrix
\ Label eq15
\ End equation
Wrijvingsbeperking (actief tijdens penetratie), waarbij \ (t \) een wrijvingsas is (2D heeft één as, 3D heeft er twee):
\ Begin equation
J = \ begin bmatrix -t & -r_1 \ keer t & t & r_2 \ keer t \ end bmatrix
\ Label eq16
\ End equation
Nu we begrijpen wat een beperking is, kunnen we praten over hoe ze op te lossen. Zoals eerder vermeld, moeten we, als een Jacobiaan eenmaal met de hand is afgeleid, alleen oplossen voor \ (\ lambda \). Het is gemakkelijk om een enkele beperking afzonderlijk op te lossen, maar tegelijkertijd is het veel moeilijk om een groot aantal beperkingen tegelijkertijd op te lossen en erg inefficiënt (rekenkundig). Dit vormt een probleem, omdat games en simulaties waarschijnlijk in één keer veel beperkingen actief willen hebben.
Een alternatieve methode om alle constraints tegelijkertijd op te lossen (globaal oplossen) is om de beperkingen iteratief op te lossen. Door oplossingsrichtingen van de oplossing op te lossen en eerdere oplossingen aan de vergelijkingen toe te voegen, kunnen we samenkomen in de oplossing.
Een dergelijke iteratieve oplosser staat bekend als sequentiële impulsen, zoals gesynchroniseerd door Erin Catto. Sequentiële impulsen lijken sterk op Projected Gauss Seidel. Het idee is om alle beperkingen één voor één meerdere keren op te lossen. De oplossingen zullen elkaar ongeldig maken, maar gedurende vele iteraties zal elke afzonderlijke beperking convergeren en kan een globale oplossing worden bereikt. Dit is goed! Iteratieve oplossers zijn snel.
Zodra een oplossing is bereikt, kan een impuls worden toegepast op beide instanties in de beperking om de beperking af te dwingen.
Om een enkele beperking op te lossen, kunnen we de volgende vergelijking gebruiken:
\ Begin equation
\ lambda = \ frac - (JV + b) JM ^ - 1 J ^ T
\ Label eq17
\ End equation
\ (M ^ - 1 \) is de massa van de beperking; \ (b \) is de bias (meer hierover later).
Dit is een matrix die de inverse massa en omgekeerde traagheid van beide starre lichamen in de beperking bevat. Het volgende is de massa van de beperking; merk op dat \ (m ^ - 1 \) de inverse massa van een lichaam is, terwijl \ (I ^ - 1 \) de inverse traagheid van een lichaam is:
\ begin vergelijking 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
Hoewel \ (M ^ - 1 \) in theorie een matrix is, moet u het eigenlijk niet als zodanig modelleren (de meeste ervan zijn nullen!). Wees in plaats daarvan slim over wat voor soort berekeningen je doet.
\ (JM ^ - 1 J ^ T \) staat bekend als de constraint massa. Deze term wordt één keer berekend en gebruikt om op te lossen voor \ (\ lambda \). We berekenen het voor een systeem zoals:
\ 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
Let op: u moet \ eqref eq19 omkeren \ nqref eq17.
De bovenstaande informatie is alles wat nodig is om een beperking op te lossen! Een kracht in de Cartesiaanse ruimte kan worden opgelost en gebruikt om de snelheid van een object bij te werken, om een beperking af te dwingen. Onthoud \ 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 + = \ 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 \ begin bmatrix
\ lambda * l_1 \\
\ lambda * a_1 \\
\ lambda * l_2 \\
\ lambda * a_2 \\
\ End bmatrix
\ Label EQ20
\ End equation
Vanwege de linearisatie van de niet-lineaire positievergelijkingen gaat er wat informatie verloren. Dit resulteert in oplossingen die niet helemaal voldoen aan de oorspronkelijke positievergelijking, maar voldoen wel aan de snelheidsvergelijkingen. Deze fout is bekend als constraint drift. Men kan deze fout zien als het resultaat van een raaklijnbenadering.
Er zijn een paar verschillende manieren om dergelijke fouten op te lossen, die allemaal de fout benaderen en een vorm van correctie toepassen. De eenvoudigste staat bekend als Baumgarte.
Baumgarte is een kleine toevoeging van energie in de beperkingsruimte en is verantwoordelijk voor de \ (b \) term in de vorige vergelijkingen. Om rekening te houden met vertekening, hier is een aangepaste versie van \ eqref eq4:
\ Begin equation
\ punt C = JV + b = 0
\ Label eq21
\ End equation
Om een Baumgarte-term te berekenen en deze toe te passen als een bias, moeten we de oorspronkelijke beperkingsvergelijking inspecteren en een geschikte methode voor het berekenen van fouten vaststellen. Baumgarte heeft de vorm:
\ Begin equation
JV = - \ beta C
\ Label eq22
\ End equation
\ (\ beta \) (Baumgarte-term) is een afstembare, eenheidloze, simulatie-afhankelijke factor. Het is meestal tussen 0.1 en 0.3.
Om de bias-term te berekenen, laten we de vergelijking voor de niet-penetratiebeperking \ eqref eq15 bekijken voordat deze afgeleid wordt met betrekking tot tijd, waarbij \ (n \) het contact normaal is:
\ Begin equation
C = \ begin bmatrix -x_1 & -r_1 & x_2 & r_2 \ end bmatrix \ cdot \ vec n
\ Label eq23
\ End equation
De bovenstaande vergelijking zegt dat de scalaire fout van \ (C \) de inter-penetratiediepte tussen twee starre lichamen is.
Dankzij Erin Catto en zijn artikel over het oplossen van problemen, hebben we een manier om positiebeperkingen in termen van snelheid op te lossen. Veel interessante gedragingen kunnen voortkomen uit beperkingen en hopelijk zal het artikel voor veel mensen nuttig zijn. Zoals altijd, aarzel dan niet om vragen te stellen of opmerkingen hieronder te geven.
Zie Box2D Lite voor een hulpbron bij het oplossen van verschillende soorten 2D-beperkingen, evenals inzicht in vele implementatiespecificaties die hier niet worden behandeld.
Accentsconagua