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

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

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

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

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

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

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

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

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

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

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

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

2.1 板架面切割

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法流程

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

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

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

步驟3：將當(dāng)前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é)束。同屬于一個(gè)分組的 Face已經(jīng)加入到一個(gè)FG中。FG中存儲(chǔ)的就是一個(gè)板區(qū)域的所有Face，此時(shí)將FG加入到vFG中去，vFG中就存儲(chǔ)了板架上的一個(gè)板區(qū)域的所有Face。

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

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

3.2 應(yīng)用實(shí)例

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

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

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

4 結(jié)語

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