Push rectangle out of line

[darkfrei]

Hi all!

Can you please help me to make the function to get the push-vector to move the rectangle from the line?
Partially works:

Code: Select all

local function signDistancePointToLine (px, py, lineX1, lineY1, lineX2, lineY2)
	local dx, dy = lineX2 - lineX1, lineY2 - lineY1
	local len = math.sqrt(dx * dx + dy * dy)
	local dist = ((lineY1 - py) * dx - (lineX1 - px) * dy) / len
	dx, dy = dx/len, dy/len
	return {dist = dist, dx=dx, dy=dy, px=px, py=py}
end

local function pushRectangleOutOfLine(rectX, rectY, rectWidth, rectHeight, lineX1, lineY1, lineX2, lineY2)
	local x1, y1 = rectX, rectY
	local x3, y3 = rectX+rectWidth, rectY+rectHeight
	local x2, y2 = x3, y1
	local x4, y4 = x1, y3
	local distances = {
		signDistancePointToLine (x1, y1, lineX1, lineY1, lineX2, lineY2),
		signDistancePointToLine (x2, y2, lineX1, lineY1, lineX2, lineY2),
		signDistancePointToLine (x3, y3, lineX1, lineY1, lineX2, lineY2),
		signDistancePointToLine (x4, y4, lineX1, lineY1, lineX2, lineY2),
	}
	local posiN, negaN = {}, {}
	for i, d in ipairs (distances) do
		if d.dist > 0 then
			table.insert (posiN, d)
		else
			table.insert (negaN, d)
		end
	end
	local dist, dx, dy = 0
	local px, py
	if #posiN == 1 then
		dist, dx, dy = posiN[1].dist, posiN[1].dx, posiN[1].dy
		px, py = posiN[1].px, posiN[1].py
	elseif #negaN == 1 then
		dist, dx, dy = negaN[1].dist, negaN[1].dx, negaN[1].dy
		px, py = negaN[1].px, negaN[1].py
	elseif #posiN > 1 then
		dist, dx, dy = posiN[1].dist, posiN[1].dx, posiN[1].dy
		px, py = posiN[1].px, posiN[1].py
	else
		dist, dx, dy = negaN[1].dist, negaN[1].dx, negaN[1].dy
		px, py = negaN[1].px, negaN[1].py
	end
	local pushVecX, pushVecY = -dist*dy, dist*dx
	print (pushVecX, pushVecY)
	return pushVecX, pushVecY, px, py
end


function love.load()
	rectX, rectY, rectWidth, rectHeight  = 100, 100, 200, 200
	lineX1, lineY1, lineX2, lineY2 = 50, 20, 200, 400
	pushVecX, pushVecY, PX, PY = pushRectangleOutOfLine(rectX, rectY, rectWidth, rectHeight, lineX1, lineY1, lineX2, lineY2)
end


function love.draw()
	love.graphics.setColor(1, 1, 1)
	love.graphics.rectangle("fill", rectX, rectY, rectWidth, rectHeight)
	love.graphics.setColor(1, 0, 0)
	love.graphics.line(lineX1, lineY1, lineX2, lineY2)
	love.graphics.setColor(0, 1, 0)
	love.graphics.line(PX, PY, PX + pushVecX, PY + pushVecY)
	love.graphics.setColor(1, 0, 0)
	love.graphics.rectangle("line", rectX+pushVecX, rectY+pushVecY, rectWidth, rectHeight)
end

function love.keypressed(k)
	if k == 'z' then
		lineX1, lineY1 = love.mouse.getPosition()
		pushVecX, pushVecY, PX, PY = pushRectangleOutOfLine(rectX, rectY, rectWidth, rectHeight, lineX1, lineY1, lineX2, lineY2)
	elseif k == 'x' then
		lineX2, lineY2 = love.mouse.getPosition()
		pushVecX, pushVecY, PX, PY = pushRectangleOutOfLine(rectX, rectY, rectWidth, rectHeight, lineX1, lineY1, lineX2, lineY2)
	end
	
   if k == 'escape' then
	  love.event.quit()
   end
end

As you see, it works when the line cuts just a one corner of rectangle.
But I've got the error on two corners cutting.

2023-02-23T16_55_57-Untitled.png (11.13 KiB) Viewed 2552 times

2023-02-23T16_59_51-Untitled.png (10.11 KiB) Viewed 2551 times

Press z and x to change the point:

[RNavega]

Hi, can you explain more?
I think both cases are the same: the line segment is cutting the rectangle into two pieces, where one piece includes 1 corner of the rectangle and the other piece includes 3 corners of the rectangle.

[togFox]

Did you work this out? I'm not too shabby with vectors but I'm not sure what the expected behaviour is.

[pgimeno]

I may be wrong, because the explanation is not clear, but I think darkfrei is looking for the separating vector between line and polygon (kinda like what HC does).

Intuitively, you want the polygon to be pushed by the shortest distance, so this method would work:

- find the areas of the two pieces of the polygon as cut by the line;
- from whichever area is smaller, take the vertex that is farthest from the line and find the perpendicular from that vector to the line.

A shortcut to avoid calculating the areas is to find which side of the line the centre of the polygon is at, and only consider vertices that are on the opposite side to that of the centre. Find the farthest and that's it.

Broken down into smaller steps, this is the algorithm:

1. Express the line as a point and a vector, if it is not already. If it's given by two points, just find the vector by subtracting the points, and take one of them as the point.
2. Calculate a normal to the line vector. If the vector is (vx, vy), the normal is simply (-vy, vx).
3. Calculate the centre of the polygon. For rectangles, that's simply the average of the X's and the average of the Y's.
4. Calculate a vector that goes from the point in the line to the centre of the polygon.
5. The sign of the dot product between the normal and the vector calculated in step 4 gives what side of the line the centre is. If it is zero, then it doesn't matter which side to take, so you can take it as if it was positive. Or negative, doesn't matter.
6. Calculate the dot product between the normal and each of the vectors from the point in the line to each vertex; consider only the vertices whose dot product has the opposite sign to that calculated in step 5.
7. If there are 0, you're done: the line doesn't intersect the polygon and there's no need to find a separating vector.
8. If there's 1, skip to step 10.
9. If there's 2 or 3, calculate the distance from each vertex to the line, and take the largest.
10. With that vertex, calculate the vector perpendicular to the line. That's the separating vector.

If it's not clear enough from the description, let me know and I'll try to express it as code.

However, when used for collision resolution, this method has the "bullet through wall" problem - if the object moves fast enough, it may end up on the opposite side of the line. The solution to that is, in steps 3 and 4, instead of using the centre of the polygon, to use the displacement vector of the object. And in step 6, you'd have to consider vertices whose dot product has the *same* sign, not different. In step 9 there may be 4 vertices too.

[Edited to clarify step 6, which missed some details]

[ivan]

I have attempted to address this problem in my fizzx library:
https://github.com/2dengine/fizzx/blob/ ... s.lua#L166
The caveat is that the segment will always push the rectangle perpendicular to its direction.
Fizzx uses this code for one-sided platforms.

[RNavega]

2. Calculate a normal to the line vector. If the vector is (vx, vy), the normal is simply (-vy, vx).

Nice, I forgot about that trick. I was going to suggest the cross-product with the 3D screen vector, (0, 0, 1).

But I was thinking of a different way to find the nearest collision vertex:

1. Find the perpendicular vector of the line segment. Not necessary to normalize it.
2. For every vertex of the polygon (in this case, a rectangle), make a vector from point A of the line segment to that vertex. Let's call these the "vertex vectors".
3. Get the dot product of each vertex vector with the perpendicular line vector. If the sign of all dot products are on the same side (all negative, or all positive), then the segment can't possibly cross the polygon. If a dot value is zero, then that vertex (edit: potentially) lies on the segment.
4. Get the dot product of each vertex vector with the line segment itself. If all the dot products are negative, or if all dot products are bigger than the dot product of the line segment with itself (i.e. its squared length), then the segment can't possibly cross the polygon. (Edit: although a simple test to see if point A or point B of the line segment are inside the boundong-box of the polygon should be a faster way to cull impossible collisions.)
5. Get the biggest dot products on each side of the perpendicular line vector. This will lead to two numbers: the biggest dot on the positive side, and the biggest on the negative side.
   Between the two, the smaller one and its originating vertex are the collision vertex being searched for.

[pgimeno]

To be clear, when I say a normal vector I don't mean a normalized normal vector, although in many contexts normals are assumed to be unit vectors. And the cross-product would have yielded the same result, after cancellation of zeros

Up to step 3, our methods are pretty similar. I assumed the line to be infinite; for line segments it's more complex to decide what's the shortest separating vector, especially when at least one end of the segment is inside the rectangle: in some cases a vector perpendicular to one side of the rectangle will be shorter than a vector perpendicular to the line segment.

[RNavega]

And the cross-product would have yielded the same result, after cancellation of zeros

I see, if you use variable names instead of values, like A=(vx, vy, 0), B=(0, 0, 1), and calculate the cross-product all the way to the end, you'll have that (-vy, vx, 0). That's very interesting.

I had a some free time so I implemented the method I wrote in that post:

Code: Select all

io.stdout:setvbuf('no')


local polygonPoints = {
    75, 69,
    303, 49,
    420, 176,
    342, 407,
    326, 176,
    138, 427
}
if #polygonPoints % 2 ~= 0 then
    error('Polygon coordinates are missing a value')
end

local segmentPoints = {
    221, 507,
    500, 417
}

local hoveredPoint = nil
local draggedPoint = nil
local draggedDelta = {0.0, 0.0}


function drawCollisionInfo()
    -- Thanks to P. Gimeno: perpendicular of a 2D vector {vx, vy} is {-vy, vx}.
    -- Where the segment is {ax, ay, bx, by}.
    -- Where vx = (bx - ax), vy = (by - ay).
    local segmentVectorX = segmentPoints[3] - segmentPoints[1]
    local segmentVectorY = segmentPoints[4] - segmentPoints[2]
    local perpendicularX = -segmentVectorY
    local perpendicularY = segmentVectorX

    local positiveBiggestDot = 0.0
    local negativeBiggestDot = 0.0
    local indexPositiveBiggest = nil
    local indexNegativeBiggest = nil

    love.graphics.setLineWidth(1.0)
    
    -- Debug: draw the line perpendicular vector.
    --[[
    love.graphics.setColor(1, 0, 1, 1)
    love.graphics.line(segmentPoints[1], segmentPoints[2],
                       segmentPoints[1]+perpendicularX, segmentPoints[2]+perpendicularY)
    ]]
    
    love.graphics.setColor(0, 1, 1, 1)

    for index = 1, #polygonPoints, 2 do
        local vertexVectorX = polygonPoints[index] - segmentPoints[1]
        local vertexVectorY = polygonPoints[index+1] - segmentPoints[2]

        local dot = vertexVectorX * perpendicularX + vertexVectorY * perpendicularY
        if dot > 0.0 then
            if dot > positiveBiggestDot then
                positiveBiggestDot = dot
                indexPositiveBiggest = index
            end
        else
            if dot < negativeBiggestDot then
                negativeBiggestDot = dot
                indexNegativeBiggest = index
            end
        end
    end
    
    if not (indexNegativeBiggest and indexPositiveBiggest) then
        -- All polygon points are on the same side of the line segment, so
        -- the segment can't possibly cross the polygon.
        return
    else
        local index = nil
        if positiveBiggestDot < -negativeBiggestDot then
            index = indexPositiveBiggest
        else
            index = indexNegativeBiggest
        end
        
        local vertexVectorX = polygonPoints[index] - segmentPoints[1]
        local vertexVectorY = polygonPoints[index+1] - segmentPoints[2]
        local dot = vertexVectorX * segmentVectorX + vertexVectorY * segmentVectorY
        local vectorScale = dot / (segmentVectorX * segmentVectorX + segmentVectorY * segmentVectorY)
        local collisionX = segmentPoints[1] + segmentVectorX * vectorScale
        local collisionY = segmentPoints[2] + segmentVectorY * vectorScale
        
        love.graphics.line(polygonPoints[index], polygonPoints[index+1],
                           collisionX, collisionY)
        love.graphics.circle('fill', polygonPoints[index], polygonPoints[index+1], 4.0)
        love.graphics.circle('fill', collisionX, collisionY, 4.0)
    end
end


function love.draw()
    love.graphics.setColor(1, 1, 1, 1)
    love.graphics.print('Click-drag the yellow dots to move the line segment.', 10, 10)

    love.graphics.setLineWidth(2.0)
    love.graphics.polygon('line', polygonPoints)

    love.graphics.setColor(1, 0, 0, 1)
    love.graphics.line(unpack(segmentPoints))

    love.graphics.setColor(1, 1, 0, 1)
    love.graphics.circle('fill', segmentPoints[1], segmentPoints[2], 4.0)
    love.graphics.circle('fill', segmentPoints[3], segmentPoints[4], 4.0)

    if hoveredPoint then
        local xIndex = (hoveredPoint - 1) * 2 + 1
        love.graphics.circle('line', segmentPoints[xIndex], segmentPoints[xIndex + 1], 12.0)
    end

    drawCollisionInfo()
end


function updateHoveredPoint(mx, my)
    local distanceSquared = ((mx - segmentPoints[1]) * (mx - segmentPoints[1])
                             + (my - segmentPoints[2]) * (my - segmentPoints[2]))
    if distanceSquared < (12.0 * 12.0) then
        hoveredPoint = 1
        return
    end

    distanceSquared = ((mx - segmentPoints[3]) * (mx - segmentPoints[3])
                       + (my - segmentPoints[4]) * (my - segmentPoints[4]))
    if distanceSquared < (12.0 * 12.0) then
        hoveredPoint = 2
        return
    end

    hoveredPoint = nil
end


function updateDraggedPoint(mx, my)
    local xIndex = (hoveredPoint - 1) * 2 + 1
    segmentPoints[xIndex]     = mx + draggedDelta[1]
    segmentPoints[xIndex + 1] = my + draggedDelta[2]
end


function love.mousemoved(mx, my)
    if draggedPoint then
        updateDraggedPoint(mx, my)
    else
        updateHoveredPoint(mx, my)
    end
end


function love.mousepressed(mx, my, button)
    if hoveredPoint then
        local xIndex = (hoveredPoint - 1) * 2 + 1
        draggedDelta[1] = segmentPoints[xIndex] - mx
        draggedDelta[2] = segmentPoints[xIndex + 1] - my
        draggedPoint = hoveredPoint
    else
        draggedPoint = nil
    end
end


function love.mousereleased(mx, my, button)
    draggedPoint = nil
end


function love.keypressed(key)
    if key == 'escape' then
        love.event.quit()
    end
end

Edit: removed a couple of unused variables.

[pgimeno]

I had a some free time so I implemented the method I wrote in that post:

As I said, for line segments things get more complex. Your algorithm seems to correctly solve the infinite line problem, but not the line segment problem. In the image below, I've drawn two separating vectors that the algorithm does not consider.

In this case, the shortest is the green one. And for collision resolution, shortest wins (or should).

I guess it shouldn't be too difficult to create an algorithm that solves the separating vector between segment and rectangle. Between segment and arbitrary concave polygon, even if not self-intersecting, it sounds quite more difficult.

[RNavega]

Hm, haven't tested it, but I think you can imagine the segment as a slice of an infinite rectangular region. So you only consider the geometry that fall within the region/crosses it.

SeparatingVectorsProblem.png (21.75 KiB) Viewed 2177 times

This can be done by mapping the polygon to a translated & rotated space, where point A of the segment is the origin, and the segment runs along the X axis. Then collecting all polygon points/lines who interact with the [0, +segment_length] range.

But OP has abandoned us. Come back OP