algorithm - Encuentra si dos triángulos se intersecan o no

language-agnostic geometry

Question

Dado 2 conjunto de puntos

((x1, y1, z1), (x2, y2, z2), (x3, y3, z3)) y

((p1, q1, r1), (p2, q2, r2), (p3, q3, r3)) formando cada uno un triángulo en el espacio 3D.

¿Cómo descubrirás si estos triángulos se intersecan o no?

Una solución obvia para este problema es encontrar la ecuación del plano formado por cada triángulo. Si los planos son paralelos, entonces no se intersecan.

De lo contrario, averigüe la ecuación de la línea formada por la intersección de estos planos utilizando los vectores normales de estos planos.

Ahora, si esta línea se encuentra en ambas regiones triangulares, entonces estos dos triángulos se intersecan, de lo contrario no.

trianglesIntersect(Triangle T1, Triangle T2)
{
   if(trianglesOnParallelPlanes(T1, T2))
   {
      return false
   }
   Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))
   if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1))
   {
      return true
   }
   return false
}

Dado que sé cómo escribir las funciones anteriores, ¿qué otras implementaciones de trianglesIntersect debo considerar?

¿Hay algoritmos más rápidos que resuelvan este problema?

Answer 1

Visite esta tabla de algoritmos de intersección geométrica, cortesía de realtimerendering.com , busque la entrada de intersecciones triángulo / triángulo y siga las referencias, por ejemplo a Christer Ericson, Detección de colisión en tiempo real , página 172. (Un libro que recomiendo altamente .)

La idea básica es sencilla. Si dos triángulos se intersecan, entonces dos bordes de un triángulo se intersecan con el otro (configuración izquierda en el diagrama a continuación), o un borde de cada triángulo se interseca con el otro (configuración derecha).

Así que realice seis pruebas de intersección de triángulos y segmentos de línea y vea si se encuentra alguna de estas configuraciones.

Ahora, usted pregunta, ¿cómo hace una prueba de intersección de segmento de línea / triángulo? Bueno, es fácil. Visite esta tabla de algoritmos de intersección geométrica , mire la entrada para intersecciones de segmentos de línea (rayo) / triángulo y siga las referencias ...

(Es importante mencionar que la prueba simple descrita anteriormente no maneja correctamente los triángulos coplanares. Para muchas aplicaciones esto no importa: por ejemplo, cuando se detecta una colisión entre mallas de triángulos, los casos coplanares son ambiguos, por lo que no importa cuál se devuelve el resultado. Pero si su aplicación es una de las excepciones, deberá verificar esto como un caso especial, o leer en Ericson otros métodos, por ejemplo, el método del eje de separación o el intervalo de Tomas Möller. método de superposición .)