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 edytuj

Metoda brył brzegowych edytuj

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 edytuj

  • 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 edytuj

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 edytuj

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 edytuj

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ż edytuj