I plan to write a new guide to sphere-mesh collision handling, since I haven't been able to find anything that doesn't come with a few problems. (The next best thing is Fauerby's guide at http://www.peroxide.dk/papers/collision/collision.pdf ).
Part of the approach I'm taking is to support one-way collisions. That is, to ignore back-facing collisions not just for a performance gain, but for practical application as well. The desired result is for the sphere to be able to find itself embedded inside a triangle and still produce "expected" motion and collisions. But not just one triangle; many triangles, at the same time, in perhaps complicated ways.
By "expected" motion, I mean that it slides only in ways that make sense, it doesn't fall through, and if required to push away from the collision, it pushes away along 1 overall normal that also makes sense. (For example, the user might simply press jump.)
Some intersections might be in front of a tri's face, while some are off to the side, while some triangles register the sphere as closest to one edge, while others find it closest to a vertex shared by earlier triangles, etc etc etc., all at once.
Much words. Such confuse.
I spent entire minutes putting together this example of 3 relatively simple embedded situations. On the left is an embedded situation; on the right is a similar realistic situation that my brain thinks matches the embedded one. The goal is for the sphere in the embedded situation to behave as if it were in the realistic situation. These 3 examples are okay demonstrations of this idea, I believe.
Embedded situations 2.png 12.26KB 1 downloads
Bear in mind these are just 2D; 3D situations must be handled as well.
I believe I have found a process to get a correct set of normals from any situation at all. But mathematical proofs are tough, and I wouldn't know how to begin unit testing this. So instead, I'll describe my solution/algorithm and challenge any readers who might be really keen to dream up an embedded situation that breaks it.
Hopefully someone will find holes in someone else's ideas. You can use as many triangles as you want. If it's not obvious, specify which side is the front of a tri.
Things we know:
* Sphere's centre
* Sphere's radius
* Position of every vertex of every triangle.
* Face intersection == the sphere's centre projects onto the face of a tri that it intersects.
* Edge intersection == the sphere's centre projects onto an edge of a tri that it intersects, but doesn't project onto the face of that tri.
* Vertex intersection == the sphere's centre overlaps a vertex of a tri that it intersects, but doesn't project onto the face of that tri, nor either of that vertex's two edges.
* Intersection point == closest point on any given intersected triangle to the sphere's centre
* Collision normal (per intersection type) == Direction from intersection point to the sphere's centre
Intersections.png 13.85KB 0 downloads
Here's that algorithm:
1. Test every triangle to see if it is intersecting the sphere. If it isn't, discard it. Ignore any back-facing situations (sphere's centre is behind triangle's plane).
2. If a triangle is intersecting the sphere, determine whether it is a face intersection, edge intersection, or vertex intersection.
3. Face intersection? Add its collision normal to "the list" of collision normals discovered so far.
4. Edge intersection? If that edge is not involved in any face intersections, add its collision normal to the list. Else, ignore it.
5. Vertex intersection? If that vertex is not involved in any edge intersections, nor face intersections, add its collision normal to the list. Else, ignore it.
6. To slide the sphere with a new velocity, remove from that velocity any vector component that goes into any collision normal in the list. Then slide.
7. Or to push away from the embedded position, average all the normals' directions and use that as an overall collision normal.
To help the brain think in 3D, recognise that this image is showing 1 face intersection, 2 edge intersections, and 1 vertex intersection. In this example, only the face intersection's normal would be used, not just because it already involves all intersected edges and vertices, but also because the sphere's centre is behind the other 3 triangles' planes.
4 ways.png 157.68KB 0 downloads