Implementation of a new Broadphase

Discuss new features and future development.

Implementation of a new Broadphase

Postby ebmoll » Fri Sep 23, 2011 8:18 pm

Hi,

I want to add a new broadphase to Chipmunk and need some help; I already found the cpSpatialIndex and cpSweep1D and I think I know how to proceed, but I have a problem...

If I understand correctly, the existing Chipmunk broadphases keep two spatial indexes, one for static and one for dynamic shapes. For dynamic/static collision they just test each dynamic BB against the whole static tree. (BTW, does the sweep1D really test every dynamic shape against all static shapes, i.e. N_d*N_s running time, or did I misunderstand that?!)

My broadphase needs the dynamic and static shapes in the same data structure (i.e. only one cpSpatialIndex, not divided into staticShapes and activeShapes) to be efficient; I would just flag all static bodies and not test for collisions among them. Is this possible without changing the rest of the Chipmunk code?

For example, in cpSpaceActivateBody():

Code: Select all
cpSpatialIndexRemove(space->staticShapes, shape, shape->hashid);
cpSpatialIndexInsert(space->activeShapes, shape, shape->hashid);

unfortunately, insertions into my broadphase index are not very efficient, so I'd like to avoid unnecessary ones.

If I succeed and my broadphase turns out to be any good, I'll share the code, of course.

BTW, thanks for this great physics library!
ebmoll
 
Posts: 5
Joined: Fri Sep 23, 2011 3:55 pm

Re: Implementation of a new Broadphase

Postby slembcke » Sat Sep 24, 2011 2:15 pm

Yes, Chipmunk keeps the static and dynamic objects in separate indexes. Actually I'm not 100% happy with how the new generic broadphase API as it led to a bunch of messy code with the BB tree. It pools linked list nodes to track cached collisions, but there is a bunch of nasty code so that the static tree get's those nodes from the dynamic tree's pool so that both trees know what pool to return the nodes to. This of course is only happens when using a tree for both the static and dynamic indexes. :-\ After a couple months of sitting on it I couldn't really think of a better way to organize it though, and the performance was certainly great as is for probably 99% of the use cases. As you found, one of the reasons that I made it the way I did was because I was moving objects back and forth between the indexes when the sleep or awake. Honestly though I'd try just ignoring the performance hit of the insertion for now. Objects really don't sleep/awake very often anyway. The sleep/wake cycle is going to be measured in hundreds of frames realistically.

Part of the reason to keep separate indexes is because most indexes perform much much better when you split up dynamic and static data. The only exception I can really think of is sweep and prune, which is rarely optimal anyway. Sweep1D was written because I wanted a super simple index that showed how to implement your own and because the Zombie Smash developers had requested it specifically and they donated quite a bit of money to Chipmunk. Their game had a lot of dynamic shapes spread out mostly over the x-axis, and filtered a lot of the collisions leading to a very high false positive ratio. In Chipmunk 5.x, they had simply hacked Sweep1D in instead of using the spatial hash.

The intention with the Sweep1D is that you would use it only for the dynamic index and use the hash or the tree for the static index. So the runtime should be more like O(Ndynamic*log(Nstatic)) with the tree or O(Ndynamic*LargeConstant) with the hash. All of the operations other than reindex+query are implemented to brute force their way through because of this. I also don't really document that the Sweep1D even exists, and you can't enable it without poking at the private API currently, so I expect a lot of people don't even know it exists.

What algorithm are you trying to implement? I might have some suggestions.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Implementation of a new Broadphase

Postby ebmoll » Sat Sep 24, 2011 10:35 pm

Part of the reason to keep separate indexes is because most indexes perform much much better when you split up dynamic and static data.


That's a very good point that I missed until now, since my focus was only on moving bodies. I think I'll implement my broadphase as dynamic only like the Sweep1D for now and maybe adapt it later to also work for static geometry.

The intention with the Sweep1D is that you would use it only for the dynamic index and use the hash or the tree for the static index. So the runtime should be more like O(Ndynamic*log(Nstatic)) with the tree or O(Ndynamic*LargeConstant) with the hash.


Ah, that makes a lot of sense; I somehow assumed using it for both...

What algorithm are you trying to implement? I might have some suggestions.


I *think* it's a new one, though algorithms tend to have been invented before ;)
I'm quite excited about it, since it has some really cool properties like:
- linear memory and linear time (linear in number of shapes + number of collisions) as long as neighborhood between objects doesn't change.
- no tuning required
- it provides neighborhood relations for free, which might be exploitable in a contact solver;
unfortunately it also has some drawbacks like if you want to use it for static geometry, it finds collisions between static BBs too (which costs some time), but I might find a way around that...

I hope it's the killer broadphase for 2D physics, but I'm still not sure how the performance is in the real world. That's why I want to try it inside Chipmunk.
ebmoll
 
Posts: 5
Joined: Fri Sep 23, 2011 3:55 pm

Re: Implementation of a new Broadphase

Postby slembcke » Sun Sep 25, 2011 10:00 am

Ah, Ok. Well let me know if you have any more questions. Like I said, the generic broadphase support isn't really perfect but hopefully it's flexible enough that you can work with it.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Implementation of a new Broadphase

Postby ebmoll » Sun Sep 25, 2011 3:24 pm

Thanks!

I have completed the first version; the API is actually quite easy to work with in retrospective ;)

My broadphase beat the BB tree in the logo smash demo, but the results are still somewhat inconclusive on other scenarios; I'll have to debug and optimize my broadphase quite a bit... I hope it can hold up to my expectations.
ebmoll
 
Posts: 5
Joined: Fri Sep 23, 2011 3:55 pm

Re: Implementation of a new Broadphase

Postby slembcke » Sun Sep 25, 2011 3:55 pm

I wouldn't really use the logo smash demo as a good generic test. That is the only demo where the BB tree doesn't trounce the spatial hash as well. It's also not a setup that I would really expect to see in a game.

You should try running the benchmark demos using -bench and run them as time trials with -trial. I think they should give you a much better set of numbers to work with.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Implementation of a new Broadphase

Postby ebmoll » Sun Sep 25, 2011 6:13 pm

Thanks for the info; that saves me the time of having to write my own benchmark for now!

Profiling revealed that it's probably not a good idea to use the BB tree for static collision with my broadphase for moving bodies; at least SubtreeQuery takes a significant amount of time; maybe I'm doing something wrong and I need to call some rebalancing function or so?

I'm currently trying to use my algorithm for static collisions also; is it a problem if my ReindexQuery function also reports collisons between static shapes?
ebmoll
 
Posts: 5
Joined: Fri Sep 23, 2011 3:55 pm

Re: Implementation of a new Broadphase

Postby slembcke » Mon Sep 26, 2011 10:59 am

The tree isn't really ideal as a static only index I guess. It's main speed advantage is that it caches collision pairs and only recalculates them for a leaf when it's bounding box is violated. That was what allowed it's performance to be so competitive with the spatial hash even when putting thousands of objects into the space. Otherwise it started to get slower at about ~300 objects or so.

Returning collisions between static objects during reindexQuery would be very bad. Chipmunk never calls that on a static index though. It only calls it on the dynamic index, but that is also responsible for querying against the static index if it has one.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm

Re: Implementation of a new Broadphase

Postby ebmoll » Tue Sep 27, 2011 8:22 am

Returning collisions between static objects during reindexQuery would be very bad. Chipmunk never calls that on a static index though.


What I meant is if it would be bad if reIndexQuery(activeShapes,...) returned also Static/Static pairs, since it also has to return Act/Stat and Act/Act pairs.
I implemented it this way and I didn't notice any adverse effects, though I removed it in the meantime. Why is it so bad?

My performance experiments so far showed that Chipmunk's BB tree is quite hard to beat. My broadphase currently loses in the benchmark by about a factor of 3 (only collision detection time as reported by gprof, so total running time is only slightly lower), but for 200,000 objects wins by a factor of 4 or 5 total running time and the memory usage is lower.

Now I have to go optimize away that factor of 3... ;)
ebmoll
 
Posts: 5
Joined: Fri Sep 23, 2011 3:55 pm

Re: Implementation of a new Broadphase

Postby slembcke » Tue Sep 27, 2011 9:32 am

If you have overlapping static objects Chipmunk will treat them as collisions between infinite mass objects and bad stuff will happen. I would venture to guess that none of the benchmarks have any overlapping static shapes though.

Hehe. Good to see that the performance of my tree is holding up. I spent quite a long time optimizing it. ;) Last time I profiled it, most of the CPU time spent in the tree was spent dereferencing the pointers for the linked list that stores the cached collisions. I figured the only way I would make it much faster than that would be to make it more CPU cache efficient.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
User avatar
slembcke
Site Admin
 
Posts: 4164
Joined: Tue Aug 14, 2007 7:13 pm


Return to Features/Development

Who is online

Users browsing this forum: No registered users and 1 guest