計(jì)算機(jī)圖形學(xué)教材光柵圖形學(xué)希賽教育基礎(chǔ)學(xué)院

1、 第二章 光柵圖形學(xué)【課前思考】計(jì)算機(jī)是如何在屏幕上畫一條直線或一個(gè)圓的？在計(jì)算機(jī)屏幕上畫直線時(shí)，經(jīng)常出現(xiàn)鋸齒，這是為什么？如何解決？【學(xué)習(xí)目標(biāo)】了解光柵圖形學(xué)的特點(diǎn)；掌握直線、圓弧和橢圓的光柵顯示方法；學(xué)習(xí)反走樣的幾種算法，并能夠編程實(shí)現(xiàn)。【學(xué)習(xí)指南】在數(shù)控插補(bǔ)技術(shù)中也有關(guān)于直線、圓弧和橢圓的nc插補(bǔ)的更多算法，可以參考有關(guān)的數(shù)控編程的書或資料；某些圖象處理方法對學(xué)習(xí)和掌握反走樣技術(shù)會(huì)有幫助?！倦y重點(diǎn)】bresenham畫直線和畫圓算法；直線的反走樣。【知識點(diǎn)】bresenham畫直線算法；bresenham畫圓算法；多邊形區(qū)域填充；直線反走樣；離散區(qū)域反走樣算法。第一節(jié)畫線算法光柵圖形顯示

2、器可以看成是由許多可發(fā)光的離散點(diǎn)（即像素）組成的矩陣，它需要專門的算法來生成直線、圓弧和曲線等等圖形。本章將介紹生成光柵圖形的相關(guān)算法。這些算法對于開發(fā)圖形設(shè)備驅(qū)動(dòng)程序是必需的。不過，在windows、unix或linux操作系統(tǒng)上開發(fā)計(jì)算機(jī)圖形時(shí)，現(xiàn)在都有支持opengl的圖形硬件和軟件開發(fā)工具可供使用，而opengl程序庫本身都提供了光柵圖形顯示的驅(qū)動(dòng)程序，這為圖形軟件開發(fā)人員提供了便利。2.1畫線算法 在數(shù)學(xué)上，理想的點(diǎn)和直線都是沒有寬度的。但是，由于每個(gè)像素對應(yīng)于圖形設(shè)備上的一個(gè)矩形區(qū)域，當(dāng)我們在光柵圖形設(shè)備上顯示一個(gè)點(diǎn)時(shí)，實(shí)際上它是有用一個(gè)發(fā)光的矩形區(qū)域來表示的；當(dāng)在光柵圖形設(shè)備上顯

3、示一條直線時(shí)，我們只能在顯示器所給定的有限個(gè)像素組成的矩陣中，按掃描線順序，依次確定最佳逼近于該直線的一組像素，并且對這些像素進(jìn)行寫操作。這個(gè)過程稱為直線的掃描轉(zhuǎn)換。對于水平線、垂直線和45斜線，選擇哪些像素是顯而易見的，但是對于其它的直線，確定用哪些像素來表示它就不那麼簡單了。本節(jié)我們介紹用于直線掃描轉(zhuǎn)換的常用算法：bresenham畫線算法。在介紹畫線算法之前，我們先討論畫直線的基本要求：直線必須有精確的起點(diǎn)和終點(diǎn)，外觀要直，線寬應(yīng)當(dāng)均勻一致、且與直線的長度和方向無關(guān)，最后，算法速度要快。bresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域使用最廣泛的直線掃描轉(zhuǎn)換算法。該方法最初是為數(shù)字繪圖儀設(shè)計(jì)的，

4、后來被廣泛地應(yīng)用于光柵圖形顯示和數(shù)控（nc）加工。該算法構(gòu)思巧妙，使得每次只需檢測誤差項(xiàng)的符號就能決定直線上的下一個(gè)像素的位置。算法原理如下：過各個(gè)像素的中心構(gòu)造一組虛擬網(wǎng)格線，首先按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后，采用增量計(jì)算，使得對于每一列，只要檢查一個(gè)誤差項(xiàng)的符號，就可以確定該列像素中與此交點(diǎn)最近的像素。先考慮斜率k=dy/dx1的直線。如圖2.1所示，設(shè)直線 方程為 ，其中，k = dy/dx。 假設(shè)當(dāng)前像素的x坐標(biāo)已經(jīng)確定為xi，其y坐標(biāo)為yi，由于坐標(biāo)（xi，yi）（i=0,1,）只能取整數(shù)，那么下一個(gè)像素的x坐標(biāo) ，而yi1的坐標(biāo)有兩種可能：1) 保持不

5、變，即y i1yi；或者2) y坐標(biāo)遞增1，即y i1yi1。令 ，y坐標(biāo)是否增加1取決于如圖所示誤差項(xiàng)d i的值。因?yàn)橹本€的起始點(diǎn)在像素中心，所以初始誤差d00。x每增加1，y的值相應(yīng)遞增直線的斜率值k，即 。一旦di+11，就把它減去1，這樣保證di+1在01之間。當(dāng)d i+10.5時(shí)，直線 與xxi1的垂線的交點(diǎn)最接近于當(dāng)前像素（xi，yi）的右上方像素（xi1，yi1）；而當(dāng)d i+10.5時(shí)，其交點(diǎn)更接近于（xi，yi）右邊的像素（xi1，yi）。為方便計(jì)算，令e0=0.5，e i+1di+10.5，增量為k。當(dāng)ei+10時(shí)，取當(dāng)前像素（xi，yi）的右上方像素（xi1， yi1）；

6、而當(dāng)e i+11的直線，只要在上述算法中交換x和y之間的規(guī)則即可。算法2.1 畫斜率0k1的直線的改進(jìn)的bresenham畫線算法：void bresenhamline (int x0, int y0, int x1, int y1, long color) int x, y, dx, dy;float k, e;dx = x1-x0；dy = y1- y0；e=-dx;x = x0；y = y0；if (dx = = 0) for (i=0；idy；i+)drawpixel (x, y+i, color)；/畫像素（x,y+i）return;for (i=0；idx；i+)drawpixel

7、 (x, y, color)；/畫像素（x,y）x+；e += e+2*dy；if (e0) y+；e - 2*dx；2.2 畫圓這一節(jié)中，我們介紹畫圓弧的bresenham算法。不失一般性，假設(shè)圓的圓心位于坐標(biāo)原點(diǎn)（如果圓心不在原點(diǎn)，可以通過坐標(biāo)平移使其與原點(diǎn)重合），半徑為r。以原點(diǎn)為圓心的圓c有四條對稱軸：x=0,y=0,x=y和x=-y。若已知圓弧上一點(diǎn)p1c（x, y），利用其對稱性便可以得到關(guān)于四條對稱軸的其它7個(gè)點(diǎn)，即：p2c（x,y），p3c（x, y），p4c（x,y），p5c（y，x），p6c（y，x），p7c（y，x），p8c（y，x）。這種性質(zhì)稱為八對稱性。因此，只要掃描

8、轉(zhuǎn)換八分之一圓弧，就可以通過圓弧的八對稱性得到整個(gè)圓。為了方便起見，考慮位于第一象限的四分之一圓弧。如果以點(diǎn)（0，r）為起點(diǎn)按順時(shí)針方向生成圓，則在第一象限內(nèi)y是x的單調(diào)遞減函數(shù)。假設(shè)圓心和起點(diǎn)均精確地落在像素中心上。如果已經(jīng)知道圓弧上的一點(diǎn)(x,y)，下一像素的選取有三種可能：正右方像素，右下角像素和正下方像素，分別用h,d和v表示，如圖2.2所示。這三個(gè)像素的偏差的平方為： 。令 ， 。如果 ，說明圓弧到d向像素的距離大于到h向像素的距離，因此，下一個(gè)像素應(yīng)當(dāng)取h向的像素（xi+1，yi）；反之，下一個(gè)像素應(yīng)當(dāng)取d向的像素（xi+1，yi1）。經(jīng)過更進(jìn)一步地分析后，可以得到：如 公式（22

9、1） 如 公式（222） 我們可以按以下規(guī)則選取下一個(gè)像素作為圓弧的最佳逼近點(diǎn)： 當(dāng)時(shí)，如果 ，則取為下一個(gè)像素點(diǎn)，否則取d為下一個(gè)像素點(diǎn)。 當(dāng) 時(shí)，如果 ，則取d為下一個(gè)像素點(diǎn)，否則取v為下一個(gè)像素點(diǎn)； 當(dāng) 時(shí)取d為下一個(gè)像素點(diǎn)。 為了提高計(jì)算速度，我們可以在bresenham畫圓算法中采用只有加、減和移位（即：乘以2）操作的遞推公式如下： 可見，只用加、減和移位操作便完全可以實(shí)現(xiàn)bresenham畫圓算法。和改進(jìn)的bresenham畫線算法一樣，bresenham畫圓算法具有很高的速度和效率，因此得到廣泛的應(yīng)用。八對稱性圖2.2 第一象限圓弧的像素選取2.3 畫橢圓中心在原點(diǎn)、軸對齊的橢圓

10、的非參數(shù)化方程為：。上式可用隱式方程表示為：由于橢圓的對稱性，僅考慮在第一象限的橢圓弧即可。橢圓弧的法向量計(jì)算公式為：橢圓弧上斜率為1的點(diǎn)將橢圓弧分為上、下部分，見圖2.3所示。在上部分（區(qū)域2），法向量的y向分量較大，選擇像素時(shí)增量y比較重要；在下部分（區(qū)域1），法向量的x分量較大，選擇像素時(shí)增量x比較重要。下面我們分開進(jìn)行討論。 在區(qū)域2，設(shè)當(dāng)前位置為點(diǎn)，下一個(gè)可能的點(diǎn)是像素點(diǎn)h和d，這時(shí)可構(gòu)造判別式：若=0,表示像素點(diǎn)h和d的中點(diǎn)在橢圓外，這時(shí)應(yīng)當(dāng)取d為下一個(gè)像素點(diǎn)。所以，對于在區(qū)域2的橢圓弧，我們可以按左邊的規(guī)則選取下一個(gè)像素作為橢圓弧的最佳逼近點(diǎn)：圖2.3 第一象限橢圓弧的像素選取2

11、.4 其它曲線二次曲線的一般方程為令，我們可以對二次曲線進(jìn)行分類：二次曲線也可以用參數(shù)方程表示為：如果時(shí)，則r(t)是一條拋物線；當(dāng)時(shí)，r(t)是一條雙曲線；當(dāng)時(shí)，r(t)是橢圓。 當(dāng)0，圖形為雙曲線對于橢圓和圓弧，我們可以用前面的方法進(jìn)行光柵化顯示。對于雙曲線，我們可以采用差分的方法進(jìn)行光柵圖形顯示。對于三次或三次以上的多項(xiàng)式曲線f(x,y)=0，可以采用遞歸空間子分算法進(jìn)行光柵圖形顯示。其基本思想是：首先建立有頂點(diǎn)（ ，）和（ ，）構(gòu)成的包圍盒，如果曲線f(x,y)=0通過包圍盒，而且包圍盒的大小大于一個(gè)像素，則對包圍盒再進(jìn)行子分，直到包圍盒只有一個(gè)像素大為止，然后用給定曲線的顏色輸出；如

12、果曲線f(x,y)=0不通過包圍盒，則該區(qū)域用背景色顯示，并忽略處理。 2.5 區(qū)域填充1) 多邊形由一系列首尾相連的直線段構(gòu)成的圖形稱為多邊形。如果在多邊形內(nèi)任意選取不相同的兩點(diǎn)，其連線上的所有點(diǎn)均在該多邊形內(nèi)，這樣的多邊形稱為凸多邊形；否則，稱為凹多邊形。2) 種子填充算法種子填充算法又稱為邊界填充算法。其基本思想是：從多邊形區(qū)域的一個(gè)內(nèi)點(diǎn)開始，由內(nèi)向外用給定的顏色畫點(diǎn)直到邊界為止。如果邊界是以一種顏色指定的，則種子填充算法可逐個(gè)像素地處理直到遇到邊界顏色為止。種子填充算法常用四連通域和八連通域技術(shù)進(jìn)行填充操作。從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素。用這種方

13、法填充的區(qū)域就稱為四連通域；這種填充方法稱為四向連通算法。從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右、左上、左下、右上和右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素。用這種方法填充的區(qū)域就稱為八連通域；這種填充方法稱為八向連通算法。一般來說，八向連通算法可以填充四向連通區(qū)域，而四向連通算法有時(shí)不能填充八向連通區(qū)域。例如，八向連通填充算法能夠正確填充如圖2.4a所示的區(qū)域的內(nèi)部，而四向連通填充算法只能完成如圖2.4b的部分填充。圖2.4 四向連通填充算法四向連通填充算法：a） 種子像素壓入棧中；b） 如果棧為空，則轉(zhuǎn)e)；否則轉(zhuǎn)c)；c） 彈出一個(gè)像素，并將該像素置成填充色；并判斷該像素相鄰的四連通像素是否為

14、邊界色或已經(jīng)置成多邊形的填充色，若不是，則將該像素壓入棧；d） 轉(zhuǎn)b）；e） 結(jié)束。四向連通填充方法可以用遞歸函數(shù)實(shí)現(xiàn)如下：算法2.3 四向連通遞歸填充算法：void boundaryfill4(int x, int y, long filledcolor, long boundarycolor)long currentcolor;currentcolor = getpixelcolor(x,y);if (currentcolor != boundarycolor & currentcolor != filledcolor)setcolor(filledcolor);setpixel (x,y

15、);boundaryfill4(x+1, y, filledcolor, boundarycolor);boundaryfill4(x-1, y, filledcolor, boundarycolor);boundaryfill4(x, y+1, filledcolor, boundarycolor);boundaryfill4(x, y-1, filledcolor, boundarycolor);上述算法的優(yōu)點(diǎn)是非常簡單，缺點(diǎn)是需要大量棧空間來存儲(chǔ)相鄰的點(diǎn)。一個(gè)改進(jìn)的方法就是：通過沿掃描線填充水平像素段，來處理四連通或八連通相鄰點(diǎn)，這樣就僅僅只需要將每個(gè)水平像素段的起始位置壓入棧，而不需要

16、將當(dāng)前位置周圍尚未處理的相鄰像素都壓入棧，從而可以節(jié)省大量的棧空間。3) 其它填充算法掃描線填充算法是另一個(gè)常用的多邊形填充算法。其基本思想是：對于一個(gè)給定的多邊形，用一組水平或垂直的掃描線進(jìn)行掃描，分別求出每條掃描線與多邊形的交點(diǎn)，這些交點(diǎn)將掃描線分割為相間排列的落在多邊形內(nèi)和多邊形外的線段，將落在多邊形內(nèi)的所有線段上的每個(gè)像素點(diǎn)賦以給定的多邊形填充色。具體算法可以參考第7章消隱顯示的相關(guān)內(nèi)容。2.6 字符生成在計(jì)算機(jī)圖形學(xué)中，字符指計(jì)算機(jī)在文本方式下能夠在屏幕上顯示的數(shù)字、字母、音標(biāo)、標(biāo)點(diǎn)符號、數(shù)學(xué)符號、漢字等符號。計(jì)算機(jī)中的字符由一個(gè)數(shù)字編碼唯一標(biāo)識。最流行的字符集是美國信息交換用標(biāo)準(zhǔn)代

17、碼集簡稱ascii碼。它用7位二進(jìn)制編碼規(guī)定了129個(gè)字符代碼，其中代碼031表示控制字符，32127表示字母、標(biāo)點(diǎn)符號、數(shù)學(xué)符號以及一些特殊符號。我國除采用ascii碼外，還另外制定了漢字編碼的國家標(biāo)準(zhǔn)字符集，如：信息交換用漢字編碼字符集基本集gb231280。該字符集分為94個(gè)區(qū)，94個(gè)位，每個(gè)符號由一個(gè)區(qū)碼和一個(gè)位碼共同標(biāo)識。區(qū)碼和位碼各用一個(gè)字節(jié)表示。為了能夠區(qū)分ascii碼與漢字編碼，采用字節(jié)的最高位來標(biāo)識：最高位為0表示ascii碼；最高位為1表示漢字編碼。共收錄了6763個(gè)常用漢字。2000年3月信息產(chǎn)業(yè)部和 國家質(zhì)量技術(shù)監(jiān)督局又頒布了gb18030-2000國家標(biāo)準(zhǔn)信息交換用漢

18、字編碼字符集基本集的擴(kuò)充。它共收錄了2.7萬多個(gè)漢字，總編碼空間超過150萬個(gè)碼位，采用單/雙/四字節(jié)混合編碼，與現(xiàn)有絕大多數(shù)操作系統(tǒng)、中文平臺在內(nèi)碼一級兼容，可支持現(xiàn)有應(yīng)用系統(tǒng),并包容了其中收錄的所有漢字和蒙、藏、彝、維等少數(shù)民族文字。為了在顯示器等輸出設(shè)備上輸出字符，計(jì)算機(jī)系統(tǒng)中必須安裝相應(yīng)的字庫。字庫分為點(diǎn)陣字庫和矢量字庫兩種，用于存儲(chǔ)每個(gè)字符的形狀信息。點(diǎn)陣字庫中，每個(gè)字符用二值點(diǎn)陣信息表示每個(gè)字符，矢量字庫則用直線和曲線（如三次b樣條曲線/bezier曲線）來描述每個(gè)字符的輪廓形狀。 1) 點(diǎn)陣字符在點(diǎn)陣字庫中，每個(gè)字符由一個(gè)位圖表示（如圖2.5所示），并把它用一個(gè)稱為字符掩膜的矩陣

19、來表示，其中的每個(gè)元素都是一位二進(jìn)制數(shù)，如果該位為1表示字符的筆畫經(jīng)過此位，該像素置為字符顏色；如果該位為0，表示字符的筆畫不經(jīng)過此位，該像素置為背景顏色。點(diǎn)陣字符的顯示分為兩步：首先從字庫中將它的位圖檢索出來，然后將檢索到的位圖寫到幀緩沖器中。在實(shí)際應(yīng)用中，同一個(gè)字符有多種字體（如宋體、楷體等），每種字體又有多種大小型號，因此字庫的存儲(chǔ)空間十分龐大。為了減少存儲(chǔ)空間，一般采用壓縮技術(shù)。圖2.5 字符的點(diǎn)陣表示和矢量輪廓表示2) 矢量字符矢量字符記錄字符的筆畫信息而不是整個(gè)位圖，具有存儲(chǔ)空間小，美觀、變換方便等優(yōu)點(diǎn)。例如：在autocad中使用圖形實(shí)體-形（shape）-來定義矢量字符，其中，

20、采用了直線和圓弧作為基本的筆畫來對矢量字符進(jìn)行描述。 對于字符的旋轉(zhuǎn)、放大、縮小等幾何變換，點(diǎn)陣字符需要對其位圖中的每個(gè)象素進(jìn)行變換，而矢量字符則只需要對其幾何圖素進(jìn)行變換就可以了，例如：對直線筆畫的兩個(gè)端點(diǎn)進(jìn)行變換，對圓弧的起點(diǎn)、終點(diǎn)、半徑和圓心進(jìn)行變換等等。矢量字符的顯示也分為兩步。首先從字庫中將它的字符信息。然后取出端點(diǎn)坐標(biāo)，對其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示出字符。輪廓字形法是當(dāng)今國際上最流行的一種字符表示方法，其壓縮比大，且能保證字符質(zhì)量。輪廓字形法采用直線、b樣條/bezier曲線的集合來描述一個(gè)字符的輪廓線。輪廓線構(gòu)成一個(gè)或若干個(gè)封閉的平面區(qū)域。輪廓線定義加上一些指示

21、橫寬、豎寬、基點(diǎn)、基線等等控制信息就構(gòu)成了字符的壓縮數(shù)據(jù)。 2.7 光柵圖形反走樣基礎(chǔ)bresenham直線算法生成的直線圖形一般都呈階梯狀（見圖2.1），實(shí)際上，這是光柵圖形的一種走樣現(xiàn)象。這種走樣現(xiàn)象是由于采用離散量表示連續(xù)量引起的。通常，我們把由離散量表示連續(xù)量引起的失真稱為走樣；把減少或克服走樣效果的技術(shù)稱為反走樣技術(shù)，簡稱反走樣。光柵圖形的走樣有如下幾種：a) 產(chǎn)生階梯或鋸齒形；b) 細(xì)節(jié)或紋理繪制失真；c) 狹小圖形遺失；d) 實(shí)時(shí)動(dòng)畫忽隱忽現(xiàn)、閃爍跳躍。當(dāng)走樣嚴(yán)重時(shí)，可能導(dǎo)致意外的結(jié)果。例如，考慮圖2.6 a)和b)所示的信號，它們是兩組完全不同的信號，對它們用同一頻率進(jìn)行采樣（

22、見圖2.6中的黑點(diǎn) ），重建后的信號卻相同。圖2.6 c)或d)是圖2.6 a)信號的走樣，也是圖2.6 b)信號的走樣。造成走樣的原因是由于采樣頻率太低造成的欠采樣。根據(jù)采樣定理，為了避免走樣，采樣頻率至少應(yīng)是信號最高頻率的2倍。對于小于像素尺寸的圖形對象，一方面，如果它未能覆蓋像素中用于計(jì)算其屬性的像素中點(diǎn)，則這個(gè)對象將不會(huì)顯示出來；另一方面，如果它覆蓋了像素中用于計(jì)算其屬性的那一點(diǎn)，它將不恰當(dāng)?shù)卮碚麄€(gè)像素的屬性。圖2.7就是這樣的一個(gè)例子。當(dāng)在光柵設(shè)備上顯示圖2.7 a)所示的一組細(xì)長的多邊形時(shí)，由于僅僅當(dāng)像素中心被這些矩形覆蓋時(shí)該像素才被顯示，因此造成狹小的圖形遺失、圖形細(xì)節(jié)失真，其

23、結(jié)果如圖2.7 b)所示。在動(dòng)畫序列中，這種走樣現(xiàn)象會(huì)導(dǎo)致圖形時(shí)隱時(shí)現(xiàn)，產(chǎn)生閃爍。圖2.8是一個(gè)小卡通動(dòng)畫序列中的三幅畫。如果像素的屬性由其中心決定，則在第一幀中，這個(gè)小卡通人是不可見的，在第二幀小卡通人可見，但第三幀又不可見。這樣，小卡通人給人的感覺不是在緩慢地連續(xù)前進(jìn)，而是一明一暗地在閃爍。圖2.6 不同信號a)和b)的采樣及走樣現(xiàn)象圖2.7 光柵圖形的細(xì)節(jié)失真圖2.8 動(dòng)畫的走樣現(xiàn)象為了提高圖形質(zhì)量，必須克服或減少走樣現(xiàn)象。這就是本節(jié)研究的重點(diǎn)。光柵圖形的反走樣方法主要有兩類： 第一類是超采樣或稱后置濾波。這類算法的基本思想著眼于提高分辨率，雖然采用高分辨率的光柵圖形顯示器也是一個(gè)選擇，

24、但它受到客觀條件的限制，而且也不經(jīng)濟(jì)。因此，我們往往采用軟件實(shí)現(xiàn)的方法，即：將低分辨率的圖形像素劃分為許多子像素，在較高分辨率上對各子像素的顏色值或灰度值進(jìn)行計(jì)算，然后采用某種平均算法，將原像素內(nèi)的各子像素的顏色值或灰度值的平均值作為該像素顯示的顏色值或灰度值，在較低分辨率的光柵圖形設(shè)備上進(jìn)行顯示。 第二類方法稱為前置濾波。即：把像素作為一個(gè)有限區(qū)域而不是一個(gè)面積為零的點(diǎn)來處理。 2.7.1 直線反走樣一、反走樣細(xì)直線可以用超采樣方法來進(jìn)行直線反走樣。即：將每個(gè)像素分成nn個(gè)子像素，然后在子像素級對直線進(jìn)行光柵化，這樣就可以得到每個(gè)像素中被激活的子像素的個(gè)數(shù)。如圖2.9所示，粗實(shí)線正方形表示物

25、理像素，虛線正方形表示子像素，陰影區(qū)域表示被激活的子像素。在nn偽光柵上，可以光柵化的子像素最多為n個(gè)。每個(gè)物理像素的光強(qiáng)與其被激活的子像素?cái)?shù)與n的比值成正比。假設(shè)一個(gè)物理像素中被激活的子像素有m個(gè)，其可能的最大光強(qiáng)為imax，則該像素的光強(qiáng)（亮度）（271）, 再取整，即可得到象素的顯示灰度值。圖2.9 反走樣細(xì)直線的超采樣二、區(qū)域反走樣算法a) 反走樣固定寬度直線的區(qū)域采樣方法假定每個(gè)象素都是一個(gè)面積等于1的小正方形矩形區(qū)域，將直線段看作寬度為一個(gè)像素的狹長矩形，如圖2.10所示。這時(shí)可以采用簡單的區(qū)域采樣方法進(jìn)行反走樣。當(dāng)直線段的矩形邊界與象素的邊界有交時(shí)，求出兩者相交區(qū)域的面積，然后根

26、據(jù)相交區(qū)域面積的大小確定該象素的亮度值。對于圖2.10中的任何一個(gè)陰影像素而言，上述陰影面積a是介于0-1之間的正數(shù)，用它乘以象素的最大光強(qiáng)為imax，則該像素的光強(qiáng)。pietteway和winkins對bresenham畫線算法稍作改進(jìn)后得到像素在多邊形內(nèi)的面積近似值，并用它調(diào)制像素的光強(qiáng)。改進(jìn)后的bresenham反走樣畫線算法如下：圖2.10 固定寬度直線 bresenhamantialiasingline(int x1, int y1, int x2, int y2，int i)/ （x1, y1）,（x2, y2）分別是直線的起點(diǎn)和終點(diǎn)/ i是畫線的最大亮度值int x,y,dx,d

27、y,m,w,e;x = x1;y = y1;dx = x2x1;dy = y2y1;m = i*dy/dx;w = im;e = i/2;setpixel(x,y,m/2);while (x x2)if (e w)x +;e += m;elsex +;y+;e -= m;setpixel(x,y,e);b) 加權(quán)區(qū)域反走樣算法從采樣理論的角度考慮，區(qū)域采樣方法相當(dāng)于使用盒式濾波器進(jìn)行前置濾波后再采樣。區(qū)域采樣方法有兩個(gè)缺點(diǎn)：（1）象素的亮度與相交區(qū)域的面積成正比，而與相交區(qū)域落在象素內(nèi)的位置無關(guān)，這在某種程度上仍然會(huì)導(dǎo)致階梯現(xiàn)象。（2）直線條上沿理想直線方向的相鄰兩個(gè)象素有時(shí)會(huì)有較大的亮度差，

28、特別是當(dāng)直線是一條接近水平或接近垂直的直線時(shí)，這種現(xiàn)象就會(huì)比較突出。為了使靠近理想直線的像素能夠分配到更大的亮度值，可以采用圓錐形濾波器，如圖2.11所示。其基本思想是：建立一個(gè)底圓半徑為一個(gè)像素單位，高為1的圓錐，并使底圓中心位于當(dāng)前像素中心。當(dāng)直線經(jīng)過該像素時(shí)，直線的矩形區(qū)域與該圓錐底面的相交區(qū)域上對濾波器的積分，就是該像素的亮度值。在幾何上，這個(gè)積分的結(jié)果相當(dāng)于用過直線矩形區(qū)域的兩邊沿、且垂直于像素區(qū)域的一對平面，與該圓錐相切割所得到的三維物體的體積。這種區(qū)域采樣法的反走樣效果較好。為了簡化計(jì)算，我們可以采用離散的區(qū)域反走樣方法。 圖2.11 圓錐形濾波器三、離散區(qū)域反走樣算法a) 基本

29、原理如圖2.12所示，首先將屏幕象素均分成nn個(gè)子像素。然后，對于每個(gè)物理像素，計(jì)算中心點(diǎn)落在直線段內(nèi)的子象素的個(gè)數(shù)m，則該象素的光強(qiáng)為：（272）。 注意，上式與（271）式是不同的。這里有（n2+1）種可能的光強(qiáng)，而反走樣細(xì)直線只有（n+1）種可能的光強(qiáng)。 圖2.12區(qū)域取樣法反走樣固定寬度直線對于彩色的情況，反走樣圖形的光強(qiáng)還需要考慮背景色。一般可取兩者的線性插值。即：像素的紅、綠、藍(lán)（r，g，b）三元色的亮度值（273）其中， 是直線的（r，g，b）三元色的最大亮度值， 是背景的（r，g，b）三元色的亮度值。為了確定m，必須計(jì)算出中心點(diǎn)落在直線段內(nèi)的子象素的個(gè)數(shù)，這就涉及到多邊形對點(diǎn)的

30、包含性檢測問題（見7.1.2.3節(jié)）。我們這里采用一種簡單的技術(shù)-代入測試（substitution test）法。 b) 代入測試法圖2.13是位于第一象象限直線上的一個(gè)內(nèi)部物理像素，即不在直線端點(diǎn)的像素，它被分為33個(gè)子像素，每個(gè)子像素的中心用圓點(diǎn)標(biāo)出。直線的寬度等于一個(gè)像素寬。圖2.13 固定寬度直線內(nèi)的子像素?cái)?shù)由于這是一個(gè)內(nèi)部物理像素，它只需要檢測子像素的中心是否位于直線的矩形條的兩條邊之間。假定直線方程為y = kx + b，其中，k是直線的斜率，b是直線的截距（即直線與y軸的交點(diǎn)的y坐標(biāo)）。直線矩形條的上下兩條邊的方程為：將子像素中心點(diǎn)的坐標(biāo)代入上式，如果 并且 ，則該中心點(diǎn)在直線

31、的矩形條內(nèi)。如果 或 ，則表示子像素中心點(diǎn)在直線矩形條的邊界上。這里必須注意，如果物理像素位于直線的端點(diǎn)，則還需要檢測其子像素中心是否位于直線的端邊。c) 加權(quán)代入測試法代入測試法的一個(gè)明顯的不足是：不管子像素的中心離理想直線有多遠(yuǎn)，只要它位于直線的矩形內(nèi)，就賦予它相同的亮度。其實(shí)，僅僅簡單地計(jì)算中心在具有一定寬度的直線內(nèi)的子像素?cái)?shù)是不夠的，我們必須根據(jù)某些度量參數(shù)對每一個(gè)子像素的貢獻(xiàn)進(jìn)行加權(quán)。在此，我們根據(jù)子像素中心與直線中心線的距離來決定權(quán)重。在圖2.13中，利用相似三角形的幾何關(guān)系，可以得到從子像素中心到理想直線距離d:,其中，xc，yc是子像素中心的坐標(biāo)， 。取第i個(gè)子像素的權(quán)函數(shù)為， 。其中，di是第i個(gè)子像素中心到理想直線的距離，f可用來調(diào)節(jié)某些特定子像素的權(quán)。例如：當(dāng)f=0時(shí)，所有子像素的權(quán)值都等于0；當(dāng)f=1時(shí)，位于直線矩形條邊界的子像素的權(quán)值最小，但位于理想直線（矩形中心）附近的子像素的權(quán)值最大。第i個(gè)子像素對物理像素的光強(qiáng)的貢獻(xiàn)為：。對于彩色的情形，可以用前面的線性混合函數(shù)（273）式作類似的處理。2.7.2 多邊形內(nèi)部的反走樣多邊形的反走樣一般采樣超采樣技術(shù)。計(jì)算平均光強(qiáng)的常用方法有：均勻平均和加權(quán)平均。首先將象素均勻分割成nn個(gè)子象素，即建立nn的偽分辨率。則每個(gè)象素的面積為1/n2。每個(gè)子像素的屬性由子像素的中