NeHe - Lektion 30 - Kollisionsabfrage

Written by Joachim on
Lektion 30



Kollisionserkennung und physikalisch basierte Modellierung Tutorial von Dimitrios Christopoulos (christop@fhw.gr).

Der Source Code dieses Tutorials basiert auf einem älteren Contest-Beitrag von mir (bei OGLchallenge.dhs.org). Das Thema war Collision Crazy und mein Beitrag (welches so nebenbei gesagt den ersten Platz erhielt :)) hieß Magic Room. Er beinhaltet Kollisionsabfrage, physikalisch basierte Modellierung und Effekte.

Kollisionserkennung

Ein schwieriges Thema und wenn ich ehrlich bin, soweit ich das bisher überblicken kann, gibt es keine einfach Lösung dafür. Für jede Applikation gibt es einen anderen Weg um Kollisionen zu finden und darauf zu testen. Natürlich gibt es Brute Force Algorithmen, welche sehr allgemein sind und mit jeder Art Objekt funktionieren würden, aber diese sind langsam.

Wir schauen uns Algorithmen an, die sehr schnell sind, einfach zu verstehen und bis zu einem gewissen Grad flexibel sind. Des weiteren muss ein Schwerpunkt darauf liegen, was getan werden muss, wenn eine Kollision erkannt wurde und wie die Objekte dann, entsprechend der physikalischen Gesetze, weiterbewegt werden müssen. Eine Menge Stoff gilt es abzudecken. Fassen wir zusammen, was wir lernen werden:

1) Kollisionserkennung
  • bewegliche Sphere - Ebene
  • bewegliche Sphere - Cylinder
  • bewegliche Sphere - bewegliche Sphere
2) Physicalisch basierte Modellierung
  • Kollisions Reaktion
  • Bewegung unter Gravität mit Benutzung der Euler Gleichung
3) Spezial Effekte
  • Explosions Modellierung unter Benutzung einer "Fin-Tree Billboard" Methode
  • Sounds unter Benutzung der Windows Multimedia Library (nur für Windows)
4) Erklärung des Codes
  • Der Code ist in 5 Dateien unterteilt
Lesson30.cpp   : Main Code für dieses Tutorial
Image.cpp, Image.h : Code zum Laden von Bitmaps
Tmatrix.cpp, Tmatrix.h : Klassen um Rotationen zu händeln
Tray.cpp, Tray.h : Klassen um Strahlen Operationen zu händeln
Tvector.cpp, Tvector.h : Klassen um Vektor Operationen zu händeln

Viel handlicher Code! Die Klassen Vector, Ray und Matrix sind sehr nützlich. Ich benutze Sie immer noch für persönliche Projekte von mir.

1) Kollisionserkennung

Für die Kollisionserkennung werden wir Algorithmen verwenden, die vor allem beim Ray Tracing verwendet werden. Lassen Sie uns erst einen Strahl (Ray) definieren.

Ein Ray, der die Vektor-Repräsentation nutzt, wird durch einen Vektor repräsentiert, welcher den Startpunkt kennzeichnet und einen Vektor (normalerweise normalisiert), welcher die Richtung (direction) angibt, in die der Strahl sich bewegt. Grundsätzlich startet ein Strahl am Startpunkt und bewegt sich in die Richtung des Richtungsvektors. Deshalb ist unsere Ray-Gleichung wie folgt:

PointOnRay = Raystart + t * Raydirection

t ist eine Fließkommazahl, welche folgende Werte annehmen kann: [0, infinity).

Mit 0 erhalten wir den Startpunkt und durch Substituierung anderer Werte erhalten wir die entsprechenden Punkte entlängs des Strahls. PointOnRay, Raystart, Raydirection sind 3D Vektoren mit Werten (x,y,z). Nun können wir diese Strahlen-Darstellung verwenden und die Intersektion mit Ebenen oder Zylindern berechnen.

Strahl - Ebene Intersektions Erkennung

Eine Ebene wird durch die folgende Vektor-Repräsentation repräsentiert:

Xn dot X = d

Xn, X sind Vektoren und d ist ein Fließkommawert.
Xn ist dessen Normalenvektor
X ist ein Punkt auf dessen Oberfläche
d ist eine Fließkommazahl der die Distanz der Ebene entlängs des Normalenvektors vom Zentrum des Koordinatensystems repräsentiert.

Grundsätzlich repräsentiert eine Ebene einen halben Raum. Deshalb benötigen wir zur Definition einer Ebene einen 3D Punkt und einen Normalenvektor von diesem Punkt aus, der senkrecht zur Ebene steht. Diese beiden Vektoren formen eine Ebene, wenn wir z.B. für den 3D Punkt den Vektor (0,0,0) nehmen und für den Normalenvektor (0,1,0), definieren wir einfach eine Ebene entlängs der X,Z Achsen. Deshalb langt es, einen Punkt und einen Normalenvektor zu definieren, um eine Ebene vektoriell darzustellen.

Bei Benutzung der Vektor-Gleichung der Ebene, wird der Normalenvektor als Xn eingesetzt und der 3D Punkt von dem der Normalenvektor ausgeht, als X eingesetzt. Der einzige Wert der noch fehlt ist d, welcher einfach über das Skalarprodukt berechnet werden kann (durch die Vektor-Gleichung).

(Anmerkung: Diese Vektor-Repräsentation ist die Selbe wie die durchaus bekannt parametrische Form der Ebene Ax + By + Cz + D=0, setzen Sie einfach die drei x,y,z Werte des Normalenvektors als A,B,C und setzen Sie D=-d).

Die zwei Gleichungen die wir bisher haben sind:

PointOnRay = Raystart + t * Raydirection
Xn dot X = d

Wenn ein Strahl eine Ebene an einem Punkt schneidet, dann muss es einen Punkt auf dem Strahl geben, der die Ebenen-Gleichung wie folgt erfüllt:

Xn dot PointOnRay = d or (Xn dot Raystart) + t * (Xn dot Raydirection) = d

Auflösen nach t:

t = (d - Xn dot Raystart) / (Xn dot Raydirection)

Ersetzung von d:

t= (Xn dot PointOnPLANE - Xn dot Raystart) / (Xn dot Raydirection)

Aufsummieren:

t= (Xn dot (PointOnPLANE - Raystart)) / (Xn dot Raydirection)

t repräsentiert die Distanz vom Start bis zum Schnittpunkt entlängs der Richtung des Strahls. Deshalb können wir durch einsetzen von t in die Strahlen-Gleichung den Kollisionspunkt ermitteln. Es gibt allerdings ein paar Sonderfälle. Wenn Xn dot Raydirection = 0, dann sind die beiden Vektoren senkrecht zu einander (Strahl verläuft parallel zur Ebene) und es wird keine Kollision geben. Wenn t negativ ist, wird die Kollision hinter dem Startpunkt des Strahls entlängs der entgegengesetzten Richtung stattfinden und erneut gibt es keinen Schnittpunkt. 

int TestIntersionPlane(const Plane& plane,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal)
{
    double DotProduct=direction.dot(plane._Normal);            // Skalarprodukt zwischen Ebenen Normalenvektor und Ray Richtung
    double l2;

    // bestimme ob Ray parallel zur Ebene ist
    if ((DotProduct<ZERO)&&(DotProduct>-ZERO))
        return 0;

    l2=(plane._Normal.dot(plane._Position-position))/DotProduct;    // Finde Distanz zum Kollisionspunkt

    if (l2// Teste ob Kollision hinter Start ist
        return 0;

    pNormal=plane._Normal;
    lamda=l2;
    return 1;
}

Der obige Code berechnet die Intersektion und liefert sie zurück. Er liefert 1 zurück, wenn eine Intersektion vorhanden ist und ansonsten 0. Die Parameter sind die Ebene, der Startpunkt und die Richtung des Vektors, ein double-Wert (lamda), wo die Kollisions-Distanz abgespeichert wird, wenn es eine gibt und der zurückgelieferte Normalenvektor des Kollisionspunktes.

Strahl - Zylinder Intersektion

Die Berechnung der Intersektion zwischen einem unendlichen Zylinder und einem Strahl ist viel komplizierter, weshalb ich es hier nicht erklären werde. Es gibt viel zu viel Mathematik dadrin um es hier einfach zu erklären und mein Ziel ist es, Ihnen Werkzeuge an die Hand zu geben, ohne großartig ins Detail zu gehen (das ist hier kein Geometrie Kurs). Wenn jemand an der Theorie hinter dem Intersektions-Code interessiert ist, schauen Sie in das Buch Graphic Gems II (S. 35f, Intersection of a with a cylinder). Ein Zylinder wird durch einen Strahl repräsentiert, wobei ein Start und ein Richtungsvektor (hier repräsentiert er die Achsen) und einem Radius (Radius um die Achsen des Zylinders) besteht. Die relevante Funktion ist: 

int TestIntersionCylinder(const Cylinder& cylinder,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal,TVector& newposition)

Gibt 1 zurück, wenn eine Intersektion gefunden wurde, ansonsten 0.

Die Parameter sind die Zylinder Struktur (schauen Sie sich die Code-Erklärung weiter unten an), der Start-, Richtungvektor des Strahls. Die Werte die durch die Parameter zurückgegeben werden, sind die Distanz, der Normalenvektor des Schnittpunktes und der Schnittpunkt selbst.

Sphere - Sphere Kollision

Eine Sphere wird durch ihr Zentrum und ihren Radius repräsentiert. Zu bestimmen, ob zwei Spheren kollidieren ist einfach. Durch herausfinden der Distanz zwischen den zwei Zentren (die dist-Methode der TVector Klasse), können wir bestimmen, ob sie sich schneiden, und zwar dann wenn die Distanz kleiner als die Summe der beiden Radien ist.

Das Problem liegt in der Bestimmung, ob 2 sich BEWEGENDE Spheren schneiden. Unten ist ein Beispiel wo 2 Spheren während eines Zeitschritts von einem Punkt zu einem anderen bewegt werden. Ihre Wege kreuzen sich, aber das ist nicht genug um zu beweisen, dass eine Schneidung passieren wird (sie könnten ja zu verschiedenen Zeiten kreuzen), noch kann ein Kollisionspunkt bestimmt werden.


Abbildung 1

Die vorherige Intersektions-Methoden haben die Gleichungen der Objekte gelöst um die Intersektion zu bestimmen. Wenn komplexe Formen benutzt werden oder wenn diese Gleichungen nicht verfügbar sind oder nicht gelöst werden können, muss eine andere Methode verwendet werden. Die Startpunkte, Endpunkte, Zeitschritt, Geschwindigkeit (Richtung der Sphere + Geschwindigkeit) der Sphere und eine Methode, wie man Intersektionen von statischen Spheren berechnet, sind bereits bekannt. Um die Intersektion zu berechnen, muss der Zeitschritt in kleinere Teile eingeteilt werden. Dann bewegen wir die Spheren entsprechend des unterteilten Zeitschrittes, indem wir seine Geschwindigkeit verwenden und auf Kollisionen überprüfen. Wenn an irgend einem Punkt eine Kollision gefunden wird (was bedeutet, dass die Spheren bereits ineinander eingedrungen sind), dann nehmen wir den vorherigen Punkt als Intersektionspunkt (wir könnten anfangen zwischen diesen Punkten zu interpolieren, um die exakte Intersektionsposition zu finden, aber das ist in der Regel nicht notwendig).

Je kleiner die Zeitschritte, je mehr Unterteilungen, desto genauer ist die Methode. Als Beispiel sagen wir, dass ein Zeitschritt 1 ist und 3 geteilt wird. Wir könnten die zwei Bälle auf Kollision überprüfen zu den Zeiten 0, 0.33, 0.66, 1. Ganz einfach !!!!

Der Code der das macht, ist folgender: 

/*************************************************************************************************/
/***                      Überprüfe ob einer der aktuellen Bälle                               ***/
/***                sich miteinander im aktuellen Zeitschritt schneiden                        ***/
/*** Gebe den Index der 2 schneidenden Bälle zurück , den Punk und die Zeit der Überschneidung ***/
/*************************************************************************************************/

int FindBallCol(TVector& point, double& TimePoint, double Time2, int& BallNr1, int& BallNr2)
{
    TVector RelativeV;
    TRay rays;
    double MyTime=0.0, Add=Time2/150.0, Timedummy=10000, Timedummy2=-1;
    TVector posi;                            // Teste alle Bälle gegeneinander in 150 kleinen Schritten
    for (int i=0;i<NrOfBalls-1;i++)
    {
        for (int j=i+1;j<NrOfBalls;j++)
        {
            RelativeV=ArrayVel[i]-ArrayVel[j];        // Finde Distanz
            rays=TRay(OldPos[i],TVector::unit(RelativeV));
            MyTime=0.0;

            if ( (rays.dist(OldPos[j])) > 40) continue;     // wenn Distanz zwischen den Zentren größer als 2*radius ist
                                    // ist eine Intersektion aufgetreten
            while (MyTime<Time2)                // durchlaufe eine Schleife um den exakten Intersektionspunkt zu finden
            {
                MyTime+=Add;
                posi=OldPos[i]+RelativeV*MyTime;
                if (posi.dist(OldPos[j])(MyTime-Add)) Timedummy=MyTime-Add;
                    BallNr1=i;
                    BallNr2=j;
                    break;
                }
            }
        }
    }

    if (Timedummy!=10000)
    {
        TimePoint=Timedummy;
        return 1;
    }
    return 0;
}

Wie man das eben gelernte anwendet

So, nun da wir den Intersektionspunkt zwischen einem Strahl und einer Ebene/Zylinder bestimmten können, müssen wir ihn irgendwie dazu benutzen um die Kollision zwischen einer Sphere und einem dieser Primitiven zu bestimmen. Was wir bisher machen können, ist den exakten Kollisionspunkt zwischen einem Partikel und einer Ebene/Zylinder bestimmen. Die Startposition des Strahls ist die Position des Partikels und die Richtung des Strahls ist seine Geschwindigkeit (Geschwindigkeit und Richtung). Es für Spheren nutzbar zu machen ist recht einfach. Schauen Sie sich Abbildung 2a an, um zu sehen, wie dieses erreicht wird.


Abbildung 2a                                         Abbildung 2b

Jede Sphere hat einen Radius, nehmen Sie das Zentrum der Sphere als den Partikel und verschiebt die Oberfläche entlängs des Normalenvektors jeder Ebene/Zylinders, die von Interesse ist. In Abbildung 2a werden diese neuen Primitiven mit gestrichelten Linien repräsentiert. Die Primitive die von eigentlichem Interesse sind, sind durch durchgängige Linien dargestellt, aber der Kollisionstest wird mit den verschobenen Primitiven (dargestellt durch gestrichelte Linien) vorgenommen. Im Grund führen wir den Intersektionstest mit einer kleinen verschobenen Ebene und einem im Radius größeren Zylinder durch. Mit diesem kleinen Trick stellen wir sicher, dass der Ball nicht in die Oberfläche eintaucht, wenn eine Intersektion mit dessen Zentrum festgestellt wird. Ansonsten erhalten wir die Situation wie in Abbiuldung 2b, wo die Sphere in die Oberfläche eintaucht. Das passiert, da wir die Intersektion zwischen dessen Zentrum den Primitiven bestimmen, was bedeutet, dass wir nicht unseren origianl Code modifizieren!

Haben wir den Ort der Kollision bestimmt, müssen wir bestimmen, ob die Intersektion in unserem aktuellen Zeitschritt statt findet. Der Zeitschritt ist die Zeit, die wir unsere Sphere von seinem aktuellen Punkt entsprechend seiner Geschwindigkeit aus bewegen. Da wir mit unendlichen Strahlen testen, gibt es immer die Möglichkeit, dass der Kollisionspunkt hinter der neuen Position der Sphere statt findet. Um das zu bestimmen, bewegen wir die Sphere, berechnen ihre neue Position und finden die Distanz zwischen dem Start und Endpunkt. Von unserer Kollisionserkennungs-Prozedur erhalten wir auch die Distanz vom Startpunkt zum Kollisionspunkt. Wenn diese Distanz kleiner als die Distanz zwischen Start und Endpunkt ist, dann gibt es da eine Kollision. Um die exakte Zeit zu berechnen, lösen wir folgende simple Gleichung. Die Distanz zwischen Start und Endpunkt wird durch Dst repräsentiert, die Distanz zwischen Start und Kollisionspunkt durch Dsc und der Zeitschritt durch T. Die Zeit zu der die Kollision stattfindet (TC) ist:

Tc= Dsc*T / Dst

All das wird ausgeführt, wenn natürlich eine Intersektion bestimmt wurde. Die zurückgegebene Zeit ist ein Bruchstück des gesamten Zeitschritts, wenn der Zeitschritt also 1 Sek. wäre und wir eine Intersektion exakt in der Mitte der Distanz finden, würde die berechnete Kollision bei 0.5 Sek. stattfinden, was als "o.5 Sek. nach dem Start gibt es eine Intersektion" interpretiert wird. Nun kann der Intersektionspunkt berechnet werden, indem einfach TC mit der aktuellen Geschwindigkeit multipliziert wird und zum Startpunkt addiert wird.

Kollisionspunkt= Start + Velocity*Tc

Dies ist der Kollisionspunkt der verschobenen Primitive, um den Kollisionspunkt auf dem wirklichen Primitiv zu finden, addieren wir zu diesem Punkt den Kehrwert des Normalenvektors dieses Punktes (welcher ebenso von den Intersektions-Routinen zurückgegeben wird) mit dem Radius der Sphere. Beachten Sie, dass die Zylinder Intersektions-Routine den Intersektions-Punkt zurückgibt, wenn es einen gibt, so dass dieser nicht berechnet werden muss.

2) Physikalisch basierte Modellierung

Kollisions Reaktion

Um zu bestimmen wie man auf einen Zusammenprall von statischen Objekten wie Ebenen, Zylindern reagieren soll, ist es wichtig, den Kollisionspunkt an sich herauszufinden. Verwendet man die beschriebenen Algorithmen und Funktionen, so kann der exakte Kollisionspunkt, der Normalenvektor des Kollisionspunktes und die Zeit innerhalb eines Zeitschrittes, zu der die Kollision auftritt, herausgefunden werden.

Um herauszufinden, wie auf eine Kollision reagiert werden soll, müssen physikalische Gesetze angewendet werden. Wenn ein Objekt mit der Oberfläche kollidiert, ändert sich dessen Richtung zum Beispiel. Der Winkel der neuen Richtung (oder des Reflektionsvektor) mit dem Normalenvektor am Kollisionspunkt ist der selbe wie der original Richtungsvektor. Abbildung 3 zeigt eine Kollision mit einer Sphere.


Abbildung 3

R ist der neue Richtungsvektor
I ist der alte Richtungsvektor vor der Kollision
N ist der Normalenvektor des Kollisionspunktes

Der neue Vektor R wird wie folgt berechnet:

R= 2*(-I dot N)*N + I

Die Restriktion ist, dass die Vektoren I und N Einheitsvektoren sein müssen. Der Geschwindigkeitsvektor, wie er in unserem Beispiel verwendet wird, repräsentiert Geschwindigkeit und Richtung. Deshalb kann er nicht in die Gleichung anstelle von I eingesetzt werden, ohne folgende Transaformation. Die Geschwindigkeit muss erst extrahiert werden. Die Geschwindigkeit für einen solchen Geschwindigkeitsvektor wird extrahiert, indem die Größe des Vektors herausgefunden wird. Wenn die Größe bekannt ist, kann der Vektor in einen Einheitsvektor umgeformt werden und in die Gleichung eingesetzt werden, die den Reflektionsvektor R berechnet. R zeigt uns nun die Richtung des reflektierten Rays, aber um ihn auch als Geschwindigkeitsvektor verwenden zu können, muss er auch die Geschwindigkeit enthalten. Deshalb wird er mit der Größe des originalen Rays multipliziert, woraus der korrekte Geschwindigkeitsvektor resultiert.

In dem Beispiel wird diese Prozedur verwendet, um die Kollisions-Reaktion zu berechnen, wenn ein Ball eine Ebene oder einen Zylinder berührt. Das funktionert aber für jede willkürliche Oberfläche, es ist egal welche Form die Oberfläche hat. So lange der Kollisionspunkt und der Normalenvektor durch die Kollisions-Reaktions-Methode gefunden werden kann, ist es immer das Selbe. Der Code der diese Operationen durchführt ist: 

rt2=ArrayVel[BallNr].mag();                        // Finde die Größe der Geschwindigkeit
ArrayVel[BallNr].unit();                        // Normalisiere

// berechne Reflektion
ArrayVel[BallNr]=TVector::unit( (normal*(2*normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );
ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;                    // multipliziere mit der Größe, um den finalen Geschwindigkeitsvektor zu erhalten

Wenn Spheren andere Spheren schneiden

Die Bestimmung der Kollisions Reaktion, wenn zwei Bälle sich treffen, ist viel schwieriger. Komplexe Gleichungen an Partikel Dynamik müssen gelöst werden, weshalb ich die endgültige Lösung ohne Beweis hier darlegen werde. Vertrauen Sie mir einfach dabei :) Während der Kollision von 2 Bällen haben wir eine Situation, wie sie in Abbildung 4 dargestellt ist.


Abbildung 4

U1 und U2 sind die Geschwindigkeitsvektoren der zwei Spheren zum Zeitpunkt des Zusammenstosses. Da ist ein Achsenvektor (X_Axis = X-Achse), der mit den 2 Zentren der Spheren verbunden wird und U1x, U2x sind die projektzierten Vektoren der Geschwindigkeitsvektoren U1,U2 auf dem Achsenvektor (X_Axis).

U1y und U2y sind die Projektionsvektoren der Geschwindigkeitsvektoren U1,U2 auf der Achse, die senkrecht zur X_Axis ist. Um diese Vektoren zu finden, werden einige simple Skalarprodukte (dot) benötigt. M1, M2 ist die Masse der jeweiligen zwei Spheren. V1,V2 sind die neuen Geschwindigkeite nach dem Zusammenstoss und V1x, V1y, V2x, V2y sind die Projektionen der Geschwindigkeitsvektoren auf der X_Axis.

Im Detail:

a) Finde X_Axis

X_Axis = (center2 - center1);
Unify X_Axis, X_Axis.unit();

b) Finde Projectionen

U1x= X_Axis * (X_Axis dot U1)
U1y= U1 - U1x
U2x =-X_Axis * (-X_Axis dot U2)
U2y =U2 - U2x

c)Finde neue Geschwindigkeiten

(U1x * M1)+(U2x*M2)-(U1x-U2x)*M2
V1x= --------------------------------
M1+M2
(U1x * M1)+(U2x*M2)-(U2x-U1x)*M1
V2x= --------------------------------
M1+M2

In unserer Applikation setzen wir M1=M2=1, so dass die Gleichungen sogar noch einfacher werden.

d)Finde die finalen Geschwindigkeiten

V1y=U1y
V2y=U2y
V1=V1x+V1y
V2=V2x+V2y

Die Ableitung dieser Gleichungen ist eine Menge Arbeite, aber wenn sie erst einmal in der obigen Form sind, können sie recht einfach verwendet werden. Der Code, der die eigentliche Reaktion auf die Kollision enthält, ist: 

TVector pb1,pb2,xaxis,U1x,U1y,U2x,U2y,V1x,V1y,V2x,V2y;
double a,b;
pb1=OldPos[BallColNr1]+ArrayVel[BallColNr1]*BallTime;            // Finde Position von Ball1
pb2=OldPos[BallColNr2]+ArrayVel[BallColNr2]*BallTime;            // Finde Position von Ball2
xaxis=(pb2-pb1).unit();                            // Finde X-Achse
a=xaxis.dot(ArrayVel[BallColNr1]);                    // Finde Projektion
U1x=xaxis*a;                                // Finde Projektierte Vectoren
U1y=ArrayVel[BallColNr1]-U1x;
xaxis=(pb1-pb2).unit();                            // mache das Selbe wie oben
b=xaxis.dot(ArrayVel[BallColNr2]);                    // um die Projektionsvektoren
U2x=xaxis*b;                                // für die anderen Bälle zu finden
U2y=ArrayVel[BallColNr2]-U2x;
V1x=(U1x+U2x-(U1x-U2x))*0.5;                        // nun finde die neuen Geschwindigkeiten
V2x=(U1x+U2x-(U2x-U1x))*0.5;
V1y=U1y;
V2y=U2y;
for (j=0;j<NrOfBalls;j++)                        // aktualisiere alle Ball Positionen
ArrayPos[j]=OldPos[j]+ArrayVel[j]*BallTime;
ArrayVel[BallColNr1]=V1x+V1y;                        // Setze neue Geschwindigkeitsvektoren
ArrayVel[BallColNr2]=V2x+V2y;                        // für die kollidierenden Bälle

Bewegung unter Gravitation unter Benutzung der Euler Gleichungen

Um realisitsche Bewegungen mit Kollisionen zu simulieren, langt es nicht, den Kollisionspunkt und die Reaktion darauf zu berechnen. Bewegung die auf physikalischen Gesetzen basiert, muss simuliert werden.

Die verbreitetste Methode um das zu machen, ist die Benutzung von Euler Gleichungen. Wie angedeutet wurde, werden alle Berechnungen in Zeitschritten ausgeführt. Das bedeutet, dass die gesamte Simulation in einigen Zeitschritten vorraus ist, während all die Bewegung, Kollision und Reaktiohn Test durchgeführt werden. Zum Beispiel können wir eine Simulation 2 Sekunden jeden Frame vorraus sein. Basierend auf Euler Gleichungen, wird die Geschwindigkeit und Position zu jedem Zeitschritt wie folgt berechnet:

Geschwindigkeit_Neu = Geschwindigkeit_Alt + Beschleunigung*Zeitschritt
Position_Neu = Position_Alt + Geschwindigkeit_Neu*Zeitschritt

Nun werden die Objekte bewegt und auf Kollision überprüft, indem diese neue Geschwindigkeit verwendet wird. Die Beschleunigung für jedes Objekt wird bestimmt, indem die Kräfte die auf jenes einwirken, akkumuliert werden und durch die Masse dividiert werden, so wie in dieser Gleichung:

Kraft = Masse * Beschleunigung

Viele physikalische Formeln :)

Aber in unserem Fall ist die einzige Kraft, die auf das Objekt einwirkt, die Anziehungskraft, welche durch einen Vektor repräsentiert wird, der eine Beschleunigung indiziert. In unserem Fall etwas negatives in die Y-Richtung, etwas wie (0,-0.5,0). Das bedeutet, dass am Anfang jedes Zeitschrittes, wir die neue Geschwindigkeit jeder Sphere berechnen und sie bewegen, testend auf Kollisionen. Wenn eine Kollision während eines Zeitschritts auftritt (sagen wir, nach 0.5 Sek. wobei ein Zeitschritt gleich 1.0 Sek is.) Wir rücken das Objekt vor zu dieser Position, berechnen die Reflektion (neuen Geschwindigkeitsvektor) und bewegen das Objekt um die verbleibende Zeit (was in unserem Beispiel 0.5 ist), erneut auf Kollision testend während dieser Zeit. Diese Prozedur wird solange wiederholt, bis der Zeitschritt vollständig ist.

Wenn mehrere bewegende Objekte vorhanden sind, wird jedes bewegende Objekt mit der statischen Geometrie für Intersektionen getestet und die nähste Intersektion gemerkt. Dann wird der Intersektions-Test für Kollisionen unter den Objekten ausgeführt, wo jedes Objekt mit jedem anderen getesetet wird. Die zurückzuliefernde Intersektion wird mit der Intersektion verglichen, die vom statischen Objekt zurückgegeben wird und die nähste wird genommen. Die ganze Simulation wird zu diesem Zeitpunkt aktualisiert (z.B. wenn die nähste Intersektion nach 0.5 Sek. wäre, würden wir alle Objekte um 0.5 Sekunden bewegen), der Reflektions-Vektor wird für das kollidierende Objekt berechnet und die Schleife wird wieder für die verbleibende Zeit durchlaufen.

3) Spezial Effekte

Explosionen

Jedes Mal, wenn eine Kollision statt findet, wird eine Explosion am Kollisionspunkt ausgelöst. Eine nette Art Explosionen zu modellieren, ist es, ein Alpha Blend zweier Polygone zu machen, welche senkrecht zu einander stehen und als Zentrum den Punkt von Interesse haben (hier der Schnittpunkt). Die Polygone werden skaliert und verschwinden mit der Zeit. Das Verschwinden wird durch Änderung der Alpha Werte jedes Vertices von 1 auf 0 erreicht. Da viele Alpha geblendete Polygone Probleme verursachen können und sich einander überlappen können (wie es im Red Book im Kapitel über Transparenz und Blending steht) wegen des Z-Buffer, borgen wir uns eine Technik, die beim Partikel Rendern verwendet wird. Um korrekt vorzugehen, müssten wir die Polygone von hinten nach vorne entsprechend dem Abstand zum Eye-Point sortieren, aber das deaktivieren der Depth-Buffer-Schreibzugriffe (nicht Lesen), macht das Selbe (das wird auch im Red Book dokumentiert). Beachten Sie, dass wir die Azahl der Explosionen auf ein Maximum von 20 pro Frame setzen, wenn zusätzliche Explosionen auftreten und der Buffer voll ist, wird die Explosion verworfen. Der Source, der die Explosionen aktualisiert und rendert, ist folgender: 

// Render / Blend Explosions
glEnable(GL_BLEND);                            // aktiviere Blending
glDepthMask(GL_FALSE);                            // deaktiviere Depth Buffer Schreibzugriffe
glBindTexture(GL_TEXTURE_2D, texture[1]);                // Upload Textur
for(i=0; i// aktualisiere und rendere Explosionen
{
    if(ExplosionArray[i]._Alpha>=0)
    {
        glPushMatrix();
        ExplosionArray[i]._Alpha-=0.01f;            // aktualisiere Alpha
        ExplosionArray[i]._Scale+=0.03f;            // aktualisiere Scale
        // verbinde Vertices Farbe Gelb mit Alpha
        // Farbe Tracks Ambient und Diffuse
        glColor4f(1,1,0,ExplosionArray[i]._Alpha);        // Skaliere
        glScalef(ExplosionArray[i]._Scale,ExplosionArray[i]._Scale,ExplosionArray[i]._Scale);
        // Translatiere zur Position unter Berücksichtigung des Offsets der durch die Skalierung entsteht
        glTranslatef((float)ExplosionArray[i]._Position.X()/ExplosionArray[i]._Scale,
            (float)ExplosionArray[i]._Position.Y()/ExplosionArray[i]._Scale,
            (float)ExplosionArray[i]._Position.Z()/ExplosionArray[i]._Scale);
        glCallList(dlist);                    // rufe Display Liste auf
        glPopMatrix();
    }
}

Sound

Für den Sound wird die Windows Multimedia Funktion PlaySound() verwendet. Das ist eine schnelle und einfache Art um Wav-Dateien, ohne Probleme abzuspielen.

4) Erklärung des Codes

Glückwunsch...

Wenn Sie immer noch bei mir sind, haben Sie den Theorie-Teil erfolgreich überlebt ;) Bevor man Spaß haben kann und mit der Demo herumspielen kann, sind einige weitere Erklärungen über den Source-Code notwendig. Der Haupt-Fluss und Schritte der Simulation sind wie folgt (in Pseudo-Code): 

While (Timestep!=0)
{
    Für jeden Ball
    {
        berechne näheste Kollision mit Ebenen;
        berechne näheste Kollision mit Zylindern;
        speichere und ersetze die näheste Intersektion;
        die in der Zeit bis jetzt berechnet wurden;
    }
    Überprüfe Kollision zwischen den Bällen;
    speichere und ersetze wenn die näheste Intersektion;
    bis jetzt berechnet wurde;
    If (Kollision aufgetreten ist)
    {
        bewege alle Bälle für die die Zeit gleich der Kollisionszeit ist;
        (Wir haben bereits den Punkt, die normale und die Kollisionszeit berechnet.)
        brechne Reaktion;
        Zeitschritt-=Kollisionszeit;
    }
    else
        Bewege alle Bälle für die die Zeit gleich dem Zeitschritt ist
}

Der eigentliche Code, welcher den obigen Pseudo-Code implementiert ist viel schwieriger zu lesen, ist aber eine exakte Implementation des obigen Pseudocodes. 

// solange der Zeitschritt nicht vorbei ist
while (RestTime>ZERO)
{
    lamda=10000;                            // Initialisiere auf sehr großen Wert
    // finde für alle Bälle die am nähste Intersektion zwischen Bällen und Ebenen / Zylindern
    for (int i=0;i<NrOfBalls;i++)
    {
        // berechne neue Position und Abstand
        OldPos[i]=ArrayPos[i];
        TVector::unit(ArrayVel[i],uveloc);
        ArrayPos[i]=ArrayPos[i]+ArrayVel[i]*RestTime;
        rt2=OldPos[i].dist(ArrayPos[i]);
        // Teste ob Kollision aufgetreten ist, zwischen Ball und allen 5 Ebenen
        if (TestIntersionPlane(pl1,OldPos[i],uveloc,rt,norm))
        {
            // Finde Intersektions Zeit
            rt4=rt*RestTime/rt2;
            // falls kleiner als die bereits gespeicherte, ersetze Zeitschritt
            if (rt4// falls Intersektions Zeit im aktuellen Zeitschritt ist
                if (rt4ZERO)) )
                    {
                        normal=norm;
                        point=OldPos[i]+uveloc*rt;
                        lamda=rt4;
                        BallNr=i;
                    }
            }
        }

        if (TestIntersionPlane(pl2,OldPos[i],uveloc,rt,norm))
        {

            // ...Das Selbe wie oben, wegen Platzgründen weggelassen
        }

        if (TestIntersionPlane(pl3,OldPos[i],uveloc,rt,norm))
        {

            // ...Das Selbe wie oben, wegen Platzgründen weggelassen
        }

        if (TestIntersionPlane(pl4,OldPos[i],uveloc,rt,norm))
        {

            // ...Das Selbe wie oben, wegen Platzgründen weggelassen
        }

        if (TestIntersionPlane(pl5,OldPos[i],uveloc,rt,norm))
        {

            // ...Das Selbe wie oben, wegen Platzgründen weggelassen
        }

        // nun teste auf Intersektion mit den 3 Zylindern
        if (TestIntersionCylinder(cyl1,OldPos[i],uveloc,rt,norm,Nc))
        {
            rt4=rt*RestTime/rt2;
            if (rt4ZERO)) )
                    {
                        normal=norm;
                        point=Nc;
                        lamda=rt4;
                        BallNr=i;
                    }
            }
        }

        if (TestIntersionCylinder(cyl2,OldPos[i],uveloc,rt,norm,Nc))
        {
            // ...Das Selbe wie oben, wegen Platzgründen weggelassen
        }

        if (TestIntersionCylinder(cyl3,OldPos[i],uveloc,rt,norm,Nc))
        {
            // ...Das Selbe wie oben, wegen Platzgründen weggelassen
        }

    }

    // Nachdem alle Bälle auf Kollision mit Ebenen / Zylindern überprüft wurde 
    // und ersetze wenn Kollisionszeit kleiner ist
    if (FindBallCol(Pos2,BallTime,RestTime,BallColNr1,BallColNr2))
    {
        if (sounds)
            PlaySound("Explode.wav",NULL,SND_FILENAME|SND_ASYNC);

        if ( (lamda==10000) || (lamda>BallTime) )
        {
            RestTime=RestTime-BallTime;
            TVector pb1,pb2,xaxis,U1x,U1y,U2x,U2y,V1x,V1y,V2x,V2y;
            double a,b;
            .
            .
            Code aus Platzgründen ausgelassen
            Der Code ist im Abschnitt physikalisch basierte Modellierung
            beschrieben, unter Sphere - Sphere Kollision
            .
            .
            //aktuallisiere Explosion Array und füge Explosion ein
            for(j=0;j// Ende der Tests
    // Wenn Kollision aufgetreten ist lasse die Zeit um den korrekten Zeitschritt weiterlaufen
    // und berechne Reaktion für den kollidierenden Ball
    if (lamda!=10000)
    {
        RestTime-=lamda;
        for (j=0;j<NrOfBalls;j++)
        ArrayPos[j]=OldPos[j]+ArrayVel[j]*lamda;
        rt2=ArrayVel[BallNr].mag();
        ArrayVel[BallNr].unit();
        ArrayVel[BallNr]=TVector::unit( (normal*(2*normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );
        ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;

        // aktualisiere Explosion Array und füge Explosion ein
        for(j=0;j// Ende der While Schleife

Die globalen Variablen die hautpsächlich wichtig sind, sind:

Repräsentiert die Richtung und Position der Kamera. Die Kamera wird durch die LooAt Funktion bewegt. Wie Sie wahrscheinlich festgestellt haben, wenn nicht gerade im Verfolgungs-Modus (welchen ich später erkläre), rotiert die gesamte Szene, die Gradzahl der Roatation wird durch camera_rotation gehändelt. TVector dir
TVector pos(0,-50,1000);
float camera_rotation=0;
Repräsentiert die Beschleunigung die auf die bewegenden Bälle angewendet wird. Wird als Gravitation in der Applikation genutzt. TVector accel(0,-0.05,0);
Arrays die die neuen und alten Ball Positionen und den Geschwindigkeitsvektor eines jeden Balls enthalten. Die Anzahl der Bälle ist hardcodiert auf 10. TVector ArrayVel[10];
TVector ArrayPos[10];
TVector OldPos[10];
int NrOfBalls=3;
Die Zeitschritte die wir benutzen. double Time=0.6;
Wenn die Kamerasicht geändert wird und einem Ball (dem Ball mit dem Index 0 in dem Array) gefolgt wird, benutzen wir dessen Positions und Geschwindigkeitsvektor um die Kamera exakt hinter den Ball zu platzieren und schauen entlängs des Geschwindigkeitsvektors des Balls. int hook_toball1=0;
Selbserklärende Strukturen die Daten über Explosionen, Ebenen und Zylinder enthelten. struct Plane
struct Cylinder
struct Explosion
Die Explosionen sind in einem Array fester Länge gespeichert. Explosion ExplosionArray[20];


Die Funktionen des hauptsächlichen Interesses sind:

Führt Schnittpunkt Test mit Primitiven durch int TestIntersionPlane(....);
int TestIntersionCylinder(...);
Lädt Texturen aus bmp Dateien void LoadGLTextures();
Hier der Rendering Code. Rendert die Bälle, Wände, Säulen und Explosionen void DrawGLScene();
Führt die Haupt-Simulations-Logik aus void idle();
Initialisiere den OpenGL Status void InitGL();
Finde heraus, ob irgendwelche Bälle miteinander kollidieren während des aktuellen Zeitschrittes int FindBallCol(...);


Für mehr Informationen schauen Sie in den Source Code. Ich habe versucht so gut wie möglich zu kommentieren. Wenn die Kollisionserkennung und die Reaktions-Logik verstanden ist, sollte der Source sehr klar sein. Zögern Sie nicht, mich wegen mehr Informationen zu kontaktieren.

Wie ich bereits am Anfang des Tutorials gesagt habe, ist das Thema Kollisionserkennung ein sehr schwieriges Thema, um es mit einem Tutorial abzudecken. Sie werden in diesem Tutorial viel lernen, genug um einige wirklich beeindruckende Demos von selbst zu schreiben, aber es gibt noch viel mehr zu lernen, als in diesem Tutorial. Nun, da Sie die Grundlagen können, sollten alle anderen Sourcen für Kollisionserkennung und physikalisch basierte Modellierung da draußen, wesentlich einfacher zu verstehen sein. Das gesagt, schicke ich Sie auf den und Weg und wünsche ihnen fröhliche Kollisionen!!!

Einige Informationen über Dimitrios Christopoulos: Er arbeitet zur Zeit als ein Virtual Reality software Engineer bei der Foundation of the Hellenic World in Athen/Griechenland (www.fhw.gr). Obwohl in Deutschland geboren, studierte er in Griechenland an der Universität von Patras als B.Sc. in Computer Engineering und Informatics. Er hat ebenso ein MSc degree (honours) von der Universität Hull (UK) in Computer Graphics und Virtual Environments. Seine erste Schritte in der Spieleprogrammierung hat er mit Basic auf einem Commodore 64 getan und wechselte zu C/C++/Assembler auf der PC Plattform, nachdem er sein Studium began. Während der letzten Jahre ist OpenGL, das Grafik API seiner Wahl geworden. Für mehr Informationen besuchen Sie seine Seite: http://members.xoom.com/D_Christop.

Dimitrios Christopoulos

Jeff Molofee (NeHe)

* DOWNLOAD Visual C++ Code für diese Lektion.

* DOWNLOAD Borland C++ Builder 6 Code für diese Lektion. ( Conversion by Christian Kindahl )
* DOWNLOAD Code Warrior 5.3 Code für diese Lektion. ( Conversion by Scott Lupton )
* DOWNLOAD Delphi Code für diese Lektion. ( Conversion by Michal Tucek )
* DOWNLOAD Dev C++ Code für diese Lektion. ( Conversion by Conrado )
* DOWNLOAD JoGL Code für diese Lektion. ( Conversion by Abdul Bezrati )
* DOWNLOAD Linux/GLX Code für diese Lektion. ( Conversion by Rodolphe Suescun )
* DOWNLOAD Mac OS X/Cocoa Code für diese Lektion. ( Conversion by Bryan Blackburn )
* DOWNLOAD Visual Studio .NET Code für diese Lektion. ( Conversion by Grant James )


Deutsche Übersetzung: Joachim Rohde
Der original Text ist hier zu finden.
Die original OpenGL Tutorials stammen von NeHe's Seite.