Deformable body using shape matching algorithm

You should check out the excellent post here, with source code (including a very clever and simple trick to avoid all of the matrix-sqrt-and-inversion in the original paper: http://labs.byhook.com/2010/06/29/particle-based-rigid-bodies-using-shape-matching/comment-page-1/

I have made a stable positionbased 2D physics engine.
It is for Windows 2000 but it can run on Windows 7 after some pain with the registry.
http://2008.gameawards.se/competition_entries/73
http://www.rapidspread.com/file.jsp?id=9gfmsdvxdf

The explained method in the pdf document seems to be transforming the highly detailed model with a low detailed model to get more speed while colliding with the high detail model in a grid transformation.

The theory behind my engine:
You don't need to know anything about torque because rotation is only an illusion. When you rotate a chair, you don't rotate the core of each atom in the chair. You only change their positions using forces. The chair holds it's shape with connections between the atoms by softly enforcing a fixed length between the 2 atoms in each connection. Think of a rigid body as a number of hard balls connected by stiff dampers. In slow motion, it is equivalent to soft balls and soft dampers and all forces are weaker.

Quote:

Original post by Dawoodoz I have made a stable positionbased 2D physics engine.

The download links don't seem to be working :(

You might be interested in this paper, which espouses a similar approach to what you describe: http://home.iae.nl/users/starcat/dynamo/publications/aynif.pdf

@Raigan

Thanks for the link, looks interesting. I'm trying to get a discussion going with then author of the article. In the mean time, I have made a 2d vector based alternative to the matrix based method described in the Muller paper. It also uses shape matching to preserve the original soft body shape, and allows for very viscous area preserving bodys. It also conserves linear and angular momentum. As a bonus it doesn't use any sqrt() calls and only needs 2 trig calls per update. I won't mind posting the source once i've tested and polished it.

@Dawoodoz

Sounds very interesting, unfortunately the links seem dead. Does the download contain any source code for inspiration?

cheers,
Mike

I'd be really interested in hearing more about your method whenever you work it out; when we tried this in 2D we ended up using the same matrix-based approach as the original paper, which seemed very inefficient (and was a huge pain to get working).

It's starting to look good, although still there may be a few bugs. The code is still very ugly though, but I won't mind uploading a proof-of-concept sandbox exe. I'll have it ready by tonight (european time) :-)

Cheers,
Mike

Ok, here we go...



So far it's just a random shape sandbox proof-of-concept thing. It features particle-to-rest-point damped spring, particle-to-neighbor damped spring, and area preserving pressure, all of which are given a random clamped value. Each body only takes two trig calls per update, and zero sqrt calls!

Cheers,
Mike

Cool! I don't see how you could calculate all those spring forces with that little work though.. can't wait for more details! :)

If the spring has length zero, the spring force is:

Fx = -k*(Px-Rx)
Fy = -k*(Py-Ry)

where F = force, P = current position, and R = rest position. That is, the spring has a fixed vertical and horizontal rest length of zero. The spring forces are perpendicular and hence does not influence each other. The horizontal spring force Fx depends only on the displacement along the x axis and is completely independent of vertical displacement, and vice versa. This is also true for springs between two moving particles, as long as they have a fixes horiz. and vert. rest length.

You only need sqrt() if the spring can rotate freely in all directions, in which case you need to find the spring length by solving the Pythagorean theorem r = sqrt(x^2 + y^2).

(EDIT: fleshed out the explanation a bit.)

Cheers,
Mike

[Edited by - h4tt3n on August 25, 2010 10:28:45 AM]

Quote:

Original post by h4tt3n This is also true for springs between two moving particles, as long as they have a fixed horiz. and vert. rest length.

That's pretty cool! This works in the body's local frame/coordinate system though, otherwise the vert/horiz components would be changing as the body rotates, right?

How are you handling the shape-matching? Maybe it's just the two sets of springs, but those blobs seem nice and solid when the collide with the ground; when we tried shape-matching, collision was always super-mushy and felt very "penalty-force-ish".

Quote:

Original post by raiganThat's pretty cool! This works in the body's local frame/coordinate system though, otherwise the vert/horiz components would be changing as the body rotates, right?

Exactly, you got the gist of how this works. All springs have two perpendicular rest lengths *in the soft bodys local frame of reference*. By rotating the soft body we also rotate all the rest lengths.

Quote:

How are you handling the shape-matching? Maybe it's just the two sets of springs, but those blobs seem nice and solid when the collide with the ground; when we tried shape-matching, collision was always super-mushy and felt very "penalty-force-ish".

I'll get back to this and the conservation of momentum stuff later, got to go.

Cheers,
Mike

[Edited by - h4tt3n on August 25, 2010 10:13:53 AM]

Hello folks,

Here's a new, cleaned up version available, where you can see both the soft body's current shape and its rigid "rest shape". The soft bodys take so little cpu power that the sandbox runs fluently with around 500 bodies on screen, and at a decent framerate with up to 1000 bodies.



Cheers,
Mike

[Edited by - h4tt3n on August 25, 2010 2:12:55 PM]

..I still can't wait to hear about your vector-based alternative to the shape-matching step :)

Sorry, I got carried away by other stuff. In the mean time I've cleaned up the algorithm a bit and done some tests. I don't mind explaining how it works, but it'll have to wait until the weekend, since I have some busy days ahead of me. Stay tuned :-)

Cheers,
Mike

No problem -- thanks! :)

Ok, here we go...

First we need to look into springs with rest-length zero. Interestingly, these can be implemented without calling the cpu-expensive square root function. The spring force along the x axis can be expresssed Fx = -k*Dx, where Fx is x component of force vector, k is spring stiffnes coefficient, and Dx is x component of displacement vector. Similarly Fy = -k*Dy, and since the two forces are perpendicular, they do not influence each other. The magnitude of Fx is proportional to Dx, independently of Dy, and vice versa.

The square root function is only needed if the spring has a non-zero length, and if it can rotate freely in all directions, in which case we need to find the spring length with the Pythagorean theorem, l = sqr(x^2 + y^2).

Similarly, we can apply a "square-root-less" spring with a predefined rest length along each axis the same way: F = -k*(L-R), where F is force vector, k is stiffnes, coefficient, L is length vector, and R is rest length vector. If f. inst. R=(10, 20), then the particles at each end of the spring will come to rest 10 units apart along the x axis and 20 units along the y axis. We drop the spring's ability to rotate freely in all directions and gain computation speed instead.

These two types of springs are beeing used to shape the soft body's boundary. Next, we'll see how it's possible to rotate the springs anyway and make them behave like a connected whole rather than individual springs.

Cheers,
Mike

Awesome, that's a really cool idea -- 2x 1D springs instead of a 2D spring.

So.. how are you actually performing the shape matching/extracting the rotation from the particles? :)

Ok, this is how it's done... First you define a 2d soft body data structure which contains a number of static points, which defines the "rest shape" of the body, and a number of free-moving particles - one for each point. There's also two sets of springs - one zero length spring for each static point - particle pair, and one fixed angle spring for each particle - particle pair. The structure also holds info about the body's linear and angular state, such as position, velocity, moment of inertia, angle and so on. Generally speaking, it works like this:

do

(1) calculate all internal forces, ie. all the spring interactions.

(2) apply this force on the particles, and the opposite equal force (and corresponding torque) on the body.

(3) calculate the local force on each particle that corresponds to the global force and torque applied on the body (throw the global summed up force back at the particles :-D).

(4) calculate all external forces ie. collision response, mouse interaction etc.

(5) Update particle state with your favourite integrator.

(6) Calculate the new global state of the soft body based on new particle states, ie. position, velocity, moment of inertia, and angular velocity.

(7) draw to screen.

loop

I may have been a bit unclear about some aspects, so feel free to ask about all the details.

Cheers,
Mike

Thanks so much for all of this info.. I can't wait to get back to our implementation and try out some of this stuff!

(6) is where the shape-matching happens, right? So.. how does that actually work? :)

Given a new position+orientation of the rigid frame, I understand how you can compute the updated "position, velocity, moment of inertia, and angular velocity", but the real magic of shape-matching is how you infer the rigid frame's state from the particle positions.

I don't see any other way to extract the rigid frame's position than by a weighted sum of particle positions (as in the original paper), so the only remaining tricky bit is extracting the rotation -- are you just using e.g weighted sum of atan2 as suggested by the Hook Labs article? You mentioned "a 2d vector based alternative to the matrix based method"..

Thanks again :)