Mathematical Structures for Computer Graphics

A comprehensive exploration of the mathematics behind the modeling and rendering of computer graphics scenes

Mathematical Structures for Computer Graphics presents an accessible and intuitive approach to the mathematical ideas and techniques necessary for two- and three-dimensional computer graphics. Focusing on the significant mathematical results, the book establishes key algorithms used to build complex graphics scenes.

• Numerous examples of two- and three-dimensional techniques along with numerical calculations
• Plenty of mathematical and programming exercises in each chapter, which are designed particularly for graphics tasks
• Additional details at the end of each chapter covering historical notes, further calculations, and connected concepts for readers who wish to delve deeper
• Unique coverage of topics such as calculations with homogeneous coordinates, computational geometry for polygons, use of barycentric coordinates, various descriptions for curves, and L-system techniques for recursive images

STEVEN J. JANKE, PhD, is Professor of Mathematics and Computer Science at Colorado College. He has over 20 years of teaching experience in the field of computer graphics and is the coauthor of Introduction to Linear Models and Statistical Inference, also published by Wiley.

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

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

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.