第5章二维变换和二维观察

1、第五章第五章 二维变换和二维观察二维变换和二维观察1二维变换内容二维变换内容n图形变换预备知识图形变换预备知识nBasic transformation（基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransformation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster method of transformation（变换（变换的光栅方法

2、）的光栅方法）25.1 5.1 图形变换预备知识图形变换预备知识n 矢量n矢量和 zyxuuuUzyxvvvVzzyyxxvuvuvuVU5.1.1 矢量和矩阵矢量和矩阵3n矢量的数乘 n矢量的点积n性质zyxkukukuUkzzyyxxvuvuvuVUUVVUVUVU000UUU4n矢量的长度 n单位矢量 n矢量的夹角n矢量的叉积 222zyxuuuUUUVUVUcoszyxzyxvvvuuukjiVU5n矩阵 n 阶矩阵nn阶方阵n零矩阵n行向量与列向量n单位矩阵n矩阵的加法 n矩阵的数乘 n矩阵的乘法 n矩阵的转置 n矩阵的逆 m n6矩阵的含义矩阵：由mn个数按一定位置排列的一个 整体

3、，简称mn矩阵。mnmmnnaaaaaaaaa . . . . . . 21222211 1211A=7矩阵运算n加法设A，B为两个具有相同行和列元素的矩阵A+B = n数乘kA = k*aij|i=1.m, j=1,. n . b . . . . b m22111112121111mnmnmmmnnbaababaaba8n乘法设A为32矩阵，B为23矩阵 C = A B = C=Cmp = Am n Bnp cij = aik*bkjn单位矩阵 在一矩阵中，其主对角线各元素aii=1,其余皆为0的矩阵称为单位矩阵。n阶单位矩阵通常记作In 。 Am n = Am n In babab aba

4、babababababababa322322221221312321221121321322121211311321121111 k=1,n9n逆矩阵若矩阵A存在AA-1=A-1A=I，则称A-1为A的逆矩阵n矩阵的转置 把矩阵A=(aij)mn的行和列互换而得到的nm矩阵称为A的转置矩阵,记作AT 。 (AT) T = A (A+B)T = AT + BT (aA)T = aAT (AB)T = BT AT 当A为n阶矩阵，且A=AT ，则 A是对称矩阵。10矩阵运算的基本性质n交换律与结合律 A+B=B+A; A+(B+C)=(A+B)+Cn数乘的分配律及结合律 a(A+B) = aA+a

5、B; a(A B) = (aA) B=A (aB) (a+b)A = aA + bA a(bA) = (ab)A11n矩阵乘法的结合律及分配律 A(B C) = (A B)C (A+B) C = A C+ B C C (A+B) = C A + C Bn矩阵的乘法不适合交换律12所谓所谓齐次坐标表示法齐次坐标表示法就是由就是由n+1维向量表示一个维向量表示一个n维向量。如维向量。如n维向量维向量(P1,P2, ,Pn)表示为（表示为（hP1,hP2,hPn,h），其中），其中h称为称为哑坐标。哑坐标。1. h可以取不同的值，所以同一点的齐次坐标不是唯一的。如可以取不同的值，所以同一点的齐次坐标

6、不是唯一的。如普 通 坐 标 系 下 的 点 （普 通 坐 标 系 下 的 点 （ 2 , 3 ） 变 换 为 齐 次 坐 标 可 以 是） 变 换 为 齐 次 坐 标 可 以 是(1,1.5,0.5)(4,6,2)(6,9,3)等等。等等。2. 普通坐标与齐次坐标的关系为普通坐标与齐次坐标的关系为“一对多一对多”由普通坐标由普通坐标 h齐次坐标齐次坐标由齐次坐标由齐次坐标h普通坐标普通坐标3. 当当h=1时产生的齐次坐标称为时产生的齐次坐标称为“规格化坐标规格化坐标”，因为前，因为前n个个坐标就是普通坐标系下的坐标就是普通坐标系下的n维坐标。维坐标。5.1.2 齐次坐标齐次坐标13(x,y)

7、点对应的齐次坐标为 (x,y)点对应的齐次坐标为三维空间的一条直线 (, )xyhhh0,hhyyhxxhhhzhyyhxxhhh141. 1. 将各种变换用阶数统一的矩阵来表示。提供了用矩阵运将各种变换用阶数统一的矩阵来表示。提供了用矩阵运算把二维、三维甚至高维空间上的一个点从一个坐标系算把二维、三维甚至高维空间上的一个点从一个坐标系变换到另一坐标系的有效方法。变换到另一坐标系的有效方法。2. 2. 便于表示无穷远点。便于表示无穷远点。例如：（例如：（x x h, y h, y h, h) h, h)，令，令h h等于等于0 03. 3. 齐次坐标变换矩阵形式把直线变换成直线段，平面变换齐次

8、坐标变换矩阵形式把直线变换成直线段，平面变换成平面，多边形变换成多边形，多面体变换成多面体。成平面，多边形变换成多边形，多面体变换成多面体。4. 变换具有统一表示形式的优点变换具有统一表示形式的优点n便于变换合成便于变换合成n便于硬件实现便于硬件实现齐次坐标的作用齐次坐标的作用15图形变换是计算机图形学基础内容之一。图形变换是计算机图形学基础内容之一。几何变换，投影变换，视窗变换几何变换，投影变换，视窗变换线性变换，属性不变，拓扑关系不变。线性变换，属性不变，拓扑关系不变。作用：作用：n把用户坐标系与设备坐标系联系起来；把用户坐标系与设备坐标系联系起来；n可由简单图形生成复杂图形；可由简单图形

9、生成复杂图形；n可用二维图形表示三维形体；可用二维图形表示三维形体；n动态显示。动态显示。5.1.3 图形变换图形变换16图形的几何变换图形的几何变换n图形变换：对图形的几何信息经过几何变换后产生新图形变换：对图形的几何信息经过几何变换后产生新的图形。的图形。n图形变换的两种形式：图形变换的两种形式：1.图形不变，坐标系改变；图形不变，坐标系改变；2.图形图形改变，坐标系不变。改变，坐标系不变。n我们所讨论的是针对坐标系的改变而讲的。我们所讨论的是针对坐标系的改变而讲的。 175.2 基本二维变换内容基本二维变换内容n图形变换预备知识图形变换预备知识nBasic transformation（

10、基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransformation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster method of transformation（变换（变换的光栅方法）的光栅方法）185.2 Basic Transformations基本变换基本变换nDef. 改变改变对象对象坐标描述坐标描述的变换称为几何变换，例如的

11、变换称为几何变换，例如改变对象的方向、尺寸和形状。改变对象的方向、尺寸和形状。 nDef. Geometric transformations alter coordinate descriptions of objects, such as changes in orientation, size and shape.nTypesnTranslation平移平移nRotation旋转旋转nScaling变比变比195.2.1 2D 平移平移nTranslation平移平移nDef. 图形对象沿直线运动产生的图形对象沿直线运动产生的变换变换nParameters:平移平移向向量量(tx, ty

12、)nFormula:x = x+txy = y+tyxyPP20n矩阵表示矩阵表示 x x txP= P= T= y y tyP = P + TxyPP215010050100(-20，20)308070120 xyxyExample225.2.2 2D 旋转旋转nRotation旋转旋转nDef.图形对象沿圆弧路径运动产生的变换图形对象沿圆弧路径运动产生的变换nParametersn基准点基准点(pivot)(pivot)，坐标原点或任意点，坐标原点或任意点n旋转角旋转角n方向方向, ,约定：约定：逆时针逆时针为正为正23xy(x,y)(x,y)rxy(x,y)(x,y)r(Xr,Yr)绕原

13、点旋转绕原点旋转绕任意点旋转绕任意点旋转24nFormula 针对坐标原点针对坐标原点x=x*cos- y*sin y= x*sin+ y*cosn 如何得到上述公式如何得到上述公式?n 针对任意点针对任意点(xr, yr)旋转的计算公式旋转的计算公式?xyPP x=r*cos(+ ) =r*(cos *cos-sin*sin) =rcos*cos - rsin*sin = x*cos- y*sin y=r*sin(+ )=r*(cos*sin+sin*cos) =rcos*sin + rsin*cos = x*sin+ y*cos25n矩阵表示矩阵表示 x x cos - -sin P= P

14、= R= y y sin cos P = R P26xy旋转旋转也是一种也是一种不产生变形而不产生变形而移动对象的刚移动对象的刚体变换。体变换。27nScaling变比变比nDef. 改变改变图形对象大小的变换图形对象大小的变换nParameters:变比因子变比因子(Sx, Sy), 基准点，方向基准点，方向nFormula: 针对坐标原点针对坐标原点 针对固定参考点针对固定参考点(xf,yf)x=x*Sxx=xf+(x-xf)*Sxy=y*Sy y=yf+(y-yf)*Sy5.2.3 2D 变比（缩放）变比（缩放）28n矩阵表示矩阵表示 x x sx 0 P= P= S= y y 0 sy

15、 P = S P2911(2，1)12xyxy1Example302D变比变比讨论讨论n如果如果|Sx|或或|Sy|大于大于1，则表示图形在，则表示图形在X轴方向或轴方向或Y轴方向放大；轴方向放大；n如果如果|Sx|或或|Sy|小于小于1，则表示图形在，则表示图形在X轴方向或轴方向或Y轴方向缩小；轴方向缩小；n如果如果|Sx|=|Sy|，则表示均匀缩放；，则表示均匀缩放；n如果如果|Sx|Sy|，则表示差值缩放；，则表示差值缩放；n如果如果|Sx|或或|Sy|等于等于1，则表示图形在，则表示图形在X轴方向或轴方向或Y轴方向不变；轴方向不变；n如果如果Sx或或Sy小于零，则表示图形在小于零，则表

16、示图形在X轴方向或轴方向或Y轴轴方向作镜面变换。方向作镜面变换。31二维变换内容二维变换内容n图形变换预备知识图形变换预备知识nBasic transformation（基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransformation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster method of transformation（变换

17、（变换的光栅方法）的光栅方法）325.2.4 2D 矩阵表示矩阵表示 n在图形系统中，矩阵式实现变换的标准方法。在图形系统中，矩阵式实现变换的标准方法。nP P = P+T (= P+T (平移平移););nP P = R= RP (P (旋转旋转););nP P = S= SP P ( (变比变比););n对于平移、旋转和缩放变换，每个基本的变换都可表示为对于平移、旋转和缩放变换，每个基本的变换都可表示为普通距阵形式：普通距阵形式：P = M1 * P + M2 采用齐次坐标采用齐次坐标(xh, yh, h)表示每个表示每个2D坐标位置坐标位置(x,y)齐次坐标表示就是用齐次坐标表示就是用n

18、+1维向量表示维向量表示n维向量。维向量。P = M * P335.2.4 2D 矩阵表示矩阵表示 nPoint (x,y) - (xh, yh, h) - (x, y, 1)Tn2D graph - 3xnn基本变换参数基本变换参数 - 3x3n2D 图形变换坐标计算：图形变换坐标计算： P最终坐标最终坐标 = M变换矩阵变换矩阵* P原坐标原坐标34n平移变换平移变换 x 1 0 tx xy = 0 1 ty y 1 0 0 1 1 P=T(tx,ty)*P 举例35n旋转变换旋转变换 x cos - sin 0 x y = sin cos 0 y 1 0 0 1 1 P=R()*P 举例

19、36n变比变换变比变换 x sx 0 0 xy = 0 sy 0 y 1 0 0 1 1 P=S(sx,sy)*P 注意：上述三种都是针对坐标原点和X/Y轴方向的。 举例37nBasic transformation（基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransformation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster met

20、hod of transformation（变换（变换的光栅方法）的光栅方法）二维变换内容二维变换内容385.2.5 2D 其他变换其他变换 nReflections反射反射(对称对称)nReflection about x-axis X轴反射轴反射nReflection about y-axis Y轴反射轴反射nReflection about (0,0) 原点反射原点反射nReflection about x=y 45度线反射度线反射nShearing错切错切nshearing in x X方向错切方向错切nshearing in y Y方向错切方向错切391. Reflection反射（

21、对称）反射（对称）about x-axis 1 0 0 0 -1 0 0 0 1 yx123231X轴坐标不变Y轴坐标变反40about y-axis -1 0 0 0 1 0 0 0 1 xy123132Y轴坐标不变X轴坐标变反41about (0,0) -1 0 0 0 -1 0 0 0 1 xy123132X轴坐标变反Y轴坐标变反绕原点旋转18042About x=y 0 1 0 1 0 0 0 0 1 xyy=x1212X,Y坐标互换位置举例432. shearing错切错切(X/Y方向的拉伸方向的拉伸) 1 SHx 0 0 1 0 0 0 1 xy112 3(2,1)(3,1)xy1

22、1SHx=2(1,1)44 1 0 0 SHy 1 0 0 0 1 xy11232(1,3)(1,2)xy11SHy=2(1,1)举例45nBasic transformation（基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransformation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster method of transformat

23、ion（变换（变换的光栅方法）的光栅方法）二维变换内容二维变换内容465.3 二维二维复合复合变换变换 n进行一次以上的基本变换进行一次以上的基本变换 复合变换复合变换n利用矩阵表示，就可通过计算单个变换的矩阵利用矩阵表示，就可通过计算单个变换的矩阵乘积，将任意顺序变换的矩阵建立为乘积，将任意顺序变换的矩阵建立为组合变换组合变换矩阵矩阵。n形成变换矩阵的乘积被称为矩阵的合并形成变换矩阵的乘积被称为矩阵的合并(concatenation)或复合或复合(composition) 475.3 复合变换复合变换 nTranslations 连续平移连续平移nRotations 连续旋转连续旋转nSca

24、lings 连续变比连续变比nGeneral pivot-point transformations 通用基准点的变换通用基准点的变换nGeneral Directions transformations 通用方向的变换通用方向的变换485.3.1 Translations 连续连续平移平移 nn个连续的平移向量个连续的平移向量(tx1 , ty1),(tx2 , ty2), ,(txn , tyn)被用被用于点于点P，那么最后的点坐标可计算为，那么最后的点坐标可计算为 P = T(txn, tyn)* T(tx2, ty2) *T(tx1, ty1) P = T(txn, tyn)* T(t

25、x2, ty2) *T(tx1, ty1) P n计算时，可先计算两个平移变换矩阵的乘积计算时，可先计算两个平移变换矩阵的乘积 T(tx2, ty2) T(tx1, ty1) = T(tx2 + tx1, ty2+ ty1)n连续平移是可加的连续平移是可加的49n平移变换平移变换 x 1 0 tx 1 0 tx1y = 0 1 ty 0 1 ty1 *P 1 0 0 1 0 0 1 1 0 tx+ tx1 P= 0 1 ty+ ty1 *P0 01举例505.3.2 Rotations 连续连续旋转旋转 n应用于点应用于点P的的n个连续旋转个连续旋转(1), (2). (n)，得到，得到的点的

26、点P的坐标可计算为的坐标可计算为 P = R(n) * R(2) R(1) P = R(n) * R(2) R(1) P nR(2) R(1)= R(1+2) 则则P的坐标可计算为的坐标可计算为 P = R(1+2) Pn连续旋转是可加的连续旋转是可加的. 自己推导。自己推导。举例515.3.3 Scalings 连续连续变比变比 nn个连续缩放操作个连续缩放操作S(sx1, sy1), S(sx2, sy2), S(sxn, syn)的变换距阵连接，产生的组合变换距阵的变换距阵连接，产生的组合变换距阵 P= S(sxn, syn)* S(sx2, sy2)* S(sx1, sy1)*Pn S

27、(sx2, sy2) *S(sx1, sy1) = S(sx1*sx2, sy1*sy1) n连续缩放操作是相乘的连续缩放操作是相乘的，非叠加的，非叠加的，自己推导自己推导。n前三个基本变换是针对原点和前三个基本变换是针对原点和X,Y轴的。轴的。举例525.3.4 通用基准点变换通用基准点变换nSolution 平移使基准点移动到坐标原点平移使基准点移动到坐标原点(T) 针对原点做指定变换针对原点做指定变换(M) 反向平移使基准点回到原始位置反向平移使基准点回到原始位置(T-1)53Example 1 针对固定点变比针对固定点变比 xy(xf,yf)yxxyxy 1 0 xf 0 1 yf 0

28、 0 1 sx 0 0 0 sy 0 0 0 1 1 0 -xf 0 1 -yf 0 0 154Example 2 针对固定点旋转针对固定点旋转 1 0 xf 0 1 yf 0 0 1xy(xf,yf)yx cos - sin 0 sin cos 0 0 0 1 1 0 -xf 0 1 -yf 0 0 1xyxy55通用基准点变换通用基准点变换旋转旋转nExamples 5-1n将三角形沿基准点将三角形沿基准点(2,3)逆时针旋转逆时针旋转 45o. 写出写出其变换矩阵和变换过程，其变换矩阵和变换过程， 并给出顶点并给出顶点a(4,8)变变化后的坐标值。化后的坐标值。nSolution 平移使

29、基准点移动到坐标原点平移使基准点移动到坐标原点T1=T(-2，-3); 绕原点做旋转变换绕原点做旋转变换 R=R(45); 反向平移反向平移，使基准点回到原始位置使基准点回到原始位置T2=T(2，3)56xy(xf,yf)575.3.5 通用方向变换通用方向变换nSolution 旋转对象使任意方向与坐标轴方向重合旋转对象使任意方向与坐标轴方向重合 针对坐标轴方向做指定变换针对坐标轴方向做指定变换 反向旋转使任意方向回到原方向反向旋转使任意方向回到原方向nExample 5-2xyS2S158Example 5-2 通用方向的缩放变换通用方向的缩放变换cos-45 sin-45 0Sin-45

30、 cos-45 0 0 0 1 1 0 0 0 2 0 0 0 1xyS2S1xy11S1=1, S2=2=45x11ycos45 -sin45 0sin45 cos45 0 0 0 159 3/2 1/2 0 1/2 3/2 0 0 0 1M= 0 3/2 2 1/2 0 1/2 2 3/2 1 1 1 1P=M * 0 1 1 0 0 0 1 1 1 1 1 1=60Example 5-2 通用方向的缩放变换通用方向的缩放变换x11y x rsxx rsxy trsx xy = rsyx rsyy trsy y 1 0 0 1 1 5.3.6 二维变换总结二维变换总结通用复合变换通用复合变

31、换61n 二维空间中某点的变换矩阵可以表示成点的齐次二维空间中某点的变换矩阵可以表示成点的齐次坐标矩阵与坐标矩阵与3阶方阵阶方阵T2D相乘，其中相乘，其中T2D又被称为二又被称为二维齐次坐标变换矩阵，简称维齐次坐标变换矩阵，简称二维变换矩阵二维变换矩阵。源代码由 king 创建二维变换内容二维变换内容nBasic transformation（基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransf

32、ormation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster method of transformation（变换（变换的光栅方法）的光栅方法）76 坐标系间的变换坐标系间的变换xyxyx0y0 平移平移 (x0,y0) 到到 (0,0) 旋转旋转 轴轴x使与使与x轴重合轴重合M = R(- ) * T(-x0,-y0)77xyxyx0y0 y方向的单位矢量方向的单位矢量v= V/|V| = (vx,vy)V顺旋顺旋90度获得度获得x的单位矢量的单位矢量u=(vy,-vx) = (ux,uy) ux uy 0R= vx vy 0 0

33、 0 1V78二维变换内容二维变换内容nBasic transformation（基本变换）（基本变换）nMatrix representation（矩阵表示）（矩阵表示）nOther 2D transformations （其他变换）（其他变换）nComposite transformation（复合变换）（复合变换）nTransformation between Coordinate Systems（坐标系间的变换）（坐标系间的变换）nRaster method of transformation（变换（变换的光栅方法）的光栅方法）795.4 二维观察二维观察n2D Viewing Pip

34、eline（二维观察流程）（二维观察流程）nClipping Window（裁剪窗口）（裁剪窗口）nViewport（视点）（视点）n2D Clipping（二维裁剪）（二维裁剪）nPoint clipping（点裁剪）（点裁剪）nLine clipping（线段裁剪）（线段裁剪）nArea clipping（多边形裁剪）（多边形裁剪）nText clipping（文字裁剪）（文字裁剪）805.4.1 二维观察流程二维观察流程nDef. 常规图形系统中，世界坐标系中指定的用于常规图形系统中，世界坐标系中指定的用于显示的坐标区域显示的坐标区域- 裁剪窗口裁剪窗口(clipping window)

35、或或窗口窗口(window)nDef. 显示设备上用于窗口映射的坐标区域显示设备上用于窗口映射的坐标区域- 视视区、视口区、视口(viewport)。nDef. 通常，世界坐标系中部分场景映射到设备坐通常，世界坐标系中部分场景映射到设备坐标系的过程标系的过程-观察观察(视图、视像视图、视像)变换变换。81n世界坐标系世界坐标系(World Coordinates) 图形定义时所采用的坐标系，坐标的大小和尺寸图形定义时所采用的坐标系，坐标的大小和尺寸由用户确定。由用户确定。n设备坐标系设备坐标系(Device Coordinates) 与一个图形设备相关的坐标系叫设备坐标系。如与一个图形设备相关

36、的坐标系叫设备坐标系。如显示器或打印机有它们自己的坐标系。显示器或打印机有它们自己的坐标系。n规范化坐标系规范化坐标系(Normalized Coordinates) 它是独立于具体物理设备的一种坐标系，其显示它是独立于具体物理设备的一种坐标系，其显示空间在空间在X和和Y方向上都是从方向上都是从0到到1坐标系坐标系82设备坐标系设备坐标系xyv1v2v3v4视口视口xyw1w2w3w4窗口窗口世界坐标系世界坐标系83111绘图仪绘图仪其他输出设备其他输出设备建模坐标建模坐标世界坐标世界坐标规范化坐标规范化坐标设备坐标设备坐标84窗口窗口-视口变换视口变换xyw1w2w3w4窗口窗口(xw,yw

37、)xyv1v2v3v4视口视口(xv,yv)85保持视口与窗口中的对象具有同样的相对位置，保持视口与窗口中的对象具有同样的相对位置，必须满足必须满足 (Xw-W1) / (W2-W1) = (Xv-V1) / (V2-V1) (Yw-W3) / (W4-W3) = (Yv-V3) / (V4-V3)窗口窗口-视口变换视口变换86 Xv = SxXw+tx Yv = SyYw+ty缩放系数缩放系数 Sx = (V2-V1) / (W2-W1) Sy = (V4-V3) / (W4-W3)平移参数平移参数 tx = (W2*V1-W1*V2) / (W2-W1) ty = (W4*V3-W3*V4

38、) / (W4-W3)87n已知已知w1=10,w2=20,w3=40,w4=80, v1=80,v2=110,v3=10,v4=130, 窗口中一点窗口中一点P(15，60)，求视区中的映射点，求视区中的映射点P?n解：解：(15-10)/(20-10) = (xv-80)/(110-80) (60-40)/(80-40) = (yv-10)/(130-10)n xv = 95, yv=70Example88二维观察内容二维观察内容n2D Viewing Pipeline（二维观察流程）（二维观察流程）nClipping WindownViewportn2D Clipping（二维裁剪）（二

39、维裁剪）nPoint clippingnLine clippingnArea clippingnText clipping895.4.4 2D裁剪裁剪n裁剪定义Clipping 识别图形在指定区域内或区域外的过程-裁剪n裁剪的时机 (1) 针对窗口边界裁剪 (2) 针对视区边界裁剪90n裁剪类型裁剪类型n点裁剪点裁剪n直线裁剪直线裁剪n多边形多边形区域区域裁剪裁剪n曲线裁剪（自学）曲线裁剪（自学）n文文字字裁剪裁剪915.4.5 点的裁剪点的裁剪点点(x,y)如果满足下列不如果满足下列不等式则保留：等式则保留： w1 = x = w2 w3 = y = w4w1w2w3w4(x,y)925.4

40、.6 直线段的裁剪直线段的裁剪93假定直线段用假定直线段用p1(x1,y1)p2(x2,y2)表示。表示。n直线段和剪裁窗口的可能关系：直线段和剪裁窗口的可能关系：n完全落在窗口内（完全可见）完全落在窗口内（完全可见）n完全落在窗口外（显然不可见）完全落在窗口外（显然不可见）n与窗口边界相交与窗口边界相交窗口窗口 直线段与窗口的关系直线段与窗口的关系A AB BC CD DE EF FH HG GI IJ J94实交点实交点是直线段与窗口是直线段与窗口矩形边界的交点。矩形边界的交点。虚交点虚交点则是直线段与窗则是直线段与窗口矩形边界延长线或直口矩形边界延长线或直线段的延长线与窗口矩线段的延长线

41、与窗口矩形边界的交点。形边界的交点。窗口 实交点与虚交点ABCDEFHGIJ虚交点实交点实交点实交点虚交点虚交点95nCohen-Sutherland直线裁剪算法直线裁剪算法nLiang梁友栋梁友栋-Barsky直线裁剪算法直线裁剪算法n中点分割算法中点分割算法nNicholl-Lee-Nicholl直线裁剪算法直线裁剪算法nCyrus-Beck算法（自学）算法（自学）直线段的裁剪算法直线段的裁剪算法961. Cohen-Sutherland直线裁剪算法直线裁剪算法基本思想基本思想：n直线由端点标识；直线由端点标识；n测试直线端点和窗口边界的关系以确定是否测试直线端点和窗口边界的关系以确定是否

42、 需要计算交点需要计算交点 ；9798nCS 编码方案编码方案n扩展窗口的边界将整个扩展窗口的边界将整个2D平面划分为平面划分为9个区域个区域n每个区域赋予一个每个区域赋予一个4位编位编码码, 称为区域码称为区域码000001100100010100100001100110001010上上下下右右左左w1w2w3w499n编码规则编码规则nb0 = 1 if x w2nb2 = 1 if y w4000001100100010100100001100110001010上上下下右右左左w1w2w3w4100n算法描述算法描述n计算直线端点编码计算直线端点编码, c1 和和 c2;n判断判断nc1

43、 和和 c2 均为均为0000，保留直线，保留直线nc1 & c2 不为零，同在某一边界外，删除该直线不为零，同在某一边界外，删除该直线nc1 和和 c2不不 均为均为0000 且且c1 & c2 为零，需要进一为零，需要进一步求解交点步求解交点n以以L,R,B,T 为序，将为序，将x=w1/w2或或y=w3/w4带入直带入直线方程，计算直线与窗口边界的交点，将交点和另一线方程，计算直线与窗口边界的交点，将交点和另一端点重复上述过程，直至线段保留或删除端点重复上述过程，直至线段保留或删除101CS线段裁剪算法线段裁剪算法 举例举例P3P41000001100100010100100001100

44、110001010102CS线段裁剪算法线段裁剪算法 举例举例132P1P2000001100100010100100001100110001010103算法的步骤：算法的步骤：(1)输入直线段的两端点坐标：输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界，以及窗口的四条边界坐标：坐标：wyt、wyb、wxl和和wxr。(2)对对p1、p2进行编码：点进行编码：点p1的编码为的编码为code1，点，点p2的编码为的编码为code2。(3)若若code1|code2=0，对直线段应简取之，转，对直线段应简取之，转(6)；否则，若；否则，若code1&code20

45、，对直线段可简弃之，转，对直线段可简弃之，转(7)；当上述两条均不满足时，；当上述两条均不满足时，进行步骤进行步骤(4)。(4)确保确保p1在窗口外部：若在窗口外部：若p1在窗口内，则交换在窗口内，则交换p1和和p2的坐标值和编码。的坐标值和编码。(5)按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换坐标值替换p1的坐标值。也即在交点的坐标值。也即在交点s处把线段一分为二，并去掉处把线段一分为二，并去掉p1s这这一段。考虑到一段。考虑到p1是窗口外的一点，因此可以去掉是窗口外的一点，因此可以去掉p1s。用。用

46、p1替代替代s转转(2)。(6)用直线扫描转换算法画出当前的直线段用直线扫描转换算法画出当前的直线段p1p2。(7)算法结束。算法结束。104计算线段计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点与窗口边界的交点if(LEFT & code !=0)if(LEFT & code !=0) x=XL;x=XL;y=y1+(y2-y1)y=y1+(y2-y1)* *(XL-x1)/(x2-x1);(XL-x1)/(x2-x1);else if(RIGHT & code !=0)else if(RIGHT & code !=0) x=XR;x=XR;y=y1+(y2-y1)y=y1+(

47、y2-y1)* *(XR-x1)/(x2-x1);(XR-x1)/(x2-x1);else if(BOTTOM & code !=0)else if(BOTTOM & code !=0) y=YB;y=YB;x=x1+(x2-x1)x=x1+(x2-x1)* *(YB-y1)/(y2-y1);(YB-y1)/(y2-y1); else if(TOP & code !=0) else if(TOP & code !=0) y=YT;y=YT;x=x1+(x2-x1)x=x1+(x2-x1)* *(YT-y1)/(y2-y1);(YT-y1)/(y2-y1);105n程序实现程序实现p1p2p3p

48、41321举例举例。106n程序流程图程序流程图107n优点优点：简单，易于实现。简单，易于实现。n算法中求交点的次数决定了算法的速度，最算法中求交点的次数决定了算法的速度，最坏要求交三次，反复循环。坏要求交三次，反复循环。n在裁剪窗口非常大或非常小时效率很高。在裁剪窗口非常大或非常小时效率很高。CS线段裁剪算法小结线段裁剪算法小结1082 2 Liang-Barsky直线裁剪算法直线裁剪算法n思想：基于直线段参数方程分析的快速直思想：基于直线段参数方程分析的快速直线裁剪算法。线裁剪算法。n参数方程参数方程直线两端点直线两端点 P1(x1, y1), P2 (x2, y2)x = x1 + (

49、x2 - x1)uy = y1 + (y2 - y1)u, 0u1109n已知直线端点已知直线端点 ： 起点起点P1(x1, y1)，终点，终点P2(x2, y2)n参数方程：参数方程：x = x1 + (x2 - x1)uy = y1 + (y2 - y1)u P1P2u1110nLB算法推导如果直线在窗口内, 则w1 x1 + dx * u w2w3 y1 + dy * u w4统一表示为：Pk * u Qk k = 1, 2, 3, 4 P1 = - dx, Q1 = x1-w1 P2 = dx, Q2 = w2-x1 P3 = - dy, Q3 = y1-w3 P4 = dy, Q4

50、= w4-y1111w1w2w3w4ubulutur01dxdyP1 = - dx, Q1 = x1-w1 P2 = dx, Q2 = w2-x1P3 = - dy, Q3 = y1-w3 P4 = dy, Q4 = w4-y1112n算法描述算法描述n计算计算 Pk, Qk, k=14nPk = 0，表示直线平行于窗口某边界，表示直线平行于窗口某边界nQk = 0，直线在窗口内，平行边界内，直线在窗口内，平行边界内n对对 Pk0的情形的情形, 用用Qk/Pk计算交点所对计算交点所对应的应的u值值113n对每条线计算参数对每条线计算参数u1&u2u1=Max(Qk/Pk|Pk 0 U 1)n如

51、果如果u1 u2, 则直线在窗口外，否则计算则直线在窗口外，否则计算交点坐标交点坐标 x(u) = x1+dx*u y(u) = y1+dy*u114LBLB线段裁剪算法线段裁剪算法 例例1 1n已知线段的两个端点已知线段的两个端点P1(3, 4)，P2(8, 2) 窗口边界窗口边界x=1, x=4, y=1, y=3n用用LB算法对线段进行裁剪算法对线段进行裁剪115n线段的参数方程线段的参数方程 x = 3 + 5u y = 4 - 2unP1 = -5, Q1 = 2, R1 = -2/5P2 = 5, Q2 = 1, R2 = 1/5P3 = 2, Q3 = 3, R3 = 3/2P4

52、 = -2, Q4 = -1, R4 = 1/2nu1 = max(0, -2/5, 1/2) = 1/2u2 = min(1, 1/5, 3/2) = 1/5nu1 u2 所以线段所以线段全部被裁剪全部被裁剪116线段的两个端点（线段的两个端点（-2，-1）和（）和（1，1.5）窗口边界窗口边界x1 = -1, x2 = 1, y1 = -1, y2 = 1LB线段裁剪算法线段裁剪算法 例例2117x = 3, y = 2.5 p1 = -3q1 = -1 r1 = 1/3 p2 = 3q2 = 3r2 = 1p3 = -2.5 q3 = 0r3 = 0p4 = 2.5 q4 = 2r1 =

53、 4/5对于对于p 0，u2 = min1，1， 4/5 = 4/5则则u1u2，则可见线段的端点坐标：，则可见线段的端点坐标：x = x1 + u1 x = -1,y = y1 + u1 y = -1/6 即即(-1, -1/6)x=x1+u2 x=2/5,y=y1+u2 y =1 即(2/5, 1)118void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT;float x1,y1,x2,y2,XL,XR,YB,YT; fl

54、oat dx,dy,u1,u2;float dx,dy,u1,u2;tl=0;tu=1;tl=0;tu=1;dx =x2-x1;dy =y2-y1;dx =x2-x1;dy =y2-y1; if(ClipT(-dx,x1-Xl,&u1,&u2) if(ClipT(-dx,x1-Xl,&u1,&u2) if(ClipT(dx,XR-x1, &u1,&u2) if(ClipT(dx,XR-x1, &u1,&u2)if(ClipT(-dy,y1-YB, &u1,&u2)if(ClipT(-dy,y1-YB, &u1,&u2) if(ClipT(dy,YT-y1, &u1,&u2) if(ClipT(

55、dy,YT-y1, &u1,&u2) displayline(x1+u1displayline(x1+u1* *dx,y1+u1dx,y1+u1* *dy, dy, x1+u2x1+u2* *dx,y1+u2dx,y1+u2* *dy)dy)return;return; 程序实现程序实现119bool ClipT(p,q,u1,u2)bool ClipT(p,q,u1,u2)float p,q,float p,q,* *u1,u1,* *u2;u2; float r; float r;if(p0)if(pif(r* *u2) return FALSE;u2) return FALSE;else

56、 if(relse if(r* *u1)u1) * *u1=r;u1=r;return TRUE;return TRUE; 。/下页下页120else if(p0)else if(p0) r=p/q;r=p/q;if(rif(r* *u1)return FALSE;u1)return FALSE;else if(relse if(r* *u2)u2) * *u2=r;return TRUE;u2=r;return TRUE; else if(q0) return FALSE; else if(q0) return FALSE; return TRUE; return TRUE; 121nLB

57、vs. CSnLB 效率高于效率高于 CS, 因为减少了交点计算次数。因为减少了交点计算次数。 参数参数u1 和和 u2 的更新需要四次除法的更新需要四次除法, 交点坐交点坐标计算至多标计算至多4次乘法。次乘法。nLiang-Barsky和和Cohen-Sutherland算算法很容易扩展为三维裁剪算法法很容易扩展为三维裁剪算法1223 中点分割裁剪算法中点分割裁剪算法基本思想：基本思想： 与前一种与前一种Cohen-SutherlandCohen-Sutherland算法一样首先对线段端点算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况进行编码，并把线段与窗口的关系分为三种情

58、况: : n全在、完全不在和线段和窗口有交。对前两种情况，全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。进行一样的处理。n对于第三种情况，用中点分割的方法求出线段与窗对于第三种情况，用中点分割的方法求出线段与窗口的交点。口的交点。123求线段与窗口的交点求线段与窗口的交点A、B分别为距P0、P1最近的可见点，Pm为P0P1中点P0P1PmAB124中点分割算法的核心思想核心思想是通过二分逼近来确定直线段与窗口的交点。n从 出发找最近可见点的方法n先求出 的中点n若 不是显然不可见的，并且 在窗口中有可见部分，则距 最近的可见点一定落在 上，所以用 代替 ；0P10PPmPmPP

59、0mPP00PmPP0mPP010PP125n否则取 代替n再对新的 求中点 。重复上述过程，直到 长度小于给定的控制常数为止，此时 收敛于交点。n从 出发找最近可见点采用上面类似方法。10PP1PPm10PPmP1PPmmP1Pn问：算法为什么可行？会不会无限循环、不断二分？1264 NLN直线裁剪算法直线裁剪算法(自学自学)nIDEA 通过在裁剪窗口周围创立通过在裁剪窗口周围创立多个区域多个区域，并在求交运算，并在求交运算之前进行更多的区域测试，从而之前进行更多的区域测试，从而避免避免对直线段进行对直线段进行多次剪裁多次剪裁。n适用范围适用范围 仅仅适用于仅仅适用于2D剪裁剪裁127n算法

60、步骤算法步骤n从从P1点向窗口的四个角点发出射线，这四点向窗口的四个角点发出射线，这四条射线和窗口的四条边界直线一起将二维平条射线和窗口的四条边界直线一起将二维平面划分为更多的小区域面划分为更多的小区域 。128线段端点线段端点P1的三种位置的三种位置129Case 1130Case 2131Case 3A132Case 3B133nP2位置位置? 比较直线段比较直线段P1P2的斜的斜率和剪裁区域边界的率和剪裁区域边界的斜率斜率. yt-y1 y2-y1 yt-y1xr-x1 x2-x1 xl-x1n交点计算交点计算p2134n裁剪类型裁剪类型n点裁剪点裁剪n直线裁剪直线裁剪n多边形多边形区域