geometría computacional, tetraedro firmó volumen

Question

No estoy seguro de si este es el lugar adecuado para preguntar, pero aquí va ...

versión corta: Estoy tratando de calcular la orientación de un triángulo en un avión, formado por la intersección de 3 aristas, sin calcular explícitamente los puntos de intersección.

Versión larga: Necesito triangular un PSLG en un triángulo en 3D. Los vértices del PSLG están definidos por las intersecciones de segmentos de línea con el plano a través del triángulo, y se garantiza que se encuentran dentro del triángulo. Asumiendo que tenía los puntos de intersección, podría proyectar a 2D y usar una prueba del lado de la línea de puntos (o triángulo con signo) para determinar la orientación de un triángulo entre cualquiera de los 3 puntos de intersección.

El problema es que no puedo calcular explícitamente los puntos de intersección debido al error de coma flotante que se acumula cuando encuentro la intersección del plano de línea. Para averiguar si los segmentos de línea chocan con el triángulo en primer lugar, estoy usando algunos predicados geométricos robustos disponibles libremente, que dan el signo del volumen de un tetraedro, o de manera equivalente en qué lado de un avión se encuentra un punto. Puedo determinar si los puntos finales del segmento de línea están en lados opuestos del plano a través del triángulo, luego formar tetraedros entre el segmento de línea y cada borde del triángulo para determinar si el punto de intersección se encuentra dentro del triángulo.

Como no puedo calcular explícitamente los puntos de intersección, me pregunto si hay una forma de expresar el mismo cálculo de oriente 2D en 3D usando solo los puntos originales. Si hay 3 bordes golpeando el triángulo que me da 9 puntos en total para jugar. Asumiendo que lo que estoy preguntando es incluso posible (utilizando solo las pruebas de orientación 3D), entonces supongo que tendré que formar un subconjunto de todos los tetraedros posibles entre esos 9 puntos. Estoy teniendo dificultades incluso para visualizar esto, y mucho menos destilarlo en una fórmula o código. Ni siquiera puedo googlear esto porque no sé cuál sería la terminología estándar de la industria para este tipo de problema.

¿Alguna idea de cómo proceder con esto? Gracias. Tal vez debería preguntar también a MathOverflow ...

EDITAR: Después de leer algunos de los comentarios, una cosa que se me ocurre ... Tal vez si pudiera ajustar tetraedros no superpuestos entre los 3 segmentos de línea, entonces la orientación de cualquiera de los que cruzaron el avión sería la respuesta que estoy buscando. Además de cuando los bordes encierran un simple prisma triangular, no estoy seguro de que este sub-problema sea solucionable tampoco.

EDITAR: La imagen solicitada.

Answer 1

Estoy respondiendo esto en ambos MO & SO, ampliando los comentarios que hice en MO.

Mi sensación es que ningún truco computacional con volúmenes de tetraedros firmados evitará los problemas de precisión que son su principal preocupación. Esto se debe a que, si tiene segmentos estrechamente retorcidos, la orientación del triángulo depende de la posición precisa del plano de corte.
[imagen eliminada; véase más adelante]
En el ejemplo anterior, el plano superior atraviesa los segmentos en el orden (a, b, c) [CCW desde arriba]: (rojo, azul, verde), mientras que el plano inferior cruza en el orden inverso (c, b, a): (verde, azul, rojo). La altura del plano de corte podría determinarse con su último bit de precisión.

En consecuencia, creo que tiene sentido simplemente seguir adelante y calcular los puntos de intersección en el plano de corte , con suficiente precisión para hacer el cálculo exacto. Si las coordenadas de punto final de su segmento y los coeficientes del plano tienen L bits de precisión, entonces solo se necesita un pequeño aumento de factor constante. Aunque no estoy seguro de qué es exactamente ese factor, es pequeño, quizás 4. No necesitará, por ejemplo, L bits, porque el cálculo resuelve ecuaciones lineales. Así que no habrá una explosión en la precisión requerida para calcular esto exactamente.

¡Buena suerte!

(I se le impidió la publicación de la imagen aclarar porque no tienen la reputación Ver la MO answer lugar..)

Editar: Hacer ver la respuesta MO, pero aquí está la imagen:

Answer 2

que iba a escribir ecuaciones vectoriales simbólicos, ya sabes, con punto cruz y productos, para encontrar la normal del triángulo de intersección. Entonces, el signo del producto de puntos de esta normal con el triángulo inicial uno da la orientación. Así que finalmente puedes expresar esto en un signo de forma (F (p1, ..., p9)), donde p1 a p9 son tus puntos y F() es una fórmula fea que incluye puntos y productos cruzados de diferencias (pi-pj) . No sé si esto puede hacerse más simple, pero este enfoque general hace el trabajo.

Answer 3

Según tengo entendido, tiene tres líneas que se cruzan con el plano, y ¿desea calcular la orientación del triángulo formado por los puntos de intersección, sin calcular los puntos de intersección?

Si es así: que tienen un avión

 
N·(x - x0) = 0 

y seis puntos ...

 
l1a, l1b, l2a, l2b, l3a, l3b 

... formando tres líneas

 
l1 = l1a + t(l1b - l1a) 
l2 = l2a + u(l2b - l2a) 
l3 = l3a + v(l3b - l3a) 

Los puntos de intersección de estas líneas al plano ocurren a valores específicos de t, u, v, que me van a llamar t _i, u _i, v _i

 
N·(l1a + ti(l1b - l1a) - x0) = 0 

     N·(x0 - l1a) 
ti = ---------------- 
     N·(l1b - l1a) 
(similarly for ui, vi) 

entonces los puntos de intersección son específicos

 
intersect1 = l1a + ti(l1b - l1a) 
intersect2 = l2a + ui(l2b - l2a) 
intersect3 = l3a + vi(l3b - l3a) 

Por último, la orientación de su triángulo es

 
orientation = direction of (intersect2 - intersect1)x(intersect3 - intersect1) 

(x está entre productos) trabajar hacia atrás tapando los valores, y usted tiene una ecuación para la orientación basada sólo en N , x , y sus seis puntos.

Answer 4

Vamos a llamar a su triángulo de vértices T[0], T[1], T[2], y los puntos finales del primer segmento de línea son L[0] y L[1], el segundo es L[2] y L[3], y el tercero es L[4] y L[5]. Imagino que desea una función

int Orient(Pt3 T[3], Pt3 L[6]); // index L by L[2*i+j], i=0..2, j=0..1 

que devuelve 1 si las intersecciones tienen la misma orientación que el triángulo, y -1 en caso contrario. El resultado debe ser simétrico en el intercambio de j valores, antisymmetric bajo intercambio de i índices y T índices. Siempre que pueda calcular una cantidad con estas simetrías, eso es todo lo que necesita.

Probemos

Sign(Product(Orient3D(T[i],T[i+1],L[2*i+0],L[2*i+1]) * -Orient3D(T[i],T[i+1],L[2*i+1],L[2*i+0])), i=0..2)) 

donde el producto debe tomarse más de permutaciones cíclicas de los índices (módulo 3). Creo que esto tiene todas las propiedades de simetría requeridas. Orient3D es la prueba de orientación de 4 puntos de Shewchuk, que supongo que está utilizando.