第五章 变换和裁剪.

Presentation on theme: "第五章 变换和裁剪."— Presentation transcript:

1 第五章 变换和裁剪

2 第五章 变换和裁剪 几何变换 二维窗口的裁剪 观察角度和物体位置的改变可以通过在世界坐标系中对物体进行各种变换来实现，如平移、放缩、旋转等。
第五章 变换和裁剪 几何变换 观察角度和物体位置的改变可以通过在世界坐标系中对物体进行各种变换来实现，如平移、放缩、旋转等。 二维窗口的裁剪 选择显示的内容--图形在窗口内的部分被显示出来，窗口外的部分被裁剪掉 裁剪算法：Sutherland-Cohen算法、Cyrus-Beck算法、梁友栋-Barsky算法、 Sutherland-Hodgman算法等。

3 5.1 变换的数学基础 几个基本概念： 1 点 2 矢量 3 矩阵 阶矩阵A定义为 ，可记为 或
一点在坐标系中的坐标，就是该点在坐标轴上的垂直投影。三维空间中两点 和 之间的距离是： 图5.1二维点的坐标 p (x,y) x y 2 矢量 矢量是一个n元组，对应于n维空间中的一个点。可以代表物体在空间的位置，运动状态等。 矢量的运算（以三维矢量为例） 3 矩阵 阶矩阵A定义为 ，可记为 或 矩阵的性质

4 5.2 几何变换 坐标系 世界坐标系（world coordinate）:一个图形场景往往由多个对象组成，为了描述它们之间的空间关系，需要把它们置于一个统一的坐标系中，该坐标系称为世界坐标系。 模型坐标系（modeling coordinate）或局部坐标系（local coordinate）：当构造单个对象的数字模型时，为了方便可以将其置于一个特定的坐标系下，即模型坐标系或局部坐标系。 设备坐标系（device coordinate）：图形输出时，则应在输出设备上建立一个坐标系，这个坐标系称为设备坐标系。设备坐标系依据设备的种类有不同的形式，如二维的屏幕坐标系，描述机械手运动轨迹的三维坐标系。 标准化设备坐标系（normalized device coordinate）：有些图形系统，对设备坐标系进行了规范化，将坐标范围限定在区间{x,y,z | 0≤x≤1, 0≤y≤1, 0≤z≤1}内，称为标准化设备坐标系。

5 void glTranslate{fd} (TYPE x, TYPE y, TYPE z);
5.2 几何变换 本节讨论的变换适用于任何直角坐标系。 世界坐标系中的各种几何变换可用本节讨论的方法来实现。 1 平移变换 点 由点(x, y, z)在x, y和z轴方向分别移动距离Δx, Δy和Δz得到。两点坐标间的关系为： (5.1) 其矩阵形式为： (5.2) 在OpenGL中使用如下函数进行平移变换： void glTranslate{fd} (TYPE x, TYPE y, TYPE z); 其中{fd}表示x、y、z的数据类型为float型或double型（下同），x、y和z分别为沿坐标轴x、y和z的平移量。

6 void glScale{fd} (TYPE x, TYPE y, TYPE z);
2 放大和缩小变换 设点(x, y, z)经缩放变换后得点 。两点坐标间的关系为 (5.3) 其中sx,sy和sz 分别为沿x, y和z轴方向放缩的比例。 其矩阵形式是 (5.4) 在OpenGL中使用如下函数进行放缩变换： void glScale{fd} (TYPE x, TYPE y, TYPE z); 其中x、y、z分别为沿三个坐标轴方向的放缩比例因子。

7 2 放大和缩小变换 放缩变换必定有一个 不动点，为了定义放缩 变换，可以指定其不动 点，一个放缩方向，以 及沿该方向的放缩因子。 当放缩因子大于1时，对 象在指定方向上变长

8 为了使缩放变换后的图形仍在原来位置附近，可另外定义一个相似中心点(xp,yp,zp)
以图形中心为中心的放缩变换 为了使缩放变换后的图形仍在原来位置附近，可另外定义一个相似中心点(xp,yp,zp) 把整个图形沿x, y和z方向平移 -xp,-yp和-zp,使相似中心移到坐标原点 对每一点按照式(5.4)作变换 沿x, y和z方向平移xp, yp和zp,把经过放缩的图形移回原处 这样做的综合效果是图形以(xp, yp, zp)为中心作了放缩变换。 以(xp,yp,zp)为中心的放缩变换

9 3 旋转变换 设给定点的坐标为: 它绕z轴旋转α角后，可得点 该变换的矩阵形式为

10 3 旋转变换

11 3 旋转变换 设给定点的坐标为: 绕y轴的旋转变换公式为:

12 3 旋转变换 设给定点的坐标为: 绕x轴的旋转变换公式为: yp

13 绕过原点的轴的旋转变换 对绕空间任一通过坐标原点的轴旋转，要给出这根轴的方向向量的坐标(Ax,Ay,Az)。
首先建立一个新的坐标系ouvw，ow 轴的指向和旋转轴(Ax,Ay,Az)的指向一致 把要作旋转变换的对象先从oxyz坐标系变到坐标系ouvw 在ouvw 坐标系绕ow 轴旋转要求转动的角度 最后把旋转后的对象从坐标系ouvw 变换到原坐标系oxyz中 图5.7 新坐标系ouvw y u v w x z o

14 两个坐标系间的变换关系 轴可取在经过O点并和 轴垂直的任一直线上。为了方便， 若 ，则 轴的方向可取成向量（-Ay,Ax,0）的方向，
否则可取 的方向。 轴方向的单位向量为： 图5.7 新坐标系ouvw y u v w x z o 当 轴方向的单位向量为 ， 若 ，则取 轴的单位方向向量为 ，即

15 坐标系变换公式 从坐标系oxyz至坐标系ouvw 的变换为 向量 、 、 是互相正交的单位向量，可知矩阵A的逆矩阵就是A的转置矩阵AT，即
（5.6） 向量 、 、 是互相正交的单位向量，可知矩阵A的逆矩阵就是A的转置矩阵AT，即 这样，从坐标系ouvw 至坐标系oxyz 的变换公式为 （5.7）

16 void glRotate{fd} (TYPE angle, TYPE x, TYPE y, TYPE z);
变换公式 由式（5.5）、式（5.6）和式（5.7）可得变换公式为: （5.8） 如果旋转轴通过点（xp，yp，zp），而不通过坐标原点，则可先作平移变换把对象沿x、y和z方向分别平移-xp 、-yp和-zp，然后按照式（5.8）作旋转变换，最后再把图形沿x、y和z方向分别平移xp 、yp和zp，这样就可以得到图形绕任意轴的旋转变换。 在OpenGL中使用如下函数进行旋转变换： void glRotate{fd} (TYPE angle, TYPE x, TYPE y, TYPE z); 其中angle为指定的旋转角度（以度数为单位），参数x、y、z指定一个从原点到（x, y, z）点的向量，该向量作为旋转中心轴，旋转的方向为逆时针。

17 绕着不是原点的固定点旋转

18 4 错切变换 设矩形ABCD沿x轴（称为方向轴）方向切变，oy轴称为依赖轴。 切变的程度由参数s=tgα决定
s的几何意义是对y=1的点在切变时沿x轴正向平移的距离。设点(x, y, z)经切变后成为(x′, y′, z′)，则 图5.8 错切 (5.9) 如果依赖轴和方向轴改成其它的坐标轴，式（5.9）中的矩阵要作相应的变动。

19 4 错切变换

20 齐次坐标与变换的矩阵表示 在实际绘图时，常要对对象连续做几次变换，例如作了平移后，作旋转，再作放大等。这样对每一点的坐标要依次用式(5.2)，式(5.8)和式(5.4)作计算，这样计算量较大。 如果只有旋转和放缩，则可把式(5.8)和式(5.4)合并成一个矩阵。可写成如下形式： (5.10) 如果再加上平移变换，变换矩阵就不容易合并了。 (5.2)

21 齐次坐标表示法就是用n+1维向量表示n维向量。 例如，我们使用齐次坐标（xh，yh，zh，h）来表示每个三维空间坐标位置（x，y，z）。
为使平移变换也能像变换(5.4)、(5.5)、(5.8)和(5.9)式那样容易合并，可以采用齐次坐标。式(5.2)的齐次坐标表示式为： (5.11) 式(5.5)的旋转变换可写成齐次坐标形式

22 5.2.3 变换的模式 两种图形的变换模式 图形模式： 矩阵合并时，先调用的矩阵放在右边，后调用的矩阵放在左边，也称为固定坐标系模式。
变换的模式 两种图形的变换模式 图形模式： 矩阵合并时，先调用的矩阵放在右边，后调用的矩阵放在左边，也称为固定坐标系模式。 特点是每一次变换均可看成相对于原始坐标系中执行的。 空间模式： 也称为活动坐标系模式，矩阵的合并方式和图形模式相反。 特点是在连续执行几次变换时，每一次变换均可看成是在上一次变换所形成的新坐标系中进行的。 对不同的应用常要求用不同的变换模式 在很多绘图的情况下用图形模式，因为用户比较容易估计变换后的结果。 在整体变换的基础上再作一些较独立的局部变换常用空间模式。

23 数学角度看变换的顺序

24 图形模式---例子 1. 先把图形绕z轴旋转30°，然后再沿x轴平移距离7 2. 先把图形沿x轴平移距离7，然后再绕z轴旋转30°
a） x y o x′ y′ b） c） x″ y″ 图5.9 先旋转后平移 （b） （a） y x x″ y″ （c） o 图5.10 先平移后旋转

25 光栅化椭圆的变换(1) 考虑4.2.3节圆弧的离散生成和4.2.4节的椭圆弧光栅化算法： 其中
（5.13） 其中 如果对由式（5.13）生成的椭圆作旋转β角或放大缩小变换，这时要分别用变换矩阵 如果这两个变换都做，则变换矩阵应是这两个矩阵的乘积T，这时只要用 TMT-1代替式（5.13）中的M，便可得到变换后的椭圆的上的顶点的坐标。

26 光栅化椭圆的变换(2) 由(5.14) 和(5.15)可推出：
我们定义椭圆PQ 坐标原点为中心，椭圆P’Q’是椭圆PQ 旋转 角，然后放大或缩小后得到的椭圆，设T 为其变换矩阵。如图5.11所示。则有： 图5.11 椭圆的变换 β (5.14) (5.15) 由(5.14) 和(5.15)可推出： (5.16) 这时只要用 TMT-1代替式（5.13）中的M，便可得到变换后的椭圆的顶点坐标。要注意的是，式(5.16)中的 需要先由式(5.15)计算得到。

27 空间模式 例子 Rotate（30，0，0，1）; Translate（7，0，0）; draw_triangle（）;
（b） （a） y x x″ y″ （c） o 图5.10 先平移后旋转 x y x′ y′ x″ y″ 图5.12 变换模式的影响 o 图5.12可看成先对坐标系oxy作旋转，同时得到相应的坐标系ox’y’，然后再相对于新坐标系ox’y’作平移得到最后结果。 经变换后得到的三角形相对于原始坐标系的位置与图5.10（c）是一样的，只是考虑变换的方式不同。

28 OpenGL中的变换 在OpenGL中矩阵是状态的一部分 模型视图(GL_MODELVIEW)；投影(GL_PROJECTION)
glMatrixMode(GL_MODELVIEW); •glMatrixMode(GL_PROJECTION); 从概念上说，当前变换矩阵(CTM)就是一个4x4阶的齐次坐标矩阵，它是状态的一部分，被应用到经过流水线中的所有顶点CTM是在应用程序中定义的，并被上载到变换单元中

29 OpenGL中的变换 CTM可以被改变，改变的方法是上载一个新的CTM或者右乘一个矩阵 上载单位阵：C ← I 上载任意矩阵：C ← M
上载一个旋转矩阵：C ← R 上载一个放缩矩阵：C ← S 右乘任意矩阵：C ← CM 右乘一个平移矩阵：C ← CT 右乘一个旋转矩阵：C ← CR 右乘一个放缩矩阵：C ← CS

30 OpenGL中的变换 绕固定点的旋转 从单位阵开始：C ← I 把固定点移到原点：C ← CT 旋转：C ← CR
结果：C = TRT-1 其中每个运算对应于程序中的一个函数调用 注意：在程序中最后指定的运算是最先被执行的运算

31 OpenGL中的变换例子 固定点为(1.0, 2.0, 3.0), 绕z轴旋转30° glMatrixMode(GL_MODEL_VIEW); glLoadIdentity(); //此命令不会把投影矩阵重设 glTranslated(1.0, 2.0, 3.0); glRotated(30.0,0.0,0.0,1.0); glTranslated(-1.0,-2.0,-3.0); 记住在程序中最后指定的矩阵是最先被执行的操作

32 变换的应用 组合图形

33 变换的应用 设计者可能需要 从不同的角度查 看同一个场景。

34 变换的应用 计算机动画

35 5.3 裁 剪 视见体：限定要绘制的图形区域，一般是一个四棱台或四棱柱。
5.3 裁 剪 视见体：限定要绘制的图形区域，一般是一个四棱台或四棱柱。 在OpenGL中函数glFrustum（…）、gluPerspective（…）和glOrtho（…）可定义视见体。 图2.1 视见体、窗口和视口 V′ X′ Y′ U′ 视 口 屏幕 窗口 投影平面 视点 X Y Z 近平面 远平面 窗口: 有时为了突出图形的某一部分，可定义一个窗口。只显示窗口内的图形。 视口：在屏幕或绘图纸上可定一个矩形，称为视口，窗口内的景物就在视口内显示。

36 5.3 裁 剪 裁剪作用： 选择显示的内容--图形在窗口内的部分被显示出来，窗口外的部分被裁剪掉
5.3 裁 剪 裁剪作用： 选择显示的内容--图形在窗口内的部分被显示出来，窗口外的部分被裁剪掉 图形中每个图形基本元素都要经过裁剪，因此裁剪直接影响整个图形系统的效率。 裁剪窗口：矩形，凸多边形，任意多边形 裁剪类型：二维裁剪、三维裁剪 裁剪对象：直线段、多边形、文字等 裁剪方法: 直线的裁剪方法: Sutherland-Cohen算法 , Cyrus-Beck算法,梁友栋-Barsky算法 多边形的裁剪方法:Sutherland-Hodgman算法 三维的裁剪方法: Sutherland-Cohen算法 ,梁友栋-Barsky算法

37 5.3.1 Sutherland-Cohen算法 Sutherland–Cohen算法分成两部分： 第一步:
1)决定完全在窗口内的直线段，称为完全可见的线段； 2) 或决定完全在窗口外的线段，称为显然完全不可见的线段。 第二步:处理不能断定完全可见或显然完全不可见的线段。 *是一个迭代的过程，每次抛弃一段显然完全不可见的线段，对余下部分再作第一步的判断，直到得出肯定结论。

38 算法的第一步 可用于确定顶点的位置 用窗口的四条边把整个平面分成九个区域，每一个区域采用四位编码表示：
在x=xL左侧的区域,编码的第四位是1； 在x=xR右侧的区域,编码的第三位是1； 在y=yB下侧的区域,编码的第二位是1； 在y=yT上侧的区域,编码的第一位是1 。 对要被裁剪的线段的两个端点，如果所在的区域的两个编码都是0000，则这条线段完全可见； 如果两个编码的逻辑乘不为0000，则这条线段是完全不可见的。 可用于确定顶点的位置

39 算法的第二步 对线段KL，从K点(1001)的编码分析出K在x=xL的左侧，KL必和x=xL有交点， 求出其交点M，KM显然是完全不可见的，
因而只要对ML从第一步开始重复上述处理。 由于ML还是不能用第一步下结论，又从M的编码发现M在y=yT的上侧，因而要求ML和y=yT的交点N。 丢掉MN，对NL用第一步的方法可断定NL为完全可见，至此裁剪结束。 XR

40 程序代码 float x1, xr, yt, yb; unsigned char code(float x, float y)
if (x < xl) c = c|1; else if (x > xr) c = c|2; if (y < yb) c = c|4; else if (y > yt) c = c|8; return c; } void clip(float x0, float y0, float x2, float y2) {unsigned char c1, c2, c; float x, y, wx, wy; c1 = code(x0, y0); c2 = code(x2, y2); while ((!(c1 == 0)) || (!(c2 == 0))) { if ((c1& c2)) return; c = c1; if (c == 0) c = c2; wx=x2-x0; wy=y2-y0; if ((c & 1) == 1) { y = y0 + wy * (xl - x0) /wx; x = xl; else if ((c & 2) == 2) { y = y0 +wy * (xr - x0) /wx; x = xr; } else if ((c & 4) == 4) { x = x0 +wx * (yb - y0) /wy; y = yb; else if ((c & 8) == 8) { x = x0 +wx * (yt - y0) / wy; y = yt; if (c == c1) { x0 = x; y0 = y; c1 = code(x0, y0); else { x2 = x; y2 = y; c2 = code(x2, y2); }// While() glLine(int(x0), int(y0), int(x2), int(y2));

41 补充：中点分割算法 设要裁剪的线段是P0P1。从P0出发找出离P0最近的可见点(A点)，和从P1点出发找出离P1最近的可见点(B点)。
*先求P0P1的中点Pm， *若P0Pm不能定为显然不可见，则取P0Pm代替P0P1， *否则取PmP1代替P0P1， *再对新的P0P1求中点Pm。重复上述过程，直到P1Pm长度小于给定的小数ε为止。 在显示时ε可取成一个象素的宽度，对分辨率为2N×2N的显示器来说，上面讲的二分的过程最多只要作N次。

42 5.3.2 Cyrus-Beck算法和梁友栋-Barsky算法
考虑如图5.15所示一个凸多边形区域R和一条线段P1P2，要求计算线段落在区域R中的部分。假定A是区域R边界L上一点。N是区域边界在A点的内法向量。线段P1P2用参数方程表示： （0≤t≤1） （5.17） 对于线段上任意一点 ， 和多边形边界L的关系有三种可能性： P2 N R P1 P(t)=(P2-P1)t+P1 P(tu) P(tl) 图5.15 凸多边形裁剪区域 A 1) ，则 在L内侧。 （性质1） 2) ，则 在L或其延长线上。 3） ，则 在L外侧。

43 可见线段的参数区间 由性质(1)知， 在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该处内法向量 ，都有 。
现假设多边形有k条边，在每 条边 上 取 — 个 点 Ai 和 该 点 处 的 内 法向量（i=1,2,…,k），则可见线段的参数区间为下列不等式的解 （i=1,2,…,k） （5.18） 解的最小值ts和最大值te分别对应于可见线段的端点。 P2 N R P1 P(t)=(P2-P1)t+P1 P(tu) P(tl) 图5.15 凸多边形裁剪区域 A 把式 （5.17）代入式（5.18）， 整理得: （5.19）

44 与边平行的情况 若对于某个i，有 ，这时 ， 与对应边平行，如图5.16所示。这时有两种情况：线段在区域外侧或内侧。 线段在区域外侧
对应于 ，可直接判断线段在多边形之外； 线段在区域内侧 对应于 ，可不予考虑，继续处理其他边。 图5.16 线段与裁剪边平行的情况 Ai Ni P1 P2

45 可见区域的解 （5.19） 注意到 的正负性，所以式（5.19）等价于 （5.20） 是线段与第i条边（或延长线）的交点参数。
注意到 的正负性，所以式（5.19）等价于 （5.20） 是线段与第i条边（或延长线）的交点参数。 式（5.20）的解的最小值与最大值为 若 ，则 和 是可见线段的端点参数，否则整条线段在区域外部。

46 解的几何意义 把 分为两组：起点组和终点组。 起点组以 为特征，表示在该处沿 方向前进将进入多边形内侧。
把 分为两组：起点组和终点组。 起点组以 为特征，表示在该处沿 方向前进将进入多边形内侧。 终点组以 为特征，表示在该处沿 方向前进进入多边形外侧。 图5.17 解的几何意义 终点组 起点组 P2 P1 上述算法称为Cyrus-Beck算法。

47 算法的程序 double ts,te; int Cyrus_Beck (int k,double A[][2],
double N[][2],double x[2], double y[2],double *ts,double *te) { int i,j; double t,dn,nw,D[2],W[2]; *ts=0;*te=1; for(i=0;i<k;i++) dn=N[i][0]*(x[1]- x[0]) +N[i][1]* (y[1]-y[0]); nw=N[i][0]* (x[0]-A[i][0]) +N[i][1]* (y[0]- A[i][1]); if(fabs(dn)<1.0e-6) { if(nw<0) return 0; } else { t=-nw/dn; if(dn<0) { if(t< *te) *te=t; } else if(t> *ts) *ts=t; if(*ts>*te) return 0; return 1;

48 梁友栋-Barsky算法 当凸多边形是矩形窗口，且矩形的边平行于坐标轴时，上述算法可简化为梁友栋-Barsky[LIANG84]算法。
对于窗口的每条边，表5.1列出了其内法向量 ，该边上一点 ，从 指向线段起点P1 的向量 ，以及线段与该边（或延长线）的交点参数。 表5.1 梁友栋-Barsky算法所用的量 由于每个法向量只有一个非零分量，所以任意一个向量与法向量求内积，相当于给出该向量的相应分量。 边 内法向量 边上一点A P1-A 左边x=XL (1，0) (XL，y) (x1-XL， y1-y) 右边x=XR (-1，0) (XR，y) (x1-XR，y1-y) 下边y=YB (0，1) (x，YB) (x1-x，y1-YB) 上边y=YT (0，-1) (x，YT) (x1-x，y1-YT)

49 梁友栋-Barsky算法 设∆x=x2－x1，∆y=y2－y1，令 （5.21）
起点组 终点组 （5.21） 上述终点组和起点组的特征分别表现为rk>0和rk<0，其中k对应于相应的裁剪边界（k=L、R、B、T分别对应于左、右、下、上边界）。沿 方向前进，rk>0时，将进入k边界的外侧；rk<0时，将进入k边界的内侧。

50 梁友栋-Barsky算法的基本步骤 初始化线段在边界内的端点参数为ts=0、te=1。 计算出各个裁剪边界的r、s值。
当r=0且s<0时，舍弃该线段；否则计算线段与边界的交点参数t。 当r<0时，参数t用于更新ts； 当r>0时，参数t用于更新te。 如果更新了ts或te后，使ts>te，则舍弃该线段。 ts te

51 算法的程序 double ts,te;double xL,xR,yB,yT; bool visible=false;
void Liang_Barsky (double x[2], double y[2],double *ts,double *te) { double dx,dy; visible=false; dx=x[1]-x[0]; dy= y[1]-y[0]; *ts=0; *te=1; if(clipt(-dx,x[0]-xL,ts,te)) if(clipt(dx,xR-x[0],ts,te)) if(clipt(-dy,y[0]-yB,ts,te)) if(clipt(dy,yT-y[0],ts,te)) visible=true; } bool clipt (double r,double s,double * ts,double *te) { double t; if(r<0) { t=s/r; if(t>* te) return false; else if(t>* ts) *ts=t; } else if(r>0) { t=s/r; if(t<*ts) return false; else if(t<* te) *te=t; else if(s<0) return false; return true;

52 5.3.3 多边形裁剪---凸多边形的二维裁剪 多边形是由一组线段围成的封闭区域，线段裁剪是多边形裁剪的基础。
多边形裁剪---凸多边形的二维裁剪 多边形是由一组线段围成的封闭区域，线段裁剪是多边形裁剪的基础。 正确的剪裁结果应是一个有边界的区域，即裁剪后的结果仍是一个（或多个）多边形，要求在裁剪过程中应当保留多边形的区域性质。 （a） 裁剪前 （b） 仅对多边形的线段做裁剪 （c） 对多边形区域做裁剪 图5.18 多边形裁剪

53 凸多边形的裁剪方法(1) 将窗口看做是由四个半平面围成的区域，依次用每个半平面同多边形求交，经四次求交后，就得到裁剪后的多边形。由于多边形是凸的，每次和半平面求交时， 多边形或者在半平面内（保留）， 或者在半平面外（去除）， 或者与半平面的边界（直线）有两个交点。 连接这两个交点及多边形在半平面内的部分，就构成了与该半平面的交，它仍是一个凸多边形。 A B C D E

54 凸多边形的裁剪方法(2) 对凸多边形的裁剪，可以看成是凸多边形和矩形窗口的求交。凸多边形和矩形的边之间或者有交点，或者无交点。
当有交点时，会产生仅有的两个交点，特殊情况下，如交点在多边形或矩形顶点上，需特殊处理，有时看做交点，有时不作为交点（如图中A、B两点），但都可以归结为两个交点的情况。这两个交点把凸多边形和矩形都分成两部分，选择凸多边形在矩形内的边界和矩形在凸多边形内的边界，就形成了裁剪后的多边形。 A B C D E

55 快速裁剪算法 求交、并、差 求交检测 （碰撞检测） 裁剪、消隐 时间复杂度o(n)

56 多边形的裁剪-Sutherland-Hodgman算法

57 线段端点S、P与裁剪线的位置关系 算法的输入是以顶点序列表示的多边形，输出也是一个顶点序列，构成一个或多个多边形。
考虑以窗口的一条边以及延长线构成的裁剪线，该线把平面分成两部分：一部分包含窗口，称为可见侧；另一部分称为不可见侧。 每条线段端点S、P与裁剪线比较后可输出0至2个顶点。 S、P都在可见一侧，则输出P。 S、P都在不可见一侧，则输出0个顶点。 S在可见一侧，P在不可见一侧，则输出SP与裁剪线的交点I。 S在不可见一侧，P在可见一侧，则输出SP与裁剪线的交点I和P。 图5.20 　S、P与裁剪线的四种位置关系 （b） （c） （d） S 可见侧 P （a）

58 算法框图 图5.21　 Sutherland-Hodgman算法流程图 （1）主框图 开始 第一个顶点→S,F 顶点输入完毕 输入顶点P 处理线段SP P→S F→P 结束 N Y （2）处理线段SP子过程 SP与裁剪线相交 求SP与裁剪线的交点I 输出I P位于可见侧 输出P 上述算法仅用一条裁剪边对多边形裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每条裁剪边，算法的框图是一样的，只是判断点在裁剪边哪一侧以及求线段SP与裁剪边的交点算法应做相应的改变。

59 5.3.4 字符裁剪 字符裁剪的策略有以下三种: 串精度裁剪:字符串完全落入窗口之内时才显示，否则不显示。
字符裁剪 字符裁剪的策略有以下三种: 串精度裁剪:字符串完全落入窗口之内时才显示，否则不显示。 字符精度裁剪:当一个字符完全包含于窗口内时，显示该字符，否则不显示。 基于构成字符最小元素的裁剪:这种策略最为精确，即使字符只有一部分在窗口内，也要把这一部分显示出来。 （a） （b） （c） （d） 图5.23 字符裁剪

60 5.4 OpenGL中简单的变换实例 本节将在2.2节的程序中增加一个画正方形的函数，通过对矩形做平移、放缩和旋转变换介绍OpenGL中的图形变换功能。 画正方形的函数可定义如下: void CExam1View::gl_Rect() { int x1, y1, x2, y2; // 设置绘图颜色为黑色 glColor3f(0,0,0); x1 = 100; y1 = 100; x2 = 200; y2 = 200; glLine(x1, y1, x2, y1); glLine(x2, y1, x2, y2); glLine(x2, y2, x1, y2); glLine(x1, y2, x1, y1); } void CExam1View::glLine(int x1, int x1, int x2, int y2) { glBegin(GL_LINES); glVertex2d(x1,y1); glVertex2d(x2,y2); glEnd();

61 例子1：平移、放缩和旋转 在Draw()函数中，加入： glTranslated(200, 0, 0); gl_Rect();
然后执行程序，则正方形向右移了200个单位，而其他的图形未动。这是因为glTranslated(200, 0, 0)对其后的绘图做了平移变换，glTranslated(-200, 0, 0)则相当于恢复平移前的变换。 同glTranslated相似，使用glScaled(x, y, z)和glRotated(x, y, z)了解放缩和旋转变换的效果。

62 例子2：窗口、视口变换 修改视区：将glViewport(0, 0, r.right-r.left, r.bottom-r.top)改为glViewport(0, 0, （r.right-r.left）/2, （r.bottom-r.top）/2），  再执行程序，可以看到图形变小了一半。这是因为glViewport()指定了一个更小的显示区域（视区）。 修改窗口（视见体）：将gluOrtho2D(0, r.right-r.left, 0, r.bottom-r.top) 改为gluOrtho2D(0, 2*（r.right-r.left）, 0, 2*（r.bottom-r.top）)， 再执行程序，可以看到图形也变小了一半。虽然视区未变，但由于窗口（视见体）变大了，图形也就显得小了。

63 矢量的运算 三维矢量 和 1 矢量和 5 矢量的点乘 6 矢量的叉乘 2 矢量的数乘 3 矢量的模 4 单位矢量 Back

64 矩阵的性质 设有两个 阶矩阵： 1. 矩阵的加法 注意：只有两个矩阵的阶数（行数和列数）相同时才能做加法运算。 2. 矩阵的数乘
设有两个 阶矩阵： 1. 矩阵的加法 注意：只有两个矩阵的阶数（行数和列数）相同时才能做加法运算。 2. 矩阵的数乘 3. 矩阵的乘法 若 为 阶矩阵， 为 阶矩阵，设 为它们的乘积，则 为 阶矩阵。

65 4. 单位矩阵 主对角线元素均为1，其余各元素均为0。 5. 矩阵的转置 将A行、列互换而得到的矩阵叫做A的转置矩阵 矩阵的转置满足 6. 矩阵的逆 对于n 阶矩阵A ，若存在一个 n 阶矩阵B，使得 ，则称B 为A的逆矩阵，记为 矩阵可逆的充分必要条件是其行列式不为0。 Back