Computer Graphics Lecture Notes

1 Computer Graphics Lecture Notes CSC418 / CSCD18 / CSC2504. Computer Science Department University of Toronto Version: November 24, 2006. Copyright c 2005 David Fleet and Aaron Hertzmann CSC418 / CSCD18 / CSC2504 CONTENTS. Contents Conventions and Notation v 1 Introduction to Graphics 1. Raster Displays .. 1. Basic Line Drawing .. 2. 2 Curves 4. Parametric Curves .. 4. Tangents and Normals .. 6. Ellipses .. 7. Polygons .. 8. Rendering Curves in OpenGL .. 8. 3 Transformations 10. 2D Transformations .. 10. Affine Transformations .. 11. Homogeneous Coordinates .. 13. Uses and Abuses of Homogeneous Coordinates .. 14. Hierarchical Transformations .. 15. Transformations in OpenGL .. 16. 4 Coordinate Free Geometry 18. 5 3D Objects 21. Surface Representations.

2 21. Planes .. 21. Surface Tangents and Normals .. 22. Curves on Surfaces .. 22. Parametric Form .. 22. Implicit Form .. 23. Parametric Surfaces .. 24. Bilinear Patch .. 24. Cylinder .. 25. Surface of Revolution .. 26. Quadric .. 26. Polygonal Mesh .. 27. 3D Affine Transformations .. 27. Spherical Coordinates .. 29. Rotation of a Point About a Line .. 29. Nonlinear Transformations .. 30. Copyright c 2005 David Fleet and Aaron Hertzmann i CSC418 / CSCD18 / CSC2504 CONTENTS. Representing Triangle Meshes .. 30. Generating Triangle Meshes .. 31. 6 Camera Models 32. Thin Lens Model .. 32. Pinhole Camera Model .. 33. Camera Projections .. 34. Orthographic Projection .. 35. Camera Position and Orientation .. 36. Perspective Projection .. 38. Homogeneous Perspective.

3 40. Pseudodepth .. 40. Projecting a Triangle .. 41. Camera Projections in OpenGL .. 44. 7 Visibility 45. The View Volume and Clipping .. 45. Backface Removal .. 46. The Depth Buffer .. 47. Painter's Algorithm .. 48. BSP Trees .. 48. Visibility in OpenGL .. 49. 8 Basic Lighting and Reflection 51. Simple Reflection Models .. 51. Diffuse Reflection .. 51. Perfect Specular Reflection .. 52. General Specular Reflection .. 52. Ambient Illumination .. 53. Phong Reflectance Model .. 53. Lighting in OpenGL .. 54. 9 Shading 57. Flat Shading .. 57. Interpolative Shading .. 57. Shading in OpenGL .. 58. 10 Texture Mapping 59. Overview .. 59. Texture Sources .. 59. Texture Procedures .. 59. Digital Images .. 60. Copyright c 2005 David Fleet and Aaron Hertzmann ii CSC418 / CSCD18 / CSC2504 CONTENTS.

4 Mapping from Surfaces into Texture Space .. 60. Textures and Phong Reflectance .. 61. Aliasing .. 61. Texturing in OpenGL .. 62. 11 Basic Ray Tracing 64. Basics .. 64. Ray Casting .. 65. Intersections .. 65. Triangles .. 66. General Planar Polygons .. 66. Spheres .. 67. Affinely Deformed Objects .. 67. Cylinders and Cones .. 68. The Scene Signature .. 69. Efficiency .. 69. Surface Normals at Intersection Points .. 70. Affinely-deformed surfaces.. 70. Shading .. 71. Basic (Whitted) Ray Tracing .. 71. Texture .. 72. Transmission/Refraction .. 72. Shadows .. 73. 12 Radiometry and Reflection 76. Geometry of lighting .. 76. Elements of Radiometry .. 81. Basic Radiometric Quantities .. 81. Radiance .. 83. Bidirectional Reflectance Distribution Function.

5 85. Computing Surface Radiance .. 86. Idealized Lighting and Reflectance Models .. 88. Diffuse Reflection .. 88. Ambient Illumination .. 89. Specular Reflection .. 90. Phong Reflectance Model .. 91. 13 Distribution Ray Tracing 92. Problem statement .. 92. Numerical integration .. 93. Simple Monte Carlo integration .. 94. Copyright c 2005 David Fleet and Aaron Hertzmann iii CSC418 / CSCD18 / CSC2504 CONTENTS. Integration at a pixel .. 95. Shading integration .. 95. Stratified Sampling .. 96. Non-uniformly spaced points .. 96. Importance sampling .. 96. Distribution Ray Tracer .. 98. 14 Interpolation 99. Interpolation Basics .. 99. Catmull-Rom Splines .. 101. 15 Parametric Curves And Surfaces 104. Parametric Curves .. 104. B ezier curves .. 104. Control Point Coefficients.

6 105. B ezier Curve Properties .. 106. Rendering Parametric Curves .. 108. B ezier Surfaces .. 109. 16 Animation 110. Overview .. 110. Keyframing .. 112. Kinematics .. 113. Forward Kinematics .. 113. Inverse Kinematics .. 113. Motion Capture .. 114. Physically-Based Animation .. 115. Single 1D Spring-Mass System .. 116. 3D Spring-Mass Systems .. 117. Simulation and Discretization .. 117. Particle Systems .. 118. Behavioral Animation .. 118. Data-Driven Animation .. 120. Copyright c 2005 David Fleet and Aaron Hertzmann iv CSC418 / CSCD18 / CSC2504 Acknowledgements Conventions and Notation Vectors have an arrow over their variable name: ~v . Points are denoted with a bar instead: p . Matrices are represented by an uppercase letter. When written with parentheses and commas separating elements, consider a vector to be a column x vector.

7 That is, (x, y) = . Row vectors are denoted with square braces and no commas: y T. T x x y = (x, y) = . y The set of real numbers is represented by R. The real Euclidean plane is R2 , and similarly Eu- clidean three-dimensional space is R3 . The set of natural numbers (non-negative integers) is rep- resented by N. There are some notable differences between the conventions used in these Notes and those found in the course text. Here, coordinates of a point p are written as px , py , and so on, where the book uses the notation xp , yp , etc. The same is true for vectors. Aside: Text in aside boxes provide extra background or information that you are not re- quired to know for this course. Acknowledgements Thanks to Tina Nicholl for feedback on these Notes .

8 Alex Kolliopoulos assisted with electronic preparation of the Notes , with additional help from Patrick Coleman. Copyright c 2005 David Fleet and Aaron Hertzmann v CSC418 / CSCD18 / CSC2504 Introduction to Graphics 1 Introduction to Graphics Raster Displays The screen is represented by a 2D array of locations called pixels. Zooming in on an image made up of pixels The convention in these Notes will follow that of OpenGL, placing the origin in the lower left corner, with that pixel being at location (0, 0). Be aware that placing the origin in the upper left is another common convention. One of 2N intensities or colors are associated with each pixel, where N is the number of bits per pixel. Greyscale typically has one byte per pixel, for 28 = 256 intensities.

9 Color often requires one byte per channel, with three color channels per pixel: red, green, and blue. Color data is stored in a frame buffer. This is sometimes called an image map or bitmap. Primitive operations: setpixel(x, y, color). Sets the pixel at position (x, y) to the given color. getpixel(x, y). Gets the color at the pixel at position (x, y). Scan conversion is the process of converting basic, low level objects into their corresponding pixel map representations. This is often an approximation to the object, since the frame buffer is a discrete grid. Copyright c 2005 David Fleet and Aaron Hertzmann 1. CSC418 / CSCD18 / CSC2504 Introduction to Graphics Scan conversion of a circle Basic Line Drawing Set the color of pixels to approximate the appearance of a line from (x0 , y0 ) to (x1 , y1 ).

10 It should be straight and pass through the end points. independent of point order. uniformly bright, independent of slope. The explicit equation for a line is y = mx + b. Note: Given two points (x0 , y0 ) and (x1 , y1 ) that lie on a line, we can solve for m and b for the line. Consider y0 = mx0 + b and y1 = mx1 + b. Subtract y0 from y1 to solve for m = xy11 x y0. 0. and b = y0 mx0 . Substituting in the value for b, this equation can be written as y = m(x x0 ) + y0 . Consider this simple line drawing algorithm: int x float m, y m = (y1 - y0) / (x1 - x0). for (x = x0; x <= x1; ++x) {. y = m * (x - x0) + y0. setpixel(x, round(y), linecolor). }. Copyright c 2005 David Fleet and Aaron Hertzmann 2. CSC418 / CSCD18 / CSC2504 Introduction to Graphics Problems with this algorithm: If x1 < x0 nothing is drawn.