hello everyone, I have a program that is built from openGL, I have objects to load in and will be using mouse to drag the object, however, i would like to have collision test between objects when i drag the object in space so that they don't overlap to each other. Can anyone give me some suggestion on which collision algorithm to use, some accuracy is needed so I reject the use of AABB or sphere vs sphere. Please help~! Millions of thanks

Quote:Original post by muimui1911
Can anyone give me some suggestion on which collision algorithm to use, some accuracy is needed so I reject the use of AABB or sphere vs sphere.

Spheres or AABBs will be far easier to code than most other algorithms, so you might reconsider that option. If you really need more accuracy, you could try other convex bounding volumes such as OBBs, capsules, or (axis-aligned) cylinders.

The next most accurate (and complicated) option would be convex hulls (assuming your objects are non-convex). This will require a convex hull builder, and an algorithm for determining whether two polytopes intersect. Of these, the SAT would probably be the easiest to code. Keep in mind though that the SAT test for arbitrary polytopes can involve testing hundreds of potential separating axes. You might be able to get away with this though if you can get it down to only one such test per frame.

Another option is GJK, which is not too hard to code for the boolean test, but is considerably more difficult if you need depth of penetration. If you have little experience with collision detection or are less than completely comfortable with 3D math, both GJK and SAT could prove to be quite challenging to implement. This is why, again, I recommend trying spheres or AABBs first; it may be that you don't need as much accuracy as you think you do.

If you need per-triangle intersection for non-convex objects, that's a whole other story. For that you'll need bounding volume hierarchies and a good tri-tri algorithm. Keep in mind that with non-convex objects it can sometimes be difficult to resolve intersections satisfactorily.

As you can see, the options range from very easy (spheres) to very difficult (arbitrary non-convex meshes). Factors to consider in choosing an algorithm are your comfort with 3D math, collision detection algorithms, and programming in general, and how much time you have available for the implementation.

thanks for you suggestion!

actually, i am thinking of using OBB. However, I am not sure how to implement it into codes...
I have some idea about the algorithm but i am not really sure the exact procedures. I can implement AABB, that is easy but how exactly do I implement the OBB, would you please give me some more helps?

thanks!

You can find an OBB test in this article (free registration required, I think). Documentation and code can also be found at geometrictools.com.

Be aware that not all references on OBB intersection address the problem of degenerate cross products, so watch out for that. Also, penetration depth is not covered by the gamasutra article (I don't know whether this is something you need). If you just need a boolean test though, the gamasutra example should work ok.