7 votos

¿Cómo encuentro la intersección de dos triángulos 3D?

Tengo bastante complicada geometría problema que estoy tratando de resolver - cómo encontrar el punto de intersección entre dos triángulos en el espacio 3D. He mirado en otras preguntas y respuestas en este sitio y otros, pero ninguno de ellos parece satisfacer a mi pregunta.

De todos modos, dados dos triángulos en dos planos que se intersectan, y una línea de intersección (vector V), ¿cómo iba yo a ser capaz de decir si cualquier parte de la intersección de la línea está contenida en ambos triángulos?

Intersecting triangles

Hasta ahora he sido capaz, dados dos triángulos, encuentre sus dos planos, y el vector de dirección de la línea donde se intersectan. Creo que yo podría ser capaz de encontrar si la línea de intersección está contenida en un triángulo mediante la proyección en 2D, pero no estoy seguro de cómo encontrar si esa línea de intersección está contenida en ambos triángulos.

Como lo que yo puedo decir, no hay mucha documentación sobre el triángulo a triángulo de colisión, si alguien me pudiera decir el proceso paso a paso para encontrar la línea de intersección entre los triángulos (y/o si es que existe) en lugar de la línea de intersección entre los dos planos, que sería genial.

Por cierto, no estoy buscando un "conceptual" de la solución (hay un montón de que por ahí ya), pero me pregunto si alguien podría aclararme en las matemáticas para tal intersección de la prueba. Gracias!

EDITAR: He aquí un ejemplo de problema - si usted sería tan amable de mostrarme un paso a paso de la solución del problema, entonces, muchas gracias! :)

Example problem

Por cierto, cuando digo "encontrar la línea de intersección entre ellos", me refiero a un segmento de línea. (perdón por la errata)

5voto

Jeff Puntos 4795

Aquí hay una manera de hacerlo:

Paso 1: Determinar los planos determinados por los dos triángulos.

Paso 2a: Si están en el mismo plano, esto se ha convertido en una de dos dimensiones.

Paso 2b: Si los planos son diferentes, existen muchas opciones.

Paso 3: Los vértices del triángulo 1 no se puede estar todos en el mismo lado del plano determinado por el triángulo de 2. Del mismo modo, los vértices del triángulo 2 no pueden estar en el mismo lado del plano determinado por el triángulo 1. Si cualquiera de estas condiciones, los triángulos no se intersecan.

Paso 4: Considere la recta de intersección de los dos planos. Esta línea cruza ambos triángulos por el paso 3. Ahora, calcular la intersección (en dos dimensiones, la intersección es un segmento determinado por la intersección de la intersección de la línea con las líneas determinadas por los bordes de los triángulos.

Paso 5: Determinar si los segmentos (que están en la misma línea) se cruzan.

1voto

Jeff Puntos 4795

Hay un error de cálculo en este que no he encontrado, pero la idea va a funcionar. Las principales herramientas que voy a utilizar constan de elementos de álgebra lineal y cálculo multivariable. Muchos de estos cálculos se pueden realizar de dos maneras y voy a recoger lo que más me gusta. Para la programación de situaciones, algunas de estas operaciones son menos estables que otros, así que puede que tenga que reemplazar algunos de estos pasos con otras opciones.

Vamos $v_1=(0,5,0)$, $v_2=(0,0,0)$, y $v_3=(8,0,0)$ ser los vértices del triángulo $O$. Vamos $w_1=(6,8,3)$, $w_2=(6,8,-2)$, y $w_3=(6,-4,-2)$ ser los vértices del triángulo $Y$.

Paso 1: comenzamos por la determinación de los planos que contienen estos triángulos. La normal al plano que contiene a $O$ está dado por $$ (v_2-v_1)\times(v_3-v_1)=(0,5,0)\times(8,0,0)=(0,0,-40). $$ Por lo tanto, el plano que contiene a $O$ es $$ 0(x-0)+0(y-0)-40(z-0)=0. $$ En otras palabras, $z=0$.

La normal al plano que contiene a $Y$ está dado por $$ (w_2-w_1)\times(w_3-w_1)=(0,0,-5)\times(0,-12,-5)=(-60,0,0). $$ Por lo tanto, el plano que contiene a $Y$ es $$ -60(x-6)+0(y-8)+0(z-3)=0. $$ En otras palabras, $x=6$.

Paso 2: Ahora, vamos a determinar la línea de intersección de estos planos. La línea debe satisfacer $z=0$$x=6$, así como una matriz ampliada, tenemos $$ \begin{bmatrix} 1&0&0&6\\0&0&1&0 \end{bmatrix} $$ Esta matriz ya está en la reducción escalonada con $x=6$, $y$ una variable libre, y $z=0$. Por lo tanto, la línea de intersección es $(6,t,0)$.

El cómputo de la rref no siempre es numéricamente estable de operación, por lo que es posible que desee reemplazar este paso con tomar el producto vectorial de los vectores normales de los planos para obtener la dirección de la línea de intersección, y encontrar un buen punto en la línea de intersección.

Paso 3: Encontrar la intersección de la línea y el triángulo $O$. La línea que contiene a $v_1$ $v_2$ dirección $v_2-v_1=(0,5,0)$ y pasa a través del punto de $(0,0,0)$, por lo que su fórmula es $$ (0+0,0+5s,0+0)=(0,5 s,0). $$ (He cambiado las variables debido a que ya he utilizado $t$ en la fórmula anterior). Los otros lados del triángulo está dada por las líneas $$ (0+8s,0+0,0+0)=(8,0,0) $$ y $$ (8-8,5s,0)=(8-8,5,0). $$ (Tenga cuidado acerca de la configuración, usted realmente quiere escribir $sv_1+(1-s)v_2$, de modo que cuando se $s=0$, se obtiene uno de los extremos y al $s=1$, se obtiene el otro extremo.)

Para encontrar los puntos de intersección, se debe resolver tres sistemas de ecuaciones. La primera es para cruzar la línea de intersección con el primer lado del triángulo. El primer sistema de ecuaciones es $$ 6=0\qquad t=5s\qquad 0=0 $$ La forma de la matriz es $$ \begin{bmatrix} 0&0&6\\ 1&-5&0\\ 0&0&0 \end{bmatrix} $$ Este sistema no tiene solución, así que no hay punto de intersección.

El segundo sistema es $$ 6=8\qquad t=0\qquad 0=0 $$ La forma de la matriz es $$ \begin{bmatrix} 0&8&6\\ 1&0&0\\ 0&0&0 \end{bmatrix} $$ La solución a este sistema es$t=0$$s=\frac{6}{8}=\frac{3}{4}$. Puesto que el $s$-valor es entre el$0$$1$, este punto se encuentra en el lado del triángulo. Este punto es $(6,0,0)$.

El tercer sistema es $$ 6=8-8\qquad t=5s\qquad 0=0 $$ La matriz correspondiente es $$ \begin{bmatrix} 0&8&2\\ 1&5&0\\ 0&0&0\\ \end{bmatrix} $$ Este sistema tiene una solución, $s=\frac{1}{4}$$t=\frac{5}{4}$. Por lo tanto, el punto de intersección es $(6,\frac{5}{4},0)$.

Por lo tanto, el segmento en el primer triángulo entre el$(6,0,0)$$(6,\frac{5}{4},0)$. Esto es entre $t=0$$t=\frac{5}{4}$.

Para el triángulo $Y$, no voy a mostrar todo el trabajo, pero le dan las luces. Las líneas de los lados de los triángulos están dadas por $(6,8,3-5s)$, $(6,8-12s,3-5s)$, y $(6,8-12s,-2)$.

La primera línea se cruza en el $t=8$$s=\frac{3}{5}$, que corresponde al punto de $(6,8,0)$. La segunda línea se cruza en el $t=\frac{4}{5}$$s=\frac{3}{5}$, que corresponde al punto de $(6,\frac{4}{5},0)$. La tercera línea no se intersectan las intersecciones de los planos.

Ahora, el primer triángulo se cruza la línea de interés entre el$t=0$$t=\frac{5}{4}$, mientras que el segundo triángulo cruza entre el$t=\frac{4}{5}$$t=8$. Intersección de estos dos segmentos da la intersección entre el $t=\frac{4}{5}$ $t=\frac{5}{4}$ (esto no es correcto, voy a buscar el error).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X