Last month, I received an e-mail from a game developer who played the alpha demo of K.I.S.A. They enjoyed the demo, and became interested in the physics engine behind K.I.S.A - more specifically, the cloth physics. I provided them with a brief overview and a promise to write a more in-depth blog entry on the subject.
I now have time to make good on that promise...so let's talk about cloth physics.
Cloth physics in K.I.S.A is 75% math and 25% hack - my favorite combination of programming.
PART I: THE MATH
Kisa herself is the best example of cloth physics in the game. She makes use of it not only for a wide variety of skirts, but also to animate her hair. In the above image, you can see an animation of her walking overlaid with a representation of the hair and skirt meshes.
The two major components of the cloth system are points (yellow dots) and constraints (green lines). Anyone who has done any sort of physics body modeling before will be very familiar with these terms, but for the uninitiated I will plow on.
Points are infinitely small physical bodies. In this simulation they have a position (x,y), velocity (xspeed, yspeed), and mass. Mass is very important in the next section.
Constraints define a relationship between two points. I only use distance constraints, which is a relationship that means 'these two points are not allowed to be more X distance apart'. Some of the physics that I'll describe later could also be considered constraints, but for now let's just stick with distance constraints.
Every step of game logic, points update their x and y position based on their velocity, and then seek to satisfy their constraints. When the points and constraints are arranged in a grid, they resemble a net or rope webbing. The more points that we have, the more closely our mesh approximates a piece of cloth. Almost simple, right?
If only. Satisfying distance constraints is a tricky business. Typically, when points are too far apart, we move each of the offending points half the excess distance closer. So, if point A is at (0, 0), point B is at (10, 0), and they have a distance constraint of 6, we would move A to (2,0) and B to (8,0) to satisfy the constraint.
When there's more than one constraint, it can be difficult to satisfy all of them at once. If the program satisfies a distance constraint for A and B and then satisfies a distance constraint for B and C, the latter constraint may move B in such a way that the first constraint is no longer satisfied. The result is like a really bouncy tug-of-war that makes for jello-like skirts.
The good news is that it's not impossible to satisfy all of the distance constraints, just computationally expensive. If you loop through the constraints list multiple times in a single step, the system begins to converge on the optimal state. Oftentimes close is good enough, so 5-10 repetitions of satisfying constraints will do.
Note: I did not figure all of this out myself. I am indebted to the works of Andrew Hoyer and Thomas Jakobsen. Check them out for a much more mathematical analysis of the math of cloth physics.
Unfortunately, I found that no matter how I optimized my code, I could not afford to loop through the constraints list more than a single time while having skirt meshes of acceptable quality and complexity. Clearly it was time for...
PART II: THE HACKS
For the record, when I say 'hacks', I am referring only roughly 15% to the definition that means 'clever and cool programmer trick' and 85% to the definition that means 'hacked together code held together by spit, hope, and rubber bands'. Now that we're clear on that:
When satisfying a distance constraint, most algorithms I've seen treat all points as if they have equal mass. You can do some nifty optimizations and simplifications if you do that, and it's truer to how the mass of a cloth is actually distributed. If you assign the points mass, however, distance constraints satisfy themselves in new and exciting ways! (Wow. That sentence is 5.3 times dirtier than I intended.)
|MA = mass of A = 2|
MB = mass of B = 1
D = displacement = 3
DA = displacement of A = D * MB / (MA+MB) = 3 * 1 / (2+1) = 1
DB = displacement of B = D * MA / (MA+MB) = 3 * 2 / (2+1) = 2
So point B is displaced twice as much as point A. Imagine a baseball attached to a bowling ball by a piece of string, and you'll have a good idea of what's happening.
I can take advantage of this by predicting how the constraint system should converge, and then assigning masses to the points to encourage this same state to come about in pretty much a single step.
Examining a skirt for a few moments tells me the top of the skirt is fixed in placed around the waist, immovable in terms of the rest of the skirt. This means that I should weight the points in such a way that they tend to move towards the top of the skirt.
I assign the points at the very top of the skirt a mass of infinity (actually negative pi, but my program thinks that equals infinity. Shh, don't tell it!), and then assign mass exponentially from the bottom up.
|All points on the hem of the skirt receive a mass of 2000^0 = 1.|
All points a level higher receive a mass of 2000^1 = 2000.
All points a level higher than that receive a mass of 2000^2, etc.
This isn't suitable for every case, of course, but for cloth that is suspended from a single point or a similar situation it works beautifully. Note that this mass-based hack was implemented after Alpha 3.2, so it can only be seen in .gif form right now.
While we're on the topic, this is the same method I used to make the chains hang from the ceiling properly. When Kisa climbs chains, however, this upsets our assumptions about how the constraint system should converge (Kisa represents a large mass on the other side of the chain that points should be converging towards). I felt very clever when I temporarily swapped out the chain links for a single distance constraint between Kisa and the fixture point of the rope, but it turns out that Erin Catto did the exact same thing in Tomb Raider.
Anyway, final two hacks.
One constraint that I did not mention but should be fairly obvious is the one that forces the points on the edge of the skirt to stay out from between Kisa's legs. After all of the other constraints are satisfied, I find the lines formed between Kisa's hips-knees-ankles and make sure the skirt's edge points are a certain distance away from these lines. If I make the lines curve slightly based on distance from hip/knee, a realistic leg shape is formed.
When Kisa rolls, there's a problem: Kisa's skirt should really - and would, if I let the simulation have its way - fall over her head. But this isn't that sort of game, so I need to fix it in place. This is as simple as feeding the script that checks whether the cloth is between Kisa's legs a false positive, so that the edges of the skirts are 'locked' onto her legs. It still doesn't look quite right, so in the future I am going to have to give the skirt a fake shape to contour to that better approximates what the skirt would look like during a roll.
The final hack is one that helps take the load off of the cloth engine. As I said earlier, the more points that we have, the more our skirt resembles a real piece of cloth. But more points = more constraints = more processing per step, so it's important to keep the number of points as low as possible.
In the above, you can see that the skirt has 12 vertical levels to provide a good contour, but only 3 horizontal levels. If I only rendered the mesh the skirt bottom would look horrible and angular, but there's an easy way to make the skirt bottom look curved with only 3 points.
At the bottom of the skirt I've added a polygon - a trianglefan - drawn from the center bottom point and then to each point of a spline (curve) drawn between the three bottom points of the skirt. It's a simple but effective way to reduce the strain placed on the cloth simulation engine.
A similar effect can be seen on the top-back of Kisa's skirt when she rolls. This is partially for aesthetics and partially to stop the top of her legs from poking through the skirt mesh.
That's it. You now know basically everything there is to know about cloth physics in K.I.S.A, and literally everything that I know about cloth physics. If you're a game developer, go forth and simulate boldly.