Programowanie Gier -> Wykład: Kolizje, portale

1. Elementarne testy kolizji

  1. Ogólne wytyczne jak implementować:

    • Najpierw wykonuj łatwe testy które mają szansę szybko udzielić odpowiedzi. Np. w przypadku testów które porównują skomplikowane obiekty, najpierw przetestuj ich bounding volumes w nadziei na szybkie udowodnienie odpowiedzi "nie ma kolizji". Pomyśl (albo faktycznie zbadaj dodając odpowiedni kod do programu) jaką odpowiedź zazwyczaj udzieli dany test (w przypadku wielu testów kolizji, zazwyczaj odpowiedź brzmi "nie ma kolizji") --- i przeorganizuj kod tak żeby najpierw testował czy zachodzi ta najbardziej prawdopodobna odpowiedź.
    • Pamiętaj o specjalnych przypadkach, wartościach bliskich zera w mianowniku etc. Unikaj jak możesz używania epsilonów (chociaż to łatwo powiedzieć, trudniej zrobić...). Jeżeli rzutujemy problem z przestrzeni 3D na 2D albo 1D, zawsze wybieraj rzutowanie wzdłuż najbardziej rozpiętych współrzędnych.
    • Naturalnie, profiluj. Testuj szybkość na prawdziwych danych --- realny model 3D ze sferą gracza zazwyczaj mają inny rozkład niż losowy zbiór trójkątów z losową sferą.

    Także naturalnie, przygotuj automatyczne testy poprawności. Testuj poprawność też na perfidnych danych, na których zachodzą szczególne przypadki.

    Jeżeli ktoś nie bawił się nigdy z profilerem albo automatycznymi testami, pisanie obsługi kolizji to dobry moment żeby zacząć --- tego typu procedury zazwyczaj profilue/testuje się stosunkowo przyjemnie (ponieważ bawimy się z krótkim, odizolowanym (zazwyczaj nie zależy od wielu czynników zewnętrznych, wynik zależy tylko od parametrów) kawałkiem kodu).

  2. Popularne bounding volumes (będziemy często potrzebowali testów kolizji z nimi, albo pomiędzy nimi):

    • AABB (axis-aligned bounding box). Ultra-prosty, ultra-szybki, zachowuje się Ok pod przesunięciem i skalowaniem. Problem: rotacja go zwiększa (albo zmienia w OBB). Tworzenie: trywialne, iteruj i wyznacz min/max.

    • Sfera.

      Tworzenie: 1. weź bbox, i jego sferę otaczającą. 2. popraw: znając centrum sfery, iterując po vertex ustal lepszy (minimalny) promień. W praktyce, to daje niezłe i szybkie rezultaty. Chociaż można lepiej:

      Ritter (graphic gems), bliski optymalnemu i ciągle prosty: 1. znajdź trzy pary vertexów: max X z min X, max Y z min Y, etc. 2. wybierz najbardziej odległą parę, początkowa sfera taka żeby obejmowała tylko dwa punkty tej pary. Idea: w tym momencie mamy optymalną sferę dla dwóch punktów, a jest spora szansa że wszystkie pozostałe punkty się w niej mieszczą lub wymagają tylko nieznacznego zwiększenia sfery. 3. popraw: iteruj po vertexach, jeżeli vertex jest w odległości d większej od aktualnego promienia sfery r to przesuń center sfery o (d-r)/2 i zwiększ radius o (d+r)/2.

      Istnieją algorytmy które gwarantują optymalne sfery (o oczekiwanym czasie liniowym), ale nie będziemy się w to wgłębiać --- nie potrzebujemy.

    • OBB (oriented bounding box) --- AABB z obrotem, zazwyczaj reprezentacja to AABB wycentrowane (centrum 3D + trzy długości) z obrotem (np. jako kwaternion, albo (mniej oszczędnie, ale użytecznie) trzy znormalizowane wektory (osie X, Y, Z po obrocie)).

      Tworzenie: nieco nietrywialne jeżeli chcemy dobrać optymalną rotację dla chmury punktów. Gottshalk (wymaga obliczenia convex hull po drodze), Elberlt. W praktyce: Zazwyczaj jest Ok jeżeli obliczamy tylko AABB z chmury punktów. OBB otrzymujemy dopiero wtedy kiedy ta chmura punktów jest poddana transformacji.

    • k-DOP (discrete oriented polytope): uogólniony OBB: część wspólna k półpłaszczyzn, półpłaszczyzny zadane jako k/2 par, równoległe w parach. Typowa reprezentacja: dla każdej pary: wektor normalny, min, max (5 skalarów).

      Tworzenie: bardzo nietrywialne, jeżeli musimy sami wybrać wektory normalne. Oczywiście trywialne jeżeli mamy zadane wktory normalne. W praktyce: niech artysta 3D zada wektory normalne.

  3. Przykład: test plane <-> AABB

    Wystarczy znaleźć 2 ekstremalne punkty (spośród 8) na AABB żeby znaleźć rozwiązanie. W przypadku testów na AABB, to częsta sytuacja: zazwyczaj wystarczy 1/2 ekstremalne kanty AABB, nie trzeba sprawdzać 8 rogów.

    Zauważcie też że test rozróżnia (prawie za darmo) po której stronie plane jest box jeżeli nie ma kolizji --- będzie użyteczne czasem (np. do frustum<->box, póxniej).

    My real world implementation (patrz impl Box3dPlaneCollision)

  4. Przykład: test trójkąt <-> AABB

    Separating axis theorem, intuicyjnie:

    1. (Stosunkowo jasne) Dwa wielościany wypukłe A, B są rozłączne wtw gdy istnieje płaszczyzna elegancko dzieląca przestrzeń pomiędzy nimi. (Alternatywnie: istnieje oś dzieląca ("separating axis") taka że rzuty wielościanów na tą oś (3D -> 1D) są rozłączne.)
    2. (Nie tak oczywiste, b. przydatne) Jeżeli w ogóle istnieje taka płaszczyzna -> to na pewno możemy znaleźć płaszczyznę dzielącą której wektor normalny (oś) powstał przez cross product dwóch krawędzi z A i/lub B. Czyli: albo znajdziemy płaszczyznę której normalna to cross product dwóch krawędzi z A (czyli płaszczyzna jest równoległa do ściany A), albo analogicznie dla dwóch krawędzi z B (czyli płaszczyzna jest równoległa do ściany B), albo cross product jednej krawędzi z A i jednej z B.

    To oznacza że dla testu trójkąt<->AABB trzeba sprawdzić 13 płaszczyzn:

    1. Płaszczyznę trójkąta (używamy testu plane<->AABB)
    2. 3 płaszczyzny AABB (AABB ma 6 płaszczyzn, ale równoległych w parach). Sprowadza się to do testu AABB z minimalnym AABB wokół trójkąta.
    3. 9 "nieintuicyjcnych" płaszczyzn: dla każdej z 3 krawędzi trójkąta, zrób jej cross product z jedną z trzech krawędzi AABB (AABB ma 12 krawędzie, ale równoległych w czwórkach). Pominiemy sobie rozpisanie tych testów, zobaczcie w Internecie.

    Details: "Fast 3D Triangle-Box Overlap Testing" by Tomas Akenine-Möller, PDF downloadable from here, sample impl from here (also in my boxes.3d.pas).

2. Kolizje ruchomych elementów (gracza, potworków etc.)

3. Frustum culling (przycinanie do piramidy widzenia)

  1. Dlaczego?

    Najprostsza i bardzo efektywna metoda optymalizacji wyświetlania w aplikacji (CPU): elementy które są poza piramidą widzenia nie muszą być renderowane. W zależności od rodzaju modelu i rozpiętości kamery, tylko niewielka część sceny jest widoczna (demo view3dscene gate_final level, z wizualizacją frustum --- typowy zysk to ~1/3 - 1/10, czyli naprawdę warto). Gdybyśmy umieli szybko odrzucić część sceny poza frustum, mielibyśmy spory zysk czasowy.

    Oczywiście nie możemy sprawdzać kolizji każdego trójkąta z piramidą widzenia --- to robi sam OpenGL. Chcemy wykorzystać naszą wiedzę o scenie, i sprawdzać bounding volumes (boxes albo spheres) całych obiektów (potworków, elementów levelu etc.) z frustum zanim będziemy renderować ten obiekt.

    Można też, a nawet należy na dużych scenach, obcinać do piramidy widzenia używając drzewa podziału przestrzeni 3D --- więcej o nich za chwilę.

  2. Jak?

    Piramida widzenia to po prostu część wspólna 6 półpłaszczyzn. Notka: czasami, zwłaszcza dla shadow volumes, używamy perspektywy bez far plane (far plane w infinity), wtedy mamy po prostu 5 półpłaszczyzn i nic się nie zmienia. Chcemy też znać orientację naszych płaszczyzn --- np. chcemy żeby wektory normalne wszystkich 6 płaszczyzn wskazywały do środka frustum (albo na zewnątrz, dowolnie byle konsekwentnie).

    Można obliczać 6 płaszczyzn na różne sposoby, w praktyce całkiem prosta i skuteczna metoda to wyciągnąć płaszczyzny frustum z macierzy (projection * macierz kamery). Patrz tutaj po szczegółowy opis (konkretny trywialny kod na końcu).

    Mając 6 płaszczyzn, test kolizji frustum <-> AABB jest trywialny. Korzystamy w pokazanego testu płaszczyzna <-> AABB, który dodatkowo zwraca po której stronie jest bbox. Jeżeli bbox jest na zewnątrz którejkolwiek płaszczyzny frustum, to bbox jest poza frustum. Jeżeli bbox jest w środku wszystkich płaszczyzn frustum, to bbox jest całkowicie w środku frustum. Wpp. nie wiadomo --- być może jest częściowa kolizja (część boxa jest w środku, część na zewnątrz frustum), a być może nie ma kolizji (może sie to zdarzyć --- patrz rysunek). Trzeci, niepewny wynik nie jest dla nas problemem --- my tylko optymalizujemy, możemy wyświetlić takiego boxa, ryzykując nieznaczny (w praktyce żaden, podchwytliwa sytuacja jest naprawdę rzadko) spadek szybkości, ale gwarantując sobie poprawność.

    Test kolizji frustum <-> sfera też jest trywialny: badamy odległość (ze znakiem) środka sfery z płaszczyznami frustum, i mamy wynik "na zewnątrz/w środku/niepewny" używając tego samego rozumowania. Tutaj przydaje się mieć płaszczyzny frustum znormalizowane, co w praktyce nie jest problemem (frustum wyznaczamy zazwyczaj raz na klatkę, tylko 6 pierwiastkowań na klatkę -> żaden problem, a zysk olbrzymi.)

    Propozycje innych optymalizacji: dla sfery można wykorzystać symetryczność frustum (bottom/top, left/right) i równoległość far/near planes. Oznacza to że można ustalić w której z ośmiu części frustum znajduje się centrum sfery, i wykonać testy tylko z 3 płaszczyznami frustum zamiast z 6. Chociaż dla sfer ta optymalizacja jest w praktyce bezużyteczna (ponieważ prosty test plane-sfera jest bardzo szybki; cytuję za Moller-Haines, sam byłem zbyt leniwy żeby w ogóle ją implementować), ale może mieć sens dla bardziej skomplikowanych niż sfera obiektów.

    Kiedy używamy drzew żeby szukać obiektów kolidujących z frustum, kiedy jakiś węzeł drzewa jest w środku frustum --- to wszystkie jego dzieci też są w środku drzewa albo przynajmniej z nim kolidują (zależy od naszej strategii wkładania elementów do drzewa).

  3. Mgła

    Przy okazji, optymalizacja na podobnym pomyśle: kiedy scena używa gęstej mgły, wiadomo że wszystkie obiekty dalej od pewnej granicy są praktyczne jednego koloru. (demo fog_culling)

    Dla mgły LINEAR OpenGLa, nawet wiemy dokładnie jaka to odległość: to co przekazaliśmy jako FOG_END. Inne rodzaje mgły (exponential, exponential2) tylko zmierzają do 0, nigdy go precyzyjnie nie osiągając, ale to też Ok, można wybrać na tyle dużą odległość dla której przejście skokowe do koloru mgły nie będzie już zauważalne. Oczywiście można też zaimplementować mgłę w/g własnego wzoru (EXT_FOG_COORD, albo shadery.)

    Elementy poza granicą mgły nie muszą być renderowane. Wystarczy że wypełnimy ekran kolorem mgły przez renderowaniem.

    Czyli można stosować podobną optymalizację dla sfery mgły co dla piramidy widzenia. Albo prościej: można po prostu ustawić far plane piramidy widzenia na zakres naszej mgły.

4. Drzewa (podziału przestrzeni i BVH)

Idea: kiedy musimy sprawdzić kolizję ze światem 3D, nie chcemy iterować po wszystkich trójkątach tego świata. Podział sceny na obiekty (z których każdy ma bbox i/lub sferę) też nie wystarcza kiedy mamy dużo obiektów. Drzewa dzielące przestrzeń 3D w naturalny sposób nam pomagają --- zamiast sprawdzać wszystko, będziemy sprawdzać tylko partie drzewa które kolidują z naszych testerem.

Drzewo może zawierać trójkąty albo bboxy albo sfery albo cokolwiek innego. Więcej o tym za chwilę, na razie możemy myśleć że mamy jedno drzewo które zawiera wszystkie trójkąty naszej (kompletnie statycznej) sceny.

Chcemy żeby drzewo było zbalansowane, ale w praktyce (przynajmniej dla prostych zastosowań) nie mamy na tym punkcie paranoi. Typowe sceny 3D rozkładają się jako-tako równomiernie w 3D, i nawet najprostsze metody konstrukcji dają dobre rezultaty dla naszych zastosowań (sprawdzanie róznorakich kolizji).

5. Bardziej dynamiczne drzewa podziału przestrzeni

Idea: kiedy zmienia się scena, trochę nie wiadomo co robić z normalnym drzewem podziału przestrzeni. Przebudowa dużego drzewa jest zdecydowanie zbyt kosztowna żeby robić ją często. BVH rozwiązują ten problem, ale kosztem struktury o nieco gorszej wydajności. Poniżej trochę pomysłów jak ulepszyć drzewa ósemkowe (i czwórkowe), niektóre z nich mają zastosowanie także do kd-drzew (o BSP najłatwiej zapomnieć jeżeli chcemy dynamicznej sceny :) ).

6. Portale

Idea: jeżeli nie patrzę na okno, nie widzę świata za oknem. Więc nie musimy wrzucać świata za oknem do OpenGLa. Portale działają fantastycznie w zamkniętych pomieszczeniach --- labirynty, korytarze, etc. W miarę jak scena robi się coraz bardziej outdoors, zalety portalów zanikają (wtedy patrz LOD, image-based rendering, ale o tym kiedy indziej).

W prostej wersji, portale oznacza projektant levelu 3D. Chociaż są algorytmy robiące to automatycznie.

Portale łączą komórki. Mamy graf portali + komórek.

  1. Możemy wyznaczyć offline z jakich komórek potencjalnie widać inne komórki. W ten sposób mamy PVS (Potentially Visible Set), chyba najbardziej znany z silników id Software.

  2. I/lub możemy badać portale podczas renderowania konkretnej klatki, znając aktualną pozycję i kierunek kamery. Sprawdź czy portal jest widoczny --- jeśli tak, to renderuj kolejną komórkę i sprawdź jej portale.

    Bonus: komórka może być widoczna tylko przez portal, więc możesz ustawić clipping OpenGLa żeby renderować komórkę tylko tam gdzie jest widoczny portal. W ten sposób prymitywy mogą być obcinane, nie muszą być rasteryzowane --- spada obciążenie na fragment stage.

    Skąd wiem kiedy portal jest widoczny? Luebke, Georges: cull box. Po prostu oblicz gdzie na ekranie jest portal. Teraz renderuj komórkę za nim: dla każdego obiektu oblicz gdzie jest ekranie, i jeżeli przecięcie obiektu i portalu na ekranie puste -> nie renderuj. Dla rekurencyjnych portali w komórce: też przytnij je aktualnym portalem, jeżeli przecięcie puste -> nie musisz renderować komórki za nimi.

7. Zalążki inteligencji w świecie 3D: waypointy

Idea: potworki muszą wiedzieć o wąskich przejściach pomiędzy elementami levelu żeby należycie tropić gracza. Jeżeli trzeba przejść przez drzwi, albo wąski most, żeby przejść z jednego sektora do drugiego, trzeba to oznaczyć waypointem.

Podczas ruchu, potworek patrzy czy jego aktualna pozycja i pozycja docelowa (tam dokąd chce iść, np. ostatnio widziana pozycja gracza) są w różynch sektorach. Jeśli tak, to znaczy że trzeba znaleźć drogę w grafie waypointów + sektórów, i iść w stronę pierwszego waypointa.

Waypointy/sektory są oznaczane przez projektantów levelu 3D, tak jak portale (i często w podobnych miejscach).

W praktyce, działają całkiem łatwo i przyjemnie. Demo: castle tower, bridge. Używane w wielu (wszystkich?) grach 3D, np. half-life.