直线段与多边形的裁剪.doc

目 录第 2 章 总体设计课程名称：《计算机图形学》论文题目：直线段与多边形的裁剪教学部： ＿ 年 级： 08级 班 级： 信息与计算科学 学 号： 00868036 姓 名： 马文尧 第 2 章 总体设计多边形裁剪算法设计的内容和要求摘要: 本文讨论了直线段的剪裁与任意多边形的剪裁关键词：Sutherland-Hodgman；；Cohen-Sutherland；barskey；多边形剪裁主要内容； 1）理解多边形裁剪与直线段裁剪的区别； 2）掌握多边形的裁剪过程； 3）理解并掌握 Sutherland-Hodgman 算法的裁剪思想 1 设计原理1.1.1 直线裁剪的基本原理图1所示的为直线与窗口边界之间可能出现的几种关系可以通过检查直线的两个端点是否在窗口之内确定如何对此直线裁剪如果一直线的两个端点均第 2 章 总体设计在窗口边界之内（如图1中P5到P6的直线），则此直线应保留如果一条直线的一个端点在窗口外（如P9）另一个点在窗口内（如P10），则应从直线与边界的交点（P9）处裁剪掉边界之外的线段如果直线的两个端点均在边界外，则可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。

图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保留P7到P8的线段，其余部分均裁剪掉图 1 直线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保留或全部裁剪，剩下的即为部分裁剪的直线对于部分裁剪的直线则首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的部分裁剪掉一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点1.1.2 直线裁剪算法的分类以及和窗口交点参数值的计算直线段裁剪算法是复杂图形裁剪的基础复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题主要的四种算法直接求交算法第 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）与窗口边界的比较求得如果 x0 时，参数 r 用于更新 u2 （u2=min{u2，…，rk}）（3）如果更新了 u1 或 u2 后，使 u1>u2，则舍弃该线段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 Pi>0 则 yi+1=yi+1；否则 yi+1=yi；3、画点（xi+1, yi-1） ；4、求下一个误差 Pi+1；if Pi>0 则 Pi+1=Pi+2dy-2dx;否则 Pi+1=Pi+2dy；5、i=i+1; if i=y 为止。

误差量由Ｆ(x,y)=x^2+y^2-R^2 给出 先找递推关系，若当前 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-R^2=(x+1)^2+(x-0.5)^2-R^2+2x+3-2y+2=d+2x-2y+5，若当前 d=F(x+1,y-0.5)0 即 d>0.25，这和 d>0 等价，所以 d 取初值 1-R第 3 章 详细设计3.3 用梁友栋-Barsky 算法进行线段裁剪设窗口为下列方程所确定：x=XL x=XR (记 XL≤x≤XR 的区域为 Δx)y=YB y=YT (记 YB≤y≤YT 的区域为 Δy)则平面上任意线段 P1P2 在窗口内的部分为：P1P2∩Δx∩Δy 设通过 P1P2 的直线与窗口左、右、上、下边界的交点分别为 L、R、B、T，则 P1P2 可见部分亦可表为：P1P2∩LR∩BT 当直线垂直时：xp1=xp2 且 XL≤xp1≤XR 时，P1P2∩LR∩BT 等价于求 P1P2∩BT；当直线平行时：yp1=yp2 且 YB≤yp1≤YT 时，P1P2∩LR∩BT 等价于求 P1P2∩LR；当直线既不垂直又不平行时：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 =0) inc=1;else inc=-1;if(abs(dx)>abs(dy)){if(dx*u2){retVal=0;accept=false;}else if(r>*u1) *u1=r; //*u1 取“进入“点的最大参数值}else if(p>0.0) {r=q/p;if(r0.0){*x1=*x1+u1*dx; //通过 u1 求得裁剪后的 p1 端点*y1=*y1+u1*dy;}}}}void keyboard(unsigned char key,int x,int y)//键盘事件，按键盘'C'键进行裁剪第 4 章 功能实现{switch(key){case 'c':clipLine(rect.xmin ,rect.ymin ,rect.xmax ,rect.ymax ,glutPostRedisplay();break;default:break;}}5 总结这次的图形学课程设计让我收获不小，到真正自己动手做的时候才会发现不足之处在做设计的期间，又温习了原来所学的知识，可以吧知识系统的归纳。

任何知识和理论都要归结于实践参考文献1.《计算机图形学》 ，徐文鹏，机械工业出版社2.《计算机图形学课程设计》 ，唐敏，浙江大学出版社，2008 年 11 月3.《计算机图形学》 ，吴庆标，韩丹夫，浙江大学出版社，2006 年 6 月4. 《OpenGL 编程指南》 ，Dave Shreiner 著，机械工业出版社，2008 年 3 月5. 中国地质大学信息工程学院，2010 年 6 月，。