# Collision detection in 3D space

I've got to write, what can be summed up as, a compelte 3D game from scratch this semester. Up untill now i have only programmed 2D games in my spare time, the transition doesn't seem tough, the game's simple. The only issue i have is collision detection. The only thing i could find was AABB, bounding spheres or recommendations of various physics engines. I have to program a submarine that's going to be moving freely inside of a cave system, AFAIK i can't use physics libraries, so none of the above solves my problem.

Up untill now i was using SAT for my collision detection. Are there any similar, great algorithms, but crafted for 3D collision? I'm not talking about octrees, or other optimalizations, i'm talking about direct collision detection of one set of 3D polygons with annother set of 3D polygons. I thought about using SAT twice, project the mesh from the top and the side, but then it seems so hard to even divide 3D space into convex shapes. Also that seems like far too much computation even with octrees.

How do proffessionals do it? Could somebody shed some light.

-
Its not so hard to divide 3D space into convex geometry. For instance using a BSP-Tree (binary space partitioning). – Maik Semder Mar 8 '12 at 18:59

GJK works on convex shapes, i might aswell use SAT. I have found information i wanted already. Here are some examples.

http://www.peroxide.dk/papers/collision/collision.pdf

http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html

To sum it up, i'll be doing collision checks of a sphere or an elipsoid against multiple triangles that form a collision mesh. That seems to be how it's done and that was the information i was asking for, unless somebody can tell me different.

-

Well, if it's not something very very demanding and state of the art, you could start by implementing the Gilbert collision detection algorithm. It can be made to be fairly fast and it will be fast, provided your collision geometry is not so detailed (and it needn't be!). That's how even some simulators do the trick.. anything more elaborate will, probably, take more effort into consideration.

-

Hey I wrote about GJK in 3D here. SAT is slower than GJK http://in2gpu.com/2014/05/18/gjk-algorithm-3d/

-
Link-only answers tend to be rather poor, as they become invalid as soon as the moves and they do not search well. Consider expanding this answer to include some information about the details of the solution you are trying to present. – Josh Petrie May 28 '14 at 16:19
oh, ok I thought it's fine – Sergiu Craitoiu May 30 '14 at 10:39