計(jì)算機(jī)圖形學(xué)-第3章-直線與圓

第3章二維圖形生成算法3.1直線圖形

對(duì)直線進(jìn)行光柵化時(shí)，只能在顯示器所給定的有限個(gè)像素中，確定最佳逼近于該直線的一組像素。用寫(xiě)點(diǎn)方式對(duì)像素進(jìn)行寫(xiě)操作，這就是通常所說(shuō)的用顯示器繪制直線，或直線的掃描轉(zhuǎn)換（如圖3-1所示）。圖3-1直線的掃描轉(zhuǎn)換示意圖3.1.1數(shù)值微分法數(shù)值微分法DDA（DigitalDifferentalAnalyzer）的本質(zhì)，是用數(shù)值方法解微分方程，即通過(guò)同時(shí)對(duì)x和y各增加一個(gè)小增量，計(jì)算下一步的x、y值。1．DDA法的公式推導(dǎo)設(shè)直線的起點(diǎn)為(x0，y0)，終點(diǎn)為(x1，y1)，直線的斜率為：

k=△y/△x△x＝x1-x0，△y＝y(tǒng)1-y0。設(shè)△x>△y>0，x從起點(diǎn)到終點(diǎn)變化，每步遞增1個(gè)像素，計(jì)算對(duì)應(yīng)的y坐標(biāo)，

y＝kx+b，這種方法直觀可行，然而效率較低。每步運(yùn)算都需一個(gè)浮點(diǎn)乘法與一個(gè)加法運(yùn)算。可簡(jiǎn)化：

yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k=yi+k直線掃描轉(zhuǎn)換的數(shù)值微分算法：k=(y1-y0)/(x1-x0)，x0=x0，y0=y0xi+1=xi+1，yi+1=yi+k，（i=0，1，2，…，x1－x0）當(dāng)0<△x<△y時(shí)，每步y(tǒng)遞增1個(gè)像素(yi+1=yi+1)，需計(jì)算對(duì)應(yīng)的x坐標(biāo)：xi+1=yi+1/k－b/k=(yi+1)/k-b/k=yi/k－b/k+1/k=yi+1/k圖3-2DDA直線掃描轉(zhuǎn)換算法示意圖2．任意方向直線的DDA公式遞推公式xi+1=xi+1，yi+1=yi+k(△x>0，|△x|>|△y|)（1）△x<0時(shí)不正確（2）|△x|<|△y|時(shí)不精確如(0,0)(2,5)將生成3個(gè)點(diǎn)0,01,32,5可將任意方向直線分為以下4類(lèi)：xi+1=xi+1，yi+1=yi+k(△x>0，|△x|>|△y|)yi+1=yi

+1，xi+1=xi+1/k

（△y>0，|△x|<|△y|）xi+1=xi

–1，yi+1=yi–k

（△x<0，|△x|>|△y|）yi+1=yi

–1，xi+1=xi

–1/k

（△y<0，|△x|<|△y|）3．程序設(shè)計(jì)繪制△x>△y>0方向直線段DDA法的主要程序intx0,y0,x1,y1;floaty,k;CDC*pDC=GetDC();k=(y1-y0)/(x1-x0);//(x0,y0)(x1,y1)為直線段的兩個(gè)端點(diǎn)坐標(biāo)y=y0;for(x=x0;x<=x1;x++) {pDC->SetPixel(x,(int)(y+0.5),RGB(0,0,0)); y=y+k; }當(dāng)x0=10,y0=10,x1=150,y1=120時(shí)，窗口的坐標(biāo)原點(diǎn)在左上角，該程序的運(yùn)行效果如圖3-3所示。圖3-3DDA法繪制直線效果示意圖3.1.3Bresenham畫(huà)線算法Bresenham算法增加了一個(gè)判別參數(shù)，實(shí)現(xiàn)了全整數(shù)計(jì)算，每步計(jì)算只包括一個(gè)正負(fù)判別和一個(gè)整數(shù)加法，適合硬件實(shí)現(xiàn)。

已知：線段(x0,y0),(x1,y1)，斜率0<k<1,x,y為整數(shù)y=kx+bΔx=x1-x0Δy=y1-y0k=Δy/Δx

（3）計(jì)算過(guò)程1計(jì)算Δx、Δy等常數(shù)計(jì)算e0=2Δy-Δx繪制點(diǎn)(x0,y0)2設(shè)xi點(diǎn)的計(jì)算、繪制已經(jīng)完成，xi、yi、ei為已知，對(duì)xi+1點(diǎn)若ei>=0，

若ei<0，3循環(huán)2

思路：x從x0開(kāi)始，每次給予增量1，計(jì)算對(duì)應(yīng)的y。事實(shí)上，y只有2個(gè)選擇，即yi或yi+1，可以尋找一個(gè)判斷方法，而不按方程進(jìn)行計(jì)算。線段(0,0),(5,2)Δy=2，Δx=5，2Δy-2Δx=-6，2Δy=4,e0=2Δy-Δx=-1

xye-----------------------------00-110321-331142-5524．程序設(shè)計(jì)直線的斜率在0、l之間的Bresenham畫(huà)線算法的VC主要代碼如下：CDC*pDC=GetDC();dx=x1-x0;dy=y1-y0;e=-dx;y=y0;dxx=dx+dx;dyy=dy+dy;for(x=x0;x<=x1;x++){ pDC->SetPixel(x,y,RGB(0,0,0));

if(e>=0)y=y++,e=e-dxx; e=e+dyy;}（1）誤差計(jì)算

可以作為選擇y的判別量，但式子還復(fù)雜。乘Δx，并代入kΔx=Δy則ei的計(jì)算僅包括整數(shù)運(yùn)算，其符號(hào)與(d1-d2)的符號(hào)相同。當(dāng)ei<0時(shí)，直線上理想位置與像素(xi＋1，yi)更接近，應(yīng)取yi；當(dāng)ei>0時(shí)，像素(xi＋1，yi＋1)與直線上理想位置更接近，應(yīng)取yi+1；當(dāng)ei=0時(shí)，兩個(gè)像素與直線上理想位置一樣接近，可約定取(xi＋1，yi＋1)。

特別地，代入xi=x0，yi=y0，b=y0-Δy/Δx*x0，則e0=2Δy-Δxe0=2Δy*x0-2Δx*y0+[2Δy+Δx*(2b-1)]=2Δy*x0-2Δx*y0+2Δy+Δx*(2y0-Δy/Δx*x0-1)=2Δy*x0-2Δx*y0+2Δy+2Δx*y0-2Δy*x0–Δx

=2Δy-Δxei的幾何意義：ei是使用xi點(diǎn)信息計(jì)算的量，用于判斷xi+1點(diǎn)上y的選取。（2）ei的遞推代入x的增量為1，則如果選擇右上方像素，即：，則：如果選擇右方像素，即：，則：上述公式假設(shè)Δx>Δy>0e0=2Δy-Δxxi+1=xi+1ifei>0yi+1=yi+1,ei+1=ei+2Δy-2Δxelseyi+1=yi,ei+1=ei+2Δy共包含8種情況，其他情況可以類(lèi)似地進(jìn)行推導(dǎo)如Δx<0,Δy>0,|Δx|>|Δy|時(shí)e0=2Δy-|Δx|xi+1=xi-1ifei>0yi+1=yi+1,ei+1=ei+2Δy-2|Δx|elseyi+1=yi,ei+1=ei+2Δy練習(xí)：1(-1,0)(4,4)2(4,1)(-1,5)3.1.4直線線寬的處理（1）垂直線刷子：假設(shè)直線斜率在[－1，1]之間，把刷子放置成垂直方向，刷子中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn)，然后讓刷子中心往直線的另一端移動(dòng)，即可“刷出”具有一定寬度的線。如圖3-8所示為線寬為5的線段。

（2）水平線刷子：直線斜率不在[－1，1]之間，可以把刷子放置成水平方向，刷子中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn)并往直線的另一端移動(dòng)，可“刷出”具有一定寬度的線，如圖3-9所示。圖3-8垂直線刷子繪制具有寬度的線圖3-9水平線刷子繪制具有寬度的線線刷子算法簡(jiǎn)單、效率高。但有以下幾個(gè)缺點(diǎn)：①線的始末端總是水平或垂直，當(dāng)線寬較大時(shí)，看起來(lái)很不自然。②兩條線的匯合處外角將有缺口，如圖3-10所示。③斜線與水平（或垂直）線不一樣粗。對(duì)于水平線或垂直線，刷子與線條垂直，因而最粗。其粗細(xì)與指定線寬相等。而對(duì)于45°斜線，刷子與線條成45°角，粗細(xì)僅為指定線寬的倍。④當(dāng)線寬為偶數(shù)個(gè)像素時(shí)，用上述方法繪制的線條要么粗一個(gè)像素，要么細(xì)一個(gè)像素。（3）方形刷子：把邊寬為指定線寬的正方形的中心沿直線作平行移動(dòng)，即可獲得具有線寬的線條。圖3-11所示為用正方形刷子繪制的具有寬度的線條。圖3-10刷子所產(chǎn)生的缺口圖3-11方形刷子繪制的具有寬度的線3.2圓與橢圓圖形3.2.1簡(jiǎn)單方程產(chǎn)生圓弧利用圓的參數(shù)方程，直接計(jì)算離散點(diǎn)值。圓的參數(shù)方程為

x=x0+rcos

y=y0+rsin

（0≤

≤2

）式中，x0和y0為圓的圓心坐標(biāo)，r為圓的半徑。對(duì)以上方程進(jìn)行離散化：

xi=x0+rcos

i

yi=y0+rsin

i關(guān)鍵的問(wèn)題是

i+1與

i的關(guān)系，即

i+1=

i+d中的d如何確定。如果使用畫(huà)點(diǎn)生成圓，則d與圓的半徑r相關(guān)，r越大，圓的周長(zhǎng)就長(zhǎng)，圓周上的像素點(diǎn)就多。對(duì)于固定范圍內(nèi)的

，d就越小，根據(jù)圓周長(zhǎng)公式，取d=1/(2

r)。離散化后圓的參數(shù)取值如下：

0=0,

i+1=

i+1/(2

r),i=0,1,2…,直到

i=2

時(shí)結(jié)束其VC主要程序代碼為：

CDC*pDC=GetDC();d=0.5/r/3.14;for(t=0;t<6.283;t=t+d){ x=x0+r*cos(t); y=y0+r*sin(t); pDC->SetPixel(x,y,RGB(0,0,0));}3.2.3Bresenham畫(huà)圓算法基本思想是尋找最接近于實(shí)際圓周上的點(diǎn)。與中點(diǎn)畫(huà)圓算法相似，考慮圓心在原點(diǎn)，半徑為R的8分圓，?。?，R）為起點(diǎn)，按順時(shí)針?lè)较蛏蓤A。即Bresenham畫(huà)圓算法的遞歸式為d0=3-2R(x0=0，y0=R)當(dāng)di＜0時(shí)，di+1=di+4xi+6，xi+1=xi+1當(dāng)di≥0時(shí)，di+1=di+4(xi－yi)+10，

xi+1=xi+1，y