CS-184: Computer GraphicsLecture #4: 2D Transformations Prof. James O’BrienUniversity of California, BerkeleyV2009-F-04-1.02Today•2D Transformations•“Primitive” Operations•Scale, Rotate, Shear, Flip, Translate•Homogenous Coordinates•SVD•Start thinking about rotations...Monday, September 5, 113Introduction•Transformation: An operation that changes one configuration into another•For images, shapes, etc.A geometric transformation maps positions that define the object to other positionsLinear transformation means the transformation is defined by a linear function... which is what matrices are good for.4Some ExamplesOriginalMonday, September 5, 115Some ExamplesImages from Conan The Destroyer, 1984OriginalUniform ScaleRotationNonuniform ScaleShear6Mapping Functionf(p)=p0p =(x, y)p0=(x0, y0)Maps points in original image to point in transformed image OriginalTransformedMonday, September 5, 116Mapping Functionf(p)=p0p =(x, y)p0=(x0, y0)Maps points in original image to point in transformed image OriginalTransformedf6Mapping Functionf(p)=p0p =(x, y)p0=(x0, y0)Maps points in original image to point in transformed image OriginalTransformedff1Monday, September 5, 117Mapping Functionf(p)=p0p =(x, y)p0=(x0, y0)Maps points in original image to point in transformed image OriginalTransformedf1= c(f1(p0)) = c(p)c(p)=[195, 120, 58]c0(p0)8Linear -vs- NonlinearLinear (shear)Nonlinear (swirl)Monday, September 5, 119Geometric -vs- Color SpaceLinear Geometric(flip)Color Space Transform(edge finding)10InstancingRHWM.C. Escher, from Ghostscript 8.0 DistributionMonday, September 5, 1111InstancingCarlo Sequin12InstancingRHW•Reuse geometric descriptions•Saves memoryMonday, September 5, 1113Linear is Linear•Polygons defined by points•Edges defined by interpolation between two points•Interior defined by interpolation between all points•Linear interpolation14Linear is Linear•Composing two linear function is still linear•Transform polygon by transforming verticesScaleMonday, September 5, 1115Linear is Linear•Composing two linear function is still linear•Transform polygon by transforming verticesf (x)=a + bxg( f )=c + dfg(x)=c + df(x)=c + ad + bdxg(x)=a0+ b0x16Points in Space•Represent point in space by vector in •Relative to some origin!•Relative to some coordinate axes!•Later we’ll add something extra...RnOrigin, 024T]4,2[=pp =[4, 2]TMonday, September 5, 1117Basic Transformations•Basic transforms are: rotate, scale, and translate•Shear is a composite transformation!RotateTranslateScaleShear -- not really “basic”Uniform/isotropicNon-uniform/anisotropic18Linear Functions in 2Dx0= f (x, y)=c1+ c2x + c3yy0= f (x, y)=d1+ d2x + d3yx0y0=txty+MxxMxyMyxMyy·xyx0= t + M · xMonday, September 5, 1119RotationsRotatepp⎥⎦⎤⎢⎣⎡−=)Cos()()()Cos('θθθθSinSinx.707 -.707.707 .707yx45 degree rotation20Rotations•Rotations are positive counter-clockwise•Consistent w/ right-hand rule•Don’t be different...•Note: •rotate by zero degrees give identity•rotations are modulo 360 (or )2πMonday, September 5, 1121Rotations•Preserve lengths and distance to origin•Rotation matrices are orthonormal• •In 2D rotations commute... •But in 3D they won’t!Det(R)=1 6= 122Scales0.5 0 0 1.5xyxyx0.5 0 0 0.5yxyScaleUniform/isotropicNon-uniform/anisotropicpp⎥⎦⎤⎢⎣⎡=yxss00'Monday, September 5, 1123Scales•Diagonal matrices•Diagonal parts are scale in X and scale in Y directions•Negative values flip•Two negatives make a positive (180 deg. rotation)•Really, axis-aligned scalesNot axis-aligned...24ShearsShearpp⎥⎦⎤⎢⎣⎡=11'xyyxHHx 1 1 0 1yxyMonday, September 5, 1125Shears•Shears are not really primitive transforms•Related to non-axis-aligned scales•More shortly.....26Translation•This is the not-so-useful way:Translate⎥⎦⎤⎢⎣⎡+=yxttpp 'Note that its not like the others.Monday, September 5, 1127Arbitrary Matrices•For everything but translations we have:•Soon, translations will be assimilated as well•What does an arbitrary matrix mean?x0= A · x28Singular Value Decomposition•For any matrix, A , we can write SVD: where Q and R are orthonormal and S is diagonal•Can also write Polar Decomposition where is also orthonormalTQSRA =A = PRSRTP = QRTPMonday, September 5, 1129Decomposing Matrices•We can force P and R to have Det=1 so they are rotations•Any matrix is now:•Rotation:Rotation:Scale:Rotation•See, shear is just a mix of rotations and scales30Composition•Matrix multiplication composites matrices•Several translations composted to one•Translations still left out...BApp ='“Apply A to p and then apply B to that result.”CppBAApBp === )()('uCpBtBAptApBp +=+=+= )('Monday, September 5, 1130Composition•Matrix multiplication composites matrices•Several translations composted to one•Translations still left out...BApp ='“Apply A to p and then apply B to that result.”CppBAApBp === )()('uCpBtBAptApBp +=+=+= )('31CompositionshearxyxyyxxshearshearTransformations built up from othersSVD builds from scale and rotationsAlso build other waysi.e. 45 deg rotation built from shearsMonday, September 5, 1132•Move to one higher dimensional space•Append a 1 at the end of the vectors•For directions the extra coordinate is a zeroHomogeneous Coordiantes⎥⎦⎤⎢⎣⎡=yxppp⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1~yxppp33Homogeneous Translation⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=11001001'~yxyxppttppAp~~'~=The tildes are for clarity to distinguish homogenized from non-homogenized vectors.Monday, September 5, 1134Homogeneous Others⎥⎥⎦⎤⎢⎢⎣⎡=10000~AANow everything looks the same...Hence the term “homogenized!”35Compositing Matrices•Rotations and scales always about the origin•How to rotate/scale about another point?-vs-Monday, September 5, 1136Rotate About Arb. Point•Step 1: Translate point to originTranslate (-C) 37Rotate About Arb. Point•Step 1: Translate point to origin•Step 2: Rotate as desiredTranslate (-C) Rotate (θ) Monday, September 5, 1138•Step 1: Translate point to origin•Step 2: Rotate as desired•Step 3: Put back where it wasRotate About Arb. PointTranslate (-C) Rotate (θ)
View Full Document