CG第6章电子教案

1、2022-3-161第6章 二维变换及二维观察提出问题提出问题 如何对二维图形进行方向、尺寸和形状方面的变换 如何方便地实现在显示设备上对二维图形进行观察2022-3-1626.1 6.1 基本概念基本概念6.1.1 6.1.1 齐次坐标齐次坐标 (homogeneous coordinates) 齐次坐标表示齐次坐标表示: 用n+1维向量表示一个n维向量。l齐次坐标的不唯一性例：非齐次坐标点Px, y: 3, 5 齐次坐标点Phx, hy, h: 12, 20, 4; 6, 10, 2; 3, 5, 1规范化齐次坐标表示规范化齐次坐标表示: h=1的齐次坐标表示。如何从齐次坐标转换到规范化齐

2、次坐标？ hp1, hp2, ,hpn, h hp1 /h, hp2 /h, , hpn /h, 12022-3-1636.1.2 6.1.2 几何变换几何变换图形的几何变换几何变换: 对图形的几何信息经过平移、比例、旋转等变换后产生新的图形，是图形在方向、尺寸和形状方面的变换。2022-3-1646.1.3 二维变换矩阵二维变换矩阵 smlqdcpbayxTyxyxD1112假设：p(x,y)为x0y平面上二维图形变化前的点， p(x,y)为变换后的点，则二维变换为：其中T2D表示为4个子矩阵。T T1 1T T2 2T T3 3T T4 4比例、旋转、对称、错切等平移投影整体比例2022-

3、3-1656.2 基本几何变换基本几何变换基本几何变换都是相对于坐标原点和坐标轴进行相对于坐标原点和坐标轴进行的几何变换的几何变换： p(x,y)p(x,y)为xOy平面上二维图形变化前的点， p(x,y)p(x,y)为变换后的点。6.2.1 平移变换平移变换平移平移是指将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程。2022-3-166平移是一种不产生变形而移动物体的刚体变换（rigid-body transformation）YXTxTy图6-1 平移变换PPTxTxxyTyy2022-3-167Tx，Ty称为平移矢量平移矢量1010001yxTT变换矩阵变换矩阵： 1101

4、000111yxyxTyTxTTyxyx平移变换演示平移变换演示2022-3-1686.2.2 比例变换比例变换比例变换比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍，沿y方向放缩Sy倍。其中Sx和Sy称为比例系数比例系数。YX图6-2 比例变换(Sx=2,Sy=3)P(4,3)P(2,1)2022-3-169比例变换的齐次坐标计算形式： 1100000011ySxSSSyxyxyxyx2022-3-1610(a) Sx=Sy比例原图(b) SxSy比例图示：比例变换原图Sx=SySySx=Sy1SxSy2022-3-1611整体比例变换整体比例变换： 10001000111SySxSyx

5、Syxyx比例变换演示比例变换演示2022-3-16126.2.3 旋转变换旋转变换二维旋转二维旋转是指将p点绕坐标原点转动某个角度（逆时针为正，顺时针为负）得到新的点p的重定位过程。YX图6-4 旋转变换PPrrcosrx sinry )sin(ry)cos(rxsinsincoscosrrcossinsincosrrcossinyxsincosyx2022-3-16131000cossin0sincos1yx矩阵矩阵：逆时针旋转角:顺时针旋转角: 1cossinsincos1000cossin0sincos11yxyxyxyx 1000)cos()sin(0)sin()cos(11yxyx

6、2022-3-1614 100010111yxyx简化计算简化计算: :当很小时，cos1, sin，则有如下简化计算公式： 旋转变换演示旋转变换演示2022-3-16156.2.4 对称变换对称变换对称变换对称变换后的图形是原图形关于某一轴线或原点的镜像。XY(a)关于x轴对称XY(b)关于y轴对称XY(c)关于原点对称2022-3-1616XY(d)关于x=y对称XY(e)关于x=-y对称2022-3-1617(1)关于关于x x轴对称轴对称100010001YXP(x,-y)P(x,y)(a)关于x轴对称2022-3-1618(2)关于关于y y轴对称轴对称YXP(-x,y)p(x,y)

7、(b)关于y轴对称1000100012022-3-1619(3)关于原点对称关于原点对称100010001YXP(x,y)(c)关于原点对称P(-x,-y)2022-3-1620(4)关于关于y=xy=x轴对称轴对称YXp(x,y)p(y,x)x=y(d)关于x=y对称1000010102022-3-1621(5)关于关于y=-xy=-x轴对称轴对称YXP(-y,-x)P(x,y)x=-y(e)关于x=-y对称100001010对称变换演示对称变换演示2022-3-16226.2.5 错切变换错切变换错切变换错切变换，也称为剪切、错位变换，用于产生弹性物体的变形处理。YXYXYX(a) 原图(

8、b) 沿x方向错切(c) 沿y方向错切图6-7 错切变换2022-3-1623其变换矩阵为： 1000101cb (1)沿x方向错切： b = 0, c 0cyxxyy 10001001c2022-3-162410001001b (2)沿y方向错切: c = 0, b 0 (3)两个方向错切: b 0 且 c 0 cyxxybxyybxyxx 1000101cb错切变换演示错切变换演示2022-3-16256.2.6 二维图形几何变换的计算二维图形几何变换的计算 smlqdcpbayxTyxyxD1112sqypxmdybxysqypxlcyaxx2022-3-1626几何变换均可表示成几何变

9、换均可表示成 P= P * T 的形式的形式 1. 点的变换：行矩阵或列矩阵 2. 直线的变换：两端点 Tyxyx11Tyxyxyxyx1111221122112022-3-1627 3. 多边形的变换：每个顶点的坐标位置 4. 曲线的变换 通过变换曲线上的每一点来实现。Tyxyxyxyxyxyxyxyxnnnn1.1111.1113322113322112022-3-16286.3 复合变换复合变换复合变换复合变换是指： 图形作一次以上的几何变换，变换结果是每次的变换矩阵相乘。 任何一复杂的几何变换都可以看作基本几何变换的组合形式。复合变换具有如下形式：nTTTTPTPP 321) 1( n

10、)(321nTTTTP 2022-3-16296.3.1 二维复合平移二维复合平移两个连续平移是相加的。10100011010001221121yxyxtttTTTTTTT10100012121yyxxTTTT复合平移变换演示复合平移变换演示2022-3-16306.3.2 6.3.2 二维复合比例二维复合比例连续比例变换是相乘的。10000001000000221121yxyxsssSSSSTTT10000002121yyxxSSSS复合比例变换演示复合比例变换演示2022-3-16316.3.3 6.3.3 二维复合旋转二维复合旋转两个连续旋转是相加的。可写为：)(21)()(21RRRR

11、1000cossin0sincos1000cossin0sincos2222111121rrrTTT1000)cos()sin(0)sin()cos(21212121复合旋转变换演示复合旋转变换演示2022-3-16326.3.4 其它二维复合变换其它二维复合变换1000cos000cos100010110001011000cos000cos1000 cos sin0 sincostgtgtgtgR分解旋转变换矩阵为：因此：旋转变换=比例变换+错切变换复合平移变换演示复合平移变换演示2022-3-16336.3.5 相对任一参考点的二维几何变换相对任一参考点的二维几何变换相对某个参考点(xF,

12、yF)作二维几何变换，其变换过程为：(1) 平移(2) 针对原点进行二维几何变换。(3) 反平移例. 相对点(xF,yF)的旋转变换 (p155: 6-23)例. 相对点(xF,yF)的比例变换 (p155: 6-24)2022-3-16346.3.6 相对任意方向的二维几何变换相对任意方向的二维几何变换相对任意方向作二维几何变换，其变换的过程是：(1) 旋转变换(2) 针对坐标轴进行二维几何变换；(3) 反向旋转例. 相对直线y=x的反射变换（p155: 6-26）2022-3-1635例例(p156) 将正方形ABCO各点沿下图所示的(0,0)(1,1)方向进行拉伸，结果为如图所示的菱形，

13、写出其变换矩阵和变换过程。YX13/21/21/23/222图6-8 针对固定方向的拉伸OABCCCBBAA2022-3-1636课后作业：课后作业：习题六（习题六（p176）6.1 名次解释：齐次坐标，规范化齐次坐标，图形的几何变换。6.2 说明二维变换矩阵T2D 中各元素在变换中的具体作用。smlqdcpba2022-3-16376.3.7 坐标系之间的变换坐标系之间的变换问题问题：图6-9 坐标系间的变换xyxyOOx0y0p(xp,yp)2022-3-1638分析：分析：xyyOO(x0,y0)图6-11 坐标系变换的变换原理xp,也即pp*pxpy *xOp*yOp2022-3-16

14、39可以分两步进行：xyyOOx0y0 x(a)将xy坐标系的原点平移到xy坐标系的原点p(xp,yp)xyOyx(b)将x轴旋转到x轴上p(xp,yp)2022-3-1640于是： 1000cossin0sincos101000100yxTTRt 1000cossin0sincos101000100yxRtTTpTp Tyxyxppppp11其中： 2022-3-16416.3.8 光栅变换光栅变换直接对帧缓存中象素点进行操作的变换称为光栅变换光栅变换。 光栅平移变换： (a)读出象素块的内容(b)复制象素块的内容(c)擦除原象素块的内容2022-3-1642 90、180和270的光栅旋转

15、变换： (a)逆时针旋转90(x,y)(y,rowlen-x)rowlen(x,y)(rowlen-x,vollen-y)(b)逆时针旋转180rowlenvollen2022-3-1643 复杂情形：任意角度的光栅旋转变换： 旋转的象素阵列光栅网格AA2132022-3-1644 光栅比例变换： ( (b)b)原图原图(a)Sx=1/2,Xy=1/2缩小时原图中的缩小时原图中的相应象素区域相应象素区域(a)Sx=1,Xy=3/2放大时原图中的放大时原图中的相应象素区域相应象素区域2022-3-16456.3.9 变换的性质变换的性质 仿射变换具有平行线不变性和有限点数目的不变性 平移、比例、

16、旋转、错切和反射等变换均是二维仿射变换的特例，反过来，任何常用的二维仿射变换总可以表示为这五种变换的复合。 ndycxymbyaxx二维仿射变换二维仿射变换是具有如下形式的二维坐标变换： 2022-3-1646二维几何变换具有如下一些性质： 直线的中点不变性； 平行直线不变性； 相交不变性； 仅包含旋转、平移和反射的仿射变换维持角度和长度的不变性； 比例变化可改变图形的大小和形状； 错切变化引起图形角度关系的改变，甚至导致图形发生畸变。2022-3-16476.4 二维观察二维观察6.4.1 6.4.1 基本概念基本概念 在计算机图形学中，将在用户坐标系中需要进行观察和处理的一个坐标区域称为窗

17、口窗口（Window） 将窗口映射到显示设备上的坐标区域称为视区视区（Viewport）2022-3-16484.1.3 坐标系用户坐标系建模坐标系观察坐标系规格化的设备坐标设备坐标系坐标系直角坐标系仿射坐标系圆柱坐标系球坐标系极坐标系图4-4 坐标系的分类2022-3-1649要将窗口内的图形在视区中显示出来，必须经过将 窗 口 到 视 区 的 变 换 （ W i n d o w - V i e w p o r t Transformation）处理，这种变换就是观察变换观察变换（Viewing Transformation）。XYwxlXYwybwxrwyt窗口vxrvybvyt视区(a)

18、用户坐标系中的窗口(b)屏幕坐标系中的视区vxl2022-3-1650XY窗口用户坐标系中旋转的窗口XY窗口用户坐标系中非矩形窗口2022-3-1651 观察坐标系观察坐标系(View Coordinate)和规格化设备坐标系和规格化设备坐标系(Normalized Device Coordinate) :l观察坐标系观察坐标系是依据窗口的方向和形状在用户坐标平面中定义的直角坐标系。l规格化设备坐标系规格化设备坐标系也是直角坐标系，它是将二维的设备坐标系规格化到（0.0，0.0）到（1.0，1.0）的坐标范围内形成的。1x用户y用户xNDCyNDC窗口视区y观察x观察1(a)观察坐标系(b)规

19、格化设备坐标系2022-3-1652引入了观察坐标系和规格化设备坐标系后，观察变换分为如下图所示的几个步骤，通常称为二维观二维观察流程察流程。 观 察 坐标 系 下对 窗 口进 行 裁剪窗口到视区 (规 范化设备坐标系中定义 )的 变换视图区从规范化坐标系到设备坐标系的变换在图形设备上输出DC用 户 坐标 系 到观 察 坐标 系 间的变换应用程序到图形的用户坐标图6-19 两维观察流程NDCVCWCVC2022-3-1653 变焦距效果变焦距效果: : 窗口大小改变，视区大小不变窗口大小改变，视区大小不变图6-20 变焦距效果（窗口变、视区不变）(a) 原图及变化的窗口(b)与窗口对应的视区1

20、(c)与窗口对应的视区2(d)与窗口对应的视区31123232022-3-1654 整体缩放效果：整体缩放效果：窗口大小不变，视区大小改变窗口大小不变，视区大小改变(a) 原图及窗口(b) 视区1图6-21 整体放缩效果（窗口不变、视区变）(c) 视区2(d)视区3 漫游效果：漫游效果：窗口大小不变，位置移动；视区不变窗口大小不变，位置移动；视区不变 6.4.2 用户坐标系到观察坐标系的变换用户坐标系到观察坐标系的变换用户坐标系到观察坐标系的变换分别由两个变换步骤合成：T=TrTR1. 将观察坐标系原点移动到用户坐标系原点x用户y用户窗口y观察x观察(a) 平移变换101000100yxTr2

21、022-3-16562. 绕原点旋转使两坐标系重合 x用户y用户窗口y观察x观察(b) 旋转变换1000cossin0sincosRT因此，用户坐标系到观察坐标系的变换：1000cossin0sincos101000100yxTTTRrTPP相应坐标点的变换：2022-3-16586.4.3 窗口到视区的变换窗口到视区的变换XYwxlXYwybwxrwyt窗口vxlvybvyt视区图6-23 窗口到视区的变换(a)窗口中的点(b)视区中的点(xw,yw)(xv,yv)vxr要将窗口内的点（xw, yw）映射到相对应的视区内的点（xv, yv）需进行以下步骤：(1) 将窗口左下角点(wxl, w

22、yb)移至用户坐标系的坐标原点:2022-3-1659(2) 针对原点进行比例变换:(3) 进行反平移：将视区左下角点移至设备坐标系原来的位置(vxl, vyb)。wybwytvybvytSy10100011000000101000121vybvxlSSwybwxlTSTyx平移平移反平移反平移比例比例)()(wxlwxrvxlvxrSx2022-3-1660TPyxPvv1100001vybSwybvxlSwxlSSyxyxyxww相应坐标点的变换：10000vybSwybvxlSwxlSSTyxyx变换矩阵：2022-3-1661课后作业：课后作业：习题六（习题六（p176-177）6.1

23、 名词解释：窗口，视区，变焦距效果。2022-3-16626.5 裁剪裁剪 在二维观察中，需要在观察坐标系下对窗口进行裁剪裁剪，即只保留窗口内的那部分图形，去掉窗口外的图形。 算法：1.图形元素在窗口内外的判别； 2.图形元素与窗口的交点。XwxlwxlwxrwxrYwybwybwytwyt窗口(a)窗口中的点(xw, yw) 假设假设窗口是标准矩形，即边与坐标轴平行的矩形，由四条边描述: 上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）。2022-3-16636.5.1 点的裁剪点的裁剪wytywybwxrxwxl且, 对于任意一点P(x, y)， 如果满足则点p(x,

24、y)在矩形窗口内，否则在矩形窗口外。P(x,y)P(x,y)XwxlwxlwxrwxrYwybwybwytwyt窗口(a)窗口中的点(xw, yw)2022-3-16646.5.2 直线段的裁剪直线段的裁剪假定假定直线段用p1(x1, y1) p2(x2, y2)表示。 直线段和剪裁窗口的可能关系：l完全落在窗口内l完全落在窗口外l与窗口边界相交 窗口图6-24 直线段与窗口的关系ABCDEFHGIJ2022-3-1665对于既不完全落在窗口内又不能确定完全落在窗口外的点，计算它与剪裁窗口边界的交点： 实交点实交点是直线段与窗口矩形边界的交点。 虚交点虚交点则是直线段与窗口矩形边界延长线或直线

25、段的延长线与窗口矩形边界的交点。 窗口图6-25 实交点与虚交点ABCDEFHGIJ虚交点实交点实交点实交点虚交点虚交点2022-3-16661. Cohen-Sutherland算法算法基本思想基本思想：对每条直线段p1(x1, y1) p2(x2, y2)分三种情况处理：(1)直线段完全可见，“简取”之。wytywybwxrxwxl且, XYwxlwybwxrwyt窗口(a)窗口中的直线2022-3-1667(2)直线段完全不可见，“简弃”之。(3)直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。 wxlx 1wxlx 2且wxrx 2

26、wxrx 1且wyby 2wyby 1且wyty 2wyty 1且XYwxlwybwxrwyt窗口(a)窗口外的直线2022-3-1668编码编码：对于任一端点(x, y)，根据其坐标所在的区域，赋予一个4位的二进制码D3D2D1D0。编码规则如下： 若xwxr，则D1=1，否则D1=0； 若ywyt，则D3=1，否则D3=0。 0000窗口01000101100100011010011010000010图6-26 窗口及区域编码D3D2D1D02022-3-1669裁剪：裁剪：裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后：(1)若code1|code2=0，对直线段

27、应简取之。(2)若code1&code20，对直线段可简弃之。(3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。2022-3-1670 左、右边界交点的计算： ; x为wxl 或wxr窗口图6-25 实交点与虚交点ABCDEFHGIJ虚交点实交点实交点实交点虚交点虚交点)(11xxkyy 上、下边界交点的计算： ; y为wyb 或wytkyyxx11求交求交：假定直线的端点坐标为(x1,y1)和(x2,y2),1212xxyyk2022

28、-3-1671算法步骤算法步骤：(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，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。(4)确保p1在窗口外部：若p1在窗口内，则交换p1和p2的坐标值和编码。(5)按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p1的坐标值。也即在交点s处把线段一分

29、为二，并去掉p1s这一段。转(2)。(6)用直线扫描转换算法画出当前的直线段p1p2。(7)算法结束。 2022-3-1672例如例如： P1P2P3P4000001000101100100011010011010000010图6-27 直线段p1p2的编码裁剪2022-3-16732. 中点分割算法中点分割算法基本思想基本思想： 当对直线段不能简取(不满足code1|code2=0)也不能简弃(不满足code1&code20)时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。 2022-3-1674中点分割算法的核心思想是通过二分逼近来确定直

30、线段与窗口的交点。p1p2p3p4p5p6p72022-3-1675算法步骤：算法步骤：(1)输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。(2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。(3)若code1|code2=0，对直线段应简取之，保留当前直线段的端点坐标，转(5)；否则，若code1&code20，对直线段可简弃之，转(5)；当上述两条均不满足时，进行步骤(4)。(4)求出直线段的中点求出直线段的中点M，将将p1M、p2M入栈入栈。(5)当栈不空时，从栈中弹出一条直线段

31、，取为p1p2，转(2)进行处理。否则，继续(6)。(6)当栈为空时，合并保留的直线段端点当栈为空时，合并保留的直线段端点，得到窗口内的直线段p1p2。用直线扫描转换算法画出当前的直线段p1p2，算法结束。2022-3-1676重新构造算法步骤算法步骤：(1)若code1|code2=0，对直线段应简取之，结束；否则，若code1&code20，对直线段可简弃之，结束；当这两条均不满足时，进行步骤(2)。(2)找出该直线段离窗口边界最远的点和该直线段的中点。判中点判中点是否在窗口内是否在窗口内：若中点不在窗口内，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线

32、段求其中点；如中点在窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内相等，则该中点就是该线段落在窗口内的一个端点坐标。(3)如另一点在窗口内，则经(2)即确定了该线段在窗口内的部分。如另一点不在窗口内，则该点和所求出的在窗口上的那一点构成一条线段，重复步骤(2)，即可求出落在窗口内的另一点。2022-3-1677例如例如： 特点特点： 1.只进行加法和位移运算，便于硬件实现； 2. 适合于并行运算p1p2p3p4p5p6p72022-3-1678课后作业：课后作业：编程并上机实现习题六（习题六（p177）6.13 试用编码裁剪算法裁剪如图6-39所示

33、线段。6.14 试用中点分割算法裁剪如图6-39所示线段。XY20A(3,3)2窗口图6-39B(-1,-2)2022-3-16793. Liang-Barsky算法算法梁友栋和Barskey提出了更快的参数化裁剪算法。首先按参数化形式写出裁剪条件:)(121xxuxx)(121yyuyyYTyyuyYB)(121XRxxuxXL)(121这四个不等式可以表示为形式：upkqk (k=1, 2, 3, 4)其中，参数pk，qk定义为12xXRqxp2XLxq11xp1YByq13yp314yYTqyp410 u2022-3-1680Liang-Barsky算法的几何解释算法的几何解释：把直线与

34、窗口边界的实交点和虚交点分为两组：下限组以pk0为特征，表示该处直线从裁剪边界延长线的内部延伸到外部。有交情况下：下限组分布于直线段起点一侧，上限组分布于直线段终点一侧。下限组的最大值和上限组的最小值就分别对应于直线与窗下限组的最大值和上限组的最小值就分别对应于直线与窗口边界的实交点口边界的实交点。2022-3-1681任何平行于裁剪边界之一的直线 pk=0，其中k对应于裁剪边界（k=1,2,3,4对应于左、右、下、上边界）: 如果还满足qk0，则线段完全在边界外，舍弃该线段。 如果qk0，则该线段平行于裁剪边界并且在窗口内。当pk0,线段从裁剪边界延长线的内部延伸到外部。pk0时，可以计算出

35、线段与边界k的延长线的交点的u值： u=qk/pk12xXRqxp2XLxq11xp1YByq13yp314yYTqyp42022-3-1682(a)直线段与窗口边界wxl和wxr平行的情况(b)直线段与窗口边界wyb和wyt平行的情况wytwybwxlwxrwxrwxlwybwytA AB BC CD DE EF FG GH HI IJ JK KL Lpk=0，qk0: A, F, L, Gpk=0，qk0: B, C, D, E, H, I, J, K特殊情况：2022-3-1683对于每条直线，可以计算出参数umax和umin，它们定义了在裁剪矩形内的线段部分：一般情况： umax的值由

36、线段从外到内遇到的矩形边界所决定(p0)。对这些边界计算rk=qk/pk。umin取1和各个rk值之中的最小值。如果umaxumin，则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数u的两个值umax,umin计算出来。2022-3-1684Liang-Barsky算法算法步骤步骤：(1) 输入直线段的两端点坐标：(x1,y1)和(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。(2) 若x=0，则p1=p2=0。此时进一步判断是否满足q10或q20，若满足，则该直线段不在窗口内，算法转(7)。否则，满足q10且q2 0，则进一步计算计算umax和和umin。算法转

37、(5)。(3) 若y=0，则p3=p4=0。此时进一步判断是否满足q30或q40，若满足，则该直线段不在窗口内，算法转(7)。否则，满足q30且q40，则进一步计算计算umax和和umin。算法转(5)。(4) 若上述两条均不满足，则有pk0（k=1,2,3,4）。此时计算计算umax和和umin。(5) 求得umax和umin后，进行判断：若umaxumin，则直线段在窗口外，算法转(7)。若umax umin，利用直线的参数方程求得直线段在窗口内的两端点坐标。(6) 利用直线的扫描转换算法绘制在窗口内的直线段。(7) 算法结束。2022-3-16856.5.3 多边形的裁剪多边形的裁剪问题

38、的提出： (a)裁剪前(b)直接采用直线段裁剪的结果(c)正确的裁剪结果2022-3-16861. Sutherland-Hodgeman多边形裁剪多边形裁剪基本思想基本思想: : 逐边裁剪算法逐边裁剪算法输入：ABCDEFGHABCDEFGH输出：A12DEFGH12(a)用左边界裁剪输出：A134D56FGHADEFGH输入：A12DEFGH12(b)用下边界裁剪34562022-3-1687输入：A134D56FGHADFGH1(c)用右边界裁剪3456输出：A134D5678GH78ADGH1(d)用上边界裁剪345678输入：A134D5678GH输出：K34D56789IHJ9IJK2022-3-1688Sutherland-Hodgeman算法原理算法原理： 为窗口各