Awesome man. This is an excellent starting point for people. An instant classic. I’m definitely adding this to the short list of places to point people looking to do their own physics.
Very useful presentation. If you want to check out a 3D implementation, you can refer to Bullet Physics Engine. It uses the described iterative impulse method, and from today is includes the clamping on the accumulated impulse.
I need to read the bit about ‘accumulated impulse’ a bit better. I glanced at your code last night and was amazed to find that you are not only not randomizing your iteration order, but are solving a pairs contacts together. Madness! haha. You may have inspired me to put together a bit of a demo using both your techniques and my techniques. If your stuff is rock solid stable and my stuff is rock solid stable then with their powers combined they will be stable^2 of course!
Billy: yes, I don’t play with the constraint order. Doing so thrashes the cache too much and my experiments didn’t show much benefit compared to the cache hit. Aside from the demo, keep in mind a more optimized version where all the constraint data is packed together for streaming.
He solves a LCP for my understanding. What he basically does is solving blockwise for
J *W * JT * impulse = -J * v
What is the same like the PGS method, with the exception that the external forces are integrated in beforehand. Note that J * W * JT equals the collision matrix K (s. Mirtich for example). There was a discussion recently on the Bullet forum regarding the equivalence between sequential impulses and the Gauss-Seidel method…
Your physics simulator is awesome!
But…
How can they be added more shapes to the simulator? (circles, triangles, others)
Could you discuss about this theme please?
This really is fantastic stuff. I’ve just ported it to Java so I can hopefully use it in my next game. I’m going to attempt to add more shapes, starting with circles - hopefully this isn’t going to screw my mind up too much
The notice at the top of the source files says:
/*
* Copyright (c) 2006 Erin Catto http://www.gphysics.com
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies.
* Erin Catto makes no representations about the suitability
* of this software for any purpose.
* It is provided “as is” without express or implied warranty.
*/
That means that no matter how the source gets relicensed, you just need that one line, right? If I license it under my own proprietary license or under the GPL, so long as the copyright notice is there, it’s fine, right?
world.cpp: In member function ‘void World::BroadPhase()’:
world.cpp:112: error: passing ‘const Arbiter’ as ‘this’ argument of ‘void Arbiter::Update(Contact*, int)’ discards qualifiers
Since arbiters is a set, and sets have immutable members, it looks like Update needs to be made const, but obviously Update is doing things that const functions can’t do, right?
Has this code changed since the initial tutorial? Has anyone else encountered this problem?
i got it to compile iusing codeblocks with the MSVC++ toolkit 2003 compiler.
i initially tried using gcc (with codeblocks) and got:
Arbiter.h:24: error: `struct FeaturePair::::Edges’ invalid; an anonymous union can only haveon-static data members
switching compilers “fixed” that.. however, i’m still getting used to codeblocks so it might be that i haven’t got things setup properly.
Yes, just include the copyright line in any redistribution.
I’ve only built Box2D with MSVC++ 2003. However, both the errors above seem like a compiler problems:
- ArbIter is a non-const iterator.
- FeaturePair has no static data members.
Actually, I did some research on the set problem. Neither g++ nor MSVC++ are wrong when it comes to how each implements sets.
Effective STL by Scott Meyers says that sets can make use of immutable keys. Technically, only the parts relevant to ordering should be immutable, but an implementation can make the entire key immutable without violating the standard.
The safe and portable way to modify entries in a set:
ArbIter arb = arbiters.begin();
while (arb != arbiters.end())
{
// Erase key from set, modify it, then add it again.
Arbiter newArb((*arb).body1, (*arb).body2);
newArb.PreStep(inv_dt);
arbiters.erase(arb++);
arbiters.insert(newArb);
}
You basically create a copy of the key, modify it, then erase the original from the set and insert the new, modified version.
I know that the slides talk about removing bouncy simulations, but is it possible to tweak some parameters for the bodies to get the velocity to remain the same when it bounces off? If I turn off gravity after a body starts to fall, I was hoping to see boxes bounce up into the air at the same speed as it hit, but there seems to be some dampening. Most likely it is just a problem with not understanding the calculations being performed, but maybe the calculations are incompatible with what I am trying to do?
Box2D uses inelastic collisions, so there should be no bounce. The penetration recovery does add some bounce. Here’s a version that does not add bounce: http://www.gphysics.com/files/Box2D.zip
It is possible to simulate restitution by adding a target relative velocity to the velocity constraint.
The power point slides don’t make it clear why penalty force physics simulation is undesirable. From my naive perspective, the accumulated impulses makes the impulses act more like penalty forces.
Penalty forces say “push here and push hard,” without regard to the resulting motion.
Accumulated impulses are computed implicitly to satisfy motion requirements.
In other words:
Penalty method
force -> motion
Accumulated impulse method
motion -> impulses
Now the accumulated impulse method uses Baumgarte stabilization to remove position error and this seems like a penalty method. However, it still operates as a motion requirement that leads to an impulse.
March 20th, 2006 at 5:24 pm
Awesome man. This is an excellent starting point for people. An instant classic. I’m definitely adding this to the short list of places to point people looking to do their own physics.
March 20th, 2006 at 8:31 pm
Very useful presentation. If you want to check out a 3D implementation, you can refer to Bullet Physics Engine. It uses the described iterative impulse method, and from today is includes the clamping on the accumulated impulse.
Keep up the good work!
Erwin
http://bullet.sourceforge.net
March 21st, 2006 at 10:16 pm
This is fantastic. I’m definitely want to role some of these ideas into my own impulse engine. Thanks!
March 22nd, 2006 at 8:24 pm
I need to read the bit about ‘accumulated impulse’ a bit better. I glanced at your code last night and was amazed to find that you are not only not randomizing your iteration order, but are solving a pairs contacts together. Madness! haha. You may have inspired me to put together a bit of a demo using both your techniques and my techniques. If your stuff is rock solid stable and my stuff is rock solid stable then with their powers combined they will be stable^2 of course!
March 23rd, 2006 at 12:33 am
Thanks for the friendly feedback everyone!
Billy: yes, I don’t play with the constraint order. Doing so thrashes the cache too much and my experiments didn’t show much benefit compared to the cache hit. Aside from the demo, keep in mind a more optimized version where all the constraint data is packed together for streaming.
April 19th, 2006 at 8:47 pm
Nice article!
It’s a kind of amazing that you can do it without forming a LCP.
April 28th, 2006 at 1:03 am
He solves a LCP for my understanding. What he basically does is solving blockwise for
J *W * JT * impulse = -J * v
What is the same like the PGS method, with the exception that the external forces are integrated in beforehand. Note that J * W * JT equals the collision matrix K (s. Mirtich for example). There was a discussion recently on the Bullet forum regarding the equivalence between sequential impulses and the Gauss-Seidel method…
June 30th, 2006 at 11:16 am
Your physics simulator is awesome!
But…
How can they be added more shapes to the simulator? (circles, triangles, others)
Could you discuss about this theme please?
Thanks in advance!
July 1st, 2006 at 1:24 pm
I plan to add more shapes GDC next year. However, I would encourage you to give it a shot. It’s the best way to learn.
July 5th, 2006 at 8:28 am
Thanks!
My knowledge on physics is limited
I want to learn it but I miss the base
I will try
July 25th, 2006 at 10:29 am
This really is fantastic stuff. I’ve just ported it to Java so I can hopefully use it in my next game. I’m going to attempt to add more shapes, starting with circles - hopefully this isn’t going to screw my mind up too much
The port can be found at http://www.cokeandcode.com/phys2d. I’ll be releasing my version of the source as soon as I’m happy it’s right
Thanks for the great presentation!
Kev
July 27th, 2006 at 4:58 am
The notice at the top of the source files says:
/*
* Copyright (c) 2006 Erin Catto http://www.gphysics.com
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies.
* Erin Catto makes no representations about the suitability
* of this software for any purpose.
* It is provided “as is” without express or implied warranty.
*/
That means that no matter how the source gets relicensed, you just need that one line, right? If I license it under my own proprietary license or under the GPL, so long as the copyright notice is there, it’s fine, right?
July 29th, 2006 at 10:52 am
Does the code compile cleanly in VC++ (which is what I presume you used)? I get an error in g++:
ArbIter arb = arbiters.find(newArb);
(*arb).Update(newArb.contacts, newArb.numContacts);
world.cpp: In member function ‘void World::BroadPhase()’:
world.cpp:112: error: passing ‘const Arbiter’ as ‘this’ argument of ‘void Arbiter::Update(Contact*, int)’ discards qualifiers
Since arbiters is a set, and sets have immutable members, it looks like Update needs to be made const, but obviously Update is doing things that const functions can’t do, right?
Has this code changed since the initial tutorial? Has anyone else encountered this problem?
July 29th, 2006 at 7:00 pm
i got it to compile iusing codeblocks with the MSVC++ toolkit 2003 compiler.
i initially tried using gcc (with codeblocks) and got:
Arbiter.h:24: error: `struct FeaturePair::::Edges’ invalid; an anonymous union can only haveon-static data members
switching compilers “fixed” that.. however, i’m still getting used to codeblocks so it might be that i haven’t got things setup properly.
July 30th, 2006 at 3:47 pm
raigan: Yeah, I encountered that problem as well. Unions must be named in C++, which I guess some compilers allow.
July 31st, 2006 at 6:37 pm
ah, cool — i figured using the MSVC compiler was probably better anyway since the original was a vcproj..
August 1st, 2006 at 3:30 pm
Yes, just include the copyright line in any redistribution.
I’ve only built Box2D with MSVC++ 2003. However, both the errors above seem like a compiler problems:
- ArbIter is a non-const iterator.
- FeaturePair has no static data members.
August 4th, 2006 at 4:21 am
Actually, I did some research on the set problem. Neither g++ nor MSVC++ are wrong when it comes to how each implements sets.
Effective STL by Scott Meyers says that sets can make use of immutable keys. Technically, only the parts relevant to ordering should be immutable, but an implementation can make the entire key immutable without violating the standard.
The safe and portable way to modify entries in a set:
ArbIter arb = arbiters.begin();
while (arb != arbiters.end())
{
// Erase key from set, modify it, then add it again.
Arbiter newArb((*arb).body1, (*arb).body2);
newArb.PreStep(inv_dt);
arbiters.erase(arb++);
arbiters.insert(newArb);
}
You basically create a copy of the key, modify it, then erase the original from the set and insert the new, modified version.
August 4th, 2006 at 11:09 pm
Hey Erin, I ported your code to VB.NET
http://www.mdxinfo.com/resources/resources.rigidBodyPhysics/rigidBodyPhysics.rar
August 9th, 2006 at 6:58 pm
Thanks GBGames, I’ll fix that in the next revision.
August 25th, 2006 at 8:22 am
I know that the slides talk about removing bouncy simulations, but is it possible to tweak some parameters for the bodies to get the velocity to remain the same when it bounces off? If I turn off gravity after a body starts to fall, I was hoping to see boxes bounce up into the air at the same speed as it hit, but there seems to be some dampening. Most likely it is just a problem with not understanding the calculations being performed, but maybe the calculations are incompatible with what I am trying to do?
August 26th, 2006 at 6:56 am
Box2D uses inelastic collisions, so there should be no bounce. The penetration recovery does add some bounce. Here’s a version that does not add bounce:
http://www.gphysics.com/files/Box2D.zip
It is possible to simulate restitution by adding a target relative velocity to the velocity constraint.
September 19th, 2006 at 4:55 pm
The power point slides don’t make it clear why penalty force physics simulation is undesirable. From my naive perspective, the accumulated impulses makes the impulses act more like penalty forces.
September 19th, 2006 at 8:09 pm
Penalty forces say “push here and push hard,” without regard to the resulting motion.
Accumulated impulses are computed implicitly to satisfy motion requirements.
In other words:
Penalty method
force -> motion
Accumulated impulse method
motion -> impulses
Now the accumulated impulse method uses Baumgarte stabilization to remove position error and this seems like a penalty method. However, it still operates as a motion requirement that leads to an impulse.
October 18th, 2006 at 2:24 pm
Hi, nice work! I want to add some 2D physics to my game engine and this looks like a nice start. I have a few questions about the code though…
1) Why use STL set? Why not a linked list?
2) Why the weird pointer arithmatic in Arbiter.update() ? Surely
Contact* cNew = newContacts + i;
can be re-written as
Contact* cNew = newContacts[i]; ?
I’m a little rusty on C++
I hope you don’t mind me posting questions about the source to your blog?
Thanks
~ Clay
October 30th, 2006 at 4:41 pm
I’ve converted this to the D programming language
http://www.dsource.org/projects/arcgames/browser/trunk/physics/demo.zip
/me waits patiently for next years version which I hope will include polygons
December 11th, 2006 at 1:25 am
I made a quick fix that seems to compile under g++. The Makefile is horribly naïve, so if it doesn’t compile, you know why ;P
http://2-2-dihexanol.net/~nornagon/box2d.tar.bz2