1 A Survey of Computer Graphics 2
1-1 Computer-Aided Design 4
1-2 Presentation Graphics 11
1-3 Computer Art 13
1-4 Entertainment 18
1-5 Education and Training 21
1-6 Visualization 25
1-7 Image Processing 32
1-8 Graphical User Interfaces 34
2 Overview of Graphics Systems 35
2-1 Video Display Devices 36
Refresh Cathode-Ray Tubes 37
Raster-Scan Displays 40
Random-Scan Displays 41
Color CRT Monitors 42
Direct-View Storage Tubes 45
Flat-Panel Displays 45
Three-Dimensional Viewing Devices 49
Stereoscopic and Virtual-Reality Systems 50
2-2 Raster-Scan Systems 53
Video Controller 53
Raster-Scan Display Processor 55
2-3 Random-Scan Systems 56
2-4 Graphics Monitors and Workstations 57
2-5 Input Devices 60
Keyboards 61
Mouse 61
Joysticks 63
Trackball and Spaceball 63
Data Glove 64
Digitizers 64
Image Scanners 67
Touch Panels 68
Light Pens 70
Voice Systems 70
2-6 Hard-Copy Devices 72
2-7 Graphics Software 75
Coordinate Representations 76
Graphics Functions 77
Software Standards 78
PHIGS Workstations 79
Summary 79
Exercises 81
References 81
3 Output Primitives 83
3-1 Points and Lines 84
3-2 Line-Drawing Algorithms 86
DDA Algorithm 87
Bresenham s Line Algorithm 88
Parallel Line Algorithms 92
3-3 Loading the Frame Buffer 94
3-4 Line Function 95
3-5 Circle-Generating Algorithms 97
Properties of Circles 97
Midpoint Circle Algorithm 98
3-6 Ellipse-Generating Algorithms 102
Properties of Ellipses 102
Midpoint Ellipse Algorithm 103
3-7 Other Curves 110
Conic Sections 110
Polynomials and Spline Curves 112
3-8 Parallel Curve Algorithms 112
3-9 Curve Functions 113
3-10 Pixel Addressing and Object Geometry 114
Screen Grid Coordinates 114
Maintaining Geometric Properties of Displayed Objects 114
3-11 Filled-Area Primitives 117
Scan-Line Polygon Fill Algorithm 117
Inside-Outside Tests 125
Scan-Line Fill of Curved Boundary Areas 126
Boundary-Fill Algorithm 127
Flood-Fill Algorithm 130
3-12 Fill-Area Functions 131
3-13 Cell Array 131
3-14 Character Generation 131
Summary 134
Applications 136
References 140
Exercises 140
4 Attributes of Output Primitives 143
4-1 Line Attributes 144
Line Type 144
Line Width 146
Pen and Brush Options 149
Line Color 149
4-2 Curve Attributes 152
4-3 Color and Grayscale Levels 154
Color Tables 155
Grayscale 157
4-4 Area-Fill Attributes 158
Fill Styles 158
Pattern Fill 159
Soft Fill 162
4-5 Character Attributes 163
Text Attributes 163
Marker Attributes 167
4-6 Bundled Attributes 168
Bundled Line Attributes 168
Bundled Area-Fill Attributes 169
Bundled Text Attributes 169
4-7 Inquiry Functions 170
Bundled Marker Attributes 170
4-8 Antialiasing 171
Supersampling Straight Line Segments 172
Pixel-Weighting Masks 174
Area Sampling Straight Line Segments 174
Filtering Techniques 174
Pixel Phasing 175
Compensating for Line Intensity Differences 175
Antialiasing Area Boundaries 176
Summary 178
References 180
Exercises 180
5 Two-Dimensional Geometric Transformations 183
5-1 Basic Transformations 184
Translation 184
Rotation 186
Scaling 187
5-2 Matrix Representations and Homogeneous Coordinates 188
5-3 Composite Transformations 191
Translations 191
Rotations 191
Scalings 192
General Pivot-Point Rotation 192
General Fixed-Point Scaling 193
General Scaling Directions 193
Concatenation Properties 194
General Composite Transformations and Computational Efficiency 195
5-4 Other Transformations 201
Reflection 201
Shear 203
5-5 Transformations Between Coordinate Systems 205
5-6 Affine Transformations 208
5-7 Transformation Functions 208
5-8 Raster Methods for Transformations 210
Summary 212
References 213
Exercises 213
6 Two-Dimensional Viewing 216
6-1 The Viewing Pipeline 217
6-2 Viewing Coordinate Reference Frame 219
6-3 Window-to-Viewport Coordinate Transformation 220
6-4 Two-Dimensional Viewing Functions 222
6-5 Clipping Operations 224
6-7 Line Clipping 225
6-6 Point Clipping 225
Cohen-Sutherland Line Clipping 226
Liang-Barsky Line Clipping 230
Nicholl-Lee-Nicholl Line Clipping 233
Line Clipping Using Nonrectangular Clip Windows 235
Splitting Concave Polygons 235
6-8 Polygon Clipping 237
Sutherland-Hodgeman Polygon Clipping 238
Weiler-Atherton Polygon Clipping 242
Other Polygon-Clipping Algorithms 243
6-9 Curve Clipping 244
6-10 Text Clipping 244
6-11 Exterior Clipping 245
Summary 245
Exercises 248
References 248
7 Structures and Hierarchical Modeling 250
7-1 Structure Concepts 250
Basic Structure Functions 250
Setting Structure Attributes 253
7-2 Editing Structures 254
Structure Lists and the Element Pointer 255
Setting the Edit Mode 256
Inserting Structure Elements 256
Replacing Structure Elements 257
Deleting Structure Elements 257
Labeling Structure Elements 258
Copying Elements from One Structure to Another 260
7-3 Basic Modeling Concepts 260
Model Representations 261
Symbol Hierarchies 262
Modeling Packages 263
7-4 Hierarchical Modeling with Structures 265
Local Coordinates and Modeling Transformations 265
Modeling Transformations 266
Structure Hierarchies 266
Summary 268
References 269
Exercises 269
8 Graphical User Interfaces and Interactive Input Methods 271
8-1 The User Dialogue 272
Windows and Icons 273
Accommodating Multiple Skill Levels 273
Backup and Error Handling 274
Consistency 274
Minimizing Memorization 274
Feedback 275
8-2 Input of Graphical Data 276
Logical Classification of Input Devices 276
Locator Devices 277
Stroke Devices 277
String Devices 277
Valuator Devices 277
Choice Devices 279
Pick Devices 279
8-3 Input Functions 281
Input Modes 281
Locator and Stroke Input in Request Mode 282
Request Mode 282
String Input in Request Mode 283
Valuator Input in Request Mode 284
Choice Input in Request Mode 284
Pick Input in Request Mode 284
Sample Mode 285
Event Mode 285
Concurrent Use of Input Modes 287
8-4 Initial Values for Input-Device Parameters 287
8-5 Interactive Picture-Construction Techniques 288
Basic Positioning Methods 288
Constraints 288
Grids 289
Rubber-Band Methods 290
Gravity Field 290
Dragging 291
Painting and Drawing 291
8-6 Virtual-Reality Environments 292
Summary 293
References 294
Exercises 294
9 Three-Dimensional Concepts 296
9-1 Three-Dimensional Display Methods 297
Parallel Projection 298
Perspective Projection 299
Depth Cueing 299
Visible Line and Surface Identification 300
Surface Rendering 300
Exploded and Cutaway Views 300
Three-Dimensional and Stereoscopic Views 300
9-2 Three-Dimensional Graphics Packages 302
10 Three-Dimensional Object Representations 304
10-1 Polygon Surfaces 305
Polygon Tables 306
Plane Equations 307
Polygon Meshes 309
10-2 Curved Lines and Surfaces 310
10-3 Quadric Surfaces 310
Sphere 311
Ellipsoid 311
Torus 311
10-4 Superquadrics 312
Superellipse 312
Superellipsoid 313
10-5 Blobby Objects 314
10-6 Spline Representations 315
Interpolation and Approximation Splines 316
Parametric Continuity Conditions 317
Geometric Continuity Conditions 318
Spline Specifications 319
10-7 Cubic Spline Interpolation Methods 320
Natural Cubic Splines 321
Hermite Interpolation 322
Cardinal Splines 323
Kochanek-Bartels Splines 325
10-8 Bézier Curves and Surfaces 327
Bézier Curves 327
Properties of Bézier Curves 329
Design Techniques Using Bézier Curves 330
Cubic Bézier Curves 331
Bézier Surfaces 333
10-9 B-Spline Curves and Surfaces 334
B-Spline Curves 335
Uniform,Periodic B-Splines 336
Cubic,Periodic B-Splines 339
Open,Uniform B-Splines 341
Nonuniform B-Splines 344
B-Spline Surfaces 344
10-10 Beta-Splines 345
Beta-Spline Continuity Conditions 345
Cubic,Periodic Beta-Spline Matrix Representation 346
10-11 Rational Splines 347
10-12 Conversion Between Spline Representations 349
Forward-Difference Calculations 351
10-13 Displaying Spline Curves and Surfaces 351
Horner s Rule 351
Subdivision Methods 353
10-14 Sweep Representations 355
10-15 Constructive Solid-Geometry Methods 356
10-16 Octrees 359
10-17 BSP Trees 362
10-18 Fractal Ceometry Methods 362
Fractal-Generation Procedures 363
Classification of Fractals 364
Fractal Dimension 364
Geometric Construction of Deterministic Self-Similar Fractals 367
Geometric Construction of Statistically Self-Similar Fractals 369
Affine Fractal-Construction Methods 372
Random Midpoint-Displacement Methods 373
Controlling Terrain Topography 376
Self-Squaring Fractals 378
Self-Inverse Fractals 385
10-19 Shape Grammars and Other Procedural Methods 387
10-20 Particle Systems 390
10-21 Physically Based Modeling 393
10-22 Visualization of Data Sets 395
Visual Representations for Scalar Fields 395
Visual Representations for Vector Fields 400
Visual Representations for Tensor Fields 401
Visual Representations for Multivariate Data Fields 402
References 404
Exercises 404
Summary 404
11 Three-Dimensional Geometric and Modeling Transformations 407
11-1 Translation 408
11-2 Rotation 409
Coordinate-Axes Rotations 409
General Three-Dimensional Rotations 413
Rotations with Quaternions 419
11-3 Scaling 420
11-4 Other Transforrnations 422
Reflections 422
Shears 423
11-5 Composite Transformations 423
11-6 Three-Dimensional Transformation Functions 425
11-7 Modeling and CoordinateTransformations 426
References 429
Summary 429
Exercises 430
12 Three-Dimensional Viewing 431
12-1 Viewing Pipeline 432
12-2 Viewing Coordinates 433
Specifying the View Plane 433
Transformation from World to Viewing Coordinates 437
12-3 Projections 438
Parallel Projections 439
Perspective Projections 443
12-4 View Volumes and General Projection Transformations 447
General Parallel-Projection Transformations 452
General Perspective-Projection Transformations 454
12-5 Clipping 456
Normalized View Volumes 458
Viewport Clipping 460
Clipping in Homogeneous Coordinates 461
12-6 Hardware Implementations 463
12-7 Three-Dimensional Viewing Functions 464
Summary 467
References 468
Exercises 468
13 Visible-Surface Detection Methods 469
13-1 Classification of Visible-Surface Detection Algorithms 470
13-2 Back-Face Detection 471
13-3 Depth-Buffer Method 472
13-4 A-Buffer Method 475
13-5 Scan-Line Method 476
13-6 Depth-Sorting Method 478
13-7 BSP-Tree Method 481
13-8 Area-Subdivision Method 482
13-9 Octree Methods 485
13-10 Ray-Casting Method 487
13-11 Curved Surfaces 488
Curved-Surface Representations 488
Surface Contour Plots 489
13-12 Wireframe Methods 490
13-13 Visibility-Detection Functions 490
Summary 491
References 492
Exercises 492
14 Illumination Models and Surface-Rendering Methods 494
14-1 Ligth Sources 496
Ambient Light 497
Diffuse Reflection 497
14-2 Basic Illumination Models 497
Specular Reflection and the Phong Model 500
Combined Diffuse and Specular Reflections with Multiple Light Sources 504
Warn Model 504
Intensity Attenuation 505
Color Considerations 507
Transparency 508
Shadows 511
14-3 Displaying Light Intensities 511
Assigning Intensity Levels 512
Gamma Correction and Video Lookup Tables 513
Displaying Continuous-Tone Images 515
14-4 Halftone Patterns and Dithering Techniques 516
Halftone Approximations 516
Dithering Techniques 519
Constant-Intensity Shading 522
14-5 Polygon-Rendering Methods 522
Gouraud Shading 523
Phong Shading 525
Fast Phong Shading 526
14-6 Ray-Tracing Methods 527
Basic Ray-Tracing Algorithm 528
Ray-Surface Intersection Calculations 531
Reducing Object-Intersection Calculations 535
Space-Subdivision Methods 535
Antialiased Ray Tracing 538
Distributed Ray Tracing 540
14-7 Radiosity Lighting Model 544
Basic Radiosity Model 544
Radiosty Method 549
Progressive Refinement Radiosity Method 549
14-8 Environment Mapping 552
14-9 Adding Surface Detail 553
Modeling Surface Detail with Polygons 553
Texture Mapping 554
Procedural Texturing Methods 556
Bump Mapping 558
Frame Mapping 559
Summary 560
References 561
Exercises 562
15 Color Models and Color Applications 564
15-1 Properties of Light 565
15-2 Standard Primaries and the Chromaticity Diagram 568
CIE Chromaticity Diagram 569
XYZ Color Model 569
15-3 Intuitive Color Concepts 571
15-4 RGB Color Model 572
15-5 YIQ Color Model 574
15-6 CMY Color Model 574
15-7 HSV Color Model 575
15-9 Conversion Between HSV and RGB Models 578
15-9 HLS Color Model 579
15-10 Color Selection and Applications 580
Summary 581
References 581
Exercises 582
16 Computer Animation 583
16-1 Design of Animation Sequences 584
16-3 Raster Animations 586
16-2 General Computer-Animation Functions 586
16-4 Computer-Animation Languages 587
16-5 Key-Frame Systems 588
Morphing 588
Simulating Accelerations 591
16-6 Motion Specifications 594
Direct Motion Specification 594
Goal-Directed Systems 595
Kinematics and Dynamics 595
Summary 596
References 597
Exercises 597
A Mathematics for Computer Graphics 599
Two-Dimensional Cartesian Reference Frames 600
A-1 Coordinate -Reference Frames 600
Polar Coordinates in the xy Plane 601
Three-Dimensional Cartesian Reference Frames 602
Three-Dimensional Curvilinear Coodinate Systems 602
Solid Angle 604
A-2 Points and Vectors 605
Vector Addition and Scalar Multiplication 607
Scalar Product of Two Vectors 607
Vector Product of Two Vectors 608
A-3 Basis Vectors and the Metric Tensor 609
Orthonormal Basis 609
Metric Tensor 610
A-4 Matrices 611
Matrix Multiplication 612
Scalar Multiplication and Matrix Addition 612
Matrix Transpose 613
Determinant of a Matrix 613
Matrix Inverse 614
A-5 Complex Numbers 615
A-6 Quaternions 617
A-7 Nonparametric Representations 618
A-8 Parametric Representations 619
A-9 Numerical Methods 620
Solving Sets of Linear Equations 620
Finding Roots of Nonlinear Equations 621
Evaluating Integrals 622
Fitting Curves to Data Sets 625
BIBLIOGRAPHY 626
INDEX 639