A collision between a ball and a triangle can occur on the triangle's face, edge, or vertex. These notes describe an algorithm for detecting edge collisions. Separate notes describe face and vertex collisions.

Detecting an edge collision is conceptually simple. The ball collides with the edge when its center is a distance r from the edge. We need to check if there are any points on the ball's path that satisfy this condition and, if so, choose the first such point. As discussed in the general collision notes, we only want to report an edge collision that occurs when the ball is moving toward the front of the incident triangle. That means that the ball may collide with an edge shared by two triangles and the collision is reported for one, both, or neither triangles. (See Figure 1.)

Figure 1

While our task is conceptually simple, the mathematics can get messy and hard to implement. To make this process easier, we begin by describing an edge collision detection algorithm for a special case of edges. We then show how to use this algorithm to solve the edge detection problem for arbitrary edges.

Standardized edge collision detection

Edge collision detection is simplified when the edge is in a standard orientation. An edge ( v₀, v₁) is in standard orientation if v₀ is at the origin and v₁ is on the positive x axis.
Let e= (v₀, v₁) be an edge in standard orientation; i.e. v₀=(0,0,0) and v₁= (x,0,0). Let the starting and ending positions of the ball be p₀ = (x₀, y₀, z₀) and p₁ = (x₁, y₁, z₁).

We can represent L parametrically as p₀ + β (p₁ -p₀). Each point on L corresponds to a unique value of β. In particular, p₀ and p₁ correspond to β=0 and β=1, respectively. Points on L between p₀ and p₀ correspond to values of β between 0 and 1.

We need to consider two cases:

1. L is parallel to the x-azis.
   If L is parallel to the x-axis (i.e. y₀= y₁ and z₀= z₁), then either the ball is rolling along the edge or a collision, should it occur, is a vertex collision. In either case we can report that no edge collision occurs.
2. L is not parallel to the x-azis.
   This is the case we consider next.

For any fixed value of β, the point p =p₀ + β (p₁ -p₀) is a distance r from the x-axis if and only if

0. If the quadratic has no real roots, then no point on L is r units from the x-axis. In this case we simply report that no edge collision occurs; i.e. we return α=1.
   
   
1. If the quadratic has one real root, β=s, then exactly one point on L, namely p =p₀ + s (p₁ -p₀), is a distance r from the x-axis. This also means that no point on L is closer than r from the x-axis. Thus an edge collision can only occur when the ball's center is at p₀ + s (p₁ -p₀). This point is on the ball's path if 0 ≤ s ≤ 1. The point the ball touches on the x-axis is on the edge if 0 ≤ x₀ + s (x₁- x₀) ≤ x. If both of these conditions hold, then we need to check that the ball is moving toward the forward face of of the incident triangle. To do this we check if the dot product of the front-facing normal to the triangle and the vector from p₀ to p₁ is less than or equal to 0. If this test succeed, we return α=β. We also return normal of the triangle.
2. Finally we consider the case where the quadratic has two real root, s₀ and s₁. We'll assume that s₀ < s₁. We claim that the only root of interest is s₀ and the test for collision is the same as for s in the previous case.
   
   Proof of claim: The roots s₀ and s₁ correspond to points S₀ and S₀ that define the region of L that is a distance r or less from the x axis. We consider three cases that depend on the relationship of p₀ to S₀ and S₁.
   1. If p₀ occurs before S₀ (as β increases from negative infinity), then the first point on the ball's path that is r units from the x-axis is S₀. So it suffice to check that point.
   2. If p₀ occurs after S₀ but before S₁ then s₀<0 and our test reports that no collision occurs. This is exactly the right answer since, in the case we are considering, the ball at p₀ is intersecting the x-axis. But we know the ball does not intersect the edge at its initial position. Therefore, if the ball does collide with edge while travelling its path, the collision must occur with an endpoint of the edge. But that is a vertex collision, which is detected by the vertex collision algorithm.
   3. Finally, if p₀ occurs after S₁, then s₀ < s₁<0. Once again our test reports that no collision occurs. And again this is the right answer since no point on the path is within r of the x-axis so no edge collision occurs.

Generalized edge collision detection
To take advantage of standardized edge collision algorithm, we can transform an arbitrary edge and the ball's path so that the edge is in standard orientation. We check for a collision in this standardized frame of reference up to the point of checking the triangle normal. At this point we've found an α representing a point on the ball's path in the standardized frame where a collision occurs. But this α also corresponds to a point on the path in the real world where a collision occurs. As the last step we perform the dot product test in the real world to determine if the collision is on the front face of an incident triangle. Separate notes describe the algorithm for standardizing an edge and for transforming points (the ball's starting and ending position) into the standardized frame. To speed our algorithm, we can precompute the standard orientation of each edge.