2d Circle vs box intersection point

[serengeor]

I was trying to figure out how to calculate a point of intersection between a box and a circle but with no success.
Searching around the internet I only found a way to calculate if circle and box collide (which is fairly simple).
Box->Box, Circle->Circle intersection points are quite easy, but when it comes to Circle->Box, I can't quite find the way to calculate it

Any info on this would be apreciated

[Mel]

A box has 4 edges, so, a circle->rectangle intersection is 4 times a circle->edge intersection, isn't it?

[serengeor]

A box has 4 edges, so, a circle->rectangle intersection is 4 times a circle->edge intersection, isn't it?

By edge you mean lines that connect 4 points of circle?
Yeah, that's how you know if they intersect, but the problem is that I need the point in the middle of intersecting parts (or contact normal?).

Maybe I should rephrase the question to: how can I get the contact normal from box->circle intersection.

[REDDemon]

Intersection point --> see intersection between a line (your edge) and your circle
normal --> take point of intersection (or average of the 2 points of intersection if you allows small overlaps for box and circle)

If you assume no friction then the result of collision is that box can start rotating after collision while circle can't rotate.

To see if box starts rotating you should check if collision point is aligned with both mass center of circle and mass center of box.

If mass centers are not algined with collision point than box apply a F*b*s torque to box where b is distance between collision point and minimum distance between collision point and line that goes from one center to another. and where F is still to be dermined and is the force, while "s" is time of contact. Since in collision F is big and s is small and this can lead to errors you should usually want to consider only the F*s quantity.

You should also check about collisions for see wich is the change of speed and energy change after 2 bodies collide.

If you assume circle/square elastic or with friction things are even harder (infact you want to do an approximation).. There are still lots of missing things..

[serengeor]

Thanks for all the physics and stuff, but I don't really need them for my application. (if I did I probably would just have used a proper physics engine )
The thing is that I can't quite get a proper collision normal in a situation like this one:

The collision normal now shouldn't be perpendicular to neither edge as it intersects with both and in different distances.

[CuteAlien]

This is about 2D? Maybe it helps if you think of the box as 4 lines so you can do line-circle collisions and then take the "best" of those (whatever best means for you). Plus probably 2 more check to find if the circle is completely inside the box or the box completely inside the circle.
Or You can think of it as 4 lines + 4 corners, might be faster checking the corners first.

[fmx]

Hang on a minute, what exactly do you want to use the "contact normal" for?
You can get a general direction vector from box-to-circle (using their centers) and use the normalized value after you determine they collide...

but that will never get you the true Surface "contact normal" on the box because of one simple reason:
when a circle intersects with anything, it always has 2 intersection points!

if you want the exact point of collision when the circle edge touched the box edge, you would need to extrapolate the circle's position backwards (after you determine collision has occured), until only a single point on the circle touches a boxes edge, then the surface "contact normal" would be exactly what you need

Maybe you should use a proper physics engine, something like box2d
http://box2d.org/

[serengeor]

This is about 2D?

Yes this is about 2d, as the topic states

Maybe it helps if you think of the box as 4 lines so you can do line-circle collisions and then take the "best" of those (whatever best means for you)

well I've already tried tons of ideas, but neither of them worked good enough to be used.

Hang on a minute, what exactly do you want to use the "contact normal" for?

Well it's going to be used in some "physics" calculations, but I wouldn't really call them so.

You can get a general direction vector from box-to-circle (using their centers) and use the normalized value after you determine they collide...

That works when the circle hit's the box at the center points of the lines or edges at the same spots, otherwise it returns some pretty weird results.

but that will never get you the true Surface "contact normal" on the box because of one simple reason:
when a circle intersects with anything, it always has 2 intersection points!

As long as I could get a close to real contact normal I'd be happy

if you want the exact point of collision when the circle edge touched the box edge, you would need to extrapolate the circle's position backwards (after you determine collision has occured), until only a single point on the circle touches a boxes edge, then the surface "contact normal" would be exactly what you need

Can't quite wrap my head around this one. Wouldn't one contact point only return a perpendicular normal to one of the four surfaces ? (remember I need proper edge normals).

Maybe you should use a proper physics engine, something like box2d
http://box2d.org/

For what I need it is totally an overkill. And I've already given it a try

I've had some more Ideas now, will try to see if either of them works.

[mongoose7]

If it is in 2d, you are intersecting a circle with a rectangle? If the rectangle is aligned to the x- and y-axes, and the centre of the circle is (a, b), then the point on the rectangle between the two (or none) points of intersection has y=b. If the leading edge of the "box" has x = m, then the distance from the centre of the circle to the edge of the box is (m - a). If the radius of the circle is r, the two points of intersection are

cpp Code: Select all

(m, b + sqrt(r^2 - (m - a)^2)) and (m, b - sqrt(r^2 - (m - a)^2))

and the normal is (-1, 0) or (1, 0) depending whether m > a or m < a. If the box is not axis-aligned, you can either rotate the world until it is, get the information you need and rotate it back, or drop a normal from the circle to the box. The normal to the vector (a, b) is the vector

cpp Code: Select all

(b, -a)/sqrt(a^2 + b^2) or (-b, a)/sqrt(a^2 + b^2)

The same considerations apply to the top/bottom of the box.

If you just want to determine if the circle is touching the box, then the difference between the x coordinate of the centre of the circle and the x-coordinates of the vertices of the box, or the y-coordinate of the centre of the cirle and the y-coordinates of the vertices of the box, is r, the radius of the circle, for some vertex. Of course, if one of these quantities is less then r, the circle intersects the box.

Oops, I wrote the wrong normal.

[REDDemon]

you must specify better what do you mean by "collision normal". for example put a hand-drawn picture with few examples.. If you don't need realistic calculationyou should at least assume 3/4 extreme cases for your collisions. after that all other cases are just interpolations of your cases. In that way you can tune everything at your will. But you must proivde first the extreme cases.

[fmx]

...

if you want the exact point of collision when the circle edge touched the box edge, you would need to extrapolate the circle's position backwards (after you determine collision has occured), until only a single point on the circle touches a boxes edge, then the surface "contact normal" would be exactly what you need

Can't quite wrap my head around this one. Wouldn't one contact point only return a perpendicular normal to one of the four surfaces ? (remember I need proper edge normals).
...

A "proper" edge normal will only exist when the circle touches the box at ONE point.
I dont know what you plan to do with the normal (collision response is a different can of worms) so I'll just elaborate on what I was saying before

I made this quickly in paint


As long as you keep track of previous circle position, you can use interpolation methods to determine actual positions for physical contact purposes.

In this case, we know that in Frame 1 the circle has intersected the box right?
All we have to do is push the circle back in time (t < 1.0) until the collision detection function only returns a single value (this can be done accurately using quadratic math because a circle is a special kind of curve).

Once you have the single contact point, you can use whatever method to determine the exact surface normal (edge-detection, trig, using centre positions, etc)

[serengeor]

I understand what you're saying. I was rather looking for a way to invert circles velocity based on how it hits the box. I had this implemented using boxes and it worked quite well for what I needed, just that I wanted to be a bit more accurate and use a circle for my circular object (2d ball).

[Mel]

Mmmm... How about this.

for all the edges of the box until you find one contact point.
calculate the closest point to the rect that contains them,
if the closest point distance was less than the radius of the circle,
check if that point is between the vertices of the edge,
if so, there is your contact point, the rect gives you the normal, and the circleCenter-Point. gives you the incident vector.

I think (can't be sure because i haven't tested it) that it is safe to asume that this point can be perfectly used as the contact point, and so, you can perform further calculations from this point on, while it is not physically accurate, i think it could prove to be a good approximation with less calculation costs.

[fmx]

I understand what you're saying. I was rather looking for a way to invert circles velocity based on how it hits the box. I had this implemented using boxes and it worked quite well for what I needed, just that I wanted to be a bit more accurate and use a circle for my circular object (2d ball).

So you still haven't got it working?
Once you have the contact point (using any of the methods posted here by people) then you should be good to go - reflect the object's velocity using the contact normal and set the position to the last known contact point.

Accuracy always comes at the price of more complex maths:
dont be afraid to alter your box-box collision response method because IMO your current method is unlikely to work "out of the box" with more complex box-circle collision tests

[serengeor]

So you still haven't got it working?

No, not yet. I haven't worked on the project the past few days. It needs some refactoring, so I will do that first I think.

Once you have the contact point (using any of the methods posted here by people) then you should be good to go - reflect the object's velocity using the contact normal and set the position to the last known contact point.
Accuracy always comes at the price of more complex maths:

Reflecting ain't that much of a trouble when it comes to circle colliding only with one of the edges since the boxes will all be axis aligned. But when it comes to corners it's a bit more complicated.

dont be afraid to alter your box-box collision response method because IMO your current method is unlikely to work "out of the box" with more complex box-circle collision tests

I'm not afraid. More complex collision tests are unlikely to be used.

I'm sure you've given me enough information to do what I want. I'll post the results when I'll get the time to do this.
Thank you all for your input