The intersection between a line and a triangle

Problem:
Input: The line L is given as input in the form of two end points. The input for triangle T is given in the form of three points (its three vertices v0, v1 and v2).
Output: We return the type of intersection (see the list below) and the vertices or the edges involved.

proper intersection
no intersection
intersection at a vertex
intersection on an edge
coplanar and no intersection
coplanar and intersection at vertex
intersection through two edges
intersection contains an edge
intersection through one vertex and an edge

Representation:
We use the plucker coordinates to solve this problem. We compute the side-operator of the line  L with the three oriented lines e1(v0 to v1), e2(v1 to v2) and  e3(v2 to v0) supporting the edges of the triangle.

S1 = side-operator(L,e1)
S2 = side-operator(L,e2)
S3 = side-operator(L,e3)

Different possible cases:
1) The triangle and the lines are not coplanar
 proper intersection S1, S2, S3 <0  Or S1, S2, S3 >0
 no intersection S1, S2 and S3 don't all have the same sign
 intersection at a vertex Two out of S1, S2, S3 are equal to zero
 Intersection on an edge One of the three S1,S2,S3 is zero and the other two have same sign (>0 or <0)
2) The triangle and the lines are coplanar, then

S1 = S2 = S3 = 0

Let p be a point not coplanar with the triangle T. Let T1, T2 and T3 denote the triangle (v0,v1,p), (v1,v2,p) and (v2,v0,p). Notice that the line and the triangle Ti are not coplanar.The following cases are solved by intersecting the line L and the triangles Ti , as in case 1

 Coplanar and no intersection Intersection of L and Ti returns "no intersection" for all i = 1,2,3.
 Coplanar and intersection at a vertex Intersection of L and one of the Ti returns "no intersection" and intersection of L and the other two Ti returns "intersection at a vertex"
 Intersection through two edges Intersection of L and two of the Ti returns  "intersection on an edge" and the intersection with the remaining Ti returns "no intersection"
 Intersection contains an edge Intersection of L and two of Ti returns "intersection at a vertex" and the intersection of L and the remaining Ti will result in the line and the triangle being coplanar
 Intersection through one vertex and an edge Intersection of L and two of the Ti will return "intersection at a vertex" and the intersection with the remaining Ti returns "intersection on an edge"

Code:
The code can be found here.

Prepared by Anoop Pant (anoop.pant@mailcity.com)
Contact : hazel.everett@loria.fr, sylvain.lazard@loria.fr,sylvain.petitjea@loria.fr