Jaki jest najszybszy sposób sprawdzenia, czy dwa ruchome AABB przecinają się?

Mam dwa ruchome AABB, jaki jest najszybszy sposób sprawdzenia, czy przecinają się pod ramką?

Poruszając się, mam na myśli nie tylko sprawdzenie za pomocą zwykłej metody przecięcia prostokąta, mam na myśli jakiś prosty prosty test przeciągnięcia, który zwraca tylko wartość logiczną, brak czasu trafienia lub cokolwiek innego.

Moim zdaniem po prostu zrobić to w ten sposób:

Ale ten sześciokąt jest dość złożony i nie wiem, jak obliczyć przecięcie AABB - wielokąt, czy jest może łatwiejszy sposób?

Dowolny język programowania, który najbardziej ci się podoba, mogę go łatwo przenieść.

Dzięki.

Użyj sumy Minkowskiego

Dobrym sposobem na rozwiązanie tego problemu jest rozważenie skrzyżowaniu linii ruchu ( v ) tłumaczone na pochodzenie ( V „ ) i suma Minkowski od A obrócony o 180 stopni na początku ( A” ) i jej przeszkód (tylko B w tym przypadku): A” ⊕ B .

W poniższym obrazku I miejsce A zadatki-DAB w początku układu współrzędnych arbitralny. Upraszcza to zrozumienie, że obrót A o 180 stopni daje A ' , a v przetłumaczone na początek równa się v' .

Suma Minkowskiego jest zielonym prostokątem, a punkty przecięcia ruchomego A i stacjonarnego B można znaleźć, wykonując przecięcie linii-AABB . Punkty te są oznaczone niebieskimi kółkami.

Na poniższym zdjęciu użyto innego początku i znaleziono te same punkty przecięcia.

Wiele ruchomych AABB

Aby to zadziałało dla dwóch AABB, które poruszają się liniowo w określonym czasie, odejmujesz wektor prędkości B od wektora prędkości A i używasz go jako odcinka linii dla przecięcia linii AABB.

Pseudo kod

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Reakcja na zderzenie

W zależności od rozgrywki albo wykonasz dokładniejsze wykrywanie kolizji (być może AABB zawiera siatki), albo przejdziesz do następnej fazy: reakcji na kolizję.

Gdy dojdzie do kolizji, algorytm przecięcia linii AABB zwróci 1 lub 2 punkty przecięcia w zależności od tego, czy A odpowiednio zakończy ruch wewnątrz B, czy też go przejdzie. (Jest to pomijanie zdegenerowanych przypadków, w których A ociera się o B wzdłuż ich boków lub wzdłuż jednego z odpowiednich narożników.)

Tak czy inaczej, pierwszym punktem przecięcia wzdłuż odcinka linii jest punkt kolizji, przełożyłbyś to z powrotem do właściwej pozycji w światowym układzie współrzędnych (pierwszy jasnoniebieski okrąg na drugim zdjęciu wzdłuż oryginalnego v , nazwij go p ), a następnie zdecyduj (np. w przypadku zderzeń sprężystych, odbijając v wzdłuż normalnej kolizji w punkcie p ), jaka będzie rzeczywista pozycja dla A na końcu ramki ( At + 1 ).

Jeśli są więcej niż tylko 2 zderzacze, stanie się to nieco bardziej skomplikowane, ponieważ chcesz również wykonać wykrywanie kolizji dla drugiej, odzwierciedlonej części v .

OBB - Zorientowana ramka ograniczająca. Oto samouczek

W efekcie obwiednia wyrównana do wektora prędkości obiektu A jako oś y (w górę). Jego szerokość i wysokość można obliczyć na podstawie początkowych i końcowych punktów obiektu A. Następnie porównujesz to z AABB obiektu B (traktując go jako OOBB) i swoim złotym.

Jeśli szukasz szybkiego testu przecięcia, aby zobaczyć, JEŚLI MOGĄ się przeciąć, możesz utworzyć AABB, który otacza AABB obiektu A zarówno w pozycji początkowej, jak i końcowej. Jeśli AABB nie przecina się z tym wszystkim, co obejmuje AABB, oznacza to, że nie ma przecięcia; Może to jednak prowadzić do wyników fałszywie dodatnich, dlatego należy go używać tylko jako testu wstępnego.

Nie potrzebujesz OOB i nie musisz używać wykrywającego kolizje skokowego czasu. Wystarczy użyć normalnego testu przeciągania AABB, zobacz ten link . W gruncie rzeczy robi dokładnie to, co masz na schemacie: ruchomy AABB jest „przesuwany” od punktu początkowego do punktu końcowego, a następnie służy do wykrywania kolizji z innymi statycznymi AABB.

Jeśli obawiasz się, że ten test zamiatania jest droższy, ponieważ zwraca „czas uderzenia”, myślę, że przedwcześnie optymalizujesz.

Bardziej szczegółowe informacje o przetoczyły testów można znaleźć w znakomitej książce: Real-Time Collision Detection Christer Ericson.

Najpierw musisz rozłożyć ruch na mniejsze kroki i wykorzystać te informacje do obliczenia wysokiego poziomu AABB. Jeśli duże AABB przecinają się, możesz sprawdzić mniejsze kroki, aby być bardziej dokładnym.

Oszacowanie, czy doszło do kolizji, poprzez sprawdzenie AABB (lub OOBB) przy użyciu tylko pozycji początkowej i końcowej, może ominąć kolizje, jeśli któryś z obiektów obraca się szybko i jest dłuższy w jednym wymiarze.

Aby obliczyć dokładniejsze oszacowanie AABB, rozłóż ruch na mniejsze etapy i używając tylko początkowego AABB (nie siatki obiektu), obróć AABB (teraz tylko pole, nie wyrównane względem osi), ponieważ obiekt będzie się obracał i poruszał przy każdym krok. Punkty maks. I min. Dla każdej osi dają AABB, który obejmuje cały ruch obiektu.

Jeśli istnieje skrzyżowanie z większym AABB, możesz użyć mniejszych AABB, które zostały już obliczone, aby ustalić, gdzie mogła wystąpić kolizja. Dla każdego z mniejszych bloków AABB, które przecinają się z innym obiektem, możesz wykonać droższe wykrywanie przecięcia siatki.

Będziesz musiał rozłożyć ruch na mniejsze etapy ruchu. Na przykład:

Chcesz zdekomponować ruch za pomocą większego komponentu (w tym przypadku osi X), a następnie sprawdź kolizję na każdym etapie.

Może to wyglądać zbyt drogo, ale należy wziąć pod uwagę, że obiekt poruszający się szybciej niż jego własna szerokość w każdym cyklu będzie BARDZO szybki, więc ten scenariusz nie jest tak powszechny, jak mogłoby się wydawać.

Powinieneś także używać prędkości względnych do sprawdzania kolizji, aby jeden AABB był „statyczny”, a drugi poruszał się z prędkością własnej prędkości minus prędkość „statycznego”.

Najszybszym sposobem sprawdzenia, czy mogą się przecinać, jest po prostu rozwinięcie ruchomego AABB z prędkością.

na przykład AABB przesuwa się w prawo o 0,1 x / ramkę, a następnie wysuwasz go, aby lewa krawędź pozostała taka sama, a prawa krawędź o 0,1 dalej. Następnie możesz sprawdzić za pomocą nowego AABB. Jeśli fałsz, to nie ma kolizji. (wczesny powrót i dokładny przy małych prędkościach).

Następnie możesz sprawdzić, czy koniec i uruchomienie AABB poruszającego się obiektu przecina się. jeśli true, to zwróć true.

W przeciwnym razie musisz sprawdzić, czy przekątna przecina statyczny ABB.

Polega to na uzyskaniu współrzędnych przekątnej, gdzie x = lewa krawędź statycznego, a prawa krawędź sprawdzają, czy y jest w dolnej i górnej części. (powtórz na odwrót)