et1.c

计算机图形学

#include "stdio.h"
#include "math.h"
#define pi 3.14159265
#include "Conio.h"
#include "graphics.h"
#include "malloc.h"
#define closegr closegraph
#define max 400

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define false 0
#define true  1
#define ok     1
#define error   0
#define infeasible -1
#define overflow  -2
typedef int Status;

typedef int bool;
typedef struct {
int y,xLeft,xRight;
}SElemType;

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

typedef struct Edge{
int ymax;
float x,deltax;
struct Edge *nextEdge;
}Edge;
Edge *EL[max];

typedef struct{
float x,y;
}point;

void initgr(void) /* BGI初始化 */
{int gd=DETECT,gm=0; /* 和gd=VGA,gm=VGAHI是同样效果 */
 registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
 initgraph(&gd,&gm,"");
}

Status SetStackEmpty(SqStack *s)
{s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 if(!s->base) return overflow;
 s->top=s->base;
 s->stacksize=STACK_INIT_SIZE;
 return ok;
}

 Status PushStack(SqStack *s,SElemType e)
{if(s->top-s->base>=s->stacksize)
{s->base=(SElemType *)(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!s->base) return error;
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;}
*s->top++=e;
return ok;
}

Status PopStack(SqStack *s,SElemType *e)
{ if(s->top==s->base) return error;

*e=*(--s->top);
 return ok;
}
Status IsStackEmpty(SqStack *s)
{if(s->base==s->top) return true;
 else return  false;
}
void ScanLineFill4(int x,int Y,int oldColor,int newColor)
{ int xLeft,xRight,y,i;
 bool isLeftEndSet,spanNeedFill;
 SElemType *span;
  SqStack *s;
 /*填充并确定种子点(x,y)所在的区段*/
 i=x; y=Y;
 while(getpixel(i,y)==oldColor)  /*向右填充*/
    {putpixel(i,y,newColor);
    i++;
    }
 span->xRight=i-1;   /*确定区段右边界*/
 i=x-1;
 while(getpixel(i,y)==oldColor)  /*向左填充*/
    {putpixel(i,y,newColor);
    i--;
    }
 span->xLeft=i+1;   /*确定区段左边界*/
 /*初始化*/
 SetStackEmpty(s);
 span->y=y;
 PushStack(s,*span); /*将前面生成的区段压入堆栈*/
 while(!IsStackEmpty(s)) /*终止判断*/
   {/*出栈*/
    PopStack(s,span);
    /*处理上面扫描线*/
    y=span->y+1;
    xRight=span->xRight;
    i=span->xLeft;
    isLeftEndSet=false;
    while(getpixel(i,y)==oldColor)  /*向左填充*/
       {/*if(getpixel(i+1,y)==color) break;*/
        putpixel(i,y,newColor);
        i--;
        }
    if(i!=span->xLeft)  /*确定区段左边界*/
      {isLeftEndSet=true;
       xLeft=i+1;
       }
    i=span->xLeft;
    while(i<=xRight)
       {spanNeedFill=false;
        while(getpixel(i,y)==oldColor) /*向右填充*/
          {if(!spanNeedFill)
             {spanNeedFill=true;
             if(!isLeftEndSet)
               {isLeftEndSet=true;
                xLeft=i;
                }
              }
           putpixel(i,y,newColor);
           i++;
          }
        if(spanNeedFill)
         {span->y=y;
          span->xLeft=xLeft;
          span->xRight=i-1;
          PushStack(s,*span);    /*将区段压入堆栈*/
isLeftEndSet=false;
          spanNeedFill=false;
         }
        while(getpixel(i,y)!=oldColor)
          i++;
        }

        /*end of while (i<xRight)*/
   /*处理下面的扫描线*/

        /*y=y-2;*/
        /* ->->->->->-> */
   } /*end of while(!isStackEmpty())*/
 }/*end of ScanLineBoundaryFill4()*/
 void ScanLineFill3(int x,int Y,int oldColor,int newColor)
{ int xLeft,xRight,y,i;
 bool isLeftEndSet,spanNeedFill;
 SElemType *span;
  SqStack *s;
 /*填充并确定种子点(x,y)所在的区段*/
 i=x; y=Y;
 while(getpixel(i,y)==oldColor)  /*向右填充*/
    {putpixel(i,y,newColor);
    i++;
    }
 span->xRight=i-1;   /*确定区段右边界*/
 i=x-1;
 while(getpixel(i,y)==oldColor)  /*向左填充*/
    {putpixel(i,y,newColor);
    i--;
    }
 span->xLeft=i+1;   /*确定区段左边界*/
 /*初始化*/
 SetStackEmpty(s);
 span->y=y;
 PushStack(s,*span); /*将前面生成的区段压入堆栈*/
 while(!IsStackEmpty(s)) /*终止判断*/
   {/*出栈*/
    PopStack(s,span);
    /*处理上面扫描线*/
    y=span->y-1;
    xRight=span->xRight;
    i=span->xLeft;
    isLeftEndSet=false;
    while(getpixel(i,y)==oldColor)  /*向左填充*/
       {
        putpixel(i,y,newColor);
        i--;
        }
    if(i!=span->xLeft)  /*确定区段左边界*/
      {isLeftEndSet=true;
       xLeft=i+1;
       }
    i=span->xLeft;
    while(i<=xRight)
       {spanNeedFill=false;
        while(getpixel(i,y)==oldColor) /*向右填充*/
          {if(!spanNeedFill)
             {spanNeedFill=true;
             if(!isLeftEndSet)
               {isLeftEndSet=true;
                xLeft=i;
                }
              }
           putpixel(i,y,newColor);
           i++;
          }
        if(spanNeedFill)
         {span->y=y;
          span->xLeft=xLeft;
          span->xRight=i-1;
          PushStack(s,*span);    /*将区段压入堆栈*/
          isLeftEndSet=false;
          spanNeedFill=false;
         }
        while(getpixel(i,y)!=oldColor)
          i++;
        }

        /*end of while (i<xRight)*/
   /*处理下面的扫描线*/

        /*y=y-2;*/
        /* ->->->->->-> */
   } /*end of while(!isStackEmpty())*/
 }/*end of ScanLineBoundaryFill4()*/

void GetST(float x[5],float y[5],float a[5],float b[5],float radius)
{int i;
float r;
 for(i=0;i<5;i++)
 {x[i]=radius*cos(i*0.4*pi+0.05*pi)-radius*sin(i*0.4*pi+0.05*pi);
  y[i]=radius*sin(i*0.4*pi+0.05*pi)+radius*cos(i*0.4*pi+0.05*pi);
 }
 r=sin(0.1*pi)*radius/sin(126.0/180.0*pi);
  for(i=0;i<5;i++)
 {a[i]=r*cos(i*0.4*pi+0.25*pi)-r*sin(i*0.4*pi+0.25*pi);
  b[i]=r*sin(i*0.4*pi+0.25*pi)+r*cos(i*0.4*pi+0.25*pi);
  }
  /*得到五角星的10个顶点*/
  }

 /*平移旋转*/

void move(float x[5],float y[5],float a[5],float b[5],float cx,float cy)
{ int i;
 for(i=0;i<5;i++)
 {x[i]=x[i]+cx;a[i]=a[i]+cx;
  y[i]=y[i]+cy;b[i]=b[i]+cy;
 }
}

void rotate(float x[5],float y[5],float a[5],float b[5],float theta)
{ int i;
   float t1,t2;
 for(i=0;i<5;i++)
 {t1=x[i];
 x[i]=x[i]*cos(theta)-y[i]*sin(theta);
  y[i]=t1*sin(theta)+y[i]*cos(theta);
  t2=a[i];
  a[i]=a[i]*cos(theta)-b[i]*sin(theta);
  b[i]=t2*sin(theta)+b[i]*cos(theta);
 }
}
 void CreatET(float x[5],float y[5],float a[5],float b[5])
 {int n;
 Edge *e,*h;
 n=(int)(y[3]+0.5);
 e=(Edge*)malloc(sizeof(Edge));
 e->ymax=(int)(b[3]+0.5);e->x=x[3];e->deltax=(a[3]-x[3])/(b[3]-y[3]);
 h=(Edge*)malloc(sizeof(Edge));
 h->ymax=(int)(b[2]+0.5);h->x=x[3];h->deltax=(a[2]-x[3])/(b[3]-y[3]);
 e->nextEdge=h;h->nextEdge=NULL;
 EL[n]=e;


 n=(int)(b[2]+0.5);
 e=(Edge*)malloc(sizeof(Edge));
 e->ymax=(int)(b[1]+0.5);e->x=x[2];e->deltax=(a[1]-x[2])/(b[1]-y[2]);
 h=(Edge*)malloc(sizeof(Edge));
 h->ymax=(int)(b[4]+0.5);h->x=x[4];h->deltax=(a[4]-x[4])/(b[4]-y[4]);
 e->nextEdge=h;h->nextEdge=NULL;
 EL[n]=e;


  n=(int)(b[1]+0.5);
e=(Edge*)malloc(sizeof(Edge));
e->ymax=(int)(y[1]+0.5);e->x=a[1];e->deltax=(x[1]-a[1])/(y[1]-b[1]);
 h=(Edge*)malloc(sizeof(Edge));
 h->ymax=(int)(y[0]+0.5);h->x=a[4];h->deltax=(x[0]-a[4])/(y[0]-b[4]);
 e->nextEdge=h;h->nextEdge=NULL;
 EL[n]=e;


  n=(int)(b[0]+0.5);
 e=(Edge*)malloc(sizeof(Edge));
 e->ymax=(int)(y[1]+0.5);e->x=a[0];e->deltax=(x[1]-a[0])/(y[1]-b[0]);
 h=(Edge*)malloc(sizeof(Edge));
 h->ymax=(int)(y[0]+0.5);h->x=a[0];h->deltax=(x[0]-a[0])/(y[0]-b[0]);
 e->nextEdge=h;h->nextEdge=NULL;
 EL[n]=e;
 }

 void Free(float y[5],float b[5])
 {int n;
 n=(int)(y[3]+0.5);
 EL[n]=NULL;
 n=(int)(b[2]+0.5);
 EL[n]=NULL;
 n=(int)(b[1]+0.5);
 EL[n]=NULL;
 n=(int)(b[0]+0.5);
 EL[n]=NULL;
}

 void Fillin(Edge *AEL,int bottom,int top )
 {Edge *e;
  Edge *p,*q;
  int n,m;
 AEL=(Edge*)malloc(sizeof(Edge));AEL->x=-1;
AEL->nextEdge=NULL;
for(n=bottom;n<top;n++)
{p=EL[n];
 while(p)
 {
e=AEL; q=AEL->nextEdge;
while(q)
  {if(p->x<q->x)break;
   q=q->nextEdge;
   e=e->nextEdge;}
   q=p->nextEdge;
   p->nextEdge=e->nextEdge;
   e->nextEdge=p;
   p=q;

}
q=AEL->nextEdge;
p=AEL;q=AEL->nextEdge;
m=1;

 while(q)
 { if(q->ymax==n)
   {p->nextEdge=q->nextEdge;
   e=q;
   q=q->nextEdge;free(e);
   }
 else{
   if(p!=AEL&&m%2==0)
   {line((int)(p->x+0.5),n,(int)(q->x+0.5),n);
    p->x+=p->deltax;
    q->x+=q->deltax;}
    p=p->nextEdge;
    q=q->nextEdge;
    m++;}
 }
 }
 }


int  Edge_code(point node,point start,point end)
 {int w,v,s=0;
 point p;
 float x0,y0;
   if(start.x>node.x&&start.y>node.y) v=0;
  if(start.x<=node.x&&start.y>node.y) v=1;
  if(start.x<=node.x&&start.y<=node.y) v=2;
  if(start.x>node.x&&start.y<=node.y) v=3;

   if(end.x>node.x&&end.y>node.y) w=0;
  if(end.x<=node.x&&end.y>node.y) w=1;
  if(end.x<=node.x&&end.y<=node.y) w=2;
  if(end.x>node.x&&end.y<=node.y) w=3;
   s=w-v;
   if(s==2||s==-2)
   {
      x0=(end.x+start.x)/2;
      y0=(end.y+start.y)/2;
      p.x=x0;p.y=y0;
   s=Edge_code(node,start,p)+Edge_code(node,p,end);
   }
   if(s==3)  s=-1;
   if(s==-3) s=1;
   return s;

 }
  point Getmax(point points[10])
  { int i;
   float maxx,maxy;
   point p;
  maxx=points[0].x;maxy=points[0].y;
  for(i=1;i<10;i++)
  {if(points[i].x>maxx) maxx=points[i].x;
    if(points[i].y>maxy) maxy=points[i].y;}
  p.x=maxx;p.y=maxy;
  return p;
}

point Getmin(point points[10])
{int i;
   float minx,miny;
   point p;
  minx=points[0].x;miny=points[0].y;
  for(i=1;i<10;i++)
  {if(points[i].x<minx) minx=points[i].x;
    if(points[i].y<miny) miny=points[i].y;}
  p.x=minx;p.y=miny;
  return p;

}

void BoundaryFill4(int x,int y)
{int color;
  color=getpixel(x,y);
if(color!=YELLOW)
 {putpixel(x,y,YELLOW);
  BoundaryFill4(x,y+1);
  BoundaryFill4(x,y-1);
  BoundaryFill4(x-1,y);
  BoundaryFill4(x+1,y);
 }
}


main()
{int n,m ,i,j;
 float x[5],y[5],a[5],b[5],r;
  Edge *AEL;
  point node, points[10],p1,p2;
initgr(); /* BGI初始化 */
 setbkcolor(RED);
 setcolor(YELLOW);
  setbkcolor(RED);
 GetST(x,y,a,b,50);
move(x,y,a,b,100,120);

n=(int)(y[3]+0.5);
  m=(int)(y[1]+0.5);
   CreatET(x,y,a,b);
   Fillin(AEL,n,m);
 /*用活化边表法填充*/



  GetST(x,y,a,b,15);
  rotate(x,y,a,b,pi*0.1);
  move(x,y,a,b,210,40);
   for(i=0;i<4;i++)
  {line(x[i],y[i],a[i],b[i]);
   line(a[i],b[i],x[i+1],y[i+1]);
}
  line(x[4],y[4],a[4],b[4]);
  line(a[4],b[4],x[0],y[0]);
  ScanLineFill3(210,40,0,YELLOW);
  ScanLineFill4(210,41,0,YELLOW);
  /*区域填充的扫描线法*/


 
  for(n=15;n>0;n--){
    GetST(x,y,a,b,n);
   rotate(x,y,a,b,-pi*0.1);
   move(x,y,a,b,260,100);
  for(i=0;i<4;i++)
  {line(x[i],y[i],a[i],b[i]);
   line(a[i],b[i],x[i+1],y[i+1]);
  }
  line(x[4],y[4],a[4],b[4]);
  line(a[4],b[4],x[0],y[0]);}
 /*向内复制边法，自创*/




 GetST(x,y,a,b,15);
 rotate(x,y,a,b,-pi*0.05);
  move(x,y,a,b,260,170);
 for(i=0;i<4;i++)
  {line(x[i],y[i],a[i],b[i]);
   line(a[i],b[i],x[i+1],y[i+1]);
}
  line(x[4],y[4],a[4],b[4]);
  line(a[4],b[4],x[0],y[0]);


  for(i=0;i<10;i++)
{if(i%2==0)
  {points[i].x=x[i/2];points[i].y=y[i/2];
  }
  else
   {points[i].x=a[i/2];points[i].y=b[i/2];
 }
  }
 p1=Getmax(points);p2=Getmin(points);
for(n=p2.y;n<p1.y;n++)
   for(m=p2.x;m<p1.x;m++)
   if(getpixel(m,n)!=YELLOW)
   {node.x=m;node.y=n; j=Edge_code(node,points[0],points[1]);
    for(i=1;i<9;i++)
   j+=Edge_code(node,points[i],points[i+1]);
     j+=Edge_code(node,points[9],points[0]);
   if(j==4||j==-4) putpixel(m,n,YELLOW);}

  /*编码算法*/





   GetST(x,y,a,b,15);
    rotate(x,y,a,b,pi*0.1);
  move(x,y,a,b,210,230);
   for(i=0;i<4;i++)
  {line(x[i],y[i],a[i],b[i]);
   line(a[i],b[i],x[i+1],y[i+1]);

}
  line(x[4],y[4],a[4],b[4]);
  line(a[4],b[4],x[0],y[0]);
BoundaryFill4(210,230);
 /*区域填充的递归算法*/
 getch(); /* 暂停一下，看看前面绘图代码的运行结果 */
 closegr(); /* 恢复TEXT屏幕模式 */
}