Referat Sichtbarkeitsalgorithmen im Zusammenhang mit CAD

Sichtbarkeitsalgorithmen im Zusammenhang mit CAD

Bei der Darstellung von computergenerierten dreidimensionalen Bildern gibt es das Problem, dass der Computer von sich aus nicht unterscheiden kann, welche Kanten und Flächen in der realen Welt sichtbar wären und welche nicht. Für den Computer ist es auch kein Problem alle Flächen darzustellen, nur kann der Mensch die Objekte dann nicht mehr erkennen. Deshalb wurden Algorithmen entwickelt, mit denen der Computer berechnen kann welche Teile eines Bildes sichtbar sind und welche nicht. Es gibt viele verschiedene Lösungsansätze für das Hidden - Line und Hidden- Surface Problem, ich stelle von ein paar Ansätzen die Lösungen vor, die mir am besten gefallen haben.

Bevor noch Sichtbare Kanten und Flächen ermittelt werden, wird geprüft ob sich das Objekt(die Objekte) überhaupt innerhalb des sichtbaren Bereichs liegen, um nicht unnötig Rechnerleistung verschwenden zu müssen. Dazu gibt es zuerst einmal zwei grobe Methoden.

1: Min- Max Test(??Wieso max Test??)

Wenn der minimale Abstand des Objekts zur Bildebene größer ist, als der Abstand des Augpunktes zur Bildebene, kann sich das Objekt nicht innerhalb der Viewing Box befinden. Die Viewing Box ist der Bereich vom Augpunkt bis zur Bildebene, alles was sich in der Viewing Box befindet ist potentiell sichtbar.

2: Bounding Box Test:

Um komplizierte Objekte wird ein Quader oder eine Kugel(Soap- Bubble- Test) umschrieben, und dann getestet, ob sich dieses vereinfachte Objekt innerhalb der Viewing Box befindet.

3: Im Buch wird von Feintests gesprochen, bei denen die einzelnen Punkte mit der Viewing Box verglichen werden, wenn die beiden ersten zwei Tests erfolglos waren, ich habe aber keinen Fall gefunden, wie ein Objekt liegen könnte, um bei den ersten zwei Tests durchfallen zu können und trotzdem sichtbar sein kann.

Wenn das Objekt innerhalb der Viewing Box liegt, aber sehr komplex ist, wird berechnet wo das Objekt die Viewing Box verlässt. Dort werden die Teile die sich außerhalb der Box befinden abgeschnitten, das nennt man dreidimensionales- Clipping.

Sichtbarkeitsalgorithmen

Nachdem das Programm die potentiell sichtbaren Objekte ermittelt hat, muss es berechnen welche Flächen und Kanten nun auch wirklich sichtbar sind, und welche auf der Rückseite von Objekten liegen, oder von anderen  Objekten verdeckt werden.

Es gibt viele Methoden um das Problem zu lösen, ich versuche einige Lösungsansätze zu zeigen.

1: Objekt-Raum-Algorithmen

Sie stellen die ersten Lösungsansätze für das Hidden-Line und Hidden-Surface Problem dar. Sie operieren in der Objekt- Welt und versuchen die verschiedenen Elemente der Objekt Welt untereinander zu vergleichen um zu ermitteln welche teile sichtbar sind und welche nicht.

Z.B.: Körper-Kanten-Vergleichsalgorithmus:

Bei diesem Algorithmus ermittelt das Programm zuerst alle Rückflächen, entfernt dann alle Rückkanten, und löscht danach alle noch vorhandenen aber nicht sichtbaren Kanten und Kantenteile.

Rückflächenerkennung:

Angenommen wird ein Polyeder P , von dem die Normalvektoren der Flächen alle nach außen gerichtet sind, und, dass sich der Augpunkt nicht innerhalb des Polyeders befindet. Wenn das skalare Produkt eines Normalvektors einer Fläche mit dem Projektionsvektor eine negative Zahl ergibt, handelt es sich um eine Rückfläche. (??Ich verstehe die weitere Überlegung nicht wieso nz>0 sein muss??)

Rückkantenentfernung:

Nachdem man die Rückflächen kennt, kann man die Kanten in folgende Kategorien einteilen:

Schnittkanten von zwei Frontflächen

Schnittkanten zwischen einer Front- und einer Rückenfläche

Schnittkanten von zwei Rückflächen

Die beiden ersten Fälle sind sichtbar; wenn sich zwei Rückflächen schneiden, muss die kante entfernt werden.

Entfernung von verdeckten Kanten und Kantenstücken.

Jetzt muss nur noch überprüft werden, ob sich verschiedene Objekte gegenseitig verdecken. Zuerst wird geprüft welches Objekt welches verdeckt. Danach muss jede Kante des Verdeckten Objekts mit dem Clipobjekt(verdeckendes Objekt) verglichen werden. (siehe Zeichnung)

2. Bild-Raum-Algorithmen

Sie waren ein komplett neuer Lösungsansatz für das Sichtbarkeitsproblem. Die Algorithmen kümmern sich nicht um die Lage der Objekte in der Objekt-Welt, sondern bloß um die richtige Darstellung in der Bildebene.

Z.B.:

Rekursiver Bild-Raum-Teilungsalgorithmus

Wenn man sich einen beliebigen Bildausschnitt ansieht, gibt es 3 Möglichkeiten wie er aussehen kann.

1: der Bildausschnitt ist leer

2: alles wird durch ein Polygon verdeckt

3: im Bildausschnitt befindet sich mindestens eine Kante

Bei Fall 1 und 2 ist für den Computer klar, wie der Bereich darzustellen ist. Nur der fall3 muss näher betrachtet werden. Jetzt kommt das geniale. Der Algorithmus kümmert sich nicht, wie die Kanten liegen, er teilt den Bildausschnitt in kleinere Teile, die dann wieder nach den drei Kriterien untersucht werden. Dieser Algorithmus wird solange wiederholt, bis entweder Fall 3 nicht mehr eintritt, oder bis der Bereich zu klein wird um ihn darzustellen. (1Pixel) Dann wird der Pixel mit der Farbe eingefärbt, das am nächsten liegt.

Dieser Algorithmus hat sich, obwohl bereits 1969 entwickelt, erst später durchgesetzt, was mit den niedrigen Auflösungen der alten Bildschirme zu tun hatte. Normalerweise wird der Bildausschnitt bei jedem Arbeitsgang geviertelt, man kann den Algorithmus aber effizienter machen, wenn man die Ausschnitte nicht willkürlich teilt, sondern die Abtrennungen intelligent setzt.

Un-intelligent              intelligent

Z.B.: Z-Buffer Algorithmus

Der Algorithmus erzeugt lauter Zellen, welche die Größe eines Pixels haben, dann wird jeweils die vorderste Fläche gesucht die in in einer Zelle Z abgebildet wird. Die Idee zu diesem Algorithmus stammt aus 1975, und basiert darauf, den Bildspeicher eines Rasterzeilenbildschirm zu erweitern. Er sollte zusätzlich zur Farbinformation, die Nummer der Sichtbaren Fläche und die Distanz des Bildes zum Augpunkt gespeichert werden. Diese Speichererweiterung heißt Z-Buffer.

Der Algorithmus berechnet zuerst das Abbild jedes Polygons der Szene, und wenn das Bild nicht projizierend, und somit eine gerade ist, wird für jedes Pixel der Abstand zum Augpunkt ermittelt, und in den z Buffer gespeichert. Danach wird von jeder Pixelzeile die das Polygon enthält, der Anfangs und Endpunkt ermittelt. (Es reichen die Z werte der Punkte, deshalb Z-Buffer) Kennt man die beiden Punkte, kann man leicht alle Z Werte (so wie ich das verstehe ist der z wert nicht die Höhe sondern der Abstand zu Augpunkt) der Pixelzeile ausrechnen. Ist einer der Z werte größer al der Bisherige Eintrag im Z Buffer wird der Z Buffer neu gesetzt, das Pixel mit der Farbe des Polygons ausgefüllt, und Fortgefahren.

3. Gemischte Algorithmen

Gemischte Algorithmen arbeiten nicht nur in einer "Umgebung" (Bild-Raum oder Objekt-Welt), sie Übertragen Prinzipien die für eine Umgebung erdacht wurden in eine andere.

Z.B.: Objekt-Raum-Rasterzeilenalgorithmus

Dieser Algorithmus arbeitet mit einer Rasterzeilen, im Unterschied zum z-Buffer Algorithmus aber nicht mit denen des Bildschirms sondern mit einer Ebene im Objekt-Raum.

Dann erstellt der Algorithmus zwei Listen.

In der ersten werden alle Kanten gespeichert die sich zwischen zwei Rasterzeilen befinden, und in der zweiten (Ereignisliste) wird unterschieden nach: Schnittpunkt von zwei Kanten im Punkt P, Eckpunkt P und Tiefster Punkt eines Objektes P.

Da sich die Sichtbarkeit nur in einem der Ereignispunkte ändern kann, legt man durch jeden Ereignispunkt eine Rasterzeile. Zwischen den Rasterzeilen kann sich die Sichtbarkeit also nicht mehr ändern. Jetzt arbeitet der Algorithmus alle Rasterzeilen von unten beginnend ab. Alle Punkte bei denen eine kante sichtbar wird oder beginnt, werden gespeichert, endet eine Kante in P so wird die kante bis P gezeichnet. (Ich verstehe zwar grundsätzlich die Überlegung, aber nicht wie er feststellen will wo Kanten sichtbar werden, was ja das Hauptproblem ist.)

4: Prioritätslisten Algorithmen

Prioritätslisten versuchen die Wahrscheinlichkeit mit der ein Objekt sichtbar ist festzustellen. Wenn man so eine Liste mit 100%er Sicherheit erstellen könnte, gäbe es das Sichtbarkeitsproblem nicht mehr, aber leider ist es nicht immer Möglich so eine Liste zu erstellen.

Z.B.:: Maleralgorithmus

Das ist der wohl einfachste aber genialste Algorithmus und wurde 1972 von Newell entwickelt. Die Idee hinter dem Algorithmus basiert auf der Arbeitsweise von Malern eines Ölbildes. Der Algorithmus erstellt eine Prioritätsliste, nach Abständen vom Augpunkt geordnet. Und dann füllt er einfach jedes Polygon, beim Hintersten beginnend mit der richtigen Farbe. Dadurch sind keine weiteren Berechnungen mehr erforderlich, das Sichtbarkeitsproblem löst sich von selbst!

Das einzige Problem ist, das es nicht immer möglich ist eine fehlerfreie Prioritätsliste zu erstellen. z.B.: Polygone die in einer Ebene liegen, und doch unterschiedliche Sichtbarkeit haben.

5: Ray Tracing

Ray Tracing ist die neueste der hier vorgestellten Methoden, und mit ihr kann man noch viel mehr als bloß die Sichtbarkeit zu berechnen. Alle Effekte die wir aus guten Computeranimationen kennen, wie Spiegelungen Lichtbrechungen usw. sind erst durch Ray Tracing ermöglicht worden.

Ray casting: Beim Ray casting wird der Sehstrahl vom Augpunkt zum Objekt zurückverfolgt. Der Rasterzeilenbildschirm wird in den Objekt-Raum verlegt, und ausgehend von Augpunkt, wird durch jedes Pixel des Bildschirms(nicht des realen) ein Sehstrahl gelegt, dar dann mit allen Flächen geschnitten wird, auf die er trifft. Danach wird die Fläche von der der vorderste Schnittpunkt stammt dargestellt.

Ray Tracing: Bein Ray Tracing wird der Schnittpunkt nicht nur dazu benutzt die vorderste Fläche zu berechnen, sondern der Sehstrahl wird weiterverfolgt. Für den Sehstrahl gibt es zwei Möglichkeiten. Entweder wurde er an der Fläche gespiegelt oder er wurde gebrochen, meistens treten aber beide Fälle gemeinsam auf. Und hiermit handelt es sich eigentlich nicht mehr um einen Sehstrahl, sondern um einen Lichtstrahl. Man wollte schon sehr Früh die Lichtstrahlen verfolgen, allerdings hatte man den Fehler gemacht die Strahlen von der Lichtquelle aus zu verfolgen, und nicht vom Auge zurückzuverfolgen. Da aber immer nur ein sehr geringer teil der Lichtstrahlen die dargestellte Szene überhaupt erreichte, waren die Ergebnisse immer sehr ungenau. (der Computer kann ja nicht so viele Lichtstrahlen erzeugen wie in Wirklichkeit; war die Lichtquelle sehr nahe an dem Objekt, waren teile des Objekts nicht beleuchtet, war sie weit weg, trafen nur einige Lichtstrahlen as Objekt, die meisten gingen daneben vorbei.

6: Sichtbarkeitsalgorithmus für Parameterflächen

Darstelung von Parameterflächen:

Parameterflächen werden dazu verwendet 'unförmige', kurvige Flächen darzustellen, oder kantige Objekte zu glätten. Dazu wird ein Netz aus Parameterlinien aufgespannt.

Man kann dieses Netz natürlich aber auch mit einer Fläche überziehen und so die Schatten richtig darstellen.

Deshalb gibt es auch zwei verschiedene Sichtbarkeitsalgorithmen. Einen um die Hidden-Line Algorithmus um die Linien darzustellen und einen Hidden-Surface Algorithmus bei dem die Fläche als ganzes dargestellt wird.

1. Sehstrahlmethode

Mit der Sehstrahlmethode kann man überprüfen, ob ein Punkt P auf der Flächenkurve k sichtbar ist, oder von einer anderen Fläche verdeckt wird. Dazu legt man einen Sehstrahl s vom Augpunkt durch P. Nun muß s mit den vorhandenen Flächen geschnitten werden. Existiert ein Schnittpunkt zwischen P und dem Augpunkt, dann kann man P nicht sehen. Der Agorithmus tut nichts anderes, als den Punkt P auf der Kurve immer weiter zu verschieben, und nach einem bestimmten Interval auf der nöchsten Kuve fortzufahren.

2. Rekursive Flächenteilung

Bei diesem Algorithmus wird die Fläche solange geteilt, bis es lauter Teilflächen gibt, die alle nicht mehr als einen Pixel enthalten dürfen. Dann werden diese Gebiete auf ihre Sichtbarkeit überprüft und der Schattierungsgrad ermittelt (dazu genügt der Normalvektor der Fläche). Dieser Algorithmus beruht auf dem Rekursiven Bild-Raum Teilungsalgorithmus (siehe oben).

3. Horizontmethode

Schneidet man Ebenen, die untereinander und zur z-Achse paralell sind ('Horizontebenen', diese Bezeichnung ist historisch gewachsen allerdings nicht sehr geschickt gewählt) mit dem Funktionsgraphen ab, so erhält man lauter Ebenen die eine kurvige Schnittfläche aufweisen siehe Zeichnung.

Weiter hinten liegende Schnittkurven werden von davorliegenen Ebenen verdeckt. Der Algorithmus beginnt 'vorne', bei der Ebene die am nächsten zum Augpunkt liegt, und zeichnet die ganze Kurve. Von jetzt an darf der Algorithmus aber nur noch die  Kurventeile darstellen die sich oberhalb aller bisherigen Kurven befinden. So kann man den oberen Teil der Parameterfläche darstellen. Für den unteren Teil der Parameterfläche wird genauso vorgegangen, nur wird diesmal der untere Teil der Ebenen 'abgeschnitten'.