I've recently written a collision detection system for detecting collisions between ellipsoids (i.e. players, NPCs) and triangle lists. The detector works flawlessly using a ton of vector operations all baked into a few lines of scalar math, but I'm having trouble with the collision response. For a single triangle, this is easy, all I have to do is work out the closest point ON the triangle to the center of the sphere (I smash the coordinates into ellipsoid-scaled space so at this point it's just a sphere), and push it away from that point until the distance is greater than or equal to the radius.

Working with multiple triangles, I tried several approaches. First, I tried allowing any triangle the player collides with to push you away in turn, all on the same frame. This worked for 90 degree angles, but caused trouble with sharp angles and high-poly collisions since the player could end up on the edge of one of the small polys and be pushed directly into another one. Next, I tried finding the average of all "closest points" and using that as the hit position and moving away from there. While it worked far better than the previous method, the average point would sometimes be inside a sharp external corner, or not far enough out from a sharp internal corner. I have no idea how to calculate how far to push the ellipsoid from this hit position, and the only solution I can think of to stop the player from getting stuck is allowing movement away from the hit normal but not towards it, so they can leave simply by moving away from the point they're stuck in. The trouble with that is that you'll still phase slightly through a sharp spike or steep crevice. Though that might not be too big of a problem, it would make it easier to phase past a mesh and into the void if the penetration is deep enough.

One last problem arises with this method-- if the player is standing on the edge of a cliff or stair step, gravity will slowly pull him off due to the "push away from edge" concept. I suppose I could treat the bottom of the ellipsoid as flat, but I'd have to think of a new collision response for that too. Maybe I could use traces to check for footholds... I guess that's up to me how I want to handle it but any tips would be appreciated.

I wish I could just use binary space partitioning, but I don't want to have to write an editor/compiler for that and I'd prefer to just use 3dsmax to export single texture UV-mapped chunks of level geometry, which can then be arranged to make up a whole level. I guess I could also try forcing convex collision meshes though, but I'd still have the crevice problem between two convex bodies.