第三講：基本圖元輸出

2008.9.16第三講：

基本圖元的光柵化（1）

OutputPrimitives

圖像可以有多種方式來描述，在光柵設(shè)備上，任何的圖形都可以用一個(gè)指定亮度的各位置點(diǎn)的集合來表示。另一方面我們也可以用一系列基本的圖形對(duì)象來表示，這些圖形對(duì)象的的顏色和形狀可以用像素點(diǎn)陣或一系列基本的幾何結(jié)構(gòu)來描述。例如線段和內(nèi)部填充顏色的多邊形，顯示場(chǎng)景的時(shí)候，可以將像素點(diǎn)陣裝入貞緩存，或者將定義的基本幾何結(jié)構(gòu)掃描轉(zhuǎn)換為像素的形式寫入貞緩存。一些圖形軟件包提供了一些基本函數(shù)用于描述輸出基本幾何結(jié)構(gòu)，這樣的基本幾何結(jié)構(gòu)叫做基本輸出圖元。利用這些基本輸出圖元可以組成復(fù)雜物體的顯示。最簡(jiǎn)單的基本圖元是點(diǎn)和線，基本圖元的是通過指定圖元的坐標(biāo)、顏色等要顯示的信息來定義的。將這樣定義的基本圖元按照其屬性轉(zhuǎn)換為像素點(diǎn)陣的過程稱為光柵化3.1點(diǎn)和線在CRT顯示器中，點(diǎn)的繪制是將程序中點(diǎn)的坐標(biāo)轉(zhuǎn)化為屏幕上確定的位置，當(dāng)掃描至該位置點(diǎn)時(shí)，開啟電子槍點(diǎn)亮該點(diǎn)熒光。在隨即掃描顯示器中，點(diǎn)在顯示列表中定義，根據(jù)點(diǎn)的坐標(biāo)產(chǎn)生偏轉(zhuǎn)電壓，控制電子槍的偏轉(zhuǎn)并點(diǎn)亮該點(diǎn)的熒光。線的繪制是根據(jù)定義線的兩個(gè)端點(diǎn)，插值計(jì)算中間點(diǎn)的位置，并點(diǎn)亮這些中間點(diǎn)。在隨即掃描設(shè)備中，可以產(chǎn)生連續(xù)的中間點(diǎn)繪制出光滑的線段。在CRT設(shè)備中，需要將直線離散化成若干個(gè)點(diǎn)，根據(jù)線段的直線方程計(jì)算出這些離散的中間點(diǎn)位置，并在掃描這些點(diǎn)的位置上開啟電子槍點(diǎn)亮熒光屏。3.1點(diǎn)和線線的離散化表示點(diǎn)在屏幕上的位置坐標(biāo)用像素為單位，點(diǎn)的像素坐標(biāo)只能是整數(shù)。

所以，通過計(jì)算得到的中間點(diǎn)在屏幕上的坐標(biāo)都要取整數(shù)，如在線段上某點(diǎn)上計(jì)算的坐標(biāo)是（10.48，20.51），則點(diǎn)在屏幕上的位置是（10，21）。3.2畫線算法任何圖元的繪制算法都要遵循的一個(gè)原則:盡量使繪制速度加快，加快繪制速度的一個(gè)途徑就是盡量減少浮點(diǎn)運(yùn)算和乘除運(yùn)算。繪制線的基本思想是沿水平或垂直方向，依次增加一個(gè)像素的長(zhǎng)度，計(jì)算出相應(yīng)的另一個(gè)方向個(gè)上的增量，從而確定線上的某一個(gè)點(diǎn)的屏幕坐標(biāo)，電子槍點(diǎn)亮該點(diǎn)。3.2.1DDA算法（digitaldrflerentialanalyzer）

假設(shè)定義直線段的兩個(gè)端點(diǎn)的坐標(biāo)為（x1,y1),（x2,y2），直線的斜截方程為

y=mx+b3.2畫線算法

得：ｍ＝（y2-y1）／（x2-x1）

b=y1-mx1設(shè)在ｘ方向上的增量為⊿x，則

⊿ｙ＝ｍ⊿x①⊿x＝⊿ｙ/ｍ②若|m|<=1則以⊿x作為步進(jìn)的基礎(chǔ)，取⊿x=1，計(jì)算相應(yīng)的y坐標(biāo)，由①得

yk+1=yk+m|m|<=1，按x軸方向采樣xy3.2畫線算法

若|m|>1,則以⊿y為步進(jìn)的基礎(chǔ)，取⊿y=1，計(jì)算相應(yīng)的x坐標(biāo)，由②得

xk+1=xk+1/m假設(shè)已經(jīng)定義了底層函數(shù)Setpixel(x,y)，此函數(shù)用于向貞緩存中坐標(biāo)為（x,y）處按指定的顏色寫入顏色值，則DDA算法可描述如下。|m|>1，按y軸方向采樣3.2畫線算法voidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,；

intdy=yb-ya,；intsteps,k;floatxincrement,yincrement；floatx=xa,;floaty=ya;if(abs(dx)>abs(dy)steps=abs(dx);elsesteps=abs(dy);xIncrement=dx/

(float)steps;yIncrement=dy/(float)steps;setpixel(xa,ya)；for(k=0;k<steps;k++){x+=xIncrment;y+=yIncrement;setpixel(round(x),round(y))；//函數(shù)round(x)為將x四舍五入

}}DDA算法的特點(diǎn)？——消除了乘法，但是有誤差積累和浮點(diǎn)計(jì)算。3.2畫線算法3.2.2Bresenham算法

Bresenham算法的優(yōu)點(diǎn)是指使用整形的增量來計(jì)算點(diǎn)的坐標(biāo)，所以速度更快，也易于硬件實(shí)現(xiàn)。123456754321

以斜率小于1的直線為例，如右圖是（1，1）到（6，4）的一條直線段，當(dāng)我們沿x軸每次遞增1采樣像素，在繪制第二個(gè)點(diǎn)時(shí)，需要選擇是（2，2）還是（2，1），Bresenham算法就是計(jì)算一個(gè)決策參數(shù)用于判斷哪一個(gè)像素點(diǎn)離直線最近。3.2畫線算法以m<1為例，如下圖所示。在Xk+1處

y=mXk+1+b=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；

d1d2xkXk+1Xk+2ykyk+1y當(dāng)m<1時(shí)3.2畫線算法

如果△d>0則在處選擇點(diǎn)（Xk+1,

yk+1），否則選擇(Xk+1,

yk)。取△x=xb-xa△y=yb-ya則m=△y/△x(xa,

ya）和(xb,

yb）是線段的兩個(gè)端點(diǎn)。

d1d2xkXk+1Xk+2ykyk+1y當(dāng)m<1時(shí)3.2畫線算法引入?yún)?shù)

pk=△x△d=△x(d1-d2)=△x(2m(xk+1)-2yk+2b-1)=2△yxk-2△xyk+2△y+△x(2b-1)，①因△x>0，所以pk和△d同號(hào)，可作為判斷△d正負(fù)號(hào)的參數(shù)。這里2△y+△x(2b-1）是常數(shù)，設(shè)

c=2△y+△x(2b-1)由①得

pk=△x△d=2△yxk-2△xyk+c②同樣：pk+1=2△yxk+1-2△xyk+1+cpk+1–pk=2△y(xk+1-xk）-2△x(yk+1-yk)△x=xb-xa△y=yb-yam=△y/△x3.2畫線算法xk+1=xk+1pk+1=pk+2△y-2△x(yk+1-yk)

當(dāng)pk>0時(shí)，yk+1-yk=1

pk+1=pk+2(△y-△x)

當(dāng)pk<0時(shí)，yk+1-yk=0

pk+1=pk+2△y

根據(jù)②式可得

p0=2△yxa-2△x(mxa+b)+2△y+△x(2b-1)==2△yxa-2△x(△y/△x)xa-2△xb+2△y+2△xb-△x=2△y-△xp0是從線段的起點(diǎn)x0后的第一個(gè)采樣點(diǎn)的決策值

pk+1–pk=2△y(xk+1-xk)-2△x(yk+1-yk)3.2畫線算法Bresenham算法的優(yōu)點(diǎn)從pk的計(jì)算公式可以看出，Bresenham算法只進(jìn)行加減運(yùn)算，并且只進(jìn)行的整數(shù)的運(yùn)算，所以運(yùn)算速度很高，并且易于用硬件實(shí)現(xiàn)。3.2畫線算法Bresenham算法的實(shí)現(xiàn)(0<m<1，xb>xa)

voidLineBres(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya;intp=2*dy-dx;inttwoDy=2*dy；

inttwoDyDx=2*(dy-dx);intx=xa,y=ya,xEnd;xEnd=xb;setpixel(x,y);

pk>0時(shí)，pk+1=pk+2(△y-△x)當(dāng)pk<0時(shí)，pk+1=pk+2△yP0=2△y-△x3.2畫線算法while(x<xEnd){x++;if(p<0)p+=twoDy;else{y++;＊

p+=twoDyDx;}setpixel(x,y);}}對(duì)于斜率大于1的情況下，將此算法調(diào)換x,y次序即可，對(duì)于m<0的情況下，將＊處的y++改為y--即可,而對(duì)于垂直和水平線可直接畫出線3.3貞緩沖的寫入前面我們用setpixel(x,y)函數(shù)在貞緩存的(x,y)處寫入顏色亮度。貞緩存在邏輯上是一個(gè)二維數(shù)組，物理上是一個(gè)一維的連續(xù)空間，所以在setpixel(x,y)中要計(jì)算具體的內(nèi)存地址。下面介紹在掃描過程中貞緩存的內(nèi)存地址計(jì)算。設(shè)（xmax，ymax)是光柵顯示器的最大橫坐標(biāo)和最大縱坐標(biāo)（也是貞緩存矩陣的寬度和高度）。任意點(diǎn)（x,y)的地址為：

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

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

addr(x+1,y+1)=addr(x,y)+xmax+2從(x,y)對(duì)豎直方向跳到下一條掃描線(x,y+1)的幀緩沖器地址的計(jì)算公式為：

addr(x,y+1)=addr(x,y)+xmax+1

這樣，在光柵掃描過程中按掃描順序，以增量的方式計(jì)算貞緩存地址，就避免了乘法計(jì)算。3.4圓的生成算法圓是圖形中常用的圖形元素，多數(shù)的圖形軟件中都包含了生成圓和圓弧的過程。圓的方程：

(x-xc)2+(y-yc)2=r2圓的最簡(jiǎn)單的繪制方法是沿一個(gè)方向遞增，計(jì)算出另一個(gè)方向上的坐標(biāo)。

y=(r2-(x-xc)2)?+yc

但是這樣畫出來的原在某些位置有很多斷點(diǎn)，計(jì)算量也很大。3.4圓的生成算法另一種方法是采用極坐標(biāo)法

x=rcosθ y=rsinθ 0≤θ≤360θ按一定的增量步進(jìn)，θ較大時(shí)，可以用沿著圓弧畫直線來代替圓弧。為了減少計(jì)算量，可以只畫出1/4圓或1/8圓，其他部分按對(duì)稱計(jì)算得到。但是這種方法同樣計(jì)算量非常大。3.4.1中點(diǎn)畫圓算法和光柵畫線算法中一樣，以單位間隔取樣并在每個(gè)步長(zhǎng)中確定離指定圓最近的像素位置。3.4圓的生成算法

只考慮1/8圓，x從０到（R/2）1/2結(jié)束.、首先，定義一個(gè)圓函數(shù)：

fcircle(x,y)=x2+y2-r2①則可按如下規(guī)則判斷任意點(diǎn)（x,y)在圓上的位置

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

>0(x,y)位于圓邊界外3.4圓的生成算法如圖，為了求下一個(gè)掃描點(diǎn)的位置，將下一個(gè)掃描點(diǎn)的兩個(gè)候選點(diǎn)(xk+1,yk)，（xk+1,yk-1）的中點(diǎn)坐標(biāo)(xk+1,yk-0.5)代入①式，如果在在圓外或圓上，則選擇(xk+1,yk），否則選（xk+1,yk-1）引入決策參數(shù)pkpk=fcircle(xk+1,yk-0.5)=xk+12+(yk-0.5)2-r2②

同樣：

pk+1=(xk+1+1)2+(yk+1-0.5)2-r2③候選點(diǎn)中點(diǎn)3.4圓的生成算法②-③得pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1很明顯，yk+1的值取決于pk的符號(hào)。

pk>0時(shí)yk+1=yk-1pk<0時(shí)yk+1=yk所以

pk+2xk+1+1pk<0（增量為2xk+1+1）pk+1=pk+2xk+1+1-2yk+1pk≥0（增量為2xk+1-2yk+1+1）3.4圓的生成算法起始位置(x0,y0)=(0,r)處的決策參數(shù)為

p0=fcircle(1,r-0.5)=5/4–r如果r為整數(shù)的話，可以舍入

p0=1–r

這是因?yàn)槠浜笥?jì)算pk時(shí)增量都是整數(shù)，所以這樣的舍入不影響pk的符號(hào)。中點(diǎn)畫圓算法的步驟：

1.輸入圓半徑r和圓心(xc,yc),并得到圓心在原點(diǎn)的圓周上的第一點(diǎn)為:(x0,y0)=(0,r)2.計(jì)算決策參數(shù)的初始值：p0=5/4–r3.4圓的生成算法3.在每個(gè)xk位置處，從k=0開始，完成下列檢測(cè)：假如pk<0，中心在(0,0)的圓的下一個(gè)點(diǎn)為(xk+1,yk)，且

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

否則，圓的下一個(gè)點(diǎn)為(xk+1,yk-1)，且

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

其中：2xk+1=2xk+1，2yk+1=2yk-24.確定在其它7個(gè)8分圓中的對(duì)稱點(diǎn)

5.將每個(gè)計(jì)算出的像素位置(x,y)移動(dòng)到中心在(xc,yc)的圓路徑上，并畫坐標(biāo)值：

x=xc+xy=yc+y6.重復(fù)步驟3到5，直至x≥y。3.4圓的生成算法中點(diǎn)圓算法的C實(shí)現(xiàn)：voidcircleMidpoint(intxCenter,intyCenter,intradius){intx=0;inty=radius;intp=1-radius;circlePlotPoints(xCenter,yCenter,x,y);//畫出第一個(gè)點(diǎn)

while(x<y){x++if(p<0)p+=2*x+1;else{y--;p+=2*(x-y)+1;}circlePlotPoints(xCenter,yCenter,x,y);}}

pk+2xk+1+1pk<0pk+1=pk+2xk+1+1-2yk+1pk≥03.4圓的生成算法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);}3.5橢圓的生成算法橢圓的特點(diǎn)橢圓被定義為到兩個(gè)定點(diǎn)(焦點(diǎn))的距離之和等于常數(shù)的點(diǎn)的集合。橢圓上任意點(diǎn)p(x,y)到兩個(gè)焦點(diǎn)的距離記為d1和d2，那么，橢圓方程可表示為：

d1+d2=常數(shù)

設(shè)兩個(gè)焦點(diǎn)坐標(biāo)F1=(x1,y1)和

F2=(x2,y2)來表示的橢圓方程：

[(x-x1)2+(y-y1)2]1/2+[(x-x2)2+(y-y2)2]1/2=常數(shù)本節(jié)內(nèi)容不作要求3.5橢圓的生成算法標(biāo)準(zhǔn)位置的橢圓：長(zhǎng)軸和短軸與X和Y軸平行，橢圓中心可在(xc,yc)。標(biāo)準(zhǔn)位置橢圓方程：

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

①

其中：rx

和ry分別為長(zhǎng)半軸和短半軸。在平面坐標(biāo)系中橢圓在四個(gè)象限中是對(duì)稱的，所以只需要計(jì)算完整一個(gè)象限內(nèi)的點(diǎn)。橢圓中點(diǎn)算法

只考慮橢圓原心在坐標(biāo)原點(diǎn)的標(biāo)準(zhǔn)橢圓，通過將計(jì)算后的坐標(biāo)平移可以得到圓心不在坐標(biāo)系原點(diǎn)的橢圓。和圓的中點(diǎn)算法相似，通過計(jì)算兩個(gè)候選點(diǎn)的中點(diǎn)是否在圓內(nèi)來判斷兩個(gè)候選點(diǎn)中哪一個(gè)離橢圓最近。3.5橢圓的生成算法安橢圓上切線的斜率將第一象限的橢圓劃分為兩個(gè)遞增區(qū)域區(qū)域，如圖，區(qū)域1，沿x方向依次遞增，區(qū)域2沿y方向依次遞增。兩個(gè)區(qū)域的分界點(diǎn)是該點(diǎn)斜率為-1定義橢圓函數(shù)，

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

圓心為（0,0)

fellipse(x,y)=ry2x2+rx2y2-rx2ry2② <0(x,y)位于橢圓邊界內(nèi)

fellipse(x,y)=0(x,y)位于橢圓邊界上

>0(x,y)位于橢圓邊界外斜率為-1123.5橢圓的生成算法由②式兩邊對(duì)x求導(dǎo)數(shù)得

dy/dx=-ry2x/rx2y

在橢圓上斜率為-1的點(diǎn)即為兩個(gè)遞增區(qū)域的分界點(diǎn)所以從區(qū)域1轉(zhuǎn)為區(qū)域2的分界點(diǎn)為

2ry2x=2rx2y

當(dāng)2ry2x<2rx2y時(shí)位于1區(qū)域，當(dāng)2ry2x>2rx2y時(shí)位于2區(qū)域斜率為-1123.5橢圓的生成算法首先考慮區(qū)域1的情況和圓的中點(diǎn)畫法相同，引入決策參數(shù)

p1k=fellipse(xk+1,yk-0.5)=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2③同樣

p1k+1=p1k+2ry2(xk+1)+ry2+rx2[(yk+1-0.5)2-(yk-0.5)2]其中yk+1的值取決于p1k的符號(hào)p1k+1=p1k+2ry2xk+1+ry2

當(dāng)p1k<0p1k+1=p1k+2ry2xk+1+ry2-2rx2yk+1當(dāng)p1k≥0將(x0,y0)=(0,ry)帶入③式求得初始位置的參數(shù)p10=fellipse(1,ry-0.5)=ry2-rx2ry+rx2/43.5橢圓的生成算法用同樣的方法可以計(jì)算出區(qū)域2內(nèi)的決策參數(shù)公式

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2yk+1=yk-1p2k+1=p2k-2rx2yk+1+rx2,當(dāng)p2k>0p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1當(dāng)p2k≤0中點(diǎn)橢圓算法步驟：

1.輸入rx,ry和橢圓中心(xc,yc)，并得到中心在原點(diǎn)的橢圓上的第一個(gè)點(diǎn)。

2.計(jì)算第一分象限的第1段橢圓曲線的決策參數(shù)的初值：

p10=ry2-rx2ry+rx2/43.5橢圓的生成算法3.在第1段曲線的每個(gè)xk處，從k=0開始，完成下列測(cè)試：假如當(dāng)p1k<0，則下一個(gè)點(diǎn)為(xk+1,yk+1)=(xk+1,yk)，且：p1k+1=p1k+2ry2(xk+1)+ry2，否則，下一個(gè)點(diǎn)為(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é)束得到最后點(diǎn)(x0,y0)。4.使用第1段曲線計(jì)算最后得到的點(diǎn)(x0,y0)，來計(jì)算第2段曲線的初始決策參數(shù)：

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry25.在第2段曲線的每個(gè)yk處，從k=0開始，完成下列檢測(cè)：假如p2k>0，則下一個(gè)點(diǎn)為(xk+1,yk+1)=(xk,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2，否則下一個(gè)點(diǎn)為(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.確定其它三個(gè)分象限中對(duì)稱的點(diǎn)。7.將每個(gè)計(jì)算出像素位置(x,y)移到中心在(xc,yc)的橢圓軌跡上，并按坐標(biāo)畫點(diǎn)：x=x+xc，y=y+yc。3.6其他曲線生成方法各種曲線在建模、動(dòng)畫運(yùn)動(dòng)軌跡的指