基本光柵圖形生成算法

基本光柵圖形生成算法2023/6/18第一頁，共四十一頁，編輯于2023年，星期日在計算機(jī)上繪圖的一般方法用現(xiàn)有繪圖軟件系統(tǒng)畫圖\Word中的圖文編輯工具\AutoCAD\Photoshop等大型繪圖軟件用繪圖軟件包OpenGL就是一個典型的、已經(jīng)被接受的國際工業(yè)標(biāo)準(zhǔn)的圖形軟件包。Java3D用操作系統(tǒng)的繪圖功能如Windows中Win32API中就提供了基本的繪圖功能第二頁，共四十一頁，編輯于2023年，星期日在數(shù)學(xué)上，理想的直線是一條由無窮多個無限小的連續(xù)的點組成。在光柵顯示平面上，我們只能用二維光柵格網(wǎng)上盡可能靠近這條直線的象素點的集合來表示它。每個象素具有一定的尺寸，是顯示平面上可被訪問的最小單位，它的坐標(biāo)x和y只能是整數(shù)，也就是說相鄰象素的坐標(biāo)值是階躍的而不是連續(xù)的。直線生成算法第三頁，共四十一頁，編輯于2023年，星期日DDA算法描述設(shè)(xs,ys)和(xe,ye)分別為直線的起點坐標(biāo)和終點坐標(biāo)，則：可通過計算由x方向的增量引起y的改變來生成直線。由，得到：同樣，可通過計算由y方向的增量引起x的改變來生成直線。由，得到：直線生成算法—DDA算法第四頁，共四十一頁，編輯于2023年，星期日DDA算法基本思想選定和中較大者作為步進(jìn)方向，在此方向上每次增加（或者減少）一個像素，然后計算另一個方向上增量的值，把每次計算出的值經(jīng)取整后順序輸出到顯示器，則可以得到光柵化的直線。DDA算法特點算法簡單，實現(xiàn)容易，但計算量較大，每產(chǎn)生一個像素需要取整運算，此外算法還要除法運算，因此生成直線的速度較慢。直線生成算法—DDA算法第五頁，共四十一頁，編輯于2023年，星期日例題1：已知起點A(16,-5)和終點B(-4,8)，用DDA法在A和B之間生成一段直線。第一步：計算初值：，，由于，所以選定x軸方向作為步進(jìn)方向；第二步：在x軸方向上每次的變化量為，則y軸方向的變化量為第三步：循環(huán)計算點的坐標(biāo)，并取整顯示：直線生成算法—DDA算法第六頁，共四十一頁，編輯于2023年，星期日Bresenham算法基本思想令，直線方程：，其中為起點坐標(biāo)；考慮，則x方向增加1，y方向增加m，由起點(xs,ys)可求得直線上的點(xi，yi)，

i=1,2,3,…,其中x1=xs,y1=ys；用坐標(biāo)為(xi，round(yi))的象素來表示直線上的點，其中round(yi)表示最靠近y的整數(shù)；直線生成算法—Bresenham算法第七頁，共四十一頁，編輯于2023年，星期日Bresenham算法基本思想令yi,r=round(yi),用坐標(biāo)為(xi，yi,r)的象素來表示直線上的點，第i+1個點只能在C和D中選取。令誤差項當(dāng)時，，即選C點當(dāng)時，，即選D點直線生成算法—Bresenham算法第八頁，共四十一頁，編輯于2023年，星期日Bresenham算法基本思想的遞推公式=初始值直線生成算法—Bresenham算法第九頁，共四十一頁，編輯于2023年，星期日實際上，誤差項的數(shù)值大小與算法的執(zhí)行沒有關(guān)系，相關(guān)的只是的符號，因而我們可以改變的定義，在兩邊同乘以

，可消除除法運算：令初始如果，則:如果，則:直線生成算法—Bresenham算法第十頁，共四十一頁，編輯于2023年，星期日

Bresenham算法基本思想上述算法擴(kuò)展到任一八分圓坐標(biāo)空間圖，從而形成一般的Bresenham算法。下圖是各象限的判斷條件。直線生成算法—Bresenham算法第十一頁，共四十一頁，編輯于2023年，星期日例題2：已知起點A(20,10)和終點B(30,18)，用Bresenham法在A和B之間生成一段直線。解：Δx=10,Δy=8,斜率在0和1之間；直線生成算法—Bresenham算法ixiyi12010=2*8-10=6x加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加1ixiyi12010x加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第十二頁，共四十一頁，編輯于2023年，星期日這里僅討論圓心位于坐標(biāo)原點的圓的掃描轉(zhuǎn)換算法，對于圓心不在原點的圓，可先用平移變換，將它的圓心平移到原點，然后進(jìn)行掃描轉(zhuǎn)換，最后再平移到原來的位置；圓的八分對稱性中點算法生成圓圓的生成算法第十三頁，共四十一頁，編輯于2023年，星期日圓心位于原點的圓有四條對稱軸x=0、y=0、y=x和y=－x，見下圖。從而若已知圓弧上一點P(x，y)，就可以得到其關(guān)于四條對稱軸的七個對稱點，這種性質(zhì)稱為八分對稱性。因此只要能畫出八分之一的圓弧，就可以利用對稱性的原理得到整個圓弧。圓的生成算法—圓的八分對稱性第十四頁，共四十一頁，編輯于2023年，星期日設(shè)要顯示圓的圓心在原點(0,0)，半徑為R，起點在(0,R)處，終點在(,)，順時針生成八分之一圓，利用對稱性掃描轉(zhuǎn)換全部圓；為了應(yīng)用圓的生成算法，我們定義一個圓函數(shù)：F(x,y)=任何點(x,y)的相對位置可由圓函數(shù)的符號來確定：若F(x,y)<0，點(x,y)位于圓內(nèi)若F(x,y)=0，點(x,y)位于圓上若F(x,y)>0，點(x,y)位于圓外圓的生成算法—中點算法生成圓第十五頁，共四十一頁，編輯于2023年，星期日如何選取下一象素點？假定當(dāng)前取點為P(xi，yi)，如果順時針生成圓，那么下一點只能取正右方的點E(xi+1，yi)或右下方的點SE(xi+1，yi-1)兩者之一。假設(shè)M是E和SE的中點，即M(xi+1,yi-0.5)，用中點M的圓函數(shù)作為決策變量di，則：當(dāng)di<0時，M在圓內(nèi)(如圖b)，說明點E距離圓更近，應(yīng)取點E作為下一象素點；當(dāng)di>0時，M在圓外(如圖a)，說明點SE距離圓更近，應(yīng)取點SE作為下一象素點；當(dāng)di=0時，在E點與SE點之中隨便取一個即可，我們約定取點SE作為下一象素點。圖a圖b圓的生成算法—中點算法生成圓第十六頁，共四十一頁，編輯于2023年，星期日如何計算新的決策變量？當(dāng)前（1）下面分兩種情況來討論在迭代計算中決策變量di+1的推導(dǎo)：若di<0，則選擇E點，接著下一個中點就是M(xi+2,yi),這時新的決策變量為（2）(2)-(1)得：

若di≥0，則選擇SE點，接著下一個中點就是M(xi+2,yi),這時新的決策變量為（3）

(3)-(1)得：

di<0di≥0圓的生成算法—中點算法生成圓第十七頁，共四十一頁，編輯于2023年，星期日如何計算初始決策變量？對于初始點(0，R)，順時針生成八分之一圓，下一個中點M的坐標(biāo)是(1,R-0.5)，所以：圓的生成算法—中點算法生成圓第十八頁，共四十一頁，編輯于2023年，星期日輸入:圓的半徑R；算法步驟：計算初始決策變量值d=1.25-R、x=0、y=R；繪制點(x,y)及其在八分圓中的另外七個對稱點；判斷決策變量d的符號：若d<0，則先將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時，重復(fù)步驟3和4。否則結(jié)束。voidmidPointCircle(intr){

floatd;

x=0;

y=r;

d=1.25-r;

while(x<=y){

draw(x,y);//繪制點(x,y)及其七個對稱點；

if(d<0){

d+=x*2.0+3;}else{

d+=2.0*(x-y)+5;

y--;

}

x++;

}}圓的生成算法—中點算法生成圓第十九頁，共四十一頁，編輯于2023年，星期日多邊形的表示方法頂點表示是用多邊形的頂點的序列來描述多邊形，該表示幾何意義強(qiáng)、占內(nèi)存少，但不能直觀地說明哪些像素在多邊形內(nèi)；點陣表示是用位于多邊形內(nèi)的象素的集合來刻劃多邊形，該方法雖然沒有多邊形的幾何信息，但具有面著色所需要的圖像表示形式；多邊形填充就是把多邊形的頂點表示轉(zhuǎn)換為點陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個像素，并將幀緩沖器內(nèi)的各個對應(yīng)元素設(shè)置相應(yīng)的灰度或顏色。多邊形頂點表示多邊形點陣表示多邊形的填充第二十頁，共四十一頁，編輯于2023年，星期日填充條件：多邊形的頂點序列(Pi，i=0，1，…，n)、填充色。對多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。多邊形內(nèi)點的判別準(zhǔn)則從測試點引出一條伸向無窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，那么：若射線與多邊形邊界的交點個數(shù)為奇數(shù)時，則該點為內(nèi)點；若交點個數(shù)為偶數(shù)時，則該點為外點。奇異點上述的判別準(zhǔn)則，在大多數(shù)情況下是正確的，但當(dāng)水平掃描線正好通過多邊形頂點時，要特別注意。例如，圖中過頂點的射線1、射線6，它們與多邊形的交點個數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點，但實際上卻是外點。而圖中過頂點的射線3、射線5，對于判別準(zhǔn)則的使用又是正確的。多邊形的填充第二十一頁，共四十一頁，編輯于2023年，星期日奇異點的處理將多邊形的頂點分為兩大類：局部極值點：如圖中的點P1、P2、P4和P6。對于這些點來說，進(jìn)入該點的邊線和離開該點的邊線位于過該點掃描線的同一側(cè)。非極值點：如圖中的點P3、P5。對于這些點來說，進(jìn)入該點的邊線和離開該點的邊線位于過該點掃描線的兩側(cè)。處理奇異點規(guī)則對于局部極值點，應(yīng)看成兩個點；對于非極值點，應(yīng)看成一個點。

多邊形的填充第二十二頁，共四十一頁，編輯于2023年，星期日逐點判別算法求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。對包圍盒中的每個象素引水平射線進(jìn)行測試。求出該射線與多邊形每條邊的有效交點個數(shù)。如果個數(shù)為奇數(shù)：該點置為填充色。逐點判別算法雖然簡單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對每個象素進(jìn)行多次求交運算，求交時要做大量的乘除運算，從而影響了填充速度。多邊形的填充—逐點判別算法第二十三頁，共四十一頁，編輯于2023年，星期日邊相關(guān)掃描線多邊形填充算法邊相關(guān)掃描線填充算法比逐點判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點進(jìn)行處理。多邊形的填充—掃描線算法第二十四頁，共四十一頁，編輯于2023年，星期日掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點時才會發(fā)生改變。見下圖(a)。邊的相關(guān)性：由于相鄰掃描線上的交點是與多邊形的邊線相關(guān)的。對同一條邊，前一條掃描線yi與該邊的交點為xi，而后一條掃描線yi+1=yi+1與該邊的交點則為xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運算。見下圖(b)所示。(a)掃描線的相關(guān)性(b)邊的相關(guān)性多邊形的填充—掃描線算法第二十五頁，共四十一頁，編輯于2023年，星期日數(shù)據(jù)結(jié)構(gòu)邊相關(guān)掃描線填充算法的實現(xiàn)需要建立兩個表：邊表（ET）和活動邊表（AET）。邊表（ET：EdgeTable）用來對除水平邊外的所有邊進(jìn)行登記，來建立邊的記錄。邊的記錄定義為：第一項：某邊的最大y值（ymax）。注意要進(jìn)行奇異點處理：對于非極值點應(yīng)該ymax=ymax-1。第二項：某邊的最小的y對應(yīng)的x值。第三項：某邊斜率的倒數(shù):1/m。第四項：指針。用來指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項置空多邊形的填充—掃描線算法第二十六頁，共四十一頁，編輯于2023年，星期日數(shù)據(jù)結(jié)構(gòu)活動邊表（AET：ActiveEdgeTable）：ET表建立以后，就可以開始掃描轉(zhuǎn)換了。對不同的掃描線，與之相交的邊線也是不同的，當(dāng)對某一條掃描線進(jìn)行掃描轉(zhuǎn)換時，我們只需要考慮與它相交的那些邊線，為此需要建立一個只與當(dāng)前掃描線相交的邊記錄鏈表，稱之為活動邊表。多邊形的填充—掃描線算法第二十七頁，共四十一頁，編輯于2023年，星期日算法步驟根據(jù)給出的多邊形頂點坐標(biāo)，建立ET表；求出頂點坐標(biāo)中最大y值ymax和最小y值ymin。初始化AET表指針，使它為空。使用掃描線的yj值作為循環(huán)變量，使其初值為ymin。對于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：如果ET表中yj桶非空，則將yj桶中的全部記錄合并到AET表中。對AET表鏈中的記錄按x的大小從小到大排序。依次取出AET表各記錄中的xi坐標(biāo)值，兩兩配對填充，即將每對xi之間的象素填上所要求的顏色。如果AET表中某記錄的ymax=yj，則刪除該記錄。對于仍留在AET表中的每個記錄，用xi+1/m代替xi進(jìn)行修改，這就是該記錄的邊線與下一條掃描線yj+1的交點。使yj加1，以便進(jìn)入下一輪循環(huán)。多邊形的填充—掃描線算法第二十八頁，共四十一頁，編輯于2023年，星期日算法實現(xiàn)：對多邊形P的每一非水平邊（i=0,1,…,n）上的各像素做向右求反運算即可，見下圖，其中(a)為給定的多邊形；(b)為對區(qū)域賦初值；(c)，(d)，(e)和(f)表示逐邊向右求反。

多邊形的填充—邊緣填充算法第二十九頁，共四十一頁，編輯于2023年，星期日基本原理：首先用一種特殊的顏色在幀緩沖器中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來。然后再把位于多邊形內(nèi)的各個像素著上所需的顏色

步驟1：以值為boundary-color的特殊顏色勾畫多邊形的邊界。設(shè)多邊形頂點為Pi=(xi,yi),0≤i≤n，

xi,yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點的個數(shù)必定是偶數(shù)(包括零)。步驟2：設(shè)interior_point是一布爾變量。對每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前是像素位于多邊形內(nèi)，則interior_point=true，需要填上值為polygon_color的顏色；否則該像素在多邊形外，需要填上值background_color的顏色多邊形的填充—邊界標(biāo)志算法第三十頁，共四十一頁，編輯于2023年，星期日3.5.1區(qū)域的基本概念

區(qū)域是指已經(jīng)表示成點陣形式的像素集合在光柵圖形中，區(qū)域可采用內(nèi)點表示和邊界表示兩種形式進(jìn)行描述。

區(qū)域填充是指先將區(qū)域內(nèi)的一點(常稱種子點)賦予給定顏色，然后將這種顏色擴(kuò)展到整個區(qū)域內(nèi)的過程。第三十一頁，共四十一頁，編輯于2023年，星期日區(qū)域填充的基本概念內(nèi)點表示法：把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點表示法。邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。圖3.25內(nèi)點表示的區(qū)域圖3.26邊界表示的區(qū)域第三十二頁，共四十一頁，編輯于2023年，星期日區(qū)域填充的基本概念4連通的區(qū)域:取區(qū)域內(nèi)任意兩點，在該區(qū)域內(nèi)若從其中一點出發(fā)通過上、下、左、右四種運動可到達(dá)另一點。圖3.27四個方向的運動8連通區(qū)域:

取區(qū)域內(nèi)任意兩點，若從其中任一點出發(fā)，在該區(qū)域內(nèi)通過沿水平方向、垂直方向和對角線方向的八種運動可到達(dá)另一點。圖3.28個方向的運動第三十三頁，共四十一頁，編輯于2023年，星期日區(qū)域填充的基本概念4連通區(qū)域也可理解成8連通區(qū)域，但是兩者的邊界不盡相同。如果圖中標(biāo)有·號的象素組成的區(qū)域作為4連通區(qū)域，則其邊界由圖中的標(biāo)有△號的象素組成。如果將該區(qū)域作為8連通的區(qū)域，則其邊界由圖中標(biāo)有△號和×號的兩種象素組成。

圖3.29內(nèi)點表示的八連通區(qū)域圖3.30邊界表示的八連通區(qū)域圖3.31四連通區(qū)域與八連通區(qū)域的不同邊界第三十四頁，共四十一頁，編輯于2023年，星期日3.5.2簡單的種子填充算法基本思想：給定區(qū)域G一種子點（x,y）首先判斷該點是否是區(qū)域內(nèi)的一點，如果是，則將該點填充為新的顏色，然后將該點周圍的四個點（四連通）或八個點（八連通）作為新的種子點進(jìn)行同樣的處理，通過這種擴(kuò)散完成對整個區(qū)域的填充

第三十五頁，共四十一頁，編輯于2023年，星期日3.5.3掃描線種子填充算法基本思想：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來。反復(fù)進(jìn)行這個過程，直到所保存的各區(qū)段都填充完畢第三十六頁，共四十一頁，編輯于2023年，星期日掃描線種子填充算法算法步驟：步驟1：將算法設(shè)置的堆棧置為空。將給定的種子點（x,y）壓入堆棧。步驟2：如果堆棧為空，算法結(jié)束；否則取棧頂元素（x,y）作為種子點。步驟3：從種子點（x,y）開始，沿縱坐標(biāo)為y的當(dāng)前掃描線向左右兩個方向逐個像素用新的顏色值進(jìn)行填充，直到邊界為止。設(shè)區(qū)間兩邊界的橫坐標(biāo)分別為xleft