Circle V Rectangle Collision Response

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
nikneym
Citizen
Posts: 56
Joined: Sat Mar 09, 2013 1:22 pm
Contact:

Circle V Rectangle Collision Response

Post by nikneym » Tue Oct 20, 2020 6:43 pm

Hi, I'm trying to make basic physics simulations. I implemented Coding Math's Verlet Integration Tutorial to my project and I wanted to add a rectangle to interact with. Problem is, I don't know how to handle circle V rectangle collision.

First I tried to make a solid rectangle. It went decently good and made circle couldn't pass through it. Though I don't know if its the right way. (collision detection script implemented from here):

Code: Select all

function collision()
	local testX = circle.x
	local testY = circle.y

	if circle.x < rect.x then
		testX = rect.x
	elseif circle.x > rect.x + rect.w then
		testX = rect.x + rect.w
	end

	if circle.y < rect.y then
		testY = rect.y
	elseif circle.y > rect.y + rect.h then
		testY = rect.y + rect.h
	end

	local distX = circle.x - testX
	local distY = circle.y - testY

	local distance = math.sqrt(distX ^ 2 + distY ^ 2)

	if distance <= circle.rad then
		--COLLISION RESPONSE-----
		local unitX, unitY = distX / distance, distY / distance

		circle.x = testX + circle.rad * unitX
		circle.y = testY + circle.rad * unitY
	end
end
Then I wanted to make circle bounce whenever it intersect with rectangle and that went pretty bad...

Code: Select all

function collision()
	local testX = circle.x
	local testY = circle.y

	if circle.x < rect.x then
		testX = rect.x
	elseif circle.x > rect.x + rect.w then
		testX = rect.x + rect.w
	end

	if circle.y < rect.y then
		testY = rect.y
	elseif circle.y > rect.y + rect.h then
		testY = rect.y + rect.h
	end

	local distX = circle.x - testX
	local distY = circle.y - testY

	local distance = math.sqrt(distX ^ 2 + distY ^ 2)

	if distance <= circle.rad then
		--COLLISION RESPONSE-----
		local unitX, unitY = distX / distance, distY / distance

		circle.x = testX + circle.rad * unitX
		circle.y = testY + circle.rad * unitY

		if circle.x < rect.x then
			circle.oldx = circle.x + vx * bounce
		elseif circle.x > rect.x + rect.w then
			circle.oldx = circle.x + vx * bounce
		end

		if circle.y < rect.y then
			circle.oldy = circle.y + vy * bounce
		elseif circle.y > rect.y + rect.h then
			circle.oldy = circle.y + vy * bounce
		end
		-------------------------
		return true
	else
		return false
	end
end
My whole Lua code looks like this (both intersection codes included):

Code: Select all

mouse    = love.mouse
graphics = love.graphics
keyboard = love.keyboard

local rect = {
	x = 300,
	y = 200,
	w = 200,
	h = 100,
}

local circle = {
	x = 10,
	y = 10,

	oldx = 5,
	oldy = 5,

	rad = 30,
	speed = 30,
}

local bounce   = 0.9
local gravity  = 0.5
local friction = 0.999

function collision()
	local testX = circle.x
	local testY = circle.y

	if circle.x < rect.x then
		testX = rect.x
	elseif circle.x > rect.x + rect.w then
		testX = rect.x + rect.w
	end

	if circle.y < rect.y then
		testY = rect.y
	elseif circle.y > rect.y + rect.h then
		testY = rect.y + rect.h
	end

	local distX = circle.x - testX
	local distY = circle.y - testY

	local distance = math.sqrt(distX ^ 2 + distY ^ 2)

	if distance <= circle.rad then
		--COLLISION RESPONSE-----
		local unitX, unitY = distX / distance, distY / distance

		circle.x = testX + circle.rad * unitX
		circle.y = testY + circle.rad * unitY

		if circle.x < rect.x then
			circle.oldx = circle.x + vx * bounce
		elseif circle.x > rect.x + rect.w then
			circle.oldx = circle.x + vx * bounce
		end

		if circle.y < rect.y then
			circle.oldy = circle.y + vy * bounce
		elseif circle.y > rect.y + rect.h then
			circle.oldy = circle.y + vy * bounce
		end
		-------------------------
		return true
	else
		return false
	end
end

function love.update(dt)
	--circle.x, circle.y = mouse.getPosition()
	vx, vy = (circle.x - circle.oldx) * friction, (circle.y - circle.oldy) * friction

	circle.oldx, circle.oldy = circle.x, circle.y

	circle.x, circle.y = circle.x + vx, circle.y + vy + gravity

	if circle.x + circle.rad > graphics.getWidth() then
		circle.x = graphics.getWidth() - circle.rad
		circle.oldx = circle.x + vx * bounce
	elseif circle.x < 0 then
		circle.x = 0
		circle.oldx = circle.x + vx * bounce
	end

	if circle.y + circle.rad > graphics.getHeight() then
		circle.y = graphics.getHeight() - circle.rad
		circle.oldy = circle.y + vy * bounce
	elseif circle.y < 0 then
		circle.y = 0
		circle.oldy = circle.y + vy * bounce
	end

	if keyboard.isDown("left") then
		circle.x = circle.x - circle.speed * dt
	elseif keyboard.isDown("right") then
		circle.x = circle.x + circle.speed * dt
	end
end

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

	if key == "space" then
		circle.y = circle.y - 10
	end
end

function love.draw()
	graphics.setColor(255, 255, 255)
	graphics.rectangle("fill", rect.x, rect.y, rect.w, rect.h)

	graphics.print("Circle X: " .. circle.x .. "\nCircle Y: " .. circle.y, 10, 10)

	if collision() then
		graphics.setColor(255, 40, 40)
	else
		graphics.setColor(0, 255, 255)
	end

	graphics.circle("fill", circle.x, circle.y, circle.rad)
end
I also had some understanding issues with Verlet Integration. It looks like oldx and oldy variables are used like velocity properties. Couldn't we just use velocity values? Thank you for your interest.

User avatar
pgimeno
Party member
Posts: 2414
Joined: Sun Oct 18, 2015 2:58 pm

Re: Circle V Rectangle Collision Response

Post by pgimeno » Wed Oct 21, 2020 2:08 am

Let me start with the last question of your post.
nikneym wrote:
Tue Oct 20, 2020 6:43 pm
I also had some understanding issues with Verlet Integration. It looks like oldx and oldy variables are used like velocity properties. Couldn't we just use velocity values?
If you want to use Verlet, you have to play by its rules. There are other integrators that use velocity, but Verlet is a pretty good one and it uses the difference between the old position and the new position as an indicator of the velocity. You can think of it from the standpoint of a classic integrator: new position = old position + v * dt, therefore v * dt = new position - old position. Note that my purpose with posting this formula is to give you a bit of an intuition of how the velocity is represented, but you can't use it to derive the exact actual velocity because the integrator is different.

nikneym wrote:
Tue Oct 20, 2020 6:43 pm
Then I wanted to make circle bounce whenever it intersect with rectangle and that went pretty bad...
I don't even know what vx is there, but never mind. Bouncing against a side is very easy: once a collision is detected, you have to mirror both the new and the old positions with respect to the side in question at a radius distance. For example, against the left side:

Code: Select all

  circle.oldx = circle.oldx + 2 * (rect.x - circle.rad - circle.oldx)
  circle.x = circle.x + 2 * (rect.x - circle.rad - circle.x)
To understand it better, look at this diagram. old and new are circle.oldx/oldy and circle.x/y, respectively, while old' and new' are the desired output of the calculation. That way, from the point of view of the Verlet integrator, the ball was coming from the right and going left, which produces exactly the effect we want.

Image

With the right side, the formula would be:

Code: Select all

  circle.oldx = circle.oldx + 2 * (rect.x + rect.w + circle.rad - circle.oldx)
  circle.x = circle.oldx + 2 * (rect.x + rect.w + circle.rad - circle.x)
Bouncing against a corner is a lot trickier. You first need the position of the centre of the circle at the time of the collision. That's the first point along the path from old to new, where the distance from said point to the collided corner equals the radius of the circle.

Now you're in this situation:

Image

The red cross represents the centre of the circle at the time of the collision. The crossing line is the line that you need to bounce against, and n is the normal vector of the collision. For the reflection formula, you actually need the tangent vector, which is the normal rotated 90° in any direction (i.e. exchange x and y and then put a minus sign in front of one of them; for example: tgx, tgy = ny, -nx). This tangent needs to be normalized before using the reflection formula; if done correctly, its length is the radius of the circle, so just divide it by the radius.

In vector form, If cxy is the position of the centre of the circle at the instant of the collision, oldxy is the old position, xy is the new position, and tgxy is the normalized tangent vector, the formula for finding the new, bounced oldxy and xy points is:

Code: Select all

  oldxy = cxy + tgxy * dot(oldxy - cxy, tgxy)
  xy = cxy + tgxy * dot(xy - cxy, tgxy)
This is pseudocode, not code; you need to separate xy into circle.x and circle.y, oldxy into circle.oldx and circle.oldy, cxy into cx and cy, and tgxy into tgx and tgy, and do the operations separately for each component.

So, all that is left is knowing how to calculate cx and cy (the centre of the circle as it collides with the corner). We have a point, oldxy, and a vector, vxy = xy - oldxy; we want to calculate the fraction of this vector, t, such that oldxy + t * (xy - oldxy) results in the circle touching the corner. That is, solve for t in this equation: dist(oldxy + t * vxy, cornerxy) = circle.rad. We also want t to be the lowest possible value, as long as it is between 0 and 1, so pick up the lowest solution that is between 0 and 1.

Let coxy = oldxy - cornerxy, for brevity. Separating the components, resolving dist and squaring both sides, we have:

(cox + t * vx)^2 + (coy + t * vy)^2 = circle.rad^2

which is a quadratic equation:

Code: Select all

A * t^2 + B * t + C = 0
where
A = vx^2 + vy^2
B = 2*(cox*vx + coy*vy)
C = cox^2 + coy^2 - circle.rad^2
Solving it will give you two solutions.

Finally, calculate cxy = oldxy + t0 * vxy, where t0 is the solution that is closest to 0 and greater than 0. EDIT: If both are out of the range 0 <= t <= 1, there's no collision, therefore nothing to do.

(edited to fix typos and add note)
Last edited by pgimeno on Wed Oct 21, 2020 1:49 pm, edited 3 times in total.

User avatar
ivan
Party member
Posts: 1655
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Circle V Rectangle Collision Response

Post by ivan » Wed Oct 21, 2020 5:46 am

Generally speaking you should probably stick to AABBs as much as possible. There is very little advantage to having both rects and circles in your collision code.
Having said that one simple technique is to first find the nearest point on the edge of the rectangle from the center of the circle. The vector between the nearest point and the center of the circle if your "separation" vector. If the center of the circle is inside the rect than that's a special case where you can treat both as rectangles.
Check out my tutorial for an example:
https://2dengine.com/?p=intersections#C ... _rectangle

Post Reply

Who is online

Users browsing this forum: Bing [Bot] and 36 guests