Graphics Reference
In-Depth Information
first test. One way of effectively accomplishing this is to determine the interior diag-
onal during preprocessing and outputting either of its end vertices as the first vertex,
thus making the diagonal
CA
the interior diagonal. Self-intersecting quadrilaterals,
however, cannot be directly tested with this method.
5.3.6
Intersecting Ray or Segment Against Triangle
Compared to the method presented in the previous section, a slightly different
approach to intersecting a ray or line segment against a triangle is described in
[Möller97a]. Recall that points (of the plane) of the triangle
ABC
are given by
T
(
u
,
v
,
w
)
=
uA
+
vB
+
wC
, where (
u
,
v
,
w
) are the barycentric coordinates of
the point such that
u
+
v
+
w
=
1.
T
is inside
ABC
if and only if its barycen-
tric coordinates satisfy 0
≤
u
,
v
,
w
≤
1. Alternatively, this may also be written as
=
+
−
+
−
=
−
−
≥
T
(
v
,
w
)
A
v
(
B
A
)
w
(
C
A
), with
u
1
v
w
.
T
is now inside
ABC
if
v
0,
≥
+
≤
w
1.
Let a directed line segment between the two points
P
and
Q
be defined paramet-
rically as
R
(
t
)
0, and
v
w
1. By setting
T
(
v
,
w
) equal to
R
(
t
) it is possible
to solve for
t
,
v
, and
w
to later verify if these are within the bounds required for an
intersection:
=
P
+
t
(
Q
−
P
), 0
≤
t
≤
T
(
v
,
w
)
=
R
(
t
)
⇔
(original expression)
A
+
v
(
B
−
A
)
+
w
(
C
−
A
)
=
P
+
t
(
Q
−
P
)
⇔
(substituting parameterized expressions)
(
P
−
Q
)
t
+
(
B
−
A
)
v
+
(
C
−
A
)
w
=
P
−
A
(rearranging terms)
This is a 3
×
3 system of linear equations, and thus it can be written in matrix
notation as
⎡
⎤
t
v
w
(
)
⎣
⎦
=
P
−
Q
)(
B
−
A
)(
C
−
A
[
(
P
−
A
)
] ,
where the vectors are given as column vectors. Now
t
,
v
, and
w
can be solved for
using Cramer's rule:
det
(
)
det
(
)
t
=
P
−
A
)(
B
−
A
)(
C
−
A
P
−
Q
)(
B
−
A
)(
C
−
A
det
(
)
det
(
)
v
=
P
−
Q
)(
P
−
A
)(
C
−
A
P
−
Q
)(
B
−
A
)(
C
−
A
det
(
)
det
(
)
w
=
P
−
Q
)(
B
−
A
)(
P
−
A
P
−
Q
)(
B
−
A
)(
C
−
A
