Cohen M.F., Wallace J.R. - Radiosity and realistic image synthesis (1995)(en)

Contents

Foreword by Donald Greenberg			xi
Preface			xiii
1 Introduction			1
1.1	Realistic Image Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		. 1
	1.1.1	Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. 2
	1.1.2	Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. 2
1.2	A Short Historical Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		. 4
	1.2.1	Raster Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. 5
	1.2.2	Global Illumination Models . . . . . . . . . . . . . . . . . . . . . . . . . .	. 6
	1.2.3	Early Radiosity Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. 7
	1.2.4	The Rendering Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. 8
1.3	Radiosity and Finite Element Methods . . . . . . . . . . . . . . . . . . . . . . .		. 8
1.4	The Radiosity Method and This Book . . . . . . . . . . . . . . . . . . . . . . . .		10
2 Rendering Concepts by Pat Hanrahan			13
2.1	Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		13
2.2	Basic Optics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		14
2.3	Radiometry and Photometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		15
2.4	The Light Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		17
	2.4.1	Transport Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	17
	2.4.2	Radiance and Luminance . . . . . . . . . . . . . . . . . . . . . . . . . . . .	19
	2.4.3	Irradiance and Illuminance . . . . . . . . . . . . . . . . . . . . . . . . . . .	24
	2.4.4	Radiosity and Luminosity . . . . . . . . . . . . . . . . . . . . . . . . . . . .	25
	2.4.5 Radiant and Luminous Intensity . . . . . . . . . . . . . . . . . . . . . . .		25
	2.4.6 Summary of Radiometric and Photometric Quantities . . . . . .		27
2.5	Reflection Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		28
	2.5.1 The Bidirectional Reflection distribution Function . . . . . . . .		28
	2.5.2	Mirror Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	30
	2.5.3	The Reflectance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	31
	2.5.4	Lambertian Diffuse Reflection . . . . . . . . . . . . . . . . . . . . . . . .	32
	2.5.5	Glossy Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	33
2.6	The Rendering Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		36
	2.6.1 Local or Direct Illumination . . . . . . . . . . . . . . . . . . . . . . . . . .		37
Radiosity and Realistic Image Synthesis			iv
Edited by Michael F. Cohen and John R. Wallace

	2.6.2 Global or Indirect Illumination . . . . . . . . . . . . . . . . . . . . . . . .		38
	2.6.3	The Radiosity Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	40
3 Discretizing the Radiosity Equation			41
3.1	The Radiosity Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		41
3.2	Making Image Synthesis Tractable . . . . . . . . . . . . . . . . . . . . . . . . . .		42
3.3	The Radiosity Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		46
3.4	Approximating Radiosity across a Surface . . . . . . . . . . . . . . . . . . . .		48
3.5	Error Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		53
	3.5.1	Point Collocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	55
	3.5.2 Galerkin Form of Weighted Residuals . . . . . . . . . . . . . . . . . .		56
3.6	Constant Element Radiosities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		57
3.7	Higher-order Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		60
3.8	Parametric Mapping to a Master Element . . . . . . . . . . . . . . . . . . . . .		61
	3.8.1	Master Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	61
	3.8.2	Isoparametric Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	62
3.9	Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		63
4 The Form Factor			65
I.	The Form Factor Integral		65
4.1	The Coefficients of K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		66
4.2	The Differential Form Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		67
4.3	Three Formulations of the Form Factor . . . . . . . . . . . . . . . . . . . . . . .		69
4.4	Computing the Form Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		70
II.	Closed Form Solutions for the Form Factor		72
4.5	Formulae for Simple Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		72
4.6	Differential Area to Convex Polygon . . . . . . . . . . . . . . . . . . . . . . . .		72
4.7	General Polygon to Polygon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		74
III.	Numerical Solutions for the Form Factor		75

4.8 Numerical Integration in General . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.8.1 Gaussian Quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.8.2 Quadrature Points and the Form Factor Integral . . . . . . . . . . 77 4.8.3 Monte Carlo Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.9 Evaluating the Inner Integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.9.1 Hemisphere Sampling Algorithms . . . . . . . . . . . . . . . . . . . . . 79 4.9.2 Nusselt Analog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.9.3 The Hemicube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.9.4 Single-Plane Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.9.5 Monte Carlo Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.9.6 Area Sampling Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.10 Full Area-to-Area Quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Radiosity and Realistic Image Synthesis	v
Edited by Michael F. Cohen and John R. Wallace

		4.10.1 Monte Carlo Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . .		. 94
	4.11	Contour Integral Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		. 95
	4.12	A Simple Test Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		96
	4.13	Nonconstant Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		98
		4.13.1 The Hemicube for General Form Factors . . . . . . . . . . . . . . . .		99
		4.13.2 Monte Carlo for General Form Factors . . . . . . . . . . . . . . . . .		99
		4.13.3 Singularities in the Integrand . . . . . . . . . . . . . . . . . . . . . . . .		100
	4.14	Acceleration Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		103
		4.14.1 Hemicube Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . .		103
		4.14.2 Ray Tracing Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . .		106
5	Radiosity Matrix Solutions			109
	5.1	Qualities of the Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		110
	5.2	Linear System Solution Methods . . . . . . . . . . . . . . . . . . . . . . . . . . .		112
		5.2.1	Direct Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	112
		5.2.2	Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	112
	5.3	Relaxation Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		113
		5.3.1	Jacobi iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	114
		5.3.2	Gauss-Seidel Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	114
		5.3.3	Southwell Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	116
		5.3.4	Ambient Energy and Overelaxation . . . . . . . . . . . . . . . . . . .	122
		5.4	Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . .	126
		5.4.1	Lighting Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	126
		5.4.2	Reflectivity Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	127
		5.4.3	Changes in Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	127
		5.5	Parallel Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . .	129
6	Domain Subdivision			131
	6.1	Error Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		132
		6.1.1	True Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	132
		6.1.2	Local Estimate of Approximation Error . . . . . . . . . . . . . . . .	132
		6.1.3	Residual of the Approximate Solution . . . . . . . . . . . . . . . . .	134
		6.1.4	Error Based on the Behavior of the Kernel . . . . . . . . . . . . .	135
		6.1.5	Image Based Error Metrics . . . . . . . . . . . . . . . . . . . . . . . . . .	135
		6.1.6	Perceptually Based Error Metrics . . . . . . . . . . . . . . . . . . . . .	136
	6.2	Mesh Characteristics and Accuracy . . . . . . . . . . . . . . . . . . . . . . . . .		136
		6.2.1	An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	137
		6.2.2	Mesh Density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	139
		6.2.3	Element Order and Continuity . . . . . . . . . . . . . . . . . . . . . . .	142
		6.2.4	Element Shape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	144
		6.2.5	Discontinuities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	149
	6.3	Automatic Meshing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . .		152
Radiosity and Realistic Image Synthesis				vi
Edited by Michael F. Cohen and John R. Wallace

		6.3.1	A Posteriori Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	154
		6.3.2 Adaptive Subdivision: H-refinement for Radiosity . . . . . . .		157
		6.3.3 Error Estimation for Adaptive Subdivision . . . . . . . . . . . . .		159
		6.3.4 Deciding How to Subdivide . . . . . . . . . . . . . . . . . . . . . . . . .		165
7	Hierarchical Methods			167
	I. Hierarchical Subdivision			168
	7.1	A Physical Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		168
	7.2	Two-Level Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		169
	7.3	The K Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		171
	7.4	Multilevel hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		176
		7.4.1	N-Body Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	177
		7.4.2 Radiosity and the N-Body Problem . . . . . . . . . . . . . . . . . . .		177
		7.4.3	Hierarchical Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . .	177
		7.4.4 Solution of the Hierarchical System . . . . . . . . . . . . . . . . . . .		181
		7.4.5	The Oracle Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	182
		7.4.6 Progressive Refinement of the Hierarchy . . . . . . . . . . . . . . .		184
		7.4.7	Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	187
	II. Hierarchical Basis Functions and Wavelets			187
	7.5	Hierarchical Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		187
	7.6	Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		190
		7.6.1	Haar Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	190
		7.6.2	Vanishing Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	194
		7.6.3 Vanishing Moments and Sparse Representations . . . . . . . . .		194
		7.6.4 A Wavelet Radiosity Algorithm . . . . . . . . . . . . . . . . . . . . . .		198
	III. Importance-Based Radiosity			201
	7.7	Importance Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		201
		7.7.1	The Importance Equation . . . . . . . . . . . . . . . . . . . . . . . . . . .	202
		7.7.2	Importance-Based Error . . . . . . . . . . . . . . . . . . . . . . . . . . . .	204
	7.8	Hierarchical Radiosity and Importance . . . . . . . . . . . . . . . . . . . . . .		205
		7.8.1	Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	205
		7.8.2	Example Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	208
8	Meshing			209
	8.1	Basic Subdivision Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		209
	8.2	Mesh Template Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		210
		8.2.1	Grid Superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	210
		8.2.2	Template Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	211
		8.2.3	Multiblocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	212
		8.2.4 Adaptive Subdivision with Templates . . . . . . . . . . . . . . . . .		214
	8.3	Decomposition Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		216
		8.3.1	Nodes-Elements-Together Decomposition . . . . . . . . . . . . . .	217
Radiosity and Realistic Image Synthesis				vii
Edited by Michael F. Cohen and John R. Wallace

	8.3.2	Decomposition by Recursive Splitting . . . . . . . . . . . . . . . . .	217
	8.3.3	Decomposition by Advancing Front . . . . . . . . . . . . . . . . . . .	218
	8.3.4	Nodes-First Decomposition . . . . . . . . . . . . . . . . . . . . . . . . .	219
8.4	Mesh Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		221
8.5	Discontinuity Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		222
	8.5.1	Discontinuities in Value . . . . . . . . . . . . . . . . . . . . . . . . . . . .	222
	8.5.2	First and Second Derivative Discontinuities . . . . . . . . . . . .	224
	8.5.3	Shadow Volume Algorithms . . . . . . . . . . . . . . . . . . . . . . . .	229
	8.5.4	Critical Surface Algorithms . . . . . . . . . . . . . . . . . . . . . . . . .	231
8.6	Topological Data Structures and Operators . . . . . . . . . . . . . . . . . . .		234
	8.6.1	Data Structure Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	235
	8.6.2	The Winged-Edge Data Structure . . . . . . . . . . . . . . . . . . . . .	235
8.7	Alternatives to Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		239
9 Rendering			243
9.1	Reconstructing the Radiosity Function . . . . . . . . . . . . . . . . . . . . . .		244
9.2	Interpolation Methods for Rendering . . . . . . . . . . . . . . . . . . . . . . . .		245
	9.2.1	C0 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	245
	9.2.2	C1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	252
9.3	Two-Pass Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		257
	9.3.1	Evaluating the Radiosity Equation per Pixel . . . . . . . . . . . .	259
	9.3.2	Multi-Pass Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	265
9.4	Incorporating Surface Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		266
	9.4.1	Texture Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	266
	9.4.2	Bump Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	267
9.5	Mapping Radiosities to Pixel Colors . . . . . . . . . . . . . . . . . . . . . . . .		267
	9.5.1	Gamma Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	268
	9.5.2	Real-World Luminance to Pixel Luminance . . . . . . . . . . . .	268
9.6	Color	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	273
	9.6.1	Human Vision and Color . . . . . . . . . . . . . . . . . . . . . . . . . . .	274
	9.6.2	Color Matching Functions and the CIE Chromaticity Di-
		agram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. 76
	9.6.3	Color Spaces and Image Synthesis . . . . . . . . . . . . . . . . . . . .	280
	9.6.4	Direct Use of Spectral Data . . . . . . . . . . . . . . . . . . . . . . . . .	283
9.7	Hardware Accelerated Rendering . . . . . . . . . . . . . . . . . . . . . . . . . .		284
	9.7.1	Walkthroughs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	284
	9.7.2	Hardware-Supported Texture Mapping . . . . . . . . . . . . . . . .	285
	9.7.3	Visibility Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . .	286
10 Extensions			289
10.1	Nondiffuse Light Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		289
	10.1.1 Form Factors to and from Light Sources . . . . . . . . . . . . . . .		290
Radiosity and Realistic Image Synthesis			viii
Edited by Michael F. Cohen and John R. Wallace

10.1.2 Point Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 293
10.1.3 Parallel Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 293
10.1.4 General Luminaires . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 293
10.1.5 Spot Lights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 295
10.1.6 Sky Light . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 295
10.1.7 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 297
10.1.8 Light Source Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 298
10.2 Directional Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 299
10.2.1 Classifying Transport Paths . . . . . . . . . . . . . . . . . . . . .	. . . . 299
10.2.2 Tracing the Transport Paths . . . . . . . . . . . . . . . . . . . . .	. . . . 302
10.2.3 Implicit Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 307
10.2.4 Explicit Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 309
10.2.5 Non-Lambertian Reflection and Hierarchical Methods	. . . . 316
10.2.6 Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 317
10.2.7 Two-Pass Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 319
10.2.8 Surface Reflectance/Transmittance Data . . . . . . . . . . .	. . . . 324
10.3 Participating Media . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 325
10.3.1 Path Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 326
10.3.2 The Zonal Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 327
11 Applications and Research	331
11.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 331
11.1.1 Architectural Design . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 332
11.1.2 Lighting Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 334
11.1.3 Remote Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 338
11.1.4 Visual Shape Understanding . . . . . . . . . . . . . . . . . . . . .	. . . 338
11.1.5 Infrared Signature Analysis . . . . . . . . . . . . . . . . . . . . . .	. . . 339
11.1.6 Fine Arts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 340
11.2 Experimental Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 340
11.3 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 343
11.3.1 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 343
11.3.2 Perceptually Based Error Metrics . . . . . . . . . . . . . . . . . .	. . . 343
11.3.3 Physically Based Emission and BRDF Data . . . . . . . . .	. . . 344
11.3.4 Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 345
11.3.5 Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 345
11.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 347
Bibliography	349
Index	373

Radiosity and Realistic Image Synthesis	ix
Edited by Michael F. Cohen and John R. Wallace

Foreword

For the past 25 years, researchers in the field of computer graphics have continuously striven for the production of realistic images of nonexistent environments. To attain this goal and its ultimate potential for design and aesthetic evaluations, it is necessary to accurately represent the appearance of objects and scenes as they look to us. This requires the knowledge of how to simulate both the physical behavior of light and the perceptual behavior of the human visual system.

The accurate simulation of physical processes is crucial for realistic image synthesis. Ad hoc procedures, despite the fact that they can produce pretty pictures, will not suffice. The radiosity method, originally based on principles of thermodynamics, provides this physical basis and establishes the foundations for future rendering and display systems.

More explicitly, the creation of photorealistic images requires four basic components, a local model of light reflection, a means for simulating the propagation of energy throughout an environment, the appropriate strategies for sampling the scene, and procedurally accurate methods for displaying the results. The radiosity method discussed in this book describes each of these steps in great detail.

Historically, a major argument against the use of radiosity procedures has been the excessive computing demands. Today these constraints are rapidly being eliminated. During the last decade alone, processing power of workstations and personal computers has increased by three orders of magnitude. However skeptical one might be, all indications are that the trend of almost doubling computer power each year will continue until at least the end of this decade. Memory and storage costs have also dropped, by approximately four orders of magnitude since the early 1970s. Most recently, new advances in network technology have improved the possibility for image transmission rates by six orders of magnitude from what was available two decades ago. Further advances in the technology will occur due to parallelism and compression schemes.

Display technology is also accelerating at a remarkable pace. The dot spacing in printing technologies has been vastly reduced. High-resolution display monitors are now commonplace. The advent of high-definition television will push video technology further, both in terms of refresh rates and display resolution, and ultimately in cost due to the economics of mass production. For normal viewing conditions, resolutions will have surpassed the visual acuity of the human eye. Intensity ranges will be increased, and the speed of displays is already sufficiently fast to imply continuous motion.

With these dramatic advances in computing and display technologies, the

Radiosity and Realistic Image Synthesis	x
Edited by Michael F. Cohen and John R. Wallace

FORWARD

arguments against the computational complexity of image synthesis techniques fall hollow. Processing and storage will essentially be free, and transmission will be sufficiently fast to deliver high quality picture information and allow the use of remote computing nodes. The computing obstacles of the past will have been overcome.

What is now needed is the ability to mimic the complex physical behavior of light distribution, from microscopic to macroscopic ranges. The radiosity method for image synthesis provides the theoretical underpinnings and algorithmic techniques toward these ends. With future experimental measurements and comparisons, these methods can be continually refined to improve their accuracy.

This book is the most thorough treatise on the radiosity method yet to be published in the field of computer graphics. The text includes detailed descriptions of all of the major components required to create a system for displaying modeled environments. From the explanations of the fundamental scientific bases to the state-of-the-art algorithms for implementation, the topics are covered in a clear and comprehensive way. The authors are to be congratulated for their in-depth treatment of the subject and for the presentation of a text that can significantly influence rendering systems of the future. The quest for photorealism will continue!

Donald P. Greenberg

Professor and Director

Program of Computer Graphics

Cornell University

Radiosity and Realistic Image Synthesis	xi
Edited by Michael F. Cohen and John R. Wallace

Preface

Over the past decade, computer graphics has exploded out of university research laboratories onto television and cinema screens, and into medical imaging, scientific visualization and computer-aided design systems. A persistent goal through much of the research that has contributed to these developments has been to recreate, with the computer, strikingly realistic images of environments that do not (and often could not) exist. This field of endeavor has come to be known as realistic image synthesis. Radiosity provides one important approach to evaluating a physically-based illumination model, which is a key part of image synthesis.

The number of papers published on radiosity and related techniques increases yearly. Although the field is by no means mature, it is at a transition point, with early intuitive methods being replaced by approaches based on more rigorous attention to underlying physical processes and numerical methods. Thus, this is a natural time to summarize the research to date and to present it in a uniform format.

Our goal in writing this book is to survey the state-of-the-art in radiosity and related image synthesis research, to explain the underlying theory, and to provide a framework that organizes the broad and growing literature surrounding this field. The book is intended for those interested in pursuing research in global illumination and image synthesis. It should also provide a useful theoretical background and insight into many practical issues, for those implementing radiosity or other global illumination systems.

After a short introductory chapter, the book continues with a chapter by Pat Hanrahan that carefully defines the terminology and concepts of radiometry and photometry, the fields concerned with the measurement of light. This discussion ends with the derivation of the rendering equation and its specialization in the form of the radiosity integral equation. The following three chapters discuss the use of finite element methods to solve this equation, by first formulating an approximately equivalent set of linear equations, then evaluating the coefficients of the linear system (the form factors), and finally solving the resulting matrix equation.

This is followed by three chapters in which the topic of domain subdivision (or meshing) is discussed. The discussion begins with an overview of meshing issues, then takes an aside to discuss new hierarchical formulations of the radiosity problem including applications of wavelet methods, and closes with a chapter on the practical issues in generating a good mesh.

Chapter 9 explores the final step in the image synthesis process, that is, mapping the results of the numerical simulation to a display device. In this

Radiosity and Realistic Image Synthesis	xii
Edited by Michael F. Cohen and John R. Wallace

PREFACE

context, the peculiarities of the human visual system are discussed, ranging from the nonlinear response of the eye to luminance, to the tristimulus theory of color perception. Chapter io then expands the scope of the radiosity methods by lifting many of the restrictions assumed in the earlier discussion, such as diffuse surfaces and non-participating media. Finally, the book concludes with a chapter that explores a number of developing applications of the radiosity method, and takes a moment to look towards the future.

The presentation in this book assumes a familiarity with the basic concepts of computer graphics. There are a number of excellent computer graphics texts that more fully explore some of the techniques that are called on in the algorithms described here [84, 97, 173, 195, 258]. The discussion also assumes an understanding of undergraduate calculus and linear algebra. Where more advanced mathematical concepts are required, an effort is made to provide the reader with enough background information to understand and appreciate the material.

Acknowledgments

We thank the many colleagues who have directly and indirectly contributed to the making of this book.

Without the dedication and persistent efforts of Prof. Donald P. Greenberg of Cornell University, neither author would be in a position today to write this text. His contributions to the development of the field of image synthesis are well known. We thank him personally for inviting us into Cornell’s Program of Computer Graphics where both authors were introduced to radiosity and image synthesis, and for contributing the Foreword to this book.

Pat Hanrahan, beyond contributing a chapter to the book, is also largely responsible for providing the first author with the stimulating environment at Princeton University in which to work.

We would like to especially acknowledge the great efforts that went into reviewing chapters of this book by Ken Chiu, Robert Cross, Brian Curless, Stuart Feldman, Alain Fournier, John Fujii, Steven Gortler, Paul Lalonde, Marc Levoy, Robert Lewis, Dani Lischinski, Earlin Lutz, Holly Rushmeier, David Salesin, Peter Shirley, and Filippo Tampieri.

We thank Jutta Joesch for many hours of editing this text and for her enormous help in gaining a better understanding of how to explain many of the more difficult concepts presented. We would also like to thank Steven Gortler and Peter Schröder for many discussions leading to much of the material on wavelets in Chapter 7; Holly Rushmeier for numerous discussions that contributed materially to the content of this book; John Abel, Maged Tawfik, Paul Heckbert, Mark Reichert, Seth Teller, David Munson, and Stuart Feldman for valuable

Radiosity and Realistic Image Synthesis	xiii
Edited by Michael F. Cohen and John R. Wallace