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

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

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

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

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

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

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

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

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

9、 從 的左端點(diǎn) 開(kāi)始，向 右端點(diǎn)步進(jìn)。步長(zhǎng)=1(個(gè)象素)，計(jì)算相應(yīng)的y坐標(biāo) ；取象素點(diǎn)(x, round(y)作為當(dāng)前點(diǎn)的坐標(biāo)。0101xxyyk),(),(111000yxPyxPbkxyx0 xxbkxy計(jì)算當(dāng) 時(shí);即：當(dāng)x每遞增1，y遞增k(即直線斜率)； xkyxkbkxbkxyiiii 111xkyyii1例：畫(huà)直線段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)格點(diǎn)表示象素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時(shí)，必須把x，y地位互換 k 1 示意圖0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)l過(guò)各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起

11、點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號(hào)確定該列象素中與此交點(diǎn)最近的象素。dddd Bresenham算法算法設(shè)直線方程為： ，其中k=dy/dx。 因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng)d的初值d00。X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。一旦d1，就把它減去1，這樣保證d在0、1之間。l當(dāng)d0.5時(shí)，最接近于當(dāng)前象素的右上方象素（ ）l而當(dāng)d0.5時(shí)，更接近于右方象素（ ）。為方便計(jì)算，令ed-0.5，e的初值為-0.5，增量為k。l當(dāng)e0時(shí)，取當(dāng)前象素（xi，yi）的右上方象素（ ）；l而當(dāng)e0時(shí)，更接近于右方象素（ ）。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逐點(diǎn)比較法用逐點(diǎn)比較法生成圓弧是在繪圖筆每走完一步，就要把繪

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