课程设计（论文）-Barsky直线裁剪算法计算机图形学课程设计

河南理工大学万方科技学院课程设计报告2011 2012 学年第二学期课程名称 计算机图形学 设计题目 计算机图形学基本算法 演示系统设计 学生姓名 学 号 专业班级 网络 11 升1 班 指导教师 徐 文 鹏 2012 年 5 月 28 日 目 录目 录第 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 Bresenham 算法画圆 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.1 Bresenham 算法画圆核心代码 9目 录I3.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 算法进行多边形裁剪测试结果 164.5 将四种算法综合测试结果 .16第 5 章 总结 17参考文献 18第 1 章 基础知识0第 1 章 设计内容与要求1.1 总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：1) 巩固和实践计算机图形学课程中的理论和算法；2) 学习表现计算机图形学算法的技巧；3) 培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环境：Viusal C+ 6.0，VC2005 或其他你认为比较熟悉的环境。1.2 内容与要求实验分为五项内容。1.2.1 直线的生成内容：用 Bresenham 算法画直线要求：1) 鼠标移动时，显示鼠标当前位置2) 显示判别式的计算过程和下一点的选择策略3) 记录生成点的坐标4) 图形生成过程可以重复进行1.2.2 圆弧的生成内容：用 Bresenham 算法画圆要求：1) 鼠标移动时，显示鼠标当前位置2) 显示判别式的计算过程和下一点的选择策略3) 记录生成点的坐标4) 图形生成过程可以重复进行第 1 章 基础知识15) 橡皮筋技术实现1.2.3 线段裁剪内容：用梁友栋-Barsky 算法进行线段裁剪要求：1) 对于线段裁剪，线段被窗口的四条边裁剪的过程要显示出来2) 用橡皮筋的形式输入剪裁线段1.2.4 多边形裁剪内容：用 Sutherland-Hodgman 算法进行多边形裁剪要求：1) 裁剪过程需先输入一多边形，然后用窗口四边裁剪的过程中要显示顶点增删过程。2) 用橡皮筋的形式输入剪裁线段1.2.5 综合内容：把前四次的实验内容整合到一起要求：第 2 章 总体设计2第 2 章 总体设计2.1 Bresenham 算法画直线2.1.1 Bresenham 算法画直线理论基础计算机是如何画直线的？简单来说，就是过各行各列像素中心构造一组虚拟的网格线，按直线从起点到终点的顺序计算各直线与歌垂直网格线的交点，然后确定各列像素中与此交点最近的像素。真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。2.1.2 Bresenham 算法画直线原理接下来的问题就是如何尽可能高效地找到这些离散的点， Bresenham 直线算法就是一个非常不错的算法。Bresenham 直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。第 2 章 总体设计3这个算法的流程图如下：可以看到，算法其实只考虑了斜率在 0 1 之间的直线，也就是与 x 轴夹角在 0 度到 45 度的直线。只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。2.2 Bresenham 算法画圆2.2.1 Bresenham 算法画圆理论基础Bresenham 画圆算法与 Bresenham 直线算法一样，其基本的方法是利用判别变量来判第 2 章 总体设计4断选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑一个圆心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。为什么只计算八分圆周上的点就可以了呢？和上面的直线算法类似，圆也有一个“八对称性”，如下图所示。 显然，我们只需要知道了圆上的一个点的坐标 (x, y) ，利用八对称性，我们马上就能得到另外七个对称点的坐标。 2.2.2 Bresenham 算法画圆原理和直线算法类似，Bresenham 画圆算法也是用一系列离散的点来近似描述一个圆，如下图。 第 2 章 总体设计5Bresenham 画圆算法的流程图如下。 可以看到，与画线算法相比，画圆的循环中用到了整数的乘法，相对复杂了一些。 2.3 梁友栋 -Barsky 算法进行线段裁剪2.3.1 梁友栋-Barsky 算法进行线段裁剪基本原理我们知道，一条两端点为 P1（x1，y1） 、P2（x2，y2）的线段可以用参数方程形式表示：x= x1+ u（x2-x1）= x1+ ux，y= y1+ u（y2-y1 ）= y1+ uy 式中，x=x2-x1，y=y2-第 2 章 总体设计6y1，参数 u 在 01 之间取值，P（x，y）代表了该线段上的一个点，其值由参数 u 确定，由公式可知，当 u=0 时，该点为 P1（x1，y1） ，当 u=1 时，该点为 P2（x2，y2） 。如果点P（x，y）位于由坐标（xwmin ，ywmin ）和（xwmax，ywmax）所确定的窗口内，那么下式成立：xwminx1+ uxxwmax，ywminy1+ uyywmax这四个不等式可以表示为：upk qk ， k=1，2，3，4其中，p、q 定义为 p1=-x， q1=x1-xwminp2= x， q2=xwmax-x1p3=-y， q3=y1-ywminp4= y， q4=ywmax-y1可以知道：任何平行于窗口某边界的直线，其 pk=0，k 值对应于相应的边界（k=1，2，3， 4 对应于左、右、下、上边界） 。如果还满足 qk0 时，线段从裁剪边界延长线的内部延伸到外部；例如，当 x0 时，对于左边界 p10（p2=x） ，线段从右边界的内部到外部。当 y0（p3=-y ） ，线段从下边界的内部到外部；对于上边界p40） ，对这些边界计算rk=qk/pk，u2 取 0 和各个 r 值之中的最小值。3、如果 u1u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端第 2 章 总体设计7点可以由 u1 和 u2 计算出来。2.4 Sutherland-Hodgman 算法进行多边形裁剪2.4.1 SutherlandHodgman 多边形裁剪算法思想该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形） 。当多边形一个顶点 Pi 相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）：1、顶点 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 点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点 A 向终点 B 看过去：如果被测试点 P 在该边界线右边(即内侧)，ABAP 的方向与 X-Y 平面垂直并指向屏幕里面，即右手坐标系中 Z 轴的负方向。反过来，如果 P 在该边界线的左边(即外侧)，这时 ABAP 的方向与 X-Y 平面垂直并指向屏幕外面，即右手坐标系中 Z 轴的正方向。设：点 P(x，y)、点 A(xA，yA)、点 B(xB，yB)，向量AB=(xB-xA)，(yB-yA)，向量 AP=(x-xA)，(y-yA)，那么 ABAP 的方向可由下式的符号来确定：V=(xB-xA)*(y-yA)- (x-xA)*(yB-yA) 因此，当 V0 时，P 在边界线内侧；而 V0 时，P 在边界线外侧。2.4.4 Sutherland-Hodgeman 多边形裁剪算法特点SutherlandHodgeman 多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依第 2 章 总体设计8次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。第 3 章 详细设计9第 3 章 详细设计3.1 Bresenham 算法画直线3.1.1 Bresenham 算法画线算法具体实现过程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|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=0 且 q2=0,则进一步判断 u=qk/pk（k=3,4） 令 u1=max(0,u|pk0)若 u1u2,则可删除直线段若 u1=0 且 q4=0,则进一步判断u=qk/pk（k=1,2）令 u1=max(0,u|pk0)若 u1u2,则可删除直线段若 u10, u|pk0)若 u1u2,则可删除直线段若 u10 且 q20，则进一步计算 u1 和 u2。转(5)。 (3) 若 y=0，则 p3=p4=0。进一步判断是否满足 q30 且 q20，则进一步计算 u1 和 u2。转(5)。(4) 若上述两条均不满足,则有 pk0(k=1,2,3,4)。此时计算 u1 和 u2。(5) 求得 u1 和 u2 后,进行判断：若 u1u2,则直线段在窗口外,转(7)。若 u1u2,利用直线的参数方程求得直线段在窗口内的两端点坐标。(6) 利用直线的扫描转换算法绘制在窗口内的直线段。(7) 算法结束。3.4 Sutherland-Hodgman 算法进行多边形裁剪3.4.1 SutherlandHodgman 多边形裁剪算法步骤考虑多边形相对于一条边界及其延长线进行裁剪的算法：1 从主函数得到待裁剪多边形的顶点序列 P2、顶点序列数 n、窗口一条边界参数 xl（假如为矩形窗口的左边界） ；2 赋初值：将顶点序列中的最后一个顶点赋给前一顶点 S；设置初始标志 flag：if(S 在边界内侧)flag=0;else flag=1；设新的顶点序列数 j=0；3 对多边形各顶点进行裁剪规则处理，结果放入新的多边形顶点序列 Q2中： for(对第一个顶点直到最后一个顶点，逐一处理）if(Pi 在边界内侧)if(flag!=0)flag=0;第 3 章 详细设计12求交点并放入新的多边形顶点序列 Qj 中；j+；将当前顶点放入新的多边形顶点序列 Qj 中：Qj=Pi；j+；Elseif(flag=0)flag=1;求交点并放入新的多边形顶点序列 Qj 中；j+；将当前顶点赋给 S：S=Pi；4 做返回准备：5 将新的多边形顶点序列 Q 又逐一放回原多边形顶点序列 P 中：P=Q；6 将新的多边形顶点数 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;case 3:select = 3;glutPostRedisplay();第 3 章 详细设计13break;case 4:select =4;glutPostRedisplay();break;default: break;void createGLUTMenus() int menu;menu = glutCreateMenu(processMenuEvents);glutAddMenuEntry(“Bresenham Line“,1);glutAddMenuEntry(“Bresenham Circle“,2);glutAddMenuEntry(“Liang-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();else if(select=3) myDisplay_cut();else if(select=4) myDisplay_cutGraphics();glutSwapBuffers();glFlush();第 4 章 功能实现14第 4 章 功能实现4.1 用 Bresenham 算法画线测试结果打开 vc+6.0,加载画线代码并运行，点击画线并输入数