Chapter - 2 Scan Conversion Algorithm Bal Krishna Nyaupane Assistant Professor Department of Electronics and Computer Engineering Paschimanchal Campus, IOE,TU bkn@[Link]Line Drawing Algorithm = Astraight-line segment in a scene is defined by the coordinate positions for the endpoints of the segment. 1) To display the line on a raster monitor, the graphics system must * first project the endpoints to integer screen coordinates and + determine the nearest pixel positions along the line path between the two endpoints. 2) Then the line color is loaded into the frame buffer at the corresponding pixel coordinates. 3) Reading from the frame buffer, the video controller plots the screen pixels. * This process digitizes the line into a set of discrete integer positions that, in general, only approximates the actual line path.Line Drawing Algorithm = On raster systems, lines are plotted with pixels, and step sizes in the horizontal and vertical directions are constrained by pixel separations. = That is, we must "sample" a line at discrete positions and determine the nearest pixel to the line at sampled position. + Sampling is measuring the values of the function at equal intervals. = Idea: A line is sampled at unit intervals in one coordinate and the corresponding integer values nearest the line path are determined for the other coordinate.Line Drawing AlgorithmDDA Algorithm The Digital differential analyzer (DDA) algorithm is an incremental scan- conversion method. Such an approach is characterized by performing calculations at each step using results from the preceding step. The DDA algorithm is based on using dx or dy. A line is sampled at unit intervals in one coordinate and the corresponding integer values nearest the line path are determined for the other coordinate.DDA AlgorithmDDA AlgorithmDDA AlgorithmDDA AlgorithmDDA AlgorithmDDA Algorithm Limitations of DDA: 1) The rounding operation & floating point arithmetic are time consuming procedures. 2) Round-off error can cause the calculated pixel position to drift away from the true line path for long line segment.Bresenham’s Line Drawing Algorithm The simple DDA has the disadvantages of using two operations that are expensive in computational time: floating point addition and the round function. The Bresenham’s algorithm is another incremental scan conversion algorithm. The big advantage of this algorithm is that it uses only integer calculations. The main Idea of the Bresenham’s line drawing algorithm ( for slope greater than equal to 1): Move across the x-axis in unit intervals and at each step choose between two different y coordinates. The Bresenham’s line algorithm has the following advantages: + An fast incremental algorithm * Uses only integer calculationsBresenham’s Line Drawing AlgorithmBresenham’s Line Drawing AlgorithmBresenham’s Line Drawing AlgorithmBresenham’s Line Drawing AlgorithmBresenham’s Line Drawing AlgorithmBresenham’s Line Drawing AlgorithmBresenham’s Line Drawing AlgorithmCircle Generating AlgorithmSymmetry of CircleMidpoint Circle AlgorithmMidpoint Circle AlgorithmMidpoint Circle Algorithm .Midpoint Circle AlgorithmMidpoint Circle AlgorithmMidpoint Circle AlgorithmMidpoint Circle AlgorithmMidpoint Circle AlgorithmEllipse Generating AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmMidpoint Ellipse AlgorithmArea FillingArea Filling: Introduction = A polyline is a chain of connected line segments. = It is specified by giving the vertices (nodes) PO, P1, P2, ... and so on. = The first vertex is called the initial or starting point and the last vertex is called the final or terminal point. Po Starting P, Py point Py Pe Po fe Pe Py Terminal point Ps (2) Potyline () PolygonTypes of Polygons = The classification of polygons is based on where the line segment joining any two points within the polygon is going to lies. = There are two types of polygons: — Convex polygon: A convex polygon is a polygon in which the line segment joining any two points within the polygon lies completely inside the polygon. — Concave polygon: A concave polygon is a polygon in which line segment joining ar polygon. o,Fill Area Algorithms = Given the edges defining a polygon, and a color for the polygon, we need to fill all the pixels inside the polygon. = Different algorithms: —Scan-line fill Algorithm — Boundary fill Algorithm — Flood fill Algorithm —Inside-outside testScan-line fill Algorithm = Basic Concept: Scan line polygon filling algorithm is used for solid color filling in polygons.Scan-line fill Algorithm = For scan line polygon filling there are three steps to perform in the following order: 1) Find the intersections of the scan line with all edges of the polygon. 2) Sort the intersections by increasing X-coordinate i.e. from left to right. 3) Make pairs of the intersections and fill in color within all the pixels inside the pair.Scan-line fill Algorithm = Special cases: — Some scan line intersections at polygon vertices require special handling. — Ascan line passing through a vertex intersects two polygon edges at that position, adding two points to the list of intersections for the scan line. yeayis 2A1 sean line y" oN A) P| sean line y x-axis 2 4 68 10121416 18 202.Scan-line fill Algorithm In this example Scan line y and Scan line y" both pass through an vertex or an edge endpoint. Now in case of scan line y’ the scan line is intersecting 4 edges i.e. even number of edges anc Also passing through a vertex/endpoint. ALSO both the edges that are connected to the vertex are on SAME SIDE, of the scan line. SO we need to count the vertex/endpoint TWICE so that we can make pairs of intersection points (8,12) & (12,14). Now in case of scan line y, the scan line is intersecting with 5 different edges i.e. ODD NUMBER and also passing through a vertex/endpoint. SO in this case we need to do some extra processing, i.e. we need to check if the 2 edges at the endpoint through which the scan line is passing are they on opposite sides or on same sides? In case of scan line y° they are on same sides and in case of scan line y both edges at the vertex are on opposite sides. SO Now we COUNT THE VERTEX AS A SINGLE INTERSECTION POINT. Now we just need to sort the intersection points and make pairs of them and fill all pixels which lie inside the pair.Boundary fill Algorithm = In Boundary filling algorithm starts at a point inside a region and paint the interior outward the boundary. = If the boundary is specified in a single color, the fill algorithm proceeds outward pixel by until the boundary color is reached. = A boundary-fill procedure accepts as input the co-ordinates of an interior point (x, y), a fill color, and a boundary color. = Starting from (x, y), the procedure tests neighboring positions to determine whether they are of boundary color. If not, they are painted with the fill color, and their neighbors are tested. = This process continues until all pixels up to the boundary color areaBoundary fill Algorithm = Two methods of implementation —4- Connected if they are adjacent horizontally and vertically. —8- Connected if they adjacent horizontally, vertically and diagonally. (x-1,y-1)] (x-1,y) fx-1,y+1)] (x.y+1) (x ye) — cy) POcy*1) (x+1,y-1)] (x+4,y) [et y41 4 - Connected 8 - ConnectedBoundary fill Algorithm: 4-connected Procedure = Step 1: First initialize the 4 values namely x,y, fill-color and default color. [ Default color is the default color of the interior pixel] = Step 2:Define the value of the boundary pixel color of boundary color. = Step 3: Now check if the current pixel is default color Repeat Step 4 and Step 5 till the boundary pixels are reached. = Step 4: Change the default color with the fill color at the current pixel. = Step 5: Repeat Step 3 and Step 4 for the neighboring 4-pixels. = Step 6: Stop.Boundary fill Algorithm * Code for 4- connected void boundaryFill4 (int x, int y, int fill, int boundary, int default) { int current; current = getpixel (x, y); if (current != boundary) && (current = default)) { setPixel (x, y, fill); boundaryFill4 (x+1, y, fill, default); boundaryFill4 (x-1, y, fill, default); boundaryFill4 (x, y+1, fill, default); boundaryFill4 (x, y-1, fill, default); (ty) }Boundary fill Algorithm = Problems in 4- connected : It cant fill all the pixels. = Solution: 8 - Connected pixel.Boundary fill Algorithm = Code for 8- connected pixel. void boundaryFill8 (int x, int y, int fill, int boundary, int default) { current = getpixel (x. y): if (current! = boun { setPixel (xy. fill): boundaryFills (x+2, y, fill, default); boundaryFilis (x-2, default bowery (x yo i, etout); yea) T Geo) Tot) boundaryFill8 (x, y-2, fill, default); boundaryFills (x+2, +2. fill, default); boundaryFills (x+2, y-1, fill, default); x+1,y-1}] (x+1,y) default); default); ry) && (current = default)) (x=1,y-1)] (x,y) fx-t,y*1)} x+yBoundary fill Algorithm: 8-connected pixelsFlood fill Algorithm = Sometimes it is required to fill in an area that is not defined within a single color boundary. In such cases we can fill areas by replacing a specified interior color instead of searching for a boundary color. This approach is called a flood-fill algorithm. = Like boundary fill algorithm, start with some seed and examine the neighboring pixels. Pixels are checked for a specified interior color instead of boundary color and they are replaced by new color. = Using either a 4-connected or 8-connected approach, we can step hrough pixel positions until all interior point hav n fillBoundary fill Algorithm = Problems in 4- connected pixel: It can + fill all the pixels. = Solution: 8 - Connected pixel.Flood fill Algorithm: procedure (x, y, old_colour, new_colour). if ( getpixel (x, y) = old_colour) { putpixel (x, y, new_colour); flood_fill (x + 1, y, old_colour, new_colour); flood_fill (x - 1, y, old_colour, new_colour); flood_fill (x, y + 1, old_colour, new_colour); flood_fill (x, y - 1, old_colour, new_colour); flood_fill (x + 1, y + 1, old_colour, new_colour); flood_fill (x — 1, y - 1, old_colour, new_colour); flood_fill (x + 1, y ~ 1, old_colour, new_colour); flood_fill (x — 1, y + 1, old_colour, new_colour);Boundary fill Algorithm: 8-connected pixelsInside-outside test = Area- filling algorithms and other graphics processes often need to identify interior of objects. /t is not always clear which regions of the xy-plane would be “interior” and which region would be “exterior” to the object. = This is because in the algorithm we can give the vertices of the fill area which does not specify which region is interior and which is exterior. = There are two tests to find out interior or exterior region: 1) Odd-Even rule also known as Odd parity rule 2) Non-zero winding number ruleInside-outside test: Odd-Even rule = Construct a line segment from any position P to a distant point outside the coordinate extents of the object. Now count how many intersections of the line segment with the polygon boundary occur. = If there are an odd number of intersection, then the point P is in the interior. If there are an even number of intersection, then the point P is in the exterior.Inside-outside test: Odd-Even rule = If the intersection point is vertex of the polygon then have to look at the other endpoints of the two segments which meet at this vertex. = If these points lie on the same side of the constructed line, then the point counts as an even number of intersections. = If they lie on opposite sides of the constructed line, then the point is counted as a single intersection.Inside-outside test: Non-zero winding number rule = Like even-odd method, in winding number method we have to picturize a line segment running from outside the polygon to the point P and consider the polygon sides which it crosses. = Here, instead of just counting the intersections, have to give a direction number to each boundary line crossed, and have to sum these direction numbers. = The direction number indicates the direction the polygon edge was drawn relative to the line segment we have constructed for the test.Inside-outside test: Non-zero winding number rule = The direction number indicates the direction the polygon edge was drawn relative to the line segment we have constructed for the test.THANK YOU 299 = References: 1) Donald D. Hearn, M. Pauline Baker - Computer Graphics with OpenGL (3rd Edition)-Prentice Hall (2003)