《多边形裁剪算法》PPT课件.ppt

1、第5章图形的变换和裁剪，5.1齐次坐标5.2从窗口到可视区域的变换5.3图形的几何变换5.4三维图形的基本问题5.5平面几何投影5.6直线段的裁剪5.7多边形裁剪、裁剪、裁剪：确定图形的哪些部分在显示区域内，哪些部分在显示区域外，这样只有那些在显示区域内的部分才能显示。这个选择过程被称为剪辑。图形裁剪算法直接影响图形系统的效率。点裁剪，图形裁剪中最基本的问题。假设窗口左下角的坐标是(xL，yB)，右上角的坐标是(xR，yT)。对于给定点P(x，y)，点P在窗口内的条件是满足以下不等式：xL=x=xR和yB=y=yT。否则，点P在窗口之外。问题：如何区分任何多边形窗口？5.6、直线切割，直线切割

2、算法是复杂图形切割的基础。复杂曲线可以用虚线段来近似，所以切割问题也可以转化为直线段的切割问题。四种主要算法是直接求交算法科恩-萨瑟兰算法、中点算法梁有东巴尔斯基算法、5.6线段切割、线段与窗口切割的关系：(1)线段完全可见；(2)明显不可见；(3)提高切割效率的其他方法：快速判断案例(1)和(2)。对于情况(3)，尽量减少交叉次数和每个交叉所需的计算量。直接相交算法、直线和窗口边缘以参数形式写入，并计算参数值。科恩-萨瑟兰剪辑，基本思想：对于每一个线段P1P2，它分为三种情况。 (1)如果P1P2完全在窗口中，它将被显示。(2)如果P1P2明显超出窗口，则丢弃该线段。(3)如果线段不满足(1

3、)或(2)的条件，则线段在交点处被分成两段。有一段完全在窗外，所以你可以把它扔掉。然后对另一段重复上述过程。为了快速判断，采用以下编码方法：(1)窗口边缘的两条边长，得到九个区域，每个区域用一个四位二进制数标识，直线的端点根据它们的区域分配相应的区域编码，用于标识端点相对于裁剪矩形边界的位置。1001，0001，0101，1000，0000，0100，1010，0010，A，B，C，D，科恩-萨瑟兰裁剪，科恩-萨瑟兰算法，区域代码如果端点在裁剪矩形内，则区域代码为0000。如果端点位于矩形的左下角，则区号为0101。科恩-萨瑟兰算法，一旦给定了所有线段的区域码，就可以快速判断哪条线完全在裁剪窗

4、口内，哪条线完全在窗口外。因此，我们得到一个规则：科恩-萨瑟兰剪辑，如果P1P2完全在窗口内，代码1=0，代码2=0，然后“采取”如果P1P2显然是在窗口外，代码1代码20，然后“放弃”线段在交叉点分成两段。有一段完全在窗外，所以你可以把它扔掉。然后对另一段重复上述过程。编码线裁剪，科恩-萨瑟兰裁剪，如何确定窗口的哪一侧应该相交？编码中相应位为1的边。计算线段P1(x1，y1)P2(x2，y2)和窗口边界之间的交点if(左)。参见p201，科恩-萨瑟兰直线裁剪算法概述。该算法简单易行。这可以简单地描述为按左、右、下和上的顺序删除窗口左侧的直线部分。处理后，其余部分可见。在该算法中寻找交点是非常

5、重要的，它决定了算法的速度。此外，这种算法对于其他形状的窗口可能不是同样有效。特点：该编码方法可以快速判断线段是完全可见还是明显不可见。中点分割裁剪算法，基本思想：从P0和P1中找出最近的可见点。连接这两个可见点的线是原始线段的可见部分。像科恩-萨瑟兰算法一样，首先对线段的端点进行编码，并将线段与窗口之间的关系分为三种情况，前两种情况处理相同；在第三种情况下，线段和窗口之间的交点通过中点分割获得。a和b分别是离P0和P1最近的可见点，Pm是P0P1的中点。中点分割算法-找出线段和窗口的交点，并从P0找到最近的可见点。首先，通过中点分割法找到P0P1的中点Pm。如果P0Pm不是明显不可见的，并且

6、P0P1在窗口中有一个可见部分，那么离P0最近的可见点必须落在P0Pm上，因此P0Pm被用来代替P01。否则，用PmP1代替P0P1。然后找到新P0P1的中点Pm。重复上述过程，直到PmP1的长度小于给定的控制常数，此时Pm收敛到交点。从P1开始，使用上述类似方法找到离P1最近的可见点。中点分割和裁剪算法，对于分辨率为2N*2N的显示器，上述二分法过程最多可以执行n次。主进程仅使用加法和除法，这适用于硬件实现。它可以用左右移位代替乘法和除法，大大加快了速度。中点切割算法，让待切割的线段为P0P1。P0P1和窗口边界在四个点相交：a、b、c和d，如图所示。该算法的基本思想是从三个点A、B和P0中

7、找到最近的P1点，在图中找到的点是P0。从C、D和P1找到最靠近P0的点。图片中的点是c点，P0C是P0P1线段的可见部分。梁有东-巴尔斯基算法，梁有东-巴尔斯基算法，线段的参数表示X=x0 TX Y=Y0 Ty0=t=1x=x1-x0 Y=y1-y0窗口边界的四条边可以分为两类：开始边和结束边。得到p0p1与两个起始边之间的相交参数t0、t1，设tl=max(t0，t1，0)，则tl是三者中最靠近p1的点的参数，并得到p0p1与两个最终边之间的相交参数t2、t3，设tu=min(t2，t3，1)，则tu是三者中最靠近P0的点的参数。如果tu tl，则可以看到线段间隔t1。t0，t1，t2，t

8、3，0，1，梁有东-巴尔斯基算法：求交算法，梁有东-巴尔斯基算法，确定起点和终点边并计算交点：让QL=-XDL=x0-XLQR=XDR=XR-X0QB=-YDB=Y0-YQT=YDT=YT-Y0，当交点为ti=Di/QI=L，R，B，T Qi 0 ti为与终点边Qi=0 Di 0，E的交点参数此时，因为EF和x=xL和x=xR是平行的，所以没有必要求出EF和x=xL和x=xR的交点，而是让EF和y=yT和y=yB的交点确定直线上的可见部分。)，E，F，A，B，第5章图形变换和裁剪，5.1齐次坐标5.2从窗口到视口的变换5.3图形的几何变换5.4三维图形的基本问题5.5平面几何投影5.6线性线段

9、的裁剪5.7多边形裁剪，5.7多边形裁剪，错觉：线性线段的裁剪组合？新问题：1)边界不再闭合，它需要用窗口边界的适当部分来闭合。如何确定它的边界？5.7多边形裁剪，2)凹多边形可以裁剪成几个小多边形。如何确定这些小多边形的边界？萨瑟兰-霍奇曼算法，分割处理策略：将矩形窗口的多边形切割分解为窗口四边所在直线的多边形切割。流水线处理(左上角和右下角):前面的结果是后面的输入。也称为逐边裁剪算法，萨瑟兰-霍奇曼算法，其基本思想是一次用一个窗口的边来裁剪多边形。考虑由窗口的一侧和延长线形成的剪裁线，它将平面分成两部分，的可见侧；不可见多边形每边的两个端点s和p。它们与裁剪线之间只有四种位置关系，萨瑟兰

10、-霍奇曼算法，其中(1)只输出顶点p；案例(2)输出0个顶点；在情况(3)中，输出线段SP和裁剪线之间的交点I；在情况(4)中，交点萨瑟兰-霍奇曼算法，它可以得到正确的结果时，适用于凸多边形，但切割凹多边形将显示一个额外的直线，如图所示。当切割的多边形有两个或更多分开的部分时，就会发生这种情况。因为只有一个输出顶点表，表中的最后一个顶点总是连接到第一个顶点。有很多方法可以解决这个问题。一种是将凹多边形分成几个凸多边形，然后分别处理每个凸多边形。第二是修改算法，检查沿任意裁剪窗口边缘的顶点表，并正确连接顶点对。然后是魏勒-阿森顿算法。萨瑟兰-霍奇曼算法，思想：如何扩展到任意凸多边形裁剪窗口？魏勒

11、-阿森顿算法，当裁剪窗口是任意多边形(凸、凹、带内环):主多边形：裁剪多边形，表示为A裁剪多边形：裁剪窗口，表示为B，魏勒-阿森顿算法，多边形顶点的排列顺序(使多边形区域在有向边的左侧)外环：逆时针；内环：顺时针主多边形和裁剪多边形将2D平面分成两部分。内部裁剪：AB外部裁剪：A-B，裁剪结果区域的边界由两部分组成：A部分边界和B部分边界，边界在交点处交替，即从A边界到B边界，或者从B边界到A边界。魏勒-阿森顿算法，如果主多边形和裁剪多边形有交点，交点成对出现。它们分为以下两类：入口点：主多边形边界进入裁剪多边形，例如I1，I3，I5，I7，I9，I11出口点：主多边形边界离开裁剪多边形区域，

12、例如i0，I2，i4，i6，i8，i10，魏勒-雅典娜算法，1)建立顶点表；2)找到交点；3)切割：1。建立主多边形和切割多边形的顶点表；2.找出主多边形和切割多边形的交点，并将这些交点依次插入两个多边形的顶点表中。双向指针建立在两个多边形顶点表的相同交点之间。3.裁剪：如果存在未跟踪的交点，执行以下步骤：魏勒-阿森顿算法、魏勒-阿森顿算法，(1)建立裁剪结果多边形的空顶点表，(2)选择任何未跟踪的交点作为起点，并将其输出到结果多边形的顶点表，(3)如果交点是入口点，则跟踪主多边形的边缘边界；否则，跟踪多边形边界(4)，并在每次遇到多边形顶点时将其输出到结果多边形顶点表，直到遇到新的交点(5)，将交点输出到结果多边形顶点表，并通过连接交点的双向指针改变跟踪方向(如果在上一步中跟踪了主多边形边界，现在将跟踪切割的多边形边界；如果在上一步中跟踪了切割多边形边界，现在将跟踪主多边形边界。(6)重复(4)和(5)直到回到起点，以I7为起点，得到切割结