5.3.5 Der Octree

  
Abbildung 5.7: Die Diskretisierung mittels eines Octrees basiert auf der rekursiven Zerlegung des Simulationsgebietes mit Würfeln. Intern wird eine Baumstruktur zur Repräsentation der Geometriedaten aufgebaut.

  
Abbildung 5.8: Bei der Zerlegung mittels eines Quadtrees werden Geometrien durch Quadrate aufgelöst.

  
Abbildung 5.9: Trench, der durch einen anisotropen Ätzschritt mit einem Topographiesimulator [Str93a] auf einer zellulären Strukturrepräsentation basierend erzeugt wurde.

  
Abbildung: Diskretisierung der Struktur von Abb. 5.9 mittels eines Octrees. Die Diskretisierung ist in diesem Fall exakt, weil von einer zellulären Struktur ausgegangen wird.

Da die in den Abschnitten 5.3.1 - 5.3.4 angeführten Methoden allesamt zu aufwendig sind wurde in dieser Arbeit ein sogenannter Octree für die Strukturrepräsentation verwendet. Diese Methode kommt aus der Bildverarbeitung (siehe z.B. [Män88], [Abr91], [Fel92]), wobei dort allerdings meist der umgekehrte Vorgang, nämlich das Zusammenfassen von Gebieten gleicher Eigenschaften anstatt dem Zerlegen eines großen Gebietes verlangt ist. Diese Technik kann allerdings an die Anforderungen der Ionen-Implantation angepaßt werden, wo ein großes Gebiet in kleinere, einfachere Teilgebiete unterteilt wird. Diese Teilgebiete sollen aber jedenfalls möglichst groß sein, um die Anzahl der entstehenden Elemente zu minimieren.

Bei der Verwendung eines Octrees wird das Simulationsgebiet mittels Würfeln diskretisiert. Dies geschieht folgendermaßen: Zuerst wird die gesamte Geometrie von einem Würfel (dem Urwürfel) umschrieben. Dieser Würfel wird dann in acht Subwürfel unterteilt, wenn eine Grenzfläche der Geometrie in dem Urwürfel liegt. Dieses Verfahren wird rekursiv weiter für jeden Subwürfel fortgesetzt, bis entweder keine Grenzfläche der Geometrie mehr in dem jeweiligen, aktuell behandelten Würfel liegt oder bis eine vorgegebene minimale Seitenlänge eines Würfels erreicht ist. Für jeden Endwürfel wird dann noch das Material, das er enthält, bestimmt; jeder dieser Würfel enthält nur ein Material.

In Abb. 5.8 wird ein Dreieck mittels eines ,,Quadtrees`` - das ist die zweidimensionale Vereinfachung des Octrees - diskretisiert. Damit soll das Konzept des Octrees verdeutlicht werden. Das Modell eines Octrees ist in Abb. 5.7 dargestellt. Programmintern wird für die Datenrepräsentation eine Baumstruktur verwendet. Jeder Würfel, der noch weiter unterteilt werden muß ist in diesem Baum als Knoten repräsentiert, Endwürfel als Blätter. Die Repräsentation in Form eines Baumes hat sowohl eine effiziente Abspeicherung als auch einen einfachen Aufbau zur Folge. Der Zugriff auf die Geometriedaten wird dadurch optimiert.

Ist der Octree einmal aufgebaut, dann können während der Simulation der Ionentrajektorien - das heißt, eigentlich bei der Kopie einer Trajektorie - einfache Vergleiche verwendet werden anstatt von komplizierten und numerisch viel sensitiveren Berechnungen von Schnitten. Um nun den Aufenthaltsort eines Ions zu bestimmen, wird ganz einfach getestet, ob die Koordinaten des Ions innerhalb der Seiten des Würfels liegen, weil der Würfel an das Koordinatensystem angebunden ist. Dies führt zu einer drastischen Verringerung in der Rechenzeit im Vergleich zu anderen Methoden. Für die in den vorigen Abschnitten beschriebenen Methoden wächst der Zeitaufwand zumindest quadratisch bei einem Ausbau auf drei Dimensionen. Bei der Schnittpunktmethode nach Abschnitt 5.3.1 müssen zuerst einmal Ebenen auf Schnittpunkte untersucht werden, wenn das Segment von Flächen begrenzt wird. Für jede Fläche müssen dann noch zweidimensionale Schnitte berechnet werden (unter der Voraussetzung, daß die Fläche Begrenzungslinien besitzt). Das führt zu insgesamt zweidimensionalen Schnitten - - zusätzlich zu den dreidimensionalen Schnittberechnungen.

Neben der Reduktion der Rechenzeit vereinfacht die Verwendung des Octrees auch die Kopplung des Moduls zur Simulation der Ionen-Implantation mit dreidimensionalen Topographiesimulatoren (das sind Simulatoren zur Simulation von Ätz- oder Depositionsverfahren), die auf zellulären Strukturen basieren, wie etwa in [Str93b] beschrieben. Solche Programme produzieren nämlich als Ausgabe schon eine mittels Würfeln diskretisierte Geometrie. Diese meistens sehr kleinen Würfel müssen nur zu möglichst großen Würfeln zusammengefaßt werden. Die Diskretisierung kann übernommen werden. In Abb. 5.9 ist ein Trench aus einer solchen Simulation abgebildet. In diesem Beispiel wurde die Geometrie ursprünglich in 256256256 gleich große Würfel unterteilt. Abb. 5.10 zeigt die Diskretisierung dieser Struktur mittels eines Octrees. Dafür waren 8667 Knoten und 60670 Blätter notwendig. Für diese Diskretisierung wurde auf einem HP 9000/735 Arbeitsplatzrechner weniger als eine Sekunde CPU-Zeit benötigt.

Bei der Octree Methode wird die Geometrie diskretisiert, bevor die eigentliche Simulation durchgeführt wird. Die Geometrieabfragen werden nun einfacher, weil sie nur mehr auf die Würfel des Octrees bezogen werden müssen. Diese Methode kann auch so gesehen werden, daß sozusagen alle möglichen Schnitte nur einmal - nämlich bei der Initialisierung - berechnet werden, anstatt bei jeder Kollision. Darüber hinaus ist die Bestimmung des Minimalabstands des Ions von den Seiten des Würfels sehr einfach; bei Verwendung einer anderen der in den Abschnitten 5.3.1 - 5.3.4 beschriebenen Methoden wären wieder aufwendige Schnittpunktberechnungen für die Bestimmung dieses Abstands notwendig. Nun ist aber diese Länge der minimale Weg, den das Ion noch im selben Material - also ohne Wechsel in ein anderes Gebiet - mindestens zurücklegt. Es ist daher möglich, einige Geometrieabfragen zu überspringen, wenn diese minimale Länge größer als die maximale freie Weglänge ist. Das führt zu einer zusätzlichen Beschleunigung in der Berechnung.