上机实验：图形填充与裁剪算法的具体实现.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.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来改变多边形*/#include"graphics.h"/*参加c图形库*/#include"stdio.h"#include"math.h"/*数学库*/#include"conio.h"/*键盘控制*/#define MP 100/*多边形边数*/#include#define false 0void edge_mark(int arr[][2],int value,int polydeflen)/*多边形直线扫描变换*/{ int by,x,y,ax,ay;/*by为上点纵坐标，x、y当前点横、纵坐标，ax、ay下点横、纵坐标*/ int i,j; float k;/*k为直线斜率的倒数*/ by=arr[polydeflen-1][1]; 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;jmax) max=ar[i][1]; if (ar[i][1]

要求：(1)该程序能实现窗口屏幕上任意一条直线的裁剪；(2)直线段要求可以随机输入；(3)程序在裁剪后不作窗口—视图变换；(4)裁剪过程为先画直线再裁剪，且运行结果列出以下3种情况：直线段与窗口有两个交点、直线段与窗口只有一个交点、直线段与窗口无交点实验目的和意义裁剪技术以及如何对线段或多边形作求交运算3. 熟悉并掌握如何通过编程把窗口内每个图形元素都划分为可见局部和不可见局部从而实现裁剪4. 熟悉并掌握直线段的裁剪算法5.了解编码裁剪算法中直线段与窗口的各种关系以及相应的裁剪算法程序制作步骤(包括算法的根本思想、流程图、设计步骤等)算法思想：这种算法利用编码的方法，延长窗口边线，使得它们把包含未经裁剪图形的窗口平面区域分成九个区域，如下列图所示：顶边线底边线左边线右边线每个区域用一个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&C2≠0 .由此可检查判断直线在窗口外，应全部舍弃 〔3〕如果直线两端点不满足上述两种情况，不能简单地全部保存或全部舍弃直线时，那么需要计算出直线与窗口边线的交点，将直线分段后继续进展检查判断这样可以逐段地舍弃位于窗口外地线段，保存剩余在窗口内的线段算法流程图：开 始初始化图形显示模式调用Cohen-Sutherland函数输入线段和视图关闭图形显示模式退 出主程序求得与左边交点坐标利用code进展交点位置判断code=code2code=code1首点是否可见?code1&code2≠0?code1=code2=0?对线段两端点编码变化得到code1和code2ＹＮＹＹＮＮ 求得与下边交点坐标求得与上边交点坐标求得与右边交点坐标利用交点坐标替换。