计算机图形学实验报告

1、计算机图形学实验报告第一次 目录1.实验目的32.实验内容32.1.Bresenham画直线算法32.2.Bresenham画圆算法32.3.Bresenham画椭圆算法42.4.多边形阴影线填充算法52.5.多边形扫描转换算法53.实验步骤63.1.程序设计63.1.1.画线段73.1.2.画圆83.1.3.画椭圆103.1.4.多边形阴影线填充113.1.5.多边形区域扫描填充153.2.程序运行结果243.2.1.画直线243.2.2.画圆253.2.3.画椭圆253.2.4.多边形阴影线填充263.2.5.多边形区域扫描填充274.实验总结281.实验目的仅调用画点函数，设计实现一个图

2、形函数库，具有以下功能：1. 画线段。2. 画圆弧。3. 画椭圆。4. 画多边形。5. 多边形区域的阴影线填充。6. 多边形扫描转换算法：颜色填充。实验环境：DevC+实验语言：C语言2.实验内容 此次实验目的采用了以下算法实现。2.1.Bresenham画直线算法根据直线的斜率确定选择X或者Y方向作为计长方向, 在此方向上每次递增一个单位步长(或者一个像素单位), 另一个方向上是否同时产生一个单位增量由一个计算量很小的判别式来判断。(以斜率在01之间的直线段为例)这种情况下, 选择X方向为计长方向，即增量dx=1。如下图所示,设Pi(xi,yi)是已选定的离直线最近的像素, 现在要决定Pi+

3、1是T还是S。若d=0.5, 则应选T。(m=y/x)令e=d-0.5(初值为m-0.5), 即有：e=0时，选Pi+1(xi+1,yi+1), 更新e=e+m-1。2.2.Bresenham画圆算法与Bresenham直线生成算法一样, 其基本方法是从一个起点出发, 利用判别式选择下一个显示点。判别式的值通过简单计算获得, 其符号用作判断。（以位于第一象限的1/8圆弧为例）此算法在每一步都选择一个离开理想圆周最近的点Pi(xi,yi)，使其误差项|D(Pi)|=|xi2 +yi2-R2|在每一步都是极小值。设Pi-1(xi-1,yi-1)已被选定为最靠近圆弧的点，下一步x=xi-1+1时,

4、参见下图：要决定T还是S更接近理想的圆弧,令D(S)=(xi-1+1)2+yi-12-R2D(T)=(xi-1+1)2+(yi-1-1)2-R2显然,|D(S)|=|D(T)|时，应该取T点，反之则取S点。即若令di=|D(S)|-|D(T)|则di=0，选择T点，否则选取S点。结论：d1=3-2R；如果di=0，选Pi(xi,yi-1-1)，将yi=yi-1-1代入求di+1：di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+102.3.Bresenham画椭圆算法与Bresenham直线和圆生成算法原理一样，但是椭圆的生成的过程中要分为上半部与下半部的情况讨论。在生成

5、椭圆上部区域时，以x轴为步进方向，如图所示：x每步进一个单位，就需要在判断y保持不变还是也步进减1，bresenham算法定义判别式为：di=d1-d2如果di0，则取P1为下一个点，否则，取P2为下一个点。采用判别式di，使得判别式规约为全整数运算，算法效率得到了很大的提升。根据椭圆方程，可以计算出d1和d2分别是：d1=a2(yi2-y2)d2=a2(y2-yi+12)以(0,b)作为椭圆上部区域的起点，将其代入判别式di可以得到如下递推关系：当di=0时，di+1=di+2b2(2xi+3)-4a2(yi-1)d1= 2b22a2b+a2在生成椭圆下部区域时，以y轴为步进方向，如图所示：

6、y每步进减一个单位，就需要在判断x保持不变还是步进加一个单位，对于下部区域，计算出d1和d2分别是：d1=b2(xi+12-x2)d2=b2(x2-xi2)以(xp,yp)作为椭圆下部区域的起点，将其代入判别式di可以得到如下递推关系：当di=0时，di+1= di+2b2(xi+1)-4a2(y-1)+2a2+b2d1=b2(xp+1)2+b2xp2-2a2b2+2a2(yp-1)22.4.多边形阴影线填充算法算法步骤如下：a.对于MN条棱边, 计算每一条棱边L i 的两个端点分别按阴影线斜率k=tg引线得到的截距, 其中较小值放在B(1,i)中, 较大值放在B(2,i)中。b.求出Bmin

7、=minB(1,i)，Bmax=maxB(2,i)，i=1,2,.,MN。c.取第一条阴影线截距为b=Bmin+b(b=h/|cos|)。d.初始化存放阴影线与各棱边交点的数组D(2,MN)；判断当前阴影线与各棱边是否有交点, 若存在则计算出交点坐标并存入D数组；按X/Y坐标排列D数组中的交点并生成阴影线段；取下一条阴影线b=b+b, 若bBmax转d继续。2.5.多边形扫描转换算法算法步骤如下：a. 非极值奇点的预处理。（极值奇点算作2个交点；非极值奇点算作1个交点）b. 建立边的分类表ET。c. 取扫描线初始值y为ET表中所列的最小y坐标值。d. 边的活化链表AEL初始化, 使其为空。e.

8、 重复下列操作, 直至ET表和AEL表都变成空：e1. 把ET表中纵坐标为y的链取下, 与AEL表合并，并保持AEL表中元素按x域值升序排列，x相同时，按x域。e2. 对于当前扫描线y, 从左到右, 将AEL表中元素两两配对,按每对两个x域定义的区段填充所需要的像素值。e3. 将AEL表中满足ymax=y的元素删除；e4. 对于仍留在AEL表中的元素, 求下一条扫描线与边的交点, 即x域累加x：x=x+ x。e5. 取下一条扫描线作为当前扫描线：y=y+1。3.实验步骤3.1.程序设计函数库的声明部分如下：#include #include #include #include #define

9、PI 3.1416#define DEF -10000#define MAX 100struct listint ymax;double x;double dx;struct list *next;struct headint num;struct list *start;struct list *end;typedef struct list L;typedef struct head H;typedef L * LP;void DrawLine(HDC hdc,int x1,int y1,int x2,int y2,COLORREF color);void DrawCircle(HDC h

10、dc,int xc,int yc,int r,COLORREF color);void DrawEllipse(HDC hdc,int xc,int yc,int a,int b,COLORREF color);void DrawPolygon(HDC hdc,int pMAX,int point_num,int in_num,COLORREF color);void PolygonShadow(HDC hdc,int pMAX,int point_num,int in_num,double a,int h,COLORREF color);void PolygonFill(HDC hdc,in

11、t pMAX,int point_num,int in_num,COLORREF color);void PlotC(HDC hdc,int x,int y,int xc,int yc,COLORREF color);void PlotE(HDC hdc,int x,int y,int xc,int yc,COLORREF color);int LineIntersection(double k,int b,int x1,int y1,int x2,int y2);void SortPoint(int dMAX,int d_num);void PreProcessing(int pMAX,in

12、t point_num,int in_num);int CreateET(int pMAX,int point_num,int in_num,int ymin,H ET);LP InsertList(int x1,int y1,int x2,int y2,LP h,LP *t);LP DeleteList(LP head,LP current,LP *tail);LP SortAEL(LP head);各个函数与数据结构的定义见下文。3.1.1.画线段将2.1里提到的算法思想推广到所有象限，设计函数void DrawLine(HDC hdc,int x1,int y1,int x2,int y

13、2,COLORREF color)其中参数意义如下：HDC hdc 画图界面int x1 线段一端横坐标int y1 线段一端纵坐标int x2 线段一端横坐标int y2 线段一端横坐标COLORREF color 直线的颜色该部分实现代码如下：void DrawLine(HDC hdc,int x1,int y1,int x2,int y2,COLORREF color)int i,interchange,s1,s2;int x,y,dx,dy,dxy,d;x=x1;y=y1;dx=abs(x2-x1);dy=abs(y2-y1);if(x2-x10)s1=1;elses1=-1;if(y

14、2-y10)s2=1;elses2=-1;if(dydx)dxy=dx;dx=dy;dy=dxy;interchange=1;elseinterchange=0;d=2*dy-dx;for(i=1;i=0)if(interchange=1)x=x+s1;elsey=y+s2;d=d-2*dx;if(interchange=1)y=y+s2;elsex=x+s1;d=d+2*dy;3.1.2.画圆将2.2中提到的算法思想根据圆的对称性推广到所有象限，其中函数void PlotC(HDC hdc,int x,int y,int xc,int yc,COLORREF color)是根据圆的对称性画8

15、个点的辅助函数。其参数意义如下：HDC hdc 画图界面int x 当前扫描的点相对圆心的横坐标距离int y 当前扫描的点相对圆心的纵坐标距离int xc 圆心横坐标int yc 圆心纵坐标COLORREF color 圆的颜色执行画圆的函数为void DrawCircle(HDC hdc,int xc,int yc,int r,COLORREF color)其参数意义如下：HDC hdc 画图界面int xc 圆心横坐标int yc 圆心纵坐标int r 圆的半径COLORREF color 圆的颜色该部分实现代码如下：void PlotC(HDC hdc,int x,int y,int

16、xc,int yc,COLORREF color)SetPixel(hdc,xc+x,yc+y,color);SetPixel(hdc,xc+x,yc-y,color);SetPixel(hdc,xc-x,yc+y,color);SetPixel(hdc,xc-x,yc-y,color);SetPixel(hdc,xc+y,yc+x,color);SetPixel(hdc,xc+y,yc-x,color);SetPixel(hdc,xc-y,yc+x,color);SetPixel(hdc,xc-y,yc-x,color);void DrawCircle(HDC hdc,int xc,int

17、yc,int r,COLORREF color)int x,y,d;y=r;d=3-2*r;x=0;while(x=y)PlotC(hdc,x,y,xc,yc,color);if(d0)d=d+4*x+6;elsed=d+4*(x-y)+10;y-;x+;3.1.3.画椭圆将2.3中提到的算法思想根据椭圆的对称性推广到所有象限，其中函数void PlotE(HDC hdc,int x,int y,int xc,int yc,COLORREF color)是根据椭圆的对称性画4个点的辅助函数。其参数意义如下：HDC hdc 画图界面int x 当前扫描的点相对椭圆心的横坐标距离int y 当前扫

18、描的点相对椭圆心的纵坐标距离int xc 椭圆心横坐标int yc 椭圆心纵坐标COLORREF color 椭圆的颜色执行画椭圆的函数为void DrawEllipse(HDC hdc,int xc,int yc,int a,int b,COLORREF color)其参数意义如下：HDC hdc 画图界面int xc 椭圆心横坐标int yc 椭圆心纵坐标int a 椭圆的长半轴长int b 椭圆的短半轴长COLORREF color 圆的颜色该部分实现代码如下：void PlotE(HDC hdc,int x,int y,int xc,int yc,COLORREF color)SetP

19、ixel(hdc,xc+x,yc+y,color);SetPixel(hdc,xc+x,yc-y,color);SetPixel(hdc,xc-x,yc+y,color);SetPixel(hdc,xc-x,yc-y,color);void DrawEllipse(HDC hdc,int xc,int yc,int a,int b,COLORREF color)int x,y,d,e;y=b;d=2*b*b-2*b*a*a+a*a;x=0;PlotE(hdc,x,y,xc,yc,color);e=(int)(double)(a*a)/sqrt(double)(a*a+b*b);while(x=

20、e)if(d=0)PlotE(hdc,x,y,xc,yc,color);y-;if(d0)x+;d=d-2*a*a*y-a*a+2*b*b*x+2*b*b;elsed=d-2*a*a*y-a*a;3.1.4.多边形阴影线填充程序设计基于2.4中的算法原理。该算法首先要画出多边形，执行画多边形的函数为void DrawPolygon(HDC hdc,int pMAX,int point_num,int in_num,COLORREF color)该函数遍历了多边形的各个定点，通过调用画线段函数void DrawLine(HDC hdc,int x1,int y1,int x2,int y2,CO

21、LORREF color)来达到效果（画线段函数详见3.1.1）。该画多边形函数的参数意义如下：HDC hdc 画图界面int pMAX 储存多边形各个定点的数组int point_num 多边形的总定点数int in_num 多边形的内部定点数COLORREF color 多边形的颜色在执行多边形阴影填充的过程中需要求填充阴影线与多边形棱边的交点，使用到函数int LineIntersection(double k,int b,int x1,int y1,int x2,int y2)该函数的参数意义如下：double k 填充阴影线的斜率int b 填充阴影线的截距int x1 该棱边的一个

22、定点的横坐标int y1 该棱边的一个定点的纵坐标int x2 该棱边另一个定点的横坐标int y2 该棱边另一个定点的纵坐标返回值(类型int) 交点的横坐标该过程还需要对一条阴影线与多边形产生的多个交点按照X坐标升序进行排列，使用到函数void SortPoint(int dMAX,int d_num)排序原理为简单的选择排序。该函数的参数意义如下：int dMAX 储存交点坐标的数组int d_num 交点个数进行多边形阴影线填充的主体函数为void PolygonShadow(HDC hdc,int pMAX,int point_num,int in_num,double a,int

23、h,COLORREF color)该函数的参数意义如下：HDC hdc 画图界面int pMAX 储存多边形各个定点的数组int point_num 多边形的总定点数int in_num 多边形的内部定点数double a 阴影线与水平线的夹角int h 阴影线之间的间隔COLORREF color 填充阴影线的颜色该部分实现代码如下：void DrawPolygon(HDC hdc,int pMAX,int point_num,int in_num,COLORREF color)int i;for(i=0;i=point_num-1-in_num;i+)if(i=point_num-1-in

24、_num)DrawLine(hdc,p0i,p1i,p00,p10,color);elseDrawLine(hdc,p0i,p1i,p0i+1,p1i+1,color);for(i=point_num-in_num;i=point_num-1;i+)if(i=point_num-1)DrawLine(hdc,p0i,p1i,p0point_num-in_num,p1point_num-in_num,color);elseDrawLine(hdc,p0i,p1i,p0i+1,p1i+1,color);int LineIntersection(double k,int b,int x1,int y

25、1,int x2,int y2)int b1,b2,min,max,x;b1=y1-(int)(0.5+k*(double)x1);b2=y2-(int)(0.5+k*(double)x2);if(b1=min&b=max)x=(x1*y2-y1*x2+b*(x2-x1)/(y2-y1)-(int)(0.5+k*(double)(x2-x1);return x;elsereturn DEF;void SortPoint(int dMAX,int d_num)int i,j,min,tempx,tempy;for(i=0;i=d_num-2;i+)min=i;for(j=i+1;j=d_num-

26、1;j+)if(d0jd0min)min=j;tempx=d0i;tempy=d1i;d0i=d0min;d1i=d1min;d0min=tempx;d1min=tempy;void PolygonShadow(HDC hdc,int pMAX,int point_num,int in_num,double a,int h,COLORREF color)DrawPolygon(hdc,p,point_num,in_num,color);/按要求画出多边形 int i,db,bMAX;double k;k=tan(a);db=(int)(0.5+(double)h/cos(a);for(i=0;

27、i=point_num-1;i+)bi=(p1i-p10)-(int)(0.5+k*(double)(p0i-p00);/对于每个顶点作阴影线求截距 int bmax,bmin;bmax=b0;bmin=b0;for(i=1;ibmax)bmax=bi;if(bibmin)bmin=bi;int bc,d2MAX,d_num;bc=bmin+db;while(bc=bmax)/扫描过程 d_num=0;for(i=0;i=point_num-1-in_num;i+)/求该条阴影线与多边形各条外部棱边的交点 if(i=point_num-1-in_num)d0d_num=LineIntersec

28、tion(k,bc,p0i-p00,p1i-p10,p00-p00,p10-p10);elsed0d_num=LineIntersection(k,bc,p0i-p00,p1i-p10,p0i+1-p00,p1i+1-p10);if(d0d_num!=DEF)d1d_num=(int)(0.5+k*(double)d0d_num)+bc;d0d_num=d0d_num+p00;d1d_num=d1d_num+p10;d_num+;for(i=point_num-in_num;i=point_num-1;i+)/求该条阴影线与多边形各条内部棱边的交点 if(i=point_num-1)d0d_n

29、um=d0d_num=LineIntersection(k,bc,p0i-p00,p1i-p10,p0point_num-in_num-p00,p1point_num-in_num-p10);elsed0d_num=d0d_num=LineIntersection(k,bc,p0i-p00,p1i-p10,p0i+1-p00,p1i+1-p10);if(d0d_num!=DEF)d1d_num=(int)(0.5+k*(double)d0d_num)+bc;d0d_num=d0d_num+p00;d1d_num=d1d_num+p10;d_num+;SortPoint(d,d_num);/将交

30、点按照X坐标升序排列 for(i=0;id_num;i=i+2)/将交点两两组合填充中间区域 DrawLine(hdc,d0i,d1i,d0i+1,d1i+1,color);bc=bc+db;/扫描下一条阴影线 3.1.5.多边形区域扫描填充程序设计基于2.5中的算法原理。算法首先要对多边形的各个点进行预处理，使用到函数void PreProcessing(int pMAX,int point_num,int in_num)该函数的参数意义如下：int pMAX 储存多边形各个定点的数组int point_num 多边形的总定点数int in_num 多边形的内部定点数之后算法要创建ET表与A

31、EL表。程序的数据结构定义如下：struct listint ymax;double x;double dx;struct list *next;struct headint num;struct list *start;struct list *end;typedef struct list L;typedef struct head H;typedef L * LP;其中，list结构中含有ymax、x、x域以及指向下一个节点的指针，作为AEL表以及ET表中的链表部分。而head结构的num用于标识ET表中的类号或者AEL表中的扫描线纵坐标，start和end分别为相应链表的头结点和尾节点

32、，该结构作为AEL表以及ET表中每个类的头部。创建ET表使用到函数int CreateET(int pMAX,int point_num,int in_num,int ymin,H ET)该函数的参数意义如下：int pMAX 储存多边形各个定点的数组int point_num 多边形的总定点数int in_num 多边形的内部定点数int ymin 扫描线起点纵坐标H ET 储存ET表表头部分的数组返回值(类型int) ET表中多边形棱边信息的数量在创建ET表的过程中，涉及到链表的插入操作，使用到函数LP InsertList(int x1,int y1,int x2,int y2,LP h

33、,LP *t)该函数的参数意义如下：int x1 当前棱边的一个定点的横坐标int y1 当前棱边的一个定点的纵坐标int x2 当前棱边另一个定点的横坐标int y2 当前棱边另一个定点的纵坐标LP h ET表中该类链表的头结点LP *t ET表中该类链表的尾结点返回值(类型LP) 更新操作后的ET表中该类链表的头结点算法执行过程中要按照AEL表中的x域以及x域进行升序排列，故需要涉及链表的排序操作，使用到函数LP SortAEL(LP head)排序原理为简单的选择排序。该函数的参数意义如下：LP head 待排序AEL表的头结点返回值(类型LP) 排序后AEL表的头结点算法执行过程中要删

34、去AEL表中ymax=y的成员，故需要涉及链表的删除操作，使用到函数LP DeleteList(LP head,LP current,LP *tail);该函数的参数意义如下：LP head 待操作AEL表的头结点LP current 待删除节点LP *tail 待操作AEL表的尾结点返回值(类型LP) 删除操作后AEL表的头结点进行多边形区域扫描填充算法的主体函数为void PolygonFill(HDC hdc,int pMAX,int point_num,int in_num,COLORREF color)该函数的参数意义如下：HDC hdc 画图界面int pMAX 储存多边形各个定点

35、的数组int point_num 多边形的总定点数int in_num 多边形的内部定点数COLORREF color 填充的颜色该部分实现代码如下：void PreProcessing(int pMAX,int bMAX,int point_num,int in_num)int i;for(i=0;i=point_num-1-in_num;i+)if(i=point_num-1-in_num)if(p1ip10)b0i=-1;b10=1;else if(p1i=p10)b0i=0;b10=0;elseb0i=1;b10=-1;elseif(p1ip1i+1)b0i=-1;b1i+1=1;el

36、se if(p1i=p1i+1)b0i=0;b1i+1=0;elseb0i=1;b1i+1=-1;for(i=point_num-in_num;i=point_num-1;i+)if(i=point_num-1)if(p1ip1point_num-in_num)b0i=-1;b1point_num-in_num=1;else if(p1i=p1point_num-in_num)b0i=0;b1point_num-in_num=0;elseb0i=1;b1point_num-in_num=-1;elseif(p1ip1i+1)b0i=-1;b1i+1=1;else if(p1i=p1i+1)b0

37、i=0;b1i+1=0;elseb0i=1;b1i+1=-1;int CreateET(int pMAX,int point_num,int in_num,int ymin,H ET)int i,down,e_num,b2MAX;e_num=0;PreProcessing(p,b,point_num,in_num);for(i=0;i=point_num-1-in_num;i+)if(i=point_num-1-in_num)if(p1i!=p10)if(p1ip10)down=p1i;if(b0i*b1i=-1)down+;elsedown=p10;if(b00*b10=-1)down+;E

38、Tdown-ymin.start=InsertList(p0i-p00,p1i-p10,p00-p00,p10-p10,ETdown-ymin.start,&ETdown-ymin.end);e_num+;elseif(p1i!=p1i+1)if(p1ip1i+1)down=p1i;if(b0i*b1i=-1)down+;elsedown=p1i+1;if(b0i+1*b1i+1=-1)down+;ETdown-ymin.start=InsertList(p0i-p00,p1i-p10,p0i+1-p00,p1i+1-p10,ETdown-ymin.start,&ETdown-ymin.end

39、);e_num+;for(i=point_num-in_num;i=point_num-1;i+)if(i=point_num-1)if(p1i!=p1point_num-in_num)if(p1ip1point_num-in_num)down=p1i;if(b0i*b1i=-1)down+;elsedown=p1point_num-in_num;if(b0point_num-in_num*b1point_num-in_num=-1)down+;ETdown-ymin.start=InsertList(p0i-p00,p1i-p10,p0point_num-in_num-p00,p1point

40、_num-in_num-p10,ETdown-ymin.start,&ETdown-ymin.end);e_num+;elseif(p1i!=p1i+1)if(p1iy2)n-ymax=y1;n-x=(double)x2;elsen-ymax=y2;n-x=(double)x1;n-dx=(double)(x2-x1)/(double)(y2-y1);n-next=NULL;if(h=NULL)h=n;else(*t)-next=n;(*t)=n;return h; LP SortAEL(LP head)LP c1=NULL,c2=NULL,min=NULL,temp=NULL;for(c1=

41、head;c1!=NULL;c1=c1-next)min=c1;for(c2=c1-next;c2!=NULL;c2=c2-next)if(c2-xx)min=c2;else if(c2-x=min-x)if(c2-dxdx)min=c2;temp=(LP)malloc(sizeof(L);temp-next=NULL;temp-ymax=c1-ymax;temp-x=c1-x;temp-dx=c1-dx;c1-ymax=min-ymax;c1-x=min-x;c1-dx=min-dx;min-ymax=temp-ymax;min-x=temp-x;min-dx=temp-dx;free(temp);return head;LP DeleteList(LP head,LP current,LP *tail)LP c=NULL;if(head=current)head=head-next;elsec=head;while(c-next!=current)c=c-next;c-next=current-next;if(current-next=NULL)(*tail)=c;current-next=NULL;free(current);return head;void PolygonFill(HDC hdc,int pMAX,int point_