第7章消除隱藏線與隱藏面

1、1 給出一個三維形體，要畫出確定的立體給出一個三維形體，要畫出確定的立體感強(qiáng)的投影視圖，必須決定形體上哪些感強(qiáng)的投影視圖，必須決定形體上哪些線線或哪或哪些些面面是是不可見不可見的，不可見的部分不顯示，這就的，不可見的部分不顯示，這就是是消除隱藏線與隱藏面消除隱藏線與隱藏面的問題。的問題。 2?34 確定可見性的基本思想非常簡單，但用計確定可見性的基本思想非常簡單，但用計算機(jī)程序?qū)崿F(xiàn)時，一般要涉及到相當(dāng)復(fù)雜的計算機(jī)程序?qū)崿F(xiàn)時，一般要涉及到相當(dāng)復(fù)雜的計算。針對不同的需要，提出了各種不同的算法。算。針對不同的需要，提出了各種不同的算法。 假設(shè)：三維形體表示為假設(shè)：三維形體表示為多邊形多邊形表面形成的

2、集合，表面形成的集合，投影約定為沿著投影約定為沿著z軸正向的軸正向的正交正交投影投影消除隱藏面算法分類：消除隱藏面算法分類： 圖象空間算法（圖象空間算法（Image Space Methods） 客體空間算法客體空間算法 （Object Space Methods） 5678),),( (),), , ,( (zyxzyx,k,kknnnk n 222222coszkykxkznynxnknknknzzyyxxknkn若分子為若分子為正正，則，則 , ,面為可見；面為可見；若分子為若分子為負(fù)負(fù)，則，則 ，面為不可見；，面為不可見；若分子為若分子為零零，則，則 ，此面退化為線。，此面退化為線。

3、2 20 02 22 29) 4 , 1 , 2() 1 , 0 , 2() 1 , 2 , 3(ABDAn例：設(shè)空間有一個四面體，頂點例：設(shè)空間有一個四面體，頂點A，B，C，D的坐標(biāo)依次是的坐標(biāo)依次是(0,0,0)，(2,0,1)，(4,0,0)，(3,2,1)。從。從z軸正向無窮遠(yuǎn)處觀察，軸正向無窮遠(yuǎn)處觀察，求各面的可見性。求各面的可見性。 觀察方向向量是觀察方向向量是k=(0,0,1)，三角面，三角面DAB的法向量是：的法向量是： 0 04 4 kn10面面DAB為可見面。類似計算可知，面為可見面。類似計算可知，面DBC是可是可見面，面見面，面ADC是不可見面，面是不可見面，面ACB退化

4、為線。退化為線。1112 對于非凸多面體或多個形體，這個方法對于非凸多面體或多個形體，這個方法通常做為預(yù)處理步驟，即先使用這個方法排除通常做為預(yù)處理步驟，即先使用這個方法排除往后不必考慮的不可見面。只考慮選出的可能往后不必考慮的不可見面。只考慮選出的可能可見面中哪些是可見或部分可見的?？梢娒嬷心男┦强梢娀虿糠挚梢姷?。 消除隱藏線的線面比較法的消除隱藏線的線面比較法的第一步第一步就是利就是利用外法線判斷出所有可能的可見面，可能可見用外法線判斷出所有可能的可見面，可能可見面上的線段是可能可見線。面上的線段是可能可見線。第二步再第二步再依次用每依次用每一條可能可見線，與每一個可能可見面比較，一條可能

5、可見線，與每一個可能可見面比較，從而確定出可見線、隱藏線及可見線上的隱藏從而確定出可見線、隱藏線及可見線上的隱藏部分。部分。1314一個多一個多邊形表邊形表面的投面的投影范圍影范圍 多邊形表面多邊形表面ABCD在在ZV=0平面上的正投影是平面上的正投影是ABCD，包含，包含ABCD且四邊分別平行于且四邊分別平行于XV和和YV軸的最小矩形軸的最小矩形PQRS就是就是ABCD的范圍，的范圍，找出找出PQRS的方法被稱為的方法被稱為包圍盒方法包圍盒方法。15 空間任一線段，只有其投影與多邊形表面空間任一線段，只有其投影與多邊形表面的的投影范圍發(fā)生交迭投影范圍發(fā)生交迭時，才可能與多邊形表面時，才可能與

6、多邊形表面有遮檔關(guān)系。有遮檔關(guān)系。16m mi in n2 2m ma ax x2 2m mi in n1 1m ma ax x1 1x x, ,x x, ,x x, ,x x 若若xmax1xmin2或者或者xmax2xmin1，線段和多邊，線段和多邊形表面就必然沒有遮擋關(guān)系。形表面就必然沒有遮擋關(guān)系。 yv方向也可以類似地做范圍檢查，可以避免方向也可以類似地做范圍檢查，可以避免消除隱藏面時很多不必要的深度比較。消除隱藏面時很多不必要的深度比較。 1718192021 如果不是上述兩種情況，必發(fā)生線如果不是上述兩種情況，必發(fā)生線段與表面相交。可以用求直線與平面交段與表面相交。可以用求直線與平

7、面交點的方法點的方法求出交點求出交點，顯然這時被交點分，顯然這時被交點分開而得到的兩條線段，恰好分別屬于前開而得到的兩條線段，恰好分別屬于前面說明的兩種情形。面說明的兩種情形。220DCzByAx直線直線l1 1的參數(shù)方程：的參數(shù)方程：x=x1，y=y1，z=z1+t，代入平面方程得：代入平面方程得： 0111Dt)C(zByAxCDCzByAxt111求交點求交點平面方程：平面方程：解得：解得：若若t0則則z1z1，若，若t0則則z1 z1。23 進(jìn)一步檢查進(jìn)一步檢查 這時要對平面遮擋了線段的哪些部分做精這時要對平面遮擋了線段的哪些部分做精確的計算。確的計算。24檢查出某一段子線段是否可見檢

8、查出某一段子線段是否可見 取子線段上任意一點，若這點在多邊形取子線段上任意一點，若這點在多邊形表面各邊線的投影所形成的封閉多邊形內(nèi)，表面各邊線的投影所形成的封閉多邊形內(nèi)，這子線段就不可見，否則就可見。這子線段就不可見，否則就可見。 25空間一條線段可能被一個多邊形表面遮擋的消除隱藏空間一條線段可能被一個多邊形表面遮擋的消除隱藏線的算法的步驟如下：線的算法的步驟如下： xv方向和方向和yv方向的方向的范圍檢查范圍檢查； 若不能判斷，則接著做若不能判斷，則接著做zv方向的范圍檢查即方向的范圍檢查即粗略的粗略的 深度比較深度比較； 若還不能判斷就再進(jìn)行若還不能判斷就再進(jìn)行精確的深度比較精確的深度比較

9、； 計算線段兩端點在可能遮擋它的平面上的計算線段兩端點在可能遮擋它的平面上的投影點投影點，比較相應(yīng)的比較相應(yīng)的z坐標(biāo)。這時可能出現(xiàn)線段與平面相交，坐標(biāo)。這時可能出現(xiàn)線段與平面相交，需要需要求交點求交點，交點把線段分成兩部分。，交點把線段分成兩部分。 對確實被平面遮擋的部分做精確計算，求出線段對確實被平面遮擋的部分做精確計算，求出線段的投影與遮擋平面上多邊形表面邊框投影的所有的投影與遮擋平面上多邊形表面邊框投影的所有交交點點，這些交點把線段的投影分成可見和不可見的一，這些交點把線段的投影分成可見和不可見的一些子線段。對些子線段。對子線段子線段的可見性，先取上面一點做點的可見性，先取上面一點做點的

10、的包含性包含性檢驗來進(jìn)行判斷。檢驗來進(jìn)行判斷。 26 考慮一條線段被考慮一條線段被多個多個多邊形表面遮擋而產(chǎn)多邊形表面遮擋而產(chǎn)生需要解決的消除隱藏線情況時，可依次判斷生需要解決的消除隱藏線情況時，可依次判斷被每個多邊形表面遮擋產(chǎn)生的隱藏部分。只要被每個多邊形表面遮擋產(chǎn)生的隱藏部分。只要被每一個多邊形都不能遮擋的公共部分才需要被每一個多邊形都不能遮擋的公共部分才需要顯示。顯示。27),(zxfy 曲面方程曲面方程constxxiconstzzi28290 , 3 , 2 , 10 ,hniiihzz 平面平面 是最靠近觀察者的，從平面是最靠近觀察者的，從平面 上的曲線上的曲線 開始，對水平方向每

11、個象開始，對水平方向每個象素的對應(yīng)素的對應(yīng)x坐標(biāo)值坐標(biāo)值 ，計算，計算nzz),(nzxfynzz浮動水平線方法：浮動水平線方法： 先考慮對應(yīng)先考慮對應(yīng) 的一族曲線的消隱算的一族曲線的消隱算法。如果圖形顯示器在水平方向有法。如果圖形顯示器在水平方向有M個像素，個像素，則建立則建立M個內(nèi)存單元個內(nèi)存單元yu(j) ，稱為上浮水平線數(shù)，稱為上浮水平線數(shù)組，在這些單元中先放上初值，初值應(yīng)取成小組，在這些單元中先放上初值，初值應(yīng)取成小于于 。 constzzi),(minzxfjx),(njjnzxfy30 對對 平面上的曲線完成上述工作后，平面上的曲線完成上述工作后，再對平面再對平面 上的曲線重復(fù)上

12、述工作，這上的曲線重復(fù)上述工作，這樣按樣按z值遞減方向一條一條曲線處理過去，就值遞減方向一條一條曲線處理過去，就得到一組消除隱藏線的曲線族了。得到一組消除隱藏線的曲線族了。 若若 ，則點，則點 是可見點，是可見點，并把并把 內(nèi)容換成內(nèi)容換成 。 若若 ，則，則 為不可見，就為不可見，就不改變不改變 的內(nèi)容的內(nèi)容。 )( jyyujn),(nzjnyjx)(jyujny)( jyu)( jyyujn),(njnjzyxnzz 1nzz31 圖圖c c點附近的線虛部分應(yīng)是可見的，但按上點附近的線虛部分應(yīng)是可見的，但按上述算法卻成了不可見了。為了解決這個問題，述算法卻成了不可見了。為了解決這個問題，

13、可另建立可另建立M M個單元個單元 ，可稱之為下浮水平線，可稱之為下浮水平線數(shù)組。數(shù)組。)( jylC32則則 為可見，并如下修改相應(yīng)的值為可見，并如下修改相應(yīng)的值 初值取成初值取成 或比這更大一或比這更大一點的數(shù)，每次求出點的數(shù)，每次求出 ),(maxzxf, 2 , 1 , 1 , 1, ),(jnnizxfyijji),( )(jlyjiyjuyjiy或若若),(izjiyjxjilljijiuujiyjyjyyyjyjyy)( then)( if)( then)( if33 如果函數(shù)如果函數(shù) 是用離散點形式是用離散點形式 給出，則可如下處理。給出，則可如下處理。這時的這時的 單元個數(shù)不

14、是由顯示器在單元個數(shù)不是由顯示器在x x方向方向的象素個數(shù)來定，而是根據(jù)給定的離散點在的象素個數(shù)來定，而是根據(jù)給定的離散點在x x方方向的個數(shù)來定。向的個數(shù)來定。 基本想法是用線性插值法所得直線來代替兩基本想法是用線性插值法所得直線來代替兩個點之間的曲線。個點之間的曲線。 ),(zxfy , 2 , 1, ),(kjizyxkii)(),(iyiyul34 若上述判斷結(jié)果為若上述判斷結(jié)果為 均為均為不可見，則認(rèn)為平面不可見，則認(rèn)為平面 上的從上的從 的一段曲線為不可見。若兩點均為可見，則用的一段曲線為不可見。若兩點均為可見，則用這兩點的連線代替原來這兩點之間的曲線，并這兩點的連線代替原來這兩點

15、之間的曲線，并認(rèn)為可見的，若這兩點中有一點可見，如圖的認(rèn)為可見的，若這兩點中有一點可見，如圖的A A點，另一點則為不可見，如圖中的點，另一點則為不可見，如圖中的B B點，這時要點，這時要求出求出ABAB連線和連線和CDCD連線的交點連線的交點E E。AEAE部分為可見，部分為可見，EBEB為不可見為不可見。),z,y(x）,z,y(xi,ijjijij11 和izz 1jixxxx至至35 一般用一般用 兩族曲線來表示兩族曲線來表示一曲面時常用斜投影。一曲面時常用斜投影。 ijzzxx 和和 為了得到消隱后曲面表示，不能對兩族曲為了得到消隱后曲面表示，不能對兩族曲線分別消隱再疊加在一起，正確的

16、做法是對兩線分別消隱再疊加在一起，正確的做法是對兩族曲線一起做，即處理好平面族曲線一起做，即處理好平面 上上 一段曲線后，馬上處理一段曲線后，馬上處理 平面上平面上 的一段曲線，的一段曲線，對這兩族曲線用公共的對這兩族曲線用公共的 和和 消隱消隱 。kxx iizzzz 1至izz kkxxxx 1至)(iyu)( jyl363738 算法的基本思想是按多邊形離觀察位置算法的基本思想是按多邊形離觀察位置的的距離距離進(jìn)行排序，然后按照進(jìn)行排序，然后按照距離減小距離減小的次序，的次序，把每個多邊形內(nèi)部點應(yīng)有的象素值送入幀緩把每個多邊形內(nèi)部點應(yīng)有的象素值送入幀緩存存貯器中。存存貯器中。 算法考查多邊

17、形的深度次序是在客體空算法考查多邊形的深度次序是在客體空間中進(jìn)行，圖形顯示時覆蓋步驟是在圖象空間中進(jìn)行，圖形顯示時覆蓋步驟是在圖象空間中實現(xiàn)，所以是一個間中實現(xiàn)，所以是一個客體空間和圖象空間客體空間和圖象空間的混合算法。的混合算法。3940不明確問題檢驗方法不明確問題檢驗方法 所有多邊形按頂點最大所有多邊形按頂點最大z坐標(biāo)值排序后得到坐標(biāo)值排序后得到一個排序表，設(shè)一個排序表，設(shè)P是排在表中最后的那個多邊是排在表中最后的那個多邊形。在把形。在把P掃描轉(zhuǎn)換送入更新緩沖存貯器中之掃描轉(zhuǎn)換送入更新緩沖存貯器中之前，必須對在前，必須對在z坐標(biāo)范圍與其發(fā)生交迭的每個多坐標(biāo)范圍與其發(fā)生交迭的每個多邊形進(jìn)行檢

18、查。邊形進(jìn)行檢查。 設(shè)設(shè)Q是排在是排在P前面并且前面并且z坐標(biāo)范坐標(biāo)范圍與其發(fā)生交迭的一個多邊形，對圍與其發(fā)生交迭的一個多邊形，對Q與與P的次序的次序關(guān)系進(jìn)行檢查。關(guān)系進(jìn)行檢查。 41 檢查可以按下面列出的五個步驟進(jìn)行，每檢查可以按下面列出的五個步驟進(jìn)行，每個步驟判斷一種情況。各步驟實現(xiàn)檢查的復(fù)雜個步驟判斷一種情況。各步驟實現(xiàn)檢查的復(fù)雜程度逐漸增加，只要某一個步驟成功，就可以程度逐漸增加，只要某一個步驟成功，就可以立即結(jié)束檢查。立即結(jié)束檢查。1.多邊形的多邊形的x坐標(biāo)范圍不相交迭，所以多邊形不坐標(biāo)范圍不相交迭，所以多邊形不相交迭。相交迭。2.多邊形的多邊形的y坐標(biāo)范圍不相交迭，所以多邊形不坐標(biāo)

19、范圍不相交迭，所以多邊形不相交迭。相交迭。3. P整個在整個在Q遠(yuǎn)離觀察點的一側(cè)。遠(yuǎn)離觀察點的一側(cè)。4. Q整個在整個在P的靠近觀察點的一側(cè)。的靠近觀察點的一側(cè)。5.多邊形在多邊形在z=0平面上的投影本身不相交迭。平面上的投影本身不相交迭。42圖圖7-13 第三步檢查為真第三步檢查為真圖圖7-14 第三步檢查為假，第三步檢查為假，第四步為真第四步為真PQ第五步檢查為真第五步檢查為真4344 如果所有這五步檢查都為假，就假定如果所有這五步檢查都為假，就假定P是遮擋了是遮擋了Q，交換交換P和和Q在排序表中的位置。重新進(jìn)行上述的五步檢在排序表中的位置。重新進(jìn)行上述的五步檢查。查。 如果仍做交換，算法

20、會永遠(yuǎn)循環(huán)下去而沒有結(jié)果。如果仍做交換，算法會永遠(yuǎn)循環(huán)下去而沒有結(jié)果。 為了避免循環(huán)，可以做一個限制。當(dāng)做過首次五為了避免循環(huán)，可以做一個限制。當(dāng)做過首次五步檢查后，發(fā)生某個多邊形被移到排序表的末尾時，步檢查后，發(fā)生某個多邊形被移到排序表的末尾時，就立即加上一個標(biāo)記，以后就不能再做移動。出現(xiàn)再就立即加上一個標(biāo)記，以后就不能再做移動。出現(xiàn)再次應(yīng)該移動時，次應(yīng)該移動時，用一個多邊形所在的平面，把另一個用一個多邊形所在的平面，把另一個多邊形剪裁分為兩個多邊形剪裁分為兩個。在對某個多邊形一分為二完成。在對某個多邊形一分為二完成后，把原來的多邊形舍棄，把得到的兩個新多邊形按后，把原來的多邊形舍棄，把得到

21、的兩個新多邊形按深度次序插入到原來的排序表中，然后就可以再開始深度次序插入到原來的排序表中，然后就可以再開始五步檢查，算法和以前一樣進(jìn)行下去。五步檢查，算法和以前一樣進(jìn)行下去。45PQ46 該算法可以應(yīng)用于對隱藏邊的消除。將更該算法可以應(yīng)用于對隱藏邊的消除。將更新緩沖器全部用某個象素值新緩沖器全部用某個象素值v0加以初始化，然加以初始化，然后每次對一個多邊形做掃描轉(zhuǎn)換時，都將其邊后每次對一個多邊形做掃描轉(zhuǎn)換時，都將其邊界置為需要的不同于界置為需要的不同于v0的某個象素值的某個象素值v1，將其，將其內(nèi)部置為原來的象素值內(nèi)部置為原來的象素值v0。這樣，先被掃描轉(zhuǎn)。這樣，先被掃描轉(zhuǎn)換的某個多邊形，如

22、果與后掃描轉(zhuǎn)換的某個新?lián)Q的某個多邊形，如果與后掃描轉(zhuǎn)換的某個新的多邊形發(fā)生交迭，原多邊形邊的被遮擋部分的多邊形發(fā)生交迭，原多邊形邊的被遮擋部分將被新多邊形填充的內(nèi)部值將被新多邊形填充的內(nèi)部值v0所湮沒，從而實所湮沒，從而實現(xiàn)了隱藏線的消除?，F(xiàn)了隱藏線的消除。47484981 0 01 1 01 1 11 0 10 0 00 1 00 1 10 0 161 2 3 42 6 7 36 5 8 75 1 4 84 3 7 85 6 2 150 程序中所使用的數(shù)據(jù)結(jié)構(gòu)包括：程序中所使用的數(shù)據(jù)結(jié)構(gòu)包括：點記錄點記錄(vertex)、面記錄、面記錄(patch)和排序數(shù)組。和排序數(shù)組。 點記錄由五個域構(gòu)

23、成：其中，三個域用于存點記錄由五個域構(gòu)成：其中，三個域用于存儲點的空間坐標(biāo)，另外兩個域用于存儲點的投儲點的空間坐標(biāo)，另外兩個域用于存儲點的投影（屏幕）坐標(biāo)。影（屏幕）坐標(biāo)。 面記錄由四個域組成，每個域存放對應(yīng)的頂面記錄由四個域組成，每個域存放對應(yīng)的頂點號。點號。 排序數(shù)組的每個元素有兩個域，其中一個域排序數(shù)組的每個元素有兩個域，其中一個域存放面與視點的距離，另一個域存放該面的面存放面與視點的距離，另一個域存放該面的面號。號。 51ReadkeyboardReadkeyboard：打開物體的邊界表示數(shù)據(jù)文：打開物體的邊界表示數(shù)據(jù)文件，從鍵盤讀進(jìn)旋轉(zhuǎn)角和透視角，物體表面件，從鍵盤讀進(jìn)旋轉(zhuǎn)角和透視角

24、，物體表面的顏色參數(shù)（色彩和飽和度），光源方向。的顏色參數(shù)（色彩和飽和度），光源方向。VerticesVertices：讀進(jìn)頂點的空間坐標(biāo)，計算物：讀進(jìn)頂點的空間坐標(biāo)，計算物體的包圍球半徑，把物體縮小到單位球中體的包圍球半徑，把物體縮小到單位球中去，計算物體各頂點在屏幕上的投影坐標(biāo)去，計算物體各頂點在屏幕上的投影坐標(biāo)。 開始開始52PatchesPatches：讀進(jìn)面定義數(shù)據(jù)，求出各面與視：讀進(jìn)面定義數(shù)據(jù)，求出各面與視點的距離，把面號與距離放進(jìn)排序數(shù)組。然點的距離，把面號與距離放進(jìn)排序數(shù)組。然后以面與視點的距離為參照值，對數(shù)組進(jìn)行后以面與視點的距離為參照值，對數(shù)組進(jìn)行排序。排序。GmodeGm

25、ode：使終端進(jìn)入圖形狀態(tài)，：使終端進(jìn)入圖形狀態(tài)，設(shè)備參數(shù)初始化設(shè)備參數(shù)初始化SetpenSetpen：建立查色表：建立查色表 53PaintingPainting：從排好序的數(shù)組中依次取出一面：從排好序的數(shù)組中依次取出一面號，計算對應(yīng)面的法向量，再計算該面的光號，計算對應(yīng)面的法向量，再計算該面的光強(qiáng)，然后顯示該面。強(qiáng)，然后顯示該面。 AmodeAmode：終端返回文字狀態(tài)。：終端返回文字狀態(tài)。結(jié)束結(jié)束54第五節(jié)第五節(jié) z 緩沖算法緩沖算法 z 緩沖算法緩沖算法(深度緩沖算法深度緩沖算法)是一種最簡單是一種最簡單的圖象空間算法。的圖象空間算法。 對每一個點，這個算法不僅需要有一個對每一個點，這

26、個算法不僅需要有一個更更新緩沖器新緩沖器存儲各點的象素值，而且還需要有一存儲各點的象素值，而且還需要有一個個z 緩沖存儲器緩沖存儲器存儲相應(yīng)的存儲相應(yīng)的z值。幀緩沖存儲值。幀緩沖存儲器初始化為背景值，器初始化為背景值，z緩沖存儲器初始化為可緩沖存儲器初始化為可以表示的最大以表示的最大z值。值。 對每一個多邊形，對每一個多邊形，不必不必進(jìn)行深度排序算法進(jìn)行深度排序算法要求的要求的初始排序初始排序，立即就可以逐個進(jìn)行掃描轉(zhuǎn)，立即就可以逐個進(jìn)行掃描轉(zhuǎn)換。換。55在掃描轉(zhuǎn)換時，對每個多邊形內(nèi)部的任意點在掃描轉(zhuǎn)換時，對每個多邊形內(nèi)部的任意點（x,y），實施如下步驟：），實施如下步驟：1.計算在點計算在點

27、(x,y)處多邊形的深度值處多邊形的深度值z(x,y)。2.如果計算所得的如果計算所得的z(x,y)值，小于在值，小于在z 緩沖存緩沖存儲器中點儲器中點 x y 處記錄的深度值，那么就做：處記錄的深度值，那么就做：1) 把值把值z x y 送入送入z 緩沖存儲器的點處。緩沖存儲器的點處。 2) 把多邊形在深度把多邊形在深度z(x y 處應(yīng)有的象素值，處應(yīng)有的象素值，送入更新緩沖存儲器的點送入更新緩沖存儲器的點 x y 處。處。 56 算法中算法中深度計算深度計算，可通過多邊形的頂點，可通過多邊形的頂點坐標(biāo)求出所在平面的方程，然后再使用平面坐標(biāo)求出所在平面的方程，然后再使用平面方程，對每個點方程

28、，對每個點 x x y y ，解出相應(yīng)的，解出相應(yīng)的z z。 平面方程平面方程 ， 解出解出 是：是： zCByAxDz0DCzByAx571zCByAxD則在點（則在點（x+x, y）處的深度值就是）處的深度值就是xCAzxCACByAxDCByx)A(xD1設(shè)在點（設(shè)在點（x, y）處的深度值是）處的深度值是z1:58z 緩沖算法的工作流程：緩沖算法的工作流程：幀緩沖區(qū)置成背景色；幀緩沖區(qū)置成背景色；z 緩沖區(qū)置成最緩沖區(qū)置成最大大z值；值；for (各個多邊形各個多邊形) 掃描轉(zhuǎn)換該多邊形；掃描轉(zhuǎn)換該多邊形； for(計算多邊形所覆蓋的每個象素（計算多邊形所覆蓋的每個象素（x,y）) 計

29、算多邊形在該象素的深度值計算多邊形在該象素的深度值Z(x,y)； if(Z(x,y)小于小于Z緩沖區(qū)中的緩沖區(qū)中的(x,y)處的值處的值) 把把Z(x,y)存入存入Z緩沖區(qū)中的緩沖區(qū)中的(x,y)處；處； 把多邊形在把多邊形在(x,y)處的亮度值存入幀緩處的亮度值存入幀緩 存區(qū)的存區(qū)的(x,y)處；處； 5960 首先首先建立一個建立一個邊表邊表ET。ET中各登記項按中各登記項按邊的較小的邊的較小的y坐標(biāo)遞增排列；每一登記項下的坐標(biāo)遞增排列；每一登記項下的“吊桶吊桶”，按所記，按所記x坐標(biāo)遞增排列。坐標(biāo)遞增排列。“吊桶吊桶”中各項的內(nèi)容依次是：中各項的內(nèi)容依次是：1. 與較小的與較小的y坐標(biāo)對

30、應(yīng)的端點的坐標(biāo)對應(yīng)的端點的x坐標(biāo)坐標(biāo)xmin。2. 邊的另一端點的較大的邊的另一端點的較大的y坐標(biāo)坐標(biāo)ymax。3. x的增量的增量x，它實際上是邊的斜率的倒數(shù)，它實際上是邊的斜率的倒數(shù)，是從一條掃描線走到下一條掃描線時，按是從一條掃描線走到下一條掃描線時，按x方方向遞增的步長。向遞增的步長。4. 邊所屬多邊形的標(biāo)記。邊所屬多邊形的標(biāo)記。 61ABCDEF兩個多邊形兩個多邊形在在z zv v=0=0平面平面上的投影上的投影 設(shè)有兩個空間的三角形設(shè)有兩個空間的三角形ABC、DEF,各頂點各頂點的坐標(biāo)依次是（的坐標(biāo)依次是（1,1,10）,（2,5,10）,（5,3,10）,（3,4,5）,（4,6

31、,5）,（6,2,5）。）。62兩個多邊形建立的兩個多邊形建立的“吊桶吊桶”已排序的邊表已排序的邊表 63還還需要一個需要一個多邊形表多邊形表PT(polygon Table)，其中，其中要包含下列信息：要包含下列信息： 每個多邊形所在平面方程的系數(shù)。在需要比每個多邊形所在平面方程的系數(shù)。在需要比較深度時，要通過所在（較深度時，要通過所在（x,y），根據(jù)平面方程），根據(jù)平面方程解出深度解出深度z。 每個多邊形的亮度或顏色值。實際做掃描轉(zhuǎn)每個多邊形的亮度或顏色值。實際做掃描轉(zhuǎn)換時應(yīng)用。換時應(yīng)用。 一個一個“進(jìn)入進(jìn)入退出退出”標(biāo)志，初值為標(biāo)志，初值為“假假”。在。在掃描轉(zhuǎn)換處理時，用以標(biāo)記掃描線對

32、該多邊形掃描轉(zhuǎn)換處理時，用以標(biāo)記掃描線對該多邊形是是“進(jìn)入進(jìn)入”，還是，還是“退出退出”。 64操作通過一個活動邊表操作通過一個活動邊表AET進(jìn)行。進(jìn)行。 65 通過以上的討論，可以寫出整個掃描線算通過以上的討論，可以寫出整個掃描線算法實施的步驟：法實施的步驟： 首先首先正確形成邊表正確形成邊表ET和多邊形表和多邊形表PT之后，之后，然后然后實施步驟與第二章敘述的多邊形填充的掃實施步驟與第二章敘述的多邊形填充的掃描線算法的實施步驟基本相同，只是需要把那描線算法的實施步驟基本相同，只是需要把那里的步驟：里的步驟：在掃描線在掃描線y上，按照上，按照AET表提供的表提供的x坐標(biāo)對，用坐標(biāo)對，用col

33、or實施填充修改加細(xì)如下：實施填充修改加細(xì)如下： 6667686970i is s P PPTPT表表FABC FDEFFABC FDEF 說明說明1 11 1(ABC)(ABC)true 1 1 到到3 3填填A(yù)BCABC的亮度或顏色值的亮度或顏色值 2 22 2(DEF,(DEF, ABC)ABC) true在步驟在步驟3 3發(fā)生深度比較，比較結(jié)果發(fā)生深度比較，比較結(jié)果DEFDEF更靠近觀察者，它仍在更靠近觀察者，它仍在P P表前面，表前面，3 3到到3 3 填填DEFDEF的亮度或顏色值的亮度或顏色值3 31 1(DEF)(DEF)false 3 3 到到5 5填填DEFDEF的亮度或顏

34、色值的亮度或顏色值4 40 0( )( ) false 2 21 14 43 32 21 17172三個多邊形三個多邊形 73 事實上前面給出的算法基本步驟沒有很好事實上前面給出的算法基本步驟沒有很好地利用深度的相關(guān)性。深度相關(guān)性是指多個多地利用深度的相關(guān)性。深度相關(guān)性是指多個多邊形之間的深度關(guān)系，常常對于一組相鄰的掃邊形之間的深度關(guān)系，常常對于一組相鄰的掃描線來說是不變化的。如果在某條掃描線上，描線來說是不變化的。如果在某條掃描線上，在在AET表中保存的邊及次序關(guān)系，與在前面一表中保存的邊及次序關(guān)系，與在前面一條掃描線上時完全相同，那么深度關(guān)系就不會條掃描線上時完全相同，那么深度關(guān)系就不會變化，深