Mathematical and computer programming techniques for computer graphics

Cover......Page 1
Mathematical and Computer Programming Techniques for Computer Graphics (Springer, 2006)......Page 3
ISBN 978-1-8233-902-9......Page 4
Preface......Page 6
Acknowledgements......Page 8
Contents......Page 9
Some Definitions of Terms......Page 19
Set Theory Survival Kit......Page 21
1.1.2 Notation and Set Specification......Page 22
1.1.3 Set Membership......Page 23
1.4 Subsets......Page 24
1.6 Proper Subsets and Supersets......Page 25
1.10 Venn-Euler Diagrams......Page 26
1.12.1 Set Union......Page 29
1.12.2 Set Intersection......Page 30
1.12.3 Set Difference......Page 31
1.12.4 The Symmetric Difference of Two Sets......Page 32
1.12.5 The Complement of a Set......Page 36
1.13.1 The Rules of the Algebra of Sets......Page 40
1.13.2 The Duality Principle......Page 42
1.14.2 Closure......Page 43
1.14.4 The Set of Rational Numbers Q......Page 44
1.14.6 The Set of Natural Numbers N......Page 45
1.14.8.3 The Set of Transcendental Numbers T......Page 46
1.14.9 Ordering Relations or Inequalities......Page 47
1.14.10 The Absolute Value or Modulus of a Number......Page 48
1.14.11 Real Number Intervals......Page 50
1.14.13 Real Number Interval Arithmetic......Page 52
1.14.14 Bounded and Unbounded Real Number Sets......Page 53
1.15 Ordered Pairs and Ordered n-tuples......Page 54
1.16 The Cartesian Product of Sets......Page 55
1.17 Functions......Page 56
1.17.1 The Formal Definition of a Function......Page 57
1.17.3 Equality of Functions......Page 59
1.17.5.2 Injective Functions or One-to-One Functions......Page 61
1.17.5.3 Surjective Functions or Onto Functions......Page 62
1.17.5.4 Bijective Functions or One-to-One Correspondences......Page 63
1.17.6 Constant Functions......Page 65
1.17.8 The Composition or Product of Functions......Page 66
1.17.9 The Inverse of a Function......Page 67
1.17.9.2 Applying the Inverse of a Function to a Subset of its Co-domain......Page 68
1.17.10 The Inverse Function......Page 70
1.17.11 Theorems on the Inverse Function......Page 71
1.17.12 The Graph of a Function......Page 72
1.17.13 The Redefinition of a Function as a Set of OrderedPairs......Page 75
1.18 Families of Indexed Sets......Page 76
1.19 The Generalised Set Union and Intersection Operations......Page 78
1.19.2 Some Algebraic Rules for the Generalised SetOperations......Page 79
1.20.1 Equivalent Sets......Page 80
1.21 The Power Set of a Set......Page 81
2.1 Some Basic Definitions and Notation......Page 82
2.2 Multiplication of a Vector by a Scalar......Page 85
2.3 Vector Addition......Page 86
2.5 The Vector Equation of a Line......Page 88
2.6 Linear Dependence/Independence of Vectors......Page 89
2.8.2 Vector Addition......Page 91
2.9 Orthogonal, Orthonormal and Right-Handed Vector Bases......Page 92
2.10 Cartesian Bases and Cartesian Coordinates......Page 94
2.12 The Scalar Product of Vectors......Page 95
2.14.2 Normalising a Vector......Page 97
2.14.3 The Projection of a Vector onto Another......Page 98
2.15 The Direction Ratios and Direction Cosines of a Vector......Page 99
2.16 The Vector Product of two Vectors......Page 101
2.17 The Vector Product Expressed in Terms of its Components......Page 102
2.18.1 The Geometric Interpretation of the Vector Product......Page 103
2.18.4 The Magnitude of the Sine of the Angle betweenTwo Vectors......Page 104
2.19.1 The Triple Scalar Product......Page 105
2.19.2 The Triple Vector Product......Page 107
2.19.3 The Scalar Product of Two Vector Products......Page 108
2.20 The Components of a Vector Relativeto a Non-orthogonal Basis......Page 109
2.21 The Decomposition of a Vector According to a Basis......Page 112
2.22.1 The Line Defined by Two Position Vectors......Page 113
2.22.2 The Line Defined by a Position Vector and Direction Vector......Page 114
2.23.1 The Plane Defined by a Position Vectorand a Normal Vector......Page 115
2.23.2 The Plane Defined by Three Position Vectors......Page 116
2.24.1 The Distance Between Two Points in Space......Page 118
2.24.2 The Perpendicular Distance from a Point to a Line......Page 119
2.24.3 The Distance of a Point from a Line......Page 120
2.24.4 The Distance Between Two Parallel Lines......Page 121
2.24.5 The Distance Between Two Non-Parallel Lines......Page 122
2.24.7 The Cosine of the Angle between Two Planes......Page 123
2.24.8 The Distance of a Point from a Plane......Page 124
2.24.9 The Point of Intersection of a Line and a Plane......Page 126
Vector Addition......Page 127
The Triple Scalar P......Page 128
The Vector Product of Two Vector Products......Page 129
2.26 A Simple Vector Algebra C Library......Page 130
Matrix Algebra Survival Kit......Page 131
3.1 The Definition of a Matrix......Page 134
3.2 Square Matrices......Page 135
3.5 The Zero or Null Matrix......Page 136
3.6 The Transpose of a Matrix......Page 137
3.7 Symmetric and Antisymmetric Matrices......Page 138
3.8 Triangular Matrices......Page 139
3.10 Equality of Matrices......Page 140
3.11.1 Addition and Subtraction of Matrices......Page 141
3.11.2 Multiplication of a Matrix by a Scalar......Page 142
3.11.3 Multiplication of a Vector by a Vector......Page 143
3.11.4 Multiplication of a Matrix by a Vector......Page 144
3.11.5 Multiplication of Two Matrices......Page 145
3.11.6 Powers of Matrices......Page 146
3.12 The Minor of a Matrix......Page 147
3.13 The Determinant of a Matrix......Page 148
3.14.1 The Transposition Rule......Page 150
3.14.3 The Factor Rule......Page 151
3.14.6 The Product Rule......Page 152
3.14.8 The Conditions for a Zero Determinant......Page 153
3.15 The Cofactor of an Element of a Matrix and the Cofactor Matrix......Page 154
3.16 The Ajoint Matrix or Adjugate Matrix......Page 155
3.17 The Reciprocal or Inverse of a Matrix......Page 156
3.17.1 Justification of the Definition of the Inverse......Page 157
3.18 A Theorem on Invertible Matrices and their Determinants......Page 158
3.19 Axioms and Rules of Matrix Inversion......Page 161
3.21 Orthogonal Matrices......Page 162
3.22 Two Theorems on Vector by Matrix Multiplication......Page 163
3.23 The Row-/Column-Reversal Matrix......Page 164
Matrix Addition/Subtraction......Page 165
Matrix Multiplication......Page 166
3.24 A Simple Matrix Algebra C Library......Page 167
4.1 Definition of a Scalar Field......Page 168
Multiplication of a Vector by a Scalar......Page 170
4.2 Definition of a Vector Space......Page 169
4.3 Linear Combinations of Vectors......Page 171
4.5 Spans and Bases of a Vector Space......Page 172
4.6 Transformations Between Bases......Page 173
4.7 Transformations Between Orthonormal Bases......Page 176
4.8 Alternative Notation for Change of Basis Transformations......Page 177
5.2 Concatenation of Transformations......Page 179
5.4.1 Scaling Transformation Relative to the Origin......Page 181
5.4.3 Rotation Transformation about the Origin......Page 182
5.4.5 Shearing Transformation Along the y-Axis......Page 185
5.5.1 Reflection Transformations About One- or Two-Coordinate Axes......Page 186
5.5.2 Scaling Transformation About an Arbitrary Point......Page 187
5.5.3 Rotation Transformation About an Arbitrary Point......Page 188
5.5.4 Reflection Transformation About an Arbitrary Axis......Page 189
5.6 Sign of the Angles in Transformations......Page 191
5.8 Matrix Representation of 2D Transformations......Page 192
5.9 Matrix Representation of Primitive Transformations......Page 194
5.11 Concatenation of Transformation Matrices......Page 195
5.12 Local Frame and Global Frame Transformations......Page 198
5.12.1 Concatenation of Global Transformations......Page 199
5.13 Transformations of the Frame of Reference or Coordinate System......Page 200
5.14.1 Windowing Transformation......Page 201
5.14.2 Viewporting Transformation......Page 202
5.15 Homogeneous Coordinates......Page 204
5.16 A Simple C Library for 2D Transformations......Page 206
6.1 Clipping a 2D Point to a Rectangular Clipping Boundary......Page 207
6.2 Clipping a 2D Line Segment to a Rectangular Clipping Boundary......Page 208
6.3 The Cohen and Sutherland 2D Line-Clipping Algorithm......Page 211
6.4 2D Polygon Clipping......Page 216
6.4.1 The Sutherland and Hodgman Polygon-Clipping Algorithm......Page 217
Finding the Point of Intersection of Two Lines......Page 222
Finding the Perpendicular Distance from a Point to a Line......Page 223
6.4.2 The Weiler and Atherton Polygon-Clipping Algorithm......Page 233
References......Page 237
7.1 Introduction......Page 238
7.2 Primitive 3D Transformations......Page 239
7.2.2 Translation Transformation......Page 240
7.2.3.1 Rotation About the Z-Axis......Page 241
7.2.3.2 Rotation About the X-Axis......Page 242
7.2.3.3 Rotation About the Y-Axis......Page 243
7.2.4 Shearing Transformations......Page 244
7.2.4.1 Shearing the X-Axis Parallel to the Y-Axis (sx y )......Page 245
7.2.4.2 Shearing the X-Axis Parallel to the Z-Axis (sx z )......Page 246
7.2.4.3 Shearing the Y-Axis Parallel to the X-Axis (sy x )......Page 247
7.2.4.4 Shearing the Y-Axis Parallel to the Z-Axis (sy z )......Page 248
7.2.4.5 Shearing the Z-Axis Parallel to the X-Axis (sz x )......Page 249
7.2.4.6 Shearing the Z-Axis Parallel to the Y-Axis (sz y )......Page 250
7.3 Global and Local Frames of Reference......Page 251
7.4 Aiming Transformations......Page 254
7.4.1 Aiming the Local X-Axis in the Direction of an Arbitrary Unit Vector V......Page 255
7.4.2 Aiming the Local Y-Axis in the Direction of an Arbitrary Unit Vector V......Page 256
7.4.3 Aiming the Local Z-Axis in the Direction of an Arbitrary Unit Vector V......Page 257
7.5.1 Composite Transformations Relative to a Point......Page 258
7.5.2.1 Composite Transformations Relative to a Major Axis......Page 259
7.5.2.2 Composite Transformations Relative to an Axis Parallel to a Major Axis......Page 260
7.5.2.3 Composite Transformations Relative to an Arbitrary Axis......Page 261
7.5.3.1 Composite Transformations Relative to a Major Plane......Page 262
7.5.3.2 Composite Transformations Relative to an Arbitrary Plane......Page 263
7.6 Local Frame and Global Frame Transformations......Page 264
References......Page 265
8.1 Conceptual Camera Model......Page 266
8.2 Viewing Transformation......Page 268
8.3 Projection Transformation......Page 273
8.4 Projection Transformation Matrix......Page 274
8.5.1.1 Multi-View Orthographic Projections......Page 275
8.5.1.2.1 Isometric Projections......Page 277
8.5.1.2.3 Trimetric Projections......Page 279
8.5.2 Oblique Projections......Page 280
8.5.2.1 Oblique Projection Matrix......Page 283
8.6 Perspective Projections......Page 284
8.6.1 Perspective Projection Matrix......Page 286
8.7 Screen or Device Coordinate System......Page 288
8.8 3D Line Clipping......Page 290
8.9 Perspective Depth......Page 300
8.10 Simple C Library for 3D Transformations......Page 302
9.1 Introduction......Page 303
9.2 Rendering Algorithms......Page 306
9.2.1 A Simple Rendering Algorithm......Page 307
9.2.2 Warnock (Screen Subdivision) Algorithm......Page 308
9.2.3 Newell, Newell and Sancha Algorithm......Page 311
9.2.4 Single Scan-Line Depth-Buffer Algorithm......Page 314
9.3 Reflection Models and Shading Techniques......Page 317
9.3.2 Diffuse Light Reflection......Page 318
9.3.3 Specular Light Reflection......Page 320
9.3.3.1 Horn’s Method for Computing the Specular Reflection Function......Page 321
9.3.3.2 Blinn’s Method for Computing the Specular Reflection Function......Page 322
9.3.4.2 Simulating Distant Light Sources......Page 323
9.3.4.3 Coloured Light Sources......Page 324
9.4.2 Gouraud Smooth Shading Technique......Page 325
9.4.3 Phong Smooth Shading Technique......Page 327
References......Page 328
10.1 Evolution of the Theory of Light......Page 329
10.2 Nature of Light......Page 332
10.3 Interaction of Light with Various Materials......Page 336
10.3.1 Light Reflection......Page 337
10.3.2 Light Refraction and Transmission......Page 338
10.3.3 Total Internal Reflection......Page 340
10.3.4 Light Scattering and Absorption......Page 341
10.3.5 Subsurface Scattering......Page 342
10.4 Some Useful Concepts, Definitions and Conventions......Page 343
10.4.1 Spherical Coordinates of a Vector......Page 345
10.4.3 Determining the Transmission Vector......Page 347
10.4.4 Illuminating Hemisphere and Solid Angles......Page 349
10.5 Some Basic Terminology of Lighting......Page 353
10.6 Light Emission......Page 359
10.7 The Scattering and Reflection Functions......Page 361
10.7.1 Bi-directional Scattering Surface Reflectance Distribution Function (BSSRDF)......Page 362
10.7.2 Bi-directional Reflectance Distribution Function (BRDF)......Page 363
10.7.3 Reflectance, Transmittance and Scattering Equations......Page 366
10.7.4.2 Symmetry Property or the Helmholtz Reciprocity Property......Page 367
10.8 Reflectance Function of a Surface......Page 368
10.9 Transmittance Function of a Surface......Page 370
10.10 Reflection and Transmission Models......Page 371
10.10.1 Diffuse Reflection Model......Page 372
10.10.2 Specular Reflection Model......Page 373
10.10.3 Fresnel Effect......Page 375
10.10.4 Glossy or Semi-coherent Reflections......Page 384
10.11 Some Classical and Physically Plausible Shading Models......Page 386
10.11.1 Phong Shader......Page 387
10.11.2 Modified Phong Shader......Page 389
10.11.3 The Cook-Torrance Shader......Page 390
10.11.4 The Ashikmin-Shirley Shader......Page 394
10.12 Illumination Models and the Rendering Equation......Page 397
10.12.1 Local or Direct Illumination Model......Page 398
10.12.2 Global or Indirect Illumination Model......Page 399
10.13 Monte Carlo Method and Monte Carlo Integration......Page 403
10.14 Physically-Based Rendering Algorithms......Page 405
10.14.1.1 The Radiosity Algorithm......Page 406
10.14.2 Image-Space Rendering Algorithms......Page 407
10.14.2.1 The Recursive Ray-Tracing Algorithm......Page 408
10.14.2.2 The Distributed Ray-Tracing Algorithm......Page 410
10.14.2.3 The Path-Tracing Algorithm......Page 412
10.14.2.4 The Bi-directional Path-Tracing Algorithm......Page 415
10.14.2.5 The Metropolis Light Transport Algorithm......Page 421
10.14.2.6 The Photon-Mapping Technique......Page 422
10.14.2.6.2 Emission of Photons......Page 423
10.14.2.6.4 Storage of Photons......Page 424
10.14.2.6.5 Photon Density Estimation......Page 425
10.14.2.6.6 The Rendering Pass......Page 426
10.14.2.6.7 Observations......Page 429
References......Page 430
Appendix 1......Page 434
Appendix 2......Page 448
Appendix 3......Page 460
Appendix 4......Page 477
Index......Page 540