Bounding Box Trees for Chipmunk

November 10th, 2010| Posted by slembcke
Categories: Uncategorized | Tags:

One of the next big features that I want to add to Chipmunk is the ability to use different collision detection broadphases. It’s been on the todo list for years, but I’ve never gotten around to it.

Lately I’ve been hard at work on adapting the bounding box tree code we started for Solaro to work with Chipmunk. The results so far have been quite promising. I pulled in some ideas from the Bullet Physics bounding box tree implementation such as extruding the bounding boxes using a velocity estimate and padding them. This means that you don’t need to update the tree’s structure every frame. On top of that, I made it so that it only needs to recalculate overlapping parts of the tree when a leaf is updated. Otherwise it can just read back the cached pairs out of a graph that it maintains.

What does this mean for performance? Good things! While I really need to make some proper benchmarking scenes, time trials of the Chipmunk demos run 5-20% faster for complex scenes (< 1000 shapes), and even more for simpler scenes. The only exception is the Logo Smash demo (YouTube) where the spatial hash’s linear cost runs almost twice as fast on the 3000+ particles.

Another huge advantage of a tree based spatial index is that it isn’t so sensitive to scale like a spatial hash is. Chipmunk’s current spatial hash doesn’t handle objects with vastly different scales in the same scene very well, and you have to specifically tune the hash to the data that you are putting into it. Trees won’t need tuning and they work just as well when dealing with different sized objects.

If you want to find out more information about where Chipmunk is headed, there is more information on the forums.

  1. James McNeill
    November 10th, 2010 at 19:55
    Reply | Quote | #1

    Sounds really promising!

Comments are closed.