EDYCJA / AKTUALIZACJA: Moje największe pytanie w tej chwili dotyczy tego, czy równanie „t = ...” z kroku 3 jest dobrym pomysłem, czy jest lepszy sposób na zrobienie tego. Większość innych problemów została częściowo lub całkowicie rozwiązana, ale żadne komentarze ani odpowiedzi tak naprawdę nie dotyczyły tego problemu. Ponownie prawdopodobnie konieczne jest rozwiązanie analityczne, prędkości i odległości są zbyt duże, a obiekty są zbyt małe, aby można było zastosować dowolne rozwiązanie iteracyjne / rekurencyjne (kilka sugerowanych poniżej w komentarzach), które mogę wymyślić (chociaż jeśli są specjalne iteracyjne / rekurencyjne rozwiązanie, które dobrze poradzi sobie z tego rodzaju sytuacjami, więc zdecydowanie jestem na to otwarty). Dziękuję bardzo za dotychczasową pomoc, wszyscy jesteście niesamowici i naprawdę doceniam wasze myśli i pomoc!
Próbuję wykryć kolizje między małymi, szybkimi obiektami. Jest to sytuacja, w której tunelowanie może odbywać się bardzo łatwo, nawet przy stosunkowo niskich prędkościach.
Odlewanie promieniowe nie będzie działać, ponieważ wykrywa to kolizję między dwoma szybkimi obiektami, a nie między jednym obiektem a nieruchomą ścianą. (Chyba, że źle rozumiem casting promieniowy?) Wydajność jest BARDZO DUŻA. jeśli to w ogóle możliwe, chcę uniknąć dużej wydajności. Mam już funkcjonalny i bardzo skuteczny quadtree ( http://en.wikipedia.org/wiki/Quadtree ), więc zmodyfikuję go i użyję zgodnie z poniższym opisem.
Edycja: Zmniejszenie odstępu czasu nie będzie działać. Prędkości są zbyt wysokie dla tego rozwiązania, co oznacza, że wyniki wydajności byłyby zbyt duże, a jednocześnie brakowałoby przeważającej większości kolizji tunelowych . (Na przykład, mogę mieć obiekt o wielkości około 1 jednostki poruszający się z prędkością mierzoną w milionach jednostek na przedział czasu ...)
PROPONOWANE ROZWIĄZANIE:
Krok 1:
Utwórz ramkę wokół ruchu każdego obiektu, a następnie wprowadź te pola do kwadratu, aby wygenerować początkową listę możliwych kolizji. Zobacz następujący obraz (ten obraz pokazuje obiekt koła przemieszczający się z jednej pozycji do drugiej oraz ruch generujący prostokąt, który zostanie wprowadzony do kwadratu):
Krok 2: (może chcesz pominąć ten krok?)
Przejrzyj listę możliwych kolizji generowanych przez quadtree. Sprawdź, czy prostokąty przecinają się w każdej możliwej kolizji. Jeśli tak, przejdź do kroku 3.
EDYCJA: poniżej Sean Middleditch zasugerował użycie przeciągniętych objętości / przecięcia kapsułek (jeśli obiekty są okręgami). To pozostawia trzy opcje: 1) całkowicie pomiń krok 2. 2) Zrób krok 2 po swojemu. 3) Zrób to po Seana. Sposób Seana będzie droższy pod względem obliczeniowym niż mój pomysł na pudełko, jednak wyeliminuje więcej fałszywych trafień niż mój sposób, uniemożliwiając im dotarcie do ostatniego kroku.
Czy ktoś może powiedzieć z doświadczenia, która z tych 3 opcji jest najlepsza? (Mam zamiar użyć tego silnika fizyki do kilku różnych rzeczy, dlatego szukam „ogólnie najlepszego” rozwiązania, które działa najszybciej w najróżniejszych sytuacjach, a nie tylko jednego konkretnego przypadku testowego, w którym mogę łatwo zmierzyć, które rozwiązanie jest najszybszy).
Krok 3:
Użyj poniższego równania t =, jeśli dyskryminator (tj. Część pod pierwiastkiem kwadratowym) jest ujemny lub 0, brak kolizji, jeśli jest dodatni, użyj wartości t jako czasu kolizji (po czym łatwo odpowiednio ustawić pozycje. ..jeśli oba obiekty nadal istnieją po zderzeniu). Równanie:
t = (-1/2 sqrt ((2 a w-2 a x + 2 b y-2 b z-2 c w + 2 c x-2 d y + 2 dz) ^ 2-4 (w ^ 2- 2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2) (a ^ 2-2 a c + b ^ 2-2 b d + c ^ 2 + d ^ 2-r ^ 2-2 r ss ^ 2)) - a w + a xb y + b z + c wc x + d yd z) / (w ^ 2-2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2 ) .
Gdzie (1 i 2 są używane do oznaczenia obiektów 1 i 2):
t jest ujemną wartością czasu między 0 a -1, gdzie 0 to bieżąca ramka, a -1 to poprzednia ramka;
a = x pozycja 1;
b = y pozycja 1;
c = x pozycja 2;
d = y pozycja 2;
w = x prędkość 1;
x = x prędkość 2;
y = y prędkość 1;
z = prędkość y 2;
r = promień 1;
s = promień 2;
Pochodna: (^ 2 oznacza do kwadratu)
Weź równania parametryczne (na przykład newxpos1 = a + t w) dla ruchów obiektów i podłącz je do wzoru odległości (kwadrat po obu stronach): wzór odległości do kwadratu = (a + t w - (c + t x)) ^ 2 + (b + t y - (d + t * z)) ^ 2. Pamiętaj, że t będzie ujemne. Aby znaleźć czas kolizji dla dwóch okrągłych obiektów, ustawiamy lewą stronę równą (r + s) ^ 2. Rozwiązując t za pomocą równania kwadratowego (i dużej ilości bardzo nudnej algebry), otrzymujemy powyższe równanie „t = ...”.
Moje pytania:
1) Czy to dobry sposób na zrobienie tego? Czy to w ogóle zadziała? Czy napotkam jakieś nieprzewidziane problemy? (Wiem, że będę miał problem, gdy zderzą się więcej niż 2 obiekty na raz, ale nie obchodzi mnie to, ponieważ jedyny przypadek, któremu tak naprawdę się sprzeciwiam, to to, że mają one niskie prędkości względne (jeśli prędkości względne są wysokie wtedy „głupkowate” rozwiązanie, które daje algorytm, będzie „wystarczająco dobre”, a człowiek nie będzie mógł zobaczyć błędu), a jeśli więcej niż 2 zderzą się z niskimi prędkościami względnymi w tym samym czasie, większość rozwiązań będzie i tak bądź wystarczająco blisko, ponieważ nie planuję wiązki nieelastycznych zderzeń)
2) Czy moje wyniki będą bardzo cierpieć? Nie sądzę, że tak będzie, ale jeśli tak, czy jest lepszy sposób?
3) Czy powinienem pominąć krok 2 i przejść od kroku 1 do 3? Oczywiście krok 2 nie jest niezbędny, ale może poprawić wydajność (LUB może kosztować więcej czasu procesora niż oszczędza).
Wszelkie inne komentarze, sugestie lub krytyka są bardzo mile widziane. Dziękuję za pomoc!
źródło
Odpowiedzi:
Zasadniczo stworzyłeś nieco zbyt entuzjastyczną wersję zamiatanych woluminów .
Zajmij dwie pozycje obiektu. „Zamiataj” obiekt od początku do końca. W przypadku kuli tworzyłoby to kapsułkę. W przypadku pudełka utworzyłoby to sześciokąt (lub dłuższe pole to ruch wzdłuż jednej osi). W przypadku ogólnych wielokątów wypukłych stworzyłoby to inny wielokąt wypukły.
Możesz teraz przeprowadzać testy przecięcia (w tym zapytania o poczwórne drzewo), korzystając z tego przemiatanego woluminu. Możesz obliczyć, kiedy doszło do kolizji, przewinąć symulację od czasu rozpoczęcia do czasu kolizji i powtórzyć.
Inną opcją, nieco prostszą, jest zrobienie tego, co powiedział @ ashes999 i po prostu użycie krótszego przedziału czasu lub mniejszych prędkości. Jest idealna maksymalna prędkość wyprowadzona z przedziału, w którym żaden obiekt nie może poruszać się dalej niż jego najwęższa strona w pojedynczej interakcji fizycznej. W przypadku szczególnie małych lub szczególnie szybkich obiektów może nie być możliwe znalezienie rozsądnie małego odstępu, który dobrze się sprawdza.
Zobacz Wykrywanie kolizji w czasie rzeczywistym, aby znaleźć jedną z lepszych książek wprowadzających / pośrednich na temat wykrywania kolizji.
źródło
Algorytm zaproponowany w pytaniu działa świetnie: jest szybki i całkowicie dokładny , nawet gdy obiekty poruszają się z ekstremalnymi prędkościami. Mam zaimplementowane cztero-drzewo, więc po wprowadzeniu skrzynek z kroku 1 do kwadratu stwierdziłem, że krok 2 jest niepotrzebny: mój program działał prawie tak szybko, jak wcześniej.
Używam tego algorytmu od kilku miesięcy i wydaje się, że jest on całkowicie dokładny w określaniu t, czasu kolizji. Ponieważ wydaje się, że w sieci nie ma nic lepszego, bardzo polecam korzystanie z tego. (Niektóre odpowiedzi w pozostałych odpowiedziach i komentarzach powyżej są świetne, ale albo nie spełniają one potrzeb, jak wskazano w pytaniu, albo autor był bardzo niejednoznaczny i nigdy nie wrócił do odpowiedzi na pytanie o niejednoznaczność ).
źródło
Nie mam jeszcze wystarczającej reputacji, aby komentować, ale chciałbym dodać, że użycie tego, o czym wspomniał Sean Middleditch, umożliwia obliczenie twojego „t”. Przynajmniej jeśli zrozumiałem jego odpowiedź, a ty pytasz poprawnie.
Oto link do niesamowitej odpowiedzi Sama Hocevara, który stanowi najlepsze wytłumaczenie tego, jakie kiedykolwiek znalazłem (on też narysował zdjęcia, hurra!)
/gamedev//a/55991/112940
Jeśli jest to szybsze niż twoja własna metoda, nie mogę powiedzieć, ale z pewnością daje ci wszystko, czego potrzebujesz, aby wdrożyć ją i porównać z twoją.
Aby uniknąć pozostawienia odpowiedzi „tylko link”, krótko podsumuję jego pomysł:
źródło