二维裁剪 计算机科学与技术系.

Presentation on theme: "二维裁剪 计算机科学与技术系."— Presentation transcript:

1 二维裁剪 计算机科学与技术系

2 裁剪概述 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪(Clipping)。 在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。 图形裁剪算法，直接影响图形系统的效率!

3 裁剪概述 绘制流水线中哪个阶段进行裁剪？ 最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。
这样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。

4 三维图形绘制流程 应用处理 阶段 几何处理 光栅化 3D 2D Pixels 模视变换 光照处理 投影变换 裁剪计算 窗口-视口映射
顶点插值计算 顶点着色 消隐计算 CPU 应用软件 读数据建模 虚拟照相机 碰撞检测等计算 3D 2D Pixels Clipping裁剪

5 点的裁剪 点裁剪是图形裁剪中最基本的问题。 (xR,yT ) 假设窗口的左下角坐标为(xL,yB),右 上角坐标为(xR,yT)，对于给定点
P(x,y)，则P点在窗口内的条件是要 满足下列不等式： xL <= x <= xR 且yB <= y <= yT 否则，P点就在窗口外。 对于任何多边形窗口，如何判别？

6 直线段裁剪 直线段裁剪算法是复杂图元裁剪的基础。复杂的 曲线可以通过折线段来近似，从而裁剪问题也可 以化为直线段的裁剪问题。

7 Cohen-Sutherland裁剪 Danny Cohen
观察坐标系 窗口 Danny Cohen born in Israel, is a computer scientist specializing in computer networking Cohen-Sutherland line clipping algorithm is created by Danny Cohen and Ivan Sutherland. 在二维观察中，需要在观察坐标系下根据窗口大小对二维图形进行裁剪（clipping），只将位于窗口内的图形变换到视区输出。直线段裁剪是二维图形裁剪的基础，裁剪的实质是判断直线段是否与窗口相交，如相交则进一步确定直线段上位于窗口内的部分。

8 Cohen-Sutherland裁剪-基本思想
对于每条线段P1P2分为三种情况处理。 （1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。 （2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。 （3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

9 Cohen-Sutherland裁剪-编码
为快速判断，采用如下编码方法： 每个区域赋予4位编码：上、下、右、左 Ct Cb Cr Cl ymax ymin xmax xmin 编码的思想在图形学中非常重要。 Sutherland：Coons奖, 图灵奖, IEEE 计算机先驱奖。

10 Cohen-Sutherland裁剪-编码
0001 0100 编码 线段裁剪

11 Cohen-Sutherland裁剪-过程
若P1P2完全在窗口内，且code1=0和code2=0，则“取” 若P1P2明显在窗口外， code1≠0,code2≠0，且code1&code2≠0 ，则“弃” 若直线段与窗口相交，且code1≠0,code2≠0，但code1&code2=0时，在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 Ct Cb Cr Cl Ct Cb Cr Cl 0010 0110 Ct Cb Cr Cl 1010 0101

12 Cohen-Sutherland裁剪-过程
按左右下上的顺序计算窗口边界分别与直线段的交点。 P0P1线段与上边界相交于P点，PP0直线段位于窗口外上部，“弃”之。将P点坐标和编码替换成P0点。 交换P0P1点的坐标和编码，使P0总位于窗口外。左边界再与P0P1直线段相交于P点， PP0直线段位于窗口外左侧， “弃”之。将P点坐标和编码替换成P0点。 P0P1直线段为“取”之。 (xL,yB ) (xR,yT ) P1 P0 P (xL,yB ) (xR,yT ) P1 P0 P (xL,yB ) (xR,yT ) P0 P1 P

13 Cohen-Sutherland裁剪-实例
当直线段完全在窗口外，且code1≠0,code2≠0但code1&code2=0时 按左右下上的顺序计算窗口边界分别与直线段的交点 P0P1线段与右边界延长线相交于P点，PP0直线段位于窗口右部，“弃”之。将P点坐标和编码替换成P0点 交换P0P1点的坐标和编码。此时，P0P1直线段位于窗口外下侧， “弃”之。 Ct Cb Cr Cl 0010 0100 P0 P1 P 0110

14 Cohen-Sutherland裁剪(续)
计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点 #define LEFT 1 //0001 #define RIGHT 2 //0010 #define BOTTOM 4 //0100 #define TOP 8 //1000 if(LEFT & code !=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} else if(RIGHT & code !=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} else if(BOTTOM & code !=0) { y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);} else if(TOP & code !=0) { y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);} 1000 (xL,yB ) (xR,yT ) 0101

15 Cohen-Sutherland裁剪算法
优点在于简单，易于实现。 可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，决定了算法的速度。另外，本算法对于其它形状的窗口未必同样有效。 特点：用编码方法可快速判断线段的完全可见和显然不可见。

16 中点分割裁剪算法 基本思想： 与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:
全在 完全不在 线段和窗口有交。 对前两种情况，进行一样的处理。 对于第三种情况，用中点分割的方法求出线段与窗口的交点。

17 求线段与窗口的交点 A、B分别为距P0、P1最近的可见点， Pm为P0P1中点。 从 出发找最近可见点的方法 先求出 的中点
从 出发找最近可见点的方法 先求出 的中点 若 不是显然不可见的，并且 在窗口中有可见部分，则距 最近的可见点一定落在 上，所以用 代替 ； 否则取 代替 再对新的 求中点 。重复上述过程，直到 长度小于给定的控制常数为止，此时 收敛于交点。 从 出发找最近可见点采用上面类似方法。

18 算法为什么可行？会不会无限循环、不断二分？
中点分割裁剪算法 算法为什么可行？会不会无限循环、不断二分？ 主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。

19 Liang（梁友栋）－Barsky算法 梁友栋先生出生于1935年7月，福建福州人。 年于复旦大学作为研究生师从苏步青先生学习几何理论，1960年研究生毕业后任教于浙江大学数学系， 年任数学系主任。80年代初梁友栋先生提出了著名的Liang-Barsky裁剪算法，通过线段的参数化表示实现快速裁剪，至今仍是计算机图形学中最经典的算法之一。 加州大学伯克利分校的Brian A. Barsky(柏世奇)教授是计算机图形学领域的先行者，他先后从康奈尔大学和犹他大学获得硕士和博士学位。计算机辅助设计与建模、交互式真实感三维计算机图形学、科学计算可视化、计算机辅助角膜建模与可视化、医学摄影以及用于手术模拟的虚拟空间建模等。 他长期致力于spline曲线和曲面造型研究，并被广泛应用于计算机图形学和几何建模。1984年与梁友栋先生提出著名的Liang-Barsky算法。

20 Liang（梁友栋）－Barsky算法 更快的参数化裁剪算法，以直线的参数方程为基础
将判断直线段与窗口边界求交的二维裁剪问题转化为求解一组不等式，确定直线段参数的一维问题。 设起点为P0（x0，y0)，终点为P1（x1，y1）直线的参数方程为 0≤t≤1

21 Liang－Barsky算法-裁剪条件 参数化形式写出裁剪条件： 可以统一表示为形式： k = 1,2,3,4
XL XR YT YB P0 P1 参数化形式写出裁剪条件： 可以统一表示为形式： k = 1,2,3,4 左边界: u1=-Δx v1 = x0-XL 右边界: u2=Δx v2 = XR-x0 下边界: u3=-Δy v3 = y0-YB 上边界: u4=Δy v4 = YT-y0

22 Liang－Barsky算法 -几何含义 当ui<0时，在该处直线段从裁剪窗口及其边界延长线的不可见侧延伸到可见侧，直线段与窗口边界的交点位于直线段的起点一侧； 当ui>0时，表示在该处直线段从裁剪窗口及其边界延长线的可见侧延伸到不可见侧，直线段和窗口边界的交点位于直线段的终点一侧。

23 Liang－Barsky算法 -几何含义 时，直线段从窗口左边界的不可见侧延伸到可见侧，与窗口左边界及其延长线相交于参数t等于t1处；

24 Liang－Barsky算法原理 =0且 <0，则线段完全在边界外， ≥0，则该线段平行于裁剪边界并且在窗口内。 x1=x0 或
=0且 <0，则线段完全在边界外， ≥0，则该线段平行于裁剪边界并且在窗口内。 x1=x0 或 y1=y0 左边界: u1=-Δx v1 = x0-XL 右边界: u2=Δx v2 = XR-x0 下边界: u3=-Δy v3 = y0-YB 上边界: u4=Δy v4 = YT-y0

25 Liang－Barsky算法原理 当uk≠0，即直线段不平行于窗口
当uk<0,线段从裁剪窗口及其边界延长线的不可见侧延伸到可见侧。对这些边界计算 tk=vk/uk 。设t为0和各个tk值之中的最大值,即tmax=max(0, tk)

26 Liang－Barsky算法原理 当uk >0,线段从裁剪窗口及其边界延长线的可见侧延伸到不可见侧，直线段和窗口边界的交点位于直线段的终点一侧。对这些边界计算tk=vk/uk 。设t为1和各个uk值之中的最小值，即tmin=min(tk，1) 。

27 Liang－Barsky算法原理 直线段位于窗口内的参数条件是：tmax≤tmin

28 Liang－Barsky算法 思考：如何裁剪直线L1和L2？

29 Liang－Barsky算法实现代码 for(int i = 0; i < 4; i++) {
r = (float)v[i] / (float)u[i]; if(u[i] < 0) t1 = max(t1,r); if(t1 > t2) { flag = true; } } if(u[i] > 0) t2 = min(t2, r); { flag = true; } if(u[i] == 0 && v[i] < 0) { flag = true; } if ( flag ) { return; } Void LB(CPoint startP, CPoint endP, RtRect rect) { bool flag = false; float t1 = 0, t2 =1; int u[4], v[4]; float r; u[0] = startP.x - endP.x; u[1] = endP.x - startP.x; u[2] = startP.y - endP.y; u[3] = -startP.y + endP.y; v[0] = startP.x - rect.x; v[1] = rect.x + rect.w - startP.x; v[2] = startP.y - rect.y; v[3] = rect.y + rect.h - startP.y; cPoint[0].x = startP.x - t1 *(startP.x - endP.x); cPoint[0].y = startP.y - t1 *(startP.y - endP.y); cPoint[1].x = startP.x - t2 *(startP.x - endP.x); cPoint[1].y = startP.y - t2 *(startP.y - endP.y);

30 算法比较 Cohen-Sutherland与Liang—Barskey两种算法所需的各种运算次数

31 多边形裁剪算法 Sutherland-Hodgman裁剪算法又称为逐边裁剪算法 基本思想是用裁剪窗口的4条边依次对多边形进行裁剪。
窗口边界的裁剪顺序无关紧要，这里采用左、右、下、上的顺序。 多边形裁剪算法的输出结果为裁剪后的多边形顶点序列。 错误结果 正确结果

32 多边形裁剪算法 多边形的各条边的两端点P0、P1。它们与裁剪窗口的位置关系只有四种 （a） （b） （c） （d） 外→内 内→内 内→外
外→外 不保存

33 多边形裁剪算法 输入：P0P1P2P3 输出：S0S1P1P2P3 用窗口左边界裁剪 输入：S0S1P1P2P3
输出：S0S1P1S2S3P3 用窗口右边界裁剪

34 多边形裁剪算法 输入：S0S1P1S2S3P3 输出：S5S0S1P1S2S3S4 用窗口下边界裁剪 输入：S5S0S1P1S2S3S4
输出：S5S0S1S6S7S2S3S4 用窗口右边界裁剪

35 多边形裁剪算法 使用Sutherland-Hodgman裁剪算法裁剪后，输出结果为两个不连通的三角形，窗口的边界AB成为了多余线段。
错误的输出结果 凹多边形裁剪 使用Sutherland-Hodgman裁剪算法裁剪后，输出结果为两个不连通的三角形，窗口的边界AB成为了多余线段。 解决方法：先将凹多边形分割为两个或更多的凸多边形，然后分别使用Sutherland-Hodgman裁剪算法裁剪。

36 字符裁剪 串精度:将包围字串的外接矩形对窗口作裁剪 字符精度:将包围字的外接矩形对窗口作裁剪 笔画/像素精度:将笔划分解成直线段对窗口作裁剪
待裁剪字符串 串精度裁剪 字符精度裁剪 象素精度裁剪