Computer Graphics Program source codes with full description.

Study of Various C Graphics Functions

Implementation and Using mouse in DOS

Implementation of DDA line algorithm with source code in C/C++.

Implementation of Bresenham Line algorithm with source code in C/C++.

Implementation of Midpoint Line algorithm with source code in C/C++.

Implementation of Bresenham Circle algorithm with source code in C/C++.

Implementation of Mid-point Circle algorithm with source code in C/C++.

Implementation of Mid-point Ellipse algorithm with source code in C/C++.

Implementation of Polygon Filling using Scan Fill with source code in C/C++.

Implementation of Polygon Filling using Flood Fill with source code in C/C++.

Implementation of Polygon Filling using Boundary Fill Algorithms.

Implementation of algorithm of 2D Transformation of an Object with source code in C/C++.

Implementation of Line Clipping using Cohen- Sutherland algorithm with source code in C/C++.

Implementation of Line Clipping using Liang-Barky algorithm with source code in C/C++.

Implementation of Polygon clipping using Sutherland-hodgeman algorithm with source code in C/C++.

Search

Thursday 5 May 2011

Implementation of Midpoint Line algorithm with source code in C/C++.


Description

Given a line segment from leftmost (xo,yo) to rightmost (x1,y1):

y = mx + b
m = ∆y / ∆x = (y1 - yo) / (x1 - xo)
assuming xo,x1,yo,y1 are integers

Assuming 0 <= m <= 1 we start at the leftmost edge of the line, and move right one pixel-column at a time illuminating the pixel either in the current row (the pixel to the PΒ) or the next higher row (the pixel to the PΒ.) as shown in figure.
Can we rewrite the line equation in the form: F(x, y) = ax + by + c = 0

y= (∆y / ∆x) * x + b
0 = (∆y / ∆x) * x - y + b
0 = ∆y * x - ∆x * y + ∆x * b

so a = ∆y b= -∆x c= ∆x*b

F(x,y) = ∆y * x - ∆x * y + ∆x * b will be

F(x,y)=ax + by + c

so for any point (xi,yi) we can plug xi,yi into the above equation and

F(xi,yi) = 0 -> (xi,yi) is on the line
F(xi,yi) > 0 -> (xi,yi) is below the line
F(xi,yi) < 0 -> (xi,yi) is above the line
Given that we have illuminated the pixel at (xk,yk) we will next either illuminate

the pixel to the Pα (xk + 1,yk)
or the pixel to the Pβ (xk + 1,yk+ 1)


 

To decide we look at the Midpoint between the Pα and Pβ pixel and see which side of the midpoint the line falls on.

line above the midpoint -> illuminate the Pα pixel
line below the midpoint -> illuminate the P
β pixel
line exactly on the midpoint -> CHOOSE TO illuminate the P
α pixel
We create a decision variable called d
We plug the Midpoint into the above function for the line and see where the midpoint falls in relation to the line.
d = F(xp +1,yp+1/2)

d > 0 -> pick Pβ pixel
d < 0 -> pick P
α pixel
d = 0 -> ***CHOOSE*** to pick P
α pixel
That tells us which pixel to illuminate next. Now we need to compute what Midpoint is for the next iteration.

If we pick the Pα pixel


 



Midpoint is incremented by 1 in X and 0 in Y
We want to compute the new d without recomputing d from the new Midpoint
We want to compute the new d only using current d
dcurrent= F(xp + 1,yp + 1/2)
using the function F(x,y) = a * x + b * y + c we can expand this out ...
dcurrent= a * (xp + 1) + b * (yp + 1/2) + c

dnew = F(xp + 2, yp + 1/2)
dnew = a * (xp + 2) + b * (yp + 1/2) + c
when you simplify it you end up with: dnew = dcurrent + a
so we create a new variable called deltaE where deltaE = a
If we pick the Pβ pixel

Midpoint is incremented by 1 in x and 1 in y

We want to compute the new d without recomputing d from the new Midpoint, only using current d
We want to compute the new d only using current d
dcurrent= F(xp + 1,yp + 1/2)
using the function F(x,y) = a * x + b * y + c we can expand this out ...
dcurrent= a * (xp + 1) + b * (yp + 1/2) + c
dnew = F(xp + 2, yp + 3/2)




dnew = a * (xp + 2) + b * (yp + 3/2) + c
when you simplify it you end up with: dnew = dcurrent + a + b
initial point (xoyo) is known
so initial M is at (xo + 1, yo + 1/2)

so initial d = F(xo + 1, yo + 1/2)
using the function F(x,y) = a * x + b * y + c we can expand this out ...

= a * (xo + 1) + b * (yo + 1/2) + c
= (a * xo + b * yo + c) + a + 1/2 * b
= F(xo,yo) + a + 1/2 * b
since (xo,yo) is on the line -> F(xo,yo) = 0
so initial d = a + b / 2

the divion by 2 is still annoying, but we can remove it by being clever
we can avoid the division by 2 by multiplying function by 2
this also multiplies d, deltaE, deltaNE by 2
but since d is only concerned with =0,< 0, or > 0 multiplication does not affect it

So now we can finally show the Midpoint Line algorithm

Assuming integral endpoints for the line segment (if not then make them integral)
starting at the leftmost edge of the line (Algorithm):

∆x = x1 - xo
∆y = y1 - yo
d = ∆y * 2 - ∆x
deltaE = ∆y * 2
deltaNE = (∆y - ∆x) * 2
x = xo
y = yo
illuminate x, y
while (X < X1) repeatedly
if ( d <= 0)
add deltaE to d
add 1 to X
else
add deltaNE to d
add 1 to X
add 1 to Y
illuminate X, Y

 

 

Advantages:

    This is faster method then DDA because here we have to do only integer calculation.


 

Disadvantages:

Accumulation of error every time due to rounding in equation.


 

Source Code in C.


 

#include<stdio.h>
#include<graphics.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 20

 

void swap(int* a,int* b)
{
    int t=*a;
    *a=*b;
    *b=t;
}

 

void midpointline(int x1,int y1,int x2,int y2)
{
    int dx,dy,d,incry,incre,incrne,slopegt1=0;
    dx=abs(x1-x2);dy=abs(y1-y2);
    if(dy>dx)
    {
        swap(&x1,&y1);
        swap(&x2,&y2);
        swap(&dx,&dy);
        slopegt1=1;
    }
    if(x1>x2)
    {
        swap(&x1,&x2);
        swap(&y1,&y2);
    }
    if(y1>y2)
        incry=-1;
    else
        incry=1;
    d=2*dy-dx;
    incre=2*dy;
    incrne=2*(dy-dx);
    while(x1<x2)
    {
        if(d<=0)
            d+=incre;
        else
        {
            d+=incrne;
            y1+=incry;
        }
        x1++;
        if(slopegt1)
            putpixel(y1,x1,15);
        else
            putpixel(x1,y1,15);
    }
}
void dot(int x1,int y1,int x2,int y2)
{
    int dx,dy,d,incry,incre,incrne,slopegt1=0,k=0;
    dx=abs(x1-x2);dy=abs(y1-y2);
    if(dy>dx)
    {
            swap(&x1,&y1);
        swap(&x2,&y2);
        swap(&dx,&dy);
        slopegt1=1;
    }
    if(x1>x2)
    {
        swap(&x1,&x2);
        swap(&y1,&y2);
    }
    if(y1>y2)
        incry=-1;
    else
        incry=1;
    d=2*dy-dx;
    incre=2*dy;
    incrne=2*(dy-dx);
    while(x1<x2)
    {
        if(d<=0)
            d+=incre;
        else
        {
            d+=incrne;
            y1+=incry;
        }
        x1++,k++;

 

        if(k%2==0)
        {
        if(slopegt1)

 


 

            putpixel(y1,x1,15);

 

        else

 


 

            putpixel(x1,y1,15);
            }

 

    }
}

 

void das(int x1,int y1,int x2,int y2)
{
    int dx,dy,d,incry,incre,incrne,slopegt1=0,k=0;
    dx=abs(x1-x2);dy=abs(y1-y2);
    if(dy>dx)
    {
            swap(&x1,&y1);
        swap(&x2,&y2);
        swap(&dx,&dy);
        slopegt1=1;
    }
    if(x1>x2)
    {
        swap(&x1,&x2);
        swap(&y1,&y2);
    }
    if(y1>y2)
        incry=-1;
    else
        incry=1;
    d=2*dy-dx;
    incre=2*dy;
    incrne=2*(dy-dx);
    while(x1<x2)
    {
        if(d<=0)
            d+=incre;
        else
        {
            d+=incrne;
            y1+=incry;
        }
        x1++,k++;

 

           if((k%5)!=0)
          {
        if(slopegt1)

 


 

            putpixel(y1,x1,15);

 

        else

 


 

            putpixel(x1,y1,15);
        }
    }
}
void dasdot(int x1,int y1,int x2,int y2)
{
    int dx,dy,d,incry,incre,incrne,slopegt1=0,k=0,y=0;
    dx=abs(x1-x2);dy=abs(y1-y2);
    if(dy>dx)
    {
            swap(&x1,&y1);
        swap(&x2,&y2);
        swap(&dx,&dy);
        slopegt1=1;
    }
    if(x1>x2)
    {
        swap(&x1,&x2);
        swap(&y1,&y2);
    }
    if(y1>y2)
        incry=-1;
    else
        incry=1;
    d=2*dy-dx;
    incre=2*dy;
    incrne=2*(dy-dx);
    while(x1<x2)
    {
        if(d<=0)
            d+=incre;
        else
        {
            d+=incrne;
            y1+=incry;
        }
        x1++,k++,y++;

 

           if((k%7)!=0&&(y%7)!=0)
          {
        if(((y-1)%7)!=0)
        {
        if(slopegt1)

 


 

            putpixel(y1,x1,15);

 

        else

 


 

            putpixel(x1,y1,15);
        }
        else
        {
         if(slopegt1)

 


 

            putpixel(y1,x1,10);

 

        else

 


 

            putpixel(x1,y1,10);
        }
        }
    }
}
void main()
{
//Request autodetection
    int gdriver = DETECT,gmode,errorcode;
    int xmax,ymax,x1,y1,x2,y2,l;
//Initialize graphics and local variables
    A:
    initgraph(&gdriver,&gmode,"C:\\TC\\BGI");
//Read result of initialization
    errorcode=graphresult();
    if(errorcode!=grOk) //Error occured
    {
        printf("Graphics error : %s\n",grapherrormsg(errorcode));
        printf("Press any key to halt.");
        getch();
        exit(1);
    }
    setcolor(2);
    xmax=getmaxx();
    ymax=getmaxy();
    line((xmax/2)+1,0,(xmax/2)+1,ymax);
    line(0,(ymax/2),xmax,(ymax/2));
    gotoxy(1,1);
    printf("0:Exit 1:Solid 2:Dot 3:Dash 4:DashDot ");
    gotoxy(1,3);
    printf("Enter value for first point (x1,y1) : ");
    gotoxy(1,4);
    printf("Enter value for second point (x2,y2) : ");
    gotoxy(1,2);
    printf("Which line you want : ");
    gotoxy(23,2);
    scanf("%d",&l);
    if(l==0)
        exit(0);
    if(l!=1&&l!=2&&l!=3&&l!=4&&l!=5)
    {
        gotoxy(45,2);
        printf("Enter valid choice");
        getch();
        clrscr();
        goto A;
    }
    gotoxy(40,3);
    printf("(");
    gotoxy(45,3);
    printf(",");
    gotoxy(50,3);
    printf(")");
    gotoxy(40,4);
    printf("(");
    gotoxy(45,4);
    printf(",");
    gotoxy(50,4);
    printf(")");
    gotoxy(41,3);
    scanf("%d",&x1);
    gotoxy(46,3);
    scanf("%d",&y1);
    gotoxy(41,4);
    scanf("%d",&x2);
    gotoxy(46,4);
    scanf("%d",&y2);

 

    if(l==1) midpointline((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
    if(l==2) dot((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
    if(l==3) das((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
    if(l==4) dasdot((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
    getch();
    goto A;
}

1 comment:

Copyright Text

Copyright @ LDRP Student Community, webmaster Rahul Bhadauriya