Chipmunk 6.0 Beta

Official forum for the Chipmunk2D Physics Library.
Post Reply
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Chipmunk 6.0 Beta

Post by slembcke »

Oh, and one thing to point out -- cpBodyActivate() when called in a collision or query callback delays some of the body activation (moving the shapes around) until the end of the step or query. So it is only safe to use your workaround outside of any callback.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
dieterweb
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany
Contact:

Re: Chipmunk 6.0 Beta

Post by dieterweb »

So to be save I have to remove a shape from the space before I can change its body? I wonder if this is a big performance problem as we change the bodies of hundreds of shapes each frame.

EDIT: I tried it and the performance hit is too big. We cannot remove and add the shapes every time we change the body.

What we are doing now is for shapes going from static to dynamic:

Code: Select all

cpSpatialIndexRemove(_space->staticShapes, shape, shape->hashid);
shape->body = body;
cpSpaceAddShape(_space, shape);
and for others (there is no dynamic to static):

Code: Select all

shape->body = body;
shape->next = shape->body->shapeList;
shape->body->shapeList = shape;
This is MUCH faster. Can you foresee any problems with this approach? It seems to run ok. We never reuse old bodies. When something changes in our space all related shapes get a new body. As I wrote in an earlier post we cannot free this old bodies as we get a bad access in this case.
Last edited by dieterweb on Thu May 26, 2011 10:34 am, edited 3 times in total.
Visit our game Blog: [url]http://zombiesmash.gamedrs.com[/url] or follow us on twitter: [url]http://twitter.com/zombiesmash[/url]
dieterweb
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany
Contact:

Re: Chipmunk 6.0 Beta

Post by dieterweb »

I also made some more tests about the crash when trying to free old, unused bodies. There are still arbiters in the space->arbiters array that point with arbiter->body_a or arbiter->body_b to this old body. But there are no more shapes attached to this body. Can you tell me for what the different arbiter lists/hashes of the space are?
Visit our game Blog: [url]http://zombiesmash.gamedrs.com[/url] or follow us on twitter: [url]http://twitter.com/zombiesmash[/url]
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Chipmunk 6.0 Beta

Post by slembcke »

You are changing hundreds of bodies each frame? What exactly are you doing, there might be a better way to do that.

I also don't think you are really going to save that much performance by avoiding the add/remove. Performing a remove, set, add will do all of these things:
1) If the original body was sleeping, wake it up. O(n*m + p*c) where n is the total number of sleeping bodies, m is the number of sleeping bodies in the same group as the original and p is the number of shapes to change from sleeping to active status, c is the cost to remove or add a shape to a spatial index a moderate but constant cost for both AABB trees and the spatial hash.
2) Remove the shape from the linked list of shapes added to the original body. -- O(n), but generally a very small n
3) Filter the entire hashset of cached arbiters to remove the collision pairs involving that shape. -- O(n) where n is the number of unique collisions in the last 3 frames.
4) Remove the shape from the spatial index. -- O(1) for trees and spatial hashes
5) If the shape is static, a query must be performed to wake up all shapes touching the static shapes. -- O(?) Hard to say for sure, but potentially expensive.
6) Set the new body.
7) Activate the new body if it was sleeping -- O(n*m + p*c)
8) Add the shape to the new body's linked list -- O(1)
9) Update the geometry and bounding box of the shape. O(n) for polygons, O(1) for circles and segments.
10) Insert the shape into the spatial index -- O(1) See #4
11) If the shape is now static, a query must be performed to wake up all shapes touching it. -- O(?)

The "fix" I had a couple days ago only did 2, 6, and 8. I thought that would be good enough. After looking more closely yesterday, I realized that to do it correctly I would need to do all of that. Only steps 4, 5 and 10 and 11 could be skipped in specific conditions. Of those, only 5 and 11 can be expensive, but only apply to static shapes anyway. So I don't think you are really saving yourself that much CPU time by avoiding performing a remove, set, add sequence. This was all much simpler before I added the sleeping feature. :-\ 6 out of those 10 steps are to keep the data used by the sleeping algorithm valid.

Anyway, it's impossible to do all of that without a reference to the space (static and rogue bodies don't keep one), and it's impossible to make it safe to do all of that in a callback.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
dieterweb
Posts: 176
Joined: Fri Feb 27, 2009 7:12 am
Location: Germany
Contact:

Re: Chipmunk 6.0 Beta

Post by dieterweb »

We are simulating around 2000 shapes and are most of the time at 60fps on an iPhone4. To archive that we have to do some tricks as for arbitrary shapes that would not be possible. I am pretty sure there is a better way to do what we are doing, but it would make other things more complex.

We group many shapes to one body, but this can change during a level. We do not change hundreds of shapes each frame, but every now and then and we do not what a frame drop in that case.

I thing most stuff of add shape are not needed to only switch the body (at least in our case):
1) seems to work without it.
2) Its O(n) for each shape we remove from this body. as we will remove all shapes from this body its would be very inefficient to do that one after the other.
3) I am not sure if we need this. The arbiter hold to shapes AND two bodies. Why is that the case. We could get out of sync here
4) It will be added right again. Even when slow its not needed.
5) Again, seems to work without it.
6) we do that
7) We o that only once as we add often many shapes to the same body.
8) we do that
9) Not needed here as we do it later
10) we do not remove it
11) this does not happen

We are using chipmunk not the way its designed, I know :) But it works and it is very fast. We only have left the cpBodyFree crash which is somehow related to the arbiters.
Visit our game Blog: [url]http://zombiesmash.gamedrs.com[/url] or follow us on twitter: [url]http://twitter.com/zombiesmash[/url]
JavierTapulous
Posts: 13
Joined: Fri Apr 01, 2011 3:17 pm
Contact:

Re: Chipmunk 6.0 Beta

Post by JavierTapulous »

Hey

It seems like you are already on the crash when using sleeping bodies. Anyway, i'm getting the crash when it's enabled and i'm trying to reset a level. Here's the stacktrace

using space->sleepTimeThreshold = 0.001;

#0 0x001f8172 in SubtreeRemove (subtree=0x788cfc0, leaf=0x0, tree=0x6d9a650) at cpBBTree.c:385
#1 0x001f89c3 in cpBBTreeRemove (tree=0x6d9a650, obj=0xc9dc640, hashid=1384) at cpBBTree.c:605
#2 0x00205107 in cpSpatialIndexRemove (index=0x6d9a650, obj=0xc9dc640, hashid=1384) at cpSpatialIndex.h:194
#3 0x00204e5f in cpSpaceActivateBody (space=0x6d9a8c0, body=0xc9dc5c0) at cpSpaceComponent.c:42
#4 0x00205708 in ComponentActivate (root=0xc9dc5c0) at cpSpaceComponent.c:129
#5 0x00205600 in cpBodyActivate (body=0xc9dc5c0) at cpSpaceComponent.c:152
#6 0x00203a86 in cpSpaceAddShape (space=0x6d9a8c0, shape=0xc9dc640) at cpSpace.c:254

bad access on
Node *parent = leaf->parent; in SubtreeRemove

Because leaf is NULL. returned by
Node *leaf = (Node *)cpHashSetRemove(tree->leaves, hashid, obj); on cpBBTreeRemove


Also, cpSpacialIndexRemove is getting called with staticShapes
cpSpatialIndexRemove(space->staticShapes, shape, shape->hashid);


The way i reset a level is as follows:

1) destroy the space
2) create a new space
3) reset the positions, rotations, joints, etc etc of the physic entities in my level
4) add the physic entities to the space (This is where it crashes, after i try to add a shape)

I'm using revision 765
Last edited by JavierTapulous on Fri Jun 17, 2011 4:41 pm, edited 2 times in total.
JavierTapulous
Posts: 13
Joined: Fri Apr 01, 2011 3:17 pm
Contact:

Re: Chipmunk 6.0 Beta

Post by JavierTapulous »

Also, when
space->sleepTimeThreshold = 10;

when i try to reset the level it hangs, the backtrace is

#0 0x00205fe0 in FloodFillComponent (root=0x11063730, body=0x1104b2f0) at cpSpaceComponent.c:181
#1 0x002060b9 in FloodFillComponent (root=0x11063730, body=0x11064d50) at cpSpaceComponent.c:186
#2 0x0020605e in FloodFillComponent (root=0x11063730, body=0x11065c30) at cpSpaceComponent.c:185
#3 0x0020605e in FloodFillComponent (root=0x11063730, body=0x1104b2f0) at cpSpaceComponent.c:185
#4 0x0020605e in FloodFillComponent (root=0x11063730, body=0x11063730) at cpSpaceComponent.c:185
#5 0x00205c17 in cpSpaceProcessComponents (space=0x6d96b60, dt=0.00128205132) at cpSpaceComponent.c:257
#6 0x0020a54b in cpSpaceStep (space=0x6d96b60, dt=0.00128205132) at cpSpaceStep.c:375
otibom
Posts: 8
Joined: Sat Mar 26, 2011 7:45 am
Contact:

Re: Chipmunk 6.0 Beta

Post by otibom »

Hi slembcke,

Chipmunk 6 looks awesome !
I noticed a change in the API for getting the static body of a Space. space.staticBody is now a cpBody*. It used to be a cpBody. Should we just remove a '&' from or code when adding a static shape or is there any other side effects we should be aware of ? Or should we use cpSpaceAddStaticShape() ?
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Chipmunk 6.0 Beta

Post by slembcke »

@JavierTapulous What SVN revision are you on? I've made a number of changes to the way the contact graph works in the last couple weeks.

Are you removing the objects from the old space before you free it? I think that might be what's causing the FloodFill hang. It's trying to reference arbiters that were freed with the old space. If you run it in debug mode, does it fail on assertions for dangling pointers in the contact graph?

cpSpaceAdd*() checks if the object you are adding is already added to the space, but it should probably check if it was added to any space instead. You can't add things to another space without removing them from the first even if you free the first. In previous versions of Chipmunk the behaviour was just sort of undefined, but I don't think it would cause a crash.

@otibom Just remove the '&'. I need to make a Chipmunk 5 to 6 migration guide as there were a number of small changes to the API. cpSpaceAddStaticShape() is actually deprecated in Chipmunk 6 as there really isn't any reason to use it anymore.

I changed cpSpace.staticBody to be a pointer to the static body instead of a directly allocated struct to make bindings easier to write. Requiring the '&' in there was also really annoying, and I regretted implementing it that way.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
JavierTapulous
Posts: 13
Joined: Fri Apr 01, 2011 3:17 pm
Contact:

Re: Chipmunk 6.0 Beta

Post by JavierTapulous »

@slembcke

I'm running the latest revision r765

I wasn't removing objects before freeing the space. Now i am, but it still hangs. Also, no assertions or warnings at all on Debug. I also changed cpSpaceAddBody to check if it's been added to any space and they are not.

Also, as i said no warnings so no Inconsistencies detected in the contact graph.

For more insight on what's going on when i reset and it hangs

1) i remove all bodies from the space
2) i destroy the space
3) i create a new space
4) i add static shapes
5) i add bodies and shapes
6) i start the simulation
7) it hangs on spSpaceStep with the backtrace i posted earlier, in this part of the spSpaceStep code:

// If body sleeping is enabled, do that now.
if(space->sleepTimeThreshold != INFINITY || space->enableContactGraph){
cpSpaceProcessComponents(space, dt);
}
Post Reply

Who is online

Users browsing this forum: No registered users and 13 guests