Marching cubes es un algoritmo de gráficos por computadora , publicado en las actas SIGGRAPH de 1987 por Lorensen y Cline, [1] para extraer una malla poligonal de una isosuperficie de un campo escalar discreto tridimensional (cuyos elementos a veces se denominan vóxeles ). Las aplicaciones de este algoritmo se refieren principalmente a visualizaciones médicas , como imágenes de datos de tomografía computarizada y resonancia magnética , y efectos especiales o modelado tridimensional con lo que generalmente se llaman metabolas u otras metasuperficies. El algoritmo de los cubos de marcha está destinado a usarse en 3-D; la versión 2-D de este algoritmo se llama algoritmo de cuadros de marcha .
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 de manera eficiente los datos de dispositivos CT y MRI. [2]
La premisa del algoritmo es dividir el volumen de entrada en un conjunto discreto de cubos. Al asumir un filtrado de reconstrucción lineal , cada cubo que contiene una parte de una isosuperficie determinada se puede identificar fácilmente porque 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 se aproxima al comportamiento del interpolante trilineal en el cubo interior.
La primera versión publicada del algoritmo aprovechó la simetría rotacional y reflexiva y también cambios de signo para construir la tabla con 15 casos únicos. Sin embargo, debido a la existencia de ambigüedades en el comportamiento interpolante trilineal en las caras e interior del cubo, las mallas extraídas por los Marching Cubes presentaron discontinuidades y problemas topológicos. Dado un cubo de la cuadrícula, se produce una ambigüedad de cara cuando los vértices de su cara tienen signos alternos. Es decir, los vértices de una diagonal de 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 interior cuando los signos de los vértices del cubo son insuficientes para determinar la triangulación de la superficie correcta , es decir, cuando son posibles múltiples triangulaciones para una misma configuración del cubo.
La popularidad de Marching Cubes y su adopción generalizada dieron como resultado 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 notar que la tabla de triangulación propuesta por Lorensen y Cline estaba 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 (ver 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 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 interpolantes y agregó 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 los Marching Cubes todavía tenían incoherencias topológicas.
Marching Cubes 33, propuesto por Chernyaev [8] en 1995, es uno de los primeros algoritmos de extracción de isosuperficies destinado a preservar la topología del interpolante trilineal. En su trabajo, Chernyaev amplía 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 interiores, que se basa en el Decididor Asintótico. Posteriormente, 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] propuso una implementación del algoritmo. También en 2003 Lopes y Brodlie [11] ampliaron 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 avanza a través del campo escalar, tomando ocho ubicaciones vecinas a la vez (formando así un cubo imaginario) y luego determina los polígonos necesarios para representar la parte de la isosuperficie que pasa a través de este cubo. Luego, los polígonos individuales se fusionan en la superficie deseada.
Esto se hace creando un índice para una matriz precalculada de 256 posibles configuraciones de polígonos (2 8 = 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 valor iso (es decir, está dentro de la superficie), entonces el bit apropiado se establece en uno, mientras que si es menor (fuera), se establece en cero. El valor final, después de comprobar los ocho escalares, es el índice real de la matriz de índices poligonales.
Finalmente, cada vértice de los polígonos generados se coloca en la posición apropiada a lo largo del borde del cubo interpolando linealmente los dos valores escalares que están conectados por ese borde.
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 desde ese punto. Por lo tanto, estas normales pueden interpolarse a lo largo de los bordes de cada cubo para encontrar las normales de los vértices generados que son esenciales para sombrear la malla resultante con algún modelo de iluminación .
Se patentó una implementación del algoritmo de los cubos en marcha como patente de Estados Unidos 4.710.876. [2] Se desarrolló otro algoritmo similar, llamado tetraedros en marcha , para eludir la patente y resolver un problema menor de ambigüedad de los cubos en marcha con algunas configuraciones de cubos. La patente expiró en 2005, y ahora es legal para la comunidad gráfica usarla sin regalías ya que han pasado más de 20 años desde su fecha de emisión (1 de diciembre de 1987 [2] ).
{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )