Interactive Computer Graphics. A Top-Down Approach with WebGL

Cover......Page 1
Dedication......Page 6
Contents......Page 8
Preface......Page 22
Chapter 1: Graphics Systems and Models......Page 32
  1.1.1 Display of Information......Page 33
  1.1.3 Simulation and Animation......Page 34
  1.1.4 User Interfaces......Page 35
  1.2.1 Pixels and the Framebuffer......Page 36
  1.2.2 The CPU and the GPU......Page 37
  1.2.3 Output Devices......Page 38
  1.2.4 Input Devices......Page 40
  1.3.1 Objects and Viewers......Page 41
  1.3.2 Light and Images......Page 43
  1.3.3 Imaging Models......Page 44
  1.4.1 The Pinhole Camera......Page 46
  1.4.2 The Human Visual System......Page 48
 1.5 The Synthetic-Camera Model......Page 49
 1.6 The Programmer’s Interface......Page 51
  1.6.1 The Pen-Plotter Model......Page 52
  1.6.2 Three-Dimensional APIs......Page 54
  1.6.3 A Sequence of Images......Page 57
  1.6.4 The Modeling–Rendering Paradigm......Page 58
 1.7 Graphics Architectures......Page 59
  1.7.2 Pipeline Architectures......Page 60
  1.7.3 The Graphics Pipeline......Page 61
  1.7.5 Clipping and Primitive Assembly......Page 62
 1.8 Programmable Pipelines......Page 63
 1.9 Performance Characteristics......Page 64
 1.10 OpenGL Versions and WebGL......Page 65
 Suggested Readings......Page 67
 Exercises......Page 68
 2.1 The Sierpinski Gasket......Page 70
 2.2 Programming Two-Dimensional Applications......Page 73
  2.3.1 Graphics Functions......Page 78
  2.3.2 The Graphics Pipeline and State Machines......Page 80
  2.3.4 The WebGL Interface......Page 81
  2.3.5 Coordinate Systems......Page 82
 2.4 Primitives and Attributes......Page 84
  2.4.1 Polygon Basics......Page 86
  2.4.2 Polygons in WebGL......Page 87
  2.4.3 Approximating a Sphere......Page 88
  2.4.4 Triangulation......Page 89
  2.4.5 Text......Page 90
  2.4.6 Curved Objects......Page 91
  2.4.7 Attributes......Page 92
 2.5 Color......Page 93
  2.5.1 RGB Color......Page 95
  2.5.2 Indexed Color......Page 97
  2.5.3 Setting of Color Attributes......Page 98
  2.6.1 The Orthographic View......Page 99
 2.7 Control Functions......Page 102
  2.7.1 Interaction with the Window System......Page 103
  2.7.2 Aspect Ratio and Viewports......Page 104
  2.7.3 Application Organization......Page 105
 2.8 The Gasket Program......Page 106
  2.8.2 Rendering the Points......Page 109
  2.8.3 The Vertex Shader......Page 110
  2.8.5 Combining the Parts......Page 111
  2.8.6 The initShaders Function......Page 112
  2.8.7 The init Function......Page 113
 2.9 Polygons and Recursion......Page 114
  2.10.1 Use of Three-Dimensional Points......Page 117
  2.10.3 Use of Polygons in Three Dimensions......Page 119
  2.10.4 Hidden-Surface Removal......Page 122
 Summary and Notes......Page 124
 Suggested Readings......Page 125
 Exercises......Page 126
 3.1 Animation......Page 130
  3.1.1 The Rotating Square......Page 131
  3.1.2 The Display Process......Page 133
  3.1.3 Double Buffering......Page 134
  3.1.4 Using a Timer......Page 135
  3.1.5 Using requestAnimFrame......Page 136
 3.2 Interaction......Page 137
 3.3 Input Devices......Page 138
  3.4.1 Keyboard Codes......Page 139
  3.4.3 The Mouse and the Trackball......Page 140
  3.4.4 Data Tablets,Touch Pads, and Touch Screens......Page 141
  3.4.6 Multidimensional Input Devices......Page 142
  3.4.7 Logical Devices......Page 143
  3.4.8 Input Modes......Page 144
 3.5 Clients and Servers......Page 146
 3.6 Programming Event-Driven Input......Page 147
  3.6.2 Adding a Button......Page 148
  3.6.3 Menus......Page 150
  3.6.4 Using Keycodes......Page 151
  3.6.5 Sliders......Page 152
 3.7 Position Input......Page 153
 3.8 Window Events......Page 154
 3.9 Picking......Page 156
 3.10 Building Models Interactively......Page 157
 Summary and Notes......Page 161
 Suggested Readings......Page 162
 Exercises......Page 163
Chapter 4: Geometric Objects and Transformations......Page 166
  4.1.1 Geometric Objects......Page 167
  4.1.3 The Mathematical View: Vector and Affine Spaces......Page 169
  4.1.4 The Computer Science View......Page 170
  4.1.5 Geometric ADTs......Page 171
  4.1.7 Affine Sums......Page 172
  4.1.9 Dot and Cross Products......Page 173
  4.1.10 Planes......Page 174
 4.2 Three-Dimensional Primitives......Page 176
 4.3 Coordinate Systems and Frames......Page 177
  4.3.1 Representations and N-Tuples......Page 179
  4.3.2 Change of Coordinate Systems......Page 180
  4.3.3 Example: Change of Representation......Page 182
  4.3.4 Homogeneous Coordinates......Page 184
  4.3.5 Example: Change in Frames......Page 186
  4.3.6 Working with Representations......Page 188
 4.4 Frames in WebGL......Page 190
 4.5 Matrix and Vector Types......Page 194
 4.6 Modeling a Colored Cube......Page 196
  4.6.1 Modeling the Faces......Page 197
  4.6.3 Data Structures for Object Representation......Page 198
  4.6.4 The Colored Cube......Page 199
  4.6.6 Displaying the Cube......Page 201
  4.6.7 Drawing with Elements......Page 202
 4.7 Affine Transformations......Page 203
  4.8.1 Translation......Page 206
  4.8.2 Rotation......Page 207
  4.8.3 Scaling......Page 208
  4.9.1 Translation......Page 210
  4.9.3 Rotation......Page 212
  4.9.4 Shear......Page 214
 4.10 Concatenation of Transformations......Page 215
  4.10.1 Rotation About a Fixed Point......Page 216
  4.10.2 General Rotation......Page 217
  4.10.3 The Instance Transformation......Page 218
  4.10.4 Rotation About an Arbitrary Axis......Page 219
 4.11 Transformation Matrices in WebGL......Page 222
  4.11.1 Current Transformation Matrices......Page 223
  4.11.2 Basic Matrix Functions......Page 224
  4.11.3 Rotation, Translation, and Scaling......Page 225
  4.11.5 Order of Transformations......Page 226
 4.12 Spinning of the Cube......Page 227
  4.12.1 Uniform Matrices......Page 229
 4.13 Interfaces to Three-Dimensional Applications......Page 231
  4.13.2 A Virtual Trackball......Page 232
  4.13.3 Smooth Rotations......Page 235
  4.13.4 Incremental Rotation......Page 236
  4.14.1 Complex Numbers and Quaternions......Page 237
  4.14.2 Quaternions and Rotation......Page 238
  4.14.3 Quaternions and Gimbal Lock......Page 240
 Summary and Notes......Page 241
 Exercises......Page 242
 5.1 Classical and Computer Viewing......Page 246
  5.1.2 Orthographic Projections......Page 248
  5.1.3 Axonometric Projections......Page 249
  5.1.4 Oblique Projections......Page 251
  5.1.5 Perspective Viewing......Page 252
 5.2 Viewing with a Computer......Page 253
  5.3.1 Positioning of the Camera Frame......Page 255
  5.3.2 Two Viewing APIs......Page 260
  5.3.3 The Look-At Function......Page 263
  5.3.4 Other Viewing APIs......Page 264
  5.4.1 Orthogonal Projections......Page 265
  5.4.2 Parallel Viewing with WebGL......Page 266
  5.4.3 Projection Normalization......Page 267
  5.4.4 Orthogonal Projection Matrices......Page 268
  5.4.5 Oblique Projections......Page 270
  5.4.6 An Interactive Viewer......Page 273
 5.5 Perspective Projections......Page 275
  5.5.1 Simple Perspective Projections......Page 276
 5.6 Perspective Projections with WebGL......Page 279
  5.6.1 Perspective Functions......Page 280
  5.7.1 Perspective Normalization......Page 281
  5.7.2 WebGL Perspective Transformations......Page 285
 5.8 Hidden-Surface Removal......Page 287
  5.8.1 Culling......Page 289
 5.9 Displaying Meshes......Page 290
  5.9.1 Displaying Meshes as Surfaces......Page 293
  5.9.2 Polygon Offset......Page 295
 5.10 Projections and Shadows......Page 296
  5.10.1 Projected Shadows......Page 297
 5.11 Shadow Maps......Page 301
 Summary and Notes......Page 302
 Exercises......Page 303
Chapter 6: Lighting and Shading......Page 306
 6.1 Light and Matter......Page 307
 6.2 Light Sources......Page 310
  6.2.2 Ambient Light......Page 311
  6.2.3 Point Sources......Page 312
  6.2.5 Distant Light Sources......Page 313
 6.3 The Phong Reflection Model......Page 314
  6.3.2 Diffuse Reflection......Page 316
  6.3.3 Specular Reflection......Page 317
  6.3.4 The Modified Phong Model......Page 319
  6.4.1 Normal Vectors......Page 320
  6.4.2 Angle of Reflection......Page 323
  6.5.1 Flat Shading......Page 324
  6.5.2 Smooth and Gouraud Shading......Page 325
  6.5.3 Phong Shading......Page 327
 6.6 Approximation of a Sphere by Recursive Subdivision......Page 328
  6.7.1 Light Sources......Page 330
 6.8 Implementing a Lighting Model......Page 332
  6.8.1 Applying the Lighting Model in the Application......Page 333
  6.8.2 Efficiency......Page 335
  6.8.3 Lighting in the Vertex Shader......Page 336
 6.9 Shading of the Sphere Model......Page 341
 6.10 Per-Fragment Lighting......Page 342
 6.11 Nonphotorealistic Shading......Page 344
 6.12 Global Illumination......Page 345
 Summary and Notes......Page 346
 Exercises......Page 347
Chapter 7: Discrete Techniques......Page 350
 7.1 Buffers......Page 351
 7.2 Digital Images......Page 352
 7.3 Mapping Methods......Page 356
 7.4 Two-Dimensional Texture Mapping......Page 358
 7.5 Texture Mapping in WebGL......Page 364
  7.5.1 Texture Objects......Page 365
  7.5.2 The Texture Image Array......Page 366
  7.5.3 Texture Coordinates and Samplers......Page 367
  7.5.4 Texture Sampling......Page 372
  7.5.5 Working with Texture Coordinates......Page 375
  7.5.6 Multitexturing......Page 376
 7.6 Texture Generation......Page 379
 7.7 Environment Maps......Page 380
 7.8 Reflection Map Example......Page 384
 7.9 Bump Mapping......Page 388
  7.9.1 Finding Bump Maps......Page 389
  7.9.2 Bump Map Example......Page 392
 7.10 Blending Techniques......Page 396
  7.10.1 Opacity and Blending......Page 397
  7.10.3 Blending in WebGL......Page 398
  7.10.4 Antialiasing Revisited......Page 400
  7.10.6 Scene Antialiasing and Multisampling......Page 402
  7.10.7 Image Processing......Page 403
 7.11 GPGPU......Page 405
 7.12 Framebuffer Objects......Page 409
 7.13 Buffer Ping-Ponging......Page 415
 7.14 Picking......Page 418
 Summary and Notes......Page 423
 Suggested Readings......Page 424
 Exercises......Page 425
Chapter 8: From Geometry To Pixels......Page 428
 8.1 Basic Implementation Strategies......Page 429
  8.2.1 Modeling......Page 431
  8.2.2 Geometry Processing......Page 432
  8.2.3 Rasterization......Page 433
 8.3 Clipping......Page 434
  8.4.1 Cohen-Sutherland Clipping......Page 435
  8.4.2 Liang-Barsky Clipping......Page 438
 8.5 Polygon Clipping......Page 439
  8.6.1 Bounding Boxes and Volumes......Page 441
  8.6.2 Curves, Surfaces, and Text......Page 443
 8.7 Clipping in Three Dimensions......Page 444
 8.8 Rasterization......Page 447
 8.9 Bresenham’s Algorithm......Page 449
 8.10 Polygon Rasterization......Page 451
  8.10.1 Inside–Outside Testing......Page 452
  8.10.2 WebGL and Concave Polygons......Page 453
  8.10.4 Flood Fill......Page 454
  8.11.1 Object-Space and Image-Space Approaches......Page 455
  8.11.3 Scan Line Algorithms......Page 457
  8.11.4 Back-Face Removal......Page 458
  8.11.5 The z-Buffer Algorithm......Page 460
  8.11.6 Scan Conversion with the z-Buffer......Page 462
  8.11.7 Depth Sort and the Painter’s Algorithm......Page 463
 8.12 Antialiasing......Page 466
  8.13.1 Color Systems......Page 468
  8.13.3 Gamma Correction......Page 472
  8.13.4 Dithering and Halftoning......Page 473
 Summary and Notes......Page 474
 Exercises......Page 476
Chapter 9: Modeling and Hierarchy......Page 480
 9.1 Symbols and Instances......Page 481
 9.2 Hierarchical Models......Page 482
 9.3 A Robot Arm......Page 484
 9.4 Trees and Traversal......Page 487
  9.4.1 A Stack-Based Traversal......Page 488
 9.5 Use of Tree Data Structures......Page 491
 9.6 Animation......Page 495
 9.7 Graphical Objects......Page 496
  9.7.1 Methods, Attributes, and Messages......Page 497
  9.7.2 A Cube Object......Page 498
  9.7.3 Objects and Hierarchy......Page 499
  9.7.4 Geometric and Nongeometric Objects......Page 500
 9.8 Scene Graphs......Page 501
 9.9 Implementing Scene Graphs......Page 503
  9.10.1 CSG Trees......Page 505
  9.10.2 BSP Trees......Page 506
  9.10.3 Quadtrees and Octrees......Page 509
 Summary and Notes......Page 510
 Exercises......Page 511
 10.1 Algorithmic Models......Page 514
 10.2 Physically Based Models and Particle Systems......Page 516
 10.3 Newtonian Particles......Page 517
  10.3.2 Spring Forces......Page 519
  10.3.3 Attractive and Repulsive Forces......Page 521
 10.4 Solving Particle Systems......Page 522
  10.5.1 Collisions......Page 525
  10.5.2 Soft Constraints......Page 527
 10.6 A Simple Particle System......Page 528
  10.6.2 Updating Particle Positions......Page 529
  10.6.3 Collisions......Page 530
  10.6.5 Flocking......Page 531
 10.7 Agent-Based Models......Page 532
 10.8 Language-Based Models......Page 534
 10.9 Recursive Methods and Fractals......Page 538
  10.9.1 Rulers and Length......Page 539
  10.9.2 Fractal Dimension......Page 540
  10.9.3 Midpoint Division and Brownian Motion......Page 541
  10.9.4 Fractal Mountains......Page 542
  10.9.5 The Mandelbrot Set......Page 543
  10.9.6 Mandelbrot Fragment Shader......Page 547
 10.10 Procedural Noise......Page 548
 Suggested Readings......Page 552
 Exercises......Page 553
  11.1.1 Explicit Representation......Page 556
  11.1.2 Implicit Representations......Page 558
  11.1.3 Parametric Form......Page 559
  11.1.4 Parametric Polynomial Curves......Page 560
 11.2 Design Criteria......Page 561
 11.3 Parametric Cubic Polynomial Curves......Page 563
 11.4 Interpolation......Page 564
  11.4.1 Blending Functions......Page 565
  11.4.2 The Cubic Interpolating Patch......Page 567
  11.5.1 The Hermite Form......Page 569
  11.5.2 Geometric and Parametric Continuity......Page 571
 11.6 Be´zier Curves and Surfaces......Page 572
  11.6.1 Be´zier Curves......Page 573
  11.6.2 Be´zier Surface Patches......Page 575
  11.7.1 The Cubic B-Spline Curve......Page 576
  11.7.2 B-Splines and Basis......Page 579
  11.7.3 Spline Surfaces......Page 580
 11.8 General B-Splines......Page 581
  11.8.1 Recursively Defined B-Splines......Page 582
  11.8.3 Nonuniform B-Splines......Page 583
  11.8.4 NURBS......Page 584
  11.8.5 Catmull-Rom Splines......Page 585
 11.9 Rendering Curves and Surfaces......Page 586
  11.9.1 Polynomial Evaluation Methods......Page 587
  11.9.2 Recursive Subdivision of Be´zier Polynomials......Page 588
  11.9.3 Rendering Other Polynomial Curves by Subdivision......Page 591
  11.9.4 Subdivision of Be´zier Surfaces......Page 592
 11.10 The Utah Teapot......Page 593
  11.11.1 Quadrics......Page 596
  11.11.2 Rendering of Surfaces by Ray Casting......Page 597
 11.12 Subdivision Curves and Surfaces......Page 598
  11.12.1 Mesh Subdivision......Page 599
  11.13.2 Delaunay Triangulation......Page 602
  11.13.3 Point Clouds......Page 606
  11.14.1 Tessellation Shading......Page 607
 Summary and Notes......Page 608
 Exercises......Page 609
 12.1 Going Beyond Pipeline Rendering......Page 612
 12.2 Ray Tracing......Page 613
  12.3.1 Recursive Ray Tracing......Page 617
  12.3.2 Calculating Intersections......Page 619
  12.3.3 Ray-Tracing Variations......Page 621
 12.4 The Rendering Equation......Page 622
 12.5 Radiosity......Page 624
  12.5.1 The Radiosity Equation......Page 625
  12.5.2 Solving the Radiosity Equation......Page 626
  12.5.3 Computing Form Factors......Page 628
  12.5.4 Carrying Out Radiosity......Page 630
 12.6 Global Illumination and Path Tracing......Page 631
 12.7 RenderMan......Page 633
 12.8 Parallel Rendering......Page 634
  12.8.1 Sort-Middle Rendering......Page 636
  12.8.2 Sort-Last Rendering......Page 637
  12.8.3 Sort-First Rendering......Page 641
 12.9 Hardware GPU Implementations......Page 642
 12.10 Implicit Functions and Contour Maps......Page 643
  12.10.1 Marching Squares......Page 644
  12.10.2 Marching Triangles......Page 648
  12.11.1 Volumetric Data Sets......Page 649
  12.11.2 Visualization of Implicit Functions......Page 650
 12.12 Isosurfaces and Marching Cubes......Page 652
 12.13 Marching Tetrahedra......Page 655
 12.15 Direct Volume Rendering......Page 656
  12.15.1 Assignment of Color and Opacity......Page 657
  12.15.2 Splatting......Page 658
  12.15.3 Volume Ray Tracing......Page 659
  12.15.4 Texture Mapping of Volumes......Page 660
  12.16.1 A Simple Example......Page 661
 Summary and Notes......Page 663
 Suggested Readings......Page 664
 Exercises......Page 665
  A.1 Shaders in the HTML file......Page 668
  A.2 Reading Shaders from Source Files......Page 671
  B.1 Scalars......Page 674
  B.2 Vector Spaces......Page 675
  B.3 Affine Spaces......Page 677
  B.4 Euclidean Spaces......Page 678
  B.5 Projections......Page 679
  B.6 Gram-Schmidt Orthogonalization......Page 680
  Exercises......Page 681
  C.1 Definitions......Page 682
  C.2 Matrix Operations......Page 683
  C.3 Row and Column Matrices......Page 684
  C.4 Rank......Page 685
  C.5 Change of Representation......Page 686
  C.7 Eigenvalues and Eigenvectors......Page 688
  Suggested Readings......Page 690
  Exercises......Page 691
  D.1 Sampling Theory......Page 692
  D.2 Reconstruction......Page 697
  D.3 Quantization......Page 699
References......Page 700
WebGL Index......Page 712
Subject Index......Page 714