i
i
i
i
i
i
i
i
28 2. Miscellaneous Math
2.4.6 Constructing a Basis from a Single Vector
Often we need an orthonormal basis that is aligned with a given vector. That is,
given a vector a, we want an orthonormal u, v,andw such that w points in the
same direction as a (Hughes & M¨oller, 1999), but we don’t particularly care what
u and v are. One vector isn’t enough to uniquely determine the answer; we just
need a robust procedure that will find any one of the possible bases.
This can be done using cross products as follows. First make w a unit vector
in the direction of a:
This same procedure can,
of course, be used to con-
struct the three vectors in
any order; just pay atten-
tion to the order of the cross
products to ensure the ba-
sis is right handed.
w =
a
a
.
Then choose any vector t not collinear with w, and use the cross product to build
a unit vector u perpendicular to w:
u =
t × w
t × w
.
If t is collinear with w the denominator will vanish, and if they are nearly collinear
the results will have low precision. A simple procedure to find a vector suffi-
ciently different from w is to start with t equal to w and change the smallest
magnitude component of t to 1. For example, if w =(1/
√
2, −1/
√
2, 0) then
t =(1/
√
2, −1/
√
2, 1).Oncew and u are in hand, completing the basis is
simple:
v = w × u.
An example of a situation where this construction is used is surface shading,
where a basis aligned to the surface normal is needed but the rotation around
the normal is often unimportant.
2.4.7 Constructing a Basis from Two Vectors
The procedure in the previous section can also be used in situations where the
rotation of the basis around the given vector is important. A common example
is building a basis for a camera: it’s important to have one vector aligned in the
direction the camera is looking, but the orientation of the camera around that
vector is not arbitrary, and it needs to be specified somehow. Once the orientation
is pinned down, the basis is completely determined.
A common way to fully specify a frame is by providing two vectors a (which
specifies w)andb (which specifies v). If the two vectors are known to be per-
u = a ×b also produces an
orthonormal basis, but it is
left-handed.
pendicular it is a simple matter to construct the third vector by u = b × a.
i
i
i
i
i
i
i
i
2.4. Vectors 29
To be sure that the resulting basis really is orthonormal, even if the input vec-
tors weren’t quite, a procedure much like the single-vector procedureis advisable:
w =
a
a
,
u =
b × w
b × w
,
v = w × u.
In fact, this procedure works just fine when a and b are not perpendicular. In this
If you want me to set w and
v to two non-perpendicular
directions, something has
to give—with this scheme
I’ll set everything the way
you want, except I’ll make
the smallest change to
v so
that it is in fact perpendicu-
lar to w.
case, w will be constructed exactly in the direction of a,andv is chosen to be the
closest vector to b among all vectors perpendicular to w.
This procedure won’t work if a and b are collinear. In this case b is of no
help in choosing which of the directions perpendicular to a we should use: it is
perpendicular to all of them.
What will go wrong with the
computation if a and b are
parallel?
In the example of specifying camera positions (Section 4.3), we want to con-
struct a frame that has w parallel to the direction the camera is looking, and v
should point out the top of the camera. To orient the camera upright, we build the
basis around the view direction, using the straight-up direction as the reference
vector to establish the camera’s orientation around the view direction. Setting v
as close as possible to straight up exactly matches the intuitive notion of “holding
the camera straight.”
2.4.8 Squaring Up a Basis
Occasionally you may find problems caused in your computations by a basis that
is supposed to be orthonormal but where error has crept in—due to rounding error
in computation, or to the basis having been stored in a file with low precision, for
instance.
The procedure of the previous section can be used; simply constructing the
basis anew using the existing w and v vectors will produce a new basis that is
orthonormal and is close to the old one.
This approach is good for many applications, but it is not the best available.
It does produce accurately orthogonal vectors, and for nearly orthogonal starting
bases the result will not stray far from the starting point. However, it is asym-
metric: it “favors” w over v and v over u (whose starting value is thrown away).
It chooses a basis close to the starting basis but has no guarantee of choosing the
closest orthonormal basis. When this is not good enough, the SVD (Section 5.4.1)
can be used to compute an orthonormal basis that is guaranteed to be closest to
the original basis.
i
i
i
i
i
i
i
i
30 2. Miscellaneous Math
2.5 Curves and Surfaces
The geometry of curves, and especially surfaces, plays a central role in graphics,
and here we review the basics of curves and surfaces in 2D and 3D space.
2.5.1 2D Implicit Curves
Intuitively, a curve is a set of points that can be drawn on a piece of paper without
lifting the pen. A common way to describe a curve is using an implicit equation.
An implicit equation in two dimensions has the form
f(x, y)=0.
The function f(x, y) returns a real value. Points (x, y) where this value is zero
are on the curve, and points where the value is non-zero are not on the curve. For
example, let’s say that f(x, y) is
f(x, y)=(x −x
c
)
2
+(y − y
c
)
2
− r
2
, (2.9)
where (x
c
,y
c
) is a 2D point and r is a non-zero real number. If we take f(x, y)=
Figure 2.22. An implicit
function
f
(
x,y
) = 0 can be
thought of as a height field
where
f
is the height (top).
A path where the height is
zero is the implicit curve
(bottom).
0, the points where this equality holds are on the circle with center (x
c
,y
c
) and ra-
dius r. The reason that this is called an “implicit” equation is that the points (x, y)
on the curve cannot be immediately calculated from the equation and instead must
be determined by solving the equation. Thus, the points on the curve are not gen-
erated by the equation explicitly, but they are buried somewhere implicitly in the
equation.
It is interesting to note that f does have values for all (x, y). We can think of f
as a terrain, with sea-level at f =0(Figure 2.22). The shore is the implicit curve.
The value of f is the altitude. Another thing to note is that the curve partitions
space into regions where f>0, f<0,andf =0. So you evaluate f to decide
whether a point is “inside” a curve. Note that f(x, y)=c is a curve for any
constant c,andc =0is just used as a convention. For example if f(x, y)=x
2
+
y
2
−1, varying c just gives a variety of circles centered at the origin (Figure 2.23).
We can compress our notation using vectors. If we have c =(x
c
,y
c
) and
p =(x, y), then our circle with center c and radius r is defined by those position
Figure 2.23. An implicit
function
f
(
x,y
) = 0 can be
thought of as a height field
where
f
is the height (top).
A path where the height is
zero is the implicit curve
(bottom).
vectors that satisfy
(p − c) · (p −c) − r
2
=0.
This equation, if expanded algebraically, will yield Equation (2.9), but it is easier
to see that this is an equation for a circle by “reading” the equation geometrically.
It reads, “points p on the circle have the following property: the vector from c to
i
i
i
i
i
i
i
i
2.5. Curves and Surfaces 31
p when dotted with itself has value r
2
.” Because a vector dotted with itself is just
its own length squared, we could also read the equation as, “points p on the circle
have the following property: the vector from c to p has squared length r
2
.”
Even better, is to observe that the squared length is just the squared distance
from c to p, which suggests the equivalent form
p − c
2
− r
2
=0,
and, of course, this suggests
p − c−r =0.
The above could be read “the points p on the circle are those a distance r from
the center point c,” which is as good a definition of circle as any. This illustrates
that the vector form of an equation often suggests more geometry and intuition
than the equivalent full-blown Cartesian form with x and y. For this reason, it
is usually advisable to use vector forms when possible. In addition, you can
support a vector class in your code; the code is cleaner when vector forms are
used. The vector-oriented equations are also less error prone in implementation:
once you implement and debug vector types in your code, the cut-and-paste errors
involving x, y,andz will go away. It takes a little while to get used to vectors in
these equations, but once you get the hang of it, the payoff is large.
2.5.2 The 2D Gradient
If we think of the function f(x, y) as a height field with height = f(x, y),the
gradient vector points in the direction of maximum upslope, i.e., straight uphill.
The gradient vector ∇f(x, y) is given by
∇f(x, y)=
∂f
∂x
,
∂f
∂y
.
The gradient vector evaluated at a point on the implicit curve f(x, y)=0is
perpendicular to the tangent vector of the curve at that point. This perpendicular
vector is usually called the normal vector to the curve. In addition, since the
gradient points uphill, it indicates the direction of the f(x, y) > 0 region.
In the contextof height fields, the geometric meaning of partial derivatives and
gradients is more visible than usual. Suppose that near the point (a, b), f(x, y) is
Figure 2.24. Asurface
height =
f
(
x,y
) is locally pla-
nar near (
x,y
)=(
a,b
). The
gradient is a projection of
the uphill direction onto the
height = 0 plane.
a plane (Figure 2.24). There is a specific uphill and downhill direction. At right
angles to this direction is a direction that is level with respect to the plane. Any
intersection between the plane and the f(x, y)=0plane will be in the direction
that is level. Thus the uphill/downhill directions will be perpendicular to the line
of intersection f(x, y)=0. To see why the partial derivative has something to do
i
i
i
i
i
i
i
i
32 2. Miscellaneous Math
with this, we need to visualize its geometric meaning. Recall that the conventional
derivative of a 1D function y = g(x) is
dy
dx
≡ lim
Δx→0
Δy
Δx
= lim
Δx→0
g(x +Δx) −g(x)
Δx
. (2.10)
This measures the slope of the tangent line to g (Figure 2.25).
The partial derivative is a generalization of the 1D derivative. For a 2D func-
tion f(x, y), we can’t take the same limit for x as in Equation (2.10), because
f can change in many ways for a given change in x. However, if we hold y
constant, we can define an analog of the derivative, called the partial derivative
(Figure 2.26):
Figure 2.25. The deriva-
tive of a 1D function mea-
sures the slope of the line
tangent to the curve.
∂f
∂x
≡ lim
Δx→0
f(x +Δx, y) − f (x, y)
Δx
.
Why is it that the partial derivatives of x and y are the components of the gradient
vector? Again, there is more obvious insight in the geometry than in the algebra.
In Figure 2.27, we see the vector a travels along a path where f does not change.
Note that this is again at a small enough scale that the surface height (x, y)=
f(x, y) can be considered locally planar. From the figure, we see that the vector
a =(Δx, Δy).
Because the uphill direction is perpendicular to a, we know the dot product is
equal to zero:
(∇f) ·a ≡ (x
∇
,y
∇
) · (x
a
,y
a
)=x
∇
Δx + y
∇
Δy =0. (2.11)
We also know that the change in f in the direction (x
a
,y
a
) equals zero:
Figure 2.26. The par-
tial derivative of a 2D func-
tion with respect to
f
must
hold
y
constant to have a
unique value, as shown by
the dark point. The hollow
points show other values of
f
that do not hold
y
con-
stant.
Δf =
∂f
∂x
Δx +
∂f
∂y
Δy ≡
∂f
∂x
x
a
+
∂f
∂y
y
a
=0. (2.12)
Given any vectors (x, y) and (x
,y
) that are perpendicular, we know that the
angle between them is 90 degrees, and thus their dot product equals zero (recall
that the dot product is proportional to the cosine of the angle between the two
vectors). Thus, we have xx
+ yy
=0.Given(x, y), it is easy to construct
valid vectors whose dot product with (x, y) equals zero, the two most obvious
being (y, −x) and (−y, x); you can verify that these vectors give the desired
zero dot product with (x, y). A generalization of this observation is that (x, y) is
perpendicular to k(y,−x) where k is any non-zero constant. This implies that
(x
a
,y
a
)=k
∂f
∂y
, −
∂f
∂x
. (2.13)
Combining Equations (2.11) and (2.13) gives
(x
∇
,y
∇
)=k
∂f
∂x
,
∂f
∂y
,
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.