1、杭州師范學院本科畢業論文反走樣技術的研究與實現反走樣技術的研究與實現說明書論文目 錄摘要iabstract i第一章 引言11.1研究背景11.2 編程實驗環境2第二章 反走樣概述52.1 過取樣技術52.2 區域取樣72.3 wu像素反走樣122.4點取樣142.5象素移相14第三章 反走樣算法的改進153.1 多段直線反走樣算法153.2 圓反走樣算法 18 3.3位圖反走樣19第四章 總結與展望23 4.1總結234.2進一步改進設想23參考文獻25第一章 引 言1.1研究背景光柵圖形顯示器是目前使用最廣泛的圖形顯示器，因為它具有以下優點：光柵掃描顯示器具有固定的刷新順序，掃描從屏幕的左

2、上角開始，從左到右，從上到下的順序進行刷新，從而刷新控制部件得以簡化，節約了成本。在光柵顯示系統中，構成圖形的最小圖形元素是像素，這樣只要計算屏幕上位于給定區域以內的所有像素，并且賦予一定的顏色，就完成了圖形的繪制。光柵顯示器中的圖形由像素構成，而每一個像素又可呈現出多級灰度或不同的顏色值，顏色豐富，顯示出來的圖形具有更好的視覺效果。光柵掃描顯示器是一個畫點設備，與圖形的復雜度無關，刷新頻率固定，因此不會象隨機掃描顯示器那樣出現閃爍現象，人眼看上去更舒服。但光柵顯示器也有它的缺陷，圖形信號是連續的，而光柵顯示系統中用來表示圖形的卻是一個個離散的像素。用離散的像素來表示連續的圖形時會出現失真，也

3、就稱為走樣，如圖1.1所示。圖1.1鋸齒狀邊界光柵顯示系統為何會出現走樣呢？光柵圖形顯示器是一個畫點設備，被顯示的線段、字符、圖形及背景色都按像素點一一存儲在幀緩沖存儲器中。當我們要畫一條直線時，它通常不可能完全精確地從一個可編址的像素點畫一條直線到另一個可編址的像素點，只可能用盡可能靠近這條直線路徑的像素點集來近似地表示這條直線。顯然只有畫水平線、垂直線時，像素點集在直線路徑上的位置才是準確的，其他情況下的直線均或多或少地存在階梯狀（鋸齒狀）的現象。光柵圖形的走樣現象除了上述鋸齒狀邊界外，還有圖形細節失真，狹小圖形遺失等現象。 圖1.2 圖形細節失真在光柵顯示器上顯示如圖1.2(a)所示的細

4、長矩形時，出現了圖形細節失真，其結果如圖1.2(b)所示，原細長的矩形被顯示成了加寬的矩形。圖1.3 狹小圖形的遺失由于光柵系統中表示圖形的最小單位是一個像素，圖形中那些比像素更窄的細節丟失了，這就出現了圖形細節失真現象。在圖1.3中，一些狹小的圖形分布在兩條掃描線之間，由于它不覆蓋任何一個像素中心，故不會被顯示出來。當這些狹小的圖形進行運動時，覆蓋像素中心時被顯示出來，不覆蓋像素中心時不被顯示出來。這樣在運動的過程中時隱時現，產生閃爍。為了提高圖形的顯示質量，需要減少或消除上述走樣現象。用于減少或消除這種走樣現象的技術，稱為反走樣（antialiasing）。研究如何消除或減緩這類走樣現象，

5、給人視覺上產生更舒適光滑的圖形，在圖形界面已成為人機交互主流方式的今天，具有一定的應用價值。 反走樣技術能提高圖形的顯示質量，因此在很多畫圖軟件中也采用了這種技術。優軟電腦有限公司設計推出的新一代繪畫程序-優軟精靈畫筆2.0，在原有的各種繪畫功能上，添加了一系列全新設計的繪畫工具；可以打開外來jpg，tag，tiff，gif，bmp文件；更新三維立體窗口系統；對壓力感應筆高效率支持，速度和流暢度達到專業軟件水準，讓用戶的體會更加細膩逼真。它的精妙之處在于具有細筆尖反走樣功能，所以使細筆畫更細致更漂亮。 反走樣技術不僅能提高圖形顯示質量,而且在反走樣漢字方面也有很好的效果。由于漢字的筆畫很多,而

6、且大多數非水平非垂直,也會產生較嚴重的走樣現象。圖1.4中第1 個字為追蹤出的輪廓,第2 個為顯示的原始矢量字符。第3 個為反走樣處理后的矢量字符。圖1.4矢量字體輪廓的反走樣由此可見，反走樣技術在實際應用中有十分重要的意義。另外, 在處理紋理圖形, 以及在動畫中閃爍的細小物體圖形等問題中反走樣技術都得到了廣泛運用。1.2 編程實驗環境 本文采用的實驗環境的是c+ builder 6。c+ builder由著名的borland公司開發，是windows環境下功能強大的可視化c+開發環境，它全面實現了ansic+標準，并提供了自己的擴展，并且兼容pc計算機上的兩種最常用的c+編譯器，即borla

7、ndc+和visualc+。borland c+和visualc+的程序幾乎不用做任何修改，就可以在c+ builder下編譯、運行。下面主要介紹在論文中使用最頻繁的、與圖形圖象處理密切相關的組件及其屬性和方法。1.2.1 tcolor在計算機圖形處理軟件中，通常顏色是根據紅、綠、藍三種顏色的飽和度來定義的，這種模型稱為rgb模型。任何顏色都是紅、綠、藍三種基本色的不同組合組成，因此每種顏色都可以用紅、綠、藍基本色來表示。red、green、blue用來表示基本色構成的三個分量，他們的取值為0-255，最小值表示沒有顏色，最大值255表示最高的飽和度。 tcolor類型用于定義一個對象的顏色，

8、很多組件的顏色屬性就是tcolor類型。同時c+ builder定義了一些常用的顏色常量，可在程序中直接使用。比如clred，clgreen等。1.2.2 tcanvas在c+ builder中提供了一個tcanvas對象，它封裝了windows應用程序在圖形輸出方面所需要的大多數gdi對象和繪圖命令。在這個區域上，程序可實現各種繪圖功能，很多圖形組件（如timage、tpaintbox）的畫布（canvas）屬性都是一個tcanvas對象。 tcanvas的屬性和方法很多，最常用的有：l tcanvas的屬性(1)pixels屬性 canvas的pixels屬性可以用來去頂像素的顏色。可以利

9、用pixels屬性來獲得某一點的顏色值，也可以通過它來設置某一點的顏色值，這個屬性在反走樣算法中起了相當重要的作用。 如要獲得坐標（20，20）的顏色值，可以使用下面的代碼： tcolor color; color=canvas-pixels2020；如果要將坐標點（10，20）的顏色設置為紅色，可以使用如下代碼：canvas-pixels1020=clred；(2)畫筆屬性 tcanvas的畫筆（pen）屬性是一個tpen對象。在用畫布劃線的時候，需要設置畫筆的屬性。對每一個畫筆均可以選擇不同的寬度，顏色，線型。我的論文中用到了顏色（color）屬性。 該屬性用于控制線的顏色，可以使用預定義

10、的顏色或設置自己的顏色，例如： canvas-pen-color=clblue； canvas-pen-color=tcolor (rgb(125,0,0)；(3)畫刷屬性 canvas的畫刷（brush）屬性是一個tbrush對象，它封裝了標準的windows刷子對象。畫刷可以利用顏色和圖案來填充矩形、多邊形和圓等。使用畫刷的color屬性可以設置畫刷的顏色，默認的畫刷顏色是clwhite。例如： canvas-brush-color=clred；這個屬性在清屏方法起著主要作用。(4)cliprect屬性 cliprect屬性用于定義一個畫圖的矩形區域.在定義了一個剪切區域后,即使畫的圖形大

11、于這個cliprect,也不會畫到這個區域的外面,同時fillrect屬性可以用來填充矩形區域的顏色。l tcanvas的方法 (1)畫直線 繪制直線涉及到兩個方法：moveto和lineto。moveto（int startx,int starty）的任務是設置當前畫筆的位置到（startx,starty），而不進行任何繪圖工作。然后可以調用lineto（int endx，int endy）來畫直線。它從當前畫筆的位置畫一條直線到點（endx，endy），并將當前的畫筆位置改變為（endx，endy）。 （2）畫橢圓弧線繪制橢圓弧線的方法比繪制直線方法要復雜一些。下面是最基本的橢圓弧線繪制函

12、數：arc(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4);arc方法畫一段橢圓弧，橢圓由（x1，y1），（x2，y2）兩點所確定的矩形所決定。弧的起點是橢圓圓周和橢圓中心與（x3，y3）連線的交點。弧的終點是橢圓圓周和橢圓中心與（x4，y4）連線的交點，以逆時針方向畫弧。在位圖的反走樣算法中所畫的弧線都是由該函數實現的。 （3）繪制矩形 rectangle的具體形式如下：rectangle（int x1, int y1, int x2, int y2）; rectangle方法是在畫布上用當前畫刷繪制矩形，其中（

13、x1，y1）是矩形的左上角，（x2，y2）是矩形的右下角。如果設置brush的style模式為bsclear,則可以繪制未填充的矩形。同時在論文中經常會用到清屏這個功能，它就是調用了fillrect方法，它是用指定的畫刷填充矩形，并且繪制的矩形沒有邊框。具體形式如下：fillrect（const windows:trect &rect）; 第二章 反走樣技術概述在光柵顯示器上顯示圖形時，直線段或圖形邊界或多或少會呈鋸齒狀。原因是圖形信號是連續的，而在光柵顯示系統中，用來表示圖形的卻是一個個離散的象素。這種用離散量表示連續量引起的失真現象稱之為走樣(aliasing)，走樣是伴隨著光柵顯示系統而

14、出現的，也是數字化的必然產物。用于減少或消除這種效果的技術稱為反走樣(antialiasing)。第一章中已經介紹了光柵圖形的走樣現象除了階梯狀的邊界外，還有圖形細節失真(圖形中的那些比象素更窄的細節變寬)，狹小圖形遺失等現象。常用的反走樣方法主要有：提高分辨率、區域采樣和加權區域采樣等。下面將對他們進行介紹。2.1 過取樣技術反走樣的方法很多，一種簡單的反走樣方法是以較高的分辨率顯示對象，如圖2.1。假設把顯示器分辨率提高一倍，直線經過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。這種反走樣方法是以4倍的存儲器代價和掃描轉換時間獲得的

15、。因此，增加分辨率雖然簡單，但是不經濟的方法，而且它也只能減輕而不能消除鋸齒問題。但是它的思想給我們以后的反走樣方法一定的啟示。 圖2.1 提高顯示分辨率一種可行的反走樣方法：在較高分辨率下用點取樣方法計算，然后對幾個像素的屬性進行平均得到較低分辨率下的像素屬性。這種技術稱為過取樣（supersampling），或后濾波（postfiltering）。該技術是把顯示器看成是比實際更細的網格來增加取樣率，然后根據這種更細的網格使用取樣點來確定每個屏幕像素合適的亮度等級。 反走樣的另一種方法是根據圖形對象在每個像素點上的覆蓋程度率來確定像素點的亮度，這種計算覆蓋率的反走樣技術稱為區域取樣（area

16、 sampling），或前濾波（prefiltering）。2.1.1 提高分辨率方法過取樣方式的一個簡單實現是用較高的分辨率進行計算，如圖2.2，在x方向和y 方向上把分辨率提高一倍，使每個像素都對應4個子像素，然后掃描轉換求得各子像素的顏色亮度，在對4個像素的顏色亮度進行平均，得到較低分辨率下的像素顏色亮度。由于像素中可供選擇的子像素最大數目是4，因此，該例中提供的亮度等級數是5。如圖2.2中，編號為1和7的像素亮度級別是1，編號為2，3，4，5和6的像素亮度是2。通過這個方法為圖中的每個像素設定不同的灰度值，可以使顯示出來的直線看起來平滑一些，達到減少走樣現象。6753412圖2.2 簡

17、單的過取樣方式2.1.2基于加權模板的過取樣另一種過取樣方式（重疊過取樣），如圖2.3，假設顯示器分辨率為m*n，其中m=4，n=3，首先把顯示窗口劃分為（2m+1）*（2n+1）個像素，然后通過掃描轉換求得各子像素的顏色值，在對為于子像素中心及四周的9個子像素的顏色值進行平均，最后得到顯示像素的顏色亮度值。 由于接近像素區域中心的子像素在決定像素的顏色亮度值中發揮著重要的作用，因此過取樣算法中采用了加權平均的方法來計算顯示像素的顏色亮度值（基于加權模板的過取樣）。圖2.4示出了3*3像素分割常采用的加權模板。中心子像素的權是角子像素的4倍，是其他子像素的2倍，中心子像素的加權系數是1/4，頂

18、部和底部及兩側子像素的加權系數是1/8，而角子像素的加權系數是1/16。000000000000121242121圖2.3 另一種過取樣方式圖 2.4 加權模板2.1.3過取樣算法的實現 過取樣的一種簡單方法就是在較高的分辨率下進行計算，掃描轉換求得各子像素的顏色亮度，然后對子像素的顏色亮度進行平均，得到較低分辨率下的像素顏色亮度。由于接近像素區域中心的子像素在決定像素的顏色亮度值中發揮著重要的作用，因此過取樣的另一種算法采用了加權平均的方法來計算顯示像素的顏色亮度值。不管是哪一種方法都需要在內存中建立一個比現在大幾倍的圖，便于對像素取樣，取得像素的亮度值。具體實現的算法如下：void sup

19、ersamplingline(int xa, int ya, int xb, int yb,boolean weighted) int dx = xb-xa+1, dy = yb-ya+1, x,y,xs,ys,i,j,s, w33= 1,2,1, 2,4,2, 1,2,1; byte gray; graphics:tbitmap * big_bmp; big_bmp = new graphics:tbitmap(); big_bmp-width = 3*dx; big_bmp-height = 3*dy; /設置白底色 big_bmp-canvas-brush-color = clwhite

20、; big_bmp-canvas-fillrect(big_bmp-canvas-cliprect); big_bmp-canvas-refresh(); /設置綠筆 big_bmp-canvas-pen-color = clgreen; big_bmp-canvas-moveto(1,1); big_bmp-canvas-lineto(3*dx-1,3*dy-1); for (x=xa;x=xb;x+) xs = 3*(x-xa); for (y=ya;y=yb;y+) ys = 3*(y-ya); s = 0; for (i=xs;ixs+3;i+) for (j=ys;jcanvas-p

21、ixelsij=clgreen) if (weighted) s=s+wi-xsj-ys; else s+; if (weighted) gray = (byte)(255.0 - s*(255.0/8.0); else gray = (byte)(255.0-s*(255.0/3.0); form1-image2-canvas-pixelsxy=rgb(gray,gray,gray); 2.2區域取樣2.2.1簡單的區域取樣直線段掃描轉換算法均假定像素是數學上的一個點，像素顏色是由對應于像素中心的圖形中一點的顏色決定的；并且直線段是數學上抽象的直線段，它的寬度是0。但實際上像素不是一個點，而

22、是一個有限區域。屏幕上所畫的直線不是數學意義上的無寬度的理想線段，而是一個寬度至少為一個像素單位的線條。算法中所假定的條件和實際情況之間的差距是造成走樣的原因之一。為了減少走樣，必須改變直線段的模型，從而得到了簡單區域取樣的方法，這個方法的具體步驟是：（1）將直線看成具有一定寬度的狹小矩形；（2）當直線與像素相交時，求出兩者相交區域的面積；（3）根據相交區域的面積，確定像素的亮度值； 圖2.5 具有一定寬度的直線 圖2.6 灰度與面積成比例通過將每個像素亮度設置成與線條部分重疊的區域面積成正比，可以完成對直線的區域取樣。若一個像素與線條部分重疊，根據重疊區域面積的大小來選擇不同的灰度。重疊面積

23、大的像素黑一點，重疊面積小的像素白一點。這種方法將產生模糊的邊界，以次來減輕鋸齒效應。圖2.5是待顯示的直線段，圖2.6是采用簡單區域取樣方法繪制的結果。這個方法中，起關鍵作用的是直線段與像素相交區域面積的計算。那么相交區域如何計算呢？假設一條直線的斜率是m，若規定它的顯示寬度是一個像素，那么直線和像素的相交有如下三種情況，如圖所示。其中（c）的計算可轉化為正方形面積減去兩個三角形面積。接下來介紹（a）和（b）兩種情況。 （a） （b） （c）圖2.7 直線段與像素相交的三種情況在圖2.7（a）中，假設三角形x方向上的邊長為d，則y方向上的邊長為md，從而三角形的面積為. 在圖2.7（b）中，

24、假設梯形左底邊長為d，則右底邊長為d-m，從而梯形的面積為；所得到的面積介于0，1之間的實數，用它乘以像素的最大灰度值，即可得到像素實際顯示的灰度值。上面的計算十分的麻煩，為了簡化計算，可以采用下面的離散方法：（見圖2.8）（1）將屏幕像素分割成n個更小的子像素；（2）計算中心點落在直線內的子像素的個數，記為k；（3）k/n為線段與像素相交區域的近似值 ；圖2.8 n=16，k=3，近似面積為3/16綜上所述，非加權區域采樣方法具有下面三條性質：（1）直線對一個像素亮度的貢獻與兩者相交區域的面積成正比，從而和直線與像素中心點的距離成反比。因為直線距像素中心越遠，相交區域的面積越小。（2）當直線

25、和一個像素不相交時，它對該像素的亮度沒有影響。（3）相同面積的相交區域對像素的亮度貢獻相同，而與這個相交區域落在像素內什么位置無關。2.2.2 加權區域取樣簡單區域取樣由于相同面積重疊區域對像素的貢獻相同，但是這樣仍然會出現走樣現象，接下來介紹的加權區域取樣對此進行了改善，使得相交區域對像素亮度的貢獻依賴于該區域與像素中心的距離。對于相同面積的相交區域，當它距離像素中心近時，它對像素亮度的貢獻大，當它距離像素中心遠時，對像素亮度貢獻小。這種方法更符合人的視覺系統對圖象信息的處理方式。 加權區域取樣的特點：一是接近理想直線的像素將被分配更多的灰度值；二是相鄰兩個像素的濾波器相交，所以直線條經過該

26、相交區域時，將對這兩個像素都分配給適當的灰度值，這樣就縮小了直線條上相鄰像素的灰度差。 加權區域取樣方法的具體步驟如下：（1）求直線段與過濾器底面的重疊區域s。（2）計算 的值，其中f（x，y）是過濾函數，s是過濾器的底面，且有 =1 。（3）上面得到的值介于0和1之間，用它乘以像素的最大灰度值，即得到該像素顯示灰度值。求積分的運算量是很大的，為了方便計算，可以利用加權區域取樣的離散計算方法： （1）將屏幕像素均勻分割成n個子像素，siin=1，則每個子像素的面積為 ，計算每個子像素對原像素亮度的貢獻， 將fi=1保存在加權表中。 （2）求出所有中心落在直線段內的子像素的集合f。 （3）計算所

27、有這些子像素對原像素亮度的貢獻之和。該值乘以像素的最大灰度值即為像素的顯示灰度值。根據上面的討論，fi是一個經驗值，因此我們可以根據經驗直接設定fi的值。例如，我們將屏幕像素劃分為n=3*3=9個子像素，加權表可取作 2.2.3簡單區域取樣算法的實現 有些反走樣方法把像素當作是數學上的一個點，像素顏色是由對應于像素中心的圖形中一點的顏色決定的；而區域取樣認為像素不是一個點，而是一個有面積的區域,因此我們在區域取樣時要計算直線段與像素相交區域的面積,然后根據相交區域面積來確定像素的亮度值。由于直線與像素相交的形式有三種，那么我們如何來判斷直線與像素相交的形式呢？圖2.9 區域取樣示意圖如圖2.9

28、所示，設直線段與某像素縱列相交區域下頂點的y坐標為yl，m為該直線的斜率，y5是掃描線y+0.5。如果yl+my5，則說明直線和像素的相交區域是由上中下三個相鄰像素中的兩個三角形和一個四邊形組成，否則相交區域是由上下兩個相鄰像素中的兩個梯形組成。然后計算出相交區域的面積就可以得到每個像素的亮度，從而達到反走樣直線，而且反走樣的效果也十分的好。綜上所述，實現的算法如下： void areasamplingline(int xa, int ya, int xb, int yb)/將直線段的寬度理解為一個像素的寬度 float m,b, / 設直線方程為： y = mx + b l, / 直線段框與

29、某像素縱列相交區域（平行四邊形）的縱向邊長 yl, / 直線段框與某像素縱列相交區域（平行四邊形）下頂點的y坐標 y5, / 掃描線y+0.5 xl, / 直線段框與y-0.5線的交點 xu, / 直線段框與y+0.5線的交點 sl, / 下方像素中的三角形（或梯形）的面積 su; / 上方像素中的三角形面積 boolean is3part; int x; m = (float)(yb-ya)/(xb-xa); / 直線的斜率 b = ya-m*xa; / 截距 l = sqrt(1+m*m); /既是縱向邊長，也是平行四邊形的面積 xl = (ya-0.5-b+l/2)/m; /xl的初值

30、xu = (ya+0.5-b-l/2)/m; /xu的初值 yl = m*(xa-0.5) + b - l/2; /yl的初值 putpixel(xa,ya,127); y5 = ya + 0.5; for ( x=xa+1;x y5) /相交區域由上中下三個相鄰像素中的兩個三角形和一個四邊形組成 is3part = true;/計算下方像素中的三角形面積sl ，并設置像素的亮度 sl = 0.5*(y5-yl)*(xl-x+0.5); putpixel(x,(int)(y5-0.499),(int)(255-255*sl); /計算上方像素中的三角形面積su，并設置像素的亮度 su = 0.

31、5*(yl+m+l-y5-1)*(x+0.5-xu); putpixel(x,(int)(y5+1.501),(int)(255-255*su); /中間像素的四邊形面積就是平行四邊形面積減去sl，su，并設置像素的亮度 putpixel(x,(int)(y5+0.501),(int)(255-255*(l-su-sl); else /相交區域由上下兩個相鄰像素中的兩個梯形組成 is3part = false; /計算下方像素中梯形的面積，并設置像素亮度 sl = 0.5*(y5-yl+y5-(yl+m); putpixel(x,(int)(y5-0.499),(int)(255-255*sl

32、); /計算上方像素中梯形的面積就是平行四邊形面積減去sl，并設置像素亮度 putpixel(x,(int)(y5+0.501),(int)(255-255*(l-sl) ); if (is3part) y5+; putpixel(xb,yb,127); form1-image1-refresh(); 本算法通過計算相交區域面積來設置像素的亮度從而達到反走樣直線的效果，實現的速度明顯比普通過取樣和加權過取樣要快的多，平滑直線的視覺效果也非常的好。2.3 wu像素反走樣2.3.1 wu反走樣普通的breshenham算法畫線很快,但并不是很精細.通常的整數畫線因為只能在整數坐標上繪圖,所以產生難

33、看的鋸齒.介紹的wu像素反走樣算法就采用了非整數坐標改進它,效果也十分的好。 一條經過wu反走樣的直線要比一條普通的直線要好,產生光滑的邊界,。如圖2.9所示。 圖2.10 普通直線和wu反走樣直線的對比在wu反走樣算法中，有一個重要的概念就是wu像素。wu像素具有兩個屬性：1、繪制的所有像素的亮度的總和等于原始的粒子的亮度。2、wu像素的中心亮度被定位在原始粒子的非整數位置。根據wu像素的這兩個屬性我們就可以實現wu反走樣直線。2.3.2 wu反走樣直線算法理想的反走樣算法將計算每條線覆蓋的精確區域，從區域可以得到像素的灰度值，從而達到反走樣的效果。wu反走樣直線不是這樣做，而是跨騎著直線繪

34、制一對像素。一個主循環將沿著直線的長度畫一對像素,端點的像素對將被分別計算處理，如圖2.10所示。 圖2.11 跨騎著直線的像素對 圖2.12 亮度設置跨騎直線的像素對中，兩個像素的亮度應該都是1,中心點的亮度就是理想直線的亮度。直線上的像素的亮度必須于(1-a)成比例,線下面的像素的亮度必須與(1-b)成比例。也就是說越靠近直線的像素應該越亮。沿著直線長度畫這樣的像素對,就可以得到一條wu反走樣直線。在畫完了中間端點后，我們要畫起始端點和終結端點，如圖2.12所示。可以看到直線的一個端點,用紅色的點來表示，藍色的點表示像素的中心點。你可以看到,頂點不在像素的中心點上，那么如何計算直線端點的兩

35、個像素的正確亮度呢？方法就是把直線延長(向后或向前)到最近的整數x坐標(p)，像計算直線上普通的像素對的亮度一樣計算這些像素對。然后,因為直線只是覆蓋這個像素的很小一部分xgap,直線將降低它的亮度，所以亮度應該乘上xgap。因此,當整條直線向右移動, xgap將變小,使得這個像素對平滑的變暗，按照這個方法可以畫出兩個端點。上面講的是abs(xd)abs(yd)的情況，其實abs(xd)abs(yd) if (x1 x2) temp= x1; x1=x2; x2=temp; temp= y1; y1=y2; y2=temp; xd = x2-x1; yd = y2-y1; grad = yd/

36、xd;/繪制起始端點 xend = x1+1; yend = y1 + grad*(xend-x1); xgap = invfrac(x1); ix1 = int(xend); iy1 = int(yend); /起始點像素亮度計算 brightness1 = invfrac(yend) * xgap ; brightness2 = frac(yend) * xgap ; c1 = byte (brightness1 * maxpixelvalue); c2 = byte (brightness2 * maxpixelvalue);putpixel(ix1,iy1, c1) ;putpixel

37、(ix1,iy1+1, c2);yf = yend+grad ;/繪制中間點的亮度需要/繪制終結端點xend = trunc(x2) ;yend = y2 + grad*(xend-x2);xgap = invfrac(x2);ix2 = int(xend);iy2 = int(yend); /終結點像素亮度計算brightness1 = invfrac(yend) * xgap;brightness2 = frac(yend) * xgap;c1 = byte (brightness1 * maxpixelvalue);c2 = byte (brightness2 * maxpixelval

38、ue);putpixel(ix2,iy2,c1);putpixel(ix2,iy2+1, c2);/繪制中間像素 for (int i=ix1+1;iabs(yd)的方法，只需要改變x和y的值即可實現； wu反走樣算法思路清晰，速度也比較快，而且采用了像素的灰度處理，在反走樣兩像素寬度的直線效果上還好，因此在計算機圖形學中得到了廣泛應用。2.4 點取樣點取樣的原理很簡單，就是對被取樣的連續信號通過取樣脈沖函數一個點一個點進行采樣，最后來確定該像素的顏色。但這個取樣方法不夠科學，最后顏色的設定不一定就能反映像素的真實顏色值。因為點采樣技術只考慮到單一的采樣點中心，而沒有考慮對像素灰度產生影響的多

39、邊形區域部分，這樣的話仍然會使圖形走樣，我們可使用像素細分技術。像素細分技術的基本思想是將發生圖形混淆的像素細胞分為四個子像素，分別對子像素進行光線跟蹤。若子像素仍有圖形混淆，則繼續細分子像素直到最后確定整個像素亮度為止。這在前面介紹的方法中已經介紹到了，在此不多做介紹。2.5 象素移相在可以對屏幕網格內的子像素位置編址的光柵系統上，可使用像素移相來反走樣圖形。將電子束移動（微定位）到更接近由物體幾何指定的近似位置，可光滑沿線路徑或物體邊界的階梯狀。加入這種技術的系統，單個像素位置可根據像素直徑的小數部分來移動。典型地，電子束根據像素直徑的1/4，1/2，3/4移動來畫接近于線或物體邊真實路徑

40、的點。有些系統也允許對單個像素的尺寸進行調整。第三章 反走樣算法的改進3.1 多段直線反走樣算法3.1.1 概述直線是最基本的圖形元素，是構成復雜圖形的基礎，人們在設計和改進直線生成算法方面已經進行了較深的研究。其中bresenham算法是最著名的，它在繪制線段的過程當中只涉及整數的加法和符號的判斷，是一種簡單、高效的算法。但不管是bresenham算法還是別的直線生成算法都會使直線產生鋸齒狀邊界。在第二章已經介紹并實現了幾種反走樣算法,但是它們都需要對直線上的每一個像素進行反走樣處理，我們研究的多段反走樣直線算法利用直線段像素可能存在的多段相似性，大大提高反走樣速度，節省了反走樣時間。3.1

41、.2算法的設計思想 設平面直線l的方程為y=kx+b，根據斜率為k的取值范圍，可將平面直線分為5類： （1）0k1；（2）1k；（3）-k-1；（4）-1k0；（5）k=0，|k|=1，|k|=；根據數字圖形的特點，對第（5）類直線不必反走樣掃描轉換就可簡單地生成直線。而對第（2），（3），（4）類直線，只要在反走樣掃描轉換時通過簡單地交換x和y，或改變其增量的符號就可變換到第（1）類的反走樣直線。設x0，y0，xn，yn為整數，不妨設x0xn，y0yn，對于以（x0，y0）和（xn，yn）為端點的直線段l，記dy=yn- y0，dx= xn-x0，則斜率k=，因為0k0，所以0dydx。記m

42、為dy，dx的最大公約數，即m=gdc（dx，dy），則存在互質的正整數p和q，使得 k=，0qp。例如，如圖3.1所示，（x0，y0）=（0，0），（xn，yn）=（15，12），m=gdc（15，12）=3，p=5，q=4。 設計思想1:反走樣直線段l掃描轉換生成的像素序列（xi，yi）|i=0，1，2，n可被劃分成具有相同形狀的m個片段：l1，l2，lm加終點像素，每個片段含p個像素，每個片段的第一個像素精確地落在l上，且在整個像素序列中有且僅有m+1個像素精確地落在l上（如圖3.1所示）。圖3.1 分段掃描示意圖證明、因為對于第(1)類直線，沿x軸正方向單位步長取樣且有dx=mp，所以

43、掃描轉換生成的像素序列具有mp+1個像素，故可等分為每段p個像素的m個片段l1，l2，lm，再加一個終點像素。記第j段的起點像素（xij，yij）(0j1的線段，根據性質1的分段相似特性, 可在反走樣線段l1段后簡單地復制或并行地反走樣線段l2,l3,，lm。 綜上所述，充分利用直線段特性，以普通過取樣算法為基礎，提出改進算法如下： 1）計算兩個數的最大公約數函數 int gdc(int x,int y)int m=x,n=y,temp,r;if(mn) temp=m;m=n;n=temp;r=m%n;while(r!=0) m=n;n=r;r=m%n;return n; 2）斜率在0與1之間

44、的直線void _fastcall tform1:improveclick(tobject *sender) int x1=20,y1=20,x2=400,y2=200,dx,dy,m; dx=x2-x1;dy=y2-y1; m=gdc(dx,dy); dx=dx/m;dy=dy/m; for(int i=1;icanvas-moveto(20,20+10); image1-canvas-lineto(400,200+10); 同理，其他斜率的直線可通過轉換到斜率在0與1之間的直線來反走樣。3.1.4 計算效率分析本算法需要通過計算獲取的掃描轉換像素個數最多為dx的一半：若m1，則僅需計算dx

45、/m個像素后就會出現dk=0；若計算達到dx的一半時仍未遇到精確落在直線上的像素，則由性質1可知m=1，從而利用性質2進行對稱復制。這樣的話比普通的反走樣直線算法明顯具有優勢,速度提高了很多。3.2圓反走樣算法3.2.1算法思想圓反走樣算法只需考慮圓心位于坐標原點的圓弧反走樣，對于圓心為任意點的圓弧，可以先將其平移到原點，然后反走樣，再平移到原來的位置上。圓心位于原點的圓有四條對稱軸x=0，y=0，x=y，x=-y，如圖3.2所示。因此只要知道圓弧上的一點（x，y）就可以得到它的七個對稱點，也稱為圓的八對稱性。因此我們只要反走樣八分之一圓弧其余的都可以對稱得到反走樣。圓的每一個八分之一圓弧都是由一段段的水平線段組成，因此圓弧反走樣的問題就是反走樣一段段小的水平線段的問題。 圖3.2圓的八對稱性3.2.2算法的實現 算法首先分析圓的特