Não renderize a grama atrás da colina: descarte de oclusão com reconhecimento do terreno

Por Oleg Sidorkin, CTO e cofundador da Cinevva

A Parte 28 apresentou o Spike 57 e comparou seus quatro caminhos de descarte em alguns parágrafos. Esta é a versão completa: por que escolhemos esses quatro, quais eram os outros quatro e o raciocínio por trás daquele que vamos lançar.

Há uma colina entre a câmera e um campo. Você não precisa renderizar o campo. Todo motor AAA moderno sabe disso. A maioria dos motores 3D para navegador não sabe — inclusive o nosso, até a semana passada.

Este post é o resultado de fazer a pesquisa com o devido rigor, fundamentá-la em nossa base de código real, criar um protótipo funcional e avaliar as técnicas de acordo com o quanto elas ajudam especificamente a nós, considerando que hoje entregamos para WebGL e amanhã para WebGPU.

Você pode experimentar o protótipo ao vivo abaixo antes de continuar a leitura. T/Y/U/I alternam entre os caminhos de descarte, C percorre as predefinições de câmera e B pinta em vermelho, com estrutura de arame, os chunks ocultados, para que você possa ver o que o teste remove. O HUD informa quantas instâncias cada etapa rejeita.

Abrir o Spike 57 em uma nova aba ↗ · Ver o código-fonte

O que nosso motor faz hoje (e o que não faz)

Nosso gerenciador de chunks em streaming carrega ao redor do jogador um anel de chunks de 64 m, distribuídos em três níveis de LOD. Cada chunk contém árvores instanciadas espalhadas sobre o mapa de alturas. A lógica de descarte, que fica em Chunk.updateObjectVisibility, é uma simples verificação de distância: árvores a até 60 m são renderizadas com a malha completa; entre 60 m e 140 m, são renderizadas como outdoors; além disso, nada é renderizado.

Esse descarte deixa passar duas enormes categorias de desperdício:

1. Tudo que está dentro do disco de 60 m, mas atrás da câmera. Reordenamos o buffer de instâncias sempre que o jogador se move mais de 4 m, mas não testamos o frustum de visão. Assim, em média, metade do disco é enviada à GPU apenas para ser recortada depois da transformação dos vértices.
2. Tudo que está dentro do disco de 60 m, mas atrás de uma colina. Nosso terreno tem 80 m de variação vertical e muitos vales. Quando a câmera está em um vale, a maior parte da vegetação dentro do raio de descarte fica geometricamente oculta pela crista mais próxima. Mesmo assim, nós a desenhamos.

A segunda categoria é o foco deste post. É também aquela que os motores AAA resolvem com um conjunto de técnicas engenhosas que, à primeira vista, não se adapta facilmente ao navegador.

Gilbert Sanders, da Guerrilla, explica como Horizon Zero Dawn renderiza a vegetação de seu mundo aberto. O conjunto de descartes ocupa os últimos 20 minutos e é uma verdadeira aula sobre por que “desenhar menos” é melhor do que “desenhar mais rápido”.

Oito técnicas, avaliadas para o nosso caso

Estudei o conjunto moderno de técnicas de descarte de oclusão e avaliei cada componente de acordo com o quanto ele ajuda em um mundo aberto procedural, baseado em mapa de alturas e executado no navegador. Dois eixos: valor (quanto desperdício remove em nossa cena) e custo (esforço de engenharia, além de quanto da nossa stack precisa mudar). O raciocínio completo está no arquivo de pesquisa por trás deste post; aqui está a versão resumida.

1. Descarte de frustum por instância. Alto valor, baixo custo. Atualmente, não testamos o frustum de forma alguma para nossa vegetação instanciada. Adicionar esse teste corta aproximadamente metade do trabalho em qualquer visão, custa cerca de trinta linhas de código e pode ser lançado hoje em WebGL. É, de longe, o maior ganho fácil, e deveríamos tê-lo implementado meses atrás.

2. Raycast de horizonte no mapa de alturas. Alto valor, custo baixo a médio. Avance um raio da câmera por cada instância candidata, amostrando a altura do terreno ao longo do caminho. Se o terreno em algum momento subir acima do raio, a instância está ocluída. Isso funciona precisamente porque nosso mundo é um mapa de alturas, o que reduz a visibilidade a um problema unidimensional ao longo da direção horizontal. A versão densa tem complexidade O(passos) por instância, por quadro. A versão acelerada (o próximo item) reduz isso para O(log passos).

3. Aceleração com pirâmide de alturas máximas. Alto valor, custo médio. Um mipmap 2D do mapa de alturas no qual cada texel armazena a altura máxima do terreno dentro de sua área. Isso permite que o raycast de horizonte avance em passos largos quando o entorno é plano e refine o teste apenas sobre colinas. Essa é a estrutura que torna a técnica nº 2 barata o suficiente para produção.

4. Oclusão por Z hierárquico (Hi-Z/HZB). Alto valor, alto custo. Construa um mipmap do buffer de profundidade, projete os limites de cada instância no espaço da tela e teste-os contra o nível de mip adequado. Esse é o padrão moderno executado na GPU, usado pelo Nanite da Unreal, pela geometria virtual da Bevy e pelo porte do VTK para WebGPU. Ele funciona para tudo, não apenas para o terreno, mas exige WebGPU, desenhos indiretos e uma etapa de computação. Compensa quando estamos renderizando milhões de lâminas de grama, não milhares de árvores.

5. Hi-Z em duas passagens (ao estilo Nanite). Ganho marginal sobre a nº 4, alto custo. Renderize novamente a profundidade do quadro atual depois da passagem 1 para evitar o artefato de desoclusão de um quadro. Só vale a pena quando estivermos avançados o suficiente no caminho orientado pela GPU para que o custo seja incremental.

6. Rasterizador de oclusão por software (Frostbite/Intel MOC). Valor médio, alto custo. Rasterize na CPU um buffer de profundidade de baixa resolução contendo grandes oclusores. Latência de leitura zero. As implementações de referência são escritas em C++ com AVX/SSE; portá-las para WASM é um projeto de verdade, e nosso raycast no mapa de alturas captura a maior parte dos mesmos ganhos com uma fração do trabalho.

7. PVS pré-calculado. Baixo valor, alto custo. Excelente para mapas estáticos da era de Quake. Nosso terreno é procedural e infinito, portanto qualquer pré-processamento teria que acontecer durante o streaming dos chunks, o que custa quase tanto quanto simplesmente calcular a visibilidade em tempo de execução. Descartado.

8. Descarte de horizonte ao estilo Cesium. Nenhum valor para nós, custo médio. Projetado para elipsoides planetários. Nosso mundo é relativamente plano e limitado; a matemática não se aplica e não faria nada ou descartaria objetos incorretamente. Descartado.

Portanto: implementar agora as técnicas nº 1 e nº 2 + nº 3 na CPU, em WebGL. Planejar a nº 4 para a migração para WebGPU. Ignorar as demais.

Por que o raycast no mapa de alturas vence em terrenos no navegador

O conselho padrão em qualquer palestra moderna sobre renderização é: “construa um buffer Hi-Z”. A análise aprofundada de Brian Karis sobre o Nanite na SIGGRAPH 2021 é a referência canônica, e vale a pena assisti-la pelo menos uma vez.

Essa é a resposta certa para um motor que já executa tudo por meio de desenhos indiretos orientados pela GPU. A maioria dos motores para navegador, incluindo o nosso, não é esse tipo de motor. Temos buffers de instâncias gerenciados pela CPU, chamadas de desenho em WebGL e nenhuma etapa de computação. Acoplar Hi-Z a essa stack significa, ao mesmo tempo, portar o motor para WebGPU, reescrever o pipeline de vegetação com desenhos indiretos e adicionar uma passagem de construção da pirâmide de profundidade. Isso representa um trimestre de trabalho até chegar ao primeiro quadro que comprova a ideia.

O raycast no mapa de alturas funciona na CPU, em WebGL e com os dados que já temos. Ele usa um fato sobre nosso mundo do qual os motores AAA não podem tirar proveito: nossos oclusores são descritos por uma função de altura unidimensional. Amostrar essa função ao longo de um raio exige duas leituras de array e uma multiplicação. Um buffer Hi-Z teria que descobrir o mesmo fato pixel por pixel.

A técnica foi publicada pela primeira vez como “Horizon Occlusion Culling for Hierarchical Terrains” na IEEE Visualization 2002 (PDF). Ela permanece na caixa de ferramentas há duas décadas porque tem as características certas: é barata quando o terreno é plano, cara apenas onde realmente há colinas e trivialmente paralelizável.

A pirâmide de alturas máximas, ilustrada

O raycast ingênuo amostra terrainHeight em cerca de 24 pontos ao longo de cada raio e para antecipadamente se o terreno o atravessar. Isso funciona bem para milhares de árvores. Com centenas de milhares de lâminas de grama, o desempenho desmorona.

A solução é um mipmap do mapa de alturas no qual cada texel armazena a altura máxima dentro de sua área:

nível 0 (256×256, 2,25 m por texel): altura máxima de 4×4 amostras deslocadas
nível 1 (128×128, 4,5 m  por texel): max(0,0), max(1,0), max(0,1), max(1,1)
nível 2 ( 64×64,  9,0 m por texel): mesma redução, um nível acima
...
nível 8 (   1×1,  576 m por texel): máximo global

Quando o segmento do raio for longo e plano, amostre um nível mais grosseiro: uma única leitura informa que “nenhum terreno neste quadrado de 9 m ultrapassa 12 m de altitude, e o raio está a 30 m nesse ponto, portanto podemos continuar”. Somente quando um texel grosseiro indicar que “o terreno pode estar acima do raio” é preciso descer um nível e refinar o teste. Toda a estrutura ocupa algumas centenas de KB e é construída em dezenas de milissegundos.

Em forma de diagrama:

                                            raio a partir do olho
        olho 1,7 m                        o─────────────────────►
              o─────────────────────────·─·─·─·─·─·──────────────
              │                          \                       │
              │   nível 3 (passo enorme)  \   nível 0 (refinar)  │
              │   "nenhum terreno acima    \   "colina de 9 m    │
              │    de 8 m"                      aqui!"            │
        ──────┴────────────/▔▔▔\─────────────/▔▔▔▔▔\─────────────
                              colina A (8 m)  colina B (12 m)
                                                ↑
                                         bloqueia aqui

Para o segmento do raio que passa pelas proximidades da colina A, a leitura do nível 3 (“a altura máxima nesta área de 18 m de largura é 8 m”) já nos informa que o raio, a uma altitude de 1,7 m mais alguns metros de subida, está livre. Pulamos 36 m de avanço com uma única consulta. Sobre a colina B, o nível 3 informa “o máximo aqui é 12 m”; descemos um nível, e o nível 0 informa “sim, há 12 m exatamente neste texel”, então rejeitamos a instância.

A construção da pirâmide está em height-pyramid.mjs, e os caminhos de descarte que a utilizam estão em cull.mjs. Ambos podem ser lidos no navegador de código-fonte do protótipo.

O que o protótipo realmente mostra

Abra o Spike 57 acima e percorra os quatro caminhos:

• T0 é o que a versão de produção faz hoje. Apenas distância. Em C1 (fundo do vale), o HUD informa cerca de 12.000 lâminas de grama visíveis.
• T1 adiciona descarte de frustum por instância. A contagem visível cai aproximadamente pela metade porque tudo que está atrás da câmera ou fora das laterais é removido antes de chegar à GPU.
• T2 adiciona o raycast de força bruta no mapa de alturas. Em C1, o número cai mais 60–80%, porque a maior parte do campo está do outro lado da crista mais próxima. A coluna Cull-ms aumenta porque estamos amostrando terrainHeight cerca de 24 vezes por instância.
• T3 substitui a força bruta pela pirâmide de alturas máximas. Cull-ms volta a ficar próximo de T1, mantendo o ganho de visibilidade. Este é o caminho que realmente deve ser lançado.

O padrão corresponde ao observado em motores de produção. A série de duas partes de Acerola sobre renderização de grama (Como os jogos renderizam tanta grama?, O que fiz para otimizar a grama do meu jogo) é a explicação mais acessível no YouTube sobre por que a etapa de descarte — e não a etapa de sombreamento — é onde você deve concentrar seu trabalho de engenharia.

A câmera C3 e o caso de falha no “topo da colina”

A terceira predefinição de câmera do protótipo coloca a câmera no topo de uma colina, olhando para toda a área de jogo. Nesse caso, o descarte de horizonte quase não faz nada, porque não há terreno entre a câmera e a maior parte do mundo. O HUD mostra que T2/T3 reduzem a contagem visível em talvez 5–10% em relação a T1.

Isso é uma característica, não um bug. A técnica para de funcionar exatamente onde deveria: quando não há nada para ocluir. O descarte de frustum ainda está fazendo trabalho útil, o descarte por distância ainda limita o orçamento e o teste de horizonte se reduz elegantemente a uma operação nula. Se você implementar isso, precisa verificar se o caso sem efeito também é barato. É por isso que a pirâmide de alturas máximas importa mesmo quando nenhum raio seria rejeitado: frequentemente, o nível mais grosseiro é suficiente para confirmar que “nada está bloqueado”.

O que vamos lançar a seguir

Há três coisas a fazer, nesta ordem.

Primeiro, portar T1 e T3 para Chunk.updateObjectVisibility na versão de produção. A pirâmide deve ficar um nível acima, no gerenciador de chunks, porque abrange mais de um chunk. O descarte permanece em Chunk para que o agrupamento existente por chunk continue funcionando. Esforço estimado: um dia, incluindo os testes. Segundo, fazer o mesmo com a grama assim que ela estiver disponível. O protótipo atual espalha 12.000 lâminas por uma área jogável de 576 m; a densidade em produção deve ser aproximadamente uma ordem de grandeza maior. As rotinas de culling na CPU processam 12.000 em menos de um milissegundo, e é a aceleração pela pirâmide que mantém esse desempenho com 120.000.

Terceiro, quando migrarmos para THREE.WebGPURenderer, portar o mesmo loop para um compute shader. Os metadados se tornam um storage buffer. O culling grava os argumentos de drawIndirect. A pirâmide é enviada como uma textura 2D com a redução por máximo já incorporada. A estrutura do código permanece praticamente idêntica, e essa é justamente a ideia: não estamos apostando a migração em um novo algoritmo; estamos levando um algoritmo que já temos para uma pista mais rápida.

A Guerrilla apresentou a versão disso executada na GPU para o sistema de posicionamento procedural de Horizon Zero Dawn; o pipeline de renderização importa menos do que as estruturas de dados, e as deles têm o mesmo formato:

O Hi-Z ainda justificará seu lugar quando lançarmos construções e elementos de cenário densos que ocluam em direções que o mapa de altura não consegue representar. Mas a pirâmide do mapa de altura continuará no pipeline porque é estritamente mais barata que o Hi-Z para instâncias próximas ao solo, e a grama que atravessa a silhueta de uma crista é exatamente o caso que o Hi-Z trata pior.

Referências

A justificativa completa, em ordem de prioridade, e as decisões arquiteturais estão acima; estas são as fontes canônicas de cada técnica, aproximadamente na ordem em que aparecem na pilha.

• Yalim & Akman, Culling de oclusão por horizonte para terrenos hierárquicos (IEEE Visualization 2002, o artigo original sobre culling por horizonte em terrenos).
• Turitzin, Buffers de profundidade hierárquicos (a explicação mais clara de como as cadeias de mipmaps Hi-Z são construídas e consultadas).
• VKGuide, Culling baseado em compute (referência de pipeline de culling orientado pela GPU; o porte para WebGPU é mecânico).
• Kruskonja, Culling de oclusão em duas passagens (a arquitetura no estilo Nanite explicada fora dos slides da Epic).
• Karis et al., Nanite — Uma análise aprofundada (SIGGRAPH 2021) (a referência moderna de como é o culling orientado pela GPU em escala AAA).
• Karis, Palestra principal da HPG 2022: a jornada até o Nanite (contexto mais amplo sobre por que a etapa de culling é importante).
• Sanders, Entre tecnologia e arte: a vegetação de Horizon Zero Dawn (a pilha completa de culling de vegetação AAA).
• Guerrilla, Posicionamento procedural em tempo de execução baseado em GPU em Horizon Zero Dawn (posicionamento instanciado e visibilidade por instância).
• Scthe, Nanite WebGPU (uma implementação de referência em WebGPU, incluindo HZB).
• Kitware, Culling de oclusão com WebGPU no VTK (o primeiro HZB em produção no navegador de que tenho conhecimento).
• Acerola, Como os jogos renderizam tanta grama? e O que fiz para otimizar a grama do meu jogo (a introdução acessível em vídeo).
• RasterGrid, Culling de oclusão baseado em mapas Hi-Z (a introdução ao Hi-Z que continua sendo a referência canônica).
• Intel, Culling de oclusão por software com máscaras (a família de rasterizadores para CPU, caso você algum dia decida que a opção nº 6 vale a pena).