章志兵，尚云飛，孟凡沖，柳玉起，孔海驕

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

在船舶學中，板架通常認為是由一個或多個板區(qū)域經(jīng)焊接而成，不同板區(qū)域的材料、厚度等各不相同[1]，因此，快速進行船舶板區(qū)域查找，定義其特定的材料、厚度等屬性，對船舶建模過程具有重要意義[2]。在船舶結(jié)構(gòu)上，板縫是板區(qū)域之間的邊界，由板縫分割開的兩部分分別屬于不同的板區(qū)域，這使得依據(jù)板縫識別板區(qū)域成為可能。船舶設(shè)計單位使用的定義板區(qū)域?qū)傩缘能浖饕?NAPA,TRIBON, PATRAN等，然而，這些軟件目前都是通過手動選取同屬于一個板區(qū)域的面來對板區(qū)域?qū)傩赃M行定義，效率較低[3]。

文中提出了一種基于特定屬性邊優(yōu)先搜索板區(qū)域的識別算法，通過定義特定的屬性邊，建立板架面與面之間的分組關(guān)系，從而實現(xiàn)搜索板區(qū)域的目的[4]。在NX11.0平臺上，使用C++語言實現(xiàn)該算法，并使用實船模型上的板架進行測試，結(jié)果表明，該算法能夠快速、準確地識別出船舶板區(qū)域[5]。使用該算法，可以有效提高船舶建模過程中的板區(qū)域識別，進而提高船舶建模的效率，降低船舶設(shè)計周期[6]。

1 船舶板區(qū)域識別總體流程

在船舶學中，板架是由一個或多個板區(qū)域焊接而成[7]。在計算機圖形學中，板架可以看成是由多個面組合而成，而板區(qū)域則對應(yīng)多個面的一個分組[8]。

在計算機圖形學中，使用邊界表示法對板架進行表示，板架對應(yīng)一個實體，是面的并集[9]。面是由一個外環(huán)和若干個內(nèi)環(huán)來進行描述。內(nèi)環(huán)一定在外環(huán)之內(nèi)，在面上沿著環(huán)的方向前進，左側(cè)一定在面內(nèi)，右側(cè)一定在面外，通過環(huán)可以區(qū)分面內(nèi)和面外。環(huán)是由有序邊組成的封閉邊界，相鄰兩邊共享一個頂點，環(huán)中的邊不能相交[10]。邊是相鄰鄰面的交集，由邊的起始頂點和終止頂點定義邊的方向。頂點的位置由幾何點來表示，是幾何造型中最基本的元素[11]。

圖1 邊數(shù)據(jù)結(jié)構(gòu)Fig.1 Edge data structure

邊數(shù)據(jù)結(jié)構(gòu)見圖1，其中每一條邊記錄了兩個鄰面（左外環(huán)和右外環(huán)）、兩個頂點、兩端各自相鄰的鄰邊[12]。為了保證每次搜索到的是一整個板區(qū)域的面，建立了基于特定屬性邊的板區(qū)域搜索算法，通過特定屬性邊得到環(huán)與環(huán)的相鄰關(guān)系，當邊滿足特定屬性時，停止向外搜索；當邊不滿足特定屬性時，繼續(xù)向外搜索，找到相鄰的環(huán)，直到找到的所有的面的邊都滿足特定屬性或為板架邊界，且無法找到新的相鄰環(huán)時，停止一次這樣的搜索過程。這樣，由特定屬性邊及板架邊界圍成的這樣一組面就是一個面的分組，即是需要查找的板區(qū)域。板架邊的3種情形見圖2，板架上的邊可能有以下幾種情形： ①板架邊界邊，如圖2中的C和D邊，表示的是板架邊界； ②特定屬性邊，這類邊具有特殊的屬性，用來標識分組的邊界，如圖2中的B邊； ③板架普通邊，這類邊既不是板架邊界，又沒有記錄特殊屬性，因此將其定義為板架普通邊，如圖2中的A邊?；趫D1邊的數(shù)據(jù)結(jié)構(gòu)，相對于板架普通邊，板架邊界邊只能找到一個內(nèi)環(huán)，而沒有外環(huán)，即由板架邊界邊只能找到一個面；而板架普通邊，既存在內(nèi)環(huán)，又存在外環(huán)，因此通過板架普通邊可以找到兩個面。需要說明的是，船舶上的板架，若存在開孔結(jié)構(gòu)，如圖2中的E表示開孔，此時，通過孔的邊也只能找到一個面，因此將孔的邊也作為板架邊界邊對待[13]。

圖2 板架邊的三種情形Fig.2 Three kinds of edges on plate

船舶板區(qū)域識別的總體流程如下： ①步驟1：建立船舶板區(qū)域相關(guān)的數(shù)據(jù)結(jié)構(gòu)，首先定義板縫，使用板縫將需要進行板區(qū)域識別的板架切割，保證一個面只屬于一個板區(qū)域，由切割而新形成的邊定義為板縫邊，再建立板縫邊的數(shù)據(jù)關(guān)系，由邊的數(shù)據(jù)關(guān)系建立整個板架上面的分組關(guān)系；② 步驟 2：利用建立好的板縫邊的數(shù)據(jù)關(guān)系，定義優(yōu)先搜索原則，從一個面出發(fā)，根據(jù)面、環(huán)、邊的關(guān)系，搜索出同屬于一個分組的面。一次搜索出來的面的分組就是一個板區(qū)域，重復進行此過程，直到板架上的所有面都被搜索完，就得到了板架的面分組關(guān)系，完成一個板架上的板區(qū)域搜索過程。

2 相關(guān)的數(shù)據(jù)結(jié)構(gòu)

2.1 板架面切割

板架在建模過程中只是簡單的通過對板架邊界進行定義，沒有考慮一個板架是由多個板區(qū)域組成，因此，必須首先進行板縫定義，使用板縫將一個板架切割為多個板區(qū)域，以保證一個面只屬于一個板區(qū)域。

使用板縫線切割板架的示意圖見圖 3，圖 3a顯示，在未進行切割之前，板架只有幾個面組成，由于模型中的面過大，一個面可能屬于多個板區(qū)域。用板縫線將板架切開之后，如圖3b所示，切割后的每個面只屬于一個板區(qū)域。使用板縫對全船所有板架進行切割，保證每個面只屬于一個板架上的一個板區(qū)域。

2.2 切割對應(yīng)關(guān)系的建立

板架在切割后，對切割形成的新邊進行特殊標識，以區(qū)分不同的板區(qū)域，因此，將切割形成的新邊定義為板縫邊。

圖3 板縫切割板架Fig.3 Seam cutting panel

切割對應(yīng)關(guān)系見圖 4。如圖 4a所示，在進行板縫定義之前，對板架上所有的邊做一次屬性記錄，用來標識板架初始邊。進行一次板縫定義之后，這些初始邊仍然具有初始定義的屬性。即使初始邊被打斷形成多段邊，這些被打斷形成的邊會繼承原有的屬性。只有新生成的邊如圖4b中的新邊，沒有初始邊上的屬性，對于這些邊，認為其是由切割形成的新邊。在這些邊上，記錄上特定的屬性，以標識其為板縫邊。

圖4 切割對應(yīng)關(guān)系Fig.4 Cutting correspondence

2.3 面分組關(guān)系建立

利用計算機圖形學中的面、環(huán)、邊的關(guān)系，在同一個板架上，可以通過任意一個面，根據(jù)面的邊，找到其相鄰的面。任意一個面與其相鄰面的關(guān)系見圖5。對于任意一個face，可以通過face的環(huán)，找到其所有的邊（edge(1)～edge(k)），對于任意一條邊，若不是板架的邊界邊，則可以通過邊的內(nèi)環(huán)與外環(huán)關(guān)系，找到其相鄰的面，從而找到一個面（face）的所有相鄰的面（face(1)～face(k)）。

圖5 面的相鄰關(guān)系Fig.5 Face-to-face relationship

板區(qū)域的一組面是由板架邊界、特定屬性邊圍成。在尋找一塊板區(qū)域的面時，需要對上述搜索過程進行一些修改。在由面得到其所有的邊之后，需要對邊進行判斷，若該邊是板架邊界邊，或是由2.2過程定義的特定屬性邊，則不進行內(nèi)環(huán)、外環(huán)這一搜索過程，這條邊直接跳過，進行下一條邊的判斷、搜索過程?；谔囟▽傩赃叿纸M的面的相鄰關(guān)系見圖6，遍歷圍成 face的邊，若是板架邊界邊如圖 6中的edge(2)，則找不到這樣的face(2)；若是特定屬性邊，雖然存在face(2)，但此時，由于該邊是分組的邊界，因此直接跳過，不向外搜索，直接進行下一條邊的判斷搜索。

圖6 基于特定屬性邊分組的面的相鄰關(guān)系Fig.6 Neighboring relationships of faces grouped based on specific attributes

有了上述基于特定屬性邊分組的面的關(guān)系，就可以開始一組面的搜索過程了。基于特定屬性邊分組的面的相鄰關(guān)系見圖7。為便于表達，圖7中面的左上角f～是人為的對面的編號，沒有其他特殊含義。每個面可能會有以下 3 種狀態(tài)：“0”, “1”, “2”，其中狀態(tài)“0”是初始狀態(tài)，表示此面沒有被搜索過且沒有加入待搜索隊列；狀態(tài)“1”表示當前的面已經(jīng)被加入待搜索隊列中，后續(xù)會對此面進行向外搜索，得到與其在同一個區(qū)域中的面；狀態(tài)“2”表示當前的面已經(jīng)進行過搜索過程，為結(jié)束狀態(tài)。對每一個面向外搜索時，搜索與此面的四邊相鄰的面，只將相鄰面中狀態(tài)為“0”的面加入到待搜索隊列中，對于狀態(tài)為“1”或狀態(tài)為“2”的面，不加入待搜索隊列，以避免重復搜索。如圖7a，首先對板架上的所有面進行初始化，所有面上都標記狀態(tài)“0”。如圖7b，在板架上任取一個狀態(tài)為“0”的面作為種子（seed）面，圖7b中選取的為面f8。如圖7c，從seed面出發(fā)，依據(jù)圖6所述基于特定屬性邊分組的面的相鄰關(guān)系，向外搜索，得到f13, f9, f3,f7這4個面，由于這些面的狀態(tài)皆為“0”，因此將其加入到待搜索隊列中，將其狀態(tài)改為“1”，同時，由于f8面已進行過搜索過程，因此將其狀態(tài)改為“2”。如圖7d，從待搜索的隊列中取出一個面，繼續(xù)進行向外搜索的過程。如圖7d中選取到f13面，f13面的4條邊總，有3條邊有鄰面，分別為f8, f12, f14，第4邊為板架邊界邊，因此此邊跳過，同時，f8的狀態(tài)為“2”，因此不加入待搜索隊列中，f12, f14的狀態(tài)為“0”，因此將其加入待搜索隊列中，將其狀態(tài)改為“1”，同時將f13的狀態(tài)改為“2”。如圖7e，接下來從待搜索隊列中取出f9面進行向外搜索的過程。f9面只有3個相鄰面：f8, f14, f4，其中f8狀態(tài)為“2”，f14狀態(tài)為“1”，僅f4狀態(tài)為“0”，因此，將f4加入待搜索隊列中，將其狀態(tài)改為“1”，同時將f9狀態(tài)改為“2”。如圖7f，對f3進行向外搜索過程。與f9類似，搜索到f2面，將其加入待搜索隊列中，更改對應(yīng)的狀態(tài)。如圖7g，接下來對f7面進行向外搜索，f7面相鄰的面有f2, f6, f8, f12，然而，f7與f6面的公共邊標記了特殊的屬性，依據(jù)圖6中的分組原則，對于特定義屬性邊，不進行向外搜索過程，因此f6面不會被搜索，而f2, f8, f12面狀態(tài)都不為“0”，因此直接將f7面的狀態(tài)改為“2”。如圖7f—7k，接下來對f12, f14, f4, f2的搜索過程與f7搜索類似，最終得到的結(jié)果見圖7k，此時，待搜索隊列已空，搜索過的這些面的狀態(tài)都變?yōu)椤?”。搜索到的這一組面就是一個面區(qū)域，至此，面的分組關(guān)系得到了建立。

圖7 面的分組關(guān)系建立過程Fig.7 Process of establishing face group relationship

3 船舶板區(qū)域識別算法流程

3.1 算法流程

根據(jù)建立好的板架面的分組關(guān)系，定義如下優(yōu)先搜索算法，對全船所有板架上的面進行分組（vF為板架上的所有的Face集合，F(xiàn)G為由一個種子面出發(fā)搜索到的一個面分組，vFG為一個板架上搜索到的所有板區(qū)域的集合，F(xiàn)State記錄面的狀態(tài)，分別有“0”,“1”, “2”這3種狀態(tài)，qF維護待搜索面的序列，狀態(tài)為“1”的面都將被加入到qF中）。

步驟1：建立板架上面的相鄰關(guān)系，定義板縫，使用板縫切割板架，在新形成的板縫邊上標識特定的屬性，將一個板架上的所有的面存入vF中，標識vF中的所有的Face狀態(tài)為“0”。

步驟2：從vF中任取一個狀態(tài)為“0”的Face作為種子（seed）面，若找不到這樣的Face，說明已經(jīng)搜索完畢，結(jié)束這個板架的搜索過程。若找到一個這樣的Face，則進入步驟3。

步驟3：將當前seed加入qF中，并更改其狀態(tài)為狀態(tài)“1”。

步驟4：判斷qF是否為空，若qF非空，則取出qF中最前面的Face，將此Face加入到FG中，通過此Face，向外搜索，若此Face的邊為板架邊界邊或特定屬性邊，則跳過，否則得到其相鄰的Face，檢測相鄰 Face狀態(tài)，若為狀態(tài)“0”，則將其加入 qF中；若相鄰Face狀態(tài)為“1”或“2”，則跳過。若qF為空，則說明由步驟3中的seed開始的一次向外搜索的過程已經(jīng)結(jié)束。同屬于一個分組的 Face已經(jīng)加入到一個FG中。FG中存儲的就是一個板區(qū)域的所有Face，此時將FG加入到vFG中去，vFG中就存儲了板架上的一個板區(qū)域的所有Face。

步驟5：重復進行以上步驟2～4的過程，直到在步驟2中，找不到一個被標識為狀態(tài)“0”的Face停止，此時，vF中的所有 Face都標識為狀態(tài)“2”，表示當前板架上的面都被搜索完成，并已被分配進各自的分組中。vFG中存儲的就是這個板架上的所有的板區(qū)域分組。

經(jīng)過上述優(yōu)先搜索過程，所有板架上的面都被分進各自的板區(qū)域分組中，從而實現(xiàn)了板區(qū)域識別的目的。

3.2 應(yīng)用實例

在NX11.0平臺上，使用C++語言對上述板區(qū)域識別算法進行開發(fā)，并使用實船模型進行測試，結(jié)果顯示，上述算法能夠快速，準確地進行船舶板區(qū)域識別[14]。

使用 318000散貨船進行測試的過程見圖 8。模型的建模公差為2.0 mm（NX11.0可通過設(shè)置系統(tǒng)公差的方法設(shè)置），使用的計算機主要參數(shù)配置為：Inter(R)Core(TM)i5 760 CPU,16 GB內(nèi)存[15]。定義板縫線過程見圖 8a，其中使用甲板作為測試對象，在甲板上適當位置建立板縫理論線，為下一步切割做準備。圖8b所示為使用圖8a中定義的板縫線對甲板進行切割，圖8b中藍色高亮顯示的邊即是板縫邊。切割后，在這些新形成的板縫邊上寫上特殊屬性“Profile System”，用以標識這些新形成的邊，這些寫上特殊屬性的邊及板架自由邊共同構(gòu)成了板架面分組的邊界。運用建立好的切割對應(yīng)關(guān)系及分組關(guān)系，在甲板上查找板區(qū)域分組的過程見圖 8c。使用此模型進行查找，在甲板上共查找到186個板區(qū)域，耗時833 ms，平均每個板區(qū)域的查找時間不到4.5 ms。在軟件實際應(yīng)用過程中也得到了驗證，使用該算法在板架上對板區(qū)域進行實時查找，具有很低的時間復雜度，查找的準確度也非常之高。

圖8 318 000散貨船板識別過程Fig.8 Identification process of bulk carrier 318000

4 結(jié)語

提出了一種基于 NX平臺的船舶板區(qū)域識別算法，該算法使用特定屬性邊及板架邊界邊對板架上的面分組，通過實時查找面分組，達到識別板區(qū)域的目的。基于NX11.0平臺，使用C++語言對此算法進行開發(fā)，并使用實船模型進行測試。結(jié)果表明，該算法能夠快速、準確地識別出船舶板區(qū)域，有效提高了船舶板區(qū)域識別、板區(qū)域?qū)傩远x的效率。對于建模精度較高的船舶模型，在甲板、外殼、船首、船尾等結(jié)構(gòu)復雜的板架上也能保持很高的識別效率和準確度。而對于建模精度較差的模型，或者是由第三方平臺導入的模型，由于建模公差較大，特定屬性邊建立時可能會出現(xiàn)沒有完全切割到邊的情況，這對板架面相鄰關(guān)系的建立有一定影響，也就可能會導致后續(xù)識別不準的問題，因此，在大的建模公差下，如何提高算法的識別準確率是下一步研究的重點。