Jump to content
  • Advertisement
Sign in to follow this  

collision detection in games and physics engine 3d

This topic is 1236 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all.
I have been looking at collision detection methods and other physics based topics and have decided that I what to try and create a physics engine but i want to ask a couple of questions before i do that.
From what i have seen, most games use OBB for collision but when it comes to physics engines i have seen that they use convex hull based collision so some of the questions i want to ask are,
what collision method do they use for games and physics engines (just for clarification)
how do you create a convex hull from a mesh and how do u get around the problem of objects like 
and what collision detection method like SAT or GJK are best to use 
Thanks for any help in advance smile.png

Share this post

Link to post
Share on other sites

This depends of the game requirements. Some games has very specifics collision detection routines; some are made of OBBs, other of a sphere and a box, e etc. In this case these problems can be solved by only using a OBB-OBB test or a simply capsule-capsule for instance. Using this loss of generality you have the positive side that is fast intersection routines. Read Christer Ericsons orange book.

Recent games needs to support basically any kind of shape, and like you said, convex polyhedras are being used in recent game physics simulations.

The most commom algorithms are the SAT and the GJK.

The image you showed is a convex version of a concave mesh. It is generally transformed in convex using the QuickHull algorithm.

SAT is slightly slower but (in my experience) is numerically stable. This is because when using GJK you usually need to use EPA to get the minimum separation distance between the objects, which leads to numerical errors.

See this thread


Dirk has described the SAT algorithm in details.

Share this post

Link to post
Share on other sites

Thanks for clearing that up Irlan.


Do u have any suggestions on the best way to create a convex hull from an object cuz that is still something im quite confused about. I have tried to look stuff up but some of it is a bit confussing. Ill prob try and start with a simple shape like a box

Edited by lexington

Share this post

Link to post
Share on other sites

You can start with a simple shape like a sphere or AABB, then switch to a OBB. Once you're familiar start looking for polyhedras, etc.


Personally, I didn't had enough time to implement efficiently the QuickHull algorithm. However you can find great slides about it in this link:




Look for Implementing QuickHull by Dirk Gregorius. He explains also the basics of the SAT algorithm. Erin Catto explains greatly the GJK algorithm in 2D which is mathematically similar to 3D.


I have a naive implementation of the GJK-SAT algorithm (a SAT version of the GJK) here if you have trouble:




In the case you have trouble with the SAT:




These links are highly recommended. As long you keep the authors name on the sources you can use in your projects. You should take a look  on it and try to understand them.

Edited by Irlan Robson

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!