Mathematical Structures for Computer Graphics



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
viii CONTENTS
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
CONTENTS ix
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
x CONTENTS
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 Bézier Curves, 223
7.2.1 Properties for Two-Dimensional Bézier
Curves, 226
7.2.2 Joining Bézier Curve Segments, 228
7.2.3 Three-Dimensional Bézier Curves, 229
7.2.4 Rational Bézier 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 Bézier Curves, 260
7.6.2 Quadratic B-Spline Blending Functions, 262
7.7 Exercises, 264
7.7.1 Programming Exercises, 266
CONTENTS xi
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
xii CONTENTS
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