宋人杰，張加玲，李曉棟

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

0 引 言

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

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

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

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

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

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

（1）單凸面體的消隱

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

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

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

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

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

（2）多個凸面體的消隱

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

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

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

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

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

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

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

圖1 凸多面體的表面模型

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

表1 面表

表2 棱邊表

2.2 包圍盒測試

所謂包圍盒，即能包含該邊的面積最小的矩形，該矩形的四條邊界線段分別平行于坐標(biāo)軸x和y。如果兩條邊的包圍盒不相交也不包含，是分離的關(guān)系，那么這兩條邊必定沒有交點?？梢酝瞥觯鼑胁幌嘟灰膊话膬蓷l線段就不用進行交點計算［7］，這樣就可以排除一部分沒有必要進行求交點運算的線段。

如果滿足

或

則兩條邊的包圍盒相交。

如果滿足

或

則兩條邊的包圍盒包含。

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

不滿足以上條件的包圍盒不相交也不包含，也就是說線段之間不相交也不包含，所以說它們之間肯定沒有交點，線段之間的交點計算就可以省略，從而減少計算時間。

2.3 深度排序（最大最小測試［8］）

所謂深度排序，即當(dāng)兩個面重疊的時候，確定哪一個面遮擋另一個面，此時選擇視點的方向為Z軸方向。

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

2.4 兩個面之間各條邊之間的測試

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

圖2 線段可見性分析

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

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

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

2.5 結(jié)果分析

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

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

3 結(jié)束語

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

［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）.［毛峽，沈巍，趙興圓.基于點線關(guān)系的透視圖消隱算法 ［J］.北京航空航天大學(xué)學(xué)報，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）.［常明，李丹，羅年猛.計算機圖形學(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］.計算機與數(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é)軟件中的一個線消隱算法 ［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］.計算機工程與應(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）.［劉勇奎.計算機圖形學(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）.［肖子楓，韓冀中，賀勁，等.平面線段相交問題的漸縮規(guī)整包圍盒過濾規(guī)則［J］.計 算 機 輔 助 設(shè) 計 與 圖 形 學(xué) 學(xué) 報，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）.［袁超.多個凹凸形多面體的深度優(yōu)先消隱算法研究 ［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è)高等?？茖W(xué)報，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.計算機圖形學(xué)的算法基礎(chǔ) ［M］.北京：機械工業(yè)出版社，2002：235－263.］

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

［12］SHI Jiaoying.Virtual reality basis and practical algorithm［M］.Beijing：Science press，2002（in Chinese）.［石教英.虛擬現(xiàn)實基礎(chǔ)及實用算法 ［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］.計算機工程與應(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］.計算機應(yīng)用，2010，30（3）：620－624.］