計算機圖形學(裁剪III).ppt

《計算機圖形學(裁剪III).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、第4章變換和裁剪直線P0P1的參數(shù)方程對于直線上一點(x,y),若它在窗口內(nèi)則有梁友棟-Barsky算法BLP0P1RTxLxRyByTxy22009-2010-2:CG:SCUEC令則有由梁友棟-Barsky算法32009-2010-2:CG:SCUEC梁友棟-Barsky算法由42009-2010-2:CG:SCUEC設P0P1和兩條始邊的交點參數(shù)為t0’，t0”，令t0=max(t0’，t0”，0)，則t0就是P0P1和兩條始邊的交點與P0三點中最靠近P1的點的參數(shù)。設P0P1和兩條終邊的交點參數(shù)為t1’，t

2、1”，令t1=min(t1’，t1”，1)，則t1就是P0P1和兩條終邊的交點與P1三點中最靠近P0的點的參數(shù)。當t1>t0時，參數(shù)t?[t0,t1]的線段就是P0P1的可見部分當t10時，參數(shù)t用于更新t1。如果更新了t0或t1后，使

3、t0>t1，則舍棄該線段。否則畫出以t0和t1為參數(shù)的線段梁友棟-Barsky算法的基本步驟62009-2010-2:CG:SCUEC梁友棟-Barsky算法doublet0=0,t1=1;doublexL,xR,yB,yT;boolvisible;voidLiang_Barsky(doublex[2],doubley[2]){doubledx,dy;visible=false;dx=x[1]-x[0];dy=y[1]-y[0];if(clipt(-dx,x[0]-xL))if(clipt(dx,xR-x[0]))

4、if(clipt(-dy,y[0]-yB))if(clipt(dy,yT-y[0]))visible=true;if(visible)drawline(P0+(P1-P0)t0,P0+(P1-P0)t1);}Booclipt(doubleq,doubled){doublet;if(q<0)//屬于起始邊參數(shù){t=q/d;if(t>t1)returnfalse;elseif(t>t0)t0=t;}elseif(q>0)//屬于終點邊參數(shù){t=q/d;if(t

5、=t;}elseif(d<0)returnfalse;returntrue;}梁-Barsky算法演示例子72009-2010-2:CG:SCUECCyrus-Beck裁剪算法（參數(shù)化裁剪算法）考慮如圖所示一個凸多邊形區(qū)域R和一條線段P1P2，要求計算線段落在區(qū)域R中的部分。假定A是區(qū)域R邊界L上一點。N是區(qū)域邊界在A點的內(nèi)法向量。線段P1P2用參數(shù)方程表示：P(t)=(P2-P1)t+P10?t?1P1P2ANR圖示稱直線上某點在某邊界的內(nèi)側(cè)，如果該點和多邊形區(qū)域內(nèi)任一點都在該邊界的同一側(cè)。Ref:M.Cyrus

6、andJ.Beck,Generalizedtwo-andthree-dimensionclipping,ComputersandGraphics,3(1),23-28,1978.82009-2010-2:CG:SCUEC線段上的點和多邊形的關(guān)系P(t)=(P2-P1)t+P10?t?1對于線段上任意一點P(t)，P(t)和多邊形邊界L的關(guān)系有三種可能（此處t為一定值）：1)N?(P(t)-A)>0，則P(t)在L內(nèi)側(cè)。2)N?(P(t)-A)=0，則P(t)在L或其延長線上。3)N?(P(t)-A)<0，則P(t)

7、在L外側(cè)。凸多邊形裁剪區(qū)域性質(zhì)1性質(zhì)1表明，P(t)在凸多邊形內(nèi)的充要條件是，對于凸多邊形邊界上任意一點A和該處內(nèi)法向量N，都有N?(P(t)-A)?0。92009-2010-2:CG:SCUEC現(xiàn)假設多邊形有k條邊，在每條邊界Li上取1個點Ai，該點處的內(nèi)法向量Ni（i=1,2,…,k），則可見線段的參數(shù)區(qū)間為下列不等式組的解i=1,2,…,k解的最小值ts和最大值te分別對應于可見線段的端點。把式P(t)=(P2-P1)t+P1代入上式，整理得當Ni?(P2-P1)??0，由上式可求得t?ti，當Ni?(P2-

8、P1)>0t?ti，當Ni?(P2-P1)<0i=1,2,…,k而是線段與第i條邊界（或延長線）的交點參數(shù)。Cyrus-Beck算法102009-2010-2:CG:SCUEC解的幾何意義：Ni?(P2-P1)把ti分為兩組：起點組和終點組。解的幾何意義終點組起點組P2P1終點組以Ni?(P2-P1)<0為特征，表示在該處沿P1P2方向前進進入多邊形外側(cè)。起