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