Marching Cubes: de voxels a mallas suaves

Cuando alguien dice "terreno voxel", la imagen mental suele ser Minecraft: cubos alineados a una rejilla, caras planas, esa estética de bloques. Pero los cubos no son la parte importante de un sistema voxel. La parte importante es que el mundo está descrito por un campo de datos en 3D, y no por una malla que alguien esculpió a mano. Un cubo es simplemente la forma más perezosa de dibujar ese campo.

En el momento en el que quieres cuevas redondeadas, colinas suaves o un planeta deformable como el de No Man's Sky, hace falta un paso intermedio: convertir ese campo de números en una superficie de triángulos que la GPU pueda pintar. Ese paso se llama extracción de isosuperficies, y el algoritmo de referencia desde 1987 sigue siendo Marching Cubes.

Durante la carrera, me enfrenté al reto de estudiar y desarrollar un sistema para poder generar este tipo de mallas y cómo poder usarlas en desarrollo de videojuegos. Este artículo cubre cómo funciona de verdad (no solo "hay unas tablas mágicas"), por qué la interpolación es lo único que separa una malla suave de una escalonada, cómo implementarlo en Unity, qué se rompe en cuanto pasas de un cubo de prueba a un mundo con chunks (división del mundo tridimensional en cubos) y niveles de detalle y algunos aprendizajes de ese mismo estudio. Así que, aviso importante, habrá muchas matemáticas.

1. El Punto de Partida: un Campo de Densidad

Antes de generar geometría hace falta una función que, dado un punto en el espacio, devuelva un número. Ese número se suele llamar densidad, y su signo decide si el punto está dentro o fuera del objeto.

La convención más habitual: negativo dentro de la roca, positivo en el aire, cero exactamente en la superficie. Una esfera de radio r centrada en el origen es literalmente length(p) - r. Un plano infinito es p.y. Un terreno con relieve es p.y - ruido(p.x, p.z). Restar una esfera del terreno para abrir una cueva es un max entre el terreno y la esfera negada.

1// El campo entero de un mundo cabe en una función pura.
2// Ese es el gran atractivo de trabajar con densidades.
3public static float Sample(float3 p)
4{
5    float terrain = p.y - Noise.FBM(p.x * 0.02f, p.z * 0.02f) * 24f;
6    float cave     = 0.6f - Noise.Simplex3D(p * 0.05f); // túneles
7    return math.max(terrain, -cave);
8}

Ese campo continuo se muestrea en una rejilla regular. Para un chunk de 32x32x32 celdas se guardan 33x33x33 valores, porque cada celda necesita los ocho valores de sus esquinas y las celdas comparten esquinas con sus vecinas.

2. La Idea: Marchar Celda a Celda

Este algoritmo recorre cada celda de la rejilla de forma independiente. Mira los ocho valores de sus esquinas y responde a una única pregunta: ¿por dónde atraviesa la superficie esta celda?

Cada esquina está dentro (densidad por debajo del isovalor) o fuera (densidad por encima). Ocho esquinas con dos estados dan 2^8 = 256 configuraciones posibles. Y aquí está el truco que hace el algoritmo viable: esas 256 configuraciones se reducen, por rotación y simetría, a 15 casos base. Todos los demás son transformaciones de esos 15.

Como el número de configuraciones es finito y pequeño, no hace falta razonar geométricamente en tiempo de ejecución. Se precalculan dos tablas y el bucle interno se convierte en unos cuantos accesos a memoria:

• edgeTable[256]: una máscara de 12 bits que indica cuáles de las 12 aristas del cubo son cruzadas por la superficie.
• triTable[256][16]: para cada configuración, la lista de índices de arista agrupados de tres en tres, cada trío un triángulo, terminada en -1.

1// Construcción del índice de configuración: un bit por esquina.
2int cubeIndex = 0;
3if (density[0] < isoLevel) cubeIndex |= 1;
4if (density[1] < isoLevel) cubeIndex |= 2;
5if (density[2] < isoLevel) cubeIndex |= 4;
6if (density[3] < isoLevel) cubeIndex |= 8;
7if (density[4] < isoLevel) cubeIndex |= 16;
8if (density[5] < isoLevel) cubeIndex |= 32;
9if (density[6] < isoLevel) cubeIndex |= 64;
10if (density[7] < isoLevel) cubeIndex |= 128;
11
12// 0 = celda entera fuera, 255 = celda entera dentro. Nada que emitir.
13if (cubeIndex == 0 || cubeIndex == 255) continue;

El orden de las esquinas y el orden de las aristas es completamente arbitrario, pero tiene que coincidir con el orden con el que se generaron las tablas. Si copias triTable de un sitio y numeras tus esquinas de otra forma, obtendrás una malla que parece correcta de lejos y está llena de agujeros de cerca. Es el error número uno de cualquier implementación desde cero.

3. La Interpolación es el Algoritmo

Aquí está el detalle que la mayoría de tutoriales pasan por encima y que decide si el resultado se ve profesional o amateur.

Una vez sabes que una arista es atravesada, hay que colocar un vértice en ella. La opción ingenua es el punto medio. Funciona, genera una malla cerrada y correcta... y produce una superficie con una especie de aspecto de burbujas cuadradas, porque todos los vértices están anclados a posiciones fijas de la rejilla. Es el equivalente a redondear todo a la mitad de un voxel.

La opción correcta es interpolar linealmente según los valores de densidad de los dos extremos:

1static float3 VertexOnEdge(float3 pa, float3 pb, float da, float db, float iso)
2{
3    float denom = db - da;
4    // Extremos con densidad casi idéntica: cualquier t es igual de válido,
5    // así que se fija a 0.5f para evitar dividir por algo minúsculo.
6    if (math.abs(denom) < 1e-6f) return (pa + pb) * 0.5f;
7
8    float t = (iso - da) / denom;
9    return pa + t * (pb - pa);
10}

Con esta línea, la superficie deja de estar pegada a la rejilla y empieza a seguir el campo real. La diferencia visual es enorme para un cambio de tres líneas: una esfera de radio 8 en una rejilla de 1 unidad pasa de parecer un dado redondeado a parecer una esfera.

4. Normales: el Gradiente, no la Cara

Con la malla ya generada, la tentación es calcular las normales con el producto vectorial de cada triángulo y promediarlas por vértice. Eso es lo que hace mesh.RecalculateNormals() de Unity, y para geometría estática está bien. Para una isosuperficie es la peor opción disponible.

El problema es doble. Primero, las normales de cara promediadas dependen de cómo se teselaron los triángulos, así que a lo largo de la superficie aparecen cambios de sombreado que siguen el patrón de la rejilla. Segundo, si generas la malla en chunks separados, cada chunk promedia solo sus propios triángulos y las normales no coinciden en los bordes, lo que produce costuras de iluminación perfectamente visibles.

La alternativa es muestrear el gradiente del campo de densidad por diferencias centrales. La normal de la superficie es, por definición, la dirección en la que el campo crece más rápido:

1static float3 FieldNormal(float3 p, float h = 0.05f)
2{
3    float dx = Sample(p + new float3(h, 0, 0)) - Sample(p - new float3(h, 0, 0));
4    float dy = Sample(p + new float3(0, h, 0)) - Sample(p - new float3(0, h, 0));
5    float dz = Sample(p + new float3(0, 0, h)) - Sample(p - new float3(0, 0, h));
6    return math.normalize(new float3(dx, dy, dz));
7}

Cuesta seis muestreos del campo por vértice, que no es gratis, pero da normales continuas independientes de la teselación y del chunking. Si el campo está cacheado en un buffer de densidades, se puede aproximar con las diferencias de los valores ya muestreados y luego interpolar la normal en la arista igual que se interpola la posición.

5. Donde Empiezan los Problemas de Verdad

Un mundo no se genera de una vez. Se divide en chunks para poder generarlos en paralelo, descargarlos por distancia y regenerar solo lo que cambia cuando el jugador dispara con la herramienta de terraformado.

El problema es que cada chunk tiene que emitir las celdas que van justo hasta su borde, y esas celdas necesitan los valores de densidad del chunk vecino. Si cada chunk muestrea solo su propio rango, queda un hueco de una celda entre chunks contiguos: el clásico terreno con rejilla de grietas.

La solución habitual es el borde de solapamiento. Un chunk de 32 celdas por lado muestrea una rejilla de 34x34x34 valores (32 celdas más una esquina extra por lado, más un anillo de guarda), y solo emite triángulos para las 32 celdas interiores. Los valores del anillo se recalculan del campo, no se copian del vecino, así que un chunk se puede generar sin conocer a nadie.

1// Un chunk se genera sin depender de sus vecinos: vuelve a muestrear
2// el campo en el borde en lugar de pedirle datos a nadie.
3const int Cells  = 32;
4const int Points = Cells + 3;        // 32 celdas + esquina final + guarda
5float3 origin = chunkCoord * Cells * voxelSize - voxelSize; // desplazado una celda
6
7for (int z = 0; z < Points; z++)
8for (int y = 0; y < Points; y++)
9for (int x = 0; x < Points; x++)
10    density[Index(x, y, z)] = Sample(origin + new float3(x, y, z) * voxelSize);

Y aquí conviene una advertencia sobre rendimiento. Un chunk de 32^3 son 32.768 celdas, cada una con ocho muestreos de un campo con varias octavas de ruido. En el hilo principal eso son decenas de milisegundos por chunk, suficiente para tirones visibles al mover al jugador. La generación de chunks pertenece al Job System con Burst, o a un compute shader, no al Update.

6. LOD y el Problema de las Costuras

Con chunks resueltos llega el siguiente escalón: los chunks lejanos no necesitan la misma densidad de rejilla que los cercanos. Duplicar el tamaño de voxel reduce el número de celdas a la octava parte, así que la tentación es obvia.

El problema es que Marching Cubes no es compatible consigo mismo entre resoluciones. Un chunk con voxels de 1 unidad y su vecino con voxels de 2 unidades no colocan sus vértices en los mismos sitios en la cara compartida, así que aparecen agujeros por los que se ve el cielo. No son artefactos sutiles, son grietas.

Hay tres formas de convivir con esto:

• Skirts: emitir un faldón de geometría vertical en los bordes de cada chunk, que baja lo suficiente para tapar cualquier grieta posible. Es un apaño, es barato y es lo que usan muchos juegos comerciales. Se nota si mueves la cámara al ras del suelo.
• Transvoxel: la extensión de Eric Lengyel al algoritmo, con un juego de tablas adicional para las celdas de transición entre dos resoluciones. Es la solución correcta y cierra las grietas de verdad, a cambio de bastante más complejidad en el generador.
• Un solo nivel de detalle con chunks grandes: perfectamente válido si el mundo no es un planeta. Muchos juegos de cuevas no necesitan LOD en absoluto.

7. Casos Ambiguos y las Alternativas

Marching Cubes tiene un defecto conocido desde su publicación: algunas configuraciones son ambiguas. Cuando dos esquinas diagonalmente opuestas de una cara están dentro y las otras dos fuera, la superficie puede conectarlas de dos maneras topológicamente distintas, y las tablas originales eligen una arbitrariamente. Si dos celdas contiguas eligen interpretaciones incompatibles en su cara compartida, queda un agujero.

En la práctica, con campos suaves y ruido continuo, estos casos aparecen poco y los agujeros son diminutos. Si el proyecto necesita mallas garantizadamente cerradas (para simulación física, cálculo de volumen o impresión 3D) hay dos caminos:

• Marching Tetrahedra: divide cada cubo en 5 o 6 tetraedros y aplica el mismo razonamiento. Un tetraedro solo tiene 16 configuraciones y ninguna es ambigua, así que la malla siempre es cerrada. El precio son bastantes más triángulos y una superficie con un ligero sesgo direccional heredado de cómo se cortó el cubo.
• Dual Contouring: en lugar de poner vértices en las aristas, pone un vértice por celda y lo coloca resolviendo un sistema de mínimos cuadrados con las normales de las intersecciones. Preserva aristas afiladas, que es exactamente lo que Marching Cubes redondea sin remedio. Necesita datos Hermite (posición y normal por intersección) y es notablemente más complejo de implementar bien.

8. Cuándo No Usar Marching Cubes

El algoritmo es una herramienta específica, no un paso obligatorio de cualquier sistema voxel.

Si la estética del juego es de bloques, generar caras de cubo con culling de caras internas es más rápido, más simple, más fácil de texturizar y de mapear a UVs. Marching Cubes solo aporta si la superficie tiene que ser suave.

Si el mundo tiene aristas afiladas intencionadas (arquitectura, estructuras artificiales, cristales) Marching Cubes las va a redondear y no hay parámetro que lo evite: es una consecuencia de colocar vértices únicamente en las aristas de la rejilla. Ahí toca Dual Contouring.

Y si el problema es 2D, la versión bidimensional se llama Marching Squares, tiene 16 casos en lugar de 256 y cabe en una tarde. Es lo que hay debajo de cualquier generador de contornos, de los mapas de nivel destructibles en 2D y de la mayoría de los sistemas de mapas de calor.

Marching Cubes es uno de esos algoritmos que se explican en veinte minutos y se dominan en varias semanas. El bucle principal es corto y las tablas están publicadas. Lo que consume el tiempo es todo lo demás: el orden de las esquinas, el anillo de guarda de los chunks, las normales del gradiente, las grietas del LOD y mover la generación fuera del hilo principal. Ninguna de esas cosas sale en el paper.