close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Full text - Institut für Baustatik und Baudynamik - Universität Stuttgart

EinbettenHerunterladen
Implementierung und
Untersuchung eines
Kontaktsuchalgorithmus
für Selbstkontakt
vorgelegt von
Anita-Maria Wanner
im
Oktober 2014
Diplomarbeit
Implementierung und Untersuchung eines
Kontaktsuchalgorithmus für Selbstkontakt
von
Anita-Maria Wanner
bearbeitet im Zeitraum
Juni 2014 bis Oktober 2014
unter der Betreuung von
Dipl.-Ing. Christoph Wilking
Erklärung
• Hiermit erkläre ich, dass ich die hier vorliegende Diplomarbeit selbständig verfasst habe.
• Es wurden nur die in der Arbeit ausdrücklich benannten Quellen und Hilfsmittel verwendet. Wörtlich oder sinngemäß übernommenes Gedankengut habe ich als solches gekennzeichnet.
• Die eingereichte Arbeit war und ist weder vollständig noch in wesentlichen Teilen Gegenstand eines anderen Prüfungsverfahrens.
• Ebenso habe ich die Arbeit weder vollständig noch in Teilen bereits veröffentlicht.
• Ich versichere, dass das elektronische Exemplar mit den anderen Exemplaren übereinstimmt.
Stuttgart, 26. Oktober 2014
Baustatik und Baudynamik
Institut für Baustatik
und Baudynamik
Prof. Dr.-Ing. habil. M. Bischoff
Diplomarbeit
Implementierung und Untersuchung
eines Kontaktsuchalgorithmus für Selbstkontakt
In der Strukturmechanik wird von Kontakt gesprochen, wenn mehrerer Körper aufeinander
treffen und Kräfte oder auch Temperaturen durch Kontakt von einem Körper auf den anderen
übertragen werden. Kontaktprobleme spielen in vielen Bereichen des Maschinenbaus sowie
des Bauingenieurwesens eine wichtige Rolle, beispielsweise in Crashtest- und Umformsimulationen. Zur numerischen Simulation dieser Probleme werden stabile Kontaktalgorithmen
benötigt.
Die Kontaktsuche hat zur Aufgabe, die Ränder der Körper zu bestimmen, die so nahe
beieinander liegen, dass Sie möglicherweise in Kontakt kommen könnten. Das hat den
Vorteil, dass die rechenintensive Abstandsberechnung zwischen den Körpern nur entlang
der durch die Kontaktsuche ermittelten Ränder erfolgen muss.
Die Kontaktränder werden für die Berechnung normalerweise bereits vor der Untersuchung
in einen Slave- und einen Masterrand unterteilt. Da die genaue Zuordnung bei komplexen
Deformationszuständen vorab nicht möglich ist, muss sie durch einen Algorithmus während
der Rechnung geschehen. Dafür sind spezielle Kontaktsuchalgorithmen erforderlich, die in
dieser Arbeit untersucht werden sollen.
Abbildung: Kontaktproblem mit Selbstkontakt
Im Einzelnen:




Einarbeitung in das Thema Kontaktmechanik und Kontaktsuche,
Implementierung eines Kontaktsuchalgorithmus für Selbstkontakt,
Beschreibung des Algorithmus,
Berechnung einzelner numerischer Beispiele.
Ansprechpartner:
Malte von Scheven (Raum 1.005)
Kurzfassung
Kurzfassung
Da Kontakt in vielen Bereichen des Ingenieurswesens eine wichtige Rolle spielt, wird für die
Simulation von Kontaktproblemen ein stabiler Kontaktalgorithmus benötigt. Da es aber nicht
immer möglich ist, bei komplexen Deformationszuständen die Kontaktränder vor der Untersuchung in Master- und Slave zuteilen, wird ein Kontaktsuchalgorithmus für Selbstkontakt
benötigt, der während der Rechnung die Kontaktpaare findet und dem jeweiligen Rand zuordnet. Hierfür, wird ein Kontaktsuchalgorithmus untersucht der mittels eines Face-ClusteringAlgorithmus die Kontaktregion beschreibt und einen Bottom-Up-Baum für die Kontaktsuche
erstellt. Auf dieser Basis werden anschließend die Kontaktpaare mittels Bounding Volumes
und zusätzlichen Kriterien ermittelt und anschließend des jeweiligen Kontaktrandes zugeordnet. Dazu soll das institutseigene FE-Programm "NumPro" erweitert werden.
i
Vorwort
Vorwort
Hiermit möchte ich mich bei dem Institut für Baustatik und Baudynamik der Universität
Stuttgart bedanken. Insbesonders gehört mein Dank meinem Betreuer Herr Dipl.-Ing. Christoph Wilking und meinem Mann, die mir immer mit Rat und Tat zu Seite standen.
Stuttgart, im Oktober 2014
Anita-Maria Wanner
ii
Inhaltsverzeichnis
Abbildungsverzeichnis
1
1 Einleitung
1.1 Motivation und Zielsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3
3
2 Mortar-Selbstkontakt
2.1 Problembeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Spannungs- und Verschiebungsrandbedingungen . . . . . .
2.1.2 Virtuelle Arbeit des Selbstkontaktproblems . . . . . . . . .
2.2 Kontaktkinematik und Kontaktbedingungen . . . . . . . . . . . . .
2.2.1 Abstandsgleichung . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Kontaktspannungen . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Normale Kontaktbedingungen (Kuhn-Tucker-Bedingungen)
2.2.4 Relative Geschwindigkeit . . . . . . . . . . . . . . . . . . .
2.3 Diskretisierung mit Finite Elemente . . . . . . . . . . . . . . . . .
2.3.1 Diskretisierung der virtuelle Kontaktarbeit . . . . . . . . .
3 Selbstkontaktsuchalgorithmus
3.1 Bounding Volumes . . . . . . . . . . . . . . . . .
3.1.1 Anforderungen für Bounding Volumes . .
3.1.2 Bounding Volume Typen . . . . . . . . .
3.2 Bounding Volume Hierachie (BVH) . . . . . . . .
3.2.1 Defintion und Anforderungen an das BVH
3.2.2 Aufbaustrategien des BVHs . . . . . . . .
3.2.3 Update des BVHs . . . . . . . . . . . . .
iii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
6
7
8
8
9
9
9
10
10
.
.
.
.
.
.
.
12
12
13
14
23
23
24
27
Inhaltsverzeichnis
3.3
3.4
3.5
3.6
3.7
3.8
Face-Clustering-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Kostenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 Ablauf des Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . .
Optimierung der Selbstkontaktsuche . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Das Nachbarschaftsproblem . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Krümmungskriterium . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.3 Nachbarschaftstest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algorithmus zur Suche von Selbstkontaktpaaren . . . . . . . . . . . . . . . . .
3.5.1 Beispiel: Belastung einer Dose . . . . . . . . . . . . . . . . . . . . . . . .
Master- und Slave-Sortieralgorithmus . . . . . . . . . . . . . . . . . . . . . . . .
Kosten des Selbstkontaktsuchalgorithmus . . . . . . . . . . . . . . . . . . . . .
Einbindung der Mortar-Selbstkontaktsuche in die Newton-Raphson-Iteration
um die Mortar-Selbstkontaktsteifigkeit zu Berechnen . . . . . . . . . . . . . . .
4 Implementierung in NumPro
4.1 Allgemeiner Programmablauf . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Eingabefile und Einlesen . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Ausgabe der Daten und Ergebnisse . . . . . . . . . . . . . . . . . . .
4.1.3 Diskretisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.4 Statisch lineare Berechnung . . . . . . . . . . . . . . . . . . . . . . .
4.2 Überblick der eingebetteten Klassen des Selbstkontaktsuchalgorithmus . . .
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
4.3.1 Contact_Surface_Node . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Contact_Surface_Element . . . . . . . . . . . . . . . . . . . . . . .
4.3.3 Face . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.4 Contact_Dis_FE . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.5 Self_contact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
27
31
33
34
34
34
40
41
43
49
50
51
52
52
52
53
53
54
54
55
55
56
56
57
57
5 Zusammenfassung und Ausblick
62
Literaturverzeichnis
64
iv
Abbildungsverzeichnis
2.1
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
3.17
3.18
3.19
Transportvorgang und Notation für ein Selbstkontakproblem mit großer Deformation (k = 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Geometrie- und Füllungseffizienz des Bounding Volumes . . . . . . . . . . . . . 13
Vergleich Hüllkörper nach Geometrie, Speicher, Testzeit und Abbildung . . . . 14
Definition: Axis-Aligned Bounding Box (AABB) in 2D . . . . . . . . . . . . . . 15
Beschreibungsmethoden von Axis-Aligned Bounding Boxes (AABB) in 2D . . . 16
Intervallüberschneidung entlang einzelner Achsen bei AABB(2D) . . . . . . . . 16
Abstandsprüfung entlang x-Achse bei AABB mit Min-Abstand (2D) . . . . . . 17
Abstandsprüfung entlang x-Achse bei AABB mit Mittelpunkt-Radius (2D) . . 18
Überlappung bei Axis-Aligned Bounding Boxes (AABB) in 2D . . . . . . . . . 18
Definition: Oriented Bounding Boxes (OBB) in 2D . . . . . . . . . . . . . . . . 19
Überlappung bei Oriented Bounding Boxes (OBB) in 2D . . . . . . . . . . . . . 19
Überlappungtest bei Oriented Bounding Boxes (OBB) . . . . . . . . . . . . . . 20
8-DOP für ein Dreieck ((3,1), (5,4) und (1,5)) für die Achsen (1,0), (0,1), (1,1)
und (1, − 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Intervallüberschneidungsprüfung zweier k-DOPS entlang einer Achse . . . . . . 22
Definitionen eines Bounding Volume Baums (Wurzel = rote Farbe, Blätter =
grüne Farbe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Bounding Volume Hierachie als Top-Down . . . . . . . . . . . . . . . . . . . . . 26
Bounding Volume Hierachie als Bottom-Up . . . . . . . . . . . . . . . . . . . . 27
Dual Graph als ein zusätzliches Oberflächennetz für den Face-Clustering-Algorithmus 28
Kantenkontraktion und Erstellung einer neuen Teilfläche (parent): (a) Initialnetz, (b) neues zusätzliches Netz mit neuem Knoten . . . . . . . . . . . . . . . 29
Hierachischer Aufbau des Bounding-Volume-Baums mit 16 FE-Elementen und
31 T-Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1
Abbildungsverzeichnis
3.20 Krümmungskriterium für „KEIN“-Selbstkontakt . . . . . . . . . . . . . . . . .
3.21 Krümmungskriterium bei einer einzelner Fläche (a) und zwei Nachbarschaftsflächen (b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.22 Bounding-Volume-Überschneidungsverfahren bei Oberflächen ohne direkte Nachbarschaftslage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.23 Richtungsbox mit 26 Mustervektoren begrenzt durch einen Würfel (rot = Ecken,
blau = Flächen, grün = Kanten) . . . . . . . . . . . . . . . . . . . . . . . . . .
3.24 Suche qualifzierte Richtungsvektoren von unten nach oben im Baum: (1) Richtungsvektorenbox mit Musterrichtungsvektoren; (2) Richtungsvektoren der Blätter und der FE-Flächen; (3) Richtungsvektoren aller T-Nodes und Teilflächen .
3.25 Vektorsuche v am Beispiel von Abb. 3.19, kein Selbstkontakt . . . . . . . . . .
3.26 Nachbarschafttest (2D) durch Prüfung auf zwei gemeinsame Eckpunkte . . . .
3.27 (a) Deformation einer Dose durch Last F und zugehörige diskretisierte Kontaktregion (b) als Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.28 Bottom-Up-Baum der Kontaktregion aus Abb. 3.27 (b) mit den zugehörigen
Richtungsvektoren an jedem T-Node . . . . . . . . . . . . . . . . . . . . . . . .
3.29 Bounding Volumes des Kontaktproblems zu jeder Ebene des Bottom-Up-Baums
aus Abb. 3.28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.30 Ablauf des Suchalgorithmus nach Algorithmus aus Abschnitt 3.5 . . . . . . . .
3.31 Nachbarschaftstest nach Algorithmus aus Abschnitts 3.4.3 . . . . . . . . . . . .
3.32 Willkürliche Definiton von Master-Slave-Elementen an zwei Patches: (Doppelpfeil beschreibt ein Kontaktpaar) . . . . . . . . . . . . . . . . . . . . . . . . . .
3.33 Sortierte Kontaktelementpaare nach dem Facet-Sorting-Algorithmus (Doppelpfeil beschreibt ein Kontaktpaar) . . . . . . . . . . . . . . . . . . . . . . . . . .
2
34
35
36
37
38
39
40
43
44
45
47
48
49
50
1
Einleitung
1.1 Motivation und Zielsetzung
Da Kontakt in vielen Bereichen des Lebens uns ganz unbewusst begegnet, spielt auch der Kontakt im Ingenieurswesen eine sehr wichtige Rolle. Im Bauingenieurswesen tritt Kontakt zum
Beispiel in Auflagern als Auflagerpressung auf. Im Maschinenbau tritt Kontakt beispielsweise
bei Crashtest und Umformungen auf. Somit kann man in der Mechanik von Kontakt sprechen,
wenn zwei oder mehrere Körper aufeinandertreffen. Statt Kontaktprobleme per Hand zu berechnen, werden numerische Simulationen zur Berechnung dieser Probleme benutzt. Hierfür ist
ein stabiler Kontaktsuchalgorithmus erforderlich, der die Ränder des Körpers bestimmt, die so
nahe beieinander liegen, dass Kontakt auftreten könnte. Somit wird nur entlang möglicher Kontakträndern der Abstand zwischen zwei Körpern berechnet. Damit dies möglich ist, werden die
Kontaktränder normalerweise vor der Berechnung in Master- und Slaveränder unterteilt. Bei
komplexen Deformationen, wie es bei Crashtests- und bei Umformungssimulationen der Fall
ist, ist eine genaue Zuordnung im Vorfeld von Master- und Slaveränder nicht möglich. Hierfür
wird ein Kontaktsuchalgorithmus für Selbstkontakt benötigt, der während der Rechnung die
Kontaktränder in Master- und Slaveränder sortiert. In dieser Arbeit wird hierfür der MortarSelbstkontaktalgorithmus aus der Arbeit von Yang (2009) verwendet. Dazu werden Methoden
aus der Computergrafik und Animation, wie den Bounding Volumes, den Bounding Volume
Hierachies und dem Face-Clustering-Algorithmus von Garland u. a. (2001) verwendet. Hierzu soll dieser Selbstkontaktsuchalgorithmus in das institutseigene FE-Programm „Num-Pro“
implementiert und untersucht werden.
1.2 Aufbau der Arbeit
Zunächst werden die Grundlagen des Mortar-Selbstkontakt geklärt. Dies beinhaltet die Problembeschreibung, die Kontaktkinematik, die Kontaktbedingungen und die Diskretisierung
3
1.2 Aufbau der Arbeit
mitttels Finiten-Elementen. Nachdem die Grundlagen des Selbstkontakts geklärt wurden, wird
im nächsten Kapitel der Selbstkontaktsuchalgortihmus behandelt. Dazu werden zunächst die
Bounding Volumes mit ihren Anforderungen, Typen und Überschneidungsmethoden vorgestellt, die benötigt werden um Kontakt festzustellen. Anschließend werden die unterschiedlichen Bounding Volume Hierachies beschrieben, mit dem ein benötigter Baum für den Suchalgorithmus aufgebaut werden kann. Über den Face-Clustering-Algorithmus wird mittels einer
Kostenfunktion und Kantenkontraktion ein Bottom-Up-Baum für die Kontaktregion erstellt.
Nachdem der Baum aufgebaut wurde, werden die Optimerungsmethoden, wie das Krümmungskriterium und der Nachbarschaftstest vorgestellt, die den Kontaktsuchalgorithmus verbessern
sollen. Mit den zuvor vorgestellten Methoden wird dann der Selbstkontaktsuchalgorithmus
zusammengebaut und die gefundenen Kontaktpaare werden durch einen Master-und Slavesortieralgorithmus den Master- und Slaverändern zugeordnet. Im anschließenden Kapitel wird
auf die Umsetzung des Selbstkontaktsuchalgorithmus in dem institutseigenen FE-Programm
vorgestellt und eingegangen.
4
2
Mortar-Selbstkontakt
In diesem Kapitel werden zunächst die Grundlagen des Mortar-Selbstkontakts geklärt. Dazu
wird zunächst das Problem, mittels Definition der Spannungs- und Verschiebungsrandbedingungen und der Formulierung der virtuellen Arbeit, beschrieben. Anschließend wird auf die
Kontaktkinematik und die Kontaktbedingungen eingegangen. Dieses Kapitel basiert hauptsächtlich auf der Literatur von Yang (2009) und Yang und Laursen (2007).
2.1 Problembeschreibung
Für die Mortar-Selbstkontaktformulierung mit großen Deformationen und großen Gleiten müssen zunächst ein paar Begriffe definiert werden. Dazu wird zunächst ein Selbstkontaktkörper
B zum Zeitpunkt t0 in der Referenzkonfiguration betrachtet (siehe Abb. 2.1) Zu diesem Zeitpunkt findet kein Selbstkontakt statt. Der Körper B wird dabei durch eine offene Menge Ω
und seinen Körperrand ∂Ω definiert. Die Oberfläche ∂Ω wird dabei in weitere Flächen, wie
• Γu : Verschiebungsbereich,
• Γσ : Bereich mit Oberflächenlasten (Traktionen),
• Γc : Kontaktbereich mit Kontaktrandbedingungen
unterteilt und es gelten die folgende Bedingungen
Γu ∪ Γσ ∪ Γc = ∂Ω,
(2.1)
Γσ ∩ Γu = Γσ ∩ Γc = Γu ∪ Γc = ∅.
(2.2)
und
5
2.1 Problembeschreibung
γσ
Γσ
(3,1)
γc
ϕ
(1,1)
γc
(3,2)
γc
(1,2)
γc (2,1)
γc
Ω
(2,2)
γc
Y
γu
X
Γu
Momentankonfiguration
Referenzkonfiguration
Abbildung 2.1: Transportvorgang und Notation für ein Selbstkontakproblem mit großer Deformation (k = 3)
Durch die Deformationsabbildungsfunktion ϕ wird der Körper in die Momentankonfiguration
zum Zeitpunkt t abgebildet. Die Oberfläche des Körpers wird dabei ähnlich, wie schon zuvor, in
γu , γσ und γc unterteilt. Zu diesem Zeitpunkt t findet Selbstkontakt an verschiedenen Stellen
des deformierten Körpers statt (siehe Abb. 2.1). Jede Selbstkontaktregion besteht aus zwei
Teilflächen von γc . Diese Teilflächen werden als Slave-Patch und Master-Patch bezeichnet.
Gibt es also k Kontaktregionen in der aktuellen Konfiguration, so gibt es auch k Slave- und
k Master-Patches auf dem Selbstkontaktrand des Körpers. Dazu wird der i-te Slave-Patch als
(i,1)
(i,2)
γc
und der i-te Master-Patch γc
für i = 1, . . . ,k Kontaktregionen bezeichnet.
2.1.1 Spannungs- und Verschiebungsrandbedingungen
Die Randbedingungen für den Bereich der Oberflächenlasten Γσ lautet bzgl. der Referenzkonfiguration:
¯ j in Γσ
PiJ NJ = T
(2.3)
mit
• PiJ : Komponenten des ersten Piola-Kirchhoff-Spannungstensor,
• NJ : Komponente der nach aussengerichteten Normalen auf ∂Γσ ,
¯ i : Traktion.
• T
Die Randbedingung für die Verschiebungen u¯i bzgl. der Referenzkonfiguration lautet:
ϕj = ϕ¯j in Γu .
6
(2.4)
2.1 Problembeschreibung
2.1.2 Virtuelle Arbeit des Selbstkontaktproblems
Für die Defintion der virtuellen Arbeit wird zunächst der Lösungsraum C und der Wichtungsraum V benötigt. Diese beiden Räume, bestehend aus der Lösung ϕ und dessen Variation ϕ,
werden wie folgt definiert:
¯ → R2 |ϕ ∈ H 1 (Ω),ϕ = ϕ¯ in Γu }
C = {ϕ : Ω
(2.5)
¯ → R2 | ϕ∈ H 1 (Ω), ϕ= 0 in Γu }
V = {ϕ: Ω
(2.6)
und
mit
• H 1 (Ω): Sobolev-Raum, Funktionsraum für quadratisch integrierbare Ableitungen.
Das Prinzip der virtuellen Arbeit für ein Selbstkontaktproblem für große Deformationen lautet:
G(ϕ, ϕ) : = G(ϕ ,ϕ)
(2.7)
[ρ0 ϕ ·A + Grad ϕ: P]dΩ −
=
Ω
Ω
G int (ϕ,ϕ)
k
−
(i,1)
ϕ
¯
ϕ ·TdΓ
ϕ ·FdΩ −
Γσ
−G ext (ϕ,ϕ)
k
·t(i,1) dΓ −
i=1 (i,1)
Γc
ϕ
(i,2)
·t(i,2) dΓ = 0
(2.8)
i=1 (i,2)
Γc
G c (ϕ,ϕ)
= G int,ext (ϕ, ϕ) + G c (ϕ, ϕ) = 0,
(2.9)
mit
• ϕ ∈ C und ϕ∈ V: Deformation und dessen Variation,
• G int,ext (ϕ, ϕ): Virtuelle Arbeit interner und externer Kräfte,
• G c (ϕ, ϕ): virtuelle Arbeit des Kontakts mit Kontaktspannungen,
• A: materielles Beschleunigungsfeld im Körper bei Trägheitseffekte,
• ρ0 : Dichte,
• F: Körperkraft.
Für die Darstellung der virtuellen Kontaktenergie in der Momentankonfiguration wird G c (ϕ, ϕ
(i,1)
(i,2)
) aus Gl. (2.8) bei dem i-ten Slave- γc und Master-Patch γc mit den Mortar-Multiplikatoren
7
2.2 Kontaktkinematik und Kontaktbedingungen
λ(i,1) und λ(i,2) wie folgt umgeschrieben:
k
(i,1)
G c (ϕ, ϕ) = −
ϕ
k
·λ(i,1) dγ −
(i=1) (i,1)
γc
ϕ
(i,2)
·λ(i,2) dγ .
(2.10)
(i=1) (i,2)
γc
i-tes Slave-Patch
i-tes Master-Patch
Dabei stellen die Mortar-Multiplikatoren die Cauchy-Kontaktspannungen dar. Entsprechend
dem Gleichgewicht („Actio = Reactio“) an der Kontaktfläche
λ(i,1) dγc(i,1) = −λ(i,2) dγc(i,2)
(2.11)
kann die virtuelle Kontaktarbeit in Gl. (2.10) ersetzt werden durch
k
G c (ϕ, ϕ) = −
(i,1)
λ(i,1) (X,t) · (ϕ
(X,t)− ϕ
(i,2)
¯
(Y,t))dγ
(2.12)
(i=1) (i,1)
γc
(i,2)
(i,1)
¯
wobei ϕ
(Y,t)
die aktuelle Kontaktstellenposition für X ist. Die Slave-Fläche γc
wird
auch als „nonmortar“ Fläche bezeichnet. Hier werden auch die Lagrange-Multiplikatoren in(i,2)
terpoliert. Die Master-Fläche γc
bezeichnet man auch als „mortar“ Fläche.
2.2 Kontaktkinematik und Kontaktbedingungen
2.2.1 Abstandsgleichung
Da Kontakt nur auftritt wenn sich die zwei Kontaktflächen Master und Slave berühren, muss
der Abstand zwischen den beiden Flächen null sein. Ausserdem dürfen sich die beiden Flächen
nicht durchdringen (Penetration) und somit der Abstand nicht negativ werden. Hierfür wird
eine Abstandsfunktion g(X,t) wie folgt definiert
¯
g(X,t) = n · [ϕ(i,1) (X,t) − ϕ(i,2) (Y,t)]
(2.13)
g(X,t) ≥ 0
(2.14)
und die Kontaktbedingung
¯ den Projektionspunkt an einem gegebenen Slave-Punkt X zum
erfüllt. Dabei beschreibt Y
Zeitpunkt t auf der Master-Oberfläche. n beschreibt die nach außen gerichtete Einheitsnormale
(i,1)
zu γc
an der Stelle x = ϕ(i,1) (X,t).
8
2.2 Kontaktkinematik und Kontaktbedingungen
2.2.2 Kontaktspannungen
Durch die Zerlegung der auftretentende Kontakspannung λ bei g(X,t) = 0 aus Gl. (2.12) in
λ = λN + λT = λN n + λTα τ α
(2.15)
Normal- λN und Tangentialanteil λT kann man das Kontaktproblem getrennt in Normal- und
Tangentialkontakt betrachten. λTα beschreibt die kovariante Komponente von der Tangentialspannung λT .
2.2.3 Normale Kontaktbedingungen (Kuhn-Tucker-Bedingungen)
Für normalen Kontakt (reibungsfrei) kann die Kontaktbedingung über die Kuhn-Tucker-Bedingungen (Willner (2003))beschrieben werden:
• kinematisches Durchdringungsverbot:
g(X,t) ≥ 0
(2.16)
Kontakt liegt vor, wen materielles Durchdringen (g(X,t) ≤ 0) ausgeschlossen wird.
• kinetisches Adhäsionsverbot:
λN (X,t) ≤ 0
(2.17)
Für den Normalanteil λN (X,t) der Kontaktspannung gilt das Adhäsionsverbot, also die
Übertragung von Zugspannungen.
Außerdem gilt, dass die Kontaktspannung λN (X,t) nur nicht null sein kann, wenn g(X,t) = 0
und somit
λN (X,t)g(X,t) = 0
(2.18)
gilt.
2.2.4 Relative Geschwindigkeit
Die relative Geschwindigkeit v bei Kontakt lässt sich wie bei den Kontaktspannungen in
Normal- vN und Tangentialgeschwindigkeit vT wie folgt zerlegen:
¯ − ϕ˙ (i,2) (X,t)
v = ϕ˙ (i,2) (Y,t)
= vN + vT = vN n + vTα τ α .
9
(2.19)
2.3 Diskretisierung mit Finite Elemente
2.3 Diskretisierung mit Finite Elemente
Bei der Diskretisierung wird der Kontaktkörper Ω mit einer Menge von Finite Elementen E h
diskretisiert
Ωh =
Ωe .
(2.20)
∀e∈E h
Die Kontaktoberflächen Γhc,s/m werden über Teilmengen von ∂Ωh diskretisiert.
Der diskretisierte Lösungsraum C h und der Wichtungsraum V h lautet dann
¯ h → Rd |ϕh ∈ C 0 (Ωh ),
C h ={ϕh : Ω
∀e ∈ E h ,ϕh (Ωhe ) ∈ PN (Ωhe ); ϕh = ϕ
¯ in Γhu }
(2.21)
und
h
h
¯ h → Rd | ϕ ∈ C 0 (Ωh ),
V h ={ϕ : Ω
h
h
∀e ∈ E h , ϕ (Ωhe ) ∈ PN (Ωhe ); ϕ = 0 in Γhu }
(2.22)
mit
• d: Dimension des Raums,
• PN (Ωhe ): Menge von Polynome in Ωhe mit der Ordnung ≤ N .
h
(i,α)h
Die „mortar“ und „nonmortar“ Felder ϕ(i,α) (Γc
tionen ϕ
(i,α)h
(i,α)h
(Γc
h
) ⊂ X (i) (α = 1,2) und deren Varia-
h
) ⊂ W (i,α) sind Teilmengen von C h und V h und sind somit durch die
(i,a)h
Gleichungen (2.21) und (2.22) auf die Kontaktflächen Γc
beschränkt.
Die Diskretisierung des Mortar-Muliplikatoren-Raums ist wie folgt definiert:
h
Mh ={λh |λh ∈ C 0 (Γc(i,1) );
h
h
∀e ∈ P h ,λh (Γc(i,1)
) ∈ PN (Γ(i,1)
), i = 1, . . . ,k}
ce
e
(2.23)
mit P h : Menge von „nonmortar“ Elementflächen bestehend aus Slave-Patches.
2.3.1 Diskretisierung der virtuelle Kontaktarbeit
Die Diskretisierung der virtuellen Kontaktarbeit (2.12) wird nach Yang (2009) Kapitel 2 dish
kretisiert. Dazu werden die Multiplikatoren λh , die Deformationsfelder ϕ(i,α) und ihre Varia(i,α)h
tionen ϕ
(i)
durch Formfunktionen Ne
interpoliert. Als diskretisierte Version der virtuellen
10
2.3 Diskretisierung mit Finite Elemente
Kontaktarbeit erhält man
G
cm
h
k
h =
(i,1)
(ϕ , ϕ ) −
λA · [nAB ϕ
i=1 A
B
(1)
(i,2)
−nAC ϕ
(2)
]
(2.24)
C
mit
• Mortar-Integralen:
(i,1)
(1)
(1)
NA (ξ (1) (X))NB (ξ (1) (X))dγ, i = 1, . . . ,k
(2.25)
(1)
(2)
¯
NA (ξ (1) (X))NC (ξ (2) (Y(X)))dγ,
i = 1, . . . ,k
(2.26)
nAB =
h
γ (i,1)
und
(i,2)
nAC =
h
γ (i,1)
(1)
(2)
¯
• NA (ξ (1) (X)) und NC (ξ (2) (Y(X))):
Formfunktionen definiert auf den diskretisierten
Slave- und Master-Patches,
• A und B: Slave-Knoten auf dem Slave-Patch,
• C : Master-Knoten auf dem Master-Patch.
11
3
Selbstkontaktsuchalgorithmus
Normalerweise werden bei der Berechnung des Kontakts die Ränder in Slave- und Masterrand
unterteilt. Dies ist jedoch bei der Selbstkontaktsuche nicht möglich. Deshalb wird hierfür ein
spezieller Selbstkontaktsuchalgorithmus benötigt, der während der Rechnung von komplexen
Deformationszuständen die Master- und Slave-Elemente sucht. Hierfür werden zunächst die
Bounding Volumes mit ihren Vor- und Nachteilen und ihren Überschneidungsmethoden vorgestellt, die später bei der Prüfung auf ein Selbstkontaktpaar benötigt werden. Anschließend
wird der Kontaktsuchalgorithmus vorgestellt:
• Aufbau des Bottom-Up-Baums mittels der Kantenkontraktion (Face- Clustering-Algorithmus),
• Krümmungskriterium um nichtgekrümmte Flächen auszuschließen,
• Nachbarschaftstest um Kontakt durch Nachbarschaften auzuschließen,
• die Selbstkontaktpaarsuche (Kombination aus den vorherigen Punkten und Bounding
Volume Überschneidung) und
• Zuordnung der Kontaktpaare zu Master- und Slaveelementen.
Dieses Kapitel basiert hauptsächlich auf der Arbeiten von Yang (2009), Garland u. a.
(2001), Willmott (2000) Volino und Magnenant-Thalmann (2000) und Ericson (2005).
3.1 Bounding Volumes
Bounding Volumes werden als Testverfahren zur Kollisionsdetektion und insbesonders zur Beschleunigung von Algorithmen in der Computergrafik (z.B. Raytracing 1 ) eingesetzt. Mit die1
Raytracing ist ein auf Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechung, also zur
Ermittlung der Sichtbarkeit von dreidimensionalen Objekten von einem bestimmenten Punkt im Raum aus
(Wikipedia, 2014).
12
3.1 Bounding Volumes
sem Verfahren können somit einfach, schnell und speichersparend komplexe Objekte auf Überlappungen oder Berührungen getestet werden. Dazu wird ein Hüllkörper mit einer einfachen
Form um ein komplexes reales Objekt gelegt und approximiert. Durch die Ersetzung des komplexen Körpers durch einen einfacheren Körper spart man bei geometrischen Tests und somit
die frühzeitige Beendigung des Tests („early out“) bei keiner stattfindenen Überlappung Arbeitszeit, Kosten und aufwändige Operationen. Da sich in der Regel nur wenige Objekte oder
Teilflächen bei Selbstkontakt berühren, kann der anfängliche Mehraufwand durch Erzeugung
zusätzlicher einfacherer Objekte zur Optimierung der Kontaktsuche verwendet werden.
3.1.1 Anforderungen für Bounding Volumes
Damit die vorherigen genannten Vorteile erfüllt werden können, stellen sich folgendene Kriterien und Anforderungen an die Bounding Volumes (Volino und Magnenant-Thalmann
(2000) und Ericson (2005)):
• Geometrie- und Füllungseffizienz: Möglichst eng anliegend am realen Objekt mit minimalen Raum (siehe Abb. 3.1 und Abb. 3.2)
gute Wahl
schlechte Wahl
Abbildung 3.1: Geometrie- und Füllungseffizienz des Bounding Volumes
• Kompaktheit: Geringe Parameteranzahl zur Beschreibung von Bounding Volumes
• Einfache Erstellung: Effiziente Erstellung von Bounding Volumes von einer Objektgruppe
oder durch zusammenfügen von Bounding Volumes
• Einfache und effiziente Kontaktsuche: Schnelle Verarbeitung beim Überlappungstest zwischen Bounding Volumes
• Umgebungsabhängigkeiten: Achsenabhängigkeit, Transformation, Koordinatensysteme
• Einfache Skalierung und Rotation
• Niedriger Speicherverbrauch: Verwendung einfacher geometrischer Formen als Hüllkörper
(siehe Abb. 3.2)
• Niedrige Kompilierzeit: Bounding Volumens werden in der Regel nicht erst während der
Laufzeit generiert (Preprocessing) (siehe Abb. 3.2)
13
3.1 Bounding Volumes
bessere Approximation des realen Objekts, weniger unausgef üllter Raum
Schneller Test, weniger Speicher
SPHERE
AABB
OBB
8 − DOP
Konvexe H ülle
Abbildung 3.2: Vergleich Hüllkörper nach Geometrie, Speicher, Testzeit und Abbildung
3.1.2 Bounding Volume Typen
Wie in Abbildung 3.2 zu sehen ist, gibt es unterschiedliche Arten von Bounding Volumes, die
die Anforderungen unterschiedlich gut erfüllen (vgl. 3.1.1). Die typischen Bounding Volumes
die gebräuchlich sind, sind:
• Bounding Spheres: Kugeln, die sich sehr leicht berechnen lassen
• Bounding Boxes: Quader oder Würfel, die meistens genauer als Kugeln sind
– Oriented Bounding Boxes (OBB): Beliebig orientierte Quader
– Axis-Aligned Bounding Boxes (AABB): An Achsen ausgerichtete Quader
• k-Discrete Oriented Polytopes (k-DOP): Polyeder, die durch mehr Beschränkungsflächen
die Objekte enger einschließen
• Sphere-Swept Volumes
– Sphere-Swept Point (SSP)
– Sphere-Swept Line (SSP)
– Sphere-Swept Rectangle (SSR)
Im nachfolgenden werden einzelne Bounding Volume Arten genauer auf ihre Vor- und Nachteile
betrachtet.
Bounding Sphere
Wie schon zuvor erwähnt, handelt es sich bei dem Bounding Sphere um eine Kugel als Hüllkörper. Im Vergleich zu den anderen Bounding Volumes, benötigt dieser Hüllkörper den geringsten
14
3.1 Bounding Volumes
Speicheraufwand, da nur der Objektmittelpunkt m und der Radius r gespeichert werden muss.
Weitere Vorteile der Spheres sind:
• Einfache Transformation: Da die Kugel achsenunabhängig ist, spielt die Rotation keine
Rolle. Die Kugel muss nur an die neue Position verschoben werden.
• Einfacher Überlappungsstest zweier Spheres (Ericson (2005))
(m1x − m2x )2 + (m1y − m2y )2 + (m1z − m2z )2 ≤ r1 + r2 .
(3.1)
Nachteile der Bounding Spheres sind die aufwändige nicht-lineare geometrische Berechnung
der optimalen Position in der Mitte des approximierten komplexen Objektes und die nicht
optimale Approximation des realen Objekts durch die Kugel. Anwendung finden Bounding
Spheres insbesonders bei Star-Körper-Verschiebungen, wie z.B. in der Robotik Verwendung.
Axis-Aligned Bounding Boxes (AABB)
Ein weitere Möglichkeit ein Bounding Volume zu definieren, ist die Axis-Aligned Bounding
Box (AABB). Dabei wird das zu approximierte Objekt durch ein Rechteck (2D: 4 Seiten) oder
ein Quader (3D: 6 Seiten), dessen Flächen parallel zu den Flächen x − y, x − z und y − z des
gegebenen Koordinatensystems sind, beschränkt. Oder anders ausgedrückt, die Flächennormalen der Box sind immer parallel zu den Achsen des gegebenen Koordinatensystems (siehe
Abb. 3.3).
y
x
Abbildung 3.3: Definition: Axis-Aligned Bounding Box (AABB) in 2D
Definiert werden die Axis-Aligned Bounding Boxes durch drei verschiedene Methoden (siehe
Abb. 3.4):
(a) Minimum min und Maximum max Koordinaten entlang jeder Achse,
(b) Minimaler Eckpunkt min und den Abständen dx, dy und dy von diesem Eckpunkt,
(c) Mittelpunkt der Box m und den Radien rx, ry und rz Richtung den Achsen.
15
3.1 Bounding Volumes
(a)
(b)
min
(c)
min
dy
ry
dx
y
y
x
max
rx
m
y
x
x
Abbildung 3.4: Beschreibungsmethoden von Axis-Aligned Bounding Boxes (AABB) in 2D
Vorteile von Axis-Aligned Bounding Boxes ist die einfache Boxerstellung, das Zusammenfügen
von Boxen und das Update von Iteration zu Iteration. Auch die Kollisionserkennung mittels
Intervallüberschneidung ist einfach zu implementieren. Beim Übeschneidungstest wird je nach
gewählter Beschreibungmethode unterschieden zwischen:
(a) Min-Max: Intervallüberschneidung entlang einzelner Achsen
y
Bmin
yBmin
yAmin
Amin
yBmax
Bmax
yAmax
Amax
xAmin
xBmin
xAmax
xBmax
x
Abbildung 3.5: Intervallüberschneidung entlang einzelner Achsen bei AABB(2D)
Wie in Abb. 3.5 gezeigt, wird in jeder Achse auf Überschneidung mittels Schnittmenge
der Intervalle geprüft. Bei 2D lautet die Formulierung dann in x-Richtung:
A : [xAmin ,xAmax ]
∩
B : [xBmin ,xBmax ]
(3.2)
A : [yAmin ,yAmax ]
∩
B : [yBmin ,yBmax ].
(3.3)
und y-Richtung:
16
3.1 Bounding Volumes
(b) Min-Abstand: Abstandsprüfung entlang einzelner Achsen
y
Bmin
yBmin
yAmin
Amin
dxB
dxA
xAmin
x
xBmin
−t
Abbildung 3.6: Abstandsprüfung entlang x-Achse bei AABB mit Min-Abstand (2D)
In x-Richtung (Abb. 3.6) z.B. gibt es keine Überschneidung, wenn der Abstand t =
xAmin − xBmin zwischen den min-Eckpunkten die Bedingung
∪
t > dxB
−t > dxA
erfüllt. Die anderen Achsen werden konform zur x-Achse geprüft.
(c) Mittelpunkt-Radius: Abstandsprüfung entlang einzelner Achsen
17
(3.4)
3.1 Bounding Volumes
y
rxB
yAm
Bm
yBm
rxA
Am
xBm
xAm
x
Abbildung 3.7: Abstandsprüfung entlang x-Achse bei AABB mit Mittelpunkt-Radius (2D)
In x-Richtung (Abb. 3.7) z.B. gibt es keine Überschneidung, wenn die Bedingung
|(xmA − xmB )| > (rxA + rxB )
(3.5)
erfüllt ist. Die anderen Achsen werden auch hier konform der x-Achse geprüft.
Nachteile von AABBs, im Vergleich (OBB 3.1.2 und k-DOP 3.1.2) zu den nachfolgenden beschriebenen Bounding Volumes, sind die ungenaue Abbildung des realen Objekts und die
Vergrösserung der Boxen bei Rotation der AABBs Somit findet schon bei grossem Abstand
zweier Flächen eine Überlappung statt (siehe Abb. 3.8).
Abbildung 3.8: Überlappung bei Axis-Aligned Bounding Boxes (AABB) in 2D
18
3.1 Bounding Volumes
Oriented Bounding Boxes (OBB)
Ein weitere Bounding Volumes Möglichkeit sind Oriented Bounding Boxes (OBBs) wie Abb.
3.9 zeigt.
y
x
Abbildung 3.9: Definition: Oriented Bounding Boxes (OBB) in 2D
Dabei handelt es sich um eine Box deren Orientierung abhängig von dem approximierten
Objekt ist. Im Vergleich zu der AABB ist eine OBB viel enger und somit ist auch der Überlappungstest bei der Kollisionssuche viel effizienter als bei AABBs. Am besten sieht man es
an dem Beispiel aus Abb. 3.8. Anstelle von AABBs werden nun OBBs (Abb. 3.10) benutzt
und man kann feststellen das keine Überlappung der Flächen stattfindet, wo zuvor noch eine
Überlappung war.
Abbildung 3.10: Überlappung bei Oriented Bounding Boxes (OBB) in 2D
Jedoch, ist die Berechnung, das Update bei jedem Iterationsschritt viel kostenintensiver und
der Überlappungstest (siehe Abb. 3.11) komplizierter, da die Achsen bei OBBs keine diskrete
19
3.1 Bounding Volumes
Orientierung haben und sich somit mit dem Objekt mitbewegen. Der Überlappungstest zweier
OBBs, wie Abb. 3.11 zeigt, kann nach Ericson (2005) wie folgt durchgeführt werden:
„Es existiert keine Überlappung der beiden OBBs wenn, bzgl. einer Achse L, die Summe der
projizierten Radien rAproj und rBproj auf die Achse L kleiner ist, als der projizierte Abstand T
beider Mittelpunkte auf die Achse L.“
|T · L| > rAproj + rBproj
(3.6)
Bm
T
Am
rAproj
rBproj
L
|T · L|
Abbildung 3.11: Überlappungtest bei Oriented Bounding Boxes (OBB)
Ein weiterer Nachteil ist der intensive Speicherbedarf der OBBs, da bei jedem OBB der Mittelpunkt, die Orientierungsmatrix und ein Vektor mit drei Längen zu den Ecken der Box
gespeichert werden müssen.
Discrete Oriented Polytopes (k-DOP)
Bei den k-Discrete Oriented Polytopes (k-DOP) handelt es sich um Polyeder mit denen sich
Objekte enger und somit besser durch mehrere Beschränkungsflächen einschließen lassen. Dabei
hat ein k-DOP eine konvexe Hülle mit k Flächen wie z.B.
• 6-DOP: Flächen in den Richtungen (±1,0,0), (0, ± 1,0) und (0,0, ± 1);
• 8-DOP: Flächen in den Richtungen (±1, ± 1, ± 1);
• 12-DOP: Flächen in Richtungen (±1, ± 1,0), (±1,0, ± 1) und (0, ± 1, ± 1);
• 14-DOP: Flächen als Kombination aus 6-DOP und 8-DOP.
20
3.1 Bounding Volumes
Ein k-DOP ist dabei immer enger als ein AABB und bei einem OBB, je nach Objektgeometrie,
mehr oder weniger enger. Wie auch immer, k-DOPs benötigen weniger Speicherplatz, sind
einfacher zu berechnen und upzudaten. Auch der Kollisionstest zweier k-DOPs ist billiger
und sehr effizient. Die diskreten orientierten Normalen eines k-DOP sind paarweise kollinear
und es handelt sich um entgegengesetzt orientierte Vektoren. Erzeugt wird ein k-DOP in 2D
durch k/2 parallele Linienpaare (siehe z.B Abb. 3.12: blaue Linien für ein 8-DOP) oder durch
Flächen in 3D. Dabei wird der Raum zwischen einem parallelen Linienpaar und einer Fläche
als „Slab“ bezeichnet und die Überschneidung von k/2 „Slabs“ definiert die Region des kDOPs. Gespeichert werden bei einem k-DOP somit nur die Achsenabschnitte der Linien mit
den Koordinatenachsen, also k/2 Paare mit min- und max-Werten in k-Richtungen. Für einen
8-DOP wären das z.B. 4 Paare mit je einem min- und max-Wert in 8 Richtungen (0, ± 45, ±
90, ± 135 und 180 Grad).
Abbildung 3.12: 8-DOP für ein Dreieck ((3,1), (5,4) und (1,5)) für die Achsen (1,0), (0,1), (1,1)
und (1, − 1)
Für ein Dreieck (siehe Abb. 3.12) mit den Koordinaten (3,1), (5,4) und (1,5) speichert man für
ein 8-DOP folgende Achsenabschnitte:
21
3.1 Bounding Volumes
(1,0)
1
5
min
max
(1,1)
4
9
(0,1)
1
5
(0, − 1)
-4
2
Tabelle 3.1: Achsenabschnitte eines Dreiecks mit 8-DOP
Anhand der gespeicherten Achsenabschnitte in jede Richtung können zwei k-DOPs mittels Intervallüberschneidung entlang jeder Achse geprüft werden. Es gilt, zwei k-DOPs überschneiden
sich nicht, wenn die Intervalle in der Richtung sich nicht überlappen (siehe Abb. 3.13).
y
in
Am
Am
in
Bm
ax
x
ax
Bm
Abbildung 3.13: Intervallüberschneidungsprüfung zweier k-DOPS entlang einer Achse
Ein grosser Nachteil der k-DOPs ist, dass sie bei jeder Transformation neu berechnet werden
müssen mittels zusätzlicher Verfahren. Zum Einsatz kommt der Hill Climbing Algorithmus,
einem heurestischen Optimierungsverfahren um Nachbarknoten eines Knoten zu finden. Dabei werden Knoten mit ihren Nachbarknoten verglichen um rauszufinden ob sie immer noch
22
3.2 Bounding Volume Hierachie (BVH)
Extremale in die selbe Richtung sind. Sind sie es nicht, werden sie durch einen extremalen
Nachbarn ersetzt (siehe Ericson (2005)).
3.2 Bounding Volume Hierachie (BVH)
Ziel eines Kontaktsuchalgorithmus ist es alle Slave-Master-Paare schnell und effizient zu finden,
bei denen Kontakt stattfinden. Da Kontakt, insbesonders bei Selbstkontakt, meistens nur in
kleinen Bereichen der Körpergeometrie statt findet, wird die Oberfläche des Körpers rekursiv
immer in kleinere Flächen gesplittet um diese zu finden. Diese rekursive Zerlegung der Körperoberfläche in kleinere Flächen wird durch eine Baumstruktur beschrieben. Dazu wird ein
Bounding Volume Baum oder auch Bounding Volume Hierachie (BVH) genannt, verwendet.
3.2.1 Defintion und Anforderungen an das BVH
Defintion
Bei einer Bounding Volume Hierachie repräsentiert jeder Knoten des Baums (T-Node genannt)
eine Fläche oder Teilfäche. An jedem Knoten des Baums werden die Informationen bzgl. der
korrespondierenden Teilfläche gespeichert, so auch die zugehörigen Bounding Volumes. Jeder
Knoten ist also verbunden mit einer Untermenge von Knoten, diese werden Kinder (childs)
genannt. Jedoch, besitzt jeder T-Node nur zwei Kinder, ein linkes und ein rechtes Kind. Nur
die kleinsten Flächen der rekursiven Zerlegung der Körperoberfläche, werden als Blätter (leaf
tree nodes) bezeichnet und besitzen somit keine Kinder. Somit besitzt jedes Kind einen ElternT-Node (parent), außer die Wurzel (root) des Baums. Sie repräsentiert die komplette, nicht
zerlegte Oberfläche (siehe Abb. 3.14). Gibt es also n Elemente für eine Kontaktfläche, somit
gibt es 2n − 1 T-Nodes im Bounding Volume Baum und es wird ein Speicherplatz von O(n)
benötigt.
23
3.2 Bounding Volume Hierachie (BVH)
root
1
right child
left child
2
3
T − Node
4
5
6
7
leaf
8
9
Abbildung 3.14: Definitionen eines Bounding Volume Baums (Wurzel = rote Farbe, Blätter =
grüne Farbe)
Anforderungen
Wie bei den Bounding Volumes (siehe 3.1.1) gibt es auch Anforderungen (Ericson (2005))
an BVHs:
• Jeder Knoten innerhalb eines Teilbaums sollten in näherer Nachbarschaft liegen.
• Jeder Knoten in der Hierachie sollte nur ein minimales Volumen haben.
• Die Summe alle Bounding Volumes sollten minimal sein.
• Das überlappende Volumen von Geschwister sollte möglichst gering sein.
• Balancierte Hierachie bzgl. Knotenstruktur und des gespeicherten Inhalts.
3.2.2 Aufbaustrategien des BVHs
Es gibt grundsätzlich drei verschiedene Methoden einen Baum zu konstruieren (Ericson
(2005)):
• Top-Down (spaltend): Zerlegung des Eingabesatzes (root) in weitere Untersätze bis zu
den Blättern (leafs).
• Bottom-Up (verdichtend): Gruppieren der Eingabsätze (leafs) in einen einzigen Knoten
(root).
24
3.2 Bounding Volume Hierachie (BVH)
• Insertion: Hierarchischer inkrementeller Aufbau durch Einfügen von Objekten. Position
wird mittels Kostenberechnung ermittelt.
Im Nachfolgenden werden die beiden geläufigsten Methoden Top-Down und Bottom-Up näher
erläutert.
Top-Down
Bei der Top-Down-Methode, wie schon erwähnt wurde, beginnt mit einem einzigen T-Node
(root), welcher die gesamte Oberfläche darstellt (siehe Abb. 3.15). Diese Oberfläche wird dann
rekursiv in immer kleinere Teilflächen zerlegt bis nur noch ein einzelnes Bounding Volume
übrig ist. Für jede neue Teilfläche wird dann ein neuer T-Node angelegt. Zum Zerlegen von
Flächen gibt es unterschiedliche Möglichkeiten:
• Mittige Zerlegung der Projektion entlang einer gewählten Achse um zwei gleichgroße
Teile zu erhalten,
• Zerlegung mittels Ebene entlang einer Achse:
– Lokale x-, y- und z-Koordinatenachsen,
– Achse eines Eltern Bounding Volumes,
– Achse zwischen zwei Punkten,
– Entlang Achse mit grösster Varianz der Eingabedaten,
– Achse des bestimmten ausgerichteten Bounding Volumes (AABB, k-DOP),
und durch einen Zerlegungspunkt:
– Objektmedian: Median der Koordinatenschwerpunkte,
– Objektdurchschnitt: Durchschnitt der Koordinatenschwerpunkte,
– Räumlicher: Median der Bounding Volumes.
Details zu weiteren Zerlegungsmöglichkeiten können bei Ericson (2005) nachgelesen werden.
Bei Verwendung einer Zerlegungsebene durch einen Median der Koordinatenschwerpunkte ergibt sich mit O(log n) Ebenen die Konstruktionskosten von O(n log n).
25
3.2 Bounding Volume Hierachie (BVH)
1
1
2
2
6
4
3
3
4
7
5
8
5
8
9
6
7
9
Abbildung 3.15: Bounding Volume Hierachie als Top-Down
Für eine bessere Effizienz bei großen Deformationen, muss der Baum in regelmässigen Abstand
aktualisert werden (siehe Abschnitt 3.2.3).
Bottom-Up
Eine weitere Methode ist der Aufbau eines Baums von den Blätter ausgehend, wie z.B. beim
Face-Clustering-Algorithmus von Garland u. a. (2001) für Selbstkontaktsuche und wird genauer im nachfolgenden Abschnitt 3.3 betrachtet. Beim Bottom-Up-Baum beginnt man von
den Blätter ausgehend anhand von Eingabeelementen (siehe Abb. 3.16). Diese Elemente werden
rekursive mittels eines Clusteralgorithmus gruppiert. Bei jeder Gruppierung von zwei Knoten
wird ein T-Node erzeugt und das zugehörige Bounding Volume. Der Aufbau endet wenn nur
noch ein T-Node übrig bleibt (kein parent).
26
3.3 Face-Clustering-Algorithmus
9
9
6
7
3
6
4
2
1
8
7
8
3
1
5
7
2
3
4
5
Abbildung 3.16: Bounding Volume Hierachie als Bottom-Up
Großer Vorteil dieser Methode ist, dass sie beim Baumaufbau sehr Robust gegen Selbstüberlappung ist.
3.2.3 Update des BVHs
Bei Kontaktproblemen mit großer Deformation muss der Baum nach jeder Iteration aktualisiert werden, da sich die Bounding Volumes durch die Deformation drastisch geändert haben.
Die Aktualisierung des Baums kann mittels der Bottom-Up-Methode erfolgen. Dabei werden
für alle Blätter die Bounding Volumes je nach Bounding-Volume-Typ neu berechnet (siehe
3.1.2). Anschließend werden die Bounding Volumes der Kinderknoten rekursiv vereinigt um
die Elternknoten zu erhalten. Da bei der Aktualisierung des Baums jeder Knoten nur einmal
aufgesucht werden muss, beläuft sich die Komplexität bei n Blätter auf O(n).
3.3 Face-Clustering-Algorithmus
Um den im vorherigen Abschnitt (3.2.2) beschriebenen Bottom-up Bounding Volume Baum zu
erstellen, wird ein Verfahren aus der Computergraphik verwendet, mit dem man kontrolliert
den Netzdetailgrad eines modellierten 3D-Körpers reduzieren kann ohne das Aussehen des
Körpers wesentlich zu verändern (Wikipedia, 2013).
Dabei handelt es sich um den zuvor erwähnten Face-Clustering-Algorithmus (Garland-HeckbertAlgorithmus) von Garland u. a. (2001) und Willmott (2000). Dazu wird wie in Abbildung
27
3.3 Face-Clustering-Algorithmus
3.17 gezeigt, ein zusätzliches Netz (Dual Graph - rote Linien) über das vorhandene FiniteElemente-Netz (gestrichelte Linien) gelegt. Dabei repräsentiert jeder Dual Node (große Knoten) ein Finites Element. Verbunden werden die angrenzenden Nachbar-FE-Elemente, die an
den Kanten anliegen, durch sogenannnte Dual Edges (rote Linien).
Dual Edge
Dual Node
Finite Element Edge
Finite Element Node
Abbildung 3.17: Dual Graph als ein zusätzliches Oberflächennetz für den Face-ClusteringAlgorithmus
Anschließend wird inkrementell immer eine Kante des zusätzlichen Netzes (Dual Edge) anhand
von einer Kostenfunktion gelöscht und die beiden adjazenten Knoten werden zu einem einzeln
neuen Knoten zusammengefasst. Dieses Verfahren wird auch als Kantenkontraktion oder kollaps bezeichnet. Durch die Referenzierung der Dual Nodes mit den FE-Elementen werden
somit zwei angrenzende Flächen gruppiert und zu einer neuen Teilfläche zusammengefasst
(siehe Abb. 3.18).
28
3.3 Face-Clustering-Algorithmus
a
b
Kantenkontraktion
Oberflächennetz
Neue Teilfläche
zusätzliches Netz (Dual Graph)
Abbildung 3.18: Kantenkontraktion und Erstellung einer neuen Teilfläche (parent): (a) Initialnetz, (b) neues zusätzliches Netz mit neuem Knoten
Somit ist die neue erzeugte Teilfläche in einer Bounding Volume Hierachie der Elternteil (parent) und die dazugehörigen Kinder (childs) sind die beiden Teilflächen, die vereinigt wurden.
Also repräsentiert jeder Dual Node und somit jede vereinigte Fläche einen Baumknoten (TNode) im Bounding-Volume-Baum. Die hierachische Struktur wird, wie in dem nachfolgenden
Beispiel gezeigt, aufgebaut (siehe Abb. 3.19).
29
3.3 Face-Clustering-Algorithmus
Abbildung 3.19: Hierachischer Aufbau des Bounding-Volume-Baums mit 16 FE-Elementen und
31 T-Nodes
30
3.3 Face-Clustering-Algorithmus
3.3.1 Kostenfunktion
Wie schon zuvor erwähnt wurde, wird die Kantenkontration und somit der Aufbau des Baums
durch eine Kostenfunktion bestimmt. Diese Funktion sorgt dafür, dass die „Qualität“, wie
z.B. die Ausgewogenheit, Form und Dichtheit, der Bounding Volume Hierachie gewährleistet
wird. Durch Zuweisung der Kostenfunktion an jede Kante (Dual Edge) wird somit geregelt,
welche Kante als erstes gelöscht wird. Die Kante mit den kleinsten Kosten wird dabei als erstes
gelöscht. Nach jeder Kantenkontraktion müssen die Kosten für die angrenzenden Kanten (Dual
Edges), wie Abb. 3.18 gezeigt, neu berechnet werden. Als Kostenfunktion E wird die Funktion
nach Yang (2009) benutzt, die ähnlich ist wie die in Willmott (2000):
E = (Efit + k · NE)
perim 2
,
projArea
(3.7)
mit
• Efit : Ebenheitsmetrik,
• NE: Anzahl FE-Elemente in der Teilfläche,
• k: Konstante Zahl um NE-Term anzupassen (nach Willmott (2000): k = 0,0001),
• perim: Umfang der Teilfläche,
• projArea: projizierte Teilfläche in Richtung flächengewichtete Normale.
Ebenheitsmetrik
Die Ebenheitsmetrik Efit oder auch „fit error“ genannt, ist der durchschnittliche quadratische
Abstand aller Punkte des Cluster zu einer optimalen Ebene. Cluster sind gleichbedeutend
zu den oben genannten Dual Edges und bestehen aus eine Menge von zugehörigen Flächen
(Faces) {f1 , . . . , fn } und ein Menge von Punkten {v1 , . . . ,vk } bestimmt durch die Eckknoten
dieser Flächen.
Eine optimale Ebene wird definiert durch eine Einheitsnormale n und einem Abstand d. Der
Abstand eines Punktes v zu der optimalen Ebene soll so gering wie möglich sein. Daher lautet
die Bedingung für den Abstand
nT v + d = 0.
(3.8)
Und Efit wird durch das Aufaddieren der Abstände der einzelnen Punkte zur optimalen Ebene
berechnet
Efit =
1
k
k
(nT vi + d)2 .
i=0
31
(3.9)
3.3 Face-Clustering-Algorithmus
Alternativ, kann der innere Term von Efit mittels der Quadrikfehlermetrik von Garland u. a.
(2001) umgeschrieben werden
T
T
T
2
(nT vi + d)2 = (nT vi + d)(vT
i n + d) = n (vi vi )n + 2dn vi + d .
(3.10)
Es werden dazu optimale Quadriken benutzt. Diese optimale Quadrik wird wie folgt definiert:
Pi = (Ai , bi , ci ) = (vi viT , vi , 1)
(3.11)
2
Pi (n, d) = nT Ai n + 2bT
i (dn) + ci d .
(3.12)
Dabei ist A eine symmetrische 3 × 3 Matrix, b ein Vektor mit drei Einträgen und c ein
Skalar. Vergleicht man Gl. (3.12) mit Gl. (3.10) kann die Ebenheitsmetrik Efit aus Gl. (3.9)
folgendermassen umgeschrieben werden
Efit =
1
k
Pi (n, d) =
i
1
(
k
Pi )(n, d)
(3.13)
i
und man erhält ein neue Ebenheitsmetrik mit der dazugehörigen Menge von Quadriken. Außer des Durchschnittsfaktors, ist der einzige Unterschied zu Gl. (3.9), dass jetzt über eine
Menge von Normalen zu einem festen Punkt aufaddiert wird, anstatt über eine Menge von
Punkten mit einer festen Normalen. Somit besitzt jeder Dual Node eine zugehörige passende
Quadrike P und eine optimale Ebene (n, d), sodass P(n, d) die Ebenheit des Clusters und dem
dazugehörigen Dual Node bemisst.
Die optimale Ebene (n, d), die die Quadrike P(n, d) minimiert, wird mit Hilfe der Hauptkomponentenanalyse (PCA - Principal Component Analysis) bestimmt. Dazu wird eine Kovarianzmatrix Z erstellt
¯T )
vi viT − k(¯
vv
Z=
(3.14)
¯
mit dem Durchschnitt der Eckpunkte v
¯=
v
(
vi )
i
k
.
(3.15)
Die Kovarianzmatrix Z aus Gl. (3.14) kann auch wieder in Form von der zugehörigen passenden
Quadrik P ausgedrückt werden und lautet somit
Z=A−
bbT
.
c
(3.16)
Anschließend kann die Normale n direkt durch die Berechnung des Eigenvektors mit dem
kleinsten Eigenwerte aus Gl. (3.16) bestimmt werden.
32
3.3 Face-Clustering-Algorithmus
Für den Abstand d wird angenommen, dass die Ebene durch den Mittelwert geht. Somit kann
der Abstand d mit
¯=
d = −nT v
−nT b
c
(3.17)
bestimmt werden. Somit sorgt Efit in der Gl. (3.7), dass nur Dual Edges gelöscht werden und
somit Flächen vereinigt werden, bei denen der Cluster fast planar ist.
Gleichgewichtsterm
2
perim
Der Term projArea
der Kostenfunktion E aus Gl. (3.7) sorgt dafür, dass der Bounding-VolumeBaum ausbalanciert wird. Er dient als eine Art „Strafterm". Durch die projizierte Fläche
projArea wird gesorgt, dass sich nicht die Teilfläche auf sich selbst zusammenfaltet. Desweiteren
sorgt der Umfang perim im Verhältniss zur projizierten Fläche, dass die Form der Teilflächen
so rund wie möglich bleiben. Der zweite Term ähnelt der Form von Willmott (2000).
3.3.2 Ablauf des Algorithmus
Der Ablauf des Face-Clustering-Algorithmus kann dann wie folgt zusammengefasst werden:
1. Erstellen eines initialen zusätzlichen Netzes (Dual Graph) über das FE-Netz (Erzeugung
von T-Nodes und Bounding Volumes für jedes FE-Element).
2. Berechnung der Kostenfunktion E mit Gl. (3.7) für alle Kanten (Dual Edges) des neuen
zusätzlichen Netzes.
3. Suche Kante mit geringsten Kosten zum löschen und erstelle neue Teilfläche durch Vereinigung von Teilflächen oder FE-Elementen.
4. Erzeuge einen neuen T-Node für die neue Teilfläche. Kinder des neuen T-Node sind die
beiden T-Nodes der zwei verbundenen Dual Nodes (Teilfäche oder Element).
5. Erzeuge für jeden neuen T-Node die zugehörigen Bounding Volumes.
6. Update aller Kostenfunktionen der angrenzenden Dual Edges.
7. Wiederhole solange 3. - 5. bis der komplette Baum aufgebaut ist.
Wie schon in Abschnitt 3.2.3 erwähnt, muss bei grossen Deformationen der Baum nach jeder
Iteration aktualisiert werden, da sich die Bounding Volumes verändert haben.
33
3.4 Optimierung der Selbstkontaktsuche
3.4 Optimierung der Selbstkontaktsuche
Da die Ergebnisse des Selbstkontakts abhängig sind von der Effizienz des Suchalgorithmus, ist
ein gutes Problemverständins notwendig. Daher muss für die Optimierung des Suchalgorithmus
zunächst geklärt werden, wann „wirklich“ Selbstkontakt stattfindet.
3.4.1 Das Nachbarschaftsproblem
Wie im Kapitel 2.1 beschrieben, findet Selbstkontakt zwischen zwei Elementen des selben Körpers und somit auf der selben Oberfläche statt. Da natürlich alle Nachbarschaftselemente der
selben Oberfläche im gegenseitigen Kontakt stehen und jeder Suchalgorithmus dazu entwickelt
wurde geometrischen Kontakt zwischen Elemente zufinden, werden auch alle Nachbarschaftselemente als Kontaktelemente fälschlicherweise gefunden. Somit würde man als Kontaktelemente die Anzahl der Nachbarschaften proportional zu der Gesamtanzahl von Elementen einer
Oberfläche finden und die aufgewendete Zeit wäre bei der Kontaktsuche proportional zu der
Anzahl Kontaktelemente multipliziert mit dem Logarithmus der Gesamtanzahl von Elementen (Volino und Magnenant-Thalmann (2000)). Dies ist jedoch absolut ineffizient, da die
Anzahl der „wirklichen“ Kontaktelemente typischerweise sehr viel kleiner oder sogar Null sind,
als die Gesamtanzahl der Elemente der Körperoberfläche. Somit wird ohne die Optimierung
des Suchalgorithmus Zeit verschwendet. Zur Effizienzsteigerung des Kontaktsuchalgorithmus
wird daher ein Kriterium benötigt, dass jeden Kontakt hervorgerufen durch Elementnachbarschaften ignoriert.
3.4.2 Krümmungskriterium
Bei einer flachen Oberfläche kann Selbstkontakt nicht stattfinden. Folglich findet Selbstkontakt
nur bei einer gekrümmt Fläche statt, die eine Schlaufe bildet. Deshalb wird zur Optimierung der
Selbstkontaktsuche das Krümmungskriterium (Curavation oder Curvature Criteria) benutzt,
dass beschreibt wann „KEIN“ Selbstkontakt stattfindet.
Für die „KEIN“-Selbstkontaktbedingung wird nach Volino und Magnenant-Thalmann
(2000) eine kontinuierliche (stetige) Oberfläche S im euklidischen Raum betrachtet, die durch
eine Kontur C begrenzt wird (siehe Abb. 3.20).
34
3.4 Optimierung der Selbstkontaktsuche
v
S
C
Abbildung 3.20: Krümmungskriterium für „KEIN“-Selbstkontakt
Erfüllt wird diese Bedingung, wenn:
• ein Vektor v an (fast) jedem Punkt von S existiert mit der Bedingung
n·v>0
(3.18)
mit n: Oberflächenormale von S am betrachteten Punkt,
• die Projektion von C auf einer Ebene orthogonal zu v ist und entlang der Richtung von
v keine Überschneidung stattfindet,
• kein Selbstkontakt auf Oberfläche S stattfindet.
Mit diesem Kriterium können sowohl alle „fast ebenen“ einzelnen Elementflächen also auch zwei
Nachbarschaftsflächen bei der Selbstkontaktsuche ausgeschlossen werden (siehe Abb. 3.21).
35
3.4 Optimierung der Selbstkontaktsuche
(a) In einer Oberflächenregion
kein Selbstkontakt
Selbstkontakt
(b) Zwischen zwei Oberflächenregionen (Nachbarn)
kein Selbstkontakt
Selbstkontakt
Abbildung 3.21: Krümmungskriterium bei einer einzelner Fläche (a) und zwei Nachbarschaftsflächen (b)
Integration des Kriteriums in den hierarchischen Algorithmus
Wie in Abschnitt 3.2 und 3.3 beschrieben, wird bei der Selbstkontaktsuche ein hierarchische Algorithmus basierend auf einer Baumstruktur mit Bounding Volumes verwendet. Dabei besteht
die Suche aus zwei Prozessen
• Kontakt in einer Oberflächenregion: jeder Kontakt mit der Oberfläche und ihren zugehörigen Kinderknoten und zwischen den Kinderknoten.
• Kontakt zwischen zwei Oberflächenregionen: jeder Kontakt zwischen beiden Regionen
und ihren Kinderknoten.
Bei zwei Knoten kann auf Kontakt sehr effizient durch die Überschneidung von den zugehörigen
Bounding Volumes geprüft werden. Bei der Prüfung auf Selbstkontakt bei einem Knoten, also
wenn sich ein Element oder Face auf sich selbst faltet, funktioniert die Überschneidungstechnik
mit Bounding Volumes nicht mehr. Genau hier, bei der Faltung auf die eigene Fläche, spielt
das Krümmungskriterium seine Vorteile aus.
Das Krümmungskriterium ersetzt somit im hierarchischen Kontaktsuchalgorithmus das BoundingVolume-Überschneidungsverfahren bei Kontakt innerhalb einer Oberflächenregion und bei
Nachbarschaftschaftsflächen. Lediglich bei Kontakt mit Oberfächen, die nicht in der Nach-
36
3.4 Optimierung der Selbstkontaktsuche
barschaft liegen wird das Bounding-Volume-Überschneidungsverfahren eingesetzt (siehe Abb.
3.22).
Selbstkontakt
kein Selbstkontakt
Abbildung 3.22: Bounding-Volume-Überschneidungsverfahren bei Oberflächen ohne direkte
Nachbarschaftslage
Suche des geeigneten Richtungsvektors v
Wie in Gleichung (3.18) beschrieben, benötigt man für das Kriterium einen optimalen Richtungsvektor v, bei dem das Skalarprodukt mit der Normalen n der gekrümmten Fläche positiv
ist. Dies bedeutet bei einem diskretisierten Oberflächenmodell, dass v mit allen Normalen der
Teilflächen ein positives Skalarprodukt haben muss. Für die Suche des passenden Richtungsvektors v, wird das Verfahren von Volino und Magnenant-Thalmann (2000) benutzt.
Dazu wird, ähnlich wie bei den Bounding Volumes, eine Box benutzt die alle zulässigen Richtungsvektoren beinhaltet. Mittels der „Richtungsbox“, dem erzeugtem Bottom-Up-Baum aus
Abschnitt 3.3 und einem Algorithmus lassen sich die zulässigen Richtungsvektoren v zu jedem
T-Node bestimmen. Hierfür geht man den Baum von den Blättern bis zur Wurzel systematisch durch und erzeugt, wie im Nachfolgenden beschrieben, zu jedem T-Node die dazugehörige „Richtungsbox“. Die „Richtungsbox“ von Root beinhaltet letztendlich den gesuchten
Richtungsvektor für die gesamte Oberfläche. Ist die Box leer, gibt es keinen passenden Vektor.
Beinhaltet die Box mehrere Vektoren, kann jeder Vektor aus der „Richtungsbox“ zur Erfüllerung des Krümmungskriterium (siehe Gl. (3.18)) gewählt werden.
Der Ablauf des rekursiven Algorithmus zur Suche des Richtungsvektors für die gesamte
Oberfläche kann wie folgt zusammengefasst werden (siehe Abb. 3.24):
1. Erzeugen einer Richtungsbox (siehe Abb. 3.24 (1)) mit konstanter Anzahl von Richtungsvektoren v.
Abhängig von der erforderlichen oder gewünschten Winkelgenauigkeit und Berechnungskosten, gibt es unterschiedliche Möglichkeiten diese Box zu definieren. Eine Variante ist
37
3.4 Optimierung der Selbstkontaktsuche
ein gleichmässiger Polyeder (z.B. ein Tetraeder, ein Würfel oder ein Dodekaeder) mit
Vektoren in Richtung Ecken, Kanten und Flächenmittelpunkte. Die einfachste Form ist
eine Richtungsbox mit 26 Vektoren innerhalb eines Würfels (siehe Abb. 3.23), die auch
in dieser Arbeit verwendet wird. Somit erhält man 8 Vektoren in Richtung der Ecken,
12 auf die Kantenmitte und 6 auf die Flächenmittelpunkte.
Abbildung 3.23: Richtungsbox mit 26 Mustervektoren begrenzt durch einen Würfel (rot
= Ecken, blau = Flächen, grün = Kanten)
2. Ermittlung der passenden Richtungsvektoren für jeden Blattknoten mittels Gl. (3.18).
D.h., suche alle Vektoren die mit der definierten Richtungsbox aus 1. ein positives Skalarprodukt mit der Normalen ni der Elementoberfläche hat (siehe Abb. 3.24 (2)). Um
Speicherplatz zu sparen, werden die Vektoren durch logische Variablen (1 = „falsch“ und
0 =„wahr“) in einem logischen Array, identisch zu den zugehörigen Richtungsvektoren,
gespeichert.
3. Ermittle alle Richtungsvektoren der T-Nodes mittels einer rekursiven Prozedur, die an
jedem T-Node die Richtungsvektoren vom linken und dem rechten Kinderknoten mit
dem logischen UND-Operator vergleicht und somit die Schnittmenge der beiden Kinder
ermittelt. Die Schnittmenge der beiden Kinder bildet die neuen Richtungsvektoren am
aktuell untersuchten T-Node und werden wieder in einem logischen Array wie in 2.
beschrieben gespeichert. Der Baum wird dabei von unten nach oben, T-Node für TNode, durchlaufen (siehe Abb. 3.24 (3)).
Der rekursive Algorithmus zur Suche der Richtungsvektoren wird vor jeder Newton-RaphsonIteration ausgeführt. Findet man mindestens einen Richtungsvektor an einem T-Node, findet
dort kein Selbstkontakt statt und somit auch nicht bei den zugehörigen Kinderknoten und
Teilflächen.
38
3.4 Optimierung der Selbstkontaktsuche
(1)
(2)
(3)
7
n3
5
6
n
1
n2
n4
1
2
3
4
Abbildung 3.24: Suche qualifzierte Richtungsvektoren von unten nach oben im Baum: (1)
Richtungsvektorenbox mit Musterrichtungsvektoren; (2) Richtungsvektoren der
Blätter und der FE-Flächen; (3) Richtungsvektoren aller T-Nodes und Teilflächen
Nimmt man das Beispiel aus Abbildung 3.19 und wendet das Kriterium an, erkennt man dass
auf Grund der fast ebenen Gesamtoberfläche und durch die gefunden Richtungsvektoren kein
Selbstkontakt statt finden kann (siehe Abb. 3.25).
39
n1
n2
n3
n4
n5 n6
n7
n8
n9
n10
n11
n12
n13
n14
n15
n16
3.4 Optimierung der Selbstkontaktsuche
Abbildung 3.25: Vektorsuche v am Beispiel von Abb. 3.19, kein Selbstkontakt
40
3.4 Optimierung der Selbstkontaktsuche
3.4.3 Nachbarschaftstest
Mit dem im Abschnitt 3.4.2 beschrieben Krümmungskriterium kann zwar bei Nachbarschaftsflächen festgestellt werden, ob Selbstkontakt statt findet oder nicht, aber es überprüft nicht
ob diese Flächen in Nachbarschaft liegen. Da jedoch das Kriterium benötigt wird zum Ignoriern von Kontakt, welcher hervorgerufen wird durch Elementnachbarschaften und somit zur
Optimierung der Selbstkontaktsuche, wird ein effizienter Algorithmus zur Bestimmung dieser
Nachbarschaft benötigt.
Bei einem 2D-Problem prüft man auf gemeinsame Eckpunkte der beiden Flächen. Haben
beide Flächen zwei gleiche Eckpunkte, sind die beiden Flächen Nachbarn (siehe Abb. 3.26).
Der Speicherverbrauch ist bei dieser Prüfung linear und die Kosten sind konstant.
Abbildung 3.26: Nachbarschafttest (2D) durch Prüfung auf zwei gemeinsame Eckpunkte
Bei einem 3D-Problem ist das Vergleichen von Eckpunkten bzgl. Zeiteffizienz und Speicherverbrauch zu aufwendig. Deshalb wird ein Algorithmus gesucht der linearen Speicherverbrauch
hat und den Test in einer konstanten Zeit durchführt.
Ablauf des Algorithmus
Der Nachbarschaftstest besteht aus zwei rekursiven Prozeduren:
1. Zu jedem T-Node werden die beide Kinder geholt und diese dann mit dem Status =
„wahr“ an den eigentlichen Nachbarschaftstest (siehe 2.) übergeben. Da diese Prozedur
rekursiv ist, werden anschließend zu jedem Kind (das auch ein T-Node ist) auch wieder die zugehörigen Kinder geholten und diese wieder an den Nachbarschaftstest (siehe
2.) mit dem Status = „wahr“ übergeben. Somit wird der erzeugt Baum aus Abschnitt
3.3 sukzessive von oben nach unten, also von der Wurzel bis zu den Blättern, abgearbeitet. Diese Prozedur wird nur ausgeführt, wenn der aktuelle untersuchte T-Node kein
Blattknoten ist.
2. Beim eigentlichen Nachbarschaftstest werden die beiden Kinder (linkes und rechtes Kind)
und dem übergeben Status mit folgenden Methoden geprüft:
41
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
a) Überschneidung der Kinder:
Hierbei handelt es sich um ein Abbruchkriterium, d.h. überschneiden sich die beiden
Kinder nicht, wird die Prozedur abgebrochen.
b) Status = „wahr“:
• Prüfung auf gemeinsame Eckknoten:
Findet man keinen einzigen gemeinsamen Knoten, wird der Status =„falsch“
gesetzt.
• Status = „wahr“: Speichern des linken Kindes als Nachbar vom rechten Kind
und umgekehrt.
c) Vergleiche Anzahl der Elemente von Kindern mit der Bedingung:
Elementanzahl linkes Kind > Elementanzahl rechtes Kind
Bedingung erfüllt und linkes Kind ist kein Blatt, gehe zu 2. zurück und überprüfe:
• linkes Kind vom aktuellen linken Kind, aktuelles rechtes Kind und aktueller
Status;
• rechtes Kind vom aktuellen linken Kind, aktuelles rechtes Kind und aktueller
Status;
Bedingung nicht erfüllt und rechtes Kind ist kein Blatt, gehe zu 2. zurück und
überprüfe:
• aktuelles linkes Kind, linkes Kind vom aktuellen rechten Kind und aktueller
Status;
• aktuelles linkes Kind, rechtes Kind vom aktuellen rechten Kind und Status.
Somit werden auch hier alle T-Notes rekursiv von der Wurzel bis zu den Blättern abgearbeitet.
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
Nachdem das Nachbarschaftsproblem (Abschnitt 3.4.1) mit dem Krümmungskriterium (Abschnitt 3.4.2) und dem Nachbarschaftstest (Abschnitt 3.4.3) gelöst ist, können die Selbstkontaktpaare, nachdem der Bounding-Volume-Baum für die zu untersuchende Kontaktoberfläche aufgebaut wurde, gesucht werden. Dazu wird ein rekursiver Selbstkontaktsuchalgorithmus
aus den vorherigen Optimierungsmethoden (Nachbarschaftstest und Krümmungskriterium)
gebaut. Als Abbruchkriterium dient ein gefundener Richtungsvektor v, der das Krümmungskriterium erfüllt.
42
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
Der Algorithmus besteht aus zwei rekursiven Prozeduren. Dazu wird eine Schleife über alle
T-Nodes der Baum sukzessive durchlaufen und jeder T-Node wird folgendermassen geprüft:
1. Prüfung des T-Nodes auf einen vorhandenen Richtungsvektor. Wird ein Richtungsvektor
am T-Node gefunden bricht die Selbstkontaktsuche ab. Existiert kein Richtungsvektor v
gehe weiter zu 2.
2. Wenn der T-Node kein Blattknoten ist werden die Kinder des aktuellen T-Node geholt und beide Kinder werden an die eigentlichen Selbstkontaktsucheprozedur (siehe im
Nachfolgenden beschrieben) mit dem Nachbarstatus = „wahr „ übergeben.
3. Wiederhole 1. und 2 für jedes Kind.
Die eigentliche Selbstkontaktsucheprozedur beginnt erst ab hier und ihr werden folgende Parameter übergeben: linkes Kind, rechtes Kind und Nachbarschaftsstatus. Anschließend werden
die beiden übergebenen Kinder mit folgenden Methoden auf ein Kontaktpaar geprüft:
1. Überschneidung der Kinder mittels Bounding Volumes. Überschneiden sich beide Kinder
nicht, dann Abbruch der Prozedur.
2. Status = „wahr“:
a) Prüfe Kinder auf Nachbarschaft (siehe Abschnitt 3.4.3 im 2. des Algorithmus) und
setze neuen Status.
b) Status = „wahr“: Hole Richtungsvektoren beider Kinder und prüfe auf gemeinsame
Richtungsvektoren durch logischen UND-Operator. Bei Fund eines gemeinsamen
Richtungvektors Abbruch der Prozedur.
3. Vergleiche Anzahl der Elemente von Kindern mit der Bedingung:
Elementanzahl linkes Kind > Elementanzahl rechtes Kind
• Bedingung erfüllt und linkes Kind ist kein Blatt, gehe zu 1. in aktueller Prozedur
und überprüfe:
– linkes Kind vom aktuellen linken Kind, aktuelles rechtes Kind und aktueller
Status;
– rechtes Kind vom aktuellen linken Kind, aktuelles rechtes Kind und aktueller
Status.
• Bedingung erfüllt und linkes Kind ist ein Blatt: Beide Kinder sind Blätter und somit
ein gefundes Selbstkontaktpaar.
• Bedingung nicht erfüllt und rechtes Kind ist kein Blatt, gehe zu 1. in aktueller
Prozedur und überprüfe:
43
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
– aktuelles linkes Kind, linkes Kind vom aktuellen rechten Kind und aktueller
Status;
– aktuelles linkes Kind, rechtes Kind vom aktuellen rechten Kind und Status.
• Bedingung nicht erfüllt und rechtes Kind ist ein Blatt: Beide Kinder sind gefundenes
Selbstkontaktpaar.
Im nachfolgenden Abschnitt wird anhand eines Beispiels der Ablauf des Algorithmus nochmals
verdeutlicht.
3.5.1 Beispiel: Belastung einer Dose
Belastet man zum Beispiel ein Rohr oder eine Dose mit einer Last F , wie es in Abbildung
3.27 (a)2 dargestellt wird, beginnt sich der Körper zu deformieren und zu falten. Durch diese
Deformation entstehen Selbstkontaktregionen. In diesem Beispiel wird so eine Kontaktregion
(Abb. 3.27 (b)) mit dem zuvor beschriebenen Selbstkontaktsuchalgorithmus auf Selbstkontakt
untersucht.
(a)
F
(b)
5
4
6
3
1
2
10
11
9
7
8
Abbildung 3.27: (a) Deformation einer Dose durch Last F und zugehörige diskretisierte Kontaktregion (b) als Modell
Im ersten Schritt wird der Bottom-Up-Baum der zu untersuchenden Kontaktregion mittels des
Face-Clustering-Algorithmus 3.3.2 aufgebaut. Desweiteren werden zu jedem Knoten (T-Node)
des Baumes die zugehörigen Richtungsvektoren berechnet. Somit erhält man folgenden Baum
und die zugehörigen Richtungsvektoren wie er in Abbildung 3.28 dargestellt wird.
2
Bildquelle: http://www.smokestars.de/after-party-aschenbecher-getrankedose-mustard.html
44
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
21
Musterrichtungsvektoren
19
20
17
18
12
1
13
2
3
14
4
5
15
6
7
8
16
9
10
11
Abbildung 3.28: Bottom-Up-Baum der Kontaktregion aus Abb. 3.27 (b) mit den zugehörigen
Richtungsvektoren an jedem T-Node
Zeitgleich werden zu jedem erzeugten Knoten und somit zu jedem Face, die zughörigen Bounding Volumes erzeugt, siehe nachfolgende Abbildung 3.29.
45
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
21
19
20
14
17
7
18
14
13
12
16
7
15
5
4
6
3
1
2
10
11
9
7
8
Abbildung 3.29: Bounding Volumes des Kontaktproblems zu jeder Ebene des Bottom-Up-Baums
aus Abb. 3.28
46
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
Anschließend beginnt die Suche nach den Kontaktpaaren mit dem in Abschnitt 3.5 beschrieben
Selbstkontaktsuchalgorithmus. Dazu werden alle Knoten des zuvor erzeugten Baums durchlaufen. Hierfür beginnt der Algorithmus bei den Blätter und arbeitet sich bis zu der Wurzel (root)
des Baums durch. Da ausser beim Knoten 21 alle Knoten Richtungsvektoren besitzen, bricht
die Kontaktpaarsuche bei all diesen Knoten sofort ab, da das Krümmungskriterium aus Abschnitt 3.4.2 erfüllt wird und somit kein Kontakt stattfinden kann (Vgl. Abschnitt 3.5). Somit
beginnt der eigentliche Kontaktpaarsuchalgorithmus erst beim Knoten 21. Hierfür, wird wie in
Abschnitt 3.5 beschrieben, der Baum aus Abb. 3.28 von Knoten 21 bis zu den Blättern durchgearbeitet, siehe Abb. 3.30. Zunächst wird an jedem Knoten auf Überschneidung („I“) geprüft
und dann auf Nachbarschaft („N“). Bei der Überprüfung der Nachbarschaft (siehe Abb. 3.31,
wird wieder der Baum von dem aktuellen Paar aus von oben nach unten, also zu den Blättern, untersucht: Überschneidung („I“), gemeinsame Ecken („E“), Vergleich der Elemente und
setzen des Nachbarschaftsstatus (Vgl. Abschnitt 3.4.3). Wird als Nachbarschaftstatus „wahr“
an den Kontaktsuchalgorithmus zurückgeben, wird wie bei den Paaren (14-20) und (14-7) auf
gemeinsame Richtungsvektoren geprüft. Werden gemeinsame Vektoren gefunden, bricht der
Algorithmus bei dem aktuellen Paar ab. Letztendlich erhält man folgende Selbstkontaktpaare:
(2-10), (1-11), (2-11) und (3-10) (siehe grünumrandeter Kasten in Abb. 3.30).
Vergleicht man die beiden Bäume aus Abb. 3.30 und Abb. 3.31 fällt auf, dass der Ablauf
der beiden Algorithmen sehr ähnlich ist, insbesonders bei der Überschneidungsprüfung der
Bounding Volumes, Vergleich der Anzahl der Element, Prüfung auf Blattknoten und somit
das rekursive Verhalten bei der Auswahl der nächsten Paaren. Ausserdem fällt auf, dass bei
der Untersuchung von möglichen Kontaktpaaren bei dem Nachbarschafttest immer wieder die
gleichen Abfragen durch das Abarbeiten des Baums von oben nach unten durchgeführt werden.
Beispiel, bei der Prüfung des Kontaktpaars (19-20) wird bei dem Nachbarschafttest der ganze
Baum aus Abb. 3.31 durchlaufen. Beim Kontaktpaar (17-20) wird, ab hier wieder der ganze
Baum durchgeprüft. Da jedoch der Algorithmus nicht die Ergebnisse dieser Nachbarschaftsüberprüfung speichert, werden Ebene für Ebene die gleiche Abfragen wiederholt ohne das sich
die Ergebnisse sich ändern.
47
48
Abbruch
Blatt:
15
Ele:
>
12
I N
Abbruch
Blatt:
7
Ele:
>
17
I N
15
Abbruch
Blatt:
8
Ele:
>
13
I N
Ele:
4>2
Blatt: 17
I N
17
Richtungsvektoren
Ele: Anzahl Elemente
N : Nachbarschaftstest
I : Intersektion
Falsch/Inaktiv
Wahr/Aktiv
STATUS:
17
20
15
13
9
Ele:
>
I N
Abbruch
Blatt:
9
4
Ele:
>
9
Abbruch
Blatt:
I N
Ele:
2>0
Blatt: 13
I N
3
Ele:
2>2
Blatt: 15
I N
13
Ele:
4>5
Blatt: 20
I N
17
18
10
Ele:
>
10
12
16
10
Kontaktpaar
11
11
Kontaktpaar
16
11
Kontaktpaar
10
10
Kontaktpaar
Ele:
>
Abbruch
Blatt:
I N
11
Ele:
>
Abbruch
Blatt:
13
I N
10
4
16
Ele:
2>2
Blatt: 16
13
I N
Ele:
2>0
Blatt: 13
13
I N
Ele:
0>0
Blatt: 10
3
I N
Ele:
4>2
Blatt: 17
17
I N
Ele:
0>0
Blatt: 11
2
I N
Ele:
2>0
Blatt: 12
12
I N
Ele:
0>0
Blatt: 11
1
I N
Ele:
2>2
Blatt: 16
I N
Ele:
0>0
Blatt: 10
2
I N
Ele:
2>0
Blatt: 12
Abbruch
Blatt:
I N
1
12
I N
Ele:
4>4
Blatt: 18
I N
20
Ele:
6>5
Blatt: 19
19
I N
Abbruch
Blatt:
7
Ele:
>
14
I N
14
20
Ele:
>
Richtungsvektoren
Blatt:
I N
18
Ele:
>
Abbruch
Blatt:
I N
14
Richtungsvektoren
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
Abbildung 3.30: Ablauf des Suchalgorithmus nach Algorithmus aus Abschnitt 3.5
49
Ele:
>
I E
Abbruch
Blatt:
15
12
Abbruch
Blatt:
7
Ele:
>
17
I E
15
Abbruch
Blatt:
8
Ele:
>
13
I E
Ele:
4>2
Blatt: 17
I E
17
Ele: Anzahl Elemente
E: Gemeinsame Ecken
I : Intersektion
Falsch/Inaktiv
Wahr/Aktiv
STATUS:
17
20
15
13
9
Ele:
>
I E
Abbruch
Blatt:
9
4
Ele:
>
9
Abbruch
Blatt:
I E
Ele:
2>0
Blatt: 13
I E
3
Ele:
2>2
Blatt: 15
I E
13
Ele:
4>5
Blatt: 20
I E
17
18
10
Ele:
>
10
12
16
10
11
11
3
13
4
13
16
11
Ele:
0>0
Blatt: 10
I E
10
Ele:
>
Abbruch
Blatt:
I E
11
Ele:
>
Abbruch
Blatt:
13
I E
10
I E
Ele:
>
7
Abbruch
Ele:
2>0
Blatt: 13
10
Ele:
2>2
Blatt: 16
I E
Blatt:
I E
Ele:
4>2
Blatt: 17
I E
5
17
16
Ele:
0>0
Blatt: 11
2
I E
Ele:
2>0
Blatt: 12
12
I E
Ele:
0>0
Blatt: 11
1
I E
Ele:
2>2
Blatt: 16
I E
Ele:
0>0
Blatt: 10
2
I E
Ele:
2>0
Blatt: 12
Abbruch
Blatt:
I E
1
12
I E
Ele:
4>4
Blatt: 18
I E
20
Ele:
6>5
Blatt: 19
19
I E
7
Ele:
2>0
Blatt: 14
14
I E
20
7
Ele:
0>0
Blatt: 7
I E
6
Ele:
2>5
Blatt: 20
14
I E
Abbruch
Blatt:
18
Ele:
>
14
I E
3.5 Algorithmus zur Suche von Selbstkontaktpaaren
Abbildung 3.31: Nachbarschaftstest nach Algorithmus aus Abschnitts 3.4.3
3.6 Master- und Slave-Sortieralgorithmus
3.6 Master- und Slave-Sortieralgorithmus
Mit dem Suchalgorithmus aus Abschnitt 3.5 werden bis jetzt nur die Selbstkontaktpaare aufgefunden ohne die Zuordnung zu Master- und Slave-Elementen. An diesen Paaren wird später die
Mortar-Projektion und somit das Mortar-Segment gefunden (siehe Puso und Laursen (2004)
und Yang u. a. (2005) für mehr Details) und an ihnen die Mortar-Integrale, die Abstandsfunktion, die Kontaktspannungen und die Mortar-Kontaktsteifigkeitsmatrizen berechnet. Wie
auch immer, ist ein Sortierung notwendig. Würde man die Selbstkontaktpaareelemente willkürlich zu Master- oder Slave-Elemente sortieren, könnten Elemente die zu mehreren anderen
Elementen in Kontakt stehen, sowohl als Master- als auch als Slave-Elemente definiert werden
(siehe Abb. 3.32).
Patch1
S
M
M
S M
M
S
S
S
M
Patch2
Abbildung 3.32: Willkürliche Definiton von Master-Slave-Elementen an zwei Patches: (Doppelpfeil beschreibt ein Kontaktpaar)
Außerdem kann sich bei jeder Iteration die Definition der Elemente ändern. Dadurch ändert
sich bei jeder Iteration ständig das Spannungsfeld zwischen den Paaren und die NewtonRaphson-Iteration konvergiert erschwert.
Für dieses Problem wird ein Facet-Sorting-Algorithmus eingesetzt, der ähnlich des Face-Clustering-Algorithmus aus Abschnitt 3.3 ist. Die Paare der Kontaktsuche werden dabei wie nachfolgten beschrieben sortiert:
1. Aufbau eines zusätzlichen Netzes (Dual Graph).
Im Gegensatz zum Dual Graph beim Face-Clustering-Algorithmus, handelt es sich um
ein entkoppeltes Netz, dass aus mehreren verbundenen Netzen für die zugehörigen Selbstkontaktregionen (Patches) besteht.
2. Iteratives Verbindung aller Dual Edges in den Dual Graphs. Außerdem werden den aufgefundenen ununterbrochenen Elementbereichen (Patch) die jeweiligen Kontaktpaarelemente zugeordnet in den sie sich befinden.
3. Zuordnung von Master- und Slave-Elementen mittels des Durchlaufens der Kontaktpaare
und ihrer Patchzugehörigkeit (siehe Abb. 3.33).
50
3.7 Kosten des Selbstkontaktsuchalgorithmus
Patch1
S
S
M
MM
S
S
M
S
M
Patch2
Abbildung 3.33: Sortierte Kontaktelementpaare nach dem Facet-Sorting-Algorithmus (Doppelpfeil beschreibt ein Kontaktpaar)
Bei k Kontaktelementen in l Kontaktpaaren belaufen sich die Kosten des Facet Sorting Algorithmus auf O(k log k + l).
3.7 Kosten des Selbstkontaktsuchalgorithmus
Die Kosten der Selbstkontaktsuche kann nach Weghorst u. a. (1984) und Yang (2009) wie
folgt berechnet werden:
Kostenanteil der Kontaktsuche für mehrere Flächen bei großen Deformationen
T=
Nv × C v + Ne × C e + Nus × C us + N ue × C ue
N c × C c + N a × C a + N ca × C ca
+
(3.19)
Kostenanteil der Selbstkontaktsuche bei großen Deformationen
mit den Parameter der Kontaktsuche
• Nv : Anzahl Bounding Volume Paare die bzgl. Überschneidung gestestet werden,
• Cv : Kosten des Überschneidungstest der Bounding Volume Paare,
• Ne : Anzahl der Slave-Master-Elementpaare für die, die Mortar Projektion durchgeführt
wird,
• Ce : Kosten des Kontakttest für Slave-Master-Elementpaare,
• Nus : Anzahl der Bounding Volumes der T-Nodes ohne Blätter, die aktualisiert werden
müssen,
• Cus : Aktualisierungskosten der Bounding Volumes an den T-Nodes ohne Blätter,
• Nue : Anzahl der Bounding Volumes der Blätterknoten, die aktualisert werden müssen,
• Cue : Aktualisierungskosten der Bounding Volumes an den Blätterknoten
und den Parameter der Selbstkontaktsuche
• Nc : Anzahl Teilflächen für dass das Krümmungskriterium angewendet wird,
• Cc : Kosten des Krümmungstests,
51
3.8 Einbindung der Mortar-Selbstkontaktsuche in die Newton-Raphson-Iteration um die Mortar-Selbstkontaktsteifi
• Na : Anzahl der Teilflächenpaare die auf Nachbarschaft untersucht werden,
• Ca : Kosten für jeden Nachbarschaftstest,
• Nca : Anzahl der Nachbarschaftsteilflächenpaare die mit dem Krümmungskriterium getestet werden,
• Cca : Kosten des Krümmungstest für Nachbarschaftsteilflächenpaare.
Die geringsten und somit besten Kosten erhält man bei einer sehr flachen Selbstkontaktfläche
da nur einmal beim Wurzelknoten das Krümmungskriterium angewendet wird. Somit sind
Nv = 0, und die Kosten für ein fast flache Fläche ergeben sich zu
T = Cn + (n − 1) × Cus + n × Cuc = O(n).
(3.20)
3.8 Einbindung der Mortar-Selbstkontaktsuche in die
Newton-Raphson-Iteration um die
Mortar-Selbstkontaktsteifigkeit zu Berechnen
Um die Mortar-Selbstkontaktsteifigkeit in einer Newton-Raphson-Iteration zu Berechnen wird
dabei die Selbstkontaktsuche wie nachfolgend beschrieben eingebunden:
1. Aktualisierung des Bounding Volume Baums basierend auf den Ergebnissen der letzen
Iteration und somit Neuberechnung der Richtungsvektoren mit dem beschrieben Algorithmus in Abschnitt 3.4.2.
2. Durchführung einer globalen Kontaktpaarsuche für die Mortar-Segmente mit den beschrieben Algorithmen in Abschnitten 3.5 und 3.4.3.
3. Sortierung der gefunden Selbstkontaktpaare mit dem Facet-Sorting-Algorithmus wie in
Abschnitt 3.6 beschrieben.
4. Durchführung einer lokalen Kontaktsuche: Projektion der Masterelemente auf ihre zugehörigen Slaveelemente um Mortar-Segmente zu finden.
5. Berechne Mortar-Integrale und Kontaktbedingungen.
6. Entscheidung basierend auf den Kontaktbedingungen und Auswertung an den SlaveKnoten, ob der Körper im Selbstkontakt ist. Wenn nicht, keine Berechnung der Kontaktsteifigkeit notwendig.
7. Berechung der Kontaktsteifigkeit basierend auf den Mortar-Segment-Informationen und
den Linearisierungsdetails nach Yang (2009).
52
4
Implementierung in NumPro
In diesem Kapitel wird das institutseigene FE-Programm „NumPro“ mit dem zuvor vorgestellten Selbstkontaktsuchalgorithmus erweitert. Die Implementierung erfolgt mit der Programmiersprache C ++ . Hierfür wird die Diskretisierung der Mortar-Kontaktsuche mit Finite
Elemente erweitert.
4.1 Allgemeiner Programmablauf
Nachdem das Programm mittels eines Eingabe-File (*.dat), dass das Kontaktproblem beschreibt ausgeführt wurde, werden folgende Schritte ausgeführt:
• Eingabefile einlesen (READ INPUT)
• Ausgabefile für GiD erzeugen (OUTPUT TO GID)
• Diskretisierung des Kontaktproblems (PREPARE DISCRETIZATION)
• Lösen des statischen nichtlinearen Problems (SLOVE STATIC NONLINEAR PROBLEM)
• Berechnung der Kontaktspannungen (CALCULATE CONTACT STRESS)
4.1.1 Eingabefile und Einlesen
Für die Berechnung des Kontaktproblems wird ein Eingabefile (*.dat) benötigt, dass mit „NumPro“ eingelesen wird. In dieser Datei stehen alle notwendigen Geometrien, Materialdaten,
Randbedingungen und Rechenmethoden. Eine Eingabedatei kann z.B. wie folgt aufgebaut
sein:
• Kopf mit Autor und CMake-Anweisungen,
53
4.1 Allgemeiner Programmablauf
• Elementtypen,
• Ausgabe,
• Materialeigenschaften (E-Modul, Querkontrationszahl),
• Raumfunktion für die Last (z.B. linear),
• Zeifunktion,
• Löser (z.B. Dense LU, CCF, Umfpack),
• Controlart (z.B. nichtlineare Rechnung: Anzahl Lastschritte, Laststeigerung, Max. Iterationen, Toleranz Iteration),
• Dirichlet-Randbedingungen,
• Neumann-Randbedingungen,
• Kontaktsuchtyp (z.B. Bounding Volumes und Parameter),
• Slave- und Master-Knoten,
• Anzahl und Koordinaten der Knoten,
• Elementanzahl und zugehörige Knoten.
Eingelesen wird das Eingabefile über ../src/io/Input.cpp
4.1.2 Ausgabe der Daten und Ergebnisse
Alle Rechenergebnisse werden durch ../src/io/GiD.cpp in zwei Daten (*.msh) und (*.res) ausgegeben. Zunächst wird die Ausgangsgeometrie der Rechnung ausgeschrieben und anschließend
nach jedem Lastschritt die Koordinaten, Verschiebungen und Spannungen. Ausgewertet, können diese Dateien mittels des Programms „GiD“.
4.1.3 Diskretisierung
Mittels der Datei ../src/contact/Contact_discretizations/Contact_Dis_FE.cpp und der Funktion self_node_ele_3D() werden aus den eingelesen Slave- und Master-Knoten, die in diesem
Fall die FE-Knoten der Kontaktregion sind, die Contact-Surface-Elemente erzeugt. Hierbei
werden sie mit ihren Nachbarn verpointet. Desweiteren werden die Flächen eines Elements,
die aus FE-Knoten bestehen als Contact-Surface-Element gespeichert. Außerdem, wird zu jedem Contact-Surface-Knoten die Normale berechnet und die Eckknoten aller Contact-SurfaceElemente werden auf gleiche angrenzende Contact-Surface-Elemente untersucht und als Nachbarelemente gespeichert. Die Aufgaben von Contact-Surface-Node und Contact-Surface-Element werden in den nachfolgenden Abschnitten genauer beschrieben.
54
4.2 Überblick der eingebetteten Klassen des Selbstkontaktsuchalgorithmus
4.1.4 Statisch lineare Berechnung
Bei der statisch linearen Berechnung laufen verschiedene, verschachtelte Schleifen ab, die wie
im nachfolgenden Ablaufdiagramm beschrieben sind.
Schleife über alle Lastschritte λ = λ + ∆λ
Newton-Schleife: norm ≤ tol
Schleife über alle Elemente - Elastizität
- Berechnung lokaler nichtlinearer Steifigkeitsmatrix
- Berechnung lokaler innerer Kräfte
- Einsortierung in globale Steifigkeitsmatrix KT
- Einsortierung in globale inneren Fint und äusseren Fext
- FHG-Reduktion: Streichung von Zeilen und Spalten mit Verschiebungsrandbedingungen
Schleife über alle Slavepunkte - Kontakt
- Berechnung des Abstands gN
- Berechnung der Zusatzterme für NTS-Kontakt
- Berechnung der Steifigkeitseinträge: K
- Berechnung der rechten Seite: F
- Eintrag der Kontakteinträge in globale Steifigkeitsmatirx und rechte Seite
- Lösen des linearen Gleichungssystems
- Rücksortierung der ∆D auf Knotenfreiheitsgrade: Dk+1 = Dk + ∆D
√
- Berechunung der Norm: norm = ∆D · ∆D
Schleife über aller Slavepunkte
- Berechnung neuer Klaffung
- Setzung neuer Aktivität
- Berechnung Kontaktspannungen
- Output schreiben
4.2 Überblick der eingebetteten Klassen des
Selbstkontaktsuchalgorithmus
In diesem Abschnitt wird auf die Klassen des Selbstkontaktsuchalgorithmus eingegangen. Dabei wurde „Num Pro“ mit folgenden Klassen erweitert:
55
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
• Contact_Surface_Node,
• Contact_Surface_Element,
• Face,
• Self_contact.
Da in „Num Pro“ die Diskretisierung und die Berechnung auf Basis von Master- und SlaveKnoten und -Elemente implementiert ist und somit auch alle Funktionen getrennt nur in
der jeweiligen Klasse stehen, wurden zwei neue Klassen Contact_Surface_Node.h und Contact_Surface_Element.h benötigt, die die benötigten Funktionen von Master und Slave vereinen und es ermöglicht alles bzgl. der FE-Knoten zu berechnen. Somit sind die beiden Klassen
als übergeordnete Schnittstelle über Master und Slave einzuordnen und man hätte die Möglichkeit das Master- und Slave-Funktionen erben könnten. Eine weiter zusätzliche Klasse ist
Face.h. Sie wird benötigt für den Aufbau des Bottom-Up-Baums. Es werden hier somit alle Beziehungen zwischen den Knoten des Baums gespeichert. Bei der Klasse Self_contact.h
handelt es sich um die Hauptklasse der Selbstkontaktsuche. Hier werden alle Funktionen der
Selbstkontaktsuche implementiert.
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und
ihre Methoden
4.3.1 Contact_Surface_Node
Wie schon zuvor erwähnt, handelt es sich um eine übergeordnete Klasse, die die Funktionen
der Slave- und Master-Knoten vereinigt. Hierbei werden folgende Daten gespeichert
• Zeiger auf zugehörigen FE-Knoten,
• Liste mit Zeigern auf zugehörige benachbarte Contact-Surface-Elemente,
• normierte Normale am Knoten,
• Tangenten.
Die hauptsächlichen Funktionen dieser Klasse sind:
• Rückgabe von gespeicherten Parameter,
• Rückgabe der aktuellen Koordinaten des Knotens,
• Berechnung der Normalen und Tangenten am Knoten.
56
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
4.3.2 Contact_Surface_Element
Auch bei Contact_Surface_Element handelt es sich um eine Klasse der beiden vereinigten
Slave- und Master-Klassen. Wobei hier insbesonders die Funktionen des Slaveelements übernommen wurden. Folgende Daten werden in dieser Klasse gespeichert:
• Nachbarschaftsliste: Zeiger auf Nachbar-Contact-Surface-Elemente,
• Nachbarschaftliste bzgl. Kante,
• Zeiger auf FE-Element,
• Liste mit Zeiger auf zugehörige Contact-Surface-Knoten,
• Normale in Contact-Surface-Elementmitte,
• Projizierter Flächeninhalt und Umfang des Contact-Surface-Elements.
Bei den Funktionen handelt es sich insbesonders um die Berechnung von Contact-SurfaceElementgrössen wie physikalische Koordinaten, Richtung der Kante, Ansatzfunktionen, Normalen, Tangenten, projizierter Flächeninhalt und Umfang des Elements. Ausserdem kann auf
Parameter zugegriffen und gespeichert werden. Diese Funktionen werden hauptsächlich für die
Kostenfunktion bei der Kantenkontraktion beim Baumaufbau benötigt.
4.3.3 Face
Bei der Klasse Face handelt es um die einzelnen Flächen, die durch die Kantenkontraktion
entstehen. Und da jede Fläche einem Knoten im Baum entspricht, wird hier auch der benötigte
Baum aufgebaut. Die Klasse Face speichert somit folgende Daten:
• Listen zu zugehörigen Contact-Surface-Knoten und -Elementen,
• Zeiger auf linkes, rechtes Kind und auf Elternteil,
• Liste auf die Nachbarschaften (Faces) entlang der Kante,
• Kantenlänge und Kosten zum Nachbarface,
• Listen auf Nachbarschafts-Faces der beiden Kinder,
• Anzahl Subsurfaces,
• Projizierter Flächeninhalt, Umfang und Normale des Faces,
• Logische Liste mit Richtungsvektoren,
• Liste mit zugehörigen Master-Faces für die Sortierung der gefundenen Kontaktpaare.
In dieser Klasse werden also bei der Kantenkontraktion neue Faces erzeugt und angelegt und
die zugehörigen Parameter berechnet und gespeichert.
57
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
4.3.4 Contact_Dis_FE
In der Klasse Contact_Dis_FE wird durch die Funktion self_node_ele_3D() die ContactSurface-Knoten und Contact-Surface-Elemente mittels eingelesener FE-Elemente und zugehörigen Knoten erstellt. Desweiteren werden die aktuellen Elemente in einer Nachbarschaftsliste
vom Elementknoten gespeichert, die Normalen an allen Contact-Surface-Knoten berechnet
und Nachbarelemente bestimmt. Ausserdem wird die Suche nach Selbstkontaktpaaren gestartet über die Methode self_contact_run() aus der Klassse Self_contact.
4.3.5 Self_contact
Bei der Klasse Self_contact handelt es sich um die eigentliche Klasse der Selbstkontaktpaarsuche. Hier werden folgende Daten gespeichert:
• Zeiger auf Kontakttyp,
• Liste mit Zeiger auf die Faces,
• Liste mit Zeiger auf die Bounding Volumes,
• Liste mit Zeiger auf die Kontaktelementpaare,
• Liste mit Patches für die Zuordnung zum Master- und Slaveelement.
Desweiteren werden hier die Musterrichtungsvektoren für das Krümmungskriterium definiert.
Bei den Methoden handelt es sich um die in Kapitel 3 beschriebenen Algorithmen. Der Kontaktsuchalgorithmus durchläuft dabei verschiedene, verschachtelte Schleifen, die wie in den
nachfolgenden Ablaufdiagrammen sehr grob beschrieben werden:
Face-Clustering Methode
• contact_surface_element(): Erzeugung von Faces durch Contact-Surface-Elemente.
Schleife über alle Contact-Surface-Elemente
- Erzeugung von Faces durch Contact-Surface-Elemente
- Erzeugung von Bounding Volumes für jedes Face
58
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
Schleife über alle Faces
Schleife über alle Nachbarn entlang Kante
- Erzeugung neuer Nachbarschaftliste bzgl. Kante
- Speicherung Nachbar-Face zu jedem Face
Schleife über alle Knoten des Faces
Schleife über alle Knoten des Nachbar-Faces
- Prüfung auf gemeinsame Knoten
- Berechnung und Speicherung Kantenlänge zum Nachbar-Face
• Kantenkontraktion: Berechnung von Kosten mittels calc_costs() und Zusammenfügen
von Faces mit merge_faces()
Schleife über alle Faces bis ein Face keine Nachbar mehr besitzt
Kostenberechnungsschleife: Schleife über alle Faces die keine Elternknoten besitzen
Schleife über alle Nachbarn des Faces
- Berechnung Durchschnitt der Eckpunkte v¯
- Berechnung Kovarianz
- Berechnung Eigenwerte und Eigenvektoren
- Bestimmng Normale n: Eigenvektor mit kleinsten Eigenwert
- Berechnung Abstand d
- Berechnung Ebenheitsmetrik Efit
- Bestimmung Anzahl Contact-Surface-Elemente
- Berechnung Umfang und projizierte Fläche mit dem aktuellen Nachbarn
- Berechnung Kosten E
Schleife über Kosten aller Faces
- Bestimmung Face und Nachbar mit Kostenminimum für Kantenkontraktion
- Erzeugung neues Face durch Kantenkontraktion von Face und Nachbar
- Zeiger auf Kinder und Eltern setzen
- Neues Bounding Volumes für neues Face erzeugen
- Nachbarschaftliste für neues Face erzeugen
- Berechnung Umfang des neuen Face
59
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
Krümmungskriterium
Bei der Methode compute_vs() werden mittels einer Schleife über aller Faces die Richtungsvektoren bestimmt:
Schleife über alle Faces
- Berechnung Richtungsvektoren für Blätterknoten (Faces)
- Berechnung Reichtungsvektoren für restliche Knoten (Faces) mittels UND-Operator
Selbstkontaktsuche
Die Suche der Selbstkontaktpaare wird über die rekursive Methode detect_self_contact(Face*
face) implementertiert.
60
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
Schleife über alle Faces:
- Suche Kontakt, wenn beim Knoten (Face) kein Richtungsvektor exisitiert und kein Blattknoten ist
- Rekursiver Aufruf der Methode mit linken Kind
- Rekursiver Aufruf der Methode mit rechtem Kind
Überprüfung des Kontaktpaars: linkes und rechtes Kind auf Kontakt mittels Methode
detect_contact(Face* child_left, Face* child_right, bool adjacent)
- Prüfung auf Überschneidung mit Bounding Volumes
Rekursive Nachbarschaftsprüfung der Kinder und Rückgabe des Nachbarschaftsstatus
- Prüfung auf Überschneidung mit Bounding Volumes
- Prüfung auf gemeinsame Eckpunkte
- Vergleich: Anzahl von Elementen beider Kinder:
–> wenn Elemente linkes Kind > Elemente rechtes Kind und linkes Kind kein
Blattknoten ist:
– Weitersuche mit Kontaktpaar: linkes Kind von linkem Kind, rechtes Kind
– Weitersuche mit Kontaktpaar: rechtes Kind vom linkem Kind, rechtes
Kind
–> wenn beide Kinder Blattknoten sind: Kontaktpaar gefunden
–> wenn Elemente linkes Kind < Elemente rechtes Kind und rechtes Kind
kein Blattknoten ist:
– Weitersuche mit Kontaktpaar: linkes Kind, linkes Kind vom rechten Kind
– Weitersuche mit Kontaktpaar: linkes Kind, rechtes Kind vom rechten
Kind
–> wenn beide Kinder Blattknoten sind: Kontaktpaar gefunden
- Prüfung auf gemeinsame Richtungsvektoren wenn Nachbarschaftsstatus = TRUE:
–> wenn Richtungsvektoren existieren: Abbruch
- Vergleich: Anzahl von Elementen beider Kinder:
–> wenn Elemente linkes Kind > Elemente rechtes Kind und linkes Kind kein Blattknoten ist:
– Weitersuche mit Kontaktpaar: linkes Kind von linkem Kind, rechtes Kind
– Weitersuche mit Kontaktpaar: rechtes Kind vom linkem Kind, rechtes Kind
–> wenn beide Kinder Blattknoten sind: Kontaktpaar gefunden
–> wenn Elemente linkes Kind < Elemente rechtes Kind und rechtes Kind kein
Blattknoten ist:
– Weitersuche mit Kontaktpaar: linkes Kind, linkes Kind vom rechten Kind
– Weitersuche mit Kontaktpaar: linkes Kind, rechtes Kind vom rechten Kind
–> wenn beide Kinder Blattknoten sind: Kontaktpaar gefunden
61
4.3 Klassenbeschreibung des Selbstkontaktsuchalgorithmus und ihre Methoden
Slave-Master-Sortierung
• Zerlegung Kontaktpaare in Patches
Schleife über Liste Kontaktpaare
Schleife über Nachbarschaftsliste des zu vergleichenden Faces aus Kontaktpaarliste
- Bestimmung von Nachbarschaften
- Bei Nachbarschaft: Erzeugung oder Zuordnung zum jeweiligen Patch
- Löschen doppelter Einträge
• Patchsortierung: Master-Slave-Sortierung
Schleife über alle Patches
Schleife über Einträge in Kontaktpaarliste
- Vergleich Einträge der Patches mit Einträge aus Kontaktpaarliste (seperater Vergleich der Kinder)
- Zuordnung von Master oder Slave
62
5
Zusammenfassung und Ausblick
Ziel dieser Arbeit war es, die in der Arbeit von Yang (2009) beschriebene Selbstkontaktsuchalgorithmus zu untersuchen und in das institutseigene FE-Programme zu implementieren.
Hierfür wurden zunächst die Grundlagen zum Mortar-Selbstkontakt erarbeitet. Anschließend
wurde auf die Bestimmung des Kontakts mittels Bounding Volumens eingegangen. Dazu wurden unterschiedliche Bounding Volume Typen mit ihren Vor- und Nachteile erörtert und ihre Überscheidungsmethoden vorgestellt. Wie schon in der Einleitung erwähnt, ist es nicht
immer möglich die Kontaktränder bei komplexen Deformationszuständen vor der Untersuchung in Master- und Slaveränder zuteilen. Deshalb wird die Zuordung des Kontaktrandes
in Master- und Slaveränder während der Rechnung durchgeführt. Dazu wird ein effizienter
Kontaktsuchalgorithmus benötigt der schnell und effizient diese Kontaktpaare findet. Da aber
Selbstkontakt meistens nur in kleinen Bereichen der Körpergeometrie sattfindet wird mittels
der Bounding Volume Hierachie (BVH) diese kleine Fläche rekursiv in kleinere Flächen gesplittet. Hierzu werden die rekursiv erzeugten Flächen durch sogenannte T-Nodes (Knoten)
und ihre Bounding Volumes in einer Baumstruktur beschrieben. Statt eines Top-Down-Baums,
die Zerlegung in immer kleinere Flächen, wird die Bottom-Up-Aufbaustrategie für die Selbstkontaktsuche verwendet. Dazu wird mittels des beschriebenen Face-Clustering-Algorithmus
die kleinsten Flächen zu immer grösseren Flächen gruppiert, bis die gesamte Kontaktregion
durch eine große Fläche dargestellt werden kann. Somit wird der Bounding Volume Baum
nicht von der Wurzel zu den Blättern aufgebaut, sondern von den Blättern ausgehend. Grosser Vorteil dieser Aufbaustrategie ist die Robustheit gegenüber der Selbstüberlappung. Bei
dem Face-Clustering-Algorithmus wird ein Verfahren benutzt, dass aus der Computergraphik
stammt und verwendet wird um kontrolliert den Netzdetailgrad eines modellierten 3D-Körpers
zu reduzieren, ohne dass sich das Aussehen des Körpers ändert. Hierfür wird ein zusätzliches
Netz erzeugt und über das vorhandene FE-Netz gelegt. Anschließend werden mittels einer
Kostenfunktion inkrementell die Kanten des zusätzlichen Netzes gelöscht und somit angrenzende Flächen gruppiert. Die Kostenfunktion gewährleistet dabei, dass ein ausgewogener Baum
erzeugt wird und basiert auf einer Ebenheitsmetrik.
63
5 Zusammenfassung und Ausblick
Nachdem die Kontaktregion mittels eines Bounding Volume Hierachie beschrieben wurde, muss
noch geklärt werden wie die Selbstkontaktsuche optimiert werden kann. Statt nur durch Intersektion von Bounding Volumes kann die Kontaktpaarsuche durch weitere Kriterien optimiert
werden. Hierfür wurde das Selbstkontaktproblem nochmals genauer betrachtet und es wurde festgestellt das Kontakt nur stattfindet bei einer gekrümmten Fläche. Deshalb wird über
ein Krümmungskriterium alle flachen Oberflächen in der Kontaktregion für die Kontaktsuche
ausgeschlossen. Dazu wird mit Hilfe von Richtungsvektoren, die je nach Genauigkeit varieren
können, und einer Oberflächennormale an einem betrachteten Punkt in der Kontaktoberfläche das Kriterium formuliert. Somit kann mit diesem Kriterium alle „fast ebenen“ einzelnen
Elementflächen als auch zwei Nachbarschaftsflächen bei der Selbstkontaktsuche ausgeschlossen werden. Ein weiteres Problem der Selbstkontaktsuche, das Auftreten von „Kontakt“ durch
Nachbarschaftselemente kann mit dem Krümmungskriterium jedoch nicht eliminiert werden.
Es kann nur feststellen ob Selbstkontakt zwischen Nachbarflächen stattfindet, jedoch nicht
welche Flächen in Nachbarschaft liegen. Deshalb wird ein Nachbarschaftstest eingeführt, der
diesen „Kontakt“ bei der Selbstkontaktsuche durch diese Flächen ignoriert. Dazu wird eine rekursive Prozedure benutzt, die das angebliche Kontaktpaar mittels Überschneidung der
Bounding Volumes, gemeinsame Eckknoten, Vergleich der Elementanzahl der zu untersuchenden Knoten und Feststellung auf Blätterknoten untersucht. Dazu wird ausgehend von dem
aktuell untersuchten Kontaktpaar der Bounding-Volume-Baum durchgearbeit und der Nachbarschaftsstatus an den Kontaktsuchalgorithmus übermittel. Wird eine Nachbarschaft festgestellt, wird nochmals auf gemeinsame Richtungsvektoren geprüft und bei vorhandensein dieser,
wird dieses Kontaktpaar bei der Suche ignoriert.
Nachdem der Kontaktsuchalgorithmus durch die Eliminierung des Nachbarschaftsproblems
optimiert wurde, wurde noch anhand eines Beispiels die Kontaktsuche erläutert. Hierbei fällt
insbesonders auf, dass der Nachbarschaftstest und der Selbstkontaktsuchalgorithmus sich sehr
ähnlich sind und Prüfungen wie die Überschneidung der Bounding Volumes doppelt geprüft
wird. Außerdem fällt auf, dass beim Nachbarschaftstest immer wieder die gleichen Paare überprüft werden aufgrund der Abarbeitung des Baums von oben nach unten. Da aber die Ergebnisse des Test nicht gespeichert werden, könnte man eventuell durch Aufbau eines zusätzlichen
Baums mit Speicherung der Ergebnisse am jeweiligen T-Node, wie in Abb. 3.31 dargestellt verbessert werden. Somit könnte man sich, insbesonders bei grösseren Datensätzen, mehrmalige
gleiche Prüfungen und Abfragen ersparen und die Kontaktsuche beschleunigen.
Das Problem mit der Zuordnung des Kontaktpaars zu den jeweiligen Slave- und Masterelementen wird über einen weiteren Sortieralgorithmus gelöst. Dabei werde die gefundenen Kontaktpaare auf gegenseitige Nachbarschaften untersucht. Alle aneinanderliegenden (benachbarten)
Elemente werden in einem Patch gespeichert und die Zuordnung der Patches mittels der Kontaktpaare dem Slave- oder Masterrand zugeordnet.
Für die Implementierung dieses Selbstkontaktsuchalgorithmus in das institutseigene FE-Programm wurde zum grundlegenden Verständins des Programmablauf die einzelnen Klassen
erklärt und mittels Strukturgramm erläutert.
64
Literaturverzeichnis
[Ericson 2005]
Ericson, C.: Real-Time Collision Detection. Elsevier, San Francisco, 2005
[Garland u. a. 2001] Garland, M.; Willmott, P.; Heckbert, P: Hierachical Face Clustering on
Polygonal Surfaces. (2001)
[Puso und Laursen 2004] Puso, M.; Laursen, T.A.: A mortar segement-to-segment contact
mehtod for large deformation solid mechanics. In: Computer Methods in Applied Mechanics
and Engineering 193 (2004), S. 601–629
[Volino und Magnenant-Thalmann 2000] Volino, P.; Magnenant-Thalmann, N.: Virtual Clothing - Theory and Practice. Springer Verlag, Heidelberg, 2000
[Weghorst u. a. 1984] Weghorst, H.; Hooper, G.; Greenberg, D.: Improved computational
methods for ray tracing. In: ACM Transactions on Graphics 3 (1984), S. 52–69
[Wikipedia 2013] Wikipedia: Garland-Heckbert-Algorthmus. 2013. – URL http://de.
wikipedia.org/wiki/Garland-Heckbert-Algorithmus/
[Wikipedia 2014]
Raytracing/
Wikipedia: Raytracing. 2014. – URL http://de.wikipedia.org/wiki/
[Willmott 2000] Willmott, A.J.: Hierachical Radiosity with Multiresolution Meshes, Carnegie
Mellon University, Dissertation, 2000
[Willner 2003] Willner, K.: Kontinuums- und Kontaktmechnanik. Springer Verlag, Berlin
Heidelberg, 2003
[Yang 2009] Yang, B.: Mortar Finite Element Methods for Large Deformation Contact
Mechanics. VDM Verlag Dr. Müller, Saarbrücken, 2009
65
[Yang und Laursen 2007] Yang, B.; Laursen, T.A.: A large deformation mortar formulation
of self contact with sliding. In: Comput. Methods Appl. Engrg. 197 (2007), S. 756–772
[Yang u. a. 2005] Yang, B.; Laursen, T.A.; Meng, X.: Two dimensional mortar contact
methods for large deformation frictional sliding. In: International Journal for Numerical
Methods in Engineering 62 (2005), S. 1183–1225
Document
Kategorie
Seele and Geist
Seitenansichten
64
Dateigröße
2 423 KB
Tags
1/--Seiten
melden