El algoritmo

Antes de ir al calculo del punto de interseccion, debemos ver si existe alguna posibilidad de que el segmento atraviese el plano donde yasen los vertices del poligono. Si no existe ninguna, entonces el segmento es paralelo al plano, de modo que su normal es otrogonal al vector director del segmento. Para comprobar esto, basta calcular

s es el vector comienzo del segmento
e es el vector final del segmento
n es la normal del plano

si n=0, entonces la normal del plano es ortogonal al vector director del segmento, y por consiguiente, no hay colision entre ambos.

A continuación presento los pasos que deberemos seguir para conseguir el punto de interseccion, en caso de existir.

1-    Calcular en que punto del espacio intersectan el segmento y el plano donde yacen los vértices del triangulo.
2-    Verificar si el punto encontrado cae dentro del triangulo.

Desarrollaremos ahora los pasos indicados anteriormente.

Calculo del punto de intersección entre el plano y el triangulo

Bien, para calcular este punto, lo que haremos será conseguir el desplazamiento necesario a partir del comienzo del segmento, para alcanzar el vector donde toma lugar la colisión.

El grafico siguiente muestra la situación actual.

donde:

n es la normal del plano
v es un punto conocido del plano (un vértice del triangulo)
s es el vector de inicio del segmento
e es el vector de finalización del segmento

Bien, anteriormente dije que hallaríamos el desplazamiento desde el punto s y la intersección entre el plano y dicho segmento. Esto es relativamente sencillo, lo que haremos será calcular un porcentaje del segmento, cuya longitud será la distancia entre el punto de inicio s, y el punto de colisión. La siguiente figura muestra un poco mejor a lo que me refiero.

Bien, hallemos primero dicho porcentaje. Contamos con dos vectores para hacerlo: 

(1)  El vector entre las puntas del segmento (e-s)
(2)  El que va entre el comienzo (s) y el punto conocido del plano (v)
 

Estos dos vectores nos darán la distancia que llamaremos TOTAL, que es el largo del vector (1) proyectado sobre la normal, la (máxima) distancia que se puede recorrer entre el punto s y e, por ultimo, la distancia entre el inicio del segmento y el plano, que es el vector (2) proyectado sobre la normal del mismo. A esta distancia la llamaremos MEDIA.

Bien, la forma de calcular ambas distancias será la siguiente:

Sabemos que como mucho, MEDIA puede tener el mismo valor que TOTAL, pero nunca será mayor, de modo que el cociente MEDIA/TOTAL será siempre un valor entre 0 y 1. Dicho valor es el porcentaje que estamos buscando. Entonces, 

Finalmente, necesitamos calcular el vector desplazamiento entre el punto s y el punto de encuentro entre el plano y el segmento, debido a que conocemos el porcentaje de segmento entre ambos puntos, podemos calcular el vector fácilmente, haciendo

Y finalmente, el vector donde tiene lugar la colisión, será

Ya tenemos el punto de colisión, este punto hallado estará dentro del plano (de modo que satisface la ecuación del mismo), ahora solo debemos determinar si dicho punto esta dentro del triangulo.

Determinando si el punto esta dentro del triangulo

La situación actual es la que muestra la figura.

Debemos detectar si el punto i esta dentro del triangulo formado por los vértices v1, v2, v3, lo que haremos será generar tres planos, uno por cada lado del triangulo. Luego, si el punto i esta delante de los tres planos simultáneamente, entonces estará dentro del triangulo. La siguiente figura muestra la situación gráficamente,

donde los sectores marcados con un ‘0’ están fuera del triangulo, y los marcados con ‘1’ están dentro.

De los nuevos planos solo debemos calcular las normales, debido a que los puntos de paso de ellos serán los vértices del triangulo, calculemos pues, dichos planos. (los vectores siguientes al  ---> corresponden a los puntos de paso).

Bien, ya tenemos casi todo hecho,  solo debemos ver si el punto esta delante de los 3 planos generados, esto es una pequeña comprobación utilizando producto punto, y su algoritmo es el siguiente:

donde:

p es el punto en cuestión
v es el punto conocido del plano
n es la normal del plano

si no se cumple ninguna de las dos condiciones, se dice que p esta en el plano.

La comprobación resulta sencilla ahora, supongamos que tenemos una función clas, a la que pasándole como parámetros p, v y n, nos retorna 3 valores, 

1 el punto esta detrás
2 el punto esta delante
3 el punto esta en el plano

Podríamos hacer lo siguiente,

Si clas(p, v1, n1) = clas(p, v2, n2) = clas(p, v3, n3) ----> punto DENTRO

Si la función clas devuelve el mismo valor para los tres planos (sea el valor que sea), entonces el plano estará dentro del triangulo (si queres comprobar esto, dibuja en una hoja de papel un triangulo, muchos puntos al azar, y fijate que solo clas devolverá lo mismo si el punto esta dentro) 

He presentado un algoritmo de deteccion de colision Ray-Triangle.

Bien, hemos terminado con la teoría de la intersección RAY-TRIANGLE. La implementacion es bastante sencilla y no deberia traer problema alguno, de todas formas, si asi lo fuere, no dude en consultarme por alguno de los siguientes medios:

msn & mail: silencer_ar@hotmail.com
phone: 4842-6705 (voice!)

rodrigo pelorosso [silencer/darkdesigns]
8/11/03