当遇到锐角时，分离轴定理函数失效。

Question

这是我为LOVE2D引擎在Lua中制作的一个小库，它使用分离轴定理来解决碰撞问题。

当我让我的SAT程序工作起来，并开始使用各种多边形进行测试时，我感到非常开心。它在大多数情况下都可以正常工作，并且为它们提供了正确的最小平移向量。奇怪的是-如果两个形状都有锐角，那么这些角会导致程序失败，返回碰撞，即使形状没有接触，或者更不寻常的是，它会给出令人费解的最小平移向量。我已经检查了返回法线的函数-因为我觉得这是可能出错的第一点，但它似乎运行良好。

这是处理我的碰撞的主要功能。

function findIntersection(shape1, shape2)
--Get axes to test.
--MTV means 'minimum translation vector' ie. the shortest vector of intersection
local axes1 = {}
local axes2 = {}
local overlap = false
local MTV = {direction = 0, magnitude = 99999}

for i, vert in pairs(shape1.hitbox) do
    nrm = getNormal(shape1.hitbox, i)
    table.insert(axes1, nrm)
end
for i, vert in pairs(shape2.hitbox)do
    nrm = getNormal(shape2.hitbox, i)
    table.insert(axes2, nrm)
end

--print(#axes1 .. '    ' .. #axes2)

--now that we have the axes, we have to project along each of them
for i, axis in pairs(axes1) do
    test1 = hitboxProj(shape1, vectorToCoord(axis.direction, axis.magnitude))
    test2 = hitboxProj(shape2, vectorToCoord(axis.direction, axis.magnitude))
    if test2.max > test1.min or test1.max > test2.min then
        if test2.max - test1.min < MTV.magnitude then
            MTV.direction = axes1[i].direction
            MTV.magnitude = test2.max - test1.min
        end
    else
        return false
    end
end

--now that we have the axes, we have to project along each of them
for i, axis in pairs(axes2) do
    test1 = hitboxProj(shape1, vectorToCoord(axis.direction, axis.magnitude))
    test2 = hitboxProj(shape2, vectorToCoord(axis.direction, axis.magnitude))
    if test2.max > test1.min or test1.max > test2.min then
        if test2.max - test1.min < MTV.magnitude then
            MTV.direction = axes2[i].direction
            MTV.magnitude = test2.max - test1.min
        end
    else
        return false
    end
end

return {MTV}
end

我的项目文件在Github上，链接为https://github.com/ToffeeGoat/ToffeeCollision

- David Kitchener

---

在获取方向函数中，尝试将 math.atan(y/x) 替换为 math.atan2( y, x )。 - DavisDude

Answer 1

这是一个不错的开始，你的代码相当清晰。有一些地方可以改进，特别是我注意到你的所有函数都是全局的。首先，你希望将所有的函数存储在一个“模块”中，以避免污染_G空间。其他的东西都可以使用局部变量。

请注意，写诸如x == 0这样的检查并不健壮，这个检查只适用于整数，在涉及浮点数运算时可能会失败。我建议为库中的每个函数编写一个简单的测试脚本。

另外，使用Lua的return xCoord, yCoord可以返回多个值，而不是写return {x = xCoord, y = yCoord}。创建大量的中间表会给垃圾回收器带来压力。

你的一些代码需要重新编写，比如“getDirection”函数。我的意思是，对于这种情况已经有了众所周知的技巧。请查看我的教程，里面有一些示例：https://2dengine.com/?p=vectors#Angle_between_two_vectors

其中有一些愚蠢的东西，例如function sq(x) return x*x end。你知道在Lua中可以写成x^2吗？ addDeg可以被取模运算符所替代：newAng = (angle + addition)%360 同时请注意，使用度数没有任何好处 - 我建议仅使用弧度。你已经在使用以弧度为单位的math.pi了。无论如何，你必须选择弧度或角度并坚持使用其中之一。不要在你的代码中混合使用两种单位。

我不想太挑剔，因为你的代码不错，你只需要习惯一些最佳实践。这是我的另一个教程： https://2dengine.com/?p=intersections

- 2dengine

Answer 2

工作函数：

local function checkSATCollision(vertices1, vertices2)
    -- Separating Axis Theorem with Minimum Translation Vector
    local function projectVertices(vertices, dx, dy)
        local min, max = math.huge, -math.huge
        local indexMin, indexMax
        for i = 1, #vertices-1, 2 do
            local dotProduct = vertices[i]*dy-vertices[i+1]*dx
            if dotProduct < min then 
                min = dotProduct 
                indexMin = i
            end
            if dotProduct > max then 
                max = dotProduct 
                indexMax = i
            end
        end
        return min, max, indexMin, indexMax
    end
    
    local minDist = math.huge
    local dx, dy
    local x1, y1, x2, y2 = vertices1[#vertices1-1], vertices1[#vertices1],vertices1[1], vertices1[2]
    for i = 1, #vertices1-1, 2 do
    local nx, ny = x2-x1, y2-y1
        local length = math.sqrt(nx*nx+ny*ny)
    nx, ny = nx/length, ny/length
    local min1, max1, indexMin1, indexMax1 = projectVertices(vertices1, nx, ny)
    local min2, max2, indexMin2, indexMax2 = projectVertices(vertices2, nx, ny)
        local dist = math.min (max2-min1, max1-min2)
    if dist < 0 then
      return false -- no collision
        elseif minDist >= dist then
            minDist = dist
            dx, dy = ny, -nx
        end
        x1, y1, x2, y2 = x2, y2, vertices1[i+2], vertices1[i+3]
  end
    if minDist*2^45 < 1 then -- rounding almost 0 to 0
        minDist = 0
    end
  return minDist, minDist*dx, minDist*dy -- collision and direction
end

并且：

-- example: 
local vertices1 = {0,0, 200,0, 0,100}
local vertices2 = {50,50, 60,80, 80,60}
local dist, dx, dy = checkSATCollision(vertices1, vertices2)
print (dist, dx, dy) -- 24.149534156998 10.8    21.6
local str = ''
for i = 1, #vertices2-1, 2 do
    vertices2[i] = vertices2[i] + dx
    vertices2[i+1] = vertices2[i+1] + dy
    str = str .. vertices2[i] .. ', ' .. vertices2[i+1] .. ', '
end
print (str) -- 58.8, 70.6, 70.8, 101.6, 90.8, 81.6, 
dist, dx, dy = checkSATCollision(vertices1, vertices2)
print (dist, dx, dy) -- 0   0.0 0.0

- darkfrei