Utrata precyzji sprawdzania kolizji dwóch obróconych prostokątów

0

Hej,
Zaimplementowałem SAT, aby sprawdzić kolizje 2 obróconych prostokątów. Wszystko działa dobrze, ale zauważyłem, że gdy obiekty się poruszają, kontrola kolizji traci precyzję.

Ustawiłem prędkość kwadratów przez (v * 5) * dt. W mojej symulacji ustaliłem, że 5 to jeden metr. Wyczytałem, że przy większych/małych prędkościach może wystąpić utrata precyzji. Dlaczego tak się dzieje skoro sprawdzam to w statycznej klatce?

W pewnym momencie wykryto kolizję w tym miejscu obiektów:

Czy możecie mi doradzić, jak zachować wysoką precyzję sprawdzania kolizji? Gdzieś znalazłem informację, że multisampling może pomóc. Czy możesz mi wyjaśnić, co to jest, jak rozwiązuje problem utraty precyzji i jak go wdrożyć?

Napisałem swoje rozwiązanie w fpc (pascal / lazarus) ale to chyba nie ma znaczenia. Poniżej kod:

Kwadraty tworzone są w ten sposób

rectangle[0].x := position.x-15;
rectangle[0].y := position.y-35;
rectangle[1].x := position.x+15;
rectangle[1].y := position.y-35;
rectangle[2].x := position.x+15;
rectangle[2].y := position.y+26;
rectangle[3].x := position.x-15;
rectangle[3].y := position.y+26;

Obracane są tak:


for i:= 0 to 3 do
begin
tempX := rectangle[i].x - position.x;
tempY := rectangle[i].y - position.y;

// now apply rotation
rotatedX := tempX * cos(DegToRad(ang)) - tempY * sin(DegToRad(ang));
rotatedY := tempX * sin(DegToRad(ang)) + tempY * cos(DegToRad(ang));

tempRectangle[i].x := position.x + rotatedX;
tempRetangle[i].y := position.y + rotatedY;

end;

rotatedRectangle:=tempRectangle;

A tutaj samo sprawdzanie kolizji. Szczerze to rozumiem koncept ale nie zagłębiałem się w samo rozwiązanie. Przepisałem to po prostu na pascala z tego wątku i nawet działa ;)
https://stackoverflow.com/questions/10962379/how-to-check-intersection-between-2-rotated-rectangles/25261708

Typy:

TRectangle = array[0..3] of TMyPoint;

TMyPoint = record
x:real;
y:real;
end;

Sprawdzanie kolizji:

res:=true; 

for i := 0 to 1 do //2 cars
begin

    // for each polygon, look at each edge of the polygon, and determine if it separates
    // the two shapes
polygon := polygons[i];

    for i1 := 0 to Length(polygon)-1 do
    begin

        // grab 2 vertices to create an edge
        i2 := (i1 + 1) mod 4;
        p11 := polygon[i1];
        p22 := polygon[i2];

        // find the line perpendicular to this edge
        normal.x := p22.y - p11.y;
        normal.y := p11.x - p22.x;

        minA.assigned := false;
        maxA.assigned := false;
        // for each vertex in the first shape, project it onto the line perpendicular to the edge
        // and keep track of the min and max of these values
        for j := 0 to 3 do 
        begin
            projected := normal.x * rectangleA[j].x + normal.y * rectanglA[j].y;
            if ((minA.assigned = false) or (projected < minA.value)) then
                begin
                     minA.value := projected;
                     minA.assigned:=true;;
                end;
            if ((maxA.assigned = false) or (projected > maxA.value)) then
                begin
                     maxA.value := projected;
                     maxA.assigned := true;
                end;
        end;

        // for each vertex in the second shape, project it onto the line perpendicular to the edge
        // and keep track of the min and max of these values
        minB.assigned:=false;
        maxB.assigned:=false;
        for j := 0 to 3 do  
        begin
            projected := normal.x * rectanglB[j].x + normal.y * rectanglB[j].y;
            if ((minB.assigned = false) or (projected < minB.value)) then
                begin
                     minB.value := projected;
                     minB.assigned :=true;
                end;
            if ((maxB.assigned=false) or (projected > maxB.value)) then
                begin
                     maxB.value := projected;
                     maxB.assigned:=true;
                end;
        end;

        // if there is no overlap between the projects, the edge we are looking at separates the two
        // polygons, and we know there is no overlap
        if ((maxA.value < minB.value) or (maxB.value < minA.value)) then
            begin
                              res := false;

            end;
    end;
    end;

   result := res;
3

Multisampling to pewnie zwiększenie ilości zmiany pozycji na jedną zmianę pozycji. Np. jeśli obiekt poruszy się o 1 na osi Y, to poruszasz go 4 razy o 0.25 na osi Y i sprawdzasz kolizję po każdej zmianie pozycji.

0

Dostałem pomysły, że może mam problem z kolejnością punktów prostokąta albo ze zwracaniem wyniku z funkcji kolizji ale z tego co widzę to raczej wszystko jest ok. Spróbuję z tym multi samplingiem chociaż kolizja (moim zdaniem problematyczna) wykrywana jest przy zdecydownie większej odległości niż odległość przesunięcia.

1

Kolizję możesz też wykryć w inny sposób: Raycast.

Przed przesunięciem każdego pojazdu rzucasz promienie we wszystkie prostokąty, oprócz danego pojazdu (z którego prowadzimy promienie). Długość rzucanego promienia ustawiasz na tyle, żeby pokrył przemieszczenie pojazdu w danej klatce. Jeśli żaden promień nie trafi innego obiektu, to nie ma kolizji i można przesunąć obiekt o całą odległość przemieszczenia. Ilość rzucanych promieni trzeba dostosować do wielkości obiektów na scenie.

W ten sposób masz pewność, że nie dojdzie do przestrzelenia (w jednym kroku jeden prostokąt nie przejdzie przez drugi).

3

@karpov: spróbuj może zaimplementować algorytm z poniższego wideo. Dotyczy on wielokątów wypukłych, w tym prostokątów, więc powinien się nadać idealnie. Kod w tym wideo pisany jest w C++, ale bez kupy cukru, więc da się go łatwo przepisać na Pascala.

0

@furious programming: znam faceta :) Właśnie z jego filmiku o szukaniu raceline wziąłem kod i przepisałem na pascala :)

Okazało się, że jest jakiś problem z tym kodem na kolizje, który przepisałem na pascala. Albo w źródle coś jest nie tak albo przepisałem go źle. Wziąłem inny algorytm z tej strony: http://www.jeffreythompson.org/collision-detection/poly-point.php

Bardzo krótki i prosty. Zaimplementowałem go do projektu i działa świetnie, także problem chyba w implementacji poprzedniego :)

Dzięki Wam wszystkim za pomoc :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1