[Please NOTE: This article is OBSOLETE. It has been re-written and completed in this newer posts: part 1 and part 2]
Today I´ve posted an answer to somebody that wanted to know more about collision detection and the use of the Mesh.Intersect method. As I liked the post, I decided to put it in here. Hope it helps somebody else. You can find the original post here:
http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1197599&SiteID=1
Determining if any two 3D objects intersect and get useful information about the intersection is not a easy task. Specially if you want to do it fast.
The key to optimize this algorithms is quick discarding non colliding objects. To do so, a list of algorithms can be applied. The more usual are the BoundXXX discard tests:
- BoundSphere: Use a hipotetical sphere surrounding objects. If the distance between objects are bigger than the sum of both radius, then they don´t intersect. This fits well for objects similar to a sphere, but not at all for something like a hockey stick, for example. This one is supported in DirectX (BoundSphereTest)
- Axis Aligned Bound Box: Use a hipotetical box surrounding objects. This box is not aligned with the object, but with the world axis (it´s not rotated with the object). It just keeps track of the maximum and minimum values of X,Y,Z along the objects´s geometry. It´s also supported in DirectX (BoundBoxTest) and fits best with squared geometry, of course.
- Oriented Bound Box: This one is more accurate of the three, but of course more expensive to compute. It rotates the bounding box with the object, so it fits better it´s geometry. It´s not supported in DirectX and you´ll have to do it yourself. Let me know if you need help on this.
Once you are doing a good discard test of non-colliding objects, and once you got two objects that "may be intersecting", it´s time to go into a more detailed collision detection model.
There are dozens of intersection algorithms, each one optimized for the kind of geometry you want to test: Ray-Polygon, Ray-Mesh, Polygon-Mesh, Cylinder-Mesh, Cylinder-Ray, Sphere-Mesh, and so on...
The best is, if at least one of your two objects can be aproximated as a geometric shape like Sphere, Cylinder, Box, etc, because the Mesh-Mesh case is of course the most expensive. You can find very good resources about this algorithms here:
http://www.realtimerendering.com/int/
One of the most common methods is to define some BoundingSpheres that aproximate the real shape of an object, and use the sphere-mesh test. This method gives very good results sometimes (specially when objects are near to spherical) and it´s very fast.
Another usual method is to aproximate one of the two objects using a bunch of rays as collision testers and then perform the ray-mesh test. For example, if wanted to detect if a character is touching somethig, you can use rays describing it´s arms directions, and do a Ray-Mesh test against all other objects in the scene.
Thats where the Mesh.Intersect() methods comes in, because it performs the Mesh-Ray test. You can use it like this:
DX.Direct3D.IntersectInformation intersectionInfo;
if (mesh.Intersect(rayOrigin, rayDirection, out intersectionInfo))
{
// There is collision
}
The IntersectInformation structure gives you the exact Distance between the ray origin and the intersection point, the face index of the mesh with which the collision occurs, and the U,V coordinates of the intersection point (useful if you want to search something in the mesh texture, i.e. if the texture is transparent in that point).
If you want to know the exact 3D point of intersection you can easily calculate it like:
intersectionPoint = rayOrigin + (rayDirection * intersectInformation.Distance);
If you want the normal of the surface in the collision point, use the normal of the mesh´ face using the face index returned in IntersectInformation.
One thing you must be careful with: this method uses the current state of the mesh. It tests all of it´s polygons against the ray. If you move or rotate the mesh setting a transform matrix in the Device.Transforms.World, that transformation will not be taken into count in the Mesh.Intersect method. If your objects are dynamic, you should keep track of a mesh version with all it´s transformations applied to the vertices.
Lastly, if you want to do some serious collision detection, specially if you are planning to do any Rigid Body management, my suggestion would be to have a look to the SAT Algorithm (Separation Axes Algorithm). Its fast, accurate and gives you very useful information, like the MTD (minimum translation distance and direction to solve inter-penetration).
Cheers!