Wykrywanie kolizji

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Wykrywanie kolizji — nazwa grupy algorytmów stosowanych w grafice komputerowej i symulacjach komputerowych służących znajdowaniu ograniczeń ruchu w scenach dwu- i trójwymiarowych. Najogólniej, algorytm wykrywający kolizję odpowiada na pytanie, czy przemieszczenie jakiegoś obiektu w danym kierunku jest możliwe, czy może na drodze ruchu znajdują się przeszkody, tj. inne obiekty ruchome lub nieruchome. W symulacjach ciał odkształcających się (np. tkanin) należy również wykrywać kolizje pomiędzy różnymi fragmentami tego samego obiektu.

W zależności od potrzeb algorytmy mogą wyłącznie stwierdzać, czy ruch jest możliwy; zwykle jednak potrzebna jest wiedza, z którym obiektem następuje kolizja, a także w którym punkcie przestrzeni. Ponadto symulacje komputerowe wykonywane są w dyskretnych chwilach czasu, algorytmy wykrywania kolizji wyznaczają także dokładny (znamy jego dokładną wartość numeryczną) czas kolizji.

W wielu trójwymiarowych grach komputerowych (np. Quake, Unreal) możliwe jest wyłączenie wykrywania kolizji, dzięki czemu gracz przechodzi przez ściany, podłogi, skrzynie i inne przedmioty.

Klasyfikacja technik wykrycia kolizji[edytuj | edytuj kod]

Metoda brył brzegowych[edytuj | edytuj kod]

Wykrywanie kolizji zachodzących na obiektach stworzonych ze skomplikowanych siatek jest niezwykle skomplikowane i złożone obliczeniowo. Aby uprościć kształt obiektu zamyka się go w tzw. bryle otaczającej. Jest to najmniejsza bryła w którą można wpisać cały obiekt. Wykrycie kolizji sprowadza się wówczas do sprawdzenia czy kolizja zachodzi między dwoma obszarami otaczającymi.

Typy brył brzegowych[edytuj | edytuj kod]

  • Bounding sphere (ang. sphere – kula – w komputerowej grafice 3D bryła w uproszczony sposób przedstawiająca jak najmniejszą przestrzeń, w której całkowicie mieszczą się dane obiekty. Dodatkowo obiekt może zostać otoczony kilkoma obszarami w celu lepszego przybliżenia jego kształtu.
  • Bounding box (ang. box – pudełko) to jak najmniejszy prostopadłościan kompletnie otaczający dany obiekt. Dodatkowo bounding box może być:
    • OBB oriented bounding box – w przypadku kiedy jego pozycja jest dowolna.
    • AAB axis-aligned bounding box – w przypadku kiedy Bounding box umieszczony jest równo z osiami układu współrzędnych w którym wyrażony jest obiekt.

Hierarchizacja brył brzegowych[edytuj | edytuj kod]

Bryły brzegowe można dodatkowo pogrupować, w nadrzędne bryły brzegowe. Wtedy kolizja sprawdzana jest najpierw z bryłami znajdującymi się wyżej w hierarchii.

Metoda promienia[edytuj | edytuj kod]

Polega ona na zdefiniowaniu na obiekcie miejsc zaczepienia wektora promienia oraz na zdefiniowaniu jego kierunku i zwrotu. Kolizje możemy rozpatrywać na dwa sposoby: poprzez obliczenie odległości punktu zaczepienia promienia od siatki obiektu z którym sprawdzana jest kolizja lub sprawdzenia odległości z obszarem otaczającym obiekt. Kolizja zachodzi w momencie, kiedy wektor wyznaczony przez punkt zaczepienia i punkt przecięcia jest zerowy. Jest to najdokładniejsza metoda wykrycia kolizji między obiektami, jednak jej złożoność obliczeniowa jest ogromna.

Mapa wysokości[edytuj | edytuj kod]

Polega na zdefiniowaniu mapy wysokości (najczęściej jest to tekstura) obiektu, z którym ma być sprawdzana kolizja. Po wygenerowaniu w/w mapy nanoszony jest na nią obiekt kolidujący. Znając wysokość na której znajduje się obiekt i przeszukując mapę (np. czy wysokość i pozycja obiektu pokrywa się z pozycją koloru odpowiadającemu danej wysokości) możemy określić, czy kolizja zachodzi, czy też nie.