Bricks game source code in C

Download the source code

Implement Polygon clipping using Sutherland-hodgeman algorithm.

Source Code:




#include<graphics.h>
#include<stdlib.h>
#include<conio.h>
#include<math.h>

int *x1,*y1,*x2,*y2,*x,*y,*ymax,*ymin,i,j,nin,nout,*pintersect;
float *dx,*xa;


int sign(long int a)
 {
  if (a<0) return(-1);
   else if (a==0) return(0);
    else return(1);
 }

void clip_polygon(void)
 {
  int s1,s2,f1,f2,spcross,svisible;
  int visible(int a,int b,int c,int d,int e,int f);
  void output(int a,int b,int *c,int *d,int *e);
  int cross(int a,int b,int c,int d,int e,int f,int g,int h);
  int *intersect(int a,int b,int c,int d,int e,int f,int g,int h);
  pintersect=(int *)malloc(sizeof(int)*2);
  for (i=1;i<=4;i++)
   {
    nout=0;
    for (j=0;j<nin;j++)
     *(x2+j)=*(y2+j)=0;
    for (j=1;j<=nin;j++)
     {
      if (j!=1) {}
       else
       {
f1=*(x1+j-1);
f2=*(y1+j-1);
s1=*(x1+j-1);
s2=*(y1+j-1);
svisible=visible(s1,s2,*(x+i-1),*(y+i-1),*(x+i),*(y+i));
if (svisible>=0) output(s1,s2,&nout,x2,y2);
continue;
       }
      spcross=cross(s1,s2,*(x1+j-1),*(y1+j-1),*(x+i-1),*(y+i-1),*(x+i),*(y+i));
      if (!spcross) {}
       else
{
pintersect=intersect(s1,s2,*(x1+j-1),*(y1+j-1),*(x+i-1),*(y+i-1),*(x+i),*(y+i));
output(*pintersect,*(pintersect+1),&nout,x2,y2);
}
      s1=*(x1+j-1);
      s2=*(y1+j-1);
      svisible=visible(s1,s2,*(x+i-1),*(y+i-1),*(x+i),*(y+i));
      if (svisible>=0) output(s1,s2,&nout,x2,y2);
     }
    if (!nout) continue;
    spcross=cross(s1,s2,f1,f2,*(x+i-1),*(y+i-1),*(x+i),*(y+i));
    if (!spcross) {}
     else
      {
       pintersect=intersect(s1,s2,f1,f2,*(x+i-1),*(y+i-1),*(x+i),*(y+i));
       output(*pintersect,*(pintersect+1),&nout,x2,y2);
      }
    for (j=0;j<nout;j++)
     {
      *(x1+j)=*(x2+j);
      *(y1+j)=*(y2+j);
     }
    nin=nout;
   }
  *(x2+nout)=*x2;
  *(y2+nout)=*y2;
 }

int cross(int s1,int s2,int p1,int p2,int wx1,int wy1,int wx2,int wy2)
 {
  int pvisible1,pvisible2;
  int visible(int a,int b,int c,int d,int e,int f);
  pvisible1=visible(s1,s2,wx1,wy1,wx2,wy2);
  pvisible2=visible(p1,p2,wx1,wy1,wx2,wy2);
  if (pvisible1==-pvisible2)
   return 1;
    else return 0;
 }

int visible(int sx1,int sx2,int px1,int py1,int px2,int py2)
 {
  long int temp1,temp2,temp3;
  int pvisible;
  temp1=(long)(sx1-px1)*(long)(py2-py1);
  temp2=(long)(sx2-py1)*(long)(px2-px1);
  temp3=temp2-temp1;
  pvisible=sign(temp3);
  return (pvisible);
 }

int *intersect(int px1,int py1,int px2,int py2,int wx1,int wy1,int wx2,int wy2)
 {
  float parameter[2][1],coeff[2][2],temp1,temp2;
  int right[2][1];
  coeff[0][0]=px2-px1;
  coeff[0][1]=wx1-wx2;
  coeff[1][0]=py2-py1;
  coeff[1][1]=wy1-wy2;
  right[0][0]=wx1-px1;
  right[1][0]=wy1-py1;
  temp1=(coeff[0][0]*coeff[1][1])-(coeff[0][1]*coeff[1][0]);
  temp2=coeff[0][0];
  coeff[0][0]=(coeff[1][1])/temp1;
  coeff[1][1]=temp2/temp1;
  coeff[0][1]=-(coeff[0][1])/temp1;
  coeff[1][0]=-(coeff[1][0])/temp1;
  parameter[0][0]=(coeff[0][0]*right[0][0])+(coeff[0][1]*right[1][0]);
  parameter[1][0]=(coeff[1][0]*right[0][0])+(coeff[1][1]*right[1][0]);
  *pintersect=px1+(px2-px1)*parameter[0][0];
  *(pintersect+1)=py1+(py2-py1)*parameter[0][0];
  return(pintersect);
 }

void output(int vertex1,int vertex2,int *n,int *x2,int *y2)
 {
  (*n)++;
  *(x2+(*n)-1)=vertex1;
  *(y2+(*n)-1)=vertex2;
 }

void include(int *end_edge,int final_edge,int scan)
 {
  while((*end_edge<=final_edge)&&(*(ymax+*end_edge)>=scan))
   (*end_edge)++;
 }

void fillscan(int end_edge,int start_edge,int scan)
 {
  int nx,j,k;
  nx=(end_edge-start_edge)/2;
  j=start_edge;
  for (k=1;k<=nx;k++)
   {
    line(*(xa+j),scan,*(xa+j+1),scan);
    j+=2;
   }
 }

void update_xvalues(int last_edge,int *start_edge,int scan)
 {
  int k1,k2;
  k2=last_edge;
  for (k1=last_edge;k1>=*start_edge;k1--)
   {
    if (*(ymin+k1)<scan)
     {
      *(xa+k2)=*(xa+k1)+*(dx+k1);
      if (k1!=k2)
       {
*(ymin+k2)=*(ymin+k1);
*(dx+k2)=*(dx+k1);
       }
      k2--;
     }
   }
  *start_edge=k2+1;
 }

void xsort(int start_edge,int last_edge)
 {
  int k,l;
  float t;
  for (k=start_edge;k<=last_edge;k++)
   {
    l=k;
    while((l>start_edge)&&(*(xa+l)<*(xa+l-1)))
     {
      t=*(ymin+l);
      *(ymin+l)=*(ymin+l-1);
      *(ymin+l-1)=t;
      t=*(xa+l);
      *(xa+l)=*(xa+l-1);
      *(xa+l-1)=t;
      t=*(dx+l);
      *(dx+l)=*(dx+l-1);
      *(dx+l-1)=t;
      l--;
     }
   }
 }

void poly_insert(int j,int xc1,int yc1,int xc2,int yc2)
 {
  int j1,ym;
  j1=j;
  if (yc1>yc2) ym=yc1;
   else ym=yc2;
  while((j1!=0)&&(*(ymax+j1-1)<ym))
   {
    *(ymax+j1)=*(ymax+j1-1);
    *(ymin+j1)=*(ymin+j1-1);
    *(xa+j1)=*(xa+j1-1);
    *(dx+j1)=*(dx+j1-1);
    j1--;
   }
  *(ymax+j1)=ym;
  *(dx+j1)=-(float)(xc2-xc1)/(yc2-yc1);
  if (yc1>yc2)
   {
    *(ymin+j1)=yc2;
    *(xa+j1)=xc1;
   }
   else
    {
     *(ymin+j1)=yc1;
     *(xa+j1)=xc2;
    }
 }

void getpoint(int i,int *xtemp,int *ytemp)
 {
  *xtemp=*(x2+i);
  *ytemp=*(y2+i);
 }

void loadpolygon(int i,int *edges)
 {
  int xc1,xc2,yc1,yc2,i1,k;
  getpoint(i,&xc1,&yc1);
  i1=i+1;
  *edges=0;
  for(k=1;k<=nin;k++)
   {
    getpoint(i1,&xc2,&yc2);
    if (yc1==yc2)
     xc1=xc2;
     else
      {
       poly_insert(*edges,xc1,yc1,xc2,yc2);
       (*edges)++;
       yc1=yc2;
       xc1=xc2;
      }
    i1++;
   }
  (*edges)--;
 }

void fillpolygon(int index)
 {
  int edges,scan,start_edge,end_edge;
  loadpolygon(index,&edges);
  if (edges<1) return;
  scan=*ymax;
  start_edge=0;
  end_edge=0;
  include(&end_edge,edges,scan);
  while(end_edge!=start_edge)
   {
    xsort(start_edge,end_edge-1);
    fillscan(end_edge,start_edge,scan);
    scan--;
    update_xvalues(end_edge-1,&start_edge,scan);
    include(&end_edge,edges,scan);
   }
 }

void main()
 {
 int gd=DETECT,gm;
  int gdriver = DETECT,gmode,errorcode;
  clrscr();
/*  //Request autodetection
int gdriver = DETECT,gmode,errorcode;
//int xmax,ymax,x1,y1,x2,y2,l;
//Initialize graphics and local variables

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);
}*/


  x=(int *)malloc(sizeof(int)*5);
  y=(int *)malloc(sizeof(int)*5);
  printf("Enter number of sides in polygon : ");
  scanf("%d",&nin);
  x1=(int *)malloc(sizeof(int)*2*nin);
  y1=(int *)malloc(sizeof(int)*2*nin);
  x2=(int *)malloc(sizeof(int)*2*nin);
  y2=(int *)malloc(sizeof(int)*2*nin);
  ymax=(int *)malloc(sizeof(int)*2*nin);
  ymin=(int *)malloc(sizeof(int)*2*nin);
  xa=(float *)malloc(sizeof(float)*2*nin);
  dx=(float *)malloc(sizeof(float)*2*nin);
  printf("Enter the coordinates of the vertices (x y) :\n");
  for (i=0;i<nin;i++)
   {
    printf("%d",(i+1));
    printf(":");
    scanf("%d%d",&*(x1+i),&*(y1+i));
   }
  *(x1+nin)=*x1;
  *(y1+nin)=*y1;
  printf("\n\nEnter the coordinates of the window vertices :\n");
  for (i=0;i<4;i++)
   {
    printf("%d",(i+1));
    printf(":");
    scanf("%d%d",&*(x+i),&*(y+i));

   }
  *(x+4)=*x;
  *(y+4)=*y;

 // registerbgidriver(EGAVGA_driver);

initgraph(&gdriver,&gmode,"C:\\TC\\BGI");
errorcode = graphresult();
// initgraph(&gd,&gm,"");
printf("Before clipping");
  outtextxy(*x1+10,*y1-10,"Polygon");
  outtextxy(*(x+1)+10,*(y+1)-10,"Clipping Window");
  for (i=0;i<4;i++)
   line(*(x+i),*(y+i),*(x+i+1),*(y+i+1));
  for (i=0;i<nin;i++)
   line(*(x1+i),*(y1+i),*(x1+i+1),*(y1+i+1));
  getch();
  clearviewport();
  printf("After clipping");
rectangle(200,200,400,400);
  clip_polygon();
  for (i=0;i<nin;i++)
   {
    if(*(y2+i)<*(y2+i+1))
     {
      *(ymax+i)=*(y2+i+1);
      *(ymin+i)=*(y2+i);
      *(xa+i)=*(x2+i+1);
     }
     else
      {
       *(ymax+i)=*(y2+i);
       *(ymin+i)=*(y2+i+1);
       *(xa+i)=*(x2+i);
      }
    *(dx+i)=*(y2+i)-*(y2+i+1);
    if (*(dx+i))
     *(dx+i)=(float)(*(x2+i)-*(x2+i+1))/(*(dx+i));
    line(*(x2+i),*(y2+i),*(x2+i+1),*(y2+i+1));
   }
  fillpolygon(0);
  getch();
  closegraph();
 }

click here to download the source code.

Theory/logic:

Compute each of the vertices against window edges. The inside vertices are saved for clipping against next boundary; outside vertices are discarded.

The algorithm:

For each edge, check both nodal values, s and p. If the point values are:

1. Inside-inside, append the second node, p.
2. Inside-outside, compute and append the intersection, i of edge sp with the clipping plane.
3. Outside-outside, no operation.
4. Outside-inside, compute and append the intersection i of edge sp with the clipping plane, then append the second node p.
1. The resultant ordered list of nodes forms the clipped polygon.

 There are four possible cases as we process line segments. Save the points in one list.

Advantage:

à It is a true three-dimensional algorithm that clips a general (convex) polygon with any plane.

Disadvantage: Convex polygons are correctly clipped by this algo, but concave polygons may be displayed with extraneous lines, as shown in figure.

Advantage:

à It is a true three-dimensional algorithm that clips a general (convex) polygon with any plane.

Disadvantage: Convex polygons are correctly clipped by this algo, but concave polygons may be displayed with extraneous lines, as shown in figure.

Implement Line Clipping using Liang-Barky algorithm

Source Code:



#include<graphics.h>
#include<dos.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void main()
{
int gd,gm;
int x1[100],y1[100],x2[100],y2[100],n=12,i;
int wxmin=200,wymin=200,wxmax=400,wymax=400;
float u1=0,u2=1;
int p1[100],q1[100],p2[100],q2[100],p3[100],q3[100],p4[100],q4[100];
float r1[100],r2[100],r3[100],r4[100];
int x11[100],y11[100],x22[100],y22[100];

clrscr();
for(i=0;i<100;i++)
{
x1[100]=y1[100]=x2[100]=y2[100]=p1[100]=q1[100]=p2[100]=q2[100]=p3[100]=q3[100]=p4[100]=q4[100]=0;
r1[100]=r2[100]=r3[100]=r4[100]=x11[100]=y11[100]=x22[100]=y22[100]=0;
}
/*printf("Enter the windows left xmin , top boundry ymin\n");
scanf("%d%d",&wxmin,&wymin);
printf("Enter the windows right xmax ,bottom boundry ymax\n");
scanf("%d%d",&wxmax,&wymax);
printf("Enter the no. of lines you want to clip : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter line x1 , y1 co-ordinate for line %d\n",i);
scanf("%d%d",&x1[i],&y1[i]);
printf("Enter line x2 , y2 co-ordinate for line %d\n",i);
scanf("%d%d",&x2[i],&y2[i]);
}*/
x1[0]=250;y1[0]=100;x2[0]=250;y2[0]=450;
x1[1]=300;y1[1]=100;x2[1]=300;y2[1]=450;
x1[2]=350;y1[2]=100;x2[2]=350;y2[2]=450;
x1[3]=100;y1[3]=250;x2[3]=450;y2[3]=250;
x1[4]=100;y1[4]=300;x2[4]=450;y2[4]=300;
x1[5]=100;y1[5]=350;x2[5]=450;y2[5]=350;
x1[6]=150;y1[6]=350;x2[6]=350;y2[6]=150;
x1[7]=150;y1[7]=450;x2[7]=450;y2[7]=150;
x1[8]=250;y1[8]=450;x2[8]=450;y2[8]=250;
x1[9]=250;y1[9]=150;x2[9]=450;y2[9]=350;
x1[10]=150;y1[10]=150;x2[10]=450;y2[10]=450;
x1[11]=150;y1[11]=250;x2[11]=350;y2[11]=450;
for(i=0;i<n;i++)
{
u1=0; u2=1;
printf("liang barsky express these 4 inequalities using lpk<=qpk\n");
p1[i]=-(x2[i]-x1[i]); q1[i]=x1[i]-wxmin;
p2[i]=(x2[i]-x1[i]); q2[i]=wxmax-x1[i];
p3[i]=-(y2[i]-y1[i]); q3[i]=y1[i]-wymin;
p4[i]=(y2[i]-y1[i]); q4[i]=wymax-y1[i];
printf("p1=0 line is parallel to left clipping\n");
printf("p2=0 line is parallel to right clipping\n");
printf("p3=0 line is parallel to bottom clipping\n");
printf("p4=0 line is parallel to top clipping\n");
if(((p1[i]==0)&&(q1[i]<0))||((p2[i]==0)&&(q2[i]<0))||((p3[i]==0)&&(q3[i]<0))||((p4[i]==0)&&(q4[i]<0)))
{
printf("Line is rejected\n");
getch();
detectgraph(&gd,&gm);
initgraph(&gd,&gm,"c:\\tc\\bgi");
setcolor(RED);
rectangle(wxmin,wymax,wxmax,wymin);
setcolor(BLUE);
line(x1[i],y1[i],x2[i],y2[i]);
getch();
setcolor(WHITE);
line(x1[i],y1[i],x2[i],y2[i]);
getch();
}
else
{
if(p1[i]!=0)
{
r1[i]=(float) q1[i]/p1[i];
if(p1[i]<0)
u1=max(r1[i],u1);
else
u2=min(r1[i],u2);
}
if(p2[i]!=0)
{
r2[i]=(float) q2[i]/p2[i];
if(p2[i]<0)
u1=max(r2[i],u1);
else
u2=min(r2[i],u2);
}
if(p3[i]!=0)
{
r3[i]=(float) q3[i]/p3[i];
if(p3[i]<0)
u1=max(r3[i],u1);
else
u2=min(r3[i],u2);
}
if(p4[i]!=0)
{
r4[i]=(float) q4[i]/p4[i];
if(p4[i]<0)
u1=max(r4[i],u1);
else
u2=min(r4[i],u2);
}
if(u1>u2)
printf("line rejected\n");
else
{
x11[i]=x1[i]+(u1*(x2[i]-x1[i]));
y11[i]=y1[i]+(u1*(y2[i]-y1[i]));

x22[i]=x1[i]+(u2*(x2[i]-x1[i]));
y22[i]=y1[i]+(u2*(y2[i]-y1[i]));

printf("Original line cordinates\n");
printf("x1 = %d , y1 = %d, x2 = %d, y2 = %d\n",x1[i],y1[i],x2[i],y2[i]);
printf("Windows coordinate are \n");
printf("wxmin = %d, wymin = %d,wxmax = %d , wymax = %d ",wxmin,wymin,wxmax,wymax);

printf("New coordinates are \n");
printf("x1 = %d, y1 = %d,x2 = %d , y2 = %d\n",x11[i],y11[i],x22[i],y22[i]);
/*detectgraph(&gd,&gm);
initgraph(&gd,&gm,"C:\\TC\\BGI");
setcolor(2);
rectangle(wxmin,wymax,wxmax,wymin);
setcolor(1);
line(x1[i],y1[i],x2[i],y2[i]);
getch();
setcolor(0);
line(x1[i],y1[i],x2[i],y2[i]);
setcolor(3);
line(x11[i],y11[i],x22[i],y22[i]);
getch();*/
}
}
}
detectgraph(&gd,&gm);
initgraph(&gd,&gm,"C:\\TC\\BGI");
gotoxy(0,100);
printf("Before Clipping\n");
setcolor(2);
rectangle(wxmin,wymax,wxmax,wymin);
for(i=0;i<n;i++)
{
setcolor(12);
line(x1[i],y1[i],x2[i],y2[i]);
}
getch();
cleardevice();
gotoxy(0,100);
printf("After Clipping\n");
rectangle(wxmin,wymax,wxmax,wymin);
for(i=0;i<n;i++)
{
setcolor(0);
;
line(x1[i],y1[i],x2[i],y2[i]);
setcolor(15);
line(x11[i],y11[i],x22[i],y22[i]);
}
getch();
}


Click here to download the source code

Theory/logic:

Liang and Barsky have created an algorithm that uses floating-point arithmetic but finds the appropriate end points with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.

Parametric equations of a line are:

x=x1 + Δx . u

y=y1 + Δy . u

where Δx=x2-x1, Δy=y2-y1

For point inside the clipping window,

            xmin <= x1 + Δx.u <= xmax

            ymin <= y1 + Δy.u <= ymax

Rewrite the four inequalities as

            p_k .u <= q_k,      k=1,2,3,4

where

            p1= - Δx         q1=x1-xmin   (left)

            p2= Δx            q2=xmax-x1  (right)

            p3= -Δy           q3=y1-ymin   (bottom)

            p4= Δy                        q4=ymax-y1   (top)

Algorithm: for all k,

• If pk=0, the line is parallel to the corresponding boundary.

--If qk < 0, the line is completely outside the boundary and can be eliminated.

--If qk >= 0, the line is inside the boundary and needs further consideration.

• If pk < 0, the extended line proceeds from outside to inside, calculate rk= qk/pk. Let u1 be maximum of the set containing 0 and the calculated r values.
• If pk > 0, the extended line proceeds from inside to outside, calculate rk= qk/pk. Let u2 be minimumum of the set containing 1 and the calculated r values.
• If u1 > u2 , eliminate the line since it is completely outside. Otherwise use u1 and

u2 to calculate the endpoints of the clipped line.

Data Structure: none.

Advantage:

à Easy to implement.

à It represents the line using parametric equations, so faster line clipping algorithm.

à Also no need of intersection point calculations as in Cohen Sutherland algorithm.

Disadvantage:

à Used for rectangle windows only.

Application :

            à When line representation is using parametric equation, this is useful.

àIn window to view port transformation, when the region is to be

                       Clipped, then this algorithm is used to clip the lines.

Implement Line Clipping using Cohen- Sutherland algorithm

Source Code:



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

enum { TOP = 0x1, BOTTOM = 0x2, RIGHT = 0x4, LEFT = 0x8 };

enum { FALSE, TRUE };
typedef unsigned int outcode;

outcode compute_outcode(int x, int y,
int xmin, int ymin, int xmax, int ymax)
{
    outcode oc = 0;

    if (y > ymax)
oc |= TOP;
    else if (y < ymin)
oc |= BOTTOM;


    if (x > xmax)
oc |= RIGHT;
    else if (x < xmin)
oc |= LEFT;

    return oc;
}

void cohen_sutherland (double x1, double y1, double x2, double y2,
double xmin, double ymin, double xmax, double ymax)
{
    int accept;
    int done;
    outcode outcode1, outcode2;

    accept = FALSE;
    done = FALSE;

    outcode1 = compute_outcode (x1, y1, xmin, ymin, xmax, ymax);
    outcode2 = compute_outcode (x2, y2, xmin, ymin, xmax, ymax);
    do
    {
if (outcode1 == 0 && outcode2 == 0)
{
   accept = TRUE;
   done = TRUE;
}
else if (outcode1 & outcode2)
{
   done = TRUE;
}
else
{
   double x, y;
   int outcode_ex = outcode1 ? outcode1 : outcode2;
   if (outcode_ex & TOP)
   {
x = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);
y = ymax;
   }

   else if (outcode_ex & BOTTOM)
   {
x = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
y = ymin;
   }
   else if (outcode_ex & RIGHT)
   {
y = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);
x = xmax;
   }
   else
   {
y = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
x = xmin;
   }
   if (outcode_ex == outcode1)
   {
x1 = x;
y1 = y;
outcode1 = compute_outcode (x1, y1, xmin, ymin, xmax, ymax);
   }
   else
   {
x2 = x;
y2 = y;
outcode2 = compute_outcode (x2, y2, xmin, ymin, xmax, ymax);
   }
}
    } while (done == FALSE);

    if (accept == TRUE)
line (x1, y1, x2, y2);
}



void main()
{
    int n;
    int i, j;
    int ln[MAX][4];
    int clip[4];
    int gd = DETECT, gm;

   /* printf ("Enter the number of lines to be clipped:");
    scanf ("%d", &n);

    printf ("Enter the x- and y-coordinates of the line-endpoints:\n");
    for (i=0; i<n; i++)
for (j=0; j<4; j++)
   scanf ("%d", &ln[i][j]);
     */
    printf ("Enter the coordinates of the clipping window:\n");
    for (i=0; i<4; i++)
scanf ("%d", &clip[i]);

    initgraph (&gd, &gm, "..//bgi");
    setcolor(GREEN);
gotoxy(0,2);
printf("before clipping");
setcolor(RED);
    rectangle (clip[0], clip[1], clip[2], clip[3]);
setcolor(WHITE);
line(250,100,250,450);
line(300,100,300,450);
line(350,100,350,450);
line(100,250,450,250);
line(100,300,450,300);
line(100,350,450,350);
line(150,350,350,150);
line(150,450,450,150);
line(250,450,450,250);
line(250,150,450,350);
line(150,150,450,450);
line(150,250,350,450);
    /*for (i=0; i<n; i++)
    {
line (ln[i][0], ln[i][1], ln[i][2], ln[i][3]); } */
    getch();
    cleardevice();
setcolor(RED);
gotoxy(0,3);
printf("after clipping");
    rectangle (clip[0], clip[1], clip[2], clip[3]);
setcolor(WHITE);
    //for (i=0; i<n; i++)
    //{
cohen_sutherland (250,100,250,450,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (300,100,300,450,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (350,100,350,450,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (100,250,450,250,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (100,300,450,300,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (100,350,450,350,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (150,350,350,150,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (150,450,450,150,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (250,450,450,250,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (250,150,450,350,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (150,150,450,450,clip[0], clip[1], clip[2], clip[3]);
cohen_sutherland (150,250,350,450,clip[0], clip[1], clip[2], clip[3]);


   // }
getch();
    closegraph();
}

click here to download the source code

Theory/logic:

This algorithm is used to clip the line against givan rectangle window. As you proceed around the window, extending each edge and defining an inside half-space and an outside half-space, nine regions are created - the eight "outside" regions and the one "inside" region. Each of the nine regions associated with the window is assigned a 4-bit code to identify the region. Each bit in the code is set to either a 1(true) or a 0(false). If the region is to the left of the window, the first bit of the code is set to 1. If the region is to the top of the window, the second bit of the code is set to 1. If to the right, the third bit is set, and if to the bottom, the fourth bit is set. The 4 bits in the code then identify each of the nine regions as shown below.

For any endpoint ( x , y ) of a line, the code can be determined that identifies which region the endpoint lies. The code's bits are set according to the following conditions:

The sequence for reading the codes' bits is LRBT (Left, Right, Bottom, Top).

Once the codes for each endpoint of a line are determined, the logical AND operation of the codes determines if the line is completely outside of the window. If the logical AND of the endpoint codes is not zero, the line can be trivally rejected. For example, if an endpoint had a code of 1001 while the other endpoint had a code of 1010, the logical AND would be 1000 which indicates the line segment lies outside of the window. On the other hand, if the endpoints had codes of 1001 and 0110, the logical AND would be 0000, and the line could not be trivally rejected.

The logical OR of the endpoint codes determines if the line is completely inside the window. If the logical OR is zero, the line can be trivally accepted. For example, if the endpoint codes are 0000 and 0000, the logical OR is 0000 - the line can be trivally accepted. If the endpoint codes are 0000 and 0110, the logical OR is 0110 and the line can not be trivally accepted.

Data Structure: none.

Advantage:

àEasy to implement.

à First check is performed to find whether line is to be accepted or rejected, so no need to do any calculations if line is to be rejected completely.

Disadvantage:

à It is limited to rectangle window only.

à Intersection point calculations are required.

Application : In window to viewport transformation, when the region is to be

                       Clipped, then this algorithm is used to clip the lines.

I/P & O/P: Before Clipping (Input) :

How Algorithm works?

1. Consider the line segment AD.

Point A has an outcode of 0000 and point D has an outcode of 1001. The logical AND of these outcodes is zero; therefore, the line cannot be trivally rejected. Also, the logical OR of the outcodes is not zero; therefore, the line cannot be trivally accepted. The algorithm then chooses D as the outside point (its outcode contains 1's). By our testing order, we first use the top edge to clip AD at B. The algorithm then recomputes B's outcode as 0000. With the next iteration of the algorithm, AB is tested and is trivially accepted and displayed.

2. Consider the line segment EI

Point E has an outcode of 0100, while point I's outcode is 1010. The results of the trivial tests show that the line can neither be trivally rejected or accepted. Point E is determined to be an outside point, so the algorithm clips the line against the bottom edge of the window. Now line EI has been clipped to be line FI. Line FI is tested and cannot be trivially accepted or rejected. Point F has an outcode of 0000, so the algorithm chooses point I as an outside point since its outcode is1010. The line FI is clipped against the window's top edge, yielding a new line FH. Line FH cannot be trivally accepted or rejected. Since H's outcode is 0010, the next iteration of the algorthm clips against the window's right edge, yielding line FG. The next iteration of the algorithm tests FG, and it is trivially accepted and display.

After Clipping (Output) :

After clipping the segments AD and EI, the result is that only the line segment AB and FG can be seen in the window.

Conclusion: Cohen Sutherland algorithm is easy to implement algorithm to clip the given line against rectangle window.

Implement algorithm of 2D Transformation of an Object.

Source Code: Translation ,Rotation, Scaling, Reflection , Shearing

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<graphics.h>
int ch,x,y,az,i,w,ch1,ch2,xa,ya,ra,a[10],b[10],da,db;
float x1,y1,az1,w1,dx,dy,theta,x1s,y1s,sx,sy,a1[10],b1[10];
void main()
{
int gm ,gr,xmax,ymax;
clrscr();
detectgraph(&gm,&gr);
initgraph(&gm,&gr,"d:\\tc\\BGI");
printf("Enter the upper left corner:");
scanf("%d%d",&x,&y);
printf("Enter the lower right corner:");
scanf("%d%d",&az,&w);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
//setviewport(1,35,xmax-1,ymax-1,1);
rectangle(((xmax)/2)+x,((ymax)/2)+y,((xmax)/2)+az,((ymax)/2)+w);
da=az-x;
db=w-y;
a[0]=x;
b[0]=y;
a[1]=x+da;
b[1]=y;
a[2]=x+da;
b[2]=y+db;
a[3]=x;b[3]=y+db;
while(1)
{
printf(" Transformations\n");
printf("Enter your choice\n");
printf("1.Translation\n2.Rotation\n3.Scaling\n4.Reflection\n5.Shearing\n6.Exit\nEnter your choice:\n");
scanf("%d",&ch);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
switch(ch)
{
case 1:
detectgraph(&gm,&gr);
initgraph(&gm,&gr,"d:\\tc\\BGI");
rectangle(((xmax)/2)+x,((ymax)/2)+y,((xmax)/2)+az,((ymax)/2)+w);
printf("Translation\n\n");
printf("Enter the two values of shift vectors tx & ty:\n");
scanf("%f%f",&dx,&dy);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
x1=x+dx;
y1=y+dy;
az1=az+dx;
w1=w+dy;
rectangle(((xmax)/2)+x1,((ymax)/2)+y1,((xmax)/2)+az1,((ymax)/2)+w1);
break;
case 2:
detectgraph(&gm,&gr);
initgraph(&gm,&gr,"d:\\tc\\BGI");
rectangle(((xmax)/2)+x,((ymax)/2)+y,((xmax)/2)+az,((ymax)/2)+w);
printf("Rotation\n\n");
printf("Enter the two value of fixed point and angle of rotation:\n");
scanf("%d%d%d",&xa,&ya,&ra);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
theta=(float)(ra*(3.14/180));
for(i=0;i<4;i++)
{
a1[i]=(xa+((a[i]-xa)*cos(theta)-(b[i]-ya)*sin(theta)));
b1[i]=(ya+((a[i]-xa)*sin(theta)+(b[i]-ya)*cos(theta)));
}
for(i=0;i<4;i++)
{
if(i!=3)
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[i+1],((ymax)/2)+b1[i+1]);
else
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[0],((ymax)/2)+b1[0]);
}
break;
case 3:
detectgraph(&gm,&gr);
initgraph(&gm,&gr,"d:\\tc\\BGI");
rectangle(((xmax)/2)+x,((ymax)/2)+y,((xmax)/2)+az,((ymax)/2)+w);
printf("Scaling\n\n");
printf("Enter the two value sx and sy of scaling factor:\n");
scanf("%f%f",&sx,&sy);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
x1=x*sx;
y1=y*sy;
az1=az*sx;
w1=w*sy;
rectangle(((xmax)/2)+x1,((ymax)/2)+y1,((xmax)/2)+az1,((ymax)/2)+w1);
break;
case 4:
detectgraph(&gm,&gr);
initgraph(&gm,&gr,"d:\\tc\\BGI");
rectangle(((xmax)/2)+x,((ymax)/2)+y,((xmax)/2)+az,((ymax)/2)+w);
printf("Reflection\n");
printf("Select your choice\n");
printf("1.About x-axis\n2.About y-axis\n3.About both axis\nEnter your choice:\n");
scanf("%d",&ch1);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
switch(ch1)
{
case 1:
printf("Enter the two fixed point\n");
scanf("%d%d",&xa,&ya);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
theta=(float)(90*(3.14/180));
for(i=0;i<4;i++)
{
a1[i]=(xa+((a[i]-xa)*cos(theta)-(-b[i]-ya)*sin(theta)));
b1[i]=(ya+((a[i]-xa)*sin(theta)+(-b[i]-ya)*cos(theta)));
}
for(i=0;i<4;i++)
{
if(i!=3)
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[i+1],((ymax)/2)+b1[i+1]);
else
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[0],((ymax)/2)+b1[0]);
}
break;
case 2:
printf("Enter the two fixed point\n");
scanf("%d%d",&xa,&ya);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
theta=(float)(270*(3.14/180));
for(i=0;i<4;i++)
{
a1[i]=(xa+((-a[i]-xa)*cos(theta)-(b[i]-ya)*sin(theta)));
b1[i]=(ya+((-a[i]-xa)*sin(theta)+(b[i]-ya)*cos(theta)));
}
for(i=0;i<4;i++)
{
if(i!=3)
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[i+1],((ymax)/2)+b1[i+1]);
else
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[0],((ymax)/2)+b1[0]);
}
break;
case 3:
printf("Enter the two fixed point\n");
scanf("%d%d",&xa,&ya);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
theta=(float)(180*(3.14/180));
for(i=0;i<4;i++)
{
a1[i]=(xa+((-a[i]-xa)*cos(theta)-(-b[i]-ya)*sin(theta)));
b1[i]=(ya+((-a[i]-xa)*sin(theta)+(-b[i]-ya)*cos(theta)));
}
for(i=0;i<4;i++)
{
if(i!=3)
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[i+1],((ymax)/2)+b1[i+1]);
else
line(((xmax)/2)+a1[i],((ymax)/2)+b1[i],((xmax)/2)+a1[0],((ymax)/2)+b1[0]);
}
break;
}
break;
case 5:
detectgraph(&gm,&gr);
initgraph(&gm,&gr,"d:\\tc\\BGI");
rectangle(((xmax)/2)+x,((ymax)/2)+y,((xmax)/2)+az,((ymax)/2)+w);
printf("Shearing\n\n");
printf("1.x-direction shear\n2.y-direction shear\nEnter your choice:\n");
scanf("%d",&ch2);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
switch(ch2)
{
case 1:
printf("Enter the value of shx:\n");
scanf("%f",&x1s);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
x1=x+(y*x1s);
y1=y;
az1=az+(w*x1s);
w1=w;
rectangle(((xmax)/2)+x1,((ymax)/2)+y1,((xmax)/2)+az1,((ymax)/2)+w1);
break;
case 2:
printf("Enter the value of shy:\n");
scanf("%f",&y1s);
xmax=getmaxx();
ymax=getmaxy();
line((xmax/2)+1,0,(xmax/2)+1,ymax);
line(0,(ymax/2),xmax,(ymax/2));
x1=x;
y1=y+(x*y1s);
az1=az;
w1=w+(az*y1s);
rectangle(((xmax)/2)+x1,((xmax)/2)+y1,((xmax)/2)+az1,((xmax)/2)+w1);
break;
}
break;
case 6:
exit(0);
}
}
getch();
}

Download the sorce code

Implementation of Flood Fill, Boundary Fill,Scanfill algorithm with source code in C/C++

Source code:


#include<graphics.h>
#include<conio.h>
#include<stdio.h>
#include<dos.h>
#include<stdlib.h>

struct Node
{
    int x;
    int y;
    struct Node* next;
};

void fill (int pt[][2], int clr);
void floodfill4 (int x, int y, int oldclr, int newclr);
void insert (int x, int y, struct Node** last);

void main()
{
int x,y,xmax,ymax,q,i,j,clr,pt[3][2];
char str[20];
int gdriver = DETECT,gmode,errorcode;

 start: clrscr();
initgraph(&gdriver,&gmode,"C:\\TC\\BGI");
errorcode = graphresult();

if (errorcode != grOk)
{
printf("Graphics error: %s\n", grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1);
}

xmax=getmaxx();
ymax=getmaxy();

//rectangle(0,100,xmax,ymax);
lineDDA(xmax/2,80,xmax/2,ymax);
lineDDA(0,ymax/2,xmax,ymax/2);

while(1)
{
moveto(xmax/2,ymax/2);
gotoxy(0,2);
printf("0:Exit,1:FloodFill,2:ScanLine,3:BoundaryFill");
gotoxy(1,3);
printf("What to do:   ");
gotoxy(12,4);
printf("Enter the x- and y-coordinates for three points: ");
for (i=0; i<3; i++)
{for (j=0; j<2; j++)
{scanf ("%d", &pt[i][j]);}}

printf ("Enter the fill-colour: (Any number from 1 to 14) ");
scanf ("%d", &clr);
// fill (pt, clr);
/*gotoxy(12,5);
printf("x1:      ");
gotoxy(12,6);
printf(" y1       ");
gotoxy(12,7);
printf("x2    ");
gotoxy(12,8);
printf("y2   ");
gotoxy(12,9);
printf("x3    ");
gotoxy(12,10);
printf("y3   ");*/
gotoxy(12,3);
scanf("%d",&q);
if(q==0) break;
if(q!=1&&q!=2&&q!=3)
{
gotoxy(20,6);
printf("Enter valid choice.");
getch();
continue;
}
/*gotoxy(14,5);
scanf("%d",&x1);
gotoxy(14,6);
scanf("%d",&y1);
gotoxy(14,7);
scanf("%d",&x2);
gotoxy(14,8);
scanf("%d",&y2);
gotoxy(14,9);
scanf("%d",&x3);
gotoxy(14,10);
scanf("%d",&y3);*/
if(q==1)  fill (pt, clr);
getch();
goto start;

}

}

void fill (int pt[][2], int clr)
{
    int gd = DETECT, gm;
    int seedx, seedy;

    initgraph (&gd, &gm, "..\\bgi");

    setcolor (WHITE);
    line (pt[0][0], pt[0][1], pt[1][0], pt[1][1]);
    line (pt[1][0], pt[1][1], pt[2][0], pt[2][1]);
    line (pt[2][0], pt[2][1], pt[0][0], pt[0][1]);
    getch();

    seedx = (pt[0][0] + pt[1][0] + pt[2][0]) / 3;
    seedy = (pt[0][1] + pt[1][1] + pt[2][1]) / 3;

    floodfill4 (seedx, seedy, BLACK, clr);
    getch();

    closegraph();
    return;
}

void floodfill4 (int x, int y, int oldclr, int newclr)
{
    struct Node* first, *last, *tmp;

    first = (struct Node*) malloc (sizeof (struct Node));
    if (first == NULL)
    {
closegraph();
fprintf (stderr, "floodfill4: Out of memory.\n");
exit (2);
    }
    if (oldclr == newclr)
    {
free (first);
return;
    }

    first->x = x;
    first->y = y;
    first->next = NULL;
    last = first;

    while (first != NULL)
    {
putpixel (x, y, newclr);

if (getpixel (x, y-1) == oldclr)
{
   putpixel (x, y-1, newclr);
   insert (x, y-1, &last);
}


if (getpixel (x, y+1) == oldclr)
{
   putpixel (x, y+1, newclr);
   insert (x, y+1, &last);
}

if (getpixel (x-1, y) == oldclr)
{
   putpixel (x-1, y, newclr);
   insert (x-1, y, &last);
}

if (getpixel (x+1, y) == oldclr)
{
   putpixel (x+1, y, newclr);
   insert (x+1, y, &last);
}

tmp = first;
first = first->next;
x = first->x;
y = first->y;
free (tmp);
    }
}

void insert (int x, int y, struct Node** last)
{
    struct Node* p;
    p = (struct Node*) malloc (sizeof (struct Node));
    if (p == NULL)
    {
closegraph();
fprintf (stderr, "\n insert: Out of memory.\n");
exit (2);
    }

    p->x = x;
    p->y = y;
    p->next = NULL;
    (*last)->next = p;
    *last = (*last)->next;
}


Click here to download the sorce code.

EUCLID and EXTENDED EUCLID algorithm.

#include<stdio.h>

#include<conio.h>

void main()

{

            int a,b,r1,r2,q,r,s1,s2,s,t1,t2,t,gcd,ans,c;

            clrscr();

            printf("0:EUCLIDIAN\n");

            printf("1:EXTENDED EUCLIDIAN\n");

            printf("Plese enter your choice\n");

            scanf("%d",&c);

            if(c==1)

            {

            printf("Enter the numbers to find GCD\n");

            printf("Enter r1 and r2:\n");

            scanf("%d%d",&a,&b);

            r1=a;

            r2=b;

       s1=1;

       s2=0;

       t1=0;

       t2=1;

            while(r2>0)

            {

                        q=r1/r2;

                        r=r1-(r2*q);

                        r1=r2;

                        r2=r;

                        s=s1-(q*s2);

                        s1=s2;

                        s2=s;

                        t=t1-(q*t2);

                        t1=t2;

                        t2=t;

            }

            gcd=r1;

            s=s1;t=t1;

            ans=(s*a)+(t*b);

            printf("\nGCD For %d and %d  GCD(%d,%d) is : %d",a,b,a,b,gcd);

            printf("\nGCD For %d and %d  GCD(%d,%d) is (%d*%d)+(%d*%d)=%d",a,b,a,b,s,a,t,b,ans);

            }

            else

            {

            printf("Enter the numbers to find GCD\n");

            printf("Enter r1 and r2 :\n");

            scanf("\t%d\t%d",&r1,&r2);

            a=r1;

            b=r2;

            while(b>0)

            {

                        q=a/b;

                        r=a-(b*q);

                        a=b;

                        b=r;

            }

            gcd=a;

            printf("\nGCD For %d and %d  GCD(%d,%d) is : %d",r1,r2,r1,r2,gcd);

            }

            getch();

}

output: