Las figuras en una pantalla de computadora se pueden dibujar usando polígonos. Para llenar esas figuras con color, necesitamos desarrollar algún algoritmo. Hay dos algoritmos famosos para este propósito: los algoritmos de relleno de límite y de relleno de línea de exploración.
El relleno de límites requiere mucho procesamiento y, por lo tanto, encuentra pocos problemas en tiempo real. Por lo tanto, la alternativa viable es el llenado de línea de exploración, ya que es de naturaleza muy robusta. Este artículo explica cómo utilizar el algoritmo de relleno Scanline para rellenar colores en una imagen.
Algoritmo de llenado de polígonos de línea de exploración
C
// CPP program to illustrate
// Scanline Polygon fill Algorithm
#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; //max y-coordinate of edge
float xofymin; //x-coordinate of lowest edge point updated only in aet
float slopeinverse;
}EdgeBucket;
typedef struct edgetabletup
{
// the array will give the scanline number
// The edge table (ET) with edges entries sorted
// in increasing y and x of the lower end
int countEdgeBucket; //no. of edgebuckets
EdgeBucket buckets[maxVer];
}EdgeTableTuple;
EdgeTableTuple EdgeTable[maxHt], ActiveEdgeTuple;
// Scanline Function
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]);
}
}
/* Function to sort an array using insertion sort*/
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)
{
// both used for edgetable and active edge table..
// The edge tuple sorted in increasing ymax and x of the lower end.
(receiver->buckets[(receiver)->countEdgeBucket]).ymax = ym;
(receiver->buckets[(receiver)->countEdgeBucket]).xofymin = (float)xm;
(receiver->buckets[(receiver)->countEdgeBucket]).slopeinverse = slopInv;
// sort the buckets
insertionSort(receiver);
(receiver->countEdgeBucket)++;
}
void storeEdgeInTable (int x1,int y1, int x2, int y2)
{
float m,minv;
int ymaxTS,xwithyminTS, scanline; //ts stands for to store
if (x2==x1)
{
minv=0.000000;
}
else
{
m = ((float)(y2-y1))/((float)(x2-x1));
// horizontal lines are not stored in edge table
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;
}
// the assignment part is done..now storage..
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()
{
/* Follow the following rules:
1. Horizontal edges: Do not include in edge table
2. Horizontal edges: Drawn either on the bottom or on the top.
3. Vertices: If local max or min, then count twice, else count
once.
4. Either vertices at local minima or at local maxima are drawn.*/
int i, j, x1, ymax1, x2, ymax2, FillFlag = 0, coordCount;
// we will start from scanline 0;
// Repeat until last scanline:
for (i=0; i<maxHt; i++)//4. Increment y by 1 (next scan line)
{
// 1. Move from ET bucket y to the
// AET those edges whose ymin = y (entering edges)
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);
// 2. Remove from AET those edges for
// which y=ymax (not involved in next scan line)
removeEdgeByYmax(&ActiveEdgeTuple, i);
//sort AET (remember: ET is presorted)
insertionSort(&ActiveEdgeTuple);
printTuple(&ActiveEdgeTuple);
//3. Fill lines on scan line y by using pairs of x-coords from AET
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)
{
/* three cases can arrive-
1. lines are towards top of the intersection
2. lines are towards bottom
3. one line is towards top and other is towards bottom
*/
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)
{
/*three cases can arrive-
1. lines are towards top of the intersection
2. lines are towards bottom
3. one line is towards top and other is towards bottom
*/
if (((x1==ymax1)&&(x2!=ymax2))||((x1!=ymax1)&&(x2==ymax2)))
{
x1 = x2;
ymax1 = ymax2;
}
else
{
coordCount++;
FillFlag = 1;
}
}
else
{
coordCount++;
FillFlag = 1;
}
if(FillFlag)
{
//drawing actual lines...
glColor3f(0.0f,0.7f,0.0f);
glBegin(GL_LINES);
glVertex2i(x1,i);
glVertex2i(x2,i);
glEnd();
glFlush();
// printf("\nLine drawn from %d,%d to %d,%d",x1,i,x2,i);
}
}
j++;
}
// 5. For each nonvertical edge remaining in AET, update x for new y
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 ("PolyDino.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);
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA