Collision Detection Optimization Tips?

programming
1

Hey Everybody, I’ve been working on a collision detection script for a couple weeks, and so far it’s doing pretty good, but I would like to make it faster, and any help would be greatly appreciated. Here are the basic steps I am using right now:

  1. Each object is declared as a Polygon, and each Polygon (except for Circles) has a bounding circle precomputed when I create the polygon. I also precompute the vectors for the polygon so I can use them in an SAT (separating axis) collision test.

  2. If the number of objects exceeds 50, i start using RDC to create groups to test for collision. Otherwise I just brute force test each object against eachother.

  3. When I test the object pairs, I do a bounding circle test first to check for collisions, and if that returns true, I proceed with an SAT test to find actual collisions and projections.

So far I can get to about 100 objects on the screen and about 10 active collisions without dropping too many frames, but after that it starts to get hairy pretty quicky as more collisions get added.

I’m using while(){–i} style loops for all my looping (i’ve read those are the fastest) and have implemented a lot of the math optimization tips you can read about at Polygonal Labs (link at bottom) but after this I’m kinda tapped out about ideas of how to improve it. I’ve seen another demo at Polygonal labs using QuadTrees that allows for potentially a thousand objects… is RDC that poor of an algorithm in comparison, or maybe I’m doing something wrong… any tips about speed or hints as to what I might be doing wrong would be appreciated.

here are some links that greatly influenced my work:

http://blog.open-design.be/2008/12/30/as3-loops-performance-benchmarking/
http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/
http://lab.polygonal.de/articles/recursive-dimensional-clustering/
http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

(also, in the quadtree demo, he seems to be setting his framerate at 120fps, if I was making a collision heavy game is that FPS in the normal range? i’ve rarely gone above 60 myself)

thanks All!