Constraint-Based Verlet Physics Engine

[Seth]

hello everyone,

I'm currently trying to implement a 2D physics engine, using the verlet integration method.
For collision detection, i have implemented a working algortithm for polygons before.
The tutorial I'm using for the Constraint / Verlet system is (Advanced Character Physics): http://teknikus.dk/tj/gdc2001.htm
In this tutorial, each vertex of the polygon is treated separately.
I constructed a polygon class with a position and relative vertex coordinates. (which works best for the collision algorithm)
Now I am not sure if I should work with the absolute vertex coordinates, satisfy all the constraints and so on, or not
If not, I think that I just have to solve the collisions and push the two polygons apart, hopefully verlet will do the rest ^^
But the biggest problem is, that i don't know how to implement physics. After reading this tutorial, it seems if I dont have to treat rotations etc. (I think I will have to do this, if I treat a Polygon as one particle, not every vertex as a particle) what exactly do i need to solve the collision ? do I need exact contact points, or only the collision normal ? I only have masses (invers) and acceleration of the particles (vertices). Another question would be, if the masses I'll be using for the particles have to be calculated separately or if I can use the mass of the polygon. (i think this depents on if my polygon IS a particle or not) It would be good, if I could go on with using the verlet method. but I dont want it to become to difficult.

I hope these are not to much questions, but I'm no physics expert.

thank you

[Seth]

I now implemented vertices as particles, this is what it looks like now:
http://www.exec-dev.de/verlet.zip

I am calculating the MTD and push the two polygons (every vertex) apart.
now I need to calculate the exact contact points and add the mtd to them only, so that they rotate correctly.
(that's what I think ^^)

As you can see, the rectangle collapses. I don't exactly know why this happens. Maybe I am able to find the mistake / solution myself, but i'm not sure.

For the physics I have no plan, yet, I think I need to calculate the exchange of energy and add a force to every single vertex (don't as me how ^^) and add a friction constant.

I appreciate every help I can get.

[Steinmetz]

As you can see, the rectangle collapses. I don't exactly know why this happens. Maybe I am able to find the mistake / solution myself, but i'm not sure.

You've got to add a Constraint between two of the diagonal edges, because otherwise the rectangle can just fall over and every constraint is satisfied.

I implemented something like your engine, but with polygons instead of particles, I also based it on the paper "Advanced Character physics", but just for the constraints, the rest is done with polygons...
So I can't help you

[Seth]

hi,
I am using polygons, but I don't have a clue about rotations, angular momentum etc.
So I built these Polygons up of particles, which seems to work.
What you said seems to work for rectangles, but is there a solution which works for every polygon ?
Triangulation would work, but is'nt there a simpler way ?

EDIT: For Convex Polygons, Triangulation is very easy, so I chose that solution

I uploaded the "working" version here: http://www.exec-dev.de/verlet.zip
Now I', trying to add contact point finding. the last thing will be the solving of the collision.

thanks

[Steinmetz]

You could look at the following tutorial:
http://uk.geocities.com/olivier_rebellion/Polycolly.zip
He explains in general, how the SAT-Algorithm ( I don't know how you did find out about collisions, so I hope you did it with SAT also ) works and shows how to calculate contact points and the normal of collision.
Also he shows a method for finding the new speeds of two objects after a collision. I think if you use Verlet, the rotation etc. should come from alone ( please, to someone who knows better, correct me if I'm wrong.)
So you apply the impulse you calculated to the particle that collided and it should work.

[Seth]

thank you, I know this tutorial and I also implemented SAT for collision detection. I am already able to calculate the collision normal, but for the contact points I am not really sure how it works. I'll have a closer look at this.
But as I am not dealing with velocities, I have to find another way to "exchange" velocities. (The same goes for the reflection formula)

[bone]

Yeah, I think you've pretty much discovered the one massive problem with position-based physics. Restitution, and any energy preservation for that matter, cannot actually be controlled in any straightforward way, basically because energy and velocity are related (and velocity is auxiliary at best in a Verlet system).

A simple example to think about is a point mass falling straight down onto an immovable surface. When you detect the point is below the surface, you must move it back above the surface to satisfy your constraint. If you move it right to the surface, and you compute the velocity from the current and previous position, then the velocity will still be downwards. The velocity will be arbitrary, depending on the position prior to the collision detection. After a second timestep, the current and previous positions will be the same, and the velocity will now be zero. You've lost all the energy with absolutely no control over it.

Sure you could try to back-calculate the position so that the velocity and therefore energy works out correctly, but it seems nearly impossible to do so once the system become more complex than the above example. Even in the above simple example, your point mass won't bounce off the actual surface at first, because you need the position high enough so that the velocity restitution is correct. And then satisfying multiple constraints while doing these strange energy-correcting back calculations seems really difficult (to me, at least).

[Seth]

thanks,
but isn't there a way to "simulate" velocity by positioning the last-step vertex coordinates ?

Another method for Verlet would be to treat the whole Polygon as a "particle", but I don't know how this works and how to deal with rotations, angular momentum etc.

[DannyChapman]

My experience is:

The Vertlet/particle method for rigid bodies is super-simple to get some simple demos running.

However, as soon as you start adding the features that are needed to make it useful - friction, controlled collision restitution, complex shapes etc you end up with so many hacks it becomes really complicated (but probably still not well behaved) - far more than impulse based methods.

[Seth]

hi,

I am no expert in this topic, so I need something which is very easy to implement and which can handle circles, polygons and things like hinge constraints etc. I have many documents about this topic but the verlet article is the first one which I find useful and easy to understand for an implementation. If there are other tutorials with better approaches, which are well explained and easy to understand and follow without having to much background information (which I don't have) this would be an alternative.

thank you

[hardwire]

Maybe JelloPhysics does what you want to do. If not you can at least look into the code:)
It doesn't use Verlet (at least at the time I looked into it lastly), but works nicely.
http://www.walaber.com/index.php?action=showitem&id=16

[Seth]

thank you,
the problem is, that there is no physics engine for the language i am using and translating for example box2d would be much work and it might also be hard to get it working.
so i am trying to implement a physics engine myself. (it doesn't have to be perfect at the first try)

The current version is to be found here:

http://www.exec-dev.de/verlet.zip

JelloPhysics seems like its able to deal with sort of deformation, which makes it even more complicated. I think box2d is very near to what I planned for my physics engine. (I could try to translate it, but it will be much work)

Another option would be to translate Polygon (which wouldn't be that hard), but I don't know how to add stuff like springs or hinges in there.

[hardwire]

thank you,
the problem is, that there is no physics engine for the language i am using and translating for example box2d would be much work and it might also be hard to get it working.
so i am trying to implement a physics engine myself. (it doesn't have to be perfect at the first try)

The current version is to be found here:

http://www.exec-dev.de/verlet.zip

JelloPhysics seems like its able to deal with sort of deformation, which makes it even more complicated. I think box2d is very near to what I planned for my physics engine. (I could try to translate it, but it will be much work)

Another option would be to translate Polygon (which wouldn't be that hard), but I don't know how to add stuff like springs or hinges in there.

Maybe you could build the Box2D or JelloPhysics as a library and then use it externally, but I don't know how it would work since I don't have any expiriences of using multi-language stuff together.

JelloPhysics is much much simpler then Box2D or any other rigid body simulator...it is also less computationally intensive IMHO.

[Seth]

when I have a look at this video
http://de.youtube.com/watch?v=SvqY_pgA6DU

this seems much more complicated. The best option at the moment seems to be translating the polycolly code and extend it, so it can deal with hinges, springs etc. is this possible ?

[hardwire]

when I have a look at this video
http://de.youtube.com/watch?v=SvqY_pgA6DU

this seems much more complicated. The best option at the moment seems to be translating the polycolly code and extend it, so it can deal with hinges, springs etc. is this possible ?

I have implemented both (very) simple rigid body simulator (similar to PollyColly) and Vertlet soft body simulator similar to JelloPhysics and I must say the latter is really much LESS complicated.

Realize that all you have to do is to simulate mass points and springs, that's all. Mass points don't rotate so you don't need to bother about angular velocity and intertia. Also using verlet makes collision response very simple - all you need to do is simply move the mass point away so it doesn't collide anymore. But looking at your demo I think you already know all of this, so I really don't know why you think it is more complicated then rigid body simulation