北航計算機圖形學(xué)9

1、二維圖形的運算二維圖形的運算基本運算基本運算1.交點計算 1.1兩直線段的交點設(shè)兩條直線段。和21SS4443332222,yxPyxPSyxP和的兩個端點為；和則兩條直線段的參數(shù)方程為：1111, yxPS的兩個端點為 101101432211vvPPvvSuuPPuuS上述方程可以寫成：10:10:34334321211211vvyyyyvxxxxSuuyyyyuxxxxS 如果兩條直線相交，則滿足vyyyuyyyvxxxuxxx343121343121即134312134312yyvyyuyyxxvxxuxx解得：當(dāng)43124312131213124312431243134313yyyy

2、xxxxyyyyxxxxvyyyyxxxxyyyyxxxxu043124312yyyyxxxx時，有(1)=0 方程組無解。說明兩條直線段所在直線相互平行或重合，所以不相交，沒有交點產(chǎn)生。(2)0 方程組有唯一解。如果0u 1則說明交點P位于線段S1上。否則，交點P位于線段S1延長線上。 如果0v1則說明交點P位于線段S2上。否則，交點P位于線段S2延長線上。 所以，只有當(dāng)0u1和0v1同時成立時，交點P既位于線段S1上又位于線段S2上。1.2直線與圓弧的交點設(shè)直線AB的方程為) 10 ()()(ttyyyytxxxxabaaba圓心為C(xc,yc)半徑為R的圓弧的參數(shù)方程為角和終止角。分別

3、表示圓弧的起始和esesccRyyRxx)(sincos如果直線段和圓弧相交，則有：222)()(Rtyyytxxxabaaba將上式展開可得02CBtAt式中A,B,C均可由已知點的坐標(biāo)求得當(dāng)=B2-4AC 0時，直線和圓弧不相交。當(dāng)=B2-4AC0時，前面的一元二次方程有兩個不相等的實根t1和t2。當(dāng)滿足0 t1 1或0 t21時，直線段才有可能與圓弧相交。此時可以通過來計算RtyyyyRtxxxxabcaabca)(sin)(cos當(dāng)求得的滿足s e時，直線段才與圓弧相交。2.關(guān)系判斷關(guān)系判斷1.1.點的包含性檢驗 點的包含性檢驗是指：判斷一個點是否被包含在某一個區(qū)域內(nèi)。區(qū)域通常是多邊形

4、。通常有兩種方法：（1）夾角和檢驗法（2）交點數(shù)檢驗法l夾角和檢驗法 （a）被測點p在多邊形外 （b）被測點p在多邊形內(nèi)BPABCDEACDEa1a2a3a4a5Pa1a2a3a4a5點與多邊形的包含性檢測點與多邊形的包含性檢測l射線法l由被測點P處向 y = - 方向作射線l交點個數(shù)是奇數(shù)，則被測點在多邊形內(nèi)部l否則，偶數(shù)，在多邊形外部。PPP1P2P3P1P2l若射線正好經(jīng)過多邊形的頂點，當(dāng)共享頂點的兩邊在射線的同一側(cè)，則交點計數(shù)加2，否則加1。1.2多邊形重疊性檢驗其思想是用包含多邊形的最小矩形來檢測。3.窗口運算窗口運算1.1.定義窗口和視區(qū)1.2.窗口視區(qū)轉(zhuǎn)換假設(shè)在用戶坐標(biāo)系xoy中

5、定義一個窗口，其左下角坐標(biāo)為(xl,yb)，右上角坐標(biāo)為(xr,yt)；在設(shè)備坐標(biāo)系x*o*y*中定義一個窗口，其左下角坐標(biāo)為(xl*,yb*)，右上角坐標(biāo)為(xr*,yt*)；則有：xyoxlxrybytpx*y*o*xl*xr*yb*yt*p*btbtblrlryyyyyyyyxxxxxxxxbll*從窗口到視口的轉(zhuǎn)換從窗口到視口的轉(zhuǎn)換WYTWXRWYBWXLVYTVXRVYBVXLvyvxwywxDCyyBAxxwvwvWYBCVYBDWYBWYTVYBVYTCWXLAVXLBWXLWXRVXLVXRA1.直線的生成算法1.1.逐點比較法（1）算法流程開始偏差判別畫筆作圖終點判斷結(jié)束偏差

6、計算是否算法說明：偏差判別：按偏差來判斷畫筆的當(dāng)前位置與規(guī)定圖形的位置的偏差符號，以確定畫筆下一步方向。畫筆作圖：給出x向或y向的走步信號，使畫筆在該方向上移動一個步距。終點判斷：判斷當(dāng)前畫筆是否到終點。偏差計算：在新位置上計算作圖偏差，作為偏差判別的依據(jù)。如果把直線的起點設(shè)置在坐標(biāo)原點，則規(guī)定直線處于4個不同的象限中時，畫筆的走向如圖所示。（2）偏差計算一般公式設(shè)直線的終點為A(xa,ya),當(dāng)前位置為M (xm,ym)。oA，oM與x軸的夾角分別為和。則偏差為amamamaammxxyxxyxyxytantan由于上述公式的分母在所有的象限為正，故偏差判別式可簡化為 Fm=ymxa-xmy

7、a第一象限為例當(dāng)0時，表示畫筆在oA線的下方，應(yīng)該走+y一步；當(dāng)0，表示畫筆在oA線上或上方，此時則應(yīng)該走+x一步。 簡化公式當(dāng)Fm0時，應(yīng)該走+y一步，即xm+1=xm，ym+1=ym1。則 Fm1 ym1xa-yaxm+1= Fm+xa當(dāng)Fm 0時，應(yīng)該走+x一步，即xm+1=xm+1，ym+1=ym。則 Fm1 ym1xa-yaxm+1= Fm-ya 起始時，設(shè)F1=0，即假設(shè)畫筆在直線段的起點。其它象限中的偏差計算公式第二象限當(dāng)Fm0時，應(yīng)該走-x一步，即xm+1=xm-1，ym+1=ym。則 Fm1 ym1xa-yaxm+1= Fm+ya = Fm+|ya| 當(dāng)Fm 0時，應(yīng)該走+y

8、一步，即xm+1=xm，ym+1=ym+1。則 Fm1 ym1xa-yaxm+1= Fm+xa= Fm-| xa |三、四象限是類似的。 終點判斷設(shè)繪圖機的步長為t，直線段在x,y兩個方向上的增量分別為x和y，則繪圖筆從直線的起點走到直線的終點，在x方向應(yīng)走x/t步，在y方向應(yīng)走y/t步。兩個方向上的總步數(shù)為(x/t+y/t)。l直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換: 確定最佳逼近于該直線的一組象素，并且按掃描線順序，將這些象素存入到幀緩存的相應(yīng)單元中。l三個常用算法：數(shù)值微分法（DDA）中點畫線法Bresenham算法。數(shù)值微分?jǐn)?shù)值微分(DDA)法法l 基本思想 已知過端點 的直線段L： 直線斜率為

9、 從 的左端點 開始，向 右端點步進。步長=1(個象素)，計算相應(yīng)的y坐標(biāo) ；取象素點(x, round(y)作為當(dāng)前點的坐標(biāo)。0101xxyyk),(),(111000yxPyxPbkxyx0 xxbkxy計算當(dāng) 時;即：當(dāng)x每遞增1，y遞增k(即直線斜率)； xkyxkbkxbkxyiiii 111xkyyii1例：畫直線段x int(y+0.5) y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：網(wǎng)格點表示象素0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2 , 5()0 , 0(10PPvoid

10、DDALine(int x0,int y0,int x1,int y1,int color) int x；float dx, dy, y, k;dx, = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; 注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每增加1, y最多增加1。當(dāng) k 1時，必須把x，y地位互換 k 1 示意圖0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)l過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起

11、點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后根據(jù)誤差項的符號確定該列象素中與此交點最近的象素。dddd Bresenham算法算法設(shè)直線方程為： ，其中k=dy/dx。 因為直線的起始點在象素中心，所以誤差項d的初值d00。X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。一旦d1，就把它減去1，這樣保證d在0、1之間。l當(dāng)d0.5時，最接近于當(dāng)前象素的右上方象素（ ）l而當(dāng)d0.5時，更接近于右方象素（ ）。為方便計算，令ed-0.5，e的初值為-0.5，增量為k。l當(dāng)e0時，取當(dāng)前象素（xi，yi）的右上方象素（ ）；l而當(dāng)e0時，更接近于右方象素（ ）。kyxxkyyiiiii

12、)(1111,iiyxiiyx,111,iiyxiiyx,1void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; 2.圓弧的生成算法圓弧的生成算法 2.1逐點比較法用逐點比較法生成圓弧是在繪圖筆每走完一步，就要把繪

13、圖筆當(dāng)前的位置距圓心的距離與半徑進行比較，根據(jù)比較結(jié)果決定下一步的走向。這種方法是用階梯折線來逼近圓弧。如圖所示：xyO由于畫圓的方向有順時針和逆時針兩種，所以討論圓弧的生成算法時，要分成順時針和逆時針及4個象限8種情況。xyOxyO 1)偏差計算(1)一般公式設(shè)圓弧的起點為A(xa,ya)，終點為B(xb,yb)，圓心在原點。則圓弧的半徑為R=(xa2+ya2)1/2設(shè)畫筆的當(dāng)前位置為M(xm,ym)，則畫筆至圓心的距離為Rm=(xm2+ym2)1/2記 Fm Rm2 -Ra2 =(xm2+ym2)-(xa2+ya2)以第一象限為例，當(dāng)Fm0時，即畫筆在圓外或圓上，此時應(yīng)向x走步；當(dāng)Fm 0時，即畫筆在圓內(nèi)，此時應(yīng)向y走步； (2)簡化公式當(dāng)Fm0時，此時應(yīng)向x走步，則xm+1=xm-1，ym+1=ym,從而 Fm1(xm+12+ym+12)-(xa2+ya2) (xm2-2xm+ 1+ ym2)-(xa2+ya2) Fm-2xm+ 1當(dāng)Fm 0時，此時應(yīng)向y走步，則xm+1=xm，ym+1=ym 1,從而Fm1(xm+12+ym+12)-(xa2+ya2) (xm2+ ym2 2ym+ 1)-(xa2+ya2) Fm+2ym+ 1 2)公式的推廣以逆圓第三