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!