cubos marchantes

El algoritmo Marching Cubes es un algoritmo de gráficos por computadora , publicado en las actas de SIGGRAPH de 1987 por Lorensen y Cline, ^{[ 1 ]} para extraer una malla poligonal de una isosuperficie a partir de un campo escalar discreto tridimensional (cuyos elementos a veces se denominan vóxeles ). Las aplicaciones de este algoritmo se centran principalmente en visualizaciones médicas, como imágenes de datos de tomografía computarizada (TC) y resonancia magnética (RM ), y efectos especiales o modelado 3D con lo que se suele llamar metabolas u otras metasuperficies. El algoritmo Marching Cubes está diseñado para usarse en 3D; la versión 2D de este algoritmo se denomina algoritmo Marching Squares .

El algoritmo fue desarrollado por William E. Lorensen (1946-2019) y Harvey E. Cline como resultado de su investigación para General Electric . En General Electric trabajaron en una forma de visualizar eficientemente los datos de los dispositivos de tomografía computarizada (TC) y resonancia magnética (RM). ^{[ 2 ]}

La premisa del algoritmo consiste en dividir el volumen de entrada en un conjunto discreto de cubos. Al asumir un filtrado de reconstrucción lineal , cada cubo, que contiene una porción de una isosuperficie dada, se puede identificar fácilmente, ya que los valores de muestra en los vértices del cubo deben abarcar el valor de la isosuperficie objetivo. Para cada cubo que contiene una sección de la isosuperficie, se genera una malla triangular que aproxima el comportamiento del interpolante trilineal en el interior del cubo.

La primera versión publicada del algoritmo aprovechó la simetría rotacional y reflectiva, así como los cambios de signo, para construir la tabla con 15 casos únicos. Sin embargo, debido a la existencia de ambigüedades en el comportamiento de interpolación trilineal en las caras y el interior del cubo, las mallas extraídas por Marching Cubes presentaron discontinuidades y problemas topológicos. Dado un cubo de la cuadrícula, se produce una ambigüedad en una cara cuando sus vértices tienen signos alternos. Es decir, los vértices de una diagonal en esta cara son positivos y los vértices de la otra son negativos. Obsérvese que, en este caso, los signos de los vértices de la cara son insuficientes para determinar la forma correcta de triangular la isosuperficie. De manera similar, se produce una ambigüedad en el interior cuando los signos de los vértices del cubo son insuficientes para determinar la triangulación correcta de la superficie , es decir, cuando son posibles múltiples triangulaciones para la misma configuración del cubo.

La popularidad del Marching Cubes y su amplia adopción dieron lugar a varias mejoras en el algoritmo para abordar las ambigüedades y rastrear correctamente el comportamiento del interpolante. Durst ^{[ 3 ]} en 1988 fue el primero en señalar que la tabla de triangulación propuesta por Lorensen y Cline era incompleta, y que ciertos casos de Marching Cubes permiten múltiples triangulaciones. La "referencia adicional" de Durst fue a un algoritmo de poligonización de isosuperficies anterior y más eficiente (véase de Araujo ^{[ 4 ] ) de Wyvill, Wyvill y McPheeters. [ 5 ]} Posteriormente, Nielson y Hamann ^{[ 6 ]} en 1991 observaron la existencia de ambigüedades en el comportamiento del interpolante en la cara del cubo. Propusieron una prueba llamada Asymptotic Decider para rastrear correctamente el interpolante en las caras del cubo. De hecho, como observó Natarajan ^{[ 7 ]} en 1994, este problema de ambigüedad también ocurre dentro del cubo. En su trabajo, el autor propuso una prueba de desambiguación basada en los puntos críticos de interpolación y añadió cuatro nuevos casos a la tabla de triangulación de Marching Cubes (subcasos de los casos 3, 4, 6 y 7). En este punto, incluso con todas las mejoras propuestas al algoritmo y su tabla de triangulación, las mallas generadas por Marching Cubes aún presentaban incoherencias topológicas.

El Marching Cubes 33, propuesto por Chernyaev ^{[ 8 ]} en 1995, es uno de los primeros algoritmos de extracción de isosuperficies destinados a preservar la topología del interpolante trilineal. En su trabajo, Chernyaev extiende a 33 el número de casos en la tabla de búsqueda de triangulación. Luego propone un enfoque diferente para resolver las ambigüedades internas, que se basa en el Asymptotic Decider. Más tarde, en 2003, Nielson ^{[ 9 ]} demostró que la tabla de búsqueda de Chernyaev es completa y puede representar todos los comportamientos posibles del interpolante trilineal, y Lewiner et al. ^{[ 10 ]} propusieron una implementación del algoritmo. También en 2003, Lopes y Brodlie ^{[ 11 ]} extendieron las pruebas propuestas por Natarajan. ^{[ 7 ]} En 2013, Custodio et al. ^{[ 12 ]} observaron y corrigieron imprecisiones algorítmicas que comprometían la corrección topológica de la malla generada por el algoritmo Marching Cubes 33 propuesto por Chernyaev. ^{[ 8 ]}

El algoritmo recorre el campo escalar, tomando ocho ubicaciones vecinas a la vez (formando así un cubo imaginario), y luego determina el o los polígonos necesarios para representar la parte de la isosuperficie que pasa por este cubo. Posteriormente, los polígonos individuales se fusionan para formar la superficie deseada.

Esto se logra creando un índice para una matriz precalculada de 256 posibles configuraciones de polígonos (2⁸ ⁼ 256) dentro del cubo, tratando cada uno de los 8 valores escalares como un bit en un entero de 8 bits. Si el valor del escalar es mayor que el isovalor (es decir, está dentro de la superficie), el bit correspondiente se establece en uno; si es menor (fuera), se establece en cero. El valor final, después de verificar los ocho escalares, es el índice real de la matriz de índices de polígonos.

Finalmente, cada vértice de los polígonos generados se coloca en la posición adecuada a lo largo de la arista del cubo mediante la interpolación lineal de los dos valores escalares que están conectados por dicha arista.

El gradiente del campo escalar en cada punto de la cuadrícula es también el vector normal de una isosuperficie hipotética que pasa por ese punto. Por lo tanto, estas normales pueden interpolarse a lo largo de las aristas de cada cubo para hallar las normales de los vértices generados, que son esenciales para sombrear la malla resultante con algún modelo de iluminación .

Una implementación del algoritmo de cubos marchantes fue patentada como la patente estadounidense 4,710,876. ^{[ 2 ]} Se desarrolló otro algoritmo similar, llamado tetraedros marchantes , para eludir la patente y resolver un pequeño problema de ambigüedad de los cubos marchantes con algunas configuraciones de cubos. La patente expiró en 2005, y ahora es legal que la comunidad gráfica la utilice sin regalías, ya que han transcurrido más de 20 años desde su fecha de emisión (1 de diciembre de 1987 ^{[ 2 ]} ).

• Isosuperficies 3D en CGAL , la biblioteca de algoritmos de geometría computacional.

• Mallado basado en imágenes
• tetraedros en marcha

• Lorensen, WE; Cline, Harvey E. (1987). "Marching cubes: Un algoritmo de construcción de superficies 3D de alta resolución". ACM SIGGRAPH Computer Graphics . 21 (4): 163– 169. CiteSeerX 10.1.1.545.613 . doi : 10.1145/37402.37422 . 
• Nielson, GM; Hamann, B. (1991). «El decisor asintótico: Resolviendo la ambigüedad en los cubos marchantes». Actas de Visualization '91 . págs. 83–91 . doi : 10.1109/VISUAL.1991.175782 . ISBN  9780818622458. S2CID 35739150 . 
• Montani, Claudio; Scateni, Riccardo; Scopigno, Roberto (1994). "Una tabla de búsqueda modificada para la desambiguación implícita de Marching Cubes". The Visual Computer . 10 (6): 353– 355. doi : 10.1007/BF01900830 . S2CID 31316542 . 
• Nielson, GM; Junwon Sung (1997). "Tetraedrización de volumen de intervalo". Actas. Visualization '97 (Cat. No. 97CB36155) . págs. 221–228 . doi : 10.1109/VISUAL.1997.663886 . ISBN  978-0-8186-8262-9. S2CID 5575097 . 
• Paul Bourke. "Descripción general y código fuente" .
• Matthew Ward. "Introducción al desarrollo de videojuegos" .
• "Descripción introductoria con gráficos adicionales" .
• "Cubos marchantes" .Algunos datos sobre la historia temprana de Marching Cubes.
• Newman, Timothy S.; Yi, Hong (2006). "Una revisión del algoritmo de cubos marchantes". Computers & Graphics . 30 (5): 854– 879. CiteSeerX 10.1.1.413.7458 . doi : 10.1016/j.cag.2006.07.021 . 
• Stephan Diehl. "Especialización en algoritmos de visualización" (PDF) . Archivado del original (PDF) el 24 de octubre de 2017. Consultado el 6 de febrero de 2013 .