Znalezienie punktu kontaktowego za pomocą SAT

Twierdzenie o separującej osi (SAT) ułatwia określenie minimalnego wektora translacji, tj. Najkrótszego wektora, który może oddzielić dwa kolidujące obiekty. Potrzebuję jednak wektora, który oddziela obiekty wzdłuż wektora, którym porusza się obiekt penetrujący (tj. Punkt styku).

Narysowałem zdjęcie, aby pomóc wyjaśnić. Jest jedno pole, przechodzące od poprzedniej do następnej pozycji. W swojej pozycji po przecina szary wielokąt. SAT może łatwo zwrócić MTV, czyli czerwony wektor. Chcę obliczyć niebieski wektor.

Moje obecne rozwiązanie przeprowadza wyszukiwanie binarne między pozycjami przed i po, dopóki długość niebieskiego wektora nie będzie znana do pewnego progu. Działa, ale jest to bardzo kosztowne obliczenie, ponieważ kolizja między kształtami musi być ponownie obliczana w każdej pętli.

Czy istnieje prostszy i / lub bardziej wydajny sposób na znalezienie wektora punktu kontaktowego?

To, o czym mówisz, jest dość trudne, jeśli skonstruujesz je jako najpierw ruch obiektu, a następnie testowanie kolizji, a następnie wycofanie się, dopóki nie wyjdziesz z obiektu. Prawdopodobnie lepiej myśleć o tym jako o dynamicznym teście przecięcia : ruchomy obiekt na nieruchomym obiekcie.

Na szczęście testy osi rozdzielających mogą ci w tym pomóc! Oto opis algorytmu, dzięki uprzejmości Rona Levine'a :

Algorytm działa w ten sposób. Pracujesz z wektorem prędkości względnej dwóch wypukłych ciał. Rzutowanie każdego z dwóch ciał i wektora prędkości względnej na określoną oś rozdzielającą w t ₀ daje dwa przedziały 1-D i prędkość 1-D, tak że łatwo jest stwierdzić, czy te dwa przedziały przecinają się, a jeśli nie, czy rozchodzą się lub poruszają razem. Jeśli są one oddzielone i oddalają się od siebie na dowolnej osi oddzielającej (lub w rzeczywistości na dowolnej osi, cokolwiek), to wiesz, że nie będzie kolizji w przyszłości. Jeżeli na dowolnej osi oddzielającej dwa rzutowane przedziały przecinają się w t₀ lub są rozdzielone i poruszają się razem, wtedy łatwo jest obliczyć (za pomocą dwóch prostych wyrażeń liniowych 1D) najwcześniejszy przyszły czas, w którym dwa przedziały najpierw się przecinają, i (zakładając kontynuację ruchu prostoliniowego) ostatni przyszły czas, w którym dwa interwały będą się przecinać i zaczną się rozchodzić. (Jeśli przecinają się w punkcie t ₀, najwcześniejszym przyszłym czasem przecięcia jest t ₀). Zrób to dla co najwyżej wszystkich osi oddzielających. Jeśli maksimum na wszystkich osiach najwcześniejszego przyszłego czasu przecięcia jest mniejsze niż minimum na wszystkich osiach ostatniego przyszłego czasu przecięcia, wówczas ten maksymalny najwcześniejszy przyszły czas przecięcia jest dokładnym czasem pierwszego zderzenia dwóch wielościanów 3D, w przeciwnym razie nie ma kolizji w przyszłości.

Innymi słowy, zapętlasz wszystkie osie, które normalnie robiłbyś w teście statycznej osi oddzielającej. Zamiast wcześnie wychodzić, jeśli nie zauważysz nakładania się, kontynuuj i sprawdzaj rzutowaną prędkość poruszającego się obiektu. Jeśli odsuwa się od obiektu statycznego, wtedy zaczynasz. W przeciwnym razie możesz rozwiązać problem z najwcześniejszym i ostatnim kontaktem dość łatwo (to jeden interwał 1D zbliża się do kolejnego interwału 1D). Jeśli zrobisz to dla wszystkich osi i zachowasz maksymalny czas najwcześniejszego przecięcia i minimalny ostatni czas przecięcia, to wiesz, czy poruszający się obiekt uderzy w obiekt statyczny, a także kiedy. Możesz więc przesunąć poruszający się obiekt dokładnie do momentu, w którym uderzy on w obiekt statyczny.

Oto kilka przybliżonych i całkowicie niezweryfikowanych pseudokodów dla algorytmu:

t_min := +∞
t_max := -∞
foreach axis in potential_separating_axes
    a_min := +∞
    a_max := -∞
    foreach vertex in a.vertices
        a_min = min(a_min, vertex · axis)
        a_max = max(a_max, vertex · axis)
    b_min := +∞
    b_max := -∞
    foreach vertex in b.vertices
        b_min = min(b_min, vertex · axis)
        b_max = max(b_max, vertex · axis)
    v := b.velocity · axis
    if v > 0 then
        if a_max < b_min then
            return no_intersection
        else if (a_min < b_min < a_max) or (b_min < a_min < b_max) then
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, 0)
        else
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, (a_min - b_max) / v)
    else if v < 0 then
        // repeat the above case with a and b swapped
    else if v = 0 then
        if a_min < b_max and b_min < a_max then
            t_min = min(t_min, 0)
            t_max = max(t_max, 0)
        else
            return no_intersection
if t_max < t_min then
    // advance b by b.velocity * t_max
    return intersection
else
    return no_intersection

Oto artykuł Gamasutra mówiący o tym zaimplementowany w kilku różnych prymitywnych testach. Zauważ, że podobnie jak SAT, wymaga to obiektów wypukłych.

Jest to również nieco bardziej skomplikowane niż prosty test osi oddzielającej. Upewnij się, że jest to potrzebne, zanim spróbujesz. Bardzo duża liczba gier po prostu wypycha obiekty ze sobą wzdłuż minimalnego wektora translacji, ponieważ po prostu nie wnikają one głęboko w żadną klatkę i jest prawie niezauważalne wizualnie.

Chcesz użyć obcinania wielokątów. Najlepiej to wyjaśnić zdjęciami, których nie mam, ale ten facet to zrobił, więc pozwolę mu to wyjaśnić.

http://www.codezealot.org/archives/394

Kolektor kontaktowy zwróci punkt na jednym z obiektów, który jest „najbardziej odpowiedzialny” za kolizję, a nie bezpośredni punkt kolizji. Jednak tak naprawdę nie potrzebujesz tego bezpośredniego punktu kolizji. Możesz po prostu odepchnąć obiekty od siebie przy użyciu głębokości penetracji i normalnej, którą już masz, i użyć kolektora kontaktowego, aby zastosować inne efekty fizyczne (na przykład sprawić, by pudełko przewróciło się / stoczyło w dół zbocza).

Zauważ, że twoje zdjęcie ilustruje mały problem: punkt na niebieskim wektorze, o który prosisz, nie zostanie znaleziony w żadnej fizycznej symulacji, ponieważ tak naprawdę nie trafiłoby to w pole. Pudełko uderzy lewym dolnym rogiem gdzieś w górę stoku, gdy tylko niewielka część narożnika wnika.

Głębokość penetracji będzie względnie mała, a po prostu wypchnięcie pudła ze zbocza wzdłuż normalnej penetracji sprawi, że będzie ono wystarczająco blisko pozycji „prawidłowej”, aby było praktycznie niezauważalne w praktyce, szczególnie jeśli skrzynia ma się odbić, przewrócić lub przesuń się później.

Wystarczy rzutować wektor MAT na kierunek Vector. Powstały wektor można dodać do wektora kierunku, aby skompensować penetrację. Wyświetlaj to w ten sam sposób, jak na Osi podczas SAT. To ustawia Obiekt dokładnie w pozycji, w której dotyka on drugiego obiektu. Dodaj mały epsilon, aby walczyć z problemami zmiennoprzecinkowymi.

Jest kilka ostrzeżeń dotyczących mojej odpowiedzi, które jako pierwsze usunę z drogi: dotyczy tylko nieobrotowych obwiedni. Zakłada się, że próbujesz poradzić sobie z problemami z tunelowaniem , tj. Problemami powodowanymi przez obiekty poruszające się z dużą prędkością.

Po zidentyfikowaniu MTV znasz normalną krawędź / powierzchnię, na której musisz przetestować. Znasz również wektor prędkości liniowej przenikającego się obiektu.

Po ustaleniu, że w pewnym momencie w ramce nastąpiło przecięcie, możesz następnie wykonać binarne operacje półetapowe, w oparciu o następujące punkty początkowe: Zidentyfikuj wierzchołek, który penetrował pierwszy podczas ramki:

vec3 vertex;
float mindot = FLT_MAX;
for ( vert : vertices )
{
    if (dot(vert, MTV) < mindot)
    {
         mindot = dot(vert, MTV);
         vertex = vert;
    }
}

Po zidentyfikowaniu wierzchołka binarny pół krok staje się znacznie tańszy:

//mindistance is the where the reference edge/plane intersects it's own normal. 
//The max dot product of all vertices in B along the MTV will get you this value.
halfstep = 1.0f;
vec3 cp = vertex;
vec3 v = A.velocity*framedurationSeconds;
float errorThreshold = 0.01f; //choose meaningful value here
//alternatively, set the while condition to be while halfstep > some minimum value
while (abs(dot(cp,normal)) > errorThreshold)
{            
    halfstep*=0.5f;
    if (dot(cp,normal) < mindistance) //cp is inside the object, move backward
    {
        cp += v*(-1*halfstep);
    }
    else if ( dot(cp,normal) > mindistance) //cp is outside, move it forward
    {
        cp += v*(halfstep);
    }
}

return cp;

Jest to dość dokładne, ale zapewni tylko jeden punkt zderzenia, w jednym przypadku.

Chodzi o to, że zwykle można z wyprzedzeniem stwierdzić, czy obiekt porusza się wystarczająco szybko na klatkę, aby móc tunelować w ten sposób, dlatego najlepszą wskazówką jest zidentyfikowanie wiodących wierzchołków wzdłuż prędkości i wykonanie testu promieniowego wzdłuż wektora prędkości. W przypadku obracających się obiektów będziesz musiał wykonać binarny krokowy krok pośredni w celu zapewnienia prawidłowego punktu kontaktowego.

Jednak w większości przypadków można bezpiecznie założyć, że większość obiektów w twojej scenie nie porusza się wystarczająco szybko, aby przebić się tak daleko w jednej klatce, więc nie jest konieczne półskokowanie i wystarczające będzie wykrywanie kolizji dyskretnej. Obiekty o dużej prędkości, takie jak pociski, które poruszają się zbyt szybko, aby je zobaczyć, mogą być śledzone promieniami w punktach kontaktowych.

Co ciekawe, ta metoda halfstep może również dać (prawie) dokładny czas wystąpienia obiektu podczas kadru:

float collisionTime = frametimeSeconds * halfstep;

Jeśli wykonujesz jakąś rozdzielczość kolizji fizyki, możesz następnie poprawić pozycję A poprzez:

v - (v*halfstep)

wtedy możesz normalnie wykonywać swoją fizykę. Minusem jest to, że jeśli obiekt porusza się dość szybko, zobaczysz, że teleportuje się z powrotem wzdłuż wektora prędkości.