Saturday, April 27, 2013

Scanline-Area Filling Algorithm

9. program to fill any given polygon using scanline-area filling algorithm.

Exams approaching and it is tough to get someone to explain the code to you.... Here are some comments to understand the code.

Scan-line area filling uses the property of coherence to color the polygon. Scanline coherence means if a point lies inside a polygon then other points lying on the same scanline near to it are also likely to be inside the polygon.

There are various ways to check if a point is inside the polygon or not. If somehow all pixels lying inside are found out then it is just a matter of changing their pixel value to color the polygon.

In this program it uses two arrays le and re denoting left edge and right edge. They span the entire window height(500-array size) and store the position(x value) of the intersection point of the scan line with one of the edges of polygon(either left or right).

Initial values in le array is 500. That of re array is 0. We scan convert individual edges of the polygon and each point on the edge, its x value goes to the correct le or re array.

Finally once le and re arrays are populated we draw a line from the left edge to the right edge in a loop and iterate over the entire window region(all 500 scanlines).

#include<stdio.h>
#include<GL/glut.h>
GLfloat x1,y1,x2,y2,x3,y3,x4,y4;
void edgedetect(GLfloat x1,GLfloat y1,GLfloat x2,GLfloat y2,int *le,int *re)
{
            float mx,x,temp;
            int i;
            if((y2-y1)<0)    // if second point is below first point interchange them
            {
              temp=x1;x1=x2;x2=temp;
              temp=y1;y1=y2;y2=temp;
            }
              if((y2-y1)!=0)      // if denominator is zero we can't find slope
                        mx=(x2-x1)/(y2-y1);
            else
                        mx=x2-x1;    // y2-y1=0 implies line is horizontal
            x=x1;
            for(i=y1;i<y2;i++)        // starting from x1,y1 add slope mx to x
            {                                  // and round it to find the next point on the
                                                // line. For that particular scan line i
                        if(x<le[i])         // insert the x value into either le or re.
                                    le[i]=x; // Initially both le and re will contain same
                                                // value...
                        if(x>re[i])         // in the next time for the other edge
                                    re[i]=x; // either le or re will change
                        x+=mx;            // NOTE: le and re are integer arrays and x
            }                                  // is float so automatic type conversion.
}
void drawpixel(int x,int y)
{
            glColor3f(0.0,1.0,1.0);
            glBegin(GL_POINTS);
            glVertex2i(x,y);
            glEnd();
}
void scanfill(float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4)
{
            int le[500],re[500];
            int i,y;
            for(i=0;i<500;i++)   // initialize le and re array values
            {
                        le[i]=500;
                        re[i]=0;
            }
            edgedetect(x1,y1,x2,y2,le,re);    // call edge detect four times
            edgedetect(x2,y2,x3,y3,le,re);    // once for each edge.
            edgedetect(x3,y3,x4,y4,le,re);
            edgedetect(x4,y4,x1,y1,le,re);
for(y=0;y<500;y++)        // for every scan line with value y
{
           if(le[y]<=re[y])            // refer to le and re arrays to see if a part
                        for(i=le[y]+1;i<re[y];i++) // of the scanline is inside polygon
                                    drawpixel(i,y);       // if so draw a horizontal line from
}                                                              // left edge to right edge
}
void display()
{
            glClear(GL_COLOR_BUFFER_BIT);
            x1=200,y1=200,x2=100,y2=300,x3=200,y3=400,x4=300,y4=300;
            glBegin(GL_LINE_LOOP);       // draw the boundary of the polygon
            glVertex2f(x1,y1);                   // to be filled.
             glVertex2f(x2,y2);
            glVertex2f(x3,y3);
            glVertex2f(x4,y4);
    glEnd();
   scanfill(x1,y1,x2,y2,x3,y3,x4,y4);       // call scanfill to fill the polygon
   glFlush();   // Usually students fail the lab because they forget glFlush.
}
void myinit()
{
            glClearColor(1.0,1.0,1.0,1.0);
            glColor3f(0.0,0.0,1.0);
            glPointSize(1.0);
            glMatrixMode(GL_PROJECTION);
            glLoadIdentity();
            gluOrtho2D(0.0,499.0,0.0,499.0);
}
int main(int argc,char **argv)
{          glutInit(&argc,argv);
            glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
            glutInitWindowSize(500,500);// 500 height is hardcoded
            glutInitWindowPosition(0,0);
            glutCreateWindow("scanfill");
            glutDisplayFunc(display);
            myinit();
            glutMainLoop();
            return 0;
   }

6 comments:

  1. Plzzz help...y left edge array is 500 and right edge 0

    ReplyDelete
    Replies
    1. The values change during the course of execution. Those are the initial values. When you scan convert you get le to have say 100 and re to have 250 for same index i of say 120.

      Delete
    2. it is depending on
      gluOrtho2D(0.0,499.0,0.0,499.0);
      your program viewing volume start frm 0 to 499
      so le array contains 500 and re contain 5000

      Delete
  2. it is only for figures like quad ....not for n side polygon

    ReplyDelete
    Replies
    1. you can use for any type of polygon...
      but this program works for only quad.
      you u modify the input..

      Delete