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 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ías computarizadas y resonancias magnéticas , y efectos especiales o modelado 3D con lo que generalmente se denomina metabolas u otras metasuperficies. El algoritmo de los cubos de marcha está pensado para usarse en 3D; la versión 2D de este algoritmo se denomina algoritmo de los cuadrados de marcha .
El algoritmo fue desarrollado por William E. Lorensen (1946-2019) y Harvey E. Cline como resultado de sus investigaciones para General Electric . En General Electric trabajaron en una forma de visualizar de manera eficiente los datos de los dispositivos de TC y RM. [2]
La premisa del algoritmo es dividir el volumen de entrada en un conjunto discreto de cubos. Al suponer un filtrado de reconstrucción lineal , cada cubo, que contiene una parte de una isosuperficie dada , se puede identificar fácilmente porque los valores de muestra en los vértices del cubo deben abarcar el valor de la isosuperficie de destino. Para cada cubo que contiene una sección de la isosuperficie, se genera una malla triangular que se aproxima al comportamiento del interpolador trilineal en el cubo interior.
La primera versión publicada del algoritmo explotó la simetría rotacional y reflexiva y también los 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 y el interior del cubo, las mallas extraídas por los Marching Cubes presentaron discontinuidades y problemas topológicos. Dado un cubo de la cuadrícula, una ambigüedad de cara ocurre cuando sus vértices de cara tienen signos alternados. 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, una ambigüedad interior ocurre 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 de los Marching Cubes y su adopción generalizada dieron como resultado varias mejoras en el algoritmo para lidiar con 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 permitían múltiples triangulaciones. La 'referencia adicional' de Durst fue a un algoritmo de poligonización de isosuperficies anterior, más eficiente (ver de Araujo [4] ) de Wyvill, Wyvill y McPheeters. [5] Más tarde, 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 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 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 interiores, que se basa en el Decisor Asintótico. 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] Se 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 determinando el o 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 para formar 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 (afuera), se establece en cero. El valor final, después de que se verifiquen 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 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 .
Una implementación del algoritmo de los cubos en marcha fue patentada como la patente de los Estados Unidos 4.710.876. [2] Se desarrolló otro algoritmo similar, llamado tetrahedra 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 que la comunidad gráfica la use 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}}: CS1 maint: varios nombres: lista de autores ( enlace )