Adaptive Echtzeit–Simulation von Stoff und Haaren Diplomarbeit im

Transcrição

Adaptive Echtzeit–Simulation von Stoff und
Haaren
Diplomarbeit im Fach Informatik
vorgelegt von
Anne-Kathrin Braun
Institut für Computervisualistik
Arbeitsgruppe Computergrafik
Abteilung für Virtuelle und
Erweiterte Realität
Prüfer: Prof. Dr. –Ing. Stefan Müller
Betreuer: Dipl. –Math. Alexander Rettig
Januar 2005
2
Eidesstattliche Erklärung
Hiermit erkläre ich an Eides statt, dass die vorliegende Arbeit selbständig verfasst wurde
und keine anderen als die angegebenen Quellen und Hilfsmittel verwendet wurden. Die
Arbeit wurde bisher in gleicher oder ähnlicher Form keiner anderen Prüfungsbehörde
vorgelegt und auch nicht veröffentlicht.
Koblenz, den 31.01.05
Unterschrift
3
Danksagung
An dieser Stelle möchte ich mich bei allen bedanken, die mich bei der Anfertigung
dieser Arbeit unterstützt haben.
Mein Dank geht an die Mitarbeiter der Abteilung für Virtuelle und Erweiterte Realität
des Fraunhofer IGD, und ganz besonders an meinen Betreuer Alexander Rettig.
Bedanken möchte ich mich auch bei meinem Prüfer Stefan Müller von der Universität
Koblenz-Landau für Anregungen und Ratschläge.
4
Inhaltsverzeichnis
1
Einleitung
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Anforderungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Übersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Grundlagen
2.1 Physikalische Grundlagen . . . . . . .
2.1.1 Kinematik . . . . . . . . . . . .
2.1.2 Dynamik . . . . . . . . . . . .
2.2 Simulationsmodelle . . . . . . . . . . .
2.2.1 Kinematische Modelle . . . . .
2.2.2 Kontinuum–Mechanik Modelle
2.2.3 Partikelsysteme . . . . . . . . .
2.3 Numerische Integration . . . . . . . . .
2.3.1 Explizites Euler–Verfahren . . .
2.3.2 Runge–Kutta–Verfahren . . . .
2.3.3 Verlet–Verfahren . . . . . . . .
2.3.4 Implizites Euler–Verfahren . . .
2.4 Kollisionserkennung und -antwort . . .
7
7
7
8
.
.
.
.
.
.
.
.
.
.
.
.
.
9
9
9
11
13
13
13
15
16
18
19
20
21
22
3
Adaptive Strukturen
3.1 Einführung in adaptive Strukturen . . . . . . . . . . . . . . . . . . . .
3.2 Level of Detail für Kleidung . . . . . . . . . . . . . . . . . . . . . . .
3.3 Level of Detail für Haare . . . . . . . . . . . . . . . . . . . . . . . . .
25
25
26
30
4
Konzept und Design
4.1 Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Dynamiksimulation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
37
39
45
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
INHALTSVERZEICHNIS
6
5
Realisierung
5.1 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Tests und Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
47
50
59
6
Zusammenfassung und Ausblick
6.1 Zusammenfassung . . . . . . . . . .
6.2 Ausblick . . . . . . . . . . . . . . . .
6.2.1 Optimierung und Ergänzung .
6.2.2 Weiterführende Überlegungen
61
61
63
63
63
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A Bilder
B Algorithmen
B.1 Explizite Euler-Integration . . . . . . . . . . . . . . . . . .
B.2 Velocity-Verlet-Integration . . . . . . . . . . . . . . . . . .
B.3 Implizite Euler-Integration . . . . . . . . . . . . . . . . . .
B.3.1 Jacobi-Matrizen berechnen . . . . . . . . . . . . . .
B.3.2 Hilfsfunktion für Multiplikation mit Jacobi-Matrizen
B.3.3 Methode der konjugierten Gradienten . . . . . . . .
B.4 Algorithmus zu Konstruktion des Zylinders . . . . . . . . .
65
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
73
73
73
74
74
75
75
76
Kapitel 1
Einleitung
1.1
Motivation
Ein interessantes Forschungsgebiet im Bereich der Computergrafik ist die Entwicklung von virtuellen Charakteren - so genannten Avataren. Das Ziel bei der Entwicklung von Avataren ist es die Mensch-Maschine-Kommunikation zu verbessern, indem
sie als persönliche Dialogpartner agieren. D.h. ein virtueller Charakter soll von seiner
realen Umwelt beeinflusst werden können. Dies bietet eine völlig neue Qualität der
Interaktion. Ein Gebiet von großer Bedeutung für den Einsatz von solchen Avataren
ist der Bereich der Bildungssoftware. Durch einen personifizierten Tutor gewinnt das
System nachweislich an Effizienz und führt somit zu einem nachhaltigen Lernerfolg.
Doch nicht nur in der Bildungssoftware können solche Charaktere zum Einsatz kommen. Möglichkeiten bieten sämtliche interaktive Anwendungen insbesondere im Bereich E-Business.
Bei der Animation von Avataren sind besonders die Bewegung von Haaren und Kleidung von großer Bedeutung. Denn Haare und Kleidung tragen maßgeblich dazu bei,
den Charakter glaubwürdig und realistisch erscheinen zu lassen und somit die Akzeptanz des Anwenders zu gewinnen.
1.2
Anforderungen
Der Avatar soll sich auf das Verhalten eines menschlichen Benutzers möglichst natürlich
und angemessen verhalten. Die Bewegungsabläufe müssen ad hoc passieren, eine vorher modellierte Punktemenge, die in aufeinander folgenden Keyframes eine Animationssequenz bilden, sind nicht möglich. Die Simulation kann also nicht wie bei manuell
erstellten und langwierig gerenderten Figuren wie in der Filmindustrie, oder durch Avatare, welche durch Bewegungssensoren an realen Schauspielern gesteuert werden, erfolgen. Eine authentisch wirkende Lösung ist eine Simulation basierend auf den Gesetzen
7
8
KAPITEL 1. EINLEITUNG
der Physik, was bedeutet, dass die Bewegung für jedes Frame neu berechnet werden
muss.
Das stellt eine große Herausforderung an die Geschwindigkeit des Systems. Denn durch
die Interaktivität mit dem Benutzer muss die Simulation in Echtzeit erfolgen. Die Darstellung der Bewegung und deren Berechnung muss so schnell erfolgen, dass sie zur
Laufzeit erfolgen kann, ohne die Animation zu stark zu beeinträchtigen. Eine echtzeitfähige Animation erhält man bei ca. 25 Frames pro Sekunde (fps).
Bei der physikalisch-basierten Simulation der Haare und Textilien ist die Berechnung
der Verformungen und Bewegungen durch zeitliche Integration der Bewegungsgleichung sowie das Erkennen und Behandeln von Kollision besonders zeitaufwendig. Es
gilt daher Lösungen zu finden, um die Simulation zu beschleunigen und echtzeitfähig
zu machen.
1.3 Übersicht
Es gibt diverse Möglichkeiten der Anforderung der Echtzeitfähigkeit gerecht zu werden.
Eine einfache Möglichkeit wäre eine grobe Modellierung der Oberfläche, um so die Anzahl der Berechnungen zu verringern, was allerdings die optische Qualität vermindert.
Eine Erweiterung davon wäre mit verschiedenen Darstellungsstufen zu arbeiten, mit
so genannten Level of Details. Damit wird die Rechenzeit reduziert, ohne dass allzu
große Verluste in der Darstellung entstehen. In der Untersuchung von solchen adaptiven
Strukturen und Simulationsmodellen beim Animieren von Haaren und Kleidung liegt
der Schwerpunkt dieser Diplomarbeit. Ferner wird ein Konzept erarbeitet, bei dem die
Untersuchungsergebnisse einfließen. Das Konzept wird abschließend in der Programmiersprache C++ umgesetzt.
Aus oben genannten Gründen erfolgt die Simulation durch Nachbildung physikalischer Gesetzmäßigkeiten, d.h. Anwenden von Gesetzen der Mechanik insbesondere der
Kinematik und der Dynamik. Im nächsten Kapitel werden kurz die für die Simulation
relevanten physikalischen Grundlagen aufgeführt sowie Modelle beschrieben, um diese abzubilden. Des weiteren werden einige Integrationsverfahren vorgestellt, die nötig
sind, um die Animation zeitlich voranzubringen. Das dritte Kapitel behandelt verschiedene adaptive Modelle zur Beschleunigung von Kleidung und Haaren und zeigt den
aktuellen Stand der Technik auf diesem Bereich. Wie ein adaptives Modell realisiert
werden kann, wird im vierten und fünften Kapitel am Beispiel von Haarsimulation beschrieben. In Kapitel vier wird das Konzept vorgestellt. Die Implementierung und die,
unter Zuhilfenahme von OpenSG und der VR-Umgebung Avalon, entstandenen Ergebnisse werden in Kapitel fünf präsentiert.
Kapitel 2
Grundlagen
In diesem Kapitel werden die Grundlagen beschrieben, die für die physikalisch-basierte
Simulation nötig sind. Ganz grundlegend ist hierbei die verwendete Physik und deren
Modellierung. Im Abschnitt Numerische Integration wird der Teil der Mathematik beschrieben, der nötig ist, um die Animation in Bewegung zu bringen. Abschließend wird
die Problematik der Kollisionsbehandlung aufgegriffen und Techniken zur Kollisionserkennung und -antwort vorgestellt.
2.1
Physikalische Grundlagen
Der Teil der Physik, der für die Simulation von deformierbaren Materialien von Bedeutung ist, ist die Mechanik. Genauer gesagt die Kinematik, die sich allgemein mit
Bewegungsvorgängen der Körper beschäftigt, und die Dynamik, die die Ursachen dafür
untersucht. Ein Körper wird idealisiert als materieller Punkt mit einer Masse m verstanden.
2.1.1
Kinematik
Die beiden wichtigen Größen in der Kinematik sind Geschwindigkeit v( ms ) und Beschleunigung a( sm2 ). Allgemein ist die Geschwindigkeit v die Strecke s die in einer Zeit
t zurückgelegt wurde.
∆s
(2.1)
∆t
Für eine infinitesimal kurze Zeitspanne drückt man die Geschwindigkeit durch einen
Differentialquotienten nach der Zeit t aus, und erhält
v=
v = limt→∞ ∆t
9
ds
∆s
=
= ṡ
∆t
dt
(2.2)
KAPITEL 2. GRUNDLAGEN
10
Geometrisch kann man sich die Geschwindigkeit als Steigung der Kurve im WegZeit-Diagramm vorstellen.
Abb. 2.1: Weg-Zeit-Diagramm mit entsprechendem Geschwindigkeits-Zeit-Diagramm
Als Beschleunigung bezeichnet man die Geschwindigkeit innerhalb einer Zeitspanne mit
∆v
a=
(2.3)
∆t
Der Differentialquotient lautet
a = limt→∞ ∆t
∆v
dv
=
= s̈ = v̇
∆t
dt
(2.4)
Geometrisch kann man die Beschleunigung als Steigung der Kurve im GeschwindigkeitZeit-Diagramm deuten.
Abb. 2.2: Geschwindigkeits-Zeit-Diagramm mit entsprechendem BeschleunigungsZeit-Diagramm
Für den in dem Fall der Materialsimulation auftretenden Dreidimensionalität wird
der Punkt im Raum durch einen Ortsvektor r(t) beschrieben, der vom Koordinatenursprung zum Ort des betreffenden Punktes zum Zeitpunkt t führt mit


x(t)


r(t) =  y(t) 
z(t)
(2.5)
2.1. PHYSIKALISCHE GRUNDLAGEN
11
Den Weg, den der Punkt im Raum verfolgt, wird als Bahnkurve bezeichnet. Die Ortsvektoren zu den unterschiedlichen Zeiten bilden diese ab.
Der Geschwindigkeitsvektor lautet


ẋ
∆r
dr  
v = limt→∞ ∆t
=
=  ẏ  = ṙ(t)
∆t
dt
ż
(2.6)
der immer tangential zur Bahnkurve liegt.
Abb. 2.3: Bahnkurve mit tangentialem Geschwindigkeitsvektor
Der Beschleunigungsvektor ist analog die
nach der Zeit und somit

ẍ
˙
dr 
=  ÿ
a=
dt
z̈
2.1.2
Ableitung des Geschwindigkeitsvektors


 = r̈(t)
(2.7)
Dynamik
Die Bewegungen, mit denen sich die Kinematik beschäftigt, werden durch Kräfte verursacht. Die Dynamik beschäftigt sich mit diesen und unterteilt sie in interne Kräfte,
12
welche das Material zusammenhalten, und externe Kräfte, welche von außen wirken.
Diese Kräfte verändern den Zustand eines Körpers bzw. verändern dessen Bewegung.
Newton hat die Gesetzmäßigkeiten, die diese Bewegungen beschreiben wie folgt formuliert.
Newtonsche Axiome: (aus [6])
Axiom 1: Trägheitsgesetz: Jeder Körper behält seine Geschwindigkeit nach Betrag und
Richtung so lange bei, wie er nicht durch äußere Kräfte gezwungen wird, seinen
Bewegungszustand zu verändern.
Axiom 2: Aktionsgesetz: Die zeitliche Veränderung der Bewegungsgröße, des Impulses
p = mv, ist gleich der resultierenden Kraft F . Um eine konstante Masse zu beschleunigen, ist eine Kraft F erforderlich, die gleich dem Produkt aus Masse m
und Beschleunigung a ist. ⇒ F = ma
Axiom 3: Wechselwirkungsgesetz: (actio = reactio) Wirkt ein Körper 1 auf einen Körper
2 mit der Kraft F12 , so wirkt der Körper 2 auf Körper 1 mit der Kraft F21 ; beide
Kräfte haben den gleichen Betrag, aber entgegengesetzte Richtungen ⇒ F12 =
−F21
Die wichtigen Größen der Dynamik sind folglich Masse m (kg) und Kraft F (N).
Es gibt verschiedene Kräfte, die auf einen Massepunkt einwirken können. Eine externe Kraft ist die Schwerkraft mit F = mg (mit g = 9,81 sm2 ). Neben der Schwerkraft
zählt auch die Reibungskraft zu den externen Kräften. Die Reibungskraft und speziell
in diesem Fall der Luftwiderstand ist definiert mit
F = −Dv 2
(2.8)
, mit D als Luftwiderstandskoeffizient. Zu den internen Kräften gehören die Elastische
Kraft oder auch Federkraft sowie die Dämpfungskraft. Die Federkraft ist definiert mit
F = (|xij | − L ∗ F K)
(2.9)
, wobei L die Länge der Feder in Ruhelage, xij die Verschiebung mit xij = xj − xi und
F K ist die Federkonstante ist. Dieses Gesetz nennt man auch das Hook’sche Gesetz.
Die Federkonstante gibt die Steifheit der Feder an
Die Dämpfungskraft ist definiert mit
Fd1 = (v2 − v1 ) ∗ |xij | ∗ D
(2.10)
,wobei D die Dämpfungskonstante ist und Fd1 = −Fd2 ist.
Die Fähigkeit, die Feder beim Nachlassen der Verformungskraft wieder in die ursprüngliche
Form zurückzuführen, nennt man Elastizität.
2.2. SIMULATIONSMODELLE
2.2
13
Simulationsmodelle
Das geometrische Modellieren ist die Grundlage für die Berechnung des physikalischgeometrischen Verhaltens. Es werden kinematische und physikalisch-basierte Modelle
unterschieden (s. Tabelle 2.1). Erstere werden in der Literatur oft als passiv bezeichnet,
weil die Elemente bzw. Segmente, aus denen sich das Modell zusammensetzt, nicht
miteinander interagieren [5]. Aktiv sind dagegen alle physikalisch-basierten Modelle.
Kinematische Modelle
Cantilever-Beam-Modell
Physikalisch-basierte Modelle
Kontinuum-Mechanik-Modelle
Partikelsysteme
Finite-Elemente-Modell (FEM)
Masse-Feder-System
Finite-Differenzen-Modell (FDM)
Tabelle 2.1: Verschiedene Simulationsmodelle
Zu den kinematischen Modellen gehört das Cantilever-Beam-Modell [14], welches
sich gut zur Modellierung von Haaren eignet. Die physikalisch-basierten Modelle, welche im Gegensatz zu den kinematischen Modellen die Gesetze der Physik abbilden, werden in zwei Kategorien unterteilt. Zum einen gibt es die stetigen Kontinuum-MechanikModelle, zu denen die Finite-Elemente-Modelle und die Finite-Differenzen-Modelle
gehören. Auf der anderen Seite gibt es die Partikelsysteme, zu denen Masse-FederSysteme zählen.
Im folgenden werden diese Modelle kurz vorgestellt.
2.2.1
Kinematische Modelle
Beim Cantilever-Beam-Modell, als Beispiel für ein kinematisches Modell, wird das
Haar in i Segmente gi unterteilt. Wirkt die Schwerkraft auf das Haar, resultiert das Bied2 y
gemoment M mit dx
2 = −M/(E + I). Dabei steht E für den Young Modulus, welcher
das Verhältnis von Druck zu Spannung ausdrückt und I für das zweite Flächenmoment.
Die Verschiebung nach y muß nun für jedes Segment berechnet werden und zwar rekursiv (vgl. Abb. 2.4). Die Richtung des zuletzt gebogenen Segmentes gibt die x-Achse
vor. Anhand dieser x-Achse wird die Verschiebung nach y berechnet und dieser Wert
auf das letzte ∆y addiert. Mit dem neuen Verschiebevektor wird das aktuelle Segment
gebeugt.
2.2.2
Kontinuum–Mechanik Modelle
Für stetige Modelle, wie die Kontinuum-Mechanik-Modelle, benutzt man stetige Ausdrücke in Form von Lagrangschen Gleichungsmodellen. Dabei erfolgt eine Diskreti-
14
Abb. 2.4: Biegevorgang beim Cantilever-Beam-Modell
sierung in Elemente, d.h. die Bewegungsgleichung wird auf jedes infinitesimal kleine
Oberflächenelement angewendet. Terzopoulos‘ [5] grundlegende Arbeit für die Simulation von Kleidung basierte auf der Vereinfachung der Elastizitäts-Theorie. Die Lagrangsche Bewegungsgleichung
Ã
δ
δr
µ
δt
δt
!
+γ
δξ(r)
= f (r, t)
δr
(2.11)
mit der Position r von Partikel a zur Zeit t, der Dichte µ des Partikels a, der Dämpfungsdichte γ und der äußeren Kraft f (r, t). ξ(r) ist die Funktion, welche die Energie der
Deformation mißt.
Kontinuum-Modelle bieten die Möglichkeit das Material durch zwei Konstanten,
statt wie bei Masse-Feder-Systemen durch eine, zu beschreiben. Die Konstanten sind
der Young Modulus E (s. 2.2.1) und der Poisson-Koeffizient v, welcher die Reaktion
des Materials orthogonal zur Deformationsrichtung mißt.
Um die Lösung der partiellen Differentialgleichung zu approximieren, wird die Methode der Finiten Elemente (FEM) oder die Methode der Finiten Differenzen (FDM)
verwendet.
Bei dem Finite-Differenzen-Modell werden die Ableitungen durch die finiten Differenzen
δr
rt+∆t − rt−∆t
=
δt
2∆t
2
rt+∆t − 2rt + rt−∆t
δ r
=
2
δt
∆t2
(2.12)
(2.13)
ersetzt. Die Methode führt allerdings im Falle eines unstrukturierten Netzes zu Problemen. Um diese zu umgehen werden stattdessen Finite-Elemente-Modelle benutzt. Entsprechend der Elastizitätstheorie wird dabei die Kraft, die auf ein Element angewendet
wird, vom Nachbarelement entnommen oder umgekehrt an das Nachbarelement weitergegeben. Dadurch erhält man zwar eine akkurate Modellierung, aber die Berechnung ist
2.2. SIMULATIONSMODELLE
15
sehr zeitintensiv.
2.2.3
Partikelsysteme
Bei den Partikelsystemen wird dagegen nicht das absolute Materialvolumen betrachtet,
wie bei den stetigen Modellen, sondern bei diesen Modellen wird das Material zu einer
Menge interagierender Massepunkte im Raum diskretisiert. Dadurch wird der Rechenaufwand stark reduziert. Durch Bewegung der einzelnen Massepunkte wird das Modell
deformiert.
Ein Partikelsystem besteht aus zwei Teilen. Den Partikeln und den Einheiten, die
Kräfte auf die Partikel ausüben. Bei einem Masse-Feder-System sind das eine Menge
von Massepunkten und die dazugehörigen Federn. Der Massepunkt selbst besitzt eine
Masse, Position und Geschwindigkeit. Die Bewegung des Materials ergibt sich aus der
Bewegung der Massepunkte.
Bei einem Masse-Feder-System werden die einzelnen Massen netzartig angeordnet,
z.B. mit m × n für Kleidung oder mit m × 1 für Haare. Die Massepunkte werden durch
Federn verbunden, welche ihrerseits keine Masse besitzen und eine Ruhelänge größer
als Null haben müssen. Es gibt verschiedene Federtypen, d.h die Massen können auf
unterschiedliche Art und Weise verbunden werden. Man unterscheidet Strukturfedern,
Scherfedern und Biegefedern (vgl. Abb. 2.5).
Abb. 2.5: Unterschiedliche Federtypen: Strukturfedern (grün), Scherfedern (rot) und
Biegefedern (blau)
Die Bewegung des Modells erfolgt durch das Newtonsche Bewegungsgesetz (s. voriges Kapitel). Die Gleichung F = ma wird dabei unabhängig für jedes Partikel integriert. Eine natürlich-wirkende Elastizität entsteht durch Austausch der Federkräfte, die
16
dem Hook’schen Gesetz folgen.
Ein großer Vorteil von Masse-Feder-Modellen gegenüber anderen Systemen ist die
einfache Implementierung. Durch die Diskretisierung auf wenige Massepunkte nimmt
die Zahl der Berechungen, im Vergleich zu den Kontinuum-Mechanik-Modellen, ab.
Durch die Diskretisierung werden allerdings auch die Ergebnisse unpräziser.
Bei Masse-Feder-Systemen besteht die Möglichkeit durch Ändern der Federparameter,
wie der Dämpfungs- oder Federkonstante, die Dynamik zu beeinflussen. Dabei muß
man allerdings aufpassen, dass die Federsteifigkeit nicht zu hoch gesetzt wird, denn
sonst wird das System instabil. Diese Instabilität ist die Folge von der sogenannten
Steifheit von Differentialgleichungen (s. S. 17).
2.3
Numerische Integration
Um eine Animation zu erhalten, muss das Modell zeitlich voran gebracht werden. Der
zentrale Aspekt der physikalisch - basierten Simulation ist das Lösen der Bewegungsgleichung in Form einer Differentialgleichung.
Eine Differentialgleichung ist eine Gleichung, die die Funktion und deren Ableitung in
Bezug zueinander setzt. Es werden gewöhnliche und partielle Differentialgleichungen
(DGL) unterschieden. Bei einer gewöhnlichen DGL hängt die Funktion von nur einer
unabhängigen Variablen ab, im Gegensatz zu den partiellen DGLs. Bei physikalischen
Simulationen ist dies immer die Zeit t.
Die Art der Differentialgleichung, die gelöst werden muss, hängt von der Wahl der Bewegungsgleichung ab. Da gibt es zum einen die Newtonsche Bewegungsgleichung (s.
S. 11) und die Lagrangsche Bewegungsgleichung (s. S. 13).
Im Rahmen dieser Arbeit bezieht sich das Lösen der Bewegungsgleichung auf die Integration einer gewöhnlichen Differentialgleichung - der Bewegungsgleichung nach Newton (2. Axiom).
F = ma = mr̈(t) = f (t, ṙ)
(2.14)
Diese Gleichung muss entlang einer Zeitentwicklung numerisch gelöst werden.
Um eine Differentialgleichung 2. Ordnung mit ẍ = f (t, ẋ) anwenden zu können,
muss sie durch Einführen von Hilfsvariablen auf ein System 1. Ordnung reduziert werden. Bei der Bewegungsgleichung geschieht dies durch Einführen der Geschwindigkeit.
Man erhält:
Ã
!
Ã
!
∆x
vn
(2.15)
=h
∆v
M −1 f (xn , vn )
2.3. NUMERISCHE INTEGRATION
17
Für die Lösung bzw. für die Stabilität des Systems ist die Wahl der Anfangswerte
sehr wichtig. Bei Gleichungen erster Ordnung muss nur eine Anfangsbedingung definiert werden. Das daraus resultierende Problem wird Anfangswertproblem genannt:
ẋ = f (t, x(t)) mit x(t0 ) = x0
Das bedeutet: starte an der Stelle t0 zu dem Wert x0 unter der Bedingung x(t0 ) = x0 .
Bezogen auf die Bewegungsgleichung ist die Bedeutung: starte an der Stelle t0 und folge den Geschwindigkeitsvektoren (vgl. Abb. 2.6).
Abb. 2.6: Anfangswertproblem
Die Bewegungsgleichung kann mit verschiedenen Methoden integriert werden. Es
werden explizite und implizite Integrationsverfahren unterschieden.
Die explizite Integration birgt Schwierigkeiten hinsichtlich Stabilität bei sogenannten steifen Differentialgleichungen. Bei Masse-Feder-Systemen drückt die Steifheit das
Verhältnis von der Starrheit der Partikelinteraktion bzw. der Härte der Feder zum gewählten Zeitschritt aus. Ein System wird dann als steif bezeichnet, wenn bei gegebener Federhärte bzw. Federkonstante der Zeitschritt inakzeptabel klein gewählt werden muss,
um eine stabile Lösung zu erhalten.
Mathematisch lässt sich dieser Zusammenhang wie folgt ausdrücken: Für einen gegebenen Zeitschritt ∆t und eine gegebene Masse µ existiert eine kritische Steifigkeit Kc ,
über der die numerische Lösung nicht mehr konvergiert.
Das System wird folglich instabil, wenn ∆t größer ist als die natürliche Periode T0 des
Systems (für mehr Informationen s. [15]).
r
T0 ≈ π
µ
K
T 02
=⇒ Kc ≈ µ 2
π
(2.16)
(2.17)
18
Es werden zunächst einige explizite Verfahren vorgestellt.
2.3.1
Explizites Euler–Verfahren
Der Lösungspunkt wird durch den Anfangspunkt (x0 , y0 ) mittels der Tangente approximiert, deren Steigung durch ẏ(x0 ) = f (x0 , y0 ) gegeben ist. An der Stelle x1 := x0 + h
mit der Schrittweite h, erhält man den Näherungswert y1 = y0 + h ∗ f (x0 , y0 ). Führt
man dieses Verfahren analog fort, so erhält man an den äquidistanten Stützstellen die
Näherungen durch die Rechenvorschrift
yk+1 = yk + hf (xk , yk ) + O(h2 )
(2.18)
mit k = 0,1,2,...
Der Fehlerterm O(hn + 1) zur Ordnung n drückt den Verfahrensfehler aus. Das explizite Euler-Verfahren hat den Fehlerterm O(h2 ), ist also eine Methode erster Ordnung.
Die Stabilität und Genauigkeit des Verfahrens hängt stark von der Schrittweite ab.
Nur wenn die Schrittweite ausreichend klein ist, ist das Verfahren ausreichend stabil
und genau.
Abb. 2.7: Explizites Euler-Verfahren: Zu Beginn des Intervalls am Punkt 1) wird die
Ableitung extrapoliert, um den nächsten Funktionswert(Punkt 2) zu finden (aus: [13])
Zur Verbesserung des expliziten Euler-Verfahrens wird der Schrittfehler mit Hilfe
der Taylor-Reihe betrachtet
x(t0 ) = x0 + hẋ(t0 ) +
h3 ˙
hn δ n x
h2
+ ẍ(t0 ) + ẍ(t
0) + . . . +
2!
3!
n! δtn
(2.19)
Dabei erkennt man, dass die Gleichung des Euler-Verfahrens die ersten beiden Terme
x(t0 ) = x0 + hẋ(t0 ) sind.
19
Das bedeutet, dass das explizite Euler-Verfahren nur exakt wäre, wenn diese Terme mit
der ganzen Taylor-Reihe übereinstimmen würden. Die Differenz zwischen dem EulerVerfahren und der Taylor-Reihe ist der Fehlerterm, welcher den Verfahrensfehler mit
der Kumulation der Restableitungen angibt.
Andere Verfahren, wie beispielsweise das Runge–Kutta–Verfahren, versuchen nach
ihrer Ordnung die verbleibenden Fehlerterme zu eliminieren. So besitzen das RungeKutta-Verfahren 2. Ordnung einen Fehlerterm von O(h3 ) und das Runge-Kutta-Verfahren
4.Ordnung einen Fehlerterm von O(h5 ).
2.3.2
Runge–Kutta–Verfahren
Das Runge–Kutta–Verfahren 2. Ordnung entspricht der Taylor-Reihe
x(t0 ) = x0 + hẋ(t0 ) +
h2
+ ẍ(t0 ) + O(h3 ).
2!
(2.20)
Das Verfahren besteht konkret aus drei Schritten:
1. Berechnen des Euler-Schritts k1 = hf (xn , yn )
2. werte f am Mittelpunkt aus k2 = hf (xn + h2 , yn +
k1
)
2
3. nächster Schritt mit Hilfe des Mittelpunktwerts yk+1 = yn + k2 + O(h3 )
Abb. 2.8: Runge-Kutta-Verfahren 2. Ordnung: Aus der Ableitung des Punktes zu Beginn
des Intervalls (1) wird ein Punkt bei der Hälfte des Intervalls bestimmt (2). Die Ableitung an diesem Punkt führt zum nächsten Funktionswert (3), usw. mit den Punkten (4)
und (5). (Aus [13])
Das Runge–Kutta–Verfahren 4. Ordnung entspricht der Taylor-Reihe
20
x(t0 ) = x0 + hẋ(t0 ) +
h2
h3 ˙
h4 ¨
+ ẍ(t0 ) +
+ ẍ(t0 ) +
+ ẍ(t0 ) + O(h5 )
2!
3!
4!
(2.21)
Das Lösen erfolgt mit:
k1 = hf (x0 , t0 )
k1
h
k2 = hf (x0 + , tn + )
2
2
k2
h
k3 = hf (x0 + , tn + )
2
2
k4 = hf (x0 + k3 , t0 + h)
1
1
1
1
x(t0 + h) = x0 + k1 + k2 + k3 + k4 + O(h5 )
6
3
3
6
(2.22)
(2.23)
(2.24)
(2.25)
(2.26)
Abb. 2.9: Runge-Kutta-Verfahren 4. Ordnung: Um von einem Funktionswert zum
nächsten zu kommen werden vier Ableitungen verwendet. Eine am Startpunkt des Intervalls (1), zwei bei der Hälfte (2) und (3) und eine am vorläufig neuen Funktionswert
(4) .(Aus [13])
Es sei allerdings angemerkt, dass höhere Ordnung nicht automatisch höhere Genauigkeit bedeutet. Das Verfahren 4. Ordnung ist dem Verfahren 2. Ordnung nur dann
überlegen, wenn bei doppelter Schrittweite die gleiche Genauigkeit erzielt wird.
Eine Verbesserung erzielt man zum Beispiel durch die adaptive Schrittweitenkontrolle. D.h. entsprechend der Umgebung wird die Schrittweite angepaßt, bei rauher Umgebung mit kleinen Schrittweiten und bei glatten mit großen Schrittweiten. (Genaueres
in [13]).
2.3.3
Verlet–Verfahren
Das Verlet-Verfahren entspricht den Taylor-Reihen
h3 ˙
h2
x(t + h) = x(t) + hẋ(t) + a(t) + ẍ(t) + O(h4 )
2
6
(2.27)
x(t − h) = x(t) − hẋ(t) +
21
h2
h3 ˙
a(t) − ẍ(t)
+ O(h4 )
2
6
(2.28)
(2.29)
Die erste Reihe geht in der Zeit vorwärts und die zweite geht rückwärts. Wenn man die
beiden Reihen zusammen nimmt und nach x(t + h) auflöst, erhält man:
x(t + h) = 2x(t) − x(t − h) + h2 a(t) + O(h4 )
(2.30)
Die Geschwindigkeit läßt sich einfach daraus ableiten zu:
v(t + h) =
x(t + h) − x(t − h)
+ O(h2 )
2h
(2.31)
Es gibt noch eine Verlet-Variante, die explizit die Geschwindigkeit abschätzt. Die
Gleichungen für x(t + h) und v(t + h) lauten:
h2
a(t) + O(h3 )
2
a(t) + a(t + h)
v(t + h) = v(t) + h
+ O(h3 )
2
x(t + h) = x(t) + hv(t) +
(2.32)
(2.33)
a(t + h) läßt sich aus x(t + h) berechnen.
Die implizite Integration ist numerisch stabil und unabhängig von der Schrittweite.
Im Gegensatz zu den expliziten Verfahren bilden bei den impliziten Verfahren nicht die
aktuelle Ableitung die Basis der Integration, sondern die approximierte Ableitung des
Folgezustands.
Die impliziten Verfahren erfordern die Lösung eines linearen Gleichungssystems.
2.3.4
Implizites Euler–Verfahren
Dieses Verfahren ist wesentlich stabiler als das explizite Euler-Verfahren, dafür muß für
jeden Schritt eine iterative Lösung eines linearen Gleichungssystems gewonnen werden.
0
yn+1 = yn + hyn+1
(2.34)
Der erste Schritt ist die Formulierung eines LGS, mit dessen Lösung eine Zustandsänderung bestimmt wird
Ã
∆x
∆v
!
Ã
=h
vn + ∆v
M −1 f (xn + ∆x, vn + ∆v)
!
(2.35)
22


1 0 0

1 
, wobei M die Masse-Matrix ist mit M = m  0 1 0 .
0 0 1
Die Funktion f ist nicht-linear, daher wird sie durch eine Taylor-Reihe erster Ordnung
approximiert.
f (xn + ∆x, vn + ∆v) = fn +
Ã
∆x
∆v
!
Ã
=h
δf
δf
∆x + ∆v
δx
δv
vn + ∆v
−1
M fn + δf
∆x +
δx
(2.36)
!
(2.37)
δf
∆v
δv
bei vn+1 = vn + ∆v und xn+1 = xn + hvn+1 lautet die unterste Reihe mit ∆x =
h(vn + ∆v):
Ã
!
Ã
!
δf
δf
δf
δf
∆v = h M −1 fn + ∆x + ∆v = h M −1 fn + h(v0 + ∆vn ) + ∆v
δx
δv
δx
δv
(2.38)
LGS A∆v = b mit:
"
δf
δx
2.4
und
δf
δv
2 δf
#
"
δf
δf
M −h
−h
∆v = h fn + h vn
δx
δv
δx
#
(2.39)
sind dabei die Jacobi-Matrizen für die Position und die Geschwindigkeit.
Kollisionserkennung und -antwort
Neben der Integration ist die Kollisionsbehandlung der zeitaufwendigste Teil einer Simulation. Die Kollisionsbehandlung geschieht innerhalb eines Simulationsschritts und
besteht aus der Kollisionserkennung, die zuerst erfolgt, und der Kollisionsantwort.
Bei der Kollisionserkennung wird zwischen Kollision mit einem anderen Objekt
und der Selbstkollision unterschieden. Es gibt verschiedene Verfahren für die Kollisionserkennung. Für konvexe Objekte gibt es die Methode der separierenden Ebene. Beim
closest feature tracking wird immer der Minimalabstand zwischen zwei Objekten verfolgt. Oft wird ein Toleranzbereich ε definiert, innerhalb dessen die Kollision bestimmt
wird. Wird der minimale Abstand zwischen dem Objekt und dem Kollisionsobjekt unterschritten, wird eine Kollision angenommen.
Bei einfachen Objekten wird der Abstand zwischen einzelnen Punkten des Objekts bestimmt. Bei komplexeren Objekten wäre das zu aufwendig. Daher werden in diesem
Fall Bounding Volumes (BV) benutzt. Es gibt verschiedene BV-Typen. Abbildung 2.10
zeigt eine kleine Auswahl. Es ist zu beachten, dass komplexere Bounding Volumes zwar
2.4. KOLLISIONSERKENNUNG UND -ANTWORT
23
enger am Objekt anliegen und somit beim Kollisionstest genauer sind, auf der anderen
Seite die Berechnungszeit hierfür steigt. D.h. dass bei der einfachsten Geometrie - der
Kugel - der Kollisionstest am schnellsten geht. Die Approximation eines Objekts durch
eine Bounding Volume Box hängt von der Form des Objekts ab. Da in den meisten
Fällen das Objekt bei einer Kugel am wenigsten eng umhüllt wird, gibt es eine Variante, das Objekt mit mehreren kleinen Kugeln zu umhüllen. Bei diesen Swept Sphere
Volumes (SSV) kann man, wie die in Abbildung 2.11 dargestellt, eine einfache Kugel
benutzen oder für längliche Objekte Line Sphere Volumes oder für eher rechteckige
Objekte Rectangle Sphere Volumes.
Abb. 2.10: Diverse Bounding Volume-Typen. 1) Sphere 2) Axis aligned Bounding Box
(AABB) 3) Discrete oriented Polytop (k-DOP), hier: 8-DOP 4) Oriented Bounding Box
(OBB)
Abb. 2.11: Swept Sphere Volumes: Sphere, Line Sphere Volume und Rectangle Sphere
Volume
Um die Rechenzeit zusätzlich zu minimieren, werden diese Volumes hierarchisch
angeordnet. Allerdings muss der Aufbau der Hierarchie gut überlegt sein, denn im
ungünstigen Fall kann die Traversierung sehr teuer werden. Zur Beschleunigung gibt
es verschiedene Formen der räumlichen Unterteilung wie Uniform Grid, Quadtree, kdTree und bsp-Tree. Das Problem dabei ist, dass sich durch die Deformation die Hierarchie des Baumes bzw. die Ordnung im Grid verändert. Nach jedem Simulationsschritt
24
muss die Hierarchie aktualisiert werden.
Verschiedene Elemente eines Objekts können von einer Bounding Box umschlossen
sein. Ein solches Element könnte ein Partikel oder ein Segment sein(Abb. 2.12). Diese
BVs können nun wieder in einem BV zusammengefasst werden.
Abb. 2.12: Links: Linie aus drei Segmenten in Bounding Volumes. Rechts: Als Bounding Volume Hierarchie
Die Bounding Volume Hierarchie wird nach Auftreten der Kollision traversiert. D.h
tritt bei einem BV eine Kollision auf, werden die Kinder der BV auf Kollision untersucht. Kollidieren die Kindknoten ebenfalls mit einem Objekt, werden deren Kinder
wieder auf Kollision getestet usw.
Bei der Kollisionsantwort ist neben dem Abstand des Partikels zur Oberfläche, der
Kollisionsrichtung und der Oberflächennormale die Beschaffenheit des Materials, ob es
sich also um einen starren oder dynamischen Körper handelt, eine wichtige Information.
Bei starren Körpern wird die Geschwindigkeit einfach auf Null gesetzt und bei dynamischen Objekten wird eine neue Kraft erzeugt oder ein Impuls, um das Objekt vom
Ort des Aufpralls wieder wegzubewegen. Eine Kollisionslösung in der Art kann durch
Penalty-Kräfte umgesetzt werden. Penalty-Kräfte sind zusätzliche symmetrische Kräfte.
Die Aufprallkraft wird durch temporäre Federn repräsentiert, die beim Aufprall zusammengedrückt werden. Um die Kollisionsantwort zu simulieren, wird diese Aufprallkraft
an das Objekt weitergegeben.
Kapitel 3
Adaptive Strukturen
3.1
Einführung in adaptive Strukturen
Die Simulation von Kleidung und Haaren oder allgemein die Simulation von deformierbaren Objekten ist sehr zeitaufwendig. Besonders teuer sind dabei die Dynamiksimulation und die Kollisionsbehandlung. Eine Verbesserung in diesen Bereichen hat für die
Beschleunigung des Systems große Bedeutung.
In dieser Arbeit liegt der Schwerpunkt bei der Beschleunigung der Dynamiksimulation.
Dabei geht es weniger um die numerische Integration an sich, als viel mehr um die Verringerung der Massepunkte. Das Problem ist, dass bei Verringerung der Massepunkte,
also Vergröberung des Modells, zwar die Performanz steigt, die visuelle Qualität aber
abnimmt. Die Lösung dieses Problems liegt bei der Verwendung von so genannten Level of Details (LOD).
Bei LODs werden bei der Simulation mehrere Detaillierungsstufen je nach Situation
benutzt. Somit werden für Regionen ohne Deformation Berechnungen vermieden. Das
Modell wird adaptiv verfeinert, um Details nur in gewissen Regionen zu erzeugen, in
denen sie die visuelle Qualität fördern.
Probleme bzw. Dinge, die bei der Verwendung von LODs zu beachten sind, sind
zum Beispiel die Menge an Detailstufen zwischen denen hin und her gewechselt werden kann. Sind es zu wenige Stufen, kann der Unterschied zu groß sein, so dass die
Adaption der einzelnen Level sehr schwer wird. Mehr Detailstufen bedeutet mehr Modellierungsaufwand.
Es ist zwischen verschiedenen LOD-Arten zu unterscheiden. Es gibt diskrete LODs,
kontinuierliche LODs und ansichtenabhängige (view-dependent) LODs [4]. Bei den diskreten LODs werden verschiedene Varianten des Objekts vorberechnet und zur Laufzeit das entsprechende ausgewählt. Eine weitere Art sind die kontinuierlichen LODs.
25
KAPITEL 3. ADAPTIVE STRUKTUREN
26
Hierbei wird anstatt verschiedener vorberechneter Modelle ein komplexes Modell, welches bereits mehrere Detailstufen enthält, verwendet. Zur Laufzeit wird das gewünschte
Level aus dem Modell extrahiert. Der Vorteil an diesem Modell kann eine bessere
Auflösung sein. Die view-dependent LODs sind eine Erweiterung der kontinuierlichen
LODs. Das passende Level wird entsprechend dem Blickpunkt des Betrachters ausgewählt.
Bei LODs gibt es verschiedene Kriterien, nach denen entschieden wird, wann das
Level gewechselt wird.
• Distanzkriterium: Dieses ist das einfachste und am weiten verbreitetste Kriterium. Dabei wird zu jedem Modell die Entfernung angegeben, bei der das Modell
verwendet werden soll.
• Größe des projizierten Objekts auf dem Bildschirm: Diese Methode ist aufwendiger, da alle Weltkoordinaten des Objekts in Bildschirmkoordinaten umgerechnet
werden müssen.
• Priorität: Wichtige Objekte werden detaillierter dargestellt.
• Wahrnehmungsspezifische Eigenschaften: Das kann die Dauer sein, die ein Objekt
im Blickfeld des Betrachters, oder wie weit ein Objekt am Rande des Blickfelds
des Betrachters liegt.
• Frame-Rate: Es wird die Detailstufe gewählt, die bei vorgegebener Frame-Rate
dargestellt werden kann.
Bei view-dependent LODs können verschiedene Teile des Netzes in unterschiedlicher Auflösung vorliegen. Eine hierarchische Repräsentation in Form eines Baumes
(Bin-, Quad-, Octree usw.) bietet sich daher an. Im Zusammenhang mit dem Wechsel
des Detaillevels, nicht nur bei view-dependent LODs, kann es zu Artefakten kommen,
so genannten popping-effects.
In den beiden folgenden Abschnitten soll ein Überblick verschafft werden, wie die Technik des Level of Detail bei der Haar- und Stoffsimulation angewendet werden kann.
3.2
Level of Detail für Kleidung
LODs können bei deformierbaren Materialien, sowohl bei Masse-Feder-Systeme als
auch bei Kontinuum-Modellen, zum Einsatz kommen. Kontinuum-Modelle bieten den
Vorteil, dass die Beibehaltung von Parametern, wie Steifheit oder Dichte, beim Wechsel
in ein anderes Level weniger Schwierigkeiten bereitet als bei Masse-Feder-Systemen.
Andererseits lassen sich bei Masse-Feder-Systemen die einzelnen Level einfach über die
3.2. LEVEL OF DETAIL FÜR KLEIDUNG
27
Anzahl der Massepunkte festlegen. An Regionen mit großer Deformation werden dann
entsprechend mehr Massepunkte erzeugt bzw. verwendet, um eine feinere Auflösung in
diesem Bereich darzustellen. So sieht man beispielsweise in Abbildung 3.1, dass am Ort
der Krafteinwirkung ein feineres Mesh verwendet wird als am restliches Körper.
Abb. 3.1: Level of Detail bei deformierbaren Materialien
Eine der ersten Arbeiten, bei der mehrere Detailstufen bei Masse-Feder-Systemen
angewendet wurden, war die von Hutchinson [2]. Die Verfeinerung wird hier erst zur
Laufzeit erzeugt. Um das Mesh zu unterteilen, werden zusätzliche Massepunkte hinzugefügt. Dabei wird eine quadratische Netzzelle in vier kleinere Quadrate unterteilt. Dies
geschieht sobald die einwirkende Kraft das Material so stark verformt, dass die Federn
stärker als ein vorgegebener Winkel gebeugt werden. Eine Unterteilung zur Laufzeit
bedeutet einen zusätzlichen Rechenaufwand bei der Simulation. Außerdem hat man das
Problem, dass die durch die Unterteilung entstehenden irregulären Strukturen die optische Qualität mindern und die Gesamtmasse des Materials während der Simulation
konstant sein muss, um auf verschiedenen Detailstufen die gleichen Ergebnisse zu erhalten. Qualitätsverluste können durch Relaxation oder Remeshing des initialen Netzes
zwar behoben werden, durch den hohen Rechenaufwand wäre die Methode für Echtzeitanwendungen dann allerdings unbrauchbar.
Eine ähnliche Methode wird auch in der Arbeit von Volkov [28] beschrieben. Hier
wird kein quadratisches Netz unterteilt, sondern ein trianguliertes Netz. Die einzelnen Level werden auch nicht getrennt voneinander dargestellt , sondern zur voherigen
Auflösung addiert. In Abbildung 3.2 wird exemplarisch das Netz nach zwei Verfeinerungen dargestellt. LOD 0 ist das Originalnetz. LOD 1 ist die erste Unterteilung und
LOD 2 die zweite. Die verfeinerten Netze werden zum Originalnetz hinzugefügt.
Bei der Unterteilung werden die Dreiecke in drei neue Dreiecke unterteilt. Um Qualitätsverluste, z.B. Artefakte, des Netzes zu vermeiden, werden bei der Verfeinerung
28
Abb. 3.2: Verschiedene LODs und resultierendes Mesh
regelmäßige Dreiecke erzeugt. Dies geschieht, indem bei zwei verfeinerten benachbarten Dreiecken die Kanten gedreht werden (vgl. Abbildung 3.3). Die beiden entstandenen
regelmäßigen Dreiecke werden zu dem nexthöheren Level addiert.
Abb. 3.3: Erzeugung regelmäßiger Dreiecke
Um das Problem der konstanten Massen zu lösen, wird bei der Verfeinerung die
Masse eines Punktes des Levels i gedrittelt. Somit wird ein plausibles Ergebnis erzielt.
In Abbildung 3.4 sieht man an drei Beispielen wie die Verfeinerung des Netzes in Regionen mit großer Deformation aussehen könnte.
Eine andere Möglichkeit besteht darin mit mehreren vorberechneten Ebenen zu arbeiten. Bei diesem Verfahren kann die Qualität des Netzes nach mehreren Unterteilungen nicht verloren gehen.
In [9] wird eine Methode vorgestellt, bei der die Simulation mit mehreren Auflösungen
arbeitet und das initiale Netz nicht rekursiv unterteilt wird. Netze mit unterschiedlicher
Auflösung sind zu bestimmten Zeiten der Simulation in unterschiedlichen Regionen
aktiv. An den Schnittstellen dieser Regionen kommt es zu Überlappungen der Netze
(s. Abbildung 3.5). Der Informationsaustausch an diesen Schnittstellen erfolgt über gemeinsame Knoten.
Wird also eine Region stark deformiert, wird dort eine höhere Auflösung benutzt. Im
Beispiel aus Abbildung 3.5 gibt der korrespondierende Knoten P1 die Verschiebungs-
3.2. LEVEL OF DETAIL FÜR KLEIDUNG
Abb. 3.4: Beispiele aus [28]
Abb. 3.5: Verbindung von zwei Leveln mit ghost-nodes
29
30
werte bzw. Offsets an seine Kinder weiter. P1 wird dann zum ghost-node. Die Verschiebungswerte errechnen sich aus einer linearen Interpolation in Form von Baryzentrischen
Koordinaten.
Abbildung 3.6 zeigt ein Beispiel, wie der Informationsaustausch zwischen den Ebenen
funktioniert. Der Knoten C1 des gröberen Netzes bekommt die Information des Kindtetrahedron mit F1 , F2 , F3 . Dieser Knoten wäre nun kein ghost-node mehr sondern wieder aktiv. Bei einer Verfeinerung des Netzes gäbe das Elterntetrahedron mit C1 , C2 , C3
den Offsetwert an den Kindknoten F1 .
Abb. 3.6: Informationsaustauch zwischen zwei Leveln
3.3
Level of Detail für Haare
Der Haarsimulation liegen andere Simulationsmodelle zu grunde als der Stoffsimulation, wodurch sich die Technik des Level of Detail unterscheidet. Für Haare gibt es
verschiedene Simulationsmodelle. In [23] werden folgende Modelle unterschieden: Partikelsysteme, explizite Modelle, Clustermodelle und Modelle basierend auf volumetrischen Texturen.
Bei expliziten oder Einzelhaarmodellen wird jedes einzelne Haar modelliert. Das Resultat ist sehr realitätsnah, bei ca. 100 000 Haaren beim Menschen allerdings auch sehr
zeitaufwendig.
Das Clustermodell ist nicht viel unrealistischer. Denn wie in der Natur, wo mehrere
Haare durch Kohäsions- und Adhäsionskräfte zusammengehalten werden, werden auch
bei diesem Modell Haarbündel durch Zylinder oder Streifen abstrahiert (s. Abb. 3.7).
Durch diese Vergröberung wird Rechenzeit eingespart.
Im folgenden werden einige Arbeiten basierend auf den Clustermodellen vorgestellt.
Das erste Modell von Kim et al. [27], das vorgestellt wird, verwendet einen hierarchischen Ansatz. Das Haarbündel wird aus einer Skelettkurve mit dazugehöriger Kontur
3.3. LEVEL OF DETAIL FÜR HAARE
31
Abb. 3.7: Clustermodelle: Streifenmodell (links) und Zylindermodell (rechts)
konstruiert. Mit einer Skalier- und Lockenfunktion wird die Strähne in Form gebracht.
Eine Hierarchie wird aufgebaut, indem die Strähne unterteilt wird. Bei der Unterteilung werden Skelette und Konturen für die Kindknoten erzeugt. Die Kindsträhnen werden mit der Formel Nρ skaliert, wobei N die Anzahl der Kinder und ρ den Grad der
Überlappung zwischen den Kindern angibt. Die Positionierung auf der Kopfhaut erfolgt durch Zufallsverteilung. Die einzelnen Kindsträhnen können wieder zu gröberen
Strähnen zusammengefasst werden. In dieser Hierarchie kann auf- und abgestiegen werden, um somit das Detaillevel zu bestimmen.
In einer weiteren Arbeit von Kim et al. [7], dem Adaptive-Wisp-Tree-Verfahren
(AWT), werden die Haarbündel als einfache Zylinder dargestellt. Diese Strähnen werden in weitere Strähnen unterteilt und in einem Baum angeordnet. Die Kinderknoten
können so leicht den Elternsträhnen zugeordnet werden. Der Radius des Zylinders wird
im Falle einer Unterteilung so gewählt, dass im folgenden Schritt die Kinderknoten innerhalb des Zylinders liegen.
Zu Beginn der Simulation ist die gröbste Repräsentation aktiv, also der Wurzelknoten
des Baumes. Die Verfeinerung der Strähne erfolgt nach zwei Kriterien. Ist zum einen
die Beschleunigung, die auf die Strähne wirkt, größer als ein bestimmter Schwellwert
und ist zum anderen der Kindknoten bereits gesplittet, so wird die Strähne unterteilt.
Durch das zweite Kriterium wird erreicht, dass die Strähne von der Spitze zur Wurzel
hin aufgesplittet wird. In Abbildung 3.8 ist der Verfeinerungsprozeß schematisch aufgezeigt. Beim ersten Schritt (ganz links) ist noch die gröbste Auflösung aktiv. Wird nun die
Strähne stark beschleunigt, tritt das zweite Kriterium in Kraft. Da noch keine Kindknoten gesplittet wurden, fängt die Verfeinerung in der Haarspitze an. Beim vierten Schritt
wird nun der zweite Knoten gesplittet, da die Kindknoten bereits gesplittet wurden.
Die Positionen der Kinder werden durch gespeicherte Offsetwerte übertragen, ebenso
wie die Geschwindigkeit. Eine Haarsträhne kann, nachdem sie verfeinert wurde, wieder
vergröbert werden, indem die Kindersträhnen zusammengefasst werden. Die Zusam-
32
Abb. 3.8: Verfeinerung einer Strähne
menfassung erfolgt ebenso nach mehreren Kriterien. Erstens müssen die Kinderknoten
innerhalb des Radius des Elternknotens sein. Zweitens dürfen ihre relativen Geschwindigkeiten nicht über einem bestimmten Schwellwert liegen um gleichmäßige Übergänge
zu erhalten. Und drittens darf auch die Beschleunigung nicht über einem bestimmten
Schwellwert liegen. Sind diese Kriterien erfüllt, wird die Position und die Geschwindigkeit gemittelt und an den Elternknoten gegeben.
In Abbildung 3.9 ist das Verfahren nochmal in einer Übersicht dargestellt.
Wie bereits erwähnt, gibt es mehrere Möglichkeiten Level of Detail anzuwenden.
In der eben vorgestellten Arbeit bezieht sich die Detaillierung auf die Kontrolle der
Animation. Dabei können komplexere Haarbewegung ermöglicht werden, indem die
Kontrollstruktur dynamisch adaptiert d.h. aufgelöst werden.
Bei dem folgenden Verfahren wird zu den Kontrollstrukturen auch die Geometrie dynamisch adaptiert. Ward et al. [17][16] verwenden dazu drei unterschiedliche Haarrepräsentationen: Haarstreifen, Haarzylinder und Einzelhaare (s. Abb. 3.10). Dabei sind
Haarstreifen die gröbste und Einzelhaare die feinste Auflösung.
Jeder Repräsentation liegt ein einheitliches Basisskelett zu grunde. Über dieses Skelett, welches als Masse-Feder-System implementiert wird, wird die Dynamik gesteuert.
Die Anzahl der Massen und Federn des Skeletts entspricht der Anzahl der Segmente des
Haarelements.
Die Adaption der Detailstufen, sowohl der Kontrollstrukturen als auch der Geometrien, erfolgt über eine Hierarchie. Der initiale Haarstreifen bildet das oberstes Level.
Unter Zuhilfenahme einer Quadtree-Datenstruktur wird dieses Basishaar unterteilt und
die Hierarchie vorberechnet. Der Haarstreifen (Strip) wird geviertelt. Diese Unterteilung
geschieht rekursiv für jeden Kindstreifen bis die Breite unter einem Schwellwert liegt.
Ist dies der Fall, wird die nächstfeinere Auflösung gewählt - der Haarzylinder (Cluster).
Abb. 3.9: Adaptive Wisp Tree (AWT) Verfahren
33
34
Abb. 3.10: Drei unterschiedliche Haarrepräsentationen: Haarstreifen, Haarzylinder und
Einzelhaare
Dieser Cluster wird wiederum geviertelt. Die Kindcluster werden auch wieder rekursiv
unterteilt bis der Radius kleiner als ein vorgegebener Schwellwert ist. Als feinstes Level
werden Einzelhaare (Strands) dargestellt. Dabei werden N Einzelhaare zufällig in jedem Cluster verteilt. Die Cluster werden in Quadranten aufgeteilt. Alle Einzelhaare die
in einem Quadranten liegen bilden eine Einzelhaar-Gruppe. Diese Gruppe folgt der Dynamik eines gemeinsamen Skeletts. Jede Einzelhaar-Gruppe wird wieder als Kind in den
Quadtree gehängt und in vier Quadranten unterteilt. Die Hierarchie wird weiterverfolgt
und die Einzelhaar-Gruppen werden solange aufgeteilt, bis die Blätter des Quadtrees
nur noch ein einzelnes Haar besitzen. Abbildung 3.11 zeigt schematisch die entstandene Hierarchie. Die Strip-Hierarchie ist dabei die Hierarchie der Kontrollstrukturen
der Haarstreifen, die Cluster-Hierarchie die der Haarzylinder und die Strand-Hierarchie
ist der Quadtree der Einzelhaarbündel. Alle drei Kontrollstrukturhierarchien bilden die
Hierarchie für die Adaption der Geometrie.
In dem Baum wird sich entsprechend dem erforderlichen Level of Detail auf und
ab bewegt. Ein Wechsel der Hierarchiestufe und somit die Art der Repräsentation hängt
von folgenden Kriterien ab. Erstens wird getestet, ob das Haar überhaupt sichtbar ist.
Zweitens wird gemessen, wie weit das Haar vom Betrachter entfernt bzw. wie viel Platz
das Haar auf dem Bildschirm einnimmt. Und beim dritten Kriterium wird gemessen,
wie stark das Haar in Bewegung ist, also wie groß die externe Kraft ist, die auf das Haar
einwirkt.
Wenn nun die Hierarchieebene gewechselt wird, müssen zur Laufzeit die dynamischen
Zustände der Knoten im Baum ausgetauscht werden. Wenn in der Hierarchie nach oben
35
Abb. 3.11: Schematische Darstellung der Hierarchie der Kontrollstrukturen und unterschiedlichen Geometrien
gegangen wird, werden die Zustände der Kinder an den Vaterknoten gegeben, indem
die Positionen der Kinder gemittelt werden. Wenn in der Hierarchie eine Stufe hinunter
gegangen wird, muss der Knoten sein Zustand an die Kinder verteilen. Um die Positionen der Kinder zu modifizieren, werden Offset-Vektoren verwendet, die beim Aufbau
des Quadtree errechnet wurden.
36
Kapitel 4
Konzept und Design
Nach der theoretischen Auseinandersetzung mit der Technik der adaptiven Simulation,
wird in diesem Kapitel ein Konzept für deren praktische Umsetzung vorgestellt.
Da die Umsetzung von Stoff- und Haarsimulation den Rahmen dieser Diplomarbeit
sprengen würde, beschränkt sich der praktische Teil dieser Arbeit auf die Realisierung
von adaptiver Haarsimulation.
Das umgesetzte Verfahren orientiert sich stark an dem Verfahren von Ward et al.
[17][16], welches im vorherigen Kapitel vorgestellt wurde. Der Vorteil an diesem Verfahren ist, neben der Echtzeitfähigkeit, auch die Verwendung des Level of Detail, nicht
nur für die Kontrollstrukturen, sondern auch für die Geometrie. Es ermöglicht also bei
einer großen Detaillierungsstufe eine Einzelhaarsimulation in Echtzeit, was zu einer
qualitativ besseren Darstellung führt.
Die Simulation von Haaren kann allgemein in drei Aufgaben aufgeteilt werden. Die
Modellierung, die Behandlung der Dynamik und das Rendering. Das Konzept für die
Umsetzung der verbleibenden Aufgaben wird in den folgenden Abschnitten vorgestellt.
4.1
Modellierung
Die Modellierung der Haare ist durch die Auswahl des Verfahrens von Ward vorgegeben: Ein Clustermodell mit Streifen, dem ein Masse-Feder-System zu grunde liegt. Um
die Streifen zu modellieren, wurde das Cinema4D-PlugIn HairDepartment 1 verwendet.
1
www.bgs-group.de/seiten/deframe.html
37
38
KAPITEL 4. KONZEPT UND DESIGN
Abb. 4.1: Cinema4D-PlugIn HairDepartment
4.2. DYNAMIKSIMULATION
4.2
39
Dynamiksimulation
Die Simulation wurde in das VR- und AR-System Avalon2 integriert. Avalon nutzt die
Idee von VRML/X3D und erweitert damit das traditionelle Konzept eines Szenegraphen
für einen Knoten. Die Idee ist nun, das Haarmodell als Avalon-Knoten zu implementieren und so die Vorteile von Avalon zu nutzen.
Die Frisur wird als VRML-Modell eingelesen. Da die eingegebenen Streifen der Frisur
innerhalb der Simulation wieder unterteilt werden müssen, ist es angebracht für jeden
Streifen ein Objekt eines Avalon-Knotens anzulegen.
In dem folgenden Beispiel wird in der VRML-Datei der Avalon-Knoten Skeleton - da
er das Skelett für das Frisurmodell bildet - namens hairs1 eingefügt.
...
DEF Haare Transform{
children[
DEF hairs1 Skeleton{
gravitaton 0 -9.81 0
coord Coordinate { point [
2 4 0,
0 4 0,
1 2 0,
3 2 0,
0 -3 0,
2 -3 0,
2.5 -5 0,
0.5 -5 0
]}
mass 10
maxFactor 20
springconstant 500.0
springdampingconstant 2.0
timestep 0.005
level -1
]
}
...
DEF ts TimeSensor
{
cycleInterval 2
2
www.zgdv.de/avalon
40
loop TRUE
}
...
ROUTE ts.time TO hairs1.time
Aus den Avalon-Knoten werden die initialen Top-Level-Haare, die Wurzelknoten
der hierarchischen Struktur, als Streifen angelegt und unterteilt. Neben Streifen gibt es
noch die Haartypen Zylinder und Einzelhaargruppe. In dem UML-Diagramme 4.2 ist
die Klassenstruktur der einzelnen Haartypen (Streifen, Zylinder und Einzelhaargruppen) dargestellt. Diese werden in den Klassen Strip, Cluster und Strand gespeichert, welche wiederum von der Klasse BaseHair abgeleitet werden.
Jedes Top-Level-Haar enthält ein Masse-Feder-System, das mit den Informationen aus
dem Avalon-Knoten initialisiert wird. Auf Klassenebene enthält die Klasse BaseHair
das Masse-Feder-System in Form der Klasse MyMassSpringSystem welche wiederum die Klassen Mass und MySpring enthält (s. UML-Diagramm 4.3). Aus dem TopLevel-Haar wird während der Initialisierung des Avalon-Haar-Knotens ein Quadtree
aufgebaut. Dabei wird der Streifen entsprechend den definierten Schwellwerten unterteilt (s. S. 57). Die unterteilten Haarknoten werden in der Quadtree-Datenstruktur
gespeichert. Jeder Quadtreeknoten enthält ein Basishaar und Zeiger auf vier weitere
Quadtreeknoten — die Kinder. (s. UML-Diagramm 4.4)
Bei der Traversierung des Baumes müssen die Parameter, wie Position und Geschwindigkeit, von der alten Ebene zur neuen Ebene ausgetauscht werden. Die Funktionen subdivide() und merge() in der Klasse Quadtree splitten bzw. fassen
die Informationen der Eltern- oder Kindknoten zusammen und reichen sie weiter. Beim
Aufteilen der Werte wird die Position des Elternknotens um den Offsetvektor, der beim
Erstellen des Baumes gespeichert wurde, verschoben und an den Kindknoten gegeben.
Beim Aufsteigen im Baum, werden die Positionen gemittelt und als Elternposition gespeichert.
Wie bereits erwähnt, sind die Kriterien für die Verfeinerung der Haarrepräsentation
zum einen die Sichtbarkeit des Haares, dann der Abstand zwischen Betrachter und Haarobjekt und die Größe der einwirkenden Kraft.
Bei der Implementierung werden nur der Abstand und die Krafteinwirkung berücksichtigt.
Diese beiden Kriterien werden zu einem Faktor verrechnet, welcher das neue Level angibt. Ist das neue Level kleiner als das vorherige Level, geht es im Quadtree die entsprechende Differenz in Schritten nach oben und umgekehrt. Der Faktor errechnet sich
aus der Durchschnittsgeschwindigkeit aller Knoten des aktuellen Levels mulipliziert
mit der Distanz des Blickpunkts des Betrachters zur Bounding Box des Haarknotens.
Die Durchschnittsgeschwindigkeit wird berechnet, indem die Integrationsmethode nach
jedem Aufruf die berechnete Geschwindigkeit zurückliefert, welche in dem Skeleton-
41
Abb. 4.2: UML-Diagramm: (a) BaseHair mit abgeleiteten Haartypen Strip, CLuster und
Strand
42
Abb. 4.3: UML-Diagramm: (b) BaseHair mit MyMassSpringSystem und den IntegratorKlassen
43
Abb. 4.4: UML-Diagramm: (c)Quadtree-Klasse die das BaseHair enthält; Masse- und
Feder-Klasse, die zu MyMassSpringSystem gehören
44
Knoten aufsummiert wird.
Bei den Levelübergängen kann es zu so genannten popping-effects kommen, z.B.
ruckartige Übergänge und stockende Bewegungen. Diese Effekte können vermindert
werden, indem getestet wird, ob die Kinderrepräsentationen innerhalb eines bestimmen
Radius des Elternknotens liegen. Um die Masseverteilung im Baum konstant zu halten,
müssen beim Splitten des Masse-Feder-Systems die Massen geviertelt werden. Das ist
nötig, um eine flüssige und richtige Simulation zu erhalten. Außerdem können unterschiedliche Massen zu einer Instabilität des Systems führen.
Eine weitere Entscheidung, die bei der Implementierung getroffen werden muß, ist
die Wahl der Integrationsmethode. In Abschnitt 2.3 wurden bereits einige Verfahren zur
numerischen Integration vorgestellt. Es gibt mehrere Kriterien, die für die Auswahl ausschlaggebend sind. Zum einen ist es sicherlich wichtig zu beachten, in welchem Kontext
die Simulation erfolgt. D.h. was wird sonst noch alles berechnet und wie groß ist der
Anteil der Simulation. Ebenfalls wichtig ist die Größe des Problems, also die Anzahl
der Partikel, die integriert werden müssen.
Bei der Integrationsmethode selbst entscheidet die Komplexität der Methode über die
Rechenzeit. Eine Methode, bei der noch lineare Gleichungssysteme gelöst werden
müssen, wie z.B. bei der impliziten Euler-Integration, ist teurer als eine einfache EulerIntegration. Dieses Argument muß man abwägen gegen die gewünschte Genauigkeit,
also wie oft die Methode ausgeführt werden muß bzw. ausgeführt werden kann. Um so
kleiner der Zeitschritt um so genauer die Integration. Der Zeitschritt repräsentiert den
Grad der Diskretisierung der Funktion. Allerdings ist dieser Grad limitiert. Nach unten hin ist eine Grenze, da die Simulation bei zu kleinen Schrittweiten nicht mehr in
Echtzeit läuft. Und nach oben hin liegt die Grenze bei der numerischen Stabilität. Wird
also der Zeitschritt zu groß, wird das System numerisch instabil. Um sich von dieser
Schrittweitenabhängigkeit zu lösen, werden oft implizite Verfahren gewählt, die in der
Berechnung teurer sind.
Um eine Variabilität hinsichtlich der Integrationsmethode zu gewährleisten, wird ein
allgemeiner Integrator definiert, über den das gewünschte Verfahren spezifiziert werden kann. Wie in dem UML-Diagramm 4.3 ersichtlich, werden von der allgemeinen
Integrator-Klasse Integrator die Klassen der Verfahren abgeleitet. Implementiert
werden das explizite Euler-Verfahren in expEulerIntegrator , das Verlet-Verfahren
in VerletIntegrator sowie das implizite Euler-Verfahren in
impEulerIntegrator . Alle diese Verfahren sind in Abschnitt 2.3 beschrieben.
Zur Lösung des linearen Gleichungssystems beim impliziten Euler-Verfahren wurde
die Methode der konjugierten Gradienten (s. B.3.3) angewendet.
4.3. RENDERING
4.3
45
Rendering
Zum Rendern wurde die szenegraphbasierte API OpenSG 3 zu Hilfe genommen. Dabei
werden die zu rendernden Geometrien als Blattknoten in den Szenegraphen gehängt.
Um dieses Szenegraphen-Prinzip auf die hierarchische Haarrepräsentation anwenden
zu können, muß jedem Quadtreeknoten seine darzustellende Geometrie, in Form eines
OpenSG-Knotens, zugeordnet sein.
Wird im Quadtree die Ebene gewechselt, muß im OpenSG-Szenegraphen die entsprechende Geometrie gerendert werden. Der Quadtree und der OpenSG-Szenegraph müssen
parallel traversiert werden. Aus diesem Grund enthält jeder Quadtreeknoten, wie in Abbildung 4.5 dargestellt, drei OpenSG-Knoten: Einen GroupCore-Knoten, einen GeometryCore-Knoten und einen Switch-Knoten, der aus beiden auswählt. Zur Erläuterung: In
OpenSG gibt es verschiedene Knotentypen, die unterschiedliche Funktionalitäten ermöglichen: Gruppieren, Transformieren, Selektieren, Geometrien erzeugen usw. Der
Teil eines Knotens, der diese Information beinhaltet, wird NodeCore bezeichnet. Je
nach Funktion heißt der NodeCore entweder GroupCore, TransformCore, SwitchCore,
GeometryCore usw. Der GroupCore-Knoten des Quadtreeknotens enthält die SwitchKnoten der Kinder des Quadtreeknotens. Wird im Quadtree eine Stufe nach unten gegangen, wird der Switch-Knoten auf 0 gesetzt. Steht der Switch-Knoten auf 1, wird der
GeometryCore ausgewählt und die Geometrie gerendert.
Beim Erzeugen der Geometrien werden unterschiedliche Typen verwendet. Diese
sind abhängig vom Typ des BaseHair im Quadtree. Da OpenSG auf OpenGL basiert,
sind die Typenbezeichner für die Geometrieprimitive identisch. So wird für einen Haarstreifen GL_QUAD_STRIP, für ein Zylinder mehrere GL_QUAD_STRIPs und für die
Einzelhaarrepräsentation mehrere GL_LINE_STRIPs, verwendet. Der Zylinder wird
entsprechend dem Algorithmus B.4 konstruiert.
Um unnötige Rechenzeit zu vermeiden, wird geprüft, ob die Geometrie eines Knotens
bereits erstellt wurde. Falls ja, wird die bereits erstellte Geometrie modifiziert und wiederverwendet.
3
www.opensg.org
46
Abb. 4.5: Ein Quadtree mit dem integrierten OpenSG-Szenegraphen
Kapitel 5
Realisierung
In diesem Kapitel wird die Umsetzung und das Resultat des im vorigen Kapitel erarbeiteten Konzepts vorgestellt. Zuerst werden einige Details der Programmierung erläutert.
Anschließend werden nach Abwägung verschiedener Voraussetzungen die entstandenen
Ergebnisse präsentiert.
5.1 Implementierung
In diesem Abschnitt sollen einige wichtige Punkte der Implementierung näher vorgestellt werden.
In der Initialisierungsfunktion des Avalon-Knotens Skeleton wird das Masse-FederSystem des Top-Level-Haares angelegt und daraus der Quadtree erzeugt. Für das Rendern der Geometrien ist es wichtig, dass der OpenSG-Szenegraph an das Avalon-System
angebunden wird. Manche Avalon-Knoten können über einen Core auf OpenSG-Knoten
verweisen. Um einen kompletten OpenSG-Szenegraphen anzubinden, wird dieser Core
als SwitchCore definiert. Die Kinder des SwitchCore sind zum einen der GeometrieKnoten des Wurzelknotens des Quadtree und zum anderen ein Gruppen-Knoten mit
den Switch-Knoten der Kinder des Wurzelknotens (s. Abbildung 4.5). Über den Core
des Avalon-Knotens kann auf diese Weise der OpenSG-Graph gerendert werden.
Die Traversierung des Quadtree, die Integration der Massepunkte und das Erzeugen
der Geometrien erfolgen aus der Skeleton-Methode simulate() heraus. Um einen
programmiertechnischen Überblick zu erhalten, wird an dieser Stelle die Methode als
Pseudocode dargestellt.
berechne factor ()factor = velocity * distance
setze oldLevel = aktuelles Level
solange d ≤ DEPTH
wenn factor < (d * INTERVALL)
47
KAPITEL 5. REALISIERUNG
48
newLevel = d-1
break
d++
wenn Quadtree sichtbar
temporäreListe1 = Knoten des aktuellen Levels
brechne steps
wenn oldLevel < newLevel
solange i < steps
solange j < temporäreListe1
wenn Knoten in temporäreListe1 unterteilbar
füge Kinder des Knotens in temporäreListe2
sonst
füge Knoten in temporäreListe2
temporäreListe1 = temporäreListe2
wenn oldLevel > newLevel
wenn i < steps
solange j < temporäreListe1
wenn Knoten in temporäreListe1 6= Root-Knoten
gehe zu Vaterknoten
wenn Positionen der Kinder nicht zu weit auseinander
füge Kinder des Vaterknotens zusammen
sonst
break
füge Vaterknoten in temporäreListe2
sonst
füge Knoten in temporäreListe2
j = nächster Knoten in temporäreListe1 mit anderem Vater
temporäreListe1 = temporäreListe2
solange n < temporäreListe
integriere Massen im Knoten
erzeuge Geometrie
Um das neue Hierarchielevel zu bestimmen, wird am Anfang der Methode ein Faktor errechnet, der das Produkt aus dem Abstand des Betrachters und der Durchschnitts-
5.1. IMPLEMENTIERUNG
49
geschwindigkeit der Haarknoten des aktuellen Levels (velocity) ist. Um die Distanz des
Betrachters zur Bounding Box des Haares zu errechnen, wird die Methode
getViewingDistance() aufgerufen. In der Methode werden vier Distanzstufen
unterschieden. Entsprechend dem Intervall, in welches der errechnete Mindestabstand
fällt, wird ein Multiplikator für die Faktorberechnung zurückgeliefert (distance).
Um das neue Level zu erechnen, wird ein definierter Wertebereich durch die Tiefe des
Quadtrees (DEPTH) geteilt, wodurch man ein Werteintervall (INTERVALL) erhält. Die
Anzahl, wie oft der Faktor in diesen Wertebereich paßt, entspricht dem neuen Level.
Die Anzahl der Schritte (steps), die im Quadtree auf- oder abgestiegen wird, ergibt
sich aus der Differenz des alten zum neuen Levels. Wird in der Hierarchie nach oben
oder nach unten gegangen, werden die Knoten des neuen Levels in einer temporären
Liste zwischengespeichert. Durch das Wiederverwenden und die Dynamik der Listen
kann die variable Anzahl der Knoten pro Ebene gehandhabt werden. Wird der Quadtree
über mehrere Ebenen traversiert, wird jeweils ausgehend von den Knoten in der Liste in
die nächste Ebene gewechselt. Die Knoten des neuen Levels werden wiederum in einer
Liste gespeichert.
Wenn beim Unterteilen der Knoten und Zusammenfassen der Kindknoten auf die Kinder zugegriffen werden muß, ist zu beachten, dass ein Knoten weniger als vier Kinder
haben kann. Das tritt in den unteren Ebenen der Einzelhaarhierarchie auf, wenn durch
die Zufallsverteilung der Einzelhaare die Quadranten in den Einzelhaargruppen nicht
gleichmäßig besetzt wurden.
Um beim Aufsteigen Popping-Effekte zu verhindern, werden nur die Informationen der
Kindknoten zusammengefaßt, die nicht zu weit vom Vaterknoten entfernt sind.
Wie im letzten Kapitel bereits erwähnt, wurden drei verschiedene Integrationsverfahren implementiert. Die drei Zeilen des expliziten Euler-Verfahrens sind als Pseudocode sind im Anhang B.1 aufgelistet.
Bei der Implementierung des Verlet-Verfahrens ist zu bedenken, dass die Berechnung
des Faktors für den Wechsel des Detaillevels über die Geschwindigkeit berechnet wird.
Daher muß statt des einfachen Verlet-Verfahrens das Velocity-Verlet-Verfahren verwendet werden, bei dem die Geschwindigkeit explizit berechnet wird (vgl. 2.3.3, B.2).
Die Umsetzung des impliziten Euler-Verfahrens ist am anspruchsvollsten. Zum einen
sind in der Gleichung 2.39 zwei Jacobi-Matrizen die erstellt und multipliziert werden
müssen, und zum anderen muß ein lineares Gleichungssystem gelöst werden.
Bei einem Masse-Feder-System wird die interne Dynamik durch Federn repräsentiert.
Die Federverbindungen drücken sich in den Jacobi-Matrizen aus. Die³ Jacobi-Matrizen,
´
δf
j
und δf
, bestehen aus Untermatrizen mit Ableitungen der Form δf
= δf
, und
δx
δv
δx
δxi
ij
entsprechend für δf
. Sind beim Masse-Feder-System die Partikel
i und j über eine Feδv
³ ´
δf
ungleich null. Die
der miteinander verbunden, ist die entsprechende Ableitung δx
ij
50
Jacobi-Matrizen für Geschwindigkeit und Position lauten (vgl. [19]):
xij xT
xij xT
δfi
L
= F K T ij + F K(1 −
)(Ident. − T ij )
δxj
xij xij
|xij |
xij xij
(5.1)
δfi
= D ∗ Ident.
(5.2)
δvj
F K ist die Federkonstante, L die Ruhelänge der Feder und D die Dämfungskonstante.
Aus diesem Grund werden die Jacobi-Matrizen in der Masseklasse Mass gespeichert.
Die Berechnung der Matrizen erfolgt nach dem Algorithmus B.3.1.
Um das lineare Gleichungssystem (s. Gleichung 2.39) zu lösen, wird die Methode der
konjugierten Gradienten angewandt (s. B.3.3). Bei diesem Verfahren wird die Lösung
des LGS approximiert, indem eine zu Beginn getroffene Anfangsannahme iterativ korrigiert wird.
Um zu dem Gleichungssystem der Form A∆v = b zu gelangen, muß zuerst b und
dann A berechnet werden. Bei der Berechnung des Vektors b ist die Multiplikation der
Jacobi-Matrix der Position mit v nicht trivial. Um dieses Problem zu lösen wurde die
Hilfsfunktion B.3.2 angewendet.
Die Berechnung der Matrix A besteht aus drei Schritten: der Multiplikation der JacobiMatrix der Position mit −h2 , der Multiplikation der Jacobi-Matrix der Geschwindigkeit mit −h und der Multiplikation mit der Massematrix M . Um die Produkte mit den
Jacobi-Matrizen zu erhalten, wird ebenfalls der Algorithmus B.3.2 zu Hilfe genommen.
5.2
Tests und Ergebnisse
Zu Beginn dieses Abschnitts werden zuerst einige grundlegende Fragen geklärt, die
für die Durchführung der Simulation wichtig sind. Als erstes wird untersucht, welches
Integrationsverfahren am geeignetsten ist. Danach wird die Frage geklärt, wie die Zylinderrepräsentation beim Cluster-Haartyp genau aussehen soll.
Wie bereits erwähnt, ist die Komplexität der Methode ein Kriterium für die Auswahl
des Integrationsverfahrens.
Um diese bei den drei Integrationsverfahren, explizites und implizites Euler-Verfahren
sowie das Verlet-Verfahren, zu testen, werden ihre Berechnungszeiten verglichen.
Getestet werden die Verfahren an drei verschiedenen Streifen mit einem darunterliegenden Masse-Feder-System. Der erste Streifen enthält 10 Massepunkte, der zweite 100
und der dritte 1000. Die Ergebnisse sind in Abbildung 5.1 zu sehen. Das Verlet- und
das explizite Euler-Verfahren unterscheiden sich nur gering in der Geschwindigkeit.
Das implizite Euler-Verfahren ist dagegen deutlich langsamer, was für eine EchtzeitAnwendung von Nachteil sein kann.
5.2. TESTS UND ERGEBNISSE
51
Abb. 5.1: Das explizite und implizite Euler-Verfahren sowie das Verlet-Verfahren im
Vergleich
Das zweite entscheidende Kriterium ist die Stabilität eines Verfahrens.
Abbildung 5.2 zeigt die Schwelle der Schrittweite zur Instabilität beim exliziten EulerVerfahren. Sie liegt bei 0.035 zu 0.036 Sekunden. Beim Verlet-Verfahren (vgl. Abb. 5.3)
liegt die Schwelle bereits bei 0.0045 Sekunden. Zwischen 0.0045 und 0.018 Sekunden
verläuft die Simulation sehr unkontrolliert, was man bei der mittleren Abbildung bei
0.006 Sekunden sehen kann. Ab 0.018 Sekunden ist das Verfahren instabil.
Abb. 5.2: Vergleich des expliziten Euler-Verfahrens mit einer Schrittweite von 0.035
sec. und 0.036 sec.
Festzustellen ist, dass das explizite Euler-Verfahren mit größeren Schrittweiten stabiler ist, als das Verlet-Verfahren. Für eine Echtzeit-Anwendung ist das von Vorteil.
52
Abb. 5.3: Vergleich des Verlet-Verfahrens mit einer Schrittweite von 0.0045 sec., 0.006
sec. und 0.018 sec.
Es bleibt anzumerken, dass die gemessenen Schwellen von dem Federkoeffizient
abhängen. In Abbildung 5.4 wurde der Federkoeffizient auf 100 gesetzt, statt auf 500
wie bei den obigen Tests. Bei niedrigerem Federkoeffizient liegt die Stabilitätsschwelle
höher, im Beispiel bei 0.07 Sekunden.
Abb. 5.4: Unterschiedliche Stabilität des expliziten Euler-Verfahrens bei einer Schrittweite von 0.07 sec. mit einem Federkoeffizient von 100 (statt 500 wie oben)
Allerdings erreicht das explizite Euler-Verfahren, bei allen getesteten Federkoeffizienten, bei einem größeren Zeitschritt numerische Instabilität, als das Verlet-Verfahren.
Die Ergebnisse des Geschwindigkeitstest und des Stabilitätstests begründen die Entscheidung für das explizite Euler-Verfahren als Integrationsverfahren für die Simulation.
Eine weitere Entscheidung, die getroffen werden muss, ist die Anzahl der Seitenflächen des Zylinders um die Cluster-Repräsentation darzustellen. Mit steigender Anzahl der Seitenflächen nimmt zwar die visuelle Qualität zu, der Rechenaufwand allerdings auch. Um einen Kompromiss zu finden, wurde die benötigte Rechenzeit mit der
Qualität der Darstellung verglichen. Getestet wurden Zylinder mit 3 bis 10 Seiten (s.
Abb. 5.5). Die Berechnungszeit setzt sich aus der Zeit für das Rendering und der Zeit
für die Konstruktion (B.4) zusammen. Eine befriedigende Darstellung erhält man erst ab
5 Seiten. Da der Rechenaufwand für einen Zylinder mit mehr als 8 Seiten stark ansteigt
(vgl Abb. 5.6), wurde eine Repräsentation mit weniger Seiten gewählt. Da der Zylinder
53
Abb. 5.5: Verschiedene Zylinderseiten, von 3 bis 10 Seiten
aus optischen Gründen mehr als 5 Seiten, aus zeitlichen Gründen jedoch 8 Seiten oder
weniger haben soll, wurde eine Repräsentation mit 6 Seiten gewählt.
Nachdem entschieden wurde, welche Integration verwendet wird, und wie der Zylinder dargestellt wird, kann nun das Simulationsverfahren untersucht werden.
Gegenstand der Untersuchung sind folgende Punkte:
1. Modellierung der Frisur (Streifenbreite) im Hinblick auf die Struktur des Quadtrees
(Tiefe)
2. Wahl der Schwellwerte für den Wechsel der Repräsentation beim Aufbau des
Baumes
3. Der Faktor für den Wechsel der Hierarchiestufe während der Simulation
4. Anzahl der Haarsegmente, bzw. Massen und Federn des darunterliegenden MasseFeder-Systems, im Hinblick auf die Geschwindigkeit und die Qualität der Bewegung
5. Anzahl der Streifen des Modells im Hinblick auf die Geschwindigkeit der Simulation und die Qualität der Darstellung
Als Modelle für die Versuche wurden zwölf Frisur-Modelle erstellt (s. Tabelle 5.1).
Fünf Frisuren sind mit einer einheitlichen Breite modelliert, unterscheiden sich aber in
der Anzahl der Streifen. Fünf weitere Frisuren haben die gleiche Anzahl an Haarstreifen, unterscheiden sich aber in der Breite der modellierten Streifen. Bei drei Modellen
sind die Haarstreifen durch unterschiedlich viele Segmente aufgebaut.
Der Quadtree wird nun, wie im letzten Kapitel bereits erklärt, aufgebaut, indem
die Geometrie immer wieder geviertelt wird. Die Haarrepräsentation wird gewechselt,
54
Abb. 5.6: Vergleich der Zylinderrepräsentation mit unterschiedlicher Anzahl Seitenflächen
Modell
Frisur A
Frisur B
Frisur C
Frisur D
Frisur E
Frisur F
Frisur G
Frisur H
Frisur I
Frisur K
Frisur L
Frisur M
Anzahl der Haarstreifen
109
78
53
127
161
109
109
109
109
78
78
78
Breite eines Haarstreifens
0.71
0.71
0.71
0.71
0.71
0.28
0.49
0.92
1.06
0.71
0.71
0.71
Tabelle 5.1: Getestete Frisurmodelle
Segmente
8
8
8
8
8
8
8
8
8
4
6
8
55
wenn ein definierter Schwellwert unterschritten wird. Bei Haarstreifen werden bei der
Unterteilung Haarzylinder gewählt, falls die Breite des Haarstreifens kleiner als ein definierter Wert ist. Ebenso werden die Kinder eines Haarzylinders zu Einzelhaargruppen,
falls der Radius unter einer vorgegebenen Schwelle liegt. Die Unterteilung geschieht
maximal so lange, bis die Blätter des Baumes aus jeweils einem Einzelhaar bestehen.
Die Tiefe des Baumes hängt folglich von den gesetzten Schwellwerten und der Anzahl
der Einzelhaare, die ein Zylinder enthält ab. Über die Schwellwerte kann man festlegen,
ob bereits sehr früh eine feinere Auflösung benutzt werden soll. Anders ausgedrückt:
bei welchem Abstand und welchen Kräften wird welcher Haartyp erzeugen.
Beim Aufbau des Quadtrees hängt die Tiefe des Baums von der Breite des Streifens
ab. Ein breiter Streifen wird öfters unterteilt als ein schmaler. Die Tiefe des Baumes
hängt auch davon ab, wie viele Einzelhaare pro Einzelhaargruppe definiert sind. In Tabelle 5.2 wurden die Frisuren A-I mit 4 Einzelhaaren pro Einzelhaargruppe definiert,
und Fisur I∗ mit 6 Einzelhaaren. Der Quadtree von Frisur I∗ erreicht ein viel tieferes
Level als Frisur I, da die Einzelhaargruppen so lange unterteilt werden, bis in jedem
Knoten nur noch ein Einzelhaar ist. Da das für 6 Haare pro Gruppe länger dauert als für
4, ist der resultierende Baum tiefer.
Level
Fisur G
0
1 Strip
1
4 Strands
2
16 Strands
3
4
5
6
Frisur A
1 Strip
4 Cluster
16 Strands
64 Strands
Frisur I
1 Strip
4 Cluster
16 Cluster
64 Strands
256 Strands
Frisur I*
1 Strip
4 Cluster
16 Cluster
64 Strands
206 - 221 Strands
374 - 384 Strands
384 Strands
Tabelle 5.2: Unterschiedliche Tiefe des Quadtree in Abhängigkeit der Breite des TopLevel-Streifens
Die Tiefe des Baums ist in vielerlei Hinsicht von Bedeutung. Zum einen wirkt sie
sich auf die Benutzung des Speicherplatzes aus, denn desto tiefer der Baum, desto mehr
Speicherplatz wird verbraucht, da die Anzahl der Knoten pro Ebene näherungsweise
exponentiell wächst. Zum anderen machen sich viele Knoten in einer Ebene in der Performanz bemerkbar. Abbildung 5.7 zeigt, wie die Anzahl der Haarknoten einer Frisur
mit zunehmendem Level ansteigt. In dem Beispiel wurde von einem Frisurmodell mit
90 top-level Streifen ausgegangen. Bereits im zweiten Level sind mehr als 1400 Haarknoten erreicht. Im dritten Level sind es schon über 5700 und im vierten 21150 Knoten.
56
Da eine Echtzeit–Simulation für über 21000 Knoten sehr schwierig wird, wird das dritte
Level als unterste Ebene gewählt.
Abb. 5.7: Anzahl der Haarknoten insgesamt pro Level bei einem Frisurmodell mit 90
initialen Streifen
Für die Struktur des Baumes sind auch die Schwellwerte für den Wechsel der Repräsentation wichtig. Sie geben an, bei welcher Streifenbreite oder bei welchem Zylinderradius der Haartyp gewechselt werden soll. Wie die Verteilung der einzelnen Repräsentationen im Baum sein kann, wird in Abbildung 5.8 gezeigt. Im linken Beispiel
sind der Clusterschwellwert und der Strandschwellwert relativ niedrig, der Anteil an
Strips ist folglich relativ hoch. Im mittleren Beispiel wurde der Schwellwert für die
Clusterrepräsentation, der maximal mögliche Radius für einen Zylinder, nach oben gesetzt. Der Anteil an Haarzylinder steigt dadurch. Wird der Schwellwert für die Clusterund für die Strandrepräsentation nach oben gesetzt, werden bereits ab einem früheren
Level Einzelhaargruppen dargestellt.
Die Aufteilung der Repräsentationen wirkt sich auf die Rechenzeit aus, denn die
einzelnen Haartypen sind unterschiedlich teuer. An Frisurmodell A (s. Abb. A.2) wurde
getestet, wie stark die Rechenzeiten für die Simulation mit den einzelnen Typen variie-
57
Abb. 5.8: Struktur des Baums bei unterschiedlichen Schwellwerten
ren. Die Zeiten sind in Tabelle 5.3 dargestellt. Die Streifen sind demnach am schnellsten,
vor den Zylindern und vor den Einzelhaargruppen.
Es ist folglich geschickt, die Schwellwerte so zu wählen, dass weder der Anteil der Zylinder noch der Anteil der Einzelhaargruppen dominiert, die visuelle Darstellung dennoch durch die LOD-Struktur des Quadtree profitiert. Eine Aufteilung, ähnlich der Abbildung links in 5.8, ist anzustreben.
Level
Zeit
0 (Strip)
72.4873 sec.
1 (Cluster)
183.898 sec.
2 (Strand)
439.995 sec.
Tabelle
5.3:
Simulation
mit
unterschiedlichen
LOD(Simulationsschleife mit 10000 Wiederholungen)
-1 (LOD)
125.057 sec.
Haartypen
und
mit
Durch die Verwendung der verschiedenen Haartypen wird die Qualität der Darstellung verbessert. Für die optische Erscheinung der Frisur ist ebenfalls die Anzahl der
Haarstreifen eines Modells von Bedeutung. Das menschliche Haupt hat im Schnitt
100 000 Haare. Um eine ansprechende Darstellung zu erzeugen, ist es nicht nötig diese Anzahl zu simulieren. Zudem ist es eine Frage der Geschwindigkeit, welche Menge
an Haaren in Echtzeit simuliert werden kann. Durch den Vergleich der Modelle A bis
E, wurde getestet, wie sich die unterschiedliche Anzahl an Streifen auf die Geschwindigkeit auswirkt. In Abbildung 5.9 sind die Ergebnisse des Tests dargestellt. Die Dauer
nimmt proportional zur Streifenzahl zu.
Da das Modell A, mit 78 top-level Streifen, optisch bereits befriedigende Ergebnisse
liefert, ist bei der Modellierung, bei entsprechender Breite der Streifen, eine Anzahl
zwischen 80 und 100 Streifen zu empfehlen.
Das zuletzt untersuchte Kriterium ist die Anzahl der Segmente, aus denen ein Haar
aufgebaut ist. Bei einer Langhaarfrisur ist es angebracht mehr Segmente zu verwenden, als bei kürzeren Haaren. Über die Anzahl der Segmente wird entschieden, wie das
58
Abb. 5.9: Frisurmodelle mit unterschiedlicher Streifenanzahl (Gemessene Zeiten in sec.:
FrisurB 47.8389, FrisurC 71.69, FrisurA 108.067, FrisurD 132.14 ,FrisurE 174.614)
5.3. FAZIT
59
Segmente
4
Zeit
76.7731 sec.
6
94.7276 sec.
8
113.1567 sec.
Tabelle 5.4: Vergleich mit unterschiedlicher Anzahl von Segmenten: Frisur K, Frisur L,
Frisur M
Masse-Feder-System aufgebaut ist, also wie viele Massen und Federn enthalten sind.
Je mehr Massepunkte integriert werden müssen, desto mehr Zeit wird in Anspruch genommen (vgl. Tab. 5.4).
5.3
Fazit
Die Tests und Ergebnisse im letzten Abschnitt, führen abschließend zu folgendem Fazit.
Bei den implementierten Integrationsverfahren empfiehlt sich die Verwendung der expliziten Euler–Integration. Die maximale Schrittweite bei der Integration hängt von der
Masse und der Federkonstanten ab. Aus diesen Parametern lässt sich auch der optimale
Dämpfungskoeffizient errechnen, mit:
FK
D= √
2 m ∗ FK
(5.3)
Dabei ist F K der Federkoeffizient und m die Masse.
Für die Darstellung der Clusterrepräsentation ist ein 6-seitiger Zylinder ausreichend.
Um eine Simulation in Echtzeit zu erhalten, ist die Streifenbreite beim Haarmodell so
zu wählen, dass eine maximale Tiefe des Quadtrees von 3 Leveln erreicht wird. Bei den
getesteten Beispielen wird dies bei einer Streifenreite von 0.7, und den Schwellwerten
für Cluster bei 0.35 und für Strands bei 0.125, erzielt.
Um eine unnötige Tiefe des Baumes zu vermeiden (vgl. Fisur I∗ in Tabelle 5.2), wird
die Menge der Strands, die aus einem Cluster hervorgehen, auf vier gesetzt.
Es ist ebenfalls ausreichend, bei der Modellierung zwischen 80 und 100 Streifen zu erzeugen, mit maximal vier Segmenten bei kürzeren Haaren (s. Modell Abb. A.1).
Unter diesen Bedingungen, ähnlich wie bei dem Versuch in Tabelle 5.3, liefert das
adaptive Verfahren sehr zufriedenstellende Ergebnisse. Wie aus Tabelle 5.3 ersichtlich,
ist die Simulation mit der LOD-Technik zwar teurer als die Simulation mit einfachen
Streifen, die Darstellung ist durch die Kombination von mehreren Haartypen jedoch erheblich verbessert.
60
Kapitel 6
Zusammenfassung und Ausblick
6.1
Zusammenfassung
Für eine glaubwürdige und realistisch wirkende Animation von virtuellen Charakteren
ist die korrekte Simulation von Kleidung und Haaren von großer Bedeutung. Dabei stellt
die Berechnung der Bewegungsabläufe in Echtzeit eine besondere Herausforderung dar.
Eine Möglichkeit der Beschleunigung ist der Einsatz von adaptiven Strukturen. In dieser Diplomarbeit wurde deren Verwendung im Zusammenhang mit der Simulation von
Kleidung und Haaren in Echtzeit untersucht. Dabei wurde ein Überblick über adaptive
Strukturen gegeben und verschiedene Möglichkeiten des Level of Detail für Stoff und
Haare vorgestellt.
Am Beispiel von Haaren wurde gezeigt, wie eine adaptive Simulation in der Praxis aussehen kann und welche Vorteile sie bietet.
Das Konzept orientiert sich stark an dem Verfahren von Ward et al. [17][16]. Als Kontrollstruktur für die Dynamiksimulation wurde ein Masse-Feder-System gewählt. Die
Adaption erfolgt zum einen über unterschiedlich aufgelöste Kontrollstrukturen und zum
anderen über unterschiedlich feine Geometrien. Durch die zweifache Anwendung der
Technik des Level of Detail, wird bei gleichzeitiger Verfeinerung der Kontrollstrukturen, die Qualität der Darstellung, durch weniger abstrakte Geometrien, verbessert. Die
unterschiedlichen Auflösungen werden vorberechnet und in einer hierarchischen Datenstruktur gespeichert. Für das Speichern der Hierarchie wurde eine Quadtree-Datenstruktur
verwendet. Zur Laufzeit wird, abhängig von folgenden Kriterien, im Quadtree auf- und
abgestiegen. Die Kriterien sind die einwirkende Kraft auf die Haare und der Abstand des
Betrachters. Wird eine starke Kraft ausgeübt, z.B. in Form von Kopfbewegung, oder ist
der Betrachter sehr nahe an den Haaren, z. B. durch Heranzoomen der Kamera, wird ein
feineres Level of Detail verwendet, indem im Quadtree eine tiefere Ebene gewählt wird.
Das Simulationssystem wurde in die VR-Umgebung Avalon integriert. Durch das
61
62
KAPITEL 6. ZUSAMMENFASSUNG UND AUSBLICK
Avalon-Webinterface (s. Abb. 6.1) können die Parameter der Haare zur Laufzeit angesteuert und verändert werden. So können die Schrittweite der Integration, die Anzahl
der Simulationsschleifen pro Frame, die Dämpfungs- und Federkonstante und die Masse des Masse-Feder-Systems geändert werden. Über das Interface kann die Technik des
LOD deaktiviert, und stattdessen ein bestimmtes Level der Hierarchie ausgewählt werden. Die Resultate des Verfahrens sind abhängig von der Parametrierung (vgl. 5.3).
Abb. 6.1: Frisurmodelle mit unterschiedlicher Streifenanzahl
Für das Rendering wurde die OpenGL-basierte API OpenSG verwendet. Die Modelle, die getestet wurden, wurden mit dem Cinema4D-PlugIn HairDepartment erzeugt.
6.2. AUSBLICK
6.2
Ausblick
6.2.1
Optimierung und Ergänzung
63
Für die meisten Dynamiksimulationen ist die Behandlung der Kollision unverzichtbar.
Es besteht die Möglichkeit, für die Kollisionserkennung frei erhältliche Bibliotheken1
aus dem Internet zu verwenden.
Einen realistischen Eindruck erhalten die Haare durch den Einsatz von Texturen und
Shadern. Dadurch werden die geometrischen Unterschiede der Haartypen verwischt,
und die Popping-Effekte gemindert.
Um eine gößere Vielfalt an Frisuren simulieren zu können, sollten verschiedene Haarstile berücksichtigt werden. So sollten neben glatten Haaren auch gelockte Haare umgesetzt werden können. Wie in der Natur beobachtet werden kann, können Haare unterschiedlich dick sein. Diese Tatsache sollte im System berücksichtigt werden, da sie sich
sowohl auf das Aussehen wie auf das Dynamikverhalten auswirkt.
6.2.2
Weiterführende Überlegungen
Bei dem implementierten Ansatz ist die Verwaltung sowie die Adaption des Modells
auf Objekte mit eindimensionalen Kontrollstrukturen ausgerichtet. Um ein allgemeines adaptives System für Dynamik-Simulation zu entwerfen, welches auch 2D- oder
3D-Objekte, wie Stoff oder Körper, unterstützt, kann das Konzept der hierarchischen
Datenverwaltung kombiniert mit adaptivem Rendering übernommen werden.
Allerdings bietet ein Kontinuum-Mechanik-Simulationsmodell für eine adaptive Simulation von Kleidung Vorteile, da es eine bessere Näherung an die Wirklichkeit bietet und
eine Abbildung der Viskoelastizität unterstützt. Für Textilien und biologisches Weichgewebe stellt die Viskoelastizität eine grundlegende Eigenschaft dar.
Als Basis für ein Konzept bietet sich die Arbeit von Hauth an. Er stellt in [22] ein Verfahren basierend auf der Methode der Finiten Elemente vor, dessen Effizienz durch einen
schnellen Lösungsalgorithmus zur impliziten numerischen Integration gesteigert wird.
Debunnes et al. [9] stellt in seinen Arbeiten Adaptionsverfahren vor, die für KontinuumModelle geeignet sind.
Bei der Simulation von Stoff gilt die Besonderheit der Gewebestruktur (gewebt, gestrickt, ...) zu beachten, denn die Gewebestruktur wirkt sich auf das dynamische Verhalten des Textils aus. Neben der Struktur verändern auch das Fasermaterial (Baumwolle,
Synthetik, ...) sowie die Dicke und der Aufbau der Fasern die Bewegung.
1
http://www.cs.unc.edu/ geom/SSV
64
KAPITEL 6. ZUSAMMENFASSUNG UND AUSBLICK
Anhang A
Bilder
Abb. A.1: Frisurmodell mit 109 Streifen mit jeweils 3-4 Segmenten
65
66
ANHANG A. BILDER
Abb. A.2: FrisurA mit 109 Streifen mit jeweils 8 Segmenten
67
Abb. A.3: FrisurA unter Einwirkung starker äußerer Kräfte. Die Haare werden in der
höchsten Auflösung, als Einzelhaare, repräsentiert.
68
ANHANG A. BILDER
Abb. A.4: Die äußeren Kräfte lassen im Vergleich zu Abb. A.3 nach. Die Haare werden
in der nächst niedrigeren Auflösung, als Zylinder, dargestellt.
69
Abb. A.5: Die Kräfte, die auf die Haare wirken, ist zum Teil so gering, dass die gröbste
Darstellungsstufe, die Streifendarstellung, gewählt wird.
70
ANHANG A. BILDER
Abb. A.6: Die Repräsentationen der Haare werden durch Heranzoomen verfeinert.
71
Abb. A.7: Durch Drehen des Kopfes nach links, geraten die Haare in Bewegung. Die
wirkende Kraft ist so groß, dass die Haare als Zylinder repräsentiert werden.
72
ANHANG A. BILDER
Anhang B
Algorithmen
B.1
Explizite Euler-Integration
i=0
for i ¿ masses.size
masses[i].acceleration = masses[i].force / masses[i].mass
masses[i].velocity = masses[i].velocity + masses[i].acceleration * dt
masses[i].position = masses[i].position + masses[i].velocity * dt
i++
B.2
Velocity-Verlet-Integration
pos = 0
accNext = 0
i=0
pos = masses[i].position
masses[i].acceleration = masses[i].force / masses[i].mass
masses[i].position = (pos + masses[i].velocity * dt) + masses[i].acceleration * (dt2 /2)
accNext = (masses[i].position - pos) * (1 / dt2 )
masses[i].velocity = masses[i].velocity + (( masses[i].acceleration + accNext) / 2) * dt
i++
73
ANHANG B. ALGORITHMEN
74
B.3
Implizite Euler-Integration
b=0
A=0
i=0
∆v = 0
b = dt (masses[i].force + (dt * JacobiProduct1))
M = I. * (1/m)
A = M - JacobiProduct2 - JacobiProduct3
∆v = solveLSE(b,A)
masses[i].velocity = masses[i].velocity + ∆v
masses[i].position = masses[i].position + masses[i].velocity * dt
i++
B.3.1
Jacobi-Matrizen berechnen
liefert Jacobi-Matrizen für Position JacobiX und für Geschwindigkeit JacobiV
i=0
displacement = 0
vp = 0
length = 0
for i ¿ springs.size
displacement = springs[i].mass1 - springs[i].mass2
vp = displacement * displacement
length = sqrt(displacement * displacement)
if(length != 0) length = 1.0 / length
vp = vp * (l*l)
springs[i].JacobiX = (vp + (I. - vp) * (1 - springs[i].length * length)) *
springs[i].springconstant
springs[i].JacobiV = I.
springs[i].JacobiV *= springs[i].dampingconstant
i++
B.3. IMPLIZITE EULER-INTEGRATION
B.3.2
Hilfsfunktion für Multiplikation mit Jacobi-Matrizen
Liefert Multiplikationsmatrizen für Jacobi-Matrizen JacobiProductN
i=0
tmp = 0
for i ¿ springs
tmp = springs[i].JacobiX * (springs[i].mass1 - springs[i].mass2)
springs[i].mass1.JacobiProduct -= tmp
springs[i].mass2.JacobiProduct += tmp
i++
B.3.3
Methode der konjugierten Gradienten
∆v=0
i=0
r=b-A∆v
d=r
epsNew = rT r
eps0 = epsNew
while(i ¿ iMax && epsNew À eps * eps0)
q=Ad
α = epsNew / (dT q)
∆r = ∆v + (α d)
r = r - (α d)
epsOld = epsNew
epsNew = rT r
β = epsNew / epsOld
d = r + (β α)
i++
75
ANHANG B. ALGORITHMEN
76
B.4
Algorithmus zu Konstruktion des Zylinders
r=0
s=0
i=0
vectors berechenen Radien zu allen Punkten des Zylinders
for r ¿ Anzahl der Seitenflächen
for s ¿ Anzahl der Masse-Feder-Segmente
i++
position = position + vectors[Anzahl der Seitenflächen * s + r]
s++
s=0
for s ¿ Anzahl der Masse-Feder-Segmente
indexA = s + r * Anzahl der Masse-Feder-Segmente
if r 6= (Anzahl der Seitenflächen - 1)
indexB = s + (r+1) * Anzahl der Masse-Feder-Segmente
else
indexB = s
s++
r++
Abbildungsverzeichnis
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
Weg-Zeit-Diagramm . . . . . . . . . . . . . . . . .
Geschwindigkeits-Zeit-Diagramm . . . . . . . . . .
Bahnkurve mit tangentialem Geschwindigkeitsvektor
Cantilever-Beam-Modell . . . . . . . . . . . . . . .
Unterschiedliche Federtypen . . . . . . . . . . . . .
Anfangswertproblem . . . . . . . . . . . . . . . . .
Explizites Euler-Verfahren . . . . . . . . . . . . . .
Runge-Kutta-Verfahren 2. Ordnung . . . . . . . . .
Runge-Kutta-Verfahren 4. Ordnung . . . . . . . . .
Diverse Bounding Volume-Typen . . . . . . . . . . .
Swept Sphere Volumes . . . . . . . . . . . . . . . .
Bounding Volume Hierarchie . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
10
11
14
15
17
18
19
20
23
23
24
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
Level of Detail bei deformierbaren Materialien
Verschiedene LODs und resultierendes Mesh .
Erzeugung regelmäßiger Dreiecke . . . . . . .
Beispiele aus [28] . . . . . . . . . . . . . . . .
Verbindung von zwei Leveln mit ghost-nodes .
Informationsaustauch zwischen zwei Leveln . .
Clustermodelle . . . . . . . . . . . . . . . . .
Verfeinerung einer Strähne . . . . . . . . . . .
Adaptive Wisp Tree (AWT) Verfahren . . . . .
Drei unterschiedliche Haarrepräsentationen . .
Schematische Darstellung der Hierarchie . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
27
28
28
29
29
30
31
32
33
34
35
4.1
4.2
4.3
4.4
4.5
Cinema4D-PlugIn HairDepartment . . . . . . . . . . . . .
UML-Diagramm (a) . . . . . . . . . . . . . . . . . . . . .
UML-Diagramm (b) . . . . . . . . . . . . . . . . . . . .
UML-Diagramm (c) . . . . . . . . . . . . . . . . . . . . .
Ein Quadtree mit dem integrierten OpenSG-Szenegraphen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
38
41
42
43
46
77
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ABBILDUNGSVERZEICHNIS
78
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
Integrationsverfahren im Vergleich . . . . . . . . .
Vergleich des expliziten Euler-Verfahrens . . . . .
Vergleich des Verlet-Verfahrens . . . . . . . . . . .
Unterschiedliche Stabilität . . . . . . . . . . . . .
Verschiedene Zylinderseiten . . . . . . . . . . . .
Unterschiedliche Zylinderrepräsentation . . . . . .
Anzahl der Haarknoten einer Frisur . . . . . . . .
Verschiedene Schwellwerte . . . . . . . . . . . . .
Frisurmodelle mit unterschiedlicher Streifenanzahl
.
.
.
.
.
.
.
.
.
51
51
52
52
53
54
56
57
58
6.1
webinterface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
A.1
A.2
A.3
A.4
A.5
A.6
A.7
final1 . . . . . . . . . . . . . . . . . . . .
FrisurA . . . . . . . . . . . . . . . . . . .
FrisurA mit Einzelhaaren . . . . . . . . . .
FrisurA als Clusterrepräsentation . . . . . .
FrisurA als teils Zylinder und teils Streifen .
Verfeinerung durch Heranzoomen . . . . .
Haarbewegung durch Drehen des Kopfes . .
65
66
67
68
69
70
71
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Tabellenverzeichnis
2.1
Verschiedene Simulationsmodelle . . . . . . . . . . . . . . . . . . . .
13
5.1
5.2
5.3
5.4
Getestete Frisurmodelle . . . . . . . . . . . . . . . . . . .
Unterschiedliche Tiefe des Quadtree . . . . . . . . . . . .
Simulation mit unterschiedlichen Haartypen und mit LOD
Vergleich mit unterschiedlicher Anzahl von Segmenten . .
54
55
57
59
79
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
80
TABELLENVERZEICHNIS
Literaturverzeichnis
[1] Witkin Andrew and Baraff David. Physically based modeling: Principles and practice. 1997.
[2] Hutchinson Dave, Preston Martin, and Hewitt Terry. Adaptive refinement for
mass/spring simulations. In Proceedings of the Eurographics workshop on Computer animation and simulation, pages 31–45. Springer-Verlag, 96.
[3] Baraff David. Large steps in cloth simulation. In ACM SIGGRAPH ’98, 1998.
[4] Luebke David, Reddy Martin, Jonathan D. Cohen, Varshney Amitabh, Watson
Benjamin, and Huebner Robert. Level of Detail for 3D Graphics. Morgan Kaufmann Publishers, 2003.
[5] Terzopoulos Demetri, Platt John, Barr Alan, and Fleischer Kurt. Elastically deformable models. In Computer Graphics, 1987.
[6] Hering Ekbert, Martin Rolf, and Stohrer Martin. Physik für Ingenieure. Springer,
Berlin, 2002.
[7] Bertails F., Kim T-Y, Cani M.-P., and Neumann U. Adaptive wisp tree - a multiresolution control structure for simulating dynamic clustering in hair motion. In
Symposium on Computer Animation’03, 2003.
[8] Freund Frank. Animation von avataren bei physikalisch basierten kleidungssimulationen. Master’s thesis, FH Darmstadt, 2003.
[9] Debunne Gilles, Desbrun Mathieu, Cani Marie-Paule, and Barr Alan. Adaptive
simulation of soft bodies in real-time. In Computer Animation, 2000.
[10] Debunne Gilles, Desbrun Mathieu, Cani Marie-Paule, and Barr Alan. Dynamic
real-time deformations using space and time adaptive sampling. In ACM SIGGRAPH, 2001.
[11] Eberly David H. Game Physics. Morgan Kaufmann Publishers, 2004.
81
82
LITERATURVERZEICHNIS
[12] House Donald H. and Breen David E., editors. Cloth Modeling and Animation. A
K Peters, Natick Massachusetts, 2000.
[13] Press William H., Teukolsky Saul A., Vetterling William T., and Flannery Brian P.
Numerical Recipes in C++, The Art of Scientific Computing. Cambridge University Press, second edition edition, 2002.
[14] Anjyo Ken Ichi, Usami Yoshiaki, and Kurihara Tsuneya. A simple method for
extracting the natural beauty of hair. In Computer Graphics, 1992.
[15] Bronstein I.N. and Semendjajew K.A. Teubner - Taschenbuch der Mathematik.
B.G. Teubner Verlagsgesellschaft, 1996.
[16] Ward Kelly and Lin Ming C. Adaptive grouping and subdivision for simulating
hair dynamics. Pacific Conference on Computer Graphics and Applications, 2003.
[17] Ward Kelly, Lin Ming C., Lee Joohi, Fisher Susan, and Macri Dean. Modeling
hair using level-of-detail representations. Proc. of Computer Animation and Social
Agents, 2003.
[18] Koh Chuan Koon and Huang Zhiyong. Modeling and animation of human hair in
strips. In Eurographics Workshop on Animation and Simulation, 2000.
[19] Choi Kwang-Jin and Ko Hyeong-Seok. Stable but responsive cloth. In ACM
SIGGRAPH, 2002.
[20] Bourg David M. Physics for Game Developers. O’Reilly, 2002.
[21] Hauth Michael. Numerical techniques for soft object simulation. In Proceedings
of the Eurographics, 2004.
[22] Hauth Michael. Visual Simulation of Deformable Models. PhD thesis, EberhardKarls-Universität Tübingen, 2004.
[23] Magnenant-Thalmann N. and Hadap S. State of the art in hair simulation. In
Proceedings of International Workshop on Human Modeling and Animation, 2000.
[24] Volino P. and Magnenant-Thalmann N. Virtual Clothing, Theory and Practice.
Springer, 2000.
[25] Volino Pascal and Magnenant-Thalmann Nadia. Comparing efficiency of integration methods for cloth simulation. In Computer Graphics International Proceedings, 2001.
[26] Hadap Sunil and Magnenant-Thalmann Nadia. Modeling dynamic hair as continuum. In Computer Graphics Forum, 2001.
LITERATURVERZEICHNIS
83
[27] Kim Tae-Young and Neumann Ulrich. Interactive multiresolution hair modeling
and editing. In SIGGRAPH ’02: Proceedings of the 29th annual conference on
computer graphics and interactive techniques, 2002.
[28] Volkov Vasily and Ling Li. Adaptive local refinement and simplification of cloth
mass. In ICITA 2002, 2002.
[29] Provot Xavier. Deformation constraints in a mass-spring model to describe rigid
cloth behavior. In Graphics Interface ’95, 1995.
[30] Bando Yosuke, Chen Bing-Yu, and Nishita Tomoyuki. Animating hair with loosely
connected particles. In Computer Graphics Forum, 2003.

Adaptive Echtzeit–Simulation von Stoff und Haaren Diplomarbeit im

Transcrição

Documentos relacionados

BIOLOGIE t - Lebendiger Unterricht

Titelseite (Bilder 1 bis 3): Der SVT 137 225 a/b, ein

Wir suchen Sie. Vertriebsingenieur Simulation / Automation (m/w)

Sägekettenschärfgeräte - Artikel: 94090, Serie: FSL94090

Der Wiener Kongreß war für die \\Tiener Hofburg natürlich eine

AS71 - Scoda

gs 650 saegekettenschaerfgeraet 94090-01

Anleitung Nadelfilzen Blumenzauber

Flyer Eventverleih