建筑造型裝飾與三維動畫 第3章

1、第3章 基本圖形 生成算法,3.1 生成直線的常用算法,均假定所畫直線的斜率k∈[0，1]。3.1.1 DDA畫線算法DDA（Digital Differential Analyzer）畫線算法也稱數(shù)值微分法，是一種增量算法。它的算法實質(zhì)是用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量，計算下一步的x、y值。,已知一條直線段L（P0, P1）,其端點坐標(biāo)為：P0 (x0, y0), P1(x1,

2、y1)。可計算出直線的斜率k為： 假定端點坐標(biāo)均為整數(shù)，取直線起點P0 (x0, y0)作為初始坐標(biāo)。畫線過程從x的左端點x0開始，向x右端點步進(jìn)，每步x遞增1，y遞增k（即直線斜率）；取像素點（x，round（y））作為當(dāng)前點的坐標(biāo)。,,3.1.2 中點畫線算法 假設(shè)x坐標(biāo)為xp的各像素點中，與直線最近者已確定，為P（xp,yp），那么，下一個與直線最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2

3、（xp+1,yp+1）兩者之一。令M為P1和P2的中點，易知M的坐標(biāo)為（xp+1,yp+0.5）。 設(shè)Q是理想直線與垂直線x=xp+1的交點。顯然，若M在Q的下方，則P2離直線近，應(yīng)取為下一個像素；否則應(yīng)取P1。,令a=y0-y1，b=x1-x0，c=x0y1-x1y0。構(gòu)造判別式： d=a(xp+1)+b(yp+0.5)+c d的初始值d0 = a+0.5b 在d≥0的情況下，取正右方像素P1，

4、 d1=a(xp+2)+b(yp+0.5)+c =d+a 在d<0的情況下，取右上方像素P2， d2=a(xp+2)+b(yp+1.5) = d+a+b,由于我們使用的只是d的符號，而且d的增量都是整數(shù)，只是其初始值包含小數(shù)。因此，我們可以用2d代替d，來擺脫小數(shù)。 如果進(jìn)一步把算法中2*a改為a+a等等，那么這個算法不僅只包含整數(shù)變量，而且不包含乘除法，適合硬件實現(xiàn)。,3.1.3 Brese

5、nham畫線算法 過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列像素中與此交點最近的像素。 由圖3-5不難看出：若s<t，則Si比較靠近理想直線，應(yīng)選Si;若s≥t，則Ti比較靠近理想直線，應(yīng)選Ti。,令dx=x2-x1，dy=y2-y1遞推公式 ：di的初值： 當(dāng)di≥0時，選Ti，當(dāng)di<0

6、時，選Si， 由于只包含加、減法和左移（乘2）的運(yùn)算，而且下一個像素點的選擇只需檢查di的符號，因此Bresenham畫線算法很簡單，速度也相當(dāng)快。,,,,,3.1.4 直線屬性1．線型2．線寬3．線色,3.2 生成圓弧的常用算法,3.2.1 圓的特性 圓心位于原點的圓有四條對稱軸：x=0，y=0，x=y和x=-y直線。若已知圓弧上一點（x,y），可以得到其關(guān)于四條對稱軸的其它7個點，這種性質(zhì)稱為

7、八對稱性，如下圖所示。 本節(jié)討論的圓的生成算法均只計算從x=0到x=y分段內(nèi)（1b區(qū)域）的像素點，其余的像素位置利用八對稱性即可得出。,3.2.2 中點畫圓算法 假設(shè)x坐標(biāo)為xp的各像素點中，與該圓弧最近者已確定，為P（xp,yp），那么，下一個與圓弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）兩者之一。 令M為P1和P2的中點，易知M的坐標(biāo)為（xp+1

8、,yp-0.5）。顯然，若M在圓內(nèi)，則P1離圓弧近，應(yīng)取為下一個像素；否則應(yīng)取P2。,判別式d：d的初始值為：在d≥0的情況下，取右下方像素P2，在d<0的情況下，取正右方像素P1，,,3.2.3 Bresenham畫圓算法 假設(shè)生成圓心在坐標(biāo)原點，半徑為r，從x=0到x=y的1/8圓弧。 xi+1=xi +1 相應(yīng)的y則在兩種可能中選擇：y=yi，或者y=yi-1 選擇的原則是考察

9、理想的y值是靠近yi還是靠近yi-1。,判別式： d i+1=2(xi+1)2+yi2+(yi-1)2-2r2 判斷式d的初始值為： d0= 3-2r。如果d i+1>=0，則y=yi-1， di+2 =d i+1 + 4(xi- yi)+10如果d i+1<0，則y=yi， d i+2 =d i+1+ 4x i+6,3.3 區(qū)域填充,3.3.1 區(qū)域的表示和類型 頂點表

10、示：也稱為幾何表示，是用區(qū)域的頂點序列來表示區(qū)域。 點陣表示：也稱為像素表示，是用位于多邊形內(nèi)的像素集合來刻畫多邊形。 內(nèi)點表示：區(qū)域內(nèi)的所有像素著同一顏色，而區(qū)域外的所有像素具有另一種顏色； 邊界表示：區(qū)域邊界上的所有像素點具有特定的顏色（可以是填充色），在區(qū)域內(nèi)的所有像素均不能具有這一特定色，而且邊界外的像素不能具有與邊界相同的顏色。,區(qū)域填充算法要求區(qū)域是連通的，因為只有在連通

11、區(qū)域中，才可能將種子點的顏色擴(kuò)展到區(qū)域內(nèi)的其它點。 區(qū)域按連通情況又可分為四連通區(qū)域和八連通區(qū)域。 四連通區(qū)域指的是從區(qū)域上一點出發(fā)，可通過四個方向，即上、下、左、右移動的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素。 八連通區(qū)域指的是從區(qū)域內(nèi)每一像素出發(fā)，可通過八個方向，即上、下、左、右、左上、右上、左下、右下移動的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素。,3.3.2

12、 掃描線多邊形填充算法 掃描線多邊形填充算法是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。 對于一條掃描線，多邊形的填充過程可以分為四個步驟：求交排序配對填色,邊表（ET）：邊表一般是由一系列的存儲桶構(gòu)成的，桶的數(shù)目與掃描線數(shù)一樣多，按掃描線遞增（減）順序存放。邊表的建立：先按下端點的y坐標(biāo)值對所有的邊進(jìn)行分組，若某邊的下低端點y值為y

13、min，則該邊就放在ymin所對應(yīng)的桶中；然后用排序方法，按下端點的x坐標(biāo)值遞增的順序?qū)⑼唤M中的邊排列成行?；罨湵恚ˋEL）：我們把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標(biāo)遞增的順序存放在一個鏈表中，稱此鏈表為活化鏈表（AEL）。,ET和AEL中的基本元素為多邊形的邊。邊表示成結(jié)點的形式，每個邊結(jié)點由以下四個域組成：其中，各符號的含義為：ymax： 邊的上端點的y坐標(biāo)x：在ET中表示邊的下端點

14、的x坐標(biāo)，在AEL中表示邊與掃描線的交點的x坐標(biāo)1/k：邊的斜率的倒數(shù)next：指向下一條邊的指針,當(dāng)建立了邊表ET后，掃描線多邊形填充算法可按如下步驟進(jìn)行：（1）初始化AEL，使之為空，取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號。 （2）按從下到上的順序?qū)γ織l掃描線重復(fù)以下各步，直至AEL和ET為空 。① 將ET中與當(dāng)前y有關(guān)的結(jié)點加入至AEL，同時保存AEL中按x值從小到大實現(xiàn)的排序序列 ②

15、對于AEL中的掃描線y，在一對交點之間填充所需要的像素值 ③ 從AEL中刪掉y>=ymax的結(jié)點④ 對于留在AEL中的每個結(jié)點，執(zhí)行xi+1=xi + 1/k⑤ 對AEL中的各結(jié)點按x值從小到大排序 ⑥ y =y+1，成為下一條掃描線的坐標(biāo),3.3.3 邊填充算法基本原理：對每一條掃描線，依次求與多邊形各邊的交點，將該掃描線上交點右邊的所有像素求補(bǔ)。算法雖然簡單易行，但對于復(fù)雜圖形而言，一些

16、像素的顏色值需反復(fù)改變多次，且多邊形外的像素處理過多，輸入、輸出的量比有序邊表大的多。,柵欄填充算法：對于每條掃描線與多邊形的交點，將交點與柵欄之間的掃描線上的像素取補(bǔ)，也就是說，若交點位于柵欄左邊，則將交點之右、柵欄之左的所有像素取補(bǔ)；若交點位于柵欄右邊，則將柵欄之右、交點之左的所有像素取補(bǔ)。多邊形外的像素處理大大減少，被重復(fù)取補(bǔ)的像素數(shù)目也有減少，但仍有一些像素被重復(fù)取補(bǔ)。,邊標(biāo)志算法：對多邊形邊界所在像素置一個特

17、殊標(biāo)志；對于每條與多邊形相交的掃描線，從左至右逐個訪問該掃描線上的像素。使用一個布爾變量inside來指示當(dāng)前點的狀態(tài)，若點在多邊形內(nèi)，則inside為真。若點在多邊形外，則inside為假。inside 的初始值為假，每當(dāng)當(dāng)前訪問像素為被打上標(biāo)志的點，就把inside取反。對未打標(biāo)志的點，inside不變。若訪問當(dāng)前像素時，對inside作必要操作之后，inside為真，則把該像素置為多邊形要填充的顏色。對每個像素只訪問一次，硬

18、件執(zhí)行速度快。,3.3.4 種子填充算法基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對其進(jìn)行填充。由于區(qū)域可采用邊界定義和內(nèi)點定義兩種方式，區(qū)域按連通性又可分為四連通區(qū)域和八連通區(qū)域兩類，所以常用的種子填充算法有：邊界表示的四連通區(qū)域種子填充算法內(nèi)點表示的四連通區(qū)域種子填充算法邊界表示的八連通區(qū)域種子填充算法內(nèi)點表示的八連通區(qū)域種子填充算法,1．邊

19、界表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒有被填充過，對其填充，并重復(fù)上述過程，直到所有像素填充完畢。可以使用棧結(jié)構(gòu)來實現(xiàn)該算法，算法的執(zhí)行步驟如下：種子像素入棧，當(dāng)棧非空時，重復(fù)執(zhí)行如下三步操作： （1）棧頂像素出棧； （2）將出棧像素置成多邊形填充的顏色； （3）按左、上、右、下的順序檢查與出棧像素相鄰的四個像

20、素，若其中某個像素不在邊界上且未置成多邊形色，則把該像素入棧。,2．內(nèi)點表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，如果是區(qū)域內(nèi)的像素，則對其填充，并重復(fù)上述過程，直到所有像素填充完畢。它也常稱為漫水法。可以使用棧結(jié)構(gòu)來實現(xiàn)該算法，算法的執(zhí)行步驟如下：種子像素入棧，當(dāng)棧非空時，重復(fù)執(zhí)行如下三步操作： （1）棧頂像素出棧； （2）將出棧像素置成多邊

21、形填充的顏色； （3）按左、上、右、下的順序檢查與出棧像素相鄰的四個像素，若其中某個像素是區(qū)域內(nèi)的像素，則把該像素入棧。,3．掃描線種子填充算法算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進(jìn)行這個過程，直到所保存的每個區(qū)段都填充完畢。 可以填充有孔區(qū)域，對于每

22、一個待填充區(qū)段，只需入棧一次，因此提高了區(qū)域填充的效率。,3.3.5 圓域的填充對每條掃描線，計算它與圓域的相交區(qū)間。接著，為每一條掃描線建立一個新圓表，存放在該行第一次出現(xiàn)的圓的有關(guān)信息。然后，為當(dāng)前掃描線設(shè)置一個活化圓表。由于一條線與一個圓只能相交一個區(qū)間，所以在活性圓表中，每個圓只需一個結(jié)點即可。結(jié)點內(nèi)存放當(dāng)前掃描線的區(qū)間端點，以及用于計算下一條掃描線與圓相交的區(qū)間端點所需的增量。該增量用于在當(dāng)前掃描線處理完畢之后，對端點

23、坐標(biāo)進(jìn)行更新計算，以便得到下一條掃描線的區(qū)間端點。,3.3.6 區(qū)域填充屬性1．填充樣式2．填充顏色3．填充圖案,3.4 字符,3.4.1 字符存儲與顯示1．點陣字符每個字符都是利用掩膜來定義，并將其寫入幀緩存保存和顯示。點陣字符的顯示：首先從字庫中將它的位圖檢索出來，然后將檢索到的位圖寫到幀緩沖器中。讀取幀緩存中這些像素值，就可以在屏幕上顯示此字符。如果將保存在幀緩存中某字符掩膜相應(yīng)像素值均置

24、成背景色或背景光強(qiáng)，就可以擦除幀緩存中的該字符。,2．矢量字符矢量字符被表達(dá)為一個點坐標(biāo)的序列，相鄰兩點表示一條矢量，字符的形狀便由矢量序列刻劃。矢量字符的顯示：首先從字庫中讀它的字符信息。然后取出端點坐標(biāo)，對其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點的標(biāo)志顯示出字符。,3.4.2 字符屬性顯示的字符的外觀由字體、字形、字號、字間距、行間距等屬性控制。一般來說，字體確定風(fēng)格，字形確定外觀，字號確定尺寸。 1．單個字符屬

25、性2．文本屬性,3.5 裁剪,3.5.1 點的裁剪對于一點P（x , y），要判斷其是否可見，可利用下面的不等式組來判斷此點是否落在窗口范圍內(nèi)：滿足上述不等式組的點則在窗口范圍內(nèi)，可見，予以保留；反之，該點落在窗口外，不可見，舍棄（裁剪）。,,3.5.2 直線裁剪1．Cohen-Sutherland裁剪算法（編碼裁剪法）基本思想：對于每條待裁剪的線段P1P2分為三種情況處理：（1）若P1P2完全在窗

26、口內(nèi)，則顯示該線段P1P2，簡稱“取”之；（2）若P1P2完全在窗口外，則丟棄該線段，簡稱“舍”之；（3）若線段既不滿足“取”的條件，也不滿足“舍”的條件，則求線段與窗口邊界的交點，在交點處把線段分為兩段，其中一段完全在窗口外，可舍棄之，然后對另一段重復(fù)上述處理。,Cohen-Sutherland直線剪裁算法以區(qū)域編碼為基礎(chǔ)，將窗口及其周圍的八個方向以4 bit的二進(jìn)制數(shù)進(jìn)行編碼，如圖3-42所示。具體編碼過程為：延長窗口的四條邊

27、線（yt、yb、xr、xl），將二維平面分成九個區(qū)域。任何一條線段的端點都按其所處區(qū)域賦予4位編碼CtCbCrCl。,,如果某線段的兩個端點的四位 二進(jìn)制編碼全為“0000”，可直 接保留；如果對兩端點的四位二進(jìn)制編碼進(jìn)行邏輯與（按位乘）運(yùn)算，結(jié)果不為零，可直接舍棄；否則，這一線段可能與窗口相交。此時，需要對線段進(jìn)行再分割，即找到與窗口邊線的一個交點，根據(jù)交點位置，也賦予四位二進(jìn)制編碼，并對分割后的線段重復(fù)進(jìn)行檢查，直到

28、全部線段均被舍棄或被保留為止。,裁剪窗口,2．中點分割算法基本思想：當(dāng)一條直線段既不能直接保留也不能直接舍棄，需要求其與區(qū)域的交點時，不斷地用對分方法，舍去線段的不可見部分，用中點去逼近線段與窗口邊界的交點。,3．梁友棟-barsky裁剪算法  定義直線的參數(shù)化方程為： 首先按參數(shù)化形式寫出裁剪條件： 這四個不等式可以表示為形式：,,,其中，參數(shù)pk,qk定義為：

29、 任何平行于裁剪邊界之一的直線pk=0，其中k對應(yīng)于裁剪邊界（k=1,2,3,4對應(yīng)于左、右、下、上邊界），如果還滿足qk0時，線段從裁剪邊界延長線的內(nèi)部延伸到外部。當(dāng)pk≠0時，可以計算出線段與邊界k的延長線的交點的u值：u=qk/pk。,梁友棟-Barsky裁剪算法在尋找線段可見部分（如果有可見線段）時可以歸結(jié)為四個步驟：（1）如果對所有的k都有pk=0和qk0的k，計算rk=qk/pk ，將1和各個rk值之中的

30、最小值賦給u2。（4）如果u1>u2，則線段完全落在裁剪窗口之外，不可見，可直接舍棄。否則，裁剪后線段的端點由參數(shù)u的兩個值u1、u2計算出來。,3.5.3 多邊形裁剪1．Sutherland-Hodgman算法基本思想：每次用窗口的一條邊界對多邊形進(jìn)行裁剪，把落在窗口外部的圖形去掉，落在窗口內(nèi)部的圖形保留，并把它作為下一次待裁剪的多邊形。這樣，當(dāng)連續(xù)用窗口的四條邊界對原始多邊形進(jìn)行裁剪后，最后得到的就是裁剪后

31、的結(jié)果多邊形。,2．Weiler-Atherton裁剪算法基本思想：將待裁剪多邊形（簡寫為P1）和裁剪矩形窗口（簡寫為P2）均設(shè)定為按順時針方向排列。算法從P1的任一頂點出發(fā)，沿著它的邊向下處理，當(dāng)P1和P2相交時（假定交點為I）：（1）若P1的邊是進(jìn)入P2，則繼續(xù)沿P1的邊往下處理，同時輸出該線段；（2）若P1的邊是從P2中出來，則從此交點I開始，沿著窗口邊框向右檢測P2的邊，即用P2的有效邊框去裁剪P1的邊，找到P

32、1和P2最靠近交點I的新交點，同時輸出由I到S之間窗邊上的線段；（3）返回交點I，再沿著P1處理各條邊，直到處理完P(guān)1的每一條邊，回到起點為止。,3.5.4 曲線裁剪對于被裁剪的曲線所圍成的區(qū)域，找出包圍（外接）此區(qū)域的最小矩形，稱其為曲線邊界對象的包圍矩形（或包圍盒），然后測試包圍矩形是否與矩形裁剪窗口有重疊。如果包圍矩形完全落在裁剪窗口內(nèi)，則全部保留該對象；如果包圍矩形完全落在裁剪窗口外，則全部舍棄該對象；

33、如果不滿足上述矩形測試的條件，則要求解直線-曲線聯(lián)立方程組，得出裁剪窗口與曲線邊界線的交點，即裁剪交點，再進(jìn)行判斷。,3.5.5 字符裁剪1．字符串裁剪把整個字符串作為整體來對待。2．字符裁剪分別對每個字符來處理。3．矢量\像素裁剪每個字符都看作是由一系列矢量（線段）或像素構(gòu)成的，故對每一個矢量或像素都必須個別地進(jìn)行裁剪。,3.5.6 三維圖形的裁剪把二維線段的Cohen-Suther

34、land裁剪算法稍加改進(jìn)，就能推廣到三維平行投影的裁剪算法中。對空間任意一點P（x,y,z）按其所處位置賦予6位二進(jìn)制編碼。（1）兩個端點的編碼全為“0000”，直接保留；（2）對兩端點的編碼進(jìn)行邏輯與運(yùn)算，結(jié)果不為零，可直接舍棄；（3）否則，計算出線段與窗口表面的交點，并將線段分段后繼續(xù)處理，直到余下的線段符合前兩種簡單情況為止。,3.6 反走樣,對圖形進(jìn)行光柵化時，是用離散的像素顯示在連續(xù)空間定義的對象。這