Symplectic Integrator

[sanotehu]

I notice that chipmunk uses a non-symplectic integrator (standard euler). This causes a lot of problems with springs and such because non-symplectic methods have unbounded energy growth so the system needs damping or it will fly apart. A symplectic integrator on the other hand has bounded energy fluctuations, so gravity, springs, and other conservative/position-dependent forces behave properly. Scientific sims usually use symplectic integrators because of this.

Standard euler is like this:

p += v*dt
v += a*dt

It turns out that if you switch it around like this:

v += a*dt
p += v*dt

It becomes symplectic. The second form (Symplectic Euler) is just as accurate, just as simple, just as easy to understand, just as decoupled, but it conserves energy (within bounds). Note that even RK4 doesn't conserve energy so it will eventually blow up (or maybe it fizzles out, I forget). In my experience, using the symplectic form has a few other perks (like forces and impulses becoming equivalent), but that stuff is minor and incidental and can't be counted on. I've always used symplectic euler in my physics code because there is really no excuse not to.

I was suprised when some stuff in chipmunk blew up quite quickly, so I looked at the source, sure enough, it was non-symplectic form. I am not familiar with the internals of chipmunk, so I don't know if moving the velocity update before the displacement update will break all that stuff that is between them now (looks like contact solving). The code in question is in cpSpaceStep().

I don't who is behind the widespread use of the traditional form of Euler integration, but it really has to be eradicated. Everyone uses and recommends it, but it has absolutely no advantage over the symplectic form. I guess its just tradition and the fact that this numerical methods stuff is like a lot of black magic, so no one asks questions. This issue needs to be alot more well-known so that we can stop using traditional euler. Tell your mom, tell your friends, tell your cat, and put it in your code.

Would this be an easy change or would it break some core assumptions in the contact code?

[slembcke]

I am aware of the downsides of standard Euler intergration, but for simplicity sake, it has some very very useful properties.

Chipmunk works like this:
1) Integrate the positions of everything and finds colliding pairs.
2) Pre-calculate a number of properties of the contacts and joints. (mass properties, bounce velocities, etc)
3) Integrate the velocities of everything.
4) Run a number of solver iterations, to fix velocity constraints.

Case 1, a box sitting on the ground:
1) The box is at rest, it's velocity is (very near) zero, it's position doesn't change. Generate a contact with the ground.
2) Precalculate the contact properties, if elasticity is set, the "bounce" velocity is calculated now (as 0).
3) Integrate the velocity, gravity makes the object accelerate downwards.
4) Solve the contact. Velocity should converge back to 0. If elasticity was set, it will be handled correctly without resorting to threshold velocities.

#1 is really the most important part. If you were to update the velocity before the postition, it would cause the box to move itself into a position where it would intersect the ground. While Chipmunk has to solve these overlaps anyway, avoiding them seems desirable. Another very useful property is that when cpSpaceStep() returns, all of the collision detection data structures are up to date. No need to reindex them twice in a single frame if you want to make queries.

I have run into problems with spring stability in the past, but they are generally pretty easy to overcome. One example is the long deprecated cpBodyApplyDampedSpring() function which calculated and applied forces between 2 bodies. Large spring and damping values would easily become unstable. I fixed that by creating a cpDampedSpring() constraint which calculated the damping values in the impulse solver instead of as forces. That solved most of the spring problems. In one case where it didn't was a physics scene I did for a contract of a flexible plant stem. The plant had over 90 constraints by the time it was done, and readily exploded when you tried to interact with it. The problem was that 1/3 of those constraints were extremely strong damped rotary springs. After tweaking the moments and damping values of the bodies, it became very stable however.

[sanotehu]

So basically it's quite ingrained in the assumptions of the solver. That's all right, as you say damping can fix much of the trouble. I wonder if it is something inherent in the problem or if it could be done the other way. I guess the other way would be to calculate spring and other forces, integrate velocities, do the contact solving and fix the velocities, then integrate the positions. Maybe there would be something in there to bite you, I'm going to think about it for a while and see if it could be done. I discovered chipmunk before I had to build a full solver (thanks), so I don't know all the ins and outs.

Thanks a lot for building chipmunk! The API is really well thought out, everything is pretty much the way it should be. Before I found chipmunk, I only knew about box2D, but I hate C++, so I learned all this stuff to try to build my own engine. Chipmunk really makes things easier. When I'm more familiar with it, maybe I'll submit some patches.

Thanks

[slembcke]

Time stepping in Chipmunk is highly inspired by this paper: http://graphics.stanford.edu/~fedkiw/pa ... 003-01.pdf In fact I used to do split elastic/collision iterations similar to how they suggested. Though I wasn't reintegrating the position and rerunning the expensive collision check each iteration. Eventually I realized that I could get just as good of an elastic response by moving the constraint pre-solve step before integrating velocities.

I'm glad that people like my APIs as I've spent a lot of time thinking about them. There are a couple places in Chipmunk where C++ classes or operator overloading would have come in handy, but overall ugh. I hate C++'s syntax. It seems like it's quite possibly the most complicated language ever made. C++ programmers can't even seem to agree about which features you should use and they keep cramming in more. I think I'll let the simplicity of Chipmunk's C implementation speak for itself. C also tends to be easier to optimize and bind to other languages (ones that I do want to write games in), which is a big plus for me.

Obviously feel free to experiment. What better is open source for right?