Encuentra todos los puntos con coordenadas enteras dentro del tetraedro

Question

Estoy tratando de encontrar todos los puntos con coordenadas enteras que se encuentran dentro de un tetraedro (quiero de alguna manera poder recorrerlos). Sé las coordenadas de los cuatro puntos (A, B, C, D) que definen el tetraedro.

Lo que estoy haciendo actualmente es encontrar el cuadro delimitador del tetraedro (coordenadas mínimas y máximas x, y, z de A, B, C, D) y luego hacer un bucle a través de todos los puntos dentro del cuadro delimitador. Para cada punto, calculo las coordenadas baricéntricas (usando the equations from Wikipedia) y verifico si el punto está dentro del tetraedro (si alguna de las coordenadas baricéntricas es negativa o mayor que 1, el punto no está adentro).

¿Hay una mejor manera de hacerlo? Actualmente hay alrededor de 1/6 de posibilidades de que el punto que estoy probando (desde el recuadro delimitador) esté realmente dentro del tetraedro, así que creo que estoy haciendo demasiados cálculos innecesarios.

Estoy trabajando con una lista de tetraedros que generé triangulando un volumen mayor (estoy expandiendo el volumen y quiero interpolar los valores perdidos mediante la interpolación tetraédrica). No estoy usando ninguna biblioteca externa.

Answer 1

Otra idea para la mejora de:

de verificación si una "barra" parrallel a eje z (es decir, x = 4, y = 6) se ejecuta a través del tetraedro. Si no, ningún valor con (x = 4, y = 5, z) puede estar dentro.

De lo contrario, busque donde la varilla se cruza con el borde del tetraedro (descubriendo dónde se cruzan los planos que forman el borde del tetraedro).

Supongamos que estos planos se cruzan en z = 1.3 yz = 10.04. Entonces sabrá que todos los puntos (4,5, 2) a (4,5,10) están dentro.

Repita para todos los valores de x y y.

Esto debería ser más rápido en la práctica, porque le ahorrará 1 bucle.

Answer 2

Su enfoque es el correcto. Hay algunas optimizaciones posibles, que pueden valer la pena o no según los requisitos. Por ejemplo:

Hay una manera más fácil de verificar si un punto dado está dentro o fuera del tetraedro. Esto equivale a verificar a qué mitad del espacio pertenece el punto con respecto a cada uno de los 4 lados del tetraedro:

Cada lado está definido por 3 puntos (digamos A, B, C). Entonces, un plano normal es un (C-A) x (B-A) (que es un producto cruzado de vectores en el plano). Si estas coordenadas son (a, b, c), entonces la ecuación del plano es F(x,y,z) = ax+by+cz = 0. Para un punto dado (x0, y0, z0), el signo de F (x0, y0, z0) determina a qué semiplano pertenecen los puntos.

El punto es que puede calcular previamente las estaciones de avión para cada lado del tetraedro así como el signo que corresponde a 'afuera' y luego el control de un punto dado equivale a hacer como máximo 4 evaluaciones (una para cada lado), cada uno teniendo 3 multiplicaciones y 2 adiciones.