Collision detection for moving 2D objects

Question

After implementing SAT (separating axis theorem) and not being happy with it only working on stationary shapes, this in theory allowing for fast objects to glitch through others, I came up with this approach to detect collisions between moving objects.

Algorithm explained

The idea is quite simple:

I figured that, if two shapes A and B aren't intersecting in their starting positions and A moves relative to B, the two shapes collide if and only if
a) any vertex of A crosses a segment of B or
b) any segment of A touches ("sweeps over") a vertex of B.

A vertex of A collides with a segment of B when the segment from A to A + V, V being the velocity of A (aka. it's movement) intersect. That is implemented in the line intersection method of the line class (see below).

Lastly, if I loop through all vertices in A and B and let them collide with all segments of the respective other and repeat the same with B and A with the movement vector turned 180 degrees, the shortest distance any point can travel until a collision happens is the shortest distance A can travel until it collides with B.

To figure out if two segments intersect, I first trasnform them both so that the first segment goes from (0, 0) to (1, 0). Then, the two segments intersect if and only if the second segment cuts the X axis between 0 and 1, which is trivial to implement.

Implementation

Collision detection itself

local function single(a, b, v)
    local vertices = {a:vertices()}
    local segments = {b:segments()}

    local min_intersection
    for idx,vertex in ipairs(vertices) do
        local v_end = vertex + v
        local projection = line(vertex.x, vertex.y, v_end.x, v_end.y)
        for idx,segment in ipairs(segments) do
            min_intersection = nil_min(min_intersection, projection * segment)
        end
    end

    if min_intersection == 1 then return nil end
    return min_intersection
end

function module.movement(a, b, v)
    return nil_min(single(a, b, v), single(b, a, -v))
end

Line intersection

intersection = function(self, other)
    if not is_line(other) then error("Invalid argument; expected line, got "..type(other), 2) end

    local origin, base = self:vectors()

    local a = vector_2d(other.x_start, other.y_start)
    local b = vector_2d(other.x_end,   other.y_end  )

    a = (a - origin):linear_combination(base)
    b = (b - origin):linear_combination(base)

    -- Both points are above or below X axis
    if a.y < 0 and b.x < 0 or a.y > 0 and b.y > 0 then
        return nil
    end

    -- A always has the smallest X value
    if a.x > b.x then
        a, b = b, a
    end

    local x0 = a.x + (b.x-a.x) * a.y / (a.y-b.y)

    if x0>=0 and x0<=1 then
        return x0
    else
        return nil, x0
    end
end

Cheaty linear combination

As you can see, I only need the linear combination of a given vector and that same vector rotated by 90 degrees, making it quite trivial. Implementation with two vectors is irrelevant to this situation and may get implemented in the future should I need it.

linear_combination = function(self, basis_x, basis_y)
    if basis_y then
        error("Not Implemented!", 2)
    else -- Assumes basis_y is basis_x + 90 degrees
        local angle = self:angle() - basis_x:angle()
        local f_len = self:length() / basis_x:length()
        return vector_2d(
            round(f_len * cos(angle)),
            round(f_len * sin(angle))
        )
    end
end;

Okay, that's pretty much it. I have done some testing using busted and it seems to work, but I am not sure if I may have overlooked some stupid mistake that might lead to complications later on. I am also unsure if that algorithm will be fast enough. Considering 3D games do complex collision detection these days, I would assume even a slightly slower algorithm wouldn't impact a 2D game on a modern gaming PC, but since this is löve, would this run on a mid-tier android phone or tablet at an acceptable framerate?

Assumptions:

• Any game this might be used in will not have an unhealthily high number of collisions
• It is purely meant for 2D, no intention to try it in 3D
• most shapes will be rectangles, on average they may have at most 10 or so vertices
• Vectors and segments are implemented using LuaJIT FFI structs, not Lua Tables

As a small extra: The angle at which the first vertex collides with a segment of the other shape, can easily be used to obtain the angle to apply a force to both shapes at the point of collision. This can mean anything from just bouncing the entire object without considering center of mass, to more advanced phyiscal calculations that apply an actual force to the object. While this is interesting and a nice feature of the algorithm, it is trivial to implement and thus out of scope for the actual question.

Answer 1

I'm not experienced in LUA, so I can't comment on the code style itself. But I can on the algorithm and implementation.

---

Bugs:

• I'm fairly confident this should be b.y < 0, not b.x < 0.

  -- Both points are above or below X axis
  if a.y < 0 and b.x < 0 or a.y > 0 and b.y > 0 then
      return nil
  end
  

• Possible division by zero: if the line segment, after transformation happens to be from (x.a,0) to (x.b,0), then neither will a.y and b.y be both greater than zero nor both less than zero, so the following code will be executed:

  local x0 = a.x + (b.x-a.x) * a.y / (a.y-b.y)
  

---

There does not seem to be any filtering of possible colliding objects; just a brute-force checking of all vertices in one object (A) against all edges in another object (B), and all vertices in the other object (B) with all edges in the former (A). Given that the game "will not have an unhealthily high number of collisions", some fast rejection code should be used.

First, compute the V_len = sqrt(V.x^2 + V.y^2), and a normal vector N = (V.x/V_len, V.y/V_len), and a perpendicular vector P = (N.y, -N.x).

Compute the projection (dot product) of the bounds of the moving object onto these two vectors. For example, if all objects have a circular bounds, described by a centre point (A.cx, A.cy) and radius A.r, then the projection of the centre on the P vector is the value Pa = A.cx * P.x + A.cy * P.y, and the projection ranges from Pa - A.r to Pa + A.r. When projecting the moving object on the N vector, add the object's movement to the project, eg Na = A.cx * N.x + A.cy * N.y, projection ranges from Na - A.r to Na + A.r + V_len.

For every other object, compute the projection (dot product) of the object's bounds onto these two vectors N and P. If the range of the projections for the moving object overlaps the range of the projections of a stationary object, on both projections, then a collision is possible between that object and the moving object.

In the following picture, the black square in moving in direction V. The projection of the black square & purple triangle overlap on the N projection, but not the P projection, so no collision is possible. The projection of the black square & green diamond overlap in the P projection, but not the N projection, so again no collision is possible. If V was slightly larger, the projections of the black square & green diamonds would overlap, so a collision would be possible, and the intersection of the line segments would need to be computed.

You don't need to use a circular boundary. You could use the bounding box, or other bounding polygon. Just compute the min/max of dot product of all vertices in the bounding polygon on each of the two vectors N & P.

Once you've decided that the object could collide (projections overlap on both the movement and perpendicular axis), then you can start computing whether the line segments overlap.

Computing the angle of the segments, in order to transform them to (0,0)-(1,0) is an expensive operation. It is easy to compute the intersection of two line segments. See how do you detect where two line segments intersect? Simple multiplications and divisions; no transcendental mathematical functions are necessary.