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.