Intersection of a Convex Hull with a line segment

A ray, or line segment can be represented parametrically as:
S(t) = A + t(B-A)
Where A and B are the endpoints of the segment, and t is the parameter that ranges from –infinity to +infinity for a ray, or just 0..1 for a segment.

A plane can be represented as n.X = d, where n is the plane’s normal, and d is the offset. (Given the plane’s normal, and a single point on the plane, P, we can calculate: d = -n.P)

A convex object can be represented as the area contained within a set of planes. Thus, to find the intersection between a line segment and a convex object, we just need to clip it against all the planes that form the convex object.

First, substitute the line equation into the plane, and solve for t:
i.e.:
n.(A+t(B-A)) = d
n.A + t*n.(B-A) = d
note: using identity ru.sv = rs(u.v), where u,v are vectors, and r,s are scalars
re-arrange to solve for t, the intersection point along the line:

We can determine if the plane faces the segment or not by evaluating the dot product of the plane’s normal, and the line segment’s direction vector.

From this we can determine which point of an intersecting line segment to influence. If the plane is facing the segment direction, then we can clip against the end point, otherwise we can clip against the start point.

As we are testing the intersection against a convex object we can simply keep clipping against each plane and altering the segment endpoints until we have the minimum remaining line length, or the intersection length becomes empty (there is no intersection).

In pseudo-code the entire operation is:

AB = B – A
tFirst = 0
tLast = 0
for all planes:
 denom = N dot AB
 dist = d – N dot A
 t = dist/denom
 if (denom>0 )
  if (t>tFirst) tFirst = t;
 else
  if (ttLast)
  No Intersection