章志兵，楊明潤，王麗榮，陳有芳

（1.華中科技大學，武漢 430074；2.中國船級社技術(shù)研究中心，北京 100007）

船舶艙室識別是船舶設(shè)計的關(guān)鍵環(huán)節(jié)，是船舶有限元分析（CAE）和船舶結(jié)構(gòu)性能校核（Structure Design Program, SDP）的基礎(chǔ)[1—2]，因此，提高艙室識別效率和準確性，增強識別過程的自動性，對于船舶設(shè)計具有重大意義。

針對艙室識別問題，國內(nèi)外學者研究提出了眾多典型解決方案。單威俊等[3—5]提出了“切分拼接”方法，首先利用自由邊過濾艙室內(nèi)部結(jié)構(gòu)，再根據(jù)船舶相交結(jié)構(gòu)的特征，定義一系列規(guī)則，將模型切分成一塊塊艙室面，最后將艙室面拼接成艙室空間。該方法具有較高的自動性，但對船舶特征依賴性強，對于不同類型的船舶，需要定義不同的識別規(guī)則，并且經(jīng)實驗驗證，識別準確率僅能達到60%，需要大量的人工干預(yù)，才可做到準確識別全船的艙室，并且識別效率不高，以大型油船、散貨船為例，識別船體中單個艙室即需要耗費5 min。LEE S U等[6]采用自頂向下方法，利用分割面，進行布爾運算，將整個船體模型逐步切分，直至識別出所有艙室。該方法識別準確率高，但屬于半自動方法，需要人工干預(yù)操作。在4萬t的大型船舶上進行實驗，表明該船體識別出所有艙室模型，需耗費約1 h。KONINGH D等[7]提出一種新的模型切分方法，混合使用體與平面來劃分船體模型，簡化了艙室建模過程，提高了艙室識別準確率，但自動化程度不高，需要人工進行圖形交互操作，導(dǎo)致效率難以有突破性提高。

文中利用一種新思路，將艙室抽象識別為三維模型中的封閉空間，基于半邊半面模型，定義了封閉空間的方向。以此為基礎(chǔ)，提出了時間復(fù)雜度O(n)（n為模型中半面的數(shù)量）的半面擴展算法，利用模型拓撲關(guān)系和空間坐標數(shù)值計算，可高效識別出種子半面所屬的極小封閉空間。在半面擴展算法基礎(chǔ)上，實現(xiàn)了高效的艙室自動識別算法。

1 半邊半面模型

CHEN H，LI Guang-ming，DANOVARO E 等[8—13]的研究表明，半邊數(shù)據(jù)結(jié)構(gòu)在三維模型的網(wǎng)格簡化、模型切割方面具有良好的性能表現(xiàn)，并且易于拓展成緊湊性數(shù)據(jù)結(jié)構(gòu)，在大規(guī)模模型處理中可節(jié)省較多的存儲空間。DYEDOV V，RAY N等[14—16]的研究表明，半面數(shù)據(jù)結(jié)構(gòu)在網(wǎng)格面細化、曲面重構(gòu)方面具有良好的性能表現(xiàn)。為了提高艙室識別算法的可拓展性，在該算法中使用半邊半面數(shù)據(jù)結(jié)構(gòu)來表示幾何元素，使該算法將來可融合于多種功能模塊中。

一條無向邊可拆分為兩條方向相反的有向邊。將有向邊稱為半邊（Half-edge）。同一條無向邊拆分成的兩條方向相反的半邊互為伴隨半邊（Accompany half edge）。

如圖1所示，無向邊e被拆分為Eh0和Eh1兩條有向邊，Eh0和Eh1互為伴隨半邊。無向邊e具有兩個端點v0和v1。半邊Eh0的起點為v0，終點為v1；半邊Eh1的起點為v1，終點為v0。

在半邊模型基礎(chǔ)上，可將一個無向面拆分為兩個方向相反的有向面，有向面的方向根據(jù)組成該面的半邊方向由右手定則確定。將有向面稱為半面（Half-face）。同一個無向面拆分成的兩個方向相反的有向面互為伴隨半面（Accompany half face）。若半邊Eh參與構(gòu)成半面Fh，則稱半面Fh包含半邊Eh、半邊Eh屬于半面Fh。

圖1 半邊定義Fig.1 Definition of half-edge

如圖2所示，無向面f被拆分為Fh0和Fh1兩個有向面（為了圖示清晰性，無向面f未在圖中畫出），F(xiàn)h0和Fh1互為伴隨半面。半邊Eh0，Eh2，Eh4，Eh6構(gòu)成半面Fh0，屬于半面Fh0。半邊Eh1，Eh3，Eh5，Eh7構(gòu)成半面Fh1，屬于半面Fh1。半面Fh0，F(xiàn)h1的方向根據(jù)半邊方向由右手定則確定。

圖2 半面定義Fig.2 Definition of half-face

張奇華等基于拓撲學原理，提出了“有向性”和“封閉性”的概念[17]。在此基礎(chǔ)上，結(jié)合半邊半面模型，將封閉空間定義為由一組有向面圍成的封閉區(qū)域，其中每個有向面的方向都指向該封閉區(qū)域內(nèi)部。該定義相較于使用無向面定義封閉空間，具有以下優(yōu)點：①提供了一種統(tǒng)一的封閉空間特征，可利用該特征，設(shè)計更簡潔高效的封閉空間識別算法；② 使得相鄰的封閉空間之間不再存在公共面，使所有的封閉空間相互獨立，從設(shè)計上降低數(shù)據(jù)結(jié)構(gòu)耦合；③ 利用組成封閉空間的有向面的方向，易于判斷一個三維空間坐標是否處于封閉空間內(nèi)部，提高算法可擴展性。

2 CAE船舶艙室自動識別算法

艙室識別算法總流程如圖3所示。

Step 1：獲取模型的所有face及face包含的edge元素。

Step 2：建立CAE模型的拓撲關(guān)系，并創(chuàng)建半邊半面數(shù)據(jù)結(jié)構(gòu)存儲拓撲關(guān)系。

Step 3：取一個尚未被訪問的半面作為種子半面；若不存在未被訪問的種子半面，則結(jié)束。

Step 4：識別種子半面所屬的極小封閉空間。使用半面擴展算法，以種子半面為始，向相鄰半面擴展，并遞歸執(zhí)行該過程，識別出所有屬于該封閉空間的半面。

Step 5：存儲識別結(jié)果。以一個新的半面數(shù)組存儲表示該封閉空間?；氐?Step3，遞歸地執(zhí)行艙室識別過程。

Step 6：采用半自動方式剔除船體外部空間。程序標識出半面數(shù)量最多的一個極小封閉空間，用戶可確認該空間為船體外部空間；或用戶手動點選船體外殼上的一個半面，程序識別出該半面所屬的極小封閉空間，標識為船體外部空間。

圖3 艙室識別算法總流程Fig.3 Flow of cabin identify algorithm

2.1 CAE模型拓撲關(guān)系建立

船舶艙室是由一組面組成的封閉空間區(qū)域，封閉空間的邊界面構(gòu)成流形拓撲，因此要求在艙室識別過程中，能夠通過給定的面獲取其邊界線，并通過邊界線獲取其連接的面，即給定的面相鄰的面。

在船舶CAE模型中，曲線段已被離散為分段的直線段，曲面已被離散為空間2D單元[18]，可將空間2D單元視為face，則艙室為由一組face組成的封閉空間區(qū)域。

在文中艙室識別算法中，需要建立的拓撲關(guān)系有：半面與半邊的包含關(guān)系；半邊與半邊的伴隨關(guān)系。

如圖4所示，半面Fh0包含半邊Eh0，Eh1，Eh2，Eh3；半面Fh1包含半邊Eh4，Eh5，Eh6，Eh7；半邊Eh1與Eh5互為伴隨半邊，并由此可推斷出半面Fh0與半面Fh1相鄰。

對于模型中每個空間 2D單元表示的無向小平面，創(chuàng)建兩個方向相反的有向半面，并創(chuàng)建每個半面包含的半邊。

圖4 CAE模型拓撲關(guān)系示意圖Fig.4 Diagram of CAE model topology relationship

為了建立半邊的伴隨關(guān)系，對每個半邊的起點和終點構(gòu)成的二元組（Star point，end point）進行編碼，使得二元組（Star point，end point）的編碼與二元組（End point，star point）的編碼互為相反數(shù)，并且所有編碼均不為 0。使用 Hash表進行存儲，以二元組編碼作為 Key，以半邊數(shù)組作為 Value。創(chuàng)建每個半邊時，設(shè)該半邊的編碼為x，則將該半邊加入Key為x對應(yīng)的Value半邊數(shù)組中，并在Hash表中查詢半邊編碼為?x的半邊，記錄半邊伴隨關(guān)系。

2.2 半面擴展算法

半面擴展算法用于識別三維模型中由半面構(gòu)成的封閉空間。算法根據(jù)一個種子半面，識別出其相鄰半面，并保證了被選擇的相鄰半面與種子半面屬于同一封閉空間。遞歸執(zhí)行上述過程，可識別出模型中與種子半面屬于同一封閉空間的所有半面，即構(gòu)成該封閉空間的所有半面。

圖5a所示為三維網(wǎng)格模型的局部示例，圖5b展示了該示例在二維視角下的半面擴展過程，即以空間內(nèi)一個半面為起始，逐漸向周圍半面搜索擴展，直至搜索出該空間內(nèi)的所有半面。

圖5c所示為半面擴展過程的一個詳細示例。在本例中，以半面Fh0為種子半面，識別出其相鄰半面中與Fh0處于同一封閉空間的半面Fh1，F(xiàn)h2，F(xiàn)h3，F(xiàn)h4。遞歸執(zhí)行半面擴展過程，以半面Fh1為種子半面，識別出半面Fh5，F(xiàn)h6，F(xiàn)h7；以半面Fh2為種子半面，識別出半面Fh8和Fh9；以半面Fh3為種子半面，識別出半面Fh10和Fh11；以半面Fh4為種子半面，識別出半面Fh12。不斷遞歸執(zhí)行此過程，直到識別出該封閉空間的所有半面為止。

種子半面在一個半邊處可能存在多個相鄰半面，針對該情況，文中提出了“半面匹配規(guī)則”。根據(jù)該規(guī)則，給定種子半面及其一條半邊，可識別出種子半面在該半邊處相鄰的所有半面，并選擇一個匹配的相鄰半面，該半面與種子半面屬于同一個封閉空間。在下文中，將該過程稱為“半面匹配過程”。

如圖5d和5e所示，從不同視角可看出半面Fh2與Fh13均與半面Fh0相鄰，但以半面Fh0為種子半面進行半面擴展時，通過半面匹配規(guī)則判斷，半面Fh2與Fh0處于同一極小封閉空間，故擴展到半面Fh2而沒有擴展到半面Fh13。

如圖6所示，種子半面為Fhseed，半面Fhseed的指定半邊為Eh0。半邊Eh0的伴隨半邊Eh1，Eh2，Eh3（為了圖示清晰性，半邊Eh2，Eh3未在圖中畫出）所屬的半面分別為Fh1，F(xiàn)h2，F(xiàn)h3，共3個半面，這些半面稱為半面Fhseed在半邊Eh0處的相鄰半面，其中半面Fh3為種子半面Fhseed的伴隨半面。如圖6b所示，以半邊Eh0為軸，按照半面Fhseed的方向，從半面Fhseed到半面Fh1，F(xiàn)h2，F(xiàn)h3的有向角分別為θ1，θ2，θ3，角度值的范圍為(0，2π]。

圖5 半面擴展算法示意圖Fig.5 Diagram of half-face expansion algorithm

圖6 半面匹配規(guī)則示意圖Fig.6 Diagram of half-face matching rule

半面匹配規(guī)則描述如下：對于給定的半面半邊二元組（Fhseed，Eh0），其中半面Fhseed為種子半面，Eh0為Fhseed的一條半邊，半面集合FH中的所有半邊Fhi均為半邊Eh0關(guān)聯(lián)的半邊所屬的半面。其中集合FH一定不為空集，因為種子半面Fhseed的伴隨半面必定屬于集合FH。以半邊Eh0為軸，按照Fhseed方向從半面Fhseed到集合FH中半面Fhi的有向角為θi，則種子半面Fhseed在半邊Eh0處的匹配半面為最小有向角θj對應(yīng)的半面Fhj。半面Fhj與種子半面Fhseed處于同一封閉空間。

例如在圖示 6b中，θ1為最小有向角，根據(jù)該規(guī)則，種子半面Fhseed在半邊Eh0處所匹配的半面為Fh1。

如3.1節(jié)所述，在艙室識別算法總流程中，使用半面擴展算法識別出種子半面所屬的封閉空間。半面擴展算法流程如圖7所示。

Step 1：新建一個半面數(shù)組，表示種子半面所屬的封閉空間，用于存儲識別出的半面。

Step 2：新建一個半面隊列。在半面擴展算法執(zhí)行過程中，該隊列中的半面狀態(tài)為：已被識別出屬于當前封閉空間，但尚未執(zhí)行以該半面為種子半面的半面匹配過程。

Step 3：將種子半面加入隊列尾部，并標記為已訪問。

Step 4：判斷隊列是否為空。若隊列為空，則半面擴展算法過程結(jié)束；否則繼續(xù)執(zhí)行半面擴展算法。

Step 5：從隊列首部取一個半面作為種子半面，并從隊列中將其刪除。

圖7 半面擴展算法流程Fig.7 Flow of half-face expansion algorithm

Step 6：執(zhí)行半面匹配過程。根據(jù)半面匹配規(guī)則，識別出種子半面相鄰的、尚未被訪問的、屬于同一封閉空間的半面。

Step 7：將 Step 6中識別出的半面加入半面隊列，后續(xù)作為種子半面遞歸地執(zhí)行半面匹配過程。將其標記為已訪問，防止后續(xù)被重復(fù)加入隊列，導(dǎo)致冗余計算。

Step 8：將Step 5中取的種子半面加入表示該封閉空間的半面數(shù)組。回到Step 4，遞歸地執(zhí)行半面擴展過程。

分析可知，在識別過程中，對模型中的每個半面，僅進行了常數(shù)次訪問；由于船舶模型中任何半面包含的半邊僅有常數(shù)個，且任何半邊的伴隨半邊僅有常數(shù)個，故半面匹配過程耗時為O(1)，所以艙室識別過程的時間復(fù)雜度為O(n)，已達漸進最優(yōu)，其中n為模型中半面的總個數(shù)。

3 應(yīng)用實例

在NX11.0平臺上，以C++語言實現(xiàn)文中的CAE艙室自動識別算法，并使用多種船體模型進行測試。測試計算機CPU為Intel Core i5-6400 2.70 GHz，內(nèi)存容量為8 GB，操作系統(tǒng)為64位。

圖8所示為一個18萬t大型散貨船CAE模型，圖9所示是對該模型的艙室識別結(jié)果。該模型共有CAE單元329 509個，識別結(jié)果共有1190個封閉空間。

經(jīng)多次重復(fù)測試，測量算法中“建立拓撲關(guān)系”、“識別艙室”兩部分的耗時情況，測量結(jié)果為：建立拓撲關(guān)系耗時約3.2 s；識別艙室耗時約0.5 s，總耗時約4 s。

分析測試結(jié)果可以發(fā)現(xiàn)，建立CAE模型拓撲關(guān)系過程耗時較多，因為該過程涉及大量的內(nèi)存申請、賦值操作，且半邊查找總過程平均情況時間復(fù)雜度為O(n)，最壞情況時間復(fù)雜度為O(nlogn)（其中n為模型中半邊的總個數(shù)）；識別艙室過程耗時較短，因為僅僅涉及數(shù)值計算和數(shù)據(jù)結(jié)構(gòu)的調(diào)用，且該過程時間復(fù)雜度為O(n)（其中n為模型中face的總個數(shù)）。從算法復(fù)雜度角度可證明該識別算法的高效性。

圖8 18萬t大型散貨船CAE模型示意圖Fig.8 Diagram of CAE model for 180,000 tons large bulk carrier

圖9 大型散貨船CAE模型艙室識別結(jié)果示意圖Fig.9 Diagram of CAE model cabin identification results for large bulk carriers

對比測試使用NX系統(tǒng)內(nèi)置的船舶模塊中的艙室識別功能。該功能需要選擇種子點，一次識別種子點所在的單個艙室，使用二次開發(fā)方式利用該功能循環(huán)識別出所有艙室，并使用計時工具僅累積測量識別過程的耗時，排除其他因素影響。利用上述模型重復(fù)測試，結(jié)果表明，識別出所有艙室耗時約180～200 s。

測試結(jié)果表明，該算法效率較高，18萬t大型散貨船CAE模型的艙室識別僅耗時4 s；識別準確率較高，所有CAE艙室都已準確識別，無遺漏部分、無多余部分。

4 結(jié)語

提出了一種半面擴展算法，并基于此提出了CAE艙室自動識別算法。經(jīng)實際工程項目應(yīng)用檢驗表明，算法具有很高的效率和準確性；算法可拓展性強，在該算法基礎(chǔ)上，易于拓展出船舶艙室的相關(guān)功能，例如，識別艙室邊界構(gòu)件和內(nèi)部構(gòu)件、識別艙室中的型材、艙室合并等。該算法可廣泛應(yīng)用于船舶 CAE系統(tǒng)中，提供艙室相關(guān)構(gòu)件的高效、準確的識別功能。本質(zhì)上，該算法是對三維模型中封閉空間的識別，可預(yù)期在未來應(yīng)用于各類三維建模系統(tǒng)中。