Cubos de marcha

Marching cubes (del  inglés  -  "walking cubes") es un algoritmo en gráficos por computadora , propuesto por primera vez en 1987 en la conferencia SIGGRAPH por William Laurensen y Harvey Kline [1] , para procesar una cuadrícula poligonal de la isosuperficie de un escalar tridimensional campo (más a menudo llamado cuadrícula de vóxeles ).

Un algoritmo similar en el plano se llama cuadrados de marcha .

Cómo funciona

El algoritmo se ejecuta a través del campo escalar, en cada iteración observa 8 posiciones vecinas (vértices del cubo paralelos a los ejes de coordenadas) y determina los polígonos necesarios para representar la parte de la isosuperficie que pasa por este cubo. A continuación, los polígonos que forman la isosuperficie especificada se muestran en la pantalla.

Dado que el algoritmo selecciona polígonos basándose únicamente en la posición de los vértices del cubo en relación con la isosuperficie, existen 256 ( ) posibles configuraciones de polígonos en total, que se pueden calcular de antemano y almacenar en una matriz. Por tanto, cada cubo se puede representar mediante un número de ocho bits asignando 1 a cada vértice si el valor del campo en el punto es mayor que en la isosuperficie, y 0 en caso contrario. El número resultante se utiliza como índice del elemento de matriz que almacena las configuraciones de polígono. Finalmente, cada vértice del polígono generado se coloca en una posición adecuada en el borde del cubo sobre el que estaba originalmente. La posición se calcula por interpolación lineal de los valores del campo escalar en los extremos del borde.

Se puede obtener una matriz precalculada de 256 configuraciones de polígonos girando y reflejando 15 configuraciones de cubos diferentes. Sin embargo, el uso de solo 15 configuraciones básicas no garantiza una superficie cerrada. En la literatura especializada se pueden encontrar configuraciones básicas desprovistas de este inconveniente. .

El gradiente de campo escalar en cada punto de la cuadrícula también es un vector normal a la isosuperficie supuesta que pasa por ese punto. Por lo tanto, es posible interpolar estas normales a lo largo de los bordes de cada cubo para encontrar las normales de los vértices generados para mostrar el modelo correctamente cuando se usa iluminación.

Este algoritmo se usa ampliamente en medicina, por ejemplo, en tomografía computarizada y resonancia magnética , así como para el modelado tridimensional de metásferas u otras metasuperficies.

Patente

El algoritmo Marching Cubes fue el primer ejemplo de gráficos por computadora que provocó un escándalo de patente de software . Fue patentado a pesar de la relativa obviedad de la solución al problema de la generación superficial. Más tarde se desarrolló un algoritmo similar, llamado tetraedros en marcha , que usa tetraedros en lugar de cubos para eludir la patente. La patente expiró en 2005 y el algoritmo ahora es de uso gratuito. (Patente fechada el 5 de junio de 1985 [2] ).

Notas

  1. ↑ William E. Lorensen, Harvey E. Cline: Marching Cubes: un algoritmo de construcción de superficies 3D de alta resolución. En: Gráficos por computadora , vol. 21, núm. 4 de julio de 1987
  2. ↑ Marching Cubes, entrada de la Oficina de Patentes de EE. UU.

Véase también

Enlaces externos