Preface xiii
1 Basics 1
1.1 Graphics Pipeline 2
1.2 Mathematical Descriptions 4
1.3 Position 5
1.4 Distance 8
1.5 Complements and Details 11
1.5.1 Pythagorean Theorem Continued 11
1.5.2 Law of Cosines Continued 12
1.5.3 Law of Sines 13
1.5.4 Numerical Calculations 13
1.6 Exercises 14
1.6.1 Programming Exercises 16
2 Vector Algebra 17
2.1 Basic Vector Characteristics 18
2.1.1 Points Versus Vectors 20
2.1.2 Addition 20
2.1.3 Scalar Multiplication 21
2.1.4 Subtraction 22
2.1.5 Vector Calculations 22
2.1.6 Properties 24
2.1.7 Higher Dimensions 25
2.2 Two Important Products 25
2.2.1 Dot Product 25
2.2.2 Cross Product 29
2.3 Complements and Details 34
2.3.1 Vector History 34
2.3.2 More about Points Versus Vectors 35
2.3.3 Vector Spaces and Affine Spaces 36
2.4 Exercises 38
2.4.1 Programming Exercises 39
3 Vector Geometry 40
3.1 Lines and Planes 40
3.1.1 Vector Description of Lines 40
3.1.2 Vector Description of Planes 44
3.2 Distances 46
3.2.1 Point to a Line 46
3.2.2 Point to a Plane 48
3.2.3 Parallel Planes and Line to a Plane 48
3.2.4 Line to a Line 50
3.3 Angles 52
3.4 Intersections 54
3.4.1 Intersecting Lines 54
3.4.2 Lines Intersecting Planes 56
3.4.3 Intersecting Planes 57
3.5 Additional Key Applications 61
3.5.1 Intersection of Line Segments 61
3.5.2 Intersection of Line and Sphere 65
3.5.3 Areas and Volumes 66
3.5.4 Triangle Geometry 68
3.5.5 Tetrahedron 69
3.6 Homogeneous Coordinates 71
3.6.1 Two Dimensions 72
3.6.2 Three Dimensions 73
3.7 Complements and Details 75
3.7.1 Intersection of Three Planes Continued 75
3.7.2 Homogeneous Coordinates Continued 77
3.8 Exercises 79
3.8.1 Programming Exercises 82
4 Transformations 83
4.1 Types of Transformations 84
4.2 Linear Transformations 85
4.2.1 Rotation in Two Dimensions 88
4.2.2 Reflection in Two dimensions 90
4.2.3 Scaling in Two Dimensions 92
4.2.4 Matrix Properties 93
4.3 Three Dimensions 95
4.3.1 Rotations in Three Dimensions 95
4.3.2 Reflections in Three Dimensions 101
4.3.3 Scaling and Shear in Three Dimensions 102
4.4 Affine Transformations 103
4.4.1 Transforming Homogeneous Coordinates 105
4.4.2 Perspective Transformations 107
4.4.3 Transforming Normals 110
4.4.4 Summary 111
4.5 Complements and Details 112
4.5.1 Vector Approach to Reflection in an Arbitrary Plane 113
4.5.2 Vector Approach to Arbitrary Rotations 115
4.6 Exercises 121
4.6.1 Programming Exercises 123
5 Orientation 124
5.1 Cartesian Coordinate Systems 125
5.2 Cameras 132
5.2.1 Moving the Camera or Objects 134
5.2.2 Euler Angles 137
5.2.3 Quaternions 141
5.2.4 Quaternion Algebra 143
5.2.5 Rotations 145
5.2.6 Interpolation: Slerp 148
5.2.7 From Euler Angles and Quaternions to Rotation Matrices 151
5.3 Other Coordinate Systems 152
5.3.1 Non-orthogonal Axes 152
5.3.2 Polar, Cylindrical, and Spherical Coordinates 154
5.3.3 Barycentric Coordinates 157
5.4 Complements and Details 158
5.4.1 Historical Note: Descartes 158
5.4.2 Historical Note: Hamilton 158
5.4.3 Proof of Quaternion Rotation 159
5.5 Exercises 161
5.5.1 Programming Exercises 163
6 Polygons and Polyhedra 164
6.1 Triangles 164
6.1.1 Barycentric Coordinates 165
6.1.2 Areas and Barycentric Coordinates 166
6.1.3 Interpolation 171
6.1.4 Key Points in a Triangle 172
6.2 Polygons 178
6.2.1 Convexity 179
6.2.2 Angles and Area 180
6.2.3 Inside and Outside 184
6.2.4 Triangulation 187
6.2.5 Delaunay Triangulation 189
6.3 Polyhedra 192
6.3.1 Regular Polyhedra 194
6.3.2 Volume of Polyhedra 196
6.3.3 Euler's Formula 200
6.3.4 Rotational Symmetries 202
6.4 Complements and Details 205
6.4.1 Generalized Barycentric Coordinates 205
6.4.2 Data Structures 206
6.5 Exercises 208
6.5.1 Programming Exercises 211
7 Curves and Surfaces 212
7.1 Curve Descriptions 213
7.1.1 Lagrange Interpolation 218
7.1.2 Matrix Form for Curves 222
7.2 Bezier Curves 223
7.2.1 Properties for Two-Dimensional Bezier Curves 226
7.2.2 Joining Bezier Curve Segments 228
7.2.3 Three-Dimensional Bezier Curves 229
7.2.4 Rational Bezier Curves 230
7.3 B-Splines 232
7.3.1 Linear Uniform B-Splines 233
7.3.2 Quadratic Uniform B-Splines 235
7.3.3 Cubic Uniform B-Splines 240
7.3.4 B-Spline Properties 242
7.4 Nurbs 246
7.5 Surfaces 250
7.6 Complements and Details 260
7.6.1 Adding Control Points to Bezier Curves 260
7.6.2 Quadratic B-Spline Blending Functions 262
7.7 Exercises 264
7.7.1 Programming Exercises 266
8 Visibility 267
8.1 Viewing 267
8.2 Perspective Transformation 269
8.2.1 Clipping 273
8.2.2 Interpolating the z Coordinate 275
8.3 Hidden Surfaces 278
8.3.1 Back Face Culling 281
8.3.2 Painter's Algorithm 283
8.3.3 Z-Buffer 286
8.4 Ray Tracing 287
8.4.1 Bounding Volumes 289
8.4.2 Bounding Boxes 289
8.4.3 Bounding Spheres 291
8.5 Complements and Details 293
8.5.1 Frustum Planes 293
8.5.2 Axes for Bounding Volumes 294
8.6 Exercises 297
8.6.1 Programming Exercises 298
9 Lighting 299
9.1 Color Coordinates 299
9.2 Elementary Lighting Models 303
9.2.1 Gouraud and Phong Shading 307
9.2.2 Shadows 311
9.2.3 BRDFs in Lighting Models 315
9.3 Global Illumination 319
9.3.1 Ray Tracing 319
9.3.2 Radiosity 323
9.4 Textures 325
9.4.1 Mapping 325
9.4.2 Resolution 332
9.4.3 Procedural Textures 333
9.5 Complements and Details 335
9.5.1 Conversion between RGB and HSV 335
9.5.2 Shadows on Arbitrary Planes 336
9.5.3 Derivation of the Radiosity Equation 337
9.6 Exercises 339
9.6.1 Programming Exercises 340
10 Other Paradigms 341
10.1 Pixels 342
10.1.1 Bresenham Line Algorithm 342
10.1.2 Anti-Aliasing 345
10.1.3 Compositing 347
10.2 Noise 350
10.2.1 Random Number Generation 350
10.2.2 Distributions 351
10.2.3 Sequences of Random Numbers 353
10.2.4 Uniform and Normal Distributions 354
10.2.5 Terrain Generation 356
10.2.6 Noise Generation 357
10.3 L-Systems 361
10.3.1 Grammars 362
10.3.2 Turtle Interpretation 363
10.3.3 Analysis of Grammars 365
10.3.4 Extending L-Systems 367
10.4 Exercises 368
10.4.1 Programming Exercises 369
Appendix A Geometry and Trigonometry 370
A.1 Triangles 370
A.2 Angles 372
A.3 Trigonometric Functions 373
Appendix B Linear Algebra 376
B.1 Systems of Linear Equations 376
B.1.1 Solving the System 377
B.2 Matrix Properties 379
B.3 Vector Spaces 381
References 383
Index 387
