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.)

• Gracz to zazwyczaj bounding sphere (sphere, chociażby po to żeby nie mógł złamać near perspektywy, ani podchodzić zbyt blisko do kiepsko filtrowanych tekstur).

• Można dodać pod gracza odcinek albo box, żeby gracz stał wysoko ponad ziemią. Michalis zazwyczaj reprezentuja gracza jako piłeczka na sprężynce (w ten sposób mamy przy okazji łagodne wchodzenie po schodach i podnoszenie się z crouching, chociaż nieco prostą metodą).

• Potworki etc. też potrzebują bounding volume, żeby nie wchodziły w ściany i nie zatapiały się w podłodze. W praktyce, można traktować potworki podobnie do gracza (piłeczka na sprężynce), ale to nieuchronnie powoduje problemy że potworki mogą wspinać się po schodach --- ale ich nogi zatapiają się w schodach kiedy patrzymy na nie od tyłu. Rzadka sytuacja, można zignorować. Albo, elegancko: potraktować wchodzenie wyżej/niżej specjalnymi animacjami w których pokazujemy bardziej naturalny ruch, unikając animacji "zatapiania nóg w podłodze". Więcej --- na wykładzie o animacji.

• Kiedy ruszamy graczem/potworkiem, sam test czy nowa pozycja jest dobra (czy nowa sfera gracza/potworka nie koliduje ze światem) nie wystarcza. Przy szybkim ruchu (albo niskiej ilości FPS, co powoduje skokowy ruch przy time-based animation) mogłoby to pozwolić nam przechodzić przez cienkie ściany (a przecież nasz świat 3D jest złożony z nieskończenie cienkich ścian = trójkątów).

  Kiepskie rozwiązanie to wyznaczyć po drodze kilka dodatkowych sfer. Oczywiście kiepskie, bo 1. stała ilość sfer będzie za duża/za mała w niektórych sytuacjach, 2. dynamiczna ilość sfer będzie albo zbyt gęsta (czemu przybliżamy "sweep sphere" przez wiele sfer?), albo zbyt rzadka (i będzie ryzyko że czegoś nie zauważy).

  Eleganckie rozwiązanie to testy na "sweep" sphere, boxes etc. Patrz google.

  Alternatywne proste rozwiązanie (używane przez Michalisa :) ) test na odcinek (stary-> nowy środek sfery gracza) i nową sferę gracza. Chociaż nie jest to tak precyzyjne jak sweepk sfery (rysunek: można ściąć rogi na które normalnie sweep sphere by nie pozwoliła). Ale gwarantuje że 1. końcowa bounding sphere gracza nie koliduje z modelem 2. gracz nie może przejść na drugą stronę ściany, czyli w sumie wszystko czego potrzeba.

• Wall sliding: Teoretyczne perfekcyjne rozwiązanie: jeśli kolizja ze ścianą, to wyznacz sferę która jest najbliżej do kolidującej ściany i wywołaj się rekurencyjnie z krótszą odległością i kierunkiem równoległym do ściany. Uwagi:
  • Pamiętaj sprawdzić czy na pewno nowa pozycja sfery nie koliduje z inną ścianą.
  • Ponieważ będziemy poruszali się tuż obok ściany, trzeba szczególnie uważać na epsilony w testach kolizji. Testy które zbyt gorliwie uznają że kolizja zachodzi mogą sprawić że utkniemy w ścianie. W praktyce: na potrzeby wall sliding, oddal się od ściany bardziej niż promień sfery gracza, żeby zyskać mały margines.
  • Uproszczenia: tak naprawdę, robienie tego rekurencyjnie jest potrzebne tylko w naprawdę specyficznych przypadkach (musielimyśmy mieć zagiętą do nas ścianę o bardzo gęstych krawędziach, patrz rysunek). Czyli nie trzeba. Tak naprawdę, nie trzeba też robić "przysuwania" się jak najbliżej do ściany, zazwyczaj tego nie widać. Czyli uproszczona (ale w praktyce zazwyczaj Ok) wersja algorytmu najpierw próbuje zrobić normalny ruch, jeżeli nie można --- to ruch wzdłuż kolidującej ściany, i koniec.

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).

• Octree (drzewa ósemkowe). W przestrzeni 3D, każdy węzeł reprezentuje jakiś wycinek przestrzeni (najczęściej i najprościej: AABB), zawiera 8 dzieci (które reprezentują 8 bboxów w środku głownego węzła). Stąd nazwa. 8 dzieci węzła jest wyznaczonych przez punkt 3D w środku węzła, który wyznacza 3 płaszczyzny które tną przestrzeń na 8 części. W prostej wersji, "punkt środkowy" to faktyczny środek bboxa węzła, bbox głównego węzła (root) bierzemy po prostu z bounding volume całej sceny.

  Jak łatwo zauważyć, ta konstrukcja działa dla dowolnie wielu wymiarów (lepsza nazwa brzmiałaby np. 2^k-trees). Ale istotnie robi się strasznie koślawa dla wielu wymiarów. W praktyce używa się wersji 3D (właśnie "octree") i 2D (quadtree).

  W niektórych wersjach trójkąty (ostateczne elementy) trzymamy tylko w liściach. Zalety:

  • Dzięki temu będziemy robili testy z trójkątami tylko w liściach kolidujących z naszym testerem. Unikamy niepotrzebnych kolizji z trójkątami które "utknęłyby" w węzłach wewnętrznych.

  Wady:

  • Trójkąty są mocno (~kilkukrotnie, chociaż zależy od sceny) duplikowane w drzewie. Trzeba o tej duplikacji wiedzieć, badać ją (demo view3dscene), warto implementować mailboxy do sprawdzania kolizji (taki cache w trójkącie pamiętający wynik ostatniej kolizji).
  • Trudno usuwać trójkąty z drzewa: są w wielu liściach.

  Konstrukcja: najprościej: na początku mamy 1 węzeł = liść = root. Po prostu wkładamy elementy do liści w drzewie. Kiedy ustalona pojemność węzła (np. 20) się przepełni, zamieniamy liść na węzeł wewnętrzny z ośmiorgiem dzieci (wrzucając trójkąty do odpowiednich dzieci). Dobrze jest dodać też limit na głębokość drzewa (np. 10) żeby drzewo nie rozrosło się zanadto w dół (co grozi olbrzymim zużyciem pamięci). Ignorujemy limity "przepełnień" dla liści które osiągnęły max głębokość.

  Konstrukcja drzewa ósemkowego jest na tyle prosta że można ją robić za każdym razem w programie po wczytaniu modelu.

  Octree są popularne, używane np. przez Sauerbraten, OGRE (chociaż OGRE ma też BSP), (i mój engine :) ).

• Kd-drzewa. Drzewa binarne, każdy węzeł to płaszczyzna prostopadła do jednej z głównych OSI. W prostej wersji na poziomie 0 dzielimy wzdłuż X, na poziomie 1 wzdłuż Y, na poziomie 2 wzdłuż Z, na poziomie 3 znowu wzdłuż X etc. Chociaż można lepiej.

  Chociaż można dzielić wzdłuż środka, można dzielić też wzdłuż mediany. Można też dzielić używając przyjemniej funkcji kosztu jak Surface area heuristic, chociaż to nas raczej nie interesuje (dla potrzeb kolizji nie potrzebujemy aż takiej perfekcji).

  Kd-drzewa są generalnie świetne obliczeniowo, populatne w ray-tracerach, łatwo je skonstruować.

• Drzewa BSP. Każdy węzeł dzieli przestrzeń wzdłuż swobodnej płaszczyzny, czyli mamy uogólnienie drzew kd. Zazwyczaj płaszczyzny drzewa BSP wybieramy jako płaszczyzny trójkątów w scenie, i trzymamy odpowiedni pojedynczy trójkąt w każdym węźle wewnętrznym drzewa.

  Zasadniczy problem z drzewem BSP to że żeby było naprawdę dobre, trzeba je skonstruować offline (tzn. nie w trakcie kiedy gracz ładuje grę) i zapamiętać w pliku. W rezultacie zabawa robi się bardziej skomplikowana, i drzewo jest mało podatne na jakiekolwiek dynamiczne zmiany sceny.

  Zalety to że z drzew BSP można skonstruować np. automatyczne portale dla sceny. Patrz np. praca mag "Automatyczna dekompozycja sceny 3D na portale i sektory", by Remigiusz Żukowski z naszego ii w zeszłym roku :)

  Popularnie używane w engine'ach id Software.

• BVH (bounding volume hierarchies)

  To nie są drzewa podziału przestrzeni. Ale poza są bardzo podobne do struktur wymienionych powyżej i w zasadzie służą do tego samego, więc rozsądnie będzie omówić je tutaj.

  Idea jest prosta: liść to konkretny obiekt z naszej sceny, węzeł wewnętrzny to kolekcja węzłów. W każdym węźle pamiętamy bounding volume elementów w środku, stąd nazwa BVH. Nie ma ograniczeń na ar-ność węzłów. Nie ma też żadnych zasad na to jak nasze dzieci są położone względem siebie w przestrzeni 3D (dlatego to drzewo nie "dzieli" przestrzeni, chociaż jest w 3D). Nasze dzieci mogą nawet bez problemu nachodzić na siebie.

  Można używać dowolnych bounding volumes, chociaż tutaj rzeczywiście można eksperymentować z bardziej skomplikowanymi, jak k-DOPy. Ciaśniejsze bounding volumes mogą się tutaj opłacać, bo pozwolą obcinać duże kawałki przestrzeni 3D.

  Nie ma żadnych oczywistych metod jak zbudować BVH --- teoretycznie moglibyśmy grupować obiekty naszej sceny zupełnie bez sensu i wrzucać je do BVH. Oczywiście, w praktyce chodzi o to żeby grupować elementy które są blisko siebie, i dzięki temu minimalizować bounding volumes po drodze. Konstrukcja BVH może być zadana przez artystę 3D implicite w modelu, różne scene graphs (jak VRML/X3D) w zasadzie zadają implicite BVH sceny. Są też algorytmy do efektywnego konstruowania ładnych BVH automatycznie, odsyłam do google (TODO: link do tej pracy z sem rok temu).

  Chociaż BVH są generalnie gorsze od wszystkich powyższych drzew, ich olbrzymia zaleta to że pozwalają na dużą dynamikę sceny. Kiedy coś się zmienia, musimy tylko uaktualnić bounding volumes wzdłuż ścieżki w drzewie do liścia który się zmienia.

  Patrz także kinetic bounding volume hierarchies.

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 :) ).

• Prosta hierarchia drzew: 1 drzewo obiektów + wiele lokalnych drzew trójkątów.

  Co właściwie jest elementem naszego drzewa? Sugerowałem żeby na początku myśleć o drzewach które zawiera wszystkie trójkąty naszej sceny. Problem: typowe zmiany sceny (winda przesuwa się w górę, drzwi się obracają przy otwieraniu) powodują zmiany wielu trójkątów. Właściwie nie ma jak tego zoptymalizować kiedy podstawowywm budulcem naszego drzewa są trójkąty i liście drzewa zawierają trójkąty z różnych elementów (np. trochę trójkątów drzwi, trochę podłogi i sufitu w pobliżu).

  Stąd podstawowy pomysł: nie trzymać w drzewie trójkątów, ale obiekty naszej sceny. Definicja "obiektu" należy tutaj do nas, powinna wynikać z organizacji naszego modelu i z oczekiwań (np. to są drzwi, zapewne będą transformowane razem). Wbrew pozorom nie jest to takie trudne, większość formatów 3D dzieli scenę na jakieś obiekty i zazwyczaj projektując levele dzielimy je na dość sensowne "obiekty".

  W każdym "obiekcie" możemy teraz utworzyć lokalne drzewo, oparte na trójkątach, w lokalnych współrzędnych tego obiektu. Zalety: transformacje obiektu (rotacje, przesuwanie etc.) nie wymagają żadnych zmian w drzewach trójkątów. Trzeba tylko uaktualnić globalne drzewo obiektów, które zazwyczaj jest stosunkowo małe. Michalis tego używa z powodzeniem, działa jak marzenie :)

  Są pewne problemy, ponieważ trzeba transformować testerów pomiędzy lokalnymi a globalnymi współrzędnymi, co wymusza używanie bardziej skomplikowanych BV (zamiast AABB mamy OBB albo coś gorszego, zamiast sfery -> elipsoidę) albo zignorwanie problemu (i robienie testów kolizji z czymś nieznacznie większym). W praktyce, w prostych przypadkach zignorowanie tego problemu działa całkiem Ok.

  Notatki Michalisa o działaniu tego w moim engine.

• Hierarchie drzew --- niewiele pozostało do dodania: naturalnie możemy rozwinąć tą ideę na wiele poziomów.

• Dynamic irregular octrees (z tej strony). Skrót na stronie Michalisa wspomnianej wyżej.

  W skrócie, dodajemy/usuwamy elementy drzewa zwyczajnie, po drodze pilnując niezmienników "pojemności" w każdym węźle. Zmusza nas to do trzymania elementów tylko raz w drzewie (więc mogą "utknąć" w węźle wewnętrznym). W przypadku drzew ósemkowych, żeby zminimalizować negatywne skutki utykania, pozwalamy sobie deaktywować 1 lub 2 płaszczyzny dzielące dany węzeł. W rezultacie, nasze drzewo ósemkowe staje się miejscami drzewem czwórkowym a miejscami binarnym.

• Loose octrees (także patrz Ulrich, Thatcher w "Game Programming Gems")

Sztywne ograniczenia naszych drzew ósemkowych zmuszają nas często do przebudowy. Więc rozluźnijmy je, tak aby dzieci mogły zachodzić na siebie. Najlepiej: powiększmy rozmiar dzieci dwukrotnie. W rezultacie, rozmiar obiektu determinuje na jakim poziomie drzewa ten element się znajduje, i element zawsze wpada elegancko do dokładnie jednego węzła drzewa. Obracanie / przesuwanie elementu oznaczają tylko ewentualne przenoszenie elementu w obrębie tego samego poziomu drzewa, co można zaimplementować bardzo szybko (log pesymistycznie, ale w praktyce zazwyczaj będzie dużo szybciej, praktycznie O(1)).

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.