Dieser Artikel behandelt das Überwinden der unbewussten Grenzen, die oft in einem Projekt gesetzt sind. Anschließend werden die verschiedenen Techniken beschrieben, die John Cormack bei der Entwicklung seiner Algorithmen zur Visible Surface Determination (Bestimmung der sichtbaren Oberfläche) und zum Culling (VSD) in Quake ausprobiert hat. Dazu gehört eine Beschreibung des potenziell sichtbaren Sets (PVS), auch bekannt als Sichtbarkeitslisten.
BSP-basiertes Culling.
Als größte Herausforderung für Programmierer erweist sich regelmäßig die Verschiebung der VSD mit den begrenzten Aufgaben der Rasterung wie dem perspektivisch korrekten Texture Mapping in der Hardware. Räumliche Unterteilung ist ein Ansatz und dieser erwähnt die Darstellung von Quake-Levels als 3D-BSP und es wird darauf hingewiesen, dass dieses BSP keine Polygone in Tree-Nodes speichert, sondern in den Sheets.
Es wird anschließend das Culling von Polygonen völlig außerhalb des View-Frustums erklärt und auf die Vorteile des Cullings der gesamten BSP-Subtress hingewiesen, die die Pflege von Begrenzungsrahmen oder Kugeln mit jedem Node erfordert.
Überziehen.
Das Problem der Überziehung ist am offensichtlichsten bei der Back-to-Front-BSP-Überquerung des Painter Algorithmus. Deine World wird nicht skalierbar dargestellt und die Leistung wird nicht nur langsam, sondern noch schlimmer, sie wird nicht gleichmäßig sein. Es ist erwähnenswert, dass bei einem Quake-Level von 10.000 Polygonen eine Überziehung von zehnmal oder mehr im Worst-Case-Fall nicht selten war.
Um dieses Problem zu lösen und die Überziehung auf eine überschaubare und vor allem ebene Größe zu reduzieren, versuchte John Carmack eine Vielzahl verschiedener Ansätze aus:
- Beam-Tree (View Frustum Subdivision durch Hierarchie der Clipping-Ebenen)
- Unterteilung des Raycast (8×8 Pixel Raster)
- Wirbelfreie Oberflächen (unendliche Ebenendarstellungen)
- Draw Buffer (ein 1-Bit „already drawn“ Flag Buffer)
- Span-basiertes Drawing
- Portale
Potenziell sichtbare Sets.
Die endgültige Lösung, die John Cormack fand, war ein vorberechneter Lookup, der für jedes Blatt des BSP eine Liste der potenziell sichtbaren Blätter (PVS) lieferte. Dies wiederum erfordert, dass die Welt statisch ist und die Blickrichtung nicht berücksichtigt wird (ein häufiges Missverständnis auch bei BSP-Bäumen). Ein Roh-PVS ist ziemlich groß, aber die RLE-Kompression und Modifikationen am BSP-Builder haben die Größe auf 20K reduziert. Die von Cormack genannten Modifikationen sind:
- Änderung der Splitauswahl durch Heuristik,
- Sealing der Map.
Sealing bedeutet hier, einen Teil des Rumpfes der World zu berechnen, um Oberflächen zu bestimmen, die von überall auf der Welt nicht sichtbar sind und diese zu entfernen. Die Idee des Renderings im Quake-Stil befindet sich in einer dicht besiedelten Welt und ein Sealing-Prozess macht vollkommen Sinn. Es bezieht sich auf die von QuakeEd verwendete pinselbasierte CSG-Modellierung. Seth Teller erwähnt einen Vorverarbeitungsschritt, um kleine Lücken und andere Leckagen durch Polygone zu identifizieren, die nicht perfekt aneinandergrenzen, Fehler abzubilden, die die PVS-Größe immens erhöhen.
Die BSP-Heuristik sollte geändert werden, um weniger Blätter zu erzeugen, vorzugsweise die Polygone, die die wenigsten anderen Polygone aufteilen. Dies wird zu weniger ausgewogenen Bäumen führen, was in diesem Fall kein großer Nachteil ist, wenn ich mich recht erinnere.
Wir hoffen, dass wir Ihnen einen ersten kleinen Überblick über die Thematik bieten konnten. Wenn Sie noch Fragen oder Anregungen haben sollten, hinterlassen Sie uns unten einen Kommentar.
Vielen Dank für Ihren Besuch.
Leave A Comment