Lekcja 30. Wykrywanie kolizji
Autor: Łukasz 'lmmilewski' Milewski
Oryginał: Collision Detection (Dimitrios Christopoulos)
Źródła: http://nehe.gamedev.net/data/lessons/vc/lesson30.zip

Kod źródłowy, na którym jest oparty ten tutorial pochodzi z mojej pracy konkursowej (OGLchallenge.dhs.org) na temat kolizji (zająłem wtedy pierwsze miejsce ;)). Moja praca nazywała się "Magiczny pokój". Demonstrowała wykrywanie kolizji oraz modelowanie i efekty oparte na fizyce.

Wykrywanie kolizji

To trudny temat. Szczerze mówiąc nie widziałem jeszcze łatwego rozwiązania. W każdej aplikacji inaczej znajduje się i testuje kolizje. Oczywiście istnieją algorytmy typu "brute force". Działają zawsze i z każdym typem obiektu. Niestety są bardzo kosztowne.

My zajmiemy się algorytmami, które są bardzo szybkie, łatwe do zrozumienia i całkiem elastyczne. Zwrócimy też uwagę na to co trzeba zrobić, gdy już kolizja zostanie wykryta oraz jak poruszać obiekty zgodnie z prawami fizyki. Czyli całkiem długa droga przed nami. Popatrzmy na skrót tego, czego się nauczymy.

Zawartość

1. Wykrywanie kolizji

2.Modelowanie oparte na fizyce

3.Efekty specjalne

4.Wyjaśnienie kodu

Lesson30.cpp : Główny kod dla tej lekcji

Image.cpp Image.h : Kod obsługujący bitmapy

Tmatrix.cpp Tmatrix.h : Klasy obsługujące obroty

Tray.cpp Tray.h : Klasy obsługujące operacje na promieniach

Tvector.cpp Tvector.h : Klasy obsługujące operacje na wektorach

Dużo poręcznego kodu! Klasy Vector (wektor), Ray (promień) oraz Matrix (macierz) są bardzo przydatne. Korzystam z nich w moich projektach.

1) Wykrywanie kolizji

Do wykrywania kolizji będziemy używali śledzenia promieni. Najpierw definiujemy promień.

Promień będziemy reprezentować jako wektor, który opisuje początek promienia oraz wektor (zazwyczaj unormowany) opisujący kierunek promienia. W gruncie rzeczy promień startuje w początku (opisanym przez pierwszy wektor) i leci w kierunku wskazanym przez drugi wektor. Stąd otrzymujemy równanie promienia.

PunktNaPromieniu = PoczątekPromienia + t * KierunekPromienia

gdzie t jest wartością typu float. Przyjmuje wartości z [0,nieskończoność).

Jeżeli podstawimy t=0 to otrzymamy punkt początkowy. PunktNaPromieniu, PoczątekPromienia oraz KierunekPromienia są wektorami 3D. Opisujemy je trzema liczbami(x,y,z). Możemy teraz, korzystając z równania, znaleźć przecięcia z płaszczyzną lub walcem.

Wykrywanie przecięcia promienia z płaszczyzną.

Wykorzystując reprezentację wektorową możemy następująco opisać płaszczyznę:

Xn dot X = d

Xn, X to wektory, d jest liczbą typu float.

Xn to normalna.

X to punkt na płaszczyźnie.

d to liczba będąca przesunięciem, wzdłuż normalnej, płaszczyzny od środka układ współrzędnych.

Płaszczyzna dzieli przestrzeń na dwie części. Możemy ją więc reprezentować przez punkt oraz normalną. Na przykład biorąc punkt (0,0,0) i normalną (0,1,0) definiujemy płaszczyznę zawierającą oś OX i OZ. Zatem punkt i normalna wystarczają aby obliczyć wektorową reprezentację płaszczyzny.

Wystarczy podstawić Xn = normalna, X = punkt. Parametr d można łatwo wyliczyć jako iloczyn skalarny Xn i X.

(Zauważ, że nasza reprezentacja jest równoważna, dobrze znanej, Ax+By+Cz+D=0. Wystarczy położyć Xn = (A,B,C) oraz d=-D).

Zatem na razie mamy następujące równania:

PunktNaPromieniu = PoczątekPromienia + t * KierunekPromienia

Xn dot X = d

Jeżeli promień przecina płaszczyznę, to musi istnieć taki punkt na promieniu, który spełnia równanie płaszczyzny.

Xn dot PunktNaPromieniu = d

Xn dot PoczątekPromienia + t * (Xn dot KierunekPromienia) = d

Rozwiązując równanie względem t

t = (d - Xn dot PoczątekPromienia) / (Xn dot KierunekPromienia)

Możemy teraz podstawić pod d

t = (Xn dot PunktNaPŁASZCZYŹNIE - Xn dot PoczątekPromienia) / (Xn dot KierunekPromienia)

podsumowując

t = (Xn dot (PunktNaPŁASZCZYŹNIE - PoczątekPromienia) / (Xn dot KierunekPromienia)

t opisuje odległość początku promienia od płaszczyzny wzdłuż kierunku promienia. Aby wyznaczyć punkt przecięcia (kolizji promienia z płaszczyzną) wystarczy podstawić t do równania promienia. Jest kilka przypadków szczególnych do rozpatrzenia. Jeżeli Xn dot KierunekPromienia = 0 to wektory są prostopadłe (promień biegnie równolegle do płaszczyzny). Zatem nie będzie kolizji. Jeżeli t jest ujemne to przecięcie jest przed punktem startu promienia. Zatem również nie ma kolizji.

int TestIntersionPlane(const Plane& plane,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal)
{
    double DotProduct=direction.dot(plane._Normal);         // Iloczyn skalarny normalnej płaszczyzny z kierunkiem promienia
    double l2;
        // Czy promień jest równoległy do płaszczyzny
    if ((DotProduct<ZERO)&&(DotProduct>-ZERO))
        return 0;
    l2=(plane._Normal.dot(plane._Position-position))/DotProduct;         // Znajdź odległość od punktu kolizji
    if (l2<-ZERO)         // Sprawdź czy kolizja nie jest przed punktem startu
        return 0;
    pNormal=plane._Normal;
    lamda=l2;
    return 1;
}

Ten kod wylicza punkt przecięcia. Zwraca 1 jeżeli jest przecięcie i 0 w przeciwnym wypadku. Parametrami są płaszczyzna, początek i kierunek promienia, double (lembda) gdzie zostanie zapisana odległość od kolizji (o ile była) oraz normala w punkcie kolizji.

Przecięcie promienia z walcem.

Obliczanie przecięcia między nieskończonym walcem i promieniem jest znacznie bardziej skomplikowane. Dlatego nie będę go opisywał. Trzeba mieć spory bagaż wiedzy matematycznej, żeby zrozumieć ten typ przecięć. Nie chcę wchodzić w szczegóły (w końcu to nie są zajęcia z geometrii). Jeżeli ktoś jest zainteresowany teorią stojącą za kodem obliczającym przecięcia, to odpowiednie informacje znajdzie w książce Graphics Gems II. Walec opisujemy jako wektor osi (początek i kierunek) oraz promień podstawy. Odpowiednia funkcja to

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

Zwraca 1 gdy jest przecięcie. 0 w przeciwnym wypadku.

Parametry to walec (omówiony dalej w tym tutorialu), początek i kierunek promienia. Funkcja zwraca odległość od przecięcia i normalną w punkcie przecięcia.

Kolizja sfera - sfera

Sferę reprezentujemy jako jej środek oraz promień. Sprawdzenie czy zaszła kolizja między dwoma sferami jest proste. Wystarczy policzyć odległość między ich środkami (metoda dist klasy TVector) i sprawdzić czy jest mniejsza od sumy promieni sfer.

Problemem jest sprawdzenie czy dwie PORUSZAJĄCE się sfery kolidują ze sobą. Poniżej jest przykład, na którym dwie sfery poruszają się z jednego punktu do drugiego. Ich ścieżki się przecinają, ale to nie wystarcza aby stwierdzić, że zajdzie kolizja (mogą przecież się minąć - wystarczy, że będą poruszały się z różnymi prędkościami). Nie można również wyznaczyć punktu przecięcia.

figure 1

W poprzedniej metodzie rozwiązywaliśmy równanie, aby obliczyć punkt przecięcia. Gdy używa się skomplikowanych kształtów lub gdy odpowiednie równania nie istnieją albo nie mogą być rozwiązane należy skorzystać z innych metod. Znamy punkty startowe i końcowe, chwilę czasu, prędkość (kierunek i szybkość) sfery oraz sposób na obliczenie przecięć dla sfer, które się nie poruszają. Aby obliczyć punkt przecięcia dla poruszających się sfer trzeba podzielić czas na małe kawałki (chwile). Następnie poruszamy sfery zgodnie z podziałem czasu, wykorzystując prędkość sfer. Jednocześnie sprawdzamy kolizje. Jeżeli kolizja zostanie znaleziona w którymkolwiek momencie czasu (tzn. sfery najdą na siebie) to bierzemy poprzedni moment czasu jako czas kolizji (można by interpolować między punktami czasu aby znaleźć dokładny czas przecięcia, ale zazwyczaj to nie jest potrzebne).

Im mniejsze przedziały czasu, tym nasza metoda jest dokładniejsza. Dla przykładu powiedzmy, że cały przedział czasu jest długości 1 i dzielmy go na 3 części. Sprawdzamy zatem kolizje w punktach 0, 0.33, 0.66, 1. Łatwizna!!!

Kod który to robi:

/***************************************************************************/
/*** Sprawdza czy któraś z aktualnych kul ***/
/*** przecina się z inną ***/
/*** Zwraca indeks przecinających się kul, punkt oraz czas przecięcia ***/
/***************************************************************************/
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;
for (int i=0;i<NrOfBalls-1;i++)         // Sprawdzaj każdą z kul z innymi w 150 możliwych stanach
{
    for (int j=i+1;j<NrOfBalls;j++)
    {
     RelativeV=ArrayVel[i]-ArrayVel[j];         // Znajdź odległość
     rays=TRay(OldPos[i],TVector::unit(RelativeV));
     MyTime=0.0;
        // Jeżeli odlełość między środkami jest większa niż 2 * promień to jest przecięcie
     if ( (rays.dist(OldPos[j])) > 40) continue;
     while (MyTime<Time2)         // Pętla znajdująca dokładny punkt przecięcia
     {
        MyTime+=Add;
        posi=OldPos[i]+RelativeV*MyTime;
        if (posi.dist(OldPos[j])<=40)
        {
         point=posi;
         if (Timedummy>(MyTime-Add)) Timedummy=MyTime-Add;
         BallNr1=i;
         BallNr2=j;
         break;
        }
     }
    }
}
if (Timedummy!=10000)
{
    TimePoint=Timedummy;
    return 1;
}
return 0;
}

Jak skorzystać z tego, czego się właśnie nauczyliśmy?

Skoro potrafimy ustalić punkt przecięcia promienia z walcem/sferą, to możemy znaleźć punkt kolizji między sferą i tymi prymitywami. To, co umiemy zrobić do tej pory to ustalenie dokładnego punktu kolizji między cząsteczką i płaszczyzną/walcem. Pozycja początkowa promienia to pozycja cząsteczki, a kierunek promienia to jej prędkość (szybkość i kierunek). Przeniesienie tej wiedzy na sferę jest proste. Popatrz na rysunek 2a aby zobaczyć jak to zrobić.

figure 2

Każda sfera ma promień. Przyjmijmy, że środek sfery to nasza cząsteczka. Każdy walec, z którym chcemy liczyć kolizję, powiększamy wzdłuż promienia (zwiększamy promień). Każdą płaszczyznę lekko przesuwamy w kierunku cząsteczki. Na rysunku 2a początkowe obiekty są narysowane linią ciągłą. Powiększone lub przesunięte linią przerywaną. Sztuczka polega na tym, aby kolizje liczyć z tymi przesuniętymi/powiększonymi obiektami. Dzięki temu sfera nie będzie nachodziła na obiekty podczas kolizji. Na rysunku 2b jest sytuacja, gdy nie przesuniemy płaszczyzny. Kulka nachodzi na płaszczyznę. Jest tak dlatego, że testujemy kolizję środka kulki z płaszczyzną.

Ustaliliśmy gdzie jest kolizja. Teraz musimy sprawdzić, czy kolizja ma miejsce w aktualnej chwili czasu. Chwila czasu to czas, gdy ruszamy sferę z jej aktualnej pozycji uwzględniając jej prędkość. Sprawdzamy nieskończone promienie. Istnieje więc ryzyko, że punkt kolizji jest dalej niż następne położenie sfery. Należy zatem obliczyć nową pozycję sfery i zbadać czy odległość od kolizji nie jest większa niż odległość od punktu początkowego do końcowego. Z naszej procedury wykrywania kolizji otrzymujemy przy okazji odległość od punktu początkowego do punktu kolizji. Jeżeli ta odległość jest mniejsza niż odległość pomiędzy początkiem i końcem to jest kolizja. Aby znaleźć dokładny czas rozwiązujemy proste równanie. Odległość między początkiem i końcem to dst, odległość między początkiem i punktem kolizji to dsc, chwila czasu to t. Czas kiedy ma miejsce kolizja (tc) to:

tc = dsc * t / dst

Wykonujemy te obliczenia gdy przecięcie jest ustalone. Zwrócony czas to ułamek czasu trwania ruchu. Zatem jeżeli czas trwania to 1 sekunda i znaleźliśmy przecięcie dokładnie w połowie drogi, to obliczony czas kolizji wynosi 0.5 sekundy. Należy to interpretować jako: "0.5 sekundy po starcie jest przecięcie". Punkt przecięcia może być łatwo obliczony poprzez pomnożenie tc przez prędkość i dodanie punktu startowego.

punkt kolizji = start + prędkość * tc

2) Modelowanie oparte na fizyce

Reakcja na kolizję.

Określenie sposobu reakcji na uderzenie statycznego obiektu takiego jak płaszczyzna czy walec jest równie istotne jak sprawdzanie kolizji. Korzystając z zaprezentowanych metod możemy znaleźć dokładny punkt kolizji, normalną w tym punkcie w tym punkcie oraz czas kolizji.

Aby określić sposób reakcji na kolizję trzeba zastosować prawa fizyki. Gdy obiekt uderza w jakąś powierzchnię, jego kierunek się zmienia - np. się odbija. Kąt między wektorem odbicia i normalną w punkcie kolizji jest równy kątowi między wektorem padania i tą normalną. Na rysunku 3 widać kolizję ze sferą.

figure 3

R to wektor nowego kierunku.

I to wektor kierunku przed kolizją.

N to normalna w punkcie kolizji.

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

przy założeniu, że I oraz N są wektorami jednostkowymi. Wektor prędkości w naszych przykładach reprezentuje szybkość i kierunek. Zatem nie można podstawić go za I w równaniu. Trzeba zapamiętać długość wektora prędkości i go unormować. Po podstawieniu do równania uzyskamy wektor R. Pokazuje on kierunek odbitego promienia, ale ma długość 1. Zatem nie wskazuje szybkości. Wektor R przemnożony przez zapamiętaną długość wektora I można wykorzystać jako nowy wektor prędkości.

W przykładzie ten sposób jest wykorzystany do reagowania na kolizję z płaszczyzną i walcem. Ta metoda zadziała dla dowolnego kształtu powierzchni. Zawszy gdy można znaleźć punkt kolizji i normalną w tym punkcie reakcja na kolizję jest taka sama. A oto kawałek kodu:

rt2=ArrayVel[BallNr].mag();         // Znajdź długość wektora prętkości
ArrayVel[BallNr].unit();         // Normalizacja tego wektora
        // oblicz wektor odbicia
ArrayVel[BallNr]=TVector::unit( (normal*(2*normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );
ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;         // Pomnóż przez długość

Gdy sfera uderza w sferę

Obliczenie prawidłowej reakcji na zderzenie się dwóch kul jest znacznie bardziej skomplikowane. Trzeba rozwiązać bardzo skomplikowane równania, więc pominę dowód poniższych wzorów. Musisz mi zaufać ;-) Podczas kolizji dwóch kul mamy sytuację pokazaną na rysunku 4.

figure 4

U1 i U2 to wektory prędkości dwóch sfer w momencie zderzenia. Na rysunku jest także wektor osi (X_Axis), który łączy środki dwóch sfer. U1x oraz U2x to rzuty wektorów prędkości U1 i U2 na wektor osi (X_Axis).

U1y i U2y to rzuty wektorów U1 i U2 na oś prostopadłą do X_Axis. Aby znaleźć te wektory wystarczy zwykły iloczyn skalarny. M1, M2 to masy sfer. V1, V2 to nowe prędkości (po zderzeniu). V1x,V1y,V2x,V2y odpowiednie rzuty wektorów V1,V2.

Bardziej szczegółowo:

a) Znajdź wektor osi X (X_Axis)

X_Axis = (środek2 - środek1)

Unormuj X_Axis

b) Znajdź odpowiednie rzuty

U1x = X_Axis * (X_Axis dot U1)

U1y = U1 - U1x

U2x = -X_Axis * (-X_Axis dot U2)

U2y = U2 - U2x

c) Znajdź nowe prędkości

(U1x * M1) + (U2x * M2) - (U1x - U2x) * M2

V1x = ------------------------------------------

M1 + M2

(U1x * M1) + (U2x * M2) - (U2x - U1x) * M1

V2x = ------------------------------------------

M1 + M2

W naszym programie przyjmujemy M1=M2=1, więc równania będą prostsze.

TVector pb1,pb2,xaxis,U1x,U1y,U2x,U2y,V1x,V1y,V2x,V2y;
double a,b;
pb1 = OldPos[BallColNr1]+ArrayVel[BallColNr1]*BallTime;         // Znajdź położenie pierwszej kuli
pb2 = OldPos[BallColNr2]+ArrayVel[BallColNr2]*BallTime;         // Znajdź położenie drugiej kuli
xaxis = (pb2-pb1).unit();         // Znajdź wektor osi X (X_Axis)
a = xaxis.dot(ArrayVel[BallColNr1]);         // Znajdź rzut
U1x = xaxis*a;         // Znajdź rzut wektora prędkośći
U1y = ArrayVel[BallColNr1]-U1x;
xaxis = (pb1-pb2).unit();         // Zrób to samo co wyżej
b = xaxis.dot(ArrayVel[BallColNr2]);         // Aby znaleźć rzut
U2x = xaxis*b;         // wektorów dla drugiej kuli
U2y = ArrayVel[BallColNr2]-U2x;
V1x = (U1x+U2x-(U1x-U2x))*0.5;         // Znajdź nowe prędkości
V2x = (U1x+U2x-(U2x-U1x))*0.5;
V1y = U1y;
V2y = U2y;
for (j=0;j<NrOfBalls;j++)         // Uaktualnij położenia kul
ArrayPos[j]=OldPos[j]+ArrayVel[j]*BallTime;
ArrayVel[BallColNr1] = V1x+V1y;         // Ustaw nowe wektory prędkości
ArrayVel[BallColNr2] = V2x+V2y;         // Dla kul

Poruszanie się w polu grawitacyjnym (z użyciem równań Eulera)

Aby realistycznie symulować ruch z kolizjami, wykrywanie punktu kolizji i obliczanie reakcji nie wystarcza. Poruszanie ciał pod wpływem siły grawitacji także powinno być symulowane.

Najbardziej powszechną metodą aby to zrobić jest stosowanie równań Eulera. Wszystkie obliczenia będą wykonywane w oparciu małe zmiany czasu. To oznacza, że w każdej chwili czasu obliczamy nowe wartości prędkości i położenia oraz wykrywamy kolizje i reakcje na nie. Dla przykładu możemy przesuwać symulację o dwie sekundy w każdej klatce. Korzystając z równań Eulera nowe prędkości i położenia obliczamy według wzorów:

NowaPrędkość = StaraPrędkość + Przyspieszenie * DługośćPrzedziałuCzasu

NowePołożenie = StarePołożenie + NowaPrędkość * DługośćPrzedziałuCzasu

Następnie obiekty są poruszane i sprawdzana jest kolizja. Przyspieszenie obiektu to suma sił, działających na niego, podzielona przez jego masę. Zgodnie z równaniem:

Siła = masa * przyspieszenie

Dużo fizycznych wzorków ;-)

W naszym przykładzie na obiekt działa jedynie siła grawitacji, którą reprezentujemy przez wektor przyspieszenia. W naszym przypadku jest to "coś" ujemnego w kierunku Y, np. (0,-0.5,0). Oznacza to, że na początku każdej chwili czasu obliczamy nowy wektor prędkości każdej ze sfer oraz poruszamy je testując kolizje. Jeżeli wystąpiła kolizja podczas danej chwili czasu to przesuwamy obiekt na miejsce kolizji, obliczamy wektor odbicia (nowy wektor prędkości) i poruszamy obiekt przez pozostały czas, ponownie testując kolizje. Ta operacja jest powtarzana aż do końca chwili czasu.

Jeżeli jest wiele obiektów ruchomych dla każdego obliczamy kolizję z każdym obiektem statycznym. Zwracamy tę najbliższą. Następnie podobnie zwracamy najbliższą kolizję z obiektami ruchomymi. Z otrzymanych dwóch punktów kolizji zwracamy ostatecznie tę bliższą. Symulacja jest aktualizowana do tego miejsca. (np. jeżeli najbliższa kolizja będzie za 0.5s, to poruszamy każdy z obiektów przez 0.5s). Obliczamy wektor odbicia dla kolidujących obiektów i pętla jest uruchamiana ponownie na pozostały czas.

3) Efekty specjalne

Eksplozje

Za każdym razem gdy zachodzi kolizja odpalana jest eksplozja w punkcie kolizji. Dobrym sposobem modelowania wybuchów jest mieszanie kolorów między dwoma wielokątami, które są wzajemnie prostopadłe i mają środek przecięcia w punkcie kolizji. Wielokąty są skalowane i z czasem znikają. Znikanie uzyskujemy płynnie zmniejszając wartości kanału alfa wierzchołków z 1 do 0. Wiele obiektów z mieszaniem kolorów może spowodować kłopoty gdy będą na siebie nachodziły (jest to opisane w Red Book w rozdziale o przezroczystości i mieszaniu kolorów). Aby tego uniknąć należy posortować obiekty po odległości od oka - od najdalszego do najbliższego. Również wyłączenie zapisu (nie odczytu) do bufora głębi pomoże (również jest to opisane w Red Book). Zauważ, że ograniczamy ilość wybuchów do maksymalnie 20 na klatkę. Jeżeli wystąpią dodatkowe eksplozje, a bufor jest pełen to nowy wybuch jest porzucany i nie zostanie wyświetlony. Kod który odpowiada za wyświetlanie eksplozji:

glEnable(GL_BLEND);         // Włącz mieszanie kolorów
glDepthMask(GL_FALSE);         // Wyłącz zapis do bufora głębi
glBindTexture(GL_TEXTURE_2D, texture[1]);         // Załaduj teksturę
for(i=0; i<20; i++)         // Uaktualnij i wyświetl teksturę
{
    if(ExplosionArray[i]._Alpha>=0)
    {
        glPushMatrix();
        ExplosionArray[i]._Alpha-=0.01f;         // Uaktualnij wartość składowej alfa
        ExplosionArray[i]._Scale+=0.03f;         // Uaktualnij skalowanie
        
        // Przypisz wierzchołkom kolor żółty z kanałem alfa
        glColor4f(1,1,0,ExplosionArray[i]._Alpha);
        glScalef(ExplosionArray[i]._Scale,ExplosionArray[i]._Scale,ExplosionArray[i]._Scale);
        
        // Translacja na pozycje biorąc pod uwagę skalę
        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);         // Wywołaj listę wyświetlania
        glPopMatrix();
    }
}

Dźwięk

Do dźwięku jest użyta funkcja PlaySound() (z systemu operacyjnego Windows). To jest szybki sposób na bezproblemowe odtwarzanie plików wav.

4) Wyjaśnienie kodu

Gratulacje...

Jeżeli nadal jesteś ze mną to oznacza, że przetrwałeś część teoretyczną ;-) Zanim zaczniesz bawić się demem muszę jeszcze objaśnić parę rzeczy. Główny części symulacji są następujące (w pseudokodzie):

While (Timestep!=0)
{
    For each ball
    {
        compute nearest collision with planes;
        compute nearest collision with cylinders;
        Save and replace if it the nearest intersection;
        in time computed until now;
    }
    Check for collision among moving balls;
    Save and replace if it the nearest intersection;
    in time computed until now;
    If (Collision occurred)
    {
        Move All Balls for time equal to collision time;
        (We already have computed the point, normal and collision time.)
        Compute Response;
        Timestep-=CollisonTime;
    }
    else
        Move All Balls for time equal to Timestep
}

Właściwy kod, który implementuje to co opisuje powyższy pseudokod jest znacznie trudniejszy do czytania, ale jest dokładną implementacją powyższego pseudokodu.

        // While Time Step Not Over
while (RestTime>ZERO)
{
    lamda=10000;         // Initialize To Very Large Value
        // For All The Balls Find Closest Intersection Between Balls And Planes / Cylinders
    for (int i=0;i<NrOfBalls;i++)
    {
        // Compute New Position And Distance
        OldPos[i]=ArrayPos[i];
        TVector::unit(ArrayVel[i],uveloc);
        ArrayPos[i]=ArrayPos[i]+ArrayVel[i]*RestTime;
        rt2=OldPos[i].dist(ArrayPos[i]);
        // Test If Collision Occured Between Ball And All 5 Planes
        if (TestIntersionPlane(pl1,OldPos[i],uveloc,rt,norm))
        {
        // Find Intersection Time
            rt4=rt*RestTime/rt2;
        // If Smaller Than The One Already Stored Replace In Timestep
            if (rt4<=lamda)
            {
        // If Intersection Time In Current Time Step
                if (rt4<=RestTime+ZERO)
                    if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
                    {
                        normal=norm;
                        point=OldPos[i]+uveloc*rt;
                        lamda=rt4;
                        BallNr=i;
                    }
            }
        }
        if (TestIntersionPlane(pl2,OldPos[i],uveloc,rt,norm))
        {
        // ...The Same As Above Omitted For Space Reasons
        }
        if (TestIntersionPlane(pl3,OldPos[i],uveloc,rt,norm))
        {
        // ...The Same As Above Omitted For Space Reasons
        }
        if (TestIntersionPlane(pl4,OldPos[i],uveloc,rt,norm))
        {
        // ...The Same As Above Omitted For Space Reasons
        }
        if (TestIntersionPlane(pl5,OldPos[i],uveloc,rt,norm))
        {
        // ...The Same As Above Omitted For Space Reasons
        }
        // Now Test Intersection With The 3 Cylinders
        if (TestIntersionCylinder(cyl1,OldPos[i],uveloc,rt,norm,Nc))
        {
            rt4=rt*RestTime/rt2;
            if (rt4<=lamda)
            {
                if (rt4<=RestTime+ZERO)
                    if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
                    {
                        normal=norm;
                        point=Nc;
                        lamda=rt4;
                        BallNr=i;
                    }
            }
        }
        if (TestIntersionCylinder(cyl2,OldPos[i],uveloc,rt,norm,Nc))
        {
        // ...The Same As Above Omitted For Space Reasons
        }
        if (TestIntersionCylinder(cyl3,OldPos[i],uveloc,rt,norm,Nc))
        {
        // ...The Same As Above Omitted For Space Reasons
        }
    }
        // After All Balls Were Tested With Planes / Cylinders Test For Collision
        // Between Them And Replace If Collision Time Smaller
    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 Omitted For Space Reasons
            The Code Is Described In The Physically Based Modeling
            Section Under Sphere To Sphere Collision
            .
            .
        //Update Explosion Array And Insert Explosion
            for(j=0;j<20;j++)
            {
                if (ExplosionArray[j]._Alpha<=0)
                {
                    ExplosionArray[j]._Alpha=1;
                    ExplosionArray[j]._Position=ArrayPos[BallColNr1];
                    ExplosionArray[j]._Scale=1;
                    break;
                }
            }
            continue;
        }
    }
        // End Of Tests
        // If Collision Occured Move Simulation For The Correct Timestep
        // And Compute Response For The Colliding 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;
        // Update Explosion Array And Insert Explosion
        for(j=0;j<20;j++)
        {
            if (ExplosionArray[j]._Alpha<=0)
            {
                ExplosionArray[j]._Alpha=1;
                ExplosionArray[j]._Position=point;
                ExplosionArray[j]._Scale=1;
                break;
            }
        }
    }
    else RestTime=0;
}         // End Of While Loop

Ważne zmienne globlane

        // Reprezentuje kierunek i położenie kamery. Kamera jest poruszana z użyciem funkcji LookAt. Jak zapewne zauważysz scena obraca się. Kąt obrotu jest pamiętany w camera_rotation.
TVector dir
TVector pos(0,-50,1000);
float camera_rotation=0;
        // Reprezentuje przyspieszenie poruszających się piłek. Ma symulować grawitację.
TVector accel(0,-0.05,0);
        // Tablice które trzymają nowe i stare pozycje piłek oraz wektor prędkości każdej z piłek. Liczba piłek jest zaszyta w kodzie. Jest to 10.
TVector ArrayVel[10];
TVector ArrayPos[10];
TVector OldPos[10];
int NrOfBalls = 3;
        // Czas trwania jednego przedziału czasowego.
double Time = 0.6;
        // Jeżeli 1 to widok kamery się zmienia i (piłka z indeksem 0 w tablicy) jest śledzona. Aby śledzić kamerą piłkę użyliśmy jej wektora pozycji i wektora prędkości aby ustawić kamerę dokładnie za piłką i skierować ją tak aby patrzyła wzdłuż wektora prędkości piłki.
int hook_toball1=0;
        // Struktury opisujące płaszczyznę, walec oraz wybuch.
struct Plane;
struct Cylinder;
struct Explosion;
        // Wybuchy są pamiętane w tablicy o ustalonej długości.
Explosion ExplosionArray[20];

Główne funkcje

        // Testują kolizje z podstawowymi kształtami geometrycznymi.
int TestIntersionPlane(....);
int TestIntersionCylinder(...);
        // Wczytuje tekstury z pliku bmp
void LoadGLTextures();
        // Kod renderujący piłki, ściany, kolumny i wybuchy.
void DrawGLScene();
        // Sterowanie symulacja (logika).
void idle();
        // Inicjalizuje OpenGL
void InitGL();
        // Sprawdza czy jakieś piłki kolidują w aktualnym przedziale czasowym.
int FindBallCol(...);

Po więcej informacji zajrzyj do kodu źródłowego. Starałem się komentować go najlepiej jak umiałem. Jeżeli zrozumiesz kod wykrywania kolizji i logikę reakcji to kod źródłowy stanie się bardzo prosty. Po więcej informacji nie wahaj się ze mną kontaktować.

Jak już stwierdziłem na początku temat wykrywania kolizji jest bardzo trudno wyczerpać w jednym tutorialu. Dużo się nauczyłeś z tego tutoriala. Wystarczająco, aby stworzyć własne, dobrze wyglądające, demka. Temat jest jednak znacznie obszerniejszy. Teraz gdy znasz już podstawy wykrywania kolizji i modelowania opartego na fizyce reszta powinna być znacznie prostsza do zrozumienia. Powiedziawszy to wysyłam Cię w Twoją własną drogę i życzę wesołych kolizji!!!

Some information about Dimitrios Christopoulos: He is currently working as a Virtual Reality software engineer at the Foundation of the Hellenic World in Athens/Greece ( http://www.fhw.gr ). Although Born in Germany, he studied in Greece at the University of Patras for a B.Sc. in Computer Engineering and Informatics. He holds also a MSc degree (honours) from the University of Hull (UK) in Computer Graphics and Virtual Environments. He did his first steps in game programming using Basic on an Commodore 64, and switched to C/C++/Assembly on the PC platform after the start of his studium. During the last few years OpenGL has become his graphics API of choice. For more information visit his site at: http://members.xoom.com/D_Christop .