Autor
|
Tema: Intersección linea - triángulo (Leído 7,680 veces)
|
BlackM4ster
Desconectado
Mensajes: 499
Error, el teclado no funciona. Pulse F1 para continuar
|
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: 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?
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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: 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: 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: 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! ..... !!!!
|
|
|
En línea
|
|
|
|
BlackM4ster
Desconectado
Mensajes: 499
Error, el teclado no funciona. Pulse F1 para continuar
|
Gracias por la respuesta, ahora estoy intentando aplicarlo en 3D, la cosa se complica
|
|
|
En línea
|
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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: 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! ..... !!!!
|
|
« Última modificación: 19 Julio 2014, 17:09 pm por leosansan »
|
En línea
|
|
|
|
avesudra
Desconectado
Mensajes: 724
Intentando ser mejor cada día :)
|
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: 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 3 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.
|
|
« Última modificación: 19 Julio 2014, 18:18 pm por avesudra »
|
En línea
|
Regístrate en
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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.
|
|
« Última modificación: 19 Julio 2014, 18:58 pm por leosansan »
|
En línea
|
|
|
|
avesudra
Desconectado
Mensajes: 724
Intentando ser mejor cada día :)
|
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.
|
|
« Última modificación: 19 Julio 2014, 18:49 pm por avesudra »
|
En línea
|
Regístrate en
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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.
|
|
|
En línea
|
|
|
|
avesudra
Desconectado
Mensajes: 724
Intentando ser mejor cada día :)
|
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=sharingMuchas gracias por tu visión de lo del triángulo. Quizás haga el código. Saludos.
|
|
|
En línea
|
Regístrate en
|
|
|
leosansan
Desconectado
Mensajes: 1.314
|
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! ..... !!!!
|
|
« Última modificación: 21 Julio 2014, 14:19 pm por leosansan »
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Reto - Intersección de 2 cubos
Ejercicios
|
[D4N93R]
|
4
|
7,923
|
19 Agosto 2010, 21:36 pm
por [D4N93R]
|
|
|
Calcular la intersección de dos segmentos
Programación C/C++
|
DickGumshoe
|
6
|
15,925
|
31 Octubre 2011, 23:11 pm
por DickGumshoe
|
|
|
Intersección de recta y punto
Programación C/C++
|
kaostias
|
4
|
3,787
|
26 Noviembre 2013, 18:23 pm
por kaostias
|
|
|
Intersección entre 3 circunferencias o más.
Foro Libre
|
xustyx
|
2
|
5,233
|
9 Abril 2015, 16:25 pm
por xustyx
|
|
|
Intersección de dos vectores
Programación C/C++
|
tokyo13
|
2
|
4,065
|
30 Junio 2019, 07:17 am
por CalgaryCorpus
|
|