• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# Collision HANDLING (not detection)

## Recommended Posts

I'm adding collision detection to my engine, just sphere-to-triangle right now. It works perfectly fine. Collision handling mostly works, but only for one triangle or one set of coplanar triangles. When you get others in the scene, it gets messed up... ESPECIALLY if the angle betweem them is less than 180 degrees. In other words, going over a hill is mostly fine, but walking along the ground up to a vertical wall and colliding with the wall is totally messed up. The way my algorithm works is I calculate the point I'm trying to move the sphere to, and if a collision takes place, I map that point onto the plane and move the sphere there. Well, I don't move it there immediately... I first take that new point and see if it collides with anything else, repeating the above steps until there are no collisions. A recent change I added to the code was to start all over when a collision takes place, in case the new point collides with something the old point did not. Illustration: The large red point at the top-left is the Origin of the entity. The red line extending from it is its path; the smaller red dot at the lower right is the Destination. Because the path collides with the bottom surface (shown in black, the arrow is its normal), the Destination is mapped to the plane, yielding the green dot, or Destination2. But the new path (from the Origin to the Destination2) collides with another face (the pink one) that the previous red path did not. The green Destination2 is mapped to that plane, yielding the cyan Destination3, the final point. This is where the entity should be placed. Of course this example assumes its radius is zero, for simplicity. My algorithm attempts this but doesn't seem to work effectively. One thing I just added was something that, upon handling a collision, restarts the collision loop all over, in case, in the above example, the pink face was evaluated before the black one - it clearly has to be re-evaluated now. Here is my code:

void town :: MoveEntity ( entity* Entity, vectorf PosChange, vectorf RotChange )
{
vectorf		Direction;
vectorf		Position;

if( PosChange != vectorf(0,0,0) )
{
Position = Entity->Position + PosChange;
Direction = PosChange / float(PosChange);

RestartCollisionLoop:
for( UINT N = 0; N < m_NumFaces; N ++ )
{
if( CollideEntityWithFace( Entity, &m_Face[N], &Position, &Direction ) )
goto RestartCollisionLoop;
}

Entity->Position = Position;
}

Entity->Rotation += RotChange;
}

bool town :: CollideEntityWithFace ( entity* Entity, face* Face, vectorf* Position, vectorf* Direction )
{
planef		Plane;
float		Distance;
float		Cosine;
vectorf		Normal;
vectorf		Vertex	[3];
planef		Side	[3];
vectorf		Intersection;

if( Face->NumFaces )
{
for( UINT N = 0; N < Face->NumFaces; N ++ )
if( CollideEntityWithFace( Entity, &Face->Face[N], Position, Direction ) )
return true;
}
else
{
for( UINT I = 0; I < Face->NumIndices - 2; I += 3 )
{
Vertex[0] = ((vertex3d*)Face->Vertex)[Face->Index[I  ]].Position;
Vertex[1] = ((vertex3d*)Face->Vertex)[Face->Index[I+2]].Position;
Vertex[2] = ((vertex3d*)Face->Vertex)[Face->Index[I+1]].Position;

Plane = planef( Vertex[0], Vertex[1], Vertex[2] );
Normal = vectorf(Plane.A, Plane.B, Plane.C);
Cosine = Normal dot *Direction;

/*	Make sure the angle is less than zero. If it is, we are moving against the plane's normal. If it's
greater than or equal to zero, then we are either behind the plane or we are moving away from it.
Either way, there is no need to perform collision detection on it. */
if( Cosine < 0 )
{
Distance = (Plane.Distance( Entity->Position ) / Cosine) - Entity->Radius;

//	Ensure that we are in front of the plane.
if( Distance < 0 )
{
Intersection = Entity->Position - (*Direction * Distance);
Distance = Plane.Distance( *Position ) - Entity->Radius;

//	Ensure we are colliding with the plane.
if( Distance < 0 )
{
Side[0] = planef( Vertex[0], Vertex[2], Vertex[2] + Normal );
Side[1] = planef( Vertex[2], Vertex[1], Vertex[1] + Normal );
Side[2] = planef( Vertex[1], Vertex[0], Vertex[0] + Normal );

//	Finally, make sure we are within the triangle.
if( Side[0].Distance( Intersection ) + Entity->Radius >= 0 &&
Side[1].Distance( Intersection ) + Entity->Radius >= 0 &&
Side[2].Distance( Intersection ) + Entity->Radius >= 0 )
{
/*	Map the destination point onto the plane, and redirect
the Direction vector to point to the new point. */
*Position = (*Position) - (Normal * Distance);
*Direction = *Position - Entity->Position;
Direction->Normalize( );
return true;
}
}
}
}
}
}

return false;
}

By the way, it often enters an infinitely recursive loop now that I added the boolean return values and RestartCollisionLoop, so it obviously is colliding with a face it already collided with, but I don't know why. ~CGameProgrammer( ); [edited by - CGameProgrammer on October 21, 2002 12:51:50 AM] [edited by - CGameProgrammer on October 22, 2002 1:08:25 AM]

##### Share on other sites
Mmm, why wouldn''t you set up your collision handling to perform like this:

The trajectory of the large red ball puts its predicted destination as the small red dot. However, the black plane causes a reflection in the plane (rather than a mapping into the plane). This then causes a predicted collision with the pink plane, which again causes a reflection in the plane, giving the final position.

If there''s a reason why this isn''t the right way for you to go about it, could you indicate why please.

Thanks,

Timkin

##### Share on other sites
The way you have it, the object bounces off the walls. That is something different. If a player walks into a wall, he doesn''t bounce off. With that system, he''d bounce off one frame, the move back towards the wall the next, then bounce, etc...

~CGameProgrammer( );

##### Share on other sites
I usually handle collisions by updating the position and velocity as soon as an impact occurs. (so I would have a different position when colliding with the second object)

This might not be great for your situation, as it''s highly imperfect, and you can encounter situations where you collide with 2+ objects and one "squishes" you through one of the previous collision peers.

The benefit of this system is that you only need to handle any pair of objects once per frame, and it''s more-or-less correct.

##### Share on other sites
Yeah, well my world has complicated geometry, and even if it didn''t I''d still not settle for an imperfect solution.

However one thing I did consider is finding the closest triangle the original path intersections and moving the entity at that intersection, then repeating the collision routine from its new position to the projected path (again, mapped onto the plane of the triangle, the green dot in my example). This produces the same results in my example, but I thought of an example in which the above method (mine) would fail but this one would succeed.

But right now I''ve gone even further to basics and done point-to-triangle collision on just one triangle only, whichever is the closest. I just got it to work on seemingly all situations that it''s capable of working with.

What threw me off for a while was when I make sure the point/sphere is in front of or at the plane of the triangle. Due to floating-point errors, I needed to allow a leniency of some value (like 0.001).

~CGameProgrammer( );

##### Share on other sites
quote:
Original post by CGameProgrammer
The way you have it, the object bounces off the walls. That is something different. If a player walks into a wall, he doesn't bounce off.

Ah, okay... so you'd like completely inelastic collisions (no bounce) and you want the player to be able to slide along the wall until they hit another wall... in which case you're already using a constraint-based approach, which is about the best you can do. You might find some tweaks based on your geometry, but there isn't really a better way to handle it that I can think of right now.

So the problem then is that your algorithm isn't working efficiently... is that correct?

The first comment I have is that you should never use the 'goto' statement. It's a nightmare to debug in complex logic situations... and can create a lot of unintended behaviours.

Also, you might want to limit collision checks to only those faces of polys that are in the vicinity of the character. A quad tree can help with locating which faces to check for collisions with.

As to the problem with your code, my first thought is that the infinite recursion may be happening when the object is colliding with two faces simultaneously, in which case each calls the collision detection for the other one. You can avoid this by noting which faces you've already checked collision with... a list rather than a loop over faces would suffice.

Cheers,

Timkin

[edited by - Timkin on October 23, 2002 11:36:37 PM]

##### Share on other sites
I got it working. Well the algorithm above was a bad one, there are cases in which it would detect a collision when there is none. But now I find the closest polygon the movement ray intersects, move the point to that intersection, map the destination point onto the plane (like above) and repeat the collision checking from the point's new position on the plane to the new final position (also on the plane). So since it's parallel to that plane, it won't collide with it and I don't have to remember that I already collided with it. Technically it still checks to see if there's a collision with that face but I'm not worried about that now.

But even that way, it didn't work for a while. But I figured out why - due to floating point errors, when it maps the destination onto the plane, it sometimes doesn't put it far enough. In my case it was 0.000002 units below the plane. Thus the algorithm saw the movement would collide with the plane and redid the collision check ad infinitum. I now add 0.001 when mapping the point and it works.

As for geometry sorting, I have many plans for that but it is not important as a first step - right now I am rendering a small portion of my level and just doing collision with every single polygon. Sorting will come when this stuff is working first.

However , there is a new problem. I know exactly what is wrong but don't know the best solution. I need to detect if something is within the bounds of a rounded triangle.

~CGameProgrammer( );

[edited by - CGameProgrammer on October 24, 2002 2:01:51 AM]

##### Share on other sites
Great to hear it''s working CGP!

• ### Forum Statistics

• Total Topics
627711
• Total Posts
2978763

• 21
• 14
• 12
• 41