Marching Tetrahedra es un algoritmo en el campo de los gráficos por computadora para representar superficies implícitas . Aclara un problema de ambigüedad menor del algoritmo de cubos en marcha con algunas configuraciones de cubos. Se introdujo originalmente en 1991. [1]
Mientras que el algoritmo original de los cubos en marcha estaba protegido por una patente de software , los tetraedros en marcha ofrecían un algoritmo alternativo que no requería una licencia de patente. Han pasado más de 20 años desde la fecha de presentación de la patente (5 de junio de 1985), y ahora el algoritmo de los cubos en marcha se puede utilizar libremente. Opcionalmente, las pequeñas mejoras de los tetraedros en marcha se pueden utilizar para corregir la ambigüedad antes mencionada en algunas configuraciones.
En los tetraedros en marcha , cada cubo se divide en seis tetraedros irregulares cortando el cubo por la mitad tres veces, cortando diagonalmente cada uno de los tres pares de caras opuestas. De esta manera, todos los tetraedros comparten una de las diagonales principales del cubo. En lugar de las doce aristas del cubo, ahora tenemos diecinueve aristas: las doce originales, seis diagonales de las caras y la diagonal principal. Al igual que en los cubos en marcha , las intersecciones de estas aristas con la isosuperficie se aproximan interpolando linealmente los valores en los puntos de la cuadrícula.
Los cubos adyacentes comparten todos los bordes de la cara que los conecta, incluida la misma diagonal. Esta es una propiedad importante para evitar grietas en la superficie renderizada, ya que la interpolación de las dos diagonales distintas de una cara generalmente da como resultado puntos de intersección ligeramente diferentes. Un beneficio adicional es que se pueden reutilizar hasta cinco puntos de intersección calculados al manipular el cubo vecino. Esto incluye las normales de superficie calculadas y otros atributos gráficos en los puntos de intersección.
Cada tetraedro tiene dieciséis configuraciones posibles, que se dividen en tres clases: sin intersección, intersección en un triángulo e intersección en dos triángulos (adyacentes). Es sencillo enumerar las dieciséis configuraciones y asignarlas a listas de índices de vértices que definen las franjas de triángulos adecuadas .
Los tetraedros en marcha calculan hasta diecinueve intersecciones de aristas por cubo, mientras que los cubos en marcha solo requieren doce. Solo una de estas intersecciones no se puede compartir con un cubo adyacente (el de la diagonal principal), pero compartir en todas las caras del cubo complica el algoritmo y aumenta considerablemente los requisitos de memoria. Por otro lado, las intersecciones adicionales proporcionan una resolución de muestreo ligeramente mejor.
El número de configuraciones, que determina el tamaño de las tablas de búsqueda que se utilizan habitualmente , es mucho menor, ya que solo se utilizan cuatro vértices separados en lugar de ocho por tetraedro. Hay seis tetraedros para procesar en lugar de un solo cubo. El proceso es inequívoco, por lo que no es necesario gestionar ambigüedades adicionales.
La desventaja es que la teselación de un cubo con tetraedros requiere una elección con respecto a la orientación de los tetraedros, lo que puede producir "protuberancias" artificiales en la isosuperficie debido a la interpolación a lo largo de las diagonales de las caras. [2]
Las celdas cúbicas que se van a mallar también se pueden cortar en 5 tetraedros, [3] utilizando una red ( cúbica de diamante ) como base. Los cubos se acoplan en cada lado con otro que tiene una alineación opuesta del tetraedro alrededor del centroide del cubo. Los vértices alternos tienen un número diferente de tetraedros que se intersecan en ellos, lo que da como resultado una malla ligeramente diferente según la posición. Cuando se corta de esta manera, se proporcionan planos de simetría adicionales; tener un tetraedro alrededor del centroide del cubo también genera espacios muy abiertos alrededor de los puntos que están fuera de la superficie.
El cubo de diamante tiene una variedad de visualizaciones. En lugar de celdas vacías, cada celda debe estar llena, con tetraedros internos alternados. Para cada tetraedro inscrito en un cubo, utilizando los vértices del cubo y las aristas que cruzan las caras del cubo, el tetraedro ocupará 4 puntos; los otros 4 puntos forman las esquinas de un tetraedro invertido; las celdas cúbicas están dispuestas en mosaico de tal manera que la posición de la celda (x+y+z+...) es impar, use una, de lo contrario use la invertida; de lo contrario, las celdas cercanas usarían una diagonal diferente para calcular la intersección.
El cálculo del color basado en un sistema de textura espacial [4] se puede realizar utilizando la posición actual del fragmento para seleccionar una textura repetida basada en los pares de coordenadas de texel (x, y), (y, z) y (x, z) y escalando esos valores por el valor absoluto de cada componente respectivo de la normal z, x e y respectivamente. El decalado de textura se puede aplicar como salpicado de textura proyectando la posición del fragmento actual en la dirección de la normal del decalado, al plano de la textura dado por un punto de origen y una normal, luego utilizando un vector direccional "arriba" o "derecha" para calcular la coordenada de textura.
Esta técnica se compararía más de cerca con el contorneado dual que se enumera en isosuperficies , como una técnica potencial. Los tetraedros DCL implican cálculos adicionales para las diagonales a través de las caras del cubo, mientras que el contorneado dual no lo hace. Esta técnica tampoco ha abordado el caso en el que dos puntos cercanos 'dentro' de una superficie están a una distancia combinada < 1 de la superficie, donde deberían generar dos puntos en el borde en lugar de 1; la modificación relacionada es el contorneado dual de colectores. [5]
{{cite web}}: CS1 maint: numeric names: authors list (link){{cite web}}: CS1 maint: numeric names: authors list (link)