Computer Graphics: Principles and Practice

Contents
Preface
About the Authors
1 Introduction
1.1 An Introduction to Computer Graphics
1.1.1 The World of Computer Graphics
1.1.2 Current and Future Application Areas
1.1.3 User-Interface Considerations
1.2 A Brief History
1.3 An Illuminating Example
1.4 Goals, Resources, and Appropriate Abstractions
1.4.1 Deep Understanding versus Common Practice
1.5 Some Numbers and Orders of Magnitude in Graphics
1.5.1 Light Energy and Photon Arrival Rates
1.5.2 Display Characteristics and Resolution of the Eye
1.5.3 Digital Camera Characteristics
1.5.4 Processing Demands of Complex Applications
1.6 The Graphics Pipeline
1.6.1 Texture Mapping and Approximation
1.6.2 The More Detailed Graphics Pipeline
1.7 Relationship of Graphics to Art, Design, and Perception
1.8 Basic Graphics Systems
1.8.1 Graphics Data
1.9 Polygon Drawing As a Black Box
1.10 Interaction in Graphics Systems
1.11 Different Kinds of Graphics Applications
1.12 Different Kinds of Graphics Packages
1.13 Building Blocks for Realistic Rendering: A Brief Overview
1.13.1 Light
1.13.2 Objects and Materials
1.13.3 Light Capture
1.13.4 Image Display
1.13.5 The Human Visual System
1.13.6 Mathematics
1.13.7 Integration and Sampling
1.14 Learning Computer Graphics
2 Introduction to 2D Graphics Using WPF
2.1 Introduction
2.2 Overview of the 2D Graphics Pipeline
2.3 The Evolution of 2D Graphics Platforms
2.3.1 From Integer to Floating-Point Coordinates
2.3.2 Immediate-Mode versus Retained-Mode Platforms
2.3.3 Procedural versus Declarative Specification
2.4 Specifying a 2D Scene Using WPF
2.4.1 The Structure of an XAML Application
2.4.2 Specifying the Scene via an Abstract Coordinate System
2.4.3 The Spectrum of Coordinate-System Choices
2.4.4 The WPF Canvas Coordinate System
2.4.5 Using Display Transformations
2.4.6 Creating and Using Modular Templates
2.5 Dynamics in 2D Graphics Using WPF
2.5.1 Dynamics via Declarative Animation
2.5.2 Dynamics via Procedural Code
2.6 Supporting a Variety of Form Factors
2.7 Discussion and Further Reading
3 An Ancient Renderer Made Modern
3.1 A Dürer Woodcut
3.2 Visibility
3.3 Implementation
3.3.1 Drawing
3.4 The Program
3.5 Limitations
3.6 Discussion and Further Reading
3.7 Exercises
4 A 2D Graphics Test Bed
4.1 Introduction
4.2 Details of the Test Bed
4.2.1 Using the 2D Test Bed
4.2.2 Corner Cutting
4.2.3 The Structure of a Test-Bed-Based Program
4.3 The C# Code
4.3.1 Coordinate Systems
4.3.2 WPF Data Dependencies
4.3.3 Event Handling
4.3.4 Other Geometric Objects
4.4 Animation
4.5 Interaction
4.6 An Application of the Test Bed
4.7 Discussion
4.8 Exercises
5 An Introduction to Human Visual Perception
5.1 Introduction
5.2 The Visual System
5.3 The Eye
5.3.1 Gross Physiology of the Eye
5.3.2 Receptors in the Eye
5.4 Constancy and Its Influences
5.5 Continuation
5.6 Shadows
5.7 Discussion and Further Reading
5.8 Exercises
6 Introduction to Fixed-Function 3D Graphics and Hierarchical Modeling
6.1 Introduction
6.1.1 The Design of WPF 3D
6.1.2 Approximating the Physics of the Interaction of Light with Objects
6.1.3 High-Level Overview of WPF 3D
6.2 Introducing Mesh and Lighting Specification
6.2.1 Planning the Scene
6.2.2 Producing More Realistic Lighting
6.2.3 “Lighting” versus “Shading” in Fixed-Function Rendering
6.3 Curved-Surface Representation and Rendering
6.3.1 Interpolated Shading (Gouraud)
6.3.2 Specifying Surfaces to Achieve Faceted and Smooth Effects
6.4 Surface Texture in WPF
6.4.1 Texturing via Tiling
6.4.2 Texturing via Stretching
6.5 The WPF Reflectance Model
6.5.1 Color Specification
6.5.2 Light Geometry
6.5.3 Reflectance
6.6 Hierarchical Modeling Using a Scene
6.6.1 Motivation for Modular Modeling
6.6.2 Top-Down Design of Component Hierarchy
6.6.3 Bottom-Up Construction and Composition
6.6.4 Reuse of Components
6.7 Discussion
7 Essential Mathematics and the Geometry of 2-Space and 3-Space
7.1 Introduction
7.2 Notation
7.3 Sets
7.4 Functions
7.4.1 Inverse Tangent Functions
7.5 Coordinates
7.6 Operations on Coordinates
7.6.1 Vectors
7.6.2 How to Think About Vectors
7.6.3 Length of a Vector
7.6.4 Vector Operations
7.6.5 Matrix Multiplication
7.6.6 Other Kinds of Vectors
7.6.7 Implicit Lines
7.6.8 An Implicit Description of a Line in a Plane
7.6.9 What About y = mx + b?
7.7 Intersections of Lines
7.7.1 Parametric-Parametric Line Intersection
7.7.2 Parametric-Implicit Line Intersection
7.8 Intersections, More Generally
7.8.1 Ray-Plane Intersection
7.8.2 Ray-Sphere Intersection
7.9 Triangles
7.9.1 Barycentric Coordinates
7.9.2 Triangles in Space
7.9.3 Half-Planes and Triangles
7.10 Polygons
7.10.1 Inside/Outside Testing
7.10.2 Interiors of Nonsimple Polygons
7.10.3 The Signed Area of a Plane Polygon: Divide and Conquer
7.10.4 Normal to a Polygon in Space
7.10.5 Signed Areas for More General Polygons
7.10.6 The Tilting Principle
7.10.7 Analogs of Barycentric Coordinates
7.11 Discussion
7.12 Exercises
8 A Simple Way to Describe Shape in 2D and 3D
8.1 Introduction
8.2 “Meshes” in 2D: Polylines
8.2.1 Boundaries
8.2.2 A Data Structure for 1D Meshes
8.3 Meshes in 3D
8.3.1 Manifold Meshes
8.3.2 Nonmanifold Meshes
8.3.3 Memory Requirements for Mesh Structures
8.3.4 A Few Mesh Operations
8.3.5 Edge Collapse
8.3.6 Edge Swap
8.4 Discussion and Further Reading
8.5 Exercises
9 Functions on Meshes
9.1 Introduction
9.2 Code for Barycentric Interpolation
9.2.1 A Different View of Linear Interpolation
9.2.2 Scanline Interpolation
9.3 Limitations of Piecewise Linear Extension
9.3.1 Dependence on Mesh Structure
9.4 Smoother Extensions
9.4.1 Nonconvex Spaces
9.4.2 Which Interpolation Method Should I Really Use?
9.5 Functions Multiply Defined at Vertices
9.6 Application: Texture Mapping
9.6.1 Assignment of Texture Coordinates
9.6.2 Details of Texture Mapping
9.6.3 Texture-Mapping Problems
9.7 Discussion
9.8 Exercises
10 Transformations in Two Dimensions
10.1 Introduction
10.2 Five Examples
10.3 Important Facts about Transformations
10.3.1 Multiplication by a Matrix Is a Linear Transformation
10.3.2 Multiplication by a Matrix Is the Only Linear Transformation
10.3.3 Function Composition and Matrix Multiplication Are Related
10.3.4 Matrix Inverse and Inverse Functions Are Related
10.3.5 Finding the Matrix for a Transformation
10.3.6 Transformations and Coordinate Systems
10.3.7 Matrix Properties and the Singular Value Decomposition
10.3.8 Computing the SVD
10.3.9 The SVD and Pseudoinverses
10.4 Translation
10.5 Points and Vectors Again
10.6 Why Use 3 × 3 Matrices Instead of a Matrix and a Vector?
10.7 Windowing Transformations
10.8 Building 3D Transformations
10.9 Another Example of Building a 2D Transformation
10.10 Coordinate Frames
10.11 Application: Rendering from a Scene Graph
10.11.1 Coordinate Changes in Scene Graphs
10.12 Transforming Vectors and Covectors
10.12.1 Transforming Parametric Lines
10.13 More General Transformations
10.14 Transformations versus Interpolation
10.15 Discussion and Further Reading
10.16 Exercises
11 Transformations in Three Dimensions
11.1 Introduction
11.1.1 Projective Transformation Theorems
11.2 Rotations
11.2.1 Analogies between Two and Three Dimensions
11.2.2 Euler Angles
11.2.3 Axis-Angle Description of a Rotation
11.2.4 Finding an Axis and Angle from a Rotation Matrix
11.2.5 Body-Centered Euler Angles
11.2.6 Rotations and the 3-Sphere
11.2.7 Stability of Computations
11.3 Comparing Representations
11.4 Rotations versus Rotation Specifications
11.5 Interpolating Matrix Transformations
11.6 Virtual Trackball and Arcball
11.7 Discussion and Further Reading
11.8 Exercises
12 A 2D and 3D Transformation Library for Graphics
12.1 Introduction
12.2 Points and Vectors
12.3 Transformations
12.3.1 Efficiency
12.4 Specification of Transformations
12.5 Implementation
12.5.1 Projective Transformations
12.6 Three Dimensions
12.7 Associated Transformations
12.8 Other Structures
12.9 Other Approaches
12.10 Discussion
12.11 Exercises
13 Camera Specifications and Transformations
13.1 Introduction
13.2 A 2D Example
13.3 Perspective Camera Specification
13.4 Building Transformations from a View Specification
13.5 Camera Transformations and the Rasterizing Renderer Pipeline
13.6 Perspective and z-values
13.7 Camera Transformations and the Modeling Hierarchy
13.8 Orthographic Cameras
13.8.1 Aspect Ratio and Field of View
13.9 Discussion and Further Reading
13.10 Exercises
14 Standard Approximations and Representations
14.1 Introduction
14.2 Evaluating Representations
14.2.1 The Value of Measurement
14.2.2 Legacy Models
14.3 Real Numbers
14.3.1 Fixed Point
14.3.2 Floating Point
14.3.3 Buffers
14.4 Building Blocks of Ray Optics
14.4.1 Light
14.4.2 Emitters
14.4.3 Light Transport
14.4.4 Matter
14.4.5 Cameras
14.5 Large-Scale Object Geometry
14.5.1 Meshes
14.5.2 Implicit Surfaces
14.5.3 Spline Patches and Subdivision Surfaces
14.5.4 Heightfields
14.5.5 Point Sets
14.6 Distant Objects
14.6.1 Level of Detail
14.6.2 Billboards and Impostors
14.6.3 Skyboxes
14.7 Volumetric Models
14.7.1 Finite Element Models
14.7.2 Voxels
14.7.3 Particle Systems
14.7.4 Fog
14.8 Scene Graphs
14.9 Material Models
14.9.1 Scattering Functions (BSDFs)
14.9.2 Lambertian
14.9.3 Normalized Blinn-Phong
14.10 Translucency and Blending
14.10.1 Blending
14.10.2 Partial Coverage (α)
14.10.3 Transmission
14.10.4 Emission
14.10.5 Bloom and Lens Flare
14.11 Luminaire Models
14.11.1 The Radiance Function
14.11.2 Direct and Indirect Light
14.11.3 Practical and Artistic Considerations
14.11.4 Rectangular Area Light
14.11.5 Hemisphere Area Light
14.11.6 Omni-Light
14.11.7 Directional Light
14.11.8 Spot Light
14.11.9 A Unified Point-Light Model
14.12 Discussion
14.13 Exercises
15 Ray Casting and Rasterization
15.1 Introduction
15.2 High-Level Design Overview
15.2.1 Scattering
15.2.2 Visible Points
15.2.3 Ray Casting: Pixels First
15.2.4 Rasterization: Triangles First
15.3 Implementation Platform
15.3.1 Selection Criteria
15.3.2 Utility Classes
15.3.3 Scene Representation
15.3.4 A Test Scene
15.4 A Ray-Casting Renderer
15.4.1 Generating an Eye Ray
15.4.2 Sampling Framework: Intersect and Shade
15.4.3 Ray-Triangle Intersection
15.4.4 Debugging
15.4.5 Shading
15.4.6 Lambertian Scattering
15.4.7 Glossy Scattering
15.4.8 Shadows
15.4.9 A More Complex Scene
15.5 Intermezzo
15.6 Rasterization
15.6.1 Swapping the Loops
15.6.2 Bounding-Box Optimization
15.6.3 Clipping to the Near Plane
15.6.4 Increasing Efficiency
15.6.5 Rasterizing Shadows
15.6.6 Beyond the Bounding Box
15.7 Rendering with a Rasterization API
15.7.1 The Graphics Pipeline
15.7.2 Interface
15.8 Performance and Optimization
15.8.1 Abstraction Considerations
15.8.2 Architectural Considerations
15.8.3 Early-Depth-Test Example
15.8.4 When Early Optimization Is Good
15.8.5 Improving the Asymptotic Bound
15.9 Discussion
15.10 Exercises
16 Survey of Real-Time 3D Graphics Platforms
16.1 Introduction
16.1.1 Evolution from Fixed-Function to Programmable Rendering Pipeline
16.2 The Programmer’s Model: OpenGL Compatibility (Fixed-Function) Profile
16.2.1 OpenGL Program Structure
16.2.2 Initialization and the Main Loop
16.2.3 Lighting and Materials
16.2.4 Geometry Processing
16.2.5 Camera Setup
16.2.6 Drawing Primitives
16.2.7 Putting It All Together—Part 1: Static Frame
16.2.8 Putting It All Together—Part 2: Dynamics
16.2.9 Hierarchical Modeling
16.2.10 Pick Correlation
16.3 The Programmer’s Model: OpenGL Programmable Pipeline
16.3.1 Abstract View of a Programmable Pipeline
16.3.2 The Nature of the Core API
16.4 Architectures of Graphics Applications
16.4.1 The Application Model
16.4.2 The Application-Model-to-IM-Platform Pipeline (AMIP)
16.4.3 Scene-Graph Middleware
16.4.4 Graphics Application Platforms
16.5 3D on Other Platforms
16.5.1 3D on Mobile Devices
16.5.2 3D in Browsers
16.6 Discussion
17 Image Representation and Manipulation
17.1 Introduction
17.2 What Is an Image?
17.2.1 The Information Stored in an Image
17.3 Image File Formats
17.3.1 Choosing an Image Format
17.4 Image Compositing
17.4.1 The Meaning of a Pixel During Image Compositing
17.4.2 Computing U over V
17.4.3 Simplifying Compositing
17.4.4 Other Compositing Operations
17.4.5 Physical Units and Compositing
17.5 Other Image Types
17.5.1 Nomenclature
17.6 MIP Maps
17.7 Discussion and Further Reading
17.8 Exercises
18 Images and Signal Processing
18.1 Introduction
18.1.1 A Broad Overview
18.1.2 Important Terms, Assumptions, and Notation
18.2 Historical Motivation
18.3 Convolution
18.4 Properties of Convolution
18.5 Convolution-like Computations
18.6 Reconstruction
18.7 Function Classes
18.8 Sampling
18.9 Mathematical Considerations
18.9.1 Frequency-Based Synthesis and Analysis
18.10 The Fourier Transform: Definitions
18.11 The Fourier Transform of a Function on an Interval
18.11.1 Sampling and Band Limiting in an Interval
18.12 Generalizations to Larger Intervals and All of R
18.13 Examples of Fourier Transforms
18.13.1 Basic Examples
18.13.2 The Transform of a Box Is a Sinc
18.13.3 An Example on an Interval
18.14 An Approximation of Sampling
18.15 Examples Involving Limits
18.15.1 Narrow Boxes and the Delta Function
18.15.2 The Comb Function and Its Transform
18.16 The Inverse Fourier Transform
18.17 Properties of the Fourier Transform
18.18 Applications
18.18.1 Band Limiting
18.18.2 Explaining Replication in the Spectrum
18.19 Reconstruction and Band Limiting
18.20 Aliasing Revisited
18.21 Discussion and Further Reading
18.22 Exercises
19 Enlarging and Shrinking Images
19.1 Introduction
19.2 Enlarging an Image
19.3 Scaling Down an Image
19.4 Making the Algorithms Practical
19.5 Finite-Support Approximations
19.5.1 Practical Band Limiting
19.6 Other Image Operations and Efficiency
19.7 Discussion and Further Reading
19.8 Exercises
20 Textures and Texture Mapping
20.1 Introduction
20.2 Variations of Texturing
20.2.1 Environment Mapping
20.2.2 Bump Mapping
20.2.3 Contour Drawing
20.3 Building Tangent Vectors from a Parameterization
20.4 Codomains for Texture Maps
20.5 Assigning Texture Coordinates
20.6 Application Examples
20.7 Sampling, Aliasing, Filtering, and Reconstruction
20.8 Texture Synthesis
20.8.1 Fourier-like Synthesis
20.8.2 Perlin Noise
20.8.3 Reaction-Diffusion Textures
20.9 Data-Driven Texture Synthesis
20.10 Discussion and Further Reading
20.11 Exercises
21 Interaction Techniques
21.1 Introduction
21.2 User Interfaces and Computer Graphics
21.2.1 Prescriptions
21.2.2 Interaction Event Handling
21.3 Multitouch Interaction for 2D Manipulation
21.3.1 Defining the Problem
21.3.2 Building the Program
21.3.3 The Interactor
21.4 Mouse-Based Object Manipulation in 3D
21.4.1 The Trackball Interface
21.4.2 The Arcball Interface
21.5 Mouse-Based Camera Manipulation: Unicam
21.5.1 Translation
21.5.2 Rotation
21.5.3 Additional Operations
21.5.4 Evaluation
21.6 Choosing the Best Interface
21.7 Some Interface Examples
21.7.1 First-Person-Shooter Controls
21.7.2 3ds Max Transformation Widget
21.7.3 Photoshop’s Free-Transform Mode
21.7.4 Chateau
21.7.5 Teddy
21.7.6 Grabcut and Selection by Strokes
21.8 Discussion and Further Reading
21.9 Exercises
22 Splines and Subdivision Curves
22.1 Introduction
22.2 Basic Polynomial Curves
22.3 Fitting a Curve Segment between Two Curves: The Hermite Curve
22.3.1 Bézier Curves
22.4 Gluing Together Curves and the Catmull-Rom Spline
22.4.1 Generalization of Catmull-Rom Splines
22.4.2 Applications of Catmull-Rom Splines
22.5 Cubic B-splines
22.5.1 Other B-splines
22.6 Subdivision Curves
22.7 Discussion and Further Reading
22.8 Exercises
23 Splines and Subdivision Surfaces
23.1 Introduction
23.2 Bézier Patches
23.3 Catmull-Clark Subdivision Surfaces
23.4 Modeling with Subdivision Surfaces
23.5 Discussion and Further Reading
24 Implicit Representations of Shape
24.1 Introduction
24.2 Implicit Curves
24.3 Implicit Surfaces
24.4 Representing Implicit Functions
24.4.1 Interpolation Schemes
24.4.2 Splines
24.4.3 Mathematical Models and Sampled Implicit Representations
24.5 Other Representations of Implicit Functions
24.6 Conversion to Polyhedral Meshes
24.6.1 Marching Cubes
24.7 Conversion from Polyhedral Meshes to Implicits
24.8 Texturing Implicit Models
24.8.1 Modeling Transformations and Textures
24.9 Ray Tracing Implicit Surfaces
24.10 Implicit Shapes in Animation
24.11 Discussion and Further Reading
24.12 Exercises
25 Meshes
25.1 Introduction
25.2 Mesh Topology
25.2.1 Triangulated Surfaces and Surfaces with Boundary
25.2.2 Computing and Storing Adjacency
25.2.3 More Mesh Terminology
25.2.4 Embedding and Topology
25.3 Mesh Geometry
25.3.1 Mesh Meaning
25.4 Level of Detail
25.4.1 Progressive Meshes
25.4.2 Other Mesh Simplification Approaches
25.5 Mesh Applications 1: Marching Cubes, Mesh Repair, and Mesh Improvement
25.5.1 Marching Cubes Variants
25.5.2 Mesh Repair
25.5.3 Differential or Laplacian Coordinates
25.5.4 An Application of Laplacian Coordinates
25.6 Mesh Applications 2: Deformation Transfer and Triangle-Order Optimization
25.6.1 Deformation Transfer
25.6.2 Triangle Reordering for Hardware Efficiency
25.7 Discussion and Further Reading
25.8 Exercises
26 Light
26.1 Introduction
26.2 The Physics of Light
26.3 The Microscopic View
26.4 The Wave Nature of Light
26.4.1 Diffraction
26.4.2 Polarization
26.4.3 Bending of Light at an Interface
26.5 Fresnel’s Law and Polarization
26.5.1 Radiance Computations and an “Unpolarized” Form of Fresnel’s Equations
26.6 Modeling Light as a Continuous Flow
26.6.1 A Brief Introduction to Probability Densities
26.6.2 Further Light Modeling
26.6.3 Angles and Solid Angles
26.6.4 Computations with Solid Angles
26.6.5 An Important Change of Variables
26.7 Measuring Light
26.7.1 Radiometric Terms
26.7.2 Radiance
26.7.3 Two Radiance Computations
26.7.4 Irradiance
26.7.5 Radiant Exitance
26.7.6 Radiant Power or Radiant Flux
26.8 Other Measurements
26.9 The Derivative Approach
26.10 Reflectance
26.10.1 Related Terms
26.10.2 Mirrors, Glass, Reciprocity, and the BRDF
26.10.3 Writing L in Different Ways
26.11 Discussion and Further Reading
26.12 Exercises
27 Materials and Scattering
27.1 Introduction
27.2 Object-Level Scattering
27.3 Surface Scattering
27.3.1 Impulses
27.3.2 Types of Scattering Models
27.3.3 Physical Constraints on Scattering
27.4 Kinds of Scattering
27.5 Empirical and Phenomenological Models for Scattering
27.5.1 Mirror “Scattering”
27.5.2 Lambertian Reflectors
27.5.3 The Phong and Blinn-Phong Models
27.5.4 The Lafortune Model
27.5.5 Sampling
27.6 Measured Models
27.7 Physical Models for Specular and Diffuse Reflection
27.8 Physically Based Scattering Models
27.8.1 The Fresnel Equations, Revisited
27.8.2 The Torrance-Sparrow Model
27.8.3 The Cook-Torrance Model
27.8.4 The Oren-Nayar Model
27.8.5 Wave Theory Models
27.9 Representation Choices
27.10 Criteria for Evaluation
27.11 Variations across Surfaces
27.12 Suitability for Human Use
27.13 More Complex Scattering
27.13.1 Participating Media
27.13.2 Subsurface Scattering
27.14 Software Interface to Material Models
27.15 Discussion and Further Reading
27.16 Exercises
28 Color
28.1 Introduction
28.1.1 Implications of Color
28.2 Spectral Distribution of Light
28.3 The Phenomenon of Color Perception and the Physiology of the Eye
28.4 The Perception of Color
28.4.1 The Perception of Brightness
28.5 Color Description
28.6 Conventional Color Wisdom
28.6.1 Primary Colors
28.6.2 Purple Isn’t a Real Color
28.6.3 Objects Have Colors; You Can Tell by Looking at Them in White Light
28.6.4 Blue and Green Make Cyan
28.6.5 Color Is RGB
28.7 Color Perception Strengths andWeaknesses
28.8 Standard Description of Colors
28.8.1 The CIE Description of Color
28.8.2 Applications of the Chromaticity Diagram
28.9 Perceptual Color Spaces
28.9.1 Variations and Miscellany
28.10 Intermezzo
28.11 White
28.12 Encoding of Intensity, Exponents, and Gamma Correction
28.13 Describing Color
28.13.1 The RGB Color Model
28.14 CMY and CMYK Color
28.15 The YIQ Color Model
28.16 Video Standards
28.17 HSV and HLS
28.17.1 Color Choice
28.17.2 Color Palettes
28.18 Interpolating Color
28.19 Using Color in Computer Graphics
28.20 Discussion and Further Reading
28.21 Exercises
29 Light Transport
29.1 Introduction
29.2 Light Transport
29.2.1 The Rendering Equation, First Version
29.3 A Peek Ahead
29.4 The Rendering Equation for General Scattering
29.4.1 The Measurement Equation
29.5 Scattering, Revisited
29.6 AWorked Example
29.7 Solving the Rendering Equation
29.8 The Classification of Light-Transport Paths
29.8.1 Perceptually Significant Phenomena and Light Transport
29.9 Discussion
29.10 Exercise
30 Probability and Monte Carlo Integration
30.1 Introduction
30.2 Numerical Integration
30.3 Random Variables and Randomized Algorithms
30.3.1 Discrete Probability and Its Relationship to Programs
30.3.2 Expected Value
30.3.3 Properties of Expected Value, and Related Terms
30.3.4 Continuum Probability
30.3.5 Probability Density Functions
30.3.6 Application to the Sphere
30.3.7 A Simple Example
30.3.8 Application to Scattering
30.4 Continuum Probability, Continued
30.5 Importance Sampling and Integration
30.6 Mixed Probabilities
30.7 Discussion and Further Reading
30.8 Exercises
31 Computing Solutions to the Rendering Equation: Theoretical Approaches
31.1 Introduction
31.2 Approximate Solutions of Equations
31.3 Method 1: Approximating the Equation
31.4 Method 2: Restricting the Domain
31.5 Method 3: Using Statistical Estimators
31.5.1 Summing a Series by Sampling and Estimation
31.6 Method 4: Bisection
31.7 Other Approaches
31.8 The Rendering Equation, Revisited
31.8.1 A Note on Notation
31.9 What Do We Need to Compute?
31.10 The Discretization Approach: Radiosity
31.11 Separation of Transport Paths
31.12 Series Solution of the Rendering Equation
31.13 Alternative Formulations of Light Transport
31.14 Approximations of the Series Solution
31.15 Approximating Scattering: Spherical Harmonics
31.16 Introduction to Monte Carlo Approaches
31.17 Tracing Paths
31.18 Path Tracing and Markov Chains
31.18.1 The Markov Chain Approach
31.18.2 The Recursive Approach
31.18.3 Building a Path Tracer
31.18.4 Multiple Importance Sampling
31.18.5 Bidirectional Path Tracing
31.18.6 Metropolis Light Transport
31.19 Photon Mapping
31.19.1 Image-Space Photon Mapping
31.20 Discussion and Further Reading
31.21 Exercises
32 Rendering in Practice
32.1 Introduction
32.2 Representations
32.3 Surface Representations and Representing BSDFs Locally
32.3.1 Mirrors and Point Lights
32.4 Representation of Light
32.4.1 Representation of Luminaires
32.5 A Basic Path Tracer
32.5.1 Preliminaries
32.5.2 Path-Tracer Code
32.5.3 Results and Discussion
32.6 Photon Mapping
32.6.1 Results and Discussion
32.6.2 Further Photon Mapping
32.7 Generalizations
32.8 Rendering and Debugging
32.9 Discussion and Further Reading
32.10 Exercises
33 Shaders
33.1 Introduction
33.2 The Graphics Pipeline in Several Forms
33.3 Historical Development
33.4 A Simple Graphics Program with Shaders
33.5 A Phong Shader
33.6 Environment Mapping
33.7 Two Versions of Toon Shading
33.8 Basic XToon Shading
33.9 Discussion and Further Reading
33.10 Exercises
34 Expressive Rendering
34.1 Introduction
34.1.1 Examples of Expressive Rendering
34.1.2 Organization of This Chapter
34.2 The Challenges of Expressive Rendering
34.3 Marks and Strokes
34.4 Perception and Salient Features
34.5 Geometric Curve Extraction
34.5.1 Ridges and Valleys
34.5.2 Suggestive Contours
34.5.3 Apparent Ridges
34.5.4 Beyond Geometry
34.6 Abstraction
34.7 Discussion and Further Reading
35 Motion
35.1 Introduction
35.2 Motivating Examples
35.2.1 A Walking Character (Key Poses)
35.2.2 Firing a Cannon (Simulation)
35.2.3 Navigating Corridors (Motion Planning)
35.2.4 Notation
35.3 Considerations for Rendering
35.3.1 Double Buffering
35.3.2 Motion Perception
35.3.3 Interlacing
35.3.4 Temporal Aliasing and Motion Blur
35.3.5 Exploiting Temporal Coherence
35.3.6 The Problem of the First Frame
35.3.7 The Burden of Temporal Coherence
35.4 Representations
35.4.1 Objects
35.4.2 Limiting Degrees of Freedom
35.4.3 Key Poses
35.4.4 Dynamics
35.4.5 Procedural Animation
35.4.6 Hybrid Control Schemes
35.5 Pose Interpolation
35.5.1 Vertex Animation
35.5.2 Root Frame Motion
35.5.3 Articulated Body
35.5.4 Skeletal Animation
35.6 Dynamics
35.6.1 Particle
35.6.2 Differential Equation Formulation
35.6.3 Piecewise-Constant Approximation
35.6.4 Models of Common Forces
35.6.5 Particle Collisions
35.6.6 Dynamics as a Differential Equation
35.6.7 Numerical Methods for ODEs
35.7 Remarks on Stability in Dynamics
35.8 Discussion
36 Visibility Determination
36.1 Introduction
36.1.1 The Visibility Function
36.1.2 Primary Visibility
36.1.3 (Binary) Coverage
36.1.4 Current Practice and Motivation
36.2 Ray Casting
36.2.1 BSP Ray-Primitive Intersection
36.2.2 Parallel Evaluation of Ray Tests
36.3 The Depth Buffer
36.3.1 Common Depth Buffer Encodings
36.4 List-Priority Algorithms
36.4.1 The Painter’s Algorithm
36.4.2 The Depth-Sort Algorithm
36.4.3 Clusters and BSP Sort
36.5 Frustum Culling and Clipping
36.5.1 Frustum Culling
36.5.2 Clipping
36.5.3 Clipping to the Whole Frustum
36.6 Backface Culling
36.7 Hierarchical Occlusion Culling
36.8 Sector-based Conservative Visibility
36.8.1 Stabbing Trees
36.8.2 Portals and Mirrors
36.9 Partial Coverage
36.9.1 Spatial Antialiasing (xy)
36.9.2 Defocus (uv)
36.9.3 Motion Blur (t)
36.9.4 Coverage as a Material Property (α)
36.10 Discussion and Further Reading
36.11 Exercise
37 Spatial Data Structures
37.1 Introduction
37.1.1 Motivating Examples
37.2 Programmatic Interfaces
37.2.1 Intersection Methods
37.2.2 Extracting Keys and Bounds
37.3 Characterizing Data Structures
37.3.1 1D Linked List Example
37.3.2 1D Tree Example
37.4 Overview of kd Structures
37.5 List
37.6 Trees
37.6.1 Binary Space Partition (BSP) Trees
37.6.2 Building BSP Trees: oct tree, quad tree, BSP tree, kd tree
37.6.3 Bounding Volume Hierarchy
37.7 Grid
37.7.1 Construction
37.7.2 Ray Intersection
37.7.3 Selecting Grid Resolution
37.8 Discussion and Further Reading
38 Modern Graphics Hardware
38.1 Introduction
38.2 NVIDIA GeForce 9800 GTX
38.3 Architecture and Implementation
38.3.1 GPU Architecture
38.3.2 GPU Implementation
38.4 Parallelism
38.5 Programmability
38.6 Texture, Memory, and Latency
38.6.1 Texture Mapping
38.6.2 Memory Basics
38.6.3 Coping with Latency
38.7 Locality
38.7.1 Locality of Reference
38.7.2 Cache Memory
38.7.3 Divergence
38.8 Organizational Alternatives
38.8.1 Deferred Shading
38.8.2 Binned Rendering
38.8.3 Larrabee: A CPU/GPU Hybrid
38.9 GPUs as Compute Engines
38.10 Discussion and Further Reading
38.11 Exercises
List of Principles
Bibliography
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z