计算机图形学 5.5裁剪算法PPT课件

5.5裁剪算法5.1.1线段裁剪算法5.1.2多边形裁剪算法，确定图形的哪些部分落在显示区域内，哪些落在显示区域外，以便仅显示图形中落在显示区域内的那些部分。这种选择过程称为裁剪。该显示区域称为裁剪窗口。5.5.1线段裁剪算法，假设矩形窗口左下角的坐标是(xL，yB)，右上角的坐标是(xR，yT)，那么点P(x，y)在窗口中的条件是：(xL，yB)，(xR，yT)，P，点的位置是裁剪中最基本的问题，否则，点P在窗口之外。满足：xL=x=xR和yB=y=yT，直线段裁剪算法是复杂图形裁剪的基础。复杂曲线可以用折线逼近，因此裁剪问题也可以简化为直线段的裁剪问题。科恩-萨瑟兰、中点分割算法和梁有栋-巴尔斯基算法是常用的线段裁剪方法。5.5.1、线裁剪算法，快速判断情况(1)(2)，对于情况(3)，尽量减少交点数量和每个交点所需的计算量。(1)线段完全可见；(2)明显不可见；(3)线段的至少一个端点在窗口之外，但它不是明显不可见的。如何提高切割效率？线段裁剪的算法很多，但基本思想是：(1)是否所有的线段都在窗口内，如果是，就结束。(2)线段是否全部在窗口中，如果是，则显示线段并到达终点。(3)计算线段与窗口边界延长线的交点，将线段分成两部分；丢弃不可见的部分；转动其余部分(2)。它也叫萨瑟兰-科恩分界线算法。5 . 5 . 1 . 1奥亨-萨瑟兰终点编码算法。矩形窗口的四条边分别延伸后，得到九个区域。每个区域由一个四位二进制数标识。直线的端点根据它们的区域分配有相应的区域代码，这些区域代码用于识别端点相对于裁剪矩形边界的位置。1。线段端点编码是最早也是最流行的裁剪算法，可以扩展到三维裁剪。区号是：XXXX从上到下、从右到左、从左到右的任何一位都被赋值为1，这意味着端点落在相应的位置，否则，该位为0。这种编码的特征是在窗口一侧之外的三个区域中的四个比特之一都是1。线段的终点代码，左上右下P1y=ytp2y=Yb，P4，P3，x=xlx=xr，线段的终点代码？对于3D剪辑，需要6位编码。(1010)，(1001)，P3: 0110p1:1001 p4:科恩-萨瑟兰端点编码算法，(3)如果线段的两个端点的四位编码为0，则在窗口外找到p1P2的端点P1(或P2)，用窗口的相应边缘与P1P2的交点替换端点P1(或P2)，并返回步骤(1)。(2)如果线段P1P2的两个端点的4位编码为非0，则线段完全不可见，算法结束。切割线段时，首先找出端点p1和p2的代码代码1和代码2，然后(1)如果代码1 |代码2=0，则简化直线段。(2)如果代码1P1:(-1，1/2)；代码(0000)辨别出知识不是完全可见的，并且P1在窗口内，因此新线段P1P2对1P2的交换；P1:(1/2，3/2)；代码(1000) P2: (-1，1/2)；代码(0000)，(3)找到上边的交点得到P-(1/4，1) P2 (-1，1/2)；和编码，两个端点代码都为0，线段完全可见，程序结束，p1，x=x1(y-y1)*(x2-x1)/(y2-y1)y=y1(x-x1)*(y2-y1)/(x2-x1)。多边形裁剪，多边形裁剪，多边形裁剪不等于裁剪多边形的每条边。因为在图形中，多边形被认为是一个封闭的区域，它将平面分为内部多边形和外部多边形。对于多边形裁剪，仍然要求多边形的裁剪结果是多边形，并且多边形中的原始点也在裁剪的多边形中。窗口的一部分的边界在裁剪后可能成为多边形的边界，而凹多边形在裁剪后可能成为几个多边形。多边形裁剪算法的输出应该是定义cl的顶点序列5 . 1 . 2作者兰-霍奇曼连续多边形裁剪算法，萨瑟兰-霍奇曼基本想法，基本想法：一次用窗口的一边裁剪多边形。考虑由窗口的一侧和延长线形成的剪裁线，其将平面分成可见侧的两部分；一边的多边形的每条边的两个端点S和P是看不见的。它们与裁剪线之间只有四种位置关系：萨瑟兰-霍奇曼的基本思想是假设当前处理的边是SP，顶点S在前一轮已经处理过。对于情况(1)，仅输出顶点P；案例(2)输出0顶点；案例(3)输出线段SP与切割线的交点一；情况(4)是交点I和终点P，输出线段SP和裁剪线的第一点？点P，SP和e相交？计算sp和e的交点I，输出I，SP，FP，s在e的可见侧，退出，输出s，(a)，萨瑟兰-霍奇曼算法框图，是，是，否，是，否，否，否，将闭合多边形的顶点设置为P1，p2，pn，在方框图e中是被修剪的窗口的四条边之一，第一个点存储在f中，用于修剪最后一条边。图(a)中的算法用于修剪边p1p2、p2p3，pn-1pn。图(b)中的算法用于修剪最后一条边PnP1。剪下一条边并输出一条边。标准普尔和e相交？计算SP和e的交点I，输出I，出口、(b)，是，否，取点f作为p，图(b)。上述算法仅使