计算机图形学课程设计 多边形的裁剪算法.doc

河南理工大学万方科技学院课程设计报告2010 2011学年第二学期课程名称 计算机图形学 设计题目 多边形裁剪算法 学生姓名 孙晓芳 学 号 0816304009 专业班级 计算机科学与技术10升 指导教师 侯守明 2011 年 6 月 29 日22目 录目 录目 录I第1章 程序运行环境11.1程序运行环境的简单介绍11.2程序运行环境的安装1 1.3 多边形裁剪算法设计的内容.第2章 直线裁剪和多边形裁剪的简单比较32.1 直线裁剪的介绍3 2.1.1 直线裁剪的基本原理. 2.1.2 直线裁剪算法的分类以及和窗口交点参数值的计算. 2.2 多边形裁剪介绍.3 2.2.1 多边形裁剪的基本思想. 2.2.2 多边形和窗口相交的判定方法.第3章 多边形裁剪方法的详细介绍53.1 Sutherland-Hodgman算法.3.2 多边形裁剪算法的流程图53.3多边形裁剪算法的实现6第4章 代码的实现7第5章 总结14参考文献15第2章 总体设计第1章 程序的运行环境1.1 程序运行环境的简单介绍本次设计主要是运用了程序设计语言主要以C/C+语言为主，开发平台为Visual C+。现在Windows系统的主流编译环境有VisualC+，C+Builder，Dev-C+等，它们都是支持OpenGL的。但这次设计主要选择VisualC+作为学习OpenGL的实验环境。Microsoft Visual C+，（简称Visual C+、MSVC、VC+或VC）微软公司的C+开发工具，具有集成开发环境，可提供编辑C语言，C+以及C+/CLI等编程语言。Microsoft Visual C+是Microsoft公司推出的开发Win32环境程序，面向对象的可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock网络、3D控制界面。OpenGL作为盖茨设计的主要软件它与其他软件相比主要有以下几个优点1）与C语言紧密结合：2）强大的可移植性：3、高性能的图形渲染：1.2 程序安装及步骤 1选择一个编译环境这里我们选择VisualC+作为学习OpenGL的实验环境2安装GLUT工具包GLUT不是OpenGL所必须的，但它会给我们的学习带来一定的方便，推荐安装。Windows环境下的GLUT下载地址：（大小约为150k）/resources/libraries/glut/glutdlls37beta.zipWindows环境下安装GLUT的步骤：1）将下载的压缩包解开，将得到5个文件2）glut.h放到GL文件夹（VC6中一般是：C:Program FilesMicrosoft Visual StudioVC98IncludeGL，VC2005中是：C:Program FilesMicrosoft Visual Studio 8VCInclude，新建GL文件夹，再将glut.h放到GL文件夹中）。3）glut.lib和glut32.lib放到静态函数库所在文件夹（VC6中一般是：C:Program FilesMicrosoft Visual StudioVC98Lib, VC2005中是：C:Program FilesMicrosoft Visual Studio 8VCLib）。4）把解压得到的glut.dll和glut32.dll放到操作系统目录下面的system32文件夹内。（其路径为：C:WindowsSystem32）3建立一个OpenGL工程这里以VC为例：首先从开始-所有程序-Microsoft Visual C+ 6.0菜单中打开VC，也可单击文件：C:Program FilesMicrosoft Visual StudioVisual C+6CommonMSDev98Binmsdev.exe打开VC，在VC中选择File-New-Project，然后选择Win32ConsoleApplication，输入一个工程名,设为A，然后按OK。在谈出的对话框左边点ApplicationSettings，找到A Simple application并勾上，选择Finish。然后打开工程代码文件:A.cpp,将其内容替换为实验示范代码.点击运行按钮就可以执行调试程序了。1.3 多边形裁剪算法设计的内容和要求这次设计的主要内容； 1）理解多边形裁剪与直线段裁剪的区别； 2）掌握多边形的裁剪过程； 3）理解并掌握Sutherland-Hodgman算法的裁剪思想。 第2章 直线裁剪和多边形裁剪的比较2.1 直线裁剪的介绍2.1.1直线裁剪的基本原理图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之内确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之内（如图1中P5到P6的直线），则此直线应保留。如果一条直线的一个端点在窗口外（如P9）另一个点在窗口内（如P10），则应从直线与边界的交点（P9）处裁剪掉边界之外的线段。如果直线的两个端点均在边界外，则可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保留P7到P8的线段，其余部分均裁剪掉。图1直线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保留或全部裁剪，剩下的即为部分裁剪的直线。对于部分裁剪的直线则首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的部分裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。2.1.2直线裁剪算法的分类以及和窗口交点参数值的计算 直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。主要的四种算法 直接求交算法Cohen-Sutherland算法 中点算法梁友栋barskey算法Cohen-Sutherland算法的大意是：对于每条线段P1P2，分为3种情况处理。若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之。若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。若线段既不满足“取”的条件，也不满足“弃”的条件，则把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。1区域码及其建立Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示：位 4 3 2 1坐标区 上 下 右 左上述各位中某位为1，则表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中内的点，其区域码应为0000，位于窗口左下方的点，其区域码应为0101，其余类推。区域码各位的值可以通过对端点坐标（x，y）与窗口边界的比较求得。如果xxwmin，则区域码的第一位为1，其余各位的确定与此相似。现在的计算机语言都可以进行位操作，因此，可以通过以下步骤建立区域码：计算出端点坐标与窗口边界的差。按计算出的各个差的符号把区域码的相应位置为0或1，即区域码的第一位置为（xxwmin）的符号位；区域码的第二位置为（xwmin-x）的符号位；图2 区域码区域码的第三位置为（y-ywmin）的符号位； 区域码的第四位置为（ywmin-y）的符号位。2区域码裁剪算法 对所有直线的端点都建立了区域码之后，就可按区域码判断直线在窗口之内或窗口之外。这可分为如下几种情况： 若一直线的两个端点的区域码均为0000则此直线在窗口边界之内，应子保留。 若一直线的两个端点的区域码的同一位同时为1，则此直线全部在窗口边界之外，应子裁剪。例如，若一直线的一个端点的区域码为1001，另一个端点的区域码为0101，则此两端点的区域码的第一位均为1，说明此两端点均在窗口边界之左，因此，直线在窗口边界之外，应予裁剪。可用将直线两个端点的区域码进行与操作的方法，判断直线是否在窗口之外，若与操作的结果为0000则两端点的区域码任何位均不同时为1，此直线不一定被裁剪。以上两种情况之外的直线，有可能穿过窗口，也有可能不穿过窗口，如图87所示。图中所示的两条直线都不符合情况的要求，但一条直线（P1P2）穿过窗口，另一直线（P3P4）不守过窗口。对这类直线可以进行如下处理：取窗口外的一个端点与窗口边界比较以确定可排除直线的哪一部分，然后，把直线剩下的部分与其他边界比较，这样一直到直线全部被排除或确定直线的哪一部分在窗口之内为止。可按“左、右、下、上”的次序建立检查直线端点与窗口边界关系的算法。下面介绍对图3所示的两条直线进行处理的过程。从直线P1P2的下端点P1开始，依次检查窗口的左、上、右及下边界，可发现此点在窗口之下（因为区域码的第三位为1）。然后求得直线与下边界的交点P1排除线段P1 P1这样直线就缩短为P1 P2。因为P2在边界之外，将此端点与各边界比较，可发现此端点在窗口上面。计算出交点P2线段P1P2保留下来。这样就完成了对这条线的处理并开始处理下一直线P3 P4。端点P3在窗口之左，可计算出交点讲裁剪掉线段。检查的区域码，可发现直线的这一剩余部分在窗口之下故也可排除。由于窗口边界均平行于坐标轴，所以直线与窗口边界的交点可以用直线方程的各参数很方便地求出，对于一条端点坐标为及的直线，其与一垂直边界的交点的y坐标可以用下式计算：这里互的取值可取x或，斜率m可用公式计算。同样地，与水平边界交点的x坐标可用下式计算： 这里y的值可取几或。本算法的优点在于简单，易于实现。可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，决定了算法的速度。另外，本算法对于其它形状的窗口未必同样有效。特点：用编码方法可快速判断线段的完全可见和显然不可见。LiangBarsky算法Liang（梁友栋)-Barsky算法又称为参数方程法。首先写出端点及之间连线的参数方程如下：其中，。参数u可取0 1之间的值，坐标表示此范围内的u值定义的直线上的一个点。当u0时，直线的另一端u0时，。我们发现，如果直线上的某点处于及及所定义的窗口之内，则满足以下条：这四个不等式可以表示为：， k=1,2,3,4其中，参数定义为； 按照直线与窗口边界的相对位置，可分为以下几种倩况。任何一条与窗口边界平行的直线，其，此处值表示取哪一个边界（=1,2,3及4，分别相应于左、右、下及上边界）。如果对某一值，还满足，则此直线完全在边界外，可不进一步考虑；如果0，则此与边界平行的直线在边界内。如果，则情况较复杂。此时，可把直线按从到连线方向作为正向，将此直线无限延伸，同时把各窗口边界也无限延伸（见图3）；然后分以下两种情况讨论：a当时，则是由窗口外发出的一条直线的无限延伸线进入相应窗口边界的无限延伸线的内部。b当时，情况相反。即直线的延伸线是由窗口边界延伸线的内部到外部。以图3中的直线为例，说明以上两图3 直线与窗口边界的相对位置种情况。表1.1给出的延伸线相对于4个边界延伸线的方向及取值。表1.1 直线方向与取值边界取值方向交点左由外到内右由内到外下由外到内上由内到外当时，可以用下式计算出一参数u，此u值应于直线延伸线与窗口边界k的延伸线的交点：对于每条直线，可计算出一对u值（及），由此两参数可判断直线是如何裁剪的。其中，的值可由从窗口边界外发出进人窗口边界之内的直线（）所涉及的窗口边界确定。对于这些窗口边界，可计算出各，取各中最大值即为回，可由自窗口边界内发出至窗口边界外的直线（）所涉及的窗口边界确定，同样可计算出这些窗口边界的值，取各中的最小值即为。如果，则此直线全部在窗口外而可排除：否则，此直线在窗口内，可由及计算出彼裁剪直线的端点。图3中标出直线及相应于及的与边界的交点。的，则彼裁剪，并可由及计算出裁剪点；而的，则此直线全部彼排除。此算法可用以下过程表示。此过程中开始把交点参数置为及。对每一窗口边界计算出相应的及值，然后用函数CliPtest由参数及决定此直线能否彼排除或者决定交点参数是否要调整。当时，用参数修改值：当时，用参数修改值。如果最后的结果为，则排除此直线；否则，只有当新的值使直线缩短时，才修改相应的参数。当，可排除此直线，因为直线与边界平行且在边界之外。如果四个及均被检查而直线被排除，则被裁剪直线的端点可由及的值确定。2.2多边形裁剪介绍2.2.1多边形裁剪的基本思想这次多边形的裁剪算法主要用的是Sutherland-Hodgman算法其基本思想是：Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德(IESutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。一，基本思想: 一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧。多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种情况（1）仅输出1个顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的1个交点I；情况（4）输出线段SP与裁剪线的1个交点I和1个终点P2.2.2 多边形和窗口相交的判定方法二、算法实现：1、已知：多边形顶点数组src，顶点个数n， 定义新多边形顶点数组dest。2、赋初值：用变量flag来标识：0表示在内侧，1表示在外侧。 3、对多边形的n条边进行处理，对当前点号的考虑为：0n-1。for(i=0；in；i+)if(当前第i个顶点是否在边界内侧？) if(flag!=0) /*前一个点在外侧吗？*/flag=0；/*从外到内的情况，将标志置0,作为下一次循环的前一点标志*/(dest + j) =求出交点；/*将交点dest放入新多边形*/ j+；(dest + j)= (src + i)； /*将当前点srci放入新多边形*/ j+；elseif(flag=0) /*前一个点在内侧吗？*/flag=1；/*从内到外的情况，将标志置1,作为下一次循环的前一点标志*/(dest + j) =求出交点；/*将交点dest放入新多边形*/ j+；s= (src + i)； /*将当前点作为下次循环的前一点*/P3C（x, y），P4C（x,y），P5C（y，x），P6C（y，x），P7C（y，x），P8C（y，x）。这种性质称为八对称性。因此，只要扫描转换八分之一圆弧，就可以通过圆弧的八对称性得到整个圆。2.2.2圆Bresenham算法基本原理计算误差值Pi，以圆心为平面坐标轴原点，以Y轴正半轴向第一象限变化作基准x与y的变化关系，每点的偏移量以误差值Pi为计算基量，Pi0则yi+1yi，否则yi+1yi+1，算出y的变化量（从Y正半轴开始到1/8弧x变化快于y变化，所以x变化量为1）。Pi的递归式，当Pi小于0，Pi+1Pi+4xi+6，否则PiPi+1+4（xi+yi）+10。每画一点后根据中心对称原理在4个坐标轴同时向8个方向画点。直至到1/8弧相交（此时X等于Y）。2.3用梁友栋-Barsky算法进行线段裁剪2.3.1梁友栋-Barsky算法特点梁友栋-Barsky算法只能应用于矩形窗口的情形。通常梁友栋-Barsky算法比CohenSutherland算法效率更高，因为需要计算的交点数目减少了。更新参数u1、u2仅仅需要一次除法；线段与窗口边界的交点仅计算一次，就计算出u1、u2最后的值。相比之下，即使一条线段完全落在裁剪窗口之外，CohenSutherland算法也要对它反复求交点，而且每次求交计算都需要做乘除法。2.3.2梁友栋-Barsky算法实现1、初始化线段交点的参数：u1=0，u2=1；2、计算出各个裁剪边界的p、q值；3、根据p、q来判断：是舍弃线段还是改变交点的参数。（1） 当p0时，参数r用于更新u2。（u2=minu2，rk）（3）如果更新了u1或u2后，使u1u2，则舍弃该线段。（4）当p=0且q|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。1、画点(x1, y2); dx=x2-x1; dy=y2-y1；计算误差初值P1=2dy-dx; i=1；2、求直线的下一点位置：xi+1=xi+1；if Pi0 则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1, yi-1）；4、求下一个误差Pi+1；if Pi0 则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1; if i=y为止。误差量由(x,y)=x2+y2-R2给出。 先找递推关系，若当前d=F(x+1,y-0.5)0，则y须减1，则下一d值为d=F(x+2,y-1.5)=(x+2)2+(y-1.5)2-R2=(x+1)2+(x-0.5)2-R2+2x+3-2y+2=d+2x-2y+5，若当前d=F(x+1,y-0.5)0即d0.25，这和d0等价，所以d取初值1-R。3.3用梁友栋-Barsky算法进行线段裁剪设窗口为下列方程所确定：x=XL x=XR (记XLxXR的区域为x)y=YB y=YT (记YByYT的区域为y)则平面上任意线段P1P2在窗口内的部分为：P1P2xy 设通过P1P2的直线与窗口左、右、上、下边界的交点分别为L、R、B、T，则P1P2可见部分亦可表为：P1P2LRBT 当直线垂直时：xp1=xp2且XLxp1XR时，P1P2LRBT 等价于求P1P2BT；当直线平行时：yp1=yp2且YByp1YT时，P1P2LRBT 等价于求P1P2LR；当直线既不垂直又不平行时：xp1！= xp2且yp1！= yp2 L、R、B、T都是确定的P1P2的斜率k=( yp2-yp1)/ ( xp2-xp1)为非零或非奇异值。xB= xp1 +(YB- yp1)/k； xT= xp1 +(YT- yp1)/k；且 xB 0； xT xB，当k=0) inc=1; else inc=-1; if(abs(dx)abs(dy) if(dx0)tmp=x0;x0=x1;x1=tmp; tmp=y0;y0=y1;y1=tmp; dx=-dx;dy=-dy;d=2*dy-dx;d1=2*dy;d2=2*(dy-dx);x=x0;y=y0;putpixel(x,y);while(xx1) x+; if(d0) d+=d1; else y+=inc; d+=d2; putpixel(x,y); else if(dy0) tmp=x0;x0=x1;x1=tmp; tmp=y0;y0=y1;y1=tmp; dx=-dx;dy=-dy; d=2*dx-dy; d1=2*dx; d2=2*(dx-dy); x=x0; y=y0; putpixel(x,y); while(yy1) y+; if(d0) d+=d1; else x+=inc; d+=d2; putpixel(x,y); 4.2用Bresenham算法画圆核心代码：void plotC(int x,int y,int xc,int yc) putpixel(xc+x,yc+y); putpixel(xc+x,yc-y); putpixel(xc-x,yc+y); putpixel(xc-x,yc-y); putpixel(xc+y,yc+x); putpixel(xc+y,yc-x); putpixel(xc-y,yc+x); putpixel(xc-y,yc-x);void Bresenham_Circle(int xc,int yc,int r)/Bresenham函数画圆 int x,y,d; y=r; d=3-2*r; x=0; while(x=y) plotC(x,y,xc,yc); if(d0) d+=4*x+6; else d+=4*(x-y)+10; y=y-1; x=x+1; 4.3梁友栋-Barsky裁剪算法剪裁前：剪裁后：核心代码：int clipTest(float p,float q,float *u1,float *u2) /裁剪算法int retVal;retVal=1; /*retVal为标志变量，0：表示舍弃；1：表示可见。float r;if(p*u2)retVal=0;accept=false;else if(r*u1) *u1=r; /*u1取进入点的最大参数值else if(p0.0) r=q/p;if(r*u1) retVal=0;accept=false;else if(r*u2)*u2=r; /*u2取离开 点的最小参数值else if(q0.0) /*p=0，且q0。平行于边界，而且在界外的线retVal=0;accept=false;return retVal;void clipLine(int xwmin,int ywmin,int xwmax,int ywmax,int *x1,int