Area Filling Algorithm used in computer graphics

area

1. Area fill algorithm Bhanu Dwivedi MRIIRS

2. Types of area fill algorithm Scan line polygon fill algorithm Boundary fill algorithm Flood fill algorithm

3. Scan-line polygon-filling algorithm The horizontal scanning of the polygon from its lowermost to its topmost vertex, Identifying which edges intersect the scan-line, and finally drawing the interior horizontal lines with the specified fill color process.

4. 4 Boundary Fill Algorithm Another approach to area filling is to start at a point inside a region and paint the interior outward toward the boundary. If the boundary is specified in a single color, the fill algorithm processed outward pixel by pixel until the boundary color is encountered. A boundary-fill procedure accepts as input the coordinate of the interior point (x, y) , a fill color , and a boundary color .

5. 5 Boundary Fill Algorithm The following steps illustrate the idea of the recursive boundary-fill algorithm: 1. Start from an interior point. 2. If the current pixel is not already filled and if it is not an edge point, then set the pixel with the fill color, and store its neighboring pixels ( 4 or 8-connected ) in the stack for processing. Store only neighboring pixel that is not already filled and is not an edge point. 3. Select the next pixel from the stack, and continue with step 2 .

6. 6 Order of Pixels The order of pixels that should be added to stack using 4-connected is above, below, left, and right. For 8-connected is above, below, left, right, above-left, above-right, below-left, and below-right.

7. 7 Start Position Boundary Fill Algorithm 4-connected (Example)

8. 8 3 2 1 1 2 3 Boundary Fill Algorithm 4-connected (Example)

9. 9 1 4 2 4 2 1 Boundary Fill Algorithm 4-connected (Example)

10. 10 1 2 2 1 Boundary Fill Algorithm 4-connected (Example)

11. 11 5 1 5 1 Boundary Fill Algorithm 4-connected (Example)

12. 12 1 1 Boundary Fill Algorithm 4-connected (Example)

13. 13 Boundary Fill Algorithm 4-connected (Example)

14. 14 Start Position Boundary Fill Algorithm 8-connected (Example)

15. 15 4 1 5 2 3 5 4 3 2 1 Boundary Fill Algorithm 8-connected (Example)

16. 16 Boundary Fill Algorithm 8-connected (Example) 6 4 1 2 3 6 4 3 2 1

17. 17 Boundary Fill Algorithm 8-connected (Example) 7 8 4 1 2 3 8 7 4 3 2 1

18. 18 Boundary Fill Algorithm 8-connected (Example) 11 9 12 7 10 4 1 2 3 12 11 10 9 7 4 3 2 1

19. 19 Boundary Fill Algorithm 8-connected (Example) 11 9 7 10 4 1 2 3 11 10 9 7 4 3 2 1

20. 20 Boundary Fill Algorithm 8-connected (Example) 9 7 10 4 1 2 3 10 9 7 4 3 2 1

21. 21 Boundary Fill Algorithm 8-connected (Example) 9 7 4 1 2 3 9 7 4 3 2 1

22. 22 Boundary Fill Algorithm 8-connected (Example) 7 4 1 2 3 7 4 3 2 1

23. 23 Boundary Fill Algorithm 8-connected (Example) 4 1 2 3 4 3 2 1

24. 24 Boundary Fill Algorithm 8-connected (Example) 1 2 3 3 2 1

25. 25 Boundary Fill Algorithm 8-connected (Example) 1 2 2 1

26. 26 Boundary Fill Algorithm 8-connected (Example) 1 1

27. 27 Boundary Fill Algorithm 8-connected (Example)

28. 28 Flood Fill Algorithm Sometimes we want to fill in (recolor) an area that is not defined within a single color boundary. We paint such areas by replacing a specified interior color instead of searching for a boundary color value. This approach is called a flood-fill algorithm .

29. void floodFill4 ( int x, int y, int fill, int oldColor ) { if ( getPixel ( x,y ) == oldColor ) { setColor (fill); setPixel ( x,y ); floodFill4 (x+1, y, fill, oldColor ); floodFill4 (x−1, y, fill, oldColor ); floodFill4(x, y+1, fill, oldColor ); floodFill4(x, y−1, fill, oldColor ); } }

30. 2 Dimensional Viewing

31. Viewing is the mechanism to view the selected part of picture on an output device. Basic terms Window :- A world-coordinate area selected for display. defines what is to be viewed Viewport:- An area on a display device to which a window is mapped. defines where it is to be displayed Viewing transformation :- The mapping of a part of a world-coordinate scene to device coordinates.

32. Two-Dimensional Viewing 32

33. 2 Dimensional Viewing transformation Pipeline

34. Modeling Co-ordinates World Co-ordinates Viewing Co-ordinates Normalized Viewing Co-ordinates Device Co-ordinates Construct World Co-ordinate Scene using Modeling Co-ordinate Transformation Construct World Co-ordinates to Viewing Co-ordinates Map Viewing Co-ordinates to Normalized Viewing Co-ordinates using Window Viewport Specification Map Normalized Viewport to Device Co-ordinates

35. Viewing Effects Zooming effects Successively mapping different-sized windows on a fixed-sized viewports. Panning effects Moving a fixed-sized window across the various objects in a scene. Device independent Viewports are typically defined within the unit square (normalized coordinates) 35

36. Viewing Coordinate Reference Frame The reference frame for specifying the world-coordinate window. Viewing-coordinate origin: P = (x , y ) View up vector V : Define the viewing y v direction 36

37. Window-to-Viewport Coordinate Transformation 37

38. To maintain the same relative placement in the viewport as in the window we require following:- xv – xv min xw - xw min xv max – xv min xw max - xw min yv – yv min yw - yw min yv max – yv min yw max – yw min Solving these expressions for the viewport position ( xv,yv ), we have xv = xv min + ( xw - xw min ) Sx yv = yv min + ( yw - yw min ) Sy

39. Where scaling factors Sx and Sy are used to converts the window area into the viewport area. Sx = xvmax – xvmin xwmax – xwmin Sy = yvmax – yvmin ywmax – ywmin Perform Scaling using a fixed point position of ( xw min , yw min ) that scales the window area to the size of the viewport. (ii) Translate the scaled window area to the position of the viewport.