Graphics Reference
In-Depth Information
6.12 A line intersecting a triangle
Triangles play an important role in modeling CG objects, and the line-triangle intersection
problem is important to the design of renderers. Triangles are planar, and it is easy to compute
whether, and where, a line intersects the plane shared by the triangle. What is not so easy
is proving that the intersection is within the triangle's boundary. Fortunately for us, in 1827,
August Ferdinand Möbius [1790-1868] published
Der barycentrische Calcul
, which formalized
the analysis of centers of gravity and also laid the foundations for vectors. Today the work of
Möbius is called barycentric coordinates.
Barycentric coordinates provide the key to unlocking this problem, and if you have never
used them, refer to the author's topic
Mathematics for Computer Graphics
[Vince, 2006].
We begin by defining triangle P
1
P
2
P
3
with vertices P
1
x
1
y
1
z
1
, P
2
x
2
y
2
z
2
, and
P
3
x
3
y
3
z
3
and their corresponding position vectors
p
1
,
p
2
, and
p
3
. This scenario is shown in
Fig. 6.17.
Y
T
λ
v
P
P
3
P
t
p
3
p
2
p
P
1
p
1
Z
X
Figure 6.17.
We can state that any point P x
P
y
P
z
P
on triangle P
1
P
2
P
3
is given by
p
rs
=
q
p
1
+
r
p
2
+
s
p
3
where
p
is P's position vector. The multipliers q, r, and s are barycentric coordinates and satisfy
the following conditions:
r
+
s
+
1
−
r
−
s
=
1
qrs
≥
0
which makes
q
=
1
−
r
−
s
If the intersecting ray is given by
p
=
t
+
v
