Triangle Intersection Tests
By Eric Haines and Tomas Moller, August 01, 2000
Source Code Accompanies This Article. Download It Now.
Our authors provide an alternative to the classic methods of testing whether a point is inside a triangle. This new technique is based on barycentric coordinates.
Aug00: Triangle Intersection Tests
bool PointInTriangle (i, p<sub>0</sub>, p<sub>1</sub>, p<sub>2</sub>)
returns ({TRUE, FALSE},u,v);
1: e<sub>0</sub>=i-p<sub>0</sub>
2: e<sub>1</sub>=p<sub>1</sub>-p<sub>0</sub>
3: e<sub>2</sub>=p<sub>2</sub>-p<sub>0</sub>
4: if (e1x=0)
5: if (e<sub>2x</sub>=0) return (FALSE,0,0);
6: u=e<sub>0x</sub>/e<sub>2x</sub>
7: if (u<0 or u>1) return FALSE,0,0);
8: if (e<sub>1y</sub>=0) return FALSE,0,0)
9: v=( e<sub>0y</sub>-e2<sub>y</sub>u)/e<sub>1y</sub>
10: if (v<0) return (FALSE,0,0);
11: else
12: d = e<sub>2y</sub>e<sub>1x</sub>-e<sub>2x</sub>e<sub>1y</sub>
13: if (d=0) return (FALSE,0,0);
14: u = (e<sub>0y</sub>e<sub>1x</sub>-e<sub>0x</sub>e<sub>1y</sub>)/d
15: if (u<0 or u>1) return (FALSE,0,0);
16: v = (e<sub>0x</sub>-e<sub>2x</sub>u) / e<sub>1x</sub>
17: if (v<0) return (FALSE,0,0);
18: if (u+v>1) return (FALSE,0,0);
19: return (TRUE,u,v);
Example 1: Pseudocode for testing some point i for inclusion in a triangle.
