第二章光柵圖形學(xué)

1、計(jì)算機(jī)圖形學(xué)福建師范大學(xué)計(jì)算機(jī)圖形學(xué)翁彬計(jì)算機(jī)圖形學(xué)福建師范大學(xué)第2章 光柵圖形學(xué)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 什么是光柵圖形學(xué)？ 光柵顯示器 圖形光柵化、 光柵化圖形的處理 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)光柵圖形學(xué)的研究?jī)?nèi)容光柵圖形學(xué)的研究?jī)?nèi)容2.1直線段的掃描轉(zhuǎn)換算法2.2圓弧的掃描轉(zhuǎn)換算法2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充2.4字符2.5裁剪2.6反走樣2.7消隱計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1 直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換：直線的掃描轉(zhuǎn)換：確定最佳逼近于該直線的一組象素，并且按掃描線順序，對(duì)這些象素進(jìn)行寫(xiě)操作。三個(gè)常用算法：三個(gè)常用算法：數(shù)值微分法（dda）中點(diǎn)畫(huà)線法bresenham算法。計(jì)

2、算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda)法 基本思想 已知過(guò)端點(diǎn) 的直線段l： 直線斜率為 從 的左端點(diǎn) 開(kāi)始，向 右端點(diǎn)步進(jìn)。步長(zhǎng)=1(個(gè)象素)，計(jì)算相應(yīng)的y坐標(biāo) ；取象素點(diǎn)(x, round(y)作為當(dāng)前點(diǎn)的坐標(biāo)。 這種方法直觀，但效率太低，因?yàn)槊恳徊叫枰淮胃↑c(diǎn)乘法、一次加法和一次舍入運(yùn)算。0101xxyyk),(),(111000yxpyxpbkxyx0 xxbkxy計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda)法 作為最底層的光柵圖形算法，在通常的cad/圖形系統(tǒng)中，會(huì)被大量應(yīng)用，因此，哪怕節(jié)約一個(gè)加法或減法，也是很了不起的改進(jìn)。 由此出發(fā)點(diǎn)，導(dǎo)致增量算法的思想。

3、 增量算法：在一個(gè)迭代算法中，如果每一步的x、y值是用前一步的值加上一個(gè)增量來(lái)獲得，則稱為增量算法。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda)法 計(jì)算 當(dāng) 時(shí); 即：當(dāng)x每遞增1，y遞增k(即直線斜率)； xkyxkbkxbkxyiiii 111xkyyii1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda)法 例：畫(huà)直線段 k = 0.4 x y int(y+0.5) y+0.5 0 0 0 0 注：網(wǎng)格點(diǎn)表示象素)2 , 5()0 , 0(10pp0 1 2 3 4 5321line: p0(0, 0)- p1(5, 2)計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda

4、)法 例：畫(huà)直線段 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 注：網(wǎng)格點(diǎn)表示象素0 1 2 3 4 5321line: p0(0, 0)- p1(5, 2)2 , 5()0 , 0(10pp計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda)法 void ddaline(int x0,int y0,int x1,int y1,int color) int x；float dx, dy, y, k;dx= x1-x0, dy=y1-y0; k=dy/dx, y=y0;

5、 for (x=x0; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.1 數(shù)值微分(dda)法 注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每增加1, y最多增加1。 問(wèn)題： 當(dāng) k 1時(shí)，會(huì)如何？(答案見(jiàn)下頁(yè)) 0 1 2 3 4 5321line: p0(0, 0)- p1(5, 2)k dda算法采用兩點(diǎn)式，可否采用其他的直線表示方式？計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法基本思想當(dāng)前象素點(diǎn)為(xp, yp) 。下一個(gè)象素點(diǎn)為p1 或p2 。設(shè)m=(xp+1, yp+0.5)，為p1

6、與p2之中點(diǎn)，q為理想直線與x=xp+1垂線的交點(diǎn)。將q與m的y坐標(biāo)進(jìn)行比較。當(dāng)m在q的下方- p2離直線更近更近-取p2 。m在q的上方- p1離直線更近更近-取p1m與q重合， p1、p2任取一點(diǎn)。p=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法問(wèn)題：如何判斷m與q點(diǎn)的關(guān)系？p=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 假設(shè)直線方程為：f(x,y)=ax+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 由常識(shí)知： 欲判斷m點(diǎn)是在q點(diǎn)上方還是在q點(diǎn)下方，只需把m代入f(x,y),并檢查它的符號(hào)。點(diǎn)在直線下方

7、點(diǎn)在直線上方點(diǎn)在直線上面0,0,0,yxfyxfyxfp=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法構(gòu)造判別式:d=f(m)=f(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0當(dāng)d0，m在l(q點(diǎn))上方，取右方p1為下一個(gè)象素；當(dāng)d=0，選p1或p2均可，約定取p1為下一個(gè)象素；p=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 但這樣做，每一個(gè)象素的計(jì)算量是4個(gè)加法，兩個(gè)乘法。 d=a(xp+1)+b(yp+0.5)+c計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中

8、點(diǎn)畫(huà)線法 如果也采用增量算法呢？計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 d是xp, yp的線性函數(shù)，因此可采用增量計(jì)算，提高運(yùn)算效率。 d=a(xp+1)+b(yp+0.5)+c計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法若當(dāng)前象素處于d0情況，則取正右方象素p1 (xp+1, yp ), 要判下一個(gè)象素位置，應(yīng)計(jì)算 d1=f(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c=d+a； 增量為a d=a(xp+1)+b(yp+0.5)+cp=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法若d0時(shí)，則取右上方象素p2 (xp+1, yp+1)

9、。要判斷再下一象素，則要計(jì)算 d2= f(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c=d+a+b ； 增量為ab d=a(xp+1)+b(yp+0.5)+cp=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 至此，至少新算法可以和dda算法一樣好。 能否再做改進(jìn)？計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 能否實(shí)現(xiàn)整數(shù)運(yùn)算？計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 畫(huà)線從(x0, y0)開(kāi)始，d的初值d0=f(x0+1, y0+0.5) = a(x0 +1)+b(y0 +0.5)+c = f(x0, y0)+a+0.5b = a+0.

10、5b 。 由于只用d 的符號(hào)作判斷，為了只包含整數(shù)運(yùn)算, 可以用2d代替d來(lái)擺脫小數(shù)，提高效率。 令 d0=2a+b, d1=2a, d2=2a+2b,我們有如下算法 。p=(xp,yp)qp2p1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法void midpoint line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (

11、xx1) if (d0) x+, y+, d+=d2; else x+, d+=d1; drawpixel (x, y, color); /* while */ /* mid pointline */計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法 例：用中點(diǎn)畫(huà)線法 ixiyid 1001 210-3 3213 431-1 54250 1 2 3 4 5321)2 , 5()0 , 0(10pp5, 20110 xxbyya, 6)(2, 42, 12210badadbad計(jì)算機(jī)圖形學(xué)福建師范大學(xué)中點(diǎn)畫(huà)線法小結(jié) 中點(diǎn)與交點(diǎn)位置來(lái)判斷象素選取 引入直接的隱式方程f(x,y)=ax+by+c=0 但

12、計(jì)算量大，故又改進(jìn)為增量算法（此處，增量分兩種情況） 為進(jìn)一步提高效率，修改為全是整數(shù)計(jì)算的算法（ 2d代替d ，同時(shí)增量也做相應(yīng)調(diào)整）計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.2 中點(diǎn)畫(huà)線法思考題：p55 2-2 用中點(diǎn)畫(huà)線法掃描轉(zhuǎn)換從點(diǎn)（1,0）到（4,7）經(jīng)過(guò)的直線段，并給出每一步的判別值。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) dda算法采用點(diǎn)斜式，中點(diǎn)法采用隱式表示。 中點(diǎn)法可以有整數(shù)算法。 其他表示可以推出整數(shù)算法嗎？計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.3 bresenham算法基本思想過(guò)各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號(hào)確定該列象素

13、中與此交點(diǎn)最近的象素。dddd計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.3 bresenham算法設(shè)直線方程為： ，其中k=dy/dx。 因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng)d的初值d00。x下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。 當(dāng)d0.5時(shí)，選擇當(dāng)前象素的右上方象素（ ），修改比較的基點(diǎn)為改點(diǎn)，即將d-1 而當(dāng)d0.5時(shí)，選擇當(dāng)前象素的右方象素（ ），此時(shí)不改變基點(diǎn)為方便計(jì)算，令ed-0.5，e的初值為-0.5，增量為k。 當(dāng)e0時(shí)，取當(dāng)前象素（xi，yi）的右上方象素（ ）； 而當(dāng)e0時(shí)，更接近于右方象素（ ）。kyxxkyyiiiii)(111,1iiyxiiyx,11,1ii

14、yxiiyx,1計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.3 bresenham算法例：line: p0(0, 0), p1(5,2) k=dy/dx=0.4 x y e 0 0 -0.5 1 0 -0.1 2 1 0.3 3 1 -0.3 4 2 0.1 5 2 -0.5 e每次加k，若e大于零則y加1且e減1， 若e小于零則不變0 1 2 3 4 5321計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.3 bresenham算法 void bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx =

15、 x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.3 bresenham算法 可以改用整數(shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換： dxee*2計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.1.3 bresenham算法 void bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, d

16、x, dy,e; dx = x1-x0, dy = y1- y0; e=- dx, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+2*dy; if (e0) y+, e=e-2*dx; int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0; k=dy/dx,e=-0.5;x=x0, y=y0;for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; 計(jì)算機(jī)圖形學(xué)福建師

17、范大學(xué)2.1.3 bresenham算法 y每次增k 誤差項(xiàng)每次也增k （同dda算法） 通過(guò) 交點(diǎn) 與 基點(diǎn) 的距離 d 來(lái)判斷 為了用正負(fù)號(hào)判斷， ed-0.5 為了變?yōu)檎麛?shù)算法 最終，bresenham算法也是每個(gè)象素，需一個(gè)整數(shù)算法， 其優(yōu)點(diǎn)是可以用于其他二次曲線。dxee*2計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.2 圓弧的掃描轉(zhuǎn)換算法 圓的特征：圓的特征：八對(duì)稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個(gè)圓弧的象素集 中點(diǎn)畫(huà)圓法中點(diǎn)畫(huà)圓法 考慮中心在原點(diǎn)，半徑為r 的第二個(gè)8分圓， 構(gòu)造判別式（圓方程）222)5 . 0() 1()5 . 0, 1()(ryxyxfmfdppppp=(xp,y

18、p)p1p2m計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.2 圓弧的掃描轉(zhuǎn)換算法若 d=0, 則應(yīng)取p2為下一象素，而且下一象素的判別式為 第 一個(gè)象素是（0,r），判別式d的初始值為32) 5 . 0()2() 5 . 0, 2(222pppppxdryxyxfd5)( 2) 5 . 1() 2() 5 . 1, 2(222ppppppyxdryxyxfdrrfd25. 1)5 . 0, 1 (0計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.2 圓弧的掃描轉(zhuǎn)換算法 midpointcircle(int r int color) int x,y; float d; x=0; y=r; d=1.25-r; circlepoint

19、s (x,y,color); /顯示圓弧上的八個(gè)對(duì)稱點(diǎn) while(x=y) if(d0時(shí) ，0時(shí)） 為了改為整數(shù)算法 e=d-0.25代替d計(jì)算機(jī)圖形學(xué)福建師范大學(xué)小結(jié) 2.1 直線段的掃描轉(zhuǎn)換算法2.1.1 數(shù)值微分(dda)法2.1.2 中點(diǎn)畫(huà)線法2.1.3 bresenham算法 2.2 圓弧的掃描轉(zhuǎn)換算法計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 多邊形的表示方法多邊形的表示方法頂點(diǎn)表示頂點(diǎn)表示點(diǎn)陣表示點(diǎn)陣表示 頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。 點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的

20、幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 多邊形的掃描轉(zhuǎn)換：多邊形的掃描轉(zhuǎn)換：把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 區(qū)域區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。 區(qū)域填充區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3 多邊形的掃描轉(zhuǎn)換

21、與區(qū)域填充 區(qū)域表示方法：區(qū)域表示方法：內(nèi)點(diǎn)表示、邊界表示 內(nèi)點(diǎn)表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色 邊界表示邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)逐點(diǎn)判斷算法 逐點(diǎn)判斷算法：逐個(gè)像素判別其是否位于多邊形內(nèi)部 判斷一個(gè)點(diǎn)是否位于多邊形內(nèi)部：射線法 從當(dāng)前像素發(fā)射一條射線，計(jì)算射線與多邊形的交點(diǎn)個(gè)數(shù) 內(nèi)部：奇數(shù)個(gè)交點(diǎn) 外部：偶數(shù)個(gè)交點(diǎn)計(jì)算機(jī)圖形學(xué)福建師范大學(xué)逐點(diǎn)判斷算法判斷一點(diǎn)是否位于多邊形內(nèi)部？計(jì)

22、算機(jī)圖形學(xué)福建師范大學(xué)逐點(diǎn)判斷算法 算法描述for(y=0; y=y_resolution; y+)for(x=0; x i 結(jié)點(diǎn)的x值遞增x； /* polyfill */計(jì)算機(jī)圖形學(xué)福建師范大學(xué)思考題 已知多邊形p=(p0p1p2p3p4p5p6p0)；其各邊坐標(biāo)分別為 （2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2） 建立其新邊表和活性邊表計(jì)算機(jī)圖形學(xué)福建師范大學(xué)新邊表計(jì)算機(jī)圖形學(xué)福建師范大學(xué)y=3y=8活動(dòng)邊表的例子計(jì)算機(jī)圖形學(xué)福建師范大學(xué)掃描線算法小結(jié) 建立新邊表 按照掃描線順序處理 每條掃描線構(gòu)造活性邊表（x遞增插入排序） 中間考慮交點(diǎn)取舍 根據(jù)當(dāng)前

23、活性邊表選取像素進(jìn)行填充（x方向） 從活性邊表中刪除y max= i 的結(jié)點(diǎn)計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.1.2邊界標(biāo)志算法 基本思想：幀緩沖器中對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過(guò)的象素打上標(biāo)志。 填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問(wèn)該掃描線上的象素。取一個(gè)布爾變量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。inside 的初始值為假，每當(dāng)當(dāng)前訪問(wèn)象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)邊標(biāo)志算法-例子多邊形p0p1p2p3p

24、4頂點(diǎn)坐標(biāo)為（2,1）,(2,7),(8,5),(8,1),(6,4),以掃描線y=3為例說(shuō)明填充過(guò)程。開(kāi)始時(shí)inside=0.1）對(duì)于x=0，該像素未置成邊界值，inside=0，該點(diǎn)為背景色；2）對(duì)于x=1，同上；3）對(duì)于x=2，該像素已置成邊界色，inside取反后為1，該點(diǎn)被置成多邊形顏色；4）對(duì)于x=3，4，像素未置成邊界色，由于inside=1，所以點(diǎn)被置成多邊形顏色；5）對(duì)于x=5，像素被置成邊界色，inside取反后為0，該點(diǎn)被置成背景色；6）對(duì)于x=6，像素未置成邊界色，由于inside=0，所以點(diǎn)被置成背景色；7）對(duì)于x=7，像素被置成邊界色，inside取反后為1，該點(diǎn)被

25、置成多邊形顏色；8）對(duì)于x=8，像素被置成邊界色，inside取反后為0，該點(diǎn)被置成背景色；計(jì)算機(jī)圖形學(xué)福建師范大學(xué)算法過(guò)程void edgemark_fill(polydef, color)多邊形定義 polydef； int color; 對(duì)多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； for (每條與多邊形polydef相交的掃描線y ) inside = false; for (掃描線上每個(gè)象素x ) if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= false) drawpixel (x, y, color); else drawpi

26、xel (x, y, background); 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.1.2邊界標(biāo)志算法 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同， 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2區(qū)域填充算法 區(qū)域區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。 區(qū)域填充區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2區(qū)域填充算法 區(qū)域表示方法：區(qū)域表示方法：內(nèi)點(diǎn)表示、邊界

27、表示 內(nèi)點(diǎn)表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素著同一個(gè)顏色邊界像素著與內(nèi)部像素不同的顏色 邊界表示邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色表示內(nèi)點(diǎn)表示邊界點(diǎn)計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2區(qū)域填充算法 區(qū)域填充要求區(qū)域是連通的區(qū)域填充要求區(qū)域是連通的 連通性連通性: : 4連通、8連通 4 4連通：連通： 8 8連通連通計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2區(qū)域填充算法 4 4連通與連通與8 8連通區(qū)域的區(qū)別連通區(qū)域的區(qū)別連通性：連通性： 4 4連通可看作連通可看作8 8連通區(qū)域，但對(duì)邊界有要連通區(qū)域，但對(duì)邊界有要求求對(duì)邊界的要求對(duì)邊界

28、的要求計(jì)算機(jī)圖形學(xué)福建師范大學(xué)a：適合于內(nèi)點(diǎn)表示區(qū)域的填充算法設(shè)g為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，oldcolor為g的原色?，F(xiàn)取(x,y)為種子點(diǎn)對(duì)區(qū)域g進(jìn)行填充：即先置像素(x,y)的顏色為newcolor，然后逐步將整個(gè)區(qū)域g都置為同樣的顏色。 步驟如下：種子象素入棧，當(dāng)棧非空時(shí)，執(zhí)行如下三步操作： （1）棧頂象素出棧； （2）將出棧象素置成多邊形色； （3）按上、下、左、右的順序檢查與出棧象素相鄰的四個(gè)象素，若其中某個(gè)象素不在邊界上且未置成多邊形色，則把該象素入棧。2.3.2.1區(qū)域填充的遞歸算法（種子填充算法）計(jì)算機(jī)圖形學(xué)福建師范大學(xué)種子填充算法例子 多 邊 形 由 p0

29、p1p2p3p4構(gòu) 成 ，p0(1,5)p1(5,5)p2(7,3)p3(7,1)p4(1,1) 設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2.1區(qū)域填充的遞歸算法 內(nèi)點(diǎn)表示內(nèi)點(diǎn)表示的4連通區(qū)域的遞歸填充算法: void floodfill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /屬于區(qū)域內(nèi)點(diǎn)oldcolordrawpixel(x,y,newcolor);floodfill4(x,y+1,oldcolor,n

30、ewcolor);floodfill4(x,y-1,oldcolor,newcolor);floodfill4(x-1,y,oldcolor,newcolor);floodfill4(x+1,y,oldcolor,newcolor); 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2.1區(qū)域填充的遞歸算法 邊界表示邊界表示的4連通區(qū)域的遞歸填充算法: void boundaryfill4(int x,int y,int boundarycolor,int newcolor) int color=getpixel(x,y);if(color!=newcolor & color!=boundarycolor)d

31、rawpixel(x,y,newcolor);boundaryfill4 (x,y+1, boundarycolor,newcolor);boundaryfill4 (x,y-1, boundarycolor,newcolor);boundaryfill4 (x-1,y, boundarycolor,newcolor);boundaryfill4 (x+1,y, boundarycolor,newcolor); 計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 該算法也可以填充有孔區(qū)域。該算法也可以填充有孔區(qū)域。 缺點(diǎn)缺點(diǎn)： (1) 有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。 (2) 遞歸執(zhí)行，算法簡(jiǎn)單，但效率

32、不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。 改進(jìn)算法，減少遞歸次數(shù)，提高效率。解決方法是用掃描線填充算法2.3.2.1區(qū)域填充的遞歸算法計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2.2區(qū)域填充的掃描線算法 目標(biāo)：減少遞歸層次 適用于內(nèi)點(diǎn)表示的4連通區(qū)域 算法步驟： 首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段 然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。 反復(fù)這個(gè)過(guò)程，直到填充結(jié)束。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.3.2.2區(qū)域填充的掃描線算法 (1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。 (2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以

33、y作為當(dāng)前掃描線。 (3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。 (4)并確定新的種子點(diǎn)：在區(qū)間xl，xr中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。 上述算法對(duì)于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)掃描線算法分析（舉例分析） 該算法也可以填充有孔區(qū)域。 像素中的序號(hào)標(biāo)指它所在區(qū)段位于堆棧中的位置計(jì)算機(jī)圖形學(xué)福建師范大學(xué)掃描線算法分析（舉例分析

34、）計(jì)算機(jī)圖形學(xué)福建師范大學(xué)掃描線算法分析（舉例分析）計(jì)算機(jī)圖形學(xué)福建師范大學(xué)掃描線算法分析（舉例分析）計(jì)算機(jī)圖形學(xué)福建師范大學(xué)多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較聯(lián)系：都是光柵圖形面著色，用于真實(shí)感圖形顯示?？上嗷マD(zhuǎn)換。多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問(wèn)題：當(dāng)給定多邊形內(nèi)一點(diǎn)為種子點(diǎn)，并用bresenham或dda算法將多邊形的邊界表示成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點(diǎn)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較 不同點(diǎn)： 1.基本思想不同；前者是頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，后者只改變

35、區(qū)域內(nèi)填充顏色，沒(méi)有改變表示方法。 2.對(duì)邊界的要求不同 前者只要求掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)。后者：區(qū)域封閉，防止遞歸填充跨界。 3.基本的條件不同 前者：從邊界頂點(diǎn)信息出發(fā)。 后者：區(qū)域內(nèi)種子點(diǎn)。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)第二章 光柵圖形學(xué) 2.1直線段的掃描轉(zhuǎn)換算法 2.2圓弧的掃描轉(zhuǎn)換算法 2.3多邊形的掃描轉(zhuǎn)換與區(qū)域填充 2.4字符 2.5裁剪 2.6反走樣 2.7消隱計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.4 字符 字符指數(shù)字、字母、漢字等符號(hào)。 計(jì)算機(jī)中字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)。 國(guó)際上最流行的字符集：“美國(guó)信息交換用標(biāo)準(zhǔn)代碼集”，簡(jiǎn)稱ascii碼。它是用7位二進(jìn)制數(shù)進(jìn)行編碼表示128

36、個(gè)字符；包括字母、標(biāo)點(diǎn)、運(yùn)算符以及一些特殊符號(hào)。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集：gb231280。該字符集分為94個(gè)區(qū)，94個(gè)位，每個(gè)符號(hào)由一個(gè)區(qū)碼和一個(gè)位碼共同標(biāo)識(shí)。區(qū)碼和位碼各用一個(gè)字節(jié)表示。 為了能夠區(qū)分ascii碼與漢字編碼，采用字節(jié)的最高位來(lái)標(biāo)識(shí)：最高位為0表示ascii碼；最高位為1表示表示漢字編碼。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 字庫(kù)：為了在顯示器等輸出設(shè)備上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字庫(kù)。字庫(kù)中存儲(chǔ)了每個(gè)字符的形狀信息，字庫(kù)分為矢量型和點(diǎn)陣型兩種。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 點(diǎn)陣字符點(diǎn)陣字符: 每個(gè)字符由一個(gè)位圖表示，該位為1表示字符的筆畫(huà)經(jīng)過(guò)此位，對(duì)應(yīng)于此位

37、的象素應(yīng)置為字符顏色。該位為0表示字符的筆畫(huà)不經(jīng)過(guò)此位，對(duì)應(yīng)于此位的象素應(yīng)置為背景顏色。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 點(diǎn)陣字符 點(diǎn)陣字庫(kù)中的位圖表示1111110001010101010101010111110001010101010101011111110000000000計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 在實(shí)際應(yīng)用中，有多種字體（如宋體、楷體等），每種字體又有多種大小型號(hào)，因此字庫(kù)的存儲(chǔ)空間是很龐大的。解決這個(gè)問(wèn)題一般采用壓縮技術(shù)。 點(diǎn)陣字符的顯示分為兩步。首先從字庫(kù)中將它的位圖檢索出來(lái)。然后將檢索到的位圖寫(xiě)到幀緩沖器中。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 矢量字符矢量字符:記錄字符的筆畫(huà)信息，而不是整個(gè)位圖，

38、具有存儲(chǔ)空間小，美觀、變換方便等優(yōu)點(diǎn)。對(duì)于字符的旋轉(zhuǎn)、縮放等變換， 點(diǎn)陣字符的變換需要對(duì)表示字符位圖中的每一象素進(jìn)行； 矢量字符的變換只要對(duì)其筆畫(huà)端點(diǎn)進(jìn)行變換就可以了。矢量字符的顯示也分為兩步。 計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 顯示：首先從字庫(kù)中將它的字符信息。然后取出端點(diǎn)坐標(biāo)，對(duì)其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示出字符。 點(diǎn)陣字符 點(diǎn)陣字庫(kù)中的位圖表示 矢量輪廓字符1111110001010101010101010111110001010101010101011111110000000000計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 特點(diǎn)： 點(diǎn)陣字符：存儲(chǔ)量大，易于顯示 矢量字符：存儲(chǔ)量小，美觀，變換方便

39、; 但需要光柵化后才能顯示。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)字符屬性字符屬性字體 宋體 仿宋體 楷體 黑體 隸書(shū)字高 宋體 宋體 宋體 宋體字寬字傾斜角傾斜 傾斜對(duì)齊 (左對(duì)齊、中心對(duì)齊、右對(duì)齊)字色 紅色紅色、綠色綠色、藍(lán)色藍(lán)色 大 海 大 海 大 海 大 海計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5 裁剪 裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過(guò)程稱為裁剪裁剪。 在使用計(jì)算機(jī)處理圖形信息時(shí)，計(jì)算機(jī)內(nèi)部存儲(chǔ)的圖形往往比較大，而屏幕顯示的只是圖的一部分。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 問(wèn)：為什么要裁減，直接處理呢？即：在繪制（寫(xiě)幀緩存時(shí)）再處理？ 計(jì)算機(jī)

40、圖形學(xué)福建師范大學(xué) 最簡(jiǎn)單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點(diǎn)之后，再判斷各點(diǎn)是否在窗內(nèi)。但那樣太費(fèi)時(shí)，一般不可取。這是因?yàn)橛行﹫D形組成部分全部在窗口外，可以完全排除，不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5.1直線段裁剪 直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過(guò)折線段來(lái)近似，從而裁剪問(wèn)題也可以化為直線段的裁剪問(wèn)題。 2.5.1.1cohen-sutherland 2.5.1.2中點(diǎn)分割算法 2.5.1.3梁友棟barskey算法。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5.1.1 cohen-sutherland裁剪 基本思想：對(duì)于每條線段p1p2

41、分為三種情況處理分為三種情況處理: （1）若p1p2完全在窗口內(nèi)，則顯示該線段p1p2簡(jiǎn)稱“取”之。 （2）若p1p2明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。 （3）若線段不滿足“取”或 “棄”的條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 為快速判斷，采用如下編碼方法：每個(gè)區(qū)域賦予4位編碼otheryycotheryycbt0101minmaxotherxxcotherxxclr0101minmaxlrbtcccc計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 編碼 線段裁剪10011000101000010000001001010100011

42、0p1p2p3p4計(jì)算機(jī)圖形學(xué)福建師范大學(xué)若p1p2完全在窗口內(nèi)code1=0,且code2=0,則“取”若p1p2明顯在窗口外,code1&code20 （？），則“棄” 在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。 計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 計(jì)算線段p1(x1,y1)p2(x2,y2)與窗口邊界的交點(diǎn)if(left&code !=0)x=xl;y=y1+(y2-y1)*(xl-x1)/(x2-x1);else if(right&code !=0)x=xr;y=y1+(y2-y1)*(xr-x1)/(x2-x1);else if(bottom&code !

43、=0) y=yb;x=x1+(x2-x1)*(yb-y1)/(y2-y1); else if(top & code !=0) y=yt;x=x1+(x2-x1)*(yt-y1)/(y2-y1);計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 示例計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 編碼的思想在圖形學(xué)中非常重要。 sutherland：coons獎(jiǎng), 圖靈獎(jiǎng), ieee 計(jì)算機(jī)先驅(qū)獎(jiǎng)。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5.1.2 中點(diǎn)分割裁剪算法 基本思想： 與前一種cohen-sutherland算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況: 全在、完全不在和線段和窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第

44、三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)求線段與窗口的交點(diǎn) a、b分別為距p0、p1最近的可見(jiàn)點(diǎn)，pm為p0p1中點(diǎn)p0p1pmab計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 從 出發(fā)找最近可見(jiàn)點(diǎn)的方法先求出 的中點(diǎn)若 不是顯然不可見(jiàn)的，并且 在窗口中有可見(jiàn)部分，則距 最近的可見(jiàn)點(diǎn)一定落在 上，所以用 代替 ；0p10ppmpmpp0mpp00pmpp0mpp010pp計(jì)算機(jī)圖形學(xué)福建師范大學(xué)否則取 代替再對(duì)新的 求中點(diǎn) 。重復(fù)上述過(guò)程，直到 長(zhǎng)度小于給定的控制常數(shù)為止，此時(shí) 收斂于交點(diǎn)。 從 出發(fā)找最近可見(jiàn)點(diǎn)采用上面類似方法。10pp1ppm10ppmp1ppmmp1p計(jì)算機(jī)圖

45、形學(xué)福建師范大學(xué) 問(wèn)：算法為什么可行？會(huì)不會(huì)無(wú)限循環(huán)、不斷二分？計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5.1.3梁友棟barsky算法 梁-barsky算法的幾何含義：入邊、出邊與端點(diǎn)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) * 寫(xiě)入圖形學(xué)教科書(shū)的唯一中國(guó)人的算 法 * communication of acm的論文 梁有棟教授的二三事 liang-barsky算法 幾何連續(xù)理論：葉、馬、鄭 從幾何學(xué)與纖維纏繞理論到基因工程計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 參數(shù)化形式寫(xiě)出裁剪條件： 可以統(tǒng)一表示為形式： 入邊 出邊ytyuyybxrxuxxl11kkqup 144113122111yytqypybyqypxxrqxpxlxqx

46、p計(jì)算機(jī)圖形學(xué)福建師范大學(xué) =0且 0，則線段完全在邊界外， 0，則該線段平行于裁剪邊界并且在窗口內(nèi)。kpkqkq計(jì)算機(jī)圖形學(xué)福建師范大學(xué)當(dāng) 0，當(dāng) 0,線段從裁剪邊界延長(zhǎng)線的內(nèi)部延伸到外部。kpkpkp計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 對(duì)于每條直線，可以計(jì)算出參數(shù)u1和u2，它們定義了在裁剪矩形內(nèi)的線段部分u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（p0）。對(duì)這些邊界計(jì)算rk=qk/pk 。u2取1和各個(gè)rk值之中的最小值。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)如果u1u2，則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)u的兩個(gè)值u1,u2計(jì)算出來(lái)。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)void lb_lineclip

47、(x1,y1,x2,y2,xl,xr,yb,yt)float x1,y1,x2,y2,xl,xr,yb,yt;float dx,dy,u1,u2;u1=0;u2=1 ; dx =x2-x1;dy =y2-y1; if(clipt(-dx,x1-xl,&u1,&u2) if(clipt(dx,xr-x1, &u1,&u2)if(clipt(-dy,y1-yb, &u1,&u2) if(clipt(dy,yt-y1, &u1,&u2) displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy)return; 計(jì)算機(jī)圖形學(xué)福建師范大學(xué)bool clipt(p,

48、q,u1,u2)float p,q,*u1,*u2; float r;if(p*u2) return false;else if(r*u1) *u1=r; return true; 。/下頁(yè)計(jì)算機(jī)圖形學(xué)福建師范大學(xué)else if(p0) r=p/q;if(r*u1)return false;else if(r*u2) *u2=r;return true; else if(q0) return false; return true;計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 裁減的插曲： 汪嘉業(yè)的快速算法 80年代的裁減熱：應(yīng)道寧(工程圖學(xué)研究所)、 汪國(guó)昭（圖形圖像研究所） 對(duì)三種算法比較: cohen-sut

49、herland與中點(diǎn)法在區(qū)域碼測(cè)試階段能以位運(yùn)算方式高效率地進(jìn)行，因而當(dāng)大多數(shù)線段能夠簡(jiǎn)單的取舍時(shí)，效率較好。 梁友棟barskey算法只能應(yīng)用于矩形窗口的情形，但其效率比前兩者要高，這是因?yàn)檫\(yùn)算只涉及到參數(shù)，僅到必要時(shí)才進(jìn)行坐標(biāo)計(jì)算。計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5.2 多邊形裁剪 基本思想是一次用窗口的一條邊裁剪多邊形。 考慮窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線 該線把平面分成兩個(gè)部分:可見(jiàn)一側(cè)；不可見(jiàn)一側(cè)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 多邊形的各條邊的兩端點(diǎn)s、p。它們與裁剪線的位置關(guān)系只有四種可見(jiàn)一側(cè)可見(jiàn)一側(cè)可見(jiàn)一側(cè)可見(jiàn)一側(cè)spsssppp(1)(2)(3)(4)對(duì)于情況（1）僅輸出頂點(diǎn)p情況（

50、2）輸出0個(gè)頂點(diǎn)情況（3）輸出線段sp與裁剪線的交點(diǎn)i情況（4）輸出線段sp與裁剪線的交點(diǎn)i和終點(diǎn)p計(jì)算機(jī)圖形學(xué)福建師范大學(xué)上述算法僅用一條裁剪邊對(duì)多邊形進(jìn)行裁剪，得到一個(gè)頂點(diǎn)序列，作為下一條裁剪邊處理過(guò)程的輸入。對(duì)于每一條裁剪邊，只是判斷點(diǎn)在窗口哪一側(cè)以及求線段sp與裁剪邊的交點(diǎn)算法應(yīng)隨之改變。計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 示意圖(5之1)p1p2p3p4p5p6p7p8p9p10r1r2計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 示意圖(5之2)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 示意圖(5之3)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 示意圖(5之4)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 示意圖(5之5)計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 其他窗口的裁剪

51、圓域窗口裁剪：潛望鏡、. 任意(凸)多邊形裁剪：個(gè)性化電腦顯示器定制，計(jì)算機(jī)圖形學(xué)福建師范大學(xué)2.5.3 字符裁剪 串精度:將包圍字串的外接矩形對(duì)窗口作裁剪 字符精度:將包圍字的外接矩形對(duì)窗口作裁剪 以及筆畫(huà)象素精度:將筆劃分解成直線段對(duì)窗口作裁剪 待裁剪字符串 串精度裁剪 字符精度裁剪 象素精度裁剪stringstring2string2ringstring2stringstring2計(jì)算機(jī)圖形學(xué)福建師范大學(xué) 用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣走樣(aliasing) 用于減少或消除這種效果的技術(shù)稱為反走反走樣樣(antialiasing) 2.6.1提高分辨率 2.6.2 區(qū)域采樣 2.6.3 加權(quán)區(qū)域取樣2.6 2.6 反走樣反走樣計(jì)算機(jī)圖形學(xué)福