Cubos de marcha

Cubos de marcha es un algoritmo de gráficos por computadora publicado en las memorias del congreso SIGGRAPH en 1987 por Lorensen y Cline.^[1]​ 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).

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

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.^[2]​ Estos casos ambiguos pueden conducir a mallas con agujeros. Sin embargo, isosuperficies topológicamente correctas pueden construirse con un esfuerzo extra.^[3]​

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^[3]​ muestra 33 configuraciones.

Las ambigüedades se mejoraron en algoritmos posteriores, como el decisor asintótico de 1991 de Nielson y Hamann,^[4]​ que corrigió estos errores.^[5]​^[6]​ 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.^[7]​ 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^[7]​).

Referencias

1. William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. el 24 de noviembre de 2016 en Wayback Machine. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
2. . Archivado desde el original el 18 de agosto de 2019. Consultado el 24 de octubre de 2017. 
3. Marching Cubes 33: Construction of Topologically Correct Isosurfaces. 
4. Nielson, Gregory M.; Hamann, B. (1991). «The asymptotic decider: resolving the ambiguity in marching cubes». Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91. 
5. Charles D. Hansen; Chris R. Johnson (2004). Visualization Handbook. Academic Press. p. 9. ISBN 978-0-12-387582-2. 
6. A. Lopes; K. Bordlie (2005). «Interactive approaches to contouring and isosurfaces for geovisualization». En Jason Dykes; Alan M. MacEachren; M. J. Kraak, eds. Exploring Geovisualization. Elsevier. pp. 352-353. ISBN 978-0-08-044531-1. 
7. Patente USPTO n.º 4710876: «Marching Cubes, US Patent Office entry»

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». 
• . Archivado desde el original el 18 de agosto de 2019. Consultado el 24 de octubre de 2017. 
• . 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. 
• . Archivado desde el original el 24 de octubre de 2017. 

•   Datos: Q1886184
•   Multimedia: Marching cubes / Q1886184