Obiekt ma pozycję i wektor prędkości. Zwykle tylko pozycja służy do sprawdzenia, czy dwa obiekty zderzają się, jest to problematyczne w przypadku bardzo szybko poruszających się obiektów, ponieważ może się zdarzyć, że obiekt porusza się tak szybko, że znajduje się przed pierwszym obiektem w pierwszej kontroli kolizji, a za nim w drugie sprawdzenie kolizji.

Teraz dostępne są również kontrole kolizji na podstawie linii, w których sprawdzane jest tylko, czy wektor ruchu każdego obiektu przecina się z obwiednią drugiego. Można to postrzegać jako rozszerzenie punktu. Działa to tylko wtedy, gdy szybko poruszający się obiekt jest naprawdę mały.

Więc moim pomysłem jest rozszerzenie punktu, dlaczego nie rozwinąć prostokąta? Daje to sześciokąt.

Jak dotąd tak dobrze. Ale jak właściwie sprawdzić, czy dwa tego rodzaju sześciokąty przecinają się? Zauważ, że są to bardzo specyficzne sześciokąty.

Pytanie bonusowe : Czy można obliczyć, gdzie dokładnie (a raczej po jakim czasie) doszło do kolizji? Może to być bardzo przydatne do wykrywania tego, co się naprawdę wydarzyło, na przykład gdzie i przy jakiej mocy, oraz do symulacji tego, jak poruszali się w czasie między kolizją a końcem kadru.

Rozwiązanie jest w rzeczywistości prostsze niż oczekiwano. Sztuką jest użycie odejmowania Minkowskiego przed techniką sześciokąta.

Oto twoje prostokąty A i B, z ich prędkościami vAi vB. Zauważ, że vAi vBtak naprawdę nie są prędkościami, są odległością przebytą podczas jednej klatki.

Teraz zastąp prostokąt B punktem P, a prostokąt A prostokątem C = A + (- B), który ma wymiary sumę wymiarów A i B. Właściwości dodawania Minkowskiego wskazują, że dochodzi do kolizji między punktem a nowym prostokątem wtedy i tylko w przypadku kolizji między oryginalnymi dwoma prostokątami:

Ale jeśli prostokąt C porusza się wzdłuż wektora vA, a punkt P porusza się wzdłuż wektora vB, prosta zmiana ramki odniesienia mówi nam, że jest tak samo, jakby prostokąt C był nadal, a punkt P poruszał się wzdłuż wektora vB-vA:

Następnie można użyć prostej formuły przecięcia segmentu skrzynkowego, aby określić miejsce wystąpienia kolizji w nowej ramce odniesienia.

Ostatnim krokiem jest powrót do właściwej ramki odniesienia. Po prostu podziel odległość przebytą przez punkt, aż do przecięcia w kółku, przez długość wektora, vB-vAa otrzymasz wartość staką, że 0 < s < 1. Kolizja ma miejsce w czasie, w s * Tktórym Tjest czas trwania ramki.

Komentarz madshogo :
Jedną OGROMNĄ przewagą tej techniki nad tą w odpowiedzi pana Beasta jest to, że jeśli nie ma rotacji, wówczas „odejmowanie Minkowskiego” A + (- B) można obliczyć raz dla wszystkich kolejnych kroków czasowych !

Więc jedyny algorytm, który wymaga czasu na to wszystko (suma Minkowskiego, złożoność O (mn) , gdzie m jest liczbą wierzchołków A i n to liczba wierzchołków B ) może być użyty tylko raz, co skutecznie wykrywanie kolizji proporcjonalnego problem z czasem!

Później możesz wyrzucić tę sumę, gdy wiesz, że A i B znajdują się w różnych częściach twojej sceny (twojego kwadratu?) I nie będą już kolidować.

W przeciwieństwie do tego metoda pana Beasta wymaga sporo obliczeń na każdym etapie.

Ponadto w przypadku prostokątów wyrównanych do osi A + (- B) można obliczyć znacznie prościej niż poprzez faktyczne obliczenie wszystkich sum, wierzchołek po wierzchołku. Po prostu rozwiń A , dodając wysokość B do jego wysokości i szerokość B do jego szerokości (jedna połowa z każdej strony).

Ale wszystko to działa tylko wtedy, gdy ani A, ani B nie obracają się i oba są wypukłe. Jeśli istnieje obrót lub jeśli używasz wklęsłych kształtów, musisz użyć przeciągniętych objętości / obszarów.
koniec komentarza

Po pierwsze, w przypadku prostokątów wyrównanych do osi odpowiedź Kevina Reida jest najlepsza, a algorytm najszybszy.

Po drugie, dla prostych kształtów użyj prędkości względnych (jak pokazano poniżej) i twierdzenia o osi oddzielającej do wykrywania kolizji. To będzie powiedzieć, czy kolizja dzieje się w przypadku ruchu liniowego (bez rotacji). A jeśli występuje rotacja, potrzebujesz krótkiego czasu, aby był precyzyjny. Teraz, aby odpowiedzieć na pytanie:

Jak stwierdzić w ogólnym przypadku, czy przecinają się dwa wypukłe kształty?

Dam ci algorytm, który działa dla wszystkich wypukłych kształtów, a nie tylko sześciokątów.

Załóżmy, że X i Y są dwoma wypukłymi kształtami. Przecinają się wtedy i tylko wtedy, gdy mają wspólny punkt, tj. Istnieje punkt x ∈ X i punkt y ∈ Y taki, że x = y . Jeśli uważasz, że przestrzeń jest przestrzenią wektorową, oznacza to powiedzenie x - y = 0 . A teraz dochodzimy do tego biznesu Minkowskiego:

Suma Minkowskiego z X i Y jest zbiorem wszystkich x + y dla x ∈ X i Y ∈ Y .

Przykład dla X i Y

X, Y i ich suma Minkowskiego, X + Y

Załóżmy, że (-Y) jest zbiorem wszystkich -y dla y ∈ Y , a następnie biorąc pod uwagę poprzedni akapit, X i Y przecinają się tylko wtedy, gdy X + (-Y) zawiera 0 , to znaczy początek .

Uwaga boczna: dlaczego piszę X + (-Y) zamiast X-Y ? Cóż, ponieważ w matematyce istnieje operacja zwana różnicą Minkowskiego A i B, która jest czasami zapisywana jako X - Y, ale nie ma nic wspólnego z zestawem wszystkich x - y dla x ∈ X i y ∈ Y (prawdziwy Minkowski różnica jest nieco bardziej złożona).

Chcielibyśmy zatem obliczyć sumę Minkowskiego X i -Y i sprawdzić, czy zawiera ona pochodzenie. Początek nie jest szczególny w porównaniu z żadnym innym punktem, więc aby ustalić, czy początek znajduje się w określonej domenie, używamy algorytmu, który mógłby powiedzieć nam, czy dany punkt należy do tej domeny.

Suma Minkowskiego X i Y ma fajną właściwość, to znaczy, że jeśli X i Y są wypukłe, to X + Y też jest. Ustalenie, czy punkt należy do zbioru wypukłego, jest znacznie łatwiejsze, niż gdyby ten zbiór nie był (jak wiadomo) wypukły.

Nie możemy obliczyć wszystkich x - y dla x ∈ X i y ∈ Y, ponieważ istnieje nieskończoność takich punktów x i y , więc mam nadzieję, że ponieważ X , Y i X + Y są wypukłe, możemy po prostu użyć „najbardziej oddalone” punkty definiujące kształty X i Y , które są ich wierzchołkami, a my otrzymamy najbardziej zewnętrzne punkty X + Y i jeszcze więcej.

Te dodatkowe punkty są „otoczone” najbardziej zewnętrznymi punktami X + Y , aby nie przyczyniły się do zdefiniowania nowo uzyskanego kształtu wypukłego. Mówimy, że nie definiują „ wypukłego kadłuba ” zbioru punktów. Więc to, co robimy, polega na tym, że pozbywamy się ich w ramach przygotowań do ostatecznego algorytmu, który mówi nam, czy początek znajduje się w wypukłym kadłubie.

Wypukły kadłub X + Y. Usunęliśmy „wewnętrzne” wierzchołki.

Dlatego otrzymujemy

Pierwszy naiwny algorytm

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Pętle mają oczywiście złożoność O (mn), gdzie m i n to liczba wierzchołków każdego kształtu. minkoswkiZestaw zawiera MN elementy w większości. convexHullAlgorytm ma złożoność, który zależy od algorytmu użytego , można dążyć do O (k log (k)) , gdzie k jest wielkość zbioru punktów, więc w naszym przypadku mamy O (mn dziennik (MN) ) . containsAlgorytm ma złożoność liniową, która jest z liczbą krawędzi (w 2D) lub powierzchni (w 3D) o wypukłej, tak naprawdę zależy od Twoich kształtów wyjściowych, ale nie będzie większa niż O (mn) .

Pozwolę ci znaleźć w Google containsalgorytm wypukłych kształtów, jest dość powszechny. Mogę to tutaj umieścić, jeśli będę miał czas.

Ale robimy wykrywanie kolizji, więc możemy to bardzo zoptymalizować

Początkowo mieliśmy dwa ciała A i B poruszające się bez obrotu podczas pomiaru czasu dt (z tego, co mogę stwierdzić, patrząc na twoje zdjęcia). Nazwijmy v _A i v _B odpowiednie prędkości A i B , które są stałe podczas naszego czasu trwania dt . Otrzymujemy następujące:

a jak wskazano na zdjęciach, ciała te przesuwają się po obszarach (lub objętościach w 3D) podczas ich przemieszczania się:

i kończą się jako A ' i B' po upływie czasu.

Aby zastosować tutaj nasz naiwny algorytm, musielibyśmy tylko obliczyć objętości przeciągnięcia. Ale my tego nie robimy.

W ramce odniesienia B , B nie rusza (duh!). A A ma pewną prędkość w stosunku do B , którą otrzymujesz obliczając v _A - v _B (możesz zrobić odwrotnie, obliczyć prędkość względną B w ramce odniesienia A ).

Od lewej do prawej: prędkości w podstawowej ramce odniesienia; prędkości względne; obliczanie prędkości względnych.

Traktując B jako nieruchomo w swoim układzie odniesienia, trzeba tylko obliczyć objętość że A zamiata przez co porusza się w czasie dt z jego względną prędkość v - v _B .

Zmniejsza to liczbę wierzchołków używanych w obliczeniach sumy Minkowskiego (czasami znacznie).

Inna możliwa optymalizacja to punkt, w którym obliczasz objętość przeciągniętą przez jedno z ciał, powiedzmy A. Nie musisz tłumaczyć wszystkich wierzchołków tworzących A. Tylko te, które należą do krawędzi (ścian w 3D), których zewnętrzna normalna „twarz” kierunku zamiatania. Z pewnością zauważyłeś to już podczas obliczania swoich obszarów zamiatanych dla kwadratów. Możesz stwierdzić, czy normalna jest w kierunku zamiatania, używając iloczynu iloczynu z kierunkiem zamiatania, który musi być dodatni.

Ostatnia optymalizacja, która nie ma nic wspólnego z twoim pytaniem dotyczącym skrzyżowań, jest naprawdę przydatna w naszym przypadku. Wykorzystuje wspomniane prędkości względne i tak zwaną metodę osi oddzielającej. Na pewno już o tym wiesz.

Załóżmy, że znamy promienie z A i B w stosunku do swoich ośrodków masy (to znaczy, że odległość pomiędzy środkiem masy i wierzchołka najdalej od niego), jak poniżej:

Kolizja może wystąpić tylko wtedy, gdy jest to możliwe, że ograniczająca krąg A spotykają się, że z B . Widzimy tutaj, że nie będzie, a sposobem, aby powiedzieć, że komputer jest obliczenie odległości od C _B do I , jak na poniższym rysunku i upewnij się, że jest większy niż suma promieni A i B . Jeśli jest większy, nie ma kolizji. Jeśli jest mniejszy, to kolizja.

Nie działa to zbyt dobrze w przypadku kształtów, które są dość długie, ale w przypadku kwadratów lub innych takich kształtów wykluczenie kolizji jest bardzo dobrą heurystą .

Twierdzenie o osi oddzielającej zastosowane do B i objętość przesunięta przez A mówi jednak, czy doszło do zderzenia. Złożoność powiązanego algorytmu jest liniowa z sumą liczb wierzchołków każdego wypukłego kształtu, ale jest mniej magiczna, kiedy przychodzi czas na faktyczną obsługę kolizji.

Nasz nowy, lepszy algorytm, który wykorzystuje skrzyżowania do wykrywania kolizji, ale nadal nie jest tak dobry jak twierdzenie o osi oddzielającej do faktycznego stwierdzenia, czy doszło do kolizji

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}

Nie sądzę, aby używanie „sześciokąta” było tak pomocne. Oto szkic sposobu uzyskania dokładnych kolizji prostokątów wyrównanych do osi:

Dwa prostokąty wyrównane do osi nachodzą na siebie wtedy i tylko wtedy, gdy ich zakresy współrzędnych X pokrywają się, a zakresy współrzędnych Y nakładają się. (Można to postrzegać jako szczególny przypadek twierdzenia o osi oddzielającej.) Oznacza to, że jeśli rzutujesz prostokąty na osie X i Y, zredukowałeś problem do dwóch przecięć linia-linia.

Oblicz przedział czasu, w którym przecinają się dwie linie na jednej osi (np. Zaczyna się w czasie (bieżące oddzielenie obiektów / względna prędkość zbliżania się obiektów)) i wykonaj to samo dla drugiej osi. Jeśli te przedziały czasowe nakładają się, to najwcześniejszy czas w zakładce to czas kolizji.

Nie sądzę, że istnieje prosty sposób na obliczenie zderzenia wielokątów o większej liczbie boków niż prostokąta. Rozbiłbym go na prymitywne kształty, takie jak linie i kwadraty:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Zwróć uwagę, jak ignoruję stan początkowy każdego obiektu, ponieważ powinien był zostać sprawdzony podczas poprzedniego obliczenia.

Twierdzenie o osobnych osiach

Twierdzenie o oddzielnych osiach mówi: „Jeśli znajdziemy oś, na której dwa wypukłe kształty się nie przecinają, wówczas te dwa kształty się nie przecinają” lub bardziej praktyczne dla IT:

„Dwa wypukłe kształty przecinają się tylko wtedy, gdy przecinają się na wszystkich możliwych osiach”.

W przypadku prostokątów wyrównanych do osi istnieją dokładnie 2 możliwe osie: xiy. Ale twierdzenie to nie ogranicza się do prostokątów, można je zastosować do dowolnego wypukłego kształtu, po prostu dodając inne osie, na których kształty mogłyby się przecinać. Aby uzyskać więcej informacji na ten temat, zapoznaj się z tym samouczkiem autora N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Zaimplementowane wygląda to tak:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Osie mogą być reprezentowane jako znormalizowane wektory.

Zakres jest linią 1-wymiarową. Początek powinien być ustawiony na najmniejszy rzutowany punkt, koniec na największy rzutowany punkt.

Zastosowanie do „przeciągniętego” prostokąta

Sześciokąt w pytaniu powstaje przez „zamiatanie” AABB obiektu. Zamiatanie dodaje dokładnie jedną możliwą oś zderzenia do dowolnego kształtu: wektor ruchu.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

Jak dotąd tak dobrze, teraz możemy już sprawdzić, czy dwa sześciokąty się przecinają. Ale jest jeszcze lepiej.

To rozwiązanie będzie działać dla dowolnych kształtów wypukłych (na przykład trójkątów) i dowolnych kształtów wypukłych (na przykład ośmiokątów). Jednak im bardziej złożony kształt, tym mniej skuteczny będzie.

Bonus: tam, gdzie dzieje się magia.

Jak powiedziałem, jedynymi dodatkowymi osiami są wektory ruchu. Ruch jest pomnożony czasowo przez prędkość, więc w pewnym sensie nie są to jedynie osie czasoprzestrzenne, to osie czasoprzestrzenne.

Oznacza to, że możemy ustalić czas, w którym mogło dojść do kolizji z tych dwóch osi. W tym celu musimy znaleźć przecięcie między dwoma przecięciami na osiach ruchu. Jednak zanim to zrobimy, musimy znormalizować oba zakresy, abyśmy mogli je faktycznie porównać.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

Kiedy zadałem to pytanie, już trochę zaakceptowałem kompromis, że przy tej metodzie będzie kilka rzadkich fałszywych trafień. Ale myliłem się, sprawdzając to skrzyżowanie czasowe, możemy przetestować, czy kolizja „rzeczywiście” się wydarzyła i możemy rozwiązać te fałszywe alarmy:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

Jeśli zauważysz jakieś błędy w przykładach kodu, daj mi znać, nie wdrożyłem go jeszcze i dlatego nie mogłem go przetestować.

Tak długo, jak obszary zamiatane są zarówno zamknięte (bez przerw w granicy utworzonej przez linie krawędzi), będą działać następujące czynności (wystarczy zredukować testy kolizji do linii i linii-punktu / punktu-tri):

1. Czy ich krawędzie się stykają? (kolizje linia-linia) Sprawdź, czy jakaś linia krawędzi obszaru zamiatanego przecina się z jakąkolwiek linią krawędzi drugiego obszaru zamiatanego. Każdy obszar zamiatania ma 6 stron.

2. Czy mały jest w środku duży? (Użyj kształtów wyrównanych do osi (point-rect & point-tri)) Zmień orientację (obróć) obszary przeciągnięcia, tak aby większy był wyrównany względem osi i sprawdź, czy mniejszy jest wewnętrzny (sprawdzając, czy którykolwiek punkt narożny ( powinny być wszystkie lub żadne) znajdują się w obszarze przesuniętym względem osi). Odbywa się to poprzez rozkład heksów na tris i rekt.

To, który test wykonasz jako pierwszy, zależy od prawdopodobieństwa każdego z nich (wykonaj najczęściej występujący jako pierwszy).

Łatwiejsze może być użycie przesuniętego okręgu ograniczającego (kapsułka zamiast heksadecymalnej), ponieważ łatwiej jest podzielić go na dwa półokręgi i prostokąt, gdy jest wyrównany względem osi. .. Pozwolę ci narysować rozwiązanie