i
i
i
i
i
i
i
i
74 4. Ray Tracing
Figure 4.7. The sample points on the screen are mapped to a similar array on the 3D
window. A viewing ray is sent to each of these locations.
All of our ray-generation methods start from an orthonormal coordinate frame
known as the camera frame, which we’ll denote by e, for the eye point, or view-
point, and u, v,andw for the three basis vectors, organized with u pointing right-
up
view
u
v
w
Figure 4.8. The vectors of
the camera frame, together
with the view direction and
up direction. The w vec-
tor is opposite the view di-
rection, and the v vector is
coplanar with w and the up
vector.
ward (from the camera’s view), v pointing upward, and w pointing backward, so
that {u, v, w} forms a right-handed coordinate system. The most common way
to construct the camera frame is from the viewpoint, which becomes e,theview
direction,whichis−w,andtheup vector, which is used to construct a basis that
has v and w in the plane defined by the view direction and the up direction, using
Since v and w have to be
perpendicular, the up vec-
tor and v are not generally
the same. But setting the
up vector to point straight
upward in the scene will ori-
ent the camera in the way
we would think of as “up-
right.”
the process for constructing an orthonormal basis from two vectors described in
Section 2.4.7.
4.3.1 Orthographic Views
For an orthographic view, all the rays will have the direction −w. Even though
a parallel view doesn’t have a viewpoint per se, we can still use the origin of the
It might seem logical that
orthographic viewing rays
should start from infinitely
far away, but then it would
not be possible to make or-
thographic views of an ob-
ject inside a room, for in-
stance.
camera frame to define the plane where the rays start, so that it’s possible for
objects to be behind the camera.
The viewing rays should start on the plane defined by the point e and the
vectors u and v; the only remaining information required is where on the plane the
image is supposed to be. We’ll define the image dimensions with four numbers,
for the four sides of the image: l and r are the positions of the left and right
edges of the image, as measured from e along the u direction; and b and t are the
Many systems assume that
l
=–
r
and
b
=–
t
so that a
width and a height suffice.
positions of the bottom and top edges of the image, as measured from e along the
v direction. Usually l<0 <rand b<0 <t. (See Figure 4.9.)
In Section 3.2 we discussed pixel coordinates in an image. To fitanimage
with n
x
× n
y
pixels into a rectangle of size (r − l) × (t − b), the pixels are
spaced a distance (r − l)/n
x
apart horizontally and (t − b)/n
y
apart vertically,
i
i
i
i
i
i
i
i
4.3. Computing Viewing Rays 75
u
e
v
w
u
e
w
v
Parallel projection
same direction, different origins
Perspective projection
same origin, different directions
Figure 4.9. Ray generation using the camera frame. Left: In an orthographic view, the rays
start at the pixels’ locations on the image plane, and all share the same direction, which is
equal to the view direction. Right: In a perspective view, the rays start at the viewpoint, and
each ray’s direction is defined by the line through the viewpoint, e, and the pixel’s location on
the image plane.
with a half-pixel space around the edge to center the pixel grid within the image
rectangle. This means that the pixel at position (i, j) in the raster image has the
position
With
l
and
r
both specified,
there is redundancy: mov-
ing the viewpoint a bit to
the right and correspond-
ingly decreasing
l
and
r
will
not change the view (and
similarly on the v-axis).
u = l +(r − l)(i +0.5)/n
x
,
v = b +(t − b)(j +0.5)/n
y
,
(4.1)
where (u, v) are the coordinates of the pixel’s position on the image plane, mea-
sured with respect to the origin e and the basis {u, v}.
In an orthographic view, we can simply use the pixel’s image-plane position
as the ray’s starting point, and we already know the ray’s direction is the view
direction. The procedure for generating orthographic viewing rays is then:
compute u and v using (4.1)
ray.direction ←−w
ray.origin ← e + u u + v v
It’s very simple to make an oblique parallel view: just allow the image plane
normal w to be specified separately from the view direction d. The procedure is
then exactly the same, but with d substituted for −w. Of course w is still used to
construct u and v.
4.3.2 Perspective Views
For a perspective view, all the rays have the same origin, at the viewpoint; it
is the directions that are different for each pixel. The image plane is no longer
i
i
i
i
i
i
i
i
76 4. Ray Tracing
positioned at e, but rather some distance d in front of e; this distance is the image
plane distance, often loosely called the focal length, because choosing d plays the
same role as choosing focal length in a real camera. The direction of each ray is
defined by the viewpoint and the position of the pixel on the image plane. This
situation is illustrated in Figure 4.9, and the resulting procedure is similar to the
orthographic one:
compute u and v using (4.1)
ray.direction ←−d w + u u + v v
ray.origin ← e
As with parallel projection, oblique perspective views can be achieved by spec-
ifying the image plane normal separately from the projection direction, then re-
placing −d w with dd in the expression for the ray direction.
4.4 Ray-Object Intersection
Once we’ve generated a ray e+ td, we next need to find the first intersection with
any object where t>0. In practice it turns out to be useful to solve a slightly
more general problem: find the first intersection between the ray and a surface that
occurs at a t in the interval [t
0
,t
1
]. The basic ray intersection is the case where
t
0
=0and t
1
=+∞. We solve this problem for both spheres and triangles. In
the next section, multiple objects are discussed.
4.4.1 Ray-Sphere Intersection
Given a ray p(t)=e + td and an implicit surface f(p)=0(see Section 2.5.3),
we’d like to know where they intersect. Intersection points occur when points on
the ray satisfy the implicit equation, so the values of t we seek are those that solve
the equation
f(p(t)) = 0 or f (e + td)=0.
A sphere with center c =(x
c
,y
c
,z
c
) and radius R can be represented by the
implicit equation
(x − x
c
)
2
+(y −y
c
)
2
+(z −z
c
)
2
− R
2
=0.
We can write this same equation in vector form:
(p − c) · (p −c) − R
2
=0.
i
i
i
i
i
i
i
i
4.4. Ray-Object Intersection 77
Any point p that satisfies this equation is on the sphere. If we plug points on the
ray p(t)=e + td into this equation, we get an equation in terms of t that is
satisfied by the values of t that yield points on the sphere:
(e + td − c) · (e + td − c) −R
2
=0.
Rearranging terms yields
(d · d)t
2
+2d ·(e − c)t +(e − c) · (e − c) − R
2
=0.
Here, everything is known except the parameter t, so this is a classic quadratic
equation in t, meaning it has the form
At
2
+ Bt + C =0.
The solution to this equation is discussed in Section 2.2. The term under the
square root sign in the quadratic solution, B
2
− 4AC, is called the discriminant
and tells us how many real solutions there are. If the discriminant is negative,
its square root is imaginary and the line and sphere do not intersect. If the dis-
criminant is positive, there are two solutions: one solution where the ray enters
the sphere and one where it leaves. If the discriminant is zero, the ray grazes
the sphere, touching it at exactly one point. Plugging in the actual terms for the
sphere and canceling a factor of two, we get
t =
−d · (e − c) ±
(d · (e − c))
2
− (d · d)((e − c) · (e − c) −R
2
)
(d · d)
.
In an actual implementation, you should first check the value of the discriminant
before computing other terms. If the sphere is used only as a bounding object for
more complex objects, then we need only determine whether we hit it; checking
the discriminant suffices.
As discussed in Section 2.5.4, the normal vector at point p is given by the
gradient n =2(p − c). The unit normal is (p − c)/R.
4.4.2 Ray-Triangle Intersection
There are many algorithms for computing ray-triangle intersections. We will
present the form that uses barycentric coordinates for the parametric plane con-
taining the triangle, because it requires no long-term storage other than the ver-
tices of the triangle (Snyder & Barr, 1987).
i
i
i
i
i
i
i
i
78 4. Ray Tracing
To intersect a ray with a parametric surface, we set up a system of equations
where the Cartesian coordinates all match:
x
e
+ tx
d
= f (u, v)
y
e
+ ty
d
= g(u, v)
z
e
+ tz
d
= h(u, v)
⎫
⎪
⎬
⎪
⎭
or, e + td = f(u, v).
Here, we have three equations and three unknowns (t, u,andv), so we can solve
numerically for the unknowns. If we are lucky, we can solve for them analytically.
In the case where the parametric surface is a parametric plane, the parametric
equation can be written in vector form as discussed in Section 2.7.2. If the vertices
of the triangle are a, b,andc, then the intersection will occur when
e + td = a + β(b − a)+γ(c − a), (4.2)
for some t, β,andγ. The intersection p will be at e + td as shown in Figure 4.10.
Again, from Section 2.7.2, we know the intersection is inside the triangle if and
only if β>0, γ>0,andβ + γ<1. Otherwise, the ray has hit the plane outside
Figure 4.10. The ray hits
the plane containing the tri-
angle at point p.
the triangle, so it misses the triangle. If there are no solutions, either the triangle
is degenerate or the ray is parallel to the plane containing the triangle.
To solve for t, β,andγ in Equation (4.2), we expand it from its vector form
into the three equations for the three coordinates:
x
e
+ tx
d
= x
a
+ β(x
b
− x
a
)+γ(x
c
− x
a
),
y
e
+ ty
d
= y
a
+ β(y
b
− y
a
)+γ(y
c
− y
a
),
z
e
+ tz
d
= z
a
+ β(z
b
− z
a
)+γ(z
c
− z
a
).
This can be rewritten as a standard linear system:
⎡
⎣
x
a
− x
b
x
a
− x
c
x
d
y
a
− y
b
y
a
− y
c
y
d
z
a
− z
b
z
a
− z
c
z
d
⎤
⎦
⎡
⎣
β
γ
t
⎤
⎦
=
⎡
⎣
x
a
− x
e
y
a
− y
e
z
a
− z
e
⎤
⎦
.
The fastest classic method to solve this 3 ×3 linear system is Cr amer’s rule.This
gives us the solutions
β =
x
a
− x
e
x
a
− x
c
x
d
y
a
− y
e
y
a
− y
c
y
d
z
a
− z
e
z
a
− z
c
z
d
|A|
,
γ =
x
a
− x
b
x
a
− x
e
x
d
y
a
− y
b
y
a
− y
e
y
d
z
a
− z
b
z
a
− z
e
z
d
|A|
,
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.