i
i
i
i
i
i
i
i
740 16. Intersection Test Methods
16.6.2 Optimized Solution
For the ray/sphere intersection problem, we begin by observing that inter-
sections behind the ray origin are not needed (this is normally the case in
picking, etc.). Therefore, a vector l = c − o, which is the vector from the
ray origin to the center of the sphere, is computed. All notation that is
used is depicted in Figure 16.6. Also, the squared length of this vector is
computed, l
2
= l · l.Nowifl
2
<r
2
, this implies that the ray origin is in-
side the sphere, which, in turn, means that the ray is guaranteed to hit the
sphere and we can exit if we want to detect only whether or not the ray hits
the sphere; otherwise, we proceed. Next, the projection of l onto the ray
direction, d, is computed: s = l·d. Now, here comes the first rejection test:
If s<0 and the ray origin is outside the sphere, then the sphere is behind
the ray origin and we can reject the intersection. Otherwise, the squared
distance from the sphere center to the projection is computed using the
Pythagorean theorem (Equation B.6): m
2
= l
2
− s
2
. The second rejection
test is even simpler than the first: If m
2
>r
2
the ray will definitely miss
the sphere and the rest of the calculations can safely be omitted. If the
sphere and ray pass this last test, then the ray is guaranteed to hit the
sphere and we can exit if that was all we were interested in finding out.
To find the real intersection points, a little more work has to be done.
First, the squared distance q
2
= r
2
− m
2
(see Figure 16.6) is calculated.
4
Since m
2
<= r
2
, q
2
is greater than or equal to zero, and this means that
q =
q
2
can be computed. Finally, the distances to the intersections
are t = s ± q, whose solution is quite similar to that of the second-order
Figure 16.6. The notation for the geometry of the optimized ray/sphere intersection.
In the left figure, the ray intersects the sphere in two points, where the distances are
t = s ±q along the ray. The middle case demonstrates a rejection made when the sphere
is behind the ray origin. Finally, at the right, the ray origin is inside the sphere, in which
case the ray always hits the sphere.
4
The scalar r
2
could be computed once and stored within the data structure of the
sphere in an attempt to gain further efficiency. In practice such an “optimization” may
be slower, as more memory is then accessed, a major factor for algorithm performance.
i
i
i
i
i
i
i
i
16.7. Ray/Box Intersection 741
equation obtained in the previous mathematical solution section. If we
are interested in only the first, positive intersection point, then we should
use t
1
= s − q for the case where the ray origin is outside the sphere and
t
2
= s + q when the ray origin is inside. The true intersection point(s) are
found by inserting the t-value(s) into the ray equation (Equation 16.1).
Pseudocode for the optimized version is shown in the box below. The
routine returns a boolean value that is REJECT if the ray misses the sphere
and INTERSECT otherwise. If the ray intersects the sphere, then the dis-
tance, t, from the ray origin to the intersection point along with the inter-
section point, p, are also returned.
RaySphereIntersect(o, d, c,r)
returns ({REJECT, INTERSECT},t,p)
1: l = c − o
2: s = l · d
3: l
2
= l ·l
4: if(s<0 and l
2
>r
2
) return (REJECT, 0, 0);
5: m
2
= l
2
− s
2
6: if(m
2
>r
2
) return (REJECT, 0, 0);
7: q =
√
r
2
− m
2
8: if(l
2
>r
2
) t = s −q
9: else t = s + q
10 : return (INTERSECT,t,o + td);
Note that after line 3, we can test whether p is inside the sphere and, if
all we want to know is whether the ray and sphere intersect, the routine can
terminate if they do so. Also, after line 6, the ray is guaranteed to hit the
sphere. If we do an operation count (counting adds, multiplies, compares,
etc.), we find that the geometric solution, when followed to completion, is
approximately equivalent to the algebraic solution presented earlier. The
important difference is that the rejection tests are done much earlier in the
process, making the overall cost of this algorithm lower on average.
Optimized geometric algorithms exist for computing the intersection
between a ray and some other quadrics and hybrid objects. For example,
there are methods for the cylinder [216, 539, 1163], cone [539, 1164], el-
lipsoid, capsule (a cylinder with spherical caps), and lozenge (a box with
cylindrical sides and spherical corners) [294].
16.7 Ray/Box Intersection
Three methods for determining whether a ray intersects a solid box are
given below. The first handles both AABBs and OBBs. The second is
i
i
i
i
i
i
i
i
742 16. Intersection Test Methods
often faster, but deal with only the simpler AABB. The third is based
on the separating axis test on page 731, and handles only line segments
versus AABBs. Here, we use the definitions and notation of the BVs from
Section 16.2.
16.7.1 Slabs Method
One scheme for ray/AABB intersection is based on Kay and Kajiya’s slab
method [480, 639], which in turn is inspired by the Cyrus-Beck line clipping
algorithm [217].
We extend this scheme to handle the more general OBB volume. It
returns the closest positive t-value (i.e., the distance from the ray origin o
to the point of intersection, if any exists). Optimizations for the AABB will
be treated after we present the general case. The problem is approached
by computing all t-values for the ray and all planes belonging to the faces
of the OBB. The box is considered as a set of three slabs,
5
as illustrated
in two dimensions in the left part of Figure 16.7. For each slab, there is
a minimum and a maximum t-value, and these are called t
min
i
and t
max
i
,
∀i ∈{u, v, w}. The next step is to compute the variables in Equation 16.14:
t
min
=max(t
min
u
,t
min
v
,t
min
w
)
t
max
=min(t
max
u
,t
max
v
,t
max
w
)
(16.14)
max
max
max
max
min
min
min
min
Figure 16.7. The left figure shows a two-dimensional OBB (oriented bounding box)
formed by two slabs, while the right shows two rays that are tested for intersection with
the OBB. All t-values are shown, and they are subscripted with u for the green slab and
with v for the other. The extreme t-values are marked with boxes. The left ray hits the
OBB since t
min
<t
max
, and the right ray misses since t
max
<t
min
.
5
A slab is two parallel planes, which are grouped for faster computations.
i
i
i
i
i
i
i
i
16.7. Ray/Box Intersection 743
Now, the clever test: If t
min
≤ t
max
, then the ray intersects the box; oth-
erwise it misses. The reader should convince himself of this by inspecting
the illustration on the right side of Figure 16.7.
Pseudocode for the ray/OBB intersection test, between an OBB (A)and
a ray (described by Equation 16.1) follows. The code returns a boolean in-
dicating whether or not the ray intersects the OBB (INTERSECT or REJECT),
and the distance to the intersection point (if it exists). Recall that for an
OBB A, the center is denoted a
c
,anda
u
, a
v
,anda
w
are the normalized
side directions of the box; h
u
, h
v
,andh
w
are the positive half-lengths (from
the center to a box face).
RayOBBIntersect(o, d,A)
returns ({REJECT, INTERSECT},t);
1: t
min
= −∞
2: t
max
= ∞
3: p = a
c
− o
4: for each i ∈{u, v, w}
5: e = a
i
· p
6: f = a
i
· d
7: if(|f| >)
8: t
1
=(e + h
i
)/f
9: t
2
=(e − h
i
)/f
10 : if(t
1
>t
2
) swap(t
1
,t
2
);
11 : if(t
1
>t
min
) t
min
= t
1
12 : if(t
2
<t
max
) t
max
= t
2
13 : if(t
min
>t
max
) return (REJECT, 0);
14 : if(t
max
< 0) return (REJECT, 0);
15 : else if( − e − h
i
> 0 or − e + h
i
< 0) return (REJECT, 0);
16 : if(t
min
> 0) return (INTERSECT,t
min
);
17 : else return (INTERSECT,t
max
);
Line 7 checks whether the ray direction is not perpendicular to the normal
direction of the slab currently being tested. In other words, it tests whether
the ray is not parallel to the slab planes and so can intersect them. Note
that is a very small number here, on the order of 10
−20
, simply to avoid
overflow when the division occurs. Lines 8 and 9 show a division by f;in
practice, it is usually faster to compute 1/f once and multiply by this value,
since division is often expensive. Line 10 ensures that the minimum of t
1
and t
2
is stored in t
1
, and consequently, the maximum of these is stored in
t
2
. In practice, the swap does not have to be made; instead lines 11 and 12
can be repeated for the branch, and t
1
and t
2
can change positions there.
Should line 13 return, then the ray misses the box, and similarly, if line 14
i
i
i
i
i
i
i
i
744 16. Intersection Test Methods
returns, then the box is behind the ray origin. line 15 is executed if the
ray is parallel to the slab (and so cannot intersect it); it tests if the ray is
outside the slab. If so, then the ray misses the box and the test terminates.
For even faster code, Haines discusses a way of unwrapping the loop and
thereby avoiding some code [480].
There is an additional test not shown in the pseudocode that is worth
adding in actual code. As mentioned when we defined the ray, we usually
want to find the closest object. So after line 15, we could also test whether
t
min
≥ l,wherel is the current ray length. If the new intersection is not
closer, the intersection is rejected. This test could be deferred until after
the entire ray/OBB test has been completed, but it is usually more efficient
to try for an early rejection inside the loop.
There are other optimizations for the special case of an OBB that is
an AABB. Lines 5 and 6 change to e = p
i
and f = d
i
, which makes the
test faster. Normally the a
min
and a
max
corners of the AABB are used
on lines 8 and 9, so the addition and subtraction is avoided. Kay and
Kajiya [639] and Smits [1200] note that line 7 can be avoided by allowing
division by 0 and interpreting the processor’s results correctly. Williams et
al. [1352] provide implementation details to handle division by 0 correctly,
along with other optimizations. Woo [1373] introduced an optimization
where only three candidate planes are identified and tested against.
A generalization of the slabs method can be used to compute the inter-
section of a ray with a k-DOP, frustum, or any convex polyhedron; code is
available on the web [481].
16.7.2 Line Segment/Box Overlap Test
In this section, it will be shown that the separating axis test on page 731
can be used to determine whether a line segment overlaps an AABB [454].
The line segment has finite length in contrast to a ray. Assume the line
segment is defined by a center (mean of the two endpoints) c and a half
vector w. Furthermore, both the AABB, denoted B, and the line segment
have been translated so the AABB’s origin is (0, 0, 0). Also, the size of the
box is (2h
x
, 2h
y
, 2h
z
), i.e., h is the half vector of the box. This is shown in
Figure 16.8.
It is normally most effective to first test against an axis that is orthog-
onal to a face of both objects to be tested. Since the line segment does not
have a face, it does not generate any test. The box generates three axes to
test: (1, 0, 0), (0, 1, 0), and (0, 0, 1). Finally, the axes formed from the cross
product between line segment direction and the box axes should be tested.
Thetestfortheaxis(1, 0, 0) is shown below, and Figure 16.8 shows this
as well. The other two axes are similar:
|c
x
| > |w
x
| + h
x
. (16.16)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.