i
i
i
i
i
i
i
i
16.7. Ray/Box Intersection 745
Figure 16.8. Left: The x-axis is tested for overlap between the box and the line segment.
Right: The a-axis is tested. Note that h
y
|w
z
| + h
z
|w
y
| and |c
y
w
z
−c
z
w
y
| are shown in
this illustration as if w is normalized. When this is not the case, then both the shown
values should be scaled with ||w||. See text for notation.
If this test is true then the line segment and the box do not overlap.
The cross product axis a = w × (1, 0, 0) = (0,w
z
, −w
y
)istestedas
follows. The extent of the box projected onto a is h
y
|w
z
| + h
z
|w
y
|.Next
we need to find the projected length of the line segment, and the projection
of the line segment center. The projection of the line segment direction w
onto a is zero, since w · (w × (1, 0, 0)) = 0. The projection of c onto a is
c · a = c · (0,w
z
, −w
y
)=c
y
w
z
− c
z
w
y
. Thus, the test becomes
|c
y
w
z
− c
z
w
y
| >h
y
|w
z
|+ h
z
|w
y
|. (16.17)
Again, if this test is true, then there is no overlap. The other two cross
product axes are similar.
The routine is summarized below:
RayAABBOverlap(c, w,B)
returns ({OVERLAP, DISJOINT});
1: v
x
= |w
x
|
2: v
y
= |w
y
|
3: v
z
= |w
z
|
4: if(|c
x
| >v
x
+ h
x
) return DISJOINT;
5: if(|c
y
| >v
y
+ h
y
) return DISJOINT;
6: if(|c
z
| >v
z
+ h
z
) return DISJOINT;
7: if(|c
y
w
z
− c
z
w
y
| >h
y
v
z
+ h
z
v
y
) return DISJOINT;
8: if(|c
x
w
z
− c
z
w
x
| >h
x
v
z
+ h
z
v
x
) return DISJOINT;
9: if(|c
x
w
y
− c
y
w
x
| >h
x
v
y
+ h
y
v
x
) return DISJOINT;
10 : return OVERLAP;
i
i
i
i
i
i
i
i
746 16. Intersection Test Methods
In terms of code, this routine is fast, but it has the disadvantage of not
being able to return the intersection distance.
16.7.3 Ray Slope Method
In 2007 Eisemann et al. [301] presented a method of intersecting boxes that
appears to be faster than previous methods. Instead of a three-dimensional
test, the ray is tested against three projections of the box in two dimensions.
The key idea is that for each two-dimensional test, there are two box corners
that define the extreme extents of what the ray “sees,” akin to the silhouette
edges of a model. To intersect this projection of the box, the slope of the
ray must be between the two slopes defined by the ray’s origin and these
two points. If this test passes for all three projections, the ray must hit
the box. The method is extremely fast because some of the comparison
terms rely entirely on the ray’s values. By computing these terms once,
the ray can then efficiently be compared against a large number of boxes.
This method can return just whether the box was hit, or can also return
the intersection distance, at a little additional cost.
16.8 Ray/Triangle Intersection
In real-time graphics libraries and APIs, triangle geometry is usually stored
as a set of vertices with associated normals, and each triangle is defined
by three such vertices. The normal of the plane in which the triangle lies
is often not stored, in which case it must be computed if needed. There
exist many different ray/triangle intersection tests, and many of them first
compute the intersection point between the ray and the triangle’s plane.
Thereafter, the intersection point and the triangle vertices are projected
on the axis-aligned plane (xy, yz,orxz) where the area of the triangle
is maximized. By doing this, we reduce the problem to two dimensions,
and we need only decide whether the (two-dimensional) point is inside
the (two-dimensional) triangle. Several such methods exist, and they have
been reviewed and compared by Haines [482], with code available on the
web. See Section 16.9 for one popular algorithm using this technique. A
wealth of algorithms have been evaluated for different CPU architectures,
compilers, and hit ratios [803], and it could not be concluded that there is
a single best test in all cases.
Here, the focus will be on an algorithm that does not presume that nor-
mals are precomputed. For triangle meshes, this can amount to significant
memory savings, and for dynamic geometry, we do not need to recompute
any extra data, such as the plane equation of the triangle every frame. This
algorithm, along with optimizations, was discussed by M¨oller and Trum-
i
i
i
i
i
i
i
i
16.8. Ray/Triangle Intersection 747
bore [890], and their presentation is used here. It is also worth noting that
Kensler and Shirley [644] noted that most ray-triangle tests operating di-
rectly in three dimensions
6
are computationally equivalent. They develop
new tests using SSE to test four rays against a triangle, and use a genetic
algorithm to find the best order of the operations in this equivalent test.
Code for the best-performing test is in the paper.
The ray from Equation 16.1 is used to test for intersection with a tri-
angle defined by three vertices, p
1
, p
2
,andp
3
—i.e., p
1
p
2
p
3
.
16.8.1 Intersection Algorithm
Apoint,f(u, v), on a triangle is given by the explicit formula
f(u, v)=(1− u − v)p
0
+ up
1
+ vp
2
, (16.19)
where (u, v)aretwoofthebarycentric coordinates, which must fulfill u ≥ 0,
v ≥ 0, and u + v ≤ 1. Note that (u, v) can be used for texture mapping,
normal interpolation, color interpolation, etc. That is, u and v are the
amounts by which to weight each vertex’s contribution to a particular lo-
cation, with w =(1− u − v) being the third weight.
7
See Figure 16.9.
Figure 16.9. Barycentric coordinates for a triangle, along with example point values.
The values u, v,andw all vary from 0 to 1 inside the triangle, and the sum of these
three is always 1 over the entire plane. These values can be used as weights for how
data at each of the three vertices influence any point on the triangle. Note how at each
vertex, one value is 1 and the others 0, and along edges, one value is always 0.
6
As opposed to first computing the intersection between the ray and the plane, and
then performing a two-dimensional inside test.
7
These coordinates are often denoted α, β,andγ.Weuseu, v,andw here for
readability and consistency of notation.
i
i
i
i
i
i
i
i
748 16. Intersection Test Methods
p
2
p
1
p
0
p
2
-p
0
p
1
-p
0
p
0
p
0
Figure 16.10. Translation and change of base of the ray origin.
Computing the intersection between the ray, r(t), and the triangle,
f(u, v), is equivalent to r(t)=f(u, v), which yields
o + td =(1−u − v)p
0
+ up
1
+ vp
2
. (16.20)
Rearranging the terms gives
⎛
⎝
−dp
1
− p
0
p
2
− p
0
⎞
⎠
⎛
⎝
t
u
v
⎞
⎠
= o − p
0
. (16.21)
This means the barycentric coordinates (u, v) and the distance t from
the ray origin to the intersection point can be found by solving this linear
system of equations.
This manipulation can be thought of geometrically as translating the
triangle to the origin and transforming it to a unit triangle in y and z with
the ray direction aligned with x. This is illustrated in Figure 16.10. If
M =(−dp
1
− p
0
p
2
− p
0
) is the matrix in Equation 16.21, then the
solution is found by multiplying Equation 16.21 with M
−1
.
Denoting e
1
= p
1
− p
0
, e
2
= p
2
− p
0
,ands = o − p
0
, the solution to
Equation 16.21 is obtained by using Cramer’s rule:
⎛
⎝
t
u
v
⎞
⎠
=
1
det(−d, e
1
, e
2
)
⎛
⎝
det(s, e
1
, e
2
)
det(−d, s, e
2
)
det(−d, e
1
, s)
⎞
⎠
. (16.22)
i
i
i
i
i
i
i
i
16.8. Ray/Triangle Intersection 749
From linear algebra, we know that det(a, b, c)=|abc| = −(a×c)·b =
−(c × b) · a. Equation 16.22 can therefore be rewritten as
⎛
⎝
t
u
v
⎞
⎠
=
1
(d × e
2
) · e
1
⎛
⎝
(s × e
1
) · e
2
(d × e
2
) · s
(s × e
1
) · d
⎞
⎠
=
1
q · e
1
⎛
⎝
r · e
2
q · s
r · d
⎞
⎠
, (16.23)
where q = d × e
2
and r = s × e
1
. These factors can be used to speed up
the computations.
If you can afford some extra storage, this test can be reformulated
in order to reduce the number of computations. Equation 16.23 can be
rewritten as
⎛
⎝
t
u
v
⎞
⎠
=
1
(d × e
2
) · e
1
⎛
⎝
(s × e
1
) · e
2
(d × e
2
) · s
(s × e
1
) · d
⎞
⎠
=
1
−(e
1
× e
2
) · d
⎛
⎝
(e
1
× e
2
) · s
(s × d) · e
2
−(s × d) · e
1
⎞
⎠
=
1
−n · d
⎛
⎝
n · s
m · e
2
−m · e
1
⎞
⎠
, (16.24)
where n = e
1
× e
2
is the unnormalized normal of the triangle, and hence
constant (for static geometry), and m = s×d.Ifwestorep
0
, e
1
, e
2
,andn
for each triangle, we can avoid many ray triangle intersection computations.
Most of the gain comes from avoiding a cross product. It should be noted
that this defies the original idea of the algorithm, namely to store minimal
information with the triangle. However, if speed is of utmost concern,
this may a reasonable alternative. The tradeoff is whether the savings
in computation is outweighed by the additional memory accesses. Only
careful testing can ultimately show what is fastest.
16.8.2 Implementation
The algorithm is summarized in the pseudocode below. Besides returning
whether or not the ray intersects the triangle, the algorithm also returns
the previously-described triple (u, v, t).Thecodedoesnotcullbackfacing
triangles, and it returns intersections for negative t-values, but these can
be culled too, if desired.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.