建筑造型裝飾與三維動(dòng)畫 第3章

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

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

3、（xp+1,yp+1）兩者之一。令M為P1和P2的中點(diǎn)，易知M的坐標(biāo)為（xp+1,yp+0.5）。 設(shè)Q是理想直線與垂直線x=xp+1的交點(diǎn)。顯然，若M在Q的下方，則P2離直線近，應(yīng)取為下一個(gè)像素；否則應(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的符號(hào)，而且d的增量都是整數(shù)，只是其初始值包含小數(shù)。因此，我們可以用2d代替d，來(lái)擺脫小數(shù)。 如果進(jìn)一步把算法中2*a改為a+a等等，那么這個(gè)算法不僅只包含整數(shù)變量，而且不包含乘除法，適合硬件實(shí)現(xiàn)。,3.1.3 Brese

5、nham畫線算法 過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)最近的像素。 由圖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時(shí)，選Ti，當(dāng)di<0

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

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

8、,yp-0.5）。顯然，若M在圓內(nèi)，則P1離圓弧近，應(yīng)取為下一個(gè)像素；否則應(yīng)取P2。,判別式d：d的初始值為：在d≥0的情況下，取右下方像素P2，在d<0的情況下，取正右方像素P1，,,3.2.3 Bresenham畫圓算法 假設(shè)生成圓心在坐標(biāo)原點(diǎn)，半徑為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ū)域的表示和類型 頂點(diǎn)表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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