Table of contents for Game physics / David H. Eberly ; with a contribution by Ken Shoemaker.


Bibliographic record and links to related information available from the Library of Congress catalog. Note: Contents data are machine generated based on pre-publication information provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
Contents
Trademarks v
List of Figures xv
List of Tables xxvii
Preface xxix
About the CD-ROM xxxiii
Chapter 1 Introduction 1
1.1 A Brief History of the World 1
1.2 A Summary of the Topics 6
1.3 Examples and Exercises 11
Chapter 2 Basic Concepts from Physics 13
2.1 Rigid Body Classification 14
2.2 Rigid Body Kinematics 15
2.2.1 Single Particle 15
2.2.2 Particle Systems and Continuous Materials 28
2.3 Newton's Laws 31
2.4 Forces 32
2.4.1 Gravitational Forces 32
2.4.2 Spring Forces 34
2.4.3 Friction and Other Dissipative Forces 35
2.4.4 Torque 37
2.4.5 Equilibrium 39
2.5 Momenta 41
2.5.1 Linear Momentum 42
2.5.2 Angular Momentum 43
2.5.3 Center of Mass 44
2.5.4 Moments and Products of Inertia 57
2.5.5 Mass and Inertia Tensor of a Solid Polyhedron 66
2.6 Energy 79
2.6.1 Work and Kinetic Energy 79
2.6.2 Conservative Forces and Potential Energy 81
Chapter 3 Rigid Body Motion 87
3.1 Newtonian Dynamics 88
3.2 Lagrangian Dynamics 100
3.2.1 Equations of Motion for a Particle 102
3.2.2 Time-Varying Frames or Constraints 114
3.2.3 Interpretation of the Equations of Motion 117
3.2.4 Equations of Motion for a System of Particles 118
3.2.5 Equations of Motion for a Continuum of Mass 121
3.2.6 Examples with Conservative Forces 133
3.2.7 Examples with Dissipative Forces 139
3.3 Euler's Equations of Motion 152
Chapter 4 Deformable Bodies 161
4.1 Elasticity, Stress, and Strain 161
4.2 Mass-Spring Systems 164
4.2.1 One-Dimensional Array of Masses 164
4.2.2 Two-Dimensional Array of Masses 166
4.2.3 Three-Dimensional Array of Masses 170
4.2.4 Arbitrary Configurations 171
4.3 Control Point Deformation 173
4.3.1 B-Spline Curves 173
4.3.2 NURBS Curves 183
4.3.3 B-Spline Surfaces 187
4.3.4 NURBS Surfaces 188
4.3.5 Surfaces Built from Curves 190
4.4 Free-Form Deformation 197
4.5 Implicit Surface Deformation 203
4.5.1 Level Set Extraction 206
4.5.2 Isocurve Extraction in 2D Images 208
4.5.3 Isosurface Extraction in 3D Images 212
Chapter 5 Physics Engines 221
5.1 Unconstrained Motion 223
5.1.1 An Illustrative Implementation 228
5.1.2 A Practical Implementation 234
5.2 Constrained Motion 240
5.2.1 Collision Points 240
5.2.2 Collision Response for Colliding Contact 242
5.2.3 Collision Response for Resting Contact 265
5.2.4 An Illustrative Implementation 270
5.2.5 Lagrangian Dynamics 278
5.3 Collision Detection with Convex Polyhedra 280
5.3.1 The Method of Separating Axes 284
5.3.2 Stationary Objects 286
5.3.3 Objects Moving with Constant Linear Velocity 311
5.3.4 Oriented Bounding Boxes 334
5.3.5 Boxes Moving with Constant Linear and Angular Velocity 342
5.4 Collision Culling: Spatial and Temporal Coherence 348
5.4.1 Culling with Bounding Spheres 349
5.4.2 Culling with Axis-Aligned Bounding Boxes 354
5.5 Variations 361
Chapter
6 Physics and Shader Programs 367
6.1 Introduction 367
6.2 Vertex and Pixel Shaders 369
6.3 Deformation by Vertex Displacement 375
6.4 Skin-and-Bones Animation 378
6.5 Rippling Ocean Waves 379
6.6 Refraction 383
6.7 Fresnel Reflectance 386
6.8 Iridescence 388
Chapter 7 Linear Complementarity and Mathematical
Programming 391
7.1 Linear Programming 392
7.1.1 A Two-Dimensional Example 392
7.1.2 Solution by Pairwise Intersections 394
7.1.3 Statement of the General Problem 396
7.1.4 The Dual Problem 404
7.2 The Linear Complementarity Problem 407
7.2.1 The Lemke-Howson Algorithm 408
7.2.2 Zero Constant Terms 413
7.2.3 The Complementary Variable Cannot Leave the Dictionary 416
7.3 Mathematical Programming 418
7.3.1 Karush-Kuhn-Tucker Conditions 421
7.3.2 Convex Quadratic Programming 423
7.3.3 General Duality Theory 426
7.4 Applications 427
7.4.1 Distance Calculations 427
7.4.2 Contact Forces 436
Chapter 8 Differential Equations 437
8.1 First-Order Equations 437
8.2 Existence, Uniqueness, and Continuous Dependence 440
8.3 Second-Order Equations 442
8.4 General-Order Differential Equations 444
8.5 Systems of Linear Differential Equations 446
8.6 Equilibria and Stability 450
8.6.1 Stability for Constant-Coefficient Linear Systems 451
8.6.2 Stability for General Autonomous Systems 453
Chapter 9 Numerical Methods 457
9.1 Euler's Method 458
9.2 Higher-Order Taylor Methods 461
9.3 Methods via an Integral Formulation 462
9.4 Runge-Kutta Methods 465
9.4.1 Second-Order Methods 466
9.4.2 Third-Order Methods 468
9.4.3 Fourth-Order Method 469
9.5 Multistep Methods 470
9.6 Predictor-Corrector Methods 472
9.7 Extrapolation Methods 473
9.7.1 Richardson Extrapolation 473
9.7.2 Application to Differential Equations 474
9.7.3 Polynomial Interpolation and Extrapolation 476
9.7.4 Rational Polynomial Interpolation and Extrapolation 476
9.7.5 Modified Midpoint Method 477
9.7.6 Bulirsch-Stoer Method 478
9.8 Verlet Integration 478
9.8.1 ForcesWithout a Velocity Component 479
9.8.2 Forces with a Velocity Component 480
9.8.3 Simulating Drag in the System 481
9.8.4 Leap Frog Method 481
9.8.5 Velocity Verlet Method 483
9.8.6 Gear's Fifth-Order Predictor-Corrector Method 485
9.9 Numerical Stability and Its Relationship to Physical Stability
487
9.9.1 Stability for Single-Step Methods 488
9.9.2 Stability for Multistep Methods 490
9.9.3 Choosing a Stable Step Size 491
9.10 Stiff Equations 503
Chapter 10 Quaternions 507
10.1 Rotation Matrices 507
10.2 The Classical Approach 512
10.2.1 Algebraic Operations 512
10.2.2 Relationship of Quaternions to Rotations 515
10.3 A Linear Algebraic Approach 517
10.4 From Rotation Matrices to Quaternions 522
10.4.1 2D Rotations 523
10.4.2 Linearity 525
10.4.3 3D Rotations: Geometry 526
10.4.4 4D Rotations 529
10.4.5 3D Rotations: Algebra 531
10.4.6 4D Matrix 534
10.4.7 Retrospect, Prospect 538
10.5 Interpolation of Quaternions 539
10.5.1 Spherical Linear Interpolation 539
10.5.2 Spherical Quadratic Interpolation 541
10.6 Derivatives of Time-Varying Quaternions 543
Appendix A Linear Algebra 545
A.1 A Review of Number Systems 545
A.1.1 The Integers 545
A.1.2 The Rational Numbers 545
A.1.3 The Real Numbers 546
A.1.4 The Complex Numbers 546
A.1.5 Fields 547
A.2 Systems of Linear Equations 548
A.2.1 A Closer Look at Two Equations in Two Unknowns 551
A.2.2 Gaussian Elimination and Elementary Row Operations 554
A.2.3 Nonsquare Systems of Equations 558
A.2.4 The Geometry of Linear Systems 559
A.2.5 Numerical Issues 562
A.2.6 Iterative Methods for Solving Linear Systems 565
A.3 Matrices 566
A.3.1 Some Special Matrices 569
A.3.2 Elementary Row Matrices 570
A.3.3 Inverse Matrices 572
A.3.4 Properties of Inverses 574
A.3.5 Construction of Inverses 575
A.3.6 LU Decomposition 577
A.4 Vector Spaces 583
A.4.1 Definition of a Vector Space 588
A.4.2 Linear Combinations, Spans, and Subspaces 593
A.4.3 Linear Independence and Bases 595
A.4.4 Inner Products, Length, Orthogonality, and Projection 601
A.4.5 Dot Product, Cross Product, and Triple Products 606
A.4.6 Orthogonal Subspaces 613
A.4.7 The Fundamental Theorem of Linear Algebra 616
A.4.8 Projection and Least Squares 621
A.4.9 Linear Transformations 624
A.5 Advanced Topics 634
A.5.1 Determinants 634
A.5.2 Eigenvalues and Eigenvectors 646
A.5.3 Eigendecomposition for Symmetric Matrices 652
A.5.4 S + N Decomposition 655
A.5.5 Applications 661
Appendix B Affine Algebra 669
B.1 Introduction 669
B.2 Coordinate Systems 673
B.3 Subspaces 675
B.4 Transformations 676
B.5 Barycentric Coordinates 677
B.5.1 Triangles 678
B.5.2 Tetrahedra 679
B.5.3 Simplices 680
B.5.4 Length, Area, Volume, and Hypervolume 681
Appendix C Calculus 691
C.1 Univariate Calculus 692
C.1.1 Limits 694
C.1.2 Limits of a Sequence 696
C.1.3 Continuity 697
C.1.4 Differentiation 698
C.1.5 L'H^ opital's Rule 701
C.1.6 Integration 701
C.2 Multivariate Calculus 704
C.2.1 Limits and Continuity 704
C.2.2 Differentiation 705
C.2.3 Integration 708
C.3 Applications 710
C.3.1 Optimization 711
C.3.2 Constrained Optimization 715
C.3.3 Derivative Approximations by Finite Differences 718
Appendix D Ordinary Difference Equations 727
D.1 Definitions 727
D.2 Linear Equations 730
D.2.1 First-Order Linear Equations 730
D.2.2 Second-Order Linear Equations 731
D.3 Constant-Coefficient Equations 734
D.4 Systems of Equations 736
References 739
Index 745
List of Figures
2.1 A couple of coordinate systems at points on a curve. 16
2.2 A polar coordinate frame at a point on a curve. 18
2.3 A curve, a tangent vector at a point, and the circle of choices for the
normal vector. The circle lies in the plane containing the point and
perpendicular to the tangent. 20
2.4 Cylindrical coordinates (x, y, z) = (r cos è , r sin è , z). 23
2.5 Spherical coordinates (x, y, z)=(ñ cos è sin ö, r sin è sin ö, ñ cos ö). 24
2.6 Motion of a particle about a fixed axis, a constant distance from the
axis. 25
2.7 (a) The body coordinate system as seen by the body observer. (b) The
body coordinate system as seen by the world observer. 29
2.8 Gravitational forces on objects located at various places around the
Earth. 33
2.9 Gravitational forces on objects located nearly on the Earth's surface,
viewed as a flat surface. 34
2.10 (a) Unstretched spring. (b) Force due to stretching the spring. (c)
Force due to compressing the string. 35
2.11 A block in contact with an inclined plane. (a) Static friction is
dominant and the block remains at rest. (b) Gravity is dominant and
the block slides, so kinetic friction applies. 36
2.12 Torque from a force exerted on a particle. 37
2.13 A force couple. 38
2.14 (a) All forces applied to a point mass are concurrent but are not
"balanced," so the point moves. (b) All forces are concurrent
but do balance, so the point does not move. (c) A rigid rod with
nonconcurrent forces applied to the end points. The forces are equal
in magnitude but opposite in direction. The rod rotates about its
center. (d) Nonconcurrent forces are applied to three locations; two
forces of equal magnitudes and directions at the end points and one
force of twice the magnitude of an end-point force but opposite in
direction applied to the rod center. The rod is "balanced" and does
not rotate about its center. 39
2.15 Balancing discrete masses on a line. The center of mass for two masses
viewed as the balance point for a seesaw on a fulcrum. 44
2.16 Balancing continuous masses on a line. The center of mass for the
wire is viewed as the balance point for a seesaw on a fulcrum. A
general point location x is shown, labeled with its corresponding mass
density ä(x). 46
2.17 Balancing discrete masses in a plane. 47
2.18 Balancing discrete masses in a plane on a fulcrum. 48
2.19 Balancing continuous masses in a plane. The shades of gray indicate
variable mass density. 48
2.20 A continuous mass bounded by a parabola and a line. 49
2.21 A continuous mass in the shape of a hemicircle. 51
2.22 A force applied to a particle traveling on a straight line from position
x0 to x1. 79
3.1 The infinitesimal area dA swept out by motion of the Earth over an
infinitesimal change in position dr. The swept region is effectively a
triangle whose sides are r and r + dr. 90
3.2 The Foucault pendulum. The pendulum joint is at O, the mass is m
and is attached to the pendulum rod of length L. The gravitational
force acts in the direction k, a unit-length vector from the joint to the
center of the Earth. 94
3.3 The Foucault pendulum. The figures show the path of the pendulum
tip in the horizontal plane. New points on the path are colored
white, but the intensity of the older points along the path gradually
decreases. (See also Color Plate 3.3.) 97
3.4 The simple pendulum. The motion is constrained to a plane. The
mass is located at position X(t) at time t and is always a fixed length
L from the joint P. The angle formed by the pendulum rod with the
vertical is è(t). The curve of motion is a circle with tangent T(t) and
outward pointing normal N(t). The only force acting on the mass
is gravitational, -mgÆr, where m is the mass of the particle, g is the
gravitational constant, and -Ær is the direction of the force (vertically
downward). The joint P provides no frictional force. 101
3.5 A ball of mass m on a flat table. A rubber band connects the ball to a
fixed point on the table. The force F due to the rubber band is shown.
The position x of the ball is shown together with its velocity ÿx. 107
3.6 A ball is at the top of a frictionless hill.With a small push, the ball will
slide down the hill. 108
3.7 A ball rolling down a hill. Image (b) shows the path of the center of the
ball as it rolls down the hill. The ball rotates at a speed commensurate
with its downhill velocity. (See also Color Plate 3.7.) 110
3.8 (a) A metal chute of length L, one end attached to the origin, the
other end raised by a height H. (b) Side view of the chute. 112
3.9 The initial configuration of a rigid rod containing a mass that is
attached to a spring. 117
3.10 Three masses aligned vertically and subject to gravitational force. 119
3.11 A modification of the simple pendulum problem. 121
3.12 A triangle pendulum. 124
3.13 A system consisting of two masses, a pulley with mass, and a spring. 126
3.14 A mass pulley spring system shown at two different times. The spring
expands and compresses, and the pulley disk rotates during the
simulation. The system stops when a mass reaches the center line of
the pulley or the ground. (See also Color Plate 3.14.) 128
3.15 A system of two pulleys, two springs, and a mass. 129
3.16 A physical system with a bent pipe rotating about the z-axis and a disk
rotating about its axis. 130
3.17 A solid disk that rolls on a rough, inclined plane. 132
3.18 A simple diving board. 133
3.19 An inclined plane that forms an angle ö with the horizontal. The
particle has mass m. It is located at r0 = (x0, y0, z0); hash marks
are shown on the axes corresponding to x0, y0, z0, and w0, where
y0 = w0 cos ö and z0 = w0 sin ö. 142
3.20 Two particles, connected by a massless rod, that slide along a rough
plane. 143
3.21 A flat board on a rough plane. 149
3.22 A side view of a solid box on a rough, inclined plane. 151
3.23 The world coordinates and body coordinates for a rigid body where
both systems have the same origin. 153
3.24 A freely spinning top with tip fixed at the origin of the world
coordinate system. 155
3.25 Two "snapshots" of a freely spinning top. The black line is the vertical
axis. The white line is the axis of the top. (See also Color Plate 3.25.) 159
4.1 Two curve mass objects represented as mass-spring systems. 164
4.2 A rope modeled as a linear chain of springs. Image (a) shows the rope
at rest with only gravity acting on it. Image (b) shows the rope subject
to a wind force whose direction changes by small random amounts.
(See also Color Plate 4.2.) 167
4.3 A surface mass represented as a mass-spring system with the masses
organized as a two-dimensional array. 168
4.4 A cloth modeled as a rectangular array of springs. Wind forces make
the cloth flap about. Notice that the cloth in image (b) is stretched in
the vertical direction. The stretching occurs while the gravitational
and spring forces balance out in the vertical direction during the
initial portion of the simulation. (See also Color Plate 4.4.) 169
4.5 A volume mass represented as a mass-spring system with the masses
organized as a three-dimensional array. Only the masses and springs
on the three visible faces are shown. The other connections are shown,
but without their springs. 170
4.6 A gelatinous cube that is oscillating due to random forces. The cube is
modeled by a three-dimensional array of mass connected by springs.
(See also Color Plate 4.6.) 172
4.7 A gelatinous blob that is oscillating due to small, random forces. This
blob has the masses located at the vertices of an icosahedron with
additional masses of infinite weight to help stabilize the oscillations.
The springs connecting the blob to the infinite masses are shown in
white. (See also Color Plate 4.7.) 174
4.8 Six pairs of B-spline curves of various types. The right image of each
pair shows the deformed curve by modifying one control point. 182
4.9 The initial control points and curve are shown at the top of the figure.
The evolved control points and curve are shown at three later times,
with time increasing from top to bottom in the figure. 185
4.10 The control points and curve at later times in the evolution. 186
4.11 Deformation of a line segment into a closed curve that splits away
from the original curve. 187
4.12 (a) The decomposition of (u, v) space into an n x mgrid of rectangles,
each rectangle consisting of two triangles. A typical rectangle is shown
in (b), with lower corner index (i , j) corresponding to u = i/n and
v = j/m. 191
4.13 A cylinder surface (b) obtained by extruding the curve (a) in a
direction oblique to the plane of the curve. 192
4.14 A generalized cylinder surface obtained by linearly interpolating pairs
of points on two curves. 193
4.15 A skirt modeled by a generalized cylinder surface. Wind-like forces
are acting on the skirt and are applied in the radial direction. Image
(a) shows the skirt after wind is blowing it about. Image (b) shows a
wireframe view of the skirt so that you can see it consists of two closed
curve boundaries and is tessellated between. (See also Color Plate
4.15.) 194
4.16 A surface of revolution. 195
4.17 A water drop modeled as a control point surface of revolution.
The surface dynamically changes to show the water drop forming,
separating from the main body of water, then falling to the floor. The
evolution is from left to right and top to bottom. (See also Color Plate
4.17.) 196
4.18 A closed tube surface whose central axis is a helix. (See also Color
Plate 4.18.) 198
4.19 A wriggling snake modeled as a tube surface whose central curve is a
control point curve. (See also Color Plate 4.19.) 199
4.20 Free-form deformation. Image (a) shows the initial configuration
where all control points are rectangularly aligned. Image (b) shows
that some control points have been moved and the surface is
deformed. The control point shown in black in (b) is the point at
which the mouse was clicked on and moved. (See also Color Plate
4.20.) 204
4.21 A disk-shaped body and various deformations of it. 205
4.22 This is an illustration of a level surface F(x, y, z) = 0, a cube whose
eight corners correspond to image samples. Four of the image values
are shown, one positive and three negative. Assuming the image
values vary continuously, each edge connecting a positive and negative
value must have a point where the image is zero. The level surface
F(x, y, z) = 0 necessarily passes through those zero-points, as
illustrated by the triangular-shaped surface shaded in gray. 207
4.23 The 16 possible sign configurations for a pixel. 209
4.24 The three possible resolutions for the ambiguous pixel cases. 210
4.25 Two possible configurations for hyperbolic isocurves with pixels
superimposed. The four edge intersections are P0, P1, P2, and P3 as
marked. 211
4.26 Topological inconsistencies introduced in two voxels sharing an
ambiguous face. 214
4.27 A voxel and its extracted edge mesh. 216
4.28 Triangle removal in the edge mesh of Figure 4.27. 217
4.29 A bouncing ball with deformation based on implicit surfaces.
Image (a) shows the bouncing ball with only the implicit surface
deformation. Image (b) shows an additional deformation of
nonuniform scaling by applying an affine transformation. (See also
Color Plate 4.29.) 219
5.1 (a) Colliding contact. Body A moves into body B. (b) Resting contact.
Body A rests on body B and attempts neither to move into B nor to
separate from B. Body A is allowed to slide along B. (c) Separation.
Body A has a velocity that separates it from body B. 241
5.2 The reduced contact set for two convex polyhedra A and B. 242
5.3 The effects on p(t) as å approaches zero: (a) small å; (b) smaller å;
and (c) really small å (like zero). 244
5.4 (a) Reflection of the preimpulse velocity v- through the contact
normal to obtain the postimpulse velocity v+. (b) An imperfect
reflection that represents a loss of kinetic energy. (c) An imperfect
reflection that represents a maximum loss of kinetic energy. 246
5.5 (a) The square traveling toward a sloped plane. (b) The preimpulse
configuration at the instant of contact. (c) The postimpulse
configuration at the instant of contact. (d) The square moving away
from the plane. 249
5.6 An axis-aligned box colliding with a sloped plane along an entire edge
of the box, (1- s)P0 + sP1 for s ü, [0, 1]. 250
5.7 A rectangle travels downward and intersects two objects
simultaneously. 257
5.8 Four rigid bodies with six points of contact. The centers of mass of the
four bodies are also shown. 261
5.9 A book resting on a table. Forces applied to the book include only
gravitational (force vertically downward) and those used to push the
book around the table (force has only a horizontal component). 280
5.10 (a) Object at time t0. (b) Object at time t0 + _t/2. (c) Object at time
t0 + _t. 282
5.11 (a) A convex set. No matter which two points you choose in the set,
the line segment connecting them is in the set. (b) A nonconvex
set. The line segment connecting two specific points is not (fully)
contained in the set. 284
5.12 Nonintersecting convex objects and a separating line for them. The
algebraic condition for separation is ë(0)
max(D) < ë(1)
min(D) as indicated
in equation (5.47). 285
5.13 (a) Nonintersecting convex polygons. (b) Intersecting convex
polygons. 287
5.14 (a) Edge-edge contact. (b) Vertex-edge contact. (c) Vertex-vertex
contact. 287
5.15 Two polygons separated by an edge-normal direction of the first
polygon. 288
5.16 (a) A convex polygon. (b) A unit circle whose vertices correspond
to normal directions of the polygon and whose arcs connecting the
vertices correspond to vertices of the polygon (the polar dual of the
polygon). 293
5.17 A BSP tree constructed by recursive splitting of the unit disk. Each
node is labeled with the test used for the split. The subsectors
consisting of points satisfying the test are shaded in dark gray. The
leaf nodes are shaded in light gray and labeled with a vertex that is
extremal. 294
5.18 Two views of two cubes that are not separated by any face normal but
are separated by a cross product of two edges, one from each cube. 299
5.19 (a) A tetrahedron. (b) A unit sphere whose vertices correspond
to normal directions of the tetrahedron, whose great circle arcs
connecting the vertices correspond to edges of the tetrahedron, and
whose spherical polygons correspond to vertices of the tetrahedron
(the spherical dual of the tetrahedron). 304
5.20 The root of the BSP tree and the two hemispheres obtained by
splitting. Both children are displayed with a viewing direction
(0, 0, -1). The right child is the top of the sphere viewed from the
outside, and the left child is the bottom of the sphere viewed from the
inside. 305
5.21 The BSP trees for the children of the root. 306
5.22 (a) Edge-edge intersection predicted. (b) Vertex-vertex intersection
predicted. (c) No intersection predicted. 315
5.23 Edge-edge contact for two moving triangles. 321
5.24 An OBB with center point C, coordinate axis directions U0, U1, and
U2, and extents e0, e1, and e2 along the coordinate axes. The object
bounded by the box is shown in gray. 335
5.25 The projection intervals of two OBBs onto a line P + tD. (a) The
intervals are disjoint, so the OBBs are separated. (b) The intervals
overlap, so the line is not a separating axis. 336
5.26 Two projected intervals, one stationary and one moving. 346
5.27 Culling of bounding spheres against a view frustum. 349
5.28 Decomposition of space to reduce the number of comparisons
between pairs of objects. 351
5.29 The sweep phase of the algorithm. 355
5.30 The update phase of the algorithm when intervals have moved. 358
5.31 Axis-aligned rectangles overlap when both their x-intervals and
y-intervals overlap. 359
6.1 Two screen shots from the BasicShader application: (a) rendering
using just the pixel shader; (b) rendering using both the vertex shader
and the pixel shader. (See also Color Plate 6.1.) 376
6.2 Screen shots from the VertexNoise shader application. (a) Top
row: The original model and its wireframe view. Bottom row: The
output of the VertexNoise shader and its wireframe view. The
vertex displacement is significantly large. (b) Top row: The vertices
displaced with a smaller maximum displacement, but same scale of
noise. Bottom row: The vertices displaced with the same maximum
displacement as in the bottom row of (a), but with a larger scale noise.
(See also Color Plate 6.2.) 377
6.3 A skin-and-bones system consisting of two bones that influence five
vertices. The vertex closest to the joint formed by the two bones is
equally influenced by the bones. For each vertex farther from the
joint, one bone influences it more than the other bone. 378
6.4 Two screen shots from the skinning application. The bones are
randomly generated to cause the object to continuously deform. The
sequence of deformations is from left to right, then top to bottom.
(See also Color Plate 6.4.) 380
6.5 Two screen shots from the rippling ocean application. The images
were captured at two different times in the simulation. (See also Color
Plate 6.5.) 382
6.6 Reflection and refraction of a light beam traveling through two media. 383
6.7 Two screen shots from the refraction shader application. (a)
Refraction, but no reflection. (b) Refraction and reflection. (See also
Color Plate 6.7.) 385
6.8 Two screen shots from the Fresnel shader application. (See also Color
Plate 6.8.) 387
6.9 Screen shots from the iridescence shader application. The two images
show a textured torus in two different orientations and with various
amounts of interpolation to produce the iridescent sheen. (See also
Color Plate 6.9.) 389
7.1 (a) Various level curves f (x1, x2) = c (straight lines) superimposed
on the quadrilateral region implied by the constraints. (b) The graph
of x3 = f (x1, x2) (a plane) over the quadrilateral region. The x3 values
at four points on the plane are shown. 393
7.2 (a) Constraints with no solution. The hash marks indicate on which
side of the lines the half planes occur. (b) Constraints defining an
unbounded convex set. (c) Constraints defining a bounded convex
set. 393
7.3 (a) All five constraints are all relevant to forming the convex domain.
(b) Two of the six constraints are redundant since only four of the
constraints form the convex domain. 395
7.4 The convex domain implied by the two nonnegativity constraints and
three linear inequality constraints of the example. 398
7.5 Graph of f (u, v) = d/üauv in the first quadrant. 419
7.6 (a) The graph of a convex function. Any line segment connecting two
graph points is always above the graph. (b) The graph of a nonconvex
function. The line segment connecting two graph points is not always
above the graph. 420
7.7 The graph of a convex function f (x, y). 421
9.1 (a) Area under a curve. (b) Approximation of the area by a rectangle
(leads to Euler's method). (c) Approximation of the area by a
trapezoid (leads to the modified Euler's method). 463
9.2 The explicit Euler's method applied to the simple pendulum problem.
The image shows a plot of the pendulum angles over time. 494
9.3 The implicit Euler's method applied to the simple pendulum problem.
The image shows a plot of the pendulum angles over time. 496
9.4 The Runge-Kutta fourth-order method applied to the simple
pendulum problem. The image shows a plot of the pendulum angles
over time. 497
9.5 The leap frog method applied to the simple pendulum problem. The
image shows a plot of the pendulum angles over time. 499
9.6 The region of stability for the explicit Euler's method is shown in gray. 500
9.7 The region of stability for the implicit Euler's method is shown in
gray. 500
9.8 The region of stability for the Runge-Kutta fourth-order method is
shown in gray. 501
9.9 The region of stability for the leap frog method is shown as a heavy
black line and consists of a line segment on the imaginary axis. 502
9.10 (a) An approximation to x(t) using the Runge-Kutta fourth-order
method. (b) The graph of the actual solution x0e-ct . 504
10.1 A right-handed orthonormal set of vectors. A rotation is desired
about d by the angleè >0. 509
10.2 A 3D rotation about the z-axis that is represented as the product of
two 4D rotations. 519
10.3 P2D rotation. 523
10.4 3D rotation. 527
10.5 Convert any quaternion q to rotation matrix R. 537
10.6 Convert rotation matrix R to unit quaternion q. 537
10.7 Illustration of the spherical linear interpolation, or slerp, of two
vectors. 539
10.8 Four points forming a convex quadrilateral. Any interior point of
the quadrilateral can be generated using bilinear interpolation with
parameters s and t . The curve connecting v0 and v3 indicates that we
want a particular function s = f (t) with f (0) = f (1) = 0. 541
A.1 (a) Two nonparallel lines. (b) Two parallel and disjoint lines. (c) Two
coincident lines (shown in bold black). 559
A.2 (a) Two nonparallel planes. (b) Two parallel and disjoint planes. (c)
Two coincident planes (shown in bold black). 561
A.3 The coincident planes are shown in bold (black for visible portions,
gray for hidden portions). 562
A.4 A vector v at two locations in the plane. 583
A.5 Addition of u and v. 584
A.6 Addition of u, v, and w. Which pair of vectors is added first is
irrelevant. 584
A.7 Addition of u and v. The order of the vectors is irrelevant. 585
A.8 A vector v and its additive identity -v. 585
A.9 The vectors u and v and the difference u - v. 586
A.10 The vectors u and v, the parallelogram formed by them, and the sum
u + v and difference u - v shown as diagonals of the parallelogram. 586
A.11 The vector v and two scalar multiples of it, one positive and one
negative. 587
A.12 (a) Distributing across a scalar sum. (b) Distributing across a vector
sum. 587
A.13 (a) Two orthogonal vectors drawn in the plane spanned by them. (b)
Two nonorthogonal vectors and the angle between them. 602
A.14 The projection of vectors onto a unit-length vector u. (a) v projects
to Lu withL>0. The angle è between u and v is shown. The vector
w is obtained as w = v - Lu and is itself a projection. (b) v is
perpendicular to u, so the projection onto u is the zero vector 0. (c)
The projection is Lu withL<0. 603
A.15 Gram-Schmidt orthonormalization applied to two vectors in the
plane. 604
A.16 Gram-Schmidt orthonormalization applied to three vectors in space. 605
A.17 (a) The cross product of u and v according to the right-hand rule. (b)
The parallelogram formed by u and v with angle è and parallelogram
base length and height marked. 606
A.18 A parallelepiped formed by vectors u, v, and w, where u forms an
acute angle with v x w. The angle between v and w is è and the angle
between u and v x w is ö. 609
A.19 The triple vector product p = u x (v x w). Note that p must lie in the
plane spanned by v and w. 611
A.20 A subspace U of R3 and its orthogonal complement UüU. 614
A.21 The four fundamental subspaces. 620
A.22 The projection p ü, S of b ü, R3, where S is a two-dimensional
subspace of R3 (a plane through the origin). 621
A.23 A linear transformation from V to V with respect to two different
bases (horizontal arrows). The change of basis for V (vertical arrows). 631
A.24 (a) A unit-area square. (b) The parallelogram obtained by
transforming the square when the transformed basis vectors have the
same order as the basis vectors. (c) The parallelogram obtained by
transforming the square when the transformed basis vectors have the
opposite order as the basis vectors. (d) The basis vectors mapped to
parallel vectors, in which case A is not invertible. 635
A.25 An illustration of the butterfly rule for the determinant of a 3 x 3
matrix. 637
A.26 (a) A unit-volume cube. (b) The parallelepiped obtained by
transforming the cube when the transformed basis vectors have the
same order as the basis vectors. 638
A.27 Three graphs showing critical points. (a) f (x0) is a local maximum.
(b) f (x0) is a local minimum. (c) (x0, f (x0)) is a point of inflection
for the graph of f . 664
A.28 Three graphs showing critical points. (a) f (x0) is a local maximum.
(b) f (x0) is a local minimum. (c) (x0, f (x0)) is a saddle point on the
graph of f . The tangent planes at the graph points are shown in all
three figures. 667
B.1 (a) A vector v connecting two points P and Q. (b) The sum of vectors,
each vector determined by two points. 670
B.2 The parallelogram law for affine algebra. 671
B.3 Three coordinate systems in the plane. Observe that the vectors in the
coordinate system are not required to be unit length or perpendicular
in pairs. 674
B.4 An illustration of condition 1 of the definition for affine
transformation. 676
B.5 Various barycentric combinations of two points P and Q. 678
B.6 The triangle partitions the plane into seven regions. The signs of c1,
c2, and c3 are listed as ordered triples. 679
B.7 (a) A triangle with base length b and height h marked. The area of the
triangle is bh/2. (b) A triangle viewed as a union of an infinite number
of line segments of varying lengths (only a few are shown). The area
of the triangle is the sum of the lengths of those line segments. 682
B.8 A tetrahedron with base formed by P0, P1, and P2. A triangle slice
parallel to the base is shown. The direction perpendicular to the base
is marked as the positive z-axis. 684
C.1 The graph of f (x) = x2 + x for x near 1. 695
C.2 The graph of a function that is discontinuous at x = 0. 698
C.3 The graph of x(t) = t (1- t) with two points marked at times t1 and
t2. The lines connecting the origin (0, 0) to (t1, x(t1)) and (t2, x(t2))
are secant lines to the graph. The line at the left is the tangent line to
the graph at (0, x(0)) = (0, 0). 699
C.4 An attempt to compute the area bounded by a parabola and the x-axis
by filling it with rectangles. 702
C.5 Bases of some rectangular solids as an attempt to fill the domain D. 709
C.6 The graph of a function f (x) on its domain [a, b]. 711
Color Plates
3.3 The Foucault pendulum.
3.7 A ball rolling down a hill.
3.14 A mass pulley spring system shown at two different times.
3.25 Two "snapshots" of a freely spinning top.
4.2 A rope modeled as a linear chain of springs.
4.4 A cloth modeled as a rectangular array of springs.
4.6 A gelatinous cube that is oscillating due to random forces.
4.7 A gelatinous blob that is oscillating due to small, random forces.
4.15 A skirt modeled by a generalized cylinder surface.
4.17 A water drop modeled as a control point surface of revolution.
4.18 A closed tube surface whose central axis is a helix.
4.19 A wriggling snake modeled as a tube surface whose central curve is a
control point curve.
4.20 Free-form deformation.
4.29 A bouncing ball with deformation based on implicit surfaces.
6.1 Two screen shots from the basic shader application.
6.2 Screen shots from the vertex noise shader application.
6.4 Two screen shots from the skinning application.
6.5 Two screen shots from the rippling ocean application.
6.7 Two screen shots from the refraction shader application.
6.8 Two screen shots from the Fresnel shader application.
6.9 Screen shots from the iridescence shader application.
List of Tables
2.1 Moments and Products of Inertia for Vertices 63
2.2 Moments and Products of Inertia for Edges 64
2.3 Moments and Products of Inertia for Faces 65
2.4 Generation of Polynomials by Vector Fields 68
4.1 Recursive dependencies for B-spline basis functions for n = 4 and
d = 2 177
4.2 Nonzero values (boxed) from Table 4.1 N3, 0(u) = 1 178
4.3 Knot vectors and parameter intervals affected by modifying the
control point 183
4.4 The vertex-edge configurations for a pixel 213
5.1 Potential separating directions for OBBs and values for r0, r1, and r 338
7.1 Solving all possible systems of two equations in two unknowns 394
7.2 Tableau of coefficients and constants (Example 7.1) 399
7.3 Updated tableau: Exchanging w2 with x2 400
7.4 Updated tableau: Exchanging x1 with w3 401
7.5 Updated tableau: Exchanging w1 with s1 401
7.6 Maximizing f 402
7.7 Maximizing f : Exchanging s1 with s2 403
9.1 The actual and approximate values for the solution to the system of
equations 505
C.1 Average speed calculation on intervals [0, _t]with decreasing _t 693
C.2 Function values for x near c 694
C.3 Derivatives of some common functions 700
C.4 Parameters for various finite difference approximations 721




Library of Congress Subject Headings for this publication: Computer games Programming, Physics Data processing