计算机图形学-填充与裁剪算法的实现

计算机图形学课程实验报告实验题目填充与裁剪算法的实现班级姓名学号指导教师日期信息与计算科学专业基础课ComputerGraphicsReportOfcourseexperiment-图形学课程实验报告--1-实验说明试验目的：掌握图形填充与裁剪算法的基本思想，并能上机编程实现相应的算法。。试验地点：教九楼401数学系机房实验要求(Direction):1.每个学生单独完成；2.开发语言为TurboC或C++，也可使用其它语言；3.请在自己的实验报告上写明姓名、学号、班级；4.每次交的实验报告内容包括：题目、试验目的和意义、程序制作步骤、主程序、运行结果图以及参考文件；5.自己保留一份可执行程序,考试前统一检查和上交。实验内容实验题一1.1实验题目上机编程序实现多边形区域填充算法。要求：(1)多边形要求采用顶点表示，且顶点的个数和顶点坐标可以随机输入；(2)要求先画出多边形，画出多边形的同时要求标明各顶点坐标；(3)水平扫描线的顺序和填充颜色可以自由选择。1.2实验目的和意义掌握多边形区域填充的概念，掌握扫描线填充法。1.3程序制作步骤(包括算法的基本思想、流程图、设计步骤等)一、算法过程（设计步骤）（1）根据给出的顶点坐标数据，按y递增顺序建立ET表。（2）根据AET指针，使之为空。（3）使y=ymin（ymin为顶点坐标中最小y值）。（4）反复做下述各步，直至y=ymax（顶点坐标中y的最大值）或ET与AET为空。①将ET表加入到AET中，并保持AET链中的记录按x值递增排序。②对扫描线yi一次成对取出AET中xi值,并对每对xi之间填上所要求的颜色或图案。③从AET中删除yi=ymax的记录。④对保留下来的AET中的每个记录，用xi+1/m代替xi，并重新按x递增排序。填充与裁剪算法的实现实验3-图形学课程实验报告--2-⑤使yi+1,以便进入下一个循环。二、流程图：图2.1NY初始化图形模式求原始边记录r输入顶点个数n和顶点坐标p开始构造ET表添加新边到AET表中yymax从AET表中删除旧边(ytop=y的边)对AET表中所有边进行更新（xbottom+=increx）依次取出每对xi，并用填充色填充之间的区间结束求ymin，ymax对AET表中的边记录按xbottom递增进行排序-图形学课程实验报告--3-1.4主程序/****************************第一部分***********************************（头文件，宏定义，点的结构体Point，原始边记录结构体RamEdge，边记录类Edge)*/#includealgorithm#includegraphics.h#includeiostream#includestdlib.h#includelist#defineMAXSIZE800usingnamespacestd;//点的结构体typedefstruct{intx;inty;}Point;//原始边记录，只记录起始和结束点，以Y递增定义typedefstruct{Pointstart;Pointend;}RamEdge;//边记录类Edge（用于ET表和AET表）classEdge{public:-图形学课程实验报告--4-intyMAXSIZE;floatxbottom;floatincrex;Edge(intyMAXSIZE=0,intxbottom=0,floatincrex=0){this-yMAXSIZE=yMAXSIZE;this-xbottom=xbottom;this-increx=increx;};booloperator(Edge&a){returnxbottoma.xbottom;};};/****************************第二部分***********************************根据已给顶点求出原始边记录*/RamEdge*SoluteRamEdge(Pointp[],intn){inti;RamEdge*r;if((r=(RamEdge*)malloc(sizeof(RamEdge)*n))==NULL){cout内存空间不足endl;exit(1);}for(i=0;in-1;i++){if(p[i].y=p[i+1].y)-图形学课程实验报告--5-{r[i].start.x=p[i].x;r[i].start.y=p[i].y;r[i].end.x=p[i+1].x;r[i].end.y=p[i+1].y;}else{r[i].start.x=p[i+1].x;r[i].start.y=p[i+1].y;r[i].end.x=p[i].x;r[i].end.y=p[i].y;}}if(p[n-1].y=p[0].y){r[n-1].start.x=p[n-1].x;r[n-1].start.y=p[n-1].y;r[n-1].end.x=p[0].x;r[n-1].end.y=p[0].y;}else{r[n-1].start.x=p[0].x;r[n-1].start.y=p[0].y;r[n-1].end.x=p[n-1].x;r[n-1].end.y=p[n-1].y;}returnr;-图形学课程实验报告--6-}/*****************************第三部分***********************************求当前扫描线i的AET链表*/listEdgeET_Structor(RamEdger[],intn,inti)//i为当前扫描线{intj,x1,x2,y1,y2;listEdgee;listEdge::iteratork;EdgetempEdge;for(j=0;jn;j++){x1=r[j].start.x;x2=r[j].end.x;y1=r[j].start.y;y2=r[j].end.y;//如果是水平线，就加入ET；否则直接画出if(y1!=y2){if(y1==i){tempEdge.yMAXSIZE=y2;tempEdge.xbottom=x1;tempEdge.increx=(float)(x2-x1)/(y2-y1);e.push_front(tempEdge);}}}-图形学课程实验报告--7-returne;}/*****************************第四部分***********************************多边形扫描线填充法的实现函数*/voidScanLineFill(Point*p,intn,intcolor){inti,x1,x2;RamEdge*r=SoluteRamEdge(p,n);//原始边记录//求ymin,yMAXSIZEintymin=p[0].y,yMAXSIZE=p[0].y;for(i=0;in;i++){if(p[i].yymin)ymin=p[i].y;if(p[i].yyMAXSIZE)yMAXSIZE=p[i].y;}listEdge::iteratork;//构造ETlistEdgeET[MAXSIZE];for(i=0;iyMAXSIZE-ymin;i++){ET[i]=ET_Structor(r,n,i+ymin);ET[i].sort();}-图形学课程实验报告--8-//构造AETlistEdgeAET;inty;for(y=0;yyMAXSIZE-ymin;y++){//加入新边AET.merge(ET[y]);//删除旧边for(listEdge::iteratorit=AET.begin();it!=AET.end();){if((*it).yMAXSIZE==y+ymin){it=AET.erase(it);}else{++it;}}//排序AET.sort();//成对取出xi，并填充k=AET.begin();while(k!=AET.end()){-图形学课程实验报告--9-x1=(*k).xbottom;x2=(*(++k)).xbottom;k++;setcolor(color);line(x1,y+ymin,x2,y+ymin);}//更新所有边for(it=AET.begin();it!=AET.end();++it){(*it).xbottom=(*it).xbottom+(*it).increx;}}}/*****************************第五部分***********************************测试部分*/voidmain(void){Pointp[8];intn=8;//输入顶点个数和顶点坐标cout输入端点个数:;cinn;cout输入端点坐标:endl'\t''\b';inti;for(i=0;in;i++)-图形学课程实验报告--10-{cout'\t'端点i+1:;cinp[i].x;cinp[i].y;}//初始化图形模式intgd,gm;detectgraph(&gd,&gm);initgraph(&gd,&gm,);//输出端点坐标charstr[15];settextstyle(0,0,2);for(i=0;in;i++){sprintf(str,%s%d%s%d%s,(,p[i].x,,,p[i].y,));outtextxy(p[i].x,p[i].y,str);}//填充（绿色）ScanLineFill(p,n,2);getch();closegraph();}1.5运行结果图-图形学课程实验报告--11-图1.5.1多边形区域填充输入数据图1.5.2多边形区域填充运行结果截图实验题二2.1实验题目上机编程实现直线的编码裁剪（Cohen-Sutherland）算法。要求：(1)该程序能实现窗口屏幕上任意一条直线的裁剪；(2)直线段要求可以随机输入；(3)程序在裁剪后不作窗口—视图变换；(4)裁剪过程为先画直线再裁剪，且运行结果列出以下3种情况：直线段与窗口有两个交点、直线段与窗口只有一个交点、直线段与窗口无交点。2.2实验目的和意义掌握编码裁剪（Cohen-Sutherland）法并上机实现。-图形学课程实验报告--12-2.3程序制作步骤(包括算法的基本思想、流程图、设计步骤等)一、基本思想把包含窗口的平面区域沿窗口的4条边线分成9个区域，如图2.1所示：图2.1每个区域用一个四位代码来表示，代码中每一位分别是0或1，是按照窗口边线来确定的。编码规则为（其中最右边为第一位，依次第2,3,4位）：第1位置1——该端点位于窗口左侧；第2位置1——该端点位于窗口右侧；第3位置1——该端点位于窗口下侧；第4位置1——该端点位于窗口上侧；否则，相应位置0。二、设计步骤：Step1:输入窗口left,top,right,bottom边界值和直线端点p1,p2的坐标；Step2:求p1,p2的编码C1,C2（编码可用十进制数来表示，也可用整形数组，此处用十进制数）。假设x为横坐标，y为纵坐标，则有xleftybottom5bottm=y=top1ytop9ybottom4-图形学课程实验报告--13-left=x=rightbottm=y=top0ytop8xrightybottom6bottm=y=top2ytop10表2.1Step3:1.若C1=C2=0,则表示p1和p2都位于窗口内，应全部保留；2.若C1^C2≠0,则表示p1和p2都位于窗口外一侧，应全部舍去；3.若C1和C2不符合上述两种情况，不能简单地保留或舍去直线，则需要计算直线与窗口边线的交点，将直线分段后继续检查判断。这样可以逐段舍去位于窗口外的直线，保留窗口内的直线。进行如下循环，直到出现情