Scan Conversion of Polygon Filling Algorithms (Published on dated: Sep 09, 2021)
3.1 Introduction
In the earlier display devices such as refresh display were basically used to draw a line. As we know that, the fundamental aspects of graphic primitives, one of them is a polygon which is basic surface primitive.
Polygon: In geometry, a polygon (/ˈpɒlɪɡɒn/) is a plane figure that is described by a finite number of straight-line segments connected to form a closed polygonal chain or polygonal circuit. The solid plane region, the bounding circuit, or the two together, may be called a polygon.
The segments of a polygonal circuit are called its edges or sides, and the points where two edges meet are the polygon’s vertices (singular: vertex) or corners. The interior of a solid polygon is sometimes called its body. An n-gon is a polygon with n sides; for example, a triangle is a 3-gon.
Some polygons of different kinds: simple convex (fig A & B), simple concave (fig C) and Non-simple (fig D) also known as self-intersecting.
Filling: In terms of Computer Graphics, “Filling is the process of coloring or painting a region or a closed area with colors”. This area can be of any shape and size. For filling polygons with colors, you need to determine the pixels falling on the border of the polygon and those which fall inside the polygon. It is also called Polygon filling as all the closed areas or shapes can be classified as a polygon.
3.2. Representation of Polygon
3.3 Types of Polygon
A polygon is classified into two types. This classification is based on the joining line segment.
(a) Convex — All points on the line segment connecting two points of the Polygon are also inside the Polygon.
(b) Concave — All points on the line segment connecting two points of the Polygon are not inside the Polygon.
3.4 Polygon Filling Algorithms
Filling a polygon is the process of coloring every pixel that comes inside the polygon region. Highlighting all the pixels inside the polygon, two approaches can be used –
1. Scan Line Fill Method
2. Seed Fill Method
(a) Flood Fill Algorithm
(b) Boundary Fill Algorithm
3.4.1 Scan Line Fill Algorithm
This algorithm works by intersecting scan-line with polygon edges and fills the polygon between pairs of intersections. Scan line filling is basically filling up of polygons using horizontal lines or scan-lines. The purpose of the SLPF algorithm is to fill (color) the interior pixels of a polygon given only the vertices of the figure. To understand Scan-line, think of the image being drawn by a single pen starting from bottom left, continuing to the right, plotting only points where there is a point present in the image, and when the line is complete, start from the next line and continue.
This algorithm works by intersecting scan-line with polygon edges and fills the polygon between pairs of intersections.
Special cases of polygon vertices:
- If both lines intersecting at the vertex are on the same side of the scanline, consider it as two points.
- If lines intersecting at the vertex are at opposite sides of the scanline, consider it as only one point.
Algorithm:
Step 1 − Find out the Ymin and Ymax from the given polygon.
Step 2 — From each edge of the polygon from Ymin to Ymax, all the edges are intersected by
Scanline. Each of the points of intersection are named as p0, p1, p2, p3.
Step 3 − Sort the intersection point in the increasing order of X coordinate i.e. (p0, p1), (p1, p2),
and (p2, p3).
Step 4 − Fill all those pair of coordinates that are inside polygons and ignore the alternate pairs.
More explanation of algorithm with example: -
3.4.2. Seed Fill Method
3.4.2.1 FLOOD FILL ALGORITHM
Flood Fill Algorithm is used to fill an area that is not defined within a single colour boundary. This method paints such areas by replacing a specified interior colour instead of searching for a boundary colour value. The idea behind the method is simple, we first replace the colour of current pixel and then recur for the 4 or 8 surrounding points. It is done until the entire figure or shape is
coloured. It is also implemented using –
4 — connected method
8 — connected method
ALGORITHM
1. 4 — connected method
After painting a pixel, the function is called for four neighboring points. These are the pixel positions that are right, left, above and below the current pixel.
void floodFillAlgo (int p, int q, int put_color, int old_color)
{
if (getpixel (p, q) == old_color)
{
putpixel (p, q, put_color);
floodfillAlgo (p+1, q, put_color, old_color);
floodfillAlgo (p-1, q, put_color, old_color);
floodfillAlgo (p, q+1, put_color, old_color);
floodfillAlgo (p, q-1, put_color, old_color);
}
}
2. 8 — connected method
More complex figures are filled using this approach. The pixels to be tested are the 8 neighboring pixels.
void floodFillAlgo (int p, int q, int put_color, int old_color)
{
if (getpixel (p, q) == old_color)
{
putpixel (p, q, put_color);
floodfillAlgo (p+1, q, put_color, old_color);
floodfillAlgo (p-1, q, put_color, old_color);
floodfillAlgo (p, q+1, put_color, old_color);
floodfillAlgo (p, q-1, put_color, old_color);
floodfillAlgo (p+1, q+1, put_color, old_color);
floodfillAlgo (p-1, q-1, put_color, old_color);
floodfillAlgo (p-1, q+1, put_color, old_color);
floodfillAlgo (p+1, q-1, put_color, old_color);
}
}
Example: A rectangle 50 by 50 needs to be coloured red using Flood Fill Algorithm.
3.4.2.2 Boundary Fill Algorithm
Boundary Fill Algorithm is an area filling algorithm. It is used where we must do an interactive painting in computer graphics, where interior points are easily selected. If we have a specified boundary in a single color, then the fill algorithm proceeds pixel by pixel until the boundary color is encountered. The algorithm is recursive in nature.
The Boundary Fill algorithm can be implemented by two means -
(i). 4 connected pixels
(ii). 8 connected pixels
4 — Connected Pixel Algorithm
After painting a pixel, the function is called for four neighboring points. These are the pixel positions that are right, left, above and below the current pixel.
void boundaryFillAlgo (int p, int q, int put_color, int boundary)
{
If (getpixel (p, q) != boundary_color && getpixel (p, q) != put_color)
{
putpixel (p, q, put_color);
boundaryFillAlgo (p + 1, q, put_color, boundary);
boundaryFillAlgo (p, q + 1, put_color, boundary);
boundaryFillAlgo (p — 1, q, put_color, boundary);
boundaryFillAlgo (p, q — 1, put_color, boundary);
}
}
8 — Connected Pixel Algorithm
More complex figures are filled using this approach. The pixels to be tested are the 8 neighboring pixels.
void boundaryFillAlgo (int p, int q, int put_color, int boundary)
{
If (getpixel (p, q) != boundary && getpixel (p, q) != put_color)
{
putpixel (p, q, put_color);
boundaryFillAlgo (p + 1, q, put_color, boundary);
boundaryFillAlgo (p, q + 1, put_color, boundary);
boundaryFillAlgo (p — 1, q, put_color, boundary);
boundaryFillAlgo (p, q — 1, put_color, boundary);
boundaryFillAlgo (p — 1, q — 1, put_color, boundary);
boundaryFillAlgo (p — 1, q + 1, put_color, boundary);
boundaryFillAlgo (p + 1, q — 1, put_color, boundary);
boundaryFillAlgo (p + 1, q + 1, put_color, boundary);
}
}
Example — A circle of radius 25 units needs to be colored yellowish green using Boundary Fill Algorithm.
Comparison between flood fill and boundary fill algorithms
References:
- https://link.springer.com/chapter/10.1007/978-3-642-46514-7_6
- Computer Graphics by AP Godse
- Computer Graphics and Multimedia Techniques By Neetu Agrwal
- Computer Graphics by Dincy Paul
