Tutorial Kollision2 - Versionsgeschichte

Erin: /* Kollision mit den Ecken und Kanten */

2009-04-30T10:29:52Z

‎Kollision mit den Ecken und Kanten

Erin: /* Kollision mit den Ecken und Kanten */

2009-04-30T09:04:18Z

‎Kollision mit den Ecken und Kanten

DGLBot: Der Ausdruck ''(.*?)'' wurde ersetzt mit ''$1''.

2009-03-10T18:47:35Z

Der Ausdruck ''<cpp>(.*?)</cpp>'' wurde ersetzt mit ''<source lang="cpp">$1</source>''.

Flash: /* Links - Literatur */

2008-06-18T08:57:53Z

‎Links - Literatur

Flash: /* Warum eine Kugel? */

2008-04-09T12:01:27Z

‎Warum eine Kugel?

Erin: /* Links - Literatur */

2008-04-09T11:28:09Z

‎Links - Literatur

Erin: /* Vorselektion und Berechnung des Schnittbereiches */

2008-04-09T11:26:35Z

‎Vorselektion und Berechnung des Schnittbereiches

Erin: /* Links - Literatur */

2008-04-09T11:22:14Z

‎Links - Literatur

Erin: /* Links - Literatur */

2008-04-09T11:19:10Z

‎Links - Literatur

Erin: /* Links - Literatur */

2008-04-09T11:17:23Z

‎Links - Literatur

@@ Zeile 219: / Zeile 219: @@
 Interessant ist, dass a wegen des Quadrates von V nur positiv sein kann. Wenn wir die kleinere der beiden Lösungen (nächster Kollisionspunkt) suchen, brauchen wir die Wurzel nur zu subtrahieren. Im Falle der Kantenkollision es es anders, da kann der Ausdruck im Nenner negativ sein.
-Nun zur Kollision mit der '''Kante'''. Wir berechnen sie auf ähnliche Weise, nur dass hier zwei Schritte erforderlich sind. Im ersten Schritt stellen wir fest, in welchem Punkt die Kugel die (unendliche) Gerade berührt, wenn überhaupt, und im zweiten Schritt prüfen wir, ob die Berührung auf dem Streckenabschnitt der Kante stattfindet.
+Nun zur Kollision mit der '''Kante''', bei der wir im Prinzip ähnlich verfahren.
 [[Bild:Tutorial_Kollision2_14.png|center|framed]]

@@ Zeile 223: / Zeile 223: @@
 [[Bild:Tutorial_Kollision2_14.png|center|framed]]
-Nun haben wir aber keinen festen Punkt mehr, auf den wir uns beziehen können. Stattdessen setzen wir den kürzesten Abstand zur Linie (die Höhe) ein und fordern, das dieser Abstand so groß sein muss wie der Radius, beides wiederum auf quadratischer Ebene.
+Jetzt haben wir aber keinen festen Punkt mehr, auf den wir uns beziehen können; deshalb müssen wir in zwei Schritten vorgehen. Zuerst prüfen wir, ob und wo die Kugel die Gerade durch die beiden Eckpunkte schneidet, dann in einem zweiten Schritt, ob der Intersektionspunkt auf dem geforderten Streckenabschnitt liegt. Das Verfahren ist wesentlich komplexer als bei der Eckenkollision; deshalb beschränke ich mich darauf, die Koeffizienten in der Normalform anzugeben. Dabei gilt: E = S - R und B = R - A.
 [[Bild:Tutorial_Kollision2_29.png|center|framed]]
-Nun brauchen wir nur noch festzustellen, ob der Punkt auf dem geforderten Streckenabschnitt, der Kante, liegt. Wie das gemacht wird, ist aus der Funktion ''EdgeIntersect'' ([[Werkzeugkiste]]) herauszulesen. Hier geht es nun mit der Funktion ''PolygonIntersect'' wie folgt weiter:
+Nun bleibt noch festzustellen, ob der Punkt auf dem geforderten Streckenabschnitt, der Kante, liegt. Wie das gemacht wird, ist aus der Funktion ''EdgeIntersect'' ([[Werkzeugkiste]]) herauszulesen. Hier geht es nun mit der Funktion ''PolygonIntersect'' wie folgt weiter:
 <source lang="cpp">

@@ Zeile 93: / Zeile 93: @@
 Beginnen wir nun, die Funktion für ein einzelnes Polygon aufzubauen. Dazu benötigen wir einige Variablen, die wir am besten in eine Struktur, Klasse oder sonstwas packen und den Funktionen mit auf den Weg geben. Die können sich bedienen und ihrerseits Eintragungen vornehmen.
-<cpp>
+<source lang="cpp">
 typedef struct {
 	TVector vel;        // Bewegungsvektor
@@ Zeile 103: / Zeile 103: @@
 	double  distance;   // Distanz bis zum Kollisionspunkt
 } TCollision;
-</cpp>
+</source>
 Nun der erste Teil der Funktion zur Kollisionserkennung an einem einzelnen Polygon. Ich verwende hier einen gemäßigten Pseudo-Code, d.h. ich schreibe lediglich die Vektoroperationen in verkürzter Form, um den Code etwas übersichtlicher zu machen. Aus dem Kontext dürfte hervorgehen, dass z.B. mit (vector1 * vector2) nur das Skalarprodukt gemeint sein kann, während (length * vector1) die Multiplikation eines Vektor mit einem Skalar ist.
-<cpp>
+<source lang="cpp">
 Rückgabewert:
   Kollision an Polygonfläche
@@ Zeile 155: / Zeile 155: @@
+	}
 	...
-</cpp>
+</source>
 ===Kollision mit der Polygonfläche===
@@ Zeile 171: / Zeile 171: @@
 Damit haben wir schon alles zusammen und können die Funktion weiter ausbauen:
-<cpp>
+<source lang="cpp">
 	...
 	// Kollision an der Ebene ist nur sinnvoll, wenn die
@@ Zeile 192: / Zeile 192: @@
+	}
 	...
-</cpp>
+</source>
 ===Kollision mit den Ecken und Kanten===
@@ Zeile 233: / Zeile 233: @@
 Nun brauchen wir nur noch festzustellen, ob der Punkt auf dem geforderten Streckenabschnitt, der Kante, liegt. Wie das gemacht wird, ist aus der Funktion ''EdgeIntersect'' ([[Werkzeugkiste]]) herauszulesen. Hier geht es nun mit der Funktion ''PolygonIntersect'' wie folgt weiter:
-<cpp>
+<source lang="cpp">
 	...
 	// Flag, ob Kollision schon festgestellt wurde
@@ Zeile 276: / Zeile 276: @@
 	return -1;
+}
-</cpp>
+</source>
 ===Die nächstliegende Kollision===
@@ Zeile 284: / Zeile 284: @@
 Ich setzte hier voraus, dass die in Frage kommenden Polygone in einem Array gesammelt sind. Dieses Array wird nun iterativ abgearbeitet. Die Vertices der Polygone werden in ein lokales Array ''vertices [ ]'' umgespeichert. Das ist zwar nur nötig, wenn wir das Verfahren auf Ellipsoide erweitern, aber so ist schon mal die Stelle gekennzeichnet, wo das erfolgen kann.
-<cpp>
+<source lang="cpp">
 // zunächst eine mögliche Datenstruktur:
 typedef struct {
@@ Zeile 330: / Zeile 330: @@
 	return hit_type;
+}
-</cpp>
+</source>
@@ Zeile 357: / Zeile 357: @@
 Ich habe diese Aspekte allerdings nicht berücksichtigt, da ich nur den geometrischen Teil umsetzen wollte. Meiner Meinung nach ist es nicht immer günstig, physikalische Sachverhalte in den geometrischen Algorithmus einfließen zu lassen, das sollte vielmehr Aufgabe einer Physik-Engine sein. Dann allerdings muss die Physik die notwendigen Informationen über die Kollision erhalten, damit sie Kraft und Bewegung richtig berechnen kann. Zu diesen Information gehört die Steilheit des Aufpralls, die wir durch das Skalarprodukt aus dem Bewegungsvektor und der Normalen der Gleitebene bestimmen können. Wir gebrauchen das Produkt außerdem in der Kollisionsbehandlung, und zwar um zu erkennen, ob die Kugel senkrecht aufprallt. Dann lässt sich nämlich kein Gleitpfad berechnen, denn (B-P) ist ein Nullvektor.
-<cpp>
+<source lang="cpp">
 void CollisionResponse (TCollision *coll, int type) {
 	// Kugel wird zum Kollisionspunkt bewegt. Vergößern wir den
@@ Zeile 390: / Zeile 390: @@
 	coll->vel = ScaleVector (coll->len, coll->dir);
+}
-</cpp>
+</source>
 ===Der gesamte Vorgang===
@@ Zeile 396: / Zeile 396: @@
 Zum Schluss sollten wir das Ganze noch zu einer Funktion zusammenfassen, die dann von zentraler Stelle aufgerufen wird.
-<cpp>
+<source lang="cpp">
 void CheckCollision (double timestep) {
 	// Es wird eine globale Kontrollvariable contrl vorausgesetzt,
@@ Zeile 458: / Zeile 458: @@
 	contrl.pos = coll.pos;  // Ellipsoid: über Matrix;
+}
-</cpp>
+</source>

@@ Zeile 496: / Zeile 496: @@
 '''Reinhard'''
-{{TUTORIAL_NAVIGATION|[[Tutorial Kollision1]]|-}}
+{{TUTORIAL_NAVIGATION|[[Tutorial Kollision1]]|[[Tutorial Kollision3]]}}
 [[Kategorie:Tutorial|Kollision2]]

@@ Zeile 15: / Zeile 15: @@
 In Wirklichkeit geht es gar nicht um die Kugel an sich wie beim Billardtisch im 1. Teil des Tutorials, sondern es geht um Objekte, die annähernd mit der Form einer Kugel beschrieben werden können. Betrachten wir mal zwei Akteure aus Tuxracer:
-[[Bild:Tutorial_Kollision2_07.jpg|center|framed|Links Tux, der uns freundlicherweise fast immer das Hinterteil zeigt, rechts Boris, etwas steif und bequem]]
+[[Bild:Tutorial_Kollision2_07.jpg|center|framed|Links Tux, der uns freundlicherweise fast immer das Hinterteil zeigt, rechts Boris, der es etwas lockerer angeht]]
 Klar, dass auch ein mit Heringen vollgefressener Pinguin trotz enormen Taillenumfangs niemals zu einer richtigen Kugel wird, aber wenn es um Kollisionen geht, muss es nicht unbedingt stören, wenn der Anzug nicht ganz genau passt ...

@@ Zeile 474: / Zeile 474: @@
 http://www.peroxide.dk/papers/collision/collision.pdf
-Ich selber konnte den Artikeln eine Menge Anregungen und Informationen entnehmen und möchte mich bei den Autoren bedanken. Wer sich näher mit der Materie befassen will, sollte die Beiträge unbedingt lesen.
+Ich selber konnte den Artikeln eine Menge Anregungen und Informationen entnehmen und möchte mich bei den Autoren bedanken. Wer sich näher mit der Materie befassen will, sollte die Beiträge unbedingt lesen. Trotzdem halte ich es für sinnvoll, die Artikel etwas kritisch unter die Lupe zu nehmen. Paul Nettle beschreibt sehr knapp, jedoch vollständig ein relativ einfaches Verfahren, das aber leider einige Mängel aufweist. Die Kantenkollision funktioniert nicht sauber, besonders bei schrägem Anschnitt (etwa < 43°) wird die Kollision nur noch unzuverlässig erkannt. Der Grund: Nettle verwendet dafür ein grobes Näherungsverfahren, das hier an seine Grenzen stößt. Auch der mitgelieferte Pseudocode ist etwas oberflächlich und ungenau und kann nicht direkt umgesetzt werden.
 Jorrit Rouwe geht ganz anders vor. Sein Verfahren ist recht aufwendig, scheint aber genau zu sein und macht in der Praxis einen robusten Eindruck. Der Artikel ist mathematisch ziemlich anspruchsvoll verfasst und dürfte Anfängern nur mit Vorbehalt zu empfehlen sein. Die Umsetzung ist teilweise sehr eigenwillig, und wer einen gradlinigen, effizienten Code bevorzugt, wird mit Jorrits Code kaum etwas anfangen können. Hinzu kommt, dass der Code in einem schwer übertragbaren Stil, der alle Register von C++ zieht, verfasst ist. Gleichwohl enthält der Beitrag eine Reihe von wichtigen und nützlichen Informationen, vor allem, wenn es um die mathematischen Sachverhalte geht.

@@ Zeile 71: / Zeile 71: @@
 Dieser Vorbereitungsschritt erfüllt zwei Aufgaben. Zum einen sollen so früh wie möglich alle Situationen ausgeschlossen werden, bei denen keine Kollision stattfinden kann. Denn bei aller "Kontaktfreudigkeit": die beste Kollision ist immer noch die nicht stattfindende, denn sie erspart dem Rechner viel Arbeit.
-Die andere Aufgabe besteht darin, den Schnittbereich der Kugel mit der Polygonebene zu berechnen - für spätere Rechnungen. Der Schnittbereich hängt vom Radius der Kugel ab und geht von der ersten Berührung mit der Vorderseite der Ebene bis zu der Stelle, wo sich die Kugel auf der Rückseite von der Ebene löst. Wenn die Kugel innerhalb eines Bewegungsschrittes die Ebene voll durchdringt, ist der Schnittbereich ein Abschnitt des Bewegungsvektors, der wiederum durch die Werte 0 und 1 begrenzt wird (siehe [Werkzeugkiste]]). Aber das ist nur ein Sonderfall. Die Zeichnung zeigt die möglichen Fälle:
+Die andere Aufgabe besteht darin, den Schnittbereich der Kugel mit der Polygonebene zu berechnen - für spätere Rechnungen. Der Schnittbereich hängt vom Radius der Kugel ab und geht von der ersten Berührung mit der Vorderseite der Ebene bis zu der Stelle, wo sich die Kugel auf der Rückseite von der Ebene löst. Wenn die Kugel innerhalb eines Bewegungsschrittes die Ebene voll durchdringt, ist der Schnittbereich ein Abschnitt des Bewegungsvektors, der wiederum durch die Werte 0 und 1 begrenzt wird (siehe [[Werkzeugkiste]]). Aber das ist nur ein Sonderfall. Die Zeichnung zeigt die möglichen Fälle:
 [[Bild:Tutorial_Kollision2_03.png|center|framed]]

← Nächstältere Version		Version vom 9. April 2008, 11:22 Uhr
Zeile 491:		Zeile 491:
	*Mehrfacherkennungen und "Kollisionsbremsen"		*Mehrfacherkennungen und "Kollisionsbremsen"

		+	Noch ein letzter Hinweis: Für diejenigen, die mit Pascal vertraut sind und sich mit C überhaupt nicht auskennen, habe ich eine kleine Übersetzungshilfe auf meine Homepage gestellt:
		+	http://www.erinacom.de/ogl/collision/translate.html

	Und jetzt wünsche ich viel Erfolg mit der Kugel. Möge sie stets den richtigen Weg finden und nicht zu eigenwillig sein.		Und jetzt wünsche ich viel Erfolg mit der Kugel. Möge sie stets den richtigen Weg finden und nicht zu eigenwillig sein.

@@ Zeile 491: / Zeile 491: @@
 *Mehrfacherkennungen und "Kollisionsbremsen"
-Bis dahin wünsche ich viel Erfolg mit der Kugel. Möge sie stets den richtigen Weg finden und nicht zu eigenwillig sein.
+Und jetzt wünsche ich viel Erfolg mit der Kugel. Möge sie stets den richtigen Weg finden und nicht zu eigenwillig sein.
 '''Reinhard'''