Triangle Intersection. In real-time graphics, triangle geometry(triangle mesh) is usualy stored, and eachtriangle is defined by three vertices.There exists many different ray/triangleintersection methods, main steps are:- First compute the intersection point between theray and the triangle's plane- Thereafter, project the intersection point ontothe triangle's plane- Decide whether or not the point is inside thetriangle
Triangle Intersection • In real-time graphics, triangle geometry (triangle mesh) is usualy stored, and each triangle is defined by three vertices. • There exists many different ray/triangle intersection methods, main steps are: – First compute the intersection point between the ray and the triangle’s plane – Thereafter, project the intersection point onto the triangle’s plane – Decide whether or not the point is inside the triangle
Triangle Intersection. Barycentric coordinates:- A point P, on a triangle P.P,P2, is given by theexplicit formula:P=αP+βP+Pwhere (α, β, ) are the barycentric coordinates,which must satisfy O≤α,β,y≤1,α+β+y= 1oPo- Note that the barycentric coordinatescould be used for texture mappingPnormal interpolation,color interpolation, etc.P,D
Triangle Intersection • Barycentric coordinates: – A point P, on a triangle P0P1P2 , is given by the explicit formula: where are the barycentric coordinates, which must satisfy – Note that the barycentric coordinates could be used for texture mapping, normal interpolation, color interpolation, etc. P P P P 0 1 2 ( , , ) 0 , , 1, 1 P0 P P1 P2
Triangle Intersection Since α+β+=l, we can write α=l-β-, Wehave:P=(1-β-)P +βP+P,Set ray equation equal to barycentric equationR+tR, =(1-β-)P+βP+PRearrange the terms, gives:t(Ra P-P P-P)Iβ=P-RYThe means the barycentric coordinate and distance tcan be found by solving this linear system ofequations
Triangle Intersection • Since =1, we can write 1 We have: • Set ray equation equal to barycentric equation: • Rearrange the terms, gives: • The means the barycentric coordinate and distance t can be found by solving this linear system of equations 0 1 2 P P P P (1 ) R tR P P P o d + (1 ) 0 1 2 0 1 0 2 0 0 ( ) d t R P P P P P R
Triangle Intersection Denoting E =P-P, E, =P-P,S=P-Rthe solution to the equation above is obtained byCramer's rule:det(S,E,, E,)1βdet(d, S, E,)det(d, E, E,)det(d,Er,S)yThen check 0≤β,≤1,β+≤1to determine whether or not the intersect point isinside the triangle
Triangle Intersection • Denoting the solution to the equation above is obtained by Cramer’s rule: • Then check to determine whether or not the intersect point is inside the triangle 1 0 1 2 0 2 0 0 E P P P P S P R , E ,1 2 2 1 2 1 det( , , ) 1 det( , , ) det( , , ) det( , , ) t S E E dSE d E E d E S 0 , 1, 1
Polygon Intersection: Even though triangles are the most commonrendering primitive, a routine to compute theintersection between a ray and a polygon isuseful.: A polygon of n vertices is defined by an orderedvertex list (Vo,Vi...,Vn-il, where vertex V, formsan edge with for 0 <= i< n-l, and the polygon isclosed by the edge from Vn-1 to Vo. The plane ofthe polygon is denoted byπp: n,'x+d,=0
Polygon Intersection • Even though triangles are the most common rendering primitive, a routine to compute the intersection between a ray and a polygon is useful. • A polygon of n vertices is defined by an ordered vertex list {v0 ,v1 ,.,vn-1 }, where vertex vi forms an edge with for 0 <= i < n-1, and the polygon is closed by the edge from vn-1 to v0 . The plane of the polygon is denoted by : 0 p p p n x d