Categories: Sonstiges

Wie Sie das Hidden-Surface-Problem in den Griff bekommen.

Wenn wir ein Bild betrachten, das nicht-transparente Objekte und Oberflächen enthält, dann können wir die Objekte nicht sehen, die sich hinter den Objekten befinden, die näher am Auge liegen. Wir müssen diese versteckten Oberflächen entfernen, um ein realistisches Bildschirmbild zu erhalten. Die Identifizierung und Entfernung dieser Objekte wird als Hidden-Surface-Problem bezeichnet.

Es gibt zwei Ansätze zur Beseitigung von versteckten Oberflächenproblemen – Object- und Image-Space Methode. Die Object-Space-Methode ist im physikalischen Koordinatensystem und die Image-Space-Methode im Screen-Koordinatensystem implementiert.

Wenn wir ein 3D-Objekt auf einem 2D-Bildschirm anzeigen möchten, müssen wir die Teile des Bildschirms identifizieren, die von einer gewählten Betrachtungsposition aus sichtbar sind.

Depth-Buffer (Z Buffer) Methode.

Diese Methode wurde von Catmull entwickelt. Es handelt sich um einen Image-Space-Ansatz. Die Grundidee besteht darin, die Z-Tiefe jeder Oberfläche zu testen, um die nächstgelegene (sichtbare) Oberfläche zu bestimmen.

Bei diesem Verfahren wird jede Oberfläche einzeln bearbeitet, jeweils eine Pixelposition über die Oberfläche. Die Tiefenwerte für ein Pixel werden verglichen und die nächstgelegene (kleinste z) Oberfläche bestimmt die Farbe, die im Frame-Puffer angezeigt werden soll.

Es wird sehr effizient auf Oberflächen von Polygonen aufgebracht. Die Oberflächen können in beliebiger Reihenfolge bearbeitet werden. Um die engeren Polygone von den weit entfernten zu überschreiben, werden zwei Puffer mit der Bezeichnung Frame-Puffer und Depth Buffer verwendet.

Der Depth Buffer wird verwendet, um Tiefenwerte für die Position (x, y) zu speichern, wenn Oberflächen bearbeitet werden (0 < Tiefe < 1).

Der Frame-Puffer wird verwendet, um den Intensitätswert des Farbwertes an jeder Position (x, y) zu speichern.

Die Z-Koordinaten werden in der Regel auf den Bereich [0, 1] normiert. Der Wert 0 für die Z-Koordinate zeigt den hinteren Ausschnitt und der Wert 1 für die Z-Koordinate den vorderen Ausschnitt.

Algorithmus.

Stufe 1 – Einstellen der Pufferwerte –

Depth-Buffer (x, y) = 0

Frame-Buffer (x, y) = Hintergrundfarbe

Stufe 2 – jedes Polygon bearbeiten (einem nach dem anderen)

Berechnen Sie für jede projizierte (x, y) Pixelposition eines Polygons die Tiefe z.

Wenn Z > Depthbuffer (x, y)

Berechne die Oberflächenfarbe,

Depth-Buffer einstellen (x, y) = z.

Frame-Buffer (x, y) = Oberflächenfarbe (x, y)

Vorteile.

  • Es ist einfach zu implementieren.
  • Es reduziert das Geschwindigkeitsproblem, wenn es in Hardware implementiert ist.
  • Es verarbeitet jeweils ein Objekt nach dem anderen.

Nachteile.

  • Es benötigt einen großen Speicherplatz.
  • Es ist ein zeitaufwendiger Prozess.

Scan-Line Methode.

Es handelt sich um eine Image-Space-Methode zur Identifizierung der sichtbaren Oberfläche. Diese Methode hat eine Tiefeninformation für nur eine einzelne Scan-Line. Um eine Abtastlinie mit Tiefenwerte zu benötigen, müssen wir alle Polygone, die sich gleichzeitig mit einer bestimmten Abtastlinie schneiden, gruppieren und verarbeiten, bevor wir die nächste Abtastlinie verarbeiten Dazu werden zwei wichtige Tabellen, Edge und Polygon Table, gepflegt.

Edge Table – Sie enthält Koordinaten-Eckpunkte jeder Linie in der Szene, die umgekehrte Steigung jeder Linie und Zeiger in der Polygontabelle, um Kanten mit Oberflächen zu verbinden.

Polygon Table – Sie enthält die Ebenenkoeffizienten, Oberflächenmaterialeigenschaften, andere Oberflächendaten und kann als Zeiger auf die Ecktabelle dienen.

Um die Suche nach Oberflächen zu erleichtern, die eine bestimmte Scan-Linie überschreiten, wird eine aktive Liste von Kanten erstellt. Die aktive Liste speichert nur die Kanten, die die Scan-Linie in der Reihenfolge des Erhöhens von X überqueren. Außerdem wird für jede Oberfläche ein Flag gesetzt, das angibt, ob sich eine Position entlang einer Scan-Line innerhalb oder außerhalb der Oberfläche befindet.

Die Pixelpositionen über jede Scan-Linie hinweg werden von links nach rechts verarbeitet. An der linken Kreuzung mit einer Fläche wird die Oberflächenflagge eingeschaltet und an der rechten Seite die Fahne ausgeschaltet. Sie müssen nur dann Tiefenberechnungen durchführen, wenn mehrere Oberflächen an einer bestimmten Position der Scan-Linie mit ihren Flaggen eingeschaltet sind.

Verfahren zur Flächenunterteilung.

Das Flächenunterteilungsverfahren nutzt die Vorteile, indem es diejenigen Sichtflächen lokalisiert, die Teil einer einzelnen Fläche sind. Teilen Sie den gesamten Sichtbereich in kleinere Rechtecke, bis jeder kleine Bereich die Projektion eines Teils einer einzelnen sichtbaren Fläche oder gar keine Fläche ist.

Setzen Sie diesen Prozess fort, bis die Unterteilungen leicht als zu einer einzigen Oberfläche gehörig analysiert werden können oder bis sie auf die Größe eines einzelnen Pixels reduziert werden. Eine einfache Möglichkeit, dies zu tun, besteht darin, den Bereich bei jedem Schritt nacheinander in vier gleiche Teile aufzuteilen. Es gibt vier mögliche Beziehungen, die eine Oberfläche mit einer bestimmten Bereichsgrenze haben kann.

  • Surrounding Surface – Eine, die den Bereich vollständig umschließt.

  • Overlapping Surface – Eine, die sich teilweise innerhalb und teilweise außerhalb des Bereichs befindet.

  • Inside Surface – Eine, die sich vollständig innerhalb des Bereichs befindet.

  • Outside Surface – Eine, die sich vollständig außerhalb des Bereichs befindet.

Die Tests zur Bestimmung der Oberflächensichtbarkeit innerhalb eines Bereichs können in Bezug auf diese vier Klassifizierungen angegeben werden. Es sind keine weiteren Unterteilungen eines bestimmten Bereichs erforderlich, wenn eine der folgenden Bedingungen erfüllt ist –

  • Alle Oberflächen sind Outside Surfaces bezogen auf die Fläche.

  • Es befindet sich nur eine innere, überlappende oder umgebende Fläche im Bereich.

  • Eine umgebende Oberfläche verdeckt alle anderen Oberflächen innerhalb der Bereichsgrenzen.

Das Erkennen von Rückseiten.

Eine schnelle und einfache Object-Space-Methode zur Identifizierung der Rückseiten eines Polyeders basiert auf den „Inside-Outside“-Tests. Ein Punkt (x, y, z) ist innerhalb einer Polygonfläche mit den Ebenenparametern A, B, C und D, wenn ein Innenpunkt entlang der Sichtlinie zur Oberfläche liegt, das Polygon muss eine Rückfläche sein (wir befinden uns innerhalb dieser Fläche und können die Vorderseite von unserer Betrachtungsposition aus nicht sehen).

Wir können diesen Test vereinfachen, indem wir den Normalvektor N auf eine Polygonfläche betrachten, die kartesische Komponenten (A, B, C) aufweist.

Im Allgemeinen, wenn V ein Vektor in Blickrichtung von der Augenposition aus ist, dann ist dieses Polygon eine Rückfläche, wenn

V.N > 0

Wenn Objektbeschreibungen in Projektionskoordinaten umgewandelt werden und ihre Blickrichtung parallel zur Z-Achse der Betrachtung ist, dann –

V = (0, 0, Vz) und V.N = VZC

So dass wir nur das Vorzeichen von C berücksichtigen müssen, die Komponente des Normalsvektors N.

Bei einem Rechtshänder-Betrachtungssystem mit Blickrichtung entlang der negativen UV-Achse ist das Polygon eine Rückfläche, wenn C < 0 ist und wir können keine Fläche sehen, deren Normalzustand die Z-Komponente C = 0 hat, da ihre Blickrichtung auf dieses Polygon gerichtet ist. So können wir im Allgemeinen jedes Polygon als Rückfläche bezeichnen, wenn sein Normalvektor einen Z-Komponentenwert hat –

C <= 0 Ähnliche Methoden können in Paketen verwendet werden, die ein Linkshänder-Betrachtungssystem verwenden. In diesen Paketen können die Ebenenparameter A, B, C und D aus Polygon-Node-Koordinaten berechnet werden, die im Uhrzeigersinn angegeben werden (im Gegensatz zu der im Rechtshänder-System verwendeten Richtung gegen den Uhrzeigersinn). Außerdem haben Rückseiten normale Vektoren, die von der Betrachtungsposition wegzeigen und mit C >= 0 gekennzeichnet sind, wenn die Blickrichtung entlang der positiven ZV-Achse liegt. Durch die Untersuchung des Parameters C für die verschiedenen Ebenen, die ein Objekt definieren, können wir sofort alle Rückseiten identifizieren.

A-Buffer-Methode.

Die A-Buffer-Methode ist eine Erweiterung der Depthbuffer-Methode. Die A-Buffer-Methode ist eine Sichtbarkeitserkennungsmethode, die in den Lucas Filmstudios für das Rendering-System Rendern Everything You Ever Saw (REYES) entwickelt wurde.

Der A-Puffer erweitert die Depthbuffer-Methode, um Transparenzen zu ermöglichen. Die Schlüsseldatenstruktur im A-Puffer ist der Akkumulationspuffer.

Jede Position im A-Puffer hat zwei Felder –

  • Depth Field – es speichert eine positive oder negative reelle Zahl.
  • Integritätsfeld – es speichert Informationen zur Oberflächenintensität oder einen Zeigerwert.
  • Wenn die Tiefe >= 0 ist, ist die an dieser Stelle gespeicherte Zahl die Tiefe einer einzelnen Oberfläche, die den entsprechenden Pixelbereich überlappt.
  • Das Intensitätsfeld speichert anschließend die RGB-Komponenten der Oberflächenfarbe an diesem Punkt und den Prozentsatz der Pixelabdeckung.

Wenn die Tiefe < 0 ist, zeigt sie mehrflächige Beiträge zur Pixelintensität an. Das Intensitätsfeld speichert dann einen Zeiger auf eine verknüpfte Liste von Oberflächendaten. Der Oberflächenpuffer im A-Puffer beinhaltet –

  • RGB-Intensitätskomponenten
  • Opazitätsparameter
  • Tiefe
  • Prozentsatz der Flächendeckung
  • Oberflächenkennung
  • Der Algorithmus verfährt genau wie der Depthbuffer-Algorithmus. Die Werte für Tiefe und Deckkraft werden verwendet, um die endgültige Farbe eines Pixels zu bestimmen.

Depth Sorting-Methode.

Die Depth Sorting-Methode verwendet sowohl Image Space als auch Object-Space Operationen. Die Depth Sorting-Methode erfüllt zwei Grundfunktionen:

Zuerst werden die Oberflächen in der Reihenfolge der abnehmenden Tiefe sortiert.
Zweitens werden die Oberflächen in der Reihenfolge der Abtastung konvertiert, beginnend mit der Oberfläche mit der größten Tiefe.
Die Scan-Konvertierung der Polygonflächen erfolgt im Image Space. Diese Methode zur Lösung des Problems der verdeckten Oberfläche wird oft als Algorithmus des Painter`s Algorithmus bezeichnet.

Der Algorithmus beginnt mit der Sortierung nach Tiefe. So kann beispielsweise die anfängliche „Tiefenschätzung“ eines Polygons auf dem nächstgelegenen Z-Wert eines beliebigen Eckpunktes des Polygons angesehen werden.

Nehmen wir das Polygon P am Ende der Liste. Berücksichtigen Sie alle Polygone Q, deren Z-Extents sich mit P`s überschneiden. Bevor wir P zeichen, führen wir die folgenden Tests durch. Wenn einer der folgenden Tests positiv ist, können wir davon ausgehen, dass P vor Q gezogen werden kann.

  • Überlappen sich die X-Extents nicht?
  • Überlappen sich die Y-Extents nicht?
  • Befindet sich P aus Sicht des Betrachters ganz auf der gegenüberliegenden Seite der Q-Ebene?
  • Befindet sich Q vollständig auf der gleichen Seite der Ebene von P wie der Ansichtspunkt?
  • Überlappen sich die Projektionen der Polygone nicht?

Wenn alle Tests fehlschlagen, dann teilen wir entweder P oder Q mit der Ebene des anderen. Die neu geschnittenen Polygone werden in die Tiefenreihenfolge eingefügt und der Prozess wird fortgesetzt. Theoretisch könnte diese Partitionierung O (n2) einzelne Polygone erzeugen, aber in der Praxis ist die Anzahl der Polygone viel kleiner.

Binary Space Partition (BSP) Trees.

Binary Space Partitionierung wird zur Berechnung der Sichtbarkeit verwendet. Um die BSP-Trees aufzubauen, sollte man mit Polygonen beginnen und alle Kanten beschriften. Wenn Sie nur eine Kante auf einmal bearbeiten, verlängern Sie jede Kante so, dass sie die Ebene in zwei Teile teilt. Platziere die erste Kante im Baum als Wurzel. Füge weitere Kanten hinzu, je nachdem, ob sie sich innerhalb oder außerhalb befinden. Kanten, die die Verlängerung einer Kante überspannen, die sich bereits im Baum befindet, werden in zwei Teile aufgeteilt und beide dem Baum hinzugefügt.

Wir hoffen, dass wir ihnen eine ersten kleinen Überblick über diese Thematik geben konnten. Falls Sie noch Fragen oder Anregungen haben, dann kontaktieren Sie unsere Fachexperten in unserem Forum.

Vielen Dank für ihren Besuch.

3DMaster