基本圖形生成

1、 第三章 基本光柵圖形基礎(chǔ)* 物體的形狀和顏色可用象素矩陣或直線線段和多邊形填充區(qū)域等基本幾何結(jié)構(gòu)來描述。點和直線段是最簡單的幾何成分，其它可供構(gòu)造圖形的輸出圖元有圓及其它圓錐曲線、二次曲面、樣條曲線和曲面、多邊形填充區(qū)域以及字符串等。而二維圖形的生成是三維圖形生成的基礎(chǔ)，研究計算機生成圖形需先從二維圖形的生成開始。下面將討論一些基本二維圖元生成技術(shù)和算法，以光柵圖形系統(tǒng)的掃描轉(zhuǎn)換方法為基礎(chǔ)。8/21/20221本章內(nèi)容？直線段的掃描轉(zhuǎn)換算法 DDA算法 Bresenham畫線算法？區(qū)域填充 掃描線填充 種子填充邊填充 8/21/20222直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換: 確定最佳逼近于該

2、直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。常用算法：數(shù)值微分法（DDA）Bresenham算法。8/21/20223 直線是點的集合，在幾何學(xué)中直線被定義為兩個點之間的最短距離。也就是說一條直線是指所有在它上面的點的集合。直線是一維的，即它們具有長度但沒有面積。直線可以向一個方向及其相反的方向無限伸長，這不是計算機圖形學(xué)中所需要的，在圖形學(xué)中研究的對象是直線段。已知線段的起點坐標（x1,y1），終點坐標（x2,y2)，這兩點就確定了一條線段。 一般來講，任何圖形輸出設(shè)備都能準確地畫出水平線X和垂直線Y,或?qū)蔷€，但要畫出一條準確斜線不是件容易的事。在光柵系統(tǒng)中，線段通過象素繪制，

3、水平和垂直方向的臺階大小受象素的間隔限制。這就是說，必須在離散位置上對線段取樣，并且在每個取樣位置上決定距線段最近的象素，畫一條直線實際上就計算出來一系列與該線靠近的象素。8/21/20224AB光柵化的直線ABCD8/21/20225數(shù)值微分法（） 假定直線的起點、終點分別為：（x0,y0), (x1,y1)，且都為整數(shù)。8/21/20226數(shù)值微分(DDA)法基本思想已知過端點P0 (x0, y0), P1(x1, y1)的直線段Ly=kx+b直線斜率為這種方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次舍入運算。 8/21/20227數(shù)值微分(DDA)法計算yi+1= kxi+1+

4、b = kxi+b+kx = yi+kx 當(dāng)x =1;yi+1 = yi+k 即：當(dāng)x每遞增1，y遞增k(即直線斜率)；注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng) k 1時，必須把x，y地位互換8/21/20228(X i+1 ,Yi + k)(X i , Round(Yi)(X i , Yi)柵格交點表示象素點位置8/21/20229數(shù)值微分(DDA)法增量算法：在一個迭代算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。8/21/202210數(shù)值微分(DDA)法void DDALine(int

5、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; for (x=x0; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; 8/21/202211數(shù)值微分(DDA)法例：畫直線段P0(0,0)-P1(5,2)x int(y+0.5) y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.58/21/202212數(shù)值微分(DDA)法缺點： 在此算法中

6、，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實現(xiàn)。8/21/202213Bresenham畫線算法在直線生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x，就0k1的情況來說明Bresenham算法。由DDA算法可知：yi+1=yi+k (1) 由于k不一定是整數(shù)，由此式求出的yi也不一定是整數(shù)，因此要用坐標為（xi,yir）的象素來表示直線上的點，其中yir表示最靠近yi的整數(shù)。8/21/202214Bresenham畫線算法 設(shè)圖中xi列上已用（xi,yir）作為表示直線的點，又設(shè)B點是直線上的點，其坐標為（xi+1,yi+1），顯然下一個表示直線

7、的點（ xi+1,yi+1,r）只能從圖中的C或者D點中去選。設(shè)A為CD邊的中點。 若B在A點上面則應(yīng)取D點作為（ xi+1,yi+1,r），否則應(yīng)取C點。xiXi+1Yi,rYi+1,rCDBA(x)的幾何意義為能確定B在A點上面或下面，令(xi+1)=yi+1-yi,r-0.5 (2) 若B在A的下面，則有(xi+1)0。由圖可知 yi+1,r=yi,r+1，若(xi+1)0 (3) yi+1,r=yi,r， 若(xi+1)08/21/202215Bresenham畫線算法由式（2）和式（3）可得到 (xi+2)=yi+2 - yi+1,r - 0.5 =yi+1 + k - yi+1,r

8、 - 0.5 （4） yi+1 - yir -0.5 + k - 1,當(dāng)(xi+1)0 yi+1 - yir -0.5 + k, 當(dāng)(xi+1)0 (xi+2)= (xi+1) + k -1 ,當(dāng)(xi+1)0 (xi+2)= (xi+1) + k , 當(dāng)(xi+1)0 8/21/202216 程序如下： BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; 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=

9、0; i= 0) y+; e = e - 1; Bresenham畫線算法8/21/202217將e乘以2x記為E2xe，則E同e有相同的符號，取代e判斷E的符號確定象素點的過程仍然正確。此時上述算法中各誤差項的表示式做如下變動：初始誤差項： E02xe0 -x；積累誤差 ek+1ekm修改為： Ek+12xek+1 2x(eky/x） 2xek2y Ek2y；如果選取上面的象素點，積累誤差還要減去1，修改為： Ek+12x（ek+11） E k+12x 8/21/202218 程序如下： BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,col

10、or; int x,y,dx,dy; float k; int e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -dx; x=x0; y=y0; for( i=0; i= 0) y+; e = e - 2*dx; 8/21/202219Bresenham畫線法例：用bresenhanm畫線法P0(0,0) P1(5,2)dy=y1-y0=2 dx=x1-x0=5 e0=-dx=-5ixiyie100-5210-13213431-354216 5 2 -58/21/202220 區(qū)域填充 一個區(qū)域是指一組相鄰而又相連的象素，且具有同樣的屬性。根據(jù)邊或輪廓線的描

11、述，生成實區(qū)域的過程稱為區(qū)域填充。 8/21/202221多邊形的表示方法頂點表示點陣表示頂點表示：用多邊形頂點的序列來刻劃多邊形。直觀、幾何意義強、占內(nèi)存少；不能直接用于面著色。點陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運用幀緩沖存儲器表示圖形，易于面著色。8/21/202222區(qū)域填充算法可分為兩大類： 一是種子填充算法； 二是掃描轉(zhuǎn)換填充算法。 種子填充算法首先假定封閉輪廓線內(nèi)某點是已知的，然后算法開始搜索與種子點相鄰且位于輪廓線內(nèi)的點。種子填充算法只適用于光柵掃描設(shè)備。 掃描轉(zhuǎn)換填充算法則是按掃描線的順序確定某一點是否位于多邊形或輪廓線范圍之內(nèi)。這

12、些算法一般從輪廓線的頂部開始進行到它的底部。 區(qū)域填充的邊界可以是直線也可以是曲線。8/21/202223多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換：把多邊形的頂點表示轉(zhuǎn)換為點陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個象素，并給幀緩沖器內(nèi)的各個對應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。幾種方法：逐點判斷法；掃描線算法；邊填充法；柵欄填充法；邊界標志法。8/21/202224掃描線算法掃描線算法目標：利用相鄰像素之間的連貫性，提高算法效率處理對象：非自交多邊形 （邊與邊之間除了頂點外無其它交點）8/21/202225右圖所示是一簡單多邊形，各條掃描線與多邊形有不同的交

13、點個數(shù)，交點將掃描線分成了不同的區(qū)域。求出掃描線與多邊形的交點后，將各條掃描線上的交點按X方向從小到大排序后兩兩配對。每對交點所確定的區(qū)間均取填充的光強或色彩，其它區(qū)間則取背景光強或色彩，即可完成填充。8/21/202226步驟： （1）求交：計算掃描線與多邊形各邊的交點；（2）排序：把所有交點按x值遞增順序排序；（3）配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區(qū)間，（4）著色：把相交區(qū)間內(nèi)的象素置成多邊形顏色，把相交區(qū)間外的象素置成背景色。8/21/2022278/21/202228掃描線算法交點的取整規(guī)則要求：使生成的像素全部位于多邊形之內(nèi)用于線畫圖元掃

14、描轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用假定非水平邊與掃描線y=e相交，交點的橫坐標為x,規(guī)則如下8/21/202229掃描線算法規(guī)則1：X為小數(shù)，即交點落于掃描線上兩個相鄰像素之間 (a)交點位于左邊之上，向右取整 (b)交點位于右邊之上，向左取整8/21/202230規(guī)則2：邊界上象素的取舍問題，避免填充擴大化。解決方法： 邊界象素：規(guī)定落在右上邊界的象素不予填充。 具體實現(xiàn)時，只要對掃描線與多邊形的相交區(qū)間左閉右開掃描線算法8/21/202231規(guī)則3：掃描線與多邊形的頂點相交時，交點的取舍，保證交點正確配對。解決方法：檢查兩相鄰邊在掃描線的哪一側(cè)。 只要檢查頂點的兩條

15、邊的另外兩個端點的Y值，兩個Y值中大于交點Y值的個數(shù)是0，1，2，來決定取0，1，2個交點。 掃描線算法8/21/202232數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進行求交運算。我們把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中，稱此鏈表為活性邊表(AET)。 8/21/202233(a)掃描線6的活性邊表(b)掃描線7的活性邊表8/21/202234假定當(dāng)前掃描線與多邊形某一條邊的交點的橫坐標為x，則下一條掃描線與該邊的交點不必要重計算，只要加一個增量x即可，下面，我們推導(dǎo)這個結(jié)論。 8/21/202235 設(shè)該邊的

16、直線方程為：ax+by+c=0，y=yi時，x=xi;則當(dāng)y=yi+1時，Xi+1=xi-b/a 另外使用增量法計算時，我們需要知道一條邊何時不再與下一條掃描線相交，以便及時把它從活性邊表中刪除出去。綜上所述，活性邊表的結(jié)點應(yīng)為對應(yīng)邊保存如下內(nèi)容：第1項存當(dāng)前掃描線與邊的交點坐標x值；第2項存從當(dāng)前掃描線到下一條掃描線間x的增量Dx；第3項存該邊所交的最高掃描線號ymax。8/21/202236為了方便活性邊表的建立與更新，我們?yōu)槊恳粭l掃描線建立一個新邊表（NET）,存放在該掃描線第一次出現(xiàn)的邊。也就是說，若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中。上圖所示各條掃描線的新

17、邊表NET8/21/202237算法過程：void polyfill (polygon, color)int color;多邊形 polygon; for (各條掃描線i ) 初始化新邊表頭指針NET i； 把y min = i 的邊放進邊表NET i; y = 最低掃描線號； 初始化活性邊表AET為空； for (各條掃描線i ) 把新邊表NETi中的邊結(jié)點用插入排序法插入AET表，使之按x坐標遞增順序排列； 遍歷AET表，把配對交點區(qū)間(左閉右開)上的象素(x, y)，用drawpixel (x, y, color) 改寫象素顏色值； 遍歷AET表，把y max= i 的結(jié)點從AET表中刪

18、除，并把y max i結(jié)點的x值遞增D x； 若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序； /* polyfill */8/21/202238邊填充法 另一種掃描轉(zhuǎn)換方法即所謂的邊填充算法。其基本思想是對每條掃描線和每條多邊形的交點（xk,yk），將該掃描線上交點右方的所有象素取補。對多邊形的每條邊作此處理，就可以完成多邊形區(qū)域填充。 邊填充算法描述如下：1. 取多邊形的一條邊；2. 求出每一條掃描線與該邊的交點坐標（xk,yk）； 3. 將（xk,yk）右邊的全部象素取補； 4還有沒處理的多邊形邊時轉(zhuǎn)1，否則結(jié)束。8/21/202239下圖示出了邊填充算法的實現(xiàn)過程。8/21/

19、202240 上述算法的缺點是對于復(fù)雜的圖形，一些象素可能被訪問多次，一種改進的辦法是引入柵欄。通過多邊形設(shè)一柵欄，每次只對交點與柵欄之間的象素點取補，可使訪問象素的次數(shù)減少。下圖示出了這一算法的原理。8/21/202241 種子填充算法* 以上討論的填充多邊形的算法都是按掃描線順序進行的。種子填充算法則來用完全不同的方法。 種子填充算法假設(shè)在多邊形或區(qū)域內(nèi)部至少有一個象素是已知的。然后設(shè)法找到區(qū)域內(nèi)所有其它象素，并對它們進行填充。8/21/202242區(qū)域指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。8/21/202243表示方法：內(nèi)點表示、邊界表示內(nèi)點表示枚舉處區(qū)域內(nèi)部的所有像素內(nèi)部的所

20、有像素著同一個顏色邊界像素著與內(nèi)部像素不同的顏色邊界表示枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色8/21/202244區(qū)域填充要求區(qū)域是連通的連通性 4連通、8連通4連通：8連通8/21/202245 對4連接算法，應(yīng)用邊界定義區(qū)域，可使用堆棧以建立簡單的種子填充算法。使用的堆棧的種子填充算法如下： 1 種子象素壓入堆棧； 2 當(dāng)堆棧非空時做 （1）棧頂象素出棧； （2）將出棧象素置成填充顏色； （3）檢查每個與當(dāng)前象素鄰接的4連接象素，若其中有象素不為邊界且沒有設(shè)置成填充顏色，將該象素壓入堆棧； （4）轉(zhuǎn)28/21/202246算法可用偽語言描述如下：算

21、法：seed(x,y) 作為種子 BV (BoundaryValue) 邊界值 NV (NewValue) 填充值 begin pixel(x, y)=seed(x,y) push pixel(x,y) while (stack not empty) pop pixel(x,y) if pixel(x,y)NV then putpixel(x,y,NV) pixel(x,y)=NV endif if pixel(x+1,y)NV and pixel(x+1,y)BV then push pixel(x+1,y) endif if pixel(x,y+1)NV and pixel(x,y+1)B

22、V then push pixel(x,y+1) endif if pixel(x-1,y)NV and pixel(x-1,y)BV then push pixel(x-1,y) endif if pixel(x,y-1)NV and pixel(x,y-1)BV then push pixel(x,y-1) endif endwhile end8/21/202247種子填充算法例子如右圖所示，種子的坐標為（3，2），以四連通順時針左起點為例，其進出棧順序為： 種子（3，2）進棧，初始棧：（3，2）（1） 種子（3，2）出棧，四個相鄰點進棧； 棧：（2，2），（3，3），（4，2），（3，1

23、）（2） 點（3，1）出棧，相鄰點（2，1），（4，1）進棧； 棧：（2，2），（3，3），（4，2），（2，1），（4，1）（3）點（4，1）出棧，相鄰點（4，2）進棧； 棧：（2，2），（3，3），（4，2），（2，1），（4，2）（4）點（4，2）出棧，相鄰點進棧（無）； 棧：（2，2），（3，3），（4，2），（2，1）8/21/202248（5）點（2，1）出棧，相鄰點（2，2）進棧； 棧：（2，2），（3，3），（4，2），（2，2）（6） 點（2，2）出棧，相鄰點（1，2），（2，3）進棧； 棧：（2，2），（3，3），（4，2），（1，2），（2，3）（7） 點（2，3）出棧，

24、相鄰點（3，3）進棧； 棧：（2，2），（3，3），（4，2），（1，2），（3，3）（8） 點（3，3）出棧，相鄰點進棧（無）； 棧：（2，2），（3，3），（4，2），（1，2）（9） 點（1，2）出棧，相鄰點進棧（無）； 棧：（2，2），（3，3），（4，2）（10）點（4，2）出棧，相鄰點進棧（無）； 棧：（2，2），（3，3）（11）點（3，3）出棧，相鄰點進棧（無）； 棧：（2，2）（12）點（2，2）出棧，相鄰點進棧（無）；（13）棧空結(jié)束。8/21/202249種子填充算法主要實現(xiàn)子程序?qū)嵗齰oid seed(x1,y1,nv,bv) /nv:填充顏色，bv:邊界顏色 int

25、x1,y1,nv,bv; int a19999,b19999; int i,k,x,y,mx,my; unsigned c; a0=x1; b0=y1; k=0; putpixel(x1,y1,nv);8/21/202250while(k=0)&(k19998) x=ak; y=bk; k-; c=getpixel(x,y); /取該點的顏色 if (c!=nv) putpixel(x,y,nv);delay(1000); mx=x; my=y;8/21/202251 for(i=1;i5;i+) x=mx; y=my; if (i=1) /右 x+; else if (i=2) /上 y+;

26、 else if (i=3) /左 x-; else y-; /下 8/21/202252c=getpixel(x,y);if (c!=nv)&(c!=bv) k+; ak=x; bk=y; 種子填充算法演示8/21/202253 上面的算法是一種深度優(yōu)先搜索算法，采用堆棧實現(xiàn)。也可以改為廣度優(yōu)先搜索，采用隊列實現(xiàn)。掃描線種子填充算法 種子填充算法的缺點是可能把太多的象素壓入堆棧，有些象素甚至?xí)霔６啻?，降低算法的效率，存儲空間需求大。解決的一種方法是對每一條掃描線實行種子算法。在任意不間斷的掃描線象素段中，只取一個種子象素。象素段是指區(qū)域內(nèi)相鄰象素在水平方向的組合，它的兩端以具有邊界值的象素

27、為界，其中間不包括具有新值的象素。8/21/202254對于區(qū)域內(nèi)的每一象素段，我們可以只保留其最右（或左）端的象素作為種子象素。因此，區(qū)域中每一個末被填充的部分，至少有一個象素段是保持在棧里的。掃描線種子填充算法適用于邊界定義的區(qū)域。區(qū)域可以是凸的，也可以是凹的，還可以包含一個或多個孔 。定義的區(qū)域。區(qū)域可以是凸的，也可以是凹的，還可以包含一個或多個孔。 算法敘述如下： 1 種子象素入棧； 2 當(dāng)堆棧非空時做 （1）棧頂象素出棧；8/21/202255 （2）沿掃描線對出棧象素的左右象素進行填充，直到遇到邊界象素為止，即每出棧一個象素，便對包含該象素的整個區(qū)間進行填充； （3）上述區(qū)間內(nèi)最左

28、最右的象素分別記為xLeft、xRight； （4）在區(qū)間xLeft,xRight中檢查與當(dāng)前掃描線相鄰的上下兩條掃描線的有關(guān)象素是否全為邊界象素或為已填充的象素，若存在非邊界未填充的象素，則把每一區(qū)間的最右象素取作種子象素入棧； （5）轉(zhuǎn)2 此算法可以有效地解決簡單種子填充算法存在的堆?？赡苓^深的問題。 8/21/202256掃描線種子填充算法主要實現(xiàn)子程序?qū)嵗齰oid push(int x,int y) pointstop0=x; pointstop1=y; top+;void pop() x=pointstop-10; y=pointstop-11; top-;void Scanline

29、_seed_fill_draw(HDC hdc) int i; COLORREF BoundColor;POINT triangle=300,275,280,325,320,325,300,275; POINT fourline=250,340,300,375,350,340,300,350,250,340; BoundColor=RGB(255,0,0); SetColor(BoundColor,hdc); 8/21/202257Ellipse(hdc,180,200,420,400);Ellipse(hdc,230,230,270,310);Ellipse(hdc,330,230,370,

30、310);Ellipse(hdc,245,264,255,296);Ellipse(hdc,345,264,355,296);for(i=0;i3;i+) line(hdc,trianglei,trianglei+1); for(i=0;i4;i+) line(hdc,fourlinei,fourlinei+1); Scanline_seed_fill(hdc,300,300,RGB(0,0,255),BoundColor); Scanline_seed_fill(hdc,250,280,RGB(0,255,0),BoundColor); Scanline_seed_fill(hdc,350,

31、280,RGB(0,255,0),BoundColor); Scanline_seed_fill(hdc,300,360,RGB(0,255,255),BoundColor); Scanline_seed_fill(hdc,235,270,RGB(0,0,0),BoundColor); Scanline_seed_fill(hdc,335,270,RGB(0,0,0),BoundColor);void Scanline_seed_fill(HDC hdc,int seed_x,int seed_y,COLORREF FillColor,COLORREF BoundColor) int acti

32、ve_x,active_y,Left_x,Right_x,flag,Nextspan_x; COLORREF rgbColor; push(seed_x,seed_y); while(top!=bottom) pop(); SetPixel(hdc,x,y,FillColor);8/21/202258/填充掃描線右半部分 active_x=x+1; while(GetPixel(hdc,active_x,y)!=BoundColor) SetPixel(hdc,active_x,y,FillColor); active_x+; Sleep(1); Right_x=active_x-1;/填充掃描線左半部分 active_x=x-1; while(GetPixel(hdc,active_x,y)!=BoundColor) SetPixel(hdc,active_x,y,FillColor); active_x-; Sleep(1); Left_x=active_x+1; active_x=Left_x;/確定下