計算機圖形學——Liang-Barsky

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

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

3、）計算計算rk=qk/pku2=minr，1算法思想算法思想若若u1u2，線段完全在裁剪，線段完全在裁剪窗口外窗口外；否則，由參數否則，由參數u1和和u2計算計算出裁剪后的線段端點出裁剪后的線段端點例題演示例題演示F1(1,-2)F2(6,3)(8,4)(0,0)yxStep1： 寫出參數方程，計算寫出參數方程，計算x和和y。 x=x0+ux y=y0+uy x=5 y=5例題演示例題演示Step2：計算：計算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例題演示例題演示 將上面的計算列入表格：將上面的計算列入表格： 故：故： u1=max0,-1/5,2/5=2/5 u2=min1,7/5,6/5=1EdgepkqkrkLeft-51-1/5Right577/5Bottom-5-22/5Top566/5例題演示例題演示Step3：判斷直線與裁剪窗口的關系。：判斷直線與裁剪窗口的關系。u1=2/5, u2=1 由于由于u1u2，則有，則有xA=x0+u1x=3; yA=y0+u1y=0 xB=6; yB=3 故，線段故，線段F1F2中（中（