Computer Graphics: C Version by Donald Hearn & M. Pauline Baker, 2nd ed. Contents: Preface xvii 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 2-2 Raster-Scan Systems 53 2-3 Random-Scan Systems 56 2-4 Graphics Monitors and Workstations 57 2-5 Input Devices 60 2-6 Hard-Copy Devices 72 2-7 Graphics Software 75 3: Output Primitives 83 3-1 Points and Lines 84 3-2 Line-Drawing Algorithms 86 3-3 Loading the Frame Buffer 94 3-4 Line Function 95 3-5 Circle-Generating Algorithms 97 3-6 Ellipse-Generating Algorithms 102 3-7 Other Curves 110 3-8 Parallel Curve Algorithms 112 3-9 Curve Functions 113 3-10 Pixel Addressing and Object Geometry 114 Screen Grid Coordinates 114 3-12 Fill-Area Functions 131 3-13 Cell Array 131 3-14 Character Generation 131 4: Attributes of Output Primitives 143 4-1 Line Attributes 144 4-2 Curve Attributes 152 4-3 Color and Grayscale Levels 154 4-4 Area-Fill Attributes 158 4-5 Character Attributes 163 4-6 Bundled Attributes 168 4-7 Inquiry Functions 170 4-8 Antialiasing 171 5: Two-Dimensional Geometric Transformations 183 5-1 Basic Transformations 184 5-2 Matrix Representations and Homogeneous Coordinates 188 5-3 Composite Transformations 191 5-4 Other Transformations 201 5-5 Transformations Between Coordinate Systems 205 5-6 Affine Transformations 208 5-7 Transformation Functions 208 5-8 Raster Methods for Transformations 210 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-6 Point Clipping 225 6-7 Line Clipping 225 6-8 Polygon Clipping 237 6-9 Curve Clipping 244 6-10 Text Clipping 244 6-11 Exterior Clipping 245 7: Structures and Hierarchical Modeling 250 7-1 Structure Concepts 250 7-2 Editing Structures 254 7-3 Basic Modeling Concepts 260 7-4 Hierarchical Modeling with Structures 265 8: Graphical User Interfaces and Interactive Input Methods 271 8-1 The User Dialogue 272 8-2 Input of Graphical Data 276 8-3 Input Functions 281 8-4 Initial Values for Input-Device Parameters 287 8-5 Interactive Picture-Construction Techniques 288 8-6 Virtual-Reality Environments 292 9: Three-Dimensional Concepts 296 9-1 Three-Dimensional Display Methods 297 9-2 Three-Dimensional Graphics Packages 302 10: Three-Dimensional Object Representations 304 10-1 Polygon Surfaces 305 10-2 Curved Lines and Surfaces 310 10-3 Quadric Surfaces 310 10-4 Superquadrics 312 10-5 Blobby Objects 314 10-6 Spline Representations 315 10-7 Cubic Spline Interpolation Methods 320 10-8 Bezier Curves and Surfaces 327 10-9 B-Spline Curves and Surfaces 334 10-10 Beta-Splines 345 10-11 Rational Splines 347 10-12 Conversion Between Spline Representations 349 10-13 Displaying Spline Curves and Surfaces 351 10-14 Sweep Representations 355 10-15 Constructive Solid-Geometry Methods 356 10-16 Octrees 359 10-17 BSP Trees 362 10-18 Fractal-Geometry Methods 362 Geometric Construction of Statistically Self-Similar Fractals 369 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 11: Three-Dimensional Geometric and Modeling Transformations 407 11-1 Translation 408 11-2 Rotation 409 11-3 Scaling 420 11-4 Other Transformations 422 11-5 Composite Transformations 423 11-6 Three-Dimensional Transformation Functions 425 11-7 Modeling and Coordinate Transformations 426 12: Three-Dimensional Viewing 431 12-1 Viewing Pipeline 432 12-2 Viewing Coordinates 433 12-3 Projections 438 12-4 View Volumes and General Projection Transformations 447 12-5 Clipping 456 12-6 Hardware Implementations 463 12-7 Three-Dimensional Viewing Functions 464 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 13-12 Wireframe Methods 490 13-13 Visibility-Detection Functions 490 14: Illumination Models and Surface-Rendering Methods 494 14-1 Light Sources 496 14-2 Basic Illumination Models 497 14-3 Displaying Light Intensities 511 14-4 Halftone Patterns and Dithering Techniques 516 14-5 Polygon-Rendering Methods 522 14-6 Ray-Tracing Methods 527 14-7 Radiosity Lighting Model 544 14-8 Environment Mapping 552 14-9 Adding Surface Detail 553 15: Color Models and Color Applications 564 15-1 Properties of Light 565 15-2 Standard Primaries and the Chromaticity Diagram 568 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-8 Conversion Between HSV and RGB Models 578 15-9 HLS Color Model 579 15-10 Color Selection and Applications 580 16: Computer Animation 583 16-1 Design of Animation Sequences 584 16-2 General Computer-Animation Functions 586 16-3 Raster Animations 586 16-4 Computer-Animation Languages 587 16-5 Key-Frame Systems 588 16-6 Motion Specifications 594 A: Mathematics for Computer Graphics 599 A-1 Coordinate-Reference Frames 600 A-2 Points and Vectors 605 A-3 Basis Vectors and the Metric Tensor 609 A-4 Matrices 611 A-5 Complex Numbers 615 A-6 Quaternions 617 A-7 Nonparametric Representations 619 A-8 Parametric Representations 619 A-9 Numerical Methods 620 BIBLIOGRAPHY 626 INDEX 639 --------------------------------------------------------------------------- Computer Graphics: C Version by Donald Hearn & M. Pauline Baker, 2nd ed. Contents: Preface xvii 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 Trackball and Spaceball 63 Joysticks 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 References 81 Exercises 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 Bundled Marker Attributes 170 4-7 Inquiry Functions 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-6 Point Clipping 225 6-7 Line 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 References 248 Exercises 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 Elements 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 Consistency 274 Minimizing Memorization 274 Backup and Error Handling 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 Request Mode 282 Locator and Stroke Input in 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 Gravity Field 290 Rubber-Band Methods 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 Bezier Curves and Surfaces 327 Bezier Curves 327 Properties of Bezier Curves 329 Design Techniques Using Bezier Curves 330 Cubic Bezier Curves 331 Bezier 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 10-13 Displaying Spline Curves and Surfaces 351 Horner's Rule 351 Forward-Difference Calculations 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-Geometry 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 378 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 Summary 404 References 404 Exercises 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 Transformations 422 Reflections 422 Shears 423 11-5 Composite Transformations 423 11-6 Three-Dimensional Transformation Functions 425 11-7 Modeling and Coordinate Transformations 426 Summary 429 References 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 Light Sources 496 14-2 Basic Illumination Models 497 Ambient Light 497 Diffuse Reflection 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 Approximation 516 Dithering Techniques 519 14-5 Polygon-Rendering Methods 522 Constant-Intensity Shading 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 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 XYZ Color Model 569 CIE Chromaticity Diagram 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-8 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-2 General Computer-Animation Functions 586 16-3 Raster Animations 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 A-1 Coordinate-Reference Frames 600 Two-Dimensional Cartesian Reference Frames 600 Polar Coordinates in the xy Plane 601 Three-Dimensional Cartesian Reference Frames 602 Three-Dimensional Curvilinear Coordinate 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 Scalar Multiplication and Matrix Addition 612 Matrix Multiplication 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 619 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