# How to perform collision detection in 3D space?

I've got to write, what can be summed up as, a complete 3D game from scratch this semester. Up until 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 until 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 optimizations, I'm talking about direct collision detection of one set of 3D polygons with another 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 professionals 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

## 3 Answers

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

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.

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 May 28 '14 at 16:19
• oh, ok I thought it's fine – Sergiu Craitoiu May 30 '14 at 10:39

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.