CHAPTER 1 GRAPHICS SYSTEMS AND MODELS 31
1.1 Applications of Computer Graphics 32
1.1.1 Display of Information 32
1.1.2 Design 33
1.1.3 Simulation and Animation 33
1.1.4 User Interfaces 34
1.2 A Graphics System 35
1.2.1 Pixels and the Frame Buffer 35
1.2.2 The CPU and the GPU 36
1.2.3 Output Devices 37
1.2.4 Input Devices 39
1.2.5 Physical Input Devices 40
1.2.6 Logical Devices 42
1.2.7 Input Modes 43
1.3 Images:Physical and Synthetic 45
1.3.1 Objects and Viewers 45
1.3.2 Light and Images 46
1.3.3 Imaging Models 48
1.4 Imaging Systems 50
1.4.1 The Pinhole Camera 50
1.4.2 The Human Visual System 52
1.5 The Synthetic-Camera Model 53
1.6 The Programmer's Interface 55
1.6.1 The Pen-Plotter Model 57
1.6.2 Three-Dimensional APIs 58
1.6.3 A Sequence of Images 61
1.6.4 The Modeling-Rendering Paradigm 62
1.7 Graphics Architectures 63
1.7.1 Display Processors 64
1.7.2 Pipeline Architectures 64
1.7.3 The Graphics Pipeline 65
1.7.4 Vertex Processing 66
1.7.5 Clipping and Primitive Assembly 66
1.7.6 Rasterization 67
1.7.7 Fragment Processing 67
1.8 Programmable Pipelines 67
1.9 Performance Characteristics 68
Summary and Notes 69
Suggested Readings 70
Exercises 71
CHPATER 2 GRAPHICS PROGRAMMING 73
2.1 The Sierpinski Gasket 73
2.2 Programming Two-Dimensional Applications 76
2.3 The OpenGL Application Programming Interface 80
2.3.1 Graphics Functions 81
2.3.2 The Graphics Pipeline and State Machines 83
2.3.3 The OpenGL Interface 83
2.3.4 Coordinate Systems 85
2.4 Primitives and Attributes 86
2.4.1 Polygon Basics 88
2.4.2 Polygons in OpenGL 89
2.4.3 Approximating a Sphere 90
2.4.4 Triangulation 92
2.4.5 Text 94
2.4.6 Curved Objects 95
2.4.7 Attributes 95
2.5 Color 97
2.5.1 RGB Color 99
2.5.2 Indexed Color 101
2.5.3 Setting of Color Attributes 102
2.6 Viewing 103
2.6.1 The Orthographic View 104
2.6.2 Two-Dimensional Viewing 107
2.7 Control Functions 108
2.7.1 Interaction with the Window System 108
2.7.2 Aspect Ratio and Viewports 109
2.7.3 The main,display,and init Functions 110
2.7.4 Program Structure 113
2.8 The Gasket Program 113
2.8.1 Rendering the Points 114
2.8.2 The Vertex Shader 115
2.8.3 The Fragment Shader 116
2.8.4 Combining the Parts 116
2.8.5 The initShader Function 116
2.9 Polygons and Recursion 118
2.10 The Three-Dimensional Gasket 121
2.10.1 Use of Three-Dimensional Points 121
2.10.2 Use of Polygons in Three Dimensions 122
2.10.3 Hidden-Surface Removal 126
2.11 Adding Interaction 128
2.11.1 Using the Pointing Device 128
2.11.2 Window Events 131
2.11.3 Keyboard Events 132
2.11.4 The Idle Callback 133
2.11.5 Double Buffering 135
2.11.6 Window Management 136
2.12 Menus 136
Summary and Notes 138
Suggested Readings 139
Exercises 140
CHAPTER 3 GEOMETRIC OBJECTS AND TRANSFORMATIONS 145
3.1 Scalars,Points,and Vectors 146
3.1.1 Geometric Objects 146
3.1.2 Coordinate-Free Geometry 147
3.1.3 The Mathematical View: Vector and Affine Spaces 148
3.1.4 The Computer Science View 149
3.1.5 Geometric ADTs 149
3.1.6 Lines 150
3.1.7 Affine Sums 151
3.1.8 Convexity 152
3.1.9 Dot and Cross Products 152
3.1.10 Planes 153
3.2 Three-Dimensional Primitives 155
3.3 Coordinate Systems and Frames 156
3.3.1 Representations and N-Tuples 158
3.3.2 Change of Coordinate Systems 159
3.3.3 Example Change of Representation 162
3.3.4 Homogeneous Coordinates 163
3.3.5 Example Change in Frames 166
3.3.6 Working with Representations 167
3.4 Frames in OpenGL 169
3.5 Matrix and Vector Classes 174
3.6 Modeling a Colored Cube 176
3.6.1 Modeling the Faces 176
3.6.2 Inward-and Outward-Pointing Faces 176
3.6.3 Data Structures for Object Representation 177
3.6.4 The Color Cube 178
3.6.5 Interpolation 180
3.6.6 Displaying the Cube 181
3.7 Affine Transformations 182
3.8 Translation,Rotation,and Scaling 185
3.8.1 Translation 185
3.8.2 Rotation 186
3.8.3 Scaling 188
3.9 Transformations in Homogeneous Coordinates 189
3.9.1 Translation 190
3.9.2 Scaling 191
3.9.3 Rotation 192
3.9.4 Shear 193
3.10 Concatenation of Transformations 194
3.10.1 Rotation About a Fixed Point 195
3.10.2 General Rotation 197
3.10.3 The Instance Transformation 198
3.10.4 Rotation About an Arbitrary Axis 199
3.11 Transformation Matrices in OpenGL 202
3.11.1 Current Transformation Matrices 203
3.11.2 Rotation,Translation,and Scaling 204
3.11.3 Rotation About a Fixed Point 205
3.11.4 Order of Transformations 206
3.12 Spinning of the Cube 206
3.12.1 Updating in the Display Callback 207
3.12.2 Uniform Variables 208
3.13 Interfaces to Three-Dimensional Applications 210
3.13.1 Using Areas of the Screen 210
3.13.2 A Virtual Trackball 211
3.13.3 Smooth Rotations 214
3.13.4 Incremental Rotation 215
3.14 Quaternions 216
3.14.1 Complex Numbers and Quaternions 216
3.14.2 Quaternions and Rotation 217
Summary and Notes 220
Suggested Readings 220
Exercises 221
CHAPTER 4 VIEWING 225
4.1 Classical and Computer Viewing 225
4.1.1 Classical Viewing 227
4.1.2 Orthographic Projections 227
4.1.3 Axonometric Projections 228
4.1.4 Oblique Projections 230
4.1.5 Perspective Viewing 231
4.2 Viewing with a Computer 232
4.3 Positioning of the Camera 234
4.3.1 Positioning of the Camera Frame 234
4.3.2 Two Viewing APIs 239
4.3.3 The Look-At Function 242
4.3.4 Other Viewing APIs 244
4.4 Parallel Projections 245
4.4.1 Orthogonal Projections 245
4.4.2 Parallel Viewing with OpenGL 246
4.4.3 Projection Normalization 247
4.4.4 Orthogonal-Projection Matrices 249
4.4.5 Oblique Projections 250
4.4.6 An Interactive Viewer 254
4.5 Perspective Projections 256
4.5.1 Simple Perspective Projections 256
4.6 Perspective Projections with OpenGL 259
4.6.1 Perspective Functions 260
4.7 Perspective-Projection Matrices 262
4.7.1 Perspective Normalization 262
4.7.2 OpenGL Perspective Transformations 266
4.7.3 Perspective Example 268
4.8 Hidden-Surface Removal 268
4.8.1 Culling 271
4.9 Displaying Meshes 271
4.9.1 Displaying Meshes as a Surface 274
4.9.2 Polygon Offset 276
4.9.3 Walking Through a Scene 277
4.10 Projections and Shadows 279
Summary and Notes 283
Suggested Readings 284
Exercises 284
CHAPTER 5 LIGHTING AND SHADING 287
5.1 Light and Matter 288
5.2 Light Sources 291
5.2.1 Color Sources 292
5.2.2 Ambient Light 292
5.2.3 Point Sources 293
5.2.4 Spotlights 294
5.2.5 Distant Light Sources 294
5.3 The Phong Reflection Model 295
5.3.1 Ambient Reflection 297
5.3.2 Diffuse Reflection 297
5.3.3 Specular Reflection 299
5.3.4 The Modified Phong Model 300
5.4 Computation of Vectors 301
5.4.1 Normal Vectors 302
5.4.2 Angle of Reflection 304
5.5 Polygonal Shading 305
5.5.1 Flat Shading 306
5.5.2 Smooth and Gouraud Shading 307
5.5.3 Phong Shading 309
5.6 Approximation of a Sphere by Recursive Subdivision 310
5.7 Specifying Lighting Parameters 313
5.7.1 Light Sources 313
5.7.2 Materials 314
5.8 Implementing a Lighting Model 316
5.8.1 Applying the Lighting Model in the Application 316
5.8.2 Efficiency 319
5.8.3 Lighting in the Vertex Shader 320
5.9 Shading of the Sphere Model 324
5.10 Per-Fragment Lighting 325
5.10.1 Nonphotorealistic Shading 327
5.11 Global Illumination 327
Summary and Notes 329
Suggested Readings 330
Exercises 330
CHAPTER 6 FROM VERTICES TO FRAGMENTS 333
6.1 Basic Implementation Strategies 334
6.2 Four Major Tasks 336
6.2.1 Modeling 336
6.2.2 Geometry Processing 337
6.2.3 Rasterization 338
6.2.4 Fragment Processing 339
6.3 Clipping 340
6.4 Line-Segment Clipping 340
6.4.1 Cohen-Sutherland Clipping 340
6.4.2 Liang-Barsky Clipping 343
6.5 Polygon Clipping 344
6.6 Clipping of Other Primitives 347
6.6.1 Bounding Boxes and Volumes 348
6.6.2 Curves,Surfaces,and Text 349
6.6.3 Clipping in the Frame Buffer 349
6.7 Clipping in Three Dimensions 349
6.8 Rasterization 353
6.9 Bresenham's Algorithm 355
6.10 Polygon Rasterization 357
6.10.1 Inside-Outside Testing 357
6.10.2 OpenGL and Concave Polygons 359
6.10.3 Fill and Sort 359
6.10.4 Flood Fill 360
6.10.5 Singularities 360
6.11 Hidden-Surface Removal 361
6.11.1 Object-Space and Image-Space Approaches 361
6.11.2 Sorting and Hidden-Surface Removal 362
6.11.3 ScanlineAlgorithms 363
6.11.4 Back-Face Removal 364
6.11.5 The z-Buffer Algorithm 365
6.11.6 Scan Conversion with the z-Buffer 368
6.11.7 Depth Sort and the Painter's Algorithm 370
6.12 Antialiasing 372
6.13 Display Considerations 374
6.13.1 Color Systems 375
6.13.2 The Color Matrix 378
6.13.3 Gamma Correction 379
6.13.4 Dithering and Halftoning 379
Summary and Notes 380
Suggested Readings 382
Exercises 382
CHAPTER 7 DISCRETE TECHNIQUES 387
7.1 Buffers 387
7.2 Digital Images 389
7.3 Writing into Buffers 392
7.3.1 Writing Modes 393
7.3.2 Writing with XOR 395
7.4 Mapping Methods 396
7.5 Texture Mapping 398
7.5.1 Two-Dimensional Texture Mapping 398
7.6 Texture Mapping in OpenGL 404
7.6.1 Two-Dimensional Texture Mapping 405
7.6.2 Texture Objects 405
7.6.3 The Texture Array 406
7.6.4 Texture Coordinates and Samplers 406
7.6.5 Texture Sampling 412
7.6.6 Working with Texture Coordinates 414
7.6.7 Multitexturing 416
7.7 Texture Generation 417
7.8 Environment Maps 418
7.9 Reflection Map Example 423
7.10 Bump Mapping 426
7.10.1 Finding Bump Maps 427
7.10.2 Bump Map Example 430
7.11 Compositing Techniques 434
7.11.1 Opacity and Blending 434
7.11.2 Image Compositing 436
7.11.3 Blending and Compositing in OpenGL 436
7.11.4 Antialiasing Revisited 437
7.11.5 Back-to-Front and Front-to-Back Rendering 439
7.11.6 Scene Antialiasing and Multisampling 440
7.11.7 Image Processing 441
7.11.8 Other Multipass Methods 442
7.12 Sampling and Aliasing 443
7.12.1 Sampling Theory 443
7.12.2 Reconstruction 448
7.12.3 Quantization 450
Summary and Notes 451
Suggested Readings 452
Exercises 452
CHAPTER 8 MODELING AND HIERARCHY 455
8.1 Symbols and Instances 456
8.2 Hierarchical Models 457
8.3 A Robot Arm 459
8.4 Trees and Traversal 462
8.4.1 A Stack-Based Traversal 464
8.5 Use of Tree Data Structures 467
8.6 Animation 471
8.7 Graphical Objects 473
8.7.1 Methods,Attributes,and Messages 473
8.7.2 A Cube Object 475
8.7.3 Implementing the Cube Object 477
8.7.4 Objects and Hierarchy 477
8.7.5 Geometric Objects 478
8.8 Scene Graphs 479
8.9 Open Scene Graph 481
8.10 Graphics and the Internet 483
8.10.1 Hypermedia and HTML 483
8.10.2 Java and Applets 484
8.10.3 Interactive Graphics and the Web 484
8.10.4 WebGL 485
8.11 Other Tree Structures 485
8.11.1 CSG Trees 485
8.11.2 BSP Trees 487
8.11.3 Quadtrees and Octrees 489
Summary and Notes 491
Suggested Readings 491
Exercises 492
CHAPTER 9 PROCEDURAL METHODS 495
9.1 Algorithmic Models 495
9.2 Physically Based Models and Particle Systems 497
9.3 Newtonian Particles 498
9.3.1 Independent Particles 500
9.3.2 Spring Forces 501
9.3.3 Attractive and Repulsive Forces 502
9.4 Solving Particle Systems 503
9.5 Constraints 506
9.5.1 Collisions 506
9.5.2 Soft Constraints 509
9.6 A Simple Particle System 510
9.6.1 Displaying the Particles 510
9.6.2 Updating Particle Positions 511
9.6.3 Collisions 512
9.6.4 Forces 513
9.6.5 Flocking 513
9.7 Language-Based Models 514
9.8 Recursive Methods and Fractals 517
9.8.1 Rulers and Length 518
9.8.2 Fractal Dimension 519
9.8.3 Midpoint Division and Brownian Motion 520
9.8.4 Fractal Mountains 522
9.8.5 The Mandelbrot Set 523
9.9 Procedural Noise 526
Summary and Notes 530
Suggested Readings 531
Exercises 531
CHAPTER 10 CURVES AND SURFACES 533
10.1 Representation of Curves and Surfaces 533
10.1.1 Explicit Representation 533
10.1.2 Implicit Representations 535
10.1.3 Parametric Form 536
10.1.4 Parametric Polynomial Curves 537
10.1.5 Parametric Polynomial Surfaces 538
10.2 Design Criteria 539
10.3 Parametric Cubic Polynomial Curves 540
10.4 Interpolation 541
10.4.1 Blending Functions 543
10.4.2 The Cubic Interpolating Patch 545
10.5 Hermite Curves and Surfaces 547
10.5.1 The Hermite Form 547
10.5.2 Geometric and Parametric Continuity 549
10.6 Bézier Curves and Surfaces 550
10.6.1 Bézier Curves 551
10.6.2 Bezier Surface Patches 553
10.7 Cubic B-Splines 554
10.7.1 The Cubic B-Spline Curve 555
10.7.2 B-Splines and Basis 558
10.7.3 Spline Surfaces 558
10.8 General B-Splines 559
10.8.1 Recursively Defined B-Splines 560
10.8.2 Uniform Splines 562
10.8.3 Nonuniform B-Splines 562
10.8.4 NURBS 562
10.8.5 Catmull-Rom Splines 564
10.9 Rendering Curves and Surfaces 565
10.9.1 Polynomial Evaluation Methods 566
10.9.2 Recursive Subdivision of Bézier Polynomials 567
10.9.3 Rendering Other Polynomial Curves by Subdivision 570
10.9.4 Subdivision of Bézier Surfaces 571
10.10 The Utah Teapot 572
10.11 Algebraic Surfaces 575
10.11.1 Quadrics 575
10.11.2 Rendering of Surfaces by Ray Casting 576
10.12 Subdivision Curves and Surfaces 576
10.12.1 Mesh Subdivision 577
10.13 Mesh Generation from Data 580
10.13.1 Height Fields Revisited 581
10.13.2 Delaunay Triangulation 581
10.13.3 Point Clouds 585
Summary and Notes 586
Suggested Readings 586
Exercises 587
CHAPTER 11 ADVANCES RENDERING 589
11.1 Going Beyond Pipeline Rendering 589
11.2 Ray Tracing 590
11.3 Building a Simple Ray Tracer 594
11.3.1 Recursive Ray Tracing 594
11.3.2 Calculating Intersections 596
11.3.3 Ray-Tracing Variations 598
11.4 The Rendering Equation 599
11.5 Radiosity 601
11.5.1 The Radiosity Equation 602
11.5.2 Solving the Radiosity Equation 604
11.5.3 Computing Form Factors 605
11.5.4 Carrying Out Radiosity 607
11.6 RenderMan 608
11.7 Parallel Rendering 609
11.7.1 Sort-Middle Rendering 611
11.7.2 Sort-Last Rendering 613
11.7.3 Sort-First Rendering 616
11.8 Volume Rendering 618
11.8.1 Volumetric Data Sets 618
11.8.2 Visualization of Implicit Functions 619
11.9 Isosurfaces and Marching Cubes 621
11.10 Mesh Simplification 624
11.11 Direct Volume Rendering 625
11.11.1 Assignment of Color and Opacity 626
11.11.2 Splatting 626
11.11.3 Volume Ray Tracing 628
11.11.4 Texture Mapping of Volumes 629
11.12 Image-Based Rendering 630
11.12.1 A Simple Example 630
Summary and Notes 632
Suggested Readings 633
Exercises 634
APPENDIX A SAMPLE PROGRAMS 637
A.1 Shader Initialization Function 638
A.1.1 Application Code 638
A.2 Sierpinski Gasket Program 640
A.2.1 Application Code 640
A.2.2 Vertex Shader 642
A.2.3 Fragment Shader 642
A.3 Recursive Generation of Sierpinski Gasket 643
A.3.1 Application Code 643
A.3.2 Vertex Shader 645
A.3.3 Fragment Shader 645
A.4 Rotating Cube with Rotation in Shader 645
A.4.1 Application Code 645
A.4.2 Vertex Shader 650
A.4.3 Fragment Shader 650
A.5 Perspective Projection 651
A.5.1 Application Code 651
A.5.2 Vertex Shader 655
A.5.3 Fragment Shader 656
A.6 Rotating Shaded Cube 656
A.6.1 Application Code 656
A.6.2 Vertex Shader 661
A.6.3 Fragment Shader 662
A.7 Per-Fragment Lighting of Sphere Model 662
A.7.1 Application Code 662
A.7.2 Vertex Shader 667
A.7.3 Fragment Shader 668
A.8 Rotating Cube with Texture 668
A.8.1 Application Code 668
A.8.2 Vertex Shader 674
A.8.3 Fragment Shader 675
A.9 Figure with Tree Traversal 676
A.9.1 Application Code 676
A.9.2 Vertex Shader 689
A.9.3 Fragment Shader 689
A.10 Teapot Renderer 689
A.10.1 Application Code 689
A.10.2 Vertex Shader 694
A.10.3 Fragment Shader 694
APPENDIX B SPACES 695
B.1 Scalars 695
B.2 Vector Spaces 696
B.3 Affine Spaces 698
B.4 Euclidean Spaces 699
B.5 Projections 700
B.6 Gram-Schmidt Orthogonalization 701
Suggested Readings 702
Exercises 703
APPENDIX C MATRICES 705
C.1 Definitions 705
C.2 Matrix Operations 706
C.3 Row and Column Matrices 707
C.4 Rank 708
C.5 Change of Representation 709
C.6 The Cross Product 711
C.7 Eigenvalues and Eigenvectors 712
C.8 Vector and Matrix Classes 713
Suggested Readings 714
Exercises 714
APPENDIX D SYNOPSIS OF OPENGL FUNCTIONS 717
D.1 Initialization and Window Functions 717
D.2 Vertex Buffer Objects 719
D.3 Interaction 720
D.4 Setting Attributes and Enabling Features 722
D.5 Texture and Image Functions 723
D.6 State and Buffer Manipulation 724
D.7 Query Functions 724
D.8 GLSL Functions 725
References 729
OpenGL Function Index 739
Subject Index 741