計(jì)算機(jī)圖形學(xué)——Liang-Barsky

1、Liang-Barsky 裁剪算法裁剪算法Contents算法思想算法思想 例題演示例題演示Contents 1Contents 2算法思想算法思想一條兩端點(diǎn)為一條兩端點(diǎn)為P1(x0,y0)、P2(x1,y1)的線段用的線段用參數(shù)方程參數(shù)方程表示為：表示為：x=x0+u(x1-x0)=x0+uxy=y0+u(y1-y0)=y0+uy；其中，；其中，0u 1線段的參數(shù)方程與點(diǎn)裁剪條件結(jié)合，得到不等式線段的參數(shù)方程與點(diǎn)裁剪條件結(jié)合，得到不等式 xminx0+uxxmax yminy0+uyymax算法思想算法思想用用upKqK(k=1,2,3,4)表示上式，則參數(shù)表示上式，則參數(shù)p、q定義為：定義

2、為：p1=-x, q1=x0-xminp2=x, q2=xmax-x0p3=-y, q3=y0-yminp4=y, q4=ymax-y0算法思想算法思想根據(jù)根據(jù)pk的值判斷線段的方向：的值判斷線段的方向： pk=0 線段線段平行平行于裁剪邊界于裁剪邊界qk0 線段完全位于線段完全位于邊界外邊界外qk0 線段位于平行線段位于平行邊界內(nèi)邊界內(nèi) pk0 反之反之算法思想算法思想pk0時(shí)，計(jì)算線段與邊界時(shí)，計(jì)算線段與邊界k延長線的交點(diǎn)延長線的交點(diǎn)u值：值：對每條直線，計(jì)算對每條直線，計(jì)算u1和和u2。kkpqu 算法思想算法思想u1-線段從外到內(nèi)遇到的矩形邊界決定（線段從外到內(nèi)遇到的矩形邊界決定（p0

3、）計(jì)算計(jì)算rk=qk/pku2=minr，1算法思想算法思想若若u1u2，線段完全在裁剪，線段完全在裁剪窗口外窗口外；否則，由參數(shù)否則，由參數(shù)u1和和u2計(jì)算計(jì)算出裁剪后的線段端點(diǎn)出裁剪后的線段端點(diǎn)例題演示例題演示F1(1,-2)F2(6,3)(8,4)(0,0)yxStep1： 寫出參數(shù)方程，計(jì)算寫出參數(shù)方程，計(jì)算x和和y。 x=x0+ux y=y0+uy x=5 y=5例題演示例題演示Step2：計(jì)算：計(jì)算pk、qk和和rk的值，并確定的值，并確定u1、u2的值。的值。p1=-x=-5, q1=x0-xmin=1， r1=q1/p1=-1/5p2=x=5, q2=xmax-x0=7， r2

4、=q2/p2=7/5p3=-y=-5, q3=y0-ymin=-2， r3=q3/p3=2/5p4=y=5, q4=ymax-y0=6， r4=q4/p4=6/5例題演示例題演示 將上面的計(jì)算列入表格：將上面的計(jì)算列入表格： 故：故： u1=max0,-1/5,2/5=2/5 u2=min1,7/5,6/5=1EdgepkqkrkLeft-51-1/5Right577/5Bottom-5-22/5Top566/5例題演示例題演示Step3：判斷直線與裁剪窗口的關(guān)系。：判斷直線與裁剪窗口的關(guān)系。u1=2/5, u2=1 由于由于u1u2，則有，則有xA=x0+u1x=3; yA=y0+u1y=0 xB=6; yB=3 故，線段故，線段F1F2中（中（