Barsky直线裁剪算法计算机图形学课程设计

PAGE河南理工大学万方科技学院课程设计报告2011—2012学年第二学期课程名称计算机图形学设计题目计算机图形学基本算法演示系统设计学生姓名学号专业班级网络11升—1班指导教师徐文鹏2012年5月28日目录目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc326503878"第1章设计内容与要求PAGEREF_Toc326503878\h1HYPERLINK\l"_Toc326503879"1.1总体目标和要求PAGEREF_Toc326503879\h1HYPERLINK\l"_Toc326503880"1.2内容与要求PAGEREF_Toc326503880\h1HYPERLINK\l"_Toc326503881"直线的生成PAGEREF_Toc326503881\h1HYPERLINK\l"_Toc326503882"圆弧的生成PAGEREF_Toc326503882\h1HYPERLINK\l"_Toc326503883"线段裁剪PAGEREF_Toc326503883\h2HYPERLINK\l"_Toc326503884"多边形裁剪PAGEREF_Toc326503884\h2HYPERLINK\l"_Toc326503885"综合PAGEREF_Toc326503885\h2HYPERLINK\l"_Toc326503886"第2章总体设计3HYPERLINK\l"_Toc326503887"2.1Bresenham算法画直线PAGEREF_Toc326503887\h3HYPERLINK\l"_Toc326503888"Bresenham算法画直线理论基础PAGEREF_Toc326503888\h3HYPERLINK\l"_Toc326503889"Bresenham算法画直线原理PAGEREF_Toc326503889\h3HYPERLINK\l"_Toc326503890"2.2Bresenham算法画圆PAGEREF_Toc326503890\h4HYPERLINK\l"_Toc326503891"算法画圆理论基础PAGEREF_Toc326503891\h4HYPERLINK\l"_Toc326503892"算法画圆原理PAGEREF_Toc326503892\h5HYPERLINK\l"_Toc326503893"2.3梁友栋-Barsky算法进行线段裁剪PAGEREF_Toc326503893\h6HYPERLINK\l"_Toc326503894"梁友栋-Barsky算法进行线段裁剪基本原理PAGEREF_Toc326503894\h6HYPERLINK\l"_Toc326503895"2.4Sutherland-Hodgman算法进行多边形裁剪PAGEREF_Toc326503895\h8HYPERLINK\l"_Toc326503896"多边形裁剪算法思想PAGEREF_Toc326503896\h8HYPERLINK\l"_Toc326503897"点在边界内侧的判断方法PAGEREF_Toc326503897\h8HYPERLINK\l"_Toc326503898"多边形裁剪算法特点PAGEREF_Toc326503898\h8HYPERLINK\l"_Toc326503899"第3章详细设计9HYPERLINK\l"_Toc326503900"3.1Bresenham算法画直线PAGEREF_Toc326503900\h9HYPERLINK\l"_Toc326503901"算法画线算法具体实现过程PAGEREF_Toc326503901\h9HYPERLINK\l"_Toc326503902"3.2Bresenham算法画圆PAGEREF_Toc326503902\h9HYPERLINK\l"_Toc326503903"算法画圆核心代码PAGEREF_Toc326503903\h9HYPERLINK\l"_Toc326503904"3.3梁友栋-Barsky算法进行线段裁剪PAGEREF_Toc326503904\h10HYPERLINK\l"_Toc326503905"梁友栋-Barsky算法推导过程PAGEREF_Toc326503905\h10HYPERLINK\l"_Toc326503906"梁友栋-Barsky算法进行线段裁剪的步骤PAGEREF_Toc326503906\h11HYPERLINK\l"_Toc326503907"3.4Sutherland-Hodgman算法进行多边形裁剪PAGEREF_Toc326503907\h11HYPERLINK\l"_Toc326503908"多边形裁剪算法步骤PAGEREF_Toc326503908\h11HYPERLINK\l"_Toc326503909"3.5将画线、画圆、线段裁剪和多边形裁剪综合PAGEREF_Toc326503909\h12HYPERLINK\l"_Toc326503910"第4章功能实现14HYPERLINK\l"_Toc326503911"4.1用Bresenham算法画线测试结果PAGEREF_Toc326503911\h14HYPERLINK\l"_Toc326503912"4.2用Bresenham算法画圆测试结果PAGEREF_Toc326503912\h14HYPERLINK\l"_Toc326503913"4.3梁友栋-Barsky算法进行线段裁剪测试结果PAGEREF_Toc326503913\h15HYPERLINK\l"_Toc326503914"4.4Sutherland-Hodgman算法进行多边形裁剪测试结果PAGEREF_Toc326503914\h16HYPERLINK\l"_Toc326503915"4.5将四种算法综合测试结果PAGEREF_Toc326503915\h16第5章 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 17HYPERLINK\l"_Toc326503917"参考文献18第1章基础知识第1章基础知识设计内容与要求总体目标和要求目标：以图形学算法为目标，深入研究。继而策划、设计并实现一个能够 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现计算机图形学算法原理的或完整过程的演示系统，并能从某些方面作出评价和改进意见。通过完成一个完整程序，经历策划、设计、开发、测试、总结和验收各阶段，达到：巩固和实践计算机图形学课程中的理论和算法；学习表现计算机图形学算法的技巧；培养认真学习、积极探索的精神。总体要求：策划、设计并实现一个能够充分表现图形学算法的演示系统，界面要求美观大方，能清楚地演示算法执行的每一个步骤。开发环境：ViusalC++6.0，VC2005或其他你认为比较熟悉的环境。内容与要求实验分为五项内容。内容：用Bresenham算法画直线要求：鼠标移动时，显示鼠标当前位置显示判别式的计算过程和下一点的选择策略 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 生成点的坐标图形生成过程可以重复进行内容：用Bresenham算法画圆要求：鼠标移动时，显示鼠标当前位置显示判别式的计算过程和下一点的选择策略记录生成点的坐标图形生成过程可以重复进行橡皮筋技术实现内容：用梁友栋-Barsky算法进行线段裁剪要求：对于线段裁剪，线段被窗口的四条边裁剪的过程要显示出来用橡皮筋的形式输入剪裁线段内容：用Sutherland-Hodgman算法进行多边形裁剪要求：裁剪过程需先输入一多边形，然后用窗口四边裁剪的过程中要显示顶点增删过程。用橡皮筋的形式输入剪裁线段内容：把前四次的实验内容整合到一起要求：第2章总体设计第4章功能实现第2章总体设计2.1Bresenham算法画直线Bresenham算法画直线理论基础计算机是如何画直线的？简单来说，就是过各行各列像素中心构造一组虚拟的网格线，按直线从起点到终点的顺序计算各直线与歌垂直网格线的交点，然后确定各列像素中与此交点最近的像素。真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。Bresenham算法画直线原理接下来的问题就是如何尽可能高效地找到这些离散的点，Bresenham直线算法就是一个非常不错的算法。Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在n维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。这个算法的流程图如下：　　可以看到，算法其实只考虑了斜率在0~1之间的直线，也就是与x轴夹角在0度到45度的直线。只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。2.2Bresenham算法画圆Bresenham画圆算法与Bresenham直线算法一样，其基本的方法是利用判别变量来判断选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑一个圆心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。为什么只计算八分圆周上的点就可以了呢？和上面的直线算法类似，圆也有一个“八对称性”，如下图所示。显然，我们只需要知道了圆上的一个点的坐标(x,y)，利用八对称性，我们马上就能得到另外七个对称点的坐标。和直线算法类似，Bresenham画圆算法也是用一系列离散的点来近似描述一个圆，如下图。Bresenham画圆算法的流程图如下。可以看到，与画线算法相比，画圆的循环中用到了整数的乘法，相对复杂了一些。2.3梁友栋-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确定，由公式可知，当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对应于左、右、下、上边界）。如果还满足qk<0，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk≥0，则线段平行于窗口某边界并在窗口内，见图中所示。1、当pk<0时，线段从裁剪边界延长线的外部延伸到内部；2、当pk>0时，线段从裁剪边界延长线的内部延伸到外部；例如，当Δx≥0时，对于左边界p1<0（p1=-Δx），线段从左边界的外部到内部；对于右边界p2>0（p2=Δx），线段从右边界的内部到外部。当Δy<0时，对于下边界p3>0（p3=-Δy），线段从下边界的内部到外部；对于上边界p4<0（p4=Δy），线段从上边界的外部到内部。当pK≠0时，可以计算出参数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>u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。2.4Sutherland-Hodgman算法进行多边形裁剪Sutherland—Hodgman多边形裁剪算法思想该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。当多边形一个顶点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(p[i][1]>=ymin)即可。2、向量叉积法为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点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=(x[B]-x[A])*(y-y[A])-(x-x[A])*(y[B]-y[A]))因此，当V≤0时，P在边界线内侧；而V>0时，P在边界线外侧。2.4.4Sutherland-Hodgeman多边形裁剪算法特点Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。第3章详细设计第3章详细设计3.1Bresenham算法画直线算法具体实现过程1、画点(x1,y2);dx=x2-x1;dy=y2-y1；计算误差初值P1=2dy-dx;i=1；2、求直线的下一点位置：xi+1=xi+1；ifPi>0则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1,yi-1）；4、求下一个误差Pi+1；ifPi>0则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1;ifi|dy|为分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。3.2Bresenham算法画圆根据Bresenham算法思想编写程序代码，在Bresenham算法画线的基础上画圆，程序代码如下：voidBresenhamCircle(intx0,inty0,intR)//,intcolor){intx,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|pk<0)    u2=min(1,u|pk>0)若u1>u2,则可删除直线段若u1<=u2,将u1,u2代入直线方程，得到直线段的两个可见端点。p3＝p4＝0若q3<0或q4<0，则可删除直线段若q3>=0且q4>=0,则进一步判断    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代入直线方程，得到直线段的两个可见端点。输入直线段的两端点坐标以及窗口的四条边界坐标。若Δx=0，则p1=p2=0。进一步判断是否满足q1<0或q2<0，若满足，则该直线段不在窗口内，转(7)。否则，满足q1>0且q2>0，则进一步计算u1和u2。转(5)。若Δy=0，则p3=p4=0。进一步判断是否满足q3<0或q4<0，若满足，则该直线段不在窗口内，转(7)。否则，满足q1>0且q2>0，则进一步计算u1和u2。转(5)。若上述两条均不满足,则有pk≠0(k=1,2,3,4)。此时计算u1和u2。求得u1和u2后,进行判断：若u1>u2,则直线段在窗口外,转(7)。若u1