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.
2.Modelowanie oparte na fizyce
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.
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.
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
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.
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:
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ć.
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
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ą.
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:
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.
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.
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.
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:
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):
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.
Ważne zmienne globlane
Główne funkcje
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 .