计算机图形学裁剪算法

1、1、 实验目标1.了解Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的基本思想；2.掌握Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的算法实现；二、实验内容本次实验主要是实现Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法。Cohen-sutherland线段裁剪算法思想：该算法也称为编码算法，首先对线段的两个端点按所在的区域进

2、行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。Cohen-sutherland线段裁剪算法步骤：1、分区编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1)第一位置1：区域在左边界外侧(2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧 (4)第四位置1：区域在上边界外侧裁剪窗

3、口内（包括边界上）的区域，四位二进制代码均为0。设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。2、判别根据C1和C2的具体值，可以有三种情况：（1）C1=C20，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C20（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3、求交点假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，

4、重新判断，如果需要接着进入下一边界的处理。为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。当条件(C1&00010)成立时，表示端点P1位于窗口左边界外侧，按照求交公式，进行对左边界的求交运算。依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。Liang-Barsky线段裁剪算法思想：我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示： x= x1+ u（

5、x2-x1）= x1+ ux y= y1+ u（y2-y1）= y1+ uy 0u1式中，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+ uxxwmax ywminy1+ uyywmax这四个不等式可以表示为：upk qk ， k=1，2，3，4其中，p、q定义为： p1=-x ， q1=x1-xwmin p2= x ，

6、 q2=xwmax-x1 p3=-y ， q3=y1-ywmin p4= y ， q4=ywmax-y1从上式可以知道：任何平行于窗口某边界的直线，其pk=0，k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足qk0，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk0，则线段平行于窗口某边界并在窗口内，见图中所示。上式还告诉我们：1、当pk0时，线段从裁剪边界延长线的内部延伸到外部；对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：1、u1的值由线段从外到内遇到的矩形边界所决定（pk0），对这些边界计算rk=qk/pk，u2取0和各个r值

7、之中的最小值。3、如果u1u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。Liang-Barsky线段裁剪算法实现：1、初始化线段交点的参数：u1=0，u2=1；2、计算出各个裁剪边界的p、q值；3、根据p、q来判断：是舍弃线段还是改变交点的参数。（1） 当p0时，参数r用于更新u2。 （u2=minu2，rk）（3）如果更新了u1或u2后，使u1u2，则舍弃该线段。（4）当p=0且qOpen-cgdemo.sln二、添加菜单1.左侧视图栏中有三个视图：ClassView、ResourceView、FileView，点击 ResourceView

8、2.展开cgdemo，展开Menu，双击IDR_MAINFRAME 3.在右侧窗口菜单栏中找到“基本图形生成”菜单项，在该菜单项中添加“Cohen-SutherLand线段裁剪算法”，在“Cohen-SutherLand线段裁剪算法”属性框中找到ID框填：ID_Cohen_SutherLand。在该菜单项中添加“Liang-Barsky线段裁剪算法”，在“Liang-Barsky线段裁剪算法”属性框中找到ID框填：ID_Liang_Barsky。在该菜单项中添加“SutherLand-Hodgeman多边形裁剪算法”，在“SutherLand-Hodgeman多边形裁剪算法”属性框中找到ID框

9、填：ID_SutherLand_Hodgeman。三、创建、编辑函数 1.打开cgdemoView.h头文件，在cgdemoView类枚举类型成员变量m_drawstyle中添加CUT_CSL,CUT_LB,CUT_SLH。2.给菜单项“Cohen-SutherLand线段裁剪算法”添加命令消息响应函数OnCohenSutherland()在该函数中添加以下程序代码。void CcgdemoView:OnCohenSutherland()/ TODO: Add your command handler code herem_drawstyle=CUT_CSL;Invalidate(true);

10、给菜单项“Liang-Barsky线段裁剪算法”添加命令消息响应函数OnLiangBarsky()在该函数中添加以下程序代码。void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code herem_drawstyle=CUT_LB;Invalidate(true);给菜单项“SutherLand-Hodgeman多边形裁剪算法”添加命令消息响应函数OnSutherlandHodgeman()在该函数中添加以下程序代码。void CcgdemoView:OnSutherlandHodgeman()/ TODO: Ad

11、d your command handler code herem_drawstyle=CUT_SLH;Invalidate(true); 3.在鼠标右键按下消息响应函数中添加如下所示代码。void CcgdemoView:OnRButtonDown(UINT nFlags, CPoint point)switch(m_drawstyle) case CUT_CSL: case CUT_LB: case CUT_SLH: b_inputcomplete=1; Invalidate(true);break; 4. 在鼠标移动消息响应函数中添加如下所示代码。void CcgdemoView:OnM

12、ouseMove(UINT nFlags, CPoint point)switch(m_drawstyle) case CUT_CSL: case CUT_LB:5. 在cgdemoView.h头文件类中分别添加成员函数void Cohen_SutherLand(CDC* pDC,int x0,int y0,int x1,int y1); 并在cgdemoView.cpp源文件中void Cohen_SutherLand(CDC* pDC,int x0,int y0,int x1,int y1);并在cgdemoView.cpp为其添加编写的Cohen-SutherLand线段裁剪算法；Lia

13、ng-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法按Cohen-SutherLand线段裁剪算法类似添加代码。在cgdemoView.cpp源文件中void CcgdemoView:OnDraw(CDC* pDC)添加m_drawstyle分别为选中三种裁剪算法所执行的代码。四、编译，运行。四、实验遇到的问题及其解决方法（重点）1.在编译运行Cohen-SutherLand线段裁剪算法时出现如下错误：error LNK2001: unresolved external symbol public: void _thiscall CcgdemoView:OnCo

14、henSutherland(void)(?OnCohenSutherlandCcgdemoViewQAEXXZ)错误原因CcgdemoView类的OnCohenSutherland函数，只有在类中的声明，没有找到具体的函数实现。菜单项“Cohen-SutherLand线段裁剪算法”添加命令消息响应函数时更换了Cohen-SutherLand线段裁剪算法的ID名称，从而产生新的命令相应函数。只是删去了原来的函数体，函数声明没有删除，从而导致错误。删除下列函数声明部分和消息队列部分，编译成功。afx_msg void OnCohenSutherland();ON_COMMAND(ID_Cohen_

15、SutherLand, &CcgdemoView:OnCohenSutherland) 2.在SutherLand-Hodgeman多边形裁剪算法遇到的错误 图一 图二图一所示是在定义窗口上画多边形的图，图二是画多边形后点击右键开始裁剪，通过点击右键发现没有裁剪多边形，程序有误。pDC-Rectangle(300,100,500,300); pDC-Rectangle(500,300,300,100);这两个画矩形是一样的，通过MSDN查找Rectangle的用法发现，它的坐标单位都是逻辑单位，逻辑坐标是独立于设备的，它与设备点的大小无关。在调用时Windows将GDI函数中指定的逻辑坐标映射

16、为设备坐标，所以，两个画矩形都是一样的。Clip_Polygon(CDC* pDC,int xmin,int ymin,int xmax,int ymax)SutherLand-Hodgeman多边形裁剪算法中要满足xmin小于xmax，ymin小于ymax。由于该pDC-Rectangle(500,300,300,100)画矩形不满足条件，导致最终多边形裁剪有误，通过改正画矩形参数值，程序运行成功。五、实验结论和收获通过Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法，使我了解到了Cohen-SutherLand线段裁剪算法、Liang-