LÖVE

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

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

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

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