Simulieren Sie zerreißbare Stoffe und Stoffpuppen mit einfacher Verlet-Integration

() translation by (you can also view the original English article)

Bei der Dynamik weicher Körper geht es darum, realistische verformbare Objekte zu simulieren. Wir werden es hier verwenden, um einen zerreißbaren Stoffvorhang und eine Reihe von Stoffpuppen zu simulieren, mit denen Sie interagieren und über den Bildschirm fliegen können. Es wird schnell, stabil und einfach genug sein, um mit Mathematik auf Highschool-Niveau zu tun zu haben.

Hinweis: Obwohl dieses Tutorial in Processing geschrieben und mit Java kompiliert wurde, sollten Sie in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte verwenden können.

Endergebnis Vorschau

In dieser Demo sehen Sie einen großen Vorhang (zeigt die Stoffsimulation) und eine Reihe kleiner Strichmännchen (zeigt die Ragdoll-Simulation):

Sie können die Demo auch selbst ausprobieren. Klicken und ziehen Sie, um zu interagieren, drücken Sie 'R', um zurückzusetzen, und drücken Sie 'G', um die Schwerkraft umzuschalten.

Schritt 1: Ein Punkt und seine Bewegung

Die Bausteine unseres Spiels sind der Punkt. Um Mehrdeutigkeiten zu vermeiden, nennen wir es PointMass. Die Details sind im Namen enthalten: Es ist ein Punkt im Raum und es repräsentiert eine Menge an Masse.

Der grundlegendste Weg, die Physik für diesen Punkt zu implementieren, besteht darin, ihre Geschwindigkeit auf irgendeine Weise "vorwärts" zu bringen.

1	x = x + velX
2	y = y + velY

Schritt 2: Zeitschritte

Wir können nicht davon ausgehen, dass unser Spiel immer mit der gleichen Geschwindigkeit läuft. Es kann für einige Benutzer mit 15 Bildern pro Sekunde ausgeführt werden, für andere jedoch mit 60. Es ist am besten, die Bildraten aller Bereiche zu berücksichtigen, was mit einem Zeitschritt erfolgen kann.

1	x = x + velX * timeElapsed
2	y = y + velY * timeElapsed

Auf diese Weise würde das Spiel immer noch mit der gleichen Geschwindigkeit laufen, wenn ein Frame für eine Person länger dauern würde als für eine andere. Für eine Physik-Engine ist dies jedoch unglaublich instabil.

Stellen Sie sich vor, Ihr Spiel friert für ein oder zwei Sekunden ein. Der Motor würde dies überkompensieren und den PointMass an mehreren Wänden und Objekten vorbei bewegen, mit denen er sonst eine Kollision festgestellt hätte. Somit wäre nicht nur die Kollisionserkennung betroffen, sondern auch die Methode zur Lösung von Einschränkungen, die wir verwenden werden.

Wie können wir die Stabilität der ersten Gleichung x = x + velX mit der Konsistenz der zweiten Gleichung x = x + velX * timeElapsed haben? Was wäre, wenn wir vielleicht beides kombinieren könnten?

Genau das werden wir tun. Stellen Sie sich vor, unsere timeElapsed wäre 30. Wir könnten genau das Gleiche wie die letztere Gleichung tun, jedoch mit einer höheren Genauigkeit und Auflösung, indem wir sechsmal x = x + (velX * 5) aufrufen.

elapsedTime = lastTime - currentTime
lastTime = currentTime // reset lastTime
 
// add time that couldn't be used last frame
elapsedTime += leftOverTime
 
// divide it up in chunks of 16 ms
timesteps = floor(elapsedTime / 16)
 
// store time we couldn't use for the next frame.
leftOverTime = elapsedTime - timesteps * 16
 
for (i = 0; i < timesteps; i++) {
     x = x + velX * 16
     y = y + velY * 16
     
     // solve constraints, look for collisions, etc.
}

Der Algorithmus verwendet hier einen festen Zeitschritt, der größer als eins ist. Es findet die verstrichene Zeit, zerlegt sie in "Stücke" fester Größe und verschiebt die verbleibende Zeit auf das nächste Bild. Wir führen die Simulation nach und nach für jeden Teil aus, in den unsere verstrichene Zeit aufgeteilt ist.

Ich habe 16 als Zeitschrittgröße ausgewählt, um die Physik so zu simulieren, als würde sie mit ungefähr 60 Bildern pro Sekunde ausgeführt. Die Konvertierung von elapsedTime in Frames pro Sekunde kann mit etwas Mathematik erfolgen: 1 second / elapsedTimeInSeconds.

1s / (16ms/1000s) = 62,5fps, sodass ein Zeitschritt von 16 ms 62,5 Bildern pro Sekunde entspricht.

Schritt 3: Abhängigkeiten

Abhängigkeiten sind Einschränkungen und Regeln, die der Simulation hinzugefügt werden und bestimmen, wohin PointMasses gehen kann und wo nicht.

Sie können so einfach sein wie diese Randbedingung, um zu verhindern, dass PointMasses vom linken Bildschirmrand abweicht:

1	if (x < 0) {
2	x = 0
3	if (velX < 0) {
4	velX = velX * -1
5	}
6	}

Das Hinzufügen der Einschränkung für den rechten Bildschirmrand erfolgt auf ähnliche Weise:

if (x > width) {
     x = width
     if (velX > 0) {
          velX = velX * -1
     }
}

Um dies für die y-Achse zu tun, müssen Sie jedes x in ein y ändern.

Die richtigen Abhängigkeiten können zu sehr schönen und faszinierenden Interaktionen führen. Abhängigkeiten können auch extrem komplex werden. Stellen Sie sich vor, Sie simulieren einen vibrierenden Korb mit Körnern, bei dem sich keines der Körner schneidet, oder einen Roboterarm mit 100 Gelenken oder sogar etwas Einfaches wie einen Stapel Kisten. Der typische Prozess besteht darin, Kollisionspunkte zu finden, den genauen Zeitpunkt der Kollision zu finden und dann die richtige Kraft oder den richtigen Impuls zu finden, um auf jeden Körper zu wirken, um diese Kollision zu verhindern.

Es kann schwierig sein, die Komplexität einer Reihe von Abhängigkeiten zu verstehen, und dann ist es noch schwieriger, diese Abhängigkeiten in Echtzeit zu lösen. Wir werden die Lösung von Einschränkungen erheblich vereinfachen.

Schritt 4: Verlet-Integration

Ein Mathematiker und Programmierer namens Thomas Jakobsen untersuchte einige Möglichkeiten, die Physik von Charakteren für Spiele zu simulieren. Er schlug vor, dass Genauigkeit bei weitem nicht so wichtig ist wie Glaubwürdigkeit und Leistung. Das Herzstück seines gesamten Algorithmus war eine seit den 60er Jahren verwendete Methode zur Modellierung der Molekulardynamik, die Verlet-Integration. Sie kennen vielleicht das Spiel Hitman: Codename 47. Es war eines der ersten Spiele, das Ragdoll-Physik verwendete und die von Jakobsen entwickelten Algorithmen verwendet.

Die Verlet-Integration ist die Methode, mit der wir die Position unseres PointMass weiterleiten. Was wir zuvor gemacht haben, x = x + velX, ist eine Methode namens Euler Integration (die ich auch beim Codieren von destruktivem Pixelgelände verwendet habe).

Der Hauptunterschied zwischen Euler- und Verlet-Integration besteht darin, wie die Geschwindigkeit implementiert wird. Mit Euler wird eine Geschwindigkeit mit dem Objekt gespeichert und bei jedem Frame zur Position des Objekts hinzugefügt. Bei Verwendung von Verlet wird jedoch die Trägheit angewendet, indem die vorherige und die aktuelle Position verwendet werden. Nehmen Sie den Unterschied zwischen den beiden Positionen und addieren Sie ihn zur neuesten Position, um die Trägheit anzuwenden.

// Inertia: objects in motion stay in motion.
velX = x - lastX
velY = y - lastY

nextX = x + velX + accX * timestepSq
nextY = y + velY + accY * timestepSq

lastX = x
lastY = y

x = nextX
y = nextY

Wir haben dort eine Beschleunigung für die Schwerkraft hinzugefügt. Ansonsten sind accX und accY für die Lösung von Kollisionen nicht erforderlich. Mit der Verlet-Integration müssen wir keine Impuls- oder Kraftlösung mehr für Kollisionen durchführen. Das Ändern der Position allein reicht aus, um eine stabile, realistische und schnelle Simulation zu erhalten. Was Jakobsen entwickelt hat, ist ein linearer Ersatz für etwas, das sonst nichtlinear ist.

Schritt 5: Link-Abhängigkeiten

Die Vorteile der Verlet-Integration lassen sich am besten anhand eines Beispiels veranschaulichen. In einer Fabric-Engine haben wir nicht nur PointMasses, sondern auch Verknüpfungen zwischen ihnen. Unsere "Links" sind eine Abstandsbeschränkung zwischen zwei PointMasses. Idealerweise möchten wir, dass zwei PointMasses mit dieser Einschränkung immer einen bestimmten Abstand voneinander haben.

Wann immer wir diese Einschränkung lösen, sollte Verlet Integration diese Punktmassen in Bewegung halten. Wenn zum Beispiel ein Ende schnell nach unten bewegt werden soll, sollte das andere Ende ihm wie eine Peitsche durch die Trägheit folgen.

Wir benötigen nur einen Link für jedes aneinander angehängte PointMasse-Paar. Alle Daten, die Sie im Link benötigen, sind die PointMasses und die Ruheentfernungen. Optional können Sie Steifheit für eine größere Federbeschränkung haben. In unserer Demo haben wir auch eine "Tränenempfindlichkeit", dh die Entfernung, in der der Link entfernt wird.

Ich werde hier nur restingDistance erklären, aber der Reißabstand und die Steifheit sind sowohl in der Demo als auch im Quellcode implementiert.

Link {
     restingDistance
     tearDistance
     stiffness
     
     PointMass A
     PointMass B
     solve() {
          math for solving distance
     }
}

Sie können lineare Algebra verwenden, um die Einschränkung zu lösen. Finden Sie die Abstände zwischen den beiden, bestimmen Sie, wie weit sie entlang der restingDistance sind, und übersetzen Sie sie dann basierend auf diesen und ihren Unterschieden.

// calculate the distance
diffX = p1.x - p2.x
diffY = p1.y - p2.y
d = sqrt(diffX * diffX + diffY * diffY) 

// difference scalar
difference = (restingDistance - d) / d

// translation for each PointMass. They'll be pushed 1/2 the required distance to match their resting distances.
translateX = diffX * 0.5 * difference
translateY = diffY * 0.5 * difference

p1.x += translateX
p1.y += translateY

p2.x -= translateX
p2.y -= translateY

In der Demo berücksichtigen wir auch Masse und Steifheit. Es gibt einige Probleme bei der Lösung dieser Einschränkung. Wenn mehr als zwei oder drei PointMasses miteinander verknüpft sind, kann das Lösen einiger dieser Abhängigkeiten andere zuvor gelöste Abhängigkeiten verletzen.

Auch Thomas Jakobsen ist auf dieses Problem gestoßen. Zunächst könnte man ein Gleichungssystem erstellen und alle Abhängigkeiten gleichzeitig lösen. Dies würde jedoch schnell an Komplexität zunehmen und es wäre schwierig, mehr als nur ein paar Links in das System einzufügen.

Jakobsen entwickelte eine Methode, die zunächst albern und naiv erscheinen könnte. Er schuf eine Methode namens "Entspannung", bei der wir die Einschränkung nicht einmal lösen, sondern mehrmals lösen. Jedes Mal, wenn wir die Links wiederholen und lösen, werden die Links immer näher an alle, die gelöst werden.

Schritt 6: Bringen Sie es zusammen

Um es noch einmal zusammenzufassen: So funktioniert unsere Engine im Pseudocode. Ein genaueres Beispiel finden Sie im Quellcode der Demo.

animationLoop {
     numPhysicsUpdates = however many we can fit in the elapsed time
     for (each numPhysicsUpdates) {
          // (with constraintSolve being any number 1 or higher. I typically use 3
          for (each constraintSolve) {
               for (each Link constraint) {
                    solve constraint
               } // end link constraint solves
          } // end constraints
          
          update physics // (use verlet!)
     } // end physics update
     
     draw points and links
}

Schritt 7: Fügen Sie einen Stoff hinzu

Jetzt können wir den Stoff selbst konstruieren. Das Erstellen der Links sollte recht einfach sein: Link nach links, wenn der PointMass nicht der erste in seiner Zeile ist, und Link, wenn er nicht der erste in seiner Spalte ist.

Die Demo verwendet eine eindimensionale Liste zum Speichern von PointMasses und findet Punkte, die mit x + y * width verknüpft werden können.

// we want the y loop to be on the outside, so it scans row-by-row instead of column-by-column
for (each y from 0 to height) {
     for (each x from 0 to width) {
          new PointMass at x,y
          
          // attach to the left
          if (x != 0)
               attach PM to last PM in list
               
          // attach to the right
          if (y != 0)
               attach PM to PM @ ((y - 1) * (width+1) + x) in list
          
          if (y == 0)
                pin PM
           
          add PM to list    
     }
}

Möglicherweise stellen Sie im Code fest, dass wir auch "Pin PM" haben. Wenn wir nicht möchten, dass unser Vorhang fällt, können wir die oberste Reihe von PointMasses an ihren Startpositionen verriegeln. Um eine Pin-Einschränkung zu programmieren, fügen Sie einige Variablen hinzu, um die Pin-Position zu verfolgen, und verschieben Sie die PointMass nach jeder Einschränkung der Einschränkung an diese Position.

Schritt 8: Fügen Sie einige Stoffpuppen hinzu

Stoffpuppen waren Jakobsens ursprüngliche Absichten hinter seiner Verwendung von Verlet Integration. Zuerst fangen wir mit den Köpfen an. Wir erstellen eine Kreisbeschränkung, die nur mit der Grenze interagiert.

Circle {
     PointMass
     radius
     solve() {
          if (y < radius)
               y = 2*(radius) - y;
         if (y > height-radius)
               y = 2 * (height - radius) - y;
         if (x > width-radius)
               x = 2 * (width - radius) - x;
         if (x < radius)
               x = 2*radius - x;
     }
}

Als nächstes können wir den Körper erschaffen. Ich habe jedes Körperteil hinzugefügt, um die Masse- und Längenanteile eines normalen menschlichen Körpers etwas genau anzupassen. Weitere Informationen finden Sie in Body.pde in den Quelldateien. Dies führt uns zu einem anderen Problem: Der Körper verformt sich leicht in unangenehme Formen und sieht sehr unrealistisch aus.

Es gibt verschiedene Möglichkeiten, dies zu beheben. In der Demo verwenden wir unsichtbare und sehr steife Verbindungen von den Füßen zur Schulter und vom Becken zum Kopf, um den Körper auf natürliche Weise in eine weniger unangenehme Ruheposition zu bringen.

Sie können auch Fake-Angle-Abhängigkeiten mithilfe von Links erstellen. Nehmen wir an, wir haben drei PointMasses, von denen zwei mit einer in der Mitte verknüpft sind. Sie können eine Länge zwischen den Enden finden, um einen beliebigen Winkel zu erfüllen. Um diese Länge zu ermitteln, können Sie das Kosinusgesetz verwenden.

A = resting distance from end PointMass to center PointMass
B = resting distance from other PointMass to center PointMass

length = sqrt(A*A + B*B - 2*A*B*cos(angle))

create link between end PointMasses using length as resting distance

Ändern Sie den Link so, dass diese Einschränkung nur gilt, wenn der Abstand kleiner als der Ruheabstand ist oder wenn er größer als ist. Dadurch wird verhindert, dass der Winkel am Mittelpunkt je nach Bedarf zu nah oder zu weit ist.

Schritt 9: Mehr Dimensionen!

Eines der großartigen Dinge bei einer vollständig linearen Physik-Engine ist die Tatsache, dass sie jede gewünschte Dimension haben kann. Alles, was mit x gemacht wurde, wurde auch mit einem y-Wert gemacht, und daher kann die Kraft auf drei oder sogar vier Dimensionen erweitert werden (ich bin mir jedoch nicht sicher, wie Sie das rendern würden!).

Hier ist beispielsweise eine Verknüpfungsbeschränkung für die Simulation in 3D:

// calculate the distance
diffX = p1.x - p2.x
diffY = p1.y - p2.y
diffZ = p1.z - p2.z
d = sqrt(diffX * diffX + diffY * diffY + diffZ * diffZ) 

// difference scalar
difference = (restingDistance - d) / d

// translation for each PointMass. They'll be pushed 1/2 the required distance to match their resting distances.
translateX = diffX * 0.5 * difference
translateY = diffY * 0.5 * difference
translateZ = diffZ * 0.5 * difference

p1.x += translateX
p1.y += translateY
p1.z += translateZ

p2.x -= translateX
p2.y -= translateY
p2.z -= translateZ

Abschluss

Danke fürs Lesen! Ein Großteil der Simulation basiert stark auf Thomas Jakobsens Artikel über fortgeschrittene Charakterphysik aus der GDC 2001. Ich habe mein Bestes getan, um die meisten komplizierten Dinge zu entfernen und bis zu dem Punkt zu vereinfachen, den die meisten Programmierer verstehen werden. Wenn Sie Hilfe benötigen oder Kommentare haben, können Sie diese gerne unten posten.