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.
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