The collision detection algorithm takes as input the endpoints of the ball's path, p₀ and p₁, the ball's radius r, and a description of the triangles in the scene. The algorithm returns the fraction, α in [0,1], of the path the ball can travel before it collides with a triangle. If no collision occurs along the path the algorithm returns α=1. When the algorithm detects a collision before the end of the path, it also returns the surface normal at the point of collision.

To simplify the collision detection algorithm, we will ignore collisions with the back faces of triangles. Since we have agreed to use closed surfaces, a collision with the back face of a triangle must be preceeded by a front-face collision!

A ball can collide with a triangle's face, edge, or vertex. There are individual tests for each of these case. Details are described in separate notes; face, edge, and vertex.



The collision detection algorithm simply steps through lists of triangles and tests each for face, edge, and vertex collisions, remembering the time of the earliest collision. (Note: This means shared edges and vertices are tested multiple time. This can be avoided by using appropriate data structures but you are not required to implement this optimization.) It is possible for the ball to collide simultaneously with more than one primitive. In this case the collision detection algorithm returns the average of the surface normals at the collision points.

Important Notes

• It is important when you construct your scene that you define triangles with the correct orientation. To test your design, you can draw front and back faces with different colors!
• If you really want to use a free-standing triangle in your scene, you can use two triangles on the same vertices that face in opposite directions. Then, regardless of the direction the ball is moving, a collision will be detected. But if a collision with an edge or vertex of a free-standing triangle occurs, the detection algorithm described in these notes will return the zero-vector as the surface normal; see the discussion of computation of normal in edge and vertex collisions for further details.
• Beware of numerical inaccuracies; they are the bane of this project.