### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Computer Graphics CS 3451

GPA 3.81

### View Full Document

## 20

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 3451 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/234098/cs-3451-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Computer Graphics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

V Figure 1 Eye rays re ected from an object The re ected rays are shown as blue arrows Red arrows are the normal vectors Given the normal vectors one can compute the re ected rays using the formulas we used to do Phong shading Note that environment mapping will not produce correct results for rays which have to bounce from the object several times before escaping to the environment like one of the rays shown above Environment Mapping 1 Geometry of re ection Consider an ideally re ective object and a ray through a pixel What color should one use for that pixel The same as the color incoming to the re ection point from the direction of the re ected ray see Figure 1 Therefore if one is able to precompute and somehow store the colors incoming towards the re ective object along di erent rays rendering would be really simple In environment mapping one stores the colors arriving at a 3D object from di erent directions in one or more textures Typically one assumes that colors incoming to di erent points along parallel rays are the same This means that we need to keep a color for each incoming ray direction rather than for every possible incoming ray Below we discuss two speci c examples 2 Spherical environment map Imagine a photograph or a synthetic image erg rendered using ray tracing of a mirror sphere This image stores colors incoming along rays of all possible directions Figure 2 It is directly used as texture for spherical environment mapping Such a texture might look like the one shown in Figure 3 To simplify things let s say that the sphere is exactly inscribed into the square photograph V r M A l Figure 2 A mirror sphere Any direction is a direction of a certain re ected horizontal ray Spherical environment mapping is based on mapping colors from a photograph of a re ective ball onto a 3D object If the photograph is taken from in nite distance colors incoming from all directions are present on that photograph Of course there are two caveats here 1 the distance between the viewpoint and the sphere is nite a typical photograph is a perspective image rather than a parallel projection based image in particular some directions are not represented on the image we ll just sweep this problem under the carpet here saying that if the photograph is taken from far away the projection is close to parallel 2 the photograph will not really store colors for every ray but only at rays through pixels and the density of sampling of the space of directions will not be uniform we ll just hope that interpolation will solve this problem 01 11 00 7 I 7 170 Figure 3 An example of a texture for use with spherical environment mapping and a 3D model with this spherical environment mapping To see what texture coordinates we need to use with spherical environment mapping notice that the direction of the re ected ray assuming that the view ing direction is the same as the direction from which the image of the sphere was taken and the viewpoint is far away so that the rays from the viewpoint are almost parallel depends solely on the normal vector at the point where the ray hits the object Therefore the color at a vertex v of the object should be the same as the color we see at the point of the sphere which has the same normal vector Assuming that the sphere is centered at the origin and has unit radius and the unit normal at v has coordinates 711 my 712 we need to use the color we see at the point n1 ny ml which projects assuming that the projection direction is along the zaxis to nmn Of course the range for n35 an my is 71 1 and the range of texture coordinates is 0 1 and therefore we need to scale ms and my so that they are in 01 To do this we add one to each coordinate and then divide it by 2 To sum up the texture coordinates we need to use for a vertex v with unit normal 711 ny ml with spherical environment map are 1 n1 1 my 2 2 The scaling can be elegantly handled using the texture transformation matrix In graphics pipeline there are 4 texture coordinates which can be transformed using 4 X 4 matrices much like vertex coordinates eventually the rst two texture coordinates are used in the case of 2D textures Using texture matrices one can also apply the environment map to a rotating object the trick is to use normals as texture coordinates and use the texture matrix to rotate the texture coordinates in the same way as the vertices are rotated and to scale them to 0 1 Graphics APls usually provide various ways of generating texture coordi nates automatically based on viewpoint normals light location and other pa rameters Automatic texture generation means that the programmer does not have to specify them explicitly but they are computed in some speci c way from other vertex attributes or view or light data Automatic texture generation can handle most of the natural scenarios of using texture to model lighting or re ections in particular environment mapping 3 Cubical In cubical environment mapping one rst records colors incoming towards a point P somewhere inside or near the object from every direction We will think of this color as being painted onto the cube s surface at the point where the ray that starts at P and has cfas the direction vector intersects the cube s surface Figure 4 Cube environment map can be thought of as six images which we obtain on the faces of the cube by applying the above procedure If just one texture is desired one can cut the cube along some edges and atten it onto the plane as shown in Figure 5 color incoming from direction of V to P Figure 4 Cubical texture mapping left bottom front top back right Figure 5 Flattening the cube environment map q2 ql negative signed area 11051the Slgne39i area Figure 1 Orientation and the sign of signed area Computing areas in 2D and volumes in 3D Ability to compute or estimate areavolume is useful in a number of geom etry processing algorithms including simpli cation 1 2D case 11 Triangle Consider a triangle with vertices p0 x0 yo p1 x1 y1 and p2 x2 yg lts area is obviously the same as the area of the 3D triangle with vertices qo army00 ql x1y10 and q army20 Now the area of this triangle can be computed as half of the length of the cross product of vectors running along its edges 1 from go to ql and 27 from go to 112 Notice that these vectors live in the xyplane Therefore the rst two coordinates of the cross product are zero it has to be perpendicular to the joyplane and therefore parallel to the zaxis and its magnitude is equal to the absolute value of the zcoordinate 961 i 960 yr yo 962 i 960 32 310 following formula for the area of the triangle Apoplpg The zcoordinate is equal to det We sum up with the 1 960 yo 1 7 7 l AreaAp0p1p2 ldet x1 x0 y1 yo l ldet 1 x1 y1 2 962 i 960 32 yo 2 1 x2 y2 Notice that the sign of the determinant under the absolute value depends on the orientation of the triangle de ned by the ordering of its vertices If the triangle is oriented clockwise the area is negative otherwise it is positive Figure 1 In what follows we ll call a half of this determinant the signed area a1 a0a5 a4 Figure 2 Area of convex polygon case 1 0 inside 1 2 Convex polygon Let a0 a1 1771 be vertices ofa convex polygon in the counterclockwise order In what follows we mean 10 whenever we write a In order to compute the area of the polygon choose an arbitrary point 0 To start with assume 0 is inside the polygon Figure 2 Then every triangle A0 1 1H1 for 239 0 1 n 7 1 is oriented counterclockwise and therefore and therefore its signed area is positive Hence the area of the polygon can be computed by simply summing the signed areas If the vertices were ordered clockwise all signed areas would be negative and therefore the area can be computed as the absolute value of the sum of all signed areas Interestingly this is still true even if 0 is outside the polygon as illustrated in gure 3 Thus area of the polygon is equal to 7171 1 1 0I 0y Eider 1 l 1 10 1 Mm az1y This formula works for any convex polygon if only its vertices are numbered in order either clockwise or counterclockwise 13 Any polygon convex or not It turns out that formula 1 works also if the polygon is not convex This is illustrated in Figure For a point p in the plane let be the number of blue triangles containing p and mp the number of red triangles containing p Notice that ifp is not on an edge connecting a vertex of the polygon to 0 or on an edge of the polygon two cases are possible 1 mp This happens ifp is outside the polygon a0a5 a0a5 o o mangies with negative Signed area mangies my positive Signed area Figure 3 Area of convex polygon case 2 0 outside Left setup Center triangles with negative signed area right triangles with positive signed area The red area minus the blue area is exactly equal to the area of the polygon 2 mp i 1 if p is inside the polygon Whether we have to use or 7 depends on W ether the polygon s vertices come in clockwise or counterclockwise order Sloppily speaking in formula 1 points outside of the polygon do not contribute to the area or to the sum of signed areas of triangles de ned by 0 and pairs of consecutive vertices the expression under the absolute value in Points inside are counted either as negative or as positive depending on the orien tation of the polygon Therefore the sum of signed areas of all triangles de ned by 0 and the edges of the polygon is equal to either positive or negative area of the polygon Note that this is remotely related to the zfail version of the shadow volume algorithm take a p and shoot a ray from 0 toward p Past p this ray is going to intersect some or none edges of the polygon lfp is outside the polygon the ray has to exit from the polygon the same number of times as it enters it Edges through which it enters together with 0 de ne triangles containing p oriented one way Edges through each it exits with 0 de ne trian gles containing p oriented the other way The numbers of triangles with the two different orientations have to be the same If p is inside the polygon number of triangles with oriented the rst way exceeds the number of triangles oriented the other way by 1 One can conclude that mp 7 np is zero outside the polygon and is either equal to 1 or 71 insi e 2 3D case All the formulas carry over to the 3D case Here is how aO as Figure 4 All triangles formed by 0 and two consecutive vertices of the polygon With positive signed area red and negative signed area blue Notice that the total area of red triangles minus the total area of blue triangles is equal to the negative area of the polygon itself This means that formula 1 can be used to compute the polygon s areal Linear interpolation Real functions are rarely given by an explicit formula allowing to evaluate them anywhere More frequently only salnple values of the function are given at certain points and in order to estimate the value at some place which is not a sample we need to somehow combine the available information This is the goal of interpolation By doing interpolation one can for example build a complete elevation map of a terrain when only an array of height values is given this is what happens in practice height cannot be measured everywhere no matter how you do it you end up with only nite number of measurements We used interpolation to estimate the color over a triangle when colors at vertices are given or normals depths over the triangle from normals depths at the vertices Linear interpolation from vertices of a triangle P0X0y0 v0 l x1 y1 vl P2X2y2 Figure 1 Linear interpolation from triangle s vertices notation Here is how the variant of linear interpolation we used works Let s say that we have a triangle as shown in Figure 1 It has vertices p0 armyo p1 x1 yl p2 x2 yg At each vertex we have a value let s say that they are v0 21 an v2 There is exactly one linear function which takes the value of 20 at p0 21 at p1 and 12 at p2 We can prove that by embedding our triangle and the values at vertices in 3D say that the triangle lies in the groung plane lift p0 to height v0 p1 to height v1 and p2 to height 12 This yields 3 points in 3space Now nd the plane passing through the three points This plane is the graph of the linear function we are looking for Here is how to compute it algebraically We seek a function of the form fxy Ax By C ABC to be determined The requirement that the values at the vertices are v0 v1 and 1 leads to three linear equations AI0By0C10 AI1By1C11 Ax2By2Cv2 Uniform B Spline Curves Uniform BSpline curves are piecewise polynomial curves associated with a sequance of control points of any length Unlike the Bezier curves their degree is independent of the number of control points P4 P2 o v quot I quot 39 39 5 Lj P10 2 0 P3 1 F1 0P5 0 P0 6 i I P6 Figure 1 The curve BO BSpline curves can be constructed by recursive averaging Start from a curve which stays one second at the rst control point P0 then jumps to the second one P1 then after one second to the third etc Figure 1 This is going to be our zerodegree Bspline curve we ll generously call it a curve even though it doesn t really look like a curve The formula for that curve call it BO is Bot P for t E 2239 1 P2 P6 Figure 2 BO black and Bl blue Now we will start making the curve more regular by averaging ltering it We de ne a new curve degree one Bspline Bl by setting Blt to the average position of a point moving along the curve BO over time interval t t 1 Thus t1 31 Bowen t Now it s not hard to see that Bl is a polygonal curve joining the control points Figure 2 It s not di erentiable but it is de nitely nicerlooking than BO The averaging procedure can be applied to Bl to lead to B2 degreetwo Bspline and so on Thus we have a recursive formula n1 Bl1t t Bz 3513 1 Smoothness By smoothness we mean the number of derivatives that can be computed for a curve The more derivatives the smoother the curve We ll say that a curve B is ClC if the derivarives B t B t i Bkt exist for all t in the parameter range iiei everywhere where B is de ned and they are all continuous We ll say a curve is C0 if it s continuous We can now say that BO the zerodegree Bspline is not even C0 The next curve in the hierarchy Bl is continuous but not differentiable it has sharp corners at the control points certainly no derivative there Hence it s C0 but not C1 It turns out that B2 is a C1 curve This is a consequence of the Fundamental Theorem of Calculus which allows to compute d gBM Blt 1 B1ta which means that the derivative can be expressed using Bl and hence is continuous since Bl is By applying this argument once again we can show that the degree3 Bsplines also called cubic Bsplines are C2 iiei have continuous second derivative In general Bk is C i In applications the cubic Bspline curves are the most common they seem to hit the right spot in the tradeo between quality smoothness and simplicity low degree They are also wellsuited for modeling mased on physics lmagine traveling in a spaceship moving along the curve Bk For Bo it s even hard to imagine For Bl this is also problematic since it would require in nite acceleration at the control points this would make the trip bumpy and unpleasant B2 seems more plausible at least not exposing us to in nite accelerations However it would not be fun at the points where the acceleration changes abruptly imagine that you have nothing to hold to and at a certain moment the acceleration generating a force on you because of the innertia of your body changes abruptly you probably won t have time to adjust yourself and would fall down Eventually B3 seems to be great offering continuous change of the acceleration and thus a pleasant journey This is also somehow related to how we tend to drive into a sharp turn turning the wheel too fast can be felt immediately and even make the car unstable Thus we try to change the turning angle closely related to curvature and second derivative over a longer time making it as slowlyvarying as possi e 2 Polar form and DeBoor algorithm Bsplines are easy to specify using polar forms If the control points are 130131 i i P7 then the segment of the uniform degreen Bspline curve corresponding to parameters t E 2239 1 is given by Pi17ni37niuiPl P23927n23947nm2391P1 P23912392m239nPw For cubic Bsplines the above equations take the form P2397223971239P Uniform B Spline Curves Uniform BSpline curves are piecewise polynomial curves associated with a sequance of control points of any length Unlike the Bezier curves their degree is independent of the number of control points P4 P2 o v quot I quot 39 39 5 Lj P10 2 0 P3 1 F1 0P5 0 P0 6 i I P6 Figure 1 The curve BO BSpline curves can be constructed by recursive averaging Start from a curve which stays one second at the rst control point P0 then jumps to the second one P1 then after one second to the third etc Figure 1 This is going to be our zerodegree Bspline curve we ll generously call it a curve even though it doesn t really look like a curve The formula for that curve call it BO is Bot P for t E 2239 1 P2 P6 Figure 2 BO black and Bl blue Now we will start making the curve more regular by averaging ltering it We de ne a new curve degree one Bspline Bl by setting Blt to the average position of a point moving along the curve BO over time interval t t 1 Thus t1 31 Bowen t Now it s not hard to see that Bl is a polygonal curve joining the control points Figure 2 It s not di erentiable but it is de nitely nicerlooking than BO The averaging procedure can be applied to Bl to lead to B2 degreetwo Bspline and so on Thus we have a recursive formula n1 Bl1t t Bz 3513 1 Smoothness By smoothness we mean the number of derivatives that can be computed for a curve The more derivatives the smoother the curve We ll say that a curve B is ClC if the derivarives B t B t i Bkt exist for all t in the parameter range iiei everywhere where B is de ned and they are all continuous We ll say a curve is C0 if it s continuous We can now say that BO the zerodegree Bspline is not even C0 The next curve in the hierarchy Bl is continuous but not differentiable it has sharp corners at the control points certainly no derivative there Hence it s C0 but not C1 It turns out that B2 is a C1 curve This is a consequence of the Fundamental Theorem of Calculus which allows to compute d gBM Blt 1 B1ta which means that the derivative can be expressed using Bl and hence is continuous since Bl is By applying this argument once again we can show that the degree3 Bsplines also called cubic Bsplines are C2 iiei have continuous second derivative In general Bk is C i In applications the cubic Bspline curves are the most common they seem to hit the right spot in the tradeo between quality smoothness and simplicity low degree They are also wellsuited for modeling mased on physics lmagine traveling in a spaceship moving along the curve Bk For Bo it s even hard to imagine For Bl this is also problematic since it would require in nite acceleration at the control points this would make the trip bumpy and unpleasant B2 seems more plausible at least not exposing us to in nite accelerations However it would not be fun at the points where the acceleration changes abruptly imagine that you have nothing to hold to and at a certain moment the acceleration generating a force on you because of the innertia of your body changes abruptly you probably won t have time to adjust yourself and would fall down Eventually B3 seems to be great offering continuous change of the acceleration and thus a pleasant journey This is also somehow related to how we tend to drive into a sharp turn turning the wheel too fast can be felt immediately and even make the car unstable Thus we try to change the turning angle closely related to curvature and second derivative over a longer time making it as slowlyvarying as possi e 2 Polar form and DeBoor algorithm Bsplines are easy to specify using polar forms If the control points are 130131 i i P7 then the segment of the uniform degreen Bspline curve corresponding to parameters t E 2239 1 is given by Pi17ni37niuiPl P23927n23947nm2391P1 P23912392m239nPw For cubic Bsplines the above equations take the form P2397223971239P 1 Texture The most common form of texture mapping means laying a color pattern de ned by an image onto a 3D surface It allows to render 3D surfaces with realistic color variation From programmer s perspective this is done by providing tex ture coordinates for each vertex For each triangle of the 3D object the texture applied to it is copied from the triangle bounded by points given by the tex ture coordinates see Figure 1 More precisely texture coorinates are linearly interpolated when the triangle is scanconverted Then on the pixel processing stage they are used to look up color from the texture image Texture coordi nates 00 0 1 10 and 1 1 correspond to the corners of the image There are several ways to handle the case of one or both coordinates being outside of the range from 0 to 1 For example one can use only the fractional part of each coordinate to do texture lookup or they can both be clamped to 0 1 see Repeating and Clamping Textures in Chapter 9 of the OpenGL programming guide u1v1 u1 v1 u38 234 1 0 70 Figure 1 Applying a texture left to a 3D triangle right unil are the texture coordinates of the vertices The contents colors of the image speci ed as the texture are copied to the 3D triangle Note that this requires stretching or shrinking the texture particularly if the two triangles differ a lot in shape or s1ze OpenGL allows to use up to 4 texture coordinates and they can be trans formed using a 4 X 4 texture matrix Eventually ie after this transformation only two texture coordinates are used Apart from 2D trextures one can also use onedimensional textures or three dimensional textures 1n onedimensional case only one texture coordinate is used to look up the color and the texture is onedimensional 1n the three dimensional case the texture is 3D think of it as a colored volume and three texture coordinates are used for color lookup The simplest application of 3D texture is to use texture that describes color distribution in some material eig wood concrete or marble and use vertex coordinates as texture coordinates This causes a color of a point on the 3D surface to be looked up from its location in the volume and produces an object looking as if it was carved from t e volume Figure 2 Sizes of windows depend on how far they are 2 Perspectively correct interpolation ln graphics pipeline setting texture coodinates enter the pipeline as vertex tributes Tl 39 39 39 39 coordinates are passed on as fragment attributes In the fragment processing stage the color of each fragment is looked up from the texture image the 1D or 3D cases work same way except for 1D or 3D texture is used instead of image2D texture 21 Inadequacy 0f screen space interleatiDn 0f texture CDDrdinates So far as away to compute depth or color of fragments we were using screen space linear interpolation The data to be interpolated was sent with vertices in screen coordinates from vertex processor to the rasterizer The rasterizer interpolated this data from projected vertices to fragments This happened for depth color in Gouraud shading and normals in Phong shading However this is not the right approach for textures in fact it is not com pletely correct for shading either but its incorrectness is less aparent in this case Imagine a tall building with uniformly regular distribution and equal sizes of windows all normal tall buildings are like this Walk close to it and loo up The windows are going to appear smaller on higher oors Figure 2 Let s say you want to render this building as a big rectangular paralleliped using a texture to model color variation on the facade including the windows On this texture all windows are going to be of the same size since they are of the same size in 3D If you were to use screenspace linear interpolation to interpolate texture coordinates they would also be of the same size on the image To sum up what we need to do for texture coordinates is to rst linearly interpolate them in 3D and then project the result to 2D this process is called perspectively correct interpolation If we do things the usual way rst project vertices and then linearly interpolate texture coordinates from projected ver tices we ll get wrong resu ts 22 Perspectively correct interpolation We ll argue here that perspectively correct interpolation is equivalent to linear interpolations and division Recall that we would like to achieve the result equivalent to linear interpolation of texture coordinates in 3D and then project the results to 2D not the other way around which would be equivalent to linear interpolation in screen space et s go ack to reduction of a general perspective view to the canonical view Break it into two stages everything that happens before the nonlinear part arrow with the perspective transformation matrix next to it on the gure in transformation notes and the nonlinear part together with everything that happens after it The rst part is purely af ne Therefore it can be described using a 4 X 4 transformation matrix 39 quot l e quot of the result are denoted by 95A yA 2A we can write the transformation as follows IA 1 M A y 2A 2 1 1 The second part of the transformation maps the result of the rst one to screen coordinates To simplify things we ll write it using the proportionality relation of vectors or points which we denote by m Thus 1 m 11 means that one can scale 1 using a nonzero constant to get 11 w cv for some c y 0 The transformation we are looking at maps xAyA 2A into xAZAyA2A k 7 lzA since it is the simple form of perspective transformation followed by scaling and translation in 2 where and l are some constants This point is proportional to 95A yA klzA 7 1 So if we denote the coordinates of the resulting point by 95 y 2 we can write xA x y m P yA 2 2 A 1 where P is in the following simple 3 X 4 matrix 1 0 0 0 P 0 1 0 0 0 0 kl fl Putting all of the above together we can write the entire transformation as 95 x N y y M Z 1 1 2 where M P A is a 3 X 4 matrix Now let s say we have a triangle with texture coordinates in 3D We want to linearly interpolate texture coordinates to points on this triangle This process can be described as an assignment of a 3D point to texture coordinates u v The 3D point corresponding to uv should get color the texture image has at u 1 Since we use linear interpolation this de nes an af ne mapping of texture coordinates into 3D in Figure 1 this mapping is shown as the blue arrow which can be thought of as a parametrization of the triangle over texture coordinates This mapping can be represented using a 4 X 3 matrix T x u Z T w 1 1 Using this equation with 1 we obtain one that essentially describes how the texture image needs to be mapped onto the screen 95 u y m M T w 2 1 The matrix M depends only on the View so it can be computed when the View is speci ed just once before rendering all triangles The matrix T has to be computed on pertriangle basis based on the coordinates and texture coordinates of its vertices Notice that B M T is a 3 X 3 matrix If B szlz1m3j1m3 we can write M 522533 f 523532 b13532 512533 b12523 b13522 96 R b23531 b21533 b11533 b13531 b21513 b11523 3 2 1 b21532 b22531 b12531 b11532 b11522 b21512 2 Transformations and projections Transformations play an important role in computer graphics they allow to describe mappings between different coordinate systems move or scale 3D models can be used to concisely describe parallel or perspective projections Here we focus on transformations performed by graphics hardware in the ver tex processing stage The purpose of such transfromations is to translate the model coordinates in which a 3D object is modelled into the world coordinates global coordinate system describing the whole virtual world we would like to render on the screen and then to translate the world coordinates into the screen coordinates essentially the location of the projection onto the screen plus depth information Both of the transformations described above can be conveniently described using matrices 1 2D linear transformations as 2X2 matrices Linear transformations of the plane can be represented by two by two matrices Here are a few examp es cosa 7 sina Rotation around the origin by the angle of oz s1n oz cos oz Scaling by a factor of CE along the acaxis and by a factor of Cy along the yaxis Cr 0 Cy Uniform scaling by a factor c if c 2 it makes everything two times bigger c 0 c Symmetry about the origin is equivalent to uniform scaling by a factor of 71 71 0 0 71 Symmetry about the acaxis scales y by a factor of 71 and leaves the ac coor dinate unchanged 0 071 Similarly symmetry about the yaxis has the matrix 31 3 1andshearalongy l 3 Shear along the acaxis has the matrix 1 0 Figure 1 shows how it works A problem with with 2X2 matrices as a representation of 2D transformations is that translations which are obviously useful to represent erg movement of Figure 1 Shear transformations and how they act on a unit square objects do not t into this framework there is no way to represent a nontrivial translation as a 2 X 2 matrix since any transformation written by a 2 X 2 matrix maps the origin into itself unlike a translation by any nonzero vector Homogenous coordinates are a way around this problem by adding one extra third coordinate they allow to represent translations as 3x3 matrices In a moment we ll see that they also allow to represent 2D perspective projections as a 3x3 matrices which makes them even more useful for graphics 2 Translations as matrices using homogenous co ordinates We ll think of a 2D point x y as a point in 3D namely 95 y 1 This imme diately allows to represent a translation by a vector T1 Ty as the 3x3 matrix 1 0 T1 0 1 T 0 0 1 It maps the point x y 1 the 3D point corresponding to x to 95TE y Ty 1 the 3D point corresponding to the translaterd point x T1 y Ty All transformations discussed in the previous section can be represented in homoge nous coordinates as 3x3 matrices just complete its 2x2 matrix to a 3x3 one by adding one row and one column like this replace the stars with the entries of the 2x2 matrix 0 0 1 3 3D case All that has been said about the 2D case carries over to the 3D case A 3D point x y 2 in homogenous coordinates has coordinates x y 2 1 Translations are represented as 4 X 4 matrices 0 0 1 0 gt7 o 0 1 0 0 COOH Rotations around the coordinate axes have matrices cos oz 7 sin oz 0 0 cos oz 0 7 sin oz 0 1 0 0 0 sin oz cos oz 0 0 0 1 0 0 0 cos oz 7 sin oz 0 0 0 1 0 sin oz 0 cos oz 0 0 sin oz cos oz 0 0 0 0 1 0 0 0 1 0 0 1 Shears have matrices of the form 1 0 1 0 1 0 0 0 0 1 one of the stars replaced by a nonzero entry and all other ones by zeroes Describing scalings and symmetries about origin coordinate axes and co ordinate planes in the 3D case is left to the reader 4 Composing transformations given by matrices in homogenous coordinates Why use matrices in homogenous coordinates First they are exible enough to represent rigid transformations and scalings which are most commonly used to map model coordinates into world coordinates And then the matrix rep resentation allows to build more complex transformations from simple ones by means of composition equivalent to matrix multiplication For example the matrix of the 2D rotation by angle oz around a point 950 yo can be computed as follows Notice that the rotation is equivalent to a sequence of three elementary transformations whose matrices we already know 1 Translation by 7950 730 which takes the center of rotation to the origin 2 Rotation by oz around the origin 3 lnverse of the rst transformation ire translation by 950 yo The matrix of the composition can be computed as the product of the three components written right to left 1 0 x0 cos oz 7 sin oz 0 1 0 7x0 0 1 yo sin oz cos oz 0 0 1 eye 0 0 1 0 0 1 0 0 1 By carrying out the matrix multiplication we can obtain one 3 X 3 matrix repre senting the rotation about 950 yo Let us stress here that the resulting trans formation is not among the elementary transformations we listed previously but it has the same representation a 3 X 3 matrix 5 Projections There are two types ofprojections that are commonly used in computer graphics parallel and perspective Parallel projection is somewhat simpler to deal with but it is less natural most pictures of the real world like photographs we are used to are based on perspective projections However parallel projections are often used for visualizing more abstract data where realism is not that important Below we discuss the two kinds of projections in 2D 51 Parallel projections A typical approach to projections is to reduce them to a simple case called the canonical view which we describe rst Later on we will show how it is possible to reduce any projection both parallel and perspective to the canonical view by means of a sequence of transformations 5 1 1 Canonical view Canonical view is a special type of parallel projection depicted in Figure 2 The near and far clipping planes allow to restrict viewing to objects which are not too close and at the same time not too far from the screen in the world space This allows to save time by rejecting objects which are too far in many cases eg walkthroughs in large buildings such objects are not visible anyway eg are behind walls or they are barely visible or unimportant because they are too distant from the viewpoint The clipping planes play an important role in depth resolution points on the front clipping plane have zero depth points on the far clipping plane have depth of 1 The front clipping plane also allows to view interesting crosssections through complex objects by clipping away what s in the front The handling of the canonical view is very simple for a point x y one simply uses its rst coordinate as the coordinate of the projected point on the screen and the second coordinate as the depth The two coordinates together form what is often referred to as screen coordinates containing information far clipping plane gt near clipping plane 1 l Figure 2 Canonical view This is a parallel projection with the screen extend ing along the Xaxis from fl 0 to l 0 The projection direction is vertically down The near and far clipping planes in 2D they are lines of course are y 0 Xaxis and y 1 about the location of the projected point on the screen and the depth of course in 3D we would have two coordinates of the projected point and one depth coordinate For points within the View volume this yields depths between 0 and l and the coordinates of the projection on the screen between fl and 1 Only points having depth between 0 and l are rendered sice all other points are outside the view volume 512 General parallel projection can be reduced to canonical view Any parallel projection can be reduced to the canonical view by a sequence of transformations as shown in Figure 52 Perspective projection 521 A simple case Perhaps the most interesting property of the homogenous coordinates is that they allow to represent perspective projections as matrices Figure 4 shows the simplest possible case of a perspective projection we ll work out rst Notice that it sends the point x y to acy 1 Thus it requires division an operation not provided by the matrix formalism To help us write the projection X3 matrix we ll use the homogenous coordinate for scaling the rst two we ll think ofa point x y t as act With this convention the perspective projection can be wtitten as the matrix 1 0 0 0 l 0 0 l 0 This is a matrix which maps as y 1 95 y in homogenous coordinates to x y y which by our scaling convention corresponds to acy 1 To get an even more interesting representation of the perspective projection we can use the matrix 100 0171 010 which represents the transformation mapping 9531 to acy y 7 7 acy 17 It can be shown to map lines into lines why The xcoordinate of the result is exactly the xcoordinate of the perspectively projected input point The ycoordinate can be interpreted as the the depth as y increases from 0 to in nity y 7 1y increases monotonously from minus in nity to 1 Thus the halfplane y gt 0 is mapped onto the halfplane y lt 1 The order of the ycoordinates is preserved by that mapping if a point p1 is above has larger ycoordinate another point p2 then the image of p1 is above the image of p2 Therefore something like y 7 1y can be a good candidate for the depth it re ects the order of points with respect to the eye and can be computed from vertices by linear interpolation we ll scale it to be between 0 and 1 for points between the near and far clipping plane before using as the depth value though The qualitative picture showing how the transformation described above acts on lines through the origin is shown in Figure 5 See Figure 6 for a similar picture showing how it acts on horizontal lines Another interesting property of perspective transformation is that it maps families of parallel lines onto families of lines intersecting at one point of the screen as shown in Figure 7 This should not be a surprise since any parallel lines in the real world appear to come together at the horizon 7 think about lanes on a straight highway or look at Figure 8 522 An arbitrary perspective projection The general perspective view setup is shown in Figure 9 A lot like in the case of parallel projection the 2D counterpart of the view volume is bounded by four lines see Fig 9 The far clipping plane no object or part of an object behind that plane will not be drawn The near clipping plane no object in front of it will be drawn Two lines de ning the eld of view through the screen Of course in 3D we have the near and far planes and the eld of view is bounded by four planes each passing through the eye and one of the edges of the screen 6 3D case As usual everything that we said about 2D case carries over to 3D In particular every View can be reduced to the canonical View using transformations repre sented using 4 X 4 matrices in homogenous coordinates The most general way to describe a 3D View would be through de ning the Viewpoint the screen a parallelogram in 3D and the distances between front and back clipping planes and the viewpoint Of course the front and back clipping planes need to be parallel to the screen and on the same side of the Viewpoint ie they should be intersected by any ray stabbing the screen 7 Accuracy of the Zbuffer The nonlinear transformation of the zcoordinate allows linear interpolation of depth which is good but also has some consequences which might not be so desirable One of them is that the accuracy of depth is not uniform and depends on the locations of the front and back clipping planes Here is why Let s examine the 2D case 3D works the same way with View as described in Section 521 Let s say that the front and back clipping lines are at y yf y yb and the ycoordinates of triangles we would like to draw are in the range ymlm ymax The depth values for the triangles vertices are in the range Iobj 1 7 1ymm 1 7 1ym u and the depth range for the entire View volume is Low 1 7 1yf 1 7 1315 The internal representation of depth uses xed point numbers rather than oats The Low interval is scaled to 0 1 and a xed number of bits in current graphi cs cards this might be 24 or 32 bits is used to represent the depth value After the scaling Obj scales down to an interval of length L lymzn 71ymax lyf 1 yr For example if gm 1 and ymm 05 this reduces to 1 L 1f 1yb Notice that the magnitude of this expression heavily depends on where the front and back clipping lines are If the back clipping plane is y 0001 then L has to be smaller than 0001 R 2 10 which practically means losing ten bits of accuracy in depth since 10 most signi cant bits of the vertices are the same for most or even all vertices that are to be processed lncreasing yb will also increase L but in a way its effect would not be as bad no matter how big yb is L is less than yf To sum up for most efficient use of zbu er bits enclose the objects in the scene between front and back clipping planes as tightly as possible Most importantly don t put the front clipping plane too close to the origin even if this might be a tempting way to ensure that everything even objects very close to the viewpoint shows up on the screen direction of projection translate rot ate shear l l scale in X 1 translate and scale in y Figure 3 The process of reducing any parallel projection to a canonical View First we apply translation Which takes the center of the screen to the origin Then we rotate to make the screen overlap With the Xaxisi A shear transfor mation makes the projection direction vertical down Then scaling makes the screen extend from 71 to 1 Finally translation and scaling along y takes the near and far clipping planes to y 0 an y 00 U r X Figure 4 A perspective projection the center of the projection think of it as the location of the eye is the origin the screen onto Which points are projected is the dashed line described by y 1 b l C Figure 5 The black rays that approach the origin are mapped into the magenta colored vertical raysi Note that a magenta ray converges to the intersection of the screen and the corresponding black rayi This is the point on the screen that all points on the black ray project to q a a Figure 6 The black horizontal lines are mapped to the corresponding green horizontal lines Imagine that you put the black line on the xaxis and move it up With constant speed black arrow on the left Then the image of the black line Which is also a horizontal line is going to move up With decreasing speed The green lines are going to converge to the screen line y i YA Figure 7 The black lines in a family of parallel lines are mapped into the red lines all of which meet at one point on the screen This is the point Where the black line 71 passing through the eye intersects the screen Notice that the entire line 71 projects to a single point 7 thus the Xcoordinate of the projection is constant and the corresponding line 71 is vertical Figure 8 Projections of parallel here Vertical lines intersect at one point center of proj ection Figure 9 View volume the red lines bound the eld of View through the screen Planar subdivisions halfedge datastructure Euler s formula 1 Planar subdivisions We ll be interested in representations and properties of planar subdivisions Planar subdivision can be de ned as a nite set of edges in the plane such that any two edges are either disjoint or meet at a common endpoint We ll focus on edges being straight lines below but in fact they need not be straight lines the datastructures work and the properties that we ll discuss carry over to subdivisions based on curved lines An example of a planar subdivision is shown in Figure 1 By a face of a planar subdivision we mean a connected component in the complement of the union of its edges For example the subdivision in Figure 1 has 6 faces One of them is unbounded In general every planar subdivision has exactly one unbounded face Planar subdivisions are convenient in many contexts ln cartography they can be used to represent maps erg political maps where faces are states or counties One can also consider subdivisions on 3D surfaces In fact represen tations of surfaces based on polygons can be thought of as subdivisions of these surfaces into these polygons which play the role of faces Figure l A planar subdivision 2 Halfedge data structure Planar subdivisions can be represented using halfedge datastructure lts basic building block can be viewed as an arrow running along an edge The way the arrows are constructed is as follows For each edge in the subdivision draw arrows on its both sides each of them in such a way that the edge is on its right This leads to an arrangement of arrows like that shown in the Figure below Thus all edges have two arrows along them running in different directions This is where the name halfedge comes from edgetwo arrows so an ar rowedge2 Each of the half edges 1 is stored as a record having the following elds see the gure above the reference to the next half edge hn the reference to the previous halfedge hp the reference to the opposite halfedge ho the reference to the starting vertex hs F PS N the reference to its face hf Except for the halfedge records there are vertex records as well A vertex record stores vertex data like coordinates if the datastructure is to represent a 3D surface then perhaps color normals and texture coordinates and a pointer to one of the half edges out of it any will do This pointer together with all other components of the half edge data structure allows to efficiently nd all vertices faces or half edges incident to any speci ed vertex Finally we also store face records Apart from face attributes they contain a pointer to a half edge on the face s outer bounding loops We also store a list of pointers to half edges on its inner bounding loops one per loop These pointers allow to efficiently execute neighborhood queries for the faces Half edge data structure allows to efficiently ie in time proportional to the local complexity of the subdivision answer neighborhood queries such as these 1 output all vertices adjacent to a given one 2 output all faces adjacent to a given face across an edge 3 output all half edges bounding a face 3 Euler s formula for a planar subdivisions Let F E V and C be the number of faces edges vertices and connected com ponents of a subdivision respectively By number of connected components we mean the number of connected components of the graph formed by vertices and edges in the subdivision in the usual graph theoretic sense For example the subdivision in Figure 1 has 2 connected components The Euler formula states that for any planar subdivision F7EV1Ci The left hand side which can be thought of as alternating sum of numbers of mesh elements of different dimensions is often called the Euler characteristics The proof of the Euler s formula is simple take any planar subdivision and remove one edge There are two possibilities 1 The removal increases the number of connected components C by one erg edge marked with in Figure l 2 C does not change as a result of the edge removal In the rst case the numbers of faces and vertices do not change and therefore both the left hand side and the right hand side of the Euler formula increase by one In the second case the numbers of both edges and faces decrease by one and the number of vertices also stays xed Thus both sides of the Euler formula do not change This means that the Euler formula holds for a subdivision if and only if it holds for a subdivision with one edge removed By induction it holds for a subdivision iH it holds for the subdivision with all edges removed But after all edges are removed what we are left with is 71 separate vertices Thus C n V n E0 Fl and the Euler s formula is obviously satis ed 4 Euler s formula for triangulated surfaces Euler s formula holds not only for planar subdivisions it is true for subdivisions of spheres ire graphs drawn on spheres as well In fact subdivisions of spheres induce planar subdivisions with the same numbers of faces edges vertices and components as follows Put the sphere with the subdivision on a table making sure its highest point is not on an edge of a subdivision Imagine the sphere is made of a transparent material and the subdivision edges are drawn on it using an opaque ink Put a point light source at the highest point of the sphere The shadows of the edges of the subdivision on the sphere form curves on the table that we ll treat as edges of the corresponding planar subdivision Since the Euler s formula holds for the planar subdivision it also has to hold for the subdivision on the sphere If all faces of the subdivision on the sphere have three edges and the graph is connected C 2 then Euler formula says that F 7 E V 2 Notice that in this case 3F 2E this is because every triangle has three edges and every edge has exactly twe incident triangles imagine yeu ge ever faces and ft r case the Euler s fermula reduces te F 4 2V er 3V 6 E In particular here are reughly twice as ce Mereever the average vertex degree in such a triangulatien is clese te 6 this fellews frem the secend equation ge The Euler fermula as discussed abeve can be generalized frem triangulatiens 39 t r A hemee emerphism is a centinueus functien that is invertible and has a centinueus inverse lntuitively if a surface can be centinueusly witheut tearing cutting er gluing defermed te a sphere it is hemeemerphic te a sphere Euler s fermula can be used te recegnize the tepelegical type ef a 3D surface A classificatien theerem fer erientable surfaces says that any erientable surface is hemeemerphic te a sphere with a seme number ef handles Handles are hard te define fermally se let s just say that terus is a sphere with ene handle deuble terus is a sphere with twe handles Figure 2 In this case by genus we mean the number ef handles sphere has genus zere Figure 2 Terus genus 1 and deuble terus genus 2 sphere with ene er twe andles Any triangulatien ef a surface ef genus g has te ful ll Euler s fermula F e E V 2 7 2g In fact it is net hard te deduce this fermula frem the Euler s fermula fer triane gulatiens ef a sphere What de we need te get rid ef a handle Fer example we ceuld find a leep running areund the terus cut it aleng that leep and then ll the resulting heles Figure 3 by triangulating them Hew dees this change the Rasterization Lines and Circles We ll discuss various ways of drawing straight lines on a raster First we ll describe a simple algorithm which allows to draw a line using one or two oating point additions per pixel drawn Then we ll discuss the Bresenham s algorithm allowing to draw a line with integer endpoints using only cheap integer addi tions Then we ll see how the jagged lines can be smoothed using a simple antialiasing idea based on the Bresenham s algorithm s decision variable Fi nally we ll describe a variant of the Bresenham s algorithm allowing to draw circles Before we start notice that there is no unique and perfect way of drawing a line on a raster Figure 1 shows that there are at least two reasonably looking possibilities The algorithms presented here lead to something looking more like the rst solution upper line Figure 1 Two ways of scan converting a line segment for each vertical row of pixels shade the one which is the closest to line in the vertical direction top and shade all pixels intersected by the line bottom 1 DDA algorithm Digital Differential Analyzer Say that the line you want to draw starts at the point p pmpy and ends at q qE qy We ll move from p to q in small steps each of which moves us by the vector p71N where N is a certain integer We ll gure out later what it should be For each point on the way we nd the pixel containing it if the pixels have centers at integers this can be done by rounding the coordinates to the nearest integer All such pixels are shaded This is shown in Figure 2 xp7x Y3Pj dx 7mm dy 111ij for i0 to N do plotRoundxRoundy x x dx yiydy Figure 2 The DDA algorithm The gure shows the points whose pixels are plotted if N 5 In order for the lines to be continuous we need to ensure that we do not jump over entire row or column of pixels as we move from p to 11 On the other hand we should not be overcautious since too many steps will mean more computation than necessary This means that the best choice for N is N Tmax px 1105b lpy lym It ensures that both coordinates of the vector 5195 dy have magnitude less than 1 This is why no jumps over rows or columns of pixels occur Notice that if both endpoints have integer coordinates then with the N de ned above either dye or dy is equal to 1 since N is either lpi 7 111 or lpy 7 qyl Therefore we can actually compute one of the coordinates using integer arithmetic There is also a possibility of computing both using integers but this requires a division operation for each plotted pixel why 2 Bresenham s Algorithm The Bresenham s algorithm uses only a few integer additions per shaded pixel It assumes that the endpoints of the line have integer coordinates We will assume that the line starts at p 0 0 and ends at a point 11 qr qy having integer coordinates and contained in the rst octant of the coordinate system That is we ll assume 111 gt qy gt 0 Figure 3 All other cases can be reduced to the rstquadrant case by applying symmetries across the axes and translations Let s look at the centers of the pixels round dots in Figure 4 They form a square grid of points Let s call a vertical line passing through centers of qqXLy p 00 x Figure 3 A line having the endpoint in the rst quadrant the pixels a scanline We ll plot one pixel on each scanline intersecting the line segment to be drawn The center of the plotted pixel will be the closest to the intersection of the scanline and the line segment black dots in Figure 4 are the plotted pixels Imagine that we follow the plotted points from left to right As we do that we either have to move horizontally to the next pixel on the right or along the diagonal to the one immediately above the one on the right Thus at each step we need to increment the x coordinate and possibly increment the y coordinate unless a horizontal move happens Figure 4 A line having the endpoint in the rst quadrant In the Bresenham s algorithm we shall walk through the scanlines intersect ing the line from left to right At each step we will decide whether we have to move horizontally or along the diagonal The decision will be based on the decision variable The decision variable will be the difference of the y coordi nates of the midpoint of the interval connecting the center of the pixel plotted and the pixel immediately above it blue squares and the intersection of the line and the scanline In Figure 4 the value of the decision variables are the heights of the red bars Because we wish to plot pixels closest to the line along scanlines our algorithm has to ensure that all the decision variables are posi tive geometrically we need to plot the points in such a way that all the blue squares are above the line It is not hard to see that if we move horizontally then the value of the decision variable decreases by the slope of the line pgp1 the blue square does not change height and the linescanline intersection moves up by pypii If the new value of the decision variable computed this way is negative this would mean we rather need to move along the diagonal to keep it positive Consequently the decision variable needs to be increased by l The gorithm is given in Figure 5 d 12 LX initial value ofthe decision variable y 0 yicoordinate of the plotted points for x0 to qx do p10txy d i d LyLX di2 qy update the decision variable pretend that we move right for nor if dlt0 then if dlt0 then we need to move along the diagonal y y1 d d1 d2qx Figure 5 A line having the endpoint in the rst quadrant To make it useinteger operations only we can scale the decision variable by 2111 which leads to replacing the righthand sides of the assignments updating the d variable with what is given in red in Figure 5 3 Bresenham s Algorithm with Antialiasing Antialiasing attempts to reduce the jaggy appearence of the rasterized lines W ile there are many ways of doing this one which particularly well incorpo rates into the Bresenham s algorithm works by distributing the intensity be tween two pixels on each scanline rather than assigning all of it to one Two closest pixels closest to the line are shaded for each scanline One is the pixel plotted by the algorithm in Figure 5 The other one is either the one immedi ately above it or below it depending on whether the decision variable is less or greater than 5 Figure 7 The intensities assigned to the pixels depend on their distances to the intersection point of the scanline and the line being drawn 4 Bresenham Algorithm for Circles Let s say we want to scanconvert a circle centered at 00 with an integer radius R Figure 7 We ll see that the ideas we previously used for line scan conversion can be made work for this task First of all notice that the interior of the circle is characterized by the inequality Dx y 2 x2 y2 7 R2 lt 0 We ll use Dx y to derive our decision variable First let s think how to plot pixels close to the 18 of the circle marked red in the gure The range of the x coordinates for such pixels is from 0 to R We ll go over vertical scanlines through the centers of the pixels and for each such scanline compute the pixel on that line which is the closest to the scanlinecircle intersection point black dots in Figure 8 All such pixels will be plotted by our procedure if dlt5 then plotXyd 5 plotXy15d else plotXy 1 Sid plotXy1d5 Figure 6 Two cases which need to be addressed in the antialiased variant of the Bresenham s Algorithm Left the plotted point is above the line in this case we need to distribute intensity between this one and the one immediately below it Center the plotted point is below the line in this case we need to distribute intensity between this one and the one immediately below it Right here is what needs to replace the plotXy call in Fig 5 if antialiased lines are to be produced the third argument of plot is the intensity to be assigned to a pixe I RsanIRsqna XA2yA2iRA2gt Figure 7 A circle and the description of its interior and exterior as two quadratic inequalities Notice that each time we move to the next scanline the ycoordinate of the plotted point either stays the same or decreases by 1 the slope of the circle there is between 71 and 0 To decide what needs to be done we ll use the decision variable which will be the value of Dx y evaluated at the blue square ie the Figure 8 A circle and the description of its interior and exterior as two quadratic inequalities midpoint between the plotted pixel and the pixel immediately below The rst pixel plotted is 0 R and therefore the initial value of the decision variable should be D0R7i5127i52 7 R2 25 7 R The y variable holding the second coordinates of the plotted pixels will be initialized to R Let s now think what happens after a point x y is plotted First we ll pretend that we need to move the plotted point to the right no change in y and check if this keeps the decision variable negative we don t want any blue squares outside the circle If xy is the last plotted point the decision variable is D x y 7 5 1 After we move to the right it becomes Dx 1 y 7 5 Simple arithmetic shows that it increases by Dx 1 y 7 5 7 Dx y 7 5 2x 1 If this increase makes it positive we d better move down by 1 pixel This puts the blue square at 95 1 y 7 15 and means that we need to increase the decision by the previous 295 1 plus Dx 1 y 7 15 7 Dx 1y75272yi This leads to the algorithm in Figure 9 Clearly to make the decision variable integer we need to scale it by a factor of 4 All the multiplications by powers of two when updates of the decision variables are made can be done efficiently using shifts ltlt operator in C Eightway symmetry is used to go from 18th of the circle to the full circle Drawing BeZier Curves 1 General polynomial curves Let Bt t E 0 1 be a polynomial curve A simple way to draw it would be to compute several points along it like 30 BAt B2Att t t BNAt 31 where At lN and join each pair of consecutive points with intervals Thus we need to evaluate the polynomial at a certain number of sample parameters and join the resulting points with lines 11 How to evaluate the polynomial Let s concentrate on scalar cubic polynomials They are of the form bt at3 th ct dt Now the straighforward way to calculate bt is by btatttbttctdt It requires 6 multiplications and 3 additions count the stars and pluses A better way is by bt atbtctdt It takes only 3 additions and 3 multiplications 12 Can we do it using even fewer multiplications We can if we know that what we need are the values of b at equispaced points like 0 At 2At t t t NAt we mentioned using for polynomial curve drawing The idea is to use nite differences Abt 7 bt At 7 bt AAbt 7 Abt At 7 Abt AAAbt 7 AAbt At 7 AAbtt It s not hard to see that these polynomials have degrees 2 l and 0 Thus the last one is really a constant independent of t Here s how to use the A s b b0 db Ab0 ddb AAb0 dddb AAAb0 for i1 to N do b db this is bz At db ddb ddb dddb Notice that this uses only 3 additions inside the loop multiplications are needed only to initialize the variables the rst four lines Notice that their number does not depend on N the number of points we are computingt 13 Example For bt t3 Abt t At3 713 3Att2 3At2t At3 AAbt Abt At 7 Abt 6 At2t 6At3 AAAbt 6 At Thus AAAb is indeed a constant and the other two are quadratic and linear 2 Subdivision for Bezier curves Figure 1 The Bezier curve with control points 130131132 P3 is the union of two Bezier curves with control points P0 P01 P012 P0123 and P0123 P123 P23 Pgt Polygon Scan Conversion 1 Triangles Fast triangle scanconversion is based on linearity of the edges If an intersection of a scanline and an edge is known then to get the intersection of that edge with the next scanline below some constant depending on the edge s slope needs to be added to the xcoordinate of the current intersection see Figure 1 Figure 1 lntersections of a line with horizontal scanlines This leads to the algorithm in Figure 2 For simplicity let s assume that the triangle s vertices have integer coordinates The algorithm works by walk ing through the scanlines intersecting the triangle starting from the uppermost one until the lowermost is reached Each such scanline intersects the triangle s boundary at two points unless degeneracy like horizontal edge in the trian gle appears 7 see next page i The xcoordinates of the intersection points are updated at each step by adding a constant one over the edge s slope xovyo x1e 39 xn h g c x0 dxle x2x0y2y0 tween xle y and mighty ma 7 dxle xright 7 dxright dxright x2x1y2y1 f 1y osttep1 do p10 all pixels between xle y and mighty x2y2 ma 7 dxle xright 7 dxright Figure 2 Triangle scanconversion Clearly things change slightly if the vertex x1y1 is on the left of the edge joining the other two vertices In this case the increment that is applied to the intersection point on the left needs to be changed Figure 3 Also care must be taken of horizontal edges Initialize xle x0 and xnght am one loop 15 810 imp at ms sunlan DUB lump is enough Figure 3 Triangle ZOO each triangle type has to be treated differently 2 Linear interpolation While scanconversion A similar idea as that of adding a sloperelated constant to update the inter section point applies to interpolated quantities Linear functions change by a constant along any vector Thus in particular if we precompute the change along horizontal and vertical unit vectors Figure 4 we can use them to com pute the value at a neighboring pixel from the available value at the current one 1 Texture The most common form of texture mapping means laying a color pattern de ned by an image onto a 3D surface It allows to render 3D surfaces with realistic color variation From programmer s perspective this is done by providing tex ture coordinates for each vertex For each triangle of the 3D object the texture applied to it is copied from the triangle bounded by points given by the tex ture coordinates see Figure 1 More precisely texture coorinates are linearly interpolated when the triangle is scanconverted Then on the pixel processing stage they are used to look up color from the texture image Texture coordi nates 00 0 1 10 and 1 1 correspond to the corners of the image There are several ways to handle the case of one or both coordinates being outside of the range from 0 to 1 For example one can use only the fractional part of each coordinate to do texture lookup or they can both be clamped to 0 1 see Repeating and Clamping Textures in Chapter 9 of the OpenGL programming guide u1v1 u1 v1 u38 234 1 0 70 Figure 1 Applying a texture left to a 3D triangle right unil are the texture coordinates of the vertices The contents colors of the image speci ed as the texture are copied to the 3D triangle Note that this requires stretching or shrinking the texture particularly if the two triangles differ a lot in shape or s1ze OpenGL allows to use up to 4 texture coordinates and they can be trans formed using a 4 X 4 texture matrix Eventually ie after this transformation only two texture coordinates are used Apart from 2D trextures one can also use onedimensional textures or three dimensional textures 1n onedimensional case only one texture coordinate is used to look up the color and the texture is onedimensional 1n the three dimensional case the texture is 3D think of it as a colored volume and three texture coordinates are used for color lookup The simplest application of 3D texture is to use texture that describes color distribution in some material eig wood concrete or marble and use vertex coordinates as texture coordinates This causes a color of a point on the 3D surface to be looked up from its location in the volume and produces an object looking as if it was carved from t e volume Figure 2 Sizes of windows depend on how far they are 2 Perspectively correct interpolation ln graphics pipeline setting texture coodinates enter the pipeline as vertex tributes Tl 39 39 39 39 coordinates are passed on as fragment attributes In the fragment processing stage the color of each fragment is looked up from the texture image the 1D or 3D cases work same way except for 1D or 3D texture is used instead of image2D texture 21 Inadequacy 0f screen space interleatiDn 0f texture CDDrdinates So far as away to compute depth or color of fragments we were using screen space linear interpolation The data to be interpolated was sent with vertices in screen coordinates from vertex processor to the rasterizer The rasterizer interpolated this data from projected vertices to fragments This happened for depth color in Gouraud shading and normals in Phong shading However this is not the right approach for textures in fact it is not com pletely correct for shading either but its incorrectness is less aparent in this case Imagine a tall building with uniformly regular distribution and equal sizes of windows all normal tall buildings are like this Walk close to it and loo up The windows are going to appear smaller on higher oors Figure 2 Let s say you want to render this building as a big rectangular paralleliped using a texture to model color variation on the facade including the windows On this texture all windows are going to be of the same size since they are of the same size in 3D If you were to use screenspace linear interpolation to interpolate texture coordinates they would also be of the same size on the image To sum up what we need to do for texture coordinates is to rst linearly interpolate them in 3D and then project the result to 2D this process is called perspectively correct interpolation If we do things the usual way rst project vertices and then linearly interpolate texture coordinates from projected ver tices we ll get wrong resu ts 22 Perspectively correct interpolation We ll argue here that perspectively correct interpolation is equivalent to linear interpolations and division Recall that we would like to achieve the result equivalent to linear interpolation of texture coordinates in 3D and then project the results to 2D not the other way around which would be equivalent to linear interpolation in screen space et s go ack to reduction of a general perspective view to the canonical view Break it into two stages everything that happens before the nonlinear part arrow with the perspective transformation matrix next to it on the gure in transformation notes and the nonlinear part together with everything that happens after it The rst part is purely af ne Therefore it can be described using a 4 X 4 transformation matrix 39 quot l e quot of the result are denoted by 95A yA 2A we can write the transformation as follows IA 1 M A y 2A 2 1 1 The second part of the transformation maps the result of the rst one to screen coordinates To simplify things we ll write it using the proportionality relation of vectors or points which we denote by m Thus 1 m 11 means that one can scale 1 using a nonzero constant to get 11 w cv for some c y 0 The transformation we are looking at maps xAyA 2A into xAZAyA2A k 7 lzA since it is the simple form of perspective transformation followed by scaling and translation in 2 where and l are some constants This point is proportional to 95A yA klzA 7 1 So if we denote the coordinates of the resulting point by 95 y 2 we can write xA x y m P yA 2 2 A 1 where P is in the following simple 3 X 4 matrix 1 0 0 0 P 0 1 0 0 0 0 kl fl Putting all of the above together we can write the entire transformation as 95 x N y y M Z 1 1 2 where M P A is a 3 X 4 matrix Now let s say we have a triangle with texture coordinates in 3D We want to linearly interpolate texture coordinates to points on this triangle This process can be described as an assignment of a 3D point to texture coordinates u v The 3D point corresponding to uv should get color the texture image has at u 1 Since we use linear interpolation this de nes an af ne mapping of texture coordinates into 3D in Figure 1 this mapping is shown as the blue arrow which can be thought of as a parametrization of the triangle over texture coordinates This mapping can be represented using a 4 X 3 matrix T x u Z T w 1 1 Using this equation with 1 we obtain one that essentially describes how the texture image needs to be mapped onto the screen 95 u y m M T w 2 1 The matrix M depends only on the View so it can be computed when the View is speci ed just once before rendering all triangles The matrix T has to be computed on pertriangle basis based on the coordinates and texture coordinates of its vertices Notice that B M T is a 3 X 3 matrix If B szlz1m3j1m3 we can write M 522533 f 523532 b13532 512533 b12523 b13522 96 R b23531 b21533 b11533 b13531 b21513 b11523 3 2 1 b21532 b22531 b12531 b11532 b11522 b21512 2 REPRESENTING TRIANGLES ON A COMPUTER 1 Triangle Soup Each triangle has three vertices Each vertex has three coordinates Let s rep resent the triangles using an array with n rows ln ith row list the coordinates of the three vertices bounding the ith triangle That s the total of 9 oats per triangle 2 Triangle table vertex table adjacency table Triangle soup works OK in some cases eig if all you care about is just to render the triangles but is inconvenient if the triangles are to be processed in any way Almost any surface processing algorithm requires many accesses to neighbors of triangles or vertices of the mesh Finding eig triangles that share an edge with a given triangle in a triangle soup is expensive basically it requires exhaustive search over all triangles Therefore in most cases representations that support efficient neighborhood queries are preferred over the plain triangle soup representation 21 Manifold Meshes Most of the time we will be interested in nice regular tilings of surfaces bound ing 3D volumes In this case it is desirable to make sure the triangles form a manifold mesh A mesh is manifold if all its vertices are manifold vertices A manifold vertex is a vertex such that its incident triangles form a cyclic fan around it A mesh is manifold with boundary if all vertices are manifold or boundary manifold A boundary manifold vertex is a vertex whose incident triangles form a not necessarily circular fan See Figure 2 for examples of manifold and nonmanifold vertices Note that in a manifold mesh no edge can have more than two incident triangles 2 2 Tables A possible representation of a manifold mesh which provides easy access to neighbors consists of three tables Vertex table It lists all vertices of the mesh three oats coordinates per row It has as many rows as there are vertices Clearly it can store more pervertex info if required in a particular application like normals texture coordinates etc Note that by listing the vertices in this table we give them unique numbers identi ers between 0 and m 7 1 mnumber of vertices Figure 1 a a manifold Vertex a boundary manifold Vertex 07e non manifold Ver tices Figure 2 A zoom into a manifold mesh Triangle table For each triangle we store three integers the IDS of its vertices They can be thought of as indices into the vertex table Again this table induces a numbering of triangles For each triangle it also xes an ordering of its vertices this is the order in which they appear in the corresponding row i Adjacency table The dimensions of this table are the same as the dimen sions of the triangle table In row 239 and column j it keeps the ID of the triangle adjacent to triangle 239 across the edge opposite to its jth vertex Here is how the tables look for the boundary of a tetrahedron 4 triangles Max H mm m table mg tab mummy table vertex 2 mm vertex 1 myLG vertex 3 x3y313 23 Triangle table from triangle soup Constructing just any triangle table from triangle soup is easy just read the vertices as they appear in the soup table and put them in this order into the vertex table Then just use the consecutive integers as entries of the triangle table For the tetrahedron mesh this would lead to tables 962 22 2 2 960 20 2 0 961 21 2 1 953 23 23 962 22 2 2 0 1 2 Vertex table x1 y1 21 triangle table 3 4 5 963 23 2 3 6 7 8 960 20 2 0 962 22 2 2 963 23 2 3 961 21 2 1 960 20 2 0 Even though this is a valid way of converting a triangle soup to triangle table it misses the purpose of triangle table It is very uneconomical there are a lot of repetitions in the vertex table Also the triangle table itself does not tell much about the structure of the mesh in particular it s impossible to gure out which triangles are neighbors without peeking into the vertex table This is why we ll want to build the vertextriangle tables so that the no two rows in the vertex table are the same every vertex appears in it just once How to achieve this efficiently An worstcase optimal On log n algorithm works as follows Build a new table T with three times as many rows as there are triangles in the soup scan the rows of the soup table and generate three rows of T for each row lf row 239 of the soup table is mm121 964242 I w w then the three corresponding rows of T will be x y 21 239 0 39 x y z 2 1 39 x 31 2 2 2 Thus the rst three columns of T hold the coordinates of the consecutive ver tices which appear in the soup table in fact they are the same as the uneconom ical vertex table we constructed previously For each row the last two entries are essentially the address in the soup table of the vertex speci ed by the rst three entries Now take the table T and sort its rows lexicographically As a result of sorting vertices with the same coordinates will end up in adjacent rows since coordinates are most signi cant entries in each row Now read the rows of the sorted table For each row use the current vertex ID initialized to zero at startup as entry 239 j of the triangle table wherez39 andj are the fourth and fth entries in the row lncrement the current vertex ID every time you move to a new row and discover that its rst three entries are different from the rst three entries of the previous row 24 Adjacency table from triangle table Of course the minimal assumption we have to make to be able to build adjacency table at all is that every edge has at most two incident triangles Otherwise we may have more than one neighbor of a triangle across a speci c edge and we may need to use list of adjacent triangles rather than just one entry in the adjacency table Adjacency table can be constructed from triangle table in linear time This can be done in two steps First one constructs a list of incident triangles for each vertex This can be done by initializing the incident lists to null and then for each triangle adding it to the incidence lists of all its vertices Having constructed the incidence lists we ll the adjacency table The idea is to go over the vertices and for each vertex 1 use its incident triangle list to gure out which pairs of triangles are adjacent along an edge whose one endpoint is 1 Notice that we already know that all triangles in the v s incidence list have 1 as a vertex We need to compute pairs of triangles belonging to that list Subdivision 1 Bezier curves PS Figure 1 The Bezier curve with control points P0 P1 P2 P3 is the union of two Bezier curves with control POintS P0 P01 P012 P0123 and P0123 P123 P23 Ps It turns out that the points we compute in the De Casteljeau algorithm when evaluating the Bezier curve at t 5 can be used for the task of drawing the curve More precisely by computing Figure 1 P01 P0P12 P12 P1 PQ2 P23 P2P32 P012 P01 PM 2 P123 P12 P232 P0123 P012 P1232 we can split the Bezier curve to be drawn into two shorter curves This procedure can be iterated to obtain a splitting into four eight sixteen or even more short curves These short curves can be approximated by the control polygon Here is the pseudocode procedure drawBezier P0 P1 P2 P3 2 if enough subdivisions have been done then draw lines P0 P1 P1 P2 P2 P3 and return compute P01 P12 P23 P012 P123 P0123 drawBezierP0P01 P012P0123 drawBezierPO123P123P23P3 Notice that this procedure is very ef cient It may seem to require divisions but all those divisions are by two Therefore they can be implemented as bit shifts if integers are used or as decrementing the exponent 2 Bsplines Subdivision can be used to draw the Bspline curves in a way similar to Bezier curves The Bspline subdivision can be obtained by superposing two kinds of operations Doubling which maps a sequence of control points P0P1P2H Pn into the twice as long sequence P0P0P1P1P2P2 i i P7 P7 and Averaging which maps 130131132 JPn into the sequence of averages of each pair P0P1P1P2P2P3 Pnil l Pn 2 2 2 m 2 More precisely in the case of Bsplines of degree k one needs to perform one doubling operation and follow it by k averaging steps The resulting sequence of control points de nes the same curve as the initial one Moreover iterating the subdivision produces sequences of points converging to the Bspline curve at a very fast rate thus by performing a few subdivision steps and then just joining the consecutive points one can get an excellent approximation of the Bspline Notice that just as in the case of Bezier curves both of the above operations are very cheap computationally the averaging involves only addition of oats and division by two which can be computed eig by decrementing the exponent and therefore is much cheaper than a general division Example Let s consider subdivision for Bsplines of degree 1 Let the control points be P0 P1P2 WP The doubling stage yields P0 130131 131132 P2 JP mPn As a result of averaging we get P0P1 P1P2 2 a a P2P3 Pnil l Pn 2 a a a a P 0 2 2 P1 P2 Put Thus between each pair of consecutive control points the subdivision inserts their average Figure 2 explains how it works Another example Now let s take a closer look at subdivision procedure for cubic Bspline curves most common in applications As before let s start from control point sequence P0P1P2H Pni The doubling stage yields P0 130131 131132 P2 JP mPn Now we need to do three subdivision steps They produce the following sequences Po P5 P5 P5 P5 Figure 2 Subdivision for degree1 Bsplinesi At each steps it adds all the midpoints I tried really hard to put them at midpointsi After a few iterations all the points are densely stretched along the Bspline curve here piecewise linear curve which joins the consecutive control points th en 3P0P1 P03P1 3P1P2 P13P2 3PHPn PH3Pn 4 4 4 4 2 2 and nally P0P1 P06P1P2 P1P2 P16P2P3 2 l 8 l 2 l 8 ll 137172 6Pn71 Pn P7171 Pn 8 l 2 l H 3 Four point rule Sometimes it is useful to have a nice smooth curve passing unlike the Bsplines exactly through the speci ed control points A particularly simple way to achieve this is by interpolating subdivision schemesi lnterpolating subdivision does not move the existing control points It only inserts one de ned by special rules in between each pairi In the case of the fourpoint rule the point inserted between P and Pl1 is given y 1 9 9 1 EPzil E13 E131 131 Thus if the initial control points are P0P1P2 Pn then the points resulting from subdivision are 7P0 9P1 9P2 P3 5 16 7P 9P 9P 7 P P1 P2 1 21 3 4133 P n73 9Pn72 9Pn71 Pn nim a nil H 68 1 18 X I gt P0P12 P1P22 P2P32 P3P42 o P06 1P28 P16P2P38 P26 3P48 68 12 1839 18 a 12 i39 H o o o o o o o o 0 Figure 3 The Cubic Bspline Subdivision One can think of one step as a procedure which adds a midpoint between each two on the previous level all midpoints are shown in red above and moves each of the existing points a bit displaced old points are shown blue The new locations of the points are computed as weighted averages with weights of 1868 and 18 Notice that we have insufficient data to compute the new locations of the rst and last vertices so they are simply removed blue circles shown on the second level from top As we keep subdividing the points cover densely the space between the points corresponding to P1 and P3 iiei second and second last of the initial control points Thus the Bspline curve doesn t start at P0 but rather somewhere close to P1 more precisely at a point which results from P1 after moving it in each of the subdivision steps Notice that since P71 is not available we can t compute the point to be inserted just before P1 this is why the sequence starts with P1 The 4point rule with the above control point sequence starts at P2 ends at 13772 and passes through all control points in between the two The process is schematically shown in Figure 4 4 Subdivision for surfaces Loop scheme Subdivision is also possible in the surface setting The Loop Subdivision Scheme allows to turn a trian gulated mesh into a much smootherlooking one by applying a process similar to those discussed above for curves Mathematically speaking it produces a sequence of triangulated surfaces which converges to a smooth having a tangent plane everywhere surface See Figure 5 for an example The schematic picture of a subdivision is shown in Figure 6 Now we ll specify precisely how the red points and the new locations for the black points are computed All the calculations are based on the immeditely neighboring points before subdivision the resulting points are their weighted combinations The weights are shown in Figure 7 For the example mesh shown in Figure 8 the new vertex correswponding to the edge joining P2 and P9 1 just copy Figure 4 Four point subdivision the points which existed on the previous level blue stay in place Red points are computed by combining the neighboring four blue points on the previous level with weights 1 1 and 11 6 The limit curve starts at the third P2 and ends at the third from the end in this case P5 Figure 5 Loop subdivision applied to a tetrahedron top left Each next picture shows the result of applying subdivision to the previous one Notice how smooth the surface get after a few subdivision steps is given by 3 3 1 1 P P P P Q 8 2 8 9 8 1 8 3 The new location of the vertex P9 is given by 5 NGWPQZ ngI P1P2P8 88 Final remarks on Loop Subdivision In order for the computation to be possible we need a manifold mesh In a manifold mesh each edge has exactly two incident trialgles Also each vertex needs to have a closed fan of triangles around it A manifold mesh as described above cannot have boundary It should be intuitively clear that it is possible to obtain a nice manifold triangulation of a surface of any 3D solid One only needs to ensure that the triangles t tightly together For vertices of degree 3 weights of 716 for the central vertex and 316 for the three neighboring ones work better than the ones given above Figure 6 Loop subdivision adds edge vertices red points one per edge Each of the triangles of the input mesh gets split into four In the gure the black lines show the initial mesh and shown in red are vertices and edges added by the subdivision procedure Note that this gure is meant to show the logical relationship between the points before and after subdivision The red points are typically not at all on the edges joining the black points but they correspond to edges one per edge is added Also the black points do not stay in place but each of them has a corresponding vertex in the mesh before subdivision 18 k degree of the cenLral venex ie number of edges 0111 of it 38 38 3 8k US 3 8k Figure 7 The weights for the Loop subdivision scheme 5 Butter y Scheme The butter y scheme is a triangular subdivision scheme that is interpolating iiei which does not move the original black vertices As a result the subdivaded surfaces no matter how many subdivision steps are applied pass through the vertices of the original mesh The edge vertices are computed using the weights shown in Figure 9 Unfortunately Butter y subdivision doesn t have as good properties as Loop subdivision it is not smooth at vertices of the control mesh that have degree 3 and generally looks and mathematicall can be shown to indeed be less smooth than the Loop subdivision surface Linear interpolation Real functions are rarely given by an explicit formula allowing to evaluate them anywhere More frequently only salnple values of the function are given at certain points and in order to estimate the value at some place which is not a sample we need to somehow combine the available information This is the goal of interpolation By doing interpolation one can for example build a complete elevation map of a terrain when only an array of height values is given this is what happens in practice height cannot be measured everywhere no matter how you do it you end up with only nite number of measurements We used interpolation to estimate the color over a triangle when colors at vertices are given or normals depths over the triangle from normals depths at the vertices Linear interpolation from vertices of a triangle P0X0y0 v0 l x1 y1 vl P2X2y2 Figure 1 Linear interpolation from triangle s vertices notation Here is how the variant of linear interpolation we used works Let s say that we have a triangle as shown in Figure 1 It has vertices p0 armyo p1 x1 yl p2 x2 yg At each vertex we have a value let s say that they are v0 21 an v2 There is exactly one linear function which takes the value of 20 at p0 21 at p1 and 12 at p2 We can prove that by embedding our triangle and the values at vertices in 3D say that the triangle lies in the groung plane lift p0 to height v0 p1 to height v1 and p2 to height 12 This yields 3 points in 3space Now nd the plane passing through the three points This plane is the graph of the linear function we are looking for Here is how to compute it algebraically We seek a function of the form fxy Ax By C ABC to be determined The requirement that the values at the vertices are v0 v1 and 1 leads to three linear equations AI0By0C10 AI1By1C11 Ax2By2Cv2 P12 P123 P0123Bt Figure 1 De Casteljau algorithm The control points P0 P1 P2 and P3 are joined with line segments shown in red those red intervals form something called control polygon even though they are not really a polygon but rather a polygonal curve Each of them is then divided in the same ratio t 1 7 t giving rise to the green points P01 P12 and P23 Again each consecutive two green points are joined with line segments which are subdivided with blue points P012 and P123 After the interval joining the blue points is subdivided only one point is left here the black one This is the location of our moving point at time t The trajectory of that point for times between 0 and 1 is the Bezier curve Of course the more control points the more colors 1 would need to use ie the more the levels of subdivision are needed Bezier Curves Curves are trajectories of moving points We ll specify them as functions assigning a location of that moving point in 2D or 3D to a parameter t think of it as time In general all curves we are going to talk about will be de ned by a sequence of control points Curves useful in in geometric modeling should have shape which has a clear and intuitive relation to the path of the sequence of control points One family of curves satisfying this requirement are Bezier Curves 1 De nition and a few formulas and properties A Bezier curve is de ned by a sequence of N 1 control points P0 P1 PN We de ned the Bezier curve using the de Casteljau algorithm based on recursive splitting of the intervals joining the consecutive control points Figure 1 It should be clear from the picture that BpoplmpNaj P0 and BpoplmpNl PN ie the curve starts at the rst and ends at the last control point think what it means to split in 10 or 01 ratio P0131 and PN1PN are tangent vectors to the curve at its endpoints Figure 2 also easily visible in the unrelated Figure 3 The latter will be straightforward to verify once we have an explicit formula for the Bezier curve at the end of this section In general if 130131 Pn are control points for the curve then BO 71130131 and B 1 nP jlpn Notice that the endpoints of the interval which is split as the last one the blue one in Figure 1 are points of Bezier curves de ned by sequences of control points P0131 PN1 and P1P PN This leads to the formula BP0P1PNt1 t BPOP1VVVPN1tt BPngmPNU Remembering that for just one control point we have constant Bezier curve ie Bpot P0 we can use Figure 2 Bezier curves black dots are the control points and the curve is shown in blue Both curves have 4 control points and therefore are given by cubic polynomials Notice that the interval joining the rst two control points is tangent to the curve at its starting point and the line joining the last two control points is tangent to the curve at its nal point the above equation to derive an explicit formula for a Bspline curve of any degree Here s how Bpop1 171a BpO tgtlltBp1 17tP0tP1 having this Bpoplp2 171 Bpop1 tgtlltBP1P2 17117tP0tP1t17tP1tP2 17t2 1P02t17tP1t2P21 It s not hard to guess that in general to evaluate BpoplmpN we need to weight the consecutive control points with the terms of the expansion of 1 7 t tN 1i That is the weight sequences are see above 1 for N 7 0 17tt N 1 17t22t17tt2 N 7 2 and 17t3 317t2t 317tt2 t3 for N 3 The weights as functions of t for a xed N are called Bezie39r basis functions of degree N Note that this is indeed a basis in the linear algebra sense for the space of all polynomials in fact every polynomial curve can be expressed as a Bezier curve for a certain control point Thus Bezier curves of degree d are exactly polynomial curves of degree d This might seem a bit disappointing at rst but remember that what we gain is an intuitive way to control the curve s shape based on control points Check out one of the applets to experience this If we have 5 control points then the weights are 17 t4 4t1 7 t3 6t21 7 t2 4t31 7 t t4 Thus the formula for the Bspline curve which is a degree4 polynomial in this case is Bpoplpzpm 17t4P04t17t3 P16t217t2 1P24t317tP3t4P41 Notice that this means that each point on a Bezier curve is a weighted average of the input points P2 Figure 3 The control polygon is shown red The convex hull of the control points is the green polygon smallest convex having all the control points inside The Bezier curve is shown in blue The convex hull property states that blue has to be contained inside the green polygon Therefore it lies inside the convex hull of the control points ie the smallest convex polygon enclosing them see Figure 3 2 Joining BeZier segments Based on the previous section it is not hard to gure out how to join two or more Bezier curves so that they all form a smooth curve Figure 4 explains it all 3 Polar representations of polynomial curves Polar forms provide a very powerful formalism for de ning as well as manipulating and understanding polynomial curves In this section we discuss the basics of this approac 31 De nition Take any polynomial of one variable P and let d be an integer such that deg P S d Then P can be written in a unique way in the following form Pm Ma 2 v v v 0 1 where M is a symmetric and multia ine function of 51 variables Symmetry means that permuting arguments does not change the value of M Formally Mx1x2 96d M967r1967r2 96m for any permutation 7r of 12Hdi For example if d 3 M110 M011 M101 If an argument x of M is repeated k times instead of writing it k times we ll just write 95k For example M001 M021 M0211 P3P0 P2 P3P039 P3 Figure 4 Joining two Bezier curves Control points for one are red and for the other primed 7 blue We want them to join so the second one should start where the rst ends Thus the last control point of the rst curve has to overlap with the rst of the second curve This point is shown in magenta redblue Top left the vectors P2133 and Pipi are not collinear Therefore the red and blue curves have di erent tangent lines at the point they meet at magenta dot and so they don t join smoothly there Right the vectors are collinear now but they point in di erent directions So the red curve arrives from one direction at the magenta point but the blue one leaves in the opposite direction This causes a very in nitely sharp cusp in the curve Bottom left The vectors are parallel and they point in the same direction the two curves join smoothly Before we say what multiaf ne means let s de ne what af ne means for a function Basically a function A V A VW are vector spaces is af ne if it preserves weighted averages 140m 1 131 01A 1 1140 for any x y in the domain and any scalar a A function of several variables is multiaf ne if it is af ne with respect to every variable Since our M has to be symmetric therefore we are free to permute the variables without changing the value it is enough to say that it has to be af ne with respect to the rst variable MOl170yI2I3dQMIQI3Id170MyI2I3d In what follows we ll call M a polar form or a blossom of P 32 A few examples or polar forms Example 1 Let Pt 1 x 2x2 x3 and 513 Then the polar form of P is given by l 2 Mxyz1 xyz xyxzyzxyz The equation Pt Mt t t is straightforward to check Symmetry is also easy to see swapping any two variables doesn t change the formula for M Multiaf nity is also not hard to see either imagine you x two variables say y and 2 making them constants Then the formula for M reduces to a degree1 polynomial in x 1 2 1 2 1 y2 y2 yzyz m Degree1 polynomials are af ne functions and therefore P is multiaf ne Example 2 For the same polynomial P and d 5 the polar form is 1 2 Mxyztu1Exyztumay952xtxuyzytyuztzutu 1 xyz xyt xyu xzt xzu xtu yzt yzu ytu am It is different from the polar form obtained in the preVious example but this does not contradict the uniqueness of the polar form since this one is based on a different d Conclusion The general procedure for writing the polar form is to de ne it as a linear combination of symmetric polynomials of 51 variables The symmetric polynomials of degree k and of 51 variables is simply a sum of all possible products of k different variables These expressions can get long fast but good news is that in practice one doesn t really need them 33 Bezier curve blossoms One reason that makes polar forms useful is that by putting constraints on them we can de ne polynomials For many polynomial curves common in CADCAM systems the polar forms are particularly simple Bezier curve of degree d can for example be de ned by the following constraints Let 130131 1 Pd be its control points Bezier curve has polar form that satis es M0 k1 7 Pk for k 0121Hd1 In fact the de Casteljau algorithm can be Viewed as a procedure for computing Pt Mtt1 1 1 t Below we elaborate on this relationship for cubic Bsplines Same argument works for Bezier curves of all other degrees In the case of cubic Bsplines the polar form is de ned by Mo 0 0 7 P0 M00 1 7 P1 M011 7 P2 M111 7 P3 2 We want to compute Pt Mt t t Here is a way to do it We use the constraints on M to compute MO 0 t MO 113 M1 1 t M00t 7 Mo 01 1 1 7 t 0 7 tM00 1 1 7 tM0 00 7 tP1 17tP0 P01 M01t 7 Mo t 1 7 M0t117t 01 7 tM011 17tM00 1 7 tPQ 17tP1 P12 M11t 7 Mt11 7 Mt117t 011 7 tM111 17tM0 1 1 7 tP3 17tP2 P23 Planar subdivisions halfedge datastructure Euler s formula 1 Planar subdivisions We ll be interested in representations and properties of planar subdivisions Planar subdivision can be de ned as a nite set of edges in the plane such that any two edges are either disjoint or meet at a common endpoint We ll focus on edges being straight lines below but in fact they need not be straight lines the datastructures work and the properties that we ll discuss carry over to subdivisions based on curved lines An example of a planar subdivision is shown in Figure 1 By a face of a planar subdivision we mean a connected component in the complement of the union of its edges For example the subdivision in Figure 1 has 6 faces One of them is unbounded In general every planar subdivision has exactly one unbounded face Planar subdivisions are convenient in many contexts ln cartography they can be used to represent maps erg political maps where faces are states or counties One can also consider subdivisions on 3D surfaces In fact represen tations of surfaces based on polygons can be thought of as subdivisions of these surfaces into these polygons which play the role of faces Figure l A planar subdivision 2 Halfedge data structure Planar subdivisions can be represented using halfedge datastructure lts basic building block can be viewed as an arrow running along an edge The way the arrows are constructed is as follows For each edge in the subdivision draw arrows on its both sides each of them in such a way that the edge is on its right This leads to an arrangement of arrows like that shown in the Figure below Thus all edges have two arrows along them running in different directions This is where the name halfedge comes from edgetwo arrows so an ar rowedge2 Each of the half edges 1 is stored as a record having the following elds see the gure above the reference to the next half edge hn the reference to the previous halfedge hp the reference to the opposite halfedge ho the reference to the starting vertex hs F PS N the reference to its face hf Except for the halfedge records there are vertex records as well A vertex record stores vertex data like coordinates if the datastructure is to represent a 3D surface then perhaps color normals and texture coordinates and a pointer to one of the half edges out of it any will do This pointer together with all other components of the half edge data structure allows to efficiently nd all vertices faces or half edges incident to any speci ed vertex Finally we also store face records Apart from face attributes they contain a pointer to a half edge on the face s outer bounding loops We also store a list of pointers to half edges on its inner bounding loops one per loop These pointers allow to efficiently execute neighborhood queries for the faces Half edge data structure allows to efficiently ie in time proportional to the local complexity of the subdivision answer neighborhood queries such as these 1 output all vertices adjacent to a given one 2 output all faces adjacent to a given face across an edge 3 output all half edges bounding a face 3 Euler s formula for a planar subdivisions Let F E V and C be the number of faces edges vertices and connected com ponents of a subdivision respectively By number of connected components we mean the number of connected components of the graph formed by vertices and edges in the subdivision in the usual graph theoretic sense For example the subdivision in Figure 1 has 2 connected components The Euler formula states that for any planar subdivision F7EV1Ci The left hand side which can be thought of as alternating sum of numbers of mesh elements of different dimensions is often called the Euler characteristics The proof of the Euler s formula is simple take any planar subdivision and remove one edge There are two possibilities 1 The removal increases the number of connected components C by one erg edge marked with in Figure l 2 C does not change as a result of the edge removal In the rst case the numbers of faces and vertices do not change and therefore both the left hand side and the right hand side of the Euler formula increase by one In the second case the numbers of both edges and faces decrease by one and the number of vertices also stays xed Thus both sides of the Euler formula do not change This means that the Euler formula holds for a subdivision if and only if it holds for a subdivision with one edge removed By induction it holds for a subdivision iH it holds for the subdivision with all edges removed But after all edges are removed what we are left with is 71 separate vertices Thus C n V n E0 Fl and the Euler s formula is obviously satis ed 4 Euler s formula for triangulated surfaces Euler s formula holds not only for planar subdivisions it is true for subdivisions of spheres ire graphs drawn on spheres as well In fact subdivisions of spheres induce planar subdivisions with the same numbers of faces edges vertices and components as follows Put the sphere with the subdivision on a table making sure its highest point is not on an edge of a subdivision Imagine the sphere is made of a transparent material and the subdivision edges are drawn on it using an opaque ink Put a point light source at the highest point of the sphere The shadows of the edges of the subdivision on the sphere form curves on the table that we ll treat as edges of the corresponding planar subdivision Since the Euler s formula holds for the planar subdivision it also has to hold for the subdivision on the sphere If all faces of the subdivision on the sphere have three edges and the graph is connected C 2 then Euler formula says that F 7 E V 2 Notice that in this case 3F 2E this is because every triangle has three edges and every edge has exactly twe incident triangles imagine yeu ge ever faces and ft r case the Euler s fermula reduces te F 4 2V er 3V 6 E In particular here are reughly twice as ce Mereever the average vertex degree in such a triangulatien is clese te 6 this fellews frem the secend equation ge The Euler fermula as discussed abeve can be generalized frem triangulatiens 39 t r A hemee emerphism is a centinueus functien that is invertible and has a centinueus inverse lntuitively if a surface can be centinueusly witheut tearing cutting er gluing defermed te a sphere it is hemeemerphic te a sphere Euler s fermula can be used te recegnize the tepelegical type ef a 3D surface A classificatien theerem fer erientable surfaces says that any erientable surface is hemeemerphic te a sphere with a seme number ef handles Handles are hard te define fermally se let s just say that terus is a sphere with ene handle deuble terus is a sphere with twe handles Figure 2 In this case by genus we mean the number ef handles sphere has genus zere Figure 2 Terus genus 1 and deuble terus genus 2 sphere with ene er twe andles Any triangulatien ef a surface ef genus g has te ful ll Euler s fermula F e E V 2 7 2g In fact it is net hard te deduce this fermula frem the Euler s fermula fer triane gulatiens ef a sphere What de we need te get rid ef a handle Fer example we ceuld find a leep running areund the terus cut it aleng that leep and then ll the resulting heles Figure 3 by triangulating them Hew dees this change the

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.