直线段裁剪算法.ppt

《直线段裁剪算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、直线段裁剪的Liang--Barsky算法线段裁剪的意义Liang-Barsky算法0问题的提出线段裁剪就是将指定窗口作为图形边界，将窗口内的线段保留，而窗口外的线段则被舍弃。1.线段裁剪的意义BeforeclippingAfterclipping裁剪处理涉及：（1）线段在窗口内外的判别；（2）线段与窗口的求交。2.Liang--Barsky算法（1）算法背景经典算法---写入图形学教科书的唯一中国人算法Sutherland梁友栋苏步青Barsky梁友栋的贡献：––Liang-Barsky算法––几何连续理论––CommunicationofACM论

2、文(83’)1935年7月出生,福建福州人.1956年毕业于复旦大学数学系,1960年复旦大学数学系研究生毕业1960年分配到浙江大学数学系任教,1979年至1981年在美国Utah大学计算机系作访问学者获国家教委科技进步一等奖,1987获国家自然科学三等奖,199160s’Cohen-Sutherland的编码方法:CohenSutherland00001000110000100100011010010001001178年Cyrus和Beck的参数化方法---更有效的算法:84年梁友栋和Barsky提出了更快的参数化线段裁剪算法。（2）算法思想Li

3、ang-Barsky算法的几何含义：入边、出边和端点u2u1xminxmaxyminymaxParameterizedlinesegment:x=x1+u(x2–x1)=x1+uDxy=y1+u(y2–y1)=y1+uDy0u1Ifapointonthelineisinsidetheclippingwindow,then:xminx1+uDxxmaxyminy1+uDyymaxu2u1xminxmaxyminymaxxminx1+uDx=>(–Dx)ux1–xminWerewritetheinequalitiesintheformup

4、kqkLeftBorder,k=1:pk=–Dx,qk=x1–xminRightBorder,k=2:pk=Dx,qk=xmax–x1BottomBorder,k=3:pk=–Dy,qk=y1–yminTopBorder,k=4:pk=Dy,qk=ymax–y1x1+uDxxmax=>(Dx)uxmax–x1yminy1+uDy=>(–Dy)uy1–yminy1+uDyymax=>(Dy)uymax–y1u2u1Case1:pk0Ifpk<0,thentheextensionofthelinesegmentgoesfromoutsid

5、etoinsidetheextendedboundary(whenmovingindirectionofincreasingu).Ifpk>0,thentheextensionofthelinesegmentgoesfrominsidetooutside.Theorderofgoingfrominsidetooutsideandoutsidetoinsidetheboundariesindicateswhetherweneedtoclip.Todeterminethis,wesolveforufortheintersectionofthelinewi

6、theachoftheextendedboundaries:uk=qk/pk(x1,y1)(x2,y2)u1u2u1

7、.ifqk≥0，thelineisinsidetheboundaryandfurtherconsideration.ymax(x1,y1)(x2,y2)Ifx2=x1thenp1andp2arezero.q2=xmax–x1<0Discardline.（3）TheLiang-BarskyAlgorithm1Ifpk=0andqk<0foranyk,discardthelineandstop.Otherwiseproceedtothenextstep.2Forallksuchthatpk<0,calculaterk=qk/pk.Letu1=max{rk

8、,0}.3Forallksuchthatpk>0,calculaterk=qk/pk.Letu2=min{r