3d collision detection

XNA Game Studio Express

davidboothe

are there any tutorials on how to do 3d collision detection. like between one model and another (and not with boxes... but complex collision detection)

currently, i have a camera that walks around 1st person. I would like to give it a boundingbox or something like that. I also have the spaceship model from the spaceship demo game on the scene. I am not currently dealing with the Y axis, but i would like to detect collisions between the camera's boundingbox and the spaceship. any help would be great. thanks
Top

Re: XNA Game Studio Express 3d collision detection

neogir

If you are familiar to the boxes collision (in pure math, not by the Help example) you have gone more than the halfway.
But it sounds strange to me the full 3d XNA Help collision example does not cover your needs. Maybe I'd prefer to change the bounding boxes to bounding spheres for your case because the simpliest bounding volume for collision detection is a sphere using the collision radius only. Boxes are more complicated and require more time to calculate collision (making your own collision system from scratch). The XNA helps us much doing a lot of lowlevel job. The next step for a more complicated (or more precise) collision implementation is to divide your geometry to the multiple bounding volumes. Also you'd to assign some properties to the meshes bounding volumes to check collisions only for the specified boundaries.
If you have learned the collision boundaries, methods and properties as described in the XNA Help, as well as raycasting and do know how it goes mathematically i'd think your question may rather sounds like "how can I find the vertex indicies for the picked triangle ".
I suppose the XNA docs is the one of the main target for MSFT and MS QM in the last months so let's wait for the descriptive examples in the forthcoming release. Not so long to wait though.


Top

Re: XNA Game Studio Express 3d collision detection

Jon Watte

Moving mesh to moving mesh is a really hard problem, and is still considered open (if you want to get good contact depth, etc, generated).

The best you can get right now is the "GJK" method (just google for GJK mesh collision). The best before that method came around was the "simplex" method. Neither of them are very approachable for those who are not well grounded in 3D algebra, but if you know your math, you can implement them robustly, with good test cases, in about a week (maybe a bit longer for acceleration and corner cases).





Top

Re: XNA Game Studio Express 3d collision detection

davidboothe

Jon,

your post is very helpful. I will search GJK and simplex, not to mention dust off my old linear algebra book. If i get any good code, i'll post it up to help others. If anyone else beats me to this topic, please post. I'de love to see or colab with someone who knows what they are doing.


Top

Re: XNA Game Studio Express 3d collision detection

neogir

If a math is your friend you'd know the GJK algorithm has been improved from the initial introduction to eliminate  erroneous behaviour. This resulted to  enhanced GJK, ISA GJK and Lin-Canny combined algo for convex polyhedra. But there  are some more advanced algotithms and computer implementations, including these for non-convex boundaries, f.e the V-Clip.
The V-clip does not explicitly construct closest points  while iterating, but localizes the closest points to various regions of interest through simple clipping operations and scalar tests, i.e. uses topological primitives while Lin-Canny must compute new objects (closest points between objects). Edge-face and face-face are the two most problematic cases in Lin-Canny algo. In V-Clip, the edge-face case is much simplifed, and the face-face case is eliminated.


Top

Re: XNA Game Studio Express 3d collision detection

Jon Watte

Actually, the whole point of GJK is that it works for concave-concave intersection, assuming that you have the "support mapping" for it.

The problem is calculating good "contacts" if you're using a penalty/penetration based solver -- there's no one "best" direction to "extract" the objects, as they are not convex.





Top