SAT with concave/complex polygon for collision response

[Bigfoot71]

Hello everyone

After having made several more or less successful attempts to solve the problem of collision between any polygons, whether between convex, non-convex or even complex polygons, I would like to know your opinion on the subject and how you would approach this problem.

I have already developed a collision detection function between convex polygons, which returns a direction vector with the penetration distance, based on the SAT algorithm in my polyMan module. If you have any comments to make on this subject, I am also a taker.

Code: Select all

local function polyInPolyConvex(polygon1, polygon2, approximate)

    local min_distance = huge
    local min_nx, min_ny

    local polygon = polygon1
    local reiterated

    ::reiterated::
    for i = 1, #polygon, 2 do

        -- Calculate the normals for each line of both polygons
        local x1, y1, x2, y2
        if i == #polygon - 1 then
            x1, y1 = polygon[i], polygon[i+1]
            x2, y2 = polygon[1], polygon[2]
        else
            x1, y1 = polygon[i], polygon[i+1]
            x2, y2 = polygon[i+2], polygon[i+3]
        end
        local nx, ny = y2-y1, x1-x2
        local length = sqrt(nx * nx + ny * ny)
        nx = nx / length
        ny = ny / length

        -- Checks the minimum distance between the two polygons along each normal
        local min1, max1, min2, max2 = huge, -huge, huge, -huge
        for j = 1, #polygon1, 2 do
            local dot = nx * polygon1[j] + ny * polygon1[j+1]
            min1 = min(min1, dot)
            max1 = max(max1, dot)
        end
        for j = 1, #polygon2, 2 do
            local dot = nx * polygon2[j] + ny * polygon2[j+1]
            min2 = min(min2, dot)
            max2 = max(max2, dot)
        end

        -- If the polygons do not overlap, there is no collision
        if min1 > max2 or min2 > max1 then
            return false
        end

        -- Get the penetration distance and keep the results if it is the current smallest
        local distance = min(max2 - min1, max1 - min2)
        if distance < min_distance then
            min_distance = distance
            min_nx, min_ny = nx, ny
            if max2 - min1 > max1 - min2 then
                min_nx = -min_nx
                min_ny = -min_ny
            end
        end

    end

    if not approximate and not reiterated then
        polygon, reiterated = polygon2, true
        goto reiterated
    end

    return true, min_nx, min_ny, min_distance

end

However, the results obtained with this function are obviously not suitable for concave or complex polygons. For these types of polygons, my latest attempt was to subdivide them into triangles and calculate, for example, an average of the direction vectors and overlaps This solution is one of the lightest and most convincing that I have found so far, but it is still far from perfect. You will find attached the code and images of my attempts (the test function does not yet use an optimized version of the collision detection function for triangles).

Code: Select all

local function polyInPolyComplex(polygon1, polygon2)

    local displacement_x, displacement_y = 0, 0
    local num_collisions = 0

    -- Triangulate polygons (using love.math.triangulate)
    local triangles1 = love.math.triangulate(polygon1)
    local triangles2 = love.math.triangulate(polygon2)

    -- Check each triangle for collision using polyInPolyConvex (SAT) function
    for i, tri1 in ipairs(triangles1) do
        for j, tri2 in ipairs(triangles2) do

            local collides, nx, ny, dist = polyInPolyConvex(tri1, tri2)

            if collides then

                -- Calculate displacement needed to separate polygons
                local displacement = dist / math.sqrt(nx * nx + ny * ny)
                local dx, dy = nx * displacement, ny * displacement

                -- Accumulate displacement
                displacement_x = displacement_x + dx
                displacement_y = displacement_y + dy
                num_collisions = num_collisions + 1

            end
        end
    end

    if num_collisions > 0 then
        -- Calculate average displacement
        displacement_x = displacement_x / num_collisions
        displacement_y = displacement_y / num_collisions
        return true, displacement_x, displacement_y
    else
        return false, 0, 0
    end

end

The replacement of the second concave polygon with the function written for this case:


Replace only the first polygon with this same function:


Do you have any suggestions to tackle this problem or even the solution let's be crazy because I already am a little crazy

If I forgot any details that you think are important, sorry in advance, but above all, don't hesitate.

I share with you the demo which is in gif, the `polyInPolyComplex` function is directly used there to replace the first polygon in parameter as it should do.

[pgimeno]

The result of pushing one polygon or the other should result in the same vectors, just with different signs. No idea what's wrong.

Anyway, the Minkowski difference is how I would approach this problem, no doubt. It's probably the easiest way to implement swept collisions.

[Bigfoot71]

Thank you very much for your suggestion, indeed I managed to implement collision detection between concave polygons earlier, but to obtain the right displacement vector and distance, it's still the same struggle...

Here's my current draft (I've been tinkering with it since earlier, sorry if there's something stupid that's not immediately obvious to me, it's just a test between two convex polygons that I wanted to do, don't pay attention to the name of the function):

Code: Select all

local function polyInPolyComplex(poly1, poly2)

    -- Calculation of the Minkowski difference between the two polygons
    -- And finds the deepest point in the Minkowski difference
    local min_distance = math.huge
    local min_nx, min_ny = 0, 0
    for i = 1, #poly1, 2 do
        for j = 1, #poly2, 2 do
            local x = poly1[i] - poly2[j]
            local y = poly1[i+1] - poly2[j+1]
            local distance = math.sqrt(x*x + y*y)
            if distance < min_distance then
                min_distance = distance
                min_nx = x / distance
                min_ny = y / distance
            end
        end
    end

    -- Calculate the penetration distance by projecting the points of the first polygon onto the collision normal
    local minA = math.huge
    local maxA = -math.huge
    for i = 1, #poly1, 2 do
        local dot = poly1[i] * min_nx + poly1[i+1] * min_ny
        if dot < minA then minA = dot end
        if dot > maxA then maxA = dot end
    end
    local minB = math.huge
    local maxB = -math.huge
    for i = 1, #poly2, 2 do
        local dot = poly2[i] * min_nx + poly2[i+1] * min_ny
        if dot < minB then minB = dot end
        if dot > maxB then maxB = dot end
    end

    local penetration = (maxA - minB) - (maxB - minA)

    if penetration < 0 then
        return true, min_nx, min_ny, penetration
    end

end

I'll still work on it later, something must be escaping me but I've been on it for too long.

[RNavega]

The replacement of the second concave polygon with the function written for this case
(...)

Replace only the first polygon with this same function (...)

I don't understand what you mean by these two statements. Is the first polygon always controlled by the user?

[Bigfoot71]

I don't understand what you mean by these two statements. Is the first polygon always controlled by the user?

Sorry if I wasn't clear enough.

The triangle represents the first polygon given as a parameter to the collision detection function (which also returns the opposite direction vector and the overlap to reposition the first polygon). In this example, the first polygon given as a parameter is indeed the one controlled by the user. (but might not be)

The second polygon given as a parameter is all the other static polygons (although if we apply the opposite vector to them, they could also be repositioned).

I already have a function that works very well for repositioning convex polygons, but when used with concave polygons, the applied distance (as well as the direction vector) corresponds to the convex hull of the concave polygon. Hence the reason why I wanted to create a separate function that would work perfectly with concave (or complex) polygon shapes.

However, the technique I am currently using (i.e. decomposing polygons into triangles and obtaining vectors and overlaps from an SAT function and taking an average) does not work well.

When we reposition the second polygon with the reversed vector, it is not very noticeable (but the problem is still there), the problem is mostly noticeable when we want to reposition the first polygon. The problem is that the average displacement is wrong when there are multiple triangle collisions between the polygons. The result is that the polygons are poorly repositioned and remain overlapping.

I also tried obtaining all the collision results between triangles, sorting them, and applying them one by one, but the result seems to be exactly the same strangely.

Sorry if I'm not yet super clear, I have trouble with English on technical terms. (you can even correct me)

[pgimeno]

Thank you very much for your suggestion, indeed I managed to implement collision detection between concave polygons earlier, but to obtain the right displacement vector and distance, it's still the same struggle...
[...]

Sorry but where do you implement the Minkowski difference?

Can you draw the Minkowski differences of the polygons in your program?

[Bigfoot71]

Of course, did I do something wrong? The function above didn't work and I was tired, I haven't returned to this project since yesterday.

The function I quickly rewrote for the display:

Code: Select all

local function drawMinkowskiDiff(poly1, poly2)

    local verts = {}
    for i = 1, #poly1-1, 2 do
        for j = 1, #poly2-1, 2 do
            table.insert(verts, poly1[i]-poly2[j])
            table.insert(verts, poly1[i+1]-poly2[j+1])
        end
    end

    local hull = pm.operations.convexHull(verts)
    love.graphics.polygon("line", hull)

end

Without convex-hull:


With convex-hull:

[RNavega]

I don't understand what you mean by these two statements. Is the first polygon always controlled by the user?

However, the technique I am currently using (i.e. decomposing polygons into triangles and obtaining vectors and overlaps from an SAT function and taking an average) does not work well.

When we reposition the second polygon with the reversed vector, it is not very noticeable (but the problem is still there), the problem is mostly noticeable when we want to reposition the first polygon. The problem is that the average displacement is wrong when there are multiple triangle collisions between the polygons. The result is that the polygons are poorly repositioned and remain overlapping.

Thanks for explaining. It looks like you have two different cases. In one case you have movable obstacles that the user polygon can push away while it always gets to go to its desired location. You seem to already have this happening (the first GIF).
In the other case you have the user polygon moving around and it collides against an immovable obstacle polygon, and it should 'slide' against that immovable obstacle.

Thinking how I'd try implementing the sliding case, you do a bunch of operations to find the first obstacle edge that the user polygon will collide against, then move the user obstacle away from that edge along its normal so it doesn't penetrate the obstacle anymore, then for the remainder of the distance that the user polygon has to move (based on the distance it wants to travel from the previous to the current frame), you move that remaining distance along that edge it collided against.

loveCollision.png (74.97 KiB) Viewed 3684 times

[pgimeno]

Thank you very much for your suggestion, indeed I managed to implement collision detection between concave polygons earlier, but to obtain the right displacement vector and distance, it's still the same struggle...

Okay, so for convex polygons, you have a line segment (of a point moving to another place) and a polygon, and you can check their intersection. I guess a decent separating vector would be one that is perpendicular to the impact side, right? That wouldn't be perfect, but it would at least be a good approximation in most cases.

For a "perfect" version which can apply also to non-convex polygons (assuming you get the Minkowski difference right), I believe you need to do it in multiple steps, pretty much like my AABB swept collision library (which I never released, sadly) did.

[Bigfoot71]

Thank you very much for your answers, I am a bit overwhelmed at the moment, I will repost when I have been able to make progress on this project or even if I have finally succeeded, let's hope!