Wie eine unbekannte Militärsimulator-Technik die 3D-Grafik von Doom antrieb

Anfang 1993, während der Entwicklung von Doom bei id Software, musste Chefprogrammierer John Carmack mitansehen, wie sein neuer dreidimensionaler Grafik-Renderer ins Stocken geriet. Die Engine versuchte, komplexe architektonische Grundrisse wie kreisförmige Treppenabsätze zu verarbeiten, was die Software zu endlosen, sich wiederholenden Rendering-Berechnungen veranlasste. Doom sollte auf gewöhnlichen Heim-PCs flüssige Action liefern, doch die zugrundeliegende Grafik-Engine konnte die nötige Leistung nicht aufrechterhalten. Um den Engpass zu beseitigen, musste Carmack eine der schwierigsten Herausforderungen der frühen Computergrafik lösen: zu bestimmen, welche Oberflächen sichtbar waren, ohne Rechenleistung an verdeckte Geometrie zu verschwenden.

Die Einschränkungen von Echtzeit-Software-Rendering

Anfang der 1990er-Jahre fehlte IBM-kompatiblen Heim-PCs dedizierte Grafikhardware, weshalb Hauptprozessoren das gesamte visuelle Rendering in Software bewältigen mussten. Um einen flüssigen Spielablauf zu gewährleisten, musste eine Game-Engine das Problem der verdeckten Oberflächen (Visible Surface Determination) lösen, indem sie mindestens 30-mal pro Sekunde entschied, welche Polygone von einem bestimmten Blickwinkel der Kamera aus sichtbar waren. Im vorherigen Titel von id Software, Wolfenstein 3D, vereinfachte Carmack diese Herausforderung, indem er das Leveldesign auf achsenparallele Wände auf einem starren Raster beschränkte. Dadurch konnte ein einfacher Ray-Marching-Algorithmus Schnittpunkte mit Wänden schnell und mit minimalen Prozessorzyklen berechnen. Doom führte jedoch dynamische Elemente wie diagonale Wände, Treppen und variable Deckenhöhen ein, was rasterbasiertes Ray Marching unbrauchbar machte.

Von Flugsimulatoren zur akademischen Forschung

Um diese komplexen Umgebungen zu unterstützen, entwickelte Carmack zunächst einen Konvex-Sektor-Algorithmus, der den unmittelbaren Raum des Spielers zeichnete und sich von dort aus in angrenzende Bereiche ausbreitete. Als komplex verschachtelte Geometrie zu gravierenden Leistungseinbrüchen führte, suchte er nach einer grundlegenden Alternative. Während der Portierung von Wolfenstein 3D auf die begrenzte Hardware des Super Nintendo begann Carmack, wissenschaftliche Arbeiten zur Computergrafik zu studieren. Er fand heraus, dass das Konzept der räumlichen Unterteilung auf einen Bericht der US Air Force aus dem Jahr 1969 mit dem Titel „Study for Applying Computer-Generated Images to Visual Simulation“ zurückging, der Echtzeitgrafik für Flugsimulatoren untersuchte. Auf dieser Grundlage veröffentlichten die Forscher Henry Fuchs, Zvi Kedem und Bruce Naylor 1980 eine Arbeit mit dem Titel „On Visible Surface Generation by A Priori Tree Structures“, die den Binary-Space-Partitioning-Baum (BSP-Baum) einführte.

Die Integration von Binary Space Partitioning in Doom

Der BSP-Baum löste die Bestimmung sichtbarer Oberflächen, indem er rechenintensive geometrische Berechnungen von der Laufzeit in die Vorverarbeitung verlagerte. Der Algorithmus berechnete räumliche Unterteilungen entlang von Ebenen in der Levelgeometrie im Voraus und strukturierte die Welt bereits in eine Hierarchie, bevor das Spiel überhaupt lief. Während des Spiels reduzierte sich das Sortieren von Objekten nach der Tiefe auf einen leichtgewichtigen In-Order-Durchlauf des Baumes basierend auf der Kameraposition des Spielers. Carmack passte diese akademische Struktur an die Rendering-Engine von Doom an. Durch den Verzicht auf redundante geometrische Berechnungen und kostenintensive Schreibzugriffe auf den VGA-Frame-Buffer renderte die Engine rasterfreie Architektur schnell auf einer Vielzahl von Heimcomputern.

Die Transformation der 3D-Grafikarchitektur

Als id Software Doom im Jahr 1993 veröffentlichte, setzte die Engine einen neuen Benchmark für Echtzeit-3D-Software-Rendering auf Heimcomputern. Indem er eine 1980 für High-End-Flugsimulatoren entwickelte Datenstruktur an Heim-PCs anpasste, bewies Carmack, dass vorausberechnete räumliche Unterteilung komplexe virtuelle Umgebungen auch ohne dedizierte Hardwarebeschleuniger spielbar machen konnte. Dieser technische Durchbruch etablierte BSP-Bäume für viele Jahre als grundlegende Architekturtechnik im Game-Engine-Design.

Titelbild: KI-generierte Illustration; kein Dokumentarfoto.

Quelle: 0b10 0b10 How Much of a Genius-Level Move Was Using Binary Space Partitioning in Doom?