GJK - Kollisionserkennung für konvexe Körper

Übersicht

BlitzMax, BlitzMax NG

FAQs und Tutorials

	ComNik Betreff: GJK - Kollisionserkennung für konvexe Körper	Di, Dez 22, 2009 15:16 Antworten mit Zitat
DIESES TUTORIAL ENTHÄLT NOCH KLEINE FEHLER! ICH ARBEITE AN EINER VERBESSERTEN VERSION! Danke... Moin, Eventuell errinnern sich noch ein paar an den Thread den ich letztens mal ins Forum geworfen hatte (Klick). Da ging es um Kollissionserkennung. Und unser allseits geschätzer Noobody erwähnte einen Algorithmus von dem ich noch nie auch nur im entferntesten gehört hatte. Der Gilbert - Johnson - Keerthi (GJK) Algorithmus. Der ist äußerst einfallsreich nach seinen Erfindern benannt. Je mehr ich mich aber mit dem Algorithmus beschäftigt habe, hab ich gemerkt das diese 3 es sowas von verdient haben, das der Algorithmus nach ihnen benannt ist. Nun dachte ich mir ich schreib was darüber, da die Fülle an Tutorials/Artikeln über den GJK nicht gerade... nun ja vorhanden ist. Part 1: Was ist der GJK und warum zur Hölle sollte ich den Benutzen? Letzteres ist eigentlich relativ einfach zu beantworten, indem ich die Vorteile des GJK aufzähle. Aber: Er ist jetzt nicht die ultimative Kollissionserkennung die jeder nutzen muss (eventuell können da Leute mit mehr Erfahrung was zu sagen). Ich persönlich finde ihn genial und werde ihn auch nutzen. Vorteile - Extrem geringer Implementierungsaufwand (vor allem wenn man besser in Mathe ist als ich...) - Schlichtes, logisches Konzept - Effizient (Keine Divisionen, nur ein paar Dotproducts) Nachteile habe ich noch keine gefunden das wird sich bei der Benutzung herausstellen. Sollte Jemand nichts mit "Dotproducts" anfangen können ist das nicht so schlimm ich werde versuchen das zu erklären. Wenn man aber täglich mit Vektoren hantiert (nicht so wie ich...), hat man diesen Algorithmus in wenigen Stunden in sein Spiel gebracht. Wie (fast) jeder andere Kollissionserkennungs - Algorithmus funktioniert der GJK nur mit kovexen Körpern. Sollte jemand auch konkave nutzen wollen, so möge er sich entweder einen anderen Algorithmus suchen oder diese Threads bemühen: Nummer 1 und [url=https://www.blitzforum.de/forum/viewtopic.php?t=32279]Nummer 2. Und was macht der denn jetzt überhaupt? Der GJK ist ein Algorithmus der "erkennt" ob zwei konvexe Körper sich überlappen. Ja das wars schon... Mehr dazu in Part 2. Part 2 Wie funktioniert er denn? Der GJK basiert auf einer Entdeckung/Feststellung des genialen Hermann Minkowski. Von ihm stammt nämlich die sogenannte "Minkowski Summe". Die beschreibt nämlich mathematische Operationen (in diesem Fall das addieren) nicht etwa mit Zahlen sondern mit Körpern. Zur besseren Verständigung und zur Unterbrechung des Leseflusses hier mal ein Bild (nicht im Blitz Koordinatensystem): Dieses Bild zeigt (in schlechter Qualität..) das man zwei Körper zu einem dritten addieren kann. Man nehme dazu jeden einzelnen Punkt in Körper 1 und addiere dazu jeden Punkt in Körper 2. Einfach oder? Was hat das mit dem ALgorithmus zu tun? Einiges. Ersteinmal nimmt der GJK nicht die Minkoski Summe sondern die Minkowski Differenz. Also: Alle Punkte in Körper 1 - alle Punkte in Körper 2. Sehr simpel. Aber das hat immer noch nichts mit Kollissionen zu tun! Doch hat es, wie uns ein Gedankenexperiment gleich zeigen wird: Bei einer Kollission muss mindestens ein Punkt von Körper 1 auf der gleichen Stelle wie ein Punkt von Körper 2 sein. Also: Körper1.Punkte[i].x = Körper2.Punkte[i].x And Körper1.Punkte[i].y = Körper2.Punkte[i].y Und jetzt kommts: Wenn zwei Körper einen oder mehr Punkte gemeinsam haben so enthält ihre Minkowski Differenz den Ursprung also (0,0). ... Keine Sorge wir müssen nicht jeden Punkt in beiden Körpern subtrahieren und gucken ob es null ergibt. Wir nehmen einfach nur die Hülle: Wobei die lustigen kleinen Ovale die 4 (oder eben mehr..) Eckpunkte eines Körpers sind. Das sind doch schonmal wesentlich weniger als davor. Und das gute ist wir müssen wieder nicht alle benutzen. Daraus ergibt sich unser Leitsatz und Lösungskonzept: Wenn wir es schaffen, drei Punkte (also ein Dreieck) der Minkowski Differenz (beziehungsweise ihrer Hülle) zu finden, die den Mittelpunkt einschliessen, so wissen wir das die beiden Körper kollidieren! Doch bevor wir an die Umsetzung gehen erstellen wir einen Ablauf der Funktionsweise des Algorithmus: Punktliste leeren \| Beliebige Suchrichtung auswählen \| Support Funktion mit dieser Richtung aufrufen --> erhaltenen Punkt zur Punktliste hinzufügen \| Suchrichtung = negative alte Suchrichtung Solange PunkteInPunktListe <= 3 Supportfunktion mit Suchrichtung aufrufen --> Punkt zur Punktliste hinzufügen Simplex Funktion aufrufen Loop Der erste Gedanke ist eventuell "HÄ?!" aber ich werde jeden einzelnen Schritt erklären. Schritt 1: Punktliste leeren sollte selbsterklärend sein (ClearList()...) Schritt 2: Man nehme einen Vektor "R" mit beliebigem Inhalt z.B R(1,1) (R.x = 1, R.y = 1) Schritt 3: Jetzt wird es etwas komplizierter. Man braucht eine sogennante Supportfunktion die einen Punkt zurückliefert. Aber nicht irgendeinen, sondern den Punkt (der Minkowski Differenz), der am weitesten in eine bestimmte Richtung entfernt liegt: Die Support Funktion: Ersteinmal, so sollte es am Ende aussehen: Support(Körper,Körper,Richtung) Die Funktion Support nimmt also zwei Körper entgegen und eine Richtung, und liefert dafür einen Punkt zurück. Eigentlich macht die Funktion aber nur das: Code: [AUSKLAPPEN] [EINKLAPPEN] punkt1 = Körper1.Support(Richtung) punkt2 = Körper2.Support(-Richtung) Return Vector(punkt1.x - punkt2.x, punkt1.y - punkt2.y) Das heisst sie sucht den Punkt auf Körper1 der am weitesten in die Richtung liegt und dann den punkt der am weitesten in die entgegengesetzte Richtung auf Körper 2 liegt. Diese Subtrahiert sie und liefert das Ergebnis (als Vektor natürlich) zurück. Warum klappt das? Nunja man sucht den weitesten Punkt in der Richtung auf Körper 1. Dann aber zieht man ihn sozusagen rückwärts. Somit erhält man einen Punkt in der Minkowski Differenz (da man ja einen Punkt von Körper1 - einen Punkt von Körper2 gemacht hat) der am weitesten in der Suchrichtung liegt. Das erstmal verdauen. Wer das nicht gleich versteht kann es sich aufmalen. Bleibt nur noch das Mysterium um "Körper1.Support() und Körper2.Support()" was machen die? Die nehmen eine Richtung entgegen (Körper1 die Suchrichtung und Körper2 halt die negative). Anschliessend bilden sie für jeden ihrer Punkte das Dotproduct (Skalarprodukt) mit der Richtung. Der dessen Ergebnis das höchste ist wird zurückgegeben. Mehr zum Skalarprodukt weiter unten. Ich schreibe einfach mal die Support Methode hier rein die ich benutzt habe, vielleicht hilft sie beim Verständnis. BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Method Support:TVector2D(dir:TVector2D) Local _max:Int, i:Int Local maxDp:Float = dir.ScalarProduct(Self.shape[0]), dp:Float For i = 0 To Self.vertices dp = dir.ScalarProduct(Self.shape[i]) If dp > maxDp _max = i maxDp = dp End If Next Return Self.shape[_max] End Method Das "TVector2D" ist der Vektor Type aus einem meiner Module, ihr könnt da einfach was beliebiges eigenes nehmen. Es ist nichts weiter als eine X und eine Y Koordinate vereint in einem Objekt... Das muss man verstanden haben, diese Support Funktion ist wichtig. Wenn sie (wie zuerst auch bei mir...) die falschen Punkte liefert, so klappt gar nichts mehr. Zurück zum Ablauf des GJK, mit Schritt 3: Eigentlich simpel die neue Richtung ist also -alteSuchrichtung. Somit zeigt die neue Richtung immer in Richtung Ursprung! Auch hier der Tipp: Aufzeichnen bei Unverständnis, hat mir sehr geholfen. Schritt 4: Das ist das Herzstück wir versuchen den sogenannten Simplex zum Dreieck zu formen und dann zu gucken ob der Ursprung drinn steckt. Dazu müssen wir erstmal klären was denn ein Simplex ist. Siehe dazu folgendes Schaubild: Ein Simplex der Stufe 1 ist ein einfacher Punkt. Mit diesem SImplex werden wir es nie zu tun haben da wir vor dem Funktionsaufruf ja schon 2 Punkte in der Punkt Liste haben. Das heisst unsere Punktliste ist schon ein Simplex der Stufe 2 also eine Linie, wenn wir die Funktion aufrufen. Unser Ziel ist es nun einen Simplex der Stufe 3, also ein Dreieck, zu konstruieren. Man kann nämlich für jeden Körper 3 Punkte wählen die einen anderen (in ihm) einschliessen. Das heisst mehr als einen Simplex der Stufe 3 brauchen wir auch nicht. Das heisst wir haben pro GJK Aufruf nur 2 Schleifendurchgänge Ok die bisherigen Schritte haben uns schonmal zu einer Linie geführt. Wie kommen wir nun zu einem Dreieck? Wir müssen auf jedenfall die Suchrichtung verändern damit wir einen neuen Punkt bekommen. Die Frage ist: Nach welchen Kriterien, und wie, verändern wir die Suchrichtung? Die Lösung ist: Code: [AUSKLAPPEN] [EINKLAPPEN] Punkt A = zuletzt hinzugefügter Punkt Punkt B = zuerst hinzugefügter Punkt If Ursprung rechts von AB Suchrichtung = AB um 90 Grad gegen Uhrzeigersinn Else Suchrichtung = AB um 90 Grad im Uhrzeigersinn End If An dieser Stelle müssen wir einen Exkurs in Richtung Vektoren nehmen. Aber wir behandeln nur zwei Sachen: 1. Wie drehe ich einen Vektor einfach um 90 Grad (im Uhrzeigersinn oder gegen) 2. Wie finde ich heraus ob ein Punkt über einer Linie liegt oder nicht? Frage 1 ist sehr einfach zu beantworten: Man dreht einen Vektor um 90 Grad gegen den Uhrzeigersinn indem man aus (x,y) (y,-x) macht. [b] Man dreht einen Vektor um 90 Grad im Uhrzeigersinn indem man aus (x,y) (-y,x) macht. Aufzeichnen - Verstehen! Frage 2 wird durch unser allseits hochgeschätztes Skalarprodukt/Dotproduct gelöst! Das lässt sich am besten mit einem Bild veranschaulichen: Wenn man nun v1.ScalarProduct(v2) macht kann man folgedes erfahren. Ergebnis > 0 = v2 ist rechts von der roten Linie Ergebnis < 0 = v2 ist links der roten Linie Wir kehren zurück zu unserer If Abfrage. Wenn eure Support Funktion jetzt richtig Arbeitet dürftet ihr euren dritten Punkt erhalten Mit ein paar Dotproducts könnt ihr nun herausfinden ob der Ursprung innerhalb des Dreiecks liegt. Hier ist der Code meiner DoSimplex() Funktion: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Function DoSimplex:Byte(simplex:Int) Local last:TVector2D,_mid:TVector2D,first:TVector2D Local lastToOrigin:TVector2D,lastToMid:TVector2D,lastToFirst:TVector2D If simplex = 2 'Line Simplex last = TVector2D(Points.last()) first = TVector2D(Points.first()) lastToOrigin = CreateVector(-last.x,-last.y) lastToFirst = CreateVector(first.x-last.x,first.y-last.y) If InArea(CreateVector(lastToFirst.y,-lastToFirst.x),lastToOrigin) = 1 dir = CreateVector(lastToFirst.y,-lastToFirst.x) 'CC Perpendicular of lastToFirst Else dir = CreateVector(-lastToFirst.y,lastToFirst.x) 'last to Origin = -last End If Return False ElseIf simplex = 3 'Triangular Simplex <-- All we need to enclose the Origin last = TVector2D(Points.last()) _mid = TVector2D(Points.ValueAtIndex(1)) lastToOrigin = CreateVector(-last.x,-last.y) lastToMid = CreateVector(_mid.x-last.x,_mid.y-last.y) If InArea(lastToMid,lastToOrigin) = 1 Return True End If Return False End If End Function Function InArea:Int(v1:TVector2D,v2:TVector2D) Return Sgn(v1.ScalarProduct(v2)) End Function Wenn Alles soweit verstanden wurde dürfte das selbsterklärend sein. Meine Implementation ist noch nicht optimiert, das mach ich in den nächsten Tagen. Heute versuche ich noch das ganze in eine kleine Demo zu verpacken, mit Binary Trees und einer Physik Engine zu koppeln. Danke fürs lesen, dieses (leider etwas verwirrenden ) Tutorials lg ComNik Fragen und Kritik einfach hier posten.
WIP: Vorx.Engine

ComNik

Betreff: GJK - Kollisionserkennung für konvexe Körper

Di, Dez 22, 2009 15:16
Antworten mit Zitat

DIESES TUTORIAL ENTHÄLT NOCH KLEINE FEHLER! ICH ARBEITE AN EINER VERBESSERTEN VERSION! Danke...

Moin,

Eventuell errinnern sich noch ein paar an den Thread den ich letztens mal ins Forum geworfen hatte
(*Klick*). Da ging es um Kollissionserkennung. Und unser allseits geschätzer Noobody erwähnte einen Algorithmus von dem ich noch nie auch nur im entferntesten gehört hatte.

Der Gilbert - Johnson - Keerthi (GJK) Algorithmus. Der ist äußerst einfallsreich nach seinen Erfindern benannt. Je mehr ich mich aber mit dem Algorithmus beschäftigt habe, hab ich gemerkt das diese 3 es sowas von verdient haben, das der Algorithmus nach ihnen benannt ist.

Nun dachte ich mir ich schreib was darüber, da die Fülle an Tutorials/Artikeln über den GJK nicht gerade... nun ja vorhanden ist.

Part 1: Was ist der GJK und warum zur Hölle sollte ich den Benutzen?

Letzteres ist eigentlich relativ einfach zu beantworten, indem ich die Vorteile des GJK aufzähle.
Aber: Er ist jetzt nicht die ultimative Kollissionserkennung die jeder nutzen muss (eventuell können da Leute mit mehr Erfahrung was zu sagen). Ich persönlich finde ihn genial und werde ihn auch nutzen.

Vorteile
- Extrem geringer Implementierungsaufwand (vor allem wenn man besser in Mathe ist als ich...)
- Schlichtes, logisches Konzept
- Effizient (Keine Divisionen, nur ein paar Dotproducts)

Nachteile habe ich noch keine gefunden das wird sich bei der Benutzung herausstellen.
Sollte Jemand nichts mit "Dotproducts" anfangen können ist das nicht so schlimm ich werde versuchen das zu erklären. Wenn man aber täglich mit Vektoren hantiert (nicht so wie ich...), hat man diesen Algorithmus in wenigen Stunden in sein Spiel gebracht.

Wie (fast) jeder andere Kollissionserkennungs - Algorithmus funktioniert der GJK nur mit kovexen Körpern. Sollte jemand auch konkave nutzen wollen, so möge er sich entweder einen anderen Algorithmus suchen oder diese Threads bemühen: *Nummer 1* und [url=https://www.blitzforum.de/forum/viewtopic.php?t=32279]*Nummer 2*.

Und was macht der denn jetzt überhaupt?
Der GJK ist ein Algorithmus der "erkennt" ob zwei konvexe Körper sich überlappen.

Ja das wars schon...
Mehr dazu in Part 2.

Part 2 Wie funktioniert er denn?

Der GJK basiert auf einer Entdeckung/Feststellung des genialen Hermann Minkowski. Von ihm stammt nämlich die sogenannte
"Minkowski Summe". Die beschreibt nämlich mathematische Operationen (in diesem Fall das addieren) nicht etwa mit Zahlen sondern mit Körpern. Zur besseren Verständigung und zur Unterbrechung des Leseflusses hier mal ein Bild (nicht im Blitz Koordinatensystem):

user posted image

Dieses Bild zeigt (in schlechter Qualität..) das man zwei Körper zu einem dritten addieren kann.
Man nehme dazu jeden einzelnen Punkt in Körper 1 und addiere dazu jeden Punkt in Körper 2.

Einfach oder? Was hat das mit dem ALgorithmus zu tun?
Einiges. Ersteinmal nimmt der GJK nicht die Minkoski Summe sondern die Minkowski Differenz.
Also: Alle Punkte in Körper 1 - alle Punkte in Körper 2.

Sehr simpel.

Aber das hat immer noch nichts mit Kollissionen zu tun! Doch hat es, wie uns ein Gedankenexperiment gleich zeigen wird:

Bei einer Kollission muss mindestens ein Punkt von Körper 1 auf der gleichen Stelle wie ein Punkt von Körper 2 sein.

Also: Körper1.Punkte[i].x = Körper2.Punkte[i].x And Körper1.Punkte[i].y = Körper2.Punkte[i].y

Und jetzt kommts: Wenn zwei Körper einen oder mehr Punkte gemeinsam haben so enthält ihre Minkowski Differenz den Ursprung also (0,0). ... Shocked

Keine Sorge wir müssen nicht jeden Punkt in beiden Körpern subtrahieren und gucken ob es null ergibt.
Wir nehmen einfach nur die Hülle:
user posted image

Wobei die lustigen kleinen Ovale die 4 (oder eben mehr..) Eckpunkte eines Körpers sind. Das sind doch schonmal wesentlich weniger als davor. Und das gute ist wir müssen wieder nicht alle benutzen.

Daraus ergibt sich unser Leitsatz und Lösungskonzept:
Wenn wir es schaffen, drei Punkte (also ein Dreieck) der Minkowski Differenz (beziehungsweise ihrer Hülle) zu finden, die den Mittelpunkt einschliessen, so wissen wir das die beiden Körper kollidieren!

Doch bevor wir an die Umsetzung gehen erstellen wir einen Ablauf der Funktionsweise des Algorithmus:

Der erste Gedanke ist eventuell "HÄ?!" aber ich werde jeden einzelnen Schritt erklären.

Schritt 1: Punktliste leeren sollte selbsterklärend sein (ClearList()...)

Schritt 2: Man nehme einen Vektor "R" mit beliebigem Inhalt z.B R(1,1) (R.x = 1, R.y = 1)

Schritt 3: Jetzt wird es etwas komplizierter. Man braucht eine sogennante Supportfunktion die einen Punkt zurückliefert. Aber nicht irgendeinen, sondern den Punkt (der Minkowski Differenz), der am weitesten in eine bestimmte Richtung entfernt liegt:

Die Support Funktion:

Ersteinmal, so sollte es am Ende aussehen: Support(Körper,Körper,Richtung)

Die Funktion Support nimmt also zwei Körper entgegen und eine Richtung, und liefert dafür einen Punkt zurück.
Eigentlich macht die Funktion aber nur das:
Code: [AUSKLAPPEN]

punkt1 = Körper1.Support(Richtung)
punkt2 = Körper2.Support(-Richtung)

Return Vector(punkt1.x - punkt2.x, punkt1.y - punkt2.y)

Das heisst sie sucht den Punkt auf Körper1 der am weitesten in die Richtung liegt und dann den punkt der am weitesten in die entgegengesetzte Richtung auf Körper 2 liegt. Diese Subtrahiert sie und liefert das Ergebnis (als Vektor natürlich) zurück.

Warum klappt das? Nunja man sucht den weitesten Punkt in der Richtung auf Körper 1. Dann aber zieht man ihn sozusagen rückwärts. Somit erhält man einen Punkt in der Minkowski Differenz (da man ja einen Punkt von Körper1 - einen Punkt von Körper2 gemacht hat) der am weitesten in der Suchrichtung liegt.

Das erstmal verdauen. Wer das nicht gleich versteht kann es sich aufmalen.

Bleibt nur noch das Mysterium um "Körper1.Support() und Körper2.Support()" was machen die?
Die nehmen eine Richtung entgegen (Körper1 die Suchrichtung und Körper2 halt die negative).
Anschliessend bilden sie für jeden ihrer Punkte das Dotproduct (Skalarprodukt) mit der Richtung. Der dessen Ergebnis das höchste ist wird zurückgegeben. Mehr zum Skalarprodukt weiter unten.

Ich schreibe einfach mal die Support Methode hier rein die ich benutzt habe, vielleicht hilft sie beim Verständnis.
BlitzMax: [AUSKLAPPEN]


Method Support:TVector2D(dir:TVector2D)
	Local _max:Int, i:Int 
	Local maxDp:Float = dir.ScalarProduct(Self.shape[0]), dp:Float 
		
	For i = 0 To Self.vertices
		dp = dir.ScalarProduct(Self.shape[i]) 	
		If dp > maxDp
			_max  = i
			maxDp = dp
		End If    
	Next
				
	Return Self.shape[_max] 
End Method

Das "TVector2D" ist der Vektor Type aus einem meiner Module, ihr könnt da einfach was beliebiges eigenes nehmen. Es ist nichts weiter als eine X und eine Y Koordinate vereint in einem Objekt...

Das muss man verstanden haben, diese Support Funktion ist wichtig. Wenn sie (wie zuerst auch bei mir...) die falschen Punkte liefert, so klappt gar nichts mehr.

Zurück zum Ablauf des GJK,
mit Schritt 3: Eigentlich simpel die neue Richtung ist also -alteSuchrichtung.
Somit zeigt die neue Richtung immer in Richtung Ursprung!

Auch hier der Tipp: Aufzeichnen bei Unverständnis, hat mir sehr geholfen.

Schritt 4:

Das ist das Herzstück wir versuchen den sogenannten Simplex zum Dreieck zu formen und dann zu gucken ob der Ursprung drinn steckt.

Dazu müssen wir erstmal klären was denn ein Simplex ist.
Siehe dazu folgendes Schaubild:

user posted image

Ein Simplex der Stufe 1 ist ein einfacher Punkt. Mit diesem SImplex werden wir es nie zu tun haben da wir vor dem Funktionsaufruf ja schon 2 Punkte in der Punkt Liste haben. Das heisst unsere Punktliste ist schon ein Simplex der Stufe 2 also eine Linie, wenn wir die Funktion aufrufen. Unser Ziel ist es nun einen Simplex der Stufe 3, also ein Dreieck, zu konstruieren. Man kann nämlich für jeden Körper 3 Punkte wählen die einen anderen (in ihm) einschliessen. Das heisst mehr als einen Simplex der Stufe 3 brauchen wir auch nicht. Das heisst wir haben pro GJK Aufruf nur 2 Schleifendurchgänge Smile

Ok die bisherigen Schritte haben uns schonmal zu einer Linie geführt. Wie kommen wir nun zu einem Dreieck? Wir müssen auf jedenfall die Suchrichtung verändern damit wir einen neuen Punkt bekommen.
Die Frage ist: Nach welchen Kriterien, und wie, verändern wir die Suchrichtung?

Die Lösung ist:
Code: [AUSKLAPPEN]

Punkt A = zuletzt hinzugefügter Punkt
Punkt B = zuerst hinzugefügter Punkt

If Ursprung rechts von AB
Suchrichtung = AB um 90 Grad gegen Uhrzeigersinn
Else
Suchrichtung = AB um 90 Grad im Uhrzeigersinn
End If

An dieser Stelle müssen wir einen Exkurs in Richtung Vektoren nehmen. Aber wir behandeln nur zwei Sachen:
1. Wie drehe ich einen Vektor einfach um 90 Grad (im Uhrzeigersinn oder gegen)
2. Wie finde ich heraus ob ein Punkt über einer Linie liegt oder nicht?

Frage 1 ist sehr einfach zu beantworten:
Man dreht einen Vektor um 90 Grad gegen den Uhrzeigersinn indem man aus (x,y) (y,-x) macht.
[b] Man dreht einen Vektor um 90 Grad im Uhrzeigersinn indem man aus (x,y) (-y,x) macht.

Aufzeichnen - Verstehen!

Frage 2 wird durch unser allseits hochgeschätztes Skalarprodukt/Dotproduct gelöst!
Das lässt sich am besten mit einem Bild veranschaulichen:

user posted image

Wenn man nun v1.ScalarProduct(v2) macht kann man folgedes erfahren.

Ergebnis > 0 = v2 ist rechts von der roten Linie
Ergebnis < 0 = v2 ist links der roten Linie

Wir kehren zurück zu unserer If Abfrage.

Wenn eure Support Funktion jetzt richtig Arbeitet dürftet ihr euren dritten Punkt erhalten Smile

Mit ein paar Dotproducts könnt ihr nun herausfinden ob der Ursprung innerhalb des Dreiecks liegt.

Hier ist der Code meiner DoSimplex() Funktion:
BlitzMax: [AUSKLAPPEN]


Function DoSimplex:Byte(simplex:Int) 
Local last:TVector2D,_mid:TVector2D,first:TVector2D
Local lastToOrigin:TVector2D,lastToMid:TVector2D,lastToFirst:TVector2D 
	
If simplex = 2 'Line Simplex
	last  = TVector2D(Points.last())
	first = TVector2D(Points.first())
	lastToOrigin = CreateVector(-last.x,-last.y)
	lastToFirst  = CreateVector(first.x-last.x,first.y-last.y) 
		
	If InArea(CreateVector(lastToFirst.y,-lastToFirst.x),lastToOrigin) = 1 
		dir = CreateVector(lastToFirst.y,-lastToFirst.x) 'CC Perpendicular of lastToFirst
	Else
		dir = CreateVector(-lastToFirst.y,lastToFirst.x) 'last to Origin = -last
	End If 
				
	Return False   
ElseIf simplex = 3 'Triangular Simplex <-- All we need to enclose the Origin  
	last  = TVector2D(Points.last())
	_mid  = TVector2D(Points.ValueAtIndex(1))
	lastToOrigin = CreateVector(-last.x,-last.y)
	lastToMid    = CreateVector(_mid.x-last.x,_mid.y-last.y) 
			
	If InArea(lastToMid,lastToOrigin) = 1 
		Return True
	End If 

	Return False 
End If 
End Function 

Function InArea:Int(v1:TVector2D,v2:TVector2D) 
	Return Sgn(v1.ScalarProduct(v2))
End Function

Wenn Alles soweit verstanden wurde dürfte das selbsterklärend sein.
Meine Implementation ist noch nicht optimiert, das mach ich in den nächsten Tagen.
Heute versuche ich noch das ganze in eine kleine Demo zu verpacken, mit Binary Trees und einer Physik Engine zu koppeln.

Danke fürs lesen, dieses (leider etwas verwirrenden Confused

) Tutorials
lg
ComNik

Fragen und Kritik einfach hier posten.

WIP: Vorx.Engine

Zuletzt bearbeitet von ComNik am Sa, Jan 23, 2010 1:28, insgesamt 2-mal bearbeitet

	Skabus	Di, Dez 22, 2009 19:45 Antworten mit Zitat
Vielen Dank ComNik für dieses Tutorial^^ Allerdings versteh ich eine Sache nicht...was genau verstehst du unter "konvexe Körper"... Mag jetzt etwas dumm klingen, aber was genau nu damit gemeint ist, versteh ich nicht... Das einzige was ich aus dem Studium kenne, sind konvexe Mengen, aber in wie fern hat das mit diesem Thema zu tun? Wäre nett wenn du da etwas Licht ins Dunkle bringen könntest.... MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu

Skabus

Di, Dez 22, 2009 19:45
Antworten mit Zitat

Vielen Dank ComNik für dieses Tutorial^^

Allerdings versteh ich eine Sache nicht...was genau verstehst du unter "konvexe Körper"...
Mag jetzt etwas dumm klingen, aber was genau nu damit gemeint ist, versteh ich nicht...

Das einzige was ich aus dem Studium kenne, sind konvexe Mengen, aber in wie fern
hat das mit diesem Thema zu tun?

Wäre nett wenn du da etwas Licht ins Dunkle bringen könntest....

MfG Ska

"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

	Alfadur	Di, Dez 22, 2009 20:36 Antworten mit Zitat
Konvex = nach außen gewölbt, die direkte Verbindung zwischen zwei Punkten des Körpers gehört zum Körper selbst ...

Alfadur

Di, Dez 22, 2009 20:36
Antworten mit Zitat

Konvex = nach außen gewölbt, die direkte Verbindung zwischen zwei Punkten des Körpers gehört zum Körper selbst ...

user posted image

Zuletzt bearbeitet von Alfadur am Di, Dez 22, 2009 20:43, insgesamt 2-mal bearbeitet

	Goodjee	Di, Dez 22, 2009 20:40 Antworten mit Zitat
http://www-lehre.informatik.un...ode33.html <- da ist eine zeichnung zu konvex und konkav
"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House http://deeebian.redio.de/ http://goodjee.redio.de/

Goodjee

Di, Dez 22, 2009 20:40
Antworten mit Zitat

http://www-lehre.informatik.un...ode33.html <- da ist eine zeichnung zu konvex und konkav

"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House
http://deeebian.redio.de/ http://goodjee.redio.de/

	ComNik	Di, Dez 22, 2009 22:00 Antworten mit Zitat
Oh sorry zu spät gesehen, aber wurde ja schon perfekt erklärt. Aber wie schon erwähnt, es ist nicht besonders schwer einen konkaven Körper in konvexe Dreiecke zu unterteilen. Man sollte aber versuchen im "Unterteilungs" Algorithmus, die Punkte zu bestimmen die auch wirklich aussen liegen, damit sich der GJK keine unnötige Arbeit macht. Der Algorithmus ist außerdem sehr performant, aber man kann wenn man will die anfängliche Suchrichtung intelligenter setzten. Das hab ich noch nicht ausprobiert, aber da kann mann sich was überlegen. Wenn ich was rausfinde poste ich es hier. lg ComNik
WIP: Vorx.Engine

ComNik

Di, Dez 22, 2009 22:00
Antworten mit Zitat

Oh sorry zu spät gesehen, aber wurde ja schon perfekt erklärt.

Aber wie schon erwähnt, es ist nicht besonders schwer einen konkaven Körper in konvexe Dreiecke zu unterteilen. Man sollte aber versuchen im "Unterteilungs" Algorithmus, die Punkte zu bestimmen die auch wirklich aussen liegen, damit sich der GJK keine unnötige Arbeit macht.

Der Algorithmus ist außerdem sehr performant, aber man kann wenn man will die anfängliche Suchrichtung intelligenter setzten. Das hab ich noch nicht ausprobiert, aber da kann mann sich was überlegen.
Wenn ich was rausfinde poste ich es hier.

lg
ComNik

WIP: Vorx.Engine

Übersicht

BlitzMax, BlitzMax NG

FAQs und Tutorials

Nach Oben

BlitzBasic Portal

GJK - Kollisionserkennung für konvexe Körper

ComNik

Betreff: GJK - Kollisionserkennung für konvexe Körper

Skabus

Alfadur

Goodjee

ComNik