Chipmunk Release 2

[Skorche]

I wasn't planning on releasing this today, but the recent interest in the other thread inspired me to finish up the loose ends.

Download: ChipmunkRelease2.tar.gz (http://epoxy.morris.umn.edu/~lembckesd/ChipmunkRelease2.tar.gz). (Demo, source, static lib and documentation)
Online copy of the docs here (http://epoxy.morris.umn.edu/~lembckesd/chipmunk-docs.html).

Changes:

Joints!
Vastly updated documentation.
Added cpDampedSpring()
Collision shape instantiation has changed (for the better). See the documentation for details.
Spaces no longer have a staticBody field. You have to create your own static body.


Once again, be warned that this isn't complete software. I'm trying to keep the sweeping changes to a minimum (like the change to the collision shape instantiation :shock: ), but I make no guarantees. Though that also means that this would be a good time to be critical of my API.

[maximile]

Those four bullet points in the Overview section make it much clearer to a newbie, so thanks. I'm looking forward to playing with it.

[Duane]

I'm quite impressed; I'm gonna use this for something. I'm new to physics engines; is there a tutorial somewhere...?

[Skorche]

I'm quite impressed; I'm gonna use this for something. I'm new to physics engines; is there a tutorial somewhere...?

No, not yet. It's been brought up several times, so I'll probably get around to it sometime. In the mean time, you can look at the demo application source code. It's uncommented though.

Also, I've somewhat avoided doing any optimization up to this point. Partly on purpose so that I wouldn't make any stupid decision that would limit the functionality in the name of a minor speed gain. I did some Shark-ing today, and after about two hours I had lowered the running time of 5000 steps of the box stacking demo by more than 30%!

[Joseph Duchesne]

Hmm... would a change log be too much to ask for? :P It's a bit tricky to fix up my version 1 code to work with version 2 with nothing more to go on than GCC errors, the docs, and guesswork :)

Plus, I find writing change-logs to be oddly satisfying...
Thanks!

Edit: There, my code is now working again :P it didn't actually take that long.

[OneSadCookie]

svn diff :p

[Skorche]

Hmm... would a change log be too much to ask for? :P It's a bit tricky to fix up my version 1 code to work with version 2 with nothing more to go on than GCC errors, the docs, and guesswork :)

Plus, I find writing change-logs to be oddly satisfying...
Thanks!

Edit: There, my code is now working again :P it didn't actually take that long.

Yeah, I realized that a little to late that I needed a change log. I had to sift through the diffs to remember everything that I had changed. I'll be more careful about that in the future.

[Joseph Duchesne]

Thanks a lot :), I realize that this project is a lot of work and I'm happy to use Chipmunk Physics regardless of its documentation state :P ... I'm remembering Processing changing versions and having 200 programs suddenly not compile :P The changelog was helpful there :P In this case, I suppose since nobody really has done much with Chipmunk Physics yet, changes like this are rather negligible in the grand scheme of things.

[Skorche]

Once again, instead of sleeping, I worked on Chipmunk. As per request, I've made a short introductory C tutorial. It doesn't get into any of the really cool features, but it's a start.

http://epoxy.mrs.umn.edu/~lembckesd/MoonBuggyTutorial.tar.gz

Time for sleeping. :bored:

[maximile]

Awesome! That makes everything much clearer. I was a little confused at first about not adding staticBody to the space, but adding all the segs. But now I can see that it makes sense. So does that mean that you could, say, have two spaces, and have a collision shape in one that's attached to a rigid body in another?

Multiple would be where it gets most interesting for me, because I can imagine myself having a foreground, background and an action plane, and each one would need different gravity settings to simulate how close they are to the 'camera'. Would there be any issues with that?

One more thing; how does the damped spring work with the pin joint? If the wheels are already 'pinned' to the chassis, I don't see how the damped spring forces can work. Or am I thinking too literally?

As always, it's looking very awesome.

[Skorche]

... So does that mean that you could, say, have two spaces, and have a collision shape in one that's attached to a rigid body in another?

Not really. When updating the space, it goes something like this:

Update the velocity of all rigid bodies. (calls cpBodyUpdateVelocity())
Apply collision and joint constraints.
Update the position of the rigid bodies. (calls cpBodyUpdatePosition())


Adding rigid bodies to more than one space would be problematic as they would get updated twice. Attaching a rigid body to a shape in another space could also be problematic because you want the collisions to be processed before the positions are updated.

However, you could keep the body outside of the space and call the cpBodyUpdateVelocity() before stepping the space, and call cpBodyUpdatePosition() afterwards. That's really all the space does with them anyway.

Using spaces as layers is an interesting idea. It wouldn't be too hard to add the ability to step a number of spaces together, allowing them to share rigid bodies and collision shapes. I'll look into it.

Multiple would be where it gets most interesting for me, because I can imagine myself having a foreground, background and an action plane, and each one would need different gravity settings to simulate how close they are to the 'camera'. Would there be any issues with that?

You can have as many spaces as you want, but like I said above, right now it's not a good idea to share objects or cross link between them.

One more thing; how does the damped spring work with the pin joint? If the wheels are already 'pinned' to the chassis, I don't see how the damped spring forces can work. Or am I thinking too literally?

I use the term pin joint because that's what I've heard it called before. The name is somewhat misleading though. Essentially, the pin joint can be thought of as a mass-less rod that is attached to the rigid bodies using swivels. It keeps the anchor points a certain distance apart. In the moon buggy tutorial, a pin joint is created that keeps the center of the wheel a certain distance away from the center of the chassis.

[Joseph Duchesne]

I have a quick question:
I have a cpSpace in my game that stores all of the level data in static cpSegmentShapes:

void addLevelToPhysics(level *l)
{
cpSpaceFreeChildren(space);
cpSpaceRehashStatic(space);
cpShape *shape;
int i,j;
for(i=0;i<l->numObjects; i++)
{
for(j=0;j<l->objects[i].exoPointsCurrent-1;j++)
{
shape = cpSegmentShapeNew(staticBody,cpv(l->objects[i].exoPointsRotated[0][j],l->objects[i].exoPointsRotated[1][j]), cpv(l->objects[i].exoPointsRotated[0][j+1],l->objects[i].exoPointsRotated[1][j+1]));
shape->e = 0.5; //elasticity
shape->u = 0.6; //coefficient of friction
cpSpaceAddStaticShape(space, shape);
}
j=l->objects[i].exoPointsCurrent;
shape = cpSegmentShapeNew(staticBody,cpv(l->objects[i].exoPointsRotated[0][0],l->objects[i].exoPointsRotated[1][0]), cpv(l->objects[i].exoPointsRotated[0][j],l->objects[i].exoPointsRotated[1][j]));
shape->e = 0.5; //elasticity
shape->u = 0.6; //coefficient of friction
cpSpaceAddStaticShape(space, shape);
}
}
Unfortunately when the level is over and the next one is loaded, the game dies:
MadTak has exited due to signal 4 (SIGILL).
Of course I don't think I should be using:
cpSpaceFreeChildren(space);
cpSpaceRehashStatic(space);
in the way that I do. What should I call to clear everything from the space and start over? (hopefully with 100% less quitting and no memory leaks :P)

[Skorche]

cpSpaceFreeChildren() is a bit of a misnomer in this case I guess. I wrote it assuming that it would be called to free the child objects when destroying the space. It doesn't actually remove them, so it effectively voids the space. I should say that in the documentation.

Just free the space and its children and create a new one.

[Joseph Duchesne]

Awesome, the level is now correctly passed to Chipmunk :) Illustrated here using your functions for drawing everything from the demo's main.c (red lines)
http://temp.duodec.net/collision.jpg

Unfortunately, my data for the moving objects will need to be redone because my original collision detection code didn't care about winding order. (most are wound correctly, but some aren't).
Edit: excuse the poor jpg'ing
Edit #2:
A useful feature for games would be a ray cast function. Example:

void cpRayCast(cpSpace *space, cpVect start, vpVect end, int onlyFirstHit, cpBody *objects);

Where:
space is the space
start and end define the ray
onlyFirstHit is a boolean that allows you to specify if you want all of the hits on the line or just the first one
objects is simply an array of all of the cpBody objects that are hit by the ray, in order of closest to start to closest to end

This could also be implemented through the collision return function
void cpRayCast(cpSpace *space, cpVect start, vpVect end, int ID);

Also useful in a function like this would be some way to find out both the intersection as the ray goes in, but also the intersection point as the eay goes out.

I'm just dreaming of course, but this would be great for small weapons, beam cannons and other projectiles that otherwise don't need to interact with the objects in any way.

[Skorche]

Haven't had a whole lot of time to work on Chipmunk lately, but I've gotten a few things done:

Performance improvements: I mentioned this a couple of weeks ago.
Collision layers: Shapes now have a layer bitmask. Objects don't collide unless they are in one or more of the same layers. Transitioning between layers is as simple as flipping bits.
Collision exclusion groups: Shapes also now have a group id. Shapes in the same group don't collide with each other. You could use this to keep the parts of a single ragdoll from colliding with each other, but allow them to collide with other ragdolls. Doing this with collision pair functions would require you to define several new functions for each ragdoll.
Thick segments shapes: Segment shapes now take an additional radius parameter when instantiating them, allowing you to have nice rounded capsules. (Still no plans to allow seg/seg collisions, sorry.)
Re-definable precision: All floating point numbers now use the cpFloat type. If for some reason you want to use doubles instead, you can simply edit the chipmunk.h header and recompile.


I was also thinking about how to implement ray-tracing. It would be fairly simple to instantiate a segment shape and use Chipmunk's collision detection to build a list of all shapes that it intersects in no particular order. This would be very suboptimal for long diagonal segments, but would work. Later if I'm ambitious, it could be re-implemented to actually ray-trace through the spatial hash, and return the shapes in order. The behavior would be backwards compatible this way.

Anyway, I'll have to update the documentation some more and make another release. Maybe I'll do that this weekend. There's only two fairly minor changes to the API this time, so you don't need to worry too much.

[Joseph Duchesne]

Great work! :)
All of the new features will be quite useful to game developers. After using your library a bit more it continues to amaze me how perfectly suited to 2D game programming (specifically, my 2D games) it is :D 99% of the time I think "Wouldn't it be great if" and check the manual only to find "yay! It's already implemented."
Also, it about 20 hours to get Newton Game Dynamics working at the level Chipmunk Physics was in half an hour ^^.

The only problems I see with the proposed "ray trace" is that it wouldn't collide with other line segments, and it would be quite slow for a lot of them. Since I would like to use something like this for fast moving bullets and I hope to have lots of fast moving bullets this could be a problem. Other than that the method would be good.

[Skorche]

The only problems I see with the proposed "ray trace" is that it wouldn't collide with other line segments, and it would be quite slow for a lot of them. Since I would like to use something like this for fast moving bullets and I hope to have lots of fast moving bullets this could be a problem. Other than that the method would be good.

Hmm, that's a good point. Hadn't though about that. I guess it wouldn't be that hard to actually implement real ray tracing, but it would take time that I don't really have. :\

[beepy]

I've got a handful of questions. I'm looking to adding Chipmunk to my project, PlayKode, and I want to present the simplest API to the user, and to make the functionality as self-evident as possible.

I'm confused in general about the matrix of possibilities with the creation of shapes and whether or not they are added to a body, to a space, and to a space as a static shape.


is there ever a time you would want to add a shape to a body which is in a space, but not add that shape to the space?
is there ever a time you would add a static shape to a body, or create one without adding it to a space?
if it's necessary to reset all bodies' forces every step (gleened from comments in Moon Buggy tutorial) to prevent bodies from exploding, is there any reason not to do this?
what's the functional difference between cpBodyApplyForce and cpBodyApplyImpulse? Applying force to a body once seems to have effect across steps, unless you reset the body's force each step, as above. Then it seems functionally identical to applying an impulse.


Thanks! Chipmunk looks great and like almost exactly what I need.

[Skorche]

I should probably add some information to the documentation about what exactly spaces do with their bodies and shapes. I think that that has confused people a bit.

To answer your questions:

No, shapes are largely useless unless you add them to a space. It can be useful to keep a body out of the space however. This will allow you to integrate the position/velocity as you see fit. In the moon buggy tutorial, I don't add the static body to the space. If I did, it would fall under the influence of gravity at the same speed as the buggy.
Shapes are just shapes. They are only differentiated as a "static" if you add it to a space as a static shape. Static shapes are simply an optimization so that shapes attached to bodies that aren't moving (such as level geometry) aren't rehashed every step.
Yes, I thought it would be useful in the case where you don't want to set a force every frame. If you always want an body to have a certain force/torque applied to it, then set it once and forget. The downside is that if you are accumulating forces every step and forget to reset the force, your object will explode, and it might not be obvious why.
Impulses in this case are referring to ideal impulses, in instantaneous change in momentum. Essentially v += j/m, where j is the impulse. You'd apply impulses for actions that would produce instantaneous (or near instantaneous) reactions such as a cannon firing.


I do have code for a Ruby extension in the main source folder. It might be useful for you to see how I wrote my object initialization code.

[beepy]

I think what I'd like to do is provide a simplified interface, where you can create two kinds of bodies, either "normal," or say "immobile" bodies, in a single call. Behind the scenes, immobile bodies wouldn't get added to the space, and their shapes would be added to the space as static.

Does that seem reasonable and not overly restrictive?

[Skorche]

No, I think that's a good way to simplify things. I used to do something similar to that where every space would have an immovable body associated with it. Adding a shape as static to the space would also attach it to the immovable body. It was easier, but a bit more restrictive.

Also, if you don't allow access to the static body, it would pretty much guarantee that you would never have to worry about the static spatial hash getting out of sync with its shapes. That would be a very confusing problem for inexperienced users.

[beepy]

What's the recommended way to calculate the force of a collision? Chipmunk is already doing the work obviously. If I'm trying to, say, estimate damage two cars crashing into each cause each other, what's my best bet during the collision call back?

[Skorche]

What you want is the relative kinetic energy of the two objects, that will give you a reasonable estimation of collision damage. I'm sure that I have the formula written down in my notebook of useful equations, but that notebook is currently about 2000 miles away. Shouldn't be too hard to figure out though.

[beepy]

Isn't it the difference in their actual force vectors? I was actually hoping that since Chipmunk was already calculating the force that gets applied to each body, and knew about elasticity, there might be something to tap into.

Yet another question: I assume that a single body with multiple shapes would receive multiple collisions in a single pass when those multiple shapes simultaneously collide with another single body.

For example, suppose you have a lunar lander type game, and the lander body has two separate landing gear shapes at the bottom. If it is perpendicular to a perfectly horizontal landing shape, it will receive two collisions, one for each landing gear.

If our lander could accumulate damage, we wouldn't want the damage applied twice when hit the ground on two landing gear and not just one -- so it'd be necessary for the lander to keep track of whether or not it had processed a given collision with a given body for every cycle.

Does that make sense? I've got it working with my project, so I should really just try it and confirm so I know that I'm not way off base, but I feel like the collision callback should work on a per-body basis, rather than a per-shape basis. Instead of two shapes and a list of contact points, the callback would get two bodies and a list of arbiters (which contain the contact points and shapes). (And in that case, the bodies would benefit from a void *data field instead of having it in the shape.)

Also I wanted to confirm that Chipmunk is completely reentrant, so that multiple spaces could be run from multiple threads simultaneously. It looks like the only globals get written to once on initialization, so I believe that it is reentrant.

Thanks, I appreciate it.

[beepy]

I just confirmed what I had assumed above, that first, a single body with multiple shapes does receive multiple collisions for each shape when those multiple shapes simultaneously collide with another single body, and second, Chipmunk is doing the right thing with its physics under those conditions (a bouncy lander doesn't bounce twice as high when its two landing gear hit simultaneously vs. a lander with one landing gear). So Chipmunk "knows" to consider multiple shape collisions as a single collision between two bodies, so my proposal to have the collision call back work on a per-body (rather than a per-shape) level seems reasonable.

What do you think?

Of course, if I wasn't lazy I could spend more time on Chipmunks internals and try to do this myself.

[Skorche]

I'm still pretty sure that the amount of damage done is going to reflect the amount of energy dissipated in the collision. Though as I'm vacation until tomorrow, I'm a bit to lazy to back that up until then. :p Either way, converting the collision impulse (force) into kinetic energy is pretty simple.

Chipmunk solves for the collision impulses iteratively, so callbacks here would be worse than useless. However, all final collision impulses are cached to be reused as a starting point for the solver if the collision reoccurs within a couple of frames. (Erin Catto's contact persistence idea.) The problem is that they can only be efficiently retrieved by supplying a shape pair.

While working with collisions on a per body basis could be useful in some situations, I feel that working on a per shape basis is much more powerful. Shapes have their own independent material properties, bodies don't. Also, that would be really difficult to implement as collisions between shapes are processed in no particular order. Grouping collisions by body couldn't be done as efficiently.

However, you could implement the functionality yourself fairly painlessly yo using a set and the user data pointer of the shape structure. Point all of the shapes for a given body at the same set, and in the collision callback add the bodies involved to each other's collision set. Then later iterate over the bodies to determine collisions.

Or, an even crazier idea that I just thought up... The array of cpContact structures passed to the collision callback is the very same place where the impulse caching takes place. If you store the pointer somewhere until after the call to cpSpaceStep() returned, you would find that the jnAcc, and jtAcc fields for each contact would be filled in with the accumulated normal and tangential impulse components. You could use these to sum up the total impulse applied to a shape or rigid body. (You could also use this information to find out if an object is getting crushed.) The only gotchas are that the contact point array may be freed on the next call to cpSpaceStep() or if your collision callback returns 0. I think this is the way to go though.

I appologize for this post getting less and less organized as I write it. :p

[Najdorf]

Wow, Skorche that's totally amazing!!

I didnt think something like this was possible :love:

*Najdorf hangs a poster of Skorche in his bedroom*

[beepy]

Or, an even crazier idea that I just thought up... The array of cpContact structures passed to the collision callback is the very same place where the impulse caching takes place. If you store the pointer somewhere until after the call to cpSpaceStep() returned, you would find that the jnAcc, and jtAcc fields for each contact would be filled in with the accumulated normal and tangential impulse components. You could use these to sum up the total impulse applied to a shape or rigid body. (You could also use this information to find out if an object is getting crushed.) The only gotchas are that the contact point array may be freed on the next call to cpSpaceStep() or if your collision callback returns 0. I think this is the way to go though

Thanks that sounds like just what I was looking for.

I think I found a bug -- though maybe I'm just abusing chipmunk. Is there an additional step you have to take to add a body to a space that is in motion?

If you have a stack of bodies, then you create more bodies somewhere else, weird things can spontaneously happen in the stack of existing bodies -- they can randomly jump into the middle of each other. This seems to only happen after you have previously created, used, and destroyed a space, but that detail could be coincidence.

To illustrate, I modified demo #3, so that there is a ground shape (so the pentagons stack up) and the pentagons get created 20 at a time, every 10 seconds. After about the third set of 20, the weirdness happens. The modification is simple but here it is: http://biggerplanet.com/sandbox/Demo3.c

[maximile]

I've come across this, without destroying a space. I had it so that whenever you click the mouse a circle is added. But after a few were in there, occasionally clicking the mouse would cause two circles to pull into each other and then vibrate lots. If it helps, I'll post my code when I find it. I didn't report it before because I assumed it was something I had done wrong.

[Skorche]

That's definitely a bug. It seems to be a problem with the contact persistence. Intermittent bugs are never fun to find. :(

I wonder why I've never come across this before?

[Skorche]

Took me a while, but I figured out what the problem was and have the fix.

EDIT: found a better solution that properly maintains the collision cache

Inserting new shapes can change the order that old shapes are collided in. If the order tow colliding shape are specified in is flipped when retrieving the cached collision information for then, the collision normals will be backwards from the shape ordering. Effectively making the objects pull into each other instead of pushing apart.

To fix it, find the queryFunc() function in cpSpace.c, and add the following line immediately before the call to cpArbiterInject(). (should be near line 362)
arb->a = a; arb->b = b;

[Skorche]

Oh, I never answered the question about threading. I had threading in mind while creating Chipmunk, and spaces can be safely threaded.

The only globals are for performance tweaking, and should only need to be set on a per application basis if at all.

[beepy]

Hooray! That did indeed fix it. Thanks for your speedy response!