I am working on physically interactive 2d terrain engine capable of classic scorched earth terrain destruction and addition. I am using GLU tesselator to break the terrain shape down into triangles for the physics engine to use. I have been using SAT (separating axis theorem) for collision detection and ODE for restitution ( and dynamics ). SAT is general for all convex polygon vs convex polygon collisions. I was wondering if I could optimize my engine by forcing all shapes to be triangles? Basically is there a faster way to detect weather two triangles are colliding, instead of using SAT for a triangle vs convex polygon collision?
-caspin
2d physics shape optimization
-
Dirk Gregorius
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: 2d physics shape optimization
FYI: You posted your message twice so I deleted one post...
Re: 2d physics shape optimization
Probably not, is my opinion (others here definitely know more than I do, though). As far as I know, SAT is pretty much it for polygons, including triangles - you can't get much simpler than testing which side of a line something is on and by how much. The only caveat would be that you might be able to achieve some minor optimizations by writing the algorithm for that particular case, just because you'd get to skip things like checking the number of vertices, etc., but these are very minor optimizations.
A couple things, though: one, make sure you're using a decent broadphase, either a quadtree or sweep and prune or something along those lines. That will take the load off of the collision handler quite a bit. Two, make sure the the GLU tessellator is really giving you what you need; to my knowledge, its only stated purpose is to come up with any old tessellation so that OpenGL can render non-convex polygons, not necessarily to provide a nice, even tessellation. It's not immediately obvious to me that what it provides would be suitable for physical simulation. You might be better off decomposing your surface yourself using some algorithm that would give you an (perhaps somewhat randomized) even triangulation of the surface.
Then again, if you're only using the tessellator to collide things against, not to actually create stuff to simulate the destruction, then it's probably exactly what you need.
A couple things, though: one, make sure you're using a decent broadphase, either a quadtree or sweep and prune or something along those lines. That will take the load off of the collision handler quite a bit. Two, make sure the the GLU tessellator is really giving you what you need; to my knowledge, its only stated purpose is to come up with any old tessellation so that OpenGL can render non-convex polygons, not necessarily to provide a nice, even tessellation. It's not immediately obvious to me that what it provides would be suitable for physical simulation. You might be better off decomposing your surface yourself using some algorithm that would give you an (perhaps somewhat randomized) even triangulation of the surface.
Then again, if you're only using the tessellator to collide things against, not to actually create stuff to simulate the destruction, then it's probably exactly what you need.