No renderices la hierba detrás de la colina: descarte de oclusión basado en el terreno

Por Oleg Sidorkin, CTO y cofundador de Cinevva

La parte 28 presentó el prototipo 57 y comparó sus cuatro rutas de descarte en un par de párrafos. Esta es la versión larga: por qué elegimos esas cuatro, cuáles eran las otras cuatro y el razonamiento detrás de la que vamos a lanzar.

Hay una colina entre la cámara y un prado. No necesitas renderizar el prado. Todos los motores AAA modernos lo saben. La mayoría de los motores 3D para navegadores no, incluido el nuestro hasta la semana pasada.

Esta publicación es el resultado de investigar el tema como es debido, contrastarlo con nuestra base de código real, crear un prototipo funcional y evaluar las técnicas según cuánto nos ayudan específicamente a nosotros, teniendo en cuenta que hoy publicamos para WebGL y mañana para WebGPU.

Puedes probar el prototipo interactivo de abajo antes de seguir leyendo. T/Y/U/I cambian entre las rutas de descarte, C recorre las cámaras predefinidas y B pinta en rojo y en modo alámbrico los chunks que se ocultan para que puedas ver qué elimina la prueba. El HUD indica cuántas instancias descarta cada etapa.

Abrir el prototipo 57 en una pestaña nueva ↗ · Ver el código fuente

Lo que hace hoy nuestro motor (y lo que no)

Nuestro gestor de chunks en streaming carga alrededor del jugador un anillo de chunks de 64 m con tres niveles de LOD. Cada chunk contiene árboles instanciados distribuidos sobre el mapa de alturas. La lógica de descarte, que reside en Chunk.updateObjectVisibility, es una simple comprobación de distancia: los árboles a menos de 60 m se renderizan con la malla completa, los que están entre 60 m y 140 m se renderizan como billboards y, más allá, no se renderiza nada.

Ese descarte pasa por alto dos enormes categorías de trabajo desperdiciado:

1. Todo lo que está dentro del disco de 60 m pero detrás de la cámara. Volvemos a ordenar el búfer de instancias cada vez que el jugador se mueve más de 4 m, pero no comprobamos el frustum de visión, así que, en promedio, enviamos la mitad del disco a la GPU solo para que se recorte después de la transformación de vértices.
2. Todo lo que está dentro del disco de 60 m pero detrás de una colina. Nuestro terreno tiene 80 m de rango vertical y muchos valles. Cuando la cámara está en un valle, la cresta más cercana oculta geométricamente la mayor parte de la vegetación situada dentro del radio de descarte. Aun así, la dibujamos.

La segunda categoría es el tema central de esta publicación. También es la que los motores AAA resuelven con una serie de técnicas ingeniosas que, a primera vista, no se trasladan fácilmente al navegador.

Gilbert Sanders, de Guerrilla, explica cómo Horizon Zero Dawn renderiza la vegetación de su mundo abierto. La cadena de descarte ocupa los últimos 20 minutos y es una clase magistral sobre por qué «dibujar menos» supera a «dibujar más rápido».

Ocho técnicas evaluadas para nuestro caso

Estudié la cadena moderna de descarte de oclusión y evalué cada componente según cuánto ayuda a un mundo abierto procedural, basado en un mapa de alturas y ejecutado en el navegador. Dos ejes: valor (cuánto trabajo innecesario elimina en nuestra escena) y coste (esfuerzo de ingeniería, además de cuánto nos obliga a cambiar de nuestra arquitectura). El razonamiento completo está en el archivo de investigación que respalda esta publicación; esta es la versión resumida.

1. Descarte por frustum para cada instancia. Valor alto, coste bajo. Ahora mismo no comprobamos en absoluto el frustum para nuestra vegetación instanciada. Añadirlo reduce aproximadamente a la mitad el trabajo en cualquier vista, cuesta unas treinta líneas de código y se puede lanzar hoy en WebGL. Es, con diferencia, la mayor mejora barata, y deberíamos haberla implementado hace meses.

2. Trazado de rayos del horizonte sobre el mapa de alturas. Valor alto, coste bajo-medio. Se hace avanzar un rayo desde la cámara hasta cada instancia candidata, muestreando la altura del terreno a lo largo del trayecto. Si en algún punto el terreno se eleva por encima del rayo, la instancia está ocluida. Funciona precisamente porque nuestro mundo es un mapa de alturas, lo que reduce la visibilidad a un problema 1D a lo largo de la dirección horizontal. La versión densa tiene una complejidad O(pasos) por instancia y por fotograma. La versión acelerada (el siguiente punto) la reduce a O(log pasos).

3. Aceleración mediante una pirámide de alturas máximas. Valor alto, coste medio. Un mipmap 2D del mapa de alturas donde cada texel almacena la altura máxima del terreno dentro de su área. Permite que el trazado de rayos del horizonte avance a grandes saltos cuando el entorno es llano y solo refine sobre las colinas. Esta es la estructura que hace que la técnica 2 sea barata en producción.

4. Oclusión mediante Z jerárquico (Hi-Z / HZB). Valor alto, coste alto. Se crea un mipmap del búfer de profundidad, se proyectan los límites de cada instancia al espacio de pantalla y se comparan con el nivel de mip adecuado. Es el estándar moderno en la GPU, utilizado por Nanite de Unreal, la geometría virtual de Bevy y la adaptación de VTK a WebGPU. Funciona para todo, no solo para el terreno, pero requiere WebGPU, llamadas de dibujo indirectas y un pase de cómputo. Compensa cuando renderizamos millones de briznas de hierba, no miles de árboles.

5. Hi-Z de dos pases (al estilo de Nanite). Mejora marginal respecto a la técnica 4, coste alto. Se vuelve a renderizar la profundidad del fotograma actual después del primer pase para evitar el artefacto de desoclusión de un fotograma. Solo merece la pena cuando hemos avanzado lo suficiente en la ruta controlada por la GPU como para que el coste sea incremental.

6. Rasterizador de oclusión por software (Frostbite/Intel MOC). Valor medio, coste alto. Rasteriza en la CPU un búfer de profundidad de baja resolución para los oclusores grandes. Latencia de lectura nula. Las implementaciones de referencia están escritas en C++ con AVX/SSE; adaptarlas a WASM es un proyecto de verdad, y nuestro trazado de rayos sobre el mapa de alturas consigue la mayoría de las mismas mejoras con una fracción del trabajo.

7. PVS precalculado. Valor bajo, coste alto. Es fantástico para los mapas estáticos de la era de Quake. Nuestro terreno es procedural e infinito, así que cualquier preprocesamiento tendría que hacerse durante el streaming de chunks, lo que cuesta aproximadamente lo mismo que calcular la visibilidad en tiempo de ejecución. Lo descartamos.

8. Descarte del horizonte al estilo de Cesium. Ningún valor para nosotros, coste medio. Está diseñado para elipsoides planetarios. Nuestro mundo es más o menos plano y está acotado; las matemáticas no son aplicables y la técnica no haría nada o produciría falsos descartes. Lo descartamos.

Así que: implementaremos ahora las técnicas 1 y 2+3 en la CPU y con WebGL. Planificaremos la técnica 4 para la migración a WebGPU. Omitiremos el resto.

Por qué gana el trazado de rayos sobre el mapa de alturas para terrenos en el navegador

El consejo habitual en cualquier charla moderna sobre renderizado es «crea un búfer Hi-Z». El análisis detallado de Nanite presentado por Brian Karis en SIGGRAPH 2021 es la referencia canónica y deberías verlo al menos una vez.

Es la respuesta correcta para un motor que ya ejecuta todo mediante llamadas de dibujo indirectas controladas por la GPU. La mayoría de los motores para navegadores, incluido el nuestro, no son ese tipo de motor. Tenemos búferes de instancias en la CPU, llamadas de dibujo de WebGL y ninguna etapa de cómputo. Incorporar Hi-Z a esa arquitectura implicaría migrar simultáneamente a WebGPU, reescribir el pipeline de vegetación para usar llamadas de dibujo indirectas y añadir un pase de creación de la pirámide de profundidad. Eso supone un trimestre de trabajo solo para obtener el primer fotograma que demuestre la idea.

El trazado de rayos sobre el mapa de alturas funciona en la CPU, con WebGL y con los datos que ya tenemos. Aprovecha un hecho sobre nuestro mundo que los motores AAA no pueden aprovechar: nuestros oclusores se describen mediante una función de altura 1D. Muestrear esa función a lo largo de un rayo requiere dos consultas a un array y una multiplicación. Un búfer Hi-Z tendría que descubrir el mismo hecho píxel a píxel.

La técnica se publicó por primera vez como «Horizon Occlusion Culling for Hierarchical Terrains» en IEEE Visualization 2002 (PDF). Se ha mantenido en el repertorio durante dos décadas porque tiene las características adecuadas: es barata cuando el terreno es llano, costosa solo donde hay colinas reales y trivialmente paralelizable.

La pirámide de alturas máximas, ilustrada

El trazado de rayos básico muestrea terrainHeight en unos 24 puntos a lo largo de cada rayo y se detiene en cuanto el terreno lo cruza. Eso funciona bien para miles de árboles. Se viene abajo con cientos de miles de briznas de hierba.

La solución es un mipmap del mapa de alturas en el que cada texel almacena la altura máxima dentro de su área:

nivel 0 (256×256, 2,25 m por texel): altura máx. de 4×4 muestras con desplazamiento aleatorio
nivel 1 (128×128, 4,5 m  por texel): máx.(0,0), máx.(1,0), máx.(0,1), máx.(1,1)
nivel 2 ( 64×64,  9,0 m por texel): la misma reducción un nivel por encima
...
nivel 8 (   1×1,  576 m por texel): máximo global

Cuando el segmento del rayo es largo y llano, se muestrea un nivel grueso: una sola consulta indica «ningún punto del terreno en este cuadrado de 9 m supera nunca los 12 m de altitud y el rayo está allí a 30 m, así que continúa». Solo cuando un texel grueso indica que «el terreno podría estar por encima del rayo» se desciende un nivel para refinar. Toda la estructura ocupa unos pocos cientos de KB y se construye en decenas de milisegundos.

En forma de diagrama:

                                        rayo desde el ojo
       ojo 1,7 m                      o────────────────────────►
              o─────────────────────·─·─·─·─·─·────────────────
              │                      \                         │
              │ nivel 3 (paso enorme) \ nivel 0 (refinamiento)│
              │ «nada supera los 8 m»  \ «¡colina de 9 m!»    │
              │                          \                     │
        ──────┴────────────/▔▔▔\─────────/▔▔▔▔▔\───────────────
                              colina A (8 m) colina B (12 m)
                                               ↑
                                         bloquea aquí

Para el segmento del rayo que pasa cerca de la colina A, la consulta del nivel 3 («la altura máxima en esta caja de 18 m de ancho es de 8 m») ya nos indica que el rayo, a una altitud de 1,7 m más unos metros de ascenso, está despejado. Saltamos 36 m de recorrido con una sola consulta. Sobre la colina B, el nivel 3 indica «el máximo aquí es de 12 m»; descendemos y el nivel 0 indica «sí, hay 12 m en este texel exacto», por lo que descartamos la instancia.

La construcción de la pirámide está en height-pyramid.mjs, y las rutas de descarte que la utilizan están en cull.mjs. Ambos archivos se pueden consultar en el navegador del código fuente del prototipo.

Lo que muestra realmente el prototipo

Abre arriba el prototipo 57 y recorre las cuatro rutas:

• T0 es lo que hace hoy la versión de producción. Solo distancia. Desde C1 (el fondo del valle), el HUD indica unas 12 000 briznas de hierba visibles.
• T1 añade descarte por frustum para cada instancia. El número de elementos visibles se reduce aproximadamente a la mitad porque todo lo que está detrás de la cámara o fuera de los laterales se descarta antes de llegar a la GPU.
• T2 añade el trazado de rayos por fuerza bruta sobre el mapa de alturas. En C1, el número se reduce otro 60-80 %, porque la mayor parte del campo está al otro lado de la cresta más cercana. La columna Cull-ms aumenta porque muestreamos terrainHeight unas 24 veces por instancia.
• T3 sustituye la fuerza bruta por la pirámide de alturas máximas. Cull-ms vuelve a valores cercanos a T1 sin perder la mejora de visibilidad. Esta es la ruta que realmente puedes lanzar.

El patrón coincide con lo observado en los motores de producción. La serie de Acerola en dos partes sobre el renderizado de hierba (¿Cómo renderizan los juegos tanta hierba?, Lo que hice para optimizar la hierba de mi juego) es la explicación más accesible de YouTube sobre por qué conviene invertir el trabajo de ingeniería en la etapa de descarte y no en la de sombreado.

La cámara C3 y el caso problemático de la «cima»

La tercera cámara predefinida del prototipo coloca la cámara en lo alto de una colina, mirando hacia el área de juego. En este caso, el descarte del horizonte apenas hace nada porque no hay terreno entre la cámara y la mayor parte del mundo. El HUD muestra que T2/T3 reducen el número de elementos visibles quizá entre un 5 % y un 10 % respecto a T1.

Eso es una característica, no un error. La técnica deja de funcionar exactamente donde debe hacerlo: cuando no hay nada que ocluya. El descarte por frustum sigue haciendo trabajo útil, el descarte por distancia sigue limitando el presupuesto y la prueba del horizonte pasa de forma natural a no hacer nada. Si implementas esto, debes comprobar que el caso en el que no se hace nada también sea barato; por eso la pirámide de alturas máximas importa incluso cuando no se va a descartar ningún rayo: a menudo, el nivel más grueso basta para confirmar que «nada está bloqueado».

Lo siguiente que vamos a lanzar

Hay tres cosas que hacer, en este orden.

Primero, trasladar T1 y T3 a Chunk.updateObjectVisibility en producción. La pirámide debe residir un nivel más arriba, en el gestor de chunks, porque abarca más de un chunk. El descarte permanece en Chunk para que el procesamiento por lotes existente para cada chunk siga funcionando. Esfuerzo estimado: un día, incluidas las pruebas. Segundo, haremos lo mismo con la hierba una vez que la tengamos. El prototipo actual distribuye 12 000 briznas por un área de juego de 576 m; la densidad de producción debería ser aproximadamente un orden de magnitud mayor. Las rutas de descarte en CPU procesan 12 000 en menos de un milisegundo, y la aceleración mediante la pirámide es lo que permite mantener ese rendimiento con 120 000.

Tercero, cuando migremos a THREE.WebGPURenderer, trasladaremos el mismo bucle a un shader de cómputo. Los metadatos se convierten en un búfer de almacenamiento. El descarte escribe los argumentos de drawIndirect. La pirámide se carga como una textura 2D con la reducción por máximos ya incorporada. La estructura del código permanece prácticamente idéntica, que es precisamente la idea: no estamos apostando la migración a un algoritmo nuevo, sino trasladando un algoritmo que ya tenemos a una pista más rápida.

Guerrilla presentó la versión para GPU de este enfoque en el sistema de colocación procedimental de Horizon Zero Dawn; la canalización de renderizado importa menos que las estructuras de datos, y las suyas tienen la misma forma:

Hi-Z seguirá mereciendo su lugar cuando incorporemos edificios y elementos densos que ocluyan en direcciones que el mapa de alturas no puede describir. Pero la pirámide del mapa de alturas seguirá en la canalización porque es estrictamente más barata que Hi-Z para las instancias pegadas al terreno, y la hierba que cruza la silueta de una cresta es precisamente el caso que Hi-Z peor resuelve.

Referencias

La justificación completa, ordenada por prioridad, y las decisiones arquitectónicas aparecen más arriba; estas son las fuentes canónicas de cada técnica, aproximadamente en el orden en que aparecen en la pila.

• Yalim y Akman, Descarte de oclusión por horizonte para terrenos jerárquicos (IEEE Visualization 2002, el artículo original sobre descarte por horizonte del terreno).
• Turitzin, Búferes de profundidad jerárquicos (la explicación más clara sobre cómo se construyen y consultan las cadenas de niveles mip de Hi-Z).
• VKGuide, Descarte basado en cómputo (referencia de la canalización de descarte controlada por GPU; la adaptación a WebGPU es mecánica).
• Kruskonja, Descarte de oclusión en dos pasadas (la arquitectura al estilo de Nanite explicada fuera de las diapositivas de Epic).
• Karis et al., Nanite: análisis en profundidad (SIGGRAPH 2021) (la referencia moderna de cómo es el descarte controlado por GPU a escala AAA).
• Karis, Ponencia principal de HPG 2022: el camino hacia Nanite (un contexto más amplio sobre por qué importa la etapa de descarte).
• Sanders, Entre la tecnología y el arte: la vegetación de Horizon Zero Dawn (la pila completa de descarte de vegetación AAA).
• Guerrilla, Colocación procedimental en tiempo de ejecución basada en GPU en Horizon Zero Dawn (colocación de instancias y visibilidad por instancia).
• Scthe, Nanite WebGPU (una implementación de referencia en WebGPU, con HZB incluido).
• Kitware, Descarte de oclusión con WebGPU en VTK (el primer HZB de producción ejecutado en el navegador del que tengo constancia).
• Acerola, ¿Cómo renderizan los juegos tanta hierba? y Lo que hice para optimizar la hierba de mi juego (el recorrido accesible en YouTube).
• RasterGrid, Descarte de oclusión basado en mapas Hi-Z (la introducción a Hi-Z que sigue siendo la referencia canónica).
• Intel, Descarte de oclusión por software con máscaras (la familia de rasterizadores para CPU, por si alguna vez decides que la opción n.º 6 merece la pena).