So I recently implemented SAT (Seperating axis theorem), which is an algorithm for finding out whether objects collide. These objects can be rotated, scaled, can have as much vertices as they want, etc.
The algorithm is mainly this: “Two convex polygons don’t intersect, if you are able to draw a straight line in between them.”
After about ~10 hours of blindly writing vector math and collision stuff code from online tutorials and own existing code, I got my version running pretty well the first time.
I corrected some lapses, for example not re-calculating the normals after updating the matrix of them or calculating the normals wrong (forgetting to create the left perpendicular of them) and things like that…
So in this screenshot I’ve got 60k polygons, each having 8 vertices, which are randomly generated. (all convex)
Usually the background is black…
Runs at a somehow steady 30 fps, due to the rendering… the collision tests only take 14-15 milliseconds.
I’ve got a GTX 550 Ti, 8GB and 3.3 GHz 8-core Xenon cpu running here.
The collision detection is single-threaded.
So here the same program is with only 60 polygons:
As you can see the background now is black ( ;D ;D ) and the vertices from the polygons are drawn white, if they’re not colliding with the “mouse-quad” and black, if they do.
The program only tests the “mouse-quad” (a 4-vertex polygon, which you can rotate with the mousewheel and move with the mouse) against all avaliable polygons, so the polygons don’t test collisions with each other, only with the mouse-quad.
I’ve got a pretty good pc, I want to see what performance you get[url=http://dl.dropbox.com/u/45530199/Programs/ArcEngine/ArcEngine_SAT.zip]Download HERE[/url] I want to see what performance you get :) Remember to start via command line to see additional information!