上机实验3：图形填充与裁剪算法的具体实现.doc

信息与计算科学专业基础课Computer Graphics Report Of course experiment 计算机图形学课程实验 报 告实验题目 填充与裁剪算法的实现 班 级 计算091 姓 名 王姣 学 号 3090811002 指导教师 胡钢 日 期 2012-5-3 西安理工大学理学院应用数学系二零零八年春季学期实验3填充与裁剪算法的实现实验说明试验目的： 掌握图形填充与裁剪算法的基本思想，并能上机编程实现相应的算法。试验地点： 教九楼401 数学系机房实验要求(Direction): 1.每个学生单独完成；2.开发语言为TurboC或C+，也可使用其它语言；3.请在自己的实验报告上写明姓名、学号、班级；4.每次交的实验报告内容包括：题目、试验目的和意义、程序制作步骤、主程序、运行结果图以及参考文件；5. 自己保留一份可执行程序,考试前统一检查和上交。实验内容:实验题一1.1实验题目上机编程序实现多边形区域填充算法。要求：(1)多边形要求采用顶点表示，且顶点的个数和顶点坐标可以随机输入；(2)要求先画出多边形，画出多边形的同时要求标明各顶点坐标；(3)水平扫描线的顺序和填充颜色可以自由选择。1.2实验目的和意义1.熟悉并掌握编程实现多边形的画法2.学会画出多边形的同时要求标明各顶点坐标的算法如何在程序中实现3.了解如何对多边形进行扫描变换4.了解如何对多边形进行扫描区域填充1.3程序制作步骤(包括算法的基本思想、流程图、设计步骤等)算法思想：多边形以n, x_array, y_array形式给出，其中x_array，y_array中存着多边形的n个顶点的x, y坐标。扫描线填色算法的基本思想是：用水平扫描线从上到下扫描由点线段构成的多段定义的多边形。每根扫描线与多边形各边产生一系列交点，将这些交点按照x坐标进行排序，将排序后的交点成对取出，作为两个端点，用所需填充的色彩画水平直线。多边形被扫描完毕，则填充结束扫描线算法的实现思想：（1）根据给出的顶点坐标数据，按y递增顺序建立ET表。（2）根据AET指针，使之为空。（3）使yi=ymin（ymin为顶点坐标中最小y值）。（4）反复做下述各步，直至yi=ymax(顶点坐标中y的最大值)或ET或AET为空。1. 将ET表加入到AET中,并保持AET链中的记录按x值增大排序；2. 对扫描线yi依次成对取出AET中xi值,并在每对xi之间填上所要求的颜色或图案；3. 从AET表中删去yi+1的边记录；4. 对保留下来的AET中的每个边记录, x域中的值用xi+1/m代替xi,并重新按x递增排序；5. 使yi+1,以便进入下一轮循环。多边形的填充过程,对于一条扫描线，多边形的填充过程可以分为四个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把所有交点按x值递增顺序排序；（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间；（4）填色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。1.4主程序/*坐标系：屏幕左上角为原点，向下为纵坐标正方向*/*可修改多边形边数polydeflen和多边形按顺时针的顶点定义polydef来改变多边形*/#includegraphics.h/*加入c图形库*/#includestdio.h#includemath.h/*数学库*/#includeconio.h/*键盘控制*/#define MP 100/*多边形边数*/#include#define false 0void edge_mark(int arr2,int value,int polydeflen)/*多边形直线扫描变换*/int by,x,y,ax,ay;/*by为上点纵坐标，x、y当前点横、纵坐标，ax、ay下点横、纵坐标*/int i,j;float k;/*k为直线斜率的倒数*/by=arrpolydeflen-11;for (i=0;i=0) putpixel(x,y,value);getch();/if(getch()=17) exit();/*读入键盘按键*/if(ayay;j-) putpixel(x+(int)(y-j)*k),j,value);else for(j=y+1;jay;j+) putpixel(x-(int)(j-y)*k),j,value);by=y;void edge_mark_fill(int ar2,int value,int polydeflen)/*填充函数*/int i,x,y,inside;/*x像素点横坐标，y像素点纵坐标，inside为判断是否在图形内标志*/int min,max;/*min、max为最小、最大顶点纵坐标*/inside=false;min=ar01;max=ar01;edge_mark(ar,value,polydeflen);for (i=1;imax)max=ari1;if (ari1min) min=ari1;for (y=min;y=max;y+)for(x=0;x=640;x+)if (getpixel(x,y) = value)inside=!(inside);if (inside!=false) putpixel(x,y,value);else putpixel(x,y,0);/getch();if(getch()=17) exit(1);/*读入键盘按键*/void main() char t100;int i,j,polydeflen,value;int polydefMP2;printf(请输入边的条数：n);scanf(%d,&polydeflen);printf(请输入填充颜色：n);scanf(%d,&value);printf(输入坐标：n);for (i=0;ipolydeflen;i+)for (j=0;j2;j+)scanf(%d,&polydefij); int driver,mode;driver=DETECT;/*初始化显示模式参数*/initgraph(&driver,&mode,D:TC);edge_mark_fill(polydef,value,polydeflen);for(i=0;ipolydeflen;i+)sprintf(t,(%d,%d),polydefi0,polydefi1);outtextxy(polydefi0,polydefi1,t);getch();closegraph();1.5运行结果图:实验题二2.1实验题目上机编程实现直线的编码裁剪（Cohen-Sutherland）算法。要求：(1)该程序能实现窗口屏幕上任意一条直线的裁剪；(2)直线段要求可以随机输入；(3)程序在裁剪后不作窗口视图变换；(4)裁剪过程为先画直线再裁剪，且运行结果列出以下3种情况：直线段与窗口有两个交点、直线段与窗口只有一个交点、直线段与窗口无交点。2.2实验目的和意义1.了解裁剪的意义以及对人们日常生活的重大影响2.熟悉并掌握裁剪技术以及如何对线段或多边形作求交运算3. 熟悉并掌握如何通过编程把窗口内每个图形元素都划分为可见部分和不可见部分从而实现裁剪4. 熟悉并掌握直线段的裁剪算法5.了解编码裁剪算法中直线段与窗口的各种关系以及相应的裁剪算法2.3程序制作步骤(包括算法的基本思想、流程图、设计步骤等)算法思想：这种算法利用编码的方法，延长窗口边线，使得它们把包含未经裁剪图形的窗口平面区域分成九个区域，如下图所示：顶边线底边线左边线右边线每个区域用一个4位编码CtCbCrCl来表示，代码中每一位分别是0或1，是按照窗口边线来确定的，下面给出具体的编码规则，其中最右边的位Cl是第一位，依次Cr第二、Cb第三、Ct第四位。则：第一位Cl置为1该端点位于窗口左侧；第二位Cr置为1该端点位于窗口右侧；第三位Cb置为1该端点位于窗口下侧；第四位Ct置为1该端点位于窗口上侧；否则，相应位置置为0Cohen-Sutherland直线裁减算法的步骤如下： （1）当两端点P1(x1,y1)和P2(x2,y2)在区域0000中，即满足点的裁剪不等式： 则两端点代码C1=C2=0表示均在窗口内，应全部保留。（2）当两个端点在窗口边线外的同侧位置，则他们的四位代码中，有一相同位，同时位“1”，显然两个端点代码C1和C2按位与运算 C1&C20 .由此可检查判断直线在窗口外，应全部舍弃。（3）如果直线两端点不满足上述两种情况，不能简单地全部保留或全部舍弃直线时，则需要计算出直线与窗口边线的交点，将直线分段后继续进行检查判断。这样可以逐段地舍弃位于窗口外地线段，保留剩余在窗口内的线段。算法流程图：开 始初始化图形显示模式调用Cohen-Sutherland函数输入线段和视图关闭图形显示模式退 出主程序求得与左边交点坐标利用code进行交点位置判断code=code2code=code1首点是否可见?code1&code20?code1=code2=0?对线段两端点编码变化得到code1和code2 求得与下边交点坐标求得与上边交点坐标求得与右边交点坐标利用交点坐标替换考察端点返回主程序连接所得端点即为所求线段2.4主程序#include graphics.h #include conio.h#include math.h#include stdio.hint w1=90, w2=270, w3=40, w4=160;void clipline(char *a,int &x,int &y,int x1,int y1,int x2,int y2) /求出与区域中各个方向边的交点int xt1=0,yt1=0,xt2=0,yt2=0,xt3=0,yt3=0,xt4=0,yt4=0;if(*a=1)yt1=y1+(y2-y1)*(w1-x1)/(x2-x1);xt1=w1; /求左交点if(*(a+1)=1)yt2=y1+(y2-y1)*(w2-x1)/(x2-x1);xt2=w2; /求右交点if(*(a+2)=1)xt3=x1+(x2-x1)*(w3-y1)/(y2-y1);yt3=w3; /求下交点if(*(a+3)=1)xt4=x1+(x2-x1)*(w4-y1)/(y2-y1);yt4=w4; /求上交点 /有可能会求出两个交点，例如左交点和上交点，必然有一个是超出窗口范围的/必须将其排除if(xt1=90 & yt1=40) x=xt1; y=yt1;if(xt2=90 & yt2=40) x=xt2; y=yt2;if(xt3=90 & yt3=40) x=xt3; y=yt3;if(xt4=90 & yt4=40) x=xt4; y=yt4;void code(int xi, int yi, char *a) /四位编码的实现if(xiw2) *(a+1)=1; /右if(yiw4) *(a+3)=1; /上return;void clipdraw(int x1, int y1, char *a, int x2, int y2, char *b) int x11,y11,x21,y21;int s1=0,s2=0;code(x1,y1,a); /得到直线第一个端点的编码code(x2,y2,b); /得到直线第二个端点的编码 if(*a=0 & *b=0 & *(a+1)=0 & *(b+1)=0 & *(a+2)=0 & *(b+2)=0 & *(a+3)=0 & *(b+3)=0)line(x1,y1,x2,y2); /若两个端点的编码全为0，则直线完全可见else if(a0-48)*(b0-48)+(a1-48)*(b1-48)+(a2-48)*(b2-48)+(a3-48)*(b3-48)=0) /两端点四位编码的逻辑乘为0if(!(a0=0&a1=0&a2=0&a3=0) /第一个端点不在窗口内，求与窗口交点clipline(a,x11,y11,x1,y1,x2,y2);s1=1;if(!(b0=0&b1=0&b2=0&b3=0) /第二个端点不在窗口内，求与窗口交点clipline(b,x21,y21,x1,y1,x2,y2);s2=1;if(s1=1&s2=1) line(x11,y11,x21,y21); /说明两个端点均不在窗口内，直线与窗口有两个交点if(s1=1&s2=0) line(x11,y11,x2,y2); /说明第一个端点不在窗口内，第二个在，直线与窗口有一个交点if(s1=0&s2=1) line(x1,y1,x21,y21); /说明第二个端点不在窗口内，第一个在，直线与窗口有一个交点void main()int x1,y1,x2,y2;printf(请输入直线的两端点坐标：);scanf(%d%d%d%d,&x1,&y1,&x2,&y2);/读入直线两个端点的坐标char a4=0,0,0,0;char b4=0,0,0,0; /分别初始化两个端点的编码数组int driver=VGA, mode=VGAHI; initgraph(&driver,&mode,); /图形初始化setcolor(1);rectangle(w1,w3,w2,w4); /画出窗口setcolor(14);line(x1,y1,x2,y2); /画出裁剪之前的直线getch();cleardevice(); /清除屏幕getch(); setcolor(5);rectangle(w1,w3,w2,w4); /再次画出窗口setcolor(12);clipdraw(x1,y1,a,x2,y2,b); /画出保留在窗口内的直线getch();closegraph(); /关闭图形系统2.5运行结果图:实验题三3.1实验题目上机编程实现直线的中点分割裁剪算法。要求：(1)该程序能实现窗口屏幕上任意一条直线的裁剪；(2)直线段要求可以随机输入；(3)程序在裁剪后不作窗口视图变换；(4)裁剪过程为先画直线再裁剪，且运行结果列出以下3种情况：直线段与窗口有两个交点、直线段与窗口只有一个交点、直线段与窗口无交点。3.2实验目的和意义1.了解裁剪的意义以及对人们日常生活的重大影响2.熟悉并掌握中点裁剪技术以及如何对线段或多边形作求交运算3. 熟悉并掌握如何通过编程实现窗口屏幕上任意一条直线的裁剪4. 熟悉并掌握中点分割的裁剪算法5.了解编码裁剪算法中直线段与窗口的各种关系以及相应的裁剪算法3.3程序制作步骤(包括算法的基本思想、流程图、设计步骤等)算法思想： 中点分割裁剪法的基本思想是：分别寻找直线段两个端点各自对应最远的可见点，只需要该线段能在窗口内留下一个可见段，则这个最远的可见点只有两种选择：要么是直线段的一个相应端点；要么是在不断中点再分过程中产生的某个子段的中点。算法步骤： （1）检验直线段P1P2是否完全被排斥在窗口之外。如果是，过程结束且无输出线段（左图中的线段b ）；否则继续执行下一步。（2）检验点P2是否可见。如果是，则P2点就是离P1点最远的可见点，过程结束。如果P2点是不可见点，那么继续执行下一步。（3）分割直线段P1P2于中点Pm。如果Pm P2被完全排斥在窗口外，那么原估计还不足，便以线段P1 Pm 作为新的P1P2线段从算法的第一步重新开始执行。反之，则以线段PmP2作为新的P1P2线段从算法的第一步重新开始执行。3.4主程序/*坐标系：屏幕左上角为原点,向下为纵坐标正方向*/#includegraphics.h/*加入c图形库*/#includeconio.h/*键盘控制*/#includemath.h#includestdio.h#includestdlib.h#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8#define XL 50#define XR 300#define YB 70#define YH 200/*定义视窗四边*/int encode(int x,int y,int *code)/*编码算法*/ int c=0; if(xXR) c=c|RIGHT; if(yYH) c=c|TOP; *code=c; return *code;void draw_ett(int x1,int y1,int x2,int y2,int *x,int *y)/*求最远可见点*/int code1,code2,code;int xx,yy;double d;int d1,d2;encode(x1,y1,&code1);encode(x2,y2,&code2);if(code2=0)/*(x2,y2)端点可见即为(x1,y1)的最远可见点*/xx=x2;yy=y2;*x=xx;*y=yy;return;if(code1&code2) != 0)return;/*原线段不可见*/while(1)xx=(x1+x2)/2;yy=(y1+y2)/2;encode(int)xx,(int)yy,&code);/*不将xx、yy变成整型将产生错误*/d1=(yy-y1)*(yy-y1);d2=(xx-x2)*(xx-x2);/*这里求中点距顶点位置，请思考没用一个顶点坐标的原因(注意d是float型)*/d=sqrt(d1+d2);/printf(%d,%d,%f,%f,%f,%f,%fn,x1,y1,xx,yy,d1,d2,d);if(getch()=17)exit(1);/*读入键盘按键*/if(d1)/*中点到(x2,y2)端点线段不可见*/x2=xx;y2=yy;if(!(code&code2)&d1) x1=xx; y1=yy;putpixel(xx,yy,4);/*画出中点位置便于观察*/ setcolor(4);circle(xx,yy,2); floodfill(xx,yy,4);void main()int x1,y1,x2,y2,xx,yy,xxx,yyy;int driver,mode;d