计算机图形学裁剪算法

1一、实验目标1.了解Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的基本思想；2.掌握Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的算法实现；二、实验内容本次实验主要是实现Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法。Cohen-sutherland线段裁剪算法思想：该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。Cohen-sutherland线段裁剪算法步骤：1、分区编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。四位二进制代码的编码规则是：(1)第一位置1：区域在左边界外侧2(2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧(4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。2、判别根据C1和C2的具体值，可以有三种情况：（1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。（2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。（3）不属于上面两种情况，均需要求交点。3、求交点假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。为了规范算法，令线段的端点P1为外端点，如果不是这样，就需要P1和P2交换端点。当条件(C1&0001≠0)成立时，表示端点P1位于窗口左边界外侧，按照求交公式，进行对左边界的求交运算。依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。Liang-Barsky线段裁剪算法思想：我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：x=x1+u·（x2-x1）=x1+u·Δxy=y1+u·（y2-y1）=y1+u·Δy0≤u≤1式中，Δ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，3ywmin）和（xwmax，ywmax）所确定的窗口内，那么下式成立：xwmin≤x1+u·Δx≤xwmaxywmin≤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时，线段从裁剪边界延长线的内部延伸到外部；对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：1、u1的值由线段从外到内遇到的矩形边界所决定（pk0），对这些边界计算rk=qk/pk，u1取0和各个r值之中的最大值。2、u2的值由线段从内到外遇到的矩形边界所决定（pk0），对这些边界计算rk=qk/pk，u2取0和各个r值之中的最小值。3、如果u1u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。Liang-Barsky线段裁剪算法实现：1、初始化线段交点的参数：u1=0，u2=1；2、计算出各个裁剪边界的p、q值；3、根据p、q来判断：是舍弃线段还是改变交点的参数。（1）当p0时，参数r用于更新u1；（u1=max{u1，…，rk}）（2）当p0时，参数r用于更新u2。（u2=min{u2，…，rk}）（3）如果更新了u1或u2后，使u1u2，则舍弃该线段。（4）当p=0且q0时，因为线段平行于边界并且位于边界之外，则舍弃该线段。见下图所示。44、p、q的四个值经判断后，如果该线段未被舍弃，则裁剪线段的端点坐标由参数u1和u2的值决定。SutherLand-Hodgeman多边形裁剪算法思想：每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：即交点和窗口顶点，从而得到一个新的多边形顶点序列。然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。如下图所示。新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两个部分：一部分称为边界内侧；另一部分称为边界外侧。如下图所示,依序考虑多边形的各条边。假设当前处理的多边形的边为SP(箭头表示顺序关系，S为前一点，P为当前点)，边SP与裁剪线的位置关系只有下面四种情况：51、S在外侧，P在内侧。则交点Q、当前点P保存到新多边形中。2、S、P均在内侧，则当前点P保存到新多边形中。3、S在内侧，P在外侧。则交点Q保存到新多边形中。4、S、P均在外侧。则没有点被保存到新多边形中。三、实验步骤一、打开cgdemoMFC工程1.打开MicrosoftVisualStudio20082.File--Open--cgdemo.sln二、添加菜单1.左侧视图栏中有三个视图：ClassView、ResourceView、FileView，点击ResourceView2.展开cgdemo，展开Menu，双击IDR_MAINFRAME3.在右侧窗口菜单栏中找到“基本图形生成”菜单项，在该菜单项中添加“Cohen-SutherLand线段裁剪算法”，在“Cohen-SutherLand线段裁剪算法”属性框中找到ID框填：ID_Cohen_SutherLand。在该菜单项中添加“Liang-Barsky线段裁剪算法”，在“Liang-Barsky线段裁剪算法”属性框中找到ID框填：ID_Liang_Barsky。在该菜单项中添加“SutherLand-Hodgeman多边形裁剪算法”，在“SutherLand-Hodgeman多边形裁剪算法”属性框中找到ID框填：ID_SutherLand_Hodgeman。三、创建、编辑函数1.打开cgdemoView.h头文件，在cgdemoView类枚举类型成员变量m_drawstyle中添加CUT_CSL,CUT_LB,CUT_SLH。2.给菜单项“Cohen-SutherLand线段裁剪算法”添加命令消息响应函数6OnCohenSutherland()在该函数中添加以下程序代码。voidCcgdemoView::OnCohenSutherland(){//TODO:Addyourcommandhandlercodeherem_drawstyle=CUT_CSL;Invalidate(true);}给菜单项“Liang-Barsky线段裁剪算法”添加命令消息响应函数OnLiangBarsky()在该函数中添加以下程序代码。voidCcgdemoView::OnLiangBarsky(){//TODO:Addyourcommandhandlercodeherem_drawstyle=CUT_LB;Invalidate(true);}给菜单项“SutherLand-Hodgeman多边形裁剪算法”添加命令消息响应函数OnSutherlandHodgeman()在该函数中添加以下程序代码。voidCcgdemoView::OnSutherlandHodgeman(){//TODO:Addyourcommandhandlercodeherem_drawstyle=CUT_SLH;Invalidate(true);}3.在鼠标右键按下消息响应函数中添加如下所示代码。voidCcgdemoView::OnRButtonDown(UINTnFlags,CPointpoint){switch(m_drawstyle){caseCUT_CSL:caseCUT_LB:caseCUT_SLH:b_inputcomplete=1;Invalidate(true);break;}4.在鼠标移动消息响应函数中添加如下所示代码。voidCcgdemoView::OnMouseMove(UINTnFlags,CPointpoint){switch(m_drawstyle){caseCUT_CSL:caseCUT_LB:}75.在cgdemoView.h头文件类中分别添加成员函数voidCohen_SutherLand(CDC*pDC,intx0,inty0,intx1,inty1);并在cgdemoView.cpp源文件中voidCohen_SutherLand(CDC*pDC,intx0,inty0,intx1,inty1);并在cgdemoView.cpp为其添加编写的Cohen-SutherLand线段裁剪算法；Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法按Cohen-SutherLand线段裁剪算法类似添加代码。在cgdemoView.cpp源文件中voidCcgdemoView::OnDraw(CDC*pDC)添加m_drawstyle分别为选中三种裁剪算法所执行的代码。四、编译，运行。四、实验遇到的问题及其解决方法（重点）1.在编译运行Cohen-SutherLand线段裁剪算法时出现如下错误：errorLNK2001:unresolvedexternalsymbolpublic:void__thiscallCcgdemoView::OnCohenSutherland(void)(?OnCohenSutherland@CcgdemoView@@QAEXXZ)错误原因CcgdemoView类的OnCohenSutherland函数，只有在类中的声明，没有找到具体的函数实现。菜单项“Cohen-SutherLand线段裁剪算法”添加命令消息响应函数时更换了Cohen-SutherLand线段裁剪算法的ID名称，从而产生新的命令相应函数。只是删去了原来的函数体，函数声明没有删除，从而导致错误。删除下列函数声明部分和消息队列部分，编译成功。afx_msgvoidOnCohenSutherland();ON_COMMAND(ID_Cohen_SutherLand,&CcgdemoView::OnCohenSutherland)2.在SutherLand-Hodgeman多边形裁剪算法遇到的错误图一图二8图一所示是在定