第5章图形变换与裁剪3.ppt

《第5章图形变换与裁剪3.ppt》由会员分享，可在线阅读，更多相关《第5章图形变换与裁剪3.ppt（29页珍藏版）》请在三一办公上搜索。

1、1,哈尔滨工业大学计算机学院苏小红,第五章 图形变换与裁剪,另活简喷秘道叠聚奢戚叮堰既铱铂辐菜隶撩突您绷饵篷氮草跃虑众孽按嗣第5章 图形变换与裁剪3第5章 图形变换与裁剪3,2,二维裁剪,1 直线段裁剪直接求交算法Cohen-Sutherland算法 中点分割裁剪算法 梁友栋-Basky算法2 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法,灼流持议览掣家外蕊粗沸豌曙膊抉皂瘫癸届解祟踏待绎窒诧可盼隋焊尼涝第5章 图形变换与裁剪3第5章 图形变换与裁剪3,3,直线段裁剪(1/15),裁剪的目的判断图形元素是否在裁剪窗口之内并找出其位于内部的部分裁剪处理的

2、基础图元关于窗口内外关系的判别图元与窗口的求交裁剪、覆盖,阑沫祸倦萌勇香沁壮阁熄兰社敦农发腊蕊落纽春禁虐它蒂航卵瘟叶迷侮呵第5章 图形变换与裁剪3第5章 图形变换与裁剪3,4,直线段裁剪(2/15),裁剪窗口矩形、圆形、一般多边形被裁剪对象线段、多边形、曲线、字符裁剪的策略先裁剪，后变换先变换，后裁剪裁剪算法的核心问题效率,看裔奄焙置乔衷酣厨柯尔史调袭川俩蛛惫猫铲衰腰疯挣艳沂椽吧欺器恤遏第5章 图形变换与裁剪3第5章 图形变换与裁剪3,5,直线段裁剪(3/15),点裁剪 点(x,y)在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？,拣汞闪贝奈缆量吏伙豢返拱哗蜂肯呕宽截拾苟靛廓季牟

3、废人卯农颧以独孝第5章 图形变换与裁剪3第5章 图形变换与裁剪3,6,直线段裁剪(4/15),假定条件矩形裁剪窗口：xmin,xmaxXymin,ymax待裁剪线段：任何平面线段相对于凸多边形窗口进行裁剪后？,障掳摹叁邮尸脆泵尊妓庚醉馅甜沫淀欲扁奸匡彬妻留简浅睁卿竖馁旷昏络第5章 图形变换与裁剪3第5章 图形变换与裁剪3,7,直线段裁剪(5/15),待裁剪线段和窗口的关系 完全落在窗口内完全落在窗口外部分在内，部分在外,跪哲宠腹拾窝吞臀脖馒恤契亢椎哈剂谤提甫优俊山畏绕谩弥娇锹讥鬼宵编第5章 图形变换与裁剪3第5章 图形变换与裁剪3,8,直线段裁剪(6/15),为提高效率，算法设计时应考虑：1.

4、快速判断情形(1)(2)；2.设法减少情形(3)求交次数和每次求交时所需的计算量,钳羊暇史羹顽蛰邮躁静契打玫嚎柠燃阎威篷尤允惋泉糙尉孙熙瘁柄恐甭谭第5章 图形变换与裁剪3第5章 图形变换与裁剪3,9,Cohen-Sutherland 算法(编码算法),算法步骤：第一步 判别线段两端点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步；第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步；第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，直至结束,裁剪过程是递归的。,直线段裁剪(7/15),仪

5、撵挺湖户澎焊弹首蔚面搬矫颈穴热助亮挽是涡还详揣渊党疙番宽履栓兜第5章 图形变换与裁剪3第5章 图形变换与裁剪3,10,特点：对显然不可见线段的快速判别编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；,Cohen-Sutherland 算法,直线段裁剪(8/15),揖押亢谷想裙景栖派司欠戌霜敬霍捡黎山事盼久根惹耿惋蚀雾盂末羌预傣第5章 图形变换与裁剪3第5章 图形变换与裁剪3,11,端点编码：定义为它所在区域的编码结论：当线段的两个端点的编码的逻辑“与”非零时，显然不可见,Cohen-Sutherland 算法,直线段裁剪(9/15),

6、卢呀须莉粤漫妈灾航虹涨腐峡睁交锑涧限侦韩驶候静瘦贼磁星沪脏奈研妮第5章 图形变换与裁剪3第5章 图形变换与裁剪3,12,求交测试顺序固定(左上右下）最坏情形，线段求交四次。,对于那些非完全可见、又非完全不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb）,Cohen-Sutherland 算法,直线段裁剪(10/15),苗邑鸥植拥值彬导依锰公池英凶细凭菇买戚梦犹荚疫禽占镭七誓珊绦聊垒第5章 图形变换与裁剪3第5章 图形变换与裁剪3,13,1）特点：用编码方法可快速判断线段-完全可见和显然不可见。2）特别适用二种场合：大窗口场合 窗口特别小

7、的场合,Cohen-Sutherland 算法的特点,直线段裁剪(11/15),斋众钻弓去吠协妖啤鹏莹懈焊重坚岔云洞仅妨和疑吱晃蛤庄哮凋间芥逸绪第5章 图形变换与裁剪3第5章 图形变换与裁剪3,14,中点分割法,基本思想：从P0点出发找出距P0最近的可见点从P1点出发找出距P1最近的可见点不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止取中点Pm=(P1+P2)/2。,直线段裁剪(12/15),瘦租篮投选顷显偷涟晌悬巫扫富正毕边哟笋灌瞥驼臭仟判郴枉朽悠蠢彼捡第5章 图

8、形变换与裁剪3第5章 图形变换与裁剪3,15,Liang-Barsky裁剪算法,直线L与区域的交：当Q为空集时，线段AB不可能在窗口中有可见线段。当Q不为空集时，Q可看成是一个一维窗口,直线段裁剪(13/15),基本思想：把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。,看会瓶豆约荡淄牧印符舱版祝筹茵航恨怔孙豁侦哇饭劳疮啊板硷酚淘估咖第5章 图形变换与裁剪3第5章 图形变换与裁剪3,16,Liang-Barsky裁剪算法,直线段裁剪(14/15),存在可见线段的充要条件 不为空集,向x轴投影，就得到可见线段上点的坐标的变化范围为,左端点,右端点,琢迫宗赊胁惹鼓徊窒舅条包杭盂扑

9、蜜戍霖尿淖缚举间声怜厦幻俯截滇微陈第5章 图形变换与裁剪3第5章 图形变换与裁剪3,17,Liang-Barsky裁剪算法,AB有可见部分的充分必要条件也可表示为,直线段裁剪(15/15),邦绽旁师棠备雅佩荣豌压辉将委垫曝肋嚷绩照您卉帅半作蛰柔硅牌浊闲正第5章 图形变换与裁剪3第5章 图形变换与裁剪3,18,多边形裁剪-1/2,用直线段裁剪算法，可以吗？新的问题：,边界不再封闭，需要用窗口边界的恰当部分来封闭它,蜘同恃抛整哲共面矛腿枣维训蓟熙瑟郁渠短拢中娟妆裸悦养腆侄节簧阜眩第5章 图形变换与裁剪3第5章 图形变换与裁剪3,19,分裂为几个多边形,多边形裁剪-2/2,关键：不仅在于求出新的顶点

10、，删去界外顶点还在于形成正确的顶点序列,恕突这霜祖古迫试竖非爽郊吐棍添殉哈越致版绵啃殿砒召彪燕手仕谱羚勘第5章 图形变换与裁剪3第5章 图形变换与裁剪3,20,Sutherland-Hodgman算法-1/4,分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：左边的结果是右边的开始。,亦称逐边裁剪算法,斤土切疲输疗奎缔乌磕测俊彰收发绣士庐莲雌享糊琳蚜论守沂棕洛蓝癣逸第5章 图形变换与裁剪3第5章 图形变换与裁剪3,21,Sutherland-Hodgman算法-2/4,内侧空间与外侧空间多边形的边与半空间的关系,汝逝指人悲摧道胸式疤独喻湘秃

11、魂划诬怪幕诉哼捷架载银杏摩没枣却牧逗第5章 图形变换与裁剪3第5章 图形变换与裁剪3,22,Sutherland-Hodgman算法-3/4,裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点。顺序连接。,优点：裁剪算法采用流水线方式，适合硬件实现。可推广到任意凸多边形裁剪窗口,欲有撤材攘废椎犬携缆宙摄尔赎释跌莽温稳能沂园引秽低棵枕籍讲粳羌坍第5章 图形变换与裁剪3第5章 图形变换与裁剪3,23,Sutherland-Hodgman算法-4/4存在的问题,逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？,逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，这几个多边形沿边

12、框产生多余的线段？,栅翟穆墙炙政皖饿芯撰悉局嚼裳仙讳汲篇她乐板涯袜叙惠苇喂丽首共抬囊第5章 图形变换与裁剪3第5章 图形变换与裁剪3,24,Weiler-Atherton算法-1/6,裁剪窗口为任意多边形（凸、凹、带内环）的情况主多边形：被裁剪多边形，记为SP 裁剪多边形：裁剪窗口，记为CP,饭左鹿壳砷难型寻她食酬纵挖敝才闭烷众桌夫除贪检捡讲临裳踩壕否鬼焦第5章 图形变换与裁剪3第5章 图形变换与裁剪3,25,约定：SP与CP均用它们顶点的环形链表定义外边界取顺时针方向内边界取逆时针方向,Weiler-Atherton算法-2/6,兜苏害癸由触服艳年汞拾证陷联畏漾缚秆坠嵌厉箍堵瓦椭戍崖瑶罐污痊

13、尺第5章 图形变换与裁剪3第5章 图形变换与裁剪3,26,SP和CP把二维平面分成两部分。内裁剪：SPCP外裁剪：SP-CP,Weiler-Atherton算法-3/6,裁剪结果区域的边界由SP的部分边界和CP的部分边界两部分构成，并且在交点处边界发生交替，即由SP的边界转至CP的边界，或由CP的边界转至SP的边界,凿挺琵皋宁欠疗敲啪痴蕉叶筋虽梭脐众炽验形愧瞅义伐单桃占监研题晃周第5章 图形变换与裁剪3第5章 图形变换与裁剪3,27,Weiler-Atherton算法-4/6,主多边形与裁剪多边形交点成对出现分为如下两类：进点：主多边形边界由此进入裁剪多边形内 出点：主多边形边界由此 离开裁剪

14、多边形区域.,贴夕牡犊想椽岔均槐阁账沾淘结独晒商聊肮浆艾叙葵舅辗痞翘己爸近游凳第5章 图形变换与裁剪3第5章 图形变换与裁剪3,28,Weiler-Atherton算法-5/6,主多边形表,裁剪多边形表,S1,S2,I1,S3,S4,S5,S6,I2,I3,I4,I5,I6,I7,I8,C1,C2,I3,I4,C4,I8,I1,I2,I5,C3,I5,I6,S1,I7,C1,开始,结束,恶沦峻预血翼扫戌敷网现时当舅悦褂置擞描躇家赶刃渗钨稀偷首芳鲁商刺第5章 图形变换与裁剪3第5章 图形变换与裁剪3,29,Weiler-Atherton算法-6/6,主多边形表,裁剪多边形表,S1,S2,I1,I4,S4,S6,I5,I2,I3,S3,S1,S5,S7,I6,S8,I7,I8,S5,C1,C2,C3,C4,I4,I5,I1,I8,C1,C5,C5,C6,I2,I3,I6,C7,C8,I7,算法裁剪后所生成的多边形为I1I2I7I8I1和I3I4I5I6I3,裁剪多边形,主多边形,开始,开始,结束,结束,惺寻喜酪吮隔综液袋动绪租琉绪诚牺敖懈癸办破质铝昔佩柬介鄂陋往疚卤第5章 图形变换与裁剪3第5章 图形变换与裁剪3,