Intersección linea - triángulo

[BlackM4ster]

Hola, llevo un tiempo intentando dar con un algoritmo para detectar el punto de intersección (si existe) entre una linea (rayo) y un triángulo. ¿Alguno tiene implementado ya ésto?
Los parámetros a pasar serían:

Código (cpp) [Seleccionar] Expandir

Vec3f InterseccionRayoTriangulo(Vec3f T1, Vec3f T2, Vec3f T3, Vec3f R1, Vec3f R2)

Siendo T1, T2 y T3 los vértices del triángulo y R1 y R2, los puntos de la linea.

Alguna idea?

[leosansan]

Hola, llevo un tiempo intentando dar con un algoritmo para detectar el punto de intersección (si existe) entre una linea (rayo) y un triángulo. ¿Alguno tiene implementado ya ésto?
Los parámetros a pasar serían:

Código (cpp) [Seleccionar] Expandir

Vec3f InterseccionRayoTriangulo(Vec3f T1, Vec3f T2, Vec3f T3, Vec3f R1, Vec3f R2)

Siendo T1, T2 y T3 los vértices del triángulo y R1 y R2, los puntos de la linea.

Alguna idea?

Supongo que T1 y compañía son tipo estrctura donde tienes los vértices de cada uno.

Lo primero es la nomenclatura:

Código (cpp) [Seleccionar] Expandir


a = ( y2 - y1 ) / ( x2 - x1 ) ///para recta R1 R2
b = y1 - a * x1               ///para recta R1 R2

A = ( Y2 - Y1 ) / ( X2 - X1 ) ///para una de las Tini Tfinal
B = Y1 - A * X1               ///para una de las Tini Tfinal


donde con minúsculas represento a la recta R1 R2 y con mayúsculas a una de las rectas del triángulo y habrá que hacerlo para cada una de las tres rectas del triángulo, siempre con la misma R1 R2.

Y al meollo de la cuestión, dónde se cortan:

Código (cpp) [Seleccionar] Expandir

if ( a = A )
  /** no se corta pues son paralelas // **/
else
  /** se cortan y el punto de corte es: **/

  x = ( B - b ) / ( a - A )
 
  y = ( a * B - A * b ) / ( a - A )

Así de simple. Existen otros métodos pero como supongo que trabajas con las coordenadas de los vértices me parece el mejor.

Espero no haberla pifiado al copiar los datos, no obstante lo he comprobado con un par de casos y va bien.

¡¡¡¡ Saluditos! ..... !!!!

[BlackM4ster]

Gracias por la respuesta, ahora estoy intentando aplicarlo en 3D, la cosa se complica

[leosansan]

Gracias por la respuesta, ahora estoy intentando aplicarlo en 3D, la cosa se complica

Un poquitín solamente.

Sin entrar demasiado a estudiar la poscición relativa de las rectas, por entrar de lleno en el meollo del problema, tendrías:

Código (cpp) [Seleccionar] Expandir

vector de la recta R1 R2:
vx  = ( x2 - x1 ) ... vy  = ( y2 - y1 ) ... vz  = ( z2 - z1 )  

ecuacion continua de la recta R1 R2:
( x - x1 ) / vx = ( y - y1 ) / vy = ( z - z1 ) / vz

ecuaciones implicitas de la recta R1 R2:
vz * x - z * vx = x1 * vz - z1 * vx (1)
vz * y - z * vy = y1 * vz - z1 * vy (2)

vector de la recta T1 T2:
wx  = ( X2 - X1 ) ... wy  = ( Y2 - Y1 ) ... wz  = ( Z2 - Z1 )  

ecuacion continua de la recta T1 T2:
( x - X1 ) / wx = ( y - Y1 ) / wy = ( z - Z1 ) / wz

ecuaciones implicitas de la recta T1 T2:
wz * x - z * wx = X1 * wz - Z1 * wx (3)
wz * y - z * wy = Y1 * wz - Z1 * wy (4)


 if ( vx / wx = vy / wy = vz / wz )
   son paralelas o coincidentes ==> no punto de corte
 else
   resolver las ecuciones (1), (2), (3) , por ejemplo por la regla de Cramer,
   y sustituir el punto obtenido en (4). Si se cumple la igualdad de (4)
   es que es el punto de corte, si no se cruzan y no hay corte.


Espero que te sea útil.  

¡¡¡¡ Saluditos! ..... !!!!

[avesudra]

Un poquitín solamente.

Sin entrar demasiado a estudiar la poscición relativa de las rectas, por entrar de lleno en el meollo del problema, tendrías:

Código (cpp) [Seleccionar] Expandir

vector de la recta R1 R2:
vx  = ( x2 - x1 ) ... vy  = ( y2 - y1 ) ... vz  = ( z2 - z1 )  

ecuacion continua de la recta R1 R2:
( x - x1 ) / vx = ( y - y1 ) / vy = ( z - z1 ) / vz

ecuaciones implicitas de la recta R1 R2:
vz * x - z * vx = x1 * vz - z1 * vx (1)
vz * y - z * vy = y1 * vz - z1 * vy (2)

vector de la recta T1 T2:
wx  = ( X2 - X1 ) ... wy  = ( Y2 - Y1 ) ... wz  = ( Z2 - Z1 )  

ecuacion continua de la recta T1 T2:
( x - X1 ) / wx = ( y - Y1 ) / wy = ( z - Z1 ) / wz

ecuaciones implicitas de la recta T1 T2:
wz * x - z * wx = X1 * wz - Z1 * wx (3)
wz * y - z * wy = Y1 * wz - Z1 * wy (4)


 if ( vx / wx = vy / wy = vz / wz )
   son paralelas o coincidentes ==> no punto de corte
 else
   resolver las ecuciones (1), (2), (3) , por ejemplo por la regla de Cramer,
   y sustituir el punto obtenido en (4). Si se cumple la igualdad de (4)
   es que es el punto de corte, si no se cruzan y no hay corte.


Espero que te sea útil.  

¡¡¡¡ Saluditos! ..... !!!!

Saludos Leosansan el problema que se plantea aquí es mucho mayor que calcular el corte entre dos rectas, pues en este problema calculando las intersecciones con las tres rectas que forman los tres segmentos del triangulo y la recta que dirige el rayo no has acabado. Simple y llanamente porque la recta puede cortar justo en el centro del triángulo sin cortar a las rectas anteriormente mencionadas, y ante ese planteamiento el método que has posteado es solamente útil cuando el problema se limite solo a Recta-Recta, pero aquí estamos hablando de Recta-Triángulo o rigurosamente hablando a Recta-Plano y solo en una región del plano determinada.

Considerando el problema en más profundidad el corte entre la Recta del rayo y el Plano del triángulo daría un punto de corte, que además habría que comprobar si está dentro del triángulo, cosa que es bastante complicada y que estoy ahora mismo mirando.

La geometría euclídea en un espacio de R³ es bastante complicada en mi opinión cuando se trata de estos casos en los que hay que restringir un elemento aunque será para mí que tengo pocos conocimientos de matemáticas.

Un cordial saludo.

[leosansan]

Saludos Leosansan el problema que se plantea........................ aquí estamos hablando de Recta-Triángulo o rigurosamente hablando a Recta-Plano y solo en una región del plano determinada.

Considerando el problema en más profundidad el corte entre la Recta del rayo y el Plano del triángulo daría un punto de corte, que además habría que comprobar si está dentro del triángulo, cosa que es bastante complicada y que estoy ahora mismo mirando.
..................................

El que planteas es otro punto de vista, válido por supuesto.

Y si ese es el caso bastaría con hallar el punto de corte del rayo con el plano y después determinar si dicho punto es interior o no.

1.*

Para lo primero se resuelve el determinante formado por (x-x1,y-y1,z-z1), siendo (x1,y1,z1) uno de los tres vértices del triángulo y los dos vectores (vx,vy,vz) y (wx,wy,wz) correspondientes a, por ejemplo, T1T2 y T1T3. Ello nos dará la ecuación del plano de la forma típica Ax+By+Cz+D=0.

A continuación se sustituye la recta del rayo en forma paramétrica, donde (ax,ay,az) es el vector del rayo y (X1,Y1,Z1) un punto del mismo (no "problem" porque tenemos dos puntos del rayo por lo que podemos hallar tanto el vector  como un punto del mismo):

x=X1+ax*t
y=X1+ay*t
z=Z1+az*t

como decía, se sustituyen las ecuaciones anteriores en la ecuación del plano, de donde se obtiene el valor de "t" que sustituido en las anteriores ecuaciones paramétricas nos dan el valor del punto intersección del rayo con el plano.

2.*
Ahora queda determinar si es interior o exterior para lo cual hay multitud de métodos. Uno simple, ya que su uso sólo implica calcular áreas de triángulos cosa que es fácil con el producto "vectorial", consiste en calcular las áreas de los triángulos PcorteT1T2, PcorteT2T3, PcorteT3T1 y si es igual al área del triángulo T1T2T3 está dentro, si no está fuera.

Pero insisto es que es una de las diversa maneras de hacerlo, lo indico por la facilidad mencionada del calculo de las áreas.

Y esto dicho a toda pastilla, si me "asiento" un poco seguro que le buscamos la vuelta de una manera más sencilla.  

¡¡¡¡ Saluditos! ..... !!!!

EDITADO: Con la correción de producto vectorial por escalar. 

[avesudra]

El que planteas es otro punto de vista, válido por supuesto.

Y si ese es el caso bastaría con hallar el punto de corte del rayo con el plano y después determinar si dicho punto es interior o no.

1.*

Para lo primero se resuelve el determinante formado por (x-x1,y-y1,z-z1), siendo (x1,y1,z1) uno de los tres vértices del triángulo y los dos vectores (vx,vy,vz) y (wx,wy,wz) correspondientes a, por ejemplo, T1T2 y T1T3. Ello nos dará la ecuación del plano de la forma típica Ax+By+Cz+D=0.

A continuación se sustituye la recta del rayo en forma paramétrica, donde (ax,ay,az) es el vector del rayo y (X1,Y1,Z1) un punto del mismo (no "problem" porque tenemos dos puntos del rayo por lo que podemos hallar tanto el vector  como un punto del mismo):

x=X1+ax*t
y=X1+ay*t
z=Z1+az*t

como decía, se sustituyen las ecuaciones anteriores en la ecuación del plano, de donde se obtiene el valor de "t" que sustituido en las anteriores ecuaciones paramétricas nos dan el valor del punto intersección del rayo con el plano.

En efecto es justo lo que yo estaba escribiendo en latex, no se me había ocurrido lo de las áreas, muy inteligente por tu parte.

Un pequeño apunte, el área se calcula con el producto vectorial no con el escalar.

¡Un saludo! Publicaré el proceso cuando termine de escribirlo.

[leosansan]

En efecto es justo lo que yo estaba escribiendo en latex, no se me había ocurrido lo de las áreas, muy inteligente por tu parte.
..................................................

Gracias, gracias.

Sólo una pequeña observación, si alguno de los triángulos  PcorteT1T2, PcorteT2T3, PcorteT3T1 da de área cero es que el punto está "sobre" uno de los lados.

Un fuerte saludo avesudra.

[avesudra]

Gracias, gracias.

Sólo una pequeña observación, si alguno de los triángulos  PcorteT1T2, PcorteT2T3, PcorteT3T1 da de área cero es que el punto está "sobre" uno de los lados.

Un fuerte saludo avesudra.

Aquí está resuelto simbólicamente, ahora solo hay que implementarlo.

https://drive.google.com/file/d/0Bw0QWEQBKEXLMjl4ZEt0eVk1T00/edit?usp=sharing

Muchas gracias por tu visión de lo del triángulo. Quizás haga el código.

Saludos.

[leosansan]

Aquí está resuelto simbólicamente, ahora solo hay que implementarlo.
https://drive.google.com/file/d/0Bw0QWEQBKEXLMjl4ZEt0eVk1T00/edit?usp=sharing
Muchas gracias por tu visión de lo del triángulo. Quizás haga el código.
Saludos.

Al menos a mí no se me abre el pdf  

Otra opción, si no me falla la geometría,  para ver si el punto es interior o no es calcular los productos vectoriales PcorteT1xPcorteT2, PcorteT2xPcorteT3 ,PcorteT3xPcorteT1 y si son paralelos, o proporcionales tienen el mismo sentido es que el punto es interior. Con ello evitamos el calcular las áreas.

¡¡¡¡ Saluditos! ..... !!!!