Cubos de marcha

Cabeza y estructuras cerebrales (ocultas) extraídas de 150 cortes IRM empleando cubos de marcha (aproximadamente 150,000 triángulos)

Cubos de marcha es un algoritmo de gráficos por computadora publicado en las memorias del congreso SIGGRAPH en 1987 por Lorensen y Cline.​ Este algoritmo tiene como objetivo extraer una malla poligonal de una isosuperficie de un campo escalar discreto tridimensional (a veces llamado vóxeles). Este artículo es uno de los más citados en el campo de gráficos por computadora. Las aplicaciones de este algoritmo se refieren principalmente a visualizaciones médicas como TAC e imágenes de datos de escáner de IRM, y efectos especiales o modelación 3-D donde normalmente son llamados metaballs o metasuperficies. Un método bidimensional análogo es llamado algoritmo cuadrados de marcha (marching squares).

Historia

El algoritmo fue desarrollado por William E. Lorensen Y Harvey E. Cline a raíz de su búsqueda para General Electric. En General Electric trabajaban en una forma eficiente de visualizar los datos de los dispositivos TAC y IRM.

Las 15 configuraciones de cubo publicadas originalmente

Su primera versión publicada explotó la simetría rotacional y reflexiva y también fijó cambios para construir la tabla con solo 15 casos. Aun así, en la mezcla de las caras, hay posiblemente casos ambiguos.​ Estos casos ambiguos pueden conducir a mallas con agujeros. Sin embargo, isosuperficies topológicamente correctas pueden construirse con un esfuerzo extra.​

El problema para los casos con signos de "ondulación", es que hay al menos dos opciones correctas para que el contorno correcto pase. La elección real no importa, pero debe ser topológicamente consistente. Los casos originales tomaron decisiones consistentes, pero el cambio de signo podría conducir a errores. La tabla extendida en​ muestra 33 configuraciones.

Las ambigüedades se mejoraron en algoritmos posteriores, como el decisor asintótico de 1991 de Nielson y Hamann,​ que corrigió estos errores.​​ Muchos otros análisis de ambigüedades y mejoras relacionadas se han propuesto desde entonces; por ejemplo, ver la encuesta de 2005 de Lopes y Bordlie.

Algoritmo

El algoritmo avanza por el campo escalar, tomando ocho ubicaciones vecinas a la vez (formando así un cubo imaginario) y luego determinando el(los) polígono(s) necesario(s) para representar la parte de la isosuperficie que pasa a través de este cubo. Los polígonos individuales se fusionan en la superficie deseada.

Esto se hace creando un índice para una matriz precalculada de 256 configuraciones de polígono posibles (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 iso-valor (es decir, está dentro de la superficie), entonces el bit apropiado se fija en uno, mientras que si es más bajo (está afuera), se establece en cero. El valor final, después de comprobar 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 tanto, estas normales se pueden interpolar  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.

Asuntos de patente

Una implementación del algoritmo de los cubos de marcha fue patentada como Patente de los Estados Unidos 4.710.876.​ Se desarrolló otro algoritmo similar, llamado tetraedro de marcha, con el fin de eludir la patente, así como para resolver un pequeño problema de ambigüedad de los cubos de marcha con algunas configuraciones de cubo. La patente expiró en 2005, y ahora es legal que la comunidad de gráficos la use sin regalías, ya que pasaron más de 17 años desde su fecha de emisión (1ro de diciembre de 1987​).

Véase también

• Modelación basada en imágenes
• Tetraedro de marcha
• Decisor asintótico
• Cuadrados de marcha

Enlaces externos

• Lorensen, W. E.; Cline, Harvey E. (1987). «Marching cubes: A high resolution 3d surface construction algorithm». ACM Computer Graphics 21: 163-169. doi:10.1145/37402.37422. 
• Nielson, G. M.; Hamann, Bernd (1991). «The asymptotic decider: resolving the ambiguity in marching cubes». Proc. 2nd conference on Visualization (VIS' 91): 83-91. 
• Montani, Claudio; Scateni, Riccardo; Scopigno, Roberto (1994). «A modified look-up table for implicit disambiguation of Marching cubes». The Visual Computer 10: 353-355. doi:10.1007/BF01900830. 
• Nielson, G. M.; Sung, Junwon (1997). «Interval volume tetrahedrization». 8th IEEE Visualization (VIS'97). doi:10.1109/VISUAL.1997.663886. 
• «Overview and source code». 
• «GameDev overview». 
• «Introductory description with additional graphics». Archivado desde el original el 18 de agosto de 2019. Consultado el 24 de octubre de 2017. 
• «Marching Cubes». Archivado desde el original el 27 de mayo de 2019. Consultado el 24 de octubre de 2017. . Some of the early history of Marching Cubes.
• Newman, Timothy S.; Yi, Hong (2006). «A survey of the marching cubes algorithm». Computers and Graphics 30: 854-879. doi:10.1016/j.cag.2006.07.021. 
• «Specializing visualization algorithms». 

• Datos: Q1886184
• Multimedia: Marching cubes / Q1886184