图形学论文

湖南理工学院图形学结课论文计算机图形学论文对COHENSUTHERLAND裁剪算法的研究姓名学号指导老师班级院部专业2017年12月29湖南理工学院图形学结课论文I对COHENSUTHERLAND裁剪算法的研究摘要近几十年来，计算机图形学发展速度很快并且有了引人瞩目的发展，它已广泛应用于计算机辅助设计、电视广告、动画和仿真等许多领域并发挥着重要作用。在二维观察中，我们会需要在观察坐标下对窗口进行裁剪，只保留窗口内的那部分图形，去掉窗口外的图形。这里的裁剪包含两部分内容一是判断图形元素与窗口区域之间的关系，二是求出窗口区域内的部分图形。本文对计算机图形学中的基础算法之一裁剪算法进行了认真研究。关键字计算机图形学，裁剪，编码，COHENSUTHERLAND算法湖南理工学院图形学结课论文IIABSTRACTINRECENTDECADES,COMPUTERGRAPHICSHASBEENDEVELOPINGRAPIDLYANDHASATTRACTEDMUCHATTENTIONITHASBEENWIDELYAPPLIEDINMANYFIELDS,SUCHASCOMPUTERAIDEDDESIGN,TELEVISIONADVERTISING,ANIMATIONANDSIMULATION,ANDPLAYSANIMPORTANTROLEINTHETWODIMENSIONALOBSERVATION,WENEEDTOCUTTHEWINDOWINTHEOBSERVATIONCOORDINATE,ONLYKEEPTHEPARTOFTHEWINDOWINTHEWINDOWANDREMOVETHEFIGUREOUTSIDETHEWINDOWTHECLIPPINGCONSISTSOFTWOPARTSONEISTOJUDGETHERELATIONSHIPBETWEENTHEGRAPHICELEMENTSANDTHEWINDOWAREA,ANDTHETWOISTOFINDOUTTHEPARTSOFTHEWINDOWAREAINTHISPAPER,ONEOFTHEBASICALGORITHMSINCOMPUTERGRAPHICS,THECUTTINGALGORITHM,ISCAREFULLYSTUDIEDKEYWORDCOMPUTERGRAPHICS,CLIPPING,CODING,COHENSUTHERLANDALGORITHM湖南理工学院图形学结课论文III目录1引言2已有工作介绍3COLENSUTHERLAND算法原理31算法分析4COLENSUTHERLAND算法实现5COLENSUTHERLAND算法结果展示6分析与结论7参考文献8致谢湖南理工学院图形学结课论文1/18正文（一）引言计算机图形学是计算机技术应用中一个很重要的研究方向，伴随着显示器的发展，计算机图形学不断发展起来。计算机图形学、数字图像处理、计算机视觉设计和模式识别等所处理的对象都是与图形图像息息相关的。计算机图形学和计算机视觉不断的结合交叉，他们之间相互融合，促进了彼此学科的不断发展。用计算机设备来显示图形、生成图形以及处理图形信息的计算机图形学成为一个非常有价值的研究热点。20世纪中后期以来，计算机图形学不断应用于电影、艺术、教育、设计、广告等各个领域。随着计算机图形学的广泛应用，计算机图形学、计算机视觉和计算机图像处理的联系越来越多，急需我们在计算机图形学的基础上，向计算机视觉方向发展，进而带动他们的综合发展。随着数字视听、虚拟现实、系统仿真等应用领域的发展，出现了一批成熟的商业化图形软件，计算机图形学与视频、图像、虚拟现实、人机交互等技术口益结合、相互渗透。在图像的处理方面，对裁剪算法的要求越来越高，因此我决定深入研究一下裁剪算法。（二）已有工作介绍二维线裁剪算法在计算机图形学中占据重要的地位，一直都是计算机图形学中研究的热点，由于直线段的裁剪是复杂图元进行裁剪的基础，因此它是国内外学者研究最为活跃的方向之一，提出了许多改进算法。当前研究的重点仍然集中在算法执行效率的提高方面。二维线裁剪可分为矩形窗口的线裁剪、圆形窗口的线裁剪等，下面对裁剪算法的国内外研究现状进行相关介绍。矩形窗口的线裁剪的研究主要有JINGJINGHAN等提出了COHENSUTHERLAND的改进算法，该算法通过增加判断条件，可以快速的舍弃完全位于矩形窗口之外的线段，避免了无效的求交运算。湖南理工学院图形学结课论文2/18并且对于与矩形窗口有交点的线段，可以快速的判断出线段与窗口的哪条边有交点，从湖南理工学院图形学结课论文而快速的计算出真实交点的坐标，提高了裁剪的效率。李竹林等提出了COHENSUTHERLAND的改进算法，该算法根据直线端点编码来确定辅助线，利用平面上三点的关系判断直线与窗口的哪条边相交，改进的算法将求交的次数降为最多两次，且避免了计算斜率和距离，具有重要的应用价值。马培华等提出了COHENSUTHERLAND的改进算法，该算法通过增加判断条件，可舍弃可见窗口外非同侧的直线，并且在改进算法实现过程中，采用添加辅助直线的方法，直接计算出直线和可见窗口的有效交点。避免了求取无效交点的运算，从而节省了算法的执行时间。（三）COHENSUTHERLAND算法原理31算法分析CS算法基本原理可以描述为矩形窗口中显示直线。与裁剪窗口相交的线段，交点将线段分为窗口外和窗口内两部分，而与裁剪窗口边没有交点的线段，不是全部在窗口内，就是全部在窗口外。直线段的裁剪的基本思想1线段完全都不在窗口里面，如果是，结束裁剪。2线段是否全部在窗口内，若是，则转4。3计算被裁剪线段与矩形裁剪窗口边界的交点，将线段分为两部分，完全在窗口外的部分舍弃掉，对剩下的部分转2。4保留并显示该线段。算法通过采用编码的方式来确定点的位置，编码由四位二进制位数进行表示，例如0000，区域码的4位分别代表端点位于窗口的上、下、右、左。如图21湖南理工学院图形学结课论文图21编码完成后就可以根据两点之间的编码判断是否在窗口内或窗口外。（1）如果CODE1和CODE2均为0000，则说明P1和P2均在窗口内，那么线段全部位于窗口内部，应取之。（2）如果CODE1和CODE2经过按位与运算后的结果CODE1/函数声明GLUBYTEENCODEWCPT2DPT,WCPT2DWINMIN,WCPT2DWINMAXVOIDSWAPPTSWCPT2DP1,WCPT2DP2VOIDSWAPCODESGLUBYTEC1,GLUBYTEC2VOIDLINECLIPCOHENSUTHERLANDWCPT2DWINMIN,WCPT2DWINMAX,WCPT2DP1,WCPT2DP2VOIDMYKEYBOARDUNSIGNEDCHARKEY,INTX,INTY/变量的初始化CONSTGLINTWINLEFTBITCODE0X1/表示0001由上下右左原则可知为窗口左边线CONSTGLINTWINRIGHTBITCODE0X2/表示0010由上下右左原则知为窗口右边线湖南理工学院图形学结课论文CONSTGLINTWINBOTTOMBITCODE0X4/表示0100由上下右左原则知为窗口下边线CONSTGLINTWINTOPBITCODE0X8/表示1000由上下右左原则可知为窗口上边线/编码函数，将每个点转换成四位二进制数,函数返回点的编码GLUBYTEENCODEWCPT2DPT,WCPT2DWINMIN,WCPT2DWINMAXGLUBYTECODE0X00IFPTXWINMAXXCODE|WINRIGHTBITCODEIFPTYWINMAXYCODE|WINTOPBITCODERETURNCODE/判断点是否在裁剪区内，若在（代码为0000）则返回真。INLINEGLINTINSIDEGLINTCODERETURNGLINTCODE/判断直线明显在裁剪窗口外，若CODE1湖南理工学院图形学结课论文/判断直线明显在裁剪窗口内，若在，则CODE1|CODE21，说明两个点都是0000INLINEGLINTACCEPTGLINTCODE1,GLINTCODE2RETURNGLINTCODE1|CODE2VOIDSWAPPTSWCPT2DP1,WCPT2DP2/交换两个点的坐标WCPT2DTMPTMPP1P1P2P2TMPVOIDSWAPCODESGLUBYTEC1,GLUBYTEC2/交换两个点的码值GLUBYTETMPTMPC1C1C2C2TMP/切割函数，当直线有一部分在窗口内时应求出线与窗口的交点，再用交点进行/运算，直到所有点都在窗口内为止。VOIDLINECLIPCOHENSUTHERLANDWCPT2DWINMIN,WCPT2DWINMAX,WCPT2DP1,WCPT2DP2湖南理工学院图形学结课论文/切割函数GLUBYTECODE1,CODE2GLINTDONEFALSE,PLOTLINEFALSEGLFLOATKWHILEDONECODE1ENCODEP1,WINMIN,WINMAX/为P1编码CODE2ENCODEP2,WINMIN,WINMAX/为P2编码IFACCEPTCODE1,CODE2/表示两个点连的线都在区域内DONETRUEPLOTLINETRUEELSEIFREJECTCODE1,CODE2/表示两个点连的线不在区域内DONETRUEELSEIFINSIDECODE1/交换坐标值和编码SWAPPTSSWAPCODES/计算斜率IFP1XP2XKP2YP1Y/P2XP1X湖南理工学院图形学结课论文/开始裁剪,以下与运算若结果为真，则P1在边界外，此时将/P1移向直线与该边界的交点IFCODE1P1XWINMINXELSEIFCODE1P1XWINMAXXELSEIFCODE1P1YWINMINYELSEIFCODE1P1YWINMAXYIFPLOTLINEGLBEGINGL_LINES湖南理工学院图形学结课论文GLLINEWIDTH5GLCOLOR3F10F,00F,00FGLVERTEX2FP1X,P1YGLVERTEX2FP2X,P2YGLEND/绘制函数VOIDDRAWPOLYGONDOUBLECDGLBEGINGL_LINE_LOOPGLLINEWIDTH10FORINTI0I8II2GLVERTEX2FCDI,CDI1GLEND/绘制函数VOIDDRAWLINEDOUBLECDGLBEGINGL_LINESGLLINEWIDTH10FORINTI0I8II2GLVERTEX2FCDI,CDI1GLEND湖南理工学院图形学结课论文/键盘控制函数切割，当键入C字符时切割，Q字符时退出VOIDMYKEYBOARDUNSIGNEDCHARKEY,INTX,INTYWCPT2DWINMIN100,100WCPT2DWINMAX400,400WCPT2DP10,0WCPT2DP2500,500WCPT2DP11200,300WCPT2DP21300,200WCPT2DP1210,50WCPT2DP2250,10IFKEYCLINECLIPCOHENSUTHERLANDWINMIN,WINMAX,P1,P2LINECLIPCOHENSUTHERLANDWINMIN,WINMAX,P11,P21LINECLIPCOHENSUTHERLANDWINMIN,WINMAX,P12,P22GLFLUSHIFKEYQEXIT0/绘制函数VOIDDISPLAYVOIDDOUBLECD8100,100,100,400,400,400,400,100DOUBLELINE40,0,500,500DOUBLELINE14200,300,300,200湖南理工学院图形学结课论文DOUBLELINE2410,50,50,10GLCLEARGL_COLOR_BUFFER_BITGLVIEWPORT0,0,500,500GLCOLOR3F0,0,0DRAWPOLYGONCDDRAWLINELINEDRAWLINELINE1DRAWLINELINE2GLFLUSH/主函数INTMAININTARGC,CHARARGVGLUTINITGLUTINITDISPLAYMODEGLUT_SINGLE|GLUT_REDGLUTINITWINDOWSIZE500,500GLUTINITWINDOWPOSITION100,100GLUTCREATEWINDOW“COHENSUTHERLAND“GLCLEARCOLOR1,1,1,0GLMATRIXMODEGL_PROJECTIONGLUORTHO2D00,5000,00,5000GLUTKEYBOARDFUNCMYKEYBOARDGLUTDISPLAYFUNCDISPLAYGLUTMAINLOOPRETURN0湖南理工学院图形学结课论文（五）COHENSUTHERLAND算法结果展示当正常运行程序时出现图24图24当按下字符C时完成了对窗口外部线的切割如图25，因为窗口内部线采用了红色，打印可能看不清楚所以用箭头标出了图25