COMPUTER GRAPHICS - Implement Scan line Polygon Fill Algorithm

 Experiment No.04

Aim : Implement Scan line Polygon Fill Algorithm

Prerequisite:C Language

Outcome: After successful completion of this experiment students will be able to Implement various output and filled area primitive algorithms 

Theory:

Basic Idea: The basic idea is to collect all of the edges (except horizontal edges) that compose the polygon, fill in the figure scan line by scan line using the edges as starting and stopping points.

Main Components:

To successfully fill in a polygon three main components will be used: Edge Buckets, an Edge Table and an Active List. These components will contain an edge’s information, hold all of the edges that compose the figure and maintain the current edges being used to fill in the polygon, respectively.

Edge Buckets

The edge bucket is a structure that holds information about the polygon’s edges. The edge bucket looks different pending on the implementation of the algorithm, in my case it looks like this:

Edge Bucket representation

Here is a breakdown of what each member represent in an edge bucket:

• yMax: Maximum Y position of the edge
• yMin: Minimum Y position of the edge
• x: The current x position along the scan line, initially starting at the same point as the yMin of the edge
• sign: The sign of the edge’s slope ( either -1 or 1)
• dX: The absolute delta x (difference) between the edge’s vertex points
• dY: The absolute delta y (difference) between the edge’s vertex points
• sum: Initiated to zero. Used as the scan lines are being filled to x to the next position

Edge Table (ET)

The ET is a list that contains all of the edges that make up the figure.

Important ET notes:

• When creating edges, the vertices of the edge need to be ordered from left to right
• The edges are maintained in increasing yMin order
• The edges are removed from the ET once the Active List is done processing them
• The algorithm is done filling the polygon once all of the edges are removed from the ET

Active List (AL)

The AL contains the edges that are being processed/used to fill the polygon. Every edge in the AL has a pairing buddy edge, because when filling a scan line, pixels are filled starting from one edge until the buddy edge is encountered.

Important AL notes:

• Edges are pushed into the AL from the Edge Table once an edge’s yMin is equal to the current scan line being processed
• Edges will always be in the AL in pairs
• Edges in the AL are maintained in increasing x order.
• The AL will be re-sorted after every pass

Steps:

Now that we have the main components covered, lets go over the SLPF algorithm in more detailed steps.

~General assumptions~

• The user has access to a method that can set the color of individual pixels. You will see that I simply call the setPixel() method whenever I fill in a pixel.
• The vertices of the given shape are listed in order around the circumference of the polygon
• This one is important, otherwise the polygons will not be drawn properly

Here are the steps:

1. Create ET

    1. Process the vertices list in pairs, start with [numOfVertices-1] and [0].

    2. For each vertex pair, create an edge bucket

2. Sort ET by yMin

3. Process the ET

    1. Start on the scan line equal to theyMin of the first edge in the ET

    2. While the ET contains edges

        1. Check if any edges in the AL need to be removes (when yMax == current scan line)

            1. If an edge is removed from the AL, remove the associated the Edge Bucket from the Edge Table.

        2. If any edges have ayMin == current scan line, add them to the AL

        3. Sort the edges in AL by X

        4. Fill in the scan line between pairs of edges in AL

        5. Increment current scan line

        6. Increment all the X's in the AL edges based on their slope

            1. If the edge's slope is vertical, the bucket's x member is NOT incremented.

Procedure:

Scan Line Polygon Fill Algorithm:

1. Set up edge table from vertex list; determine range of scanlines spanning polygon (miny, maxy)

2. Preprocess edges with nonlocal max/min endpoints

 3. Set up activation table (bin sort) 

4. For each scanline spanned by polygon: – 

Add new active edges to AEL using activation table –

 Sort active edge list on x – Fill between alternate pairs of points (x,y) in order of sorted active edges – 

For each edge e in active edge list: If (y != ymax[e]) 

Compute & store new x (x+=1/m)

 Else 

Delete edge e from the active edge list

Code : 

#include <stdio.h>

#include <conio.h>

#include <graphics.h>

main()

{

int n,i,j,k,gd,gm,dy,dx;

int x,y,temp;

int a[20][2],xi[20];

float slope[20];

clrscr();

printf("\n\n\tEnter the no. of edges of polygon : ");

scanf("%d",&n);

printf("\n\n\tEnter the cordinates of polygon :\n\n\n ");

for(i=0;i<n;i++)

{

printf("\tX%d Y%d : ",i,i);

scanf("%d %d",&a[i][0],&a[i][1]);

}

a[n][0]=a[0][0];

a[n][1]=a[0][1];

detectgraph(&gd,&gm);

initgraph(&gd,&gm,"c:\\tc\\bgi");

/*- draw polygon -*/

for(i=0;i<n;i++) 

{

line(a[i][0],a[i][1],a[i+1][0],a[i+1][1]);

}

getch();

for(i=0;i<n;i++)

{

dy=a[i+1][1]-a[i][1];

dx=a[i+1][0]-a[i][0];

if(dy==0) slope[i]=1.0;

if(dx==0) slope[i]=0.0;

if((dy!=0)&&(dx!=0)) /*- calculate inverse slope -*/ 

{

slope[i]=(float) dx/dy;

}

}

for(y=0;y< 480;y++)

{

k=0;

for(i=0;i<n;i++)

{

if( ((a[i][1]<=y)&&(a[i+1][1]>y))||

((a[i][1]>y)&&(a[i+1][1]<=y)))

{

xi[k]=(int)(a[i][0]+slope[i]*(y-a[i][1]));

k++;

}

}

for(j=0;j<k-1;j++) /*- Arrange x-intersections in order -*/

for(i=0;i<k-1;i++)

{

if(xi[i]>xi[i+1])

{

temp=xi[i];

xi[i]=xi[i+1];

xi[i+1]=temp;

}

}

setcolor(35);

for(i=0;i<k;i+=2)

{

line(xi[i],y,xi[i+1]+1,y);

getch();

}

}

}

Output : 

Conclusion:   

In this experiment we learnt the scanline polygon fill algorithm, which makes it easy to draw a colour filled polygon by entering the desired coordinates.

Question of Curiosity:

Q.1] What are advantages and disadvantages of scan line fill agorithm?

Ans : It takes advantage of coherence resulting in fast algorithm.

It does require as much storage as depth buffer.

It only draws visible pixels.

This algorithm is common in software.

Q.2] What is an Active Edge List in the Scan Line Algorithm?

Ans : Active Edge List contain edges a given scan line intersects during its sweep. The active edge list should be sorted in increasing order of x. The Active Edge List is dynamic, growing and shrinking.