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 Output Devices 7
1.2.3 Input Devices 9
1.3 Images: Physical and Synthetic 9
1.3.1 Objects and Viewers 9
1.3.2 Light and Images 11
1.3.3 Ray Tracing 13
1.4 The Human Visual System 15
1.5 The Pinhole Camera 17
1.6 The Synthetic-Camera Model 19
1.7 The Programmer's Interface 21
1.7.1 Application Programmer's Interfaces 22
1.7.2 The Pen-Plotter Model 22
1.7.3 Three-Dimensional APIs 24
1.7.4 A Sequence of Images 26
1.7.5 The Modeling-Rendering Paradigm 27
1.8 Graphics Architectures 28
1.8.1 Display Processors 29
1.8.2 Pipeline Architectures 29
1.8.3 Transformations 31
1.8.4 Clipping 31
1.8.5 Projection 32
1.8.6 Rasterization 32
1.8.7 Performance Characteristics 32
1.9 Summary and Notes 33
1.10 Suggested Readings 34
Exercises 35
CHAPTER 2 Graphics Programming 37
2.1 The Sierpinski Gasket 37
2.2 Programming Two-Dimensional Applications 39
2.2.1 Coordinate Systems 44
2.3 The OpenGL API 44
2.3.1 Graphics Functions 44
2.3.2 The Graphics Pipeline and State Machines 46
2.3.3 The OpenGL Interface 46
2.4 Primitives and Attributes 47
2.4.1 Polygon Basics 50
2.4.2 Polygon Types in OpenGL 51
2.4.3 Drawing a Sphere 52
2.4.4 Text 53
2.4.5 Curved Objects 55
2.4.6 Attributes 56
2.5 Color 57
2.5.1 RGB Color 61
2.5.2 Indexed Color 63
2.5.3 Setting of Color Attributes 64
2.6 Viewing 65
2.6.1 Two-Dimensional Viewing 66
2.6.2 The Orthographic View 67
2.6.3 Matrix Modes 68
2.7 Control Functions 68
2.7.1 Interaction with the Window System 69
2.7.2 Aspect Ratio and Viewports 70
2.7.3 The main,display,and myinit Functions 72
2.7.4 Program Structure 73
2.8 The Gasket Program 74
2.9 Polygons and Recursion 75
2.10 The Three-Dimensional Gasket 77
2.10.1 Use of Three-Dimensional Points 78
2.10.2 Use of Polygons in Three Dimensions 79
2.10.3 Hidden-Surface Removal 81
2.11 Summary and Notes 82
2.12 Suggested Readings 84
Exercises 85
CHAPTER 3 Input and Interaction 89
3.1 Interaction 89
3.2 Input Devices 90
3.2.1 Physical Input Devices 91
3.2.2 Logical Devices 94
3.2.3 Measure and Trigger 95
3.2.4 Input Modes 95
3.3 Clients and Servers 97
3.4 Display Lists 98
3.4.1 Definition and Execution of Display Lists 100
3.4.2 Text and Display Lists 102
3.4.3 Fonts in GLUT 105
3.5 Programming Event-Driven Input 106
3.5.1 Using the Pointing Device 106
3.5.2 Window Events 110
3.5.3 Keyboard Events 111
3.5.4 The Display and Idle Callbacks 112
3.5.5 Window Management 113
3.6 Menus 113
3.7 Picking 114
3.7.1 Picking and Selection Mode 116
3.8 A Simple Paint Program 121
3.9 Animating Interactive Programs 127
3.9.1 The Rotating Square 127
3.9.2 Double Buffering 129
3.9.3 Other Buffering Problems 130
3.10 Design of Interactive Programs 132
3.10.1 Toolkits,Widgets,and the Frame Buffer 132
3.11 Logic Operations 133
3.11.1 Drawing Erasable Lines 135
3.11.2 XORand Color 137
3.11.3 Cursors and Overlay Planes 137
3.12 Summary and Notes 138
3.13 Suggested Readings 139
Exercises 140
CHAPTER 4 Geometric Objects and Transforrnations 143
4.1 Scalars,Points,and Vectors 144
4.1.1 The Geometric View 144
4.1.2 Coordinate-Free Geometry 146
4.1.3 The Mathematical View:Vector and Affine Spaces 146
4.1.4 The Computer-Science View 147
4.1.5 Geometric ADTs 148
4.1.6 Lines 149
4.1.7 Affine Sums 149
4.1.8 Convexity 150
4.1.9 Dot and Cross Products 150
4.1.10 Planes 151
4.2 Three-Dimensional Primitives 152
4.3 Coordinate Systems and Frames 154
4.3.1 Representations and N-tuples 156
4.3.2 Changes of Coordinate Systems 157
4.3.3 Example of Change of Representation 159
4.3.4 Homogeneous Coordinates 160
4.3.5 Example of Change in Frames 163
4.3.6 Working with Representations 165
4.3.7 Frames and ADTs 166
4.3.8 Frames in OpenGL 168
4.4 Modeling a Colored Cube 171
4.4.1 Modeling of a Cube 172
4.4.2 Inward- and Outward-Pointing Faces 173
4.4.3 Data Structures for Object Representation 173
4.4.4 The Color Cube 174
4.4.5 Bilinear Interpolation 175
4.4.6 Vertex Arrays 176
4.5 Affine Transformations 179
4.6 Translation,Rotation,and Scaling 181
4.6.1 Translation 182
4.6.2 Rotation 182
4.6.3 Scaling 184
4.7 Transformations in Homogeneous Coordinates 184
4.7.1 Translation 184
4.7.2 Scaling 185
4.7.3 Rotation 186
4.7.4 Shear 188
4.8 Concatenation of Transformations 189
4.8.1 Rotation About a Fixed Point 190
4.8.2 General Rotation 191
4.8.3 The Instance Transformation 192
4.8.4 Rotation About an Arbitrary Axis 193
4.9 OpenGL Transformation Matrices 196
4.9.1 The Current Transformation Matrix 197
4.9.2 Rotation,Translation,and Scaling 198
4.9.3 Rotation About a Fixed Point in OpenGL 199
4.9.4 Order of Transformations 199
4.9.5 Spinning of the Cube 200
4.9.6 Loading,Pushing,and Popping Matrices 201
4.10 Interfaces to Three-Dimensional Applications 202
4.10.1 UsingAreas of the Screen 203
4.10.2 AVirtual Trackball 203
4.10.3 Smooth Rotations 206
4.10.4 Incremental Rotation 207
4.11 Quaternions 208
4.11.1 Complex Numbers and Quaternions 208
4.11.2 Quaternions and Rotation 209
4.12 Summary and Notes 211
4.13 Suggested Readings 212
Exercises 213
CHAPTER 5 Viewing 217
5.1 Classical and Computer Viewing 217
5.1.1 Classical Viewing 219
5.1.2 Orthographic Projections 220
5.1.3 Axonometric Projections 221
5.1.4 Oblique Projections 222
5.1.5 Perspective Viewing 223
5.2 Viewing with a Computer 225
5.3 Positioning of the Camera 226
5.3.1 Positioning of the Camera Frame 226
5.3.2 Two Viewing APIs 231
5.3.3 The Look-At Function 234
5.3.4 Other Viewing APIs 235
5.4 Simple Projections 236
5.4.1 Perspective Projections 236
5.4.2 Orthogonal Projections 239
5.5 Projections in OpenGL 240
5.5.1 Perspective in OpenGL 241
5.5.2 Parallel Viewing in OpenGL 243
5.6 Hidden-Surface Removal 244
5.6.1 Culling 246
5.7 Walking Through a Scene 247
5.8 Parallel-Projection Matrices 248
5.8.1 Projection Normalization 249
5.8.2 Orthogonal-Projection Matrices 249
5.8.3 Oblique Projections 252
5.9 Perspective-Projection Matrices 255
5.9.1 Perspective Normalization 256
5.9.2 OpenGL Perspective Transformations 259
5.10 Projections and Shadows 261
5.11 Summary and Notes 264
5.12 Suggested Readings 265
Exercises 265
CHAPTER 6 Shading 267
6.1 Light and Matter 267
6.2 Light Sources 271
6.2.1 Color Sources 272
6.2.2 Ambient Light 272
6.2.3 Point Sources 273
6.2.4 Spotlights 274
6.2.5 Distant Light Sources 274
6.3 The Phong Reflection Model 275
6.3.1 Ambient Reflection 277
6.3.2 Diffuse Reflection 277
6.3.3 Specular Reflection 278
6.4 Computation of Vectors 280
6.4.1 Normal Vectors 281
6.4.2 Angle of Reflection 283
6.4.3 Use of the Halfway Vector 284
6.4.4 Transmitted Light 285
6.5 Polygonal Shading 286
6.5.1 Flat Shading 286
6.5.2 Interpolative and Gouraud Shading 288
6.5.3 Phong Shading 290
6.6 Approximation of a Sphere by Recursive Subdivision 291
6.7 Light Sources in OpenGL 294
6.8 Specification of Materials in OpenGL 296
6.9 Shading of the Sphere Model 298
6.10 Global Rendering 299
6.11 Summary and Notes 301
6.12 Suggested Readings 302
Exercises 302
CHAPTER 7 Discrete Techniques 305
7.1 Buffers 305
7.2 Digital Images 307
7.3 Writing into Buffers 310
7.3.1 Writing Modes 311
7.3.2 Writing with XOR 313
7.4 Bit and Pixel Operations in OpenGL 314
7.4.1 OpenGL Buffers and the Pixel Pipeline 314
7.4.2 Bitmaps 316
7.4.3 Raster Fonts 317
7.4.4 Pixels and Images 318
7.4.5 Lookup Tables 319
7.4.6 Buffers for Picking 321
7.5 Mapping Methods 321
7.6 Texture Mapping 323
7.6.1 Two-Dimensional Texture Mapping 323
7.6.2 Texture Mapping in OpenGL 330
7.6.3 Texture Objects 337
7.6.4 Multitexturing 337
7.6.5 Texture Generation 337
7.7 Environmental Maps 338
7.8 Bump Maps 341
7.9 Compositing Techniques 343
7.9.1 Opacity and Blending 343
7.9.2 Image Compositing 345
7.9.3 Blending and Compositing in OpenGL 345
7.9.4 Antialiasing 346
7.9.5 Back-to-Front and Front-to-Back Rendering 348
7.9.6 Depth Cueing and Fog 349
7.10 Multirendering and the Accumulation Buffer 350
7.10.1 Scene Antialiasing 351
7.10.2 Bump Mapping and Embossing 351
7.10.3 Image Processing 352
7.10.4 Imaging Extensions 353
7.10.5 Other Multipass Methods 354
7.11 Sampling and Aliasing 355
7.11.1 Sampling Theory 355
7.11.2 Reconstruction 360
7.11.3 Quantization 362
7.12 Summary and Notes 363
7.13 Suggested Readings 363
Exercises 364
CHAPTER 8 Implementation of a Renderer 367
8.1 Basic Implementation Strategies 367
8.2 Four Major Tasks 370
8.2.1 Modeling 370
8.2.2 Geometric Processing 370
8.2.3 Rasterization 371
8.2.4 Display 372
8.3 Implementation of Transformations 372
8.4 Line-Segment Clipping 374
8.4.1 Cohen-Sutherland Clipping 375
8.4.2 Liang-Barsky Clipping 377
8.5 Polygon Clipping 379
8.6 Clipping of Other Primitives 382
8.6.1 Bounding Boxes and Volumes 382
8.6.2 Curves,Surfaces,and Text 383
8.6.3 Clipping in the Frame Buffer 384
8.7 Clipping in Three Dimensions 384
8.8 Hidden-Surface Removal 388
8.8.1 Object-Space and Image-Space Approaches 388
8.8.2 Sorting and Hidden-Surface Removal 390
8.8.3 Back-Face Removal 390
8.8.4 The z-Buffer Algorithm 391
8.8.5 Depth Sort and the Painter's Algorithm 393
8.8.6 The Scan-Line Algorithm 396
8.9 Scan Conversion 397
8.10 Bresenham's Algorithm 399
8.11 Scan Conversion of Polygons 401
8.11.1 Inside-Outside Testing 401
8.11.2 OpenGL and Concave Polygons 403
8.11.3 Scan Conversion with the z Buffer 404
8.11.4 Fill and Sort 405
8.11.5 Flood Fill 406
8.11.6 Scan-Line Algorithms 406
8.11.7 Singularities 407
8.12 Antialiasing 408
8.13 Display Considerations 410
8.13.1 Color Systems 410
8.13.2 The Color Matrix 413
8.13.3 Gamma Correction 414
8.13.4 Dithering and Halftoning 415
8.14 Summary and Notes 416
8.15 References 417
Exercises 418
CHAPTER 9 Hierarchical and Object-Oriented Modeling 421
9.1 Symbols and Instances 422
9.2 Hierarchical Models 423
9.3 A Robot Arm 425
9.4 Trees and Traversal 428
9.4.1 A Stack-Based Traversal 429
9.5 Use of Tree Data Structures 431
9.6 Animation 435
9.7 Graphical Objects 437
9.7.1 Methods,Attributes,and Messages 438
9.7.2 A Cube Object 439
9.7.3 Implementing the Cube Object 442
9.7.4 Objects and Hierarchy 442
9.7.5 Geometric Objects 443
9.8 Scene Graphs 444
9.9 A Simple Scene Graph API 446
9.9.1 The Node Class 447
9.9.2 Geometry Nodes 448
9.9.3 Camera Class 451
9.9.4 Lights and Materials 451
9.9.5 Transformations 453
9.9.6 The Robot Figure 454
9.9.7 Implementing the Viewer 456
9.9.8 Implementing a Node 459
9.10 Other Tree Structures 463
9.10.1 CSG Trees 463
9.10.2 Shade Trees 464
9.10.3 BSP Trees 466
9.10.4 Quadtrees and Octrees 468
9.11 Graphics and the Web 469
9.11.1 Networks and Protocols 470
9.11.2 Hypermedia and HTML 471
9.11.3 Databases and VRML 472
9.11.4 Java and Applets 473
9.12 Summary and Notes 473
9.13 Suggested Readings 474
Exercises 474
CHAPTER 10 Curves and Surfaces 477
10.1 Representation of Curves and Surfaces 477
10.1.1 Explicit Representation 477
10.1.2 Implicit Representations 479
10.1.3 Parametric Form 480
10.1.4 Parametric Polynomial Curves 481
10.1.5 Parametric Polynomial Surfaces 482
10.2 Design Criteria 483
10.3 Parametric Cubic Polynomial Curves 484
10.4 Interpolation 485
10.4.1 Blending Functions 487
10.4.2 The Cubic Interpolating Patch 489
10.5 Hermite Curves and Surfaces 491
10.5.1 The Hermite Form 491
10.5.2 Geometric and Parametric Continuity 493
10.6 Bezier Curves and Surfaces 494
10.6.1 Bezier Curves 494
10.6.2 Bezier Surface Patches 497
10.7 Cubic B-Splines 498
10.7.1 The Cubic B-Spline Curve 498
10.7.2 B-Splines and Bases 501
10.7.3 Spline Surfaces 502
10.8 General B-Splines 503
10.8.1 Recursively Defined B-Splines 504
10.8.2 Uniform Splines 505
10.8.3 Nonuniform B-Splines 506
10.8.4 NURBS 506
10.9 Rendering of Curves and Surfaces 507
10.9.1 Polynomial Evaluation Methods 508
10.9.2 Recursive Subdivision of Bezier Polynomials 509
10.9.3 Rendering of Other Polynomial Curves by Subdivision 512
10.9.4 Subdivision of Bezier Surfaces 512
10.10 The Utah Teapot 513
10.11 Algebraic Surfaces 516
10.11.1 Quadrics 516
10.11.2 Rendering of Surfaces by Ray Casting 517
10.11.3 Subdivision Curves and Surfaces 517
10.12 Curves and Surfaces in OpenGL 520
10.12.1 Bezier Curves 520
10.12.2 Bezier Surfaces 521
10.12.3 Displaying the Teapot 522
10.12.4 NURBS Functions 524
10.12.5 Quadrics 524
10.13 Summary and Notes 525
10.14 References and Notes 526
Exercises 526
CHAPTER 11 Procedural Methods 529
11.1 Reasons for Using Procedural Models 529
11.2 Physically Based Models and Particle Systems 531
11.3 Newtonian Particles 532
11.3.1 Independent Particles 534
11.3.2 Spring Forces 534
11.3.3 Attractive and Repulsive Forces 536
11.4 Solving Particle Systems 537
11.5 Constraints 540
11.5.1 Collisions 540
11.5.2 Particles Inside a Sphere 543
11.5.3 Soft Constraints 544
11.6 Language-Based Models 545
11.7 Recursive Methods and Fractals 548
11.7.1 Rulers and Length 549
11.7.2 Fractal Dimension 550
11.7.3 Midpoint Division and Brownian Motion 551
11.7.4 Fractal Mountains 553
11.8 The Mandelbrot Set 554
11.9 Summary and Notes 556
11.10 Suggested Readings 557
Exercises 557
CHAPTER 12 Visualization 559
12.1 Data+Geometry 559
12.2 Height Fields and Contours 560
12.2.1 Meshes 561
12.2.2 Contour Plots 563
12.2.3 Marching Squares 564
12.3 Visualizing Surfaces and Scalar Fields 570
12.3.1 Volumetric Data Sets 571
12.3.2 Visualization of Implicit Functions 572
12.4 Isosurfaces and Marching Cubes 574
12.5 Mesh Simplification 578
12.6 Direct Volume Rendering 578
12.6.1 Assignment of Color and Opacity 579
12.6.2 Splatting 580
12.6.3 Volume Ray Tracing 582
12.6.4 Texture Mapping of Volumes 583
12.7 Vector-Field Visualization 584
12.7.1 Hedgehogs 584
12.7.2 Glyphs 585
12.7.3 Color 585
12.7.4 Particle Traces and Streamlines 586
12.8 Tensor Visualization 589
12.9 Summary and Notes 591
12.10 Suggested Readings 591
Exercises 592
CHAPTER 13 Advanced Rendering 595
13.1 Going Beyond Pipeline Rendering 595
13.2 Ray Tracing 596
13.3 Building a Simple Ray Tracer 599
13.3.1 Recursive Ray Tracing 600
13.3.2 Calculating Intersections 601
13.3.3 Ray-Tracing Variations 604
13.4 The Rendering Equation 605
13.5 Radiosity 607
13.5.1 The Radiosity Equation 607
13.5.2 Solving the Radiosity Equation 609
13.5.3 Computing Form Factors 610
13.5.4 Carrying Out Radiosity 613
13.6 RenderMan 614
13.7 Large-Scale Rendering 615
13.7.1 Sort-Middle Rendering 616
13.7.2 Sort-Last Rendering 617
13.7.3 Sort-First Rendering 620
13.8 Image-Based Rendering 621
13.8.1 A Simple Example 622
13.9 Summary and Notes 624
13.10 Suggested Readings 625
Exercises 625
APPENDIX A Sample Programs 629
A.1 Sierpinski Gasket Program 630
A.2 Recursive Generation of Sierpinski Gasket 632
A.3 Three-Dimensional Sierpinski Gasket 633
A.4 Recursive Three-Dimensional Sierpinski Gasket 635
A.5 Square Drawing Program 637
A.6 Paint Program 640
A.7 Double-Buffering Example 647
A.8 Selection-Mode Picking Program 649
A.9 Rotating-Cube Program 652
A.10 Rotating Cube Using Vertex Arrays 655
A.11 Rotating Cube with a Virtual Trackball 657
A.12 Moving Viewer 661
A.13 Sphere Program 664
A.14 Pixel-Reading Program 668
A.15 Rotating Cube with Texture 669
A.16 Scene-Graph Example 672
A.17 Program for Drawing Bezier Curves 677
APPENDIX B Spaces 681
B.1 Scalars 681
B.2 Vector Spaces 682
B.3 Affine Spaces 684
B.4 Euclidean Spaces 685
B.5 Projections 686
B.6 Gram-Schmidt Orthogonalization 687
B.7 Suggested Readings 688
Exercises 688
APPENDIX C Matrices 689
C.1 Definitions 689
C.2 Matrix Operations 690
C.3 Row and Column Matrices 691
C.4 Rank 692
C.5 Change of Representation 693
C.6 The Cross Product 695
C.7 Eigenvalues and Eigenvectors 696
C.8 Suggested Readings 697
Exercises 698
References 699
Function Index 707
Subject Index 709