Box2D Demo & Tutorial

kevglass
Posts: 7
Joined: Mon Aug 07, 2006 6:48 pm
Location: Davis, CA, USA
Contact:

Post by kevglass »

Ok, I'm definitely confusing myself now then. I've taken restitution code out all together and set up a scenario where I have two balls colliding. The first comes down at a velocity of (0,100) where it collides at a 45 degree angle with a second ball. At the collision I have the following debug displayed:

Code: Select all

[Body 'Ball0,0' [Vec 230.0,200.0 (304.795)] vel: [Vec 0.0,0.0 (0.0)] (0.0)]
[Body 'Cue' [Vec 250.0,166.6667 (300.46262)] vel: [Vec 0.0,100.0 (100.0)] (0.0)]
100.0,100.0
[Body 'Ball0,0' [Vec 228.73671,203.21344 (305.96762)] vel: [Vec -14.705896,41.17645 (43.723717)] (0.5212924)]
[Body 'Cue' [Vec 251.26329,170.11995 (303.43704)] vel: [Vec 14.705896,58.823547 (60.633926)] (0.49191874)]
100.0,104.35764
As you can see before the "cue" ball is moving at 0,100 and the target ball is 0,0. Afterwards the velocities are (-14.705896,41.17645) and (14.705896,58.823547). Now if I add the velocity vectors before and after the total is 100. However, the total length of the velocities is 104 and a bit - to me this indicates energy has been added.

I realise this is too low level to really be useful and I'm not expecting a solution. I'd just like to check that my evaluation of velocities is correct and it does indicate there is extra energy in the system?

EDIT: Ah ha - have I forgotten to factor in angular velocity? Hmm, even without this the total velocity probably shouldn't go up.

Thanks for the support so far :)

Kev
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

I didn't run the numbers, but what you should see for two dynamic bodies is:

Conservation of linear and angular momentum (no external forces/torques exist):
m1 v1 + m2 v2 = const
I1 omega1 + I2 omega2 = const

Energy should not increase (potential energy is constant accross the collision):
m1 dot(v1, v1) + m2 dot(v2, v2) + I1 omega1^2 + I2 omega2^2 <= orignal value
kevglass
Posts: 7
Joined: Mon Aug 07, 2006 6:48 pm
Location: Davis, CA, USA
Contact:

Post by kevglass »

Thanks so much, the numbers coming out were unintuitive - but having dumped out the resolution of the energy equation you've given me it seems energy is conserved across the whole system. Wonderful!

If you're Java enabled you can see the results of this in my version of Erin's demo box which now has an energy display :)

Java Webstart is here: http://www.cokeandcode.com/phys2d/phys2d.jnlp

Thanks to both of you for the great support!

Kev
SpongeBob
Posts: 2
Joined: Wed Oct 11, 2006 10:43 am
Contact:

Box2D Sponginess

Post by SpongeBob »

Erin,

Very nice GDC papers from this and last year, I really like the way you break things down into graspable components. I downloaded and played with the box2D demo and found the code intuitive.

But one thing that I did notice is the "sponginess" of the simulation and being a novice in the field of sequential impulse based physics, I have some questions:

1. In demo 5 when you shoot a rotating box down on the stack, things are quite bouncy. I guess this has to do with convergence so there is no way of alleviating this compression/sponginess of the stack other than shock propagation or ramping up he #iterations?

2. In your (or anyone else's for that matter) experience, how does your sequential impulse method hold up against guendelman et al in the previously mentioned aspect ( and overall performance aspects as well for that matter ) ?

I really like this approach as it seems very simple and clean and above all faster than guendelman et al (correct me if I'm wrong) so it would be really kick ass if one could tweak out the sponginess in a fast way that does not mean building contact graphs.


Thanks for your time.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

I implemented both algorithms and I found it much easier to add joints to Erin's approach than to Guendelman. I think others have made similiar experiences. Look at the paper of Weinstein and you see how expensive this can get. Maybe you want to look at the work of Jan Bender as well...

Cheers,
-Dirk
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

I managed to remove a lot of the sponginess using "split impulses." The idea is to prevent position correction from affecting the velocities. There is an updated demo for this:

http://www.gphysics.com/files/Box2D.zip

Also keep in mind that in some of the demos the bomb box is much heavier than the other boxes. Large mass ratios often lead to worse convergence, however it is not entirely unrealistic. Imagine stacking a 100kg box on top of a 1kg box. You would expect some stability problems.
SpongeBob
Posts: 2
Joined: Wed Oct 11, 2006 10:43 am
Contact:

Joints

Post by SpongeBob »

Dirk,

what problems did you encounter when trying to add joins to the guendelman approach?
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany
Contact:

Post by Jan Bender »

[SpongeBob]

I implemented the approach from Grundelman too. It was nice for collisions and contacts but as well as Dirk I had problems to use it with joints. The problem is the modified time step. Guendelman first resolves collisions, then updates the velocities, makes the contact resolution and at the end he computes the new positions of the bodies. In every physics lesson you learn that the position of a body after a time step is

c(t+h) = c(t) + h*v(t) + 0.5 * g *h^2

with the time step size h and gravitation g. But Guendelman has something like this in the end:

c(t+h) = c(t) + h*(v+h)

This is not physically correct and leads to wrong positions. The problem with joints is that if you use an impulse-based approach like myself you change the velocities of the bodies in order to satisfy the joint constraints. But afterwards the contact resolution changes the velocities again. So you can't satisfy a joint constraint in this way. Maybe you want to compute the impulses parallel to the contact resolution but in this case I had the problem that a collision changes the velocity of a body instantaneous but a joint must be kept together for a whole time step. So for me it were too many problems just to get a physically incorrect solution.

Jan
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

I doubt that this is the reason. When I implemented the Guendelman approach I alway relaxed both joints and contacts together (also for the collisions). Something like this:

// Collision phase
for ( 5 iterations )
{
SatisfyConstraints();
ResolveCollisions();
}


// Contatct phase
static const float e = { -0.9, -0.8, ... , 0.0f };
for ( 10 iterations i )
{
SatisfyConstraints();
ResolveContacts( e );
}

The problem in my opinion was that you need the negative ascending epsilons ( -0.9 -> 0.0 ) in the contact phase to get a better sampling at the manifold and make the simulation converge. That means that you don't correct the full velocity error for the contact constraint which gives you more a Jacobian like convergence as opposed to the much better Gauss Seidel convergence. So I ran into problems with ragdolls lying on the ground. If you are for speed I recommend Erin's approach - if you are more into robotics you can look into Jan's method.


HTH,
-Dirk
John Schultz
Posts: 23
Joined: Sat Aug 06, 2005 7:48 am
Contact:

Post by John Schultz »

I found that if I changed velocity for position resolution, I could eliminate the need for iteration of resting contacts, stacks, etc., and also eliminate springiness/sponginess. The trick is to make sure that the change in velocity preserves total kinetic energy. Moving objects without correcting energy will result in accumulation of energy error, especially for stacks, making the system less stable. For example, moving an object upward without correcting its velocity will result in accumulated potential energy over time, adding energy to the system, along with an effective artificial downward velocity.

I use a hybrid Verlet deformed tetrahedral approach for computing new positions and correcting kinetic energy: http://www.brightland.com/Physics/inex.htm , for everything else a traditional rigid body integrator is used.

Other ways of correcting for kinetic energy are possible: here's a simulator using impulse-based dynamics with momentum (and thus kinetic energy) correction for contacts: http://phyar.cn.googlepages.com/spe.html, http://www.gamedev.net/community/forums ... _id=418376 . Note the lack of springiness in the stacks (not clear if they are iterating, though the simulation runs reasonably fast).

Tracking and making sure kinetic energy is correct helps a simulation look more realistic as well as promoting stability (striving to make the simulation 'Energy Accurate'). Moving objects without correcting for (effective) change in energy is physically incorrect and also leads to unstable and inaccurate simulations (requiring iteration for stability, etc.).
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

John,

I'm curious about your algorithm. Here are a few questions:

1) What is the particle model used for (just for correcting KE)? How do you compute contact points (RB or particle)? How do you integrate velocities (RB or particle)? How do you handle overlap resolution?

2) What does it mean to correct KE when collision and contact are inelastic?

3) Do you solve one contact at a time?

4) How stable is a vertical stack of 4 1mx1mx1m boxes at 30 Hz with 9.8m/s^2 gravity and no damping? Use a friction coefficient of 0.3. Can you start the boxes with a small vertical offset and some random horizontal shift?

5) Do lower boxes feel the weight of upper boxes? Will a diagonal stack fall over correctly?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Me too :-)

How does your algorithm fits into Erin approach where he applies sequential impulses? The algorihm adds enery through Baumgarte stabiliaztion and when using splitting impulses through gaining potential energy. So when I resolve a contact or a joint and stabilize the penetration or drift I have to scale my overall energy between the two bodies to account for energy conservation?

So if a box falls to the ground during the interval from t1 and t2 it gains kinetic energy. When I push the box up I re-add aditional potential energy to the system. So you state that this accumulates even though for an elastic collision due to contact the system looses quite some energy?

Taking Jacobsen cloth as another example. Lets say we advance the system using the velocityless Verlet integration scheme and then sequentially satisfy constraints through projection. How would you correct the energy here?


Cheers,
-Dirk
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany
Contact:

Post by Jan Bender »

[Dirk]
// Collision phase
for ( 5 iterations )
{
SatisfyConstraints();
ResolveCollisions();
}

// Contatct phase
static const float e = { -0.9, -0.8, ... , 0.0f };
for ( 10 iterations i )
{
SatisfyConstraints();
ResolveContacts( e );
}


Okay, but if you handle constraints like this you have to solve them twice. Since you just use 5 or 10 iterations this will be fast enough but as you already know I am a fan of exact solutions :wink:

So in my work collisions are resolved at the same time as the velocity constraints and resting contacts at the same time as the position constraints.

Jan
John Schultz
Posts: 23
Joined: Sat Aug 06, 2005 7:48 am
Contact:

Post by John Schultz »

Erin Catto wrote:John,

I'm curious about your algorithm. Here are a few questions:

1) What is the particle model used for (just for correcting KE)? How do you compute contact points (RB or particle)? How do you integrate velocities (RB or particle)? How do you handle overlap resolution?

2) What does it mean to correct KE when collision and contact are inelastic?

3) Do you solve one contact at a time?

4) How stable is a vertical stack of 4 1mx1mx1m boxes at 30 Hz with 9.8m/s^2 gravity and no damping? Use a friction coefficient of 0.3. Can you start the boxes with a small vertical offset and some random horizontal shift?

5) Do lower boxes feel the weight of upper boxes? Will a diagonal stack fall over correctly?
Erin, Dirk:

The particle model was originally used for the complete simulation of rigid bodies. Using Jacobsen's concepts, a tetrahedron is embedded in a rigid body. All four particles have the same mass, 1/4 of the total RB mass. The tetrahedron is iteratively scaled in x, y, and z until the particle inertia tensor matches the desired 'ideal' inertia tensor (off diagonals zero). We now have enough information to integrate a rigid body using either the Verlet tetrahedron, or via a standard Baraff style momentum-based integrator (Note: in the current system, the tetrahedron is uniform and not scaled to match the actual RB inertia tensor (Verlet particles are not used for the integration step). This was required for long, thing objects to be stable).

I use only convex hulls in my simulation, where vertices, edges, and planes are stored. Terrain contacts can use just the vertices, while RB-RB contacts use just the edges and planes. Overlap results in 'virtual' points being found inside a convex hull, which are projected to the proper surface.

The displacement required to move the virtual point to the collision hull surface is applied to the tetrahedron using a weighted barycentric method (see Jacobsen's paper). Since the virtual points are computed in barycentric coordinates of the tetrahedron, each projection+distortion effects how far subsequent virtual particles must be moved. These concepts are explained in more detail in Jacobsen's paper. One contact is solved at a time. Impulses are applied to the RB sequentially, whereby the total momentum is updated after each contact is processed. The same concept is used for friction.

Before the displacements are applied, the total kinetic energy of the particles are computed using the following methods from http://www.brightland.com/Physics/index.htm :

getTotalKineticEnergy() is called and the total KE(before) is stored before displacement.
After displacement, getTotalKineticEnergy() is called again KE(after), followed by setTotalKineticEnergy() to correct the KE. Note in the example code on my website, I allow energy to be lost between RB?s (even gained slightly), which helps with stability. The current code also does no KE correction for objects on the terrain. The current implementation works reasonably well at 100Hz with the objects in my game (9.81m/s^2 gravity, ~1m^3 boxes, etc.). Older versions that did not reset the tetrahedron each step were stable at 30Hz (though slightly springy unless iteration was used).

The lower boxes do feel the weight of the upper boxes, and if the base box is shot on edge (in my demo), the upper boxes will rotate realistically.

http://www.brightland.com/ac/video/KE_mod.mp4 (h.264)

The demo isn?t perfect (note a box sleeping when it should not be, some jitter between boxes (OK as no iteration is used)), but it?s good enough for my game. Since I have not seen much discussion on kinetic energy tracking/correction/modification, I figured it might be helpful to put the ideas out there and see if others can improve on them.

Using KE correction, a bouncing Verlet tetrahedron can be made 100% elastic. KE correction for cloth could be applied using the same principles. Tracking and modifying KE can help debug and stabilize a physics engine. The 'perfect' physics simulator would be Energy Accurate: no energy is arbitrarily lost or gained. It's relatively easy to make a single bouncing rigid body Energy Accurate ( http://www.brightland.com/ac/amazingcur ... s_prev.htm ); creating Energy Accurate stacks, constraints, etc., is much harder.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Hey John,

thanks for the reply. I know your website and examples and they really look great. Also thanks for posting the link to the paper. Though I have the Hairer books I didn't know these papers.

I am also looking into the Jacobsen method and I want to share some thoughts that you maybe can help me with. Even though the integrator is called "Velocity Less Verlet" it defines a velocity implictly through x(t) - x(t - dt). So when you project the positions according to the position constraints as done in all papers I am aware of you ignore the velocity constraints. Examples:

1) Think of a simple particle falling onto the ground. At time t it has the height h. At time t + dt it is penetrated into the ground. The next you do is to project the particle onto the surface. If you wanted a plastic collision the velocity now should be zero, which is not satisfied since x(t) - x(t-dt) != 0. So if I wanted to model any form of collision I have to adjust the "old" position as well.

2) Take the simple distance constraint where we require two particles to stay some constant distance apart. After the integration the positions are corrected to meet the constraint. As above the distance constraint also requires the relative velocity along their difference vector to be zero which is not considered, so I wonder if it feasible to adjust the old velocity here as well. I am thinking of this because for cape or skirt like cloth which must follow some keyframed vertices the displacement off these vertices adds kinetic energy to the system and you clearly see (e.g. stretchyness) that the velocity takes to long to propagate through the system. Also think of a skirt being hit by a knee. I think for this case you must adjust the velocity (again the old position) such that it equals the velocity on the point on the knee where it was projected onto?

Do you think these velocity adustments are related to your energy considerations? What is your (or anybody elses) opinon on the mentioned issues here? The Verlet scheme seems to help you with the velocities a bit, but it might be a good idea to consider velocity constraints at some places as well. For simple flags you can definetely spare them, but for RB or more complicated cloth it might be a good idea. Any comments on this are welcome!


Cheers,
-Dirk
Post Reply