Department of Computer Sciences CS354 { Fall 2004Geometric Spaces and Op erationsMathematical underpinnings of computer graphicsHierarchy of geometric spaces{Vector spaces{AÆne spaces{Euclidean spaces{Cartesian spaces{Projective spacesAÆne geometry and transformationsProjective transformations and p ersp ectiveMatrix formulations of transformationsViewing transformationsQuaternions and surface orientationFormally, a space is dened byThe University of Texas at Austin1Department of Computer Sciences CS354 { Fall 2004A set of objectsOp erations on the objectsAxioms dening invariant prop ertiesThe University of Texas at Austin2Department of Computer Sciences CS354 { Fall 2004Vector SpacesDenition:Set ofvectorsVOp erations on~u; ~v2 V:{Addition:~u+~v2 V{Scalar Multiplication:~u2 Vwhere2some eldFAxioms{Unique zero element:0 +~u=~u{Field unit element:1~u=~u{Addition commutative:~u+~v=~v+~u{Addition asso ciative:(~u+~v) +~w=~u+ (~v+~w){Distributive scalar multiplication:(~u+~v) =~u+~vAdditional denitions{LetB=f~v1;~v2;;~vng.{ThenBspansVi any~v2 Vcan be written as~v=Pni=1i~vi.{Pni=1i~viis called alinear combinationof the vectors inB.{Bis called abasisofVif it is a minimal spanning set.{All bases ofVcontain the same numb er of vectors.The University of Texas at Austin3Department of Computer Sciences CS354 { Fall 2004{The numb er of vectors in any basis ofVis called thedimensionofV.Comments:{We are interested in 2 and 3 dimensional spaces.{No denition of distance (size) exists yet.{Angles and p oints have not b een dened.The University of Texas at Austin4Department of Computer Sciences CS354 { Fall 2004AÆne SpacesDenition:A set of vectorsVand a set ofp ointsP Vis a vector space.Point-vector sum:P+~v=QwithP; Q2 Pand~v2 VPoint subtraction: ForP; Q2 Pand~v2 V, ifP+~v=Q, thenQP~vAdditional denitions:{AframeF= (B;O)whereB=f~v1;~v2;;~vngis a basis ofVand the p ointOis called theoriginof the frame.{The dimension ofFis the same as the dimension ofV.Comments:{Still no distances or angles{Closer to what we want for graphics{The space has no distinguished originThe University of Texas at Austin5Department of Computer Sciences CS354 { Fall 2004Euclidean SpacesDenition:Ametric spaceis any space with adistance metricd(P; Q)dened on its elements.Distance metric axioms:{d(P; Q)0{d(P; Q) = 0iP=Q{d(P; Q) =d(Q; P){d(P; Q)d(P; R) +d(R; Q)(triangle inequality)Euclideandistance metric:d2(P; Q) = (PQ)(PQ)Comments:{Euclidean metric based on dot pro duct{Dot pro duct dened on vectors{Distance metric dened on p oints{Distance is a prop erty of the space, not a frameDot pro duct axioms:The University of Texas at Austin6Department of Computer Sciences CS354 { Fall 2004{(~u+~v)~w=~u~w+~v~w{(~u~v) = (~u)~v=~u(~v){~u~v=~v~uAdditional denitions:{Thenormof a vector~uis given byj~uj=p~u~u.{Angles are dened by their cosines:cos(6~u~v) =~u~vj~ujj~vj{Orthogonal vectors:~u~v= 0!~u?~vThe University of Texas at Austin7Department of Computer Sciences CS354 { Fall 2004Cartesian SpacesDenition:A frame(~i;~j;~k;O)isorthonormali{~i;~j;and~kareorthogonal, i.e.~i~j=~j~k=~k~i= 0and{~i;~j;and~karenormal, i.e.j~ij=j~jj=j~kj= 1Additional denitions:{Thestandard frameFs= (~i;~j;~k;O){Points can be distinguished from vectors using an extra co ordinate 0 for vectors:~v= (vx;vy;vz;0)means~v=vx~i+vy~j+vz~k 1 for p oints:P= (px;py;pz;1)meansP=px~i+py~j+pz~k+O This is known as ahomogeneousrepresentationComments{Co ordinates have no meaning without an asso ciated frame{There will be other ways to lo ok at the extra co ordinate{Sometimes we are sloppy and omit the extra co ordinate{Assume standard frame unless sp ecied otherwise{Points and vectors are dierent{Points and vectors have dierent op erations{Points and vectors transform dierentlyThe University of Texas at Austin8Department of Computer Sciences CS354 { Fall 2004Linear TransformationsVector spaceVLinear combinations of vectors inVare inVFor~u; ~v2 V{~u+~v2 V{~u2 Vfor any scalar{In general,Pii~ui2 Vfor any scalarsiLinear transformations{LetT:V07! V1, whereV0andV1are vector spaces{ThenTislineari T(~u+~v) =T(~u) +T(~v) T(~u) =T(~u) In general,T(Pii~ui) =PiiT(~ui)The University of Texas at Austin9Department of Computer Sciences CS354 { Fall 2004AÆne TransformationsAÆne spaceA= (V;P)Recall that for~u2 VandP2 P,P+~u2 PDenep oint blending:{ForP; P1;P22 Pand scalar, ifP=P1+(P2P1)thenP(1)P1+P2{This can also be writtenP1P1+2P2where1+2= 1{Geometrically,jPP0jjPP1j=d1d2orP=d1P1+d2P2d1+d2{In general,PiiPiis ap ointiPii= 1Vectors can always be combined linearlyPii~uiGiven p oint subtraction,PiiPiis avectoriPii= 0Points can be combined linearlyPiiPii{The co eÆcients sum to 1, giving a p oint (\aÆne combination"){The co eÆcients sum to 0, giving a vector (\vector combination"){Example aÆne combination:P(t) =P0+t(P1P0) = (1t)P0+tP1The University of Texas at Austin10Department of Computer Sciences CS354 { Fall 2004{This says any p oint on the line is an aÆne combination of the line segment's endp oints.AÆne transformations{LetT:A07! A1whereA0andA1are aÆne spaces{Tis said to be anaÆne transformationi Tmaps vectors to vectors and p oints to p oints Tis a linear transformation on the vectors T(P+~u) =T(P) +T(~u){Prop erties of aÆne transformations Tpreserves aÆne combinations:T(0P0++nPn) =0T(P0) ++nT(Pn)wherePii= 0orPii= 1 Tmaps lines to lines:T((1t)P0+tP1) = (1t)T(P0) +tT(P1) Tis aÆne i it preserves ratios of distance along a line:P=d0P0+d1P1d0+d1)T(P) =d0T(P0) +d1T(P1)d0+d1The University of Texas at Austin11Department of Computer Sciences CS354 { Fall 2004 Tmaps parallel lines to parallel lines (can you prove this?){Example aÆne transformations Rigid body motions (translations, rotations) Scales, reections ShearsThe University of Texas at Austin12Department of Computer Sciences CS354 { Fall 2004Matrix Representation of TransformationsLetA0andA1be aÆne spaces.LetT:A07! A1be an aÆne transformation.LetF0= (~i0;~j0;O0)be a frame forA0.LetF1= (~i1;~j1;O1)be a frame forA1.LetP=x~i0+y~j0+O0be a p oint inA0.Theco ordinatesofPrelative toA0are(x; y