Najlepszy algorytm skutecznego wykrywania kolizji między obiektami

Question

Jestem zdezorientowany. Nie mylić, tak bardzo, że nie chcemy robić 6 programów testowych, aby zobaczyć, który algorytm jest najlepszy. Pomyślałem więc, że poproszę moich przyjaciół ekspertów tutaj w SO, aby dać mi korzyści z ich doświadczenia.

Scenariusz to scena 3d o potencjalnie dość dużym obszarze w porównaniu do rozmiarów znajdujących się w niej obiektów. Na scenie znajdują się potencjalnie tysiące obiektów. Obiekty różnią się wielkością od dziesiątych części jednostki do około 10 jednostek, ale nie większych (lub mniejszych). Obiekty są skupione razem, ale te klastry mogą potencjalnie pojawić się w dowolnym miejscu sceny. Wszystkie obiekty są dynamiczne i poruszające. Klastry mają tendencję do poruszania się razem, ale kiedy robią, ich prędkości mogą nie być takie same przez cały czas. Uwzględnia się również geometrię statyczną. Chociaż istnieje duża liczba obiektów dynamicznych, w scenie znajdują się również pewne obiekty statyczne (obiekty statyczne są zwykle o jeden lub dwa rzędy wielkości większe niż obiekty dynamiczne).

Teraz potrzebuję struktury danych przestrzennych do efektywnego wykrywania kolizji dla wszystkich przedmiotów na scenie. Byłoby wspaniale, gdyby algorytm obsługiwał również zapytanie o widoczność dla potoku renderowania. Dla uproszczenia przyjmijmy, że detekcja kolizji ma tu charakter szerokopasmowy (tzn. Wszystkie dynamiczne obiekty są po prostu doskonałymi sferami).

Tak, w moich badaniach można użyć jednego z:

(1) Octree (2) Kontenery Octree (3) Liniowy Octree (+ luźny) (4) KD Drzewo (5) BSP Drzewo (6) Hashing

Do tej pory (6) jest jedynym, którego próbowałem. W rzeczywistości jest całkowicie znakomity pod względem szybkości (kolizja 8192 elementów została sprawdzona poniżej 1 ms w moim systemie), jeśli obiekty w scenie są średnio równomiernie rozłożone. Nie jest to taki dobry algorytm, jeśli wszystkie obiekty zostaną scalone na mniejszy obszar, co moim zdaniem jest możliwe.

Czy ktoś ma pewien wgląd w to, do którego użyć lub jakąkolwiek sztuczkę, którą mogę użyć, aby przyspieszyć działanie? Myślę, że cokolwiek się stanie, mogę po prostu użyć osobnego drzewa BSP dla geometrii statycznej. Przypuszczam, że dynamiczne "sfery" są tym, co mnie najbardziej interesuje. Uwaga: brak CUDA, tylko CPU: p.

Dzięki

EDIT: Ok, dzięki Floris, znalazłem więcej informacji o AABB Drzew. Tutaj jest stara dyskusja na temat GameDev: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Wygląda na dobry kompromis.

Końcowa edycja: Postanowiła nie odkrywać na nowo koła. Jest możliwe, że biblioteka fizyki pocisków zrobi to wszystko dla mnie (ma w niej drzewo AABB, prawdopodobnie również bardzo dobrze zoptymalizowane).

Answer 1

Świetne pytanie.

Zasadniczo mają złożoną kompromis pomiędzy:

1. Szybkości kompletnego fazie wykrywania kolizji
2. narzut aktualizację/utrzymanie struktury danych jako obiekty poruszać

Zła wiadomością jest to, że z tego powodu nie ma "idealnej" odpowiedzi - będzie ona naprawdę zależeć od wielu różnych czynników, które są unikalne w danej sytuacji. Przykładowo, BSP są bardzo szybkie, gdy są wstępnie obliczane z dużą ilością statycznej geometrii planarnej, co wyjaśnia, dlaczego były tak powszechne we wczesnych grach FPS.

Moje osobiste przypuszczenie jest takie, że luźne drzewo AABB (Axis Aligned Bounding Box) z rozsądną liczbą obiektów (5-10?) W każdej dolnej ramce ograniczającej poziom będzie prawdopodobnie najlepiej działać w twoim przypadku. Powody:

• Masz dość dużą/rzadką przestrzeń z skupiskami obiektów. Drzewa AABB są na to dobre, ponieważ można wyciąć wiele poziomów, które w przeciwnym razie byłyby potrzebne.
• Zakładasz idealne kule. Testy kolizji sfera-kula są bardzo tanie, więc możesz łatwo pozwolić sobie na wykonanie 10-45 testów dla każdego dolnego węzła poziomu. Zasadniczo N^2 jest w porządku dla małych wartości N :-)
• Osiowanie osi sprawia, że ​​aktualizacja drzewa jest o wiele prostsza, a testy przecięć znacznie tańsze niż w przypadku większości alternatyw. Ponieważ zakładasz obiekty o mniejszej sferyczności, nie sądzę, byś zyskał wiele ze zorientowanych obwiedni (które tylko dają ci przewagę, jeśli masz dużo długich/cienkich kształtów pod śmiesznymi kątami).
• Pozwalając, aby obwiednie były luźne i zawierały rozsądną liczbę obiektów, zmniejsza się prawdopodobieństwo, że ruch dowolnego pojedynczego obiektu spowoduje usunięcie go poza granice AABB. O ile tak się nie stanie, nie trzeba aktualizować drzewa. Pozwoli to zaoszczędzić wiele czasu na aktualizację drzewa. Kiedy tak się stanie, przedłuż granicę z pewnym marginesem, aby nie trzeba od razu ponownie ponownie rozciągać kolejnej klatki - pamiętaj, że większość ruchu ma tendencję do kontynuowania w tym samym kierunku dla kilku klatek!

Przepraszamy za lekko wełnianą odpowiedź, ale mam nadzieję, że daje to kilka przydatnych pomysłów/rzeczy do rozważenia!

Answer 2

Wiele silników fizycznych używa AABBTree (Drzewo Bounding Bounding Tree), dzieli obiekt na mniejsze i mniejsze kawałki. Możesz uzyskać bardzo dobre wykrywanie kolizji przy użyciu tego algorytmu. To drzewo wygląda trochę jak Octree.

OOBBTree (Orientated Bounding Box) będzie lepszą częścią licznika.