Wednesday, 7 February 2007

3D intersection concepts and the Mesh.Intersect() method

[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!

3 comments:

Miguel Sandro Lucero said...

Hace un tiempo atras, empezando a programar con directx y c# desarrollé una version del cubo rubik. esta versión usa los métodos Mesh.Intersect() y un objeto IntersectInformation para determinar que bloque del cubo se ha seleccionado con el mouse, método que uso para poder mover las caras del cubo etc.

Ahora bien, en estos días me he puesto a pasar esa version de escritorio a una version para windows mobile usando compact framework 2.0 y su respectivo directx reducido. y es acá donde me encuentro con que la clase mesh no tiene el método Intersect() ni la clase IntersectInformation.

Como no soy experto en teorías de gráficos en 3D me ha costado encontrar información de como reemplazar dicho código para poder determinar que bloque del cubo ha sido seleccionado con el mouse. En la página de microsoft encontré un código para seleccionar un mesh con el mouse pero para mi caso no sirve porque al no tener forma de determinar que bloque es el elegido, según ese método me selecciona cualquier bloque que esté haciendo intersección con el vector generado

Entonces ... hay alguna forma de reemplazar el método Intersect() de la clase mesh u alguna otra forma de resolver el problema de interseccion de un vector con un mesh determinando no solo si existe o no iterseccion sino también la distancia etc. datos que son devueltos en el objeto del tipo IntersectInformation

Desde ya muchisimas gracias

Miguel Sandro Lucero

Iñaki Ayucar said...

Hola Miguel,

se me ocurren varias opciones:

1.- No conozco el ejemplo de Microsoft ni que información te devuelve, pero si te da una lista de los objetos que hay "debajo" del mouse, quizá podrías tratar de encontrar cual de esos objetos es el más cercano a la cámara, es decir, el primero de todos ellos que se encontraría un rayo trazado desde el mouse.

2.- Pasando del ejemplo de microsoft, tienes varias formas de reemplazar el Mesh.Intersect:

2.a.- Dado que tus objetos son cubos, puedes utilizar tests de intersección entre formas geométricas y el rayo, en lugar de entre el rayo y la maya de polígonos.

2.a.1.- Si en tu aplicación, tu cubo de Rubik está siempre en la misma posición (sin rotar), lo tienes todavía más fácil, porque puedes calcular intersecciones entre el rayo y los "Axis Aligend Bound Boxes" (o AABB, para los amigos) de tus cubos.

2.a.2.- Si tus cubos pueden rotar, entonces ya no puedes asumir que los cubos estarán siempre alineados con los ejes de tu sistema de coords, por lo que los AABB no te sirven. En este caso puedes calcular intersecciones entre el rayo y los "Oriented Bound Boxes" o OBB para los amigos.

Encontrarás montones de información tanto para el caso AABB como para el caso OBB y cómo calcular intersecciones con éstos.

2.b.- Otra posibilidad (aunque más lenta) es reemplazar por completo el metodo Mesh.Intersect. Éste método no hace otra cosa más que recorrerse la lista de polígonos de tu objeto efectuando un test de colisión de tipo Rayo-Triángulo para cada uno de ellos, y se queda con el triángulo más cercano de todos. Obviamente, aplica sistemas para optimizar el proceso. Como en tu caso solo vas a utilizar el algoritmo para hacer "picking" con el mouse, el rendimiento no es un aspecto crucial, así que puedes programarte tu este método y optimizarlo hasta donde puedas. Entontrarás también montones de información sobre como hacer el test Rayo-Triángulo.

No obstante, si tienes cualquier problema coméntamelo.

Saludos!

Miguel Sandro Lucero said...

gracias por las ideas, fueron de mucha ayuda. he adaptado la version en c++ del ejemplo de picking que viene con el sdk de directx.

Ahora tengo que optimizar el código porque la aplicación funciona un poco lenta y además consume muchos recursos del s.o.