Exercise from Last year Exam

Question 16 ( 8 marks ) :

Write an algorithm (Java-like pseudocode) that will calculate the point of intersection of a ray (semi segment) and a triangle. The method should return the status of the intersection (intersect or not, and, if not, why not ). If it intersects, then the method should also return the coordinates of the intersection. Use comments in your code to explain the algorithm.

The ray is defined by the origin point O and the direction vector V.
The triangle is defined by the 3 vertices P0, P1, P2.

Tip : if vertices A, B, C and D are on the same plane and if D = A + sAB + tAC then D is inside triangle ABC if and only if s>=0, t>=0 and s+t <= 1


flat triangle case

ray // to plane case

// NB epsilon = 0.0.1

M = O + r D

N = P0P1 x P0P2 // Normal to the triangle // NB : if norm( N ) < epsilon, just testing intersection of two rays : flat triangle

POM . N = 0 // M belongs to the plane

(O + r D - P0) . N = 0

r D . N = P0O . N

if D . N <> 0 // ray not // to triangle // NB : test if value < epsilon
then r = ( P0O . N ) / ( D . N )

if r >=0 then plane intersection

be V1 = N x P0P1 // V1 ortho to P0P1 => V1 . P0P1 = 0
V2 = N x P0P2

P0M . V1 = t P0P2 . V1 // not flat triangle => P0P2 <> 0

t = ...

s = ...