Interactive Computer Graphics: A Top-Down Approach with Shader-Based OpenGL

Computer animation and graphics are now prevalent in everyday life from the computer screen, to the movie screen, to the smart phone screen. The growing excitement about WebGL applications and their ability to integrate HTML5, inspired the authors to exclusively use WebGL in the Seventh Edition of Interactive Computer Graphics with WebGL. Thisis the only introduction to computer graphics text for undergraduates that fully integrates WebGL and emphasizes application-based programming. The top-down, programming-oriented approach allows for coverage of engaging 3D material early in the course so students immediately begin to create their own 3D graphics.

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 Framebuffer 5
1.2.2 The CPU and the GPU 6
1.2.3 Output Devices 7
1.2.4 Input Devices 9
1.3 Images: Physical and Synthetic 10
1.3.1 Objects and Viewers 10
1.3.2 Light and Images 12
1.3.3 Imaging Models 13
1.4 Imaging Systems 15
1.4.1 The Pinhole Camera 15
1.4.2 The Human Visual System 17
1.5 The Synthetic-Camera Model 18
1.6 The Programmer’s Interface 20
1.6.1 The Pen-Plotter Model 21
1.6.2 Three-Dimensional APIs 23
1.6.3 A Sequence of Images 26
1.6.4 The Modeling—Rendering Paradigm 27
1.7 Graphics Architectures 28
1.7.1 Display Processors 29
1.7.2 Pipeline Architectures 29
1.7.3 The Graphics Pipeline 30
1.7.4 Vertex Processing 31
1.7.5 Clipping and Primitive Assembly 31
1.7.6 Rasterization 32
1.7.7 Fragment Processing 32
1.8 Programmable Pipelines 32
1.9 Performance Characteristics 33
1.10 OpenGL Versions and WebGL 34
Summary and Notes 36
Suggested Readings 36
Exercises 37
CHAPTER 2 GRAPHICS PROGRAMMING 39
2.1 The Sierpinski Gasket 39
2.2 Programming Two-Dimensional Applications 42
2.3 The WebGL Application Programming Interface 47
2.3.1 Graphics Functions 47
2.3.2 The Graphics Pipeline and State Machines 49
2.3.3 OpenGL and WebGL 50
2.3.4 The WebGL Interface 50
2.3.5 Coordinate Systems 51
2.4 Primitives and Attributes 53
2.4.1 Polygon Basics 55
2.4.2 Polygons in WebGL 56
2.4.3 Approximating a Sphere 57
2.4.4 Triangulation 58
2.4.5 Text 59
2.4.6 Curved Objects 60
2.4.7 Attributes 61
2.5 Color 62
2.5.1 RGB Color 64
2.5.2 Indexed Color 66
2.5.3 Setting of Color Attributes 67
2.6 Viewing 68
2.6.1 The Orthographic View 68
2.6.2 Two-Dimensional Viewing 71
2.7 Control Functions 71
2.7.1 Interaction with the Window System 72
2.7.2 Aspect Ratio and Viewports 73
2.7.3 Application Organization 74
2.8 The Gasket Program 75
2.8.1 Sending Data to the GPU 78
2.8.2 Rendering the Points 78
2.8.3 The Vertex Shader 79
2.8.4 The Fragment Shader 80
2.8.5 Combining the Parts 80
2.8.6 The initShaders Function 81
2.8.7 The init Function 82
2.8.8 Reading the Shaders from the Application 83
2.9 Polygons and Recursion 83
2.10 The Three-Dimensional Gasket 86
2.10.1 Use of Three-Dimensional Points 86
2.10.2 Naming Conventions 88
2.10.3 Use of Polygons in Three Dimensions 88
2.10.4 Hidden-Surface Removal 91
Summary and Notes 93
Suggested Readings 94
Exercises 95
CHAPTER 3 INTERACTION AND ANIMATION 99
3.1 Animation 99
3.1.1 The Rotating Square 100
3.1.2 The Display Process 102
3.1.3 Double Buffering 103
3.1.4 Using a Timer 104
3.1.5 Using setAnimFrame 105
3.2 Interaction 106
3.3 Input Devices 107
3.4 Physical Input Devices 108
3.4.1 Keyboard Codes 108
3.4.2 The Light Pen 109
3.4.3 The Mouse and the Trackball 109
3.4.4 Data Tablets,Touch Pads, and Touch Screens 110
3.4.5 The Joystick 111
3.4.6 Multidimensional Input Devices 111
3.4.7 Logical Devices 112
3.4.8 Input Modes 113
3.5 Clients and Servers 115
3.6 Programming Event-Driven Input 116
3.6.1 Events and Event Listeners 117
3.6.2 Adding a Button 117
3.6.3 Menus 119
3.6.4 Using Keycodes 120
3.6.5 Sliders 121
3.7 Position Input 122
3.8 Window Events 123
3.9 Picking 125
3.10 Building Models Interactively 126
3.11 Design of Interactive Programs 130
Summary and Notes 130
Suggested Readings 131
Exercises 132
CHAPTER 4 GEOMETRIC OBJECTS AND TRANSFORMATIONS 135
4.1 Scalars, Points, and Vectors 136
4.1.1 Geometric Objects 136
4.1.2 Coordinate-Free Geometry 138
4.1.3 The Mathematical View: Vector and Affine Spaces 138
4.1.4 The Computer Science View 139
4.1.5 Geometric ADTs 140
4.1.6 Lines 141
4.1.7 Affine Sums 141
4.1.8 Convexity 142
4.1.9 Dot and Cross Products 142
4.1.10 Planes 143
4.2 Three-Dimensional Primitives 145
4.3 Coordinate Systems and Frames 146
4.3.1 Representations and N-Tuples 148
4.3.2 Change of Coordinate Systems 149
4.3.3 Example: Change of Representation 151
4.3.4 Homogeneous Coordinates 153
4.3.5 Example: Change in Frames 155
4.3.6 Working with Representations 157
4.4 Frames in WebGL 159
4.5 Matrix and Vector Types 163
4.5.1 Row versus Column Major Matrix Representations 165
4.6 Modeling a Colored Cube 165
4.6.1 Modeling the Faces 166
4.6.2 Inward- and Outward-Pointing Faces 167
4.6.3 Data Structures for Object Representation 167
4.6.4 The Colored Cube 168
4.6.5 Color Interpolation 170
4.6.6 Displaying the Cube 170
4.6.7 Drawing with Elements 171
4.7 Affine Transformations 172
4.8 Translation, Rotation, and Scaling 175
4.8.1 Translation 175
4.8.2 Rotation 176
4.8.3 Scaling 177
4.9 Transformations in Homogeneous Coordinates 179
4.9.1 Translation 179
4.9.2 Scaling 181
4.9.3 Rotation 181
4.9.4 Shear 183
4.10 Concatenation of Transformations 184
4.10.1 Rotation About a Fixed Point 185
4.10.2 General Rotation 186
4.10.3 The Instance Transformation 187
4.10.4 Rotation About an Arbitrary Axis 188
4.11 Transformation Matrices in WebGL 191
4.11.1 Current Transformation Matrices 192
4.11.2 Basic Matrix Functions 193
4.11.3 Rotation, Translation, and Scaling 194
4.11.4 Rotation About a Fixed Point 195
4.11.5 Order of Transformations 195
4.12 Spinning of the Cube 196
4.12.1 Uniform Matrices 198
4.13 Interfaces to Three-Dimensional Applications 200
4.13.1 Using Areas of the Screen 201
4.13.2 A Virtual Trackball 201
4.13.3 Smooth Rotations 204
4.13.4 Incremental Rotation 205
4.14 Quaternions 206
4.14.1 Complex Numbers and Quaternions 206
4.14.2 Quaternions and Rotation 207
4.14.3 Quaternions and Gimbal Lock 209
Summary and Notes 210
Suggested Readings 211
Exercises 211
CHAPTER 5 VIEWING 215
5.1 Classical and Computer Viewing 215
5.1.1 Classical Viewing 217
5.1.2 Orthographic Projections 217
5.1.3 Axonometric Projections 218
5.1.4 Oblique Projections 220
5.1.5 Perspective Viewing 221
5.2 Viewing with a Computer 222
5.3 Positioning of the Camera 224
5.3.1 Positioning of the Camera Frame 224
5.3.2 Two Viewing APIs 229
5.3.3 The Look-At Function 232
5.3.4 Other Viewing APIs 233
5.4 Parallel Projections 234
5.4.1 Orthogonal Projections 234
5.4.2 Parallel Viewing with WebGL 235
5.4.3 Projection Normalization 236
5.4.4 Orthogonal Projection Matrices 237
5.4.5 Oblique Projections 239
5.4.6 An Interactive Viewer 242
5.5 Perspective Projections 244
5.5.1 Simple Perspective Projections 245
5.6 Perspective Projections with WebGL 248
5.6.1 Perspective Functions 249
5.7 Perspective Projection Matrices 250
5.7.1 Perspective Normalization 250
5.7.2 WebGL Perspective Transformations 254
5.7.3 Perspective Example 256
5.8 Hidden-Surface Removal 256
5.8.1 Culling 258
5.9 Displaying Meshes 259
5.9.1 Displaying Meshes as Surfaces 262
5.9.2 Polygon Offset 264
5.9.3 Walking through a Scene 265
5.10 Projections and Shadows 265
5.10.1 Projected Shadows 266
5.11 Shadow Maps 270
Summary and Notes 271
Suggested Readings 272
Exercises 272
CHAPTER 6 LIGHTING AND SHADING 275
6.1 Light and Matter 276
6.2 Light Sources 279
6.2.1 Color Sources 280
6.2.2 Ambient Light 280
6.2.3 Point Sources 281
6.2.4 Spotlights 282
6.2.5 Distant Light Sources 282
6.3 The Phong Reflection Model 283
6.3.1 Ambient Reflection 285
6.3.2 Diffuse Reflection 285
6.3.3 Specular Reflection 286
6.3.4 The Modified Phong Model 288
6.4 Computation of Vectors 289
6.4.1 Normal Vectors 289
6.4.2 Angle of Reflection 292
6.5 Polygonal Shading 293
6.5.1 Flat Shading 293
6.5.2 Smooth and Gouraud Shading 294
6.5.3 Phong Shading 296
6.6 Approximation of a Sphere by Recursive Subdivision 297
6.7 Specifying Lighting Parameters 299
6.7.1 Light Sources 299
6.7.2 Materials 301
6.8 Implementing a Lighting Model 301
6.8.1 Applying the Lighting Model in the Application 302
6.8.2 Efficiency 304
6.8.3 Lighting in the Vertex Shader 305
6.9 Shading of the Sphere Model 310
6.10 Per-Fragment Lighting 311
6.11 Nonphotorealistic Shading 313
6.12 Global Illumination 314
Summary and Notes 315
Suggested Readings 316
Exercises 316
CHAPTER 7 DISCRETE TECHNIQUES 319
7.1 Buffers 320
7.2 Digital Images 321
7.3 Mapping Methods 325
7.4 Two-Dimensional Texture Mapping 327
7.5 Texture Mapping in WebGL 333
7.5.1 Texture Objects 334
7.5.2 The Texture Image Array 335
7.5.3 Texture Coordinates and Samplers 336
7.5.4 Texture Sampling 341
7.5.5 Working with Texture Coordinates 344
7.5.6 Multitexturing 345
7.6 Texture Generation 348
7.7 Environment Maps 349
7.8 Reflection Map Example 353
7.9 Bump Mapping 357
7.9.1 Finding Bump Maps 358
7.9.2 Bump Map Example 361
7.10 Blending Techniques 365
7.10.1 Opacity and Blending 366
7.10.2 Image Blending 367
7.10.3 Blending in WebGL 367
7.10.4 Antialiasing Revisited 369
7.10.5 Back-to-Front and Front-to-Back Rendering 371
7.10.6 Scene Antialiasing and Multisampling 371
7.10.7 Image Processing 372
7.10.8 Other Multipass Methods 374
7.11 GPGPU 374
7.12 Framebuffer Objects 378
7.13 Buffer Ping-Ponging 384
7.14 Picking 387
Summary and Notes 392
Suggested Readings 393
Exercises 394
CHAPTER 8 FROM GEOMETRY TO PIXELS 397
8.1 Basic Implementation Strategies 398
8.2 Four Major Tasks 400
8.2.1 Modeling 400
8.2.2 Geometry Processing 401
8.2.3 Rasterization 402
8.2.4 Fragment Processing 403
8.3 Clipping 403
8.4 Line-Segment Clipping 404
8.4.1 Cohen-Sutherland Clipping 404
8.4.2 Liang-Barsky Clipping 407
8.5 Polygon Clipping 408
8.6 Clipping of Other Primitives 410
8.6.1 Bounding Boxes and Volumes 410
8.6.2 Curves, Surfaces, and Text 412
8.6.3 Clipping in the Framebuffer 413
8.7 Clipping in Three Dimensions 413
8.8 Rasterization 416
8.9 Bresenham’s Algorithm 418
8.10 Polygon Rasterization 420
8.10.1 Inside—Outside Testing 421
8.10.2 WebGL and Concave Polygons 422
8.10.3 Fill and Sort 423
8.10.4 Flood Fill 423
8.10.5 Singularities 424
8.11 Hidden-Surface Removal 424
8.11.1 Object-Space and Image-Space Approaches 424
8.11.2 Sorting and Hidden-Surface Removal 426
8.11.3 Scan Line Algorithms 426
8.11.4 Back-Face Removal 427
8.11.5 The z-Buffer Algorithm 429
8.11.6 Scan Conversion with the z-Buffer 431
8.11.7 Depth Sort and the Painter’s Algorithm 432
8.12 Antialiasing 435
8.13 Display Considerations 437
8.13.1 Color Systems 437
8.13.2 The Color Matrix 441
8.13.3 Gamma Correction 441
8.13.4 Dithering and Halftoning 442
Summary and Notes 443
Suggested Readings 445
Exercises 445
CHAPTER 9 MODELING AND HIERARCHY 449
9.1 Symbols and Instances 450
9.2 Hierarchical Models 451
9.3 A Robot Arm 453
9.4 Trees and Traversal 456
9.4.1 A Stack-Based Traversal 457
9.5 Use of Tree Data Structures 460
9.6 Animation 464
9.7 Graphical Objects 465
9.7.1 Methods, Attributes, and Messages 466
9.7.2 A Cube Object 467
9.7.3 Objects and Hierarchy 468
9.7.4 Geometric and Nongeometric Objects 469
9.8 Scene Graphs 470
9.9 Implementing Scene Graphs 472
9.10 Other Tree Structures 474
9.10.1 CSG Trees 474
9.10.2 BSP Trees 475
9.10.3 Quadtrees and Octrees 478
Summary and Notes 479
Suggested Readings 480
Exercises 480
CHAPTER 10 PROCEDURAL METHODS 483
10.1 Algorithmic Models 483
10.2 Physically Based Models and Particle Systems 485
10.3 Newtonian Particles 486
10.3.1 Independent Particles 488
10.3.2 Spring Forces 488
10.3.3 Attractive and Repulsive Forces 490
10.4 Solving Particle Systems 491
10.5 Constraints 494
10.5.1 Collisions 494
10.5.2 Soft Constraints 496
10.6 A Simple Particle System 497
10.6.1 Displaying the Particles 498
10.6.2 Updating Particle Positions 498
10.6.3 Collisions 499
10.6.4 Forces 500
10.6.5 Flocking 500
10.7 Agent-Based Models 501
10.8 Language-Based Models 503
10.9 Recursive Methods and Fractals 507
10.9.1 Rulers and Length 508
10.9.2 Fractal Dimension 509
10.9.3 Midpoint Division and Brownian Motion 510
10.9.4 Fractal Mountains 511
10.9.5 The Mandelbrot Set 512
10.9.6 Mandelbrot Fragment Shader 516
10.10 Procedural Noise 517
Summary and Notes 521
Suggested Readings 521
Exercises 522
CHAPTER 11 CURVES AND SURFACES 525
11.1 Representation of Curves and Surfaces 525
11.1.1 Explicit Representation 525
11.1.2 Implicit Representations 527
11.1.3 Parametric Form 528
11.1.4 Parametric Polynomial Curves 529
11.1.5 Parametric Polynomial Surfaces 530
11.2 Design Criteria 530
11.3 Parametric Cubic Polynomial Curves 532
11.4 Interpolation 533
11.4.1 Blending Functions 534
11.4.2 The Cubic Interpolating Patch 536
11.5 Hermite Curves and Surfaces 538
11.5.1 The Hermite Form 538
11.5.2 Geometric and Parametric Continuity 540
11.6 Be´ zier Curves and Surfaces 541
11.6.1 Be´ zier Curves 542
11.6.2 Be´ zier Surface Patches 544
11.7 Cubic B-Splines 545
11.7.1 The Cubic B-Spline Curve 545
11.7.2 B-Splines and Basis 548
11.7.3 Spline Surfaces 549
11.8 General B-Splines 550
11.8.1 Recursively Defined B-Splines 551
11.8.2 Uniform Splines 552
11.8.3 Nonuniform B-Splines 552
11.8.4 NURBS 553
11.8.5 Catmull-Rom Splines 554
11.9 Rendering Curves and Surfaces 555
11.9.1 Polynomial Evaluation Methods 556
11.9.2 Recursive Subdivision of Be´ zier Polynomials 557
11.9.3 Rendering Other Polynomial Curves by Subdivision 560
11.9.4 Subdivision of Be´ zier Surfaces 561
11.10 The Utah Teapot 562
11.11 Algebraic Surfaces 565
11.11.1 Quadrics 565
11.11.2 Rendering of Surfaces by Ray Casting 566
11.12 Subdivision Curves and Surfaces 567
11.12.1 Mesh Subdivision 568
11.13 Mesh Generation from Data 571
11.13.1 Height Fields Revisited 571
11.13.2 Delaunay Triangulation 571
11.13.3 Point Clouds 575
11.14 Graphics API support for Curves and Surfaces 576
11.14.1 Tessellation Shading 576
11.14.2 Geometry Shading 577
Summary and Notes 577
Suggested Readings 578
Exercises 578
CHAPTER 12 ADVANCED RENDERING 581
12.1 Going Beyond Pipeline Rendering 581
12.2 Ray Tracing 582
12.3 Building a Simple Ray Tracer 586
12.3.1 Recursive Ray Tracing 586
12.3.2 Calculating Intersections 588
12.3.3 Ray-Tracing Variations 590
12.4 The Rendering Equation 591
12.5 Radiosity 593
12.5.1 The Radiosity Equation 594
12.5.2 Solving the Radiosity Equation 595
12.5.3 Computing Form Factors 597
12.5.4 Carrying Out Radiosity 599
12.6 Global Illumination and Path Tracing 600
12.7 RenderMan 602
12.8 Parallel Rendering 603
12.8.1 Sort-Middle Rendering 605
12.8.2 Sort-Last Rendering 606
12.8.3 Sort-First Rendering 610
12.9 Hardware GPU Implementations 611
12.10 Implicit Functions and Contour Maps 612
12.10.1 Marching Squares 613
12.10.2 Marching Triangles 617
12.11 Volume Rendering 618
12.11.1 Volumetric Data Sets 618
12.11.2 Visualization of Implicit Functions 619
12.12 Isosurfaces and Marching Cubes 621
12.13 Marching Tetrahedra 624
12.14 Mesh Simplification 625
12.15 Direct Volume Rendering 625
12.15.1 Assignment of Color and Opacity 626
12.15.2 Splatting 627
12.15.3 Volume Ray Tracing 628
12.15.4 Texture Mapping of Volumes 629
12.16 Image-Based Rendering 630
12.16.1 A Simple Example 630
Summary and Notes 632
Suggested Readings 633
Exercises 634
APPENDIX A INITIALIZING SHADERS 637
A.1 Shaders in the HTML file 637
A.2 Reading Shaders from Source Files 640
APPENDIX B SPACES 643
B.1 Scalars 643
B.2 Vector Spaces 644
B.3 Affine Spaces 646
B.4 Euclidean Spaces 647
B.5 Projections 648
B.6 Gram-Schmidt Orthogonalization 649
Suggested Readings 650
Exercises 650
APPENDIX C MATRICES 651
C.1 Definitions 651
C.2 Matrix Operations 652
C.3 Row and Column Matrices 653
C.4 Rank 654
C.5 Change of Representation 655
C.6 The Cross Product 657
C.7 Eigenvalues and Eigenvectors 657
C.8 Vector and Matrix Classes 659
Suggested Readings 659
Exercises 660
APPENDIX D SAMPLING AND ALIASING 661
D.1 Sampling Theory 661
D.2 Reconstruction 666
D.3 Quantization 668
References 669