Computer Graphics Pollygon filling Techniques.pdf

Pollygon Filling Algorithm

1. Polygon Filling

2. What is polygon ?
•Closedfigurerepresentedbyacollectionofmorethantwo-linesegments
connectedendtoend
•Thelinesegmentiscalledasedgeofthepolygon,whichmakesthepolygon
boundary
•Endpointsofedgesareknownasvertexofthepolygon
2

3. Inside-outside test
3
This method is also known ascounting number method. While
filling an object, we often need to identify whether particular
point is inside the object or outside it.
There are two methods by which we can identify whether
particular point is inside an object or outside.
• Odd-Even Rule
• Nonzero winding number rule

4. Inside-outside test: Odd-Even rule
4
•In this technique, we will count the edge crossing along the line
from any point (x,y) to infinity.
•If the number of interactions is odd, then the point (x,y) is an
interior point
•If the number of interactions is even, then the point (x,y) is an
exterior point.

5. Inside-outside test: Odd-Even rule
When intersection point is vertex then, use following cases:
1.Case A: Edges are monotonically increasing or decreasing : Consider this as only
one edge intersection.
2.Case B: Edge reverse direction: Consider it as two edge intersection.
6

6. Inside-outside test: Non-zero Winding Number Rule
7
1.Give directions to all the edges of the polygon.
2.Draw a scan line from the point to be test towards the left most of X direction.
3.Give the value 1 to all the edges which are going to upward direction and all other -1 as
direction values.
4.Check the edge direction values from which the scan line is passing and sum up them.
5.If the total sum of this direction value is non-zero, then this point to be tested is aninterior
point,otherwise it is anexterior point.

7. Polygon filling: Seed-fill Algorithm
8
Seed-fill algorithms are further classified in two broad categories:
1)Boundary fill: Boundary fill is an algorithm used to fill an area with a specified
colour until the specified boundary colour is encountered
2)Flood fill: Instead of relying on the boundary of the object, it relies on the fill
colour. In other words, it replaces the interior colour of the object with the fill
colour.

8. Polygon filling: Seed-fill Algorithm
9
1. Boundary fill algorithm:
There are two methods for processing neighbouring pixels from a
current test position:
➢Four neighbouring points - are right, left, above, and below – 4
connected
➢ Eight neighbouring points – right, left, above, below and four
diagonal positions – 8 connected
(x, y-1)
(x, y)(x+1, y)
(x, y+1)
(x-1, y)
(x, y-1)
(x, y)(x+1, y)
(x, y+1)
(x-1, y)
(x+1, y+1)
(x+1, y-1)(x-1, y-1)
(x-1, y+1)

9. Polygon Fill algorithm: Boundary Fill Algorithm
10
Four-neighbouring points Algorithm:
Boundaryfill ( x, y, fill_color, boundary_color)
Step 1− Obtain the current pixel attributes such as colour
current = getpixel ( x,y)
Step 2− Perform check and fill appropriate pixels
if( current != boundary_color) && (current != fill_color) then
setpixelcolor(x, y, fill_color)
call Boundaryfill( x+1, y, fill_color, boundary_color)
call Boundaryfill( x-1, y, fill_color, boundary_color)
call Boundaryfill( x, y+1, fill_color, boundary_color)
call Boundaryfill( x, y-1, fill_color, boundary_color)
Step 3− Stop

10. Polygon Fill algorithm: Boundary Fill Algorithm
11
Four-neighbouring points Example

fillcolor=GREEN
boundary_color=RED
current=WHITE
if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
Start Position

11. Polygon Fill algorithm: Boundary fill algorithm
12
Four-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1 3
2
1
3
1
2
fillcolor=GREEN
boundary_color=RED

12. Polygon Fill algorithm: Boundary Fill Algorithm
13
Four-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1 4
2
1
1
2
fillcolor=GREEN
boundary_color=RED
4

13. Polygon Fill algorithm: Boundary fill algorithm
14
Four-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
2
1
1
2
fillcolor=GREEN
boundary_color=RED

14. Polygon Fill algorithm: Boundary fill algorithm
15
Four-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
5
1
15
fillcolor=GREEN
boundary_color=RED

15. Polygon Fill algorithm: Boundary fill algorithm
16
Four-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
1
1
fillcolor=GREEN
boundary_color=RED

16. Polygon Fill algorithm: Boundary fill algorithm
17
Four-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
fillcolor=GREEN
boundary_color=RED

17. Polygon Fill algorithm: Boundary fill algorithm
18
Eight-neighbouring points Algorithm:
Boundaryfill( x, y, fill_color, boundary_color)
Step 1− Obtain the current pixel attributes such as color
current = getpixel( x,y)
Step 2− Perform check and fill appropriate pixels
if( current != boundary_color) && (current != fill_color) then
setpixelcolor(x, y, fill_color)
call Boundaryfill( x+1, y, fill_color, boundary_color)
call Boundaryfill( x-1, y, fill_color, boundary_color)
call Boundaryfill( x, y+1, fill_color, boundary_color)
call Boundaryfill( x, y-1, fill_color, boundary_color)
call Boundaryfill( x+1, y+1, fill_color, boundary_color)
call Boundaryfill( x-1, y-1, fill_color, boundary_color)
call Boundaryfill( x+1, y-1, fill_color, boundary_color)
call Boundaryfill( x-1, y+1, fill_color, boundary_color)
Step 3− Stop

18. Polygon Fill algorithm: Boundary Fill Algorithm
19
Eight-neighbouring points Example

fillcolor=GREEN
boundary_color=RED
current=WHITE
if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
Start Position

19. Polygon Fill algorithm: Boundary fill algorithm
20
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
5
4
3
2
1
3
4
2
fillcolor=GREEN
boundary_color=RED
15

20. Polygon Fill algorithm: Boundary fill algorithm
21
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
6
4
3
2
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
6

21. Polygon Fill algorithm: Boundary fill algorithm
22
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
8
7
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
78

22. Polygon Fill algorithm: Boundary fill algorithm
23
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
12
11
10
9
7
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
7
9
10
11 12

23. Polygon Fill algorithm: Boundary fill algorithm
24
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
11
10
9
7
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
7
9
10
11

24. Polygon Fill algorithm: Boundary fill algorithm
25
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
10
9
7
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
7
9
10

25. Polygon Fill algorithm: Boundary fill algorithm
26
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
9
7
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
7
9

26. Polygon Fill algorithm: Boundary fill algorithm
27
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
7
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1
7

27. Polygon Fill algorithm: Boundary fill algorithm
28
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
4
3
2
1
1
3
4
2
fillcolor=GREEN
boundary_color=RED
1

28. Polygon Fill algorithm: Boundary fill algorithm
29
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
3
2
1
1
32
fillcolor=GREEN
boundary_color=RED
1

29. Polygon Fill algorithm: Boundary fill algorithm
30
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
2
1
1
2
fillcolor=GREEN
boundary_color=RED
1

30. Polygon Fill algorithm: Boundary fill algorithm
31
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
1
fillcolor=GREEN
boundary_color=RED
1

31. Polygon Fill algorithm: Boundary fill algorithm
32
Eight-neighbouring points Example

if( current != boundary_color) && (current != fill_color)
then setpixelcolor(x, y, fill_color)
1
fillcolor=GREEN
boundary_color=RED

32. Polygon Fill algorithm: Flood fill algorithm
33
Flood fill algorithm: Instead of relying on the boundary of the object, it relies on the
fill color. In other words, it replaces the interior color of the object with the fill color.
i)Four-neighbouring Points Algorithm:

Floodfill( x, y, old_color, new_color)
Step 1− Obtain the current pixel attributes such as color
current = getpixel( x,y)
Step 2− Perform check and fill appropriate pixels
if( current == old_color)
setpixelcolor(x, y, new_color)
call Floodfill( x+1, y, old_color, new_color)
call Floodfill( x-1, y, old_color, new_color)
call Floodfill( x, y+1, old_color, new_color)
call Floodfill( x, y-1, old_color, new_color)
Step 3− Stop

33. Polygon Fill algorithm: Flood fill algorithm
34
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Start Position
Four-neighbouring Points Algorithm

34. Polygon Fill algorithm: Flood fill algorithm
35
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Four-neighbouring Points Algorithm

35. Polygon Fill algorithm: Flood fill algorithm
36
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Four-neighbouring Points Algorithm

36. Polygon Fill algorithm: Flood fill algorithm
37
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Four-neighbouring Points Algorithm

37. Polygon Fill algorithm: Flood fill algorithm
38
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Four-neighbouring Points Algorithm

38. Polygon Fill algorithm: Flood fill algorithm
39
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Four-neighbouring Points Algorithm

39. Polygon Fill algorithm: Flood fill algorithm
40
ii) Eight-neighbouring points Algorithm:
Floodfill( x, y, old_color, new_color)
Step 1− Obtain the current pixel attributes such as color
current = getpixel( x,y)
Step 2− Perform check and fill appropriate pixels
if( current == old_color)
setpixelcolor(x, y, fill_color)
call Floodfill( x+1, y, old_color, new_color)
call Floodfill( x-1, y, old_color, new_color)
call Floodfill( x, y+1, old_color, new_color)
call Floodfill( x, y-1, old_color, new_color)
call Boundaryfill( x+1, y+1, old_color, new_color)
call Boundaryfill( x-1, y-1, old_color, new_color)
call Boundaryfill( x+1, y-1, old_color, new_color)
call Boundaryfill( x-1, y+1, old_color, new_color)
Step 3− Stop

40. Polygon Fill algorithm: Flood fill algorithm
41
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Start Position
Eight-neighbouring Points Algorithm

41. Polygon Fill algorithm: Flood fill algorithm
42
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Eight-neighbouring Points Algorithm

42. Polygon Fill algorithm: Flood fill algorithm
43
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Eight-neighbouring Points Algorithm

43. Polygon Fill algorithm: Flood fill algorithm
44
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Eight-neighbouring Points Algorithm

44. Polygon Fill algorithm: Flood fill algorithm
45
old_color= WHITE
new_color = GREEN
if( current == old_color)
setpixelcolor(x, y, fill_color)
Eight-neighbouring Points Algorithm

45. 46
•If some inside pixels are already displayed in fill Colour then
recursive branch terminates leaving further neighborhood
pixels unfilled
•As it uses stack for storing neighborhood nodes, for large
polygons this stack space may be insufficient
Limitations of Seed Fill Algorithm

46. Scan-Line Fill
•To fill the polygon- apply the inside test and then highlight pixels which lie inside
the polygon
•Look only for those pixels at which changes occur.
•Fill the polygon 1 scan line at a time
47

47. Basic Scan Conversion Algorithm
48
•Let P be a polygon with n vertices v
0 to v
n-1 (v
n=v
0)
•Let C be the color to paint this polygon
•Each intersection of straight line with boundary moves into/out-
of the polygon
• Detect (and set) pixels inside the polygon boundary

48. Basic Scan Conversion
49
•1 ScanConvert(Polygon , Color )
• 1.1 For y := 0 to ScreenYMax do
• 1.2 I=Points of intersections of edges of P with line Y=y ;
• 1.3 Sort I in increasing X order and
• 1.4 Fill with color C by making pair of intersection points ;
•2 end ;
How to process the vertex?