opengl - Separating Axis Theorem in Python/Pyglet -

i'm trying make (sort-of) clone of asteroids in python using pyglet. figured i'd try little fancy , implement separating axis theorem collision. got work, problem it's miserably slow. test collision between bullets player shoots , asteroids on screen in double for-loop, believe quadratic time, frame rate drops 60 30 fps time there's 6 asteroids , 6 bullets on screen, seems incredibly slow, non-optimized way of detecting collision.

so ran profiler determine where, exactly, in code program getting hung up. seems hung in method transform shape vertices world space (i define shapes around origin , use opengl code transform world space drawing, believe right way it). grab transformation matrix opengl, turn numpy array, , multiply each vertex matrix transformed vertices. it's worth noting every collision check: used use xna, , when implemented sat in (i made asteroids clone there, too), vertices defined around origin , had transform them using world matrix.

is best store vertices around (0, 0) , transform each call, or store transformed vertices? feel algorithm shouldn't slow, i'm willing bet screwed implementing something. if better @ profiling (i'm pretty unfamiliar it) might able more complete picture, hoping guys might have idea.

here's direct link file shape class in it, collision logic happens: shape.py. specific method profiler seemed mark bottleneck __get_transformed_verts. can entire repo there too, aware there's still deal not commented.

as nico suggests in comments, quick way speed-up check simpler geometry first. asteroids clone guess circle fit (or sphere 3d). if circles (at least large enough cover actual shape) don't overlap, there no need more expensive geometry test.

if have many objects, want avoid doing n*n tests every frame. take @ space partitioning structures/algorithms. simplest scheme lot of moving objects in 2d grid. need test objects belonging same - or neighbouring - grid cells collision.

another thing noticed: generate transformed vertices every time test collision. quicker generate them once per timestep (frame) each object fails circle-circle test.