2.1.4 Dreidimensionale Simulation



next up previous contents
Next: 2.2 Der Ray-Trace-Algorithmus Up: 2.1 Der String-Algorithmus Previous: 2.1.3 Erweiterungen

2.1.4 Dreidimensionale Simulation

Im dreidimensionalen Fall stellt sich der bisher eindimensionale String nun als zweidimensionales Oberflächengitter dar, wobei jetzt Dreiecksflächen als Oberflächensegmente verwendet werden. Während der Simulation werden die Punkte des Gitters entlang einer vorausberechneten Richtung bewegt. Das sich daraus ergebende neue Oberflächengitter stellt den Rand der Simulationsgeometrie zum nächsten Zeitschritt dar (Abbildung 2.14). Die Richtung des Bewegungsvektors eines Punktes ergibt sich aus dem arithmetischen Mittel der Normalvektoren der angrenzenden Dreiecksflächen. Der Betrag des Vektors errechnet sich aus der Multiplikation von lokaler Ätzrate und verwendetem Zeitschritt. Das Vorzeichen der Ätzrate entscheidet über Ätzung oder Deposition.

  
Abbildung 2.14: Der String-Algorithmus für die dreidimensionale Simulation.

  
Abbildung 2.15: Ein Dreieckselement des Oberflächengitters.

Ein Dreieckselement des Gitters besteht aus Punkten und Linien (Abbildung 2.15), wobei die Orientierung der Liniensegmente die Richtung des Normalvektors des Dreiecks bestimmen. Ähnlich zum zweidimensionalen Fall ergibt sich auch hier die Forderung nach einem geordneten Oberflächengitter, um eindeutig die Richtung der Punktbewegung bestimmen zu können. Ein geordnetes Gitter besteht aus Dreiecken, deren Punkte jeweils in aufsteigender Reihenfolge angeordnet sind, sodaß sich automatisch die Orientierung der Liniensegmente und damit die Richtung des Normalvektors eines Dreiecks bestimmen läßt.

Durch die Bewegung der Oberfläche entfernen sich einige Punkte voneinander, andere rücken näher zusammen. Aus Speicherplatz- und Rechenzeitgründen ist es erforderlich, zu klein geratene Dreiecke aus dem Gitter zu entfernen. Andererseits müssen zu groß gewordene Dreiecke weiter unterteilt werden, um mit einer bestimmten Dreiecksgröße die aktuelle Geometrie möglichst gut zu approximieren. Methoden für die Gitteradaption wurden von Moniwa et al. [Mon87] und von Toh [Toh90] vorgeschlagen. Ein möglicher Weg ist, von einer idealen Liniensegmentlänge der Dreiecke auszugehen und dazu eine untere und obere Schranke zu definieren. Liniensegmente, deren Länge den unteren Grenzwert unterschreitet, werden aus dem Gitter entfernt, wodurch die zu klein geratenen Dreicke mit ihren benachbarten Dreiecken zu größeren Dreicken zusammengelegt werden. Abbildung 2.16 zeigt das Zusammenlegen von Dreiecken durch das Entfernen von Liniensegmenten aus dem Oberflächengitter.

  
Abbildung 2.16: Das Zusammenlegen von Dreiecken durch das Entfernen von Liniensegmenten aus dem Oberflächengitter; (a) vor dem Entfernen des Liniensegmentes S7, (b) nach dem Entfernen des Liniensegmentes S7.

Liniensegmente, deren Länge den vordefinierten oberen Grenzwert überschreiten, werden durch das Einfügen neuer Punkte entsprechend verkürzt. Zusätzlich werden neue Liniensegmente eingefügt, die den eingesetzten Punkt mit Eckpunkten der angrenzenden Dreiecke verbinden, wodurch neue Dreiecke entstehen, die die zu groß geratenen Dreiecke in kleinere Dreiecke aufteilen. Abbildung 2.17 zeigt das Unterteilen von Dreiecken durch das Einfügen von Punkten und Liniensegmenten in das Oberflächengitter.

  
Abbildung 2.17: Das Unterteilen von Dreiecken durch das Einfügen von Punkten und Liniensegmenten in das Oberflächengitter; (a) vor dem Einfügen des Punktes P5, (b) nach dem Einfügen des Punktes P5.

Die am schwierigsten durchzuführenden Gittermodifikationen sind mit dem Entstehen von Oberflächen-Loops verbunden. Oberflächen-Loops müssen rechtzeitig erkannt und entfernt werden, denn durch das Vergrössern der Loops während der Simulation würde es zu einem rapiden Anwachsen von Punkten, Linien und Dreiecken im Oberflächengitter kommen. In der dreidimensionalen Simulation gestaltet sich das Entfernen von Oberflächen-Loops jedoch äußerst schwierig und ist mit beträchtlichem Rechenzeitaufwand verbunden. Es muß zunächst jedes Dreieck des Oberflächengitters mit allen übrigen Dreiecken auf einen möglichen Schnitt untersucht werden. Die sich schneidenen Dreiecke müssen anschließend entsprechend ihrer Schnittlinie modifiziert werden, und anhand der angrenzenden Dreiecke muß im weiteren der Oberflächen-Loop detektiert werden. Wurde ein Oberflächen-Loop einmal erkannt, können zugehörige Punkte, Linien und Dreiecke aus dem Gitter entfernt werden. Verschiedene Verfahren für das Erkennen und das Entfernen von Oberflächen-Loops werden in [Hel92], [Sch91a] und [Toh90] beschrieben.



next up previous contents
Next: 2.2 Der Ray-Trace-Algorithmus Up: 2.1 Der String-Algorithmus Previous: 2.1.3 Erweiterungen



Martin Stiftinger
Thu Nov 24 17:41:25 MET 1994