一種新的線(xiàn)框模型自動(dòng)隱藏線(xiàn)算法

蔣曙

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

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

中圖分類(lèi)號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）12-0130-01

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

1 可見(jiàn)面判別算法

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

2 線(xiàn)框可見(jiàn)算法

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

3 算法實(shí)現(xiàn)

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

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

立體幾何教學(xué)軟件中的圖形都是線(xiàn)框模型，所以實(shí)際渲染繪圖時(shí)，主要繪制頂點(diǎn)、線(xiàn)段，具體過(guò)程為先判斷所有邊的可見(jiàn)性，然后用實(shí)線(xiàn)畫(huà)出可見(jiàn)的邊，用虛線(xiàn)畫(huà)出不可見(jiàn)的邊，畫(huà)出頂點(diǎn)，就得到了所需要的立體圖形。

3.2 算法主要流程

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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