Wykrywanie kolizji

Wykrywanie kolizji – grupa 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ę jakieś 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ą stwierdzać wyłącznie czy ruch jest możliwy, zwykle jednak wymagana jest wiedza, z którym obiektem następuje kolizja, a także w którym punkcie przestrzeni będzie miała miejsce. W przypadku symulacji komputerowych, wykonywane są one w dyskretnych chwilach czasu, dlatego algorytmy wykrywania kolizji pozwalają na precyzyjne wyznaczenie jej momentu – znana jest dokładna wartość numeryczna czasu 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 obiekty.

Klasyfikacja technik wykrywania kolizji

Metoda brył brzegowych

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

Typy brył brzegowych

  • Bounding sphere (ang. sphere – kula) w komputerowej grafice 3D, to bryła będąca kulą, która w uproszczony sposób przedstawia jak najmniejszą przestrzeń, w której całkowicie mieszczą się dane obiekty. Ponadto obiekt może zostać otoczony kilkoma takimi 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.
    • AABB (axis-aligned bounding box) – w przypadku kiedy bounding box umieszczony jest zgodnie z osiami układu współrzędnych, w którym wyrażony jest obiekt.

Hierarchie brył brzegowych

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

Metoda promienia

Polega ona na zdefiniowaniu na obiekcie miejsc zaczepienia wektora promienia oraz na zdefiniowaniu jego kierunku i zwrotu. Kolizje można rozpatrywać na dwa sposoby: poprzez obliczenie odległości punktu zaczepienia promienia od siatki obiektu, z którym sprawdzana jest kolizja lub sprawdzenie 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 wykrywania kolizji między obiektami, jednak jej złożoność obliczeniowa jest ogromna.

Mapa wysokości

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.

Zobacz też