基于射線法的凹多面體消隱算法研究與實現

摘要： 為了在計算機中得到空間圖形的立體感顯示效果，只能在輸出界面顯示空間圖形中朝向觀察者的表面，而其余部分則不被顯示。空間立體可采用多邊形建模。簡單凸多面體的求解較容易，但凹多面體的求解則相對困難。在此利用圖形學中的平移、旋轉、正平行投影、深度緩存消隱算法、射線法等相關理論，結合可視化的MFC開發平臺，研究并實現了一個凹多面體表面的全方位觀察，對進一步研究消隱算法及射線法的改進具有較好的參考作用。

關鍵詞： 平行投影； 消隱算法； 射線法； 凹多面體

中圖分類號： TN919?34； TP391文獻標識碼： A文章編號： 1004?373X（2014）08?0129?03

Research and implementation of ray method based blanking algorithm for concave polyhedron

WEI Hong?chun

（Department of Computer Science， Sichuan University of Arts and Science， Dazhou 635000， China）

Abstract： In order to display three?dimensional graphics in the computer， only the surfaces of objects toward the observer are showed in the output interface， but the rests are not displayed. The three?dimensional model can be established by polygon. Its easy to solve simple convex polyhedron， but the concave polyhedron is not. In combinstion with visual MFC development platform， the all?round observation about the concave polyhedron is studied and implemented by using the theories of translation， rotation and parallel projection， depth buffer blanking algorithm， and ray method in graphics. It's a good reference to further research the improvements of blanking algorithm and ray method.

Keywords： paralell projection； blanking algorithm； ray method； concave polyhedron

0引言

在觀察不透明物體時，只能看到物體朝向觀察者的表面。當用計算機生成具有立體感的圖形時，利用消隱算法可以得到一個確定的、立體感強的投影圖。隱線、隱面消除算法與排序算法相關。排序的依據是被顯示的點、線、面或體與觀察點之間的幾何距離。對于簡單的凸多面體，可利用平面法線向量與視線向量的關系快速求解，但對于凹多面體，其求解算法較凸多面體復雜得多。本文利用射線法的深度緩存消隱算法和正平行投影的相關理論，研究并實現了一個凹多面體在鍵盤控制下的全方位顯示，對進一步研究消隱算法及射線法的改進具有較好的參考。

1基本理論

在計算機中，復雜立體可以借助三角形、四邊形等平面多邊形完成建模，若要生成具有立體感的圖形，須借助三維圖形變換中相關算法，包括平移、旋轉、縮放、投影、消隱等。但凹多面體僅這些理論還不夠，必須運用計算幾何中的其他相關知識，如角度和或射線法判斷一個點是否在一個平面多邊形內，快速排斥與交叉跨立判斷兩條線段是否相交等。相關算法理論的簡介如下。

1.1消隱方法

（l） 背面消除算法

背面消除算法是隱藏面消除算法中的關鍵部分。在消隱問題中，最簡單的問題是單個凸多面體。此時，利用背面消除即可達到隱面消除的目的。為了確定凸多面體的不可見面，對于每個面進行如下操作：

① 求平面法向量n；

② 求平面的視線向量v；

③ 計算v·n；

④ 根據v·n符號判別該面是否可見。

（2） 深度緩存Z?buffer消隱算法

深度緩存（Z?buffer）是在圖像空間下的消隱算法，包括：幀緩沖器（保存各像素顏色值CB）和z緩沖器zBuffer（保存各像素處物體深度值ZB）。其中z 緩沖器中的單元與幀緩沖器中的單元一一對應。

算法思想：首先用給定深度值初始化z 緩沖器。當改變某個像素的顏色時，先檢查當前像素點的深度值是否大于該像素原來的深度值，若大于，說明當前像素點更靠近觀察點，則用當前色替換像素原來的顏色；否則說明當前像素點不可見，像素的顏色值不改變。Z?buffer 算法的實現步驟如下：

① 初始化ZB和CB，使ZB（i，j）=Zmax，CB（i，j）=背景色。其中，i=1，2，…,m，j=1，2，…，n。

② 對某個多邊形，計算它在點（i，j）處的深度值zi，j。

③ 若zij

④ 對每個多邊形重復②，③兩步后，在CB中存放的就是消隱后的圖形[1?2]。

1.2射線法判斷點與平面多邊形的位置

利用射線法判斷一個平面點M是否位于一個多邊形內部的原理如下：

從點M向左作水平射線，若M在多邊形內部，則該射線與多邊形的交點為奇數；若M在多邊形外部，則交點個數必為偶數（包含0個）。順序考慮多邊形的每條邊，便可求出該射線與各邊交點的總數。

對于平面多邊形的某條邊PQ的特殊情況處理：

（1） 若射線穿過頂點P或Q，則會重復計數。處理規則是如果穿過的頂點縱坐標是PQ中較小的則忽略。

（2） 如果PQ為水平線段，則有可能與射線“重合”。處理規則是P點要么在PQ上，要么不在。只需在開始判斷一下是否在PQ上[3?5]。

2算法設計與實現

在VC 6.0開發平臺下，新建一基于MFC的單文檔的名為CWhc3DTransform工程，在視圖類中添加按鍵響應函數OnKeyDown（）、判斷點是否位于位于多邊形內的函數PointInPolygon（）。完成凹多面體深度緩存消隱算法的詳細設計如下：

int zBuffer[MAXNUM][MAXNUM]；//深度緩存，外部數組

int cBuffer[MAXNUM][MAXNUM]；//顏色緩存，外部數組

CWhc3DTransformView（）

{//在構造函數中完成凹多邊體相關數據的初始化

初始化顏色緩存與對應像素點的深度緩存

初始化凹多面體的各個頂點坐標

初始化凹多面體各個面的顏色

初始化多面體的總面數FN = 8（共8個面）

初始化faceInfo [ ][ ]。//第二維是面編號，faceInfo[i][0]是該面的頂點數，

// faceInfo[i][j]（j>0）是構成該面的頂點序列

用立體各頂點坐標初始化變換后的立體中心到原點的坐標分量

初始化變換后的立方體的坐標分量

將變換后的立方體平移到指定位置

初始化立方體相對于其起始狀態的各坐標軸的旋轉角

初始化立方體的最大包圍盒

}

voidOnDraw（CDC* pDC）{ /*根據在OnKeyDown（）中完成的消隱算法，重新繪制該立體*/

設置背景為白色

用給定顏色繪制立體深度緩存中的像素點

}

voidOnKeyDown（UINT nChar， UINT nRepCnt， UINT nFlags） {//完成指定的變換及消隱

初始化顏色緩存與對應點的深度緩存

用多面體的原始頂點坐標初始化數組resultP

double real_per_degree = 3.1415926/180； //每度所對應的弧度數

計算在鍵盤相應鍵控制下，初始狀態立方體分別繞坐標軸x，y，z旋轉后的角度

生成繞z軸變化的變換陣并計算變換后的頂點坐標

生成繞x軸變化的變換陣并計算變換后的頂點坐標

生成繞y軸變化的變換陣并計算變換后的頂點坐標

將變換后的幾何體平移到指定的位置，以方便顯示

double zzbufer；//根據（x，y）計算該面上 （x，y）處的z坐標。

重置立方體的最大包圍盒為初始值

重新計算立方體的最大包圍盒，即最小的（xmin，ymin）和最大的（xmax，ymax）

While（若點（i，j）在最大包圍盒中）{

for（k=0；k<總面數FN；k++）{//遍歷每個面，面中的第0號元素記錄了構成該面的頂點數

if（若（i，j）位于某個面k中）{//點（i，j）在第k個面內

根據該面k的法線向量的z分量

if（若法線向量的z分量> 0）{ /*z>0，該面可見，計算zzbufer坐標*/根據（i，j）計算該面上該點的zzbufer分量，即（i，j，zzbufer）

if（zzbufer > zBuffer[i][j]）

{ /*若（i，j）點處的z坐標>該點處的深度*/

zBuffer[i][j] = （int）zzbufer； //更換（i，j）處的深度值

cBuffer[i][j] = faceColor[k]；//更新顏色緩存（i，j）中的顏色值

}}}} }

RedrawWindow（）；

}

intPointInPolygon（int faceK，double xCoord， double yCoord）{//判斷點與多邊形的位置關系

/* 從第faceK面上的點（xCoord， yCoord）向左產生一條射線，記錄與交點相交的個數counter*/

獲取構成第faceK面的頂點數并保存在pointNum中

初始化交點個數counter = 0；

將第faceK面中各頂點轉存到數組vertemp

for（i=0；i

p=第i點，q=第（（i+1）% pointNum）點

若點（xCoord， yCoord）在線段pq上，則return 1；

若線段pq是水平的，則continue；

//若處于相交線段的端點，取y坐標大的以避免重復計數

若射線穿過的頂點縱坐標是PQ中較大的，

則counter++；

若射線穿過的頂點縱坐標是QP中較大的，

則counter++；

若（利用快速排斥與交叉跨立實驗判斷當yCoord不是線段兩端點，且線段pq與射線相交時）

counter++；

}

return （counter % 2）； //返回交點的個數是否為奇數

}

通過以上算法，給定的凹多面體可在鍵盤的上下左右鍵、Insert鍵、Delete鍵的控制下，完成在各種狀態下的消隱顯示[6]。運算結果如圖1~圖3所示（部分狀態下的顯示截圖）。

圖1 初始狀態的消隱

3結語

在計算機中，獲得物體的具有立體感的顯示效果是一個較復雜的過程，涉及的算法較多，且人們對消隱算法的研究還在繼續，以期獲取更好顯示效果。本文利用平行投影算法、基于射線法的深度緩存消隱算法研究并實現了一個凹多面體的立體顯示過程，可以全方位地觀察物體在各種位置的消隱狀態，獲得了較好的演示效果，并且能容易地將此算法改為詳細的實現代碼，對進一步研究射線法、消隱算法的改進具有較好的參考作用。

圖2 施行變換后的消隱（1）

圖3 施行變換后的消隱（2）

參考文獻

[1] 王汝傳，黃海平，林巧民.計算機圖形學教程[M].2版.北京：人民郵電出版社，2009.

[2] 和青芳.計算機圖形學原理及算法教程（Visual C++版）[M].

2版.北京：清華大學出版社，2010.

[3] 陳瑞卿，周健，虞烈.一種判斷點與多邊形關系的快速算法[J].西安交通大學學報，2007，41（1）：59?63.

[4] 馬晨，張毅.一種改進的點與多邊形關系的叉乘判別法[J].測繪科學，2013，38（1）：125?127.

[5] 李楠，肖克炎.一種改進的點在多邊形內外判斷算法[J].計算機工程，2012，38（5）：30?34.

[6] 衛洪春，彭小利.掃描線多邊形區域填充算法研究[J].四川文理學院學報，2012，22（5）：77?82.

[7] 李雪，石產田.一種三角形內外點的快速判定方法[J].現代電子技術，2008，31（4）：110?112.

[8] 夏俊杰，趙剛.基于MFC的代碼編輯器設計方法[J].現代電子技術，2012，35（12）：28?30.

// faceInfo[i][j]（j>0）是構成該面的頂點序列

用立體各頂點坐標初始化變換后的立體中心到原點的坐標分量

初始化變換后的立方體的坐標分量

將變換后的立方體平移到指定位置

初始化立方體相對于其起始狀態的各坐標軸的旋轉角

初始化立方體的最大包圍盒

}

voidOnDraw（CDC* pDC）{ /*根據在OnKeyDown（）中完成的消隱算法，重新繪制該立體*/

設置背景為白色

用給定顏色繪制立體深度緩存中的像素點

}

voidOnKeyDown（UINT nChar， UINT nRepCnt， UINT nFlags） {//完成指定的變換及消隱

初始化顏色緩存與對應點的深度緩存

用多面體的原始頂點坐標初始化數組resultP

double real_per_degree = 3.1415926/180； //每度所對應的弧度數

計算在鍵盤相應鍵控制下，初始狀態立方體分別繞坐標軸x，y，z旋轉后的角度

生成繞z軸變化的變換陣并計算變換后的頂點坐標

生成繞x軸變化的變換陣并計算變換后的頂點坐標

生成繞y軸變化的變換陣并計算變換后的頂點坐標

將變換后的幾何體平移到指定的位置，以方便顯示

double zzbufer；//根據（x，y）計算該面上 （x，y）處的z坐標。

重置立方體的最大包圍盒為初始值

重新計算立方體的最大包圍盒，即最小的（xmin，ymin）和最大的（xmax，ymax）

While（若點（i，j）在最大包圍盒中）{

for（k=0；k<總面數FN；k++）{//遍歷每個面，面中的第0號元素記錄了構成該面的頂點數

if（若（i，j）位于某個面k中）{//點（i，j）在第k個面內

根據該面k的法線向量的z分量

if（若法線向量的z分量> 0）{ /*z>0，該面可見，計算zzbufer坐標*/根據（i，j）計算該面上該點的zzbufer分量，即（i，j，zzbufer）

if（zzbufer > zBuffer[i][j]）

{ /*若（i，j）點處的z坐標>該點處的深度*/

zBuffer[i][j] = （int）zzbufer； //更換（i，j）處的深度值

cBuffer[i][j] = faceColor[k]；//更新顏色緩存（i，j）中的顏色值

}}}} }

RedrawWindow（）；

}

intPointInPolygon（int faceK，double xCoord， double yCoord）{//判斷點與多邊形的位置關系

/* 從第faceK面上的點（xCoord， yCoord）向左產生一條射線，記錄與交點相交的個數counter*/

獲取構成第faceK面的頂點數并保存在pointNum中

初始化交點個數counter = 0；

將第faceK面中各頂點轉存到數組vertemp

for（i=0；i

p=第i點，q=第（（i+1）% pointNum）點

若點（xCoord， yCoord）在線段pq上，則return 1；

若線段pq是水平的，則continue；

//若處于相交線段的端點，取y坐標大的以避免重復計數

若射線穿過的頂點縱坐標是PQ中較大的，

則counter++；

若射線穿過的頂點縱坐標是QP中較大的，

則counter++；

若（利用快速排斥與交叉跨立實驗判斷當yCoord不是線段兩端點，且線段pq與射線相交時）

counter++；

}

return （counter % 2）； //返回交點的個數是否為奇數

}

通過以上算法，給定的凹多面體可在鍵盤的上下左右鍵、Insert鍵、Delete鍵的控制下，完成在各種狀態下的消隱顯示[6]。運算結果如圖1~圖3所示（部分狀態下的顯示截圖）。

圖1 初始狀態的消隱

3結語

在計算機中，獲得物體的具有立體感的顯示效果是一個較復雜的過程，涉及的算法較多，且人們對消隱算法的研究還在繼續，以期獲取更好顯示效果。本文利用平行投影算法、基于射線法的深度緩存消隱算法研究并實現了一個凹多面體的立體顯示過程，可以全方位地觀察物體在各種位置的消隱狀態，獲得了較好的演示效果，并且能容易地將此算法改為詳細的實現代碼，對進一步研究射線法、消隱算法的改進具有較好的參考作用。

圖2 施行變換后的消隱（1）

圖3 施行變換后的消隱（2）

參考文獻

[1] 王汝傳，黃海平，林巧民.計算機圖形學教程[M].2版.北京：人民郵電出版社，2009.

[2] 和青芳.計算機圖形學原理及算法教程（Visual C++版）[M].

2版.北京：清華大學出版社，2010.

[3] 陳瑞卿，周健，虞烈.一種判斷點與多邊形關系的快速算法[J].西安交通大學學報，2007，41（1）：59?63.

[4] 馬晨，張毅.一種改進的點與多邊形關系的叉乘判別法[J].測繪科學，2013，38（1）：125?127.

[5] 李楠，肖克炎.一種改進的點在多邊形內外判斷算法[J].計算機工程，2012，38（5）：30?34.

[6] 衛洪春，彭小利.掃描線多邊形區域填充算法研究[J].四川文理學院學報，2012，22（5）：77?82.

[7] 李雪，石產田.一種三角形內外點的快速判定方法[J].現代電子技術，2008，31（4）：110?112.

[8] 夏俊杰，趙剛.基于MFC的代碼編輯器設計方法[J].現代電子技術，2012，35（12）：28?30.

// faceInfo[i][j]（j>0）是構成該面的頂點序列

用立體各頂點坐標初始化變換后的立體中心到原點的坐標分量

初始化變換后的立方體的坐標分量

將變換后的立方體平移到指定位置

初始化立方體相對于其起始狀態的各坐標軸的旋轉角

初始化立方體的最大包圍盒

}

voidOnDraw（CDC* pDC）{ /*根據在OnKeyDown（）中完成的消隱算法，重新繪制該立體*/

設置背景為白色

用給定顏色繪制立體深度緩存中的像素點

}

voidOnKeyDown（UINT nChar， UINT nRepCnt， UINT nFlags） {//完成指定的變換及消隱

初始化顏色緩存與對應點的深度緩存

用多面體的原始頂點坐標初始化數組resultP

double real_per_degree = 3.1415926/180； //每度所對應的弧度數

計算在鍵盤相應鍵控制下，初始狀態立方體分別繞坐標軸x，y，z旋轉后的角度

生成繞z軸變化的變換陣并計算變換后的頂點坐標

生成繞x軸變化的變換陣并計算變換后的頂點坐標

生成繞y軸變化的變換陣并計算變換后的頂點坐標

將變換后的幾何體平移到指定的位置，以方便顯示

double zzbufer；//根據（x，y）計算該面上 （x，y）處的z坐標。

重置立方體的最大包圍盒為初始值

重新計算立方體的最大包圍盒，即最小的（xmin，ymin）和最大的（xmax，ymax）

While（若點（i，j）在最大包圍盒中）{

for（k=0；k<總面數FN；k++）{//遍歷每個面，面中的第0號元素記錄了構成該面的頂點數

if（若（i，j）位于某個面k中）{//點（i，j）在第k個面內

根據該面k的法線向量的z分量

if（若法線向量的z分量> 0）{ /*z>0，該面可見，計算zzbufer坐標*/根據（i，j）計算該面上該點的zzbufer分量，即（i，j，zzbufer）

if（zzbufer > zBuffer[i][j]）

{ /*若（i，j）點處的z坐標>該點處的深度*/

zBuffer[i][j] = （int）zzbufer； //更換（i，j）處的深度值

cBuffer[i][j] = faceColor[k]；//更新顏色緩存（i，j）中的顏色值

}}}} }

RedrawWindow（）；

}

intPointInPolygon（int faceK，double xCoord， double yCoord）{//判斷點與多邊形的位置關系

/* 從第faceK面上的點（xCoord， yCoord）向左產生一條射線，記錄與交點相交的個數counter*/

獲取構成第faceK面的頂點數并保存在pointNum中

初始化交點個數counter = 0；

將第faceK面中各頂點轉存到數組vertemp

for（i=0；i

p=第i點，q=第（（i+1）% pointNum）點

若點（xCoord， yCoord）在線段pq上，則return 1；

若線段pq是水平的，則continue；

//若處于相交線段的端點，取y坐標大的以避免重復計數

若射線穿過的頂點縱坐標是PQ中較大的，

則counter++；

若射線穿過的頂點縱坐標是QP中較大的，

則counter++；

若（利用快速排斥與交叉跨立實驗判斷當yCoord不是線段兩端點，且線段pq與射線相交時）

counter++；

}

return （counter % 2）； //返回交點的個數是否為奇數

}

通過以上算法，給定的凹多面體可在鍵盤的上下左右鍵、Insert鍵、Delete鍵的控制下，完成在各種狀態下的消隱顯示[6]。運算結果如圖1~圖3所示（部分狀態下的顯示截圖）。

圖1 初始狀態的消隱

3結語

在計算機中，獲得物體的具有立體感的顯示效果是一個較復雜的過程，涉及的算法較多，且人們對消隱算法的研究還在繼續，以期獲取更好顯示效果。本文利用平行投影算法、基于射線法的深度緩存消隱算法研究并實現了一個凹多面體的立體顯示過程，可以全方位地觀察物體在各種位置的消隱狀態，獲得了較好的演示效果，并且能容易地將此算法改為詳細的實現代碼，對進一步研究射線法、消隱算法的改進具有較好的參考作用。

圖2 施行變換后的消隱（1）

圖3 施行變換后的消隱（2）

參考文獻

[1] 王汝傳，黃海平，林巧民.計算機圖形學教程[M].2版.北京：人民郵電出版社，2009.

[2] 和青芳.計算機圖形學原理及算法教程（Visual C++版）[M].

2版.北京：清華大學出版社，2010.

[3] 陳瑞卿，周健，虞烈.一種判斷點與多邊形關系的快速算法[J].西安交通大學學報，2007，41（1）：59?63.

[4] 馬晨，張毅.一種改進的點與多邊形關系的叉乘判別法[J].測繪科學，2013，38（1）：125?127.

[5] 李楠，肖克炎.一種改進的點在多邊形內外判斷算法[J].計算機工程，2012，38（5）：30?34.

[6] 衛洪春，彭小利.掃描線多邊形區域填充算法研究[J].四川文理學院學報，2012，22（5）：77?82.

[7] 李雪，石產田.一種三角形內外點的快速判定方法[J].現代電子技術，2008，31（4）：110?112.

[8] 夏俊杰，趙剛.基于MFC的代碼編輯器設計方法[J].現代電子技術，2012，35（12）：28?30.