Computer Graphics Notes PDF

INDEX UNIT NO TOPIC PAGE NO Introduction: Application areas of Computer Graphics I 1-11 Output primitives: Points and lines 2-D geometrical transforms:...

INDEX UNIT NO TOPIC PAGE NO Introduction: Application areas of Computer Graphics I 1-11 Output primitives: Points and lines 2-D geometrical transforms: II 12-29 2-D viewing 3-D object representation III 30-43 3-D Geometric transformations IV 44-56 Visible surface detection methods V 57-60 Computer animation  UNIT- 1 Overview of Computer Graphics Application of Computer Graphics Computer-Aided Design for engineering and architectural systems etc. Objects maybe displayed in a wireframe outline form. Multi-window environment is also favored for producing various zooming scales and views. Animations are useful for testing performance. Presentation Graphics To produce illustrations which summarize various kinds of data. Except 2D, 3D graphics are good tools for reporting more complex data. Computer Art Painting packages are available. With cordless, pressure-sensitive stylus, artists can produce electronic paintings which simulate different brush strokes, brush widths, and colors. Photorealistic techniques, morphing and animations are very useful in commercial art. For films, 24 frames per second are required. For video monitor, 30 frames per second are required. Entertainment Motion pictures, Music videos, and TV shows, Computer games Education and Training Training with computer-generated models of specialized systems such as the training of ship captains and aircraft pilots. Visualization For analyzing scientific, engineering, medical and business data or behavior. Converting data to visual form can help to understand mass volume of data very efficiently. Image Processing Image processing is to apply techniques to modify or interpret existing pictures. It is widely used in medical applications. Graphical User Interface Multiple window, icons, menus allow a computer setup to be utilized more efficiently. Video Display devices Cathode-Ray Tubes (CRT) - still the most common video display device presently 1  Electrostatic deflection of the electron beam in a CRT An electron gun emits a beam of electrons, which passes through focusing and deflection systems and hits on the phosphor-coated screen. The number of points displayed on a CRT is referred to as resolutions (eg. 1024x768). Different phosphors emit small light spots of different colors, which can combine to form a range of colors. A common methodology for color CRT display is the Shadow-mask meth Illustration of a shadow-mask CRT The light emitted by phosphor fades very rapidly, so it needs to redraw the picture repeatedly. There are 2 kinds of redrawing mechanisms: Raster-Scan and Random-Scan Raster-Scan The electron beam is swept across the screen one row at a time from top to bottom. As it moves across each row, the beam intensity is turned on and off to create a pattern of illuminated spots. This scanning process is called refreshing. Each complete scanning of a screen is normally called a frame. The refreshing rate, called the frame rate, is normally 60 to 80 frames per second, or described as 60 Hz to 80 Hz. Picture definition is stored in a memory area called the frame buffer. This frame buffer stores the intensity values for all the screen points. Each screen point is called a pixel (picture element). On black and white systems, the frame buffer storing the values of the pixels is called a bitmap. Each entry in the bitmap is a 1-bit data which determine the on (1) and off (0) of the intensity of the pixel. On color systems, the frame buffer storing the values of the pixels is called a pixmap (Though nowadays many graphics libraries name it as bitmap too). Each entry in the pixmap 2 occupies a number of bits to represent the color of the pixel. For a true color display, the number of bits for each entry is 24 (8 bits per red/green/blue channel, each channel 2 8=256 levels of intensity value, ie. 256 voltage settings for each of the red/green/blue electron guns). Random-Scan (Vector Display) The CRT's electron beam is directed only to the parts of the screen where a picture is to be drawn. The picture definition is stored as a set of line-drawing commands in a refresh display file or a refresh buffer in memory. Random-scan generally have higher resolution than raster systems and can produce smooth line drawings, however it cannot display realistic shaded scenes. Display Controller For a raster display device reads the frame buffer and generates the control signals for the screen, ie. the signals for horizontal scanning and vertical scanning. Most display controllers include a color map (or video look-up table). The major function of a color map is to provide a mapping between the input pixel value to the output color. Anti-Aliasing On dealing with integer pixel positions, jagged or stair step appearances happen very usually. This distortion of information due to under sampling is called aliasing. A number of ant aliasing methods have been developed to compensate this problem. One way is to display objects at higher resolution. However there is a limit to how big we can make the frame buffer and still maintaining acceptable refresh rate. Drawing a Line in Raster Devices DDA Algorithm 3 In computer graphics, a hardware or software implementation of a digital differential analyzer (DDA) is used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. In its simplest implementation the DDA Line drawing algorithm interpolates values in interval [(xstart, ystart), (xend, yend)] by computing for each xi the equations xi = xi−1+1/m, yi = yi−1 + m, where Δx = xend − xstart and Δy = yend − ystart and m = Δy/Δx. The dda is a scan conversion line algorithm based on calculating either dy or dx. A line is sampled at unit intervals in one coordinate and corresponding integer values nearest the line path are determined for other coordinates. Considering a line with positive slope, if the slope is less than or equal to 1, we sample at unit x intervals (dx=1) and compute successive y values as Subscript k takes integer values starting from 0, for the 1st point and increases by until endpoint is reached. y value is rounded off to nearest integer to correspond to a screen pixel. For lines with slope greater than 1, we reverse the role of x and y i.e. we sample at dy=1 and calculate consecutive x values as Similar calculations are carried out to determine pixel positions along a line with negative slope. Thus, if the absolute value of the slope is less than 1, we set dx=1 if i.e. the starting extreme point is at the left. The basic concept is: - A line can be specified in the form: y = mx + c - Let m be between 0 to 1, then the slope of the line is between 0 and 45 degrees. - For the x-coordinate of the left end point of the line, compute the corresponding y value according to the line equation. Thus we get the left end point as (x1,y1), where y1 may not be an integer. - Calculate the distance of (x1,y1) from the center of the pixel immediately above it and call it D1 - Calculate the distance of (x1,y1) from the center of the pixel immediately below it and call it D2 - If D1 is smaller than D2, it means that the line is closer to the upper pixel than the lower pixel, then, we set the upper pixel to on; otherwise we set the lower pixel to on. - Then increatement x by 1 and repeat the same process until x reaches the right end point of the line. - This method assumes the width of the line to be zero Bresenham's Line Algorithm 4 This algorithm is very efficient since it use only incremental integer calculations. Instead of calculating the non-integral values of D1 and D2 for decision of pixel location, it computes a value, p, which is defined as: p = (D2-D1)* horizontal length of the line if p>0, it means D1 is smaller than D2, and we can determine the pixel location accordingly However, the computation of p is very easy: The initial value of p is 2 * vertical height of the line - horizontal length of the line. At succeeding x locations, if p has been smaller than 0, then, we increment p by 2 * vertical height of the line, otherwise we increment p by 2 * (vertical height of the line - horizontal length of the line) All the computations are on integers. The incremental method is applied to void BresenhamLine(int x1, int y1, int x2, int y2) { int x, y, p, const1, const2; p=2*(y2-y1)-(x2-x1); const1=2*(y2-y1); const2=2*((y2- y1)-(x2-x1)); x=x1; y=y1; SetPixel(x,y); while (x= y To see the mid-point circle algorithm in action lets use it to draw a circle centred at (0,0) with radius 10. Scan-Line Polygon Fill Algorithm - Basic idea: For each scan line crossing a polygon, this algorithm locates the intersection points of the scan line with the polygon edges. These intersection points are shorted from left to right. Then, we fill the pixels between each intersection pair. - Some scan-line intersection at polygon vertices require special handling. A scan line passing through a vertex as intersecting the polygon twice. In this case we may or may not add 2 points to the list of intersections, instead of adding 1 points. This decision depends on whether the 2 edges at both sides of the vertex are both above, both below, or one is above and one is below the scan line. Only for the case if both are above or both are below the scan line, then we will add 2 points. Inside-Outside Tests: - The above algorithm only works for standard polygon shapes. However, for the cases which the edge of the polygon intersects, we need to identify whether a point is an interior or exterior point. Students may find interesting descriptions of 2 methods to solve this problem in many text books: odd-even rule and nonzero winding number rule. 9 Boundary-Fill Algorithm - This algorithm starts at a point inside a region and paint the interior outward towards the boundary. - This is a simple method but not efficient: 1. It is recursive method which may occupy a large stack size in the main memory. void BoundaryFill(int x, int y, COLOR fill, COLOR boundary) { COLOR current; current=GetPixel(x,y); if (currentboundary) and (currentfill) then { SetPixel(x,y,fill); BoundaryFill(x+1,y,fill,boundary); BoundaryFill(x-1,y,fill,boundary); BoundaryFill(x,y+1,fill,boundary); BoundaryFill(x,y-1,fill,boundary); } } - More efficient methods fill horizontal pixel spands across scan lines, instead of proceeding to neighboring points. 10 Flood-Fill Algorithm - Flood-Fill is similar to Boundary-Fill. The difference is that Flood-Fill is to fill an area which I not defined by a single boundary color. void BoundaryFill(int x, int y, COLOR fill, COLOR old_color) { if (GetPixel(x,y)== old_color) { SetPixel(x,y,fill); BoundaryFill(x+1,y,fill,boundary); BoundaryFill(x-1,y,fill,boundary); BoundaryFill(x,y+1,fill,boundary); BoundaryFill(x,y-1,fill,boundary); } 11  Part –I, UNIT -2 Two Dimensional Transformations In many applications, changes in orientations, size, and shape are accomplished with geometric transformations that alter the coordinate descriptions of objects. Basic geometric transformations are: Translation Rotation Scaling Other transformations: Reflection Shear 3.1 Basic Transformations Translation We translate a 2D point by adding translation distances, tx and ty, to the original coordinate position (x,y): x' = x + tx, y' = y + ty Alternatively, translation can also be specified by the following transformation matrix : 1 0t x 0 1 t y 0 01 Then we can rewrite the formula as: x' 1 0 tx x 0 t y y' = 1 y 1 0 01 1 For example, to translate a triangle with vertices at original coordinates (10,20), (10,10), (20,10) by tx=5, ty=10, we compute as followings: Translation of vertex (10,20): x' 1 0 5 10 1*10 0 * 20 5 *1 15 y' = 0 1 10 20 = 0 *10 1* 20 10 *1 = 30 1 0 01 1 0 *10 0 * 20 1*1 1 Translation of vertex (10,10): x' 1 05 10 1*10 0 *10 5 *1 15 y' = 0 1 10 10 = 0 *10 1*10 10 *1 = 20 1 0 0 1 1 0 *10 0 *10 1*1 1 12 Translation of vertex (20,10): x' 1 0 5 20 1* 20 0 *10 5 *1 25 y' =0 1 10 10 = 0 * 20 1*10 10 *1 = 20 1 0 01 1 0 * 20 0 *10 1*1 1 The resultant coordinates of the triangle vertices are (15,30), (15,20), and (25,20) respectively. Exercise: translate a triangle with vertices at original coordinates (10,25), (5,10), (20,10) by tx=15, ty=5. Roughly plot the original and resultant triangles. 3.1.2 Rotation About the Origin To rotate an object about the origin (0,0), we specify the rotation angle ?. Positive and negative values for the rotation angle define counterclockwise and clockwise rotations respectively. The followings is the computation of this rotation for a point: x' = x cos ? - y sin ? y' = x sin ? + y cos ? Alternatively, this rotation can also be specified by the following transformation matrix: cos sin 0 0 sin cos 0 1 0 Then we can rewrite the formula as: x' cos sin 0 x y' = sin cos 0 y 1 0 0 1 1 For example, to rotate a triange about the origin with vertices at original coordinates (10,20), (10,10), (20,10) by 30 degrees, we compute as followings: cos sin 0 cos 30 sin 30 0 0.866 0.5 0 sin cos 0 = sin 30 cos 30 0 = 0.5 0.866 0 0 0 1 0 0 1 0 0 1 Rotation of vertex (10,20): x' 0.866 0.5 0 10 0.866 *10 ( 0.5) * 20 0 *1 1.34 y' = 0.5 0.866 0 20 = 0.5 *10 0.866 * 20 0 *1 = 22.32 1 0 0 1 1 0 *10 0 * 20 1*1 1 2 13 Rotation of vertex (10,10): x' 0.866 0.5 0 10 0.866 *10 ( 0.5) *10 0 *1 3.66 y' = 0.5 0.866 0 10 = 0.5 *10 0.866 *10 0 *1 = 13.66 1 0 0 1 1 0 *10 0 *10 1*1 1 Rotation of vertex (20,10): x' 0.866 0.5 0 20 0.866 * 20 ( 0.5) *10 0 *1 12.32 y' = 0.5 0.866 0 10 = 0.5 * 20 0.866 *10 0 *1 = 18.66 1 0 0 1 1 0 * 20 0 *10 1*1 1 The resultant coordinates of the triangle vertices are (-1.34,22.32), (3.6,13.66), and (12.32,18.66) respectively. Exercise: Rotate a triange with vertices at original coordinates (10,20), (5,10), (20,10) by 45 degrees. Roughly plot the original and resultant triangles. Scaling With Respect to the Origin We scale a 2D object with respect to the origin by setting the scaling factors sx and sy, which are multiplied to the original vertex coordinate positions (x,y): x' = x * sx, y' = y * s y Alternatively, this scaling can also be specified by the following transformation matrix: sx 0 0 0 s 0 y 0 0 1 Then we can rewrite the formula as: x' sx 0 0 x y' = 0 s 0 y y 1 0 01 1 For example, to scale a triange with respect to the origin, with vertices at original coordinates (10,20), (10,10), (20,10) by sx=2, sy=1.5, we compute as followings: Scaling of vertex (10,20): x' 2 0 0 10 2 *10 0 * 20 0 *1 20 y' = 0 1.5 0 20 = 0 *10 1.5 * 20 0 *1 = 30 1 0 0 1 1 0 *10 0 * 20 1*1 1 3 14 Scaling of vertex (10,10): x' 2 0 0 10 2 *10 0 *10 0 *1 20 y' = 0 1.5 0 10 = 0 *10 1.5 *10 0 *1 = 15 1 0 0 1 1 0 *10 0 *10 1*1 1 Scaling of vertex (20,10): x' 2 0 0 20 2 * 20 0 *10 0 *1 40 y' = 0 1.5 0 10 = 0 * 20 1.5 *10 0 *1 = 15 1 0 01 1 0 * 20 0 *10 1*1 1 The resultant coordinates of the triangle vertices are (20,30), (20,15), and (40,15) respectively. Exercise: Scale a triange with vertices at original coordinates (10,25), (5,10), (20,10) by sx=1.5, sy=2, with respect to the origin. Roughly plot the original and resultant triangles. Concatenation Properties of Composite Matrix I. Matrix multiplication is associative: A·B·C = (A·B) ·C = A·(B·C) Therefore, we can evaluate matrix products using these associative grouping. For example, we have a triangle, we want to rotate it with the matrix B, then we translate it with matrix A. Then, for a vertex of that triangle represented as C, we compute its transformation as: C'=A·(B·C) But we can also change the computation method as: C' = (A·B)·C The advantage of computing it using C' = (A·B)·C instead of C'=A·(B·C) is that, for computing the 3 vertices of the triangle, C1, C2, C 3, the computation time is shortened: Using C'=A·(B·C): 1. compute B · C1 and put the result into I1 2. compute A · I1 and put the result into C1' 3. compute B · C2 and put the result into I2 4. compute A · I2 and put the result into C2' 5. compute B · C3 and put the result into I3 6. compute A · I3 and put the result into C3' Using C' = (A·B)·C: - compute A · B and put the result into M - compute M · C1 and put the result into C1' - compute M · C2 and put the result into C2' - compute M · C3 and put the result into C3' 4 15  Example: Rotate a triangle with vertices (10,20), (10,10), (20,10) about the origin by 30 degrees and then translate it by tx=5, ty=10, We compute the rotation matrix: cos 30 sin 30 0 0.866 0.5 0 B = sin 30 cos 30 0 = 0.5 0.866 0 0 0 1 0 0 1 And we compute the translation matrix: 1 0 5 A= 0 1 10 0 0 1 Then, we compute M=A·B 1 0 5 0.866 0.5 0 M= 0 1 10 · 0.5 0.866 0 0 0 1 0 0 1 1* 0.866 0 * 0.5 5 * 0 1* 0.5 0 * 0.866 5 * 0 1* 0 0 * 0 5 *1 M= 0 * 0.866 1* 0.5 10 * 0 0 * 0.5 1* 0.866 10 * 0 0 * 0 1* 0 10 *1 0 * 0.866 0 * 0.5 1* 0 0 * 0.5 0 * 0.866 1* 0 0 * 0 0 * 0 1*1 0.866 0.5 5 M= 0.5 0.866 10 0 0 1 Then, we compute the transformations of the 3 vertices: Transformation of vertex (10,20): x' 0.866 0.5 5 10 0.866 *10 ( 0.5) * 20 5 *1 3.66 y' = 0.5 0.866 10 20 = 0.5 *10 0.866 * 20 10 *1 = 32.32 1 0 0 1 1 0 *10 0 * 20 1*1 1 Transformation of vertex (10,10): x' 0.866 0.5 5 10 0.866 *10 ( 0.5) *10 5 *1 8.66 y' = 0.5 0.866 10 10 = 0.5 *10 0.866 *10 10 *1 = 23.66 1 0 0 1 1 0 *10 0 *10 1*1 1 5 16 Transformation of vertex (20,10): x' 0.866 0.5 5 20 0.866 * 20 ( 0.5) *10 5 *1 17.32 y' = 0.5 0.866 10 10 = 0.5 * 20 0.866 *10 10 *1 = 28.66 1 0 0 1 1 0 * 20 0 *10 1*1 1 The resultant coordinates of the triangle vertices are (3.66,32.32), (8.66,23.66), and (17.32,28.66) respectively. II. Matrix multiplication may not be commutative: A·B may not equal to B·A This means that if we want to translate and rotate an object, we must be careful about the order in which the composite matrix is evaluated. Using the previous example, if you compute C' = (A·B)·C, you are rotating the triangle with B first, then translate it with A, but if you compute C' = (B·A)·C, you are translating it with A first, then rotate it with B. The result is different. Exercise: Translate a triangle with vertices (10,20), (10,10), (20,10) by t x=5, ty=10 and then rotate it about the origin by 30 degrees. Compare the result with the one obtained previously: (3.66,32.32), (8.66,23.66), and (17.32,28.66) by plotting the original triangle together with these 2 results. Composite Transformation Matrix Translations By common sense, if we translate a shape with 2 successive translation vectors: (t x1, ty1) and (tx2, ty2), it is equal to a single translation of (t x1+ tx2, ty1+ t y2). This additive property can be demonstrated by composite transformation matrix: 1 0 t x1 1 0 tx2 1*1 0 * 0 t x1 * 0 1* 0 0 *1 t x1 * 0 1* t x 2 0 * t y 2 t x1 *1 0 t 0 1t 1 y1 · y2 = 0 *1 1* 0 t y1 * 0 0 * 0 1*1 t y1 *0 0 * t x 2 1* t y 2 t y1 *1 0 0 1 0 0 1 0 *1 0 * 0 1* 0 0 * 0 0 *1 1* 0 0 * t x 2 0 * tu 2 1*1 1 0 t x1 t x 2 01 t t = y1 y2 0 0 1 This demonstrates that 2 successive translations are additive. 6 17 Rotations By common sense, if we rotate a shape with 2 successive rotation angles: ? and a, about the origin, it is equal to rotating the shape once by an angle ? + a about the origin. Similarly, this additive property can be demonstrated by composite transformation matrix: cos sin 0 cos sin 0 sin cos 0 · sin cos 0 0 0 1 0 0 1 cos cos ( sin ) * sin 0 * 0 cos * ( sin ) ( sin ) * cos 0 * 0 cos * 0 ( sin ) * 0 0 *1 = sin cos cos * sin 0*0 sin * ( sin ) cos * cos 0 *0 sin * 0 cos * 0 0 *1 0 * cos 0 * sin 1* 0 0 * ( sin ) 0 * cos 1* 0 0 * 0 0 * 0 1 *1 cos cos sin sin (cos sin sin cos ) 0 = sin cos cos sin sin sin cos cos 0 0 0 1 cos( ) sin( ) 0 0 cos( ) = sin( ) 0 0 1 This demonstrates that 2 successive rotations are additive. Scalings With Respect to the Origin By common sense, if we scale a shape with 2 successive scaling factor: (s x1, sy1) and (sx2, sy2), with respect to the origin, it is equal to a single scaling of (s x1* sx2, sy1* sy2) with respect to the origin. This multiplicative property can be demonstrated by composite transformation matrix: s x1 0 0 sx2 0 0 0 s 0 · 0 s 0 y1 y2 0 0 1 0 0 1 s x1 * s x 2 0 * 0 0 * 0 s x1 * 0 0 * s y 2 0 * 0 s x1 * 0 0 * 0 0 *1 = 0 * s x 2 s y1 * 0 0 * 0 0 * 0 s y1 * s y 2 0 * 0 0 * 0 s y1 * 0 0 *1 0*s 0 * 0 1* 0 0 *0 0 *s 1* 0 0 * 0 0 * 0 1*1 x2 y2 s x1 * s x 2 0 0 = 0 s * s 0 y1 y2 0 0 1 This demonstrates that 2 successive scalings with respect to the origin are multiplicative. 7 18 General Pivot-Point Rotation Rotation about an arbitrary pivot point is not as simple as rotation about the origin. The procedure of rotation about an arbitrary pivot point is: - Translate the object so that the pivot-point position is moved to the origin. - Rotate the object about the origin. - Translate the object so that the pivot point is returned to its original position. The corresponding composite transformation matrix is: 1 0 xr cos sin 0 1 0 xr y y 0 1 r sin cos 0 0 1 r 0 0 1 0 0 1 0 0 1 cos sin xr 1 0 xr y 0 y = sin cos r 1 r 0 0 1 0 0 1 cos sin x r cos y r sin xr = sin cos x r sin y r cos yr 1 0 0 General Fixed-Point Scaling Scaling with respect to an arbitrary fixed point is not as simple as scaling with respect to the origin. The procedure of scaling with respect to an arbitrary fixed point is: 1. Translate the object so that the fixed point coincides with the origin. 2. Scale the object with respect to the origin. 3. Use the inverse translation of step 1 to return the object to its original position. 8 19 The corresponding composite transformation matrix is: 1 0 xf sx 0 0 1 0 xf sx 0 x f (1 s x ) 0 y 1 yf 0 sy 0 0 1 f = 0 s y yf (1 s y ) 0 0 1 0 0 1 0 0 1 0 0 1 General Scaling Direction Scaling along an arbitrary direction is not as simple as scaling along the x-y axis. The procedure of scaling along and normal to an arbitrary direction (s 1 and s2), with respect to the origin, is: 1. Rotate the object so that the directions for s1 and s2 coincide with the x and y axes respectively. 2. Scale the object with respect to the origin using (s1, s2). 3. Use an opposite rotation to return points to their original orientation. The corresponding composite transformation matrix is: cos( ) sin( ) 0 s1 0 0 cos sin 0 s0 sin( ) cos( ) 0 0 2 sin cos 0 0 0 1 0 0 1 0 0 1 20 Other Transformations Reflection Reflection about the x axis: x' 1 0 0 x y' = 0 1 0 y 1 0 0 1 1 ie. x'=x; y'=-y Reflection about the y axis: x' 10 0 x y' = 0 10 y 1 0 0 1 1 ie. x'=-x; y'=y Flipping both x and y coordinates of a point relative to the origin: x' 10 0 x y' = 0 1 0 y 1 0 01 1 ie. x'=-x; y'=-y Reflection about the diagonal line y=x: x' 0 1 0 x y' = 1 00 y ie.1 x'=y; 0y'=x0 1 1 Reflection about the diagonal line y=-x: x' 0 1 0 x y' = 10 0 y 1 0 0 1 1 ie. x'=-y; y'=-x Shear X- direction shear, with a shearing parameter shx, relative to the x-axis: 21  x' 1 sh x 0 x y' = 0 1 0 y 1 0 0 1 1 ie. x'=x+y*shx; y'=-x Exercise: Think of a y-direction shear, with a shearing parameter shy, relative to the y-axis. Transformation Between 2 Cartesian Systems For modelling and design applications, individual objects may be defined in their own local Cartesian References. The local coordinates must then be transformed to position the objects within the overall scene coordinate system. Suppose we want to transform object descriptions from the xy system to the x'y' system: The composite transformation is: cos( ) sin( ) xr 1 0 x0 y 0 y sin( ) cos( ) r 1 0 0 0 1 0 0 1 22  Part-II,UNIT -2 2-Dimensional viewing Images on the Screen All objects in the real world have size. We use a unit of measure to describe both the size of an object as well as the location of the object in the real world. For example, meters can be used to specify both size and distance. When showing an image of an object on the screen, we use a screen coordinate system that defines the location of the object in the same relative position as in the real world. After we select the screen coordinate system, we change the picture to display interior screen that means change it into screen coordinate system. 4.1.1 Windows and Clipping The world coordinate system is used to define the position of objects in the natural world. This system does not depend on the screen coordinate system , so the interval of number can be anything(positive, negative or decimal). Sometimes the complete picture of object in the world coordinate system is too large and complicate to clearly show on the screen, and we need to show only some part of the object. The capability that show some part of object internal a specify window is called windowing and a rectangular region in a world coordinate system is called window. Before going into clipping, you should understand the differences between window and a viewport. A Window is a rectangular region in the world coordinate system. This is the coordinate system used to locate an object in the natural world. The world coordinate system does not depend on a display device, so the units of measure can be positive, negative or decimal numbers. A Viewport is the section of the screen where the images encompassed by the window on the world coordinate system will be drawn. A coordinate transformation is required to display the image, encompassed by the window, in the viewport. The viewport uses the screen coordiante system so this transformation is from the world coordinate system to the screen coordinate system. 23 When a window is "placed" on the world, only certain objects and parts of objects can be seen. Points and lines which are outside the window are "cut off" from view. This process of "cutting off" parts of the image of the world is called Clipping. In clipping, we examine each line to determine whether or not it is completely inside the window, completely outside the window, or crosses a window boundary. If inside the window, the line is displayed. If outside the window,the lines and points are not displayed. If a line crosses the boundary, we must determine the point of intersection and display only the part which lies inside the window. Cohen-Sutherland Line Clipping The Cohen-Sutherland line clipping algorithm quickly detects and dispenses with two common and trivial cases. To clip a line, we need to consider only its endpoints. If both endpoints of a line lie inside the window, the entire line lies inside the window. It is trivially accepted and needs no clipping. On the other hand, if both endpoints of a line lie entirely to one side of the window, the line must lie entirely outside of the window. It is trivially and needs to be neither clipped nor displayed. Inside-Outside Window Codes To determine whether endpoints are inside or outside a window, the algorithm sets up a half- space code for each endpoint. Each edge of the window defines an infinite line that divides the whole space into two half-spaces, the inside half-space and the outside half-space, as shown below. 24 As you proceed around the window, extending each edge and defining an inside half-space and an outside half-space, nine regions are created - the eight "outside" regions and the one "inside" region. Each of the nine regions associated with the window is assigned a 4-bit code to identify the region. Each bit in the code is set to either a 1(true) or a 0(false). If the region is to the left of the window, the first bit of the code is set to 1. If the region is to the top of the window, the second bit of the code is set to 1. If to the right, the third bit is set, and if to the bottom, the fourth bit is set. The 4 bits in the code then identify each of the nine regions as shown below. For any endpoint ( x , y ) of a line, the code can be determined that identifies which region the endpoint lies. The code's bits are set according to the following conditions: The sequence for reading the codes' bits is LRBT (Left, Right, Bottom, Top). Once the codes for each endpoint of a line are determined, the logical AND operation of the codes determines if the line is completely outside of the window. If the logical AND of the endpoint codes is not zero, the line can be trivially rejected. For example, if an endpoint had a code of 1001 while the other endpoint had a code of 1010, the logical AND would be 1000 which indicates the line segment lies outside of the window. On the other hand, if the endpoints had codes of 1001 and 0110, the logical AND would be 0000, and the line could not be trivially rejected. The logical OR of the endpoint codes determines if the line is completely inside the window. If the logical OR is zero, the line can be trivially accepted. For example, if the endpoint codes are 0000 and 0000, the logical OR is 0000 - the line can be trivially accepted. If the endpoint codes are 0000 and 0110, the logical OR is 0110 and the line cannot be trivially accepted. Algorithm The Cohen-Sutherland algorithm uses a divide-and-conquer strategy. The line segment's endpoints are tested to see if the line can be trivially accepted or rejected. If the line cannot be trivally accepted or rejected, an intersection of the line with a window edge is determined and the trivial reject/accept test is repeated. This process is continued until the line is accepted. 25 To perform the trivial acceptance and rejection tests, we extend the edges of the window to divide the plane of the window into the nine regions. Each end point of the line segment is then assigned the code of the region in which it lies. 1. Given a line segment with endpoint and 2. Compute the 4-bit codes for each endpoint. If both codes are 0000,(bitwise OR of the codes yields 0000 ) line lies completely inside the window: pass the endpoints to the draw routine. If both codes have a 1 in the same bit position (bitwise AND of the codes is not 0000), the line lies outside the window. It can be trivially rejected. 3. If a line cannot be trivially accepted or rejected, at least one of the two endpoints must lie outside the window and the line segment crosses a window edge. This line must be clipped at the window edge before being passed to the drawing routine. 4. Examine one of the endpoints, say. Read 's 4-bit code in order: Left- to-Right, Bottom-to-Top. 5. When a set bit (1) is found, compute the intersection I of the corresponding window edge with the line from to. Replace with I and repeat the algorithm. Liang-Barsky Line Clipping The ideas for clipping line of Liang-Barsky and Cyrus-Beck are the same. The only difference is Liang-Barsky algorithm has been optimized for an upright rectangular clip window. So we will study only the idea of Liang-Barsky. Liang and Barsky have created an algorithm that uses floating-point arithmetic but finds the appropriate end points with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport. Let P(x1,y1) , Q(x2,y2)be the line which we want to study. The parametric equation of the line segment from gives x-values and y-values for every point in terms of a parameter that ranges from 0 to 1. The equations are 26  and We can see that when t = 0, the point computed is P(x1,y1); and when t = 1, the point computed is Q(x2,y2). Algorithm 1. Set and 2. Calculate the values of tL, tR, tT, and tB (tvalues). o if or ignore it and go to the next edge o otherwise classify the tvalue as entering or exiting value (using inner product to classify) o if t is entering value set ; if t is exiting value set 3. If then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax, y1 + dy*tmax) 4. If the line crosses over the window, you will see (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax, y1 + dy*tmax) are intersection between line and edge. Sutherland - Hodgman Polygon Clipping The Sutherland - Hodgman algorithm performs a clipping of a polygon against each window edge in turn. It accepts an ordered sequence of verices v1, v2, v3,..., vn and puts out a set of vertices defining the clipped polygon. This figure represents a polygon (the large, solid, upward pointing arrow) before clipping has occurred. The following figures show how this algorithm works at each edge, clipping the polygon. 27  a. Clipping against the left side of the clip window. b. Clipping against the top side of the clip window. c. Clipping against the right side of the clip window. d. Clipping against the bottom side of the clip window. Four Types of Edges As the algorithm goes around the edges of the window, clipping the polygon, it encounters four types of edges. All four edge types are illustrated by the polygon in the following figure. For each edge type, zero, one, or two vertices are added to the output list of vertices that define the clipped polygon. The four types of edges are: 1. Edges that are totally inside the clip window. - add the second inside vertex point 2. Edges that are leaving the clip window. - add the intersection point as a vertex 3. Edges that are entirely outside the clip window. - add nothing to the vertex output list 4. Edges that are entering the clip window. - save the intersection and inside points as vertices How To Calculate Intersections Assume that we're clipping a polgon's edge with vertices at (x1,y1) and (x2,y2) against a clip window with vertices at (xmin, ymin) and (xmax,ymax). The location (IX, IY) of the intersection of the edge with the left side of the window is: i. IX = xmin ii. IY = slope*(xmin-x1) + y1, where the slope = (y2-y1)/(x2-x1) The location of the intersection of the edge with the right side of the window is: i. IX = xmax ii. IY = slope*(xmax-x1) + y1, where the slope = (y2-y1)/(x2-x1) The intersection of the polygon's edge with the top side of the window is: i. IX = x1 + (ymax - y1) / slope ii. IY = ymax Finally, the intersection of the edge with the bottom side of the window is: 28  i. IX = x1 + (ymin - y1) / slope ii. IY = ymin Some Problems With This Algorithm 1. This algorithm does not work if the clip window is not convex. 2. If the polygon is not also convex, there may be some dangling edges. 29  UNIT-3 3D Object Representations Methods:  Polygon and Quadric surfaces: For simple Euclidean objects  Spline surfaces and construction: For curved surfaces  Procedural methods: Eg. Fractals, Particle systems  Physically based modeling methods  Octree Encoding  Isosurface displays, Volume rendering, etc. Classification: Boundary Representations (B-reps) eg. Polygon facets and spline patches Space-partitioning representations eg. Octree Representation Objects may also associate with other properties such as mass, volume, so as to determine their response to stress and temperature etc. Polygon Surfaces This method simplifies and speeds up the surface rendering and display of objects. For other 3D objection representations, they are often converted into polygon surfaces before rendering. Polygon Mesh - Using a set of connected polygonally bounded planar surfaces to represent an object, which may have curved surfaces or curved edges. - The wireframe display of such object can be displayed quickly to give general indication of the surface structure. - Realistic renderings can be produced by interpolating shading patterns across the polygon surfaces to eliminate or reduce the presence of polygon edge boundaries. Polygon Tables This is the specification of polygon surfaces using vertex coordinates and other attributes: 1. Geometric data table: vertices, edges, and polygon surfaces. 2. Attribute table: eg. Degree of transparency and surface reflectivity etc. Some consistency checks of the geometric data table: 30  Every vertex is listed as an endpoint for at least 2 edges  Every edge is part of at least one polygon  Every polygon is closed Plane equation and visible points Consider a cube, each of the 6 planes has 2 sides: inside face and outside face. For each plane (in a right-handed coordinate system), if we look at its surface and take 3 points in counter-clockwise direction: (x1,y1), (x2,y2), and (x3,y3), we can compute 4 values: A,B,C,D as 1 y1 z1 x1 1 z1 x1 y1 1 x1 y1 z1 D= A = 1 y2 z2 B = x2 1 z2 C = x2 y2 1 - x2 y2 z2 1 y3 z3 x3 1 z3 x3 y3 1 x3 y3 z3 Then, the plane equation at the form: Ax+By+Cz+D=0 has the property that: If we substitute any arbitrary point (x,y) into this equation, then, Ax + By + Cz + D < 0 implies that the point (x,y) is inside the surface, and Ax + By + Cz + D < 1 implies that the point (x,y) is outside the surface. Polygon Meshes Common types of polygon meshes are triangle strip and quadrilateral mesh. Fast hardware-implemented polygon renderers are capable of displaying up to 1,000,000 or more shaded triangles per second, including the application of surface texture and special lighting effects. Curved Surfaces 1. Regular curved surfaces can be generated as - Quadric Surfaces, eg. Sphere, Ellipsoid, or - Superquadrics, eg. Superellipsoids These surfaces can be represented by some simple parametric equations, eg, for ellipsoid: x = rx cos s1 cos s2 , - /2