|
Metody wykrywania kolizji w grach 3D Autor: Mirosław Kozioł |
|
Pisząc silnik do gier 3D każdy prędzej czy później będzie zmuszony do implementacji kolizji. Poniższy opis metod wykrywania kolizji powinien pomóc w wyborze sposobu implementacji kolizji.
1. Metoda wykrycia kolizji dla zbiorów małych wielokątów: Gdy scena składa się z małych wielokątów wystarczy do kolizji sprawdzić czy któryś z wierzchołków wielokątów zawiera się w bryle obserwatora. Sprowadza się to do sprawdzenia czy:
-x bryły < x < x bryły -y bryły < y < y bryły -z bryły < z < z bryły
Metoda ta sprawdza się wyłącznie dla małych wielokątów.
2. Metoda wykrywania kolizji na punkty kolizji (mapa kolizji). Dla każdego wielokąta sceny generujemy n punktów leżących wewnątrz tego wielokąta. Kolizje z wielokątami sceny sprawdzamy tak jak w metodzie pierwszej ale nie na wierzchołki wielokątów lecz na zbiory punktów wygenerowanych wcześniej.
Metoda sprawdza się dla każdego rodzaju wielokątów. Jest wolna przy dużej ilości dużych wielokątów.
3. Metoda wykrywania kolizji na przejście punktu przez ścianę Polega na podstawieniu współrzędnych obserwatora do równania płaszczyzny na której leży wielokąt a następnie sprawdzeniu znaku wyniku. Gdy stwierdzimy że znak otrzymany dla współrzędnych obserwatora przed ruchem jest różny od znaku otrzymanego po ruchu to istnieje możliwość kolizji. Należy wtedy wyznaczyć punkt przecięcia prostej przechodzącej przez współrzędne obserwatora z płaszczyzną którą testowaliśmy. Gdy mamy punkt przecięcia należy sprawdzić czy leży on wewnątrz wielokąta czy nie. Jeżeli leży wewnątrz to wystąpiła kolizja.
Metoda bardzo szybka ale nie uwzględnia objętości obserwatora. Gdy poprawimy metodę dodając testowanie punktów leżących w objętości obserwatora to staje się dość wolna. Przy małej ilości punktów które testujemy w objętości obserwatora rośnie nam szybkość procedury ale maleje dokładność wykrywania kolizji. Przy dużej ilości punktów mamy sytuację odwrotną.
Realizacja: Obserwator jest w punkcie A(x, y, z) i wykonał ruch do punktu B(x, y, z) Testujemy ścianę o wierzchołkach w1,w2,w3,w4 dla której mamy policzone równanie płaszczyzny w postaci N, D oraz równania płaszczyzn prostopadłych do krawędzi ściany p1,p2,p3,p4 w postaci N1,D1 N2,D2 N3,D3 N4,D4.
Sprawdzamy czy wystąpiła kolizja: Sprawdzenie czy wystąpiła kolizja polega na policzeniu dla punktów A i B wyrażenia: ( DotProduct( N, A ) + D ) * ( DotProduct( N, B ) + D ) Gdy znak wyniku jest mniejszy od zera to oba punkty leżą po przeciwnych stronach płaszczyzny wyznaczonej dla ściany czyli istnieje możliwość wystąpienia kolizji. Należy wtedy wyznaczyć punkt przecięcia odcinka (A, B) z płaszczyzną ściany
V = A - B P = B W = (DotProduct( N, P ) + D)/DotProduct( N, V ) Wyznaczamy punkt przecięcia P' P' = P - V*W
Teraz pozostało nam już sprawdzenie czy wyznaczony punkt przecięcia P' leży wewnątrz ściany. Dla każdej z płaszczyzn prostopadłych do krawędzi ściany sprawdzamy czy punkt P' leży po tej samej stronie. Jeżeli leży po tej samej stronie dla wszystkich płaszczyzn p1,p2,p3,p4 to wystąpiła kolizja. Opis tej metody kolizji z odwołaniem do teorii znajduje się w dziale Podstawy.
4. Metoda wykrywania kolizji na bryłę (kolizje bryłowe) Polega na cięciu wielokątów sceny płaszczyznami tworzącymi bryłę wypukłą. Tniemy wielokąt i sprawdzamy czy coś nam zostało. Testujemy zawsze tą część która leży za płaszczyzną. Gdy przetestujemy wszystkie płaszczyzny i coś nam zostanie to wystąpiła kolizja. Gdy w trakcie testowania kolejnych płaszczyzn nic nam nie zostanie to brak kolizji.
Metoda ta jest bardzo szybka i posiada bardzo dużą dokładność wykrywania kolizji. Sprawdza się dla dowolnie dużych brył obserwatora
5. Metoda wykrywania kolizji na sferę (kolizje sferyczne) Jest to rozwinięcie kolizji na przejście punktu przez ścianę. W metodzie tej musimy stwierdzić czy ściana leży w odległości mniejszej od promienia sfery. Jeżeli ściana znajduje się w mniejszej odległości to wystąpiła kolizja.
Kolizje sferyczne polegają na policzeniu odległości obserwatora od ściany. Następnie gdy odległość ta jest mniejsza od promienia sfery musimy policzyć punkt przecięcia prostej (przechodzącej przez pozycję obserwatora i skierowanej zgodnie ze zwrotem wektora normalnego ściany) z płaszczyzną ściany. Następnie stwierdzamy czy wyznaczony punkt leży wewnątrz ściany lub czy jest oddalony od niej o odległość mniejszą od promienia sfery. Ostatnim krokiem jest odsunięcie obserwatora tak aby jego odległość od ściany była równa promieniowi sfery.
Metoda ta jest bardzo szybka i posiada dużą dokładność wykrywania kolizji. Sprawdza się dla dużych brył obserwatora. Pozwala łatwo implementować efekty fizyczne. Przy małym promieniu sfery powoduje że gracz jest zawieszony nisko nad gruntem co powoduje powstawanie efektu 'karła' chodzącego po grafice (większość gier FPP ma ten efekt co może wskazywać na użycie kolizji sferycznych)
6. Metoda wykrywania kolizji na elipsoidę (kolizje elipsoidalne) Jest to rozwinięcie kolizji na sferę. Polega na niezależnym testowaniu kolizji sferycznych dla osi x, y, z. Dla każdej z osi musimy zdefiniować oddzielne promienie. Innym rozwiązaniem jest przekształcenie wierzchołków obiektu z którym testujemy kolizję. Przekształcenie to polega na pomnożeniu współrzędnych obiektu przez odpowiednie współczynniki korygujące różnice w promieniach na osiach x, y, z. Po tym kroku możemy traktować kolizje elipsoidalne jak zwykłe kolizje sferyczne.
Metoda ta posiada wszystkie cechy metody wykrywania kolizji na sferę oraz eliminuje efekt 'karła'.
Metody realizacji ślizgu: Implementując kolizje każdy prędzej czy później będzie zmuszony do implementacji ślizgu gracza po powierzchni z którą ten gracz się zderzył.
Ślizg możemy implementować iteracyjnie. Metoda ta polega na iteracyjnym przemieszczaniu gracza po składowych jego wektora ruchu.
Zalety: Prostota metody Nie wymaga wektorów normalnych
Wady: Podczas wyznaczania nowej pozycji gracza wymaga wykonania n kroków. Może się okazać że po niektórych powierzchniach np. pochyłych czy ukośnych gracz nie będzie się mógł ślizgać.
Ślizg możemy implementować wektorowo. Metoda ta polega na policzeniu wektora odbicia gracza od ściany. Wektor odbicia od ściany jest wektorem normalnym tej ściany którego wartość została zmodyfikowana przez odległość na jaką gracz przemieścił się za tą ścianę.
Zalety: Prostota metody Szybkość (w 1 kroku uzyskujemy nową pozycję gracza)
Wady: Wykorzystuje wektory normalne Wada ta jest pomijalna ponieważ w większości przypadków musimy mieć policzone wektory normalne dla wielokątów sceny.
|
Wszelkie prawa do serwisu posiada Komires Sp. z o. o.