Filled Area Primitives
Polygon is an ordered list of vertices as shown in the following figure. For filling polygons with particular colors, you
need to determine the pixels falling on the border of the polygon and those which fall inside the polygon. In this
chapter, we will see how we can fill polygons using different techniques.
In graphics system we fill polygons or hardwired structure constructed using points, straight-
line segments, curves etc and create the surfaces. The main idea behind the 2D or 3D object filling
procedure is that it provides us more realism on the object of interest.
A. Scan-Line Polygon Fill Algorithm
For each scan line crossing a polygon, the area-fill algorithm locates the intersection points
of the scan line with the polygon edges. These intersection points are then sorted from left to right, and
the corresponding frame-buffer positions between each intersection pair are set to the specified fill color.
But what happens when the scan line passes through the vertex?
At two edge connecting point called the vertex, we count the scan line two to handling the problem for
scan line passing through vertex, but this consideration also may create problem for some instant as shown
in figure.
To handle such problem consider,
a. intersection edges are opposite sides count as 1.
b. intersection edges are same side count as 2
B. Boundary fill algorithm:
Introduction : Boundary Fill Algorithm starts at a pixel inside the polygon to be filled and paints the interior
proceeding outwards towards the boundary. This algorithm works only if the color with which the region has to be
filled and the color of the boundary of the region are different. If the boundary is of one single color, this approach
proceeds outwards pixel by pixel until it hits the boundary of the region.
Boundary Fill Algorithm is recursive in nature. It takes an interior point(x, y), a fill color, and a boundary
color as the input. The algorithm starts by checking the color of (x, y). If
it’s color is not equal to the fill color and the boundary color, then it is
painted with the fill color and the function is called for all the neighbours
of (x, y). If a point is found to be of fill color or of boundary color, the
function does not call its neighbours and returns. This process
continues until all points up to the boundary color for the region have
been tested.
The boundary fill algorithm can be implemented by 4-connected pixels or 8-connected pixels.
The 4- connected method has some demerits which can solve by the 8-connected method.
Demerit of 4-connected?
boundaryFill(intx,y,fill_color, boundary_color){
intcolor;
getpixel(x,y,color)
if(color != boundary_color AND color != fill_color){
setpixel( x,y,fill_color)
boundaryFill( x+1,y,fill_color, boundary_color)
boundaryFill( x,y+1,fill_color, boundary_color)
boundaryFill( x-1,y,fill_color, boundary_color)
boundaryFill( x,y-1,fill_color, boundary_color)
}
}
3.7 Flood-Fill Algorithm
Sometimes we want to fill in an area that is not defined within
a single color boundary. We can 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. We start
from a specified interior point (x, y) and reassign all pixel values
that are currently set to a given interior color with the desired fill
color. If the area we want to paint has more than one interior color,
we can first reassign pixel values so that all interior points have
the same color. Using either a 4 connected or 8-connected
approach, we then step through pixel positions until all interior
points have been repainted.
Void floodFill (int x, y, fill_color, old_color)
{
If(fill_color == old_color){
exit;
}
If (getpixel (x, y) == fill_color){
exit;
If (getpixel (x, y) ==old_color)
{
setpixel (x, y);
setColor (fill_color);
floodFill (x+1, y, fill_color, old_color)
floodFill (x, y+1, fill_color, old_color)
floodFill (x-1, y, fill_color, old_color)
floodFill (x, y-1, fill_color, old_color)
}
}
Note: To display the operation of boundary fill algorithm in raster display screen, the each
pixel filling procedure is left to right in downward manner but not exactly as the algorithm
defined because even if the frame buffer set the value according as the algorithm but
display it raster display procedure.
What is the difference between the boundary fill & flood-fill algorithm.
Write down the pseudo code procedure to show how a flood fill algorithm would
fill the region using four connected definition for region pixel.