梁友栋-Barsky直线裁剪算法计算机图形学课程设计

1、河南理工大学万方科技学院课程设计报告2011 2012学年第二学期课程名称 计算机图形学 设计题目 计算机图形学基本算法 演示系统设计 学生姓名 学 号 专业班级 网络11升1班 指导教师 徐 文 鹏 2012 年 5 月 28 日18目 录目 录第1章 设计内容与要求11.1总体目标和要求11.2内容与要求 11.2.1 直线的生成11.2.2 圆弧的生成11.2.3 线段裁剪21.2.4 多边形裁剪21.2.5 综合2第2章 总体设计32.1 Bresenham算法画直线32.1.1 Bresenham算法画直线理论基础32.1.2 Bresenham算法画直线原理32.2 Bresenh

2、am算法画圆42.2.1 Bresenham算法画圆理论基础42.2.2 Bresenham算法画圆原理52.3 梁友栋-Barsky算法进行线段裁剪62.3.1梁友栋-Barsky算法进行线段裁剪基本原理62.4 Sutherland-Hodgman算法进行多边形裁剪82.4.1 SutherlandHodgman多边形裁剪算法思想82.4.2 点在边界内侧的判断方法82.4.4 Sutherland-Hodgeman多边形裁剪算法特点8第3章 详细设计93.1 Bresenham算法画直线93.1.1 Bresenham 算法画线算法具体实现过程93.2 Bresenham算法画圆93.2

3、.1 Bresenham 算法画圆核心代码93.3 梁友栋-Barsky算法进行线段裁剪103.3.1梁友栋-Barsky算法推导过程103.3.2梁友栋-Barsky算法进行线段裁剪的步骤113.4 Sutherland-Hodgman算法进行多边形裁剪113.4.1 SutherlandHodgman多边形裁剪算法步骤113.5将画线、画圆、线段裁剪和多边形裁剪综合12第4章 功能实现144.1用Bresenham算法画线测试结果144.2用Bresenham算法画圆测试结果144.3梁友栋-Barsky算法进行线段裁剪测试结果154.4 Sutherland-Hodgman算法进行多边形

4、裁剪测试结果164.5将四种算法综合测试结果16第5章 总结17参考文献18第1章 基础知识第1章 设计内容与要求1.1 总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：1) 巩固和实践计算机图形学课程中的理论和算法；2) 学习表现计算机图形学算法的技巧；3) 培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环

5、境：Viusal C+ 6.0，VC2005或其他你认为比较熟悉的环境。1.2 内容与要求实验分为五项内容。1.2.1 直线的生成内容：用Bresenham算法画直线要求：1) 鼠标移动时，显示鼠标当前位置2) 显示判别式的计算过程和下一点的选择策略3) 记录生成点的坐标4) 图形生成过程可以重复进行1.2.2 圆弧的生成内容：用Bresenham算法画圆要求：1) 鼠标移动时，显示鼠标当前位置2) 显示判别式的计算过程和下一点的选择策略3) 记录生成点的坐标4) 图形生成过程可以重复进行5) 橡皮筋技术实现1.2.3 线段裁剪内容：用梁友栋-Barsky算法进行线段裁剪要求：1) 对于线段裁

6、剪，线段被窗口的四条边裁剪的过程要显示出来2) 用橡皮筋的形式输入剪裁线段1.2.4 多边形裁剪内容：用Sutherland-Hodgman算法进行多边形裁剪要求：1) 裁剪过程需先输入一多边形，然后用窗口四边裁剪的过程中要显示顶点增删过程。2) 用橡皮筋的形式输入剪裁线段1.2.5 综合内容：把前四次的实验内容整合到一起要求：第2章 总体设计第2章 总体设计2.1 Bresenham算法画直线2.1.1 Bresenham算法画直线理论基础计算机是如何画直线的？简单来说，就是过各行各列像素中心构造一组虚拟的网格线，按直线从起点到终点的顺序计算各直线与歌垂直网格线的交点，然后确定各列像素中与此

7、交点最近的像素。真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。2.1.2 Bresenham算法画直线原理接下来的问题就是如何尽可能高效地找到这些离散的点，Bresenham直线算法就是一个非常不错的算法。Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。这个算法的流程图如下：可以看到，算法其实只考虑了斜率在 0 1 之间的直线，也就是与

8、x 轴夹角在 0 度到 45 度的直线。只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。 2.2 Bresenham算法画圆2.2.1 Bresenham算法画圆理论基础Bresenham画圆算法与Bresenham 直线算法一样，其基本的方法是利用判别变量来判断选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑一个圆心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。为什么只计算八分圆周上的点就可以了呢？和上面的直线算法类似，圆也有一个“八对称性”，如下图所示。 显然，我们只需要知道了圆上的一

9、个点的坐标 (x, y) ，利用八对称性，我们马上就能得到另外七个对称点的坐标。 2.2.2 Bresenham算法画圆原理和直线算法类似，Bresenham画圆算法也是用一系列离散的点来近似描述一个圆，如下图。 Bresenham画圆算法的流程图如下。 可以看到，与画线算法相比，画圆的循环中用到了整数的乘法，相对复杂了一些。 2.3 梁友栋-Barsky算法进行线段裁剪2.3.1梁友栋-Barsky算法进行线段裁剪基本原理我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：x= x1+ u·（x2-x1）= x1+ u·x，y= y1

10、+ u·（y2-y1）= y1+ u·y式中，x=x2-x1，y=y2-y1，参数u在01之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xwmin，ywmin）和（xwmax，ywmax）所确定的窗口内，那么下式成立：xwminx1+ u·xxwmax，ywminy1+ u·yywmax这四个不等式可以表示为：u·pk qk ， k=1，2，3，4其中，p、q定义为p1=-x， q1=x1-xwminp2= x

11、， q2=xwmax-x1p3=-y， q3=y1-ywminp4= y， q4=ywmax-y1可以知道：任何平行于窗口某边界的直线，其pk=0，k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足qk<0，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk0，则线段平行于窗口某边界并在窗口内，见图中所示。1、当pk<0时，线段从裁剪边界延长线的外部延伸到内部；2、当pk>0时，线段从裁剪边界延长线的内部延伸到外部；例如，当x0时，对于左边界p1<0（p1=-x），线段从左边界的外部到内部；对于右边界p2>0（p2=x），线段从右边

12、界的内部到外部。当y<0时，对于下边界p3>0（p3=-y），线段从下边界的内部到外部；对于上边界p4<0（p4=y），线段从上边界的外部到内部。当pK0时，可以计算出参数u的值，它对应于无限延伸的直线与延伸的窗口边界k的交点，即：对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：1、u1的值由线段从外到内遇到的矩形边界所决定（pk<0），对这些边界计算rk=qk/pk，u1取0和各个r值之中的最大值。2、u2的值由线段从内到外遇到的矩形边界所决定（pk>0），对这些边界计算rk=qk/pk，u2取0和各个r值之中的最小值。3、如果u1>

13、;u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。2.4 Sutherland-Hodgman算法进行多边形裁剪2.4.1 SutherlandHodgman多边形裁剪算法思想该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。当多边形一个顶点Pi相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）：1、顶

14、点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列；2、顶点Pi在内侧，前一顶点Pi-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列；3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列；4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。2.4.2 点在边界内侧的判断方法为了判断点是否在边界内侧可用坐标比较法和更通用的向量叉积符号判别法。1、坐标比较法将点的某个方向分量与边界进行比较。例如，判断某点是否在下边界内侧,用条件判别式： if(pi1>=ymin) 即可。2、向量叉积法为简单计，测试点表示为P点。假设窗口边界

15、方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点A向终点B看过去：如果被测试点P在该边界线右边(即内侧)，AB×AP的方向与X-Y平面垂直并指向屏幕里面，即右手坐标系中Z轴的负方向。反过来，如果P在该边界线的左边(即外侧)，这时AB×AP的方向与X-Y平面垂直并指向屏幕外面，即右手坐标系中Z轴的正方向。设：点P(x，y)、点A(xA，yA)、点B(xB，yB)，向量AB=(xB-xA)，(yB-yA)，向量AP=(x-xA)，(y-yA)，那么AB×AP的方向可由下式的符号来确定：V=(xB-xA)*(y-yA)- (x-xA)*(yB-yA) 因此，当

16、V0时，P在边界线内侧；而V>0时，P在边界线外侧。2.4.4 Sutherland-Hodgeman多边形裁剪算法特点SutherlandHodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。第3章 详细设计第3章 详细设计3.1 Bresenham算法画直线3.1.1 Bresenham 算法画线算法具体实现过程1、画点(x1, y2)

17、; 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<dx+1则转2；否则end。由上述算法思想编制算法程序。这个程序适用于所有8个方向的直线的生成。程序画出一条端点为（x1, y1）和（x2, y2）的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量

18、；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断|dx|>|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。3.2 Bresenham算法画圆3.2.1 Bresenham 算法画圆核心代码根据Bresenham算法思想编写程序代码，在Bresenham算法画线的基础上画圆，程序代码如下：void BresenhamCircle(int x0,int y0,int R)/,int color) int x,y,d; x=0;y=R; d=3-2*R;while(x<

19、y) glColor3f (0.0f, 1.0f, 0.0f); putpixel(x0+x,y0+y); putpixel(x0+x,y0-y); putpixel(x0-x,y0+y); putpixel(x0-x,y0-y); putpixel(x0+y,y0+x); putpixel(x0+y,y0-x); putpixel(x0-y,y0+x); putpixel(x0-y,y0-x); if(d<0) d=d+4*x+6; elsed=d+4*(x-y)+10;y=y-1; x+; 3.3 梁友栋-Barsky算法进行线段裁剪3.3.1梁友栋-Barsky算法推导过程情形一&

20、#160;  pk=0p1p20若q1<0或q2<0，则可删除直线段 若q1>=0且q2>=0,则进一步判断      u=qk/pk（k=3,4） 令  u1=max(0,u|pk<0)     u2=min(1,u|pk>0)若u1>u2,则可删除直线段若u1<=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。p3p40 若q3<0或q4<0，则可删除直线段若q3>=0且q4>=0,则进一步判断

21、60;    u=qk/pk（k=1,2）令  u1=max(0,u|pk<0)     u2=min(1,u|pk>0)若u1>u2,则可删除直线段若u1<=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。情形二   pk不为0u=qk/pk（k=1,2,3,4）令 u1=max(0,u|pk<0,u|pk<0)u2=min(1,u|pk>0, u|pk>0)若u1>u2,则可删除直线段若u1<=u2,将u1,u2

22、代入直线方程，得到直线段的两个可见端点。3.3.2梁友栋-Barsky算法进行线段裁剪的步骤(1) 输入直线段的两端点坐标以及窗口的四条边界坐标。(2) 若x=0，则p1=p2=0。进一步判断是否满足q1<0或q2<0，若满足，则该直线段不在窗口内，转(7)。否则，满足q1>0且q2>0，则进一步计算u1和u2。转(5)。 (3) 若y=0，则p3=p4=0。进一步判断是否满足q3<0或q4<0，若满足，则该直线段不在窗口内，转(7)。否则，满足q1>0且q2>0，则进一步计算u1和u2。转(5)。(4) 若上述两条均不满足,则有pk0(k=1,

23、2,3,4)。此时计算u1和u2。(5) 求得u1和u2后,进行判断：若u1>u2,则直线段在窗口外,转(7)。若u1<u2,利用直线的参数方程求得直线段在窗口内的两端点坐标。(6) 利用直线的扫描转换算法绘制在窗口内的直线段。(7) 算法结束。3.4 Sutherland-Hodgman算法进行多边形裁剪3.4.1 SutherlandHodgman多边形裁剪算法步骤考虑多边形相对于一条边界及其延长线进行裁剪的算法：1 从主函数得到待裁剪多边形的顶点序列P2、顶点序列数n、窗口一条边界参数xl（假如为矩形窗口的左边界）；2 赋初值：将顶点序列中的最后一个顶点赋给前一顶点S；设置初

24、始标志flag：if(S在边界内侧)flag=0;else flag=1；设新的顶点序列数j=0；3 对多边形各顶点进行裁剪规则处理，结果放入新的多边形顶点序列Q2中： for(对第一个顶点直到最后一个顶点，逐一处理）if(Pi在边界内侧) if(flag!=0) flag=0;求交点并放入新的多边形顶点序列Qj中； j+； 将当前顶点放入新的多边形顶点序列Qj中：Qj=Pi； j+； Elseif(flag=0) flag=1;求交点并放入新的多边形顶点序列Qj中； j+； 将当前顶点赋给S：S=Pi； 4 做返回准备：5 将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中：P=Q；6 将

25、新的多边形顶点数j放回原多边形顶点数n中：n=j；3.5将画线、画圆、线段裁剪和多边形裁剪综合在显示函数中将各个算法添加到一个程序中，使用右键菜单的特殊功能实现画线、画圆、线段裁剪和多边形裁剪，主要是processMenuEvents函数和createGLUTMenus函数的编写。这两个函数的程序代码如下：void processMenuEvents(int option) switch (option) case 1:select = 1; glutPostRedisplay(); break;case 2: select = 2; glutPostRedisplay(); break;ca

26、se 3:select = 3; glutPostRedisplay(); break;case 4:select =4; glutPostRedisplay(); break;default: break;void createGLUTMenus() int menu;menu = glutCreateMenu(processMenuEvents);glutAddMenuEntry("Bresenham Line",1);glutAddMenuEntry("Bresenham Circle",2); glutAddMenuEntry("Lia

27、ng-Barsky Cut",3);glutAddMenuEntry("Sutherland-Hodgman Cut",4);glutAttachMenu(GLUT_RIGHT_BUTTON); void Display() glClear(GL_COLOR_BUFFER_BIT); Wangge();glColor3f (0.0f, 0.0f, 0.0f); glRectf(rect.xmin,rect.ymin,rect.xmax,rect.ymax);if(select = 1) myDisplay_Line();else if(select=2) myDisplay_Circle();