Computer Graphics Lecture Notes

lecture notes on computer graphics and multimedia, computer graphics and visualization lecture notes, computer graphics and image processing lecture notes pdf free download
Dr.GordenMorse Profile Pic
Dr.GordenMorse,France,Professional
Published Date:22-07-2017
Your Website URL(Optional)
Comment
Computer Graphics Lecture Notes CSC418 / CSCD18 / CSC2504 Computer Science Department University of Toronto Version: November 24, 2006 Copyright c 2005 David Fleet and Aaron HertzmannCSC418 / CSCD18 / CSC2504 CONTENTS Contents Conventions and Notation v 1 Introduction to Graphics 1 1.1 Raster Displays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Basic Line Drawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Curves 4 2.1 Parametric Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Tangents and Normals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Ellipses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Rendering Curves in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Transformations 10 3.1 2D Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Affine Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Homogeneous Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Uses and Abuses of Homogeneous Coordinates . . . . . . . . . . . . . . . . . . . 14 3.5 Hierarchical Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.6 Transformations in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Coordinate Free Geometry 18 5 3D Objects 21 5.1 Surface Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.3 Surface Tangents and Normals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3.1 Curves on Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3.2 Parametric Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3.3 Implicit Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.4 Parametric Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.4.1 Bilinear Patch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.4.2 Cylinder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.4.3 Surface of Revolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.4.4 Quadric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.4.5 Polygonal Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.5 3D Affine Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.6 Spherical Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.6.1 Rotation of a Point About a Line . . . . . . . . . . . . . . . . . . . . . . . 29 5.7 Nonlinear Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Copyright c 2005 David Fleet and Aaron Hertzmann iCSC418 / CSCD18 / CSC2504 CONTENTS 5.8 Representing Triangle Meshes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.9 Generating Triangle Meshes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Camera Models 32 6.1 Thin Lens Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.2 Pinhole Camera Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.3 Camera Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.4 Orthographic Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.5 Camera Position and Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.6 Perspective Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.7 Homogeneous Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.8 Pseudodepth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.9 Projecting a Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.10 Camera Projections in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7 Visibility 45 7.1 The View Volume and Clipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 7.2 Backface Removal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7.3 The Depth Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7.4 Painter’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.5 BSP Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.6 Visibility in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8 Basic Lighting and Reflection 51 8.1 Simple Reflection Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8.1.1 Diffuse Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8.1.2 Perfect Specular Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . 52 8.1.3 General Specular Reflection . . . . . . . . . . . . . . . . . . . . . . . . . 52 8.1.4 Ambient Illumination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8.1.5 Phong Reflectance Model . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8.2 Lighting in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 9 Shading 57 9.1 Flat Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 9.2 Interpolative Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 9.3 Shading in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 10 Texture Mapping 59 10.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 10.2 Texture Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 10.2.1 Texture Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 10.2.2 Digital Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Copyright c 2005 David Fleet and Aaron Hertzmann iiCSC418 / CSCD18 / CSC2504 CONTENTS 10.3 Mapping from Surfaces into Texture Space . . . . . . . . . . . . . . . . . . . . . 60 10.4 Textures and Phong Reflectance . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 10.5 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 10.6 Texturing in OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 11 Basic Ray Tracing 64 11.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 11.2 Ray Casting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 11.3 Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 11.3.1 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 11.3.2 General Planar Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 11.3.3 Spheres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 11.3.4 Affinely Deformed Objects . . . . . . . . . . . . . . . . . . . . . . . . . . 67 11.3.5 Cylinders and Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 11.4 The Scene Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 11.5 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 11.6 Surface Normals at Intersection Points . . . . . . . . . . . . . . . . . . . . . . . . 70 11.6.1 Affinely-deformed surfaces. . . . . . . . . . . . . . . . . . . . . . . . . . 70 11.7 Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 11.7.1 Basic (Whitted) Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . 71 11.7.2 Texture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 11.7.3 Transmission/Refraction . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 11.7.4 Shadows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 12 Radiometry and Reflection 76 12.1 Geometry of lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 12.2 Elements of Radiometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 12.2.1 Basic Radiometric Quantities . . . . . . . . . . . . . . . . . . . . . . . . 81 12.2.2 Radiance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 12.3 Bidirectional Reflectance Distribution Function . . . . . . . . . . . . . . . . . . . 85 12.4 Computing Surface Radiance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 12.5 Idealized Lighting and Reflectance Models . . . . . . . . . . . . . . . . . . . . . 88 12.5.1 Diffuse Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 12.5.2 Ambient Illumination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 12.5.3 Specular Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 12.5.4 Phong Reflectance Model . . . . . . . . . . . . . . . . . . . . . . . . . . 91 13 Distribution Ray Tracing 92 13.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 13.2 Numerical integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 13.3 Simple Monte Carlo integration . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Copyright c 2005 David Fleet and Aaron Hertzmann iiiCSC418 / CSCD18 / CSC2504 CONTENTS 13.4 Integration at a pixel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 13.5 Shading integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 13.6 Stratified Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 13.7 Non-uniformly spaced points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 13.8 Importance sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 13.9 Distribution Ray Tracer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 14 Interpolation 99 14.1 Interpolation Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 14.2 Catmull-Rom Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 15 Parametric Curves And Surfaces 104 15.1 Parametric Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 15.2 Be ´zier curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 15.3 Control Point Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 15.4 Be ´zier Curve Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 15.5 Rendering Parametric Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 ´ 15.6 Bezier Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 16 Animation 110 16.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 16.2 Keyframing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 16.3 Kinematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 16.3.1 Forward Kinematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 16.3.2 Inverse Kinematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 16.4 Motion Capture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 16.5 Physically-Based Animation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 16.5.1 Single 1D Spring-Mass System . . . . . . . . . . . . . . . . . . . . . . . 116 16.5.2 3D Spring-Mass Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 16.5.3 Simulation and Discretization . . . . . . . . . . . . . . . . . . . . . . . . 117 16.5.4 Particle Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 16.6 Behavioral Animation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 16.7 Data-Driven Animation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Copyright c 2005 David Fleet and Aaron Hertzmann ivCSC418 / 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. That is, (x,y) = . Row vectors are denoted with square braces and no commas: y   T   x T x y = (x,y) = . y 2 The set of real numbers is represented byR. The real Euclidean plane isR , and similarly Eu- 3 clidean three-dimensional space isR . The set of natural numbers (non-negative integers) is rep- resented byN. There are some notable differences between the conventions used in these notes and those found in the course text. Here, coordinates of a pointp¯ are written asp , p , and so on, where the book x y uses the notationx ,y , etc. The same is true for vectors. p p 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. Alex Kolliopoulos assisted with electronic preparation of the notes, with additional help from Patrick Coleman. Copyright c 2005 David Fleet and Aaron Hertzmann vCSC418 / CSCD18 / CSC2504 Introduction to Graphics 1 Introduction to Graphics 1.1 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. N One of 2 intensities or colors are associated with each pixel, where N is the number of bits per 8 pixel. Greyscale typically has one byte per pixel, for 2 = 256 intensities. 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 1CSC418 / CSCD18 / CSC2504 Introduction to Graphics Scan conversion of a circle 1.2 Basic Line Drawing Set the color of pixels to approximate the appearance of a line from(x ,y ) to(x ,y ). 0 0 1 1 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 isy =mx+b. Note: Given two points(x ,y ) and(x ,y ) that lie on a line, we can solve form andb for 0 0 1 1 the line. Considery =mx +b andy =mx +b. 0 0 1 1 y −y 1 0 Subtracty fromy to solve form = andb =y −mx . 0 1 0 0 x −x 1 0 Substituting in the value forb, this equation can be written asy =m(x−x )+y . 0 0 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 2CSC418 / CSCD18 / CSC2504 Introduction to Graphics Problems with this algorithm: • Ifx x nothing is drawn. 1 0 Solution: Switch the order of the points ifx x . 1 0 • Consider the cases whenm 1 andm 1: (a) m 1 (b) m 1 A different number of pixels are on, which implies different brightness between the two. 1 Solution: Whenm 1, loop overy =y ...y instead ofx, thenx = (y−y )+x . 0 1 0 0 m • Inefficient because of the number of operations and the use of floating point numbers. Solution: A more advanced algorithm, called Bresenham’s Line Drawing Algorithm. Copyright c 2005 David Fleet and Aaron Hertzmann 3CSC418 / CSCD18 / CSC2504 Curves 2 Curves 2.1 Parametric Curves There are multiple ways to represent curves in two dimensions: • Explicit: y =f(x), givenx, findy. Example: The explicit form of a line is y = mx + b. There is a problem with this representation–what about vertical lines? • Implicit: f(x,y) = 0, or in vector form,f(p¯) = 0. Example: The implicit equation of a line throughp¯ andp¯ is 0 1 (x−x )(y −y )−(y−y )(x −x ) = 0. 0 1 0 0 1 0 Intuition: – The direction of the line is the vectord =p¯ −p¯ . 1 0 – So a vector fromp¯ to any point on the line must be parallel tod. 0 – Equivalently, any point on the line must have direction from p¯ perpendic- 0 ⊥ ular tod = (d ,−d )≡n. y x ⊥ This can be checked withd·d = (d ,d )·(d ,−d ) = 0. x y y x – So for any pointp¯ on the line,(p¯−p¯ )·n = 0. 0 Heren = (y −y ,x −x ). This is called a normal. 1 0 0 1 – Finally,(p¯−p¯ )·n = (x−x ,y−y )·(y −y ,x −x ) = 0. Hence, the 0 0 0 1 0 0 1 line can also be written as: (p¯−p¯ )·n = 0 0 Example: The implicit equation for a circle of radiusr and centerp¯ = (x ,y ) is c c c 2 2 2 (x−x ) +(y−y ) =r , c c or in vector form, 2 2 kp¯−p¯k =r . c Copyright c 2005 David Fleet and Aaron Hertzmann 4CSC418 / CSCD18 / CSC2504 Curves 2 ¯ ¯ • Parametric: p¯=f(λ) wheref :R→R , may be written asp¯(λ) or(x(λ),y(λ)). Example: A parametric line throughp¯ andp¯ is 0 1 p¯(λ) =p¯ +λd, 0 whered =p¯ −p¯ . 1 0 Note that bounds onλ must be specified: – Line segment fromp¯ top¯ : 0≤λ≤ 1. 0 1 – Ray fromp¯ in the direction ofp¯ : 0≤λ∞. 0 1 – Line passing throughp¯ andp¯ :−∞λ∞ 0 1 Example: What’s the perpendicular bisector of the line segment betweenp¯ andp¯ ? 0 1 1 1 p¯ +p¯ 0 1 – The midpoint isp¯(λ) whereλ = , that is,p¯ + d = . 0 2 2 2 – The line perpendicular top¯(λ) has direction parallel to the normal ofp¯(λ), which isn = (y −y ,−(x −x )). 1 0 1 0   1 Hence, the perpendicular bisector is the lineℓ(α) = p¯ + d +αn. 0 2 Example: ¯ Find the intersection of the linesl(λ) =p¯ +λd andf(p¯) = (p¯−p¯ )·n = 0. 0 0 1 1 ¯ Substitute l(λ) into the implicit equation f(p¯) to see what value of λ satisfies it:    ¯ f l(λ) = p¯ +λd −p¯ ·n 0 0 1 1 = λd ·n −(p¯ −p¯ )·n 0 1 1 0 1 = 0 Therefore, ifd ·n 6= 0, 0 1 (p¯ −p¯ )·n 1 0 1 ∗ λ = , d ·n 0 1 ∗ ¯ and the intersection point isl(λ ). Ifd ·n = 0, then the two lines are parallel 0 1 with no intersection or they are the same line. Copyright c 2005 David Fleet and Aaron Hertzmann 5CSC418 / CSCD18 / CSC2504 Curves Example: The parametric form of a circle with radiusr for0≤λ 1 is p¯(λ) = (rcos(2πλ),rsin(2πλ)). This is the polar coordinate representation of a circle. There are an infinite number of parametric representations of most curves, such as circles. Can you think of others? An important property of parametric curves is that it is easy to generate points along a curve by evaluatingp¯(λ) at a sequence ofλ values. 2.1.1 Tangents and Normals The tangent to a curve at a point is the instantaneous direction of the curve. The line containing the tangent intersects the curve at a point. It is given by the derivative of the parametric formp¯(λ) with regard toλ. That is,   dp¯(λ) dx(λ) dy(λ) τ(λ) = = , . dλ dλ dλ The normal is perpendicular to the tangent direction. Often we normalize the normal to have unit length. For closed curves we often talk about an inward-facing and an outward-facing normal. When the type is unspecified, we are usually dealing with an outward-facing normal. τ(λ) n(λ) tangent normal p(λ) curve We can also derive the normal from the implicit form. The normal at a pointp¯= (x,y) on a curve defined byf(p¯) =f(x,y) = 0 is:   ∂f(x,y) ∂f(x,y) n(p¯) =∇f(p¯) = , p¯ ∂x ∂y Derivation: For any curve in implicit form, there also exists a parametric representation p¯(λ) = Copyright c 2005 David Fleet and Aaron Hertzmann 6CSC418 / CSCD18 / CSC2504 Curves (x(λ),y(λ)). All points on the curve must satisfy f(p¯) = 0. Therefore, for any choice ofλ, we have: 0 =f(x(λ),y(λ)) We can differentiate both side with respect toλ: d 0 = f(x(λ),y(λ)) (1) dλ ∂f dx(λ) ∂f dy(λ) 0 = + (2) ∂x dλ ∂y dλ     ∂f ∂f dx(λ) dy(λ) 0 = , · , (3) ∂x ∂y dλ dλ 0 = ∇f(p¯) ·τ(λ) (4) p¯ This last line states that the gradient is perpendicular to the curve tangent, which is the definition of the normal vector. Example: 2 2 2 The implicit form of a circle at the origin is: f(x,y) =x +y −R = 0. The normal at a point(x,y) on the circle is:∇f = (2x,2y). Exercise: show that the normal computed for a line is the same, regardless of whether it is com- puted using the parametric or implicit forms. Try it for another surface. 2.2 Ellipses 2 2 x y • Implicit: + = 1. This is only for the special case where the ellipse is centered at the 2 2 a b origin with the major and minor axes aligned withy = 0 andx = 0. b a • Parametric: x(λ) =acos(2πλ), y(λ) =bsin(2πλ), or in vector form   acos(2πλ) p¯(λ) = . bsin(2πλ) Copyright c 2005 David Fleet and Aaron Hertzmann 7CSC418 / CSCD18 / CSC2504 Curves The implicit form of ellipses and circles is common because there is no explicit functional form. This is becausey is a multifunction ofx. 2.3 Polygons A polygon is a continuous, piecewise linear, closed planar curve. • A simple polygon is non self-intersecting. • A regular polygon is simple, equilateral, and equiangular. • An n-gon is a regular polygon withn sides. • A polygon is convex if, for any two points selected inside the polygon, the line segment between them is completely contained within the polygon. Example: To find the vertices of ann-gon, findn equally spaced points on a circle. r θ 2π In polar coordinates, each vertex (x ,y ) = (rcos(θ ),rsin(θ )), whereθ = i for i i i i i n i = 0...n−1. • To translate: Add(x ,y ) to each point. c c • To scale: Changer. • To rotate: AddΔθ to eachθ . i 2.4 Rendering Curves in OpenGL OpenGL does not directly support rendering any curves other that lines and polylines. However, you can sample a curve and draw it as a line strip, e.g.,: float x, y; glBegin(GL_LINE_STRIP); for (int t=0 ; t = 1 ; t += .01) Copyright c 2005 David Fleet and Aaron Hertzmann 8CSC418 / CSCD18 / CSC2504 Curves computeCurve( t, &x, &y); glVertex2f(x, y); glEnd(); You can adjust the step-size to determine how many line segments to draw. Adding line segments will increase the accuracy of the curve, but slow down the rendering. The GLU does have some specialized libraries to assist with generating and rendering curves. For example, the following code renders a disk with a hole in its center, centered about thez-axis. GLUquadric q = gluNewQuadric(); gluDisk(q, innerRadius, outerRadius, sliceCount, 1); gluDeleteQuadric(q); See the OpenGL Reference Manual for more information on these routines. Copyright c 2005 David Fleet and Aaron Hertzmann 9CSC418 / CSCD18 / CSC2504 Transformations 3 Transformations 3.1 2D Transformations Given a point cloud, polygon, or sampled parametric curve, we can use transformations for several purposes: 1. Change coordinate frames (world, window, viewport, device, etc). 2. Compose objects of simple parts with local scale/position/orientation of one part defined with regard to other parts. For example, for articulated objects. 3. Use deformation to create new shapes. 4. Useful for animation. There are three basic classes of transformations: 1. Rigid body - Preserves distance and angles. • Examples: translation and rotation. 2. Conformal - Preserves angles. • Examples: translation, rotation, and uniform scaling. 3. Affine - Preserves parallelism. Lines remain lines. • Examples: translation, rotation, scaling, shear, and reflection. Examples of transformations: • Translation by vectort: p¯ =p¯ +t. 1 0   cos(θ) −sin(θ) • Rotation counterclockwise byθ: p¯ = p¯ . 1 0 sin(θ) cos(θ) Copyright c 2005 David Fleet and Aaron Hertzmann 10CSC418 / CSCD18 / CSC2504 Transformations   a 0 • Uniform scaling by scalara: p¯ = p¯ . 1 0 0 a   a 0 • Nonuniform scaling bya andb: p¯ = p¯ . 1 0 0 b   1 h • Shear by scalarh: p¯ = p¯ . 1 0 0 1   −1 0 • Reflection about they-axis: p¯ = p¯ . 1 0 0 1 3.2 Affine Transformations An affine transformation takes a pointp¯ toq¯ according toq¯= F(p¯) = Ap¯+t, a linear transfor- mation followed by a translation. You should understand the following proofs. Copyright c 2005 David Fleet and Aaron Hertzmann 11CSC418 / CSCD18 / CSC2504 Transformations • The inverse of an affine transformation is also affine, assuming it exists. Proof: −1 Letq¯=Ap¯+t and assumeA exists, i.e. det(A) =6 0. −1 −1 ThenAp¯= q¯−t, sop¯= A q¯−A t. This can be rewritten asp¯= Bq¯+d, −1 −1 whereB =A andd =−A t. Note: The inverse of a 2D linear transformation is     −1 1 a b d −b −1 A = = . c d −c a ad−bc • Lines and parallelism are preserved under affine transformations. Proof: ¯ To prove lines are preserved, we must show thatq¯(λ) =F(l(λ)) is a line, where ¯ F(p¯) =Ap¯+t andl(λ) =p¯ +λd. 0 ¯ q¯(λ) = Al(λ)+t = A(p¯ +λd)+t 0 = (Ap¯ +t)+λAd 0 This is a parametric form of a line throughAp¯ +t with directionAd. 0 • Given a closed region, the area under an affine transformationAp¯+t is scaled bydet(A). Note: – Rotations and translations havedet(A) = 1.   a 0 – ScalingA = hasdet(A) =ab. 0 b – Singularities havedet(A) = 0. Example:   1 0 The matrixA = maps all points to thex-axis, so the area of any closed 0 0 region will become zero. We have det(A) = 0, which verifies that any closed region’s area will be scaled by zero. Copyright c 2005 David Fleet and Aaron Hertzmann 12CSC418 / CSCD18 / CSC2504 Transformations • A composition of affine transformations is still affine. Proof: LetF (p¯) =A p¯+t andF (p¯) =A p¯+t . 1 1 1 2 2 2 Then, F(p¯) = F (F (p¯)) 2 1 = A (A p¯+t )+t 2 1 1 2 = A A p¯+(A t +t ). 2 1 2 1 2 Letting A = A A and t = A t +t , we have F(p¯) = Ap¯+t, and this is an 2 1 2 1 2 affine transformation. 3.3 Homogeneous Coordinates Homogeneous coordinates are another way to represent points to simplify the way in which we express affine transformations. Normally, bookkeeping would become tedious when affine trans- formations of the formAp¯+t are composed. With homogeneous coordinates, affine transforma- tions become matrices, and composition of transformations is as simple as matrix multiplication. In future sections of the course we exploit this in much more powerful ways.   p¯ With homogeneous coordinates, a pointp¯ is augmented with a 1, to formpˆ= . 1 All points(αp¯,α) represent the same pointp¯ for realα6= 0. Given pˆ in homogeneous coordinates, to get p¯, we divide pˆ by its last component and discard the last component. Example: The homogeneous points (2,4,2) and (1,2,1) both represent the Cartesian point (1,2). It’s the orientation ofpˆ that matters, not its length. Many transformations become linear in homogeneous coordinates, including affine transforma- tions:        q a b p t x x x = + q c d p t y y y     p x a b t x   = p y c d t y 1   = A t pˆ Copyright c 2005 David Fleet and Aaron Hertzmann 13CSC418 / CSCD18 / CSC2504 Transformations To produceqˆ rather thanq¯, we can add a row to the matrix:     a b t x A t   c d t qˆ= pˆ= pˆ. y T 0 1 0 0 1 This is linear Bookkeeping becomes simple under composition. Example: F (F (F (p¯))), where F (p¯) = A (p¯) + t becomes M M M p¯, where M = 3 2 1 i i i 3 2 1 i   A t i i . T 0 1 With homogeneous coordinates, the following properties of affine transformations become appar- ent: • Affine transformations are associative. For affine transformationsF ,F , andF , 1 2 3 (F ◦F )◦F =F ◦(F ◦F ). 3 2 1 3 2 1 • Affine transformations are not commutative. For affine transformationsF andF , 1 2 F ◦F 6=F ◦F . 2 1 1 2 3.4 Uses and Abuses of Homogeneous Coordinates Homogeneous coordinates provide a different representation for Cartesian coordinates, and cannot be treated in quite the same way. For example, consider the midpoint between two points p¯ = 1 (1,1) and p¯ = (5,5). The midpoint is (p¯ + p¯ )/2 = (3,3). We can represent these points 2 1 2 in homogeneous coordinates as pˆ = (1,1,1) and pˆ = (5,5,1). Directly applying the same 1 2 computation as above gives the same resulting point: (3,3,1). However, we can also represent ′ ′ ′ ′ these points as pˆ = (2,2,2) and pˆ = (5,5,1). We then have (pˆ + pˆ )/2 = (7/2,7/2,3/2), 1 2 1 2 which cooresponds to the Cartesian point (7/3,7/3). This is a different point, and illustrates that we cannot blindly apply geometric operations to homogeneous coordinates. The simplest solution is to always convert homogeneous coordinates to Cartesian coordinates. That said, there are several important operations that can be performed correctly in terms of homogeneous coordinates, as follows. Copyright c 2005 David Fleet and Aaron Hertzmann 14

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.