Scribd
Upload
42 views32 pages

Computer Graphics: Lecture 05-Polygon Filling

The document discusses two algorithms for filling polygons in computer graphics: the scan-line algorithm and the boundary fill algorithm. The scan-line algorithm works by finding the intersections of polygon edges with horizontal scan lines and filling the pixels between intersections. The boundary fill algorithm picks an interior point and recursively fills neighboring pixels of the same color until it hits the polygon boundary. Both 4-connected and 8-connected versions are described for the boundary fill approach.

Uploaded by

devzani nipa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
42 views32 pages

Computer Graphics: Lecture 05-Polygon Filling

The document discusses two algorithms for filling polygons in computer graphics: the scan-line algorithm and the boundary fill algorithm. The scan-line algorithm works by finding the intersections of polygon edges with horizontal scan lines and filling the pixels between intersections. The boundary fill algorithm picks an interior point and recursively fills neighboring pixels of the same color until it hits the polygon boundary. Both 4-connected and 8-connected versions are described for the boundary fill approach.

Uploaded by

devzani nipa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 32

Computer Graphics

Lecture 05- Polygon Filling


Outlines

• Scan-Line Algorithm
• Boundary fill algorithm
Polygons
A polygon is a many-sided planar figure composed of vertices and
edges. A polygon is bounded (finite area) and closed (includes
boundary).

Vertices are represented by points (x,y).

Edges are represented as line segments which connect two points,


(x1,y1) and (x2,y2).

E1
(x1,y1) (x2,y2)

E3 E2

(x3,y3)
Polygons
Scan-Line Algorithm

For each scan-line:


-Find the intersections of the scan line with all edges of the
polygon.
-Sort the intersections by increasing x-coordinate.
-Fill in all pixels between pairs of intersections.

6
For scan-line number 7 the sorted list
of x-coordinates is (1,3,7,9)
4

2 Therefore fill pixels with x-


coordinates 1-3 and 7-9.
2 4 6 8
Scan-Line Algorithm
Y-max a c
b
h i g
u v y z

e f

X-max

Case-1:If scan line passes through vertex Case-2:If scan line passes through vertex
and both the edges that are connected to and both the edges that are connected to
the vertex are on the same side of the the vertex are on the different side of the
scan line, then the vertex should scan line, then the vertex should
considered as 2 intersection points. considered as a single intersection point.
Scan-Line Algorithm
Y-max a c
b
h i g

u z
v y

e f

X-max

If y value is continuously decreasing If y value is decreasing in one edge and


(clockwise) or increasing (anti clockwise) in increasing at another edge then
the two edges that are connected with consider it as two intersection point
samrthen consider it as one intersection
point
Boundary Fill Algorithm

This algorithm picks a point inside the polygon and starts


to fill until it hits the boundary of the object.
Boundary Fill Algorithm (Code)

void boundaryFill4(int x, int y, int fill_color,int boundary_color)


{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill4(x + 1, y, fill_color, boundary_color);
boundaryFill4(x - 1, y, fill_color, boundary_color);
boundaryFill4(x, y + 1, fill_color, boundary_color);
boundaryFill4(x, y - 1, fill_color, boundary_color);
}
Boundary Fill Algorithm

The boundary fill algorithm algorithm can be


implemented by 4-connected pixels or 8-connected pixels.
Boundary Fill Algorithm (Code)
void boundaryFill8(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill8(x + 1, y, fill_color, boundary_color);
boundaryFill8(x, y + 1, fill_color, boundary_color);
boundaryFill8(x - 1, y, fill_color, boundary_color);
boundaryFill8(x, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y + 1, fill_color, boundary_color);
boundaryFill8(x + 1, y - 1, fill_color, boundary_color);
boundaryFill8(x + 1, y + 1, fill_color, boundary_color);
}
}
4-connected (Example)

Start Position
x + 1, y R
x - 1, y L
x, y + 1 T
x, y – 1 B

3
2
1
1
2 3
4
2
1 4
1
2
2
1
1
2
5
5 1
1
1
1
Some region remains unfilled
8-connected (Example)

Start Position
4 1 5
5
2 3
4
3
2
1
6
4 1
6
2 3
4
3
2
1
7 8

8
4 1
7
2 3
4
3
2
1
12
11 9 12
11
7 10
10
9
4 1
7
2 3
4
3
2
1
11 9
11
7 10
10
9
4 1
7
2 3
4
3
2
1
9
7 10
10
9
4 1
7
2 3
4
3
2
1
9
7

9
4 1
7
2 3
4
3
2
1
7

4 1
7
2 3
4
3
2
1
4 1
2 3
4
3
2
1
1
2 3

3
2
1
1
2

2
1
1

You might also like