一種新的線框模型自動隱藏線算法

蔣曙

摘要：為了解決立體幾何教學軟件中不可見線段的虛線消隱問題，筆者設(shè)計了一種新的線框模型自動隱藏線算法：找出立體幾何圖形中所有線段與面的交點，以及線段與線段在投影平面中的交點，并用這些交點重新分解現(xiàn)有線段，然后再用后向面判別法判斷新線段的可見性。經(jīng)測試證明，此算法完全能實現(xiàn)立體幾何圖形中不可見線段的虛線消隱。

關(guān)鍵詞：線消隱 算法 立體幾何

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1007-9416（2016）12-0130-01

在生成真實感圖形時，考慮最多的是如何判斷從某一個選定的觀察位置所能看到的場景中的內(nèi)容。所謂消隱，是為了獲得更好的視覺效果，往往會把不在視線范圍的部分（隱藏面或隱藏線）進行消除或以其他方式顯示，它包含隱藏面消除和隱藏線消除。在三維造型技術(shù)、真實感圖形的顯示、慮擬場景的顯示、以及在地形、地圖的繪制中，消隱都起到至關(guān)重要的作用。所以研究和實現(xiàn)消隱算法，并根據(jù)場景的復雜度和各個不同應用領(lǐng)域的場景來提高消隱算法的速度是很有必要的，它對整個三維圖形顯示、真實感圖形的顯示以及各種地形地貌圖形的顯示是很有意義的。

1 可見面判別算法

根據(jù)其處理場景時是直接處理對象定義還是處理它們的投影圖像，隱藏面消除算法分為物空間（object-space）算法和像空間（image-space）算法。物空間算法將場景中的各對象和對象的各個組成部件相互進行比較，從而最終判別出哪些面是可見的，常見的物空間算法有后向面判別算法、BSP樹算法、深度排序算法、光線投射算法。像空間算法是在平面投影平面上逐點判斷各像素所對應的可見面。常見的像空間算法有深度緩存算法（也叫z緩沖器算法）、A緩存算法、掃描線算法、區(qū)域細分算法和八叉樹算法。

2 線框可見算法

我們常常為了快速顯示對象特征而僅用輪廓線形式顯示三維場景，生成場景線框圖最快的方法是顯示對象所有的邊。然而，在這樣的顯示中很難確定對象的前后特征。一種解決辦法是應用可見性測試，將隱藏線消除或使用與可見面不同的方式進行顯示。常用的可見線判別算法主要是由可見面判別算法移植過來，或者由圖形程序接口（如OpenGL）來實現(xiàn)。但是在一些場合下，如果使用上述方式實現(xiàn)可見線判別算法，工作量太大。筆者在開發(fā)立體幾何教學軟件時，就遇到了這樣的問題。為了解決問題，設(shè)計了一套簡單易用的可見線判別算法。其主要原理是將所有邊按照一定規(guī)則分解成一些子邊，然后判斷這些子邊與所有的面之間的位置關(guān)系僅為在平面前、后和平面上三種關(guān)系，從而實現(xiàn)了邊的可見性判斷，并以虛線的方式進行消隱。

3 算法實現(xiàn)

3.1 基本數(shù)據(jù)結(jié)構(gòu)

本算法是為了解決立體幾何圖形的線消隱問題，在整個算法過程中主要涉及了構(gòu)造立體幾何圖形所必須的三個幾何元素：點、邊、面，所以，最基本的數(shù)據(jù)結(jié)構(gòu)也就是點（Point）、線（Edge）、面（Face）和有前面三項構(gòu)成幾何體（Solid），具體如表1-2所示。

立體幾何教學軟件中的圖形都是線框模型，所以實際渲染繪圖時，主要繪制頂點、線段，具體過程為先判斷所有邊的可見性，然后用實線畫出可見的邊，用虛線畫出不可見的邊，畫出頂點，就得到了所需要的立體圖形。

3.2 算法主要流程

第一步：找出邊和面的內(nèi)交點。找出所有邊與面的內(nèi)交點，所謂內(nèi)交點指的是邊與面的交點，且交點位于邊的內(nèi)部，而不在邊的端點或者延長線上的交點。如圖1所示，邊EF與面ABCD相交于點G，且點G在邊EF內(nèi)，所以點G是邊EF的一個內(nèi)交點。

實現(xiàn)方法及要點：（1）必須用投影變換之前的坐標，也就是P_Init或P_View。（2）根據(jù)邊的兩個端點P_Strat（xs，ys，zs）和P_End（xe，ye，ze），建立直線參數(shù)方程

第二步：找出所有邊與邊的內(nèi)交點。邊與邊的內(nèi)交點是指在投影變換之后，根據(jù)所有邊的在投影平面上的關(guān)系，判斷邊與邊是否存在交點，且交點在邊的內(nèi)部。如圖2所示，在三維空間中，邊EF與邊CD是沒有交點的，但是在投影平面上，邊EF與邊CD有一個內(nèi)交點I，同樣，邊EF與邊AB有一個內(nèi)交點H。

實現(xiàn)方法及要點：（1）必須用投影變換之后的坐標，也就是P_Pro。（2）每次求兩邊交點時，兩邊參數(shù)方程可以表示為：

第三步：根據(jù)內(nèi)交點劃分子邊。將第一步和第二步中得到的內(nèi)交點和邊原來的兩個端點重新劃分邊，如圖2所示，邊EF有3個內(nèi)交點，因此將邊EF分解成邊EH、邊HG、邊GI和邊IF，一共4條新邊。實現(xiàn)方法及要點：把點坐標代入直線參數(shù)方程，求出參數(shù)，然后根據(jù)參數(shù)t的大小排序，得到所有內(nèi)交點之間的順序關(guān)系。

第四步：判斷所有子邊與面的位置關(guān)系。經(jīng)過第三步重新劃分后的邊與面之間的位置關(guān)系有三種：在平面上、在平面后面、在平面前面。其中，只有在平面前面的這種情況，表明該邊是可見的。

實現(xiàn)方法及要點：（1）判斷邊與面位置關(guān)系時，面的一般方程中的參數(shù)A、B、C、D必須嚴格使用從前往后觀察平面時逆時針順序排列的點坐標計算。解決方法為：任意選擇面上的三個頂點、、，如果，則這三點是逆時針順序，否則調(diào)整三點順序為、、。計算向量和的叉積，其結(jié)果的三個分量就是平面方程的參數(shù)A、B、C，并和其中一個點坐標代入求出。（2）將邊的兩端點坐標代入，當至少有一個端點代入計算的結(jié)果大于0時，表示這個線段不被改平面遮擋，即可見。（3）有時邊處在兩個平面之間，造成可見性結(jié)果沖突的情況，這時只要遍歷所有的面，并且邊的每一次可見性標判斷結(jié)果與之前的結(jié)果進行邏輯與運算即可解決。

4 結(jié)語

本算法可以用于各種平臺，不依賴于硬件和圖形庫函數(shù)，用各種計算機語言實現(xiàn)也比較簡單，筆者用C#結(jié)合OpenGL編程實現(xiàn)了該算法，并且制作了測試程序，其動態(tài)虛線消隱的效果完全滿足要求。同時，該算法不僅適用于封閉的凸多面體，也適用于不封閉的情況。對于凹多邊形情況，只需修改第四步中平面參數(shù)求解方式就可解決。

參考文獻

[1]彭群生，金小剛，萬華根，馮結(jié)青，編著.計算機圖形學應用基礎(chǔ)[M].北京：科學出版社，2009.

[2]D.F.羅杰斯著，梁友棟等譯.計算機圖形學的算法基礎(chǔ)[M].科學出版社，1984.