Abbildung 5.3: Bei der Bestimmung des
Gebietes, in dem sich das Ion befindet, mittels der Schnittmethode
wird eine Halbgerade vom gegenwärtigen Aufenthaltsort des Ions
gelegt. Die Anzahl der Schnittpunkte mit den Grenzflächen wird
bestimmt; wenn diese Zahl ungerade ist, dann liegt das Ion in der
fraglichen Region.
Die Schnittmethode [Pre85] (vgl. Abb. 5.3) ist relativ einfach zu implementieren und wird daher sehr oft für zweidimensionale Anwendungen benützt, weil dort die Geometrieabfragen nicht das Hauptproblem darstellen. Es ist jedoch bereits in diesem Fall zu beachten, daß es numerische Probleme geben kann, wenn nicht spezielle Überlegungen angestellt werden.
Bei dieser Methode wird eine Halbgerade konstruiert, die an der aktuellen Position des Ions beginnt und bis ins Unendliche reicht. Die Anzahl der Schnitte dieser Halbgeraden mit allen Grenzflächen, die das aktuelle Gebiet definieren, wird bestimmt. Wenn diese Anzahl ungerade ist, so befindet sich das Ion innerhalb der fraglichen Region; bei einem geraden Zähler liegt der derzeitige Aufenthalsort des Ions außerhalb des Gebietes. In diesem Fall muß die nächste Region untersucht werden. Das Problem dieser Methode im dreidimensionalen Fall ist die aufgrund der großen Anzahl der notwendigen Schnittberechnungen sehr hohe Rechenzeit.
Folgender Algorithmus wird für die Schnittberechnung der Hilfslinie mit den Seitenflächen des Körpers verwendet: Zuerst wird der Schnittpunkt der konstruierten Halbgeraden mit der Ebene, in der die Fläche liegt, bestimmt. Wenn es einen Schnittpunkt gibt (die Gerade also nicht parallel zur Ebene ist), dann muß noch weiter untersucht werden, ob der Schnittpunkt innerhalb der Fläche liegt oder nicht. Dafür werden zuerst alle Punkte der Grenzfläche und auch der Schnittpunkt in den zweidimensionalen Raum transformiert. Danach kann dann der gleiche Schnitt-Algorithmus verwendet werden, um zu testen, ob der vorher bestimmte Schnittpunkt innerhalb der Fläche liegt oder nicht. Für die Grenzflächen gilt nämlich auch, daß sie keineswegs konvex sein müssen, was auch schon im zweidimensionalen erhebliche Vorteile brächte. Es wird wieder eine Halbgerade ins Unendliche gelegt - diesmal allerdings vom transformierten Schnittpunkt und im zweidimensionalen Raum. Die Anzahl der Schnitte dieser Halbgeraden mit den Linien, die die Grenzfläche definieren, wird bestimmt. Wieder gilt, daß der Schnittpunkt innerhalb der Berandung liegt, wenn diese Zahl ungerade ist.
Um diese Methode zu beschleunigen, können - falls das Simulationsgebiet aus mehreren Regionen besteht, die mit verschiedenen Materialien ausgefüllt sind - zuerst alle Grenzflächen, die von der Hilfslinie geschnitten werden, markiert werden. Danach müssen nur mehr für jede Region die zugehörigen markierten Seitenflächen gezählt werden. So wird sichergestellt, daß jede Fläche nur einmal geschnitten wird.
Neben dem Problem des großen Rechenzeitbedarfes können auch wie bereits weiter oben angesprochen - und dies ist speziell im dreidimensionalen Raum sehr kritisch - numerische Probleme auftreten. So darf etwa diese Halbgerade, die vom gegenwärtigen Aufenthaltsort des Ions ins Unendliche führt, nicht in einer Ebene mit einer Grenzfläche liegen; diese Linie darf durch keinen Eckpunkt gehen und auch keine Begrenzungslinie enthalten. Spezielle Überlegungen für die Wahl eines entsprechenden Richtungsvektors (im dreidimensionalen Raum) müssen angestellt werden, um alle diese Fälle zu vermeiden.
Die Schnittmethode wurde für den zweidimensionalen Simulator verwendet. Wegen der aufgezeigten Probleme mußte für den dreidimensionalen Fall nach anderen Möglichkeiten für die Geometriefragen gesucht werden. In den folgenden Abschnitten soll daher auf weitere Methoden für dreidimensionale Geometrietests eingegangen werden.