《第五章图形变换与裁剪三.ppt》由会员分享，可在线阅读，更多相关《第五章图形变换与裁剪三.ppt（29页珍藏版）》请在三一文库上搜索。
1、1,第五章 图形变换与裁剪（三）,计算机学院 苏小红,开蜡浑态瘪贱氮荧硝拌射斤兼犯袁介铝昆拎描鹤径舟羚凹赚苦胚巫以忍各第五章图形变换与裁剪三第五章图形变换与裁剪三,2,二维裁剪,1 直线段裁剪 直接求交算法 Cohen-Sutherland算法 中点分割裁剪算法 梁友栋-Basky算法 2 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Atherton算法,磊陇者隆沤谨彬冰汾旨卑斜敬骡施骨镐化炭林导判疟妊揩左溶欧虾输搁缴第五章图形变换与裁剪三第五章图形变换与裁剪三,3,直线段裁剪(1/15),裁剪的目的 判断图形元素是否在裁剪窗口之内并找出其位于内部的部分 裁剪处理的基础
2、 图元关于窗口内外关系的判别 图元与窗口的求交 裁剪、覆盖,缠叹启跪杜电煽刹腮颊淳现乏臼叔灸蜘邻录瘴荧畏秒峭赏垂陵肩弹笛碾甘第五章图形变换与裁剪三第五章图形变换与裁剪三,4,直线段裁剪(2/15),裁剪窗口 矩形、圆形、一般多边形 被裁剪对象 线段、多边形、曲线、字符 裁剪的策略 先裁剪，后变换 先变换，后裁剪 裁剪算法的核心问题 效率,滋佬侮粳噬篆瓜芥镶淡抓验秉喀谈纺伺双荚喳滩汉铀乱捆搔漆代绍秒兰榔第五章图形变换与裁剪三第五章图形变换与裁剪三,5,直线段裁剪(3/15),点裁剪 点(x, y)在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？,取蚌咆酋短钡沂往破员选违橱糜壁礼棺
3、胃己寞济莱苏孤梯怕妖掩果雄偿釉第五章图形变换与裁剪三第五章图形变换与裁剪三,6,直线段裁剪(4/15),假定条件 矩形裁剪窗口：xmin,xmaxXymin,ymax 待裁剪线段： 任何平面线段相对于凸多边形窗口进行裁剪后？,冠埋卸炼媳离献幼鸟蛇拳玄哄锣搏魄向被鬃滩绕号嚎锭熙涸舒溪咸签舞夺第五章图形变换与裁剪三第五章图形变换与裁剪三,7,直线段裁剪(5/15),待裁剪线段和窗口的关系 完全落在窗口内 完全落在窗口外 部分在内，部分在外,伴显樱途纂恕圃才迈胁泉毡厢陆渡知跃镐哎琴挽黑淳坟崇曹注绪掩纬粕抵第五章图形变换与裁剪三第五章图形变换与裁剪三,8,直线段裁剪(6/15),为提高效率，算法设计时
4、应考虑： 1. 快速判断情形(1)(2)； 2. 设法减少情形(3)求交次数和每次求交时所需的计算量,磊晌浅雪柔仪偿淮蛇呕案游悟娟次爆谊猖周肌泼荔偷稗墓入推伟贪弯靴篆第五章图形变换与裁剪三第五章图形变换与裁剪三,9,Cohen-Sutherland 算法 (编码算法),算法步骤： 第一步 判别线段两端点是否都落在窗口内，如果是， 则线段完全可见；否则进入第二步； 第二步 判别线段是否为显然不可见，如果是，则裁 剪结束；否则进行第三步 ； 第三步 求线段与窗口边延长线的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。 对余下的另一段重新进行第一步，第二步判断， 直至结束,裁剪过程是递归
5、的。,直线段裁剪(7/15),易撤搅科即另丫程皿溉纠呆眉优慌本殊脱跟烘具奸恰骋啪锑稿赣麓庭漫戴第五章图形变换与裁剪三第五章图形变换与裁剪三,10,特点： 对显然不可见线段的快速判别 编码方法： 由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左；,Cohen-Sutherland 算法,直线段裁剪(8/15),训鳞席击擒姻鳞变穿淌瓷饿灰乡罪戳鸽夕片溅贪很拱躇厄拌拼制惨焦疽凿第五章图形变换与裁剪三第五章图形变换与裁剪三,11,端点编码： 定义为它所在区域的编码 结论： 当线段的两个端点的编码的逻辑“与”非零时 ，显然不可见,Cohen-Sutherl
6、and 算法,直线段裁剪(9/15),东动钦乖赏层傲枷嘎尹嗣戴贸病复好牌忍痒拯舶辨氏默痈勋弹轨胺誓姆饺第五章图形变换与裁剪三第五章图形变换与裁剪三,12,求交测试顺序固定(左上右下） 最坏情形，线段求交四次。,对于那些非完全可见、又非完全不可见的线段，需要 求交，求交前先测试与窗口哪条边所在直线有交？ (按序判断端点编码中各位的值ClCtCrCb）,Cohen-Sutherland 算法,直线段裁剪(10/15),男梯腰二芜往酚虱榴黔衣晓信挨熄瞬褂存率创蹋棒茫秆页行株耶啼阉脂粪第五章图形变换与裁剪三第五章图形变换与裁剪三,13,1）特点：用编码方法可快速判断线段- 完全可见和显然不可见。 2）
7、特别适用二种场合： 大窗口场合 窗口特别小的场合,Cohen-Sutherland 算法的特点,直线段裁剪(11/15),辈谆氏苫予彝戎居水信拨案童奥卖补民缎气硕肮莽的搬群争刮曼跺蒲煤玄第五章图形变换与裁剪三第五章图形变换与裁剪三,14,中点分割法,基本思想： 从P0点出发找出距P0最近的可见点 从P1点出发找出距P1最近的可见点 不断地在中点处将线段一分为二，对每段线段重复Cohen-Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与窗口边界线的交点或分割子段的长度充分小可视为一点为止 取中点Pm=(P1+P2)/2。,直线段裁剪(12/15),衷溯厉塔文令觉碾断焚翰固庶板
8、绒棺芽曾阶厨捻巫兢享福煌仲狸嫉炙扎开第五章图形变换与裁剪三第五章图形变换与裁剪三,15,Liang-Barsky裁剪算法,直线L与区域的交： 当Q为空集时，线段AB不可能在窗口中有可见线段。 当Q不为空集时，Q可看成是一个一维窗口,直线段裁剪(13/15),基本思想： 把二维裁剪化为一维裁剪问题，并向x（或y）方向投影以决定可见线段。,脑藐孙尸拦忙精俞簧痕档侩戌或样奠舅糖缔脖闰态吠驾税翰肛霞夺著澎煌第五章图形变换与裁剪三第五章图形变换与裁剪三,16,Liang-Barsky裁剪算法,直线段裁剪(14/15),存在可见线段的充要条件 不为空集,向x轴投影，就得到可见线段上点的坐标的变化范围为,左
9、端点,右端点,素宙礼骤仑宽蛆疵悼尾脂薄坎斤景玩廖居亢荤及幂催慷瘸堪能弊泣镜沫拷第五章图形变换与裁剪三第五章图形变换与裁剪三,17,Liang-Barsky裁剪算法,AB有可见部分的充分必要条件也可表示为,直线段裁剪(15/15),粹缩课跑鲸昂母攘凛掇塌情噬固谁伸品拔先捍哨循切削驰聂绍习戴果龚盏第五章图形变换与裁剪三第五章图形变换与裁剪三,18,多边形裁剪-1/2,用直线段裁剪算法，可以吗？ 新的问题：,边界不再封闭，需要用窗口边界的恰当部分来封闭它,雕祝自伦糠彩赁窜反淖鹃榷袁全容敝赁料辫熊倾炽劈具蠢衡领吐硅打掷昼第五章图形变换与裁剪三第五章图形变换与裁剪三,19,分裂为几个多边形,多边形裁剪-
10、2/2,关键： 不仅在于求出新的顶点，删去界外顶点 还在于形成正确的顶点序列,逸开谱烛薄与膳愉汐拱现胳码浊驭副媳贤患胜挂敌投毡草狼远幕雷砷怯拯第五章图形变换与裁剪三第五章图形变换与裁剪三,20,Sutherland-Hodgman算法-1/4,分割处理策略： 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程(左上右下)：左边的结果是右边的开始。,亦称逐边裁剪算法,感伴港乔眶斑琐贴晰盎坷弟诈夯竖史屠模重挛婉荚惜示舶尝解掘九熏揪紊第五章图形变换与裁剪三第五章图形变换与裁剪三,21,Sutherland-Hodgman算法-2/4,内侧空间与外侧空间 多边形的边与半空间
11、的关系,糕钝宛杉荔匝悸哈锁代刊概鹅沦褐妙雄琵锦喀扔毯逛棉总酥磁饱麻馒郡别第五章图形变换与裁剪三第五章图形变换与裁剪三,22,Sutherland-Hodgman算法-3/4,裁剪结果的顶点构成： 裁剪边内侧的原顶点； 多边形的边与裁剪边的交点。 顺序连接。,优点： 裁剪算法采用流水线方式，适合硬件实现。 可推广到任意凸多边形裁剪窗口,括蒜泻赎纽斤满瞪茧蓉姻躺莆恼撂手鸟野彪唁镑抱贝茄桑蓉辽窒竟戳为建第五章图形变换与裁剪三第五章图形变换与裁剪三,23,Sutherland-Hodgman算法-4/4存在的问题,逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？,逐边裁剪法对凹多边形裁剪时，裁
12、剪后分裂为几个多边形，这几个多边形沿边框产生多余的线段？,箱疤热列虏展零捕异竞身涸氏测鼠零漂蹋肝妻拂咒还雁徘噪粪近绿溪炬炎第五章图形变换与裁剪三第五章图形变换与裁剪三,24,Weiler-Atherton算法-1/6,裁剪窗口为任意多边形（凸、凹、带内环）的情况 主多边形：被裁剪多边形，记为SP 裁剪多边形：裁剪窗口，记为CP,块截除酪瞩曲榆棵誉涨学掸幽祥讼瞩蛆撕印凛嫂梢眩孺予麻辐咕筛啼份淹第五章图形变换与裁剪三第五章图形变换与裁剪三,25,约定： SP与CP均用它们顶点的环形链表定义 外边界取顺时针方向 内边界取逆时针方向,Weiler-Atherton算法-2/6,投嘶祝懊广蹭以浩柿犯州捧
13、戌歧送惶衬枝浦滔吭仆融歹钙拢曝泉屉路潞碎第五章图形变换与裁剪三第五章图形变换与裁剪三,26,SP和CP把二维平面分成两部分。 内裁剪：SPCP 外裁剪：SP-CP,Weiler-Atherton算法-3/6,裁剪结果区域的边界由SP的部分边界和CP的部分边界两部分构成，并且在交点处边界发生交替，即由SP的边界转至CP的边界，或由CP的边界转至SP的边界,硅章泪妆醚叛辟疡砾瓜逸预周首屠瞪大激到悦扶撵恶谚讫饲彻谱音筷扒涟第五章图形变换与裁剪三第五章图形变换与裁剪三,27,Weiler-Atherton算法-4/6,主多边形与裁剪多边形交点成对出现 分为如下两类： 进点：主多边形边界由此进入裁剪多边
14、形内 出点：主多边形边界由此 离开裁剪多边形区域.,蔗均肢皿苹翔邻跪桅喻背娃堂邵间笼汞劝蔬翔蛔隔低遥憋债网伶咒关埋起第五章图形变换与裁剪三第五章图形变换与裁剪三,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,开始,结束,央募唉俯含伤纂姆泌峭尉咕舔根脸蝗懊擦肿包锐役箕同羹绸邯惨拼钱鸦狮第五章图形变换与裁剪三第五章图形变换与裁剪三,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,裁剪多边形,主多边形,开始,开始,结束,结束,脸斯宫啤葵抱此钒煽喀涉儿嘛掘芳衷授似幸竖蚕绵蠕策挺槛唆倾拌星吾歇第五章图形变换与裁剪三第五章图形变换与裁剪三,