第三章基本圖形的掃描轉(zhuǎn)換1掃描轉(zhuǎn)換的基本概念JackEltonBresenham簡(jiǎn)介直線的掃描轉(zhuǎn)換算法圓的掃描轉(zhuǎn)換算法本章學(xué)習(xí)目標(biāo)直線的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換本章小結(jié)本章內(nèi)容直線、圓、橢圓是二維場(chǎng)景中的最基本圖形。盡管MFC的CDC類已經(jīng)提供了相關(guān)的繪制函數(shù)，但直接使用這些函數(shù)仍然無(wú)法滿足真實(shí)感圖形繪制的要求。光柵掃描顯示器是畫(huà)點(diǎn)設(shè)備，基本圖形的光柵化就是在像素點(diǎn)陣中確定最佳逼近于理想圖形的像素點(diǎn)集，并用指定顏色顯示這些像素點(diǎn)集的過(guò)程。當(dāng)光柵化與按掃描線順序繪制圖形的過(guò)程結(jié)合在一起時(shí)，也稱為掃描轉(zhuǎn)換。本章從基本圖形的生成原理出發(fā)，使用繪制像素點(diǎn)函數(shù)實(shí)現(xiàn)基本圖形的掃描轉(zhuǎn)換。繪制像素點(diǎn)函數(shù)的原型為

BOOLSetPixelV(intx,inty,COLORREFcrColor);直線、圓、橢圓的掃描轉(zhuǎn)換主要使用Bresenham算法實(shí)現(xiàn)。JackEltonBresenham

Plottermovement

Bresenham算法最初是為數(shù)字繪圖儀提出，但同樣適用于CRT光柵顯示器。BresenhamretiredfromofserviceatIBMasaSeniorTechnicalStaffMemberin1987.Hetaughtfor16yearsatWinthropUniversity.Bresenham‘slinealgorithm,developedin1965,ishismostwell-knowninnovation.“Algorithmforcomputercontrolofadigitalplotter”。Itdetermineswhichpointsona2-dimensionalrastershouldbeplottedinordertoformastraightlinebetweentwogivenpoints,andiscommonlyusedtodrawlinesonacomputerscreen.Itisoneoftheearliestalgorithmsdiscoveredinthefieldofcomputergraphics.直線的掃描轉(zhuǎn)換是在屏幕像素點(diǎn)陣中確定最佳逼近于理想直線的像素點(diǎn)集的過(guò)程。計(jì)算機(jī)圖形學(xué)要求直線的繪制速度要快，即盡量使用加減法（增量算法），避免乘、除、開(kāi)方、三角等復(fù)雜運(yùn)算。最著名的算法是由J.E.Bresenham于1965年提出的Bresenham算法。3.1直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換光柵掃描顯示器的本質(zhì)決定它難以生成完美的直線段，也不能保證直線段精確地通過(guò)起點(diǎn)和終點(diǎn)。繪制直線段的基本要求：直線要直。要求具有精確的起點(diǎn)和終點(diǎn)。直線無(wú)方向性。從起點(diǎn)繪制到終點(diǎn)的直線段與從終點(diǎn)繪制到起點(diǎn)的直線段要重合。直線的繪制速度要快。即盡量使用加減法整數(shù)運(yùn)算，避免乘、除、開(kāi)方、三角等復(fù)雜運(yùn)算。Bresenham算法的特點(diǎn)：Bresenham算法是一個(gè)經(jīng)典的增量算法。在一個(gè)迭代算法中，如果每一步的x，y值是用前一步的值加上一個(gè)增量來(lái)獲得的，那么這種算法就稱為增量算法。Bresenham算法有幾種變體，計(jì)算方法略有不同。本章只介紹中點(diǎn)Bresenham算法（MidpointBresenhamAlgorithm）。對(duì)于直線，中點(diǎn)Bresenham算法與Bresenham算法產(chǎn)生同樣的像素點(diǎn)，而且還可以擴(kuò)展為更復(fù)雜的圖形掃描轉(zhuǎn)換算法，如繪制圓的中點(diǎn)Bresenham算法和繪制橢圓的中點(diǎn)Bresenham算法。3.1.1算法原理

直線的中點(diǎn)Bresenham算法的原理：每次在主位移方向上走一步，另一個(gè)方向上走不走步取決于中點(diǎn)誤差項(xiàng)的值。給定理想直線的起點(diǎn)坐標(biāo)為P0(x0,y0)，終點(diǎn)坐標(biāo)為P1(x1,y1),則直線的隱函數(shù)方程為：（3-1）

其中，直線的斜率：

直線水平方向位移：

直線垂直方向位移：理想直線將平面劃分成三個(gè)區(qū)域：對(duì)于直線上的點(diǎn)，F(xiàn)(x，y)＝0；對(duì)于直線上方的點(diǎn)，F(xiàn)（x，y）＞0；對(duì)于直線下方的點(diǎn)，F(xiàn)（x，y）＜0。

假設(shè)直線的斜率為0≤k≤1，則|△x|≥|△y|，x0<x1,y0<y1。所以確定x方向?yàn)橹魑灰品较?。按照Bresenham原理，x方向上每次加1，y方向上加不加1取決于中點(diǎn)誤差項(xiàng)的值。直線中點(diǎn)Bresenham算法原理假定直線的當(dāng)前點(diǎn)是P，沿主位移x方向走一步，下一點(diǎn)只能在Pu和Pd兩點(diǎn)中選取，Pu和Pd的中點(diǎn)為M。顯然，若中點(diǎn)M在理想直線的下方，則Pu點(diǎn)距離直線近，否則選取Pd。3.1.2構(gòu)造中點(diǎn)誤差項(xiàng)從Pi(xi,yi）點(diǎn)出發(fā)選取下一像素時(shí)，需將Pu和Pd的中點(diǎn)M(x

i＋1,yi＋0.5)代入隱函數(shù)方程，構(gòu)造中點(diǎn)誤差項(xiàng)di。（3-2）

（3-3）

3.1.3遞推公式

1.中點(diǎn)誤差項(xiàng)的遞推公式M(xi+2,yi+1.5）M(xi+2,yi+0.5)Pi(xi,yi）

（a）di<0（b）di≥0

中點(diǎn)的遞推Pi(xi,yi）PuPdPdPu

(1)當(dāng)d<0時(shí)

⑵當(dāng)d≥0時(shí)

（3-5）

（3-4）

直線的起點(diǎn)坐標(biāo)為P0(x0,y0)，x為主位移方向。因此，第一個(gè)中點(diǎn)是M(x0+1,y0+0.5)，相應(yīng)的di的初始值為：

其中，因?yàn)椋▁0，y0）在直線上，所以

則：

（3-6）

2.中點(diǎn)誤差項(xiàng)的初始值3.整數(shù)中點(diǎn)誤差項(xiàng)令fi=2di△x可去掉前面公式中的浮點(diǎn)數(shù)則有（3-7）（3-8）仍然根據(jù)（3-3）判斷下一個(gè)點(diǎn)的y值4.算法：x=x0;y=y0;dx=x1-x0;dy=y1-y0;f=dx-2*dy;//式(3-7)for(i=1;i<=dx+1;i++){setpixel(x,y,color);

//畫(huà)點(diǎn)x=x+1;if(f<0){y=y+1;//式（3-3）f=f+2*dx;｝//式（3-8）f=f-2*dy;}起點(diǎn)（2，1），終點(diǎn)（10，7），寫(xiě)出每步fi,xi,yi5.實(shí)例3.1.4任意斜率直線的一般性算法算法開(kāi)始假設(shè)了直線的斜率為0≤k≤1，則|△x|≥|△y|，x0<x1,y0<y1。除假設(shè)情況外，另外還有7種情況算法不能處理。k=-1k=10≤k≤1k=0|k|=∞k＜-1k＞1-1≤k＜0k>-10≤k≤1-1≤k＜0k＜-1直線斜率的對(duì)稱性3.1.4任意斜率直線一般性算法原算法做如下改動(dòng)：|△x|<|△y|情況處理當(dāng)|△x|<|△y|時(shí)，交換x與y，并設(shè)標(biāo)志變量interchange=1;否則interchange=0;原程序中：當(dāng)interchange=1時(shí)，x=x+1變成y=y+1，y=y+1變成x=x+1;(2)如果x0>x1，x=x+1變成x=x-1；一般地：令s1=sign(x1-x0),

x=x+1變成x=x+s1(3)同理，令s2=sign(y1-y0),

y=y+1變成y=y+s2intx=x0,y=y0;

int

dx=abs(x0-x1),dy=abs(y0-y1);

int

temp,interchange,f,i;

ints1,s2;

if(x1>x0)s1=1;elses1=-1;//sign(x1-x0)if(y1>y0)s2=1;elses2=-1;//sign(y1-y0)

if(dy>dx){temp=dx;

dx=dy;

dy=temp;interchange=1;}

elseinterchange=0;

具體算法（一）f=dx-2*dy;for(i=1;i<=dx;i++){setpixel(x,y,color);if(interchange==1)y=y+s2;elsex=x+s1;//x++;if(f<0){if(interchange==1)x=x+s1;elsey=y+s2;//y++f=f-2*dx;}f=f+2*dy;

}//for具體算法（二）后面講解的圓的中點(diǎn)Bresenham算法與橢圓的中點(diǎn)Bresenham算法，采用類似的步驟。直線是構(gòu)成復(fù)雜圖形的基本圖元，場(chǎng)景中的模型往往由成千上萬(wàn)條直線組成，所以直線的中點(diǎn)Bresenham算法是本章學(xué)習(xí)的重點(diǎn)，自定義CLine類來(lái)繪制直線段。直線的中點(diǎn)Bresenham算法小結(jié)：確定主位移方向。在主位移方向上每次加1，另一個(gè)方向上加不加1，取決于中點(diǎn)誤差項(xiàng)。計(jì)算f的初始值。區(qū)分f

<0與f≥0兩種情況，分別計(jì)算f的遞推公式。算法中只有整數(shù)加減運(yùn)算，效率很高3.2圓的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換是在屏幕像素點(diǎn)陣中確定最佳逼近于理想圓的像素點(diǎn)集的過(guò)程。圓的繪制可以使用簡(jiǎn)單方程畫(huà)圓算法或極坐標(biāo)畫(huà)圓算法，但這些算法涉及開(kāi)方運(yùn)算或三角運(yùn)算，效率很低。主要講解僅包含加減運(yùn)算的順時(shí)針繪制1/8圓的中點(diǎn)Bresenham算法原理，根據(jù)對(duì)稱性可以繪制整圓。圓的掃描轉(zhuǎn)換提出問(wèn)題：默認(rèn)的圓是圓心位于坐標(biāo)系原點(diǎn)，半徑為R的圓。屏幕設(shè)備坐標(biāo)系的原點(diǎn)位于左上角，繪制結(jié)果為1/4圓，需要進(jìn)行圓心平移或使用自定義坐標(biāo)系可以繪制整圓。圓是橢圓的特例，使用橢圓中點(diǎn)Bresenham算法也可繪制。設(shè)備坐標(biāo)系自定義坐標(biāo)系

圓心在原點(diǎn)、半徑為R的圓方程的隱函數(shù)表達(dá)式為：圓將平面劃分成三個(gè)區(qū)域：對(duì)于圓上的點(diǎn)，F(xiàn)(x，y)＝0；對(duì)于圓外的點(diǎn)，F(xiàn)（x，y）＞0；對(duì)于圓內(nèi)的點(diǎn)，F(xiàn)（x，y）＜0。根據(jù)圓的對(duì)稱性，可以用四條對(duì)稱軸x＝0，y＝0，x＝y(tǒng)，x＝－y將圓分成8等份。只要繪制出第一象限內(nèi)的1/8圓弧，根據(jù)對(duì)稱性就可繪制出整圓，這稱為八分法畫(huà)圓算法。假定第一象限內(nèi)的任意點(diǎn)為P(x,y)，可以順時(shí)針確定另外7個(gè)點(diǎn)：P(y,x)，P(-y,x)，P(x,-y)，P(-x,-y)，P(-y,-x)，P(y,-x)，P(-x,y)。

（3-9）

3.2.1算法原理P（-y，x）P（-y，-x）x=-yP（-x，-y）P（x，-y）P（y，-x）P（y，x）P（x，y）P（-x，y）x=yx=0y=0圓的對(duì)稱性

中點(diǎn)Bresenham算法要從(0,R)順時(shí)針確定最佳逼近于該段圓弧的像素點(diǎn)集。此段圓弧的斜率k處處滿足|k|＜1，即|△x|＞|△y|，所以x方向?yàn)橹魑灰品较?，因此中點(diǎn)Bresenham算法的原理簡(jiǎn)化如下：x方向上每次加1，y方向上減不減1取決于中點(diǎn)誤差項(xiàng)的值。假定圓上當(dāng)前點(diǎn)是Pi(xi,yi)，下一像素只能在Pu(x

i+1,yi)和Pd(x

i+1,yi-1)中選取。Pu和Pd的中點(diǎn)為M(x

i+1,yi-0.5)顯然，若M點(diǎn)在理想圓弧的下方，則Pu點(diǎn)離圓弧近，選取Pu；否則應(yīng)選取Pd。圓中點(diǎn)Bresenham算法原理3.2.2構(gòu)造中點(diǎn)誤差項(xiàng)

從P（xi，yi）開(kāi)始，為了進(jìn)行下一像素點(diǎn)的選取，需將Pu和Pd的中點(diǎn)M(xi+1,yi-0.5)代入隱函數(shù)，構(gòu)造中點(diǎn)誤差項(xiàng)：（3-10）

當(dāng)di<0時(shí)，中點(diǎn)M在圓內(nèi)，下一像素點(diǎn)應(yīng)選取Pu，即y方向上不退步；當(dāng)di>0時(shí)，中點(diǎn)M在圓外，下一像素點(diǎn)應(yīng)選取Pd，即y方向上退一步；當(dāng)di＝0時(shí)，中點(diǎn)M在圓上，Pu、Pd和圓的距離相等，選取Pu或Pd均可，約定取Pd。因此，

（3-11）1.中點(diǎn)誤差項(xiàng)的遞推公式

現(xiàn)在如果考慮主位移方向再走一步，應(yīng)該選擇哪個(gè)中點(diǎn)代入中點(diǎn)誤差項(xiàng)以決定下一步應(yīng)該選取的像素，分兩種情況討論。3.2.3遞推公式

Pi(xi,yi)M(xi+2,yi-0.5)Pi(xi,yi)M(xi+2,yi-1.5）(a)di<0(b)di≥0中點(diǎn)的遞推⑴當(dāng)d<0時(shí)，下一步的中點(diǎn)坐標(biāo)為：

（3-12）⑵當(dāng)d≥0時(shí)，下一步的中點(diǎn)坐標(biāo)為：（3-14）

圓的起點(diǎn)為P0（0，R），x為主位移方向。因此，第一個(gè)中點(diǎn)是（1，R-0.5），對(duì)應(yīng)的di的初始值為：

（3-15）

2.中點(diǎn)誤差項(xiàng)的初始值圓中點(diǎn)Bresenham算法voidCTestView::MBCircle(doubleR,CDC*pDC)//圓中點(diǎn)Bresenham算法{ doublex,y,d; d=1.25-R;x=0;y=R;

for(x=0;x<=y;x++) {

CirclePoint(x,y,pDC);//調(diào)用八分法畫(huà)圓子函數(shù)

if(d<0) d+=2*x+3;else { d+=2*(x-y)+5; y--; }}}voidCTestView::CirclePoint(doublex,doubley,CDC*pDC)//八分法畫(huà)圓子函數(shù){ //圓心坐標(biāo)

CP2pc=CP2((p0.x+p1.x)/2.0,(p0.y+p1.y)/2.0); //定義圓的邊界顏色

COLORREFclr=RGB(0,0,255);

pDC->SetPixelV(Round(x+pc.x),Round(y+pc.y),clr);//x,y

pDC->SetPixelV(Round(y+pc.x),Round(x+pc.y),clr);//y,x

pDC->SetPixelV(Round(y+pc.x),Round(-x+pc.y),clr);//y,-x

pDC->SetPixelV(Round(x+pc.x),Round(-y+pc.y),clr);//x,-y

pDC->SetPixelV(Round(-x+pc.x),Round(-y+pc.y),clr);//-x,-y

pDC->SetPixelV(Round(-y+pc.x),Round(-x+pc.y),clr);//-y,-x

pDC->SetPixelV(Round(-y+pc.x),Round(x+pc.y),clr);//-y,x

pDC->SetPixelV(Round(-x+pc.x),Round(y+pc.y),clr);//-x,y}直線、圓和橢圓作為二維場(chǎng)景中的基本圖形，其生成算法的優(yōu)劣對(duì)整個(gè)圖形系統(tǒng)的效率至關(guān)重要。直線段的掃描轉(zhuǎn)換是計(jì)算機(jī)圖形學(xué)中最基本的算法。中點(diǎn)Bresenham

算法避免了復(fù)雜運(yùn)算，使用了增量算法，使單點(diǎn)基本圖形生成算法已無(wú)優(yōu)化的余地，獲得了廣泛的應(yīng)用。本章重點(diǎn)掌握算法的基本原理與形成過(guò)程，借鑒其思想，算法的效率極有可能是靠一點(diǎn)一滴積累形成的，在編程時(shí)需要對(duì)算法設(shè)計(jì)精益求精。本章小結(jié)習(xí)題3計(jì)算起點(diǎn)坐標(biāo)為（0,0），終點(diǎn)坐標(biāo)（12,9）直線的中點(diǎn)Bresenham算法的每一步坐標(biāo)值以及中點(diǎn)偏差判別式d的值，填入表3-1中，并用黑色繪制圖3