基于CAE模型的船舶艙室自動識別高效算法

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

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

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

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

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

1 半邊半面模型

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

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

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

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

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

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

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

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

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

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

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

Step 2：建立CAE模型的拓撲關系，并創建半邊半面數據結構存儲拓撲關系。

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

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

Step 5：存儲識別結果。以一個新的半面數組存儲表示該封閉空間。回到 Step3，遞歸地執行艙室識別過程。

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

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

2.1 CAE模型拓撲關系建立

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

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

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

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

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

圖4 CAE模型拓撲關系示意圖Fig.4 Diagram of CAE model topology relationship

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

2.2 半面擴展算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 4：判斷隊列是否為空。若隊列為空，則半面擴展算法過程結束；否則繼續執行半面擴展算法。

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

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

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

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

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

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

3 應用實例

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

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

經多次重復測試，測量算法中“建立拓撲關系”、“識別艙室”兩部分的耗時情況，測量結果為：建立拓撲關系耗時約3.2 s；識別艙室耗時約0.5 s，總耗時約4 s。

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

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

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

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

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

4 結語

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