5.3.2 Die Methode der konvexen Teilgebiete



next up previous contents
Next: 5.3.3 Die Winkelmethode Up: 5.3 Geometrieabfragen Previous: 5.3.1 Die Schnittmethode

5.3.2 Die Methode der konvexen Teilgebiete

 

Laut Definition [Lup81] ist ein Gebiet genau dann konvex, wenn für zwei beliebige Punkte und , die in dem Gebiet liegen ( und ), auch deren Verbindung nach Gl. 5.1 vollständig im Gebiet liegt.

 

Für konvexe Geometrien kann das Problem der Ortsbestimmung eines Punktes trivial gelöst werden. Alle Grenzflächen zwischen zwei benachbarten Gebieten liegen in Ebenen, die durch die folgende Gleichung beschrieben werden

 

wobei der Normalvektor auf die -te Ebene, ein Punkt der Ebene und der Abstand vom Ursprung des Koordinatensystems ist. Um nun zu bestimmen, ob das Ion innerhalb des fraglichen Gebietes liegt, müssen nun alle Normalvektoren entweder in das Gebiet hinein oder aus dem Gebiet heraus zeigen. Falls alle in die Region hineinzeigen, so muß folgende Ungleichung:

  
Abbildung 5.4: Für konvexe Gebiete ist die Bestimmung des Aufenthaltsortes eines Ions trivial: Das Ion muß ,,über`` den Grenzlinien liegen.

 

erfüllt sein. bezeichnet in Gl. (5.3) den gegenwärtigen Aufenthaltsort des Ions (< muß in obiger Gl. (5.3) verwendet werden, wenn nach außen zeigt). Ein Beispiel dafür ist in Abb. 5.4 dargestellt.

Die allgemeinen Geometrien, die bei der Simulation der Ionen-Implantation behandelt werden müssen, können nicht auf konvexe Gebiete eingeschränkt werden. Daher muß man konkave Gebiete in konvexe Teilgebiete unterteilen. In diesem Fall wird das Problem der Ortsbestimmung von den eigentlichen Geometrietests hin zur Bestimmung beziehungsweise Generation von konvexen Gebieten verlagert. Für zweidimensionale Anwendungen ist dieses Problem gelöst [Pre85], [Fis89], obwohl diese Methode numerisch aufwendig werden kann.

Im dreidimensionalen Fall ist die Methode des Aufteilens von konkaven Gebieten in konvexe Teilgebiete aus zwei Gründen nicht anwendbar: Erstens ist der Test auf Konvexität sehr komplex und rechenzeitaufwendig. Es reicht nicht, daß alle Flächen konvex sind; der gesamte dreidimensionale Körper muß auf Konvexität untersucht werden, was keine triviale Aufgabe ist. Der zweite Grund ist, daß während der Generation konvexer Teilgebiete neue Flächen, Linien und unter Umständen sogar neue Punkte generiert werden. Dadurch steigt der Speicheraufwand erheblich, und diese neuen Elemente müssen für alle Nachbargebiete ins Kalkül gezogen werden.

Eine Lösungsmöglichkeit für diese Probleme wäre eine generelle Aufteilung des gesamten Gebietes in Tetraeder, die ja im dreidimensionalen Raum zu den einfachsten Strukturelementen gehören. Diese Tetraeder können dann zu möglichst großen konvexen Regionen zusammengelegt werden. Das ist aber wieder eine aufwendige und komplexe Aufgabe. Andererseits, wenn diese Tetraeder nicht zusammengelegt werden, müssen für die Ortsbestimmung viele Gebiete getestet werden, weil entsprechend viele Tetraeder generiert werden. Das hat aber wieder einen Anstieg in der Rechenzeit zur Folge, weil diese von der Anzahl der zu testenden Gebiete abhängt.



next up previous contents
Next: 5.3.3 Die Winkelmethode Up: 5.3 Geometrieabfragen Previous: 5.3.1 Die Schnittmethode



Martin Stiftinger
Sat Oct 15 14:00:19 MET 1994