Fastest 2D exact collision detection method?
Author
Im working on a 2D physics engine and I have the solver, but I need to make the collision detection work faster.
These are the methods Iv been looking at as possible options, though I cant really find anything describing which one would be the fastest and dont have time to implement them all.. (keep in mind this is for 2d)
-seperating axis thm. (SAT) - this is what im currently using and it seems to work well
-JGK - seems to be used alot for 3d, not sure how well this would work for 2d
-V Clip - a lin-canny approach (i dont know much about this one)
-Signed distance maps (SDM) - (again, I dont know much, couldnt find any papers on using these for collision detection)
if anyone could compare and of these or make a suggestion for the fastest known exact collision detection algo.
Thanks in advance
It looks like your looking at object to object schemes. What you really need is something to reduce the number of object to object tests instead of something to make the object to object tests faster.
Are you doing a brute force method? That is, testing every object against every other object it can collide with every cycle? Even the simplest test in the world isn't going to do much good if it's called a million times a cycle. The order of complexity needs to be reduced. Most approaches can bring the complexity to O(n) instead of O(n^2).
Look into space partitioning methods. If your objects are about the same size, you should look into a grid approach. It's by far the fastest method to implement and maintain. This is a good resource.
Are you doing a brute force method? That is, testing every object against every other object it can collide with every cycle? Even the simplest test in the world isn't going to do much good if it's called a million times a cycle. The order of complexity needs to be reduced. Most approaches can bring the complexity to O(n) instead of O(n^2).
Look into space partitioning methods. If your objects are about the same size, you should look into a grid approach. It's by far the fastest method to implement and maintain. This is a good resource.
Author
actualy Iv already implemented a hash based broadphase collision detection that works very fast. It gives me all the pairs of objects that i need to check using exact collision detection. Right now I can get about 600 boxes all colliding at once but then it starts getting slow. I wana get this up as much as possible
What shape are your objects? Oriented boxes? Arbitrary polytopes?
In any case, if the narrow phase really is a bottleneck, there are a lot of little optimizations and shortcuts that can be made to streamline the SAT test. If you're still looking for input on this, perhaps you could provide some more info, such as what shapes the objects are, how you're calculating the projections, and anything else that seems relevant. You could also post some of your code, just in case there are some obvious opportunities for optimization.
In any case, if the narrow phase really is a bottleneck, there are a lot of little optimizations and shortcuts that can be made to streamline the SAT test. If you're still looking for input on this, perhaps you could provide some more info, such as what shapes the objects are, how you're calculating the projections, and anything else that seems relevant. You could also post some of your code, just in case there are some obvious opportunities for optimization.
Have you profiled the code at all? You might find that the slowdown is in some other aspect of the code, or that the collision detection isn't as problematic as you think. Maybe you're graphics card is the bottleneck if it's old and you're drawing your boxes inefficiently, etc. etc.
My personal experience seems to indicate that at 600 objects you shouldn't be experiencing a problematic slowdown just yet if you've implemented an efficient broadphase algorithm. My guess would be that it's another part of the code.
My personal experience seems to indicate that at 600 objects you shouldn't be experiencing a problematic slowdown just yet if you've implemented an efficient broadphase algorithm. My guess would be that it's another part of the code.
SAT should be enough for 2D, if objects are convex and not over the top (100+ segment sphere approximation).
Author
Iv optimised it as much as i could and found some example code that seems to work well, so now i can get a couple hundred more for a total of about 800-1000 simultaniously colliding bodies without serious slowdown (depending on their size)
Iv profiled my code while having 1000 simultaniously colliding bodies and determined that dynamics (including solving the contacts) takes about 30% of the time, broadphase takes anout 10%, and narrow-phase takes the other 60%
I didnt include the rendering in the profile since i highly dougt that it caused any slowdown. I have a gf. 6800 and im just drawing 4 segment boxes with opengl so i dont think it would be any problem.
So i assume im correct in thinking that SAT is the best method in this case..
Right now im only using boxes for my tests but it could be any convex polygon. Broadphase uses a hash table based approach, which cant get much better. If no objects are colliding at all there can be many thousands. Then before even performing narrow phase on an object I check if their bounding boxes are intersecting, so narrow phase seems to definately be the bottleneck.
Is it possible to use some type of temperal coherance with SAT? Would it speed it up alot if I tryed using things like MMX and SSE in my vector/matrix classes to speed up floating point computations?
Also, any thoughts on how to do circle - convex collisions efficiently? I really dont want to have to approximate them with 100 line segments..
Iv profiled my code while having 1000 simultaniously colliding bodies and determined that dynamics (including solving the contacts) takes about 30% of the time, broadphase takes anout 10%, and narrow-phase takes the other 60%
I didnt include the rendering in the profile since i highly dougt that it caused any slowdown. I have a gf. 6800 and im just drawing 4 segment boxes with opengl so i dont think it would be any problem.
So i assume im correct in thinking that SAT is the best method in this case..
Right now im only using boxes for my tests but it could be any convex polygon. Broadphase uses a hash table based approach, which cant get much better. If no objects are colliding at all there can be many thousands. Then before even performing narrow phase on an object I check if their bounding boxes are intersecting, so narrow phase seems to definately be the bottleneck.
Is it possible to use some type of temperal coherance with SAT? Would it speed it up alot if I tryed using things like MMX and SSE in my vector/matrix classes to speed up floating point computations?
Also, any thoughts on how to do circle - convex collisions efficiently? I really dont want to have to approximate them with 100 line segments..
Quote:Original post by coderchrisIs your narrow phase discrete or continuous?
Also, any thoughts on how to do circle - convex collisions efficiently? I really dont want to have to approximate them with 100 line segments..
I would recommend adding a toggle in the game to turn of graphics rendering entirely. You might be surprised at the amount of clock cycles rendering even simple geometry on a fast card might take if done in certain ways. Basically, rendering might be negligable, or it might be rather large. It might change from computer to computer. Don't assume anything.
I find it extremely suspicious that your broadphase and narrowphase are so disproportionate from each other. Either your broadphase is still causing too many bodies to be checked against each other (broadphase too broad) or your narrowphase is really, really inefficient. How complex is the collision geometry? You might be using needlessly complex geometry to test collisions. Something screwy is going on here regardless. Even 1000 objects in a small enclosed space in 2D shouldn't have that many object to object tests if a good broadphase test is used.
You might want to add another level of abstraction between your broadphase and narrowphase if your collision geometry is very complex and your broadphase isn't as narrow as you'd like. Perform a bounding sphere to bounding sphere test before the more complex collision geometry tests. This should be an incredibly fast test to perform since you can precalculate the bounding spheres. Just be sure not to note that a^2 < b^2 is the same as sqrt(a^2) < sqrt(b^2), ie: don't be taking any square roots. You could add another layer in here, but in my experience it's not worth it.
Honestly I think your narrowphase should be about on par with your broadphase as far as CPU cycles. Maybe up to twice or 3 times as much, but certainly not 6 times more.
I find it extremely suspicious that your broadphase and narrowphase are so disproportionate from each other. Either your broadphase is still causing too many bodies to be checked against each other (broadphase too broad) or your narrowphase is really, really inefficient. How complex is the collision geometry? You might be using needlessly complex geometry to test collisions. Something screwy is going on here regardless. Even 1000 objects in a small enclosed space in 2D shouldn't have that many object to object tests if a good broadphase test is used.
You might want to add another level of abstraction between your broadphase and narrowphase if your collision geometry is very complex and your broadphase isn't as narrow as you'd like. Perform a bounding sphere to bounding sphere test before the more complex collision geometry tests. This should be an incredibly fast test to perform since you can precalculate the bounding spheres. Just be sure not to note that a^2 < b^2 is the same as sqrt(a^2) < sqrt(b^2), ie: don't be taking any square roots. You could add another layer in here, but in my experience it's not worth it.
Honestly I think your narrowphase should be about on par with your broadphase as far as CPU cycles. Maybe up to twice or 3 times as much, but certainly not 6 times more.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
