計(jì)算機(jī)圖形學(xué)(裁剪III).ppt

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

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

2、1”，令t1=min(t1’，t1”，1)，則t1就是P0P1和兩條終邊的交點(diǎn)與P1三點(diǎn)中最靠近P0的點(diǎn)的參數(shù)。當(dāng)t1>t0時(shí)，參數(shù)t?[t0,t1]的線段就是P0P1的可見(jiàn)部分當(dāng)t10時(shí)，參數(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)//屬于終點(diǎn)邊參數(shù){t=q/d;if(t

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

6、andJ.Beck,Generalizedtwo-andthree-dimensionclipping,ComputersandGraphics,3(1),23-28,1978.82009-2010-2:CG:SCUEC線段上的點(diǎn)和多邊形的關(guān)系P(t)=(P2-P1)t+P10?t?1對(duì)于線段上任意一點(diǎn)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或其延長(zhǎng)線上。3)N?(P(t)-A)<0，則P(t)

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

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