In der 3D-Computergrafik ist die Oberflächenbestimmung (auch bekannt als Hidden Surface Removal (HSR), Occlusion Culling (OC) oder Visible Surface Determination (VSD)) das Verfahren, mit dem bestimmt wird, welche Oberflächen und Teile von Oberflächen aus einem bestimmten Blickwinkel nicht sichtbar sind. Ein Hidden Surface Determination Algorithmus ist eine Lösung für das Sichtbarkeitsprobelm, das eines der ersten großen Probleme im Bereich der 3D-Computergrafik war.

Der Prozess der Bestimmung von versteckten Oberflächen wird manchmal als Hiding (verstecken) bezeichnet. Das Analogon für das Linien-Rendering ist die Entfernung von verdeckten Linien.

Die Bestimmung der versteckten Oberfläche ist notwendig, um ein Bild korrekt darzustellen, so dass man keine hinter dem Modell selbst versteckten Merkmale sehen kann, so dass nur der natürlich sichtbare Teil der Grafik sichtbar ist.

Hidden Surface Determination

Hintergrund.

Hidden Surface Determination ist ein Verfahren, bei dem Oberflächen, die für den Anwender nicht sichtbar sein sollen (z.B. weil sie hinter undurchsichtigen Objekten wie Wänden liegen), an der Darstellung gehindert werden. Trotz der Fortschritte bei der Hardwarefähigkeit besteht nach wie vor Bedarf an fortschrittlichen Rendering-Algorithmen. Die Verantwortung einer Rendering-Engine liegt darin, große World Spaces zu ermöglichen, und wenn sich die Größe der Welt der Unendlichkeit nähert, sollte die Engine nicht langsamer werden, sondern bei konstanter Geschwindigkeit bleiben. Die Optimierung dieses Prozesses setzt voraus, dass möglichst wenig Ressourcen für die Darstellung von Oberflächen eingesetzt werden können, die dem Benutzer nicht angezeigt werden.

Es gibt viele Hidden Surface Determination-Techniken. Sie sind grundsätzlich eine Übung in der Sortierung und unterscheiden sich in der Regel in der Reihenfolge, in der die Sortierung durchgeführt wird und wie das Problem unterteilt ist. Das Sortieren großer Mengen von Grafik-Primitiven erfolgt in der Regel durch Teilen und Erobern.

Algortihmen.

Unter Berücksichtigung der Rendering-Pipeline werden die Projektion, das Clipping und die Rasterisierungsschritte durch die folgenden Algorithmen unterschiedlich behandelt:

Z-Buffering.

Während der Rasterung wird die Tiefe/Z-Wert jedes Pixels (oder Stichprobe im Falle von Anti-Aliasing, aber ohne Verlust der Allgemeinheit wird der Begriff Pixel verwendet) gegen einen vorhandenen Tiefenwert geprüft. Wenn das aktuelle Pixel hinter dem Pixel im Z-Buffer liegt, wird das Pixel abgelehnt, andernfalls wird es schattiert und sein Tiefenwert ersetzt den im B-Puffer. Z-Buffering unterstützt dynamische Szenen auf einfache Weise und wird derzeit effizient in Grafikhardware implementiert. Dies ist die aktuelle Norm. Die Kosten für die Verwendung von Z-Buffering bestehen darin, dass es bis zu 4 Bytes pro Pixel verwendet, und dass der Rasterungsalgorithmus jedes gerasterte Sample gegen den Z-Buffer prüfen muss. Der Z-Buffer kann aufgrund von Präzisionsfehlern auch unter Artefakten leiden (auch bekannt als Z-Fighting).

Coverage Buffer (C-Buffer) und Surface Buffer (S-Buffer).

Diese sind schneller als Z-Buffer und werden häufig in Spielen der Quake I-Ära verwendet. Anstatt den Z-Wert pro Pixel zu speichern, speichern sie eine Liste der bereits angezeigten Segmente pro Zeile des Bildschirms. Neue Polygone werden dann gegen bereits angezeigte Segmente geschnitten, die sie ausblenden würden. Ein S-Buffer kann unsortierte Polygone anzeigen, während ein C-Buffer erfordert, dass Polygone von unten nach oben angezeigt werden. Da bei der C-Buffer-Technik ein Pixel nicht mehr als einmal gezeichnet werden muss, ist der Prozess etwas schneller. Dies wurde häufig bei BSP-Bäumen (Binary Space Partitioning) verwendet, die eine Sortierung der Polygone ermöglichen würden.

Sorted active edge list.

In Quake 1 verwendet, war dies das Speichern einer Liste der Kanten von bereits angezeigten Polygonen (siehe Scanline-Rendering). Polygone werden von der nächstgelegenen bis zu entferntesten Stelle angezeigt. Neue Polygone werden an den Kanten der bereits angezeigten Polygone abgeschnitten, wodurch neue Polygone erstellt werden, die dann angezeigt und die zusätzlichen Kanten gespeichert werden. Es ist viel schwieriger zu implementieren als S/C/Z-Buffer, aber es skaliert viel besser mit zunehmender Auflösung.

Painter`s Algorithmus.

Sortiert Polygone nach ihrem Schwerpunkt und zieht sie nach vorne. Dies führt zu wenigen Artefakten, wenn man sie auf Szenen mit Polygonen ähnlicher Größe angewendet, die glatte Maschen bilden und die Rückseitenauslese eingeschaltet ist. Die Kosten sind hier der Sortierschritt und die Tatsache, dass visuelle Artefakte auftreten können. Dieser Algorithmus ist für allgemeine Szenen vom Design her gebrochen, da er Polygone in verschiedenen gängigen Konfigurationen nicht verarbeiten kann.

Binary space partitioning (BSP).

Teilt eine Szene entlang von Ebenen, die den Polygongrenzen entsprechen. Die Unterteilung ist so konstruiert, dass eine eindeutige Tiefenordnung von jedem Punkt der Szene aus, wenn der BSP-Baum durchlaufen wird, gewährleistet ist. Der Nachteil dabei ist, dass der BSP-Baum mit einem teuren Vorprozess erstellt wird. Das bedeutet, dass die Daten vorsortiert und fehlerfrei sind, bereit für die zuvor genannten Algorithmen. Beachten Sie, dass das BSP keine Lösung für HSR ist, sondern nur ein Hilfsmittel.

Ray tracing.

Versucht, den Weg der Lichtstrahlen zu einem Standpunkt zu modellieren, indem er die Stahlen vom Standpunkt aus in die Szene verfolgt. Obwohl es sich nicht um einen Algorithmus zur Entfernung von versteckten Oberflächen als solchen handelt, löst er implizit das Problem der Entfernung von versteckten Oberflächen, indem er bei jedem Blickstrahl die nächstgelegene Oberfläche findet. Dies entspricht effektiv der Sortierung der gesamten Geometrie auf Pixelbasis.

Der Warnock Algorithmus.

Unterteilt den Bildschirm in kleinere Bereiche und sortiert Dreiecke innerhalb dieser. Bei Mehrdeutigkeit (d.h. Polygone überlappen sich in diesen Bereichen in der Tiefe) kommt es zu einer weiteren Unterteilung. An der Grenze kann eine Unterteilung bis auf Pixelebene erfolgen.

Culling und Visible Surface Determination.

Ein verwandter Bereich zur Bestimmung der sichtbaren Oberfläche (VSD) ist das Culling, was normalerweise vor VSD in einer Rendering-Pipeline geschieht. Primitive oder Chargen von Primitiven können vollständig abgelehnt werden, was in der Regel die Belastung eines gut durchdachten Sytems reduziert.

Der Vorteil der frühzeitigen Aussortierung besteht darin, dass ganze, unsichtbare Objekte nicht geholt, transformiert, gerastert oder schattiert werden müssen. Hier sind einige Arten con Culling Algorithmen:

Viewing Frustum Culling.

Das Viewing Frustum ist eine geometrische Darstellung des für die virtuelle Kamera sichtbaren Volumens. Natürlich sind Objekte außerhalb dieses Volumens im endgültigen Bild nicht sichtbar, so dass sie verworfen werden. Oftmals liegen Objekte an der Grenze des Blickwinkels. Diese Objekte werden in einem Prozess, der als Clipping bezeichnet wird, entlang dieser Grenze in Stücke geschnitten, und die Stücke, die außerhalb des Sturzes liegen, werden verworfen, da es keinen Platz zum Zeichnen gibt.

Back-face Culling.

Bei 3D-Objekten zeigt ein Teil der Objektoberfläche zur Kamera, der rest ist von der Kamera weg gerichtet, d.h. auf der Rückseite des Objekts, behindert durch die Vorderseite. Wenn das Objekt völlig undurchsichtig ist, müssen diese Oberflächen nicht gezeichnet werden. Sie werden durch die Reihenfolge der Scheitelwindung bestimmt: Wenn das gezeichnete Dreieck seine Scheitelpunkte auf der Projektionsebene vor der Kamera im Uhrzeigersinn hat, wechseln sie in die Reihenfolge gegen den Uhrzeigersinn, wenn sich die Oberfläche von der Kamera abwendet.

Übrigens macht dies die Objekte auch dann völlig transparent, wenn sich die Blickwinkelkamera in ihnen befindet, denn dann sind alle Oberflächen des Objekts von der Kamera weggerichtet und werden vom Renderer ausgewählt. Um dies zu verhindern, muss das Objekt doppelseitig eingstellt sein (d.h. es wird kein Backface Culling durchgeführt) oder separate Innenflächen aufweisen.

Contribution Culling.

Oftmals sie die Objekte so weit weg, dass sie keinen wesentlichen Beitrag zum Endbild leisten. Diese Objekte werden weggeworfen, wenn ihre Projektion zu klein ist.

Occlusion Culling.

Objekte, die sich vollständig hinter anderen undurchsichtigen Objekten befinden, können ausgewählt werden. Dies ist ein sehr beliebter Mechanismus, um die Darstellung großer Szenen mit einer mittleren bis hohen Komplexität zu beschleunigen. Es gibt mehrere verschiedene Occlusion Culling Ansätze:

  • Das Rendering des potenziell sichtbaren Satzes (PVS) teilt eine Szene in Regionen ein und stellt die Sichtbarkeit für sie vor. Diese Sichtbarkeitssätze werden dann zur Laufzeit indiziert, um schnell qualitativ hochwertige Sichtbarkeitssätze (unter Berücksichtigung komplexer Okkluderinteraktionen) zu erhalten.
  • Das Portal-Rendering unterteilt eine Szene in Zellen/Sektoren (Räume) und Portale (Türen) und berechnet, welche Sektoren sichtbar sind, indem es sie gegen Portale kürzt.

Teilen und Erobern.

Ein beliebtes Thema in der VSD-Literatur ist Teilen und Erobern. Der Warnock Algorithmus war der erste Schritt zur Aufteilung des Bildschirms. Beam Tracing ist ein Ray-Tracing-Ansatz, der die sichtbaren Volumen in Strahlen unterteilt. Verschiedene Ansätze zur Unterteilung des Bildschirmraums reduzieren die Anzahl der berücksichtigten Primitiven pro Region, z.B. Tiling oder Screen-Space-BSP-Clipping. Tiling kann als Vorstufe zu anderen Techniken verwendet werden. Die Hardware des Z-Buffers kann typischerweise ein grobes „hi-Z“ beinhalten, gegen das Primitive ohne Rasterung frühzeitig abgelehnt werden können, dies ist eine Form des Occlusion Cullings.

Bounding Volume Hierarchies (BVHs) werden häufig verwendet, um den Raum der Szene zu unterteilen (Beispiele sind der BSP-Baum, der Octree und der kd-tree). Dadurch kann die Sichtbarkeitsbestimmung hierarchisch durchgeführt werden: Wenn ein Node im Baum als unsichtbar betrachtet wird, sind alle seine Unter-Nodes ebenfalls unsichtbar, und es ist keine weitere Verarbeitung erforderlich (sie können alle vom Renderer abgelehnt werden). Wenn ein Node als sichtbar angesehen wird, muss jeder seiner Childs ausgewertet werden. Diese Durchquerung ist praktisch eine Baumwanderung, bei dem Unsichtbarkeit/Verschluss oder das Erreichen eines Blattnodes bestimmt, ob man anhalten oder wiederkehren soll.

Vielen Dank für ihren Besuch.