Polygon fill using the scan-line technique is a key method in computer graphics to display solid shapes on a screen. This process involves a systematic scan of the image, analyzing each line for intersections with the edges of the polygon. Subsequently, the area between these intersections is colored in with the specified hue.
Importance of the Scan-Line polygon filling:
Filling polygons is a key process in computer graphics as it is essential for creating lifelike images and displaying shapes visually. The Scan-Line Polygon Filling Algorithm is pivotal in this context, allowing for the accurate and efficient rendering of solid-colored or textured polygons.
Working of the Scan-Line Polygon Filling Algorithm in C
Identify Boundary Lines: Recognize the boundaries of the polygon, depicted as line segments. Every boundary line is specified by its two endpoints.
Arrange the edges in ascending order according to their y-coordinates to establish the sequence of intersection with the scan lines.
Set up Edge Table: Establish an Edge Table to retain details regarding every edge, such as the gradient, x-coordinate of intersection with the ongoing scan line, and additional pertinent characteristics.
Create the Active Edge Table (AET) by beginning with an empty table. As the scanning process moves through each scan line, edges will be added to and removed from the AET according to their intersections.
Iterate over individual scan lines starting from the bottom and moving upwards across the polygon. As you progress through each scan line, make adjustments to the Active Edge Table (AET) by incorporating fresh edges from the Edge Table and eliminating edges that have completed their span.
For every set of neighboring edges within the AET, color the pixels between their x-coordinates on the existing scan line using the designated color.
Update Edge Coordinates: This process involves increasing the x-coordinates of the edges within the Active Edge Table (AET) according to their respective slopes.
Repeat this procedure iteratively until all scan lines have been examined and the complete interior of the polygon has been filled.
Advantages of the Scan-line Filling Algorithm:
There are multiple benefits associated with the Scan-Line Filling Algorithm. Some key advantages of this algorithm include:
- Efficiency:
It effectively handles pixels located on crossing scan lines, minimizing computational burden. This method proves highly efficient when dealing with sizable polygons that require minimal repetitive computations.
- Flexibility:
It can be applied to intricate polygons, irregular shapes, and shapes containing cutouts. This feature is valuable in numerous computer graphics situations.
- Simplicity of Integration:
It presents a simple idea that is easily understandable by developers and designers. It doesn't demand intricate data structures, simplifying the execution phase.
- Handles Different Edge Scenarios:
It effectively manages both parallel and non-parallel edges without any disruptions. It is ideal for polygons with intersecting or identical edges.
- Enables the Inclusion of Internal Characteristics:
It allows for the application of solid colors or textures to the interior spaces, enhancing the realism in computer-generated imagery.
Steps for implementation of Scan-Line Filling Algorithm using ubuntu operating system.
Step 1:
- Begin by launching the terminal application, then proceed to install the freeglut3 library using the command provided below.
Sudo apt-get install freeglut3 freeglut3-dev
To create a new folder with a specific name, such as "javaLogic Practice," you can utilize the following command to generate a directory.
mkdir javaLogic Practiceh
Create a new text document and assign specific names to save the coordinates. Next, access the text file using a text editing program and input the coordinate values. The following commands can be employed for this task:
touch sample.txt
nano sample.txt
Step 3:
- Begin by generating a C file and assigning an appropriate name to it for scripting the scan-line filling algorithm. Subsequently, launch the C file using the text editor and insert the necessary code. Below are the commands at your disposal. In this scenario, we have denoted the C file as 'c'.
touch main.c
nano main.c
Example:
Let's consider a C program that needs to be written in the main.c file.
#include <stdio.h>
#include <math.h>
#include <GL/glut.h>
#define maxHt 800
#define maxWd 600
#define maxVer 10000
FILE *fp;
// Start from lower left corner
typedef struct edgebucket
{
int ymax;
float xofymin;
float slopeinverse;
} EdgeBucket;
typedef struct edgetabletup
{
int countEdgeBucket;
EdgeBucket buckets[maxVer];
} EdgeTableTuple;
EdgeTableTuple EdgeTable[maxHt], ActiveEdgeTuple;
void initEdgeTable()
{
int i;
for (i = 0; i < maxHt; i++)
{
EdgeTable[i].countEdgeBucket = 0;
}
ActiveEdgeTuple.countEdgeBucket = 0;
}
void printTuple(EdgeTableTuple *tup)
{
int j;
if (tup->countEdgeBucket)
printf("\nCount %d-----\n", tup->countEdgeBucket);
for (j = 0; j < tup->countEdgeBucket; j++)
{
printf(" %d+%.2f+%.2f",
tup->buckets[j].ymax, tup->buckets[j].xofymin, tup->buckets[j].slopeinverse);
}
}
void printTable()
{
int i, j;
for (i = 0; i < maxHt; i++)
{
if (EdgeTable[i].countEdgeBucket)
printf("\nScanline %d", i);
printTuple(&EdgeTable[i]);
}
}
void insertionSort(EdgeTableTuple *ett)
{
int i, j;
EdgeBucket temp;
for (i = 1; i < ett->countEdgeBucket; i++)
{
temp.ymax = ett->buckets[i].ymax;
temp.xofymin = ett->buckets[i].xofymin;
temp.slopeinverse = ett->buckets[i].slopeinverse;
j = i - 1;
while ((temp.xofymin < ett->buckets[j].xofymin) && (j >= 0))
{
ett->buckets[j + 1].ymax = ett->buckets[j].ymax;
ett->buckets[j + 1].xofymin = ett->buckets[j].xofymin;
ett->buckets[j + 1].slopeinverse = ett->buckets[j].slopeinverse;
j = j - 1;
}
ett->buckets[j + 1].ymax = temp.ymax;
ett->buckets[j + 1].xofymin = temp.xofymin;
ett->buckets[j + 1].slopeinverse = temp.slopeinverse;
}
}
void storeEdgeInTuple(EdgeTableTuple *receiver, int ym, int xm, float slopInv)
{
(receiver->buckets[(receiver)->countEdgeBucket]).ymax = ym;
(receiver->buckets[(receiver)->countEdgeBucket]).xofymin = (float)xm;
(receiver->buckets[(receiver)->countEdgeBucket]).slopeinverse = slopInv;
insertionSort(receiver);
(receiver->countEdgeBucket)++;
}
void storeEdgeInTable(int x1, int y1, int x2, int y2)
{
float m, minv;
int ymaxTS, xwithyminTS, scanline;
if (x2 == x1)
{
minv = 0.000000;
}
else
{
m = ((float)(y2 - y1)) / ((float)(x2 - x1));
if (y2 == y1)
return;
minv = (float)1.0 / m;
printf("\nSlope string for %d %d & %d %d: %f", x1, y1, x2, y2, minv);
}
if (y1 > y2)
{
scanline = y2;
ymaxTS = y1;
xwithyminTS = x2;
}
else
{
scanline = y1;
ymaxTS = y2;
xwithyminTS = x1;
}
storeEdgeInTuple(&EdgeTable[scanline], ymaxTS, xwithyminTS, minv);
}
void removeEdgeByYmax(EdgeTableTuple *Tup, int yy)
{
int i, j;
for (i = 0; i < Tup->countEdgeBucket; i++)
{
if (Tup->buckets[i].ymax == yy)
{
printf("\nRemoved at %d", yy);
for (j = i; j < Tup->countEdgeBucket - 1; j++)
{
Tup->buckets[j].ymax = Tup->buckets[j + 1].ymax;
Tup->buckets[j].xofymin = Tup->buckets[j + 1].xofymin;
Tup->buckets[j].slopeinverse = Tup->buckets[j + 1].slopeinverse;
}
Tup->countEdgeBucket--;
i--;
}
}
}
void updatexbyslopeinv(EdgeTableTuple *Tup)
{
int i;
for (i = 0; i < Tup->countEdgeBucket; i++)
{
(Tup->buckets[i]).xofymin = (Tup->buckets[i]).xofymin + (Tup->buckets[i]).slopeinverse;
}
}
void ScanlineFill()
{
int i, j, x1, ymax1, x2, ymax2, FillFlag = 0, coordCount;
for (i = 0; i < maxHt; i++)
{
for (j = 0; j < EdgeTable[i].countEdgeBucket; j++)
{
storeEdgeInTuple(&ActiveEdgeTuple, EdgeTable[i].buckets[j].ymax, EdgeTable[i].buckets[j].xofymin,
EdgeTable[i].buckets[j].slopeinverse);
}
printTuple(&ActiveEdgeTuple);
removeEdgeByYmax(&ActiveEdgeTuple, i);
insertionSort(&ActiveEdgeTuple);
printTuple(&ActiveEdgeTuple);
j = 0;
FillFlag = 0;
coordCount = 0;
x1 = 0;
x2 = 0;
ymax1 = 0;
ymax2 = 0;
while (j < ActiveEdgeTuple.countEdgeBucket)
{
if (coordCount % 2 == 0)
{
x1 = (int)(ActiveEdgeTuple.buckets[j].xofymin);
ymax1 = ActiveEdgeTuple.buckets[j].ymax;
if (x1 == x2)
{
if (((x1 == ymax1) && (x2 != ymax2)) || ((x1 != ymax1) && (x2 == ymax2)))
{
x2 = x1;
ymax2 = ymax1;
}
else
{
coordCount++;
}
}
else
{
coordCount++;
}
}
else
{
x2 = (int)ActiveEdgeTuple.buckets[j].xofymin;
ymax2 = ActiveEdgeTuple.buckets[j].ymax;
FillFlag = 0;
// checking for intersection...
if (x1 == x2)
{
if (((x1 == ymax1) && (x2 != ymax2)) || ((x1 != ymax1) && (x2 == ymax2)))
{
x1 = x2;
ymax1 = ymax2;
}
else
{
coordCount++;
FillFlag = 1;
}
}
else
{
coordCount++;
FillFlag = 1;
}
if (FillFlag)
{
glColor3f(0.0f, 0.7f, 0.0f);
glBegin(GL_LINES);
glVertex2i(x1, i);
glVertex2i(x2, i);
glEnd();
glFlush();
}
}
j++;
}
updatexbyslopeinv(&ActiveEdgeTuple);
}
printf("\nScanline filling complete");
}
void myInit(void)
{
glClearColor(1.0, 1.0, 1.0, 0.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0, maxHt, 0, maxWd);
glClear(GL_COLOR_BUFFER_BIT);
}
void drawPolyDino()
{
glColor3f(1.0f, 0.0f, 0.0f);
int count = 0, x1, y1, x2, y2;
rewind(fp);
while (!feof(fp))
{
count++;
if (count > 2)
{
x1 = x2;
y1 = y2;
count = 2;
}
if (count == 1)
{
fscanf(fp, "%d,%d", &x1, &y1);
}
else
{
fscanf(fp, "%d,%d", &x2, &y2);
printf("\n%d,%d", x2, y2);
glBegin(GL_LINES);
glVertex2i(x1, y1);
glVertex2i(x2, y2);
glEnd();
storeEdgeInTable(x1, y1, x2, y2); // storage of edges in edge table.
glFlush();
}
}
}
void drawDino(void)
{
initEdgeTable();
drawPolyDino();
printf("\nTable");
printTable();
ScanlineFill(); // actual calling of scanline filling..
}
void main(int argc, char **argv)
{
fp = fopen("sample.txt", "r");
if (fp == NULL)
{
printf("Could not open file");
return;
}
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize(maxHt, maxWd);
glutInitWindowPosition(100, 150);
glutCreateWindow("Scanline filled dinosaur");
myInit();
glutDisplayFunc(drawDino);
glutMainLoop();
fclose(fp);
}
Commands for executing the above code:
"gcc -o main main.c -lGL -lgLU -lglut -lm"
Then for displaying the output use the below command
"./main.c"
Output:
[Program Output]
Output:
[Program Output]
Explanation:
This C++ script showcases the implementation of the Scanline Polygon Fill Algorithm with the assistance of OpenGL and GLUT. Now, let's dissect the essential elements of this code:
Imports:
The stdio.h, math.h, and GL/glut.h headers are essential C and OpenGL libraries. stdio.h facilitates file handling operations, math.h supports mathematical computations, and GL/glut.h provides OpenGL Utility Toolkit functionalities.
Global Variables:
maxHt, maxWd, maxVer: These constants establish the upper limits for height, width, and the quantity of vertices within the software. They play a crucial role in configuring the OpenGL viewport and handling edge tables.
*FILE fp: This specific file pointer is employed to extract the coordinates of a polygon from a file labeled as "sample.txt".
Structures (EdgeBucket, EdgeTableTuple): These specify the formats for an edge bucket and an edge table tuple. The edge bucket stores details related to a polygon edge, while the edge table tuple oversees a group of edge buckets.
Functions:
InitializeEdgeTable: This function sets up the global array EdgeTable by initializing the number of edge buckets to zero.
DisplayTuple(EdgeTableTuple tuple): This function showcases the details of an edge table tuple, encompassing the highest y-coordinate, x-coordinate of the bottom edge point, and reciprocal of the slope for every edge.
The function printTable displays the complete edge table by iterating over each scanline.
The function insertionSort(EdgeTableTuple) is responsible for arranging a collection of edge buckets in ascending order based on their x-coordinate values.
The function storeEdgeInTuple(...) saves an edge within a specified tuple for an edge table, organizing the buckets according to ymax and xofymin.
The function storeEdgeInTable(...) calculates the reciprocal of the slope and saves the edges in the edge table.
The function removeEdgeByYmax deletes edges from the active edge table where the y-coordinate is equal to ymax.
The function updatexbyslopeinv(...) modifies the x-coordinates of every edge in the active edge table according to the inverse of their slopes.
The function ScanlineFill executes the scanline fill technique by populating lines on every scanline through the utilization of x-coordinate pairs from the active edge table.
The function myInit is responsible for setting up the OpenGL window with a white background and configuring the orthographic projection.
Executing the function drawPolyDino involves reading coordinate data from the file named "PolyDino.txt", drawing line segments accordingly, and saving the edge information into the edge table.
The function drawDino starts by setting up the edge table, then proceeds to execute drawPolyDino, displays the edge table, and carries out the scanline filling process.
main(...): The main function sets up the file pointer, OpenGL window, and display function before entering the GLUT main loop.
Control Flow:
- The program starts by opening the file "PolyDino.txt" to read polygon coordinates.
- The drawDino function is the main driver of the program, initializing the edge table, drawing the polygon, printing the edge table, and performing scanline filling.
- The drawPolyDino function reads coordinates, draws lines, and stores edges in the edge table.
- Scanline filling is achieved by processing each scanline, moving edges from the edge table to the active edge table, and filling lines on the current scanline.
Conclusion:
In summary, the C program applies the Scanline Polygon Fill Algorithm through the utilization of OpenGL and GLUT. This algorithm effectively populates the inside of a polygon by scanning lines and identifying intersections with its edges. This essential computer graphics algorithm showcases adaptability, straightforward implementation, and handling of diverse scenarios. The software relies on conventional C libraries, OpenGL for visual representation, and GLUT for interface management. The program's flow adheres to a coherent process of setup, drawing, and executing scanline filling, highlighting the algorithm's efficiency in displaying filled shapes on a monitor.