基本圖形生成算法

1、第三章 基本圖形生成算法圖形的掃描轉(zhuǎn)換1基本圖形生成算法圖元掃描轉(zhuǎn)換直線段掃描轉(zhuǎn)換圓弧掃描轉(zhuǎn)換實(shí)區(qū)域填充圖形反走樣2光柵圖形中點(diǎn)的表示(x,y)坐標(biāo)地址線性表1D表示顯示屏幕2D表示像素由其左下角坐標(biāo)表示3光柵圖形中點(diǎn)的表示地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址xyxmaxxminymaxymin每行像素點(diǎn)數(shù)行數(shù)行中位置4光柵圖形中點(diǎn)的表示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ù)尋址時(shí)，如何減少計(jì)算量？增量法的優(yōu)點(diǎn)？5圖形顯示的幾種方式圖形顯示前需要：掃描轉(zhuǎn)換+裁剪裁剪掃描轉(zhuǎn)換：最常用，節(jié)約計(jì)算時(shí)間掃描轉(zhuǎn)換裁剪：算法簡單6直線段掃描轉(zhuǎn)換假設(shè)像素間均勻網(wǎng)格，整型坐標(biāo)系，直線段斜率0m1對m1，x、y互換7直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換 確定最佳逼近于該直線的一組象素按掃描線順序，對這些象素進(jìn)行寫操作三個(gè)常用算法：1數(shù)值微分

3、法（DDA）2中點(diǎn)畫線法3Bresenham算法。8數(shù)值微分(DDA)法(1/5)已知線段端點(diǎn)：P0(x0,y0), P1(x1,y1)直線方程 y=kx+b (xi, yi), i=0,.n.浮點(diǎn)數(shù)取整 : yi=round(yi)=(int)(yi+0.5)用到浮點(diǎn)數(shù)的乘法、加法和取整運(yùn)算9數(shù)值微分(DDA)法(2/5)增量算法yi+1=kxi+1+b=k(xi+1)+b=yi+k(xi,yi)(xi+1,yi+k)缺點(diǎn)：有浮點(diǎn)數(shù)取整運(yùn)算不利于硬件實(shí)現(xiàn)效率低僅適用于k 1的情形:x每增加1,y最多增加1。當(dāng) k 1時(shí)，必須把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 如何選?。窟x取的原則：使0.5|x|,|y|111數(shù)值微分(DDA)法(4/5)對稱的DDA取=2-n使 2n-1max(|x |,|y|)2n簡單的DDA取= 1/max(|x |,|y|)使 |x |, |y|中必有一個(gè)是單位步長x為最大時(shí)， x =1, x =ky為最大時(shí)， y =1, y =1/k12數(shù)值微分(DDA)法(5/5)缺點(diǎn)：浮點(diǎn)數(shù)運(yùn)算不易硬件實(shí)現(xiàn)13中點(diǎn)畫線法（1/4）問題：判斷距離理想直線最近的下一個(gè)象素點(diǎn)已知：

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

6、增量為a若d0，中點(diǎn)M在直線下方，取右上方象素P2 (Xp+1,Yp+1)再下一個(gè)象素的判別式為： 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)點(diǎn)：只有整數(shù)運(yùn)算，不含乘除法可用硬件實(shí)現(xiàn)因(X0,Y0)在直線上，所以F(X0,Y0)=0中點(diǎn)畫線法（4/4）17Bresenham畫線算法（1/7）使用最廣泛與中點(diǎn)畫線法的思想類似由誤差項(xiàng)符號決定下一個(gè)象素取正右

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

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

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

10、中點(diǎn)畫圓法（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實(shí)際畫出的曲線不是圓，而是螺旋線，為什么？29DDA畫圓法（2/3）將遞推公式寫成矢量形式：構(gòu)造一個(gè)行列式值為1的矩陣對應(yīng)的圓

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

12、,yi-1)32Bresenham畫圓算法（2/7）圓弧與點(diǎn)(xi,yi)附近光柵網(wǎng)格的相交關(guān)系有5種右下角像素D (xi,yi)與實(shí)際圓弧的近似程度i=(xi+1)2+(yi-1)2-R2當(dāng)i0時(shí)，D在圓外，當(dāng)i=0時(shí)，D在圓上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)33Bresenham畫圓算法（3/7）當(dāng)i0時(shí)，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）當(dāng)i0時(shí)，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）當(dāng)i=0時(shí)，D在圓上，按d判別，有d0，應(yīng)選D按d判別，有d0，應(yīng)選D36Bresenham畫圓算法（6/7）當(dāng)i0，選D當(dāng)i0時(shí),若d 0，選D 若d0，選V當(dāng)i=0時(shí)，選D37Bresenham畫圓算法（7/7）判別式的遞推關(guān)系當(dāng)取H(xi+1,yi)時(shí)i+1=(xi+1+1)2+(yi-1)2-R2= i