   Indoor floor collision
  I have a basic third person shooter engine running now, however at the moment he is only running on a plane. I need to add an actual level for him to fight on, with ramps and stairs and hallways, etc.Can anyone help me with an accurate-but-fast way to keep the player character on the ground?thanks,killigan 
  ain''t gonna be easy I''ll give it a go. I hope you like vector maths and others.If you are not bothered about having your character bounce, but just slide on floors and walls....first, you need a representation of the geometry. In my example, I''ll use a large triangle list, and a large vertex list. Triangles reference vertices, vertices have a position, and a normal. then, you need a collision shape for your character. I''ll use a sphere, as they are the simplest things. the algorithm is very simple. You just need a function that detects an intersection between a sphere and a triangle, and a function that pushes the sphere away from the triangle.  bool CTriangle::Collide(CSphere& Sphere) const{    //-----------------------------------------------    // first, find the point on the triangle the closest    // to the sphere centre.    //-----------------------------------------------    CVertex Pcoll;    if (!FindIntersectionPoint(Sphere, Pcoll))   return false;    //-----------------------------------------------    // then move the sphere away from the point.    //-----------------------------------------------    Sphere.PushAwayFrom(Pcoll);    return true;}now, the tricky part, to find the intersection point on the triangle. First, Calculate the closest position on the triangle to the sphere centre. Then, check if that point is in the sphere (simple radius check). If not, since it was the closest point, then no other point on the triangle can possibly collide, so the sphere does not collide with the triangle. So, you have the closest point, now you need to calculate it''s ''normal'', which will tell in what way we ned to push the sphere. To calculate the normal, you can use bilinear interpolation, or barycentric coordinates to interpolate the vertex normal among the three vertex normals of the triangle. I''ll explain why you need the normal at the collision point later.then you have a full collision vertex, with position and normal. bool CTriangle::FindIntersectionPoint(const CSphere& Sphere, CVertex& Pcoll) const{    //----------------------------------------------------    // find closest point on the triangle the closest// to the sphere centre    //----------------------------------------------------    Pcoll.Position = FindClosestPoint(Sphere.Position);    //----------------------------------------------------    // if closest point does not intersect sphere, then    // return no collision    //----------------------------------------------------    if (!Sphere.ContainsPoint(Pcoll.Position))   return false;    //----------------------------------------------------    // finally, given the vertex position, calculate it''s normal    // by interpolating with the three triangle''s vertices    //----------------------------------------------------    CalculateVertexNormal(Pcoll);    return true;}using the vertex normal smooth out rough edges and sharp pointy corners, where overwise, you''d get the character bumping on corners and sharp edges. It also makes the surface of the whole collision world nicely smooth and consistent. now you have the colliding vertex, you need to push the sphere away. Note that, you do not need to normalise the vetex normal. you do that by tracing a ray from the colliding vertex, and along the opposite of the normal, and finding the intersection point with the sphere. You are guaranteed to find a point, since the ray origin is inside the sphere. once you get the point on the sphere, it''s simply a matter of making the point on sphere and point on triangle meet, by pushing the sphere along the vertex normal. //-----------------------------------------------// move the sphere away from a collision vertex//-----------------------------------------------void CSphere::PushAwayFrom(const CVertex& Pcoll){    float t; // intersection parameter   //-----------------------------------------------    // if failed to find an intersection, fall back// to simple solution (that should NEVER have to be done).    //-----------------------------------------------    if (!RayIntersect(Pcoll.Position, -Pcoll.Normal, t))    {   //-------------------------------------------------   // calcualte the separation vector   //-------------------------------------------------   PushAwayFrom(Pcoll.Position);   return;    }   //-------------------------------------------------    // move the sphere away from point    //-------------------------------------------------    m_Centre += Pcoll.Normal * t;}to speed up the algorithm, and avoid testing all the triangles in the world, partition your triangles with an octree, quad tree, Axis aligned box tree, sphere tree.... and that''s a simple solution. You can try swept volumes, bsp trees with dynamic plane shifting, .... ;  oliii, you''re too friggin nice and generous sometimes you know that right? ;  Thank you very much for that informative reply, oliii! That should help me alot!Thanks again!killigan ;  You might want to look at a prebuilt system; I like Quake 3 BSPs. They provide a lot of the structure for a collision tree, and allow you to do collisions quite easily. ;  yeah, ODE, Tokamak can be a solution if you are lazy ;  I''ve got a demo of that stuff if you are interested, btw. ;  A demo would be very helpful, thank you!cheers,killigan ;  available at simple sphere-triangle collisionor from my index page, right at the bottom.   [edited by - oliii on February 2, 2004 12:50:03 PM];  I did one major update. It''s now importing an OBJ file, and testing collisions with the model. The wavefront test model has 7,000 triangles, and you can move the sphere about, and collide with triangles. There are also 3 other spheres around the place you can push around. Press ''r'' to reset, the mouse to look around, ans ,a,s,d,w,q,z to move. keep mouse button pressed. there is only 4 spheres, as the model is not partitioned in any way. So, it''s 7,000 x 4 collision tests per frame. Still, it runs decent on my config. you''ll see the limitations of the algorithm after a while, but for a simple implementation and demo, it''s quite efficient. 