Co to są „pola odległości” i jak mają one zastosowanie do wykrywania kolizji?

Kiedy natknąłem się na „pola odległości”, szukałem skutecznych metod wykrywania kolizji w scenie z obiektami zarówno statycznymi, jak i dynamicznymi.

Próbowałem poszukać i zrozumieć tę koncepcję, ale mogłem znaleźć tylko artykuły napisane w bardzo złożonym języku. Czy ktoś może wyjaśnić prostymi słowami, jakie są pola odległości i jak można je wykorzystać do wykrywania kolizji?

Pole odległości ( lub transformacja odległości lub mapa odległości ) to struktura siatkowa, w której każda komórka w siatce reprezentuje najkrótszą odległość od tej komórki do komórki z pewnymi innymi właściwościami. Najczęściej ta „inna właściwość” jest komórką graniczną, taką jak ściana, na którą gracz nie może przejść, lub powierzchnia siatki.

Pola odległości mają wiele zastosowań. Można sobie wyobrazić, na przykład, w jaki sposób można je wykorzystać do wdrożenia wskazówek dotyczących ruchu (poprzez tworzenie map odległości do niebezpiecznych lub pożądanych obiektów i podejmowanie przez nich decyzji dotyczących ruchu).

Jednak konkretnie zapytałeś o kolizję. Używanie pól odległości do wykrywania kolizji między dwoma ruchomymi obiektami może szybko stać się raczej nieefektywne, ponieważ odbudowa pól odległości może stać się bardzo powolna wraz ze wzrostem zasięgu pola (szczególnie w 3D, chociaż metody poprawy czasu generowania są przedmiotem badań ).

Kolizja pola odległości jest zatem wykorzystywana głównie do wykrywania zderzenia obiektu dynamicznego ze statycznym. Najczęściej widziałem to w wykrywaniu kolizji tkanin (lub innych odkształcalnych) obiektów z innymi stałymi obiektami w scenie .

Zasadniczo osiąga się to poprzez zastosowanie podpisanego pola odległości dla obiektu statycznego, gdzie jeden znak (często ujemny) reprezentuje komórkę wewnątrz siatki, a drugi (oczywiście często dodatni) reprezentuje komórkę na zewnątrz siatki. Cząstki siatki tkaniny można przekształcić w lokalną przestrzeń siatki statycznej, a pozycje „przed” i „za” cząstki podczas danego etapu symulacji tkaniny można sprawdzić względem pola odległości w celu ustalenia, czy znak się zmienił (i dlatego nastąpiła kolizja). Jest to na przykład metoda omówiona w artykule z 2003 r. Dotyczącym symulacji tkanin .

Zauważ, że nie sugerowałbym używania pól odległości jako jedynej metody wykrywania kolizji. Mogą być dość wydajni w tym, w czym są dobrzy, ale nie są we wszystkim dobrzy. Najlepszym sposobem na skuteczne wykrywanie kolizji jest często stosowanie wielu metod, hierarchicznie, ze zwiększoną precyzją podczas przechodzenia w dół hierarchii.

Co to są pola odległości?

W geometrii i grafice komputerowej, a także w przetwarzaniu obrazu, pole odległości (w prostych słowach) jest etykietą na każdej komórce (piksel w przetwarzaniu obrazu) z odległością najbliższego obiektu wielokąta lub piksela o specjalnych właściwościach w przetwarzaniu obrazu .

Innymi słowy, jest to etykieta dla każdej komórki, która ma wartość najbliższego obiektu ze specjalną właściwością zdefiniowaną przez mapę. Obiekt różni się w zależności od aplikacji.

Powyższy obraz zawiera mapę odległości dla pikseli brzegowych. Zauważ, jak każdy piksel zawiera odległość do najbliższego piksela granicznego. Odległość jest obliczana na podstawie odległości na Manhattanie.

Istnieją różne sposoby obliczania odległości, typowe podejścia obejmują:

• Odległość Manhattan (zwykle stosowana w przetwarzaniu obrazu).
• Odległość euklidesowa .

Jak to ma zastosowanie w wykrywaniu kolizji?

Utrzymując mapę odległości dla obiektów w scenie, możesz sprawdzić, czy dwa obiekty kolidują na podstawie tamtej odległości. Niestety utrzymanie takiej mapy jest drogie. Jest to zwykle stosowane w przecinających się obiektach, takich jak symulacje tkanin, w których mapy odległości mogą być utrzymywane i aktualizowane bardziej wydajnie ze względu na naturę obiektu.