印刷圖像及圖形處理實驗參考生成

印刷圖像及圖形處理PrintingImageandGraphProcessing主講：鐘云飛第三章圖形處理的基本理論3.1二維輸出圖元及其屬性3.2多邊形的掃描轉(zhuǎn)換及區(qū)域填充（X）3.3幾何變換3.4曲線曲面造型知識點：熟悉掌握計算機圖形學(xué)的基本概念，計算機圖形算法基礎(chǔ)知識，了解圖形變換基礎(chǔ)類型，了解計算機對曲線與曲面處理的工作原理。重點：計算機圖形學(xué)的基本概念。難點：計算機圖形算法。

3.1二維輸出圖元及其屬性如何在指定的輸出設(shè)備上根據(jù)坐標描述構(gòu)造基本二維幾何圖形（點、直線、圓、橢圓、多邊形域、像素數(shù)組、字符串及其相關(guān)屬性等）提出問題直線生成算法圓弧生成算法橢圓生成算法其它輸出圖元的生成輸出圖元的屬性字符的生成本章內(nèi)容主要內(nèi)容學(xué)習(xí)目標深入認識圖形函數(shù)包功能，了解函數(shù)是如何實現(xiàn)的，從而可改進圖形函數(shù)以適應(yīng)某些特殊的應(yīng)用需求。開發(fā)和改進圖形技術(shù)，發(fā)展網(wǎng)絡(luò)圖形應(yīng)用，開發(fā)更快的實時性更強的圖形顯示。掌握直線、圓、橢圓的生成算法熟悉輸出圖元的屬性控制、字符的生成學(xué)習(xí)目標圖形設(shè)計中最基本的圖形元素是點、直線、圓、曲線。任何復(fù)雜的圖形均可看成是點和直線組成。本質(zhì)上，物體的形狀和顏色可用像素矩陣或直線段和多邊形填充區(qū)域等基本幾何結(jié)構(gòu)來描述。通常，圖形編程軟件包提供使用輸出圖元的基本幾何結(jié)構(gòu)來描述場景和將輸出圖元組合成更復(fù)雜結(jié)構(gòu)的功能。點和直線段是最簡單的幾何成分。一、點和直線在CRT上，點的顯示是通過開關(guān)電子槍，使電子束打擊在屏幕上的某一位置發(fā)光。電子束的定位取決于采用的顯示技術(shù)。

a.在向量顯示系統(tǒng)中，畫點命令存放在顯示列表中，而坐標位置被轉(zhuǎn)換為偏轉(zhuǎn)線圈上的電壓以使電子束定位在指定的屏幕位置上。

b.在黑白光柵顯示系統(tǒng)中，通過設(shè)置幀緩沖區(qū)中對應(yīng)屏幕位置的位的值為1來顯示點，這樣，當電子束掃描過水平掃描線時，如遇到幀緩沖區(qū)中值為1時，就發(fā)射電子打擊屏幕，產(chǎn)生亮點。對于RGB系統(tǒng)，顏色碼隨幀緩存加載，以便能顯示彩色點。畫直線通過計算兩端點間的中間點來畫直線。像向量筆、向量顯示器這樣的模擬輸出設(shè)備能輸出光滑的直線。數(shù)字設(shè)備畫直線是通過畫直線兩個端點間的各個離散的點來完成。每個分散的點的位置通過直線方程來計算。對于光柵顯示系統(tǒng)，直線顏色裝載在相應(yīng)象素位置的幀緩存中。屏幕坐標只能為整數(shù)，因此，畫點的位置只能近似實際直線上點的位置。例如計算的點的位置(10.48,20.51)近似為(10,21)。這樣畫出的直線會出現(xiàn)鋸齒樣，在低分辨率的顯示系統(tǒng)上尤其明顯。通過調(diào)整顯示點的亮度可以減輕鋸齒影響，無法消除。點的坐標 點在屏幕上的位置坐標用像素為單位，點的像素坐標只能是整數(shù)。 而理論上的點的坐標根據(jù)直線方程可以為任何實數(shù)，而點的像素坐標受設(shè)備坐標系的制約，只能為整數(shù)。本章將討論光柵系統(tǒng)上設(shè)備級圖元生成算法，物體坐標用整數(shù)的設(shè)備坐標指定。目前我們假定象素位置根據(jù)水平掃描線和垂直掃描線的交叉定義，如圖。裝載指定位置象素的顏色到幀緩存用函數(shù)：setPixel(x,y)或setPixel(x,y,color)讀取指定位置象素的顏色用函數(shù)：

getPixel(x,y)0123453210光柵掃描轉(zhuǎn)換的定義 根據(jù)圖形的幾何描述,確定在二維的像素矩陣上那些像素正好在圖形上或最靠近圖形,這一過程就稱為光柵掃描轉(zhuǎn)換。評價光柵掃描轉(zhuǎn)換算法優(yōu)劣的標準a.顯示圖形的精度。b.算法的時間復(fù)雜性。c.算法的空間復(fù)雜性。二、直線生成算法計算機繪制的直線是由一系列與該直線最近的像素繪制而成,因此,理論直線與計算機繪制的直線之間總有一定的偏差,由繪圖的方式?jīng)Q定,只能盡量減少偏差。偏差取決于屏幕光柵(分辨率)和光點的運動方向。直線的笛卡爾斜率截距方程：

y=mx+b (3-1)

給定直線的兩個端點(xa,ya)和(xb,yb)，則可計算出：

m=(yb-ya)/(xb-xa)(3-2) b=(yaxb-ybxa)/(xb-xa) (3-3)

對于任何沿直線給定的x方向上的增量△x，可從方程(3-2)計算出對應(yīng)的y方向上的增量△y: △y=m△x(3-4)

同樣，可以得出對應(yīng)于指定y方向上的增量△y,可從方程(3-2)計算出對應(yīng)的x向上的增量△x △x=△y/m(3-5)對于模擬顯示設(shè)備，方程(3-4)(3-5)使決定偏轉(zhuǎn)電壓變化的基礎(chǔ)。

a.當|m|<1，△x可以設(shè)置為正比于一水平偏轉(zhuǎn)電壓，△y則可以根據(jù)公式計算。

b.當|m|>1，△y可以設(shè)置為正比于一水平偏轉(zhuǎn)電壓，△x則可以根據(jù)公式計算。對于光柵顯示器，直線用象素點來畫，在水平或垂直上的步長△x/△y受象素間距限制。即需要在直線上不同的位置取樣，并在每個樣本點上取最接近直線的點。如圖:xaxb二、常用直線生成算法.1.1DDA算法.1.2Bresenham直線算法.1.3中點直線算法.1.4并行直線算法DDA(digitaldifferentialanalyzer)方法是利用方程(3-4)或(3-5)計算△x或△y的一個線段掃描轉(zhuǎn)換算法。在一個坐標軸上以單位間隔取樣，以決定另一個坐標軸上最靠近線段路徑的對應(yīng)整數(shù)值。對于0≤m≤1，則在單位x間隔(△x=1)取樣并計算每個順序的y值：

yk+1=yk+m（3-6） 下標k取整數(shù)，從起點開始遞增至末點。由于m可是0到1之間的任意實數(shù)，所以計算出的y值必須取整。.1.1DDA算法對于1≤m的直線段，則將x和y的規(guī)則交換，即在單位y間隔(△y=1)取樣，并計算每個連續(xù)的x值：

xk+1=xk+1/m（3-7）方程（3-6）和（3-7）基于線段從左端點到右端點進行處理的假設(shè)。假設(shè)這個過程相反，即起始點在右側(cè)，那么，△x=-1，并且

yk+1=yk-m（3-8） 或△y=-1，且

xk+1=xk-1/m（3-9） 方程（3-6）至（3-9）也可用于計算負斜率的線段的像素位置。一般地： 畫直線的DDA算法可表示為:若|m|≤1:xk+1=xk+1,yk+1=yk+m;xa<xb or:xk+1=xk-1,yk+1=yk-m ;xa>xb若|m|≥1:yk+1=yk+1,xk+1=xk+1/m;ya<yb or:yk+1=yk-1,yk+1=yk-1/m;ya>ybDDA算法的C實現(xiàn)#defineRound(a)((int)(a+0.5))voidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya,steps,k;floatxIncrement,yIncrement,x=xa,y=ya;if(abs(dx)>abs(dy)) steps=abs(dx);else steps=abs(dy);

xIncrement=dx/(float)steps;yIncrement=dy/(float)steps;setpixel(Round(x),Round(y),RED);for(k=0;k<steps;k++){x+=xIncrement;y+=yIncrement;setpixel(Round(x),Round(y),RED);}}分析從(0,0)到(20,10)的直線段和從(20,10)到(0,0)的直線DDA算法的缺點:a.計算量大(取整操作和浮點運算)b.效率低，速度慢

c.誤差累計，造成畫長直線時點逐漸偏離理論點.1.2Bresenham直線算法它是由Bresenham提出的一種精確而有效的光柵線段生成算法,可用于直線、圓(圓弧)和其它曲線的生成?？紤]直線斜率0≤m≤1,且xa<xb,根據(jù)DDA算法，則: xk+1=xk+1 yk+1=yk+m(xk,yk)是第k步計算出的點的坐標,它在x=xk處最接近/通過直線。那么下一點需要確定在xk+1處繪制哪個像素，是(xk+1,yk)還是(xk+1,yk+1)?其位置如圖：XkYkXk+1Yk+1ABC由DDA算法知道，當xk+1=xk+1時，yk+1=yk+m后取整，有兩種情況yk+1=yk和yk+1=yk+1，即B(xk+1,yk)和A(xk+1,yk+1)兩個點.對于Bresenham算法，根據(jù)直線y=mx+b在x=xk+1處的理論坐標點與點A、B間的距離大小關(guān)系，選擇距離小的點。設(shè)定d1=|BC|，d2=|AC|，由直線方程y=mx+b，在x=xk+1的y坐標

y=m(xk+1)+b則：

d1=y-yk=m(xk+1)+b-yk d2=yk+1-y=yk+1-m(xk+1)-b △d=d1-d2=2m(xk+1)-2yk+2b-1根據(jù)△d的符號可判斷在x=xk+1應(yīng)該取理論坐標的上下中的那一個點，判定方法：

A.△d>0，取上面的點A(yk+1=yk+1) B.△d≤0，取下面的點B(yk+1=yk)由于△d的計算量大，考慮到△x=xb-xa>0,△y=yb-ya因此做如下變化：

pk=△x△d=2△yxk-2△xyk+c，(c=2△y+△x(2b-1)為常數(shù))則：pk+1=2△yxk+1-2△xyk+1+cpk+1=pk+2△y-2△x(yk+1-yk)p0=2△y-△xBresenham的算法表示(適用于0≤m≤1且xa<xb)：

p0=2△y-△x xk+1=xk+1 yk+1=yk+1，pk+1=pk+2(△y-△x)當pk≥0 yk+1=yk，pk+1=pk+2△y當pk<00≤m≤1,且xa<xb的Bresenham畫線算法步驟：1.輸入線的兩個端點，左端點存儲在(x0,y0)中；2.將(x0,y0)裝入幀緩沖器，畫出第一個點；3.計算常量△x，△y，2△y和2△y-2△x，并得到?jīng)Q策參數(shù)的第一個值：p0=2△y-△x4.從k=0開始，在沿線的每個xk處，進行如下檢測： 假如pk<0，下一個待畫點是(xk+1,yk)，且 pk+1=pk+2△y

否則，下一個待畫點是(xk+1,yk+1)，且pk+1=pk+2(△y-△x)5.重復(fù)步驟4，共△x次。Bresenham算法的C實現(xiàn)(0<m<1且x0<x1)voidlineBres(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya;intp=2*dy-dx;inttwoDy=2*dy,twoDyDx=2*(dy-dx);intx,y,xEnd;x=xa;y=ya;xEnd=xa;setpixel(x,y,RED);while(x<xEnd){x++;if(p<0)p+=twoDy;else{y++;p+=twoDyDx;}setpixel(x,y,RED);}}例:分析從(0,0)到(20,10)的直線段051015200510思考：請給出任意m且區(qū)分起始點的Bresenham直線算法表示或程序。(1)0<m<1,xa<xb(2)0<m<1,xa>xb(3)1<m，ya<yb(4)1<m，ya>yb(5)-1<m<0,xa<xb(6)-1<m<0,xa>xb(7)m<-1，ya<yb(8)m<-1，ya>ybBresenham的算法表示(適用于0≤m≤1且xa>xb)：

p0=-2△y+△x xk+1=xk-1 yk+1=yk-1，pk+1=pk-2(△y-△x)當pk≥0 yk+1=yk，pk+1=pk-2△y當pk<0.1.3中點直線算法一種精確而有效的光柵線段生成算法,可用于直線、圓(圓弧)和其它曲線的生成?？紤]直線斜率0≤m≤1,且xa<xb,根據(jù)DDA算法，則: xk+1=xk+1 yk+1=yk+m(xk,yk)是第k步計算出的點的坐標,它在x=xk處最接近/通過直線。那么下一點需要確定在xk+1處繪制哪個像素，是(xk+1,yk)還是(xk+1,yk+1)?其位置如圖：XkYkXk+1Yk+1ABC由DDA算法知道，當xk+1=xk+1時，yk+1=yk+m后取整，有兩種情況yk+1=yk和yk+1=yk+1，即B(xk+1,yk)和A(xk+1,yk+1)兩個點.A,B的中點M(xk+1,yk+0.5)，直線與x=xk+1的交點C(xk+1,mxk+1+b)，如果YC>YM(C的縱坐標較大)，則C離A近，下一點取A，否則取B.判別式：點與直線的位置關(guān)系

F(x,y)=y-(mx+b)則

<0(x,y)位于直線下方F(x,y) =0(x,y)位于直線本身上

>0(x,y)位于直線上方所以：△d=-2F(M)=-2F(xk+1,yk+0.5)=2m(xk+1)-2yk+2b-1根據(jù)△d的符號可判斷在x=xk+1應(yīng)該取理論坐標的上下中的那一個點，判定方法：

A.△d>0，取上面的點A(yk+1=yk+1) B.△d≤0，取下面的點B(yk+1=yk)由于△d的計算量大，考慮到△x=xb-xa>0,△y=yb-ya因此做如下變化：pk=△x△d=2△yxk-2△xyk+c，(c=2△y+△x(2b-1)為常數(shù))則：pk+1=2△yxk+1-2△xyk+1+cpk+1=pk+2△y-2△x(yk+1-yk)同樣：

A.pk>0，取上面的點A(yk+1=yk+1) B.pk

≤0，取下面的點B(yk+1=yk)初始條件

p0=2△yxa-2△xya+2△y+△x(2b-1)=2△y-△x中點直線的算法表示(適用于0≤m≤1且xa<xb)：

p0=2△y-△xxk+1=xk+1yk+1=yk+1，pk+1=pk+2(△y-△x)當pk≥0yk+1=yk，pk+1=pk+2△y當pk<0.1.4并行直線算法前面討論的直線生成算法順序地生成象素點。對于并行計算機，可以將這樣的順序執(zhí)行任務(wù)在多個處理器間分配來實現(xiàn)直線的并行生成。假設(shè)有np個處理器，對于Bresenham直線算法，我們可將直線分成np段，然后在每個處理器上分別計算這些直線段。設(shè)直線斜率0<m<1，且左端點坐標(xa,ya)。則兩個相鄰直線段的開始x坐標的距離：

xp=

(x+np-1)/np整數(shù)除法

(3-15)直線段從0,1,2,…,np-1編號，第k段的起始x坐標：

xk=xa+kxp(3-16)例：設(shè)x=15，4個處理器，則每段直線段長度4，每直線段的起始x坐標xa，xa+4，xa+8，xa+12。要應(yīng)用Bresenham直線算法，還必須知道每段直線段的起始y坐標和決策參數(shù)的初始值。知道xp，則yp=mxp(3-17)第k段直線段的起始y坐標:yk=ya+round(kyp)(3-18)第k段直線段的初始決策參數(shù):pk=(kxp)(2y)-round(kyp)(2x)+2y-x三、幀緩沖器裝載用光柵顯示系統(tǒng)進行直線段和其它物體掃描轉(zhuǎn)換顯示時，必須計算幀緩沖器的位置前面，我們已經(jīng)假設(shè)由setpixel程序來完成，它將像素的亮度存儲到幀緩沖器矩陣中對應(yīng)位置，而掃描轉(zhuǎn)換算法以連續(xù)的單位間隔生成像素位置.因而，就可以用增量方法來計算幀緩沖器地址假設(shè)幀緩沖器地址是以行序為主序來編址，且像素位置以屏幕左下方為(0,0)變化到屏幕右上方(xmax,ymax)。對于像素位置(x,y)的幀緩沖器位地址可計算為：

addr(x,y)=addr(0,0)+y(xmax+1)+x沿掃描線移動，像素(x+1,y)處的幀緩沖器地址可從位置(x,y)的地址做偏移來計算：

addr(x+1,y)=addr(x,y)+1從(x,y)對角地跳到下一條掃描線，(x+1,y+1)的幀緩沖器地址的計算公式為：

addr(x+1,y+1)=addr(x,y)+xmax+2上述的計算公式只針對黑白系統(tǒng)而言，對于能顯示彩色的顯示系統(tǒng)，因為屏幕上每個像素在存儲器中占用多個bit，因此，在用上述的計算公式計算特定點在幀緩沖器中的地址時還必須考慮像素寬度。例如8/16/24/32bit。四、圓弧生成算法由于圓是圖形和圖像中常使用的元素，因此在大多數(shù)圖形軟件中都包含了生成圓和圓弧的過程。也會提供一個既能顯示圓曲線，又能顯示橢圓曲線的過程。.4.1直角坐標法.4.2極坐標法.4.3折線逼近法.4.4中點圓算法.4.5Bresenham圓算法.4.1直角坐標法圓被定義為所有離一中心位置(xc,yc)距離為給定值r的點集?？捎梅匠瘫硎救缦拢?/p>

(x-xc)2+(y-yc)2=r2為簡便起見，我們討論圓心在原點，半徑為r的圓：

x2+y2=r2可以沿x軸從-r到r，以單位步長計算對應(yīng)的y值來得到圓周上每點的位置：

y=±(r2-x2)1/2缺點：計算量大，且畫出的像素位置的距離是不一致的?？紤]到圓的對稱性，可先計算1/8圓，再計算其余的7/8圓。在計算1/8圓時，根據(jù)DDA算法的討論，當|m|<1時，取x方向步長1，計算y后取整；當|m|>1時，取y方向步長1，計算x后取整。.4.2極坐標法使用極坐標法表示圓：

x=rcosθ y=rsinθ 0≤θ≤360但是，算法的計算量仍然很大。更有效的圓算法是如Bresenham畫線算法一樣以決策參數(shù)的增量計算為基礎(chǔ)，僅包括簡單的整數(shù)操作。.4.3折線逼近法圓可以用內(nèi)接正多邊形來逼近。同樣，對于曲線也可以用折線段來逼近，當然，折線段的數(shù)量越多則越逼近曲線本身，但復(fù)雜性就越大。下面我們討論用折線逼近圓。假設(shè)用n段等長折線段來逼近一段半徑R，弧角θ的圓弧，則每段圓弧對應(yīng)的弧角為δ=θ/n.誤差計算a.弧長-弦長=Rδ-Rcos(δ/n)不容易計算。b.e=半徑-|OA|=R[1-cos(δ/2)]≈2Rsin2(δ/4)≈Rδ2/8.

即:e=Rδ2/8

為了使誤差e≤ε,則：

n≥θ*[R/(8ε)]1/2

表明，對于R越大，要求的誤差越小，則所需要的折線段就越多例如：假設(shè)圓弧的半徑R=256個像素，圓弧的角度θ=π,若要求誤差不超過兩個像素，則最少需要多少段折線段來逼近該圓?。?4.4中點圓算法像在光柵畫線算法中一樣，以單位間隔取樣并在每個步長中確定離指定圓最近的像素位置。對于給定半徑r和圓心(xc,yc)，可先給出計算中心在原點(0,0)圓的像素位置的算法，然后通過平移使每個計算出的(x,y)移動到其適當?shù)钠聊晃恢?。同樣，只考慮1/8圓，x從０到R/21/2結(jié)束.為了應(yīng)用中點圓算法，定義一個圓函數(shù)：

fcircle(x,y)=x2+y2-r2

則任何點(x,y)的相對位置可由對圓函數(shù)符合的檢測來決定: <0(x,y)位于圓邊界內(nèi)fcircle(x,y)=0(x,y)位于圓邊界上

>0(x,y)位于圓邊界外假設(shè)用該算法計算出第k個點(xk,yk),下一步需要決定像素位置是A(xk+1,yk),B(xk+1,yk-1)，其中xk+1=xk+1 A,B的中點M(xk+1,yk-0.5)在M處決策參數(shù)：

pk=fcircle(xk+1,yk-0.5)=xk+12+(yk-0.5)2-r2

當pk<0，這個中點M在圓內(nèi)，掃描線yk上的像素(xk+1,yk)更接近于圓邊界，則下一點應(yīng)取右邊的點A(xk+1,yk)。否則，中點M位于圓外或在邊界上，我們選擇掃描線yk-1上的像素B(xk+1,yk-1)pk+1=(xk+1+1)2+(yk+1-0.5)2-r2遞歸表達式：

pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1

其中:yk+1是yk(pk<0)或是yk-1(pk≥0)，這取決于pk的符號。圓在起始位置(x0,y0)=(0,r)處求值就可得到初始決策參數(shù)：

p0=fcircle(1,r-0.5)=5/4–r中點圓算法的算法表示：

p0=5/4–r xk+1=xk+1 yk+1=yk，pk+1=pk+2xk+1+1，當pk<0yk+1=yk-1，pk+1=pk+2xk+1+1-2yk+1，當pk≥0對于2xk+1和2yk+1本身又是一個增量表達式，2xk+1增量始終為2，而2yk+1增量為0(當pk<0)或-2(當pk≥0)，在起始位置(x0,y0)=(0,r)，2xk+1和2yk+1的初始值分別為0和2r。中點畫圓算法的步驟：

1.輸入圓半徑r和圓心(xc,yc),并得到圓心在原點的圓周上的第一點為:(x0,y0)=(0,r)2.計算決策參數(shù)的初始值：

p0=5/4–r3.在每個xk位置處，從k=0開始，完成下列檢測：假如pk<0，中心在(0,0)的圓的下一個點為(xk+1,yk)，且

pk+1=pk+2xk+1+1

否則，圓的下一個點為(xk+1,yk-1)，且

pk+1=pk+2xk+1+1-2yk+1

其中：2xk+1=2xk+1，2yk+1=2yk-24.確定在其它7個8分圓中的對稱點

5.將每個計算出的像素位置(x,y)移動到中心在(xc,yc)的圓路徑上，并畫坐標值：

x=xc+xy=yc+y6.重復(fù)步驟3到5，直至x≥y.中點圓算法的C實現(xiàn)：voidcircleMidpoint(intxCenter,intyCenter,intradius){intx=0;inty=radius;intp=1-radius;voidcirclePlotPoints(int,int,int,int);circlePlotPoints(xCenter,yCenter,x,y);while(x<y){x++if(p<0)p+=2*x+1;else{y--;p+=2*(x-y)+1;}circlePlotPoints(xCenter,yCenter,x,y);}}voidcirclePlotPoints(intxCenter,intyCenter,intx,inty){setpixel(xCenter+x,yCenter+y);setpixel(xCenter-x,yCenter+y);setpixel(xCenter+x,yCenter-y);setpixel(xCenter-x,yCenter-y);setpixel(xCenter+y,yCenter+x);setpixel(xCenter-y,yCenter+x);setpixel(xCenter+y,yCenter-x);setpixel(xCenter-y,yCenter-x);}Ex.半徑為20個像素的1/8圓.4.5Bresenham圓算法與Bresenham直線生成算法一樣，其基本思想：利用判別變量來判斷選擇最近的像素，判別變量僅用加減和移位就可計算出來同樣，只考慮1/8圓，x從０到R/21/2結(jié)束假設(shè)用該算法計算出第k個點(xk,yk),下一步需要決定像素位置是A(xk+1,yk), B(xk+1,yk-1)，其中xk+1=xk+1根據(jù)理論坐標點與A,B的距離大小選擇A或B. da=yk2-y2=yk2-r2+xk+12

db=y2-(yk-1)2=r2-xk+12-(yk-1)2

?d=da-db≥0，則下一像素取B(xk+1,yk)?d<0，則下一像素取A(xk+1,yk-1)決策參數(shù)：

pk=?d=2xk+12+(yk-1)2+yk2-2r2

pk+1=2(xk+1+1)2+(yk+1-1)2+yk+12-2r2

所以：

pk+1=pk+4xk+6+2(yk+12-yk2)-2(yk+1-yk)初始條件 起始點(x0,y0)＝(0,r)帶入上式：

p0=3-2rBresenham圓弧算法可表示為：

p0=3-2r xk+1=xk+1 yk+1=yk-1，pk+1=pk+4(xk-yk)+10當pk≥０

yk+1=yk，pk+1=pk+4xk+6，當pk<０Bresenham圓弧算法的C實現(xiàn)voidcircleBres(intxCenter,intyCenter,intradius){intx=0,y=radius,p=3-2*radius;voidcirclePlotPoints(int,int,int,int);circlePlotPoints(xCenter,yCenter,x,y);while(x<y){if(p<0)p+=(4*x+6);else{p+=(4*(x-y)+10);y--;}x++;circlePlotPoints(xCenter,yCenter,x,y);}}半徑為20個像素的1/8圓五、橢圓生成算法橢圓曲線的生成考慮長軸和短軸尺寸不同，可通過修改畫圓程序來實現(xiàn).5.1橢圓的特征.5.2中點橢圓算法.5.1橢圓的特征橢圓被定義為到兩個定點(焦點)的距離之和等于常數(shù)的點的集合。橢圓上任意點p(x,y)到兩個焦點的距離記為d1和d2，那么，橢圓方程可表示為：d1+d2=常數(shù)設(shè)兩個焦點坐標F1=(x1,y1)和F2=(x2,y2)來表示的橢圓方程：

[(x-x1)2+(y-y1)2]1/2+[(x-x2)2+(y-y2)2]1/2=常數(shù)改寫橢圓方程，則通用橢圓方程：

Ax2+By2+Cxy+Dx+Ey+F=0標準位置的橢圓：長軸和短軸與X和Y軸平行，橢圓中心可在(xc,yc)。標準位置橢圓方程：

[(x-xc)/rx]2+[(y-yc)/ry]2=1

其中：rx

和ry分別為長半軸和短半軸。極坐標表示：

x=xc+rxcosθ,y=yc+rysinθ標準位置的橢圓其在四分象限是對稱的，因此我們只需要計算一個四分象限的橢圓曲線位置，然后根據(jù)對稱性得到其余的部分。.5.2中點橢圓算法基本思想：計算橢圓中心在(0,0)的標準位置橢圓曲線的第一分象限的曲線部分的位置像素(x,y)，然后將點變換到橢圓中心在(xc,yc)。.5.2中點橢圓算法基本思想：計算橢圓中心在(0,0)的標準位置橢圓曲線的第一分象限的曲線部分的位置像素(x,y)，然后將點變換到橢圓中心在(xc,yc)。.5.2中點橢圓算法基本思想：計算橢圓中心在(0,0)的標準位置橢圓曲線的第一分象限的曲線部分的位置像素(x,y)，然后將點變換到橢圓中心在(xc,yc)。.5.2中點橢圓算法根據(jù)前面DDA算法的討論，當|m|≤1時，取x方向單位步長(1或-1)，相反，取y方向單位步長(1或-1)。因此，對于第一分象限的橢圓曲線分成兩部分：一部分曲線的斜率絕對值小于1和斜率絕對值大于1。并分別對兩段曲線分別取x方向步長和y方向取步長.這里可選擇(0,ry)或(rx,0)作為起點開始算法。以從(0,ry)開始從左到右進行。橢圓函數(shù)作為決策參數(shù)：

fellipse(x,y)=ry2x2+rx2y2-rx2ry2

該函數(shù)具有如下特性：

<0(x,y)位于橢圓邊界內(nèi)fellipse(x,y)=0(x,y)位于橢圓邊界上

>0(x,y)位于橢圓邊界外橢圓函數(shù)fellipse(x,y)作為中點橢圓算法的決策參數(shù)。在每個取樣位置，按照橢圓函數(shù)在沿橢圓軌跡兩個候選像素點的中點求值的符號選擇下一個像素從(0,ry)開始，在x方向取單位步長1直到斜率變?yōu)椤?1。橢圓的斜率：

dy/dx=-ry2x/rx2y兩段曲線采用不同的算法的分界點：

2ry2x=2rx2y對于第1段曲線設(shè)用該算法計算出點(xk,yk)，下一個點(xk+1,yk+1)為A(xk+1,yk)或B(xk+1,yk-1)，即右邊點或右下點。根據(jù)如下決策參數(shù)符號判斷： p1k=fellipse(xk+1,yk-0.5)=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2

下一點的判斷：當p1k<0，取A(xk+1,yk)，

yk+1=yk

當p1k≥0，取B(xk+1,yk-1)，

yk+1=yk-1其中xk+1=xk+1遞歸表達式：

p1k+1=p1k+2ry2(xk+1)+ry2+rx2[(yk+1-0.5)2-(yk-0.5)2]初始決策參數(shù)：將(x0,y0)=(0,ry)帶入:p10=fellipse(1,ry-0.5)=ry2-rx2ry+rx2/4該橢圓第一分象限的第一部分橢圓曲線的中點算法表示：

p10=ry2-rx2ry+rx2/4xk+1=xk+1yk+1=yk

，p1k+1=p1k+2ry2xk+1+ry2

當p1k<0yk+1=yk-1，p1k+1=p1k+2ry2xk+1+ry2-2rx2yk+1

當p1k≥0決策參數(shù)增量=2ry2xk+1+ry2當p1k<02ry2xk+1+ry2-2rx2yk+1當p1k≥0對于2ry2xk+1和2rx2yk+1本身又是一個增量表達式，2ry2xk+1增量始終為2ry2，而2rx2yk+1增量為0(當p1k<0)或-2rx2(當p1k≥0)，在起始位置(x0,y0)=(0,ry)，2ry2xk+1和2rx2yk+1的初始值分別為0和2rx2ry。然而對于第一分象限的第2段曲線，取y方向單位步長。在每一步，計算決策參數(shù)時取兩個候選水平像素的中點。設(shè)前一步取(xk,yk)，下一個點(xk+1,yk+1)的選擇：B(xk,yk-1)或A(xk+1,yk-1)，即下邊點或右下點。M(xk+0/5,yk-1)為AB的中點。根據(jù)如下決策參數(shù)符號判斷：

p2k=fellipse(xk+0.5,yk-1)=ry2(xk+0.5)2+rx2(yk-1)2-rx2ry2

取點的判斷：

p2k≤0，取(xk+1,yk-1),(xk+1,yk+1)=(xk+1,yk-1),

即右下點Ap2k>0，取(xk,yk-1),(xk+1,yk+1)=(xk,yk-1),

即下邊點B遞歸表達式：

p2k+1=p2k-2rx2(yk-1)+rx2+ry2[(xk+1+0.5)2-(xk+0.5)2]當從第一分象限橢圓的第1段曲線進入第2段曲線時，采用p2k作為決策參數(shù)，此時，p2k的初始點為第段曲線的最后計算點，設(shè)為(x0,y0)。則第二部分曲線的初始決策參數(shù):p20=fellipse(x0+0.5,y0-1)=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2

該橢圓第一分象限的第2段橢圓曲線的中點算法表示：

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2yk+1=yk-1xk+1=xk，p2k+1=p2k-2rx2yk+1+rx2,當p2k>0xk+1=xk+1，p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1

當p2k≤0決策參數(shù)增量=-2rx2yk+1+rx2當p2k>0-2rx2yk+1+rx2+2ry2xk+1當p2k≤0對于2rx2yk+1和2ry2xk+1本身又是一個增量表達式，2rx2yk+1增量始終為-2rx2，而2ry2xk+1增量為0(當p2k>0)或2ry2(當p2k≤0)，在起始位置(x0,y0)，2rx2yk+1和2ry2xk+1的初始值分別為2rx2y0和2ry2x0。中點橢圓算法步驟：1.輸入rx,ry和橢圓中心(xc,yc)，并得到中心在原點的橢圓上的第一個點。2.計算第一分象限的第1段橢圓曲線的決策參數(shù)的初值：

p10=ry2-rx2ry+rx2/43.在第1段曲線的每個xk處，從k=0開始，完成下列測試：假如當p1k<0，則下一個點為(xk+1,yk+1)=(xk+1,yk)，且：p1k+1=p1k+2ry2(xk+1)+ry2，否則，下一個點為(xk+1,yk+1)=(xk+1,yk-1)，且：p1k+1=p1k+2ry2(xk+1)+ry2-2rx2(yk-1)。且循環(huán)至2ry2x≥2rx2y，循環(huán)結(jié)束得到最后點(x0,y0)。4.使用第1段曲線計算最后得到的點(x0,y0)，來計算第2段曲線的初始決策參數(shù)：

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry25.在第2段曲線的每個yk處，從k=0開始，完成下列檢測：假如p2k>0，則下一個點為(xk+1,yk+1)=(xk,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2，否則下一個點為(xk+1,yk+1)=(xk+1,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2+2ry2(xk+1)，且循環(huán)至2rx2y=0即y=0。6.確定其它三個分象限中對稱的點。7.將每個計算出像素位置(x,y)移到中心在(xc,yc)的橢圓軌跡上，并按坐標畫點：x=x+xc，y=y+yc。中點橢圓算法的C實現(xiàn)#defineROUND(a)((int)(a+0.5))voidellipseMidpoint(intxCenter,intyCenter,intRx,intRy){intRx2=Rx*Rx,Ry2=Ry*Ry;inttwoRx2=2*Rx2,twoRy2=2*Ry2;intp,x=0,y=Ry,px=0,py=twoRx2*y；

voidellipsePlotPoints(int,int,int,int);ellipsePlotPoints(xCenter,yCenter,x,y)；

p=ROUND(Ry2-(Rx2*Ry)+(0.25*Rx2));

while(px<py){x++;px+=twoRy2;if(p<0)p+=Ry2+px;else{y--,py-=twoRx2;p+=Ry2+px-py;}ellipsePlotPoints(xCenter,yCenter,x,y);}/*section2*/p=ROUND(Ry2*(x+0.5)*(x+0.5)+Rx2*(y-1)*(y-1)-Rx2*Ry2);while(y>0){y--;py-=twoRx2;if(p>0)p+=Rx2-py;else{x++;px+=twoRy2;p+=Rx2-py+px;}ellipsePlotPoints(xCenter,yCenter,x,y);}}voidellipseMidPoints(intxCenter,intyCenter,intx,inty){setpixel(xCenter+x,yCenter+y);setpixel(xCenter-x,yCenter+y);setpixel(xCenter+x,yCenter-y);setpixel(xCenter-x,yCenter-y);}思考：1.由于第2段曲線的初始決策參數(shù)依賴于第1段曲線最后計算的點，因此兩個部分不能同時進行，如何修改一下算法，使兩部分曲線的計算可同時進行。2.對于非標準位置(長/短半軸不與坐標軸重合)的橢圓，如何實現(xiàn)？六、其它輸出圖元的生成點、線、圓是圖形設(shè)計中最基本的元素，此外，設(shè)計中還需要其它圖元，如曲線、文字和符號常用曲線：正弦函數(shù)曲線、指數(shù)函數(shù)曲線、多項式函數(shù)曲線、概率分布函數(shù)曲線及樣條函數(shù)曲線等。曲線生成與圓和橢圓相似。思考：如何繪制曲線，如正弦函數(shù)曲線。七、輸出圖元的屬性.7.1直線屬性.7.2曲線屬性.7.3顏色和灰度等級.7.4填充區(qū)域的屬性通常，任何影響圖元顯示方法的參數(shù)被稱為屬性參數(shù)。如顏色、大小等屬性是確定圖元的基本特性；其它則指出在特定條件下怎樣顯示圖元。如三維視圖的深度信息以及交互式對象選擇程序所需的可見性或可檢測性。這里我們僅考慮哪些控制圖元基本顯示特性的屬性，而不考慮特定條件。如線段可以是點線或虛線、粗線或細線以及藍色或其它顏色等。區(qū)域可用一種顏色或多色圖案填充。文本可從左到右閱讀方式顯示，沿屏幕對角線傾斜或按垂直列向顯示.7.1直線屬性直線段的基本屬性線型寬度顏色在一些軟件包中，線用可選擇的筆或刷來顯示。下面，考慮怎樣修改畫線程序來實現(xiàn)各種指定屬性。線型線型屬性可能包括實線、虛線和點線等。我們通過設(shè)置沿線路徑顯示的實線段的長度和間距來修改畫線算法，以生成各種類型的線。虛線可通過在實線段間插入與實線段等長的空白段來顯示；畫線的長度和空白段長度常作為用戶的選項來指定。點線，可通過生成很短的畫線和等于或大于畫線大小的空白段來顯示對于各種畫線、點線和點畫線，用像素掩模來指定實線段和空白段的長度。例如，掩模1111000可表示畫線長度為四個像素和中間空白段為3個像素的虛線。用固定數(shù)目的像素畫線會產(chǎn)生如圖所示的在不同方向不同長度的線段。為此，可按線的斜率來調(diào)整實心段和空白段的像素數(shù)目。另一個保持畫線等長的方法是將畫線看作為單獨的線段，將每條畫線的端點坐標定位后，調(diào)用沿畫線路徑計算像素位置的畫線程序。線寬線寬選擇的實現(xiàn)取決于輸出設(shè)備的能力。在視頻顯示器上的粗線可以用相鄰的平行線來顯示。在光柵實現(xiàn)中，標準線寬是用像Bresenham算法那樣在每個取樣位置處用一個像素來生成。其它寬度是作為標準線的正整數(shù)倍通過沿相鄰平行線路徑畫額外的像素而顯示的。對于斜率絕對值小于1的線，可修改畫線程序，通過在沿線的每個x位置畫像素的垂直段來顯示粗線。每段的像素數(shù)目等于線寬的整數(shù)值。在圖中，我們通過在原線段路徑之上生成一條平行線而畫出了雙倍線寬的線段。在每個位置x處，計算對應(yīng)的y坐標，并使用屏幕坐標(x,y)和(x,y+1)畫像素。通過交替地在單線寬度的上下畫像素就可以顯示線寬≥3的粗線對于斜率絕對值大于1的粗線，可以在水平段交替地畫線段路徑左邊和右邊像素形成粗線，如圖，其線寬為4，用水平段繪制。盡管通過繪制水平段或垂直段能快速地生成粗線，但線的顯示寬度(垂直于線段路徑測量)仍取決于線的斜率，45o線的顯示線寬只有垂直線或水平線的用水平段或垂直段實現(xiàn)寬度選擇的另一個問題是：不管斜率多少，所生成線段的端點是水平或垂直的。這對于較粗的線的影響更突出。我們可以通過添加“線帽”來調(diào)整線端的形狀以給出較好的外觀，如圖。線帽有方帽、圓帽和突方帽。方帽通過調(diào)整所構(gòu)成平行線的端點位置，使粗線的顯示具有垂直于線段路徑的正方形端點。假如指定線的斜率m，則粗線的方端的斜率-1/m。生成粗線的其它方法包括將顯示線段看作填充長方形，或用選定的筆或刷樣式來生成線段。生成粗折線需要一些額外的處理。通常，顯示單根折線段所用的方法不能生成光滑連接的折線段。我們可通過在線段端點進行額外處理來生成光滑連接的粗折線。圖顯示出了兩線段光滑連接的三種可能方法：斜角連接、圓連接和斜切連接。斜角連接通過延伸兩條線的外邊界直到它們相交來完成。圓連接通過用直徑等于線寬的圓弧邊界將兩線段間連接而成。斜切連接則是通過用方帽和在兩線段相交處的三角形間歇中填充來生成顏色當系統(tǒng)提供顏色(或亮度)選擇時，給出當前顏色索引的參數(shù)被包括在系統(tǒng)屬性表中。折線程序以當前顏色顯示折線，是通過用setPixel程序?qū)⑦@種顏色設(shè)置在幀緩沖器中沿線段路徑像素位置處得以實現(xiàn)。顏色選擇的數(shù)目取決于幀緩沖器中每個像素有效值的數(shù)目筆和畫刷有些圖形軟件包中，線可選擇筆或刷的方式來顯示。選項包括形狀、尺寸和式樣。如圖顯示的可能的筆和刷形狀。這些形狀可以以像素位置數(shù)值形式存儲在一個像素模板中，在必要時設(shè)置到線段路徑上。例如圖顯示的是一個長方形筆的像素模板，用這個模板的中心沿線段路徑運動可畫出相應(yīng)寬度的線段通過改變筆或刷的像素模板的尺寸，則使用該模板的筆或刷來生成的線段就可以有不同的寬度.7.2曲線屬性曲線屬性的參數(shù)與直線段相同，我們可用各種顏色、寬度、點劃模式和有效的筆或刷選擇來顯示曲線。采用畫線算法來適應(yīng)屬性選擇的方法也類似于畫直線。如圖,顯示的一個用模板11100來生成虛線圓弧。可用圓的對稱性生成圓的其它部分。如前面討論的一樣，各種寬度的光柵曲線可用水平或垂直像素段來顯示，曲線斜率的絕對值小于1，用垂直段；斜率絕對值大于1，用水平段。如圖示另一種顯示粗曲線的方法是填充兩條距離等于預(yù)定寬度的平行曲線路徑間的區(qū)域?？梢杂弥付ǖ那€路徑作為一條邊界，并在其內(nèi)側(cè)或外側(cè)建立第二條邊界來實現(xiàn)，然而，這樣的粗曲線會發(fā)生偏移，因此，通常在曲線路徑兩側(cè)以預(yù)定寬度的一半距離，設(shè)置兩條邊界曲線來保持曲線位置，如圖。曲線的筆或刷顯示可使用前面直線段中討論的相同方法來實現(xiàn)。當曲線斜率為1時，用這種長方形筆顯示的曲線會比較粗。因此，要顯示一致的曲線寬度可通過旋轉(zhuǎn)長方形筆以使其在沿曲線移動時與曲線斜率方向一致，或用圓弧筆來實現(xiàn).7.3顏色和灰度等級通用光柵掃描系統(tǒng)通常提供較多的顏色，而隨機掃描系統(tǒng)最多只能提供幾種顏色供選擇。顏色選項用0到某一正整數(shù)值編碼。對于CRT顯示器，這些顏色碼被轉(zhuǎn)換成電子束的強度等級。對于彩色繪圖儀，這些編碼將控制噴墨或選筆.顏色信息可以用兩種方法存儲在幀緩沖器中：1.將顏色碼直接存儲在幀緩沖器中.2.把顏色碼放在一個獨立的表(調(diào)色板)中并用像素值作為這個表的索引.利用直接存儲策略，一旦在應(yīng)用程序中指定某種顏色編碼，就在幀緩沖器中為要以那種顏色顯示的輸出圖元的每個組成像素設(shè)置為對應(yīng)的二進制值.例如，每個像素占3位存儲器時，它提供了最小數(shù)目的彩色顏色數(shù)，三位位置的每一位用來控制RGB顯示器中對應(yīng)電子槍的亮度等級(開或關(guān))，給緩沖器中每個像素增加位數(shù)將使可選擇的顏色數(shù)量增加，假如每個像素6位，則每支電子槍用2位，這允許三支電子槍的每一支具有四種不同的亮度，對每個屏幕像素共有64個有效顏色。對于1024×1024的分辨率，真彩色/全色(每個像素占24位)RGB系統(tǒng)需要幀緩沖器的存儲量：1024×1024×24bit=3Mbyte。彩色表是不需要增大幀緩沖器而又擴充顏色能力的一種變換方法顏色表圖顯示了在彩色查找表中存儲顏色值的一種方案。在該表中，幀緩沖器值用作彩色表的索引。在這個例子中，每個像素在幀緩沖器中占用8位，可引用表中256個表位置的任何一個，表中的每個表項可用24位來指定RGB顏色。擁有這種特殊查找表的系統(tǒng)，將允許用戶從將近1億7千萬種顏色的調(diào)色表中選擇任意256種顏色同時顯示。與真彩色系統(tǒng)相比，這種方案減少了可以同時顯示的顏色數(shù)目，但它也將緩沖器的容量需要減少到1M。有些圖形系統(tǒng)在幀緩沖器中為每個像素提供9位，允許用戶在每次顯示中能