凸多面體線消隱算法的研究與改進(jìn)

宋人杰，張加玲，李曉棟

（東北電力大學(xué) 信息工程學(xué)院，吉林 吉林132012）

0 引 言

所謂消隱，是把場(chǎng)景中的視點(diǎn)虛擬成人眼，將物體被遮擋的線段或者是面隱藏起來(lái)不顯示，只顯示從視點(diǎn)出發(fā)的視線能看到的部分，來(lái)真實(shí)的生成人眼看到的場(chǎng)景。三維立體造型使觀察者看到更完整的物體，真實(shí)感圖形使人們更加直觀、形象的認(rèn)識(shí)和了解地理、工程信息，這些信息廣泛應(yīng)用在仿真模擬、幾何造型、指揮控制、科學(xué)計(jì)算的可視化等領(lǐng)域［1］。不消除物體自身遮擋或相互遮擋而無(wú)法看見(jiàn)的線條，顯示的線條將雜亂無(wú)章，三維圖形也將失去立體感，進(jìn)而就會(huì)產(chǎn)生二義性［2，10－11］。為了使展示的圖形具有理想的三維顯示效果，消除物體的隱藏線和隱藏面成為必須解決的問(wèn)題。

現(xiàn)今的線消隱算法通常需要很大的存儲(chǔ)空間或者要經(jīng)過(guò)非常復(fù)雜的步驟，求交的計(jì)算量大，使得消隱的代價(jià)大或者導(dǎo)致消隱效率低，為解決這一問(wèn)題，本文提出改進(jìn)的消隱算法來(lái)彌補(bǔ)傳統(tǒng)算法的不足。

1 傳統(tǒng)線消隱算法的缺點(diǎn)及實(shí)現(xiàn)

Roberts算法是最早幾個(gè)公開(kāi)發(fā)表的隱藏線消除算法之一，它在對(duì)象空間中實(shí)現(xiàn)。采用此算法將首先消除被物體自身遮擋的邊和面，即所謂的自隱藏線和自隱藏面［3］。處理多個(gè)凸面體的消隱時(shí)，傳統(tǒng)的算法要使每個(gè)物體留下的邊或面與剩余的物體一一比較，以確定邊或面上哪些部分被遮擋，如果場(chǎng)景中的凸多面體個(gè)數(shù)比較多時(shí)，會(huì)使算法的工作量隨著場(chǎng)景中物體數(shù)量的平方遞增，消隱時(shí)間會(huì)隨之增加，使得效率大大降低。

傳統(tǒng)算法實(shí)現(xiàn)過(guò)程

簡(jiǎn)單的三維場(chǎng)景只包含一個(gè)凸面體，單個(gè)凸多面體的消隱只需要檢查每個(gè)面的可見(jiàn)性，建立可見(jiàn)邊表，通過(guò)面的可見(jiàn)性進(jìn)而可以推導(dǎo)出線段的可見(jiàn)性；復(fù)雜場(chǎng)景中的凸面體的個(gè)數(shù)會(huì)比較多，其消隱算法因物體之間的相互遮擋而變得較為復(fù)雜，除了對(duì)每個(gè)面進(jìn)行可見(jiàn)性判斷，還要進(jìn)行線段的分段處理，以判斷線段的哪一部分被遮擋，涉及到大量的交點(diǎn)計(jì)算。本文分以下兩個(gè)方面進(jìn)行介紹。

（1）單凸面體的消隱

如果場(chǎng)景中只有一個(gè)凸面體，不存在多個(gè)凸面體之間的相互遮擋，具體算法如下：

1）計(jì)算各個(gè)凸面體平面方程Ax＋By＋Cz＋D＝0的方程系數(shù)［3］。

2）利用后向面判別法判別隱藏面的可見(jiàn)性，設(shè)多邊形法矢量為N（A，B，C），設(shè)V為由視點(diǎn)出發(fā)的觀察矢量，取V＝（0，0，－1），此時(shí)是從觀察視點(diǎn)向坐標(biāo)原點(diǎn)看去的方向，若V·N＜0，則該面為隱藏面［2］。

假設(shè)三維空間中存在一點(diǎn)P（x，y，z），若Ax＋By＋Cz＋D＜0，則該點(diǎn)P在多邊形表面的內(nèi)側(cè)，此點(diǎn)稱(chēng)為內(nèi)點(diǎn)［3，13］。如果內(nèi)點(diǎn)位于視點(diǎn)和多邊形表面之間，則該表面必為后向面。若V·N＜0，說(shuō)明夾角為鈍角，即N的方向與Z軸負(fù)方向一致，所以可判斷該表面為隱藏面。

3）物體中的所有自隱藏面被確定以后，根據(jù)兩個(gè)自隱藏面的交線必為隱藏線的原則，即可將單凸多面體中隱藏面和隱藏線都確定出來(lái)［4］。

（2）多個(gè)凸面體的消隱

傳統(tǒng)的線消隱算法在實(shí)現(xiàn)多個(gè)凸面體的消隱時(shí)，首先利用（1）中的原理消隱圖形中的自隱藏面和自隱藏線，由于多個(gè)凸多面體之間存在相互遮擋，被遮擋的部分不一定是整一條線段，可能僅僅是一條線段其中的一段或者兩段［5］，所以下一步的工作是將當(dāng)前檢測(cè)物體留下的邊或面與其他物體的邊進(jìn)行一一比較，以確定邊或面上哪些部分被遮擋，需要求交的工作量非常大。

由以上算法可以看出，在處理凸多面體的消隱算法中，單個(gè)凸多面體的消隱算法比較簡(jiǎn)單，實(shí)際上就是消除物體被自身遮擋的線段和面。如果場(chǎng)景中的凸多面體較多時(shí)，就會(huì)花費(fèi)很大的時(shí)間處理面與面之間、線段與線段之間的求交運(yùn)算；事實(shí)上，求交運(yùn)算的準(zhǔn)確性和效率直接影響整個(gè)算法的結(jié)果。按照上面的算法，一方面，有很多本來(lái)就不相交的線段也需要進(jìn)行求交運(yùn)算，無(wú)形中增加了計(jì)算量；另一方面，在進(jìn)行求交運(yùn)算時(shí)，求交線段的先后順序也很重要，如果從視點(diǎn)的由近及遠(yuǎn)的方向選擇線段進(jìn)行求交時(shí)，會(huì)導(dǎo)致線段的重復(fù)求交，也會(huì)增加計(jì)算量。

2 改進(jìn)的線消隱算法設(shè)計(jì)思想及實(shí)現(xiàn)

基于傳統(tǒng)的線消隱算法的不足，提出改進(jìn)的線消隱算法，首先給算法一個(gè)恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，其次在處理多個(gè)凸多面體的實(shí)際情況中，平面中與某特定的邊存在交點(diǎn)的邊一般情況下只有幾條，而沒(méi)有必要把所有的邊都納入到求交的范圍內(nèi)。算法中加入包圍盒的最大最小測(cè)試做一個(gè)預(yù)判斷，以及將傳統(tǒng)的線消隱算法與畫(huà)家算法中的深度優(yōu)先排序結(jié)合起來(lái)。使用最大最小測(cè)試使得本來(lái)沒(méi)有遮擋關(guān)系的物體首先排除，以減少算法的計(jì)算量，提高消隱效率。使用深度排序，使得首先進(jìn)行消隱的是離視點(diǎn)最遠(yuǎn)的物體，由此減少隱藏邊的后續(xù)求交運(yùn)算的次數(shù)，避免重復(fù)。

2.1 數(shù)據(jù)結(jié)構(gòu)

選擇適合的數(shù)據(jù)結(jié)構(gòu)不但可以使物體的結(jié)構(gòu)更清晰明了，而且可以大大簡(jiǎn)化算法的運(yùn)算，降低運(yùn)算復(fù)雜度。從幾何形態(tài)上完善地描述一個(gè)物體，所用的數(shù)據(jù)結(jié)構(gòu)一般是兩組相互聯(lián)系而又相互獨(dú)立的信息，即幾何信息和拓?fù)湫畔ⅲ?］。幾何信息是指組成物體的點(diǎn)、線、面的大小、位置、形狀等信息；在此模型中，頂點(diǎn)二維數(shù)組中存儲(chǔ)幾何信息；拓?fù)湫畔⒅傅氖墙M成物體的點(diǎn)、線、面之間的連接關(guān)系，本文中的面表和邊表存放拓?fù)湫畔ⅰ?/p>

本算法采用以下表結(jié)構(gòu)：面表F、邊表L、頂點(diǎn)表V以及可見(jiàn)邊表?？梢?jiàn)邊表的用途為：當(dāng)檢測(cè)出一條可見(jiàn)邊以后，就和可見(jiàn)邊表中的數(shù)據(jù)進(jìn)行核對(duì)，如果表中沒(méi)有此邊，則將此邊加入此表。各頂點(diǎn)坐標(biāo)用齊次坐標(biāo)給出，存入V ［i，j］二維頂點(diǎn)表中，此時(shí)的頂點(diǎn)表用二維數(shù)組的形式存放。面表F中存放面號(hào)、起始邊、頂點(diǎn)個(gè)數(shù)等信息，其中屬性是指面的可見(jiàn)性標(biāo)志。邊鏈表L中存放邊號(hào)，其中的編號(hào)要保證統(tǒng)一使用統(tǒng)一順序存儲(chǔ)，逆時(shí)針或者順時(shí)針都可以，以鏈表形式存放。由于面表和頂點(diǎn)表中進(jìn)行查找、插入、刪除的次數(shù)比較多，使用相對(duì)比較頻繁，所以也用鏈表存放，這種安排占用較小的存儲(chǔ)空間，可以減少內(nèi)存的占用量。通過(guò)表L和F可以得到所有邊的兩端點(diǎn)編號(hào)以及每個(gè)面所有的頂點(diǎn)的編號(hào)。如圖1所示。

圖1 凸多面體的表面模型

通過(guò)凸多面體的表面模型圖，可以得到如下的面與邊，以及邊與點(diǎn)的關(guān)系表，如表1和表2所示。

表1 面表

表2 棱邊表

2.2 包圍盒測(cè)試

所謂包圍盒，即能包含該邊的面積最小的矩形，該矩形的四條邊界線段分別平行于坐標(biāo)軸x和y。如果兩條邊的包圍盒不相交也不包含，是分離的關(guān)系，那么這兩條邊必定沒(méi)有交點(diǎn)?？梢酝瞥?，包圍盒不相交也不包含的兩條線段就不用進(jìn)行交點(diǎn)計(jì)算［7］，這樣就可以排除一部分沒(méi)有必要進(jìn)行求交點(diǎn)運(yùn)算的線段。

如果滿足

或

則兩條邊的包圍盒相交。

如果滿足

或

則兩條邊的包圍盒包含。

其中X代表的是包圍盒的X方向的坐標(biāo)，Minx代表X方向的最小坐標(biāo)值，MaxX代表X方向的最大坐標(biāo)值，同樣，Y代表的是包圍盒的Y方向的坐標(biāo)，MinY代表Y方向的最小坐標(biāo)值，MaxY代表Y方向的最大坐標(biāo)值。

不滿足以上條件的包圍盒不相交也不包含，也就是說(shuō)線段之間不相交也不包含，所以說(shuō)它們之間肯定沒(méi)有交點(diǎn)，線段之間的交點(diǎn)計(jì)算就可以省略，從而減少計(jì)算時(shí)間。

2.3 深度排序（最大最小測(cè)試［8］）

所謂深度排序，即當(dāng)兩個(gè)面重疊的時(shí)候，確定哪一個(gè)面遮擋另一個(gè)面，此時(shí)選擇視點(diǎn)的方向?yàn)閆軸方向。

進(jìn)行深度排序的目的在于減少后續(xù)的線段之間的求交運(yùn)算，主要步驟可以分為以下：①對(duì)多邊形進(jìn)行排序，排序的順序?yàn)椋合却_定每個(gè)頂點(diǎn)的最大和最小的X，Y，Z方向的坐標(biāo)。將每一個(gè)頂點(diǎn)的Zmax按照從小到大的順序進(jìn)行排序，挑出最小的Zmax，也就是離視點(diǎn)最遠(yuǎn)的物體。按照Z(yǔ)max的遞增順序?qū)Χ噙呅芜M(jìn)行排序。②按照視點(diǎn)的方向，由遠(yuǎn)及近取面，與和它有深度重疊的面進(jìn)行測(cè)試，若不重疊，則不需要修改次序，如果重疊，就要進(jìn)行進(jìn)一步的深度測(cè)試。③如果一個(gè)面的所有點(diǎn)的Zmax都比另一個(gè)面的大或是小，就需要按次序排列。④綜合包圍盒的最大最小測(cè)試，由此找出被隱藏的邊，此時(shí)隱藏邊就被篩選出來(lái)，下一步確定這條隱藏邊上的具體哪一段被隱藏。

2.4 兩個(gè)面之間各條邊之間的測(cè)試

（1）利用線段的參數(shù)方程：L（t）＝S＋dt，其中L（t）是線段上對(duì)應(yīng)參數(shù)t的點(diǎn)的位置矢量，S是線段的起點(diǎn)，d為線段的矢量方向［3］。由此得出t的取值范圍為t∈［0，1］。如圖2所示，E為視點(diǎn)方向，L（t）為被測(cè)線段，在場(chǎng)景中，一條線段并不是全部可見(jiàn)，根據(jù)是否可見(jiàn)，L（t）可能會(huì)被分為幾段，L（t1）、L（t2）、L（t3）等等。

圖2 線段可見(jiàn)性分析

（2）當(dāng)t的值確定以后，也就是線段的分界點(diǎn)就找到了，此分界點(diǎn)分的線段其中一段可能是可見(jiàn)的，另一段可能是不可見(jiàn)的，下一步就可以構(gòu)造一條從觀察點(diǎn)出發(fā)到L（t）上一點(diǎn)V的線段，設(shè)EV＝V＋eu，其中V是此線段的起始點(diǎn)，也是線段L（t）上由t引發(fā)的分界點(diǎn)，e為線段EV的方向向量，由于被檢測(cè)的線段是離視點(diǎn)最遠(yuǎn)的面的一條邊，所以可以得出u∈ ［0，＋∞］，即此物體只可能被前面的邊或者面擋住。由此得出：EV＝V＋eu＝S＋dt＋eu，設(shè)物體的體矩陣為T(mén)，令P＝S＊T，Q＝d＊T，R＝e＊T，若有hj＝pj＋Qj＋uRj，其中j為體矩陣T中列的下標(biāo)，若rj＜＝0、pj＜＝0且pj＋Qj＜＝0都符合，則這段線段完全可見(jiàn)［9］。在空間中當(dāng)t、u兩個(gè)值都確定了以后，就確定了EV線段上的一個(gè)點(diǎn)，如果此點(diǎn)在物體內(nèi)部，屬于內(nèi)點(diǎn)的話，說(shuō)明此時(shí)被測(cè)線段被遮擋了，所以只要求出所有的內(nèi)點(diǎn)，所求點(diǎn)對(duì)應(yīng)的t值就是待檢測(cè)線段部分被遮擋而出現(xiàn)的分界點(diǎn)。這樣就可以推斷出如圖2所示的L（t3）就是被遮擋的線段。

（3）邊的求交過(guò)程如下：設(shè)被測(cè)線段為L(zhǎng)（t），L（t）應(yīng)該與所有的非自隱藏面進(jìn)行求交運(yùn)算，由于t、u確定的是一個(gè)平面，設(shè)為P（t，u），若平面P（t，u）與任何一個(gè)待求的平面有交點(diǎn)，P（t，u）與各平面系數(shù)的點(diǎn)積大于零，即說(shuō)明此時(shí)待測(cè)的線段L（t）被遮擋，將場(chǎng)景中存在的所有的面都檢查一遍，加入條件t∈ ［0，1］以及u∈［0，＋∞］就可以求出所有滿足條件的t和u的值，由此得出線段的哪一部分被遮擋，計(jì)算完成以后，將對(duì)應(yīng)的可見(jiàn)和不可見(jiàn)標(biāo)志分別存入數(shù)據(jù)結(jié)構(gòu)中，然后換另一條線段作檢測(cè)；如果計(jì)算滿足t的條件不存在的時(shí)候，此時(shí)說(shuō)明此線沒(méi)有遮擋段，是完全可見(jiàn)的，然后換下一條線段繼續(xù)計(jì)算。以此類(lèi)推，完成所有的線段檢測(cè)。

當(dāng)把所有的線段都檢測(cè)完以后，所有線段的屬性都可以通過(guò)查相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的可見(jiàn)邊表得知，使被隱藏的線段或者面都不能顯示在場(chǎng)景中，其他的面和線段顯示在場(chǎng)景中，此時(shí)整個(gè)算法就結(jié)束了。

2.5 結(jié)果分析

本算法通過(guò)C＋＋編程實(shí)現(xiàn)場(chǎng)景中三維物體的線消隱，通過(guò)變化多面體的數(shù)目來(lái)實(shí)際測(cè)試消隱需要的時(shí)間。以下是傳統(tǒng)算法和改進(jìn)算法的時(shí)間對(duì)比圖，如圖3所示。其中 ‘o’所在曲線代表的是傳統(tǒng)算法消隱所需時(shí)間與邊數(shù)的關(guān)系圖，從圖中可以看出，所需時(shí)間與邊數(shù)呈現(xiàn)n2的關(guān)系，‘＋’所在直線表示的是改進(jìn)后的算法消隱所需時(shí)間與邊數(shù)的關(guān)系，基本上與n呈線性關(guān)系。不難看出，隨著邊數(shù)的增長(zhǎng)，改進(jìn)的消隱算法能有效減少消隱時(shí)間，進(jìn)而提高效率。

圖3 改進(jìn)算法與傳統(tǒng)算法的消隱時(shí)間隨邊數(shù)變化關(guān)系

3 結(jié)束語(yǔ)

本算法在實(shí)現(xiàn)過(guò)程中的難點(diǎn)集中在求交運(yùn)算中。對(duì)邊與凸多面體進(jìn)行求交運(yùn)算時(shí)，此時(shí)的棱邊可能已經(jīng)被分為好幾段，有的段是可見(jiàn)的，有的段是不可見(jiàn)的，進(jìn)行可見(jiàn)性的判斷就是本算法的主要計(jì)算量，在加入包圍盒的最大最小測(cè)試和深度優(yōu)先排序以后，本來(lái)沒(méi)有相交的線段被排除掉，這樣就大大減少了計(jì)算量，節(jié)省了消隱時(shí)間，實(shí)驗(yàn)表明，改進(jìn)的算法使時(shí)間復(fù)雜度幾乎與場(chǎng)景中的物體個(gè)數(shù)呈線性增長(zhǎng)，由此可以得出，場(chǎng)景中的三維形體越多，改進(jìn)的算法也能顯現(xiàn)出其優(yōu)勢(shì)。

［1］MAO Xia，SHEN Wei，ZHAO Xingyuan.Hidden－removal method of perspective drawing based on constrains between lines and junctions ［J］.Journal of Beijing University of Aeronautics and Astronautics，2009，35（8）：925－928（in Chinese）.［毛峽，沈巍，趙興圓.基于點(diǎn)線關(guān)系的透視圖消隱算法 ［J］.北京航空航天大學(xué)學(xué)報(bào)，2009，35（8）：925－928.］

［2］CHANG Ming，LI Dan，LUO Nianmeng.Compututer graphics：Algorithm and practice ［M］.Wuhan：The Press of Huazhong University of Science and Technology，2009：233－264（in Chinese）.［常明，李丹，羅年猛.計(jì)算機(jī)圖形學(xué)算法與應(yīng)用 ［M］.武漢：華中科技大學(xué)出版社，2009：233－264.］

［3］JIN Hailiang，GAO Jingxiang.A summary of algorithms for removing the hidden lines and surfaces ［J］.Computer ＆ Digital Engineering，2006，34（9）：27－31（in Chinese）.［靳海亮，高井祥，圖形消隱算法綜述 ［J］.計(jì)算機(jī)與數(shù)字工程2006，34（9）：27－31.］

［4］CHEN Rui，TANG Ningjiu，LIN Tao，et al.Hidden line removal algorithm in solid geometry teaching software ［J］.Application Research of Computers，2009，26（12）：4833－4835（in Chinese）.［陳銳，唐寧九，林濤，等.立體幾何教學(xué)軟件中的一個(gè)線消隱算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（12）：4833－4835.］

［5］PAN Shaoming.The research of projection decomposition and elimination algorithm based on bounded and directed graphic elements［J］.Computer Engineering and Applications，2004，40（2）：75－77（in Chinese）.［潘少明.基于有界有向圖形元素的投影分解法消隱算法的研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（2）：75－77.］

［6］LIU Yongkui.The basic algorithm of computer graphics ［M］.Beijing：Science Press，2007：125－129（in Chinese）.［劉勇奎.計(jì)算機(jī)圖形學(xué)的基礎(chǔ)算法 ［M］.北京：科學(xué)出版社，2007：125－129.］

［7］XIAO Zifeng，HAN Jizhong，HE Jin，et al.Shrinking regular bounding box filter for line segment intersection problem ［J］.Journal of Computer－Aided Design ＆Computer Graphics，2008，20（10）：1345－1352（in Chinese）.［肖子楓，韓冀中，賀勁，等.平面線段相交問(wèn)題的漸縮規(guī)整包圍盒過(guò)濾規(guī)則［J］.計(jì) 算 機(jī) 輔 助 設(shè) 計(jì) 與 圖 形 學(xué) 學(xué) 報(bào)，2008，20（10）：1345－1352.］

［8］YUAN Chao.Research on the depth order hidden algorithm for multiple concavo－convex polyhedrons ［J］.Computer Engineering ＆Science，2006，28（9）：97－102（in Chinese）.［袁超.多個(gè)凹凸形多面體的深度優(yōu)先消隱算法研究 ［J］.計(jì)算機(jī)工程與科學(xué)，2006，28（9）：97－102.］

［9］LI Ruo.A research of quickly elimination algorithm for the convex polyhendron ［J］.Journal of Guilin College of Aerospace Thchnology，2006，11（2）：18－20（in Chinese）.［李若.凸多面體的一種快速消隱算法的研究 ［J］.桂林航天工業(yè)高等專(zhuān)科學(xué)報(bào)，2006，11（2）：18－20.］

［10］DAVID FR.The basic of computer algorithm graphics ［M］.Beijing：Machinery Industry Press，2002：235－263（in Chinese）.［JAMESDF.計(jì)算機(jī)圖形學(xué)的算法基礎(chǔ) ［M］.北京：機(jī)械工業(yè)出版社，2002：235－263.］

［11］JAMESDF.The principles and practice in computer graphics［M］.Beijing：Machinery Industry Press，2002：316－343（in Chinese）.［JAMESDF.計(jì)算機(jī)圖形學(xué)的原理及實(shí)踐 ［M］.北京：機(jī)械工業(yè)出版社，2002：316－343.］

［12］SHI Jiaoying.Virtual reality basis and practical algorithm［M］.Beijing：Science press，2002（in Chinese）.［石教英.虛擬現(xiàn)實(shí)基礎(chǔ)及實(shí)用算法 ［M］.北京：科學(xué)出版社，2002.］

［13］MA Ziping，MA Jinglin.Comparison among several hidden surface removal algorithms ［J］.Science and Technology Information，2008，22（2）：69－71（in Chinese）.［馬自萍，馬金林，幾種面消隱算法的比較 ［J］.科技信息，2008，22（2）：69－71.］

［14］SHENG Bin，LI Dong，XU Xuegan.An improvement to Z－buffer hidden surface removal algorithm ［J］.Computer Engineering and Applications，2001，37（23）：114－116（in Chinese）. ［生濱，李東，徐學(xué)敢.Z緩沖區(qū)消隱算法的改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2001，37（23）：114－116.］

［15］ZHAO Jun，GAO Mantun，WANG Sanmin.Hidden line removal for wire frame projection drawing ［J］.Journal of Computer Applications，2010，30（3）：620－624（in Chinese）.［趙軍，高滿屯，王三民.線框模型投影圖的消隱 ［J］.計(jì)算機(jī)應(yīng)用，2010，30（3）：620－624.］