The face collision algorithm takes as input a triangle, the starting and ending positions of the ball, and the ball's radius. The algorithm returns an α in [0,1], which is the fraction of the path the ball can travel before colliding with the front face of the triangle. In the event of a collision, the algorithm also returns the foward-facing normal of the triangle.

We begin by describing the standardized face collision algorithm, which handles a special case of triangles. Then we show how to use the special case algorithm to detect collisions for arbitrary triangles.

Standardized Face Collision Algorithm
The special case we consider first is when the triangle is in a standard orientation; triangle ( v₀, v₁, v₂) is in a standard orientation if v₀ is at the origin, v₁ is in the x - positive z half-plane, and v₂ is on the positive x axis. We note that the front face of a standardized triangle is facing up. The figure below illustrates a triangle in standard orientation.

If y₀ < r or y0 = y1 then there cannot be a front face collision. In the first case, the ball, in its initial position, either intersects the x-z plane or is below it. In the second case, the ball moves parallel to the x-z plane. In either case, no matter how the ball moves it cannot collide with the front face of the triangle. Our algorithm returns α=1. The two cases are illustrated below

If neither of the two cases described above hold, we go on to test for a face collision.

1. Find the point q on the line through p₀ and p₁ that is exactly r units above the x-z plane.

   Note that the point q exists. Since y₀ ≠ y1, p0 and p₁ are distinct points and define a line. Further, this line is not parallel to the x-z plane. Thus there is a unique point on this line that is exactly r units above the x-z plane.

   

   To compute q, we first represent the line through p₀ and p₁ parametrically as p₀ + β (p₁ -p₀). Each point on the line corresponds to a unique value of β. In particular, p₀ and p₁ correspond to β=0 and β=1, respectively. Points on the line segment between p₀ and p₀ correspond to values of β in the range [0,1].

   To compute q, we simply need to find the value of β such that the y-component of q = p₀ + β (p₁ -p₀) is r. This occurs at β =(r- y₀)/ (y₁ -y₀).

2. If β is not in [0,1], then q does not lie on the line segment between p₀ and p₁. In this case we can conclude that no collision occurs and return α=1.

3. When q lies on the ball's path, we go on to test if the ball touches the triangle when its center is at q. We compute the projection q' of q onto the x-z plane.

   Assuming q=( x_q, y_q, z_q), the projection is simply q'=( x_q,0, z_q).

   
   
4. Determine if q' is inside the triangle. If not, no face collision occurs and the algorithm returns α=1. Otherwise a face collision does occur when the ball is a β fraction of the way along its path. In this case we return α=β.

   Next we show how to test whether this projected point, q', lies inside the triangle. First we need a definition. An edge e of the triangle lies on a line L that partitions the x-z plane into two half-planes. We'll say that the point q' is in with respect to e if q' lies in in the half-plane defined by L that contains the triangle. This idea is illustrated in the figure below.
   
   Thus the point q' is inside the triangle if and only if it is in with respect to the three edges of the triangle.

   Following are the tests that determine if q' is in with respect to each of the edges.
   1. Edge (v₀, v₁):
      
      1. If this edge lies on the z-axis, then q' is inside with respect to the edge if and only if x_q > 0.
      2. If this edge does not lie on the z-axis, the equation of its line is x = x₁ * z/ z₁. and q' is inside with respect to the edge if and only if x_q > x₁ * z_q / z₁.
   2. Edge (v₁, v₂):
      The equation of this edge's line is x = x₂+ (x₁- x₂) * ( z- z₂)/ (z₁- z₂) and the point q' is in with respect to this edge if and only if x_q < x₂ + (x₁- x₂) *( z_q- z₂)/ (z₁- z₂)

   3. Edge (v₂, v₀):
      

      This edge lies on the x-axis. The q' is inside with respect to the edge if and only if

      z_q > 0 .

To detect a collision, we transform the triangle into its standard orientation. We also transform the ball's starting and ending position into this standard frame. We use the standardized face collision algorithm to determine if a collision occurs and, if so, the corresponding α value. Note that the α value is unchanged by the transformation. We return this α value and, if a collision does occur (i.e. 0 ≤ α <1), the forward facing normal of the triangle in its real world orientation.

Separate notes describe the algorithm for standardizing a triangle and for transforming points (the ball's starting and ending position) into the standard frame. To speed our algorithm, we can precompute the standard orientation of each triangle.