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