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

河南理工大学万方科技学院课程设计报告2011—2012学年第二学期课程名称计算机图形学设计题目计算机图形学基本算法演示系统设计学生姓名学号专业班级网络11升—1班指导教师徐文鹏2012年5月28日目录I目录第1章设计内容与要求........................................................11.1总体目标和要求..........................................................11.2内容与要求............................................................11.2.1直线的生成.......................................................11.2.2圆弧的生成.......................................................11.2.3线段裁剪.........................................................21.2.4多边形裁剪.......................................................21.2.5综合.............................................................2第2章总体设计..............................................................32.1Bresenham算法画直线...................................................32.1.1Bresenham算法画直线理论基础...........................................32.1.2Bresenham算法画直线原理...............................................32.2Bresenham算法画圆.....................................................42.2.1Bresenham算法画圆理论基础.............................................42.2.2Bresenham算法画圆原理.................................................52.3梁友栋-Barsky算法进行线段裁剪..........................................62.3.1梁友栋-Barsky算法进行线段裁剪基本原理..................................62.4Sutherland-Hodgman算法进行多边形裁剪...................................82.4.1Sutherland—Hodgman多边形裁剪算法思想.................................82.4.2点在边界内侧的判断方法.................................................82.4.4Sutherland-Hodgeman多边形裁剪算法特点.................................8第3章详细设计..............................................................93.1Bresenham算法画直线...................................................93.1.1Bresenham算法画线算法具体实现过程.....................................93.2Bresenham算法画圆.....................................................93.2.1Bresenham算法画圆核心代码.............................................9目录II3.3梁友栋-Barsky算法进行线段裁剪.........................................103.3.1梁友栋-Barsky算法推导过程.............................................103.3.2梁友栋-Barsky算法进行线段裁剪的步骤...................................113.4Sutherland-Hodgman算法进行多边形裁剪..................................113.4.1Sutherland—Hodgman多边形裁剪算法步骤................................113.5将画线、画圆、线段裁剪和多边形裁剪综合.................................12第4章功能实现.............................................................144.1用Bresenham算法画线测试结果...........................................144.2用Bresenham算法画圆测试结果...........................................144.3梁友栋-Barsky算法进行线段裁剪测试结果.................................154.4Sutherland-Hodgman算法进行多边形裁剪测试结果..........................164.5将四种算法综合测试结果................................................16第5章总结.................................................................17参考文献...................................................................18第1章基础知识1第1章设计内容与要求1.1总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够表现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：1)巩固和实践计算机图形学课程中的理论和算法；2)学习表现计算机图形学算法的技巧；3)培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环境：ViusalC++6.0，VC2005或其他你认为比较熟悉的环境。1.2内容与要求实验分为五项内容。1.2.1直线的生成内容：用Bresenham算法画直线要求：1)鼠标移动时，显示鼠标当前位置2)显示判别式的计算过程和下一点的选择策略3)记录生成点的坐标4)图形生成过程可以重复进行1.2.2圆弧的生成内容：用Bresenham算法画圆要求：1)鼠标移动时，显示鼠标当前位置2)显示判别式的计算过程和下一点的选择策略3)记录生成点的坐标4)图形生成过程可以重复进行5)橡皮筋技术实现第1章基础知识21.2.3线段裁剪内容：用梁友栋-Barsky算法进行线段裁剪要求：1)对于线段裁剪，线段被窗口的四条边裁剪的过程要显示出来2)用橡皮筋的形式输入剪裁线段1.2.4多边形裁剪内容：用Sutherland-Hodgman算法进行多边形裁剪要求：1)裁剪过程需先输入一多边形，然后用窗口四边裁剪的过程中要显示顶点增删过程。2)用橡皮筋的形式输入剪裁线段1.2.5综合内容：把前四次的实验内容整合到一起要求：第2章总体设计3第2章总体设计2.1Bresenham算法画直线2.1.1Bresenham算法画直线理论基础计算机是如何画直线的？简单来说，就是过各行各列像素中心构造一组虚拟的网格线，按直线从起点到终点的顺序计算各直线与歌垂直网格线的交点，然后确定各列像素中与此交点最近的像素。真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。2.1.2Bresenham算法画直线原理接下来的问题就是如何尽可能高效地找到这些离散的点，Bresenham直线算法就是一个非常不错的算法。Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在n维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。第2章总体设计4这个算法的流程图如下：可以看到，算法其实只考虑了斜率在0~1之间的直线，也就是与x轴夹角在0度到45度的直线。只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。2.2Bresenham算法画圆2.2.1Bresenham算法画圆理论基础Bresenham画圆算法与Bresenham直线算法一样，其基本的方法是利用判别变量来判断第2章总体设计5选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑一个圆心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。为什么只计算八分圆周上的点就可以了呢？和上面的直线算法类似，圆也有一个“八对称性”，如下图所示。显然，我们只需要知道了圆上的一个点的坐标(x,y)，利用八对称性，我们马上就能得到另外七个对称点的坐标。2.2.2Bresenham算法画圆原理和直线算法类似，Bresenham画圆算法也是用一系列离散的点来近似描述一个圆，如下图。第2章总体设计6Bresenham画圆算法的流程图如下。可以看到，与画线算法相比，画圆的循环中用到了整数的乘法，相对复杂了一些。2.3梁友栋-Barsky算法进行线段裁剪2.3.1梁友栋-Barsky算法进行线段裁剪基本原理我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：x=x1+u·（x2-x1）=x1+u·Δx，y=y1+u·（y2-y1）=y1+u·Δy式中，Δx=x2-x1，Δy=y2-y1，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式第2章总体设计7可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xwmin，ywmin）和（xwmax，ywmax）所确定的窗口内，那么下式成立：xwmin≤x1+u·Δx≤xwmax，ywmin≤y1+u·Δy≤ywmax这四个不等式可以表示为：u·pk≤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，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk≥0，则线段平行于窗口某边界并在窗口内，见图中所示。1、当pk0时，线段从裁剪边界延长线的外部延伸到内部；2、当pk0时，线段从