基本圖形生成算法

1、第三章 基本圖形生成算法圖形的掃描轉換1基本圖形生成算法圖元掃描轉換直線段掃描轉換圓弧掃描轉換實區(qū)域填充圖形反走樣2光柵圖形中點的表示(x,y)坐標地址線性表1D表示顯示屏幕2D表示像素由其左下角坐標表示3光柵圖形中點的表示地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址xyxmaxxminymaxymin每行像素點數(shù)行數(shù)行中位置4光柵圖形中點的表示Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + xAddress(x1,y) = k1 + k2y + (x1) = A

2、ddress(x,y) 1Address(x,y1) = k1 + k2(y 1) + x = Address(x,y) k2Address(x1,y1) = k1 + k2(y 1) + (x1) = Address(x,y) k2 1對像素連續(xù)尋址時，如何減少計算量？增量法的優(yōu)點？5圖形顯示的幾種方式圖形顯示前需要：掃描轉換+裁剪裁剪掃描轉換：最常用，節(jié)約計算時間掃描轉換裁剪：算法簡單6直線段掃描轉換假設像素間均勻網(wǎng)格，整型坐標系，直線段斜率0m1對m1，x、y互換7直線段的掃描轉換算法直線的掃描轉換 確定最佳逼近于該直線的一組象素按掃描線順序，對這些象素進行寫操作三個常用算法：1數(shù)值微分

3、法（DDA）2中點畫線法3Bresenham算法。8數(shù)值微分(DDA)法(1/5)已知線段端點：P0(x0,y0), P1(x1,y1)直線方程 y=kx+b (xi, yi), i=0,.n.浮點數(shù)取整 : yi=round(yi)=(int)(yi+0.5)用到浮點數(shù)的乘法、加法和取整運算9數(shù)值微分(DDA)法(2/5)增量算法yi+1=kxi+1+b=k(xi+1)+b=yi+k(xi,yi)(xi+1,yi+k)缺點：有浮點數(shù)取整運算不利于硬件實現(xiàn)效率低僅適用于k 1的情形:x每增加1,y最多增加1。當 k 1時，必須把x，y互換。10數(shù)值微分(DDA)法(3/5)digital di

4、fferential analyzer基本思想用數(shù)值方法解微分方程 dy/dt = xdy/dt = y xn+1 = xn + x yn+1 = yn + y 如何選??？選取的原則：使0.5|x|,|y|111數(shù)值微分(DDA)法(4/5)對稱的DDA取=2-n使 2n-1max(|x |,|y|)2n簡單的DDA取= 1/max(|x |,|y|)使 |x |, |y|中必有一個是單位步長x為最大時， x =1, x =ky為最大時， y =1, y =1/k12數(shù)值微分(DDA)法(5/5)缺點：浮點數(shù)運算不易硬件實現(xiàn)13中點畫線法（1/4）問題：判斷距離理想直線最近的下一個象素點已知：

5、線段兩端點(x0,y0)，(x1,y1)直線方程：F(x,y)=ax+by+c=0a=y0-y1b=x1-x0c=x0y1-x1y0M如何判斷M點在Q點上方還是在Q點下方？14MP1P2P直線上方點： F(x,y)0 直線下方點: F(x,y)0構造判別式： d=F(M)=F(Xp+1,Yp+0.5)由d0，d0可判定下一個象素(Xp+1,Yp+0.5)中點畫線法（2/4）15分兩種情形考慮再一下個象素的判定：若d0，中點M在直線上方，取正右方象素P1 (Xp+1,Yp)再下一個象素的判別式為： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的

6、增量為a若d0，中點M在直線下方，取右上方象素P2 (Xp+1,Yp+1)再下一個象素的判別式為： d2=F(Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c =d+a+b d的增量為a+bMP1P2MP1P216d的初始值d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5 =a+0.5b用2d代替d后，d0=2a+bd的增量都是整數(shù)優(yōu)點：只有整數(shù)運算，不含乘除法可用硬件實現(xiàn)因(X0,Y0)在直線上，所以F(X0,Y0)=0中點畫線法（4/4）17Bresenham畫線算法（1/7）使用最廣泛與中點畫線法的思想類似由誤差項符號決定下一個象素取正右

7、方像素還是右上方像素18Bresenham畫線算法（2/7）基本思想比較從理想直線到位于直線上方的像素的距離d1和相鄰的位于直線下方的像素的距離d2根據(jù)距離誤差項的符號確定與理想直線最近的象素19Bresenham畫線算法（3/7）最大位移方向每次走一步k1時，x為最大位移方向y方向走步與否取決于誤差e值的大小誤差計算初值：e0= y/ x當e0.5時，最接近P2(xi+1,yi+1)y方向走一步當e0.5時，最接近P1(xi+1,yi)y方向不走步eP1P2PeeP1P2Pe20Bresenham畫線算法（4/7）為方便與0比較，設e=e-0.5e0=y/ x-0.5當e0時，最接近P2(x

8、i+1,yi+1)y方向走一步當e0時，最接近P1(xi+1,yi)y方向不走步有除法，不宜硬件實現(xiàn)eP1P2PeeP1P2Pe21Bresenham畫線算法（5/7）設e=e2x，不影響判斷的準確性e0=2y - x 當e0時，最接近P2(xi+1,yi+1)y方向走一步當e0時，最接近P1(xi+1,yi)y方向不走步eP1P2PeeP1P2Pe22Bresenham畫線算法（6/7）下一步誤差的計算當e0時，y方向走一步e=2y/ x - 1 =e + y/ x - 1 e=e + 2y - 2x當e0時，y方向不走步e=2y/ x=e + y/ xe=e + 2yeP1P2PeeP1P

9、2Pe23Bresenham畫線算法（7/7）優(yōu)點整數(shù)運算，速度快精度高乘2運算可用移位實現(xiàn)，適于硬件實現(xiàn)24圓弧的掃描轉換圓的八對稱性只考慮第二個八分圓假設圓心在原點 x2+y2=R2 yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR25圓弧的掃描轉換兩種直接離散生成方法離散點開方運算離散角度三角函數(shù)運算缺點：計算量大所畫像素位置間的間距不一致 26中點畫圓法（1/2）F(X,Y)=X2+Y2-R2=0中點 M=(Xp+1,Yp-0.5)當F(M)0時，M在圓內(nèi)，P1距離圓弧近，取P1當F(M)0時，M在圓外，P2距離圓弧近，取P227

10、中點畫圓法（2/2）若 d=0, 取P1為下一象素，再下一象素的判別式為 初始象素是（0,R），判別式d的初值為P1(Xp+1,Yp)P2(Xp+1,Yp-1)使用e=d-0.25代替de0=1-R28DDA畫圓法（1/3）圓的方程：f(x,y)=x2+y2-R2=0全微分：df(x,y)=2xdx+2ydy=0微分方程：dy/dx=-x/y遞推方程: (yn+1-yn)/ (xn+1-xn)=-xn/ yn xn+1 - xn = yn yn+1 - yn = -xn實際畫出的曲線不是圓，而是螺旋線，為什么？29DDA畫圓法（2/3）將遞推公式寫成矢量形式：構造一個行列式值為1的矩陣對應的圓

11、方程遞推關系為 xn+1 = xn + yn yn+1 = -xn +(1-2)yn= yn- xn+1 30DDA畫圓法（3/3）針對不同象限及順逆時針畫圓，賦給適當?shù)姆?不同，圓形狀不同， 大近似橢圓31Bresenham畫圓算法（1/7）順時針畫第一四分圓，下一步選擇哪個點？基本思想：通過比較像素與圓的距離平方來避免開方運算下一像素有3種可能的選擇mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2 +(yi-1)2-R2 |選擇像素的原則使其與實際圓弧的距離平方達到最小(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1

12、,yi-1)32Bresenham畫圓算法（2/7）圓弧與點(xi,yi)附近光柵網(wǎng)格的相交關系有5種右下角像素D (xi,yi)與實際圓弧的近似程度i=(xi+1)2+(yi-1)2-R2當i0時，D在圓外，當i=0時，D在圓上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)33Bresenham畫圓算法（3/7）當i0時，D在圓內(nèi)，情形，選mH ，mD 中最小者d=mH - mD =|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2| =(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2 =2 (i+yi)-

13、1若d0，則選D若d=0，則選H情形也適用34Bresenham畫圓算法（4/7）當i0時，D在圓外，情形，選mv ，mD 中最小者d=mD - mV =|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1若d0，則選V若d=0，則選D情形也適用35Bresenham畫圓算法（5/7）當i=0時，D在圓上，按d判別，有d0，應選D按d判別，有d0，應選D36Bresenham畫圓算法（6/7）當i0，選D當i0時,若d 0，選D 若d0，選V當i=0時，選D37Bresenham畫圓算法（7/7）判別式的遞推關系當取H(xi+1,yi)時i+1=(xi+1+1)2+(yi-1)2-R2= i