Graphics Reference
In-Depth Information
Listing 7.2: Intersecting a ray with a triangle.
// input: ray
P
+
t
d
;
triangle
ABC
// precomputation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n
=
(
B
−
A
)
×
(
C
−
A
)
AB
⊥
=
n
×
(
B
−
A
)
AB
⊥
/=
(
C
−
A
)
·
AB
⊥
AC
⊥
=
n
×
(
A
−
C
)
AC
⊥
/=
(
B
−
A
)
·
AC
⊥
// ray-triangle intersection
u
=
n
·
d
if (
|
u
|
<
) return UNSTABLE
t
=
(
A
−
P
)
·
n
u
if
t
<
0
return RAY_MISSES_PLANE
Q
=
P
+
t
d
γ
AC
⊥
=
(
Q
−
C
)
·
(
Q
−
B
)
·
AB
⊥
β
=
α
−
(
β
+
γ
)
if
any of
α
,
β
,
γ
is negative or greater than one
return (OUTSIDE_TRIANGLE,
=
1
α
,
β
,
γ
)
else
return (INSIDE_TRIANGLE,
α
,
β
,
γ
)
Section 15.4.3 applies this idea in developing an alternative ray-triangle intersec-
tion procedure—one which, at its core, is very similar to the one we've given, but
which, when you read it, may seem completely opaque. Why have more than one
method? Ray-triangle intersection testing is at the heart of a great deal of graphics
code. It's one of those places where the slightest gain in efficiency has an impact
everywhere. We wanted to show you two different approaches in hopes that you
might find another, even faster approach, and to show you some of the optimiza-
tion tricks that might help you improve your own inner-loop code.
(
A
,
B
)
Figure 7.17: The graph of a lin-
ear function on
R
2
defined by
F
(
x
,
y
,
z
)=
Ax
+
By
+
Cisa
plane shown in red, which is
tilted relative to the large pale
gray z
From algebra we know that the function
F
(
x
,
y
)=
Ax
+
By
+
C
(where
A
and
B
are
not both zero) has a graph that's a plane intersecting the
xy
-plane in a line
.We've
0
plane as long as either
A or B is nonzero; it intersects the
z
=
0
plane in a line
(a por-
tion of which is shown as a heavy
black segment). The ray from the
origin to the point
(
A
,
B
)
is per-
pendicular to
.
=
seen that the ray from the origin to
(
A
,
B
)
is perpendicular to
. The zero set of
F
is exactly the line
the function
F
is positive; on the other it's negative (see Figure 7.17). Thus, an inequality like
F
(
x
,
y
)=
Ax
+
By
+
C
, that is, if
P
∈
, then
F
(
P
)=
0. On one side of
≥
0 defines a
half-plane bounded by
, provided that
A
and
B
are not both zero. But which side of the line
does it describe? The answer
in the direction of the normal vector
AB
T
, you are
moving to the side where
F
is this: If you move from
>
0.
A triangle in the plane can also be characterized as the intersection of three
half-planes. If the vertices are
P
,
Q
, and
R
, one can consider the half-plane
bounded by the line
PQ
and containing
R
, the one bounded by
QR
and containing
P
, and the one defined by
PR
and containing
Q
. Such a description can be used
for testing whether a point is contained in a triangle. If the three inequalities are
F
1
≥
0,
F
2
≥
0, and
F
3
≥
0, one can test a point
X
for inclusion in the triangle as
follows:
