VoxelSpace: Ein Terrain-Rendering-Algorithmus in weniger als 20 Zeilen Code (2020)

 (github.com/s-macke)
4 Punkte von GN⁺ 2025-01-05 | 1 Kommentare | Auf WhatsApp teilen
  • Voxel Space ist eine 2,5D-Terrain-Rendering-Technik, die 1992 in NovaLogics Comanche verwendet wurde und in einer Zeit, in der GPU-Beschleunigung unbekannt oder teuer war, allein auf der CPU texturierte Berge und Täler darstellte
  • Das Terrain wird durch eine Höhenkarte und eine Farbkarte beschrieben; Comanche nutzte eine 1024×1024 große 1-Byte-Höhenkarte und eine 1024×1024 große 1-Byte-Farbkarte
  • Die Farbkarte enthält bereits Schattierung und Schatten, sodass beim Rendering keine Beleuchtungsberechnung nötig ist; da jede Position der Karte jedoch nur eine Höhe haben kann, lassen sich komplexe geometrische Strukturen wie Gebäude oder Bäume nur schwer darstellen
  • Das grundlegende Rendering rastert Liniensegmente der Karte von hinten nach vorn und zeichnet für jede Bildschirmspalte anhand von Höhe und Farbe eine vertikale Linie; ein Sichtfeld von 90° und perspektivische Projektion werden in wenigen Codezeilen umgesetzt
  • Leistungsverbesserungen sind möglich, indem man von vorn nach hinten zeichnet, verdeckte Bereiche mit einem spaltenweisen y-buffer überspringt und für große Entfernungen den Detailgrad reduziert

Kontext, in dem Voxel Space entstand

  • 1992 waren CPUs 1000-mal langsamer als heute, und GPU-Beschleunigung war entweder unbekannt oder unerschwinglich
  • 3D-Spiele wurden allein auf der CPU berechnet; Rendering-Engines zeichneten üblicherweise mit Vollfarben gefüllte Polygone
  • NovaLogic veröffentlichte 1992 Comanche; die Darstellung von Texturen, Schattierungen und Schatten in Bergen und Tälern hob sich von der damaligen Spielegrafik ab
  • Das README bietet eine Web Demo of the Voxel Space Engine

Terrain-Darstellung: Höhenkarte und Farbkarte

  • Die einfachste Methode, Terrain in Voxel Space darzustellen, ist die Verwendung einer height map und einer color map
  • Comanche verwendet die folgenden zwei Karten
    • 1024×1024 große 1-Byte-Höhenkarte
    • 1024×1024 große 1-Byte-Farbkarte
  • Diese Karten wiederholen sich periodisch
  • Jede Kartenposition kann nur eine Höhe besitzen
    • Komplexe geometrische Strukturen wie Gebäude oder Bäume können nicht dargestellt werden
    • Dafür sind Schattierungen und Schatten bereits in der Farbkarte enthalten, sodass im Rendering-Prozess keine Beleuchtung berechnet werden muss

Grundlegender Rendering-Algorithmus

  • Die Voxel-Space-Engine rendert Terrain, indem sie Höhenkarte und Farbkarte rastert und vertikale Linien auf den Bildschirm zeichnet
  • Der grundlegende Ablauf ist wie folgt
    • Bildschirm löschen
    • Von hinten nach vorn zeichnen, um Verdeckung sicherzustellen
    • Auf der Karte die Linie finden, die derselben optischen Entfernung vom Betrachter entspricht
    • Sichtfeld und perspektivische Projektion berücksichtigen
    • Diese Linie entsprechend der Anzahl der Bildschirmspalten unterteilen
    • An jeder Liniensegment-Position Höhe und Farbe aus den 2D-Karten lesen
    • Perspektivische Projektion auf die Höhenkoordinate anwenden
    • Mit der projizierten Höhe und der Farbe aus der Farbkarte eine vertikale Linie zeichnen
  • Die einfachste Kernschleife in Python-Form verringert z von der Ferne zur Nähe und ruft für jede Bildschirmspalte DrawVerticalLine auf
  • Der Beispielaufruf übergibt Position, Kamerahöhe, Horizontposition, Höhenskalierung, maximale Entfernung sowie Bildschirmbreite und -höhe

Rotation hinzufügen

  • Der Basisalgorithmus kann nur nach Norden blicken
  • Um in andere Richtungen zu schauen, wird Code zum Rotieren der Koordinaten hinzugefügt
  • Die Rotationsversion nimmt phi als Blickwinkel entgegen und berechnet sin(phi) und cos(phi) vorab
  • Für die Berechnung der linken und rechten Sichtfeldgrenzen werden rotierte Koordinaten angewendet, und entlang jeder Bildschirmspalte werden x und y gemeinsam erhöht
  • Die Kernstruktur des Renderings bleibt unverändert
    • Liniensegmente nach Entfernung berechnen
    • Rasterung passend zu den Bildschirmspalten
    • Höhenkarte und Farbkarte abfragen
    • Nach perspektivischer Projektion vertikale Linien zeichnen

Methoden zur Leistungsverbesserung

  • Zeichnet man statt von hinten nach vorn von vorn nach hinten, lässt sich der später verdeckte Bereich reduzieren
  • Diese Methode benötigt für jede Bildschirmspalte einen y-buffer, der die höchste y-Position speichert
    • Der anfängliche y-buffer-Wert wird auf die Bildschirmhöhe gesetzt
    • Nur wenn das neu berechnete height_on_screen oberhalb des bisherigen y-buffers liegt, wird der sichtbare Teil gezeichnet
    • Nach dem Zeichnen wird der y-buffer auf eine höhere Position aktualisiert
  • Die Entfernung z steigt von nah nach fern
  • Wenn dz schrittweise vergrößert wird, kann in größerer Entfernung mit größeren Abständen gesampelt werden, wodurch ein Level of Detail-Effekt entsteht
  • Nahe Bereiche werden detaillierter gerendert, entfernte Bereiche weniger detailliert

Bereitgestellte Materialien und Lizenz

  • Das Repository enthält mehrere Paare aus Farbkarten und Höhenkarten
  • Der Softwareteil steht unter der MIT-Lizenz
  • Die Voxel-Space-Technik kann in einigen Ländern noch patentgeschützt sein
  • Farbkarte und Höhenkarte sind aus dem Spiel Comanche reverse-engineert und daher von der Lizenz ausgenommen
  • Als weiterführendes Material wird der Link Voxel terrain engine - an introduction bereitgestellt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-05
Hacker-News-Meinungen

  • Sehr cool. Ich vermisse die Zeiten, in denen solche neuen und eleganten Algorithmen Erlebnisse geschaffen haben, die sich wie Magie anfühlten.
    Vielleicht empfinde ich das nur so, weil ich älter werde, aber Spiele aus der Zeit, als Hardware-Ressourcen begrenzt waren, hatten meiner Meinung nach mehr Magie als heute. In den 80ern, 90ern und frühen 2000ern haben Spiele fast jedes Jahr, mindestens aber jede Generation, das Medium selbst vorangebracht, und Entwickler holten mit neuen Techniken und Optimierungen, die sich wie reine Magie anfühlten, das Letzte aus der Hardware heraus.
    Heutzutage finde ich Fantasy-Plattformen wie PICO-8 viel interessanter als die wiederholten Releases von AAA-Studios, und ich verstehe ehrlich gesagt nicht so recht, warum Spiele, bei denen praktisch nur die Assets ausgetauscht wurden, Jahr für Jahr so erfolgreich sind.

    • Auch in modernen AAA-Spielen steckt immer noch viel magische Technik. Tatsächlich ist die Spielebranche einer der wenigen Bereiche, die Performance wirklich ernst nehmen, und manchmal wird Performance sogar höher priorisiert als Sicherheit oder Korrektheit.
      Nur ist das heute viel komplexer und weniger offensichtlich. Früher konnte man den Fortschritt sehen, wenn clevere Mathe-Tricks den Sprung von flachen Dreiecken zu Texturen ermöglichten; heute besteht der Fortschritt eher darin, die Schattierung in einer Zimmerecke zu verbessern. Verbesserte Texturen bemerkt jeder sofort, aber den Schatten in der Ecke können Nicht-Branchenleute schwer konkret benennen. Trotzdem summieren sich solche Elemente zu einer besseren Gesamtgrafik, nur wirkt es nicht mehr so beeindruckend wie früher.
      Die AAA-Spielebranche ist ein großes Geschäft, die Entwicklungskosten für Spiele sind enorm, und Investoren wollen Rendite. Deshalb wird in der Regel der Markt untersucht, man schaut, was sich gut verkauft, und entwickelt dann in eine ähnliche Richtung. Das ist weniger originell, senkt aber das Risiko.
      In der Indie-Spielebranche dagegen gibt es Tausende Studios, und weil sie bei Umfang oder Polishing nicht mit AAA mithalten können, brauchen sie andere Waffen, etwa originelle Ideen, um aus der Masse herauszustechen. Allerdings ist das Überwinden technischer Grenzen heute oft nicht mehr der wichtigste Antrieb, weil es nicht mehr so viele Beschränkungen gibt wie früher. Häufig wird technisch sogar weniger weit gegangen als bei AAA-Produktionen, weil es aus Kostengründen nicht tragbar wäre.
      Die PICO-8-Szene kenne ich nicht gut, aber ich frage mich, wie viel davon darin besteht, künstliche technische Beschränkungen zu überwinden, und wie viel darin, die Plattform auf die vorgesehene Weise zu nutzen und sich auf das Gameplay zu konzentrieren.
    • Das klingt für mich fast nach Erinnerungen durch eine rosarote 1/4-Zoll-Schweißerbrille. Auch moderne AAA-Spiele haben Momente, die einen schwindelig machen, so gut sind sie; es gibt zwar die Krankheit der endlosen Fortsetzungen, aber auch originelle Werke, und die Technik macht das ganz eindeutig möglich.
      Man sollte auch nicht vergessen, dass es früher wirklich, wirklich, wirklich viele grottenschlechte Spiele gab.
    • Ich habe mit diesem Algorithmus an 3D Mario Kart auf einem Taschenrechner gebaut. Der Rechner schafft normalerweise kaum 2D-Grafik, deshalb war das ziemlich spannend, aber ich habe es nie fertiggestellt.
      Einer der Prototypen ist dieser hier: https://youtu.be/9Z8Bm8ZmWKI
    • Ich habe mit diesem Algorithmus an 3D Mario Kart auf einem Taschenrechner gebaut. Der Rechner schafft normalerweise kaum 2D-Grafik, deshalb war das ziemlich spannend, aber ich habe es nie fertiggestellt.
      Einer der Prototypen ist dieser hier: https://media.discordapp.net/attachments/953383695908216843/...
    • In der Spieletechnik gibt es immer noch viele großartige Innovationen. Man muss sich nur Spiele wie Noita, Dreams oder Teardown ansehen, und als neueres Beispiel gibt es auch Tiny Glade.
      Der jüngste Technikvortrag zu Tiny Glade ist voller magischer Dinge: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      Auch auf der grundlegenderen Ebene von Engines und Frameworks entstehen tolle Technologien. Beispiele dafür sind Nanite/Lumen/MegaLights in UE5.

  • Hier sind ein paar verwandte Links. Gibt es noch andere?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - Oktober 2023, 2 Kommentare
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - März 2021, 71 Kommentare
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - Januar 2020, 116 Kommentare
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - November 2017, 93 Kommentare
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - September 2017, 2 Kommentare

  • mars.com kam mir sofort in den Sinn. Kein Domainname, sondern ein Programm. Video: https://www.youtube.com/watch?v=_zSjpIyMt0k
    Nachtrag: Gibt es auch auf Pouet: https://www.pouet.net/prod.php?which=4662

    • Habe auch eine JavaScript-Implementierung dieser Demo gefunden: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Da kommen die Erinnerungen an früher richtig hoch. Als es mir etwa 1998 weitergegeben wurde, steckte es in einer Microsoft-Word-Datei und wurde mit der Maus gesteuert.
      Damals fand ich es cool, war aber enttäuscht, weil es kein vollständiges Spiel war – ich war ein Kind, das von Demoszene oder Programmierung überhaupt keine Ahnung hatte. Rückblickend hielt ich es nur für irgendeine dürftige DirectX-Demo, die per E-Mail herumging; ich wusste nicht, dass es tatsächlich ein existierendes Ding war.
    • Genau genommen lief mars.com sogar auf einem 8-MHz-286 flüssig.
    • Das tut weh. Ich erinnere mich noch, wie ich es auf einem 286 laufen ließ und völlig überwältigt war. Gleichzeitig war ich enttäuscht, dass Wing Commander 3 auf derselben Maschine nicht lief.

  • Die Rendering-Methode ist elegant, aber ich weiß nicht, ob man das Voxel nennen kann. Man kann keine beliebigen Volumen rendern, und auch die Datenspeicherung lässt für ein gegebenes x,y nur eine einzige Position zu.
    Ist das nicht einfach eine schicke Implementierung eines Heightmap-Renderers?

    • Ich denke schon, dass man das eindeutig als Voxel-Engine betrachten kann. Eine Heightmap unterstützt zwar keine Überhänge wie ein Octree, aber letztlich ist die Höhe ein Stapel von Voxeln.
      Ein Octree ohne Überhänge hätte exakt dieselbe Form wie das hier.
    • Soweit ich weiß, bedeutet Voxel so etwas wie Volume Element. Ähnlich wie Pixel von Picture Element kommt; das x ist eher ein Buchstabe fürs Aussehen.
      Bei dieser Rendering-Methode ist jede Spalte eine 3D-Box, daher finde ich es unproblematisch, sie eine 2x2-Voxel-Matrix zu nennen.
    • Solche Heightmap-Renderer wurden damals ganz eindeutig „voxel“ genannt.
    • Stimmt, der Name für diesen Algorithmus ist irreführend.

  • Ich habe sehr gute Erinnerungen daran, wie ich in den 1990ern in der Highschool gerade die dafür nötige Trigonometrie lernte und gleichzeitig solche Terrain-Viewer baute. Zuerst in Pascal, dann in C und Assembly.
    Damals brauchte man alle möglichen Low-Level-Optimierungen, damit es überhaupt lief.
    Ohne Bücher oder Internet herauszufinden, wie man das implementiert und optimiert, war für mich persönlich eine der lohnendsten Erfahrungen.

  • Ich habe mit dieser Technik ein Spiel gemacht: https://eri0o.itch.io/i-rented-a-boat
    Es wurde mit Adventure Game Studio gebaut und entstand auf einer früheren Version der Engine, die noch nicht optimiert war. Ich bin zu faul, die itch-Seite zu aktualisieren, deshalb bleibt es erst mal so, aber irgendwann mache ich es.
    Dort habe ich aufgeschrieben, wie ich es gemacht habe, und im AGS-Forum gibt es noch mehr Details.

    • Beeindruckend, dass das in AGS möglich ist.

  • Man könnte wohl [2020] in den Titel setzen, und wenn man sich die anderen Kommentare im unten verlinkten Thread ansieht, wirkt auch [2017] möglich.
    Es gab auch eine Diskussion von 2021 zum selben Repository: https://news.ycombinator.com/item?id=26631995
    In diesem Thread führen die Links ebenfalls zu weiteren Diskussionen.
    Nicht ganz dasselbe, aber ich erinnere mich, dass ich, als ich Programmieren lernte, ein Programm schrieb, das Terrain-Heightmaps erzeugte und sie mit einer ähnlichen Technik im isometrischen Stil renderte. Ich schrieb es in QBasic, ließ es auf DOS-Maschinen mit 386ern in der Middle School laufen und nutzte den Grafikspeicher als temporären Arbeitsbereich.
    Es war unglaublich langsam, aber das Ergebnis faszinierte mich – und es war einer der Gründe, warum ich weiterprogrammiert habe.

  • Ich erinnere mich, das früher irgendwo gelesen zu haben; diesmal hinterlasse ich einen Kommentar, damit ich es nicht wieder verliere.
    Als Fan von Flugsimulatoren erinnere ich mich noch immer an den Schock, als ich Comanche zum ersten Mal spielte. Es fühlte sich an, als käme es aus der Zukunft oder aus einem Film, und ich hatte wirklich das Gefühl, im Computerzeitalter zu leben.

    • Novalogic hat diese Technik ziemlich lange für Terrain-Rendering verwendet, und mein Favorit ist der erste Delta Force-Teil.
      Bei Comanche 4 und dem ursprünglichen Black Hawk Down scheinen sie diese Methode aufgegeben und auf eine Polygon-Engine umgestellt zu haben: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Ich erinnere mich an Comanche. Das brachte mich zurück zu dem Staunen über die prozedurale Generierung von Rescue on Fractalus[0] auf dem 8-Bit-Atari, das vor der Veröffentlichung Behind Jaggi Lines hieß.
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg Die Erdlandeszene kommt bei 1:00.

  • Wirklich cool.
    In den meisten modernen Spielen sieht man wegen merkwürdiger Kamerawinkel oder Clipping-Problemen manchmal, dass Berge hohle Strukturen sind.
    Bei dieser Methode sind die Berge aber solide und vollständig gefüllt >:)

  • Ich kann nur sehr empfehlen, solche Software-Renderer zum Spaß zu bauen. Raytracer sind ein verbreitetes Projekt, aber solcher Retro-Echtzeit-Rendering-Code eignet sich auch gut als Wochenendprojekt.
    Vor langer Zeit habe ich fast denselben Algorithmus implementiert. Genauer gesagt habe ich als Übung zum Lernen von canvas2d SDL-Code portiert: http://namuol.github.io/earf-html5/
    Natürlich ist die verlinkte Implementierung viel schneller und viel einfacher als meine; wenn ihr also Referenzmaterial sucht, empfehle ich meinen alten CoffeeScript-Code nicht …