Samouczek fizyki gier wideo — część II: Wykrywanie kolizji dla obiektów stałych

To jest druga część naszej trzyczęściowej serii poświęconej fizyce gier wideo. Dla reszty tej serii zobacz:

Część I: Wprowadzenie do dynamiki ciała sztywnego
Część III: Symulacja sztywnego korpusu usztywnianego

W części I tej serii badaliśmy ciała sztywne i ich ruchy. Jednak w tej dyskusji przedmioty nie wchodziły ze sobą w interakcje. Bez dodatkowej pracy symulowane ciała sztywne mogą przechodzić przez siebie nawzajem lub „przenikać się”, co w większości przypadków jest niepożądane.

Aby bardziej realistycznie symulować zachowanie ciał stałych, musimy sprawdzać, czy zderzają się ze sobą za każdym razem, gdy się poruszają, a jeśli tak, to musimy coś z tym zrobić, np. zastosować siły zmieniające ich prędkości, czyli że ruszą w przeciwnym kierunku. W tym miejscu zrozumienie fizyki kolizji jest szczególnie ważne dla twórców gier.

W części II omówimy krok wykrywania kolizji, który polega na znalezieniu par ciał, które zderzają się z możliwie dużą liczbą ciał rozsianych po świecie 2D lub 3D. W następnej, ostatniej części, porozmawiamy więcej o „rozwiązywaniu” tych kolizji w celu wyeliminowania przenikania się.

Aby zapoznać się z koncepcją algebry liniowej, o której mowa w tym artykule, możesz odwołać się do awaryjnego kursu algebry liniowej w Części I.

Fizyka kolizji w grach wideo

W kontekście symulacji brył sztywnych do kolizji dochodzi, gdy kształty dwóch ciał sztywnych przecinają się lub gdy odległość między tymi kształtami spada poniżej małej tolerancji.

Jeśli w naszej symulacji mamy n ciał, złożoność obliczeniowa wykrywania kolizji za pomocą testów parami wynosi O ( n 2 ) , liczba, która przyprawia informatyków na ostro. Liczba testów parami rośnie kwadratowo wraz z liczbą ciał, a ustalenie, czy dwa kształty w dowolnych pozycjach i orientacjach się kolidują, już nie jest tanie. Aby zoptymalizować proces wykrywania kolizji, dzielimy go generalnie na dwie fazy: fazę szeroką i fazę wąską .

Faza szeroka jest odpowiedzialna za znalezienie par ciał sztywnych, które potencjalnie zderzają się, i wykluczenie par, które z pewnością się nie zderzają, spośród całego zestawu ciał biorących udział w symulacji. Ten krok musi być w stanie naprawdę dobrze skalować się z liczbą ciał sztywnych, aby upewnić się, że pozostaniemy dobrze w złożoności czasowej O ( n 2 ) . Aby to osiągnąć, w tej fazie na ogół wykorzystuje się partycjonowanie przestrzeni w połączeniu z ograniczającymi objętościami , które ustalają górną granicę kolizji.

Faza wąska działa na parach ciał sztywnych znalezionych w fazie szerokiej, które mogą się zderzać. Jest to etap doprecyzowania, w którym określamy, czy kolizje rzeczywiście mają miejsce, a dla każdej wykrytej kolizji obliczamy punkty styku, które zostaną później użyte do rozwiązania kolizji.

W następnych sekcjach omówimy niektóre algorytmy, które można wykorzystać w fazie szerokiej i wąskiej.

Szeroka faza

W szerokiej fazie fizyki kolizji w grach wideo musimy określić, które pary ciał sztywnych mogą się zderzać. Te ciała mogą mieć złożone kształty, takie jak wielokąty i wielościany, a to, co możemy zrobić, aby to przyspieszyć, to użyć prostszego kształtu, aby objąć obiekt. Jeśli te objętości ograniczające się nie przecinają, to rzeczywiste kształty również się nie przecinają. Jeśli się przecinają, rzeczywiste kształty mogą się przecinać.

Niektóre popularne typy objętości ograniczających to zorientowane prostokąty ograniczające (OBB), okręgi w 2D i kule w 3D. Przyjrzyjmy się jednej z najprostszych objętości ograniczających: prostokąty ograniczające wyrównane do osi (AABB) .

AABBs są bardzo kochane przez programistów fizyki, ponieważ są proste i oferują dobre kompromisy. Dwuwymiarowy AABB może być reprezentowany przez strukturę taką jak ta w języku C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Pole min reprezentuje położenie lewego dolnego rogu pola, a pole max reprezentuje prawy górny róg.

Aby sprawdzić, czy dwie AABB przecinają się, musimy tylko sprawdzić, czy ich projekcje przecinają się na wszystkich osiach współrzędnych:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Ten kod ma taką samą logikę jak funkcja b2TestOverlap z silnika Box2D (wersja 2.3.0). Oblicza różnicę między min i max wartością obu AABB, w obu osiach, w obu rzędach. Jeśli którakolwiek z tych wartości jest większa od zera, AABB nie przecinają się.

Mimo że test nakładania się AABB jest tani, niewiele pomoże, jeśli nadal będziemy wykonywać testy parami dla każdej możliwej pary, ponieważ nadal mamy niepożądaną złożoność czasową O ( n 2 ) . Aby zminimalizować liczbę testów nakładania się AABB, możemy użyć pewnego rodzaju partycjonowania przestrzeni , które działa na tych samych zasadach, co indeksy bazy danych, które przyspieszają zapytania. (Geograficzne bazy danych, takie jak PostGIS, w rzeczywistości używają podobnych struktur danych i algorytmów dla swoich indeksów przestrzennych.) W tym przypadku jednak AABB będą się stale poruszać, więc ogólnie rzecz biorąc, musimy odtworzyć indeksy po każdym etapie symulacji.

Istnieje wiele algorytmów partycjonowania przestrzeni i struktur danych, które można do tego wykorzystać, takich jak jednolite siatki, drzewa czwórkowe w 2D, oktry w 3D i mieszanie przestrzenne. Przyjrzyjmy się bliżej dwóm popularnym algorytmom partycjonowania przestrzennego: sortowaniu i przemiataniu oraz ograniczającym hierarchiom woluminów (BVH).

Algorytm sortowania i przeglądania

Metoda sortowania i wymiatania (alternatywnie znana jako sweep and prune ) jest jednym z ulubionych wyborów programistów fizyki do stosowania w symulacji brył sztywnych. Na przykład silnik Bullet Physics ma implementację tej metody w klasie btAxisSweep3 .

Rzut jednego AABB na pojedynczą oś współrzędnych jest zasadniczo odstępem [ b , e ] (czyli początkiem i końcem). W naszej symulacji będziemy mieli wiele ciał sztywnych, a więc wiele AABB, a to oznacza wiele przedziałów. Chcemy dowiedzieć się, które przedziały się przecinają.

W algorytmie sort and sweep wstawiamy wszystkie wartości b i e na pojedynczą listę i sortujemy ją rosnąco według ich wartości skalarnych. Następnie zamiatamy lub przemierzamy listę. Za każdym razem, gdy zostanie napotkana wartość b , odpowiadający jej przedział jest przechowywany na oddzielnej liście aktywnych przedziałów , a za każdym razem, gdy zostanie napotkana wartość e , odpowiadający jej przedział jest usuwany z listy aktywnych przedziałów. W każdej chwili przecinają się wszystkie aktywne interwały. (Sprawdź pracę doktorską Davida Baraffa, s. 52, aby uzyskać szczegółowe informacje. Proponuję skorzystać z tego narzędzia online, aby wyświetlić plik postscriptowy). ta lista przy użyciu sortowania przez wstawianie, które jest dobre przy sortowaniu prawie posortowanych list.

W dwóch i trzech wymiarach, uruchomienie sortowania i przeszukiwania, jak opisano powyżej, na jednej osi współrzędnych zmniejszy liczbę bezpośrednich testów przecięcia AABB, które należy wykonać, ale opłacalność może być lepsza na jednej osi współrzędnych niż na innej. Dlatego implementowane są bardziej wyrafinowane odmiany algorytmu sortowania i przeszukiwania. W swojej książce Real-Time Collision Detection (strona 336), Christer Ericson przedstawia wydajną odmianę, w której przechowuje wszystkie AABB w jednej tablicy, a dla każdego przebiegu sortowania i przemiatania wybierana jest jedna oś współrzędnych, a tablica jest sortowana według min wartość AABB w wybranej osi przy użyciu funkcji szybkiego sortowania. Następnie tablica jest przemierzana i wykonywane są testy nakładania się AABB. Aby określić następną oś, która powinna być użyta do sortowania, obliczana jest wariancja środka kulek AABB, a do następnego kroku wybierana jest oś o większej wariancji.

Dynamiczne drzewa objętości ograniczającej

Inną przydatną metodą partycjonowania przestrzennego jest dynamiczne drzewo woluminów ograniczających , znane również jako Dbvt . Jest to rodzaj ograniczonej hierarchii woluminów .

Dbvt to drzewo binarne, w którym każdy węzeł ma AABB, który ogranicza wszystkie AABB jego dzieci. AABB samych ciał sztywnych znajdują się w węzłach liści. Zazwyczaj Dbvt jest „odpytywany” poprzez podanie AABB, dla którego chcielibyśmy wykryć skrzyżowania. Ta operacja jest wydajna, ponieważ dzieci węzłów, które nie przecinają się z pytanym AABB, nie muszą być testowane pod kątem nakładania się. Jako takie, zapytanie kolizyjne AABB zaczyna się od korzenia i kontynuuje rekursywnie przez drzewo tylko dla węzłów AABB, które przecinają się z pytanym AABB. Drzewo można zrównoważyć poprzez rotację drzew, jak w drzewie AVL.

Box2D ma zaawansowaną implementację Dbvt w klasie b2DynamicTree . Klasa b2BroadPhase jest odpowiedzialna za realizację szerokiej fazy i wykorzystuje instancję b2DynamicTree do wykonywania zapytań AABB.

Wąska faza

Po szerokiej fazie fizyki kolizji w grach wideo mamy zestaw par ciał sztywnych, które potencjalnie mogą się zderzać. Tak więc dla każdej pary, biorąc pod uwagę kształt, położenie i orientację obu ciał, musimy dowiedzieć się, czy faktycznie się one zderzają; jeśli się przecinają lub jeśli ich odległość jest poniżej małej wartości tolerancji. Musimy również wiedzieć, jakie punkty kontaktu znajdują się między zderzającymi się ciałami, ponieważ jest to potrzebne do późniejszego rozwiązania kolizji.

Kształty wypukłe i wklęsłe

Zgodnie z ogólną zasadą fizyki gier wideo ustalenie, czy dwa dowolne kształty się przecinają, lub obliczenie odległości między nimi nie jest proste. Jednak jedną z właściwości, która ma decydujące znaczenie przy określaniu, jaka jest twardość, jest wypukłość kształtu. Kształty mogą być wypukłe lub wklęsłe , a kształty wklęsłe są trudniejsze w obróbce, więc potrzebujemy kilku strategii, aby sobie z nimi poradzić.

W kształcie wypukłym odcinek linii między dowolnymi dwoma punktami w kształcie zawsze znajduje się całkowicie wewnątrz kształtu. Jednak w przypadku kształtu wklęsłego (lub „niewypukłego”) to samo nie dotyczy wszystkich możliwych segmentów linii łączących punkty w kształcie. Jeśli znajdziesz co najmniej jeden segment linii, który w ogóle wychodzi poza kształt, to kształt jest wklęsły.

Obliczeniowo pożądane jest, aby wszystkie kształty w symulacji były wypukłe, ponieważ mamy wiele potężnych algorytmów testowania odległości i przecięcia, które działają z kształtami wypukłymi. Jednak nie wszystkie obiekty będą wypukłe i zwykle pracujemy nad nimi na dwa sposoby: wypukłą powłoką i wypukłą dekompozycją.

Wypukły kadłub kształtu to najmniejszy wypukły kształt, który w pełni go zawiera. W przypadku wielokąta wklęsłego w dwóch wymiarach byłoby to jak wbijanie gwoździa w każdy wierzchołek i owijanie gumką wokół wszystkich gwoździ. Aby obliczyć wypukłą kadłub dla wielokąta lub wielościanu, lub ogólniej, dla zbioru punktów, dobrym algorytmem jest algorytm szybkiej kadłuba , który ma średnią złożoność czasową O ( n log n ) .

Oczywiście, jeśli użyjemy wypukłego kadłuba do przedstawienia wklęsłego obiektu, straci on swoje wklęsłe właściwości. Niepożądane zachowanie, takie jak kolizje „duchów”, może stać się widoczne, ponieważ obiekt nadal będzie miał wklęsłą reprezentację graficzną. Na przykład samochód ma zwykle wklęsły kształt i jeśli użyjemy wypukłego kadłuba do fizycznego przedstawienia go, a następnie umieścimy na nim pudełko, może się wydawać, że pudełko unosi się w przestrzeni powyżej.

Ogólnie rzecz biorąc, kadłuby wypukłe są często wystarczająco dobre, aby reprezentować obiekty wklęsłe, albo dlatego, że nierealistyczne kolizje nie są zbyt zauważalne, albo ich właściwości wklęsłe nie są istotne dla tego, co jest symulowane. Jednak w niektórych przypadkach możemy chcieć, aby wklęsły obiekt zachowywał się fizycznie jak wklęsły kształt. Na przykład, jeśli użyjemy wypukłego kadłuba do fizycznego przedstawienia miski, nie będziemy w stanie nic w nim umieścić. Przedmioty po prostu unoszą się na nim. W tym przypadku możemy zastosować wypukłą dekompozycję kształtu wklęsłego.

Algorytmy dekompozycji wypukłej otrzymują kształt wklęsły i zwracają zestaw kształtów wypukłych, których suma jest identyczna z oryginalnym kształtem wklęsłym. Niektóre kształty wklęsłe mogą być reprezentowane tylko przez dużą liczbę kształtów wypukłych, a ich obliczenia i użytkowanie mogą być zbyt kosztowne. Jednak przybliżenie jest często wystarczająco dobre, więc algorytmy takie jak V-HACD tworzą mały zestaw wielościanów wypukłych z wielościanu wklęsłego.

Jednak w wielu przypadkach fizyki kolizji rozkład wypukły może być wykonany ręcznie przez artystę. Eliminuje to potrzebę opodatkowania wydajności za pomocą algorytmów dekompozycji. Ponieważ wydajność jest jednym z najważniejszych aspektów symulacji w czasie rzeczywistym, ogólnie dobrym pomysłem jest tworzenie bardzo prostych fizycznych reprezentacji złożonych obiektów graficznych. Poniższy obraz przedstawia jeden możliwy rozkład wypukły samochodu 2D przy użyciu dziewięciu wypukłych kształtów.

Testowanie przecięć — twierdzenie o osi rozdzielającej

Twierdzenie o osi rozdzielającej (SAT) stwierdza, że ​​dwa wypukłe kształty nie przecinają się wtedy i tylko wtedy, gdy istnieje co najmniej jedna oś, na której nie przecinają się rzuty ortogonalne kształtów na tej osi.

Zazwyczaj bardziej intuicyjne wizualnie jest znalezienie linii w 2D lub płaszczyzny w 3D, która oddziela te dwa kształty, co w rzeczywistości jest tą samą zasadą. Wektor ortogonalny do prostej w 2D lub wektor normalny płaszczyzny w 3D może być użyty jako „oś rozdzielająca”.

Silniki fizyki gier mają wiele różnych klas kształtów, takich jak okręgi (kulki w 3D), krawędzie (pojedynczy segment linii) i wielokąty wypukłe (wielościany w 3D). Dla każdej pary typu kształtu mają określony algorytm wykrywania kolizji. Najprostszym z nich jest prawdopodobnie algorytm koło-koło:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Mimo że SAT dotyczy okręgów, znacznie łatwiej jest po prostu sprawdzić, czy odległość między ich środkami jest mniejsza niż suma ich promieni. Z tego powodu SAT jest wykorzystywany w algorytmie wykrywania kolizji dla określonych par klas kształtu, takich jak wielokąt wypukły przeciw wielokątowi wypukłemu (lub wielościany w 3D).

Dla dowolnej pary kształtów istnieje nieskończona liczba osi, które możemy przetestować pod kątem separacji. Dlatego określenie, którą oś przetestować jako pierwszą, ma kluczowe znaczenie dla efektywnej implementacji SAT. Na szczęście podczas testowania zderzenia pary wielokątów wypukłych możemy użyć normalnych krawędzi jako potencjalnych osi rozdzielających. Wektor normalny n krawędzi jest prostopadły do ​​wektora krawędzi i wskazuje na zewnątrz wielokąta. Dla każdej krawędzi każdego wielokąta musimy tylko dowiedzieć się, czy wszystkie wierzchołki drugiego wielokąta znajdują się przed krawędzią.

Jeśli jakikolwiek test zakończy się pomyślnie – to znaczy, jeśli dla dowolnej krawędzi wszystkie wierzchołki drugiego wielokąta znajdują się przed nią – wówczas wielokąty się nie przecinają. Algebra liniowa dostarcza prostego wzoru na ten test: mając krawędź pierwszego kształtu z wierzchołkami a i b oraz wierzchołek v drugiego kształtu, jeśli ( v - a ) · n jest większe od zera, to wierzchołek jest z przodu krawędzi.

W przypadku wielościanów możemy użyć normalnych ścian, a także iloczynu poprzecznego wszystkich kombinacji krawędzi z każdego kształtu. To brzmi jak wiele rzeczy do przetestowania; jednak, aby przyspieszyć działanie, możemy buforować ostatnio używaną oś rozdzielającą i spróbować użyć jej ponownie w kolejnych krokach symulacji. Jeśli buforowana oś rozdzielająca nie rozdziela już kształtów, możemy szukać nowej osi, zaczynając od ścian lub krawędzi, które sąsiadują z poprzednią ścianą lub krawędzią. To działa, ponieważ ciała często nie poruszają się ani nie obracają między krokami.

Box2D używa SAT do sprawdzenia, czy dwa wypukłe wielokąty przecinają się w swoim algorytmie wykrywania kolizji wielokąt-wielokąt w b2CollidePolygon.cpp.

Odległość obliczeniowa — algorytm Gilberta-Johnsona-Keerthiego

W wielu przypadkach fizyki zderzeń chcemy uznać, że obiekty zderzają się nie tylko wtedy, gdy faktycznie się przecinają, ale także, gdy znajdują się bardzo blisko siebie, co wymaga od nas znajomości odległości między nimi. Algorytm Gilberta-Johnsona-Keerthi (GJK) oblicza odległość między dwoma wypukłymi kształtami, a także ich najbliższymi punktami. Jest to elegancki algorytm, który działa z niejawną reprezentacją kształtów wypukłych za pomocą funkcji pomocniczych, sum Minkowskiego i sympleksów, jak wyjaśniono poniżej.

Funkcje wspierające

Funkcja wspierająca s A ( d ) zwraca punkt na granicy kształtu A , który ma najwyższy rzut na wektor d . Matematycznie ma najwyższy iloczyn skalarny z d . Nazywa się to punktem wsparcia , a operacja ta jest również znana jako mapowanie wsparcia . Geometrycznie punkt ten jest najdalszym punktem kształtu w kierunku d .

Znalezienie punktu podparcia na wieloboku jest stosunkowo łatwe. Aby uzyskać punkt podparcia dla wektora d , wystarczy wykonać pętlę przez jego wierzchołki i znaleźć ten, który ma najwyższy iloczyn skalarny z d , w ten sposób:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Jednak prawdziwa siła funkcji podparcia polega na tym, że ułatwia pracę z takimi kształtami, jak między innymi stożki, cylindry i elipsy. Trudno jest bezpośrednio obliczyć odległość między takimi kształtami, a bez algorytmu takiego jak GJK zwykle musiałbyś zdyskretyzować je do wielokąta lub wielościanu, aby uprościć sprawę. Może to jednak prowadzić do dalszych problemów, ponieważ powierzchnia wielościanu nie jest tak gładka jak powierzchnia, powiedzmy, kuli, chyba że wielościan jest bardzo szczegółowy, co może prowadzić do słabej wydajności podczas wykrywania kolizji. Mogą również pojawić się inne niepożądane skutki uboczne; na przykład kula „wielościenna” może nie toczyć się płynnie.

Aby uzyskać punkt podparcia dla kuli wyśrodkowanej na początku, wystarczy znormalizować d (to znaczy obliczyć d / || d || , który jest wektorem o długości 1 (jednostkowa), który wciąż wskazuje w tym samym kierunku z d ), a następnie mnożymy przez promień kuli.

Sprawdź artykuł Gino van den Bergena, aby znaleźć więcej przykładów funkcji wsparcia dla cylindrów i stożków, między innymi kształtów.

Nasze obiekty będą oczywiście przemieszczane i obracane od początku w przestrzeni symulacji, więc musimy być w stanie obliczyć punkty podparcia dla przekształconego kształtu. Używamy transformacji afinicznej T ( x ) = R x + c , aby przemieścić i obrócić nasze obiekty, gdzie c jest wektorem przemieszczenia, a R jest macierzą rotacji . Ta transformacja najpierw obraca obiekt wokół początku, a następnie dokonuje jego translacji. Funkcja podparcia dla przekształconego kształtu A to:

Sumy Minkowskiego

Suma Minkowskiego dwóch kształtów A i B jest zdefiniowana jako:

Oznacza to, że obliczamy sumę dla wszystkich punktów zawartych w A i B . Wynik jest jak nadmuchiwanie A przez B .

Podobnie definiujemy różnicę Minkowskiego jako:

którą możemy również zapisać jako sumę Minkowskiego A z -B :

Dla wypukłych A i B A⊕B jest również wypukły.

Jedną z przydatnych właściwości różnicy Minkowskiego jest to, że jeśli zawiera początek przestrzeni, kształty przecinają się, jak widać na poprzednim obrazie. Dlaczego? Bo jeśli dwa kształty się przecinają, to mają co najmniej jeden wspólny punkt, który leżą w tym samym miejscu w przestrzeni, a ich różnicą jest wektor zerowy, czyli tak naprawdę początek.

Inną miłą cechą różnicy Minkowskiego jest to, że jeśli nie zawiera początku, minimalną odległością między początkiem a różnicą Minkowskiego jest odległość między kształtami.

Odległość między dwoma kształtami definiuje się jako:

Innymi słowy, odległość między A i B to długość najkrótszego wektora, który biegnie od A do B . Ten wektor jest zawarty w A⊖B i jest to ten o najmniejszej długości, czyli w konsekwencji najbliższy początku.

Na ogół nie jest łatwo jednoznacznie zbudować sumę Minkowskiego dwóch kształtów. Na szczęście tutaj również możemy użyć mapowania wsparcia, ponieważ:

Simpleksy

Algorytm GJK iteracyjnie poszukuje punktu na różnicy Minkowskiego najbliższego początku. Robi to, budując serię sympleksów , które są bliższe początku w każdej iteracji. Simpleks – a dokładniej k-simplex dla liczby całkowitej k – jest wypukłą powłoką k + 1 afinicznie niezależnych punktów w k-wymiarowej przestrzeni. To znaczy, jeśli dla dwóch punktów nie mogą się pokrywać, dla trzech punktów dodatkowo nie mogą leżeć na tej samej prostej, a jeśli mamy cztery punkty, to również nie mogą leżeć na tej samej płaszczyźnie. Zatem 0-simplex to punkt, 1-simplex to odcinek linii, 2-simplex to trójkąt, a 3-simplex to czworościan. Jeśli usuniemy punkt z simpleksu, zmniejszymy jego wymiarowość o jeden, a jeśli dodamy punkt do simpleksu, zwiększymy jego wymiarowość o jeden.

GJK w akcji

Połączmy to wszystko razem, aby zobaczyć, jak działa GJK. Aby określić odległość między dwoma kształtami A i B , zaczynamy od wzięcia ich różnicy Minkowskiego A⊖B . Szukamy najbliższego punktu początkowego na wynikowym kształcie, ponieważ odległość do tego punktu jest odległością między dwoma pierwotnymi kształtami. Wybieramy jakiś punkt v w A⊖B , który będzie naszym przybliżeniem odległości. Definiujemy również pusty zbiór punktów W , który będzie zawierał punkty w bieżącym testowym simpleksie.

Następnie wchodzimy w pętlę. Zaczynamy od uzyskania punktu podparcia w = s A⊖B (- v ) , punktu na A⊖B , którego rzut na v jest najbliższy początku.

Jeżeli || w || niewiele różni się od || v || a kąt między nimi nie zmienił się zbytnio (zgodnie z pewnymi predefiniowanymi tolerancjami), oznacza to, że algorytm się zbieżny i możemy zwrócić || v || jako odległość.

W przeciwnym razie dodajemy w do W . Jeśli wypukła kadłub W (czyli simpleks) zawiera początek, kształty się przecinają, a to również oznacza, że ​​skończyliśmy. W przeciwnym razie znajdujemy w simpleksie punkt, który jest najbliżej początku, a następnie ustawiamy v tak, aby było to nowe najbliższe przybliżenie. Na koniec usuwamy wszystkie punkty w W , które nie przyczyniają się do obliczenia najbliższego punktu. (Na przykład, jeśli mamy trójkąt, a najbliższy punkt początku leży na jednej z jego krawędzi, możemy usunąć punkt z W , który nie jest wierzchołkiem tej krawędzi.) Następnie powtarzamy te same kroki, aż algorytm zbiega się.

Kolejny obraz przedstawia przykład czterech iteracji algorytmu GJK. Niebieski obiekt reprezentuje różnicę Minkowskiego A⊖B , a zielony wektor to v . Tutaj możesz zobaczyć, jak v ostrzy się w najbliższym punkcie początkowym.

Aby uzyskać szczegółowe i dogłębne wyjaśnienie algorytmu GJK, zapoznaj się z artykułem A Fast and Robust GJK Implementation for Collision Detection of Convex Objects autorstwa Gino van den Bergen. Blog poświęcony silnikowi fizyki dyn4j ma również świetny post na GJK.

Box2D posiada implementację algorytmu GJK w b2Distance.cpp, w funkcji b2Distance . Wykorzystuje GJK tylko w czasie obliczania uderzenia w swoim algorytmie do ciągłego wykrywania kolizji (temat omówimy dalej).

Silnik fizyki Chimpunk używa GJK do wykrywania kolizji, a jego implementacja znajduje się w cpCollision.c, w funkcji GJK . Jeśli algorytm GJK zgłasza przecięcie, nadal musi wiedzieć, jakie są punkty styku, wraz z głębokością penetracji. W tym celu wykorzystuje algorytm Expanding Polytope Algorithm, który omówimy dalej.

Określanie głębokości penetracji — algorytm rozszerzającego się wielotopu

Jak wspomniano powyżej, jeśli kształty A i B przecinają się, GJK wygeneruje simpleks W , który zawiera początek, wewnątrz różnicy Minkowskiego A⊖B . Na tym etapie wiemy tylko, że kształty się przecinają, ale przy projektowaniu wielu systemów wykrywania kolizji pożądane jest, aby móc obliczyć, ile mamy przecięcia i jakie punkty możemy wykorzystać jako punkty styku, aby realistycznie radzimy sobie z kolizją. Algorytm Expanding Polytope Algorithm (EPA) pozwala nam uzyskać te informacje, zaczynając od miejsca, w którym skończyło się GJK: od simpleksu zawierającego źródło.

Głębokość penetracji to długość minimalnego wektora translacji (MTV), który jest najmniejszym wektorem, wzdłuż którego możemy przesunąć przecinający się kształt, aby oddzielić go od innego kształtu.

Kiedy dwa kształty się przecinają, ich różnica Minkowskiego zawiera początek, a punktem na granicy różnicy Minkowskiego, który jest najbliższy początku, jest MTV. Algorytm EPA znajduje ten punkt, rozszerzając simpleks, który dał nam GJK, w wielokąt; sukcesywnie dzieląc jego krawędzie o nowe wierzchołki.

Najpierw znajdujemy krawędź simpleksu najbliżej początku i obliczamy punkt podparcia w różnicy Minkowskiego w kierunku normalnym do krawędzi (tj. prostopadłym do niej i skierowanym na zewnątrz wielokąta). Następnie dzielimy tę krawędź, dodając do niej ten punkt podparcia. Powtarzamy te kroki, aż długość i kierunek wektora nie zmienią się zbytnio. Gdy algorytm się zbiega, mamy MTV i głębokość penetracji.

Używając GJK w połączeniu z EPA, otrzymujemy szczegółowy opis kolizji, bez względu na to, czy obiekty już się przecinają, czy tylko na tyle blisko, by uznać je za kolizję.

Algorytm EPA jest opisany w artykule Proximity Queries and Penetration Depth Computation on 3D Game Objects , również napisanym przez Gino van den Bergen. Blog dyn4j zawiera również post o EPA.

Ciągłe wykrywanie kolizji

Przedstawione dotychczas techniki fizyki gier wideo umożliwiają wykrywanie kolizji w celu uzyskania statycznej migawki symulacji. Nazywa się to dyskretnym wykrywaniem kolizji i ignoruje to, co dzieje się między poprzednim a bieżącym krokiem. Z tego powodu niektóre kolizje mogą nie zostać wykryte, zwłaszcza w przypadku szybko poruszających się obiektów. Ten problem jest znany jako tunelowanie .

Techniki ciągłego wykrywania kolizji próbują ustalić , kiedy dwa ciała zderzyły się między poprzednim a bieżącym etapem symulacji. Obliczają czas uderzenia , dzięki czemu możemy cofnąć się w czasie i w tym momencie przetworzyć kolizję.

Czas uderzenia (lub czas kontaktu) t c to moment, w którym odległość między dwoma ciałami wynosi zero. Jeśli możemy napisać funkcję określającą odległość między dwoma ciałami w czasie, chcemy znaleźć najmniejszy pierwiastek tej funkcji. Tak więc czas obliczania wpływu jest problemem związanym ze znalezieniem pierwiastków .

Do obliczenia czasu uderzenia bierzemy pod uwagę stan (położenie i orientację) ciała w poprzednim kroku w czasie t i -1 , aw kroku bieżącym w czasie t i . Aby uprościć sprawę, zakładamy ruch liniowy między krokami.

Uprośćmy problem, zakładając, że kształty są okręgami. Dla dwóch okręgów C 1 i C 2 , o promieniu r 1 i r 2 , gdzie ich środek masy x 1 i x 2 pokrywa się z ich środkiem ciężkości (tj. naturalnie obracają się wokół swojego środka masy), możemy zapisać funkcję odległości Jak:

Rozważając ruch liniowy między krokami, możemy zapisać następującą funkcję dla położenia C 1 od t i -1 do t i

Jest to interpolacja liniowa od x 1 ( t i -1 ) do x 1 ( t i ) . To samo można zrobić dla x 2 . Dla tego przedziału możemy zapisać inną funkcję odległości:

Ustaw to wyrażenie na zero, a otrzymasz równanie kwadratowe na t . Korzenie można znaleźć bezpośrednio za pomocą wzoru kwadratowego. Jeśli okręgi się nie przecinają, wzór kwadratowy nie będzie miał rozwiązania. Jeśli tak, może to skutkować jednym lub dwoma korzeniami. Jeśli ma tylko jeden pierwiastek, wartością tą jest czas uderzenia. Jeśli ma dwa pierwiastki, najmniejszy to czas uderzenia, a drugi to czas rozdzielenia się kręgów. Zauważ, że czas uderzenia to liczba od 0 do 1. Nie jest to czas w sekundach; to tylko liczba, której możemy użyć do interpolacji stanu ciał do dokładnego miejsca, w którym doszło do zderzenia.

Ciągłe wykrywanie kolizji w przypadku braku kręgów

Pisanie funkcji odległości dla innych rodzajów kształtów jest trudne, głównie dlatego, że ich odległość zależy od ich orientacji. Z tego powodu zwykle używamy algorytmów iteracyjnych, które przesuwają obiekty coraz bliżej w każdej iteracji, aż będą wystarczająco blisko, aby można je było uznać za kolidujące.

Konserwatywny algorytm zaawansowania przesuwa ciała do przodu (i obraca je) iteracyjnie. W każdej iteracji oblicza górną granicę przemieszczenia. Oryginalny algorytm jest przedstawiony w rozprawie doktorskiej Briana Mirticha (sekcja 2.3.2), która uwzględnia ruch balistyczny ciał. Ten artykuł autorstwa Erwina Coumansa (autora Bullet Physics Engine) przedstawia prostszą wersję, która wykorzystuje stałe prędkości liniowe i kątowe.

Algorytm oblicza najbliższe punkty między kształtami A i B , rysuje wektor z jednego punktu do drugiego i rzutuje prędkość na ten wektor, aby obliczyć górną granicę ruchu. Gwarantuje to, że żadne punkty na ciele nie wyjdą poza tę projekcję. Następnie przesuwa ciała do przodu o tę wartość i powtarza, aż odległość spadnie poniżej małej wartości tolerancji.

W niektórych przypadkach zbieżność może zająć zbyt wiele iteracji, na przykład gdy prędkość kątowa jednego z ciał jest zbyt duża.

Rozwiązywanie kolizji

Po wykryciu kolizji konieczna jest realistyczna zmiana ruchów zderzających się obiektów, na przykład spowodowanie ich wzajemnego odbijania się. W następnej i ostatniej części tej teorii omówimy niektóre popularne metody rozwiązywania kolizji w grach wideo.

Bibliografia

Jeśli jesteś zainteresowany uzyskaniem głębszego zrozumienia fizyki kolizji, takich jak algorytmy i techniki wykrywania kolizji, książka Christera Ericsona o wykrywaniu kolizji w czasie rzeczywistym jest koniecznością.

Ponieważ wykrywanie kolizji w dużej mierze opiera się na geometrii, artykuł Toptala Computational Geometry in Python: From Theory to Application jest doskonałym wprowadzeniem do tematu.