VoxelSpace: algoritmo de renderizado de terreno implementado en menos de 20 líneas de código (2020)

 (github.com/s-macke)
4 puntos por GN⁺ 2025-01-05 | 1 comentarios | Compartir por WhatsApp
  • Voxel Space es una técnica de renderizado de terreno 2.5D usada en Comanche de NovaLogic en 1992, que permitía representar montañas y valles con textura usando solo la CPU en una época en que la aceleración por GPU no existía o era demasiado cara
  • El terreno se representa con un mapa de alturas y un mapa de colores; Comanche usaba un mapa de alturas de 1024×1024 de 1 byte y un mapa de colores de 1024×1024 de 1 byte
  • El mapa de colores ya incluye sombreado y sombras, por lo que no hace falta calcular iluminación durante el renderizado, pero como cada posición del mapa solo puede tener una altura, es difícil representar geometrías complejas como edificios o árboles
  • El renderizado básico rasteriza segmentos de línea del mapa de atrás hacia adelante, lee la altura y el color para cada columna de la pantalla y dibuja líneas verticales; implementa un campo de visión de 90° y proyección en perspectiva con apenas unas líneas de código
  • Las mejoras de rendimiento se pueden lograr dibujando de adelante hacia atrás, usando un y-buffer por columna para omitir las partes ocultas y reduciendo el nivel de detalle en distancias lejanas

Contexto en el que surgió Voxel Space

  • En 1992, las CPU eran 1000 veces más lentas que las actuales, y la aceleración por GPU era desconocida o inaccesible
  • Los juegos 3D se calculaban solo con la CPU, y lo habitual era que los motores de renderizado dibujaran polígonos rellenos con colores planos
  • NovaLogic lanzó Comanche en 1992, y su representación de texturas, sombreado y sombras en montañas y valles lo distinguía de los gráficos de juegos de la época
  • El README ofrece una Web Demo of the Voxel Space Engine

Representación del terreno: mapa de alturas y mapa de colores

  • La forma más sencilla de representar terreno en Voxel Space es usar un height map y un color map
  • Comanche usa los siguientes dos mapas
    • Mapa de alturas de 1 byte de 1024×1024
    • Mapa de colores de 1 byte de 1024×1024
  • Estos mapas se repiten de forma periódica
  • Cada posición del mapa solo puede tener una altura
    • No se pueden representar geometrías complejas como edificios o árboles
    • A cambio, el mapa de colores ya incluye sombreado y sombras, por lo que no hace falta calcular la iluminación durante el renderizado

Algoritmo básico de renderizado

  • El motor Voxel Space renderiza el terreno rasterizando el mapa de alturas y el mapa de colores, y dibujando líneas verticales en pantalla
  • El procedimiento básico es el siguiente
    • Limpiar la pantalla
    • Dibujar de atrás hacia adelante para garantizar el manejo de oclusiones
    • Encontrar en el mapa una línea que corresponda a la misma distancia óptica desde el observador
    • Considerar el campo de visión y la proyección en perspectiva
    • Dividir esa línea según el número de columnas de la pantalla
    • Leer la altura y el color desde los mapas 2D en cada posición del segmento de línea
    • Aplicar proyección en perspectiva a la coordenada de altura
    • Dibujar una línea vertical con la altura proyectada y el color del mapa de colores
  • El bucle central en su forma más simple en Python reduce z desde una distancia lejana hacia una cercana y llama a DrawVerticalLine para cada columna de pantalla
  • La llamada de ejemplo pasa la posición, la altura de la cámara, la posición del horizonte, la escala de altura, la distancia máxima, y el ancho y alto de la pantalla

Agregar rotación

  • El algoritmo básico solo puede mirar hacia el norte
  • Para mirar en otras direcciones, se agrega código para rotar las coordenadas
  • La versión con rotación recibe phi como ángulo de visión y precalcula sin(phi) y cos(phi)
  • Aplica las coordenadas rotadas al cálculo de los puntos límite izquierdo y derecho del campo de visión, e incrementa x e y juntos a lo largo de cada columna de pantalla
  • La estructura central del renderizado se mantiene igual
    • Cálculo de segmentos de línea por distancia
    • Rasterización según las columnas de la pantalla
    • Consulta del mapa de alturas y del mapa de colores
    • Dibujo de líneas verticales tras la proyección en perspectiva

Formas de mejorar el rendimiento

  • En lugar de dibujar de atrás hacia adelante, se puede dibujar de adelante hacia atrás para reducir las áreas que quedarán ocultas
  • Este método requiere un y-buffer que guarde la posición y más alta para cada columna de la pantalla
    • El valor inicial del y-buffer se configura como la altura de la pantalla
    • Solo se dibuja la parte visible cuando el nuevo height_on_screen está por encima del y-buffer existente
    • Después de dibujar, el y-buffer se actualiza a una posición más alta
  • La distancia z aumenta desde lo cercano hacia lo lejano
  • Si se incrementa gradualmente dz, se puede muestrear con intervalos más grandes en distancias lejanas y obtener un efecto de Level of Detail
  • Es una forma de renderizar con más detalle lo cercano y con menos detalle lo lejano

Materiales proporcionados y licencia

  • El repositorio incluye varios pares de mapas de colores y mapas de alturas
  • La parte de software está bajo la licencia MIT
  • La tecnología Voxel Space podría seguir teniendo patentes vigentes en algunos países
  • Los mapas de colores y de alturas fueron obtenidos mediante ingeniería inversa del juego Comanche, por lo que quedan excluidos de la licencia
  • Como material relacionado, se proporciona el enlace Voxel terrain engine - an introduction

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-01-05
Comentarios de Hacker News

  • Está muy bueno. Extraño la época en que este tipo de algoritmos nuevos y elegantes creaban experiencias casi mágicas
    Puede que lo sienta así porque me estoy haciendo mayor, pero me parece que los juegos de la época en que los recursos de hardware eran limitados tenían más magia que ahora. En los 80, 90 y principios de los 2000, casi cada año, o al menos con cada generación, los juegos empujaban hacia adelante al medio mismo, y los desarrolladores exprimían el hardware al máximo con nuevas técnicas y optimizaciones que parecían magia pura
    Hoy en día, plataformas de fantasía como PICO-8 me resultan mucho más interesantes que los lanzamientos repetitivos de los estudios AAA, y la verdad no entiendo muy bien por qué juegos que básicamente solo cambian los assets tienen tanto éxito año tras año

    • Incluso en los juegos AAA modernos sigue habiendo mucha tecnología casi mágica. De hecho, la industria de los videojuegos es uno de los pocos sectores que se toma el rendimiento muy en serio, y a veces incluso lo prioriza por encima de la seguridad o la precisión
      Solo que ahora todo es mucho más complejo y menos visible. Antes se notaba el salto de un triángulo plano a una textura gracias a un truco matemático ingenioso; ahora el avance consiste en mejorar el sombreado en una esquina de una habitación. Cualquiera nota una mejora en las texturas, pero las sombras en una esquina son algo que cuesta señalar con precisión si no eres del rubro. Aun así, todos esos elementos se van acumulando y hacen que los gráficos en conjunto se vean mejor, aunque ya no impresionen tanto como antes
      La industria AAA es un gran negocio, hacer juegos cuesta muchísimo y los inversionistas quieren ganancias. Por eso normalmente estudian el mercado, ven qué se vende bien y hacen algo parecido. Hay menos originalidad, pero también menos riesgo
      En cambio, en la industria indie hay miles de estudios y, como no pueden superar a los AAA en cantidad de contenido o nivel de acabado, necesitan otras armas, como ideas originales, para destacar entre la multitud. Pero hoy en día muchas veces el principal motor ya no es superar limitaciones técnicas, porque ya no hay tantas como antes. De hecho, por costos, es común que empujen la tecnología menos que una producción AAA No conozco mucho la escena de PICO-8, pero me da curiosidad cuánto de eso consiste en superar limitaciones técnicas artificiales y cuánto en usar la plataforma del modo previsto y enfocarse en la jugabilidad
    • Esto suena casi como una nostalgia con gogles de soldadura de 1/4 de pulgada color de rosa. Los juegos AAA modernos también tienen momentos increíblemente buenos, sí existe la enfermedad de las secuelas repetitivas, pero también hay obras originales, y la tecnología claramente lo hace posible
      También recuerdo que antes había muchísimos juegos realmente, realmente, realmente malos
    • Estaba haciendo un Mario Kart 3D en una calculadora con este algoritmo. Como esa calculadora normalmente apenas puede con gráficos 2D, era bastante divertido, pero al final nunca lo terminé
      Este es uno de los prototipos: https://youtu.be/9Z8Bm8ZmWKI
    • Estaba haciendo un Mario Kart 3D en una calculadora con este algoritmo. Como esa calculadora normalmente apenas puede con gráficos 2D, era bastante divertido, pero al final nunca lo terminé
      Este es uno de los prototipos: https://media.discordapp.net/attachments/953383695908216843/...
    • En la tecnología de videojuegos todavía hay mucha innovación genial. Basta ver juegos como Noita, Dreams y Teardown, y entre los más recientes también está Tiny Glade
      La presentación técnica reciente de Tiny Glade está llena de cosas casi mágicas: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      Incluso en motores y frameworks de nivel más básico siguen apareciendo técnicas muy interesantes. Por ejemplo, en UE5 están Nanite/Lumen/MegaLights

  • Aquí van algunos enlaces relacionados. ¿Habrá más?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - octubre de 2023, 2 comentarios
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - marzo de 2021, 71 comentarios
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - enero de 2020, 116 comentarios
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - noviembre de 2017, 93 comentarios
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - septiembre de 2017, 2 comentarios

  • mars.com me vino de inmediato a la mente. No el dominio, sino el programa. Video: https://www.youtube.com/watch?v=_zSjpIyMt0k
    Extra: también está en Pouet: https://www.pouet.net/prod.php?which=4662

    • También encontré una implementación en JavaScript de este demo: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Me llegaron de golpe los recuerdos. Cuando me lo pasaron, por ahí de 1998, venía dentro de un archivo de Microsoft Word y se controlaba con el mouse
      En ese momento me pareció genial, pero como era un niño que no sabía absolutamente nada de la demoscene ni de programación, me decepcionó que no fuera un juego completo. Viéndolo en retrospectiva, yo lo tenía más bien como una especie de demo chafa de DirectX que circulaba por email, no sabía que era algo real
    • Si queremos ser precisos, mars.com corría con fluidez incluso en una 286 de 8 MHz
    • Me duele. Todavía recuerdo haberlo probado en una 286 y haber quedado impresionado. Al mismo tiempo, también me decepcionó que Wing Commander 3 no corriera en esa misma máquina

  • La forma de renderizar es elegante, pero no sé si realmente se le puede llamar vóxel. No puede renderizar volúmenes arbitrarios, y la forma de almacenar los datos también solo permite una posición para cada x,y
    ¿No es simplemente una muy buena implementación de un renderizador de mapas de altura?

    • Yo diría que sí cuenta claramente como un motor vóxel. Un mapa de altura no soporta salientes como un octree, pero al final la altura es una pila de vóxeles
      Un octree sin salientes tendría exactamente esta misma forma
    • Hasta donde sé, vóxel significa algo así como elemento de volumen, parecido a cómo píxel viene de picture element, y la x es más bien por estilo
      En este método de renderizado, cada columna es una caja 3D, así que no veo problema en llamarlo una matriz de vóxeles de 2x2
    • Este tipo de renderizador de mapas de altura en esa época sí se llamaba “voxel”
    • Sí, el nombre que le pusieron a este algoritmo lleva a confusión

  • Tengo muy buenos recuerdos de cuando en los 90, mientras aprendía la trigonometría necesaria en la preparatoria, hice uno de estos visores de terreno. Primero en Pascal, luego en C y Assembly
    En ese entonces, para hacer que corriera, hacían falta todo tipo de optimizaciones de bajo nivel
    Dar con la forma de implementarlo y optimizarlo sin libros de referencia ni internet fue, personalmente, una de las cosas más satisfactorias que he hecho

  • Hice un juego con esta técnica: https://eri0o.itch.io/i-rented-a-boat
    Lo hice con Adventure Game Studio, y fue creado con una versión anterior del motor que todavía no había optimizado. Me da flojera actualizar la página de itch y por eso la dejo así, pero algún día lo haré
    Ahí mismo escribí cómo lo hice, y en el foro de AGS hay más detalles

    • Impresiona que esto sea posible en AGS

  • Parece que también se podría poner [2020] en el título, y viendo otros comentarios en el enlace de discusión de abajo, [2017] también parece posible
    También hubo una discusión de 2021 sobre el mismo repositorio: https://news.ycombinator.com/item?id=26631995
    En ese hilo también hay enlaces a otras discusiones
    No es exactamente lo mismo, pero recuerdo haber hecho, cuando recién estaba aprendiendo a programar, un programa que generaba mapas de altura de terreno y hacía renderizado estilo isométrico con una técnica parecida. Lo hice en QBasic, corría en una máquina DOS 386 de la secundaria, y usaba la memoria gráfica como espacio de trabajo temporal
    Era lentísimo, pero me fascinó el resultado, y fue una de las cosas que me empujó a seguir programando

  • Recuerdo haber leído sobre esto en algún lado hace tiempo, y esta vez dejo un comentario para no volver a perderlo
    Como fan de los simuladores de vuelo, todavía recuerdo el impacto de jugar por primera vez Comanche. Se sentía como algo traído del futuro o de una película, y realmente me hizo sentir que estaba viviendo en la era de las computadoras

    • Novalogic usó esta técnica para renderizar terreno durante bastante tiempo, y mi favorita sigue siendo la primera Delta Force
      Parece que en Comanche 4 y en el Black Hawk Down original abandonaron este enfoque y se pasaron a un motor poligonal: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Sí me acuerdo de Comanche. Me hizo pensar en cuando me impresionó la generación procedural de Rescue on Fractalus[0] en Atari de 8 bits, que antes de salir se llamaba Behind Jaggi Lines
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg la escena de aterrizaje en la Tierra sale en 1:00

  • Está buenísimo
    En la mayoría de los juegos modernos, por ángulos raros de cámara o problemas de clipping, a veces se alcanza a ver que las montañas son una estructura hueca
    Pero con este enfoque las montañas están totalmente macizas >:)

  • Recomiendo muchísimo hacer uno de estos renderizadores por software por diversión. Los ray tracers son un proyecto muy común, pero este tipo de código de renderizado retro en tiempo real también queda perfecto como proyecto de fin de semana
    Hace mucho implementé casi el mismo algoritmo. Más exactamente, porteé código SDL como ejercicio para aprender canvas2d: http://namuol.github.io/earf-html5/
    Claro, la implementación enlazada es mucho más rápida y mucho más simple que la mía, así que si buscas material de referencia, no recomendaría mi viejo código en CoffeeScript…