計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法課件

1、計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 DDA方法 Bresenham算法 中點(diǎn)圓生成算法 多邊形表示方法 多邊形填充的掃描線算法 邊緣填充算法 邊界標(biāo)志算法 區(qū)域的基本概念 簡(jiǎn)單種子填充算法 掃描線種子填充算法 光柵圖形的反走樣算法光柵圖形的反走樣算法計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 畫圖Word中的圖文編輯工具AutoCADPhotoshop等大型繪圖軟件 OpenGL就是一個(gè)典型的、已經(jīng)被接受的國際工業(yè)標(biāo)準(zhǔn)的圖形軟件包。 Java3D 如Windows中Win32API中就提供了基本的繪圖功能計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 在數(shù)學(xué)上，理想的直線是一條由無窮多個(gè)無限小的

2、連續(xù)的點(diǎn)組成。 在光柵顯示平面上，我們只能用二維光柵格網(wǎng)上盡可能靠近這條直線的象素點(diǎn)的集合來表示它。每個(gè)象素具有一定的尺寸，是顯示平面上可被訪問的最小單位，它的坐標(biāo)x和y只能是整數(shù)，也就是說相鄰象素的坐標(biāo)值是階躍的而不是連續(xù)的。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 上述算法擴(kuò)展到任一八分圓坐標(biāo)空間圖，

3、從而形成一般的Bresenham算法。下圖是各象限的判斷條件。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法例題2：已知起點(diǎn)A(20,10)和終點(diǎn)B(30,18)，用Bresenham法在A和B之間生成一段直線。解：解：x=10, y= 8 ,斜率在0和1之間；ixiyi12010 x加1，y加122111x加1，y加132212x加1，y不變42312x加1，y加152413x加1，y加162514x加1，y加172615x加1，y加182716x加1，y不變92816x加1，y加1102917x加1，y加1計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 圓心位于

4、原點(diǎn)的圓有四條對(duì)稱軸x=0、y=0、y=x和y=x，見下圖。從而若已知圓弧上一點(diǎn)P(x，y)，就可以得到其關(guān)于四條對(duì)稱軸的七個(gè)對(duì)稱點(diǎn)，這種性質(zhì)稱為八分對(duì)稱性。因此只要能畫出八分之一的圓弧，就可以利用對(duì)稱性的原理得到整個(gè)圓弧。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法圖a圖b計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 di0di0計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法輸入:圓的半徑R；算法步驟：計(jì)算初始決策變量值d=1.25-R、x=0、y=R；繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱點(diǎn)；判斷決策變量d的符號(hào)：

5、若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)；當(dāng)x=y時(shí)，重復(fù)步驟3和4。否則結(jié)束。void midPointCircle(int r)float d;x=0;y=r;d=1.25-r;while(x=y)draw(x,y);/繪制點(diǎn)(x,y)及其七個(gè)對(duì)稱點(diǎn)；if(d0) d+=x*2.0+3; elsed+=2.0*(x-y)+5;y-; x+;計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法是用多邊形的頂點(diǎn)的序列來描述多邊形，該表示幾何意義強(qiáng)、占內(nèi)存少，但不能直觀地說明哪些像素在多邊形內(nèi)；是用位

6、于多邊形內(nèi)的象素的集合來刻劃多邊形，該方法雖然沒有多邊形的幾何信息，但具有面著色所需要的圖像表示形式；就是，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素，并將幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度或顏色。 多邊形頂點(diǎn)表示多邊形點(diǎn)陣表示計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 填充條件：多邊形的頂點(diǎn)序列(Pi，i=0，1，n)、填充色。對(duì)多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。 多邊形內(nèi)點(diǎn)的判別準(zhǔn)則從測(cè)試點(diǎn)引出一條伸向無窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，那么：若射線與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，則該點(diǎn)為內(nèi)點(diǎn)；若交點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，則該點(diǎn)為外點(diǎn)。 奇異點(diǎn)上述的判別準(zhǔn)則，在大多數(shù)情況下是

7、正確的，但當(dāng)水平掃描線正好通過多邊形頂點(diǎn)時(shí)，要特別注意。例如，圖中過頂點(diǎn)的射線1、射線6，它們與多邊形的交點(diǎn)個(gè)數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點(diǎn)，但實(shí)際上卻是外點(diǎn)。 而圖中過頂點(diǎn)的射線3、射線5，對(duì)于判別準(zhǔn)則的使用又是正確的。 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法奇異點(diǎn)的處理將多邊形的頂點(diǎn)分為兩大類：局部極值點(diǎn)：如圖中的點(diǎn)P1、P2、P4和P6。對(duì)于這些點(diǎn)來說，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的同一側(cè)。非極值點(diǎn)：如圖中的點(diǎn)P3、P5。對(duì)于這些點(diǎn)來說，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的兩側(cè)。處理奇異點(diǎn)規(guī)則對(duì)于局部極值點(diǎn)，應(yīng)看成兩個(gè)點(diǎn)；對(duì)于非極值點(diǎn)，應(yīng)看成一個(gè)點(diǎn)。

8、計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 逐點(diǎn)判別算法求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。 對(duì)包圍盒中的每個(gè)象素引水平射線進(jìn)行測(cè)試。 求出該射線與多邊形每條邊的有效交點(diǎn)個(gè)數(shù)。 如果個(gè)數(shù)為奇數(shù)：該點(diǎn)置為填充色。 逐點(diǎn)判別算法雖然簡(jiǎn)單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)要做大量的乘除運(yùn)算，從而影響了填充速度。 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法邊相關(guān)掃描線多邊形填充算法 邊相關(guān)掃描線填充算法比逐點(diǎn)判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。 該算法利用了掃

9、描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 掃描線的相關(guān)性：掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點(diǎn)時(shí)才會(huì)發(fā)生改變。見下圖(a)。 邊的相關(guān)性：邊的相關(guān)性：由于相鄰掃描線上的交點(diǎn)是與多邊形的邊線相關(guān)的。對(duì)同一條邊，前一條掃描線yi與該邊的交點(diǎn)為xi，而后一條掃描線yi+1=yi+1與該邊的交點(diǎn)則為xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運(yùn)算。見下圖(b)所示。(a)掃描線的相關(guān)性掃描線的相關(guān)性(b)邊的相關(guān)性邊的相關(guān)性計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 邊

10、相關(guān)掃描線填充算法的實(shí)現(xiàn)需要建立兩個(gè)表：邊表（ET）和活動(dòng)邊表（AET）。 邊表（邊表（ET：Edge Table）用來對(duì)除水平邊外的所有邊進(jìn)行登記，來建立邊的記錄。邊的記錄定義為： 第一項(xiàng)：某邊的最大y值（ymax）。注意要進(jìn)行奇異點(diǎn)處理：對(duì)于非極值點(diǎn)應(yīng)該ymax=ymax-1。 第二項(xiàng)：某邊的最小的y對(duì)應(yīng)的x值。 第三項(xiàng)：某邊斜率的倒數(shù):1/m。 第四項(xiàng)：指針。用來指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項(xiàng)置空計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 活動(dòng)邊表（活動(dòng)邊表（AET：Active Edge Table）：）：ET表建立以后，就可以開始掃描轉(zhuǎn)換了。對(duì)不同的掃描線，與之

11、相交的邊線也是不同的，當(dāng)對(duì)某一條掃描線進(jìn)行掃描轉(zhuǎn)換時(shí)，我們只需要考慮與它相交的那些邊線，為此需要建立一個(gè)只與當(dāng)前掃描線相交的邊記錄鏈表，稱之為活動(dòng)邊表。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法根據(jù)給出的多邊形頂點(diǎn)坐標(biāo)，建立ET表； 求出頂點(diǎn)坐標(biāo)中最大y值ymax和最小y值ymin。初始化AET表指針，使它為空。使用掃描線的yj值作為循環(huán)變量，使其初值為ymin。 對(duì)于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：如果ET表中yj桶非空，則將yj桶中的全部記錄合并到AET表中。對(duì)AET表鏈中的記錄按x的大小從小到大排序。依次取出AET表各記錄中的x

12、i坐標(biāo)值，兩兩配對(duì)填充，即將每對(duì)xi之間的象素填上所要求的顏色。如果AET表中某記錄的ymax=yj，則刪除該記錄。對(duì)于仍留在AET表中的每個(gè)記錄，用xi+1/m代替xi進(jìn)行修改，這就是該記錄的邊線與下一條掃描線yj+1的交點(diǎn)。使yj加1，以便進(jìn)入下一輪循環(huán)。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法 對(duì)多邊形P的每一非水平邊（i=0,1,n）上的各像素做運(yùn)算即可，見下圖，其中(a)為給定的多邊形；(b)為對(duì)區(qū)域賦初值；(c)，(d)，(e)和(f)表示逐邊向右求反。 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法首先用一種在幀緩沖器中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來。然后再把位于多邊形

13、內(nèi)的各個(gè)像素著上所需的顏色 步驟1：以值為boundary-color 的特殊顏色勾畫多邊形的邊界。設(shè)多邊形頂點(diǎn)為Pi= (xi, yi),0in， xi, yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點(diǎn)的個(gè)數(shù)必定是偶數(shù)(包括零)。步驟2：設(shè)interior_point 是一布爾變量。對(duì)每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前是像素位于多邊形內(nèi)，則interior_point=true，需要填上值為polygon_color的顏色；否則該像素在多邊形外，需要填上值background_color的顏色 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法3.5.1 3.5.1 區(qū)域的基本

14、概念區(qū)域的基本概念 區(qū)域是指已經(jīng)表示成點(diǎn)陣形式的像素集合在光柵圖形中，區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種形式進(jìn)行描述。 區(qū)域填充是指先將區(qū)域內(nèi)的一點(diǎn)(常稱種子點(diǎn))賦予給定顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過程。計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法區(qū)域填充的基本概念區(qū)域填充的基本概念內(nèi)點(diǎn)表示法：把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點(diǎn)表示法。邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。圖3.25內(nèi)點(diǎn)表示的區(qū)域圖3.26邊界表示的區(qū)域計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法區(qū)域填充的基本概念區(qū)域填充的基本概念 4連通的區(qū)域: 取區(qū)域內(nèi)任意兩點(diǎn)，在該區(qū)域

15、內(nèi)若從其中一點(diǎn)出發(fā)通過上、下、左、右四種運(yùn)動(dòng)可到達(dá)另一點(diǎn)。圖3.27四個(gè)方向的運(yùn)動(dòng)8連通區(qū)域: 取區(qū)域內(nèi)任意兩點(diǎn)，若從其中任一點(diǎn)出發(fā)，在該區(qū)域內(nèi)通過沿水平方向、垂直方向和對(duì)角線方向的八種運(yùn)動(dòng)可到達(dá)另一點(diǎn)。圖3.28個(gè)方向的運(yùn)動(dòng)計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法區(qū)域填充的基本概念區(qū)域填充的基本概念4連通區(qū)域也可理解成8連通區(qū)域，但是兩者的邊界不盡相同。如果圖中標(biāo)有號(hào)的象素組成的區(qū)域作為4連通區(qū)域，則其邊界由圖中的標(biāo)有號(hào)的象素組成。如果將該區(qū)域作為8連通的區(qū)域，則其邊界由圖中標(biāo)有號(hào)和號(hào)的兩種象素組成。 圖3.29內(nèi)點(diǎn)表示的八連通區(qū)域圖3.30邊界表示的八連通區(qū)域圖3.31四連通區(qū)域與八連通區(qū)

16、域的不同邊界計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法3.5.2 3.5.2 簡(jiǎn)單的種子填充算法簡(jiǎn)單的種子填充算法基本思想：給定區(qū)域G一種子點(diǎn)（x, y）首先判斷該點(diǎn)是否是區(qū)域內(nèi)的一點(diǎn)，如果是，則將該點(diǎn)填充為新的顏色，然后將該點(diǎn)周圍的四個(gè)點(diǎn)（四連通）或八個(gè)點(diǎn)（八連通）作為新的種子點(diǎn)進(jìn)行同樣的處理，通過這種擴(kuò)散完成對(duì)整個(gè)區(qū)域的填充 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法3.5.3 3.5.3 掃描線種子填充算法掃描線種子填充算法基本思想：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來。反復(fù)進(jìn)行這個(gè)過程，直到所保存的各區(qū)

17、段都填充完畢計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法掃描線種子填充算法掃描線種子填充算法算法步驟：步驟步驟 1：將算法設(shè)置的堆棧置為空。將給定的種子點(diǎn)（x, y）壓入堆棧。步驟步驟 2：如果堆棧為空，算法結(jié)束；否則取棧頂元素（x, y）作為種子點(diǎn)。步驟步驟 3：從種子點(diǎn)（x, y）開始，沿縱坐標(biāo)為y的當(dāng)前掃描線向左右兩個(gè)方向逐個(gè)像素用新的顏色值進(jìn)行填充，直到邊界為止。設(shè)區(qū)間兩邊界的橫坐標(biāo)分別為xleft 和xright。步驟步驟4 4：在與當(dāng)前掃描線相鄰的上下兩條掃描線上，以區(qū)間xleft,xright為搜索范圍，求出需要填充的各小區(qū)間，把各小區(qū)間中最右邊的點(diǎn)并作為種子點(diǎn)壓入堆棧，轉(zhuǎn)到步驟2。

18、 計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法掃描線種子填充算法掃描線種子填充算法執(zhí)行過程圖3.32掃描線種子填充算法的執(zhí)行過程121212123計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法3.6.1 光柵圖形的走樣現(xiàn)象光柵圖形的走樣現(xiàn)象 圖形的邊界一般都呈階梯形 圖形的細(xì)節(jié)失真、狹小圖形遺失 （a） 待顯示的細(xì)小圖形（b） 顯示結(jié)果圖3.35 細(xì)節(jié)失真（a）待顯示的狹小矩形（b） 顯示結(jié)果圖3.36 狹小圖形的遺失狹小圖形遺失和運(yùn)動(dòng)圖形的閃光現(xiàn)象 圖3.33階梯形邊界圖圖3.34階梯形線段計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法3.6.2 3.6.2 提高分辨率的反走樣方法提高分辨率的反走樣方法提高分辨率的方法：提高分辨率的方法 采用硬件:采用高分辨率的光柵圖形顯示器，花費(fèi)的代價(jià)大。 采用軟件:花費(fèi)的代價(jià)小，也容易實(shí)現(xiàn)。用軟件提高分辨率的方法是：高分辨率計(jì)算，低分辨率顯示。高分辨率計(jì)算：將低分辨的圖形顯示象素劃分為許多子象素，如22劃分，33劃分等，然后按通常的算法計(jì)算出各個(gè)子象素的顏色值或灰度值。低分辨率顯示：將一象素內(nèi)的各個(gè)子象素的顏色值或灰度值的平均值作為該象素的顏色值或灰度值。求平均值時(shí)可取算術(shù)平均，也可取加權(quán)平均。 圖3.37加權(quán)表計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法3.6.33.6.