Volumen-Diskretisierung für flexible Körper

Um eine stabile finite Elemente oder Masse-Feder Simulation berechnen zu können, muß das zugrundeliegende Gitter bestimmten Anforderungen genügen: Die Gitterstäbe sollten ungefähr gleich lang sein, die Gitterelemente sollten eine Tedraederform besitzen, es darf keine allzu stumpen und allzu spitzen Winkel geben und die vorgegebene Oberfläche des zu triangulierenden Körpers sollte möglichst gut approximiert werden. Im Rahmen der Diplomarbeit wurde der Oberflächentriangulierungs-Algorithmus von Fang Fang1 zu einem Volumentriangulierer weiterentwickelt. Er stammt aus dem Bereich der rekursiv aufbauenden Algorithmen und liefert eine Delaunay Triangulierung, die die geforderten Eigenschaften erfüllt. In jedem Schritt wird, von einem Initial-Tedraeder ausgehend, ein weiterer Punkt der zu triangulierenden Punktemenge so einfügt, daß immer die leere Umkugelbedingung der Delaunay Triangulierung gewährleistet ist. Grundidee des Algorithmus ist es, die zu bearbeitenden Dreiecksflächen in einer zentralen Liste zu verwalten. Die Berechnung läuft so lange, bis diese zentrale Liste abgearbeitet wurde. Bei jeder neu entstehenden Fläche sind die Berührfälle mit bereits vorhandenen Flächen zu prüfen und danach entsprechend umzusetzen, so daß keine Kantenschnitte oder sich durchdringende Tedraeder entstehen. Um die Punktsuche zu beschleunigen wird der Raum in Zellen eingeteilt, so daß nur die Zellen um eine Dreiecksfläche herum nach einem neuen günstigen Punkt absucht werden. Dadurch wird vermieden, daß immer die gesamte Punktmenge durchsucht werden muß, um den passenden Punkt für einen neuen Tedraeder zu finden. Mit Hilfe des in der Diplomarbeit entwickelten robusten und stabilen Algorithmus kann man vorgegebene konvexe Körper, die durch eine polygonale Oberfläche beschrieben werden, mit Punkten füllen und über diesen Punkte dann eine Delaunay Triangulierung berechnen. Dadurch ist es möglich volumenenthaltende elastische Verformungen von Körpern mit auf der Triangulierung aufsetzenden Methoden der finiten Elemente Rechnung zu simulieren