Jaki jest dobry algorytm do wykrywania kolizji między ruchomymi sferami?

27

Jeśli (w celu wykrywania kolizji) obiekty 3D są reprezentowane w grze przez kule, to jaki jest dobry algorytm do wykrywania kolizji między kulami?

Jeśli każdy obiekt ma pozycję z ostatniej klatki i nową (pożądaną) pozycję, co jest dobrym algorytmem, który zidentyfikuje kolizje, w których kule nie przecinały się w poprzedniej klatce, i nie mogą przecinać się w drugiej klatce, ale przecięli się gdzieś pomiędzy?

collision-detection kevin42
źródło

Odpowiedzi:

18

Zasadniczo szukasz śladu.

Ta strona prawdopodobnie Ci pomoże: http://www.realtimerendering.com/intersections.html

Ruchoma kula / Kula: (lokalizacja) Dodaj promień ruchomej kuli do kuli statycznej i traktuj poruszającą się kulę jak promień. Użyj tego promienia, aby wykonać przecięcie promień / kula. Zobacz Gomez; Schroeder dla kodu (artykuł ma błąd w wyprowadzeniu, kod jest w porządku); i RTR2, str. 622.

Tetrad
źródło
1
To nie działa, jeśli obie kule się poruszają (nawet jeśli zrobisz to dwa razy). Wydaje mi się, że musiałbyś najpierw sprawdzić odległość między liniami obejmującymi ruch a i jednym obejmującym ruch b, a jeśli jest to mniej niż promień a + promień b, możliwe jest zderzenie. Następnie sprawdziłbym, gdzie jest ten punkt w czasie dla kuli a, a gdzie dla kuli b, czy czasy się zbliżają. Jeśli tak, sprawdziłbym prędkość względem odległości w tym punkcie, jeśli nadal jest możliwe kolizje, zrobiłbym stopniowe udoskonalenie.
Kaj,
15
W rzeczywistości tak jest, po prostu musisz uczynić ruch względnym. Więc jeśli obie kule się poruszają, po prostu odejmij prędkość jednej z nich od obu, aby uzyskać jedną „ruchomą” sferę i jedną „stacjonarną”. Następnie możesz użyć powyższego.
Tetrad,
8

Użyj testu wobulacji, jak pokazano w tym artykule Gamasutra.

Firas Assaad
źródło
4

Z czubka mojej głowy:

  1. Utwórz dwa segmenty linii od środka każdego koła, od którego zaczął się do miejsca, w którym się przesunął w tym kroku czasu.
  2. Znajdź minimalną odległość między tymi dwoma segmentami linii; jak wyjaśniono tutaj .
  3. Jeśli odległość ta jest mniejsza lub równa promieniu pierwszego koła plus drugiego, wówczas zderzyły się; w przeciwnym razie nie.

I to wszystko. Spodziewałbym się, że będzie to dość szybkie.

Robert Massaioli
źródło
1

Oto kolejny fajny artykuł o Gamasaturze .

Mateen Ulhaq
źródło
1
Zdaję sobie sprawę, że to 7 lat później, ale ta odpowiedź to tylko link. Na szczęście link wciąż żyje, ale gdyby tak nie było, twoja odpowiedź ... nie byłaby odpowiedzią.
Draco18,
0

Mówiąc jak ktoś, kto to zrobił: nie warto się męczyć . O ile Twój projekt gry tego absolutnie nie potrzebuje i prawie na pewno nie będzie, poświęcisz znacznie więcej wysiłku na zamiatanie, niż się spodziewasz. I będzie wolniej niż chciałeś.

ZorbaTHut
źródło
Mógł tworzyć grę w bilard dla wszystkich, których znasz.
Kaj,
Jeśli tworzył grę w bilard, to „projekt gry tego absolutnie potrzebuje” .
deft_code
Masz rację, nie wymyślaj koła na nowo . Ale dla ćwiczenia może być tego warte.
user712092
4
Nie zgadzam się z bezpośrednim zniechęceniem jako odpowiedzią .
bobobobo
Zgadzam się z @bobobobo, pytanie nie brzmi, czy warto, czy nie, przyszły użytkownik, który zobaczy ten wątek, może absolutnie potrzebować odpowiedzi bez względu na koszty. Byłoby lepiej jako komentarz.
TomTsagk
0

W Flipcode jest artykuł na temat uzyskiwania wykrycia kolizji za pomocą matematyki . Ma krąg koła. Istnieje sposób precyzyjnego wykrycia punktu kolizji i sprawdzenia, czy w ogóle występuje kolizja.

użytkownik712092
źródło
Zdaję sobie sprawę, że to 7 lat później, ale ta odpowiedź to tylko link. Na szczęście link wciąż żyje, ale gdyby tak nie było, twoja odpowiedź ... nie byłaby odpowiedzią.
Draco18,
0

Wykrywanie kolizji dla poruszającego się obiektu jest zwykle nazywane „Obliczaniem objętości przesuwanej”, oto kilka kodów / artykułów na ten temat.

http://www.gpu-voxels.org/demos/ (Demo)

Biblioteki kodów źródłowych:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Artykuły:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (Niestety nie ma kodu źródłowego)

http://www.realtimerendering.com/intersections.html (raczej duży zbiór linków)

TarmoPikaro
źródło
1
Odpowiedzi zawierające tylko łącze (lub w tym przypadku kilka) nie zawierają rzeczywistej odpowiedzi. Powinieneś zamieścić odpowiednie informacje w swoim poście, aby w przypadku zaniku linków Twój post był nadal zrozumiały.
Draco18,
Informacje za linkami nieco lepiej wyjaśniają w tej chwili niż ja. Za linkami znajdują się również filmy demonstracyjne, które dają pewne wyobrażenie o tym, co dzieje się w czasie rzeczywistym.
TarmoPikaro
1
meta.stackexchange.com/a/8259/313685
Draco18s,