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

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

k=△y/△x△x＝x1-x0，△y＝y1-y0。設△x>△y>0，x從起點到終點變化，每步遞增1個像素，計算對應的y坐標，

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

yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k=yi+k直線掃描轉換的數值微分算法：k=(y1-y0)/(x1-x0)，x0=x0，y0=y0xi+1=xi+1，yi+1=yi+k，（i=0，1，2，…，x1－x0）當0<△x<△y時，每步y遞增1個像素(yi+1=yi+1)，需計算對應的x坐標：xi+1=yi+1/k－b/k=(yi+1)/k-b/k=yi/k－b/k+1/k=yi+1/k圖3-2DDA直線掃描轉換算法示意圖2．任意方向直線的DDA公式遞推公式xi+1=xi+1，yi+1=yi+k(△x>0，|△x|>|△y|)（1）△x<0時不正確（2）|△x|<|△y|時不精確如(0,0)(2,5)將生成3個點0,01,32,5可將任意方向直線分為以下4類：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．程序設計繪制△x>△y>0方向直線段DDA法的主要程序intx0,y0,x1,y1;floaty,k;CDC*pDC=GetDC();k=(y1-y0)/(x1-x0);//(x0,y0)(x1,y1)為直線段的兩個端點坐標y=y0;for(x=x0;x<=x1;x++) {pDC->SetPixel(x,(int)(y+0.5),RGB(0,0,0)); y=y+k; }當x0=10,y0=10,x1=150,y1=120時，窗口的坐標原點在左上角，該程序的運行效果如圖3-3所示。圖3-3DDA法繪制直線效果示意圖3.1.3Bresenham畫線算法Bresenham算法增加了一個判別參數，實現了全整數計算，每步計算只包括一個正負判別和一個整數加法，適合硬件實現。

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

（3）計算過程1計算Δx、Δy等常數計算e0=2Δy-Δx繪制點(x0,y0)2設xi點的計算、繪制已經完成，xi、yi、ei為已知，對xi+1點若ei>=0，

若ei<0，3循環2

思路：x從x0開始，每次給予增量1，計算對應的y。事實上，y只有2個選擇，即yi或yi+1，可以尋找一個判斷方法，而不按方程進行計算。線段(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．程序設計直線的斜率在0、l之間的Bresenham畫線算法的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）誤差計算

可以作為選擇y的判別量，但式子還復雜。乘Δx，并代入kΔx=Δy則ei的計算僅包括整數運算，其符號與(d1-d2)的符號相同。當ei<0時，直線上理想位置與像素(xi＋1，yi)更接近，應取yi；當ei>0時，像素(xi＋1，yi＋1)與直線上理想位置更接近，應取yi+1；當ei=0時，兩個像素與直線上理想位置一樣接近，可約定取(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點信息計算的量，用于判斷xi+1點上y的選取。（2）ei的遞推代入x的增量為1，則如果選擇右上方像素，即：，則：如果選擇右方像素，即：，則：上述公式假設Δ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種情況，其他情況可以類似地進行推導如Δx<0,Δy>0,|Δx|>|Δy|時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練習：1(-1,0)(4,4)2(4,1)(-1,5)3.1.4直線線寬的處理（1）垂直線刷子：假設直線斜率在[－1，1]之間，把刷子放置成垂直方向，刷子中點對準直線一端點，然后讓刷子中心往直線的另一端移動，即可“刷出”具有一定寬度的線。如圖3-8所示為線寬為5的線段。

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

x=x0+rcos

y=y0+rsin

（0≤

≤2

）式中，x0和y0為圓的圓心坐標，r為圓的半徑。對以上方程進行離散化：

xi=x0+rcos

i

yi=y0+rsin

i關鍵的問題是

i+1與

i的關系，即

i+1=

i+d中的d如何確定。如果使用畫點生成圓，則d與圓的半徑r相關，r越大，圓的周長就長，圓周上的像素點就多。對于固定范圍內的

，d就越小，根據圓周長公式，取d=1/(2

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

0=0,

i+1=

i+1/(2

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

i=2

時結束其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畫圓算法基本思想是尋找最接近于實際圓周上的點。與中點畫圓算法相似，考慮圓心在原點，半徑為R的8分圓，取（0，R）為起點，按順時針方向生成圓。即Bresenham畫圓算法的遞歸式為d0=3-2R(x0=0，y0=R)當di＜0時，di+1=di+4xi+6，xi+1=xi+1當di≥0時，di+1=di+4(xi－yi)+10，

xi+1=xi+1，y