Create Presentation
Download Presentation

Download Presentation
## Viewing and solid area scan conversion

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Introduction**• We have used variety of transformations like scaling, rotation and reflection that can be used to generate variety of different views of a single picture. • Most of the times, we might be interested in northern region or southern region only, in such a situation we need a method to display only those portions of the drawing which are of immediate interest.**A world coordinate area selected for display is called as a**window. • The process of selecting and viewing the picture is called windowing. • A view is what can be seen. • Portion that are not of interest must not be visible. The technique to do so is called clipping. • A clipping refers to removing a part of scene which are not of interest. • Window defines what is to be viewed. clipping means what to omit. View port defines where it is to be displayed.**Viewing transformation In 2D**• A picture is stored in the computer’s memory in the world coordinate system(WCS). • When the picture is displayed on the display device, it is measured in physical device coordinate system(PDCS) corresponding to the display device. • Therefore, displaying an image of a picture involves mapping the coordinates of the points and lines that forms the picture into the appropriate physical device coordinate where the image is to be displayed. • The viewing transformation maps picture coordinate in the WCS to display coordinates in physical device coordinate system.**Introduction to Clipping**• Procedure that identifies the portion of the picture that are either inside or outside of a specified region of space is referred to as clipping. • The region against which an object is to be clipped is known as clip window. • A clipping refers to the removal part of a scene where the internal clipping removes parts of a picture outside a given viewing window, while external clipping removes part inside a viewing window.**Clipping algorithm determines which points, lines lie within**a clipping window. • These points, lines are retained for display. • Primitive clipping procedure include point clipping, line clipping and polygon clipping.**Point clipping**• Point clipping algorithm finds the points that are interior to a clipping window. • Any points (X,Y) is said to be in the interior of the clipping windows if it satisfies the following condition • X ≤ X ≥ Y ≥ Y <**Line clipping**• A line clipping is the process of removing lines or portion of lines outside of an area of interest. • Lines which are external to the clipping window are discarded. • Lines which are inside the clipping window are displayed. • Find the intersection point if it intersects the edges. • For line clipping we make use of Cohen-Sutherland Line Clipping Algorithm.**Intersection of lines with the edges**• For intersecting edges find out the intersecting points. • This will divide the line into different sections. • Check each section of line against the clipping window. • Discard the section if it is outside the window.**Cohen-Sutherland Line Clipping Algorithm**• This algorithm divides a plane in nine region by four straight lines. • The middle region is a rectangular window with each point in the plane. • The algorithm extends window boundary to define nine regions: top-left, top-center, top-right, center-left, center, center-right, bottom-left, bottom-center, bottom-right**Cohen-Sutherland Line Clipping**• Uses a 4 digit code to indicate which of the nine region contains the end points of the line. • These codes identifies the location of the point relative to the boundaries of rectangle • Each region is allocated a Region Code (consisting of 4 Bit) which is found based on following conditions: • Set the bit from right: • Set Bit 1: If the endpoint is to the left of window • Set Bit 2 : If the endpoint is to the right of window • Set Bit 3 : If the endpoint is below the window • Set Bit 4 If the endpoint is above the window • The point with code 0000 will lie in viewing region**Bit 1**Bit 4 1001 1000 1010 0001 0000 0010 0101 0100 0110**Cohen-Sutherland Line Clipping (verification conditions)**• Lines that are completely inside the boundaries have a region code of 0000 • Lines that have 1 in the same bit position are completely outside the region so those lines are rejected. • If the result of logical AND operation is not zero then the line is completely outside.**P1**P5 P6 P3 P2 P4**Cohen-Sutherland Line Clipping**• If Code(A) And Code(B) != 0000 then reject A else either it will become completely visible or partially visible • 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 the window. • If the logical AND of the end point is not equal to zero then the line is rejected • The logical OR of the endpoint codes determines if the line is completely inside the window. • If the logical OR is zero then the line is accepted. • If the line cannot be rejected or accepted then an intersection of the line with a window edge is determined and the reject/accept test is repeated. • This process is continued until the line is accepted.**Cohen-Sutherland Line Clipping Algorithm**• Read two end points • Read two corner of the window • Assign region code • Check for visibility • Determine intersection edge • Divide the line segment considering intersection point • Reject the line segment if any one end point of it appears out side the clipping window • Draw the remaining line segment • Stop**Polygon clipping**• Polygon is a chain of connected poly lines. • It is a closed figure bounded by straight lines. • Starting vertex is called as the initial vertex and the last vertex is called as the final vertex. • Types of polygon: • Convex - It is a polygon in which the line segment joining any two points within the polygon lies completely inside the polygon. • Concave – It s a polygon in which the line segment joining any two points within the polygon may not lie completely inside the polygon. • Computer graphics deals with the both types of polygons.**Convex polygon**Concave polygon**Sutherland Hodgeman Polygon Clipping**• This algorithm processes the polygon as a whole against each window edge. • It begins with initial set of polygon vertices and clipping against the left window to produce new set of vertices. • The new set of vertices is clipped against bottom edge, right edge and top edge respectively. • It uses divide and conquer strategy to attack the problem. • First it clips the polygon against the right clipping boundary. • The resulting polygon is clipped against the top boundary. • And then process is repeated for the remaining boundaries. • It works in any order to make sure that all the edges of the clipping polygon are taken sequentially.**Sutherland Hodgeman Polygon Clipping**Case : 1 Case : 2 V1’ V2 If V1 is Outside AND V2 is Inside then Save V1’ and V2 If V1 and V2 are inside then Save V2 V1 V1 V2 Case : 4 Case : 3 If V1 is Inside AND V2 is Outside then Save V1’ V2 If V1 And V2 are Outside then Save nothing V1 V2 V1’ V1**Sutherland Hodgeman Polygon Clipping**• Case 1: • If previous vertex is outside and current vertex is inside the window boundary, then both the intersection points and the current vertex are added to the new vertex list • Case 2: • If both vertex are inside then only the current vertex will be added to the list • Case 3: • If the previous vertex is inside and the current vertex is outside then only the intersection point is added to the list • Case 4: • If both the vertex are outside then intersection point are tested for visibility and then added to the vertex list**Text clipping**• Character or text generation is an interesting activity in computer graphics • These characters can be formed by lines and pixels • Character are defined by a character cell or box • While clipping the character box is compared to the clipping window and pixels are activated only if it inside the clipping window. • Different cases of text and character clipping of the word “CLIPPING”(Example) • All or none text clipping • All or none character clipping • Precise level character clipping**Introduction to solid area scan conversion**• Solid filled area? • Thick lines and colored geometric shapes • Generation of such filled areas requires edges and vertex information • The process of generating solid filled area using edges and vertex information is called as solid area scan conversion**Inside Outside Test / Even Odd Test**• This test is used to detect whether a point is inside or outside the polygon • In this approach a line segment is drawn from infinity to the point which we want to find whether it lies inside or outside the polygon • Now if the line segment makes odd number of intersection with the polygon edge then the point is said to be inside the polygon else it is outside. • Odd number of intersections---point inside the polygon • Even number of intersections---point outside the polygon**Winding number method**• An alternative method for defining a polygon interior point. • Consider a piece of elastic between the point of question and the point on polygon. • Elastic is tied firmly on the point and slides from other side. • If the elastic wounds at least once then the point is inside. • If no net winding then it is outside.**To explain this with the help of even odd test**• Direction numbers are given to each boundary line that is crossed by the line drawn by joining the point in question and the outside point • And then sum these direction numbers. • Starting=above • Ending below • Direction =1**Starting = below**• Ending=above • Direction=-1 • Then find the sum.. • nonzero = inside • Zero=outside**Winding Number Test**Inside Outside Test P Q R P S T**Polygon filling**• Filling is the process of coloring a fixed area or region • Filling algorithm are used to fill in or shade the given regions of a drawing • Algorithm deals with pixel defined region i.e group of pixels with same color.**Seed filling**• The selected point which is completely inside the polygon is called as seed point. • Seed filling algorithms are classified as: • Boundary fill (4-adjacent, 8-adjacent) • Flood fill • Boundary fill is an algorithm used to fill an area with a specified color until the specified boundary color is encountered. • It can be either 4 connected or 8 connected • The algorithm works by starting in a specified point (x, y) filling that point with a specified fill color, if that is not a boundary and recursively continuous with 4 or 8 neighbor.**4-Adjacent pixel**• Pixel has 4 neighbors namely-left, right, top, bottom • Procedure: boundary_fill(x,y, fill_col, b_col) { If(getpixel(x,y)!=b_col && getpixel(x,y)!=fill_col) { putpixel(x,y,fill_col); boundary_fill(x+1,y,fill_col,b_col); boundary_fill(x,y+1,fill_col,b_col); boundary_fill(x-1,y,fill_col,b_col); boundary_fill(x,y-1,fill_col,b_col); } }**8-Adjacent pixel**Pixel has 8 neighbors Neighboring pixels lies horizontally Vertically and diagonally**Boundary_fill(int x, int y, intfill_col, intboundary_col)**{ if(getpixel(x, y) != boundary_col && getpixel(x, y) != fill_col) { putpixel(x, y, fill_col) boundary_fill(x+1, y, fill_col, boundary_col) boundary_fill(x-1, y, fill_col, boundary_col) boundary_fill(x, y+1, fill_col, boundary_col) boundary_fill(x, y-1, fill_col, boundary_col) boundary_fill(x+1, y+1, fill_col, boundary_col) boundary_fill(x+1, y-1, fill_col, boundary_col) boundary_fill(x-1, y+1, fill_col, boundary_col) boundary_fill(x-1, y-1, fill_col, boundary_col) } }**Drawback of boundary fill**• Fills the polygon with unique boundary. • Fails if the polygon has different boundaries**Flood Fill Algorithm**• Sometimes it is required to fill an area that is not defined within a single color boundary. • In such cases we can fill area by replacing a specified interior color instead of searching for boundary color. • This approach is called flood fill. • In this pixel are checked for interior color instead of boundary color and they are replaced by new color. • Using either 4 or 8 connected approach we can step through pixel position until all interior points have been filled**flood_fill(int x, int y, intold_col, intnew_col)**{ if(getpixel(x, y) == old_col) { putpixel(x, y, new_col) flood_fill(x+1, y, old_col, new_col) flood_fill(x-1, y, old_col, new_col) flood_fill(x, y+1, old_col, new_col) flood_fill(x, y-1, old_col, new_col) flood_fill(x+1, y+1, old_col, new_col) flood_fill(x+1, y-1, old_col, new_col) flood_fill(x-1, y+1, old_col, new_col) flood_fill(x-1, y-1, old_col, new_col) } }**Aliasing & Anti-aliasing**• Various forms of distortion resulted from scan conversion is called aliasing. • Anti aliasing: Making text, graphics appear easy to read & pleasant to the eyes. • Way of making the object appear smoother. • Anti-aliasing is often used in games & on graphics card. • It makes the jagged edge to appear smooth by increasing the low resolution to high resolution. • Anti-aliasing does not really smooth the edge it merely fools the eye to see it as a smooth edge**Half toning**• Half toning is a technique for obtaining visual resolution with a minimum number of intensity levels. • Rectangular grid of pixels are treated as single pixel which is done by adding multiple pixels • When a small area is viewed from a large distance, our eye’s averages the fine details and records only the overall details. • This process is used to produce photographs for magazines and books.**Thresholding**• Used to create a binary image(composed of black &white color). • Technique for improving visual resolution of the image. • Select a fixed threshold for each pixel. • If I(x,y)>T then paint the pixel with white color. • Else paint pixel with black color. • Where I(x,y)=Intensity of the image at coordinates(x,y) and T is the threshold value.**Dithering**• Attempt by a computer program to approximate a color from a mixture of other color when the required color is not available. • E.g: • Dithering occurs when the required color for the web page is not supported by the OS. • The browser then replaced the requested color with an approximation composed of two or more other colors it can produce. • Lead to noticeable degradation of the image.