T (nr ramki)



Pobieranie 56.63 Kb.
Data28.04.2016
Rozmiar56.63 Kb.
KOLIZJA

Wykład 4



v = s/t,

t = const.





s


s

s


s

0 1 2


0

1

t (nr ramki)

t (nr ramki)

W zależności od prędkości obiektu może on „wejść” w obiekt statyczny lub „przejść” przez niego.


Kiedy potrzebna jest detekcja kolizji?

  1. Wykrywanie kolizji między tymi obiektami, których kolizję umożliwia aplikacja.

  2. Planowanie w którym miejscu ścieżki należy umieścić animowanego agenta aby znalazł się on z dala od innych obiektów.

Najpopularniejsza strategia: Faza rozszerzania (broad phase) odrzuca pary obiektów, które nie mogą kolidować. Następnie faza zawężania (narrow phase) determinuje, które z pozostałych par wchodzą w kolizję i znajduje przecięcia z odpowiednią dokładnością.

Taksonomia detekcji kolizji:



  1. Algorytmy fazy rozszerzania / zawężania

    • Faza rozszerzania (można stosować jedną z poniższych metod lub ich kombinację):

    • Prawa gry lub kontekst

    • Podział przestrzenny (spatial partitioning) w przestrzeni świata

    • Podział przestrzenny w przestrzeni lokalnej

    • Bryły otaczające (bounding volumes - sfery, AABB, OBB) i hierarchie brył otaczających

    • Faza zawężania

    • Test wielościan/wielościan

    • Śledzenie cech zamknięcia Lin-Canny

    • Płaszczyzny separujące

    • Metody obsługujące obie fazy

      • Hierarchie brył otaczających

      • Podział przestrzenny w przestrzeni lokalnej

      • Z-bufor

  1. Metody z jedną fazą

      • Pojedyncza metoda podziału dla przetwarzania wstępnego (np. drzewo sfer Hubbarda)

      • Popularny schemat podziału z drzewem BSP (zarówno dla renderingu jak
        i detekcji kolizji)

  1. Strategie stosowane w algorytmach czasu rzeczywistego

  • Spójność przestrzenno/czasowa (spatial/temporal coherence) – obiekty mają tendencję do zajmowania tego samego obszaru przestrzeni z ramki do ramki.

  • Obliczenia wstępne (pre-calculation) – inwestycja w obliczenia wstępne lub fazę off-line może odciążyć obliczenia w czasie rzeczywistym. Podział przestrzeni i bryły otaczające
    z definicji wymagają obliczeń wstępnych.


Kula. Jej wyznaczenie wymaga więcej obliczeń niż dla bryły otaczającej typu AABB - najczęściej znajduje się środek otaczanej bryły i oblicza promień. Zaleta: największe możliwe uproszczenie testu przecięcia. Wada: możliwy duży zbyteczny koszt obliczeń fazy zawężania.


Prostopadłościan niezorientowany (AABB). W celu wyznaczenia bryły przegląda się kolejne wierzchołki otaczanego obiektu szukając minimalnych i maksymalnych wartości (x,y,z). Zaleta: lepsze dopasowanie objętości. Wady: konieczność tworzenia bryły otaczającej po każdej reorientacji obiektu i dłuższy czas obliczeń przecięć niż dla kuli.


Prostopadłościan zorientowany (OBB). Konstruowany jest z prostopadłościanu, który skalujemy i obracamy tak aby zminimalizować różnicę objętości pomiędzy prostopadłościanem
i obiektem otaczanym. Zalety: lepsze dopasowanie objętości niż brył poprzednich, analogicznie jak dla kuli objętość bryły otaczającej nie zależy od kąta o jaki obrócono otaczaną bryłę (OBB może być obliczone w fazie obliczeń wstępnych i nie musi być zmieniana przy reorientacji obiektu). Wada: zwiększenie kosztu wyliczenia przecięć w stosunku do bryły AABB.


Prostopadłościan zorientowany ścięty (k-dop). Konstruowana analogicznie jak bryła OBB. Dodatkowo bryła otaczająca jest ścinana z kierunków głównych osi tak, aby była jeszcze bardziej dopasowana do bryły otaczanej (najczęściej składa się z par równoległych płaszczyzn). Zalety: najlepsze dopasowanie objętości. Wady: czasochłonne obliczanie przecięć.



        1. Hierarchie brył otaczających



Najpierw pojedyncze obiekty otaczamy bryłami otaczającymi, następnie odpowiednio grupujemy je. Powtarzamy tę czynność aż do stworzenia grupy obejmującej wszystkie obiekty w scenie.
Zalety: Jeśli promień nie przetnie się z rodzicem to nie przetnie się z żadnym jego potomkiem.

Metody budowy hierarchii

Bez względu na wybraną metodę przed rozpoczęciem procesu renderingu musimy otoczyć pojedyncze obiekty bryłami otaczającymi.



Metoda dół-góra. Najpierw pod uwagę bierzemy pojedyncze obiekty otoczone odpowiednimi bryłami otaczającymi. Obiekty te odpowiednio grupujemy, po czym operację tą powtarzamy aż do stworzenia grupy zawierającej wszystkie obiekty. Cała hierarchia musi być stworzona przed rozpoczęciem renderingu.

Przykład 1: Ołówki.

Przykład 2: Kwiaty w wazonie stojącym na stole. Najpierw otaczamy pojedyncze obiekty: każdy kwiatek, wazon i stół. Po czym grupujemy ze sobą wszystkie kwiatki. Kolejnym piętrem
w hierarchii będą kwiatki wraz z wazonem. Ostatnim będzie grupa składająca się ze wszystkich obiektów sceny.

Metoda góra-dół. Rozpoczynamy od otoczenia wszystkich obiektów w scenie bryłą otaczającą,
po czym dzielimy ją na coraz mniejsze fragmenty. Powtarzamy tę czynność do momentu gdy wszystkie bryły otaczające będą zawierać tylko po jednym obiekcie.

Przed renderingiem wszystkie obiekty w scenie muszą być otoczone jedną bryłą otaczającą. Następnie możemy tworzyć hierarchię w locie, tzn. gdy któryś z promieni testujących trafi w bryłę otaczającą zawierającą niepodzieloną grupę obiektów to tworzymy hierarchię. Może to przyspieszyć rendering, ponieważ promienie testujące omijają część obiektów sceny.



Metoda minimalizująca objętość. Najważniejszym czynnikiem jest różnica między objętością bryły otaczającej a objętością otaczanych obiektów w celu zmaksymalizowania liczby promieni nie przecinających brył otaczających. Skutkuje to zwiększeniem kosztu obliczeń przy tworzeniu hierarchii i przy obchodzeniu drzewa. Hierarchia z ołówkami nie spełnia założeń tej metody. Dla obiektów o kształcie ołówków należałoby użyć bryły otaczające typu prostopadłościan zorientowany albo jeszcze lepiej prostopadłościan zorientowany ścięty.

3. Obliczanie przecięć dla kolizji
3.1. Kolizja z kulą

Punkt - np. punkt położenia kamery - przesuwa się po ścieżce od Pt-1 do Pt. Obiekt znajduje się wewnątrz bryły otaczającej – kuli o promieniu r.

Równanie kuli o środku w punkcie S(l,m,n):

(4.1)

(4.2)

M < 0 – kolizja (przypadek C, punkt Pt wewnątrz kuli)

M = 0 – kolizja lub kontakt (przypadek B, punkt Pt na powierzchni kuli)

M > 0 – nieokreślony (przypadek A, tzn. punkt Pt na zewnątrz kuli)

Aby rozstrzygnąć przypadek A potrzebne jest równanie odcinka ścieżki Pt-1, Pt leżącej na promieniu:



, gdzie 0 w  1 (4.3)
lub

Podstawiając (4.3) do (4.1) otrzymujemy:



(4.4)

Równanie (4.4) jest równaniem kwadratowym , (4.5)

gdzie: a =(KK), b=2(KD), c=(DD) – r2, D=(Pt-1  S). (4.6)

Możliwe rozwiązania w równania (4.5) determinuje wartość : (4.7)

 < 0 – brak przecięcia promienia z kulą, a więc brak kolizji,

 = 0 – promień styczny do kuli (); jeżeli w = 1 to jest kontakt,

 > 0 – promień przecina kulę (); jest kolizja jeżeli przynajmniej dla jednego w
spełniony jest warunek 0  w  1, w przeciwnym przypadku brak kolizji.

Normalna N w punkcie przecięcia Pw:



. (4.8)

3.2. Kolizja z płaszczyzną

Równanie płaszczyzny:



Ax + By + Cz + D = 0 lub NP(x,y,z) +D = 0, (4.8)

gdzie: N=[A, B, C] – normalna do płaszczyzny,


P(x,y,z) – dowolny punkt na płaszczyźnie.

Stąd D =  NP(x,y,z). (4.9)

Badamy znak (4.10)

3.3. Kolizja z wielokątem

Etap 1: Przecięcie ścieżki z płaszczyzną wielokąta

Wektory rozpinają płaszczyznę, a ich iloczyn wektorowy jest normalną N płaszczyzny:

(4.11)

Wtedy dla dowolnego punktu P płaszczyzny wektor


(PP0) jest prostopadły do N. Stąd równaniem płaszczyzny jest N(PP0) =0, a więc D = – NP0.

Badamy znak zgodnie z warunkami (4.10). Jeżeli Dt-1 Dt > 0 to koniec obliczeń (brak kolizji).

W przeciwnym przypadku przechodzimy do etapu 2.

Etap 2. Przecięcie z wielokątem

Punkt przecięcia płaszczyzny z promieniem będzie punktem przecięcia promienia z wielokątem pod warunkiem, że znajduje się wewnątrz wielokąta.

Podstawiając punkt P(w) zdefiniowany równaniem promienia (4.3) do równania płaszczyzny (4.8) otrzymujemy parametr w promienia


w punkcie przecięcia:

(4.12)

Zależność ta nie ma sensu gdy NK = 0, tzn. gdy promień i płaszczyzna są równoległe.

Mając w można z równania promienia (4.3) obliczyć P(w). Teraz należy sprawdzić, czy punkt ten leży wewnątrz wielokąta.



Wielokąt jest zdefiniowany przez zbiór wierzchołków {Pi}={[xi, yi, zi]}, i=0,1,2,...,n-1.

Prosta {Pi, Pi+1} dzieli płaszczyznę na dwie części. Jeżeli równaniem prostej jest:

Au +Bv + C = 0, (4.13)

to wszystkie punkty (u,v) znajdujące się po dodatniej stronie prostej spełniają warunek:



Au +Bv + C > 0. (4.14)

Aby uprościć obliczenia rzutuje się prostopadle wierzchołki wielokąta na jedną z trzech płaszczyzn układu współrzędnych, tą dla której normalna N płaszczyzny ma największą składową (otrzymujemy wtedy największą powierzchnię rzutu):



. (4.15)

Wtedy równanie zrzutowanej prostej ma postać:



, (4.16)

gdzie: ,



, (4.17)

.

3.4. Kolizja z trójkątem

Badanie przecięć między ścieżką punktu, a trójkątem


(wg Moore i Wilhelms, 1987, 1988).

(4.18)

gdzie: w – parametr ścieżki, u, v – parametry trójkąta.

Ścieżka punktu przecina trójkąt, jeśli rozwiązania (4.18) spełniają nierówności:

0  w  1, u  0 oraz v  0, u + v 1. (4.19)



3.5. Kolizja z prostopadłościanem AABB

Definicja promienia jak w (4.3):

Stąd w = (PPt-1) / K. (4.20)

Dla każdej pary płaszczyzn można obliczyć dystans wzdłuż promienia do pierwszej napotkanej płaszczyzny wnear (tzn. bliższe przecięcie) i do drugiej (wfar - dalsze przecięcie). Otrzymujemy trzy takie pary. Aby sprawdzić czy promień przecina prostopadłościan porównuje się większą z wartości wnear z mniejszą z wartości wfar.



Najdogodniejszy algorytm bierze pod uwagę dystans między punktami przecięcia pary równoległych płaszczyzn jako przedziałów.

Dla każdej pary płaszczyzn prostopadłościanu oblicza się dystans w, np. odległości w1x, w2x, liczone wzdłuż promienia od jego początku do przecięcia z płaszczyznami x=const. prostopadłościanu:



. (4.21)

Szukamy która z nich jest wxmin, a która wxmax. Analogicznie postępujemy z pozostałymi parami płaszczyzn. Mamy dwa zbiory: , .

Największa wartość ze zbioru wmin daje szukane wnear (tzn. największe bliższe przecięcie), najmniejsza wartość ze zbioru wmax daje wfar (tzn. najmniejsze dalsze przecięcie).

Jeżeli wnear > wfar to promień nie może przeciąć prostopadłościanu.

Algorytm może skończyć obliczenia na płaszczyźnie y.


  1. Detekcja kolizji w fazie rozszerzania


4.1. Kolizja brył otaczających AABB
Dwie bryły AABB będą się przecinać jeżeli pary ich odcinków (si, ei) będą się zaplatać wzdłuż wszystkich głównych osi (X, Y, Z).

Test wykonywany jest w przestrzeni jednowymiarowej.

Algorytm I-COLLIDE (Baraff 1990, Cohen et al., 1995).

Minimalne (si) i maksymalne (ei) współrzędne każdej bryły AABB są zapamiętywane w posortowanej liście (od wartości najmniejszej do największej). Następnie lista jest porządkowana (sweep)


i tworzona jest lista aktywnych przedziałów I.



  1. Gdy napotykamy wartość si wszystkie przedziały aktywnej listy są wyjściowe jako zaplatające się z i-tym przedziałem, i przedział Ii jest dodawany do listy.

Np. gdy napotkamy s1 aktywna lista obejmuje przedziały I3, I6. Przedział I1 jest uznawany za zaplatający się z nimi, dodawany do listy i algorytm jest kontynuowany.

  1. Gdy napotykamy wartość ei przedział Ii jest usuwany z aktywnej listy.

Np. gdy napotkamy e1 to usuwany jest przedział I1.

W najgorszym przypadku złożoność obliczeniowa algorytmu jest O(n log n+k), O(k) – wyjście wszystkich zapleceń, O(n) – porządkowanie. Optymalna dla wstępnego rozwiązania (Baraff, 1990).

Jeżeli posortowana lista nie nie zmienia się znacznie w następnych krokach czasowych, to można
w kolejnej ramce wystartować z listą z poprzedniego kroku. Elementy są przesuwane w kierunku do poczatku listy tak długo, aż napotyka się mniejszy element (Cohen et al., 1995).




4.2. Kolizja brył otaczających OBB
Klasyczny algorytm detekcji kolizji miedzy dwiema bryłami OBB wymaga testów krawędź-ściana (tzn. czy krawędź jednej bryły przecina ściany drugiej i vice versa). Potrzebujemy 144 testy = 12 krawędzi  6 ścian  2 bryły.

Algorytm Gottchalk et al., 1996

Załóżmy, że dwie bryły OBB rzutujemy na dowolną oś. Jeżeli odcinki między zrzutowanymi wierzchołkami nie zaplatają się to bryły nie mogą się przecinać.

Weźmy pod uwagę, że jeżeli bryły OBB są rozłączone to mogą być rozdzielone przez płaszczyznę, która zawiera jedną z ich ścian (a). Jeśli OBB są rozłączone ale nie mogą być rozdzielone przez płaszczyznę ściany, to mogą być rozdzielone przez płaszczyznę równoległą do krawędzi każdego prostopadłościanu (c).

Odseparowanie brył OBB obejmuje testowanie 15 potencjalnych osi (trzy orientacje ścian każdej bryły + 9 kombinacji par krawędzi).
Zakładamy, że oś L przechodzi przez środek bryły A.

D – wektor translacji brył.

L – wektor kierunkowy (jednostkowy) osi.

A1, A2, A3, B1, B2, B3 - wektory kierunkowe

a1, a2, a3, b1, b2, b3 - wymiary brył OBB

Rzut „promienia” (połowa średnicy) bryły OBB:



(4.22)

Bryły OBB nie przecinają się (brak kolizji) jeżeli:



. (4.23)

Gdy 15 potencjalnych osi jest zdefiniowanych w stosunku do jednego z ruchomych obiektów, to przesuwają się one z tym obiektem. Jeżeli założymy, że obiekt porusza się wzdłuż prostej ze stałą prędkością między ramkami (s=const.), prędkość jego odcinków można łatwo obliczyć,


i możemy rozstrzygnąć czy i kiedy ruchomy obiekt będzie kolidował z obiektem statycznym aktualnie z nim porównywanym.


  1. Detekcja kolizji w fazie zawężania


5.1. Test wielościan / wielościan
Weźmy pod uwagę dwa wielościany: P i Q.

  1. Sprawdzamy, czy wierzchołki Q leżą wewnątrz P i odwrotnie.

  2. Sprawdzamy, czy krawędzie Q przecinają P i odwrotnie.


Warunek kolizji 1.

Jeżeli wierzchołek vi bryły Q znajduje się po wewnętrznej stronie każdej ściany bryły P to leży wewnątrz tej bryły:



dla każdego j, (4.24)

gdzie jest rzutem wektora na wektor jednostkowy nj.

Większość systemów poprzestaje na sprawdzaniu tego warunku.
Warunek kolizji 2.

Krawędź obiektu Q przecina płaszczyznę k w której leży ściana obiektu P, jeżeli odległości d dwóch wierzchołków krawędzi od płaszczyzny k zmieniają znak.



, , (4.25)

(4.26)

Stąd punkt przecięcia: (4.27)

Obliczając przecięcia promienia krawędzi z wszystkimi płaszczyznami dostajemy zbiór przecięć. Odrzucamy te w których w jest spoza przedziału <0,1>. Pozostałe jako potencjalne przecięcia krawędzi ze ścianą porządkujemy od najmniejszej do największej wartości w. Dwa kolejne przecięcia mogą być wejściem i wyjściem krawędzi z obiektu. Jeżeli punkt środkowy pary leży wewnątrz obiektu (warunek 1) to jest kolizja (Moore i Wilhelms, 1988).


Odległość d wierzchołka v od płaszczyzny:

Równa jest rzutowi wektora (v u) na znormalizowaną normalną płaszczyzny n = N/||N||, gdzie u - dowolny punkt na płaszczyźnie.

Stąd


lub




5.2. Płaszczyzny separujące


Metoda użyteczna dla ruchomych obiektów, wykorzystuje spójność czasową sąsiednich ramek (Baraff, 1990).

Płaszczyzna separująca jest związana z ruchomym obiektem (szary)
i porusza się razem z nim. Obiekt przemieszcza się w kierunku statycznego obiektu (biały).

Tak długo jak płaszczyzna separująca nie jest w kontakcie z drugim obiektem lub nie przecina go (ramki 1, 2) utrzymujemy ten sam separator. Aby sprawdzić, czy płaszczyzna jest w dalszym ciągu separatorem sprawdzamy położenie wierzchołków brył względem płaszczyzny.

Gdy test nie jest pozytywny (ramka 3) obliczany jest nowy separator na drugim obiekcie, zawierający punkt kontaktu. Aby znaleźć punkt kontaktu należy porównać tylko te ściany, krawędzie lub wierzchołki, które są koincydentne ze starym separatorem.


  1. Metody obsługujące obie fazy


6.1. Bufor głębokości
Szukamy wartości głębokości w której występuje maksymalna penetracja obiektu A przez obiekt B i odpowiadającego jej piksela [i,j].

1. Rasteryzuj obiekt A do Z-bufora, aby otrzymać wartości Zmin (zwykły warunek dla Z-bufora) i Zmax.

2. Rasteryzuj obiekt B:

ZBmax = 0

Jeżeli (Zmin  ZB  Zmax) to kolizja w tym pikselu

Jeżeli (ZB  ZBmax) to ZBmax = ZB



Max_penetracja = [i,j]







©absta.pl 2016
wyślij wiadomość

    Strona główna