1、第二次課第2章 光柵圖形學光柵圖形顯示器相當于一個象素的矩陣。圖形的掃描轉換（或圖形的光柵化）：確定最佳逼近圖形的象素集合，并用指定屬性寫象素的過程。重要概念及算法：區域填充：二維圖形的光柵化必須確定區域對應的象素集，并用指定的屬性或圖案顯示之。裁剪：確定一個圖形的哪些部分在窗口內，必須顯示；那些部分落在窗口之外，不該顯示的過程。走樣反走樣：光柵化時，由于顯示器分辨率有限，對于非水平、非垂直的直線，因象素逼近誤差，使所畫圖形產生畸變（臺階、鋸齒）的現象稱之為走樣。用于減少或消除走樣的技術稱為反走樣。隱藏消隱：隱藏部分是不可見的，如果不刪除隱藏的線或面，可能對圖形錯誤理解。因此必須把隱藏的部分從

2、圖中刪除，稱為消隱。2.1 直線段的掃描轉換算法直線的掃描轉換：確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。三個常用算法：l 數值微分法（DDA）l 中點畫線法l Bresenham算法 數值微分(DDA)法基本思想：已知過端點的直線段L：，直線斜率為 ，從x的左端點x0開始，向x右端點步進，步長=1(個象素)，計算相應的y坐標y=kx+b；取象素點(x, round(y)作為當前點的坐標。l 作為最底層的光柵圖形算法，在通常的CAD/圖形系統中，會被大量應用，因此，哪怕節約一個加法或減法，也是很了不起的改進。l 由此出發點，導致增量算法的思想。計算當時；即：當x每

3、遞增1，y遞增k(即直線斜率) 。算法程序2-1 （P18）例：畫直線段，DDA算法演示。 中點畫線法基本思想：當前象素點為(xp, yp) ，下一個象素點為P1或P2。設M=(xp+1, yp+0.5)，為P1與P2之中點，Q為理想直線與x=xp+1垂線的交點。將Q與M的y坐標進行比較。l 當M在Q的下方，則P2應為下一個象素點；l M在Q的上方，應取P1為下一點。構造判別式：d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1, b=x1-x0, c=x0y1-x1y0n 當d<0，M在L(Q點)下方，取右上方P2為下一個象素；n 當

4、d>0，M在L(Q點)上方，取右方P1為下一個象素；n 當d=0，選P1或P2均可，約定取P1為下一個象素；可采用增量計算，提高運算效率：l 若d³0，則取正右方象素P1 (xp+1, yp)，要判下一個象素位置，應計算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量為a。l 若d<0，則取右上方象素P2 (xp+1, yp+1)。要判斷再下一象素，則要計算d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量為ab。畫線從(x0, y0)開始，d的初值：d0=F(x0+1, y0+0.5)

5、=F(x0, y0)+a+0.5b=a+0.5b。可以用2d代替d來擺脫小數，提高效率。令d0=2a+b，d1=2a，d2=2a+2b。算法程序2-2 （P19）例：用中點畫線法中點畫線算法演示 Bresenham算法基本思想：過各行各列象素中心構造一組虛擬網格線。按直線從起點到終點的順序計算直線與各垂直網格線的交點，然后根據誤差項的符號確定該列象素中與此交點最近的象素。設直線方程為：yi+1= yi+k(xi+1-xi)= yi+k，其中k=dy/dx。 因為直線的起始點在象素中心，所以誤差項d的初值d0=0。x下標每增加1，d的值相應遞增直線的斜率值k，即ddk。一旦d1，就把它減去1，這

6、樣保證d在0、1之間。l 當d0.5時，最接近于當前象素的右上方象素(xi+1,yi+1)，y方向加1，d減去1；l 而當d<0.5時，更接近于右方象素(xi+1,yi)。為方便計算，令ed-0.5，e的初值為-0.5，增量為k。l 當e0時，取當前象素（xi，yi）的右上方象素(xi+1,yi+1)，e減小1；l 而當e<0時，更接近于右方象素(xi+1,yi)。算法程序2-3 （P21）例：Line: P0(0, 0), P1(5,2) k=dy/dx=0.4，圖示可以改用整數以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換： 。最終，Bresenham算法也是每個象

7、素，需一個整數算法，其優點是可以用于其他二次曲線。第三次課2.2 圓弧的掃描轉換算法圓的特征：八對稱性，只要掃描轉換八分之一圓弧，就可以求出整個圓弧的象素集。中點畫圓法：考慮中心在原點，半徑為R的第二個8分圓。構造判別式（圓方程）：l 若 d<0, 則取P1為下一象素，而且再下一象素的判別式l 若d>=0, 則應取P2為下一象素，而且下一象素的判別式第一個象素是（0,R），判別式d的初始值為。算法程序2-5 （P22）為了進一步提高算法的效率，可以將上面的算法中的浮點數改寫成整數，將乘法運算改成加法運算，即僅用整數實現中點畫圓法。使用e=d-0.25代替d，e0=1-R。中點畫圓算

8、法演示2.3 多邊形的掃描轉換與區域填充多邊形有兩種重要的表示方法：頂點表示和點陣表示。多邊形的掃描轉換：把多邊形的頂點表示轉換為點陣表示。區域可采用內點表示和邊界表示兩種表示形式。區域填充：指先將區域的一點賦予指定的顏色，然后將該顏色擴展到整個區域的過程。多邊形分為凸多邊形、凹多邊形、含內環的多邊形。 多邊形的掃描轉換.1 掃描線算法基本思想：按掃描線順序，計算掃描線與多邊形的相交區間，再用要求的顏色顯示這些區間的象素，即完成填充工作。對于一條掃描線填充過程可以分為四個步驟：l 求交 計算掃描線與多邊形各邊的交點。l 排序 把所有交點按x值的遞增順序排序。l 配對 將第1個與第2個、第3個與

9、第4個交點配對每對交點代表掃描線與多邊形的一個相交區間。l 填色 把相交區間內的象素置成多邊形的顏色，把相交區間外的象素置成背景色。圖2-8掃描線與多邊形的頂點或邊界相交時，必須正確的交點的取舍。只需檢查頂點的兩條邊的另外兩個端點的y值。按這兩個y值中大于交點y值的個數是0,1,2來決定。 圖2-11數據結構：l 活性邊表(AET)：把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中。l 結點內容：x：當前掃描線與邊的交點坐標x：從當前掃描線到下一條掃描線間x的增量ymax：該邊所交的最高掃描線號ymaxl 新邊表（NET）：存放在該掃描線第一次出現的邊。

10、若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中。圖2-10假定當前掃描線與多邊形某一條邊的交點的橫坐標為x，則下一條掃描線與該邊的交點不需要重新計算，只要加一個增量x。設該邊的直線方程為：ax+by+c=0。若yyi，x=xi；則當y = yi+1時，其中為常數。算法程序2-6圖2-8中多邊形的AET和填充過程：5 -3 25 3 3 2 0 78 3 3 填充5,5)填充2,8)掃描線1掃描線22 0 711 0 8 填充2,11)掃描線32 0 711 0 8 填充2,11)掃描線42 0 7掃描線55 2 85 -1.5 7填充2,5) 5,11)11 0 8 2 0

11、7掃描線67 2 83.5 -1.5 7填充2,3.5) 7,11)11 0 8 掃描線79 2 811 0 8 填充9,11)掃描線8掃描線0初始化.2 邊界標志算法基本思想：l 幀緩沖器中對多邊形的每條邊進行直線掃描轉換，亦即對多邊形邊界所經過的象素打上標志。l 然后再采用和掃描線算法類似的方法將位于多邊形內的各個區段著上所需顏色。l 使用一個布爾量inside來指示當前點是否在多邊形內的狀態。l Inside的初值為假，每當當前訪問的象素為被打上邊標志的點，就把inside取反。對未打標志的象素，inside不變。 l 若訪問當前象素時，inside為真，說明該象素在多邊形內，則把該象素

12、置為填充顏色。 用軟件實現時，掃描線算法與邊界標志算法的執行速度幾乎相同，但由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現，這時它的執行速度比有序邊表算法快一至兩個數量級。 區域填充算法l 區域指已經表示成點陣形式的填充圖形，它是象素的集合。l 區域可采用內點表示和邊界表示兩種表示形式。l 區域可分為4向連通區域和8向連通區域。l 區域填充指先將區域的一點賦予指定的顏色，然后將該顏色擴展到整個區域的過程。區域填充算法要求區域是連通的。l 4向連通區域和8向連通區域.1 區域填充的遞歸算法內點表示的4連通區域的遞歸填充算法，算法程序2-8邊界表示的4連通區域的遞

13、歸填充算法，算法程序2-9.2 區域填充的掃描線算法算法基本過程：l 首先填充種子點所在掃描線上的位于給定區域的一個區段；l 然后確定與這一區段相連通的上、下兩條掃描線上位于給定區域內的區段，并依次保存下來；l 反復這個過程，直到填充結束。(1) 初始化：堆棧置空。將種子點（x，y）入棧。(2) 出棧：若棧空則結束。否則取棧頂元素（x，y），以y作為當前掃描線。(3) 填充并確定種子點所在區段：從種子點（x，y）出發，沿當前掃描線向左、右兩個方向填充，直到邊界。分別標記區段的左、右端點坐標為xl和xr。(4) 并確定新的種子點：在區間xl，xr中檢查與當前掃描線y上、下相鄰的兩條掃描線上的象素

14、。若存在非邊界、未填充的象素，則把每一區間的最右象素作為種子點壓入堆棧，返回第（2）步。上述算法對于每一個待填充區段，只需壓棧一次；因此，掃描線填充算法提高了區域填充的效率。例題圖示，共6幅圖，未完成部分由學生思考完成2.4 字符字符指數字、字母、漢字等符號。計算機中字符由一個數字編碼唯一標識。國際上最流行的字符集：“美國信息交換用標準代碼集” （American Standard Code for Information Interchange），簡稱ASCII碼。它是用7位二進制數進行編碼表示128個字符；包括字母、標點、運算符以及一些特殊符號。漢字編碼的國家標準字符集GB2312-80，

15、94個區，94個位，符號 = 1個區碼 + 1個位碼用字節的最高位標識，最高位為0表示ASCII碼；最高位為1表示漢字編碼。字庫：存儲每個字符的形狀信息，分為點陣型和矢量型。2.4.1 點陣字符點陣字符：每個字符由一個位圖表示，該位為1表示字符的筆畫經過此位，對應于此位的象素應置為字符顏色。該位為0表示字符的筆畫不經過此位，對應于此位的象素應置為背景顏色。圖2-15在實際應用中，有多種字體（如宋體、楷體等），每種字體又有多種大小型號，因此字庫的存儲空間是很龐大的。解決這個問題一般采用壓縮技術。點陣字符的顯示分為兩步。首先從字庫中將它的位圖檢索出來。然后將檢索到的位圖寫到幀緩沖器中。 矢量字符.

16、1 相關概念在一個使用X-Y坐標系的平面中，對于一個有確定方向的線段，若已知：l 一個端點（如起點）坐標l 線段長度l 線段與X座標軸正方向的夾角角度值就可以畫出平面內的一個有向線段矢量，那么：(1) 矢量的方向是線段起點指向線段的終點，(2) 矢量X坐標軸正方向的夾角是指，以矢量起點為旋轉中心，該矢量從與X軸正向平行、且方向相同的位置逆時針旋轉至當前位置所經過的旋轉角度，記作LDA。在一個使用X-Y坐標系的平面中，一個有確定方向的線段（即矢量），有以下特征：l 起點的坐標l 線段的長度l LDA值YOA(x0,y0)LDAB(x1,y1)X.2 矢量字符構建定義：(1) 字符由線段構成；(2

17、) 每條線段有方向；(3) 構成字符的所有線段是連續的，即首尾相連；(4) 每條線段有三個屬性：a.長度；b.LDA值；c.可見性；(5) 整個字符圖形只有一個起點和一個終點；(6) 起點位于右下角。矢量字符構造步驟：(1) 使用起點作為第一個矢量線段的端點；(2) 將矢量線段置于水平位置，線段方向與X軸正向相同，以起點為中心，旋轉角度為LDA；(3) 以矢量線段的終點作為下一個線段的起點，重復(1)(2)，直到所有的矢量線段被放在正確的位置上。.3 矢量字符舉例特點：l 點陣字符：存儲量大，易于顯示l 矢量字符：存儲量小，美觀，變換方便；但需要光柵化后才能顯示。 字符屬性l 字體： l 字高

18、：l 字寬因子：l 字傾斜角：l 對齊：l 字色：l 寫方式：“替換”方式，字符掩膜中空白區置成背景色；“與”方式，空白區顏色不受影響。字符掩膜：包含表示該字符的象素圖案的一小塊光柵。2.5 裁剪裁剪：確定圖形中哪些部分落在顯示區之內，哪些落在顯示區之外，以便只顯示落在顯示區內的那部分圖形。這個選擇過程稱為裁剪。圖2-16最簡單的裁剪方法是把各種圖形掃描轉換為點之后，再判斷各點是否在窗內。但那樣太費時，一般不可取。這是因為有些圖形組成部分全部在窗口外，可以完全排除，不必進行掃描轉換。所以一般采用先裁剪再掃描轉換的方法。 直線段裁剪直線段裁剪算法是復雜圖元裁剪的基礎。復雜的曲線可以通過折線段來近

19、似，從而裁剪問題也可以化為直線段的裁剪問題。l Cohen-Sutherlandl 中點分割算法l 梁友棟barskey算法.1 Cohen-Sutherland裁剪算法算法：對于每條線段P1P2分為三種情況處理：(1) 若P1P2完全在窗口內，則顯示該線段P1P2簡稱“取”之。(2) 若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。(3) 若線段不滿足“取”或“棄”的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。編碼：為快速判斷，采用如下編碼方法：每個區域賦予4位編碼CtCbCrCl。定義：圖2-17，18先求出P1P2所在的區號code1，co

20、de2。若code1=0且code2=0，則P1P2完全在窗口內，“取”之；若按位與運算code1&code20，則P1P2明顯在窗口外，“棄”之；否則求出線段與窗口某邊的交點，在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。算法程序2-11 #define LEFT 1 /0001#define RIGHT 2 /0010#define BOTTOM 4 /0100#define TOP 8 /1000“|”按位或，如c|=LEFT即c=c|LEFT=0000|0001=0001“&”按位與XLXRYBYTP1code1=0000P2code2

21、=0000“|”或“&&”與更正：if(y>YT)c|=TOP;求交部分算法示例1：code1=0000；XLXRYBYTP1code1=1001P2code2=0001code2=0000；不進入while循環；displaylineP1P2。示例2：code1=1001；code2=0001；進入while循環；code1&code2=00010；return，即不繪制線段。XLXRYBYTP1code1=1001P2code2=0110示例3：code1=1001；code2=0110；進入while循環； code10 code=code1=1001即從P

22、1點開始求交；LEFT & code=0001&1001=00010即端點P1在左；XLXRYBYTP1code1=0000P2code2=0110求左交點(XL,y)；code=code1=1001 左交點為新的P1點，且code1=0000；進入第二次循環；code1=0 code=code2=0110即從P2點開始求交；BOTTOM & code=0100&0110=01000XLXRYBYTP1code1=0000P2code2=0000即端點P2在下；求下交點(x,YB)；code=code2=0110下交點為新的P2點，且code2=0000；此時，

23、code1=code2=0000； 跳出循環；displaylineP1P2。 中點分割裁剪算法基本思想：與前一種Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關系分為三種情況：全在、完全不在和線段和窗口有交。對前兩種情況，進行一樣的處理。對于第三種情況，用中點分割的方法求出線段與窗口的交點。圖2-19描述算法：求線段與窗口的交點，A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。AB之間的連線即為線段P0P1的可見部分。l 從P0出發找最近可見點A的方法先求出P0 P1 的中點Pm若P0Pm不是顯然不可見的，并且P0 P1在窗口中有可見部分，則距P0

24、最近的可見點一定落在 P0 Pm上，所以用P0 Pm代替P0 P1 ；否則取 PmP1代替P0 P1 再對新的P0 P1求中點Pm。重復上述過程，直到PmP1長度小于給定的控制常數為止，此時Pm收斂于交點。l 從P1出發找最近可見點B采用上面類似方法。作業：按中點分割裁剪算法，求出點A、B的坐標，控制常數為1。P0(-2,3)P1(3,-1)PmABXL=0XR=4YB=0YT=4.3 梁友棟-Barskey裁剪算法描述算法：梁-Barsky算法的幾何含義：入邊、出邊與端點。入邊出邊端點參數化形式寫出裁剪條件：可以統一表示為形式：更正：q3=y1-YB當pk=0，即直線平行于裁剪邊界（其中k=

25、1，2，3，4對應左、右、下、上邊界）若qk<0，則線段完全在邊界外；若qk0，則該線段平行于裁剪邊界并且在窗口內；當pk0，若pk<0，線段從裁剪邊界延長線的外部延伸到內部；若pk>0，線段從裁剪邊界延長線的內部延伸到外部。可計算出線段與邊界k的延長線的交點的u值：u= qk/pk。對于每條直線，可以計算出參數u1和u2，它們定義了在裁剪矩形內的線段部分。l u1的值由線段從外到內遇到的矩形邊界所決定（p<0）。對這些邊界計算rk=qk/pk 。u1取0和各個rk值之中的最大值。l u2的值由線段從內到外遇到的矩形邊界所決定（p>0）。對這些邊界計算rk=qk/

26、pk 。u2取1和各個rk值之中的最小值。l 如果u1>u2，則線段完全落在裁剪窗口之外，被舍棄。l 否則裁剪線段由參數u的兩個值u1，u2計算出來。對三種算法比較：l Cohen-Sutherland與中點法在區域碼測試階段能以位運算方式高效率地進行，因而當大多數線段能夠簡單的取舍時，效率較好。l 梁友棟Barskey算法只能應用于矩形窗口的情形，但其效率比前兩者要高，這是因為運算只涉及到參數，僅到必要時才進行坐標計算。梁友棟Barsky算法演示 多邊形裁剪Sutherland-Hodgeman算法：l 基本思想是一次用窗口的一條邊裁剪多邊形。l 考慮窗口的一條邊以及延長線構成的裁剪線

27、，該線把平面分成兩個部分：可見一側；不可見一側。l 多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關系只有四種，圖2-20，S、P與裁剪線的位置關系對于l 情況（1）僅輸出頂點P；l 情況（2）輸出0個頂點；l 情況（3）輸出線段SP與裁剪線的交點I；l 情況（4）輸出線段SP與裁剪線的交點I和終點P上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，只是判斷點在窗口哪一側改變求線段SP與裁剪邊的交點的算法。圖2-21；裁剪例題示意圖2.5.3 字符裁剪按三個精度裁剪：l 串精度：將包圍字串的外接矩形對窗口作裁剪l 字符精度：將包圍字的

28、外接矩形對窗口作裁剪l 畫筆或象素精度：將筆劃分解成直線段對窗口作裁剪2.6 反走樣走樣：用離散量表示連續量引起的失真現象稱之為走樣(aliasing)。反走樣：用于減少或消除這種效果的技術稱為反走樣(antialiasing)。光柵圖形的走樣現象： (1) 鋸齒現象（圖示）(2) 圖形細節失真（圖示）(3) 微小對象遺失與動態圖形閃爍（圖示）常用的反走樣方法：(1) 提高分辨率(2) 區域采樣 非加權區域采樣（盒式濾波器） 加權區域采樣（圓錐形濾波器、半球形濾波器等）提高分辨率把顯示器分辨率提高一倍，直線經過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起

29、來就平直光滑了一些。增加分辨率雖然簡單，但是不經濟的方法，有物理上的困難；而且它也只能減輕而不能消除鋸齒問題。 非加權區域采樣基本思想：每個象素是一個具有一定面積的小區域，將直線段看作具有一定寬度的狹長矩形。當直線段與象素有交時，求出兩者相交區域的面積，然后根據相交區域面積的大小確定該象素的亮度值。面積計算：l 情況(1)(5)陰影面積為：D2/2m；l 情況(2)(4)陰影面積為：D-m/2；l 情況(3)陰影面積為：1-D2/m為了簡化計算可以采用離散的方法：l 首先將屏幕象素均分成n個子象素；l 然后計算中心點落在直線段內的子象素的個數k；l 將屏幕該象素的亮度置為相交區域面積的近似值可

30、k/n。非加權區域采樣方法有兩個缺點：l 象素的亮度與相交區域的面積成正比，而與相交區域落在象素內的位置無關，這仍然會導致鋸齒效應。l 直線條上沿理想直線方向的相鄰兩個象素有時會有較大的灰度差。 加權區域采樣(1) 圓錐形濾波器為了克服非加權區域采樣的兩個缺點，可采用更接近優化的圓錐形濾波器。該濾波器（加權函數）是一個圓錐。圓錐的底圓中心在當前象素中心，底圓半徑為一個象素單位，錐高為1。當直線條經過該象素時，該象素的灰度值是在直線與圓錐相交區域上對濾波器進行積分的積分值。相當于使用過直線條兩邊緣，且垂直于象素區域的一對平面，切割圓錐所得到的厚度等于直線條寬度的三維物體的體積。圓錐形濾波器特點：

31、l 接近理想直線的象素將被分配更多的灰度值。l 相鄰兩個象素的濾波器相交，所以直線條經過該相交區域時，將對這兩個象素都分配給適當的灰度值，有利于縮小直線條上相鄰象素的灰度差。(2) 離散計算方法：n 將屏幕劃分為n=3×3個子象素，加權表可以取作：；n 計算每個子象素對原象素的貢獻，并保存在一張二維加權表中；n 然后求出所有中心落于直線段內的子象素集；n 最后計算所有這些子象素對原象素亮度貢獻之和，該值乘以象素的最大灰度值作為該象素的顯示灰度值。2.7 消隱消隱：為消除圖形的二義性，繪制時消除被遮擋的不可見的線或面，稱之為消除隱藏線或隱藏面。 消隱的分類消除對象為三維物體，三維物體的

32、表示有B-rep（Boundary representation，邊界表示）和CSG（Constructive Solid Geometry，構造實體幾何）表示。消隱分類：l 按對象：u 線消隱：消隱物體上不可見的邊u 面消隱：消隱物體上不可見的面l 按空間：u 物體空間的消隱算法：光線投射算法，Roberts算法（將場景中每一個面與其它各個面比較，求所有點、邊、面的遮擋關系）u 圖象空間的消隱算法：Z-Buffer算法，掃描線算法，Warnock算法 （對屏幕上每個象素進行判斷，決定哪個多邊形在該象素可見）u 物體空間和圖象空間的消隱算法：畫家算法 （在物體空間中預先計算面的可見性優先級，再

33、在圖象空間中生成消隱圖） 消除隱藏線(1) 對造型的要求 造型系統中要有面的信息，最好有體的信息。(2) 坐標變換視點是Z軸正無窮大處，視線方向變為Z軸的負方向。對視椎體以外的物體先作裁剪。(3) 最基本的運算判斷面對線的遮擋關系，反復地進行線線、線面之間的求交運算。 判斷面對線的遮擋關系； 把體分解為面，再判斷面與線的遮擋關系。算法：(1) 若線段的兩端點及視點在給定平面的同側，線段不被給定平面遮擋，轉7(2) 若線段的投影與平面投影的包圍盒無交，線段不被給定平面遮擋，轉7(3) 求直線與相應無窮平面的交。若無交點，轉4。否則，交點在線段內部或外部。若交點在線段內部，交點將線段分成兩段，與視

34、點同側的一段不被遮擋，另一段在視點異側，轉4再判；若交點在線段外部，轉4。(4) 求所剩線段的投影與平面邊界投影的所有交點，并根據交點在原直線參數方程中的參數值求出Z值(即深度)。若無交點，轉5。(5) 以上所求得的各交點將線段的投影分成若干段，求出第一段中點。(6) 若第一段中點在平面的投影內，則相應的段被遮擋，否則不被遮擋；其他段的遮擋關系可依次交替取值進行判斷。(7) 結束。 (4) 線消隱算法 基本數據結構：面表（存放參與消隱的面）+ 線表（存放待顯示的線）畫出數據結構 算法：為了提高算法的效率，需要設法減少求交的工作量。若V· N>0，稱該多邊形為后向面。若V

35、3; N<0，稱該多邊形為前向面。后向面總是看不見的，不會由于后向面的遮擋，而使別的棱成為不可見的。因此計算時，可以把這些后向面全部去掉，這并不影響消隱結果。 消除隱藏面(1) 畫家算法算法描述：先把屏幕置成背景色，再把物體的各個面按其離視點的遠近進行排序，排序結果存在一張深度優先級表中。然后按照從遠到近的順序逐個繪制各個面。關鍵是如何對場景中的物體按深度排序。對場景中的物體按深度排序：(1) 深度重疊測試設Zmin最小的多邊形為P，多邊形序列中其他多邊形記為Q；因Zmin(P)<Zmin(Q)，若Zmax(P)<Zmin(Q)，則P肯定不能遮擋Q。否則作進一步的檢查。(2) 投影重疊判斷l P和Q在oxy平面上投影的包圍盒在x方向上不相交l P和Q在oxy平面上投影的包圍盒在y方向上不相交l P和Q在oxy平面上的投影不相交l P在Q之后。P的各頂點均在Q的遠離視點的一側l Q在P之前。Q的各頂點均在P的靠近視點的一側(3) 精確的重疊測試以上測試失敗，須對兩個多邊形在xy平面上的投影作求交運算。計算時不必具體求出重疊部分。在交點處進行深度比較，只要能判斷出前后順序即可。若遇到多邊形相交或循環重疊的情況（如圖f），還必須在相交處分割多邊形，然后進行判斷。優點：原理簡單。缺點：只能處理互不相交的面，而且深度優先級表