Interactive Computer Graphics

Edward Angel is a professor of computer science, electrical and computer engineering, and media arts at the University of New Mexico. He holds a PhD from the University of Southern California and a BS in engineering from the California Institute of Technology. He is also the director of Art, Research, Technology, and Science Laboratory (ARTS Lab) and the Arts Technology Center at the University of New Mexico. He is the author of Interactive Computer Graphics and OpenGL: A Primer. Dave Shreiner is a computer graphics specialist at ARM, Inc. He's been working with OpenGL since its inception at Silicon Graphics Computer Systems (SGI). During his 15-year tenure at SGI, he authored the first commercial OpenGL training course, co-authored the OpenGL programming guide and reference manuals, and engineered OpenGL drivers for a multitude of different systems. Dave's been working in the computer graphics industry for the past two decades, where he's authored applications for flight simulators, scientific visualization, production animation, and numerous other disciplines. Also passionate about educating programmers about OpenGL and computer graphics, he's presented lectures and short courses at conference world wide, including SIGGRAPH and the Games Developer Conference.

Preface xxi

CHAPTER 1 GRAPHICS SYSTEMS AND MODELS 1

1.1 Applications of Computer Graphics 2

1.1.1 Display of Information 2

1.1.2 Design 3

1.1.3 Simulation and Animation 3

1.1.4 User Interfaces 4

1.2 A Graphics System 5

1.2.1 Pixels and the Frame Buffer 5

1.2.2 The CPU and the GPU 6

1.2.3 Output Devices 7

1.2.4 Input Devices 9

1.2.5 Physical Input Devices 10

1.2.6 Logical Devices 12

1.2.7 Input Modes 13

1.3 Images: Physical and Synthetic 15

1.3.1 Objects and Viewers 15

1.3.2 Light and Images 16

1.3.3 Imaging Models 18

1.4 Imaging Systems 20

1.4.1 The Pinhole Camera 20

1.4.2 The Human Visual System 22

1.5 The Synthetic-Camera Model 23

1.6 The Programmer’s Interface 25

1.6.1 The Pen-Plotter Model 27

1.6.2 Three-Dimensional APIs 28

1.6.3 A Sequence of Images 31

1.6.4 The Modeling—Rendering Paradigm 32

1.7 Graphics Architectures 33

1.7.1 Display Processors 34

1.7.2 Pipeline Architectures 34

1.7.3 The Graphics Pipeline 35

1.7.4 Vertex Processing 36

1.7.5 Clipping and Primitive Assembly 36

1.7.6 Rasterization 37

1.7.7 Fragment Processing 37

1.8 Programmable Pipelines 37

1.9 Performance Characteristics 38

Summary and Notes 39

Suggested Readings 40

Exercises 41

CHAPTER 2 GRAPHICS PROGRAMMING 43

2.1 The Sierpinski Gasket 43

2.2 Programming Two-Dimensional Applications 46

2.3 The OpenGL Application Programming Interface 50

2.3.1 Graphics Functions 51

2.3.2 The Graphics Pipeline and State Machines 53

2.3.3 The OpenGL Interface 53

2.3.4 Coordinate Systems 55

2.4 Primitives and Attributes 56

2.4.1 Polygon Basics 58

2.4.2 Polygons in OpenGL 59

2.4.3 Approximating a Sphere 60

2.4.4 Triangulation 62

2.4.5 Text 64

2.4.6 Curved Objects 65

2.4.7 Attributes 65

2.5 Color 67

2.5.1 RGB Color 69

2.5.2 Indexed Color 71

2.5.3 Setting of Color Attributes 72

2.6 Viewing 73

2.6.1 The Orthographic View 74

2.6.2 Two-Dimensional Viewing 77

2.7 Control Functions 78

2.7.1 Interaction with the Window System 78

2.7.2 Aspect Ratio and Viewports 79

2.7.3 The main, display, and init Functions 80

2.7.4 Program Structure 83

2.8 The Gasket Program 83

2.8.1 Rendering the Points 84

2.8.2 The Vertex Shader 85

2.8.3 The Fragment Shader 86

2.8.4 Combining the Parts 86

2.8.5 The initShader Function 86

2.9 Polygons and Recursion 88

2.10 The Three-Dimensional Gasket 91

2.10.1 Use of Three-Dimensional Points 91

2.10.2 Use of Polygons in Three Dimensions 92

2.10.3 Hidden-Surface Removal 96

2.11 Adding Interaction 98

2.11.1 Using the Pointing Device 98

2.11.2 Window Events 101

2.11.3 Keyboard Events 102

2.11.4 The Idle Callback 103

2.11.5 Double Buffering 105

2.11.6 Window Management 106

2.12 Menus 106

Summary and Notes 108

Suggested Readings 109

Exercises 110

CHAPTER 3 GEOMETRIC OBJECTS AND TRANSFORMATIONS 115

3.1 Scalars, Points, and Vectors 116

3.1.1 Geometric Objects 116

3.1.2 Coordinate-Free Geometry 117

3.1.3 The Mathematical View: Vector and Affine Spaces 118

3.1.4 The Computer Science View 119

3.1.5 Geometric ADTs 119

3.1.6 Lines 120

3.1.7 Affine Sums 121

3.1.8 Convexity 122

3.1.9 Dot and Cross Products 122

3.1.10 Planes 123

3.2 Three-Dimensional Primitives 125

3.3 Coordinate Systems and Frames 126

3.3.1 Representations and N-Tuples 128

3.3.2 Change of Coordinate Systems 129

3.3.3 Example Change of Representation 132

3.3.4 Homogeneous Coordinates 133

3.3.5 Example Change in Frames 136

3.3.6 Working with Representations 137

3.4 Frames in OpenGL 139

3.5 Matrix and Vector Classes 144

3.6 Modeling a Colored Cube 146

3.6.1 Modeling the Faces 146

3.6.2 Inward- and Outward-Pointing Faces 146

3.6.3 Data Structures for Object Representation 147

3.6.4 The Color Cube 148

3.6.5 Interpolation 150

3.6.6 Displaying the Cube 151

3.7 Affine Transformations 152

3.8 Translation, Rotation, and Scaling 155

3.8.1 Translation 155

3.8.2 Rotation 156

3.8.3 Scaling 158

3.9 Transformations in Homogeneous Coordinates 159

3.9.1 Translation 160

3.9.2 Scaling 161

3.9.3 Rotation 162

3.9.4 Shear 163

3.10 Concatenation of Transformations 164

3.10.1 Rotation About a Fixed Point 165

3.10.2 General Rotation 167

3.10.3 The Instance Transformation 168

3.10.4 Rotation About an Arbitrary Axis 169

3.11 Transformation Matrices in OpenGL 172

3.11.1 Current Transformation Matrices 173

3.11.2 Rotation, Translation, and Scaling 174

3.11.3 Rotation About a Fixed Point 175

3.11.4 Order of Transformations 176

3.12 Spinning of the Cube 176

3.12.1 Updating in the Display Callback 177

3.12.2 Uniform Variables 178

3.13 Interfaces to Three-Dimensional Applications 180

3.13.1 Using Areas of the Screen 180

3.13.2 A Virtual Trackball 181

3.13.3 Smooth Rotations 184

3.13.4 Incremental Rotation 185

3.14 Quaternions 186

3.14.1 Complex Numbers and Quaternions 186

3.14.2 Quaternions and Rotation 187

Summary and Notes 190

Suggested Readings 190

Exercises 191

CHAPTER 4 VIEWING 195

4.1 Classical and Computer Viewing 195

4.1.1 Classical Viewing 197

4.1.2 Orthographic Projections 197

4.1.3 Axonometric Projections 198

4.1.4 Oblique Projections 200

4.1.5 Perspective Viewing 201

4.2 Viewing with a Computer 202

4.3 Positioning of the Camera 204

4.3.1 Positioning of the Camera Frame 204

4.3.2 Two Viewing APIs 209

4.3.3 The Look-At Function 212

4.3.4 Other Viewing APIs 214

4.4 Parallel Projections 215

4.4.1 Orthogonal Projections 215

4.4.2 Parallel Viewing with OpenGL 216

4.4.3 Projection Normalization 217

4.4.4 Orthogonal-Projection Matrices 219

4.4.5 Oblique Projections 220

4.4.6 An Interactive Viewer 224

4.5 Perspective Projections 226

4.5.1 Simple Perspective Projections 226

4.6 Perspective Projections with OpenGL 229

4.6.1 Perspective Functions 230

4.7 Perspective-Projection Matrices 232

4.7.1 Perspective Normalization 232

4.7.2 OpenGL Perspective Transformations 236

4.7.3 Perspective Example 238

4.8 Hidden-Surface Removal 238

4.8.1 Culling 241

4.9 Displaying Meshes 241

4.9.1 Displaying Meshes as a Surface 244

4.9.2 Polygon Offset 246

4.9.3 Walking Through a Scene 247

4.10 Projections and Shadows 249

Summary and Notes 253

Suggested Readings 254

Exercises 254

CHAPTER 5 LIGHTING AND SHADING 257

5.1 Light and Matter 258

5.2 Light Sources 261

5.2.1 Color Sources 262

5.2.2 Ambient Light 262

5.2.3 Point Sources 263

5.2.4 Spotlights 264

5.2.5 Distant Light Sources 264

5.3 The Phong Reflection Model 265

5.3.1 Ambient Reflection 267

5.3.2 Diffuse Reflection 267

5.3.3 Specular Reflection 269

5.3.4 The Modified Phong Model 270

5.4 Computation of Vectors 271

5.4.1 Normal Vectors 272

5.4.2 Angle of Reflection 274

5.5 Polygonal Shading 275

5.5.1 Flat Shading 276

5.5.2 Smooth and Gouraud Shading 277

5.5.3 Phong Shading 279

5.6 Approximation of a Sphere by Recursive Subdivision 280

5.7 Specifying Lighting Parameters 283

5.7.1 Light Sources 283

5.7.2 Materials 284

5.8 Implementing a Lighting Model 286

5.8.1 Applying the Lighting Model in the Application 286

5.8.2 Efficiency 289

5.8.3 Lighting in the Vertex Shader 290

5.9 Shading of the Sphere Model 294

5.10 Per-Fragment Lighting 295

5.10.1 Nonphotorealistic Shading 297

5.11 Global Illumination 297

Summary and Notes 299

Suggested Readings 300

Exercises 300

CHAPTER 6 FROM VERTICES TO FRAGMENTS 303

6.1 Basic Implementation Strategies 304

6.2 Four Major Tasks 306

6.2.1 Modeling 306

6.2.2 Geometry Processing 307

6.2.3 Rasterization 308

6.2.4 Fragment Processing 309

6.3 Clipping 310

6.4 Line-Segment Clipping 310

6.4.1 Cohen-Sutherland Clipping 310

6.4.2 Liang-Barsky Clipping 313

6.5 Polygon Clipping 314

6.6 Clipping of Other Primitives 317

6.6.1 Bounding Boxes and Volumes 318

6.6.2 Curves, Surfaces, and Text 319

6.6.3 Clipping in the Frame Buffer 319

6.7 Clipping in Three Dimensions 319

6.8 Rasterization 323

6.9 Bresenham’s Algorithm 325

6.10 Polygon Rasterization 327

6.10.1 Inside—Outside Testing 327

6.10.2 OpenGL and Concave Polygons 329

6.10.3 Fill and Sort 329

6.10.4 Flood Fill 330

6.10.5 Singularities 330

6.11 Hidden-Surface Removal 331

6.11.1 Object-Space and Image-Space Approaches 331

6.11.2 Sorting and Hidden-Surface Removal 332

6.11.3 Scanline Algorithms 333

6.11.4 Back-Face Removal 334

6.11.5 The z-Buffer Algorithm 335

6.11.6 Scan Conversion with the z-Buffer 338

6.11.7 Depth Sort and the Painter’s Algorithm 340

6.12 Antialiasing 342

6.13 Display Considerations 344

6.13.1 Color Systems 345

6.13.2 The Color Matrix 348

6.13.3 Gamma Correction 349

6.13.4 Dithering and Halftoning 349

Summary and Notes 350

Suggested Readings 352

Exercises 352

CHAPTER 7 DISCRETE TECHNIQUES 357

7.1 Buffers 357

7.2 Digital Images 359

7.3 Writing into Buffers 362

7.3.1 Writing Modes 363

7.3.2 Writing with XOR 365

7.4 Mapping Methods 366

7.5 Texture Mapping 368

7.5.1 Two-Dimensional Texture Mapping 368

7.6 Texture Mapping in OpenGL 374

7.6.1 Two-Dimensional Texture Mapping 375

7.6.2 Texture Objects 375

7.6.3 The Texture Array 376

7.6.4 Texture Coordinates and Samplers 376

7.6.5 Texture Sampling 382

7.6.6 Working with Texture Coordinates 384

7.6.7 Multitexturing 386

7.7 Texture Generation 387

7.8 Environment Maps 388

7.9 Reflection Map Example 393

7.10 Bump Mapping 396

7.10.1 Finding Bump Maps 397

7.10.2 Bump Map Example 400

7.11 Compositing Techniques 404

7.11.1 Opacity and Blending 404

7.11.2 Image Compositing 406

7.11.3 Blending and Compositing in OpenGL 406

7.11.4 Antialiasing Revisited 407

7.11.5 Back-to-Front and Front-to-Back Rendering 409

7.11.6 Scene Antialiasing and Multisampling 410

7.11.7 Image Processing 411

7.11.8 Other Multipass Methods 412

7.12 Sampling and Aliasing 413

7.12.1 Sampling Theory 413

7.12.2 Reconstruction 418

7.12.3 Quantization 420

Summary and Notes 421

Suggested Readings 422

Exercises 422

CHAPTER 8 MODELING AND HIERARCHY 425

8.1 Symbols and Instances 426

8.2 Hierarchical Models 427

8.3 A Robot Arm 429

8.4 Trees and Traversal 432

8.4.1 A Stack-Based Traversal 434

8.5 Use of Tree Data Structures 437

8.6 Animation 441

8.7 Graphical Objects 443

8.7.1 Methods, Attributes, and Messages 443

8.7.2 A Cube Object 445

8.7.3 Implementing the Cube Object 447

8.7.4 Objects and Hierarchy 447

8.7.5 Geometric Objects 448

8.8 Scene Graphs 449

8.9 Open Scene Graph 451

8.10 Graphics and the Internet 453

8.10.1 Hypermedia and HTML 453

8.10.2 Java and Applets 454

8.10.3 Interactive Graphics and the Web 454

8.10.4 WebGL 455

8.11 Other Tree Structures 455

8.11.1 CSG Trees 455

8.11.2 BSP Trees 457

8.11.3 Quadtrees and Octrees 459

Summary and Notes 461

Suggested Readings 461

Exercises 462

CHAPTER 9 PROCEDURAL METHODS 465

9.1 Algorithmic Models 465

9.2 Physically Based Models and Particle Systems 467

9.3 Newtonian Particles 468

9.3.1 Independent Particles 470

9.3.2 Spring Forces 471

9.3.3 Attractive and Repulsive Forces 472

9.4 Solving Particle Systems 473

9.5 Constraints 476

9.5.1 Collisions 476

9.5.2 Soft Constraints 479

9.6 A Simple Particle System 480

9.6.1 Displaying the Particles 480

9.6.2 Updating Particle Positions 481

9.6.3 Collisions 482

9.6.4 Forces 483

9.6.5 Flocking 483

9.7 Language-Based Models 484

9.8 Recursive Methods and Fractals 487

9.8.1 Rulers and Length 488

9.8.2 Fractal Dimension 489

9.8.3 Midpoint Division and Brownian Motion 490

9.8.4 Fractal Mountains 492

9.8.5 The Mandelbrot Set 493

9.9 Procedural Noise 496

Summary and Notes 500

Suggested Readings 501

Exercises 501

CHAPTER 10 CURVES AND SURFACES 503

10.1 Representation of Curves and Surfaces 503

10.1.1 Explicit Representation 503

10.1.2 Implicit Representations 505

10.1.3 Parametric Form 506

10.1.4 Parametric Polynomial Curves 507

10.1.5 Parametric Polynomial Surfaces 508

10.2 Design Criteria 509

10.3 Parametric Cubic Polynomial Curves 510

10.4 Interpolation 511

10.4.1 Blending Functions 513

10.4.2 The Cubic Interpolating Patch 515

10.5 Hermite Curves and Surfaces 517

10.5.1 The Hermite Form 517

10.5.2 Geometric and Parametric Continuity 519

10.6 Bézier Curves and Surfaces 520

10.6.1 Bézier Curves 521

10.6.2 Bézier Surface Patches 523

10.7 Cubic B-Splines 524

10.7.1 The Cubic B-Spline Curve 525

10.7.2 B-Splines and Basis 528

10.7.3 Spline Surfaces 528

10.8 General B-Splines 529

10.8.1 Recursively Defined B-Splines 530

10.8.2 Uniform Splines 532

10.8.3 Nonuniform B-Splines 532

10.8.4 NURBS 532

10.8.5 Catmull-Rom Splines 534

10.9 Rendering Curves and Surfaces 535

10.9.1 Polynomial Evaluation Methods 536

10.9.2 Recursive Subdivision of Bézier Polynomials 537

10.9.3 Rendering Other Polynomial Curves by Subdivision 540

10.9.4 Subdivision of Bézier Surfaces 541

10.10 The Utah Teapot 542

10.11 Algebraic Surfaces 545

10.11.1 Quadrics 545

10.11.2 Rendering of Surfaces by Ray Casting 546

10.12 Subdivision Curves and Surfaces 546

10.12.1 Mesh Subdivision 547

10.13 Mesh Generation from Data 550

10.13.1 Height Fields Revisited 551

10.13.2 Delaunay Triangulation 551

10.13.3 Point Clouds 555

Summary and Notes 556

Suggested Readings 556

Exercises 557

CHAPTER 11 ADVANCED RENDERING 559

11.1 Going Beyond Pipeline Rendering 559

11.2 Ray Tracing 560

11.3 Building a Simple Ray Tracer 564

11.3.1 Recursive Ray Tracing 564

11.3.2 Calculating Intersections 566

11.3.3 Ray-Tracing Variations 568

11.4 The Rendering Equation 569

11.5 Radiosity 571

11.5.1 The Radiosity Equation 572

11.5.2 Solving the Radiosity Equation 574

11.5.3 Computing Form Factors 575

11.5.4 Carrying Out Radiosity 577

11.6 RenderMan 578

11.7 Parallel Rendering 579

11.7.1 Sort-Middle Rendering 581

11.7.2 Sort-Last Rendering 583

11.7.3 Sort-First Rendering 586

11.8 Volume Rendering 588

11.8.1 Volumetric Data Sets 588

11.8.2 Visualization of Implicit Functions 589

11.9 Isosurfaces and Marching Cubes 591

11.10 Mesh Simplification 594

11.11 Direct Volume Rendering 595

11.11.1 Assignment of Color and Opacity 596

11.11.2 Splatting 596

11.11.3 Volume Ray Tracing 598

11.11.4 Texture Mapping of Volumes 599

11.12 Image-Based Rendering 600

11.12.1 A Simple Example 600

Summary and Notes 602

Suggested Readings 603

Exercises 604

APPENDIX A SAMPLE PROGRAMS 607

A.1 Shader Initialization Function 608

A.1.1 Application Code 608

A.2 Sierpinski Gasket Program 610

A.2.1 Application Code 610

A.2.2 Vertex Shader 612

A.2.3 Fragment Shader 612

A.3 Recursive Generation of Sierpinski Gasket 613

A.3.1 Application Code 613

A.3.2 Vertex Shader 615

A.3.3 Fragment Shader 615

A.4 Rotating Cube with Rotation in Shader 615

A.4.1 Application Code 615

A.4.2 Vertex Shader 620

A.4.3 Fragment Shader 620

A.5 Perspective Projection 621

A.5.1 Application Code 621

A.5.2 Vertex Shader 625

A.5.3 Fragment Shader 626

A.6 Rotating Shaded Cube 626

A.6.1 Application Code 626

A.6.2 Vertex Shader 631

A.6.3 Fragment Shader 632

A.7 Per-Fragment Lighting of Sphere Model 632

A.7.1 Application Code 632

A.7.2 Vertex Shader 637

A.7.3 Fragment Shader 638

A.8 Rotating Cube with Texture 638

A.8.1 Application Code 638

A.8.2 Vertex Shader 644

A.8.3 Fragment Shader 645

A.9 Figure with Tree Traversal 646

A.9.1 Application Code 646

A.9.2 Vertex Shader 659

A.9.3 Fragment Shader 659

A.10 Teapot Renderer 659

A.10.1 Application Code 659

A.10.2 Vertex Shader 664

A.10.3 Fragment Shader 664

APPENDIX B SPACES 665

B.1 Scalars 665

B.2 Vector Spaces 666

B.3 Affine Spaces 668

B.4 Euclidean Spaces 669

B.5 Projections 670

B.6 Gram-Schmidt Orthogonalization 671

Suggested Readings 672

Exercises 672

APPENDIX C MATRICES 675

C.1 Definitions 675

C.2 Matrix Operations 676

C.3 Row and Column Matrices 677

C.4 Rank 678

C.5 Change of Representation 679

C.6 The Cross Product 681

C.7 Eigenvalues and Eigenvectors 682

C.8 Vector and Matrix Classes 683

Suggested Readings 684

Exercises 684

APPENDIX D SYNOPSIS OF OPENGL FUNCTIONS 687

D.1 Initialization and Window Functions 687

D.2 Vertex Buffer Objects 689

D.3 Interaction 690

D.4 Setting Attributes and Enabling Features 692

D.5 Texture and Image Functions 693

D.6 State and Buffer Manipulation 694

D.7 Query Functions 694

D.8 GLSL Functions 695

References 699

OpenGL Function Index 709

Subject Index 711