Algoritmo Marching Squares

En el post anterior, comenté que no hay solamente una forma de representar voxels en pantalla. Mostré las formas mas simples y mencioné el algoritmo Marching Cube como una posibilidad para suavizar el renderizado de voxels.

En este post, en lugar de mostrar el algoritmo Marching Cubes voy a mostrar su versión 2D: Marching Squares. El algoritmo Marching Squares permite hacer una analogía directa con Marching Cubes y puede ser comprendido mas fácilmente.

La idea entonces, es que tenemos un campo de voxels 2D. Una posible representación de ese campo de voxels es un simple array bidimensional de números enteros:

  v = [[0,     0,   0, 0],
       [30,  100,  30, 0],
       [100, 100, 100, 0],
       [ 30, 100,  30, 0]];

Una forma de representar esto sería utilizando una escala de grises con 0 = blanco y 100 = negro. Pero para  evitar un resultado pixelado sería necesario un array de mayor dimensión.

Si lo que buscamos es usar un array de tamaño reducido para representar los voxels, pero a su vez un resultado no tan pixelado, podemos generar una "curva de nivel". Esto es, un contorno continuo de este campo usando segmentos de lineas. Es ahi donde entra Marching Squares.

Algoritmo Marching Squares

Este algoritmo permite obtener una "curva de nivel" de una función discreta (en este caso, los voxels). Los pasos a seguir son:

1. Convertir los voxels a un campo de valores 0 o 1 según un isovalor predeterminado.
2. Seleccionar un sub cuadrado 2x2 del campo de valores 0/1 y determinar un caso utilizando una tabla de casos (ver table mas adelante).
3. Utilizar los valores del campo de voxels original junto con el caso determinado en el paso 2 para obtener una linea interpolada.
4. Repetir desde el paso 2 para cada subcuadrado 2x2 del array original.

Utilizando el ejemplo anterior sería:

1. Convertir a campo de valores:

En este paso elijo un isovalor de 50 (punto medio entre 0 y 100) y creo un nuevo array que tiene 0 cuando el valor v[i][j] es menor o igual a 50 y 1 cuando v[i][j] es mayor a 50.

  v_iso = [[0, 0, 0, 0],
           [0, 1, 0, 0],
           [1, 1, 1, 0],
           [0, 1, 0, 0]];

2. Determinar casos:

Viendo cada subarray de 2x2 y comparando con la siguiente tabla de casos, determino el caso.

Tabla de casos. Un circulo negro corresponde a un voxel con valor superior al isovalor, uno blanco corresponde a un valor inferior. Los extremos de la linea resultante tienen que ser interpolados utilizando los valores de los voxels

En nuestro ejemplo, volviendo a v_iso, el primer subarray de 2x2 es

  [[0, 0], 
   [0, 1]

Comparando con la imagen, esto corresponde al caso 2. Ese caso es una linea diagonal de abajo hacia la derecha.

3. Interpolar usando voxels:

Si miramos en la tabla, cada extremo de las lineas celestes tiene una flecha que indica que ese extremo deberá ser ubicado teniendo en cuenta los valores de los extremos del lado. Tomemos el ejemplo encontrado en el paso anterior. Los valores de cada voxel eran 0, 0, 30 y 100, que resultaron en un Caso 2:

En este punto, hay que tener en cuenta que lo que estamos buscando es una linea correspondiente a un valor de 50. Si la distancia vertical y horizontal entre voxels es L y los valores en la posición de cada voxel son los valores dados por el voxel, entonces podemos interpolar las posiciones de cada extremo de la linea usando una proporción.

(100-30)/L = (50-30)/x

que implica que x es L*(50-30)/(100-30) = 0.28L

De la misma manera, para obtener la coordenada Y de la posición del otro extremo, podemos usar una proporción similar. En este caso, dado que los extremos corresponden a 0 y a 100, el valor de y es en el centro exacto de los voxels, o sea y=L*(50-0)/(100-0) = 0.5L

4. Repetir cada paso:

Si repetimos los pasos anteriores para cada subarray de 2x2 obtenemos el siguiente gráfico:

En el dibujo ya están las posiciones interpoladas de cada linea y un sombreado marcando el interior del polígono resultante. El interior del polígono se puede determinar fácilmente modificando la tabla de casos para mostrar cual es el interior en cada caso.

Ejemplo interactivo

La mejor forma de entender el algoritmo es utilizando un ejemplo interactivo y viendo el código. Hice un pequeño widget para poder experimentar. El ejemplo está realizado completamente en HTML5 usando webgl y javascript, por lo que es necesario un navegador moderno. El código fuente está disponible en google code.

Para usar el ejemplo solamente hay que asignar valores en la tabla. Se puede desactivar y activar el renderizado de voxels y de la isolinea.

Mostrar Voxels Mostrar Isolinea

Isovalue

En el  próximo artículo voy a mostrar cómo se generaliza esta idea a un caso 3D con el algoritmo Marching Cubes.

Introducción a Voxels

Una forma utilizada frecuentemente para representar objetos tridimensionales es mediante triángulos en un espacio tridimensional. Esto es, conjuntos de vértices que forman triángulos en el espacio. Esta es la forma en que las placas de video actuales reciben los datos antes de representarlos en pantalla y por lo tanto es la forma en que se almacenan los polígonos que se utilizan en aplicaciones gráficas.

Un ortoedro representado mediante triángulos. Representación gráfica y formulación matemática.

Una forma alternativa de almacenar información tridimensional es el uso de voxels. Así como un pixel es un elemento 2D que indica el estado (color) de un punto en una pantalla, un voxel es un elemento 3D que asocia un valor (o valores) a cada posición de un espacio tridimensional. El voxel puede contener información de "cantidad" de materia (0 a 1 con 0 = vacío y 1 = lleno) así como información mas compleja como tipo de material, textura, etc.

Representación gráfica y matemática de los voxels. Solo se muestran 4 voxels "vacíos" pero se supone que hay voxels vacios en todas las posiciones en que no hay voxels llenos.

En la imagen se ve una representación de la figura de antes, pero ahora usando voxels. Así como antes se almacenaban vértices y uniones entre estos para formar triángulos, en la representación de voxels se asignan valores a los distintos puntos del espacio tridimensional. En la representación anterior se almacenaba información de la superficie de la figura, en la representación actual se almacena información del volumen.

Esta representación es solo una forma de almacenar información. La ventaja de esta forma de representar la información es que permite editar el objeto representado simplemente agregando o removiendo voxels. 

En la figura de arriba se puede ver cada voxel como un cubo. Esta representación asume que un voxel solo puede tener el valor 0 o 1 (lleno/vacío), pero en general podríamos asignar cualquier valor entre 0 y 1 a cada voxel. Por otro lado, está el problema de convertir los voxels a un formato que pueda ser manejado por una placa de video (o sea, una serie de triángulos).

Formas de Representación

Izquierda: alta densidad de voxels representados mediante cubos de colores.
Derecha: baja densidad de voxels con la misma representación. (fuente: Google Images)

Si uno se limita a reemplazar puntos por cubos de color (así como en una imagen 2D se reemplazan puntos por rectángulos), el resultado es una imagen pixelada. Al igual que en una imagen 2D (pantalla o impresión) la calidad de la imagen depende de la densidad de pixels, la calidad de la representación 3D dependerá de la densidad de voxels. Es posible aumentar la resolución de voxels tanto como el hardware lo permita y obtener objetos fotorealistas. Esta forma de representar voxels no es eficiente para renderizado en tiempo real (por ejemplo un videojuego) si lo que se busca es fotorealismo ya que una alta densidad de voxels se traduce en una alta densidad de vértices incluso si evita renderizar las caras de los voxels que no son visibles por la cámara.

Una alternativa a lo anterior, para bajas densidades de voxels, es utilizar cubos con textura para reemplazar cada voxel. Esto permite darle una ambientación retro a un juego 3D, ver por ejemplo Minecraft.

Mincraft renderiza voxels usando cubos texturados.

Si lo que se busca es evitar formas "pixeladas" pero a la vez evitar usar altas densidades de voxels, hay que recurrir a algoritmos que utilicen el estado del voxel y el estado de sus vecinos para generar una superficie suave.

En el próximo post voy a explicar el algoritmo de Marching Cubes usando un ejemplo 2D para simplificar la explicación.