VoxelSpace: algoritmo de renderização de terreno implementado em menos de 20 linhas de código (2020)

 (github.com/s-macke)
4 pontos por GN⁺ 2025-01-05 | 1 comentários | Compartilhar no WhatsApp
  • Voxel Space é uma técnica de renderização de terreno 2.5D usada no Comanche, da NovaLogic, em 1992; numa época em que aceleração por GPU não existia ou era cara demais, ela representava montanhas e vales texturizados usando apenas a CPU
  • O terreno é representado por um mapa de altura e um mapa de cores; o Comanche usava um mapa de altura de 1024×1024 com 1 byte e um mapa de cores de 1024×1024 com 1 byte
  • O mapa de cores já inclui sombreamento e sombras, então não é necessário calcular iluminação durante a renderização, mas cada posição do mapa só pode ter uma única altura, o que dificulta representar geometrias complexas como prédios ou árvores
  • A renderização básica rasteriza segmentos de linha do mapa de trás para frente e, para cada coluna da tela, lê a altura e a cor para desenhar uma linha vertical; campo de visão de 90° e projeção em perspectiva são implementados em poucas linhas de código
  • Melhorias de desempenho são possíveis desenhando da frente para trás, pulando partes ocultas com um y-buffer por coluna e reduzindo o nível de detalhe em distâncias maiores

Contexto do surgimento do Voxel Space

  • Em 1992, as CPUs eram 1000 vezes mais lentas que as atuais, e aceleração por GPU era desconhecida ou difícil de bancar
  • Jogos 3D eram calculados apenas pela CPU, e os motores de renderização normalmente desenhavam polígonos preenchidos com cores sólidas
  • A NovaLogic lançou Comanche em 1992, e a representação de texturas, sombreamento e sombras em montanhas e vales se destacava dos gráficos de jogos da época
  • O README oferece uma Web Demo of the Voxel Space Engine

Representação do terreno: mapa de altura e mapa de cores

  • A forma mais simples de representar terreno no Voxel Space é usar um height map e um color map
  • O Comanche usa os dois mapas a seguir
    • Mapa de altura de 1 byte com 1024×1024
    • Mapa de cores de 1 byte com 1024×1024
  • Esses mapas se repetem de forma periódica
  • Cada posição do mapa pode ter apenas uma altura
    • Não é possível representar geometrias complexas como prédios e árvores
    • Em compensação, o mapa de cores já inclui sombreamento e sombras, então não é preciso calcular iluminação durante a renderização

Algoritmo básico de renderização

  • O motor Voxel Space renderiza o terreno rasterizando o mapa de altura e o mapa de cores e desenhando linhas verticais na tela
  • O procedimento básico é o seguinte
    • Limpar a tela
    • Desenhar de trás para frente para garantir o tratamento de oclusão
    • Encontrar a linha no mapa correspondente à mesma distância óptica a partir do observador
    • Considerar o campo de visão e a projeção em perspectiva
    • Dividir essa linha de acordo com o número de colunas da tela
    • Ler a altura e a cor no mapa 2D em cada posição do segmento
    • Aplicar projeção em perspectiva à coordenada de altura
    • Desenhar uma linha vertical com a altura projetada e a cor do mapa de cores
  • O loop central na forma mais simples em Python reduz z de uma distância maior para uma menor e chama DrawVerticalLine para cada coluna da tela
  • A chamada de exemplo passa posição, altura da câmera, posição do horizonte, escala de altura, distância máxima, largura e altura da tela

Adicionando rotação

  • O algoritmo básico só permite olhar para o norte
  • Para olhar em outras direções, é adicionado código para rotacionar as coordenadas
  • A versão com rotação recebe phi como ângulo de visão e pré-calcula sin(phi) e cos(phi)
  • Coordenadas rotacionadas são aplicadas ao cálculo dos pontos de limite esquerdo e direito do campo de visão, e x e y são incrementados juntos ao longo de cada coluna da tela
  • A estrutura central da renderização permanece a mesma
    • Cálculo de segmentos por distância
    • Rasterização ajustada às colunas da tela
    • Consulta ao mapa de altura e ao mapa de cores
    • Desenho de linhas verticais após a projeção em perspectiva

Formas de melhorar o desempenho

  • Em vez de desenhar de trás para frente, desenhar da frente para trás pode reduzir as áreas que serão ocultadas
  • Esse método exige um y-buffer que armazena a posição y mais alta para cada coluna da tela
    • O valor inicial do y-buffer é definido como a altura da tela
    • Só se desenha a parte visível quando o novo height_on_screen calculado está acima do y-buffer existente
    • Depois de desenhar, o y-buffer é atualizado para uma posição mais alta
  • A distância z aumenta de perto para longe
  • Aumentar dz gradualmente permite amostrar com intervalos maiores em distâncias longas, obtendo um efeito de Level of Detail
  • A ideia é renderizar o que está perto com mais detalhes e o que está longe com menos detalhes

Materiais fornecidos e licença

  • O repositório inclui vários pares de mapas de cores e mapas de altura
  • A parte de software está sob a licença MIT
  • A tecnologia Voxel Space ainda pode estar protegida por patentes em alguns países
  • Os mapas de cores e mapas de altura foram obtidos por engenharia reversa do jogo Comanche, por isso ficam excluídos da licença
  • Como material relacionado, é fornecido o link Voxel terrain engine - an introduction

Leituras relacionadas

1 comentários

 
GN⁺ 2025-01-05
Comentários do Hacker News

  • Muito legal. Sinto falta de uma época em que algoritmos novos e elegantes criavam experiências que pareciam magia
    Pode ser só coisa da idade, mas parece que os jogos da época em que os recursos de hardware eram limitados tinham mais magia do que os de hoje. Nos anos 80, 90 e começo dos 2000, quase todo ano, ou pelo menos a cada geração, os jogos empurravam a própria mídia adiante, e os desenvolvedores espremiam o hardware até o limite com técnicas novas e otimizações que pareciam pura magia
    Hoje em dia, plataformas de fantasia como PICO-8 são muito mais interessantes do que lançamentos repetitivos de estúdios AAA, e sinceramente não entendo por que jogos que na prática só trocam os assets fazem tanto sucesso ano após ano

    • Os jogos AAA modernos ainda têm muita tecnologia que parece mágica. Na verdade, a indústria de games é uma das poucas áreas que levam desempenho realmente a sério, e às vezes até o priorizam mais do que segurança ou precisão
      A diferença é que agora tudo é muito mais complexo e menos visível. Antes, dava para ver o salto de truques matemáticos espertos para texturas sobre triângulos chapados; hoje, o avanço é algo como melhorar o sombreamento no canto de uma sala. Melhorias em textura qualquer um percebe na hora, mas sombras no canto são difíceis de apontar especificamente para quem não é da área. Ainda assim, esses elementos se acumulam e melhoram o visual como um todo, só que de um jeito menos impactante do que antigamente
      A indústria de jogos AAA é um grande negócio, os custos de produção são enormes e os investidores querem retorno. Então normalmente se pesquisa o mercado, vê-se o que vende bem e faz-se algo na mesma linha. A originalidade cai, mas o risco também
      Já na cena indie existem milhares de estúdios e, como eles não conseguem vencer os AAA em quantidade de conteúdo ou nível de acabamento, precisam de outras armas para se destacar da multidão, como ideias originais. Mas hoje em dia superar limites técnicos muitas vezes já não é a força principal. Isso porque há menos restrições do que antes. Na verdade, por questão de custo, é comum que eles forcem menos o lado técnico do que produções AAA
      Não conheço bem a cena de PICO-8, mas fico curioso sobre quanto dela gira em torno de superar limitações técnicas artificiais e quanto gira em torno de usar a plataforma da forma pretendida e focar na jogabilidade
    • Isso parece quase uma lembrança através de óculos de solda cor-de-rosa de 1/4 de polegada. Os jogos AAA modernos também têm momentos de cair o queixo, existe sim a doença das sequências repetitivas, mas também existem obras originais, e a tecnologia claramente torna isso possível
      Também vale lembrar que antigamente havia muitos, muitos, muitos jogos realmente horríveis
    • Eu estava fazendo um Mario Kart 3D numa calculadora com esse algoritmo. Como essa calculadora normalmente mal dá conta de gráficos 2D, era algo bem divertido, mas no fim nunca concluí
      Um dos protótipos é este: https://youtu.be/9Z8Bm8ZmWKI
    • Eu estava fazendo um Mario Kart 3D numa calculadora com esse algoritmo. Como essa calculadora normalmente mal dá conta de gráficos 2D, era algo bem divertido, mas no fim nunca concluí
      Um dos protótipos é este: https://media.discordapp.net/attachments/953383695908216843/...
    • Ainda há muita inovação incrível em tecnologia para jogos. Basta olhar para jogos como Noita, Dreams e Teardown, e entre os mais recentes também há Tiny Glade
      A apresentação técnica recente de Tiny Glade está cheia de coisas que parecem magia: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      Mesmo em níveis mais básicos de engines e frameworks, tecnologias legais continuam surgindo. Por exemplo, há Nanite/Lumen/MegaLights da UE5

  • Aqui estão links relacionados. Será que existe mais algum?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - outubro de 2023, 2 comentários
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - março de 2021, 71 comentários
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - janeiro de 2020, 116 comentários
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - novembro de 2017, 93 comentários
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - setembro de 2017, 2 comentários

  • mars.com vem imediatamente à mente. Não o domínio, e sim o programa. Vídeo: https://www.youtube.com/watch?v=_zSjpIyMt0k
    Adendo: também está no Pouet: https://www.pouet.net/prod.php?which=4662

    • Também encontrei uma implementação em JavaScript desse demo: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Trouxe de volta muitas lembranças. Quando isso chegou até mim por volta de 1998, vinha dentro de um arquivo do Microsoft Word e era controlado com o mouse
      Na época achei incrível, mas como eu era uma criança que não entendia nada de demoscene nem de programação, fiquei decepcionado por não ser um jogo completo. Olhando para trás, eu só pensava nisso como um demo meia-boca de DirectX que circulava por e-mail, não fazia ideia de que era algo que realmente existia
    • Para ser preciso, o mars.com rodava suavemente até em um 286 de 8MHz
    • Isso dói. Ainda lembro de rodar isso em um 286 e ficar impressionado. Ao mesmo tempo, também fiquei decepcionado porque Wing Commander 3 não rodava na mesma máquina

  • O método de renderização é elegante, mas não sei se isso pode mesmo ser chamado de voxel. Não dá para renderizar volumes arbitrários, e o formato de armazenamento dos dados também só permite uma posição para cada x,y
    Não seria apenas uma implementação muito boa de um renderizador de heightmap?

    • Acho que certamente dá para considerar isso um motor de voxel. Um heightmap não suporta saliências como uma octree, mas no fim das contas a altura é uma pilha de voxels
      Uma octree sem saliências teria exatamente a mesma forma que isso
    • Pelo que sei, voxel significa algo como volume element. Semelhante a como pixel vem de picture element, e o x é mais um detalhe estilístico
      Nesse método de renderização, cada coluna é uma caixa 3D, então não vejo grande problema em chamar isso de uma matriz de voxels 2x2
    • Esse tipo de renderizador de heightmap certamente era chamado de “voxel” na época
    • Sim, o nome dado a esse algoritmo induz ao erro

  • Tenho ótimas lembranças de, nos anos 1990, estar aprendendo a trigonometria necessária no ensino médio ao mesmo tempo em que fazia um visualizador de terreno como esse. Primeiro em Pascal, depois em C e Assembly
    Naquela época, era preciso todo tipo de otimização de baixo nível só para fazê-lo rodar
    Descobrir como implementar e otimizar isso sem livros nem internet para consultar foi, para mim, uma das experiências pessoais mais gratificantes

  • Fiz um jogo com essa técnica: https://eri0o.itch.io/i-rented-a-boat
    Foi feito no Adventure Game Studio e usando uma versão mais antiga do motor, que eu ainda não tinha otimizado. Tenho preguiça de atualizar a página no itch, então está assim por enquanto, mas pretendo fazer isso algum dia
    Escrevi lá como foi feito, e há mais detalhes no fórum do AGS

    • Impressionante que isso seja possível no AGS

  • Talvez desse para colocar [2020] no título, e pelos outros comentários no link da discussão abaixo, [2017] também parece possível
    Também houve uma discussão em 2021 sobre o mesmo repositório: https://news.ycombinator.com/item?id=26631995
    Naquela thread também há links para outras discussões
    Não é exatamente a mesma coisa, mas lembro que, quando estava aprendendo a programar, escrevi um programa que gerava heightmaps de terreno e fazia renderização em estilo isométrico com uma técnica parecida. Fiz em QBasic, rodava nas máquinas DOS 386 da escola, no ensino fundamental, e eu usava a memória gráfica como área de trabalho temporária
    Era absurdamente lento, mas eu ficava fascinado com o resultado, e isso foi uma das coisas que me fizeram continuar programando

  • Lembro de já ter lido sobre isso em algum lugar antes, e desta vez estou deixando um comentário para não perder de novo
    Como fã de simuladores de voo, ainda lembro do impacto de jogar Comanche pela primeira vez. Parecia algo vindo do futuro ou de um filme, e dava mesmo a sensação de estar vivendo na era dos computadores

    • A Novalogic usou essa técnica por bastante tempo para renderização de terreno, e meu favorito é o primeiro Delta Force
      Parece que em Comanche 4 e no Black Hawk Down original eles abandonaram isso e passaram para um motor poligonal: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Lembro de Comanche. Isso me fez pensar em quando eu ficava admirado com a geração procedural de Rescue on Fractalus[0], no Atari de 8 bits, cujo nome antes do lançamento era Behind Jaggi Lines
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg a cena de pouso na Terra aparece em 1:00

  • Muito legal
    Na maioria dos jogos modernos, às vezes dá para ver que as montanhas são estruturas ocas por causa de ângulos de câmera estranhos ou problemas de clipping
    Mas com esse método as montanhas são sólidas e maciças >:)

  • Recomendo fortemente fazer um renderizador por software desses por diversão. Ray tracer é um projeto comum, mas esse tipo de código de renderização retrô em tempo real também rende um ótimo projeto de fim de semana
    Há muito tempo implementei quase exatamente o mesmo algoritmo. Mais precisamente, portei um código SDL como exercício para aprender canvas2d: http://namuol.github.io/earf-html5/
    Claro, a implementação linkada é muito mais rápida e muito mais simples que a minha, então, se estiver procurando material de referência, eu não recomendaria meu velho código em CoffeeScript…