Darth lehrt: 2D Vektoren

Übersicht BlitzBasic FAQ und Tutorials

Neue Antwort erstellen

darth

Betreff: Darth lehrt: 2D Vektoren

BeitragFr, Jan 13, 2012 0:20
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,

viele Leute haben aus mir unerklärlichen Gründen immer Angst vor Vektoren, das muss nicht sein, Vektoren sind ganz lieb und hilfreich! In diesem Beitrag beschäftige ich mich vor allem im 2D-Raum, aber die Erweiterung zu 3D (und weiter) sollte eigentlich klar sein. Ich habe das Tutorial noch nicht völlig ausgeplant..
Zitat:
"I'll make it up as i go"


1.0 Grundsätzliches

Was ist ein Vektor? Ein Vektor ist eine Richtung (mit einer bestimmten Länge). Er hat keinen "Platz" als solches, er kann beliebig verschoben werden und bleibt immer der selbe.
Zitat:
"Aber Darth, ein Punkt ist doch auch ein Vektor?", fragte eine Nachhilfeschülerin, worauf ich antwortete: "Jein."

Ein Punkt kann mittels eines Vektors dargestellt werden. Was man dort macht, ist den Vektor einfach zum Ursprung zu addieren und man erhält den Punkt, das nennt sich Ortsvektor.

user posted image
(Src: http://lernprocessing.files.wo...vektor.png)

Wie man sieht, hat der Vektor verschiedene Komponenten, in jede Richtung eine. In dem Beispiel wäre der Vektor P = [4 ; 2].
Das geht übrigens für beliebig viele Dimensionen. Das führt dann direkt zu unserem Vektor-Type!

BlitzBasic: [AUSKLAPPEN]
Type TVector2
Field x#
Field y#
End Type

Function newVector2.TVector2(x#, y#)
Local v.TVector2 = New TVector2

v\x = x
v\y = y

Return v
End Function


Damit wären mal die Grundlagen geschaffen. Jetzt soll es aber möglich sein, damit zu arbeiten. Wie immer in der Mathematik, müssen wir also die Rechenregeln für unsere Elemente definieren.

1.1 Rechenregeln

1.1.1 Addition, Subtraktion

Wenn man Vektoren addiert, macht man das komponentenweise. Wie oben erwähnt, hat jeder Vektor für jede Richtung eine Komponente. Bei der Addition wird jetzt also jede Komponente von Vektor A zur gleichen Komponente von Vektor B addiert. Zu kompliziert? Code:

BlitzBasic: [AUSKLAPPEN]
Function vAdd.TVector2(a.TVector2, b.TVector2)
Local r.TVector2 = New TVector2

r\x = a\x + b\x
r\y = a\y + b\y

Return r
End Function


Ihr könnt euch das nicht vorstellen? Hier ein Bild:

user posted image
(Src: http://www.mathe-online.at/mat...0.htm2.gif)

Eine Subtraktion ist eine umgekehrte Addition. Da gibts nicht wirklich viel zu erklären.

BlitzBasic: [AUSKLAPPEN]
Function vSub.TVector2(a.TVector2, b.TVector2)
Local r.TVector2 = New TVector2

r\x = a\x - b\x
r\y = a\y - b\y

Return r
End Function


1.1.2 Multiplikation

Vektoren können nicht einfach Multipliziert werden. Es gibt verschiedene Arten von Multiplikation.

Eine ist die Skalarmultiplikation (und der Name wird euch später noch verwirren). Das heisst man multipliziert den Vektor mit einem Skalar.

Zitat:
"Aber Darth, was ist denn ein Skalar?", fragte die Nachhilfeschülerin. Leicht genervt antwortete ich knapp: "Es ist einfach eine Zahl. Ganz einfach!"


Das geht wieder Komponentenweise. Jede Komponente wird mit der Zahl multipliziert, und fertig ist der ganze Zauber. Hiermit wird ein Vektor gestreckt (für s > 1) oder gestaucht (für s < 1).

BlitzBasic: [AUSKLAPPEN]
Function vMult.TVector2(a.TVector2, s#)
Local r.TVector2 = New TVector2

r\x = a\x * s
r\y = a\y * s

Return r
End Function


Im Gegensatz zu Addition/Subtraktion ist es unüblich, hier eine Funktion für die skalare Division zu schreiben. Jede Division kann als Multiplikation geschrieben werden, von daher ist es etwas sinnlos.
Code: [AUSKLAPPEN]
V / 2 = V * (1/2)


Dann gibt es aber noch die Vektormultiplikation (wird hin und wieder auch Skalarmultiplikation genannt weil:), deren Resultat das Skalarprodukt genannt wird. Das Skalarprodukt ist, wie der Name schon sagt, ein Skalar (das ein Produkt aus den Vektoren ist). Zu Englisch: Dotproduct.
Hier multipliziert man die Komponenten miteinander und summiert sie dann alle auf.

BlitzBasic: [AUSKLAPPEN]
Function vDot#(a.TVector2, b.TVector2)
Return a\x * b\x + a\y * b\y
End Function


Zitat:
"Aber wozu braucht man sowas denn?", fragte die Nachhilfeschülerin. Ich schaute ihr freundlich in ihre grossen blauen Augen (sie ist über 18 btw) und sagte mit samtweicher Stimme: "Gedulde dich mein Kind (ich bin weit über 18 btw), das folgt in Kürze."


Der Vollständigkeit halber erwähne ich auch noch kurz das Kreuzprodukt (engl: Crossprodukt). Das ist allerdings nur in 3D definiert und liefert einen Vektor, der rechtwinklig auf den beiden Multiplikanden steht. Aber ist im Moment nicht wirklich wichtig, wen es interessiert, kann es hier nachlesen. Hint: Rechte Hand Regel.

Division von Vektoren gibt es nicht. Punkt!

2.0 Eigenschaften

2.1 Länge

Jeder Vektor hat eine Länge. Diese wird ganz einfach dem Satz des Pythagoras berechnet. Wieso geht das? Hier ein Beispielbild:

user posted image
(Src: http://eliteinformatiker.de/wp...euclid.png)

Wie man sieht, bilden die Komponenten des Vektors ein rechtwinkliges Dreieck, mit dem Vektor selber als Hypothenuse. Also Pythagoras! (Der funktioniert überigens auch in beliebig vielen Dimensionen!)

Zitat:
"Aber Darth, da sind Punkte und keine Komponenten. Was mach ich jetzt?", wurde ich gefragt. Die Antwort ist einfach: "Stell dir vor, du rennst in einem Rennen und bist bei 50m, jetzt willst du nach 60m, was machst du? Genau, du gehst 10m nach vorne. Das heisst 60-50 = 10. Klar?".


Das Gleiche kann man auch auf Punkte anwenden. Der Vektor von A zu B ist dann einfach A - B, wobei A und B Ortsvektoren sind und jeweils eine X und Y Koordinate haben. Der Vektor dazwischen (c auf dem Bild) ist dann also V = [B\x - A\x ; B\y - A\y]. Damit sollten dann auch die Komponenten klar sein, die das Dreieck bilden: V\x ist die untere Ankathete b, V\y ist die rechte Gegenkathete a, und der Vektor V selber ist die Hypothenuse c (deren Länge durch den Pythagoras definiert ist, wie oben erwähnt).

Vielleicht ein zweites Bild dazu, welches die Aufteilung des Vektors in seine Komponenten zeigt (Vektor a = [ax ; ay]):

user posted image
(Src: http://www.frustfrei-lernen.de...vektor.jpg)

BlitzBasic: [AUSKLAPPEN]
Function vLength#(a.TVector2)
Return Sqr(a\x * a\x + a\y * a\y)
End Function


Vektoren mit Länge 1 nennt man normalisiert. Wie macht man das? Ganz einfach, man Dividiert den Vektor durch seine Länge! (Kann man mathematisch ganz einfach beweisen, überlasse ich meiner Nachhilfeschülerin..)

BlitzBasic: [AUSKLAPPEN]
Function vNormalise(a.TVector2)
Local l# = vLength(a)

a\x = a\x / l
a\y = a\y / l
End Function


(ANM: Mir ist bewusst, dass ich hier etwas inkonsistent bin. Vorher haben die Funktionen immer einen neuen Vektor zurückgeliefert. Prinzipiell sollte man noch funktionen schreiben, die den Vektor selber verändern. Also so, dass Vektor b direkt zu Vektor a addiert wird usw.. Wie das geht sollte klar sein, das überlasse ich jedem selbst.)

2.2 Winkel zwischen Vektoren

Das Skalarprodukt zweier Vektoren ist der Cosinus des Winkels zwischen ihnen.
Code: [AUSKLAPPEN]
a = ACos(A * B)


Ich wurde freundlicherweise auf einen kleinen Flüchtigkeitsfehler aufmerksam gemacht. Damit die oben angegebene Formel stimmt, müssen A und B normalisiert sein. Generell würde gelten:
Code: [AUSKLAPPEN]
phi = ACos(A * B / (a * b))

Wobei a = |A| die Länge von Vektor A ist und b = |B| die Länge des Vektors B.

Der Cosinus hat die tolle Eigenschaft, dass er bei 90° (oder PI/2) 0 ist. Das heisst, wenn A * B = 0 sind die beiden Vektoren senkrecht (rechtwinklig) zueinander.
(Ist das Kreuzprodukt zweier Vektoren 0, sind sie parallel, aber das funktioniert hier leider nicht.)

Diesen senkrechten Vektor nennt man auch die Normale. Wie irgendwo oben mal erwähnt, kann man solche Vektoren mit dem Kreuzprodukt errechnen. Das geht auch hier, indem man den Vektor um eine Dimension erweitert und mit der Ebenennormalen kreuzmultipliziert. Zu kompliziert?
Code: [AUSKLAPPEN]
N = [Ax ; Ay ; 0] x [0 ; 0 ; 1]

Was rauskommt ist: N = [Ay ; -Ax]. Oder als Code:

BlitzBasic: [AUSKLAPPEN]
Function vNormal.TVector2(a.TVector2)
Local r.TVector2 = New TVector2

r\x = a\y
r\y = -a\x

Return r
End Function

(Nicht verwechseln mit normalisieren!)

To be continued..

Der Beitrag ist schon viel zu lange, deshalb werde ich hier mal splitten. Ich hoffe es postet mir niemand dazwischen, während ich den zweiten Teil schreibe. Falls doch, ist es eine fiese Socke (nicht zu verwechseln mit aTnSocke!) und ich werde einen freundlichen Mod bitten, den Beitrag zu entfernen! OH JA! *droh* Bis dahin,

Cheers,
Darth
Diese Signatur ist leer.
  • Zuletzt bearbeitet von darth am Mi, Feb 01, 2012 19:43, insgesamt 5-mal bearbeitet

darth

BeitragFr, Jan 13, 2012 0:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,

Doppelpost. Wieso? Weil ichs kann! Gut, weiter gehts!

3.0 Geraden

3.1 Geradengleichung

Ich habe eingangs mal erwähnt, dass Vektoren Richtungen sind, nicht mehr, nicht weniger. Das macht sie aber nicht zu Geraden! Eine Gerade braucht immer einen Aufhängepunkt. Mit einem Vektor und einem Punkt ist eine Gerade komplett definiert.
Es gibt zwei Arten, eine Gerade darzustellen, die erste Möglichkeit nennt sich Parametergleichung:
Code: [AUSKLAPPEN]
P = A + t * G

Wobei P einen beliebigen Punkt auf der Geraden beschreibt, A den Aufhängepunkt und G den Geradenvektor. Diese Methode macht es einfach, sich das ganze vorzustellen. Wenn man sich daran erinnert, dass eine skalare Multiplikation den Vektor streckt sieht man, dass man beliebige Abschnitte von G zu A dazuzählen kann, und dann jeden Punkt (in beide Richtungen! t kann negativ sein) erreichen kann, der auf der Gerade liegt. Leider heisst das, dass man immer 2 Gleichungen behandeln muss, und das ist mühsam.

Zitat:
"Aber was für zwei Gleichungen sind das denn Darth?", fragte die Nachhilfeschülerin. Etwas verwirrt antwortete ich: "Na.. eine für jede Komponente. Du siehst ja, der Ortsvektor A (Vektoren sind keine Punkte haben wir festgestellt, du erinnerst dich?) hat eine Komponente für X und eine für Y, genauso der Geradenvektor von G, t ist ein Skalar - und wie man damit umgeht hast du auch gesehen. Das heisst du hast für die Koordinaten von P = [X ; Y] je eine Gleichung, und 1+1 gibt 2."


Daher hat sich irgend ein kluger Kopf eine andere Methode ausgedacht. Die Geradengleichung. Und so sieht sie aus:
Code: [AUSKLAPPEN]
A * x + B * y + C = 0

Das sagt den meisten wohl nichts, vor allem fragen sich wohl viele, was denn jetzt A, B und C sein sollen. Dazu muss man erst einmal verstehen, wie die Gleichung funktioniert. Diese Gleichung misst eingentlich den Abstand eines Punktes zur Gerade (und wenn der Abstand 0 ist, liegt er darauf - logisch, nichwahr?).

Wie misst man den Abstand eines Punktes zu einer Geraden (keine Angst, die mathematische Methode folgt in Kürze!) Man nimmt den kleinstmöglichen Abstand, und der ist immer durch das Lot definiert.

user posted image
(Src: http://www.hinterseher.de/Dipl...Gerade.GIF)

Das bringt uns schon A und B! Denn das sind die Komponenten der Normalen zum Geradenvektor. Wer sich nicht mehr erinnert (soll sich schämen..): [A ; B] = [Gy ; -Gx].

C ist der Offset. Nicht jede Gerade soll durch den Ursprung (U = [0 ; 0]) gehen, sondern durch beliebige Punkte P. Dafür löst man die Gleichung einfach für den Punkt P auf, der sicher auf der Geraden liegen soll.
Code: [AUSKLAPPEN]
A * Px + B * Py + C = 0 <=> C = - A * Px - B * Py


Und der Zauber wäre vollbracht. Abrakadabra.

3.2 Abstandsproblem

Wie misst man aber einen allgemeinen Abstand d (siehe Bild oben)? Dafür benutzt man die Hessesche Normalform. Da der Wikipedia-Artikel aber "zu kompliziert" ist, hier die Kurzversion:

Code: [AUSKLAPPEN]
    A * x + B * y + C
d = -----------------
     sqr(A^2 + B^2)


Generell gesprochen wird hier eigentlich eine Gleichung gelöst: Um wieviel muss man die Normale strecken, bis sie den Punkt P erreicht? (Oder von Punkt P die Gerade schneidet).

3.3 Geradenschnitte

Für Geradenschnitte muss man ein wenig Arithmetik betreiben. Generell muss man einen Punkt suchen, der auf beiden Geraden liegt, das heisst beide Geradengleichungen müssen erfüllt sein. Dann hat man zwei Gleichungen und zwei Unbekannte.

Das Problem kann man in verschiedenen Schwierigkeitsstufen lösen. Eigentlich schneiden sich zwei Geraden ja immer (es sei denn sie sind parallel). Segmentschnitte sind eine etwas andere Frage. (Und hier ist leider die Version in 3D etwas komplizierter als in 2D).

Da mir langsam etwas die Motivation ausgeht, verweise ich euch auf eine sehr gute Anleitung: Siehe hier. Ist auf zwar auf englisch, aber die Rechnungen kann jeder nachbasteln.
Wichtig ist einfach: ua und ub müssen zwischen 0 und 1 sein, dann liegt der Schnittpunkt auf beiden Segmenten. Dadurch kann man die Komplexität des Schnittes steuern. Jenachdem ob man eine Bedingung für die u einschiebt oder nicht.

4.0 Zusätzliches

Parallel zur Motivation gehen mir auch die Ideen aus, was ich noch bringen könnte. Eine kleine Rechnung, die immer wieder mal für Spiele gebraucht wird ist zum Beispiel die Reflektion von Vektoren an Geraden (für abprallende Bälle).

4.1 Reflektion

Für die Vektorreflektion wollen die meisten immer mit dem alten Lehrsatz "Einfallwinkel = Ausfallswinkel" punkten. Das stimmt natürlich, macht die Sache nur leider unsinnig kompliziert. Es gibt eine viel einfachere Formel für Vektoren.
Code: [AUSKLAPPEN]
R = V - 2 * N * (N * V)

Wobei R der Reflektierte Vektor ist, V der Vektor den man Reflektieren will und N die Normale der Gerade an der man Reflektiert. Wobei N normalisiert sein muss.

user posted image
(Src: http://www.asawicki.info/files/Reflect_Refract.png)

Zu beachten ist, dass es hier völlig egal ist WO man reflektiert, der Entscheid ob überhaupt reflektiert werden soll, muss woanders getroffen werden! (Siehe Geradenschnitt).

Verpackt im Code sähe das so aus:
BlitzBasic: [AUSKLAPPEN]
Function vReflect.TVector2D(v.TVector2D, n.TVector2D)
Local r.TVector2D
Local dp#, nl#

vs = New TVector2D

nl = vLength2D(n)
dp = 2*vDot3D(v, n) /(nl *nl)

r\x = v\x - dp *n\x
r\y = v\y - dp *n\y
r\z = v\z - dp *n\z

Return r
End Function


Zitat:
"Wie kommst du denn von der schönen Formel auf diesen komischen Code?", fragte die Nachhilfeschülerin verwirrt. Also nahm ich ein Stück Papier hervor und begann zu schreiben:
"R = V - 2 * N * (N * V)"
"Ich habe dir ja gesagt, das gilt nur für normalisierte Vektoren, nichtwahr? Aber Anwender sind oft faul, oder wollen aus anderen Gründen ihre Vektoren nicht normalisieren. Also machen wir das für sie!"
"R = V - 2 * N/n * (N/n * V)"
"(N * V) ist ein Skalarprodukt, das wird dann über eine skalare Multiplikation mit dem N Vektor verrechnet, die 2 ist auch ein Skalar, das nehmen wir gleich mit."
"s = 2 * (N * V) /n /n = 2 * (N * V) / n^2"
"Klar soweit? Ja? Sehr gut. Was bleibt jetzt von der Gleichung noch übrig?"
"R = V - s * N"
"Sehr gut. Und nun sieh dir die letzten drei Rechenschritte im Code an, was wird dort gemacht? Genau! Man macht genau das.. Eine skalare Multiplikation von N (mit s) wird vom einfallenden Vektor V abgezogen. Sehr gut, hast dus jetzt verstanden?"
Worauf sie nickte und ich ihr ein freundliches Lächeln schenkte, weil sie so eine brave und aufmerksame Nachhilfeschülerin ist.


4.2 Finale

Als Abschluss (weil mir jetzt wirklich nichtsmehr einfällt) poste ich hier meine TVector3D.bb "Library", enthält auch gewisse Dreicksberechnungen. Diese Funktionen können ohne weiteres in 2D übernommen werden, indem man einfach z = 0 setzt überall. (Natürlich sind Dreiecke dann reichlich sinnlos..)

BlitzBasic: [AUSKLAPPEN]
;/*
; * Vectors
; *
; * TVector3D
; * Standard 3D Vector
; * enthält zusätzlich eine Grösse d (für Offsets)
; * sowie UV Koordinaten
; *
; * newTVector3D(x, y, z)
; * Standard Konstruktor
; *
; * vNormalise3D(v)
; * normalisiert den Vektor
; *
; * vDot3D(v1, v2)
; * Vektorprodukt, v1 * v2
; *
; * vCross3D(v1, v2)
; * Kreuzprodukt, v1 x v2
; *
; * vDist3D(v1, v2)
; * Distanz zwischen zwei Punkten |v1 - v2|
; *
; * vLength3D(v)
; * Länge des Vektors
; *
; * vReflect3D(v, n)
; * Reflektiert den Vektor an einer Ebene, anhand des Normalenvektors
; *
; * lineSegmentIntersect3D(p1, p2, p3, p4)
; * Schneidet die beiden Segmente (p1, p2) - (p3, p4)
; */

Type TVector3D
Field x#
Field y#
Field z#

Field d#

Field u#
Field v#
End Type

Function newTVector3D.TVector3D(x#, y#, z#)
Local v.TVector3D = New TVector3D

v\x = x
v\y = y
v\z = z

Return v
End Function

Function vAdd3D( v.TVector3D, o.TVector3D )
v\x = v\x + o\x
v\y = v\y + o\y
v\z = v\z + o\z
End Function

Function nAdd3D.TVector3D( a.TVector3D, b.TVector3D )
Local r.TVector3D = New TVector3D

r\x = a\x + b\x
r\y = a\y + b\y
r\z = a\z + b\z

Return r
End Function

Function vSub3D( v.TVector3D, o.TVector3D )
v\x = v\x - o\x
v\y = v\y - o\y
v\z = v\z - o\z
End Function

Function nSub3D.TVector3D( a.TVector3D, b.TVector3D )
Local r.TVector3D = New TVector3D

r\x = a\x - b\x
r\y = a\y - b\y
r\z = a\z - b\z

Return r
End Function

Function vMult3D( v.TVector3D, s# )
v\x = v\x *s
v\y = v\y *s
v\z = v\z *s
End Function

Function nMult3D.TVector3D( v.TVector3D, s# )
Local r.TVector3D = New TVector3D

r\x = v\x *s
r\y = v\y *s
r\z = v\z *s

Return r
End Function

Function vNormalise3D(v.TVector3D)
Local il# = 1./Sqr(v\x*v\x + v\y*v\y + v\z*v\z)

v\x = v\x *il
v\y = v\y *il
v\z = v\z *il
End Function

Function vDot3D#(v1.TVector3D, v2.TVector3D)
Return v1\x*v2\x + v1\y*v2\y + v1\z*v2\z
End Function

Function vCross3D.TVector3D(v1.TVector3D, v2.TVector3D)
Return newTVector3D(v1\y*v2\z-v2\y*v1\z, v2\x*v1\z-v1\x*v2\z, v1\x*v2\y-v2\x*v1\y)
End Function

Function vDist3D#(v1.TVector3D, v2.TVector3D)
Return Sqr( (v1\x-v2\x)*(v1\x-v2\x) + (v1\y-v2\y)*(v1\y-v2\y) + (v1\z-v2\z)*(v1\z-v2\z) )
End Function

Function vLength3D#(v.TVector3D)
Return Sqr( v\x*v\x + v\y*v\y + v\z*v\z )
End Function

Function vReflect3D.TVector3D(v.TVector3D, n.TVector3D)
Local vs.TVector3D
Local dp#, nl#

vs = New TVector3D

nl = vLength3D(n)
dp = 2*vDot3D(v, n) /(nl *nl)

vs\x = v\x -dp *n\x
vs\y = v\y -dp *n\y
vs\z = v\z -dp *n\z

Return vs
End Function

Function lineSegmentIntersect3D.TVector3D(p1.TVector3D, p2.TVector3D, p3.TVector3D, p4.TVector3D)
Local EPS#=10^-8

Local p13.TVector3D, p43.TVector3D, p21.TVector3D
Local d1343#, d4321#, d1321#, d4343#, d2121#
Local numer#, denom#, mua#, mub#

p13=newTVector3D(p1\x-p3\x, p1\y-p3\y, p1\z-p3\z)

p43=newTVector3D(p4\x-p3\x, p4\y-p3\y, p4\z-p3\z)
If Abs(p43\x)<EPS And Abs(p43\y)<EPS And Abs(p43\z)<EPS
Delete p13
Delete p43

Return Null
EndIf

p21=newTVector3D(p2\x-p1\x, p2\y-p1\y, p2\z-p1\z)
If Abs(p21\x)<EPS And Abs(p21\y)<EPS And Abs(p21\z)<EPS
Delete p13
Delete p43
Delete p21

Return Null
EndIf

d1343 = p13\x * p43\x + p13\y * p43\y + p13\z * p43\z
d4321 = p43\x * p21\x + p43\y * p21\y + p43\z * p21\z
d1321 = p13\x * p21\x + p13\y * p21\y + p13\z * p21\z
d4343 = p43\x * p43\x + p43\y * p43\y + p43\z * p43\z
d2121 = p21\x * p21\x + p21\y * p21\y + p21\z * p21\z

denom = d2121*d4343 -d4321*d4321
If Abs(denom)<EPS
Delete p13
Delete p43
Delete p21

Return Null
EndIf

numer=d1343*d4321 -d1321*d4343

mua=numer/denom
mub=(d1343+d4321*mua)/d4343

Local pA.TVector3D=newTVector3D(p1\x+mua*p21\x, p1\y+mua*p21\y, p1\z+mua*p21\z)
Local pB.TVector3D=newTVector3D(p3\x+mub*p43\x, p3\y+mub*p43\y, p3\z+mub*p43\z)

Delete p13
Delete p43
Delete p21

If equalPoints3D(pA, pB)
If mua>=0 And mua<=1 And mub>=0 And mub<=1
Delete pB
Return pA
EndIf
EndIf

Delete pA
Delete pB

Return Null
End Function

Function equalPoints3D(p1.TVector3D, p2.TVector3D)
Local dist#=0.5

If p1=p2
Return True
EndIf

If Abs(p1\x-p2\x)<dist And Abs(p1\y-p2\y)<dist And Abs(p1\z-p2\z)<dist
Return True
EndIf

Return False
End Function

;/*
; * Triangles
; *
; * TTrig3D
; * Dreieck in 3D
; * enthält die 3 Punkte, sowie den Normalenvektor (+Offset)
; * zusätzliche Eigenschaften wie Farbe, Textur, Alpha,..
; *
; * newTTrig3D(p1, p2, p3)
; * Konstruktor
; *
; * linePlaneIntersection3D(p, v, t)
; * liefert den Schnittpunkt zwischen der Geraden und der Dreiecksebene
; *
; * pointInTrig3D(x, y, z, t)
; * Boolean, Punkt im Dreieck
; */

Type TTrig3D
Field p1.TVector3D
Field p2.TVector3D
Field p3.TVector3D

Field n.TVector3D

Field r
Field g
Field b

Field alpha
Field reflect
End Type

Function newTTrig3D.TTrig3D(p1.TVector3D, p2.TVector3D, p3.TVector3D)
Local t.TTrig3D=New TTrig3D

t\p1=p1
t\p2=p2
t\p3=p3

Local vx1# = p2\x-p1\x
Local vy1# = p2\y-p1\y
Local vz1# = p2\z-p1\z

Local vx2# = p3\x-p1\x
Local vy2# = p3\y-p1\y
Local vz2# = p3\z-p1\z

t\n=newTVector3D(vy1*vz2-vz1*vy2, vz1*vx2-vx1*vz2, vx1*vy2-vy1*vx2)
vNormalise3D(t\n)
t\n\d= -t\n\x*p3\x -t\n\y*p3\y -t\n\z*p3\z

t\r = 255
t\g = 255
t\b = 255

t\alpha = 100
t\reflect = 0

Return t
End Function

Function linePlaneIntersection3D.TVector3D(p.TVector3D, v.TVector3D, t.TTrig3D)
If Abs(v\x*t\n\x + v\y*t\n\y + v\z*t\n\z)<1
Return Null
EndIf

If Abs(p\x*t\n\x + p\y*t\n\y + p\z*t\n\z + t\n\d)<0.1
Return newTVector3D(p\x, p\y, p\z)
EndIf

Local k#= -(t\n\x*p\x +t\n\y*p\y +t\n\z*p\z +t\n\d)/(t\n\x*v\x +t\n\y*v\y +t\n\z*v\z)

Return newTVector3D(p\x+k*v\x, p\y+k*v\y, p\z+k*v\z)
End Function

Function pointInTrig3D(x#, y#, z#, t.TTrig3D)
If Abs(x*t\n\x + y*t\n\y + z*t\n\z + t\n\d)>1
Return False
EndIf

Local v0.TVector3D, v1.TVector3D, v2.TVector3D

v0 = newTVector3D(t\p3\x-t\p1\x, t\p3\y-t\p1\y, t\p3\z-t\p1\z)
v1 = newTVector3D(t\p2\x-t\p1\x, t\p2\y-t\p1\y, t\p2\z-t\p1\z)
v2 = newTVector3D(x-t\p1\x, y-t\p1\y, z-t\p1\z)

Local dot00#, dot01#, dot02#, dot11#, dot12#

dot00 = vDot3D(v0, v0)
dot01 = vDot3D(v0, v1)
dot02 = vDot3D(v0, v2)
dot11 = vDot3D(v1, v1)
dot12 = vDot3D(v1, v2)

Delete v0
Delete v1
Delete v2

Local invDet# = 1./(dot00*dot11 - dot01*dot01)
Local u# = (dot11*dot02 - dot01*dot12) *invDet
Local v# = (dot00*dot12 - dot01*dot02) *invDet

Return (u>=0) And (v>=0) And (u+v<=1)
End Function


Done

Falls irgendjemand Fragen hat, gibt es sicher Leute die diese gerne beantworten. Sollten irgendwelche Ergänzungen gewünscht sein (Themen die ich vergessen habe, die wichtig sein könnten), dann postet diese doch bitte im Anschluss. Ich hoffe ich habe das Thema nicht "zu kompliziert" dargestellt sondern einigermassen verständlich. Wichtig ist einfach, dass man nicht direkt aufgibt wenn man Begirffe liest die man nicht versteht. Man muss nicht alles verstehen, um damit umgehen zu können.
Zudem gibt es im Internet massenweise Hilfe, weil Vektoren ein ziemlich weit verbreitetes Thema in der Programmierung sind. Wer damit nicht umgehen kann ist über kurz oder lang aufgeschmissen. Von daher: Tough Luck!

Cheers,
Darth
Diese Signatur ist leer.

darth

BeitragSa, Jan 21, 2012 2:49
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,

ich denke mal, es ist an der Zeit, dass ihr ein wenig lineare Algebra lernt. Wer jetzt schon aussteigt, weil es kompliziert klingt, ist hier falsch, zum Rapseminar gehts die Treppe runter, in den Keller.. wo ihr hoffentlich bleibt Sad Niemand will euch rappen hören, kthx. (HA! ich Troll ich!)

5.0 Matrizen

Was ist eine Matrix? Falls ihr den Film Matrix gesehen habt und nun denkt: "Das weiss ich!" muss ich euch enttäuschen. Das hat so ziemlich überhaupt nichts damit zu tun. Viel eher ist eine Matrix eine .. Tabelle (im weitesten Sinne des Wortes, und auch nur, wenn mans ganz einfach erklären will).

user posted image
(Src: http://upload.wikimedia.org/wi...german.svg)

Ich werde vorläufig mal im 2D-Raum bleiben. Allgemeine LinAlg zu betreiben hat hier wohl wenig Sinn, weil die wenigsten es zu schätzen wüssten (es gibt hübsche Beweise die man zeigen könnte, und nützliche Eigenschaften).

Normalerweise benutzt man hier 2x2 Matrizen. Was bedeutet das? Wenn ihr euch das Bild oben anschaut seht ihr die beiden Pfeile (rot und blau) mit dem m x n darüber. Diese Zahlen beschreiben die Grösse der Matrix (ich will es hier nicht Dimension nennen, weil eine Matrix eigentlich immer nur zwei Dimensionen hat).

Hier ein einfacher 2x2-Matrix-Type:

BlitzBasic: [AUSKLAPPEN]
Type Matrix2
Field e11#
Field e12#

Field e21#
Field e22#
End Type

Function newMatrix.Matrix2(e11#, e12#, e21#, e22#)
Local m.Matrix2 = New Matrix2

m\e11 = e11 : m\e12 = e12
m\e21 = e21 : m\e22 = e22

Return m
End Function


5.1 Grundsätze der Matrixmultiplikation

Grundsätzlich gilt bei der Matrixmultiplikation, dass sie nicht kommutativ ist. Das heisst: A * B != B * a. Hier der Lehrsatz zur Matrixmultiplikation:
Zitat:
Zeile mal Spalte.


Damit dies aufgeht, muss in der Multiplikation A * B gelten, dass A\n = B\m. Die einzelnen Ergebnisse werden dann aufsummiert. Hier als (Pseudo)Codebeispiel (nicht in BB, das erlaubt ja keine 2D-Arrays..):

Code: [AUSKLAPPEN]
Function MMultiply(A#[m1, n1], B#[m2, n2])
   If (n1 != m2)
      Error "Inner Matrix Dimensions must agree"
   EndIf
   
   Local m3 = m1
   Local n3 = n2

   Local R#[m3, n3]
   
   For i = 1 To m3
      For j = 1 To n3
         For k = 1 To n1
            R[i, j] = R[i, j] + A[i, k] * B[k, j]
         Next
      Next
   Next

   return R
End Function

(Kleiner Disclaimer: Ich verwechsle gerne mal m und n. In meinem ursprünglichen Code war es gerade andersrum definiert als in der Wiki-Seite. Ich habe es umgekehrt und hoffe, keine Fehler eingebaut zu haben. Falls doch, werde ich es natürlich korrigieren.. Aber eigentlich sollte es stimmen.)

Hier ein Bild, das die Wirkung des Codes zeigt:

user posted image
(Src: http://www.grundstudium.info/l...nimg42.png)

Und hier eines, das es vllt verständlicher macht sich das Prinzip dahinter zu merken:

user posted image
(Src: http://www.faes.de/Basis/Basis...Falk_3.gif)

Aber genug vom allgemeinen. Wir sind hier in 2D, da ist das ganze noch überschaubar. Deshalb hier die zwei Multiplikationen, die man machen kann:
(i) Matrix * Matrix = Matrix
(ii) Matrix * Vektor = Vektor
(Anmerkung: Vektor * Matrix geht NICHT!)

BlitzBasic: [AUSKLAPPEN]
Function mmMult.Matrix2(a.Matrix2, b.Matrix2)
Local r.Matrix2 = New Matrix2

;beachte, wie A * B != B * A

r\e11 = a\e11 * b\e11 + a\e12 * b\e21
r\e12 = a\e11 * b\e12 + a\e12 * b\e22

r\e21 = a\e21 * b\e11 + a\e22 * b\e21
r\e22 = a\e21 * b\e12 + a\e22 * b\e22

Return r
End Function

Function mvMult.Vector2(a.Matrix2, v.Vector2)
Local r.Vector2 = New Vector2

r\x = a\e11 * v\x + a\e12 * v\y
r\y = a\e21 * v\x + a\e22 * v\y

Return r
End Function


5.2 Wie komme ich zur Matrix

Wissen, was man mit der Matrix anfangen kann ist das eine. Wie man auf eine Matrix kommt, die das gewünschte macht ist etwas anderes. Ich erkläre das immer gerne anhand des Einheitskreises.

user posted image
(Src: http://upload.wikimedia.org/wi...skreis.png)

Die meisten kennen wahrscheinlich den "Lehrsatz": x = r * cos(a) und y = r * sin(a). Das ergibt ein schönes rechtwinkliges Dreieck und wir können es alle sehen. Aber das liefert ein sehr schönes Beispiel! Wir (also.. ich) wollen nämlich eine Rotationsmatrix finden! Dazu schauen wir, was aus unseren beiden Basisvektoren wird.

Was ist ein Basisvektor? Es sind die Eigenvektoren unserer Matrix. Sagt euch das was? Wenn ja, dann wisst ihr schon viel mehr als ich in diesem kurzen Tutorial erklären werde, ihr verschwendet eure Zeit. Falls nein: Ignoriert es, ich wollte nur angeben. Was ihr allerdings mitnehmen solltet ist dies:

Zitat:
Aus den Basisvektoren lassen sich über Linearkombinationen jegliche Vektoren des Raumes generieren.


Was ist eine Linearkombination (keine Angst, ich bin durch mit der Angeberei, das ist tatsächlich wichtig..)? Wenn ihr zwei Vektoren V und W habt, ist ein Vektor P = a * V + b * W eine Linearkombination. Und wenn V und W Basisvektoren sind, dann kann man daraus jeden Punkt P im Raum berechnen. Im kartesischen Koordinatensystem sind diese beiden generell
Code: [AUSKLAPPEN]
V = [1 ; 0]
W = [0 ; 1]

(Wenn mans genau nehmen will sind die nicht wirklich eindeutig. Man könnte sie auch ein wenig verändern. Zum Beispiel [-1 ; 0] und [0 ; 1]. Eigentlich müssen sie nichteinmal senkrecht aufeinander stehen. Sie dürfen bloss nicht linear abhängig sein - aber was das bedeutet kann euch egal sein. Nehmt einfach die beiden oben erwähnten, damit fahrt ihr am besten.)

So, damit wir das Ziel nicht aus den Augen verlieren: Wir wollen eine Matrix, die einen beliebigen Vektor P um alpha (um den Ursprung) dreht. Wenn ihr euch jetzt den Vektor [1 ; 0] anschaut und im Einheitskreis nachschaut werdet ihr sehen was damit passiert:
Code: [AUSKLAPPEN]
[1 ; 0] -> [cos(a) ; sin(a)]

Das gleiche Spiel macht ihr mit dem zweiten Basisvektor [0 ; 1]. Und ihr werdet feststellen, dass sowas rauskommt:
Code: [AUSKLAPPEN]
[0 ; 1] -> [-sin(a) ; cos(a)


Was bringt uns das jetzt? Wenn wir unser Wissen aus der Matrixmultiplikation anwenden sehen wir, dass wir die beiden neuen Vektoren einfach in unsere Matrix reinschreiben können! So kommt unsere Rotationsmatrix heraus, und die sieht also wie folgt aus:
user posted image
(Src: http://upload.wikimedia.org/wi...bfb16a.png)

BlitzBasic: [AUSKLAPPEN]
Function newMatrixRot.Matrix2(a#)
Local m.Matrix2 = New Matrix2

Local c# = Cos(a)
Local s# = Sin(a)

m\e11 = c : m\e12 = -s
m\e21 = s : m\e22 = c

Return m
End Function


Wenn ihr das so in BlitzBasic verwenden wollt, solltet ihr ein wenig aufpassen. Die Y-Achse geht im 2D-Grafikmodus von oben nach unten, nicht von unten nach oben wie in einem "normalen" Koordinatensystem. Deshalb müsstet ihr ein wenig anpassen. (Was sich ändert ist eigentlich der Drehsinn oder Drehrichtung.) Beispielcode:

BlitzBasic: [AUSKLAPPEN]
Type Matrix2
Field e11#
Field e12#

Field e21#
Field e22#
End Type

Type Vector2
Field x#
Field y#
End Type

Function newVector.Vector2(x#, y#)
Local v.Vector2 = New Vector2

v\x = x
v\y = y

Return v
End Function

Function mvMult.Vector2(a.Matrix2, v.Vector2)
Local r.Vector2 = New Vector2

r\x = a\e11 * v\x + a\e12 * v\y
r\y = a\e21 * v\x + a\e22 * v\y

Return r
End Function

Function newMatrixRot.Matrix2(a#)
Local m.Matrix2 = New Matrix2

Local c# = Cos(a)
Local s# = Sin(a)

; NORMAL:
;m\e11 = c : m\e12 = -s
;m\e21 = s : m\e22 = c

; Graphics2D:
m\e11 = c : m\e12 = s
m\e21 = -s : m\e22 = c

Return m
End Function

Graphics 800, 600, 0, 2
SetBuffer BackBuffer()

Origin 400, 300

Local p.Vector2 = newVector(10, 0)
Local m.Matrix2 = newMatrixRot(1)

Local pNew.Vector2

While Not KeyHit(1)

Oval p\x - 3, p\y - 3, 6, 6

pNew = mvMult(m, p)
Delete p
p = pNew

Flip
Cls
Wend
End


Natürlich gibt es noch andere lustige Matrizen im 2D-Raum. Zum Beispiel die Skaliermatrix oder die Schermatrix. Wie man auf die kommt überlasse ich euch als Hausaufgabe (hihi!).

5.3 Spezielles für 2x2 Matrizen

Eigentlich ist mit der wirklich sichtbaren Nützlichkeit jetzt schluss. Ich bringe nur noch ein paar lustige Eigenschaften, für Leute, die sich ein wenig mehr für die lineare Algebra interessieren.

5.3.1 Determinante

Die Determinante ordnet der Matrix M ein Skalar (eine Zahl, ihr erinnert euch?) zu. Das hat verschiedene nützliche Eigenschaften, die ihr später sehen werdet. Generell ist das Ding ziemlich mühsam zu berechnen, und allgemeine Anleitungen findet ihr hier. Aber für 2x2 Matrizen ist es ganz einfach.

Zuerst kurz Darstellungstechnisch: [A , B ; C , D] gibt euch folgende Matrix:
user posted image
(Src: http://upload.wikimedia.org/wi...3c13a9.png)

Mit dem aus dem Weg:
Code: [AUSKLAPPEN]
det([A , B ; C , D]) = A * D - B * C


5.3.2 Inverse

Wenn ihr eine Gleichung A * x = b lösen wollt, dann macht ihr (eigentlich) nichts anderes, als links und rechts (von links!) mit der Inversen von A zu multiplizieren. Also A^-1 * A * x = A^-1 * b, denn A^-1 * A = I gibt die Einheitsmatrix [1 , 0 ; 0 , 1]. Diese Matrix verändert einen Vektor nicht. Also I * x = x.
Das Inverse einer Matrix zu finden gehört zu den mühsamsten und aufwändigsten Rechenvorgängen der numerischen Mathematik. Deshalb wird es meistens umgangen mit irgendwelchen Verfahren (GMRES und ähnliche). Aber auch hier ist es für 2x2 Matrizen ganz einfach:

user posted image
(Src: http://upload.wikimedia.org/wi...642bc3.png)

Dies bringt übrigens die lustige Eigenschaft mit sich, dass ein Lösungsssystem A * x = b nur dann eine Lösung hat, wenn det(A) != 0. (Sonst ist A nicht invertierbar -> keine Lösung.)

5.3.3 Eigenwerte

Eigenwerte sind etwas, das man vorallem in der Physik braucht. Aber wieso muss euch nicht weiter beschäftigen (es sei denn ihr interessiert euch wirklich für Quantenmechanik, dann kann ichs euch gerne erklären). Generell gilt die Eigenschaft:

user posted image
(Src: http://upload.wikimedia.org/wi...512567.png)

Wie man sie berechnet geht auch ziemlich einfach (der Einfachheit halber soll der Eigenwert Lambda jetzt mit k bezeichnet werden). Man sucht sich die Nullstellen des charakteristischen Polynoms heraus. Dies ist definiert durch die folgende Determinante:
det(A - k * I) = 0

Für 2x2 Matrizen gibt das eine quadratische Gleichung und liefert somit zwei Eigenwerte.

5.3.4 Eigenvektoren

Eigenvektoren sind eng mit Eigenwerten verwandt. Das x in der oberen Formel ist nämlich der Eigenvektor. Man findet ihn, indem man die Gleichung (A - k * I) * x = 0 für einen bestimmten Eigenwert löst (beachte: GleichungsSYSTEM, keine einzelne Gleichung). Dadurch erhält man Eigenvektor x zu Eigenwert k.

Genauer beschrieben ist das alles auf Wikipedia. Diese Art von Problemen sind sehr wichtig für bestimmte Sorten numerischer Probleme. Es gibt mittlerweilen recht effiziente Verfahren die EV von Matrizen zu bestimmen, aber die meisten sind (soweit ich informiert bin) irgendwelche Näherungen, die nur auf bestimmte Klassen von Matrizen zutreffen (korrigiert mich bitte falls ich falsch liege).

Done

So. Ich glaube ich habe das Thema ausreichend bearbeitet. Sollten zusätzliche Informationen oder Erklärungen erwünscht sein findet sich sicher jemand, der dies anfügt. Für Ergänzungen bin ich natürlich immer offen.

MfG,
Darth
Diese Signatur ist leer.

Neue Antwort erstellen


Übersicht BlitzBasic FAQ und Tutorials

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group