7.3.4 Implementation des Tiefensortieralgorithmus

 

Von den verschiedenen bekannten Verfahren zur Bestimmung der Sichtbarkeit wurde der sogenannte Tiefensortieralgorithmus (depth sort) gewählt [15]. Einer seiner entscheidenden Vorteile liegt darin, daß er keinen Bildraster voraussetzt und sich daher für Weiterverarbeitung des Bildes in voller Qualität eignet. Das mehrfache Überschreiben von Bildinformation stellt für die erwarteten Ausgabemedien kein Problem dar.

Gegenüber einer allgemeinen Geometrie wurden folgende vereinfachende Annahmen getroffen:

1. Die Geometrie ist Waferstate-konform, hat also keine einander schneidenden Flächen und Linien.
2. Der Fall einander zyklisch überdeckender Flächen wird bei den zu erwartenden Bauelementen als so unwahrscheinlich angesehen, daß er nicht durch spezielle Behandlung gelöst wird.

Um dem Anwender Unterstützung beim Editieren der Geometrie zu geben, wurde die Möglichkeit eingebaut, außer Flächen auch einzelne Punkte und Linien bei der Sortierung mitzuführen.

Im allgemeinen Fall soll eine Geometrie dargestellt werden, die durch eine Liste von Segmenten, Grenzen, Volumina, Flächen, Linien und Punkten definiert ist. Um die Farben sinnvoll zu wählen, werden zunächst die Segmente nach dem aktuellen Modus, z.B. gemäß Material, gefärbt. Diese Farben werden auf die zugrundeliegenden Volumina übertragen, und von diesen auf die Flächen.

Zwei Optimierungen sollen den Datenumfang vor der zeitkritischen Sortierung reduzieren:

1. Aufgrund der Annahme (1) sind Flächen, die zu zwei Volumina gehören, nicht sichtbar, da sie beidseitig verdeckt sind. Solche Flächen werden entfernt.
2. Aufgrund der Annahme (1) liegen Flächen, die von ihrem Volumen ,,nach hinten`` orientiert sind, tatsächlich auf der Rückseite. Auch diese werden entfernt.

Mit der auf CLS-Objekte vom Typ Flächen, Linien und Punkte reduzierten Liste wird die Tiefensortierung ausgeführt. Zunächst werden alle Objekte in ein spezielles Datenformat kopiert, wobei gleichzeitig die Koordinatentupel in das Bildsystem (Bildebene h, v; Distanz d) transformiert werden (s. Abschnitt 7.6.2). Dieses Datenformat enthält für die Sortierung wichtige Angaben wie die minimalen und maximalen Koordinatenwerte und den Normalvektor.

Dann werden alle Objekte nach ihrem entferntesten (niedrigsten) d-Wert sortiert, um eine möglichst gute Annäherung zu erhalten.

Nun wird der eigentliche Tiefensortieralgorithmus angewendet. Das ,,letzte`` Objekt wird mit allen davor angeordneten verglichen, soweit eine Überlappung in d-Richtung möglich ist (um darüber die Kontrolle zu haben, wird parallel zur Liste der Objekte eine Liste geführt, die für jedes Objekt den minimalen d-Werte dieses und aller davor angeordneten Objekte angibt). Jeder Vergleich liefert eines der drei folgenden Resultate:

1. Die Reihenfolge der beiden Elemente ist egal.
2. Die Reihenfolge der beiden Elemente ist richtig.
3. Die Reihenfolge der beiden Elemente ist verkehrt.

Die Erkenntnis, daß die Reihenfolge falsch ist, erzwingt eine Umsortierung und führt mit hoher Wahrscheinlichkeit zur Wiederholung früherer Vergleiche. Daher wird der erste Fall gleich wie ,,richtig`` behandelt. Die Antwort reduziert sich damit auf ,,verkehrt`` oder ,,nicht verkehrt``.

Im folgenden werden die Adjektiva ,,vordere`` und ,,hintere`` für die aktuelle Reihenfolge in der Liste verwendet, während ,,untere`` und ,,obere`` sichtmäßige Abhängigkeit bedeuten.

Bei jedem Vergleich werden die Tests hintereinander ausgeführt, bis ein Ergebnis vorliegt. Einfache, schnelle Tests werden zuerst ausgeführt, aufwendige später.

1. Wenn die Objekte einander in d-Richtung nicht überlappen, dann ist ihre Reihenfolge richtig (unter Annahme (2)).
2. Wenn die Objekte einander in h- oder v-Richtung nicht überlappen, dann ist ihre Reihenfolge egal.
3. Wenn alle Eckpunkte der hinteren Fläche unter der Ebene der vorderen Fläche liegen, dann ist die Reihenfolge richtig. Es wird nicht der Umkehrschluß gezogen, daß, wenn alle Punkte der hinteren Fläche über der vorderen Ebene liegen, die Reihenfolge verkehrt ist - die könnte immer noch egal sein, s. oben!
4. Wenn alle Eckpunkte der vorderen Fläche über der Ebene der hinteren Fläche liegen, dann ist die Reihenfolge richtig oder egal.
5. Wenn die Flächen einander nicht überlappen, ist die Reihenfolge egal. Da die vorliegenden Flächen meistens Drei- oder Vierecke sind, wurden einfache Algorithmen mit Aufwand ( ...Anzahl der Eckpunkte von Fläche i) für diesen Test implementiert: Wenn keine der beiden Flächen einen Punkt der anderen enthält und keine Begrenzungslinien einander schneiden, dann überlappen die Flächen einander nicht.
6. Die Flächen überlappen einander, und ihre Ebenen schneiden die jeweils andere Fläche. Aus Annahme (2) folgt, daß es trotzdem eine eindeutige Reihenfolge gibt. Diese wird aus den d-Koordinaten der ersten gefundenen Überlappung geschlossen, und entsprechend wird das Ergebnis ,,richtig`` oder ,,falsch`` geliefert.

Für Vergleiche Fläche-Linie und Fläche-Punkt sind entsprechende Tests implementiert, die im Detail natürlich etwas einfacher sind. Die Reihenfolge von Linien und Punkten untereinander wird immer als egal, also nicht falsch, angenommen.

Falls die Daten die Annahme (2) nicht erfüllen, kommt der Algorithmus in eine Endlosschleife, da zwei oder mehr Objekte ständig gegeneinander vertauscht werden. Dies wird daran erkannt, daß für n Objekte mehr als Vergleiche stattfinden. Bei Auftreten dieser Bedingung wird die Sortierung abgebrochen.

Wenn die Sortierung erfolgreich abgeschlossen wurde, werden die Objekte in der vorliegenden Reihenfolge ausgegeben, wobei die späteren (oberen) die früheren (unteren) übermalen (s. Abb. 7.1).

  
Abbildung 7.1: Einfache dreidimensionale Struktur, dargestellt mit dem PIF-Editor