computergrafikII 10 Physikalische Spielereien · Prof. Dr. Marco Block-Berlitz Vorlesung Computergrafik II SoSe 2014 Folie 5 Schauen wir uns noch einmal die Trigonometrie (trigon,

Vorlesung

Computergrafik/Visualisierung II

Hochschule für Technik und Wirtschaft DresdenUniversity of Applied Sciences

Prof. Dr. Marco Block-BerlitzSommersemester 2014

Studiengang Medieninformatik

Vorlesung Computergrafik II

Prof. Dr. Marco Block-Berlitz

Vorlesungsteil

Physikalische Spielereien

Wer die Geometrie begreift, vermag in dieser Welt alles zu verstehen.Galileo Galilei

.+ .

.+

reelle Achse

imaginäre Achse

1

Prof. Dr. Marco Block-Berlitz Vorlesung Computergrafik II SoSe 2014 Folie 3

Ohne Lineare Algebra geht es nicht.


Hinweise zum Selbststudium

Die Lineare Algebra ist eines des wichtigsten, mathematischen Handwerkzeuge der Computer-grafik. Für das Studium der Grundlagen empfehle ich das hervorragende Buch von GilbertStrang:

Strang G.: „Introduction to Linear Algebra“, 4.Auflage, Wellesley-Cambridge Press, 2009

Wer dabei Lust hat, sich mal in eineVorlesung von Prof. Strang (MIT)zu setzen, hat hier die Möglichkeitdazu:

http://www.academicearth.org/courses/linear-algebra/


Schauen wir uns noch einmal die Trigonometrie (trigon, griechisch für Dreieck) etwas genauer an.

Daraus resultierende trigonometrische Funktionen:

Um sich diese drei Regeln zu merken, erinnern wir uns immer an den trigonometrischen Gott der Winkel „SohCahToa“...

Trigonometrie und Vektoren

Ankathete

Gegenkath

ete

.b

a

immer rechter Winkel!

opposite adjazent hypotenuse

Isch großa

Sohcahtoa!

c


Winkel können in rad (Radiant, radians) oder ° (Grad, degree) angegeben werden.

Radiant Grad

Die jeweiligen Umrechnungen sind sehr einfach:

Winkelangaben und -umrechnungen

0°

90°

180°

270°


u=(cos ,sin )

Ein Einheitsvektor u ist ein Vektor mit der Länge Eins. Es gilt u∙u=1. Um einen Vektor in einen Einheitsvektor zu transformieren, teilen wir ihn einfach durch seine Länge:

Für =0 wird der Vektor u gerade zu i. Für jeden Winkel ergeben dieKomponenten cos und sin gerade u u=1, weil cos + sin =1.

Einheitsvektoren und Einheitskreis

1

1

j=(0,1)

i=(1,0)cos

sin

Einheitskreis

1

-i=(-1,0)

-j=(0,-1)

2 2


Um einen Vektor v (der ungleich dem Nullvektor ist) zu normieren, also in einen Einheits-vektor der Länge Eins zu transformieren, teilen wir ihn einfach durch seine Länge.

Dann ist u= ein Einheitsvektor in dieselbe Richtung wie v.

Normierung von Vektoren

1

1

1

v

u =

w

normierte Vektorenhaben die Länge Eins


Behauptung: Das Skalarprodukt v∙w ist Null, falls v rechtwinklig zu w steht.

Beweis: Wenn v und w rechtwinklig zueinander stehen, bilden sie zwei Seiten eines rechtwinkligen Dreiecks. Die dritte Seite ist dann v-w (Hypothenuse).

Damit wird aus für die Seitenlängen (für senkrechte Vektoren!):

daraus leiten wir ab

Winkel zwischen Vektoren und Skalarprodukt I

und wir erhalten wiedergerade das Skalarprodukt


Wenn das Skalarprodukt v∙w ungleich Null ist, kann es positiv oder negativ sein.

Winkel zwischen Vektoren und Skalarprodukt II

v

.v

v‘

w

w

ist es positiv, so ist der Winkelzwischen ihnen <90°

ist es negativ, so ist der Winkelzwischen ihnen >90°


Konkrete Winkelbestimmung I

u=

Additionstheorem

i=

u=

v=

Wenn u und v Einheitsvektoren sind, so gilt u∙v=cos und es gilt der absolute Betrag|u∙v|≤1. Das Skalarprodukt zweier Einheitsvektoren liegt zwischen -1 und 1.

u∙i = cos ∙1+sin ∙0=cos u∙v = cos ∙cos +sin ∙sin =cos( - )

Diese Winkelbestimmung gilt für beliebige Dimensionen.


Für Vektoren, die keine Einheitsvektoren und ungleich dem Nullvektor sind, gilt dann die Kosinusformel:

Korrekterweise begegnet man dem Skalarprodukt v∙w nicht so ∙ , sondernso:

Später, nach Einführung der Matrizen, werden wir den Unterschied besser verstehen. Den Winkel erhalten wir schließlich mit:

Konkrete Winkelbestimmung II

Alternativ können wir auch rechnen:


Lineare Algebra in der Praxis.


Seien die m Vektoren der Dimension n in Menge V gegeben

Zentrieren einer Menge von Vektoren

Zentrum (Schwerpunkt) der Vektorenmenge

Verschiebung aufUrsprung

D.h. wir ziehen von allen Vektoren der Menge ab, um diese zu

zentrieren:

, mit

Anschließend liegen die Vektoren mit zentriert vor.


Als praktische Anwendung wollen wir ein Clustering-Verfahren kennenlernen.

10 Klassen werden dabei unter-schieden. Für die entsprechende Klasse wird eine 1.0 vermerkt, alle anderen mit 0.0 (Etikette oder Label).

1000 Ziffernbilder wurden von Menschen klassifiziert und liegen als Trainingsmenge TMin einer Datenbank zur Verfügung.

Ziel ist es, einen Klassifikator zu entwerfen, der mit Hilfe der klassifizierten Daten, unbekannte korrekt klassifiziert. Zunächst bringen wir die Bilddaten in eine Vektorform, das geht sehr einfach:

wir konstruieren einen 192-dim Vektor

0.0 0.0 ... 1.0 ...

3

Praktische Anwendung (Mustererkennung)

12

16

0.0 0.0 ...

0.0 0.5 1.0 ...

i

Bildwerte für i liegen im Intervall [0.0, 0.1, ..., 1.0]

Zeile 1

Zeile 2

Zeile 16

... ...Zeile 1 Zeile 2 Zeile 16


x

Um für einen unbekannten Vektor u zu entscheiden, welcher Klasse er amwahrscheinlichsten angehört, wird der Abstand dist(u, ) für alle berechnet. Diek nächsten entscheiden demokratisch über u.

Beispiel:

3 Klassen liegen im 2-dim Raum vor, das rote xist ein unbekannter Vektor und k ist 3 (ungeradeund klein).

Auf Grund der Tatsache, dass 2 mal Kreis und 1 mal Viereck vertreten sind, schlußfolgernwir, dass es sich bei dem x um einen Kreis handelt. Falls keine Klärung an dieser Stellemöglich ist, können wir k variieren, per Zufall entscheiden oder die Zentren der Klassenmit einbeziehen.

Verfahren: k-nächste Nachbarn


In der Computergrafik „dreht sich alles“ um Lineare Algebra


Das Kreuzprodukt (oder Vektorprodukt) von zwei Vektoren erzeugt einen neuen Vektor,der senkrecht zu den beiden steht.

Das Vektoren-Kreuzprodukt

Für zwei 3-dimensionale Vektoren ist es gerade definiert als:

(für ein rechtshändiges

Koordinatensystem)

wir können das aber auch wie folgt ausdrücken:

Ob der Ergebnisvektor senkrecht zu v und w ist, lässt sich über das Skalarprodukt leichtermitteln:

w analog


Die Richtung des Vektors kann mit der rechten Hand angegeben werden:

Kreuzprodukt im rechtsh. Koordinatensystem

linkshändig rechtshändig

Wenn wir die Vektoren vertauschen, wird der Ergebnisvektor negiert.

Es gilt , denn das Kreuzprodukt ist nicht kommutativ! Es ist auch nichtassoziativ.


Beim Kreuzprodukt zweier Einheitsvektoren ergibt sich der entsprechende dritte:

Wenn wir die Vektoren im Kreuzprodukt vertauschen, erhalten wir selbstverständlich dienegierten Einheitsvektoren:

Für zwei gleiche Einheitsvektoren liefert das Kreuzprodukt immer den Nullvektor

Kreuzprodukt und Einheitsvektoren


Aus Sicht einer 3D-Engine gibt es in Wahrheit noch viel mehr Koordinatensysteme. Die wichtigsten fünf sind:

world space

Spielumgebung

model space (object space, local space)

Kreierte Objekte

view space (camera space, eye space)

Sicht des Betrachters

clip space (projection space, homogeneous space)

Projektion in und Repräsentation im 2D-Raum

window space

Bildschirmkoordinaten für Ausgabe

Koordinatensysteme und Transformationen II

alles kartesische Koordinatensysteme


Wir haben es in der Computergrafik/Spieleentwicklung ständig mit verschiedenenKoordinatensystemen zu tun. Es gibt beispielsweise ein System, das die Weltrepräsentiert (world space) und alle vorhandenen Objekte kennt.

Koordinatensysteme und Transformationen I

world space local space

Jedes Objekt für sich hat aber meistens ein eigenes, lokales Koordinatensystem (localspace).

Wir können jetzt die Welt so transformieren, dass wir sie aus der Sicht des Objektessehen. Anschließend können wir lokale Betrachtungen/Berechnungen sehr viel einfachervornehmen.


Transformationen Objekt vs. Koordinatensystem


SimpleSoccer – Eine einfache Fußballsimulation


Hallenfußball - 5 gegen 5

Bande

Torlinie


Feldaufteilung für Positionierung

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17


Die drei Zustände der Mannschaften

Anstoss Verteidigung

Angriff

Startpositionen der Spieler

Angriffsformation

Verteidungsformation


Bewegungen des Torhüters


Torhüter im Zustand TendBall

Zwischen Ball und Tor positionieren


Grobe Bewertung der Mitspieler

B

A

CD

gut

schlecht riskant


Ermittlung des Best Support Spot (BSS)


BSS – Potential für weitere Pässe


BSS – Potential für Torschuss


BSS – Entfernung zu Gegenspieler


SimpleSoccer – Visualisierung des BSS


Schlüsselmethode: Sicherheit eines Passes

A

B

X

Y

W

Z



A

B

X

Y

W

Z




Angenommen, wir haben zwei Koordinatensysteme. A mit x, y und z und B mit x‘, y‘und z‘. Jetzt wollen wir v aus A nach B transformieren:

Koordinatentransformationen im 3D I


Wir konstruieren den neuen Vektor v‘ also über:

Koordinatentransformationen im 3D II

In Koordinatensystem A gilt und nach der Transformation gilt:

Für die Rücktransformation nutzen wir die Eigenschaft von orthogonalen Matrizen aus,denn es gilt .

Daher gilt die Vorschrift:

Das macht uns die Hin- und Rücktransformationen sehr einfach.

So macht uns Mathematik Spaß!


Ein Beispiel dazu aus dem 2-dimensionalen Raum. Wir wollen Vektoren aus demKoordinatensystem A in das um 45° gedrehte System B transformieren:

Beispiel im 2D-Raum I

21

1

2

1

-1

sin x cos x

Transformieren wir den Vektor v=(2,1) aus A nach B:

Warum ist dieser Schritt sinnvoll?


Transformieren wir den Vektor v=(2,1) von A nach B komplett (links) und zeigenanschließend mit Hilfe der transponierten Matrix, dass der ursprüngliche Vektor verfolgreich reproduziert werden kann:

Beispiel im 2D-Raum II

wir wissen (vielleicht noch) aus der Schule, dass

... und wir erhalten .


Das vorhergehende Beispiel hat uns nicht nur gezeigt, dass für orthogonale Matrizen dieInverse gerade die Transponierte ist, sondern darüber hinaus eine allgemeineTransformationsvorschrift für die Rotation im 2-dimensionalen Raum geliefert.

Transformationsvorschrift für Rotation

Die allgemeine Rotationsvorschrift lautet:

, mit

Wir können damit zwar die Achsen in verschiedene Richtungen rotieren, aber derUrsprung bleibt jeweils der gleiche. Die Objekte sollen sich aber nicht alle im Ursprungbefinden.

Dazu benötigen wir noch einen Translationsvektor:

das führt uns zu:

Zwei Dinge machen diese Form der Transformation nicht besonders schön:

1) Eine Transformation benötigt zwei Verarbeitungsstufen und 2) die Transformation unterscheidet nicht zwischen Vektoren die Punkte repräsentieren

und Vektoren die Richtungen repräsentieren.


Dafür gibt es mit den homogenen Koordinaten eine elegante Lösung. Es wird eine weitereKomponente hinzugefügt. Wenn Vektoren Richtungen repräsentieren, dann wird die w-Koordinate auf Null gesetzt. Ein Positionsvektor wird mit w=1 entsprechend markiert.

Homogene Koordinaten

world space

local space

Positionsvektoren

RichtungsvektorDie 3x3-Matrix mit Translationsvektor:

wird zu den homogenen Koordinaten wie folgt transformiert:

Es ist auch möglich, dass die w-Komponente weder 0 noch 1 ist, dann gilt:


Physikalische Spielereien sind so einfach mit Linearer Algebra.


Ein autonomer Agent, bestimmt seine Bewegung innerhalb einer gegebenen Welt durchfolgende drei Faktoren:

� Auswahl eines abstrakten Ziels/Plans (Action selection)

� Steuerung durch Einfluss unterschiedlicher Kräfte, die physikalischer oder spieltech-nischer Natur sind (Steering)

� Physikalisches Verhalten und Fähigkeiten der Fortbewegung (Locomotion)

� Modell unseres Agenten in der Umwelt:

Verhalten autonomer Agenten

Agent1

Hinderniss

Agent3

Agent2

Ziel (Plan)


Eigenschaften und Aufbau eines Agenten

Position

GeschwindigkeitGeschwindigkeit

Fahrtrichtung(normalisierter Ge-schwindigkeitsvektor)

Senkrechte zur Fahrtrichtung(normalisiert)

Massemax. Geschwindigkeitmax. Kraftmax. Drehrate

Position


Wenn wir einen Zielpunkt Ziel gegeben haben, dann gibt es eine Steuerungskraft, die direktin die Richtung des Ziels zeigt.

Steuerungskraft: Ziel folgen

norm (Zielkraft) maxGeschwindigkeit.

AgentPos

ZielPos

Zielrichtung ZielPos - AgentPos=

Geschwindigkeit

Zielkraft Zielrichtung - Geschwindigkeit=


Wir haben gesehen, dass unser Agent um das Ziel manövriert und nicht zur Ruhe kommt.Damit wir die Geschwindigkeit drosseln können, müssen wir den Agenten in Abhängigkeitzum Objektabstand abbremsen.

Steuerungskraft: Ziel erreichen

Ziel folgen in Abhaengigkeit des Abstands

Geschwindigkeit


Von einem Zielpunkt (kann sich bewegen) zu fliehen entspricht einfach nur dem negiertenFolgen.

Steuerungskraft: fliehen

Ziel folgen

Geschwindigkeit

fliehen - (Ziel folgen)=


Wie lassen sich diese Kraftvektoren verwenden?Ein Beispiel kennen wir aus der Vergangenheit …


Bisher waren die beiden Funktionen update() und render() noch abhängig von t:

Funktionen update und render

...public void renderLoop() {

while (!Display.isCloseRequested()) {loescheBildschirm();

for (int i=1; i<=flummies.getFlummiSize(); i++) {Flummi aktFlummi = flummies.getFlummi(i);aktFlummi.update();aktFlummi.render();

}

Display.update();}

}...


Ein Blick in die update-Funktion zeigt die Anpassung der Position in Abhängigkeit zurGeschwindigkeit:

Funktionen update und render

public class VerhaltenPerfekterFlummi implements Verhalten {private Flummi flummi;

public VerhaltenPerfekterFlummi(Flummi flummi) {this.flummi = flummi;

}

@Overridepublic void update() {

flummi.yPos += flummi.ySpeed;

if (flummi.yPos>480 || flummi.yPos<0)flummi.ySpeed *= -1;

}}

Die Geschwindigkeit direkt auf die Position zu addieren klingt zunächst nicht unplausibel, aberwie müssten wir das jetzt mit den Kräften in Einklang bringen?


Vektoren erleichtern uns die Handhabung der Parameter.


Wir führen drei nützliche Klassen zur Verwendung von Linearer Algebra ein:

Vektor2D, Vektor3D und LineareAlgebra

package math;

public class Vektor2D {public float x, y;

public Vektor2D() {this(0, 0);

}

public Vektor2D(float x, float y) {setX(x);setY(y);

}

public Vektor2D(Vektor2D vec) {this(vec.x, vec.y);

}

public Vektor2D(float x, float y, float x2, float y2) {this(x2 - x, y2 - y);

}

public Vektor2D(Vektor2D a, Vektor2D b) {this(b.getX() - a.getX(), b.getY() - a.getY());

}

public void setPosition(Vektor2D vec) {setX(vec.getX());setY(vec.getY());

}

public boolean isNullvector() {return (x == 0 && y == 0);

}

public void add(Vektor2D vec) {x += vec.x;y += vec.y;

}...

}

package math;

public class Vektor3D {public float x, y, z;

public Vektor3D() {this(0, 0, 0);

}

public Vektor3D(float x, float y, float z) {setX(x);setY(y);setZ(z);

}

public Vektor3D(Vektor3D vec) {this(vec.getX(), vec.getY(), vec.getZ());

}

public Vektor3D(float x, float y, float z, float x2, float y2, float z2) {

this(x2 - x, y2 - y, z2 - z);}

public Vektor3D(Vektor3D a, Vektor3D b) {this(b.getX() - a.getX(), b.getY() - a.getY(),

b.getZ() - a.getZ());}

public void setX(float x) {this.x = x;

}

public float getX() {return x;

}...

}

package math;

public class LineareAlgebra {private LineareAlgebra() {};

public static Vektor2D add(Vektor2D vec1, Vektor2D vec2) {

return new Vektor2D(vec1.getX()+vec2.getX(), vec1.getY()+vec2.getY());

}

public static Vektor3D add(Vektor3D vec1, Vektor3D vec2){

return new Vektor3D(vec1.getX()+vec2.getX(), vec1.getY()+vec2.getY(), vec1.getZ()+vec2.getZ());

}

public static Vektor2D sub(Vektor2D vec1, Vektor2D vec2) {

return new Vektor2D(vec1.getX()-vec2.getX(), vec1.getY()-vec2.getY());

}

public static Vektor3D sub(Vektor3D vec1, Vektor3D vec2){

return new Vektor3D(vec1.getX()-vec2.getX(), vec1.getY()-vec2.getY(),vec1.getZ()-vec2.getZ());

}

public static Vektor2D mult(Vektor2D vec, float s) {return new Vektor2D(vec.getX()*s, vec.getY()*s);

}

...}


Die Klassen werden entsprechend angepasst. Hier das Resultat der Anpassung von derKlasse VerhaltenPerfekterFlummi:

Anpassung an Vektoren

public class VerhaltenPerfekterFlummi implements Verhalten {private Flummi flummi;

public VerhaltenPerfekterFlummi(Flummi flummi) {this.flummi = flummi;

}

@Overridepublic void update() {

flummi.position.add(flummi.velocity);

if (flummi.position.y>480 || flummi.position.y<0)flummi.velocity.y *= -1;

}}


Allerdings wirken Objekte mit konstanten Geschwindigkeiten nicht sehr realisitisch.


Wir erweitern das Objektmodell mit position/velocity umacceleration

Vektor3D

Vektor3D

Vektor3D


Die Funktion update wird um die Beschleunigung (acceleration) erweitert:

Erweiterung um acceleration

public void update() {velocity.add(acceleration);velocity.truncate(maxSpeed);position.add(velocity);

}


1) Erzeugen Sie viele Flummies und verwenden zufällige Beschleunigungsvektoren zurÄnderung der Geschwindigkeiten.

2) Erzeugen Sie eine Beschleunigung in Richtung eines Mausklicks und sehen was passiert.Kennen Sie eine Möglichkeit, genau bei dem Mausklick zu landen?

Übungsvorschläge


„A force is a vector that causes an object with mass to accelerate.“ (Newton)

Ein Blick ins Physikbuch

Newton hat noch mehr schlaue Sachen gesagt:

I) Newtons first law of motion:

„An object at rest stays at rest and an object in motion stays in motion.“

„… at a constant speed and direction unless acted upon by an unbalanced force.“

„An objects velocity (Vektor3D) will remain constant if it is in a state of equilibrium.“

III) Newtons third law of motion:

„For every action there is an equal and opposite reaction.“

„Forces always occur in pairs. The two forces are of equal strength, but opposite

direction.“

II) Newtons second law of motion:

„Force equals mass times acceleration.“�� ∙ ��

��


Hier der kleine aber feine Unterschied (bzw. Zusammenhang) von Masse und Gewicht:

Masse [kg]

Gewicht = Masse • g [N = newton]

Ein Objekt mit der Masse von 1 kg auf der Erde hat auch 1 kg Masse auf dem Mond. DasObjekt wiegt allerdings nur ein Sechstel auf dem Mond!

Gewicht versus Masse

Gravitationsbeschleunigung


Dann wollen wir unser Konzept verfeinern


Wenn wir die Masse für einen Moment mal ausser Acht lassen und nur die Kraft betrachten:

Erweiterung um acceleration

applyForce(Vektor3D force) {acceleration = force;

}

Wenn wir später aber mehrere Kräfte hinzufügen wollen

applyForce(wind);applyForce(gravitation);...

benötigen wir hier die Akumulation von Kräften:

object.applyForce(wind);object.applyForce(gravitation);object.update();object.render();...


Ein Blick ins Physikbuch

Die gute Nachricht: „Net Force equals mass times acceleration.“

��

Dann müssen wir bei der Funktion update allerdings darauf achten, die Beschleunigungimmer zu initialisieren, bzw. am Ende zu löschen:

public void update() {velocity.add(acceleration);velocity.truncate(maxSpeed);position.add(velocity);acceleration.mult(0);

}


Jetzt führen wir die Masse ein.


Wir erweitern das Objektmodell mit den Eigenschaften position/velocity/acceleration um mass

Vektor3D float


Wir könnten die Masse in applyForce direkt mit dem Kraftvektor verrechnen:

Einführung von mass (Versuch 1)

applyForce(Vektor3D force) {force.div(mass);acceleration = force;

}

�� ∙ ��

��


Was könnte schief gehen?


Mit dieser Version der applyForce-Methode ändern wir den Kraftvektor, was Auswirkungenauf weitere Funktionsaufrufe hätte:

Einführung von mass (Versuch 2)

Wir könnten aber einmal eine Kraft berechnen und diese auf mehrere Akteure anwenden:

wind = ...obj1.applyForce(wind);obj2.applyForce(wind);...

applyForce(Vektor3D force) {force.div(mass);acceleration.add(force);

}

Eine einfache Lösung lautet:

applyForce(Vektor3D force) {Vektor3D forceCopy = new Vektor3D(force);forceCopy.div(mass);acceleration.add(forceCopy);

}

Documents

computergrafikII 10 Physikalische Spielereien · Prof. Dr. Marco Block-Berlitz Vorlesung Computergrafik II SoSe 2014 Folie 5 Schauen wir uns noch einmal die Trigonometrie (trigon,