## Edge Collision Response Problem

Member
Posts: 269
Joined: 2005.04
Post: #1
So, I'm stuck.

I've been working on this proof-of-concept first-person movement and collision code off and on. I've mostly been following articles at GameDev.net like this one and this one. However, I've run into an issue with how to respond to edge collisions.

Here's an image I'll be referring to.

In figure 1 we've got a sphere heading towards a corner at a 45 degree angle. In figure 2 the sphere has embedded itself into the corner and we've got a collision. The red dots are the collision points with the sphere and the wall. Now, to respond to the collision I don't want to just back the player up, I want the player to slide along the wall. The easiest way to do this is just to push the player along the polygon's normal, and this works fine when the sphere collides with the inside of a polygon.

So the response that I'd like is for the sphere to be pushed along Wall 2's normal. And here's where the problem is. Wall 1 sits before Wall 2 in whatever data structure you wish to use. Thus, it handles the collision before Wall 2, and just pushing along the polygon normal results in Figure 4, which is the wrong response. You can't sort the walls by the sphere's closeness to the planes, as the sphere is actually closer to Wall 1's plane than Wall 2's. You can't sort by which collision happens first, because they happen at the same time at the same location (since it's an edge shared by both polygons).

The first GameDev.net article mentions creating a sliding plane that the sphere/ellipsoid would travel along, and that would work fine for sliding along a polygon. But it has issues with edges where you'd just end up sliding *away* from the edge instead of along it. (Look at the Sliding section and the left part of Figure 13; that's the wrong response)

Ideas? Did I adequately explain the problem? I can post a couple dozen more pictures if you want.
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
Doesn't pushing back along the vector between the two red dots in figure 2 work?
Moderator
Posts: 3,591
Joined: 2003.06
Post: #3
Yeah, seems to me you should just push back along the two red dot vector, even though it sounds like that's not what you *want* to do, according to your post. If not along the red dot vector in figure 2 then maybe you can figure out which way to correct back without taking the wall normals into consideration. I mean, looking at the diagram there appears to be a relationship between the location of the two red dots (in fig 2) and the center of the sphere and its direction vector, which may be useful (although the correct way of looking at it doesn't pop out at me). So maybe you can just ignore the walls and go with the information you have only from the circle's point of view and direction of movement.
Member
Posts: 269
Joined: 2005.04
Post: #4
OneSadCookie Wrote:Doesn't pushing back along the vector between the two red dots in figure 2 work?

It'll work fine for getting the player out of the wall, but it won't cause the player to slide along the wall. He'll be stuck at that position until he changes direction.
Member
Posts: 269
Joined: 2005.04
Post: #5
One thing I've noticed that if you create a ray/normal/whatever from the sphere center to the sphere intersection point and compare that to the direction the sphere is traveling in it tells you the general direction you want to slide.

Like so (My apologies if this pic makes no sense)

However, I haven't figured out how to convert that to actual math/code that I can use.
Member
Posts: 320
Joined: 2003.06
Post: #6
I think what you want is to decide which wall it hit first (which has been penetrated deeper), and respond based on the normal of that wall, ignoring the other one.

Edit: which has been penetrated deeper is probably not right... you know, in figure 2 of the first example, you would translate wall1's penetration depth along wall2's normal

Chopper, iSight Screensavers, DuckDuckDuck: http://majicjungle.com
Moderator
Posts: 455
Joined: 2002.09
Post: #7
I haven't really thought this through [to the point where I'd be ready to implement it] but if you think of it as forces, at the point of collision wall #2 is pushing more directly against the center of gravity.

The procedure might be:
- Push the sphere away from the collision along the vector of movement until it no longer intersects.
- Find the point(s) of contact. Hitting a corner, two walls will have a point of contact. (Happens to be the same point in this example, but it doesn't have to be.)
- Calculate the force that each wall exerts at the point of contact. The wall is pushing towards the sphere's center of gravity, but the wall only pushes along it's normal. So you take the component of the wall's normal that is pushing directly towards the center of gravity.

Ps = sphere center
Pc = point of collision
Vw = wall normal
F = scalar force of the sphere moving along it's movement vector

F * [cosine of the angle between (Pc - Ps) and Vw] = the force a wall pushes back against the sphere. If my fading memory serves, that cosine is simply the dot product of the two vectors.
F * (Pc-Ps) dot Vw

So both walls push in the directions they face, but one of the walls pushes more, unless the impact is exactly on the corner, in which case both walls push equally.

If you aren't already working with forces, you could simply check all the cosines to help you decide which wall to move along.

There are potentially some pitfalls here. Moving the sphere back until it intersects at precisely one or more points is problematic, for example. More typically you may have to handle small patches of intersection, or "close enough" points where you are about to intersect. That's another topic.

Hopefully I've given you some ideas, and haven't totally butchered my high school physics.

Measure twice, cut once, curse three or four times.
Sage
Posts: 1,487
Joined: 2002.09
Post: #8
Doesn't have to be so complicated if you don't care about friction.

Treat collisions with each line segment separately. Find the collision depth and normal, push the circle back along the normal by the penetration distance. Rinse and repeat for each segment. (possibly several times if you have multiple contacts)

You can look at the collision code in Chipmunk Physics to see how to get the collision depth and normal. It's pretty simple for segment/circle collisions.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Moderator
Posts: 455
Joined: 2002.09
Post: #9
Skorche Wrote:Doesn't have to be so complicated if you don't care about friction.

Treat collisions with each line segment separately. Find the collision depth and normal, push the circle back along the normal by the penetration distance. Rinse and repeat for each segment. (possibly several times if you have multiple contacts)

Not sure whether you mean, calculate all the colliding-wall vectors at once and apply them simultaneously; or find the first one and move the sphere, then repeat.

The second approach has the problem that was originally complained about. Also, depending on the geometry it could move the sphere into a narrow location that is in collision with several other walls where there is no escape.

The first approach gives the behavior that was requested, but I believe in most cases it's exactly the same as moving the sphere backwards along the vector of the original movement. Moving it backwards along the original movement vector is safer though - imagine the sphere colliding with a thin barrier so that it hits both the original wall and the wall on the far side of the barrier. The further wall would push the sphere out past the barrier, and the sphere has just moved right through the barrier.

Actually just about all of the suggestions so far are perfectly valid for certain circumstances. For example if we were dealing with simple geometry then I certainly wouldn't implement my own suggestion - as Skorche said it's overkill. But the original post mentioned FPS - if the camera is centered in or near the sphere then we may have to be careful, particularly if the level geometry can be complicated, with narrow spaces and acute angles...

Measure twice, cut once, curse three or four times.
Sage
Posts: 1,487
Joined: 2002.09
Post: #10
It doesn't have the original issue because you don't exclusively use the wall normals. If it hits an endpoint, treat it as a sphere to sphere collision.

You are correct that it would have issues with fast objects passing through each other (tunneling) and possibly getting stuck. If doing static triangles vs moving elipsoids/spheres, then you can still do a swept test easily enough as it just boils down to a quadratic formula in the worst case. Though again, this may be overkill.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.