Computer Graphics : Principles and Practice

Computer Graphics: Principles and Practice, Third Edition, remains the most authoritative introduction to the field. The first edition, the original "Foley and van Dam," helped to define computer graphics and how it could be taught. The second edition became an even more comprehensive resource for practitioners and students alike. This third edition has been completely rewritten to provide detailed and up-to-date coverage of key concepts, algorithms, technologies, and applications. The authors explain the principles, as well as the mathematics, underlying computer graphics-knowledge that is essential for successful work both now and in the future. Early chapters show how to create 2D and 3D pictures right away, supporting experimentation. Later chapters, covering a broad range of topics, demonstrate more sophisticated approaches. Sections on current computer graphics practice show how to apply given principles in common situations, such as how to approximate an ideal solution on available hardware, or how to represent a data structure more efficiently. Topics are reinforced by exercises, program­ming problems, and hands-on projects. This revised edition features New coverage of the rendering equation, GPU architecture considerations, and importance- sampling in physically based rendering An emphasis on modern approaches, as in a new chapter on probability theory for use in Monte-Carlo rendering Implementations of GPU shaders, software rendering, and graphics-intensive 3D interfaces 3D real-time graphics platforms-their design goals and trade-offs-including new mobile and browser platforms Programming and debugging approaches unique to graphics development The text and hundreds of figures are presented in full color throughout the book. Programs are written in C++, C#, WPF, or pseudocode-whichever language is most effective for a given example. Source code and figures from the book, testbed programs, and additional content will be available from the authors' website ( cgpp.net ) or the publisher's website ( informit.com/title/9780321399526 ). Instructor resources will be available from the publisher. The wealth of information in this book makes it the essential resource for anyone working in or studying any aspect of computer graphics Contents 12 Preface 38 About the Authors 48 1 Introduction 52 1.1 An Introduction to Computer Graphics 52 1.1.1 The World of Computer Graphics 55 1.1.2 Current and Future Application Areas 55 1.1.3 User-Interface Considerations 57 1.2 A Brief History 58 1.3 An Illuminating Example 60 1.4 Goals, Resources, and Appropriate Abstractions 61 1.4.1 Deep Understanding versus Common Practice 63 1.5 Some Numbers and Orders of Magnitude in Graphics 63 1.5.1 Light Energy and Photon Arrival Rates 63 1.5.2 Display Characteristics and Resolution of the Eye 64 1.5.3 Digital Camera Characteristics 64 1.5.4 Processing Demands of Complex Applications 65 1.6 The Graphics Pipeline 65 1.6.1 Texture Mapping and Approximation 66 1.6.2 The More Detailed Graphics Pipeline 67 1.7 Relationship of Graphics to Art, Design, and Perception 70 1.8 Basic Graphics Systems 71 1.8.1 Graphics Data 72 1.9 Polygon Drawing As a Black Box 74 1.10 Interaction in Graphics Systems 74 1.11 Different Kinds of Graphics Applications 75 1.12 Different Kinds of Graphics Packages 76 1.13 Building Blocks for Realistic Rendering: A Brief Overview 77 1.13.1 Light 77 1.13.2 Objects and Materials 78 1.13.3 Light Capture 80 1.13.4 Image Display 80 1.13.5 The Human Visual System 80 1.13.6 Mathematics 81 1.13.7 Integration and Sampling 82 1.14 Learning Computer Graphics 82 2 Introduction to 2D Graphics Using WPF 86 2.1 Introduction 86 2.2 Overview of the 2D Graphics Pipeline 87 2.3 The Evolution of 2D Graphics Platforms 88 2.3.1 From Integer to Floating-Point Coordinates 89 2.3.2 Immediate-Mode versus Retained-Mode Platforms 90 2.3.3 Procedural versus Declarative Specification 91 2.4 Specifying a 2D Scene Using WPF 92 2.4.1 The Structure of an XAML Application 92 2.4.2 Specifying the Scene via an Abstract Coordinate System 93 2.4.3 The Spectrum of Coordinate-System Choices 95 2.4.4 The WPF Canvas Coordinate System 96 2.4.5 Using Display Transformations 97 2.4.6 Creating and Using Modular Templates 100 2.5 Dynamics in 2D Graphics Using WPF 106 2.5.1 Dynamics via Declarative Animation 106 2.5.2 Dynamics via Procedural Code 109 2.6 Supporting a Variety of Form Factors 109 2.7 Discussion and Further Reading 110 3 An Ancient Renderer Made Modern 112 3.1 A Dürer Woodcut 112 3.2 Visibility 116 3.3 Implementation 116 3.3.1 Drawing 119 3.4 The Program 123 3.5 Limitations 126 3.6 Discussion and Further Reading 127 3.7 Exercises 129 4 A 2D Graphics Test Bed 132 4.1 Introduction 132 4.2 Details of the Test Bed 133 4.2.1 Using the 2D Test Bed 133 4.2.2 Corner Cutting 134 4.2.3 The Structure of a Test-Bed-Based Program 134 4.3 The C# Code 139 4.3.1 Coordinate Systems 141 4.3.2 WPF Data Dependencies 142 4.3.3 Event Handling 143 4.3.4 Other Geometric Objects 144 4.4 Animation 145 4.5 Interaction 146 4.6 An Application of the Test Bed 146 4.7 Discussion 149 4.8 Exercises 149 5 An Introduction to Human Visual Perception 152 5.1 Introduction 152 5.2 The Visual System 154 5.3 The Eye 157 5.3.1 Gross Physiology of the Eye 157 5.3.2 Receptors in the Eye 158 5.4 Constancy and Its Influences 161 5.5 Continuation 162 5.6 Shadows 163 5.7 Discussion and Further Reading 164 5.8 Exercises 166 6 Introduction to Fixed-Function 3D Graphics and Hierarchical Modeling 168 6.1 Introduction 168 6.1.1 The Design of WPF 3D 169 6.1.2 Approximating the Physics of the Interaction of Light with Objects 169 6.1.3 High-Level Overview of WPF 3D 170 6.2 Introducing Mesh and Lighting Specification 171 6.2.1 Planning the Scene 171 6.2.2 Producing More Realistic Lighting 175 6.2.3 “Lighting” versus “Shading” in Fixed-Function Rendering 178 6.3 Curved-Surface Representation and Rendering 179 6.3.1 Interpolated Shading (Gouraud) 179 6.3.2 Specifying Surfaces to Achieve Faceted and Smooth Effects 181 6.4 Surface Texture in WPF 181 6.4.1 Texturing via Tiling 183 6.4.2 Texturing via Stretching 183 6.5 The WPF Reflectance Model 184 6.5.1 Color Specification 184 6.5.2 Light Geometry 184 6.5.3 Reflectance 184 6.6 Hierarchical Modeling Using a Scene 189 6.6.1 Motivation for Modular Modeling 189 6.6.2 Top-Down Design of Component Hierarchy 190 6.6.3 Bottom-Up Construction and Composition 191 6.6.4 Reuse of Components 195 6.7 Discussion 198 7 Essential Mathematics and the Geometry of 2-Space and 3-Space 200 7.1 Introduction 200 7.2 Notation 201 7.3 Sets 201 7.4 Functions 202 7.4.1 Inverse Tangent Functions 203 7.5 Coordinates 204 7.6 Operations on Coordinates 204 7.6.1 Vectors 206 7.6.2 How to Think About Vectors 207 7.6.3 Length of a Vector 208 7.6.4 Vector Operations 208 7.6.5 Matrix Multiplication 212 7.6.6 Other Kinds of Vectors 213 7.6.7 Implicit Lines 215 7.6.8 An Implicit Description of a Line in a Plane 215 7.6.9 What About y = mx + b? 216 7.7 Intersections of Lines 216 7.7.1 Parametric-Parametric Line Intersection 217 7.7.2 Parametric-Implicit Line Intersection 218 7.8 Intersections, More Generally 218 7.8.1 Ray-Plane Intersection 219 7.8.2 Ray-Sphere Intersection 221 7.9 Triangles 222 7.9.1 Barycentric Coordinates 223 7.9.2 Triangles in Space 224 7.9.3 Half-Planes and Triangles 225 7.10 Polygons 226 7.10.1 Inside/Outside Testing 226 7.10.2 Interiors of Nonsimple Polygons 228 7.10.3 The Signed Area of a Plane Polygon: Divide and Conquer 228 7.10.4 Normal to a Polygon in Space 229 7.10.5 Signed Areas for More General Polygons 230 7.10.6 The Tilting Principle 231 7.10.7 Analogs of Barycentric Coordinates 233 7.11 Discussion 233 7.12 Exercises 233 8 A Simple Way to Describe Shape in 2D and 3D 238 8.1 Introduction 238 8.2 “Meshes” in 2D: Polylines 240 8.2.1 Boundaries 241 8.2.2 A Data Structure for 1D Meshes 242 8.3 Meshes in 3D 243 8.3.1 Manifold Meshes 244 8.3.2 Nonmanifold Meshes 246 8.3.3 Memory Requirements for Mesh Structures 247 8.3.4 A Few Mesh Operations 248 8.3.5 Edge Collapse 248 8.3.6 Edge Swap 248 8.4 Discussion and Further Reading 249 8.5 Exercises 249 9 Functions on Meshes 252 9.1 Introduction 252 9.2 Code for Barycentric Interpolation 254 9.2.1 A Different View of Linear Interpolation 258 9.2.2 Scanline Interpolation 259 9.3 Limitations of Piecewise Linear Extension 261 9.3.1 Dependence on Mesh Structure 262 9.4 Smoother Extensions 262 9.4.1 Nonconvex Spaces 262 9.4.2 Which Interpolation Method Should I Really Use? 264 9.5 Functions Multiply Defined at Vertices 264 9.6 Application: Texture Mapping 265 9.6.1 Assignment of Texture Coordinates 266 9.6.2 Details of Texture Mapping 267 9.6.3 Texture-Mapping Problems 267 9.7 Discussion 268 9.8 Exercises 268 10 Transformations in Two Dimensions 272 10.1 Introduction 272 10.2 Five Examples 273 10.3 Important Facts about Transformations 275 10.3.1 Multiplication by a Matrix Is a Linear Transformation 275 10.3.2 Multiplication by a Matrix Is the Only Linear Transformation 275 10.3.3 Function Composition and Matrix Multiplication Are Related 276 10.3.4 Matrix Inverse and Inverse Functions Are Related 276 10.3.5 Finding the Matrix for a Transformation 277 10.3.6 Transformations and Coordinate Systems 280 10.3.7 Matrix Properties and the Singular Value Decomposition 281 10.3.8 Computing the SVD 282 10.3.9 The SVD and Pseudoinverses 282 10.4 Translation 284 10.5 Points and Vectors Again 285 10.6 Why Use 3 × 3 Matrices Instead of a Matrix and a Vector? 286 10.7 Windowing Transformations 287 10.8 Building 3D Transformations 288 10.9 Another Example of Building a 2D Transformation 289 10.10 Coordinate Frames 291 10.11 Application: Rendering from a Scene Graph 292 10.11.1 Coordinate Changes in Scene Graphs 299 10.12 Transforming Vectors and Covectors 301 10.12.1 Transforming Parametric Lines 305 10.13 More General Transformations 305 10.14 Transformations versus Interpolation 310 10.15 Discussion and Further Reading 310 10.16 Exercises 311 11 Transformations in Three Dimensions 314 11.1 Introduction 314 11.1.1 Projective Transformation Theorems 316 11.2 Rotations 317 11.2.1 Analogies between Two and Three Dimensions 317 11.2.2 Euler Angles 318 11.2.3 Axis-Angle Description of a Rotation 320 11.2.4 Finding an Axis and Angle from a Rotation Matrix 321 11.2.5 Body-Centered Euler Angles 323 11.2.6 Rotations and the 3-Sphere 324 11.2.7 Stability of Computations 329 11.3 Comparing Representations 329 11.4 Rotations versus Rotation Specifications 330 11.5 Interpolating Matrix Transformations 331 11.6 Virtual Trackball and Arcball 331 11.7 Discussion and Further Reading 334 11.8 Exercises 335 12 A 2D and 3D Transformation Library for Graphics 338 12.1 Introduction 338 12.2 Points and Vectors 339 12.3 Transformations 339 12.3.1 Efficiency 340 12.4 Specification of Transformations 341 12.5 Implementation 341 12.5.1 Projective Transformations 342 12.6 Three Dimensions 344 12.7 Associated Transformations 345 12.8 Other Structures 345 12.9 Other Approaches 346 12.10 Discussion 348 12.11 Exercises 348 13 Camera Specifications and Transformations 350 13.1 Introduction 350 13.2 A 2D Example 351 13.3 Perspective Camera Specification 352 13.4 Building Transformations from a View Specification 354 13.5 Camera Transformations and the Rasterizing Renderer Pipeline 361 13.6 Perspective and z-values 364 13.7 Camera Transformations and the Modeling Hierarchy 364 13.8 Orthographic Cameras 366 13.8.1 Aspect Ratio and Field of View 367 13.9 Discussion and Further Reading 368 13.10 Exercises 369 14 Standard Approximations and Representations 372 14.1 Introduction 372 14.2 Evaluating Representations 373 14.2.1 The Value of Measurement 374 14.2.2 Legacy Models 375 14.3 Real Numbers 375 14.3.1 Fixed Point 376 14.3.2 Floating Point 377 14.3.3 Buffers 378 14.4 Building Blocks of Ray Optics 381 14.4.1 Light 381 14.4.2 Emitters 385 14.4.3 Light Transport 386 14.4.4 Matter 387 14.4.5 Cameras 387 14.5 Large-Scale Object Geometry 388 14.5.1 Meshes 389 14.5.2 Implicit Surfaces 392 14.5.3 Spline Patches and Subdivision Surfaces 394 14.5.4 Heightfields 395 14.5.5 Point Sets 396 14.6 Distant Objects 397 14.6.1 Level of Detail 398 14.6.2 Billboards and Impostors 398 14.6.3 Skyboxes 399 14.7 Volumetric Models 400 14.7.1 Finite Element Models 400 14.7.2 Voxels 400 14.7.3 Particle Systems 401 14.7.4 Fog 402 14.8 Scene Graphs 402 14.9 Material Models 404 14.9.1 Scattering Functions (BSDFs) 405 14.9.2 Lambertian 409 14.9.3 Normalized Blinn-Phong 410 14.10 Translucency and Blending 412 14.10.1 Blending 413 14.10.2 Partial Coverage (α) 415 14.10.3 Transmission 418 14.10.4 Emission 420 14.10.5 Bloom and Lens Flare 420 14.11 Luminaire Models 420 14.11.1 The Radiance Function 421 14.11.2 Direct and Indirect Light 421 14.11.3 Practical and Artistic Considerations 421 14.11.4 Rectangular Area Light 428 14.11.5 Hemisphere Area Light 429 14.11.6 Omni-Light 430 14.11.7 Directional Light 431 14.11.8 Spot Light 432 14.11.9 A Unified Point-Light Model 433 14.12 Discussion 435 14.13 Exercises 436 15 Ray Casting and Rasterization 438 15.1 Introduction 438 15.2 High-Level Design Overview 439 15.2.1 Scattering 439 15.2.2 Visible Points 441 15.2.3 Ray Casting: Pixels First 442 15.2.4 Rasterization: Triangles First 442 15.3 Implementation Platform 444 15.3.1 Selection Criteria 444 15.3.2 Utility Classes 446 15.3.3 Scene Representation 451 15.3.4 A Test Scene 453 15.4 A Ray-Casting Renderer 454 15.4.1 Generating an Eye Ray 455 15.4.2 Sampling Framework: Intersect and Shade 458 15.4.3 Ray-Triangle Intersection 459 15.4.4 Debugging 462 15.4.5 Shading 463 15.4.6 Lambertian Scattering 464 15.4.7 Glossy Scattering 465 15.4.8 Shadows 465 15.4.9 A More Complex Scene 468 15.5 Intermezzo 468 15.6 Rasterization 469 15.6.1 Swapping the Loops 469 15.6.2 Bounding-Box Optimization 471 15.6.3 Clipping to the Near Plane 473 15.6.4 Increasing Efficiency 473 15.6.5 Rasterizing Shadows 479 15.6.6 Beyond the Bounding Box 480 15.7 Rendering with a Rasterization API 483 15.7.1 The Graphics Pipeline 483 15.7.2 Interface 485 15.8 Performance and Optimization 495 15.8.1 Abstraction Considerations 495 15.8.2 Architectural Considerations 495 15.8.3 Early-Depth-Test Example 496 15.8.4 When Early Optimization Is Good 497 15.8.5 Improving the Asymptotic Bound 498 15.9 Discussion 498 15.10 Exercises 500 16 Survey of Real-Time 3D Graphics Platforms 502 16.1 Introduction 502 16.1.1 Evolution from Fixed-Function to Programmable Rendering Pipeline 503 16.2 The Programmer’s Model: OpenGL Compatibility (Fixed-Function) Profile 505 16.2.1 OpenGL Program Structure 506 16.2.2 Initialization and the Main Loop 507 16.2.3 Lighting and Materials 509 16.2.4 Geometry Processing 509 16.2.5 Camera Setup 511 16.2.6 Drawing Primitives 512 16.2.7 Putting It All Together—Part 1: Static Frame 513 16.2.8 Putting It All Together—Part 2: Dynamics 514 16.2.9 Hierarchical Modeling 514 16.2.10 Pick Correlation 515 16.3 The Programmer’s Model: OpenGL Programmable Pipeline 515 16.3.1 Abstract View of a Programmable Pipeline 515 16.3.2 The Nature of the Core API 517 16.4 Architectures of Graphics Applications 517 16.4.1 The Application Model 517 16.4.2 The Application-Model-to-IM-Platform Pipeline (AMIP) 519 16.4.3 Scene-Graph Middleware 525 16.4.4 Graphics Application Platforms 528 16.5 3D on Other Platforms 529 16.5.1 3D on Mobile Devices 530 16.5.2 3D in Browsers 530 16.6 Discussion 530 17 Image Representation and Manipulation 532 17.1 Introduction 532 17.2 What Is an Image? 533 17.2.1 The Information Stored in an Image 533 17.3 Image File Formats 534 17.3.1 Choosing an Image Format 535 17.4 Image Compositing 536 17.4.1 The Meaning of a Pixel During Image Compositing 537 17.4.2 Computing U over V 537 17.4.3 Simplifying Compositing 538 17.4.4 Other Compositing Operations 539 17.4.5 Physical Units and Compositing 540 17.5 Other Image Types 541 17.5.1 Nomenclature 542 17.6 MIP Maps 542 17.7 Discussion and Further Reading 543 17.8 Exercises 544 18 Images and Signal Processing 546 18.1 Introduction 546 18.1.1 A Broad Overview 546 18.1.2 Important Terms, Assumptions, and Notation 548 18.2 Historical Motivation 549 18.3 Convolution 551 18.4 Properties of Convolution 554 18.5 Convolution-like Computations 555 18.6 Reconstruction 556 18.7 Function Classes 556 18.8 Sampling 558 18.9 Mathematical Considerations 559 18.9.1 Frequency-Based Synthesis and Analysis 560 18.10 The Fourier Transform: Definitions 562 18.11 The Fourier Transform of a Function on an Interval 562 18.11.1 Sampling and Band Limiting in an Interval 565 18.12 Generalizations to Larger Intervals and All of R 567 18.13 Examples of Fourier Transforms 567 18.13.1 Basic Examples 567 18.13.2 The Transform of a Box Is a Sinc 568 18.13.3 An Example on an Interval 569 18.14 An Approximation of Sampling 570 18.15 Examples Involving Limits 570 18.15.1 Narrow Boxes and the Delta Function 570 18.15.2 The Comb Function and Its Transform 571 18.16 The Inverse Fourier Transform 571 18.17 Properties of the Fourier Transform 572 18.18 Applications 573 18.18.1 Band Limiting 573 18.18.2 Explaining Replication in the Spectrum 574 18.19 Reconstruction and Band Limiting 575 18.20 Aliasing Revisited 578 18.21 Discussion and Further Reading 580 18.22 Exercises 583 19 Enlarging and Shrinking Images 584 19.1 Introduction 584 19.2 Enlarging an Image 585 19.3 Scaling Down an Image 588 19.4 Making the Algorithms Practical 589 19.5 Finite-Support Approximations 591 19.5.1 Practical Band Limiting 592 19.6 Other Image Operations and Efficiency 592 19.7 Discussion and Further Reading 595 19.8 Exercises 596 20 Textures and Texture Mapping 598 20.1 Introduction 598 20.2 Variations of Texturing 600 20.2.1 Environment Mapping 600 20.2.2 Bump Mapping 601 20.2.3 Contour Drawing 602 20.3 Building Tangent Vectors from a Parameterization 603 20.4 Codomains for Texture Maps 604 20.5 Assigning Texture Coordinates 606 20.6 Application Examples 608 20.7 Sampling, Aliasing, Filtering, and Reconstruction 608 20.8 Texture Synthesis 610 20.8.1 Fourier-like Synthesis 610 20.8.2 Perlin Noise 611 20.8.3 Reaction-Diffusion Textures 612 20.9 Data-Driven Texture Synthesis 613 20.10 Discussion and Further Reading 615 20.11 Exercises 616 21 Interaction Techniques 618 21.1 Introduction 618 21.2 User Interfaces and Computer Graphics 618 21.2.1 Prescriptions 622 21.2.2 Interaction Event Handling 624 21.3 Multitouch Interaction for 2D Manipulation 625 21.3.1 Defining the Problem 626 21.3.2 Building the Program 627 21.3.3 The Interactor 627 21.4 Mouse-Based Object Manipulation in 3D 631 21.4.1 The Trackball Interface 631 21.4.2 The Arcball Interface 635 21.5 Mouse-Based Camera Manipulation: Unicam 635 21.5.1 Translation 636 21.5.2 Rotation 637 21.5.3 Additional Operations 638 21.5.4 Evaluation 638 21.6 Choosing the Best Interface 638 21.7 Some Interface Examples 639 21.7.1 First-Person-Shooter Controls 639 21.7.2 3ds Max Transformation Widget 639 21.7.3 Photoshop’s Free-Transform Mode 640 21.7.4 Chateau 640 21.7.5 Teddy 641 21.7.6 Grabcut and Selection by Strokes 641 21.8 Discussion and Further Reading 642 21.9 Exercises 644 22 Splines and Subdivision Curves 646 22.1 Introduction 646 22.2 Basic Polynomial Curves 646 22.3 Fitting a Curve Segment between Two Curves: The Hermite Curve 646 22.3.1 Bézier Curves 649 22.4 Gluing Together Curves and the Catmull-Rom Spline 649 22.4.1 Generalization of Catmull-Rom Splines 652 22.4.2 Applications of Catmull-Rom Splines 653 22.5 Cubic B-splines 653 22.5.1 Other B-splines 655 22.6 Subdivision Curves 655 22.7 Discussion and Further Reading 656 22.8 Exercises 656 23 Splines and Subdivision Surfaces 658 23.1 Introduction 658 23.2 Bézier Patches 659 23.3 Catmull-Clark Subdivision Surfaces 661 23.4 Modeling with Subdivision Surfaces 664 23.5 Discussion and Further Reading 665 24 Implicit Representations of Shape 666 24.1 Introduction 666 24.2 Implicit Curves 667 24.3 Implicit Surfaces 670 24.4 Representing Implicit Functions 672 24.4.1 Interpolation Schemes 672 24.4.2 Splines 674 24.4.3 Mathematical Models and Sampled Implicit Representations 674 24.5 Other Representations of Implicit Functions 675 24.6 Conversion to Polyhedral Meshes 676 24.6.1 Marching Cubes 679 24.7 Conversion from Polyhedral Meshes to Implicits 680 24.8 Texturing Implicit Models 680 24.8.1 Modeling Transformations and Textures 681 24.9 Ray Tracing Implicit Surfaces 682 24.10 Implicit Shapes in Animation 682 24.11 Discussion and Further Reading 683 24.12 Exercises 684 25 Meshes 686 25.1 Introduction 686 25.2 Mesh Topology 688 25.2.1 Triangulated Surfaces and Surfaces with Boundary 688 25.2.2 Computing and Storing Adjacency 689 25.2.3 More Mesh Terminology 692 25.2.4 Embedding and Topology 693 25.3 Mesh Geometry 694 25.3.1 Mesh Meaning 695 25.4 Level of Detail 696 25.4.1 Progressive Meshes 700 25.4.2 Other Mesh Simplification Approaches 703 25.5 Mesh Applications 1: Marching Cubes, Mesh Repair, and Mesh Improvement 703 25.5.1 Marching Cubes Variants 703 25.5.2 Mesh Repair 705 25.5.3 Differential or Laplacian Coordinates 706 25.5.4 An Application of Laplacian Coordinates 708 25.6 Mesh Applications 2: Deformation Transfer and Triangle-Order Optimization 711 25.6.1 Deformation Transfer 711 25.6.2 Triangle Reordering for Hardware Efficiency 715 25.7 Discussion and Further Reading 718 25.8 Exercises 719 26 Light 720 26.1 Introduction 720 26.2 The Physics of Light 720 26.3 The Microscopic View 721 26.4 The Wave Nature of Light 725 26.4.1 Diffraction 728 26.4.2 Polarization 728 26.4.3 Bending of Light at an Interface 730 26.5 Fresnel’s Law and Polarization 732 26.5.1 Radiance Computations and an “Unpolarized” Form of Fresnel’s Equations 734 26.6 Modeling Light as a Continuous Flow 734 26.6.1 A Brief Introduction to Probability Densities 735 26.6.2 Further Light Modeling 737 26.6.3 Angles and Solid Angles 737 26.6.4 Computations with Solid Angles 739 26.6.5 An Important Change of Variables 741 26.7 Measuring Light 743 26.7.1 Radiometric Terms 745 26.7.2 Radiance 745 26.7.3 Two Radiance Computations 746 26.7.4 Irradiance 748 26.7.5 Radiant Exitance 750 26.7.6 Radiant Power or Radiant Flux 750 26.8 Other Measurements 751 26.9 The Derivative Approach 751 26.10 Reflectance 753 26.10.1 Related Terms 755 26.10.2 Mirrors, Glass, Reciprocity, and the BRDF 756 26.10.3 Writing L in Different Ways 757 26.11 Discussion and Further Reading 758 26.12 Exercises 758 27 Materials and Scattering 762 27.1 Introduction 762 27.2 Object-Level Scattering 762 27.3 Surface Scattering 763 27.3.1 Impulses 764 27.3.2 Types of Scattering Models 764 27.3.3 Physical Constraints on Scattering 764 27.4 Kinds of Scattering 765 27.5 Empirical and Phenomenological Models for Scattering 768 27.5.1 Mirror “Scattering” 768 27.5.2 Lambertian Reflectors 770 27.5.3 The Phong and Blinn-Phong Models 772 27.5.4 The Lafortune Model 774 27.5.5 Sampling 775 27.6 Measured Models 776 27.7 Physical Models for Specular and Diffuse Reflection 777 27.8 Physically Based Scattering Models 778 27.8.1 The Fresnel Equations, Revisited 778 27.8.2 The Torrance-Sparrow Model 780 27.8.3 The Cook-Torrance Model 782 27.8.4 The Oren-Nayar Model 783 27.8.5 Wave Theory Models 785 27.9 Representation Choices 785 27.10 Criteria for Evaluation 785 27.11 Variations across Surfaces 786 27.12 Suitability for Human Use 787 27.13 More Complex Scattering 788 27.13.1 Participating Media 788 27.13.2 Subsurface Scattering 789 27.14 Software Interface to Material Models 791 27.15 Discussion and Further Reading 792 27.16 Exercises 794 28 Color 796 28.1 Introduction 796 28.1.1 Implications of Color 797 28.2 Spectral Distribution of Light 797 28.3 The Phenomenon of Color Perception and the Physiology of the Eye 799 28.4 The Perception of Color 801 28.4.1 The Perception of Brightness 801 28.5 Color Description 807 28.6 Conventional Color Wisdom 809 28.6.1 Primary Colors 809 28.6.2 Purple Isn’t a Real Color 810 28.6.3 Objects Have Colors; You Can Tell by Looking at Them in White Light 810 28.6.4 Blue and Green Make Cyan 811 28.6.5 Color Is RGB 812 28.7 Color Perception Strengths andWeaknesses 812 28.8 Standard Description of Colors 812 28.8.1 The CIE Description of Color 813 28.8.2 Applications of the Chromaticity Diagram 817 28.9 Perceptual Color Spaces 818 28.9.1 Variations and Miscellany 818 28.10 Intermezzo 819 28.11 White 820 28.12 Encoding of Intensity, Exponents, and Gamma Correction 820 28.13 Describing Color 822 28.13.1 The RGB Color Model 823 28.14 CMY and CMYK Color 825 28.15 The YIQ Color Model 826 28.16 Video Standards 826 28.17 HSV and HLS 827 28.17.1 Color Choice 828 28.17.2 Color Palettes 828 28.18 Interpolating Color 828 28.19 Using Color in Computer Graphics 830 28.20 Discussion and Further Reading 831 28.21 Exercises 831 29 Light Transport 834 29.1 Introduction 834 29.2 Light Transport 834 29.2.1 The Rendering Equation, First Version 837 29.3 A Peek Ahead 838 29.4 The Rendering Equation for General Scattering 840 29.4.1 The Measurement Equation 842 29.5 Scattering, Revisited 843 29.6 AWorked Example 844 29.7 Solving the Rendering Equation 847 29.8 The Classification of Light-Transport Paths 847 29.8.1 Perceptually Significant Phenomena and Light Transport 848 29.9 Discussion 850 29.10 Exercise 850 30 Probability and Monte Carlo Integration 852 30.1 Introduction 852 30.2 Numerical Integration 852 30.3 Random Variables and Randomized Algorithms 853 30.3.1 Discrete Probability and Its Relationship to Programs 854 30.3.2 Expected Value 855 30.3.3 Properties of Expected Value, and Related Terms 857 30.3.4 Continuum Probability 859 30.3.5 Probability Density Functions 861 30.3.6 Application to the Sphere 864 30.3.7 A Simple Example 864 30.3.8 Application to Scattering 865 30.4 Continuum Probability, Continued 866 30.5 Importance Sampling and Integration 869 30.6 Mixed Probabilities 871 30.7 Discussion and Further Reading 872 30.8 Exercises 872 31 Computing Solutions to the Rendering Equation: Theoretical Approaches 876 31.1 Introduction 876 31.2 Approximate Solutions of Equations 876 31.3 Method 1: Approximating the Equation 877 31.4 Method 2: Restricting the Domain 878 31.5 Method 3: Using Statistical Estimators 878 31.5.1 Summing a Series by Sampling and Estimation 879 31.6 Method 4: Bisection 881 31.7 Other Approaches 882 31.8 The Rendering Equation, Revisited 882 31.8.1 A Note on Notation 886 31.9 What Do We Need to Compute? 887 31.10 The Discretization Approach: Radiosity 889 31.11 Separation of Transport Paths 895 31.12 Series Solution of the Rendering Equation 895 31.13 Alternative Formulations of Light Transport 897 31.14 Approximations of the Series Solution 898 31.15 Approximating Scattering: Spherical Harmonics 899 31.16 Introduction to Monte Carlo Approaches 902 31.17 Tracing Paths 906 31.18 Path Tracing and Markov Chains 907 31.18.1 The Markov Chain Approach 908 31.18.2 The Recursive Approach 912 31.18.3 Building a Path Tracer 915 31.18.4 Multiple Importance Sampling 919 31.18.5 Bidirectional Path Tracing 921 31.18.6 Metropolis Light Transport 922 31.19 Photon Mapping 923 31.19.1 Image-Space Photon Mapping 927 31.20 Discussion and Further Reading 927 31.21 Exercises 930 32 Rendering in Practice 932 32.1 Introduction 932 32.2 Representations 932 32.3 Surface Representations and Representing BSDFs Locally 933 32.3.1 Mirrors and Point Lights 937 32.4 Representation of Light 938 32.4.1 Representation of Luminaires 939 32.5 A Basic Path Tracer 940 32.5.1 Preliminaries 940 32.5.2 Path-Tracer Code 944 32.5.3 Results and Discussion 952 32.6 Photon Mapping 955 32.6.1 Results and Discussion 961 32.6.2 Further Photon Mapping 964 32.7 Generalizations 965 32.8 Rendering and Debugging 966 32.9 Discussion and Further Reading 970 32.10 Exercises 974 33 Shaders 978 33.1 Introduction 978 33.2 The Graphics Pipeline in Several Forms 978 33.3 Historical Development 980 33.4 A Simple Graphics Program with Shaders 983 33.5 A Phong Shader 988 33.6 Environment Mapping 990 33.7 Two Versions of Toon Shading 991 33.8 Basic XToon Shading 993 33.9 Discussion and Further Reading 994 33.10 Exercises 994 34 Expressive Rendering 996 34.1 Introduction 996 34.1.1 Examples of Expressive Rendering 999 34.1.2 Organization of This Chapter 999 34.2 The Challenges of Expressive Rendering 1000 34.3 Marks and Strokes 1001 34.4 Perception and Salient Features 1002 34.5 Geometric Curve Extraction 1003 34.5.1 Ridges and Valleys 1007 34.5.2 Suggestive Contours 1008 34.5.3 Apparent Ridges 1009 34.5.4 Beyond Geometry 1010 34.6 Abstraction 1010 34.7 Discussion and Further Reading 1012 35 Motion 1014 35.1 Introduction 1014 35.2 Motivating Examples 1017 35.2.1 A Walking Character (Key Poses) 1017 35.2.2 Firing a Cannon (Simulation) 1020 35.2.3 Navigating Corridors (Motion Planning) 1023 35.2.4 Notation 1024 35.3 Considerations for Rendering 1026 35.3.1 Double Buffering 1026 35.3.2 Motion Perception 1027 35.3.3 Interlacing 1029 35.3.4 Temporal Aliasing and Motion Blur 1031 35.3.5 Exploiting Temporal Coherence 1034 35.3.6 The Problem of the First Frame 1035 35.3.7 The Burden of Temporal Coherence 1036 35.4 Representations 1038 35.4.1 Objects 1038 35.4.2 Limiting Degrees of Freedom 1039 35.4.3 Key Poses 1040 35.4.4 Dynamics 1040 35.4.5 Procedural Animation 1041 35.4.6 Hybrid Control Schemes 1041 35.5 Pose Interpolation 1043 35.5.1 Vertex Animation 1043 35.5.2 Root Frame Motion 1044 35.5.3 Articulated Body 1045 35.5.4 Skeletal Animation 1046 35.6 Dynamics 1047 35.6.1 Particle 1047 35.6.2 Differential Equation Formulation 1048 35.6.3 Piecewise-Constant Approximation 1050 35.6.4 Models of Common Forces 1051 35.6.5 Particle Collisions 1059 35.6.6 Dynamics as a Differential Equation 1063 35.6.7 Numerical Methods for ODEs 1068 35.7 Remarks on Stability in Dynamics 1071 35.8 Discussion 1073 36 Visibility Determination 1074 36.1 Introduction 1074 36.1.1 The Visibility Function 1076 36.1.2 Primary Visibility 1078 36.1.3 (Binary) Coverage 1078 36.1.4 Current Practice and Motivation 1079 36.2 Ray Casting 1080 36.2.1 BSP Ray-Primitive Intersection 1081 36.2.2 Parallel Evaluation of Ray Tests 1083 36.3 The Depth Buffer 1085 36.3.1 Common Depth Buffer Encodings 1088 36.4 List-Priority Algorithms 1091 36.4.1 The Painter’s Algorithm 1092 36.4.2 The Depth-Sort Algorithm 1093 36.4.3 Clusters and BSP Sort 1094 36.5 Frustum Culling and Clipping 1095 36.5.1 Frustum Culling 1095 36.5.2 Clipping 1096 36.5.3 Clipping to the Whole Frustum 1098 36.6 Backface Culling 1098 36.7 Hierarchical Occlusion Culling 1100 36.8 Sector-based Conservative Visibility 1101 36.8.1 Stabbing Trees 1102 36.8.2 Portals and Mirrors 1103 36.9 Partial Coverage 1105 36.9.1 Spatial Antialiasing (xy) 1106 36.9.2 Defocus (uv) 1111 36.9.3 Motion Blur (t) 1112 36.9.4 Coverage as a Material Property (α) 1113 36.10 Discussion and Further Reading 1113 36.11 Exercise 1114 37 Spatial Data Structures 1116 37.1 Introduction 1116 37.1.1 Motivating Examples 1117 37.2 Programmatic Interfaces 1119 37.2.1 Intersection Methods 1120 37.2.2 Extracting Keys and Bounds 1124 37.3 Characterizing Data Structures 1128 37.3.1 1D Linked List Example 1129 37.3.2 1D Tree Example 1130 37.4 Overview of kd Structures 1131 37.5 List 1132 37.6 Trees 1134 37.6.1 Binary Space Partition (BSP) Trees 1135 37.6.2 Building BSP Trees: oct tree, quad tree, BSP tree, kd tree 1140 37.6.3 Bounding Volume Hierarchy 1143 37.7 Grid 1144 37.7.1 Construction 1144 37.7.2 Ray Intersection 1146 37.7.3 Selecting Grid Resolution 1150 37.8 Discussion and Further Reading 1152 38 Modern Graphics Hardware 1154 38.1 Introduction 1154 38.2 NVIDIA GeForce 9800 GTX 1156 38.3 Architecture and Implementation 1158 38.3.1 GPU Architecture 1159 38.3.2 GPU Implementation 1162 38.4 Parallelism 1162 38.5 Programmability 1165 38.6 Texture, Memory, and Latency 1168 38.6.1 Texture Mapping 1169 38.6.2 Memory Basics 1172 38.6.3 Coping with Latency 1175 38.7 Locality 1178 38.7.1 Locality of Reference 1178 38.7.2 Cache Memory 1180 38.7.3 Divergence 1183 38.8 Organizational Alternatives 1186 38.8.1 Deferred Shading 1186 38.8.2 Binned Rendering 1188 38.8.3 Larrabee: A CPU/GPU Hybrid 1189 38.9 GPUs as Compute Engines 1193 38.10 Discussion and Further Reading 1194 38.11 Exercises 1194 List of Principles 1196 Bibliography 1200 Index 1234 A 1234 B 1235 C 1236 D 1239 " Computer Graphics: Principles and Practice, Third Edition, remains the most authoritative introduction to the field. The first edition, the original "Foley and van Dam," helped to define computer graphics and how it could be taught. The second edition became an even more comprehensive resource for practitioners and students alike. This third edition has been completely rewritten to provide detailed and up-to-date coverage of key concepts, algorithms, technologies, and applications. The authors explain the principles, as well as the mathematics, underlying computer graphics-knowledge that is essential for successful work both now and in the future. Early chapters show how to create 2D and 3D pictures right away, supporting experimentation. Later chapters, covering a broad range of topics, demonstrate more sophisticated approaches. Sections on current computer graphics practice show how to apply given principles in common situations, such as how to approximate an ideal solution on available hardware, or how to represent a data structure more efficiently. Topics are reinforced by exercises, program­ming problems, and hands-on projects.This revised edition features New coverage of the rendering equation, GPU architecture considerations, and importance- sampling in physically based rendering An emphasis on modern approaches, as in a new chapter on probability theory for use in Monte-Carlo rendering Implementations of GPU shaders, software rendering, and graphics-intensive 3D interfaces 3D real-time graphics platforms-their design goals and trade-offs-including new mobile and browser platforms Programming and debugging approaches unique to graphics development The text and hundreds of figures are presented in full color throughout the book. Programs are written in C++, C#, WPF, or pseudocode-whichever language is most effective for a given example. Source code and figures from the book, testbed programs, and additional content will be available from the authors' website (cgpp.net) or the publisher's website (informit.com/title/9780321399526). Instructor resources will be available from the publisher. The wealth of information in this book makes it the essential resource for anyone working in or studying any aspect of computer graphics."--Page 4 de la couverture "Computer Graphics: Principles and Practice, Third Edition, remains ... [an] authoritative introduction to the field. The first edition, the original "Foley and van Dam," helped to define computer graphics and how it could be taught. The second edition became an even more comprehensive resource for practitioners and students alike. This third edition has been completely rewritten to provide detailed and up-to-date coverage of key concepts, algorithms, technologies, and applications. The authors explain the principles, as well as the mathematics, underlying computer graphics--knowledge that is essential for successful work both now and in the future. Early chapters show how to create 2D and 3D pictures right away, supporting experimentation. Later chapters, covering a broad range of topics, demonstrate more sophisticated approaches. Sections on current computer graphics practice show how to apply given principles in common situations, such as how to approximate an ideal solution on available hardware, or how to represent a data structure more efficiently. Topics are reinforced by exercises, programming problems, and hands-on projects. This revised edition features: new coverage of the rendering equation, GPU architecture considerations, and importance- sampling in physically based rendering; an emphasis on modern approaches, as in a new chapter on probability theory for use in Monte-Carlo rendering; implementations of GPU shaders, software rendering, and graphics-intensive 3D interfaces; 3D real-time graphics platforms--their design goals and trade-offs--including new mobile and browser platforms; and programming and debugging approaches unique to graphics development. The text and hundreds of figures are presented in full color throughout the book. Programs are written in C++, C♯, WPF, or pseudocode--whichever language is most effective for a given example. Source code and figures from the book, testbed programs, and additional content will be available from the authors' website (cgpp.net) or the publisher's website (informit.com/title/9780321399526). Instructor resources will be available from the publisher."--Publisher's description