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].Position;
			Vertex[1] = ((vertex3d*)Face->Vertex)[Face->Index[I+2]].Position;
			Vertex[2] = ((vertex3d*)Face->Vertex)[Face->Index[I+1]].Position;
<br>
			Plane = planef( Vertex[0], Vertex[1], Vertex[2] );
			Normal = vectorf(Plane.A, Plane.B, Plane.C);
			Cosine = Normal dot *Direction;
<br>
		/*	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 &#111;n 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 );
<br>
					//	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 &#111;nto the plane, and redirect
							the Direction vector to point to the new point. */
	<br>						*Position = (*Position) - (Normal * Distance);
						*Direction = *Position - Entity->Position;
							Direction->Normalize( );
							return true;
						}
					}
				}
			}
		}
	}
<br>
	return false;
}
    </pre>  
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.    

<font face="Courier">~CGameProgrammer( );</font>

<SPAN CLASS=editedby>[edited by - CGameProgrammer &#111;n October 21, 2002 12:51:50 AM]</SPAN>

<SPAN CLASS=editedby>[edited by - CGameProgrammer &#111;n October 22, 2002 1:08:25 AM]</SPAN>    

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( );

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( );

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]