孔令德

第三章基本圖形的掃描轉(zhuǎn)換掃描轉(zhuǎn)換的基本概念JackEltonBresenham簡(jiǎn)介直線的掃描轉(zhuǎn)換算法圓的掃描轉(zhuǎn)換算法橢圓的掃描轉(zhuǎn)換算法Wu反走樣算法本章學(xué)習(xí)目標(biāo)3.1直線的掃描轉(zhuǎn)換3.2圓的掃描轉(zhuǎn)換3.3橢圓的掃描轉(zhuǎn)換3.4反走樣技術(shù)3.5Wu反走樣算法3.6本章小結(jié)本章內(nèi)容直線、圓和橢圓是圖形設(shè)計(jì)的基本圖形元素。盡管在MFC的CDC類中已有繪制這三種基本圖元的成員函數(shù)，但是基于光柵掃描顯示器的真實(shí)感圖形生成技術(shù)要求使用繪制像素點(diǎn)函數(shù)來(lái)逐點(diǎn)繪制這些基本圖元。光柵掃描顯示器是畫點(diǎn)設(shè)備，不能從像素點(diǎn)陣的一個(gè)可編址像素點(diǎn)直接繪制一段直線到達(dá)另一個(gè)可編址的像素點(diǎn)，只能用靠近這段直線的像素點(diǎn)集來(lái)近似地表示。光柵掃描顯示器的繪圖過(guò)程就是在像素點(diǎn)陣中確定最佳逼近于理想圖元的像素點(diǎn)集，并用指定顏色顯示這些像素點(diǎn)集的過(guò)程，這稱為圖形的掃描轉(zhuǎ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ò)程。如圖3-1所示。計(jì)算機(jī)圖形學(xué)要求直線的繪制速度要快，盡量使用加減法，避免乘除、開方、三角等復(fù)雜運(yùn)算。直線的掃描轉(zhuǎn)換有許多算法，如數(shù)值微分法、逐點(diǎn)比較法等，最著名的是中點(diǎn)Bresenham算法。3.1直線的掃描轉(zhuǎn)換圖3-1直線的掃描轉(zhuǎn)換理想直線

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）

其中，直線的斜率：

直線水平方向位移：

直線垂直方向位移：b是直線在y軸上的截距理想直線將平面劃分成三個(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，所以確定x方向?yàn)橹魑灰品较?。按照Bresenham原理，x方向上每次加1，y方向上加不加1取決于中點(diǎn)誤差項(xiàng)的值。

圖3-2直線中點(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)（3-2）

（3-3）

從Pi（xi，yi）點(diǎn)走第一步后，為了選取下一個(gè)像素點(diǎn)，需將Pu和Pd的中點(diǎn)M（xi＋1，yi＋0.5）代入直線的隱函數(shù)方程，構(gòu)造中點(diǎn)誤差項(xiàng)di。當(dāng)di<0時(shí)，下一像素點(diǎn)應(yīng)選取Pu，當(dāng)di>0時(shí)，下一像素點(diǎn)應(yīng)選取Pd，當(dāng)di＝0時(shí)，選取Pu或Pd均可，約定取Pd，如圖3-2所示。

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圖3-3中點(diǎn)誤差項(xiàng)的遞推Pi(xi,yi）PuPdPdPuM(xi+1,yi+0.5）M(xi+1,yi+0.5）

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

⑵當(dāng)di≥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.1.4整數(shù)化處理中點(diǎn)Bresenham算法有一個(gè)缺點(diǎn)：在計(jì)算誤差項(xiàng)di時(shí)，其初始值和遞推公式分別包含有小數(shù)0.5和斜率k。計(jì)算過(guò)程中使用了除法，不利于硬件實(shí)現(xiàn)。由于中點(diǎn)Bresenham算法中只用到誤差項(xiàng)di的符號(hào)，可以使用正整數(shù)乘以di來(lái)擺脫小數(shù)運(yùn)算。這樣得到了繪制直線的整數(shù)中點(diǎn)Bresenham算法。整數(shù)化處理后，誤差項(xiàng)的初始值為當(dāng)di<0時(shí)，誤差項(xiàng)的遞推公式為當(dāng)di≥0時(shí)，誤差項(xiàng)的遞推公式為

（3-7）

（3-8）（3-9）中點(diǎn)Bresenham算法并不僅用于繪制一段直線，常用于繪制折線構(gòu)成的多邊形。假定多邊形各條邊的顏色為單色且不相同，如圖3-4（a）所示，需要考慮直線段連接點(diǎn)的正確著色問(wèn)題。對(duì)每段折線的兩個(gè)端點(diǎn)一般采用“起點(diǎn)閉區(qū)間、終點(diǎn)開區(qū)間”的處理方法，且要考慮折線繪制的方向如圖3-4（b）圖所示。使用本算法繪制的三角形邊界放大效果如圖3-5所示。（a）折線的方向（b）端點(diǎn)處理圖3-4折線繪制三角形圖3-5三角形邊界放大效果圖3.2圓的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換就是在屏幕像素點(diǎn)陣中確定最佳逼近于理想圓的像素點(diǎn)集的過(guò)程。圓的繪制可以使用簡(jiǎn)單方程畫圓算法或極坐標(biāo)畫圓算法，但這些算法涉及開方運(yùn)算或者三角運(yùn)算，效率很低。本節(jié)主要講解僅包含加減操作的順時(shí)針繪制1/8圓的中點(diǎn)Bresenham算法原理。圖3-6圓的掃描轉(zhuǎn)換

圓心在原點(diǎn)、半徑為R的圓方程的隱函數(shù)表達(dá)式為：圓將平面劃分成3個(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，如圖3-6所示。。根據(jù)圓的對(duì)稱性，可以用四條對(duì)稱軸x＝0，y＝0，x＝y(tǒng)，x＝－y將圓分成8等份。只要繪制出第一象限內(nèi)的1/8圓弧，根據(jù)對(duì)稱性就可繪制出整圓，這稱為八分法畫圓算法。假定第一象限內(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-10）

3.2.1算法原理首先考慮掃描轉(zhuǎn)換圖3-7中陰影部分所示的第一象限內(nèi)的1/8圓弧。此時(shí)中點(diǎn)Bresenham算法要從(0,R)到(，)順時(shí)針確定最佳逼近于該段圓弧的像素x=-yx=yP（-x,y）P(x,y）P（-y,x）P(y,x)P（-y,-x）P（y,-x）P（-x,-y）P（x,-y）圖3-7圓的對(duì)稱性點(diǎn)集。此段圓弧的斜率k處處滿足|k|≤1，即：|△x|≥|△y|，因此：x方向?yàn)橹魑灰品较?，中點(diǎn)Bresenham算法的原理簡(jiǎn)化如下：x方向上每次加1，y方向上減不減1取決于中點(diǎn)誤差項(xiàng)的值。圖3-8圓中點(diǎn)Bresenham算法原理假定圓弧上當(dāng)前點(diǎn)是Pi(xi,yi)，下一像素只能在Pu（xi＋1，yi）和Pd（xi＋1，yi－1）兩點(diǎn)中選取，如圖3-8所示。Pu和Pd的中點(diǎn)為M（xi＋1，yi－0.5）顯然，若M點(diǎn)在理想圓弧的下方，則Pu點(diǎn)離圓弧近，選取Pu；否則應(yīng)選取Pd。3.2.2構(gòu)造中點(diǎn)誤差項(xiàng)

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

當(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-12）1.中點(diǎn)誤差項(xiàng)的遞推公式

現(xiàn)在如果考慮主位移方向再走一步，應(yīng)該選擇哪個(gè)中點(diǎn)代入中點(diǎn)誤差項(xiàng)以決定下一步應(yīng)該選取的像素，分兩種情況討論，如圖3-9所示。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

圖3-9中點(diǎn)誤差項(xiàng)的遞推⑴當(dāng)d<0時(shí)，下一步的中點(diǎn)坐標(biāo)

M（xi＋2，yi－0.5），下一步中點(diǎn)誤差項(xiàng)為：

（3-13）⑵當(dāng)d≥0時(shí)，下一步的中點(diǎn)坐標(biāo)M（xi＋2,yi－1.5）。下一步中點(diǎn)誤差項(xiàng)為（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算法3.3橢圓的掃描轉(zhuǎn)換橢圓的掃描轉(zhuǎn)換是在屏幕像素點(diǎn)陣中選取最佳逼近于理想橢圓像素點(diǎn)集的過(guò)程。橢圓是長(zhǎng)半軸和短半軸不相等的圓，橢圓的掃描轉(zhuǎn)換與圓的掃描轉(zhuǎn)換有類似之處。本節(jié)主要講解順時(shí)針繪制1/4橢圓的中點(diǎn)Bresenham算法原理，根據(jù)對(duì)稱性可以繪制完整橢圓。圖3-10橢圓的掃描轉(zhuǎn)換F(x,y)<0F(x,y)=0F(x,y)>0理想橢圓提出問(wèn)題：默認(rèn)的橢圓是圓心位于坐標(biāo)系原點(diǎn)，長(zhǎng)半軸為a、短半軸為b的橢圓。需要進(jìn)行圓心平移或使用自定義坐標(biāo)系可以繪制橢圓。如果“x方向上每次加1，y方向上減不減1取決于中點(diǎn)誤差項(xiàng)的值”。繪制結(jié)果是圓，如何能繪制為橢圓？3.3.1算法原理圓心在原點(diǎn)、長(zhǎng)半軸為a、短半軸為b的橢圓方程的隱函數(shù)表達(dá)式為：（3-16）

橢圓將平面劃分成三個(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，如圖3-10所示?？紤]到橢圓的對(duì)稱性，可以用對(duì)稱軸x＝0，y＝0，把橢圓分成4等份。只要繪制出第一象限內(nèi)的1/4橢圓弧，如圖3-10的陰影部分Ⅰ和Ⅱ所示，根據(jù)對(duì)稱性就可繪制出整個(gè)橢圓，這稱為四分法繪制橢圓算法。已知第一象限內(nèi)的點(diǎn)P(x,y)，可以順時(shí)針得到另外3個(gè)對(duì)稱點(diǎn)：P(x,-y)，P(-x,-y)和P(-x,y)。P(-x,y)P(x,y)P(-x,-y)P(x,-y)圖3-11橢圓的對(duì)稱性ACBX方向分量y方向分量法矢量圖3-12橢圓的法矢量在處理第一象限的1/4橢圓弧時(shí)，進(jìn)一步以法矢量?jī)蓚€(gè)分量相等的點(diǎn)分為兩部分：上半部分Ⅰ和下半部分Ⅱ。橢圓上任意一點(diǎn)P(x,y)處的法矢量為

（3-17）式中，i和j是沿x軸向和沿y軸向的單位矢量。在圖3-12所示的部分Ⅰ的AC橢圓弧上，法矢量的x方向分量小于y方向分量，斜率k處處滿足|k|＜1，|△x|＞|△y|，所以x方向?yàn)橹魑灰品较颍?/p>

在C點(diǎn)，法矢量的x方向分量等于y方向分量，斜率k滿足k＝－1，|△x|＝|△y|；

在部分Ⅱ的CB橢圓弧上，法矢量的x方向分量大于y方向分量，斜率k處處滿足|k|＞1，|△y|＞|△x|，所以y方向?yàn)橹魑灰品较?。本算法需要分Ⅰ和Ⅱ兩個(gè)部分，按順時(shí)針方向繪制1/4橢圓。在上半部分Ⅰ，x方向上每次加1，y方向上減1不減1取決于中點(diǎn)誤差項(xiàng)的值；在下半部分Ⅱ，y方向上每次減1，x方向上加不加1取決于中點(diǎn)誤差項(xiàng)的值。橢圓的中點(diǎn)Bresenham的原理先考慮圖3-13所示部分Ⅰ的AC段橢圓弧。此時(shí)中點(diǎn)Bresenham算法要從點(diǎn)A（0，b）向點(diǎn)C（，），沿順時(shí)針方向確定最佳逼近于該段橢圓弧的像素點(diǎn)集。由于x方向?yàn)橹魑灰品较颍俣ó?dāng)前點(diǎn)是Pi(xi,yi)，下一步只能在正右方的像素Pu（xi+1，yi）和右下方的像素Pd（xi+1，yi-1）兩點(diǎn)中選取。，PPuPdPPlPA（0，b）B（a，0）ⅠⅡCPrP圖3-13橢圓中點(diǎn)Bresenham算法原理再考慮圖3-13所示部分Ⅱ的CB段橢圓弧。此時(shí)中點(diǎn)Bresenham繪制橢圓算法要從點(diǎn)C（，），向點(diǎn)B(a,0)，沿順時(shí)針方向確定最佳逼近于該段橢圓弧的像素點(diǎn)集。由于y方向?yàn)橹魑灰品较?，假定?dāng)前點(diǎn)是Pi（xi，yi），下一步只能在正下方的像素Pl（xi，yi-1)和右下方的像素Pr（xi+1，yi-1）兩點(diǎn)中選取。下標(biāo)l代表left，r代表right。3.3.2構(gòu)造上半部分Ⅰ的中點(diǎn)誤差項(xiàng)在上半部分Ⅰ，x方向每次加1，y方向上減不減1取決于中點(diǎn)誤差項(xiàng)的值。從Pi(xi,yi)點(diǎn)出發(fā)選取下一像素時(shí)，需將Pu(xi+1，yi)和Pd(x

i+1,yi-1)的中點(diǎn)M(xi+1,yi-0.5)代入隱函數(shù)，構(gòu)造中點(diǎn)誤差項(xiàng)（3-18）

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

（3-19）3.3.3上半部分Ⅰ的遞推公式

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

如果考慮主位移方向再走一步，應(yīng)該選擇哪個(gè)中點(diǎn)代入中點(diǎn)誤差項(xiàng)以決定下一步應(yīng)該選取的像素，分兩種情況討論。Pi(xi,yi)M(xi+2,yi-0.5)Pi(xi,yi)M(xi+2,yi-1.5）(a)di<0(b)di≥0圖3-15上半部分中點(diǎn)誤差項(xiàng)的遞推（3-20）(1)當(dāng)d1i<0，下一步的中點(diǎn)坐標(biāo)為M（xi＋2，yi－0.5）。下一步的中點(diǎn)誤差項(xiàng)為：

（2)當(dāng)d1i≥0時(shí)，下一步中點(diǎn)坐標(biāo)為M（xi＋2，yi－1.5）。下一步中點(diǎn)誤差項(xiàng)為：

（3-21）2.中點(diǎn)誤差項(xiàng)的初始值上半部分橢圓的起點(diǎn)為A（0，b），因此，第一個(gè)中點(diǎn)是（1，b－0.5），對(duì)應(yīng)的d1i的初值為

（3-22）3.3.4構(gòu)造下半部分Ⅱ的中點(diǎn)誤差項(xiàng)

在下半部分Ⅱ，主位移方向發(fā)生變化，中點(diǎn)Bresenham算法原理為：y方向上每次減1，x方向上加1不加1取決于中點(diǎn)誤差項(xiàng)的值。從上半部分Ⅰ的終止點(diǎn)Pi(xi,yi)出發(fā)選取下一像素時(shí)，需將Pl(xi,yi-1)和Pr(xi+1,yi-1)的中點(diǎn)M(xi+0.5,yi-1)代入隱函數(shù)，構(gòu)造中點(diǎn)誤差項(xiàng)（3-23）因此，（3-21）當(dāng)d2i<0時(shí)，中點(diǎn)M在橢圓內(nèi)，下一像素點(diǎn)應(yīng)選取Pr，即x方向上走一步；當(dāng)d2i>0時(shí)，中點(diǎn)M在橢圓外，下一像素點(diǎn)應(yīng)選取Pl，即x方向上不走步；當(dāng)d2i＝0時(shí)，中點(diǎn)M在橢圓上，Pl、Pr和橢圓的距離相等，選取Pl或Pr均可，約定取Pl。3.3.5下半部分Ⅱ的遞推公式

現(xiàn)在如果考慮主位移方向再走一步，應(yīng)該選擇哪個(gè)中點(diǎn)代入中點(diǎn)誤差項(xiàng)以決定應(yīng)該選取的像素。分兩種情況討論。（a）d2i<0（b）d2i≥0圖3-17下半部分中點(diǎn)誤差項(xiàng)的遞推Pi(xi,yi)M(xi+1.5,yi-2)Pi(xi,yi)M(xi+0.5,yi-2)中點(diǎn)誤差項(xiàng)的遞推公式⑴當(dāng)d2i<0，下一步的中點(diǎn)坐標(biāo)為M（xi＋1.5，yi－2）。下一步的中點(diǎn)誤差項(xiàng)為：

（3-26）⑵當(dāng)d2i≥0時(shí)，下一步中點(diǎn)坐標(biāo)為M（xi＋0.5，yi－2）。下一步的中點(diǎn)誤差項(xiàng)為：

（3-25）2.中點(diǎn)誤差項(xiàng)的初始值在上半部分Ⅰ，法矢量的x向分量小于y向分量；在C點(diǎn)，法矢量的x向分量等于y向分量；在下半部分Ⅱ，法矢量的x向分量大于y向分量。則對(duì)于上半部分橢圓上一點(diǎn)P（xi，yi），如果其當(dāng)前中點(diǎn)M(xi+1,yi-0.5)，滿足x向分量小于y向分量（3-27）而在下一個(gè)中點(diǎn)，不等號(hào)改變方向，則說(shuō)明橢圓從上半部分Ⅰ轉(zhuǎn)入了下半部分Ⅱ。Pl(xi,yi)Pl(xi,yi-1)Pd(xi+1,yi-1)=Pr(xi+1,yi-1)MⅡ(xi+0.5,yi-1)MⅠ(xi+1,yi-0.5)Pu(xi+1,yi)圖3-18確定下半部分的初始值

假定Pi(xi,yi)點(diǎn)是橢圓上半部分Ⅰ的最后一個(gè)像素，MⅠ(xi+1,yi-0.5)是用于判斷選取Pu和Pd像素的中點(diǎn)。由于下一像素轉(zhuǎn)入了下半部分Ⅱ，其中點(diǎn)改為判斷Pl和Pr的中點(diǎn)MⅡ(xi+0.5,yi-1)。所以下半部分的初值d20為（3-28）橢圓中點(diǎn)Bresenham算法3.4反走樣技術(shù)直線掃描轉(zhuǎn)換算法在處理非水平、非垂直且非45°的直線段時(shí)會(huì)出現(xiàn)鋸齒，這是因?yàn)橹本€段在光柵掃描顯示器上顯示的圖像是由一系列亮度相同而面積不為零的離散像素點(diǎn)構(gòu)成的。這種由離散量表示連續(xù)量而引起的失真稱為走樣（aliasing）。用于減輕走樣現(xiàn)象的技術(shù)稱為反走樣（anti-aliasing,AA）或者抗鋸齒。走樣是理想直線（理想直線寬度為零）掃描轉(zhuǎn)換后（真實(shí)像素點(diǎn)面積不為零）的必然結(jié)果。走樣是光柵掃描顯示器的一種固有現(xiàn)象，不可避免，只能減輕。不走樣直線走樣直線未開抗鋸齒開啟抗鋸齒“word”繪制的斜線“畫圖”繪制的斜線圖3-24中，從硬件角度把顯示器的分辯率提高了一倍。由于每個(gè)鋸齒在x方向和y方向都只有原先分辨率的一半，所以看上去走樣現(xiàn)象有所改善。雖然如此，硬件反走樣技術(shù)由于受到硬件條件和成本的限制，實(shí)現(xiàn)起來(lái)較為困難，很難達(dá)到理想的反走樣效果。反走樣技術(shù)主要分為兩類：

一類是硬件技術(shù)，通過(guò)提高顯示器的分辨率來(lái)實(shí)現(xiàn)；另一類是軟件技術(shù)，通過(guò)改進(jìn)軟件算法來(lái)實(shí)現(xiàn)。圖3-24顯示器的分辨率提高一倍的效果圖

軟件反走樣技術(shù)主要是加權(quán)區(qū)域采樣。算法的實(shí)質(zhì)是利用人眼視覺特性，通過(guò)加權(quán)平均的方法，調(diào)節(jié)像素的亮度和灰度，以產(chǎn)生模糊的邊界，從而達(dá)到較好的視覺效果以消除“鋸齒”。加權(quán)參數(shù)可以選擇距離、面積和體積等。下面主要講解直線的距離加權(quán)反走樣算法，關(guān)于面積加權(quán)和體積加權(quán)反走樣算法請(qǐng)讀者參考相關(guān)文獻(xiàn)。3.5Wu反走樣算法1998年獲得加拿大UWO卓越研究教授獎(jiǎng)，2000年獲得丹麥Monsteds研究獎(jiǎng)（每年僅一人），2003年獲得芬蘭諾基亞國(guó)際研究獎(jiǎng)（每年三人）等。武筱林于1991年在computerGraphics上提出“EfficientAntialiasingTechnique”。

武筱林（XiaolinWu）教授1982年畢業(yè)于武漢大學(xué)，1988年獲得加拿大卡爾加里大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位，現(xiàn)任加拿大麥克馬斯特大學(xué)電子與計(jì)算機(jī)工程系終身教授，并擔(dān)任加拿大NSERC-DALSA數(shù)字影院首席科學(xué)家。3.5.1算法原理P6P4P2P3P1P5F1F3距離理想直線0.8個(gè)像素遠(yuǎn)的像素亮度為80％距離理想直線0.2個(gè)像素遠(yuǎn)的像素亮度為20％距離理想直線0.45個(gè)像素遠(yuǎn)的像素亮度為45％距離理想直線0.1個(gè)像素遠(yuǎn)的像素亮度為10％距離理想直線0.55個(gè)像素遠(yuǎn)的像素亮度為55％距離理想直線0.9個(gè)像素遠(yuǎn)的像素亮度為90％AB圖3-25距離加權(quán)反走樣算法原理F1F2F3

Wu反走樣算法是采用空間混色原理來(lái)對(duì)走樣進(jìn)行修正。空間混色原理指出，人眼對(duì)某一區(qū)域顏色的識(shí)別是取這個(gè)區(qū)域顏色的平均值。Wu反走樣算法原理是對(duì)于理想直線上的任一點(diǎn)，同時(shí)以兩個(gè)不同亮度級(jí)別的相鄰像素來(lái)表示。理想直線段上的點(diǎn)F1，掃描轉(zhuǎn)換后可用像素點(diǎn)P1和像素點(diǎn)P4以不同的亮度級(jí)別共同顯示，像素點(diǎn)離理想直線段越近，其亮度值越小，像素越暗；像素點(diǎn)離理想直線段越遠(yuǎn)，其亮度值就越大，像素越亮，但二者的亮度級(jí)別之和等于像素F1的灰度值。從圖3-25可知，Wu算法是用兩個(gè)相鄰像素來(lái)共同表示理想直線段上的一個(gè)點(diǎn)，依據(jù)兩個(gè)像素與理想直線段的距離而對(duì)其亮度等級(jí)進(jìn)行調(diào)整，使所繪制的直線段達(dá)到視覺上消除鋸齒的效果。實(shí)際使用中，兩個(gè)像素寬度的直線反走樣的效果較好，視覺效果上直線的寬度會(huì)有所減小，看起來(lái)好像是一個(gè)像素寬度的直線。3.5.2構(gòu)造距離誤差項(xiàng)

Pi(xi,yi)Fi(xi+1,ei）Pu(xi+1,yi+1)Pd(xi+1,yi)圖3-26Wu反走樣算法設(shè)通過(guò)原點(diǎn)的直線方程為y＝kx（3-29）式中，k為直線的斜率，假定0≤k≤1。設(shè)理想直線段的當(dāng)前像素點(diǎn)為Pi(xi,yi)，在主位移x方向上走一步，下一像素點(diǎn)只能在Pu（xi+1，yi+1）和Pd（xi+1，yi）兩點(diǎn)中選取，如圖3-26所示。

理想直線段與Pu和Pd像素中心連線的交點(diǎn)為Fi。ei為Fi與Pd的距離。設(shè)Pd（xi+1，yi）像素的亮度級(jí)別為RGB（ei×255，ei×255，ei×255），則Pu（xi+1，yi+1）像素的亮度級(jí)別為RGB（（1-ei）×255，（1-ei）×255，（1-ei）×255）。當(dāng)ei>0.5時(shí)，直線更接近于像素點(diǎn)Pu；當(dāng)ei<0.5時(shí)，直線更接近于像素點(diǎn)Pd；當(dāng)ei=0.5時(shí)，直線與Pu、Pd點(diǎn)的距離相等，約定取Pd。

（3-30）誤差項(xiàng)ei的初始值為k。主位移方向上每走一步，有ei+1＝ei+k。當(dāng)ei≥1.0時(shí)，相當(dāng)于y方向上走一步，即yi+1=yi+1，此時(shí)將ei減1，即ei+1=ei-1。3.5.3計(jì)算機(jī)化if(0.0<=k&&k<=1.0)//繪制0≤k≤1{for(p=P0,e=k;p.x<P1.x;p.x++){COLORREFcd=CRGB(e,e,e);//Pd像素顏色COLORREFcu=CRGB((1.0-e),(1.0-e),(1.0-e)););//Pu像素顏色pDC->SetPixelV(Round(p.x),Round(p.y),RGB(cd.red*255,cd.green*255,cd.blue*255));pDC->SetPixelV(Round(p.x),Round(p.y+1),RGB(cu