羅月童，韓承村，杜華，嚴伊蔓

（1.合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽合肥 230601； 2.中國科學(xué)院 等離子體物理研究所，安徽合肥 230031； 3.國家電投集團科學(xué)技術(shù)研究院有限公司，北京 100033）

0 引 言

邊界表示（boundary representation，B-Rep）法和構(gòu)造實體幾何（construction solid geometry，CSG）法是使用最廣泛的2 種實體表示法，其中B-Rep 法已廣泛應(yīng)用于各種商用CAD 軟件，借助商用CAD軟件強大的造型功能，用戶能方便快捷地構(gòu)建三維B-Rep 模型。也有很多科學(xué)計算程序用CSG 法，如粒子輸運程序MCNP［1］、cosRMC［2］等，這是因為CSG 法具有對科學(xué)計算程序非常重要的穩(wěn)定、簡單等優(yōu)點。目前市場上能直接構(gòu)建CSG 模型的成熟軟件較少，因此希望借助商業(yè)CAD 軟件建立B-Rep模型，然后將B-Rep 模型自動轉(zhuǎn)換為CSG 模型，以減輕建模工作量。如面向MCNP、cosRMC 等粒子輸 運 程 序 的cosVMPT［3］、MCAM［4］、McCAD［5］等軟件，這些軟件的核心功能都是將B-Rep 模型轉(zhuǎn)換為CSG 模型，即B-Rep→CSG 轉(zhuǎn)換算法。本文源于自主研發(fā)的粒子輸運COSINE 可視建模（COSINE visual modelling of particle transport，cosVMPT）軟件，旨在基于拉伸特征提升B-Rep→CSG 轉(zhuǎn)換算法的穩(wěn)定性和速度，以提高cosVMPT 軟件對大規(guī)模模型的處理能力。

B-Rep→CSG 轉(zhuǎn)換問題備受關(guān)注［6］，主要有三類轉(zhuǎn)換方法：（1）半空間分割法［7］，通常利用某些面分割B-Rep 模型，基于面的半空間分割組合獲得CSG 表示，其核心是分割面的選擇，較常見的做法是從B-Rep 模型中提取分割面。文獻［8-9］利用CLoop 環(huán)構(gòu)造分割面以改善分割效果，但CLoop 環(huán)的識別比較復(fù)雜。（2）交替和差分解法［10］，通過求BRep 模型的凸包并與之做布爾減運算得到差體，繼續(xù)對差體求凸包并與之做布爾差運算，如此反復(fù)循環(huán)直至差體為空，將凸包和差體組合得到B-Rep 模型的CSG 表示。（3）單元分解法［11-12］，將B-Rep 模型分解為一組單元體，用優(yōu)化方法求解相關(guān)單元體組合，實現(xiàn)B-Rep→CSG 轉(zhuǎn)換，但此類方法通常存在過分割問題。半空間分割法因其具有直觀、易實現(xiàn)等優(yōu)點廣受關(guān)注，其中，cosVMPT、MCAM、McCAD 采用的均為半空間分割法。

圖1 半空間分割法示意圖Fig.1 Schematic diagram of half space partition method

半空間分割法，沿一系列面將B-Rep 模型分解為若干簡單模型，然后基于簡單模型實現(xiàn)B-Rep→CSG 轉(zhuǎn)換，圖1 展示的為模型的分割過程。對復(fù)雜的B-Rep 模型分割量較大，通常通過造型引擎的布爾交/減運算實現(xiàn)分割，如MCAM 采用商業(yè)造型引擎ACIS［13］，cosVMPT 和McCAD 采用開源造型引擎OpenCascade［14］。經(jīng)過多年發(fā)展，雖然ACIS、OpenCascade 引擎已較成熟，但因為布爾運算涉及復(fù)雜的數(shù)值運算，所以仍然存在布爾運算失敗的概率。 筆者在實踐中發(fā)現(xiàn)，開源造型引擎OpenCascade 失敗概率更高，從而降低了B-Rep→CSG 轉(zhuǎn)換算法的穩(wěn)定性。因為cosVMPT 等軟件經(jīng)常需要一次性轉(zhuǎn)換數(shù)萬個B-Rep 模型，中國聚變工程 實驗堆（China fusion engineering test reactor，CFETR）模型由50 000 多個B-Rep 模型組成，如圖2 所示，存在布爾運算失敗導(dǎo)致轉(zhuǎn)換失敗的概率，因此，在實際應(yīng)用中，不得不對模型進行預(yù)處理，如將復(fù)雜的B-Rep 模型預(yù)先分解為若干簡單的B-Rep模型，這不僅需耗費大量時間，而且對用戶的CAD建模技能有很高要求，嚴重影響cosVMPT 等軟件的易用性和友好性。因此，降低B-Rep→CSG 轉(zhuǎn)換算法對布爾運算的依賴性、提升B-Rep→CSG 轉(zhuǎn)換算法的穩(wěn)定性、改善相關(guān)軟件的可用性和易用性等研究具有一定的理論意義和實用價值［15-16］。

圖2 CFETR 聚變堆模型Fig.2 CFETR fusion reactor model

自主研發(fā)的cosVMPT 軟件常常用于處理裂變堆模型和聚變堆模型，圖2 為CFETR 聚變堆模型，圖3 為AP1000 裂變堆堆芯模型。筆者觀察到這類模型中存在大量掃略體，即二維圖形通過拉伸或旋轉(zhuǎn)所形成的三維對象?；诖?，提出利用掃略體特點優(yōu)化B-Rep→CSG 轉(zhuǎn)換：對二維圖形進行B-Rep→CSG轉(zhuǎn)換，然后將轉(zhuǎn)換映射至三維模型。因二維圖形的B-Rep→CSG 轉(zhuǎn)換不需要布爾運算，通過大幅度減少布爾運算，提升B-Rep→CSG 轉(zhuǎn)換算法的穩(wěn)定性。掃略體通常包括拉伸體和旋轉(zhuǎn)體，本文以拉伸體為例探討優(yōu)化B-Rep→CSG 轉(zhuǎn)換算法。拉伸特征是指單獨存在的完整拉伸體、部分拉伸體，或作為模型一部分的完整拉伸體、部分拉伸體，圖4 給出了典型拉伸特征的各種存在形式，轉(zhuǎn)換流程的關(guān)鍵是拉伸特征的識別和二維圖形的B-Rep→CSG轉(zhuǎn)換。

本文的主要貢獻包括：

（1）提出了基于拉伸特征的B-Rep→CSG 轉(zhuǎn)換算法，以減少轉(zhuǎn)換算法對布爾運算的依賴，提升了算法的穩(wěn)定性；

（2）給出了拉伸特征的定義及其識別方法，解決了基于拉伸特征的B-Rep→CSG 轉(zhuǎn)換算法的關(guān)鍵問題；

（3）將所提算法集成至自主研發(fā)的cosVMPT軟件，并投入實際應(yīng)用。

圖3 AP1000 裂變堆堆芯模型Fig.3 AP1000 fission core model

圖4 拉伸特征的各種存在形式Fig.4 Various existing forms of stretch feature

1 拉伸特征的識別

由圖4 可知，拉伸特征可看作由二維圖形沿一定方向拉伸形成的三維圖形（本文稱其為拉伸體）或其一部分。其中，由二維圖形的邊拉伸形成的面稱為拉伸面，由二維圖形的頂點拉伸形成的邊稱為拉伸邊，且所有拉伸邊均為直線，如圖5（a）所示。

雖然拉伸特征可能是拉伸體的一部分，但本文要求保留拉伸體所有拉伸邊的全部或部分。圖5（b）中，因為拉伸邊被完全切割，所以其為無效拉伸體。拉伸特征包含相應(yīng)拉伸體的所有拉伸邊，可通過拉伸邊識別拉伸特征，其核心是提取拉伸特征所包含的一組拉伸邊，本文稱其為拉伸邊集。

圖5 拉伸體、拉伸面、拉伸邊示意Fig.5 Schematic diagram of extruded body，extruded surface and extruded edge

1.1 拉伸邊集特點分析

為準確識別拉伸邊集，筆者對拉伸邊集進行了觀察、分析和總結(jié)，得到以下條件。

（1）相互平行性：拉伸邊集中的所有邊相互平行，拉伸邊集由一組平行邊構(gòu)成。

（2）首尾相連性：如果兩條邊共享一個面，則稱這兩條邊相連。拉伸邊集中的任何一條邊與且僅與另外兩條邊相連，拉伸邊集中所有邊將形成一個首尾相連的環(huán)。

（3）方向相反性：按順時針或逆時針遍歷所有邊，按遍歷順序定義邊的方向。若拉伸邊集中的兩條邊共享一個面，則此兩條邊方向相反。

（4）唯一連接性：拉伸邊集中最多有兩條邊共享一個面。由拉伸特征的定義可知，兩條邊共享的面為拉伸特征的側(cè)面，只出現(xiàn)一次。

上述4 條均為拉伸邊集的必要而非充分條件，若一組邊同時滿足上述條件，則構(gòu)成一個拉伸邊集。本文雖然未能給出嚴格的理論證明，但從大量的觀察、實驗和實際應(yīng)用中已得到驗證。并基于上述結(jié)論設(shè)計了拉伸邊集提取算法。

對 B-Rep 模 型M=(EM，F(xiàn))，其 中EM=表示模型M中所有邊的集合，F(xiàn)={f1，f2，…，fm}表示模型M中所有面的集合。

提取拉伸邊集算法：

（i）從EM中提取所有平行邊組：P1，P2，…，PK。因為相互平行性是拉伸邊集的必要條件，所以M的所有拉伸邊集均包含P1，P2，…，PK，每個Pi可能包含0 個或多個拉伸邊集。

（ii）利用拉伸邊集的首尾相連性、方向相反性和唯一連接性，從平行邊組Pi中提取0 個或多個拉伸邊集。

因算法（i）提取平行邊組的方法比較成熟，不再贅述，下文主要討論算法（ii）。

1.2 基于平行邊連接圖的拉伸邊集識別

因為拉伸邊集的首尾相連性與圖的簡單回路特點非常相似，所以采用基于簡單回路的算法提取拉伸邊集。提出用平行邊連接圖G=(V，EG)刻畫平行邊組各元素的連接關(guān)系，并在圖G=(V，EG)中由拉伸邊集的方向相反性和唯一連接性準確提取拉伸邊集。

平行邊連接圖G=(V，EG)的構(gòu)造過程：

（2）如 果vi，vj∈V所 對 應(yīng) 的 平 行 邊滿足：

則創(chuàng)建邊(vi，vj)∈EG；

（3）將共享面f作為邊(vi，vj) 的屬性，即令attr（vi，vj）=f。

如圖6（a）所示，B-Rep 模型垂直方向平行邊P={A，B，C，D，E，F(xiàn)，G，H}，其中，A-B，B-C，CD，D-A，E-F，F(xiàn)-G，G-H，H-E，A-F，B-E，A-E和B-F共12 對平行邊共享某個面，但A-E以及B-F的共享面為f1且方向相同，其對應(yīng)平行邊連接圖如圖6（c）所示，包括8 個頂點、10 條邊及邊的屬性。

完成平行邊連接圖G=(V，EG)構(gòu)建后，按以下步驟提取拉伸邊集：

（1）基于深度優(yōu)先搜索的改進算法［8］求G=(V，EG)中所有簡單回路{L1，L2，…，Ln}，其中，回路Li中的節(jié)點記為{v1，v2，…，vm}，所有邊記為

圖6 拉伸特征及其平行邊連接圖Fig.6 Stretch feature and its parallel edge connection graph

上述步驟可輸出0 個或多個平行邊集，可以證明，所輸出的每個平行邊集均滿足1.1 節(jié)中的4 個條件，因此均構(gòu)成拉伸邊集。

證明過程如下：

（1）相互平行性：因為平行邊連接圖的所有節(jié)點對應(yīng)模型中的一組平行邊，所以輸出的邊集為一組平行邊，滿足相互平行性；

（2）首尾相連性：因為這組平行邊對應(yīng)圖中的簡單回路，所以滿足首尾連接性；

（3）方向相反性：由平行邊連接圖構(gòu)建方法可知，圖中邊所連接的兩個頂點對應(yīng)的平行邊方向相反，所以滿足方向相反性；

（4）唯一連接性：由提取拉伸邊集算法（ii），可排除不滿足該條件的簡單回路，因此，最終輸出結(jié)果均滿足唯一連接性。

圖6（c）為平行邊連接圖，有3 個簡單回路{A，B，C，D}、{A，B，E，F(xiàn)}和{E，F(xiàn)，G，H}，如 圖6（d）所 示，但 由 于{A，B，E，F(xiàn)} 中，attr(A，F(xiàn))=attr(B，E)=f1，因此將其剔除，最后只保留有效簡單 回 路{A，B，C，D}和{E，F(xiàn)，G，H}，見 圖6（e），其分別對應(yīng)圖6（b）中紅色和黃色所示的拉伸特征。

2 基于拉伸特征的B-Rep→CSG 轉(zhuǎn)換

如果B-Rep 模型M的部分或全部是一個或多個拉伸特征F1，F(xiàn)2，…，F(xiàn)n，那么，首先將模型M分解為模型MF1，MF2，…，MFn和MR，其中，MFi表示拉伸特征Fi對應(yīng)的模型，MR表示分離所有拉伸特征后的剩余部分，圖7（a）模型的分解結(jié)果見圖7（b）。然后對MFi和MR實施B-Rep→CSG 轉(zhuǎn)換獲得相應(yīng)的CSG 表示CSG(MFi)和CSG(MR)，于是B-Rep 模型M的B-Rep→CSG 轉(zhuǎn)換結(jié)果可表示為CSG(M) =CSG(MR)+CSG(MFi)。

圖7 拉伸特征分解過程示意Fig.7 Schematic diagram of feature decomposition process of stretch

剩余部分MR為一般的B-Rep 模型，因此采用文獻［3］所述的B-Rep→CSG 算法。

2.1 基于環(huán)收縮的拉伸特征分離

拉伸特征是B-Rep 模型的一部分，可按各種方式與模型其余部分連接，圖8（a）中，連接處只有一個平面，較簡單，但圖8（b）中，連接處涉及多個面，較復(fù)雜。無論連接處較簡單還是較復(fù)雜，拉伸特征體MF和模型M之間的邊界都只有一個環(huán)，而文獻［9］提出基于環(huán)收縮的面殼封閉法，可依據(jù)環(huán)分離B-Rep 模型的多個部分，圖8（c）展示的為相關(guān)例題，本文用環(huán)收縮算法分離拉伸特征。

文獻［9］詳細介紹了環(huán)收縮算法，筆者在前期工作中也已實現(xiàn)環(huán)收縮算法［17］。本節(jié)主要討論拉伸特征體MF和模型M連接處環(huán)的提取，環(huán)提取后即可運用環(huán)收縮算法對拉伸特征體進行分類。本文稱拉伸特征體MF和模型M連接處的環(huán)為分割環(huán)。

由圖8 可知，拉伸特征邊的分割環(huán)具有以下特點：

（1）每個拉伸特征有且僅有2 個分割環(huán)，分別在拉伸特征體的兩端；

（2）分割環(huán)由拉伸面的邊組成，且不包括拉伸邊。

圖8 切割環(huán)示意Fig.8 Schematic diagram of cutting ring

基于以上觀察，對拉伸特征F，如果其拉伸邊面集和邊集分別為{f1，f2，…，fn}和{e1，e2，…，en}，則提取分割環(huán)的過程如下：

（1）提取所有拉伸面的邊，組成集合E=其中edge(fi)表示面fi的所有邊；

（2）去除所有拉伸邊，形成新邊集E′=E?{e1，e2，…，en}；

（3）依據(jù)E′中邊的連接關(guān)系，提取分割環(huán)。

在如圖9（a）所示的模型中，上面黃色部分為拉伸特征，其所對應(yīng)的分割環(huán)如圖9（b）所示，運用環(huán)收縮分離可獲得如圖9（c）所示的2 個模型。

圖9 基于環(huán)搜索的分割過程Fig.9 Segmentation process based on ring search

2.2 基于拉伸特征的B-Rep→CSG 轉(zhuǎn)換

基于拉伸特征，將二維圖形沿一定方向拉伸，將三維拉伸特征的B-Rep→CSG 問題轉(zhuǎn)換為二維圖形的B-Rep→CSG 問題。如圖10 所示，在采用半空間分割法進行B-Rep→CSG 轉(zhuǎn)換時，可先對二維圖形進行轉(zhuǎn)換，然后將轉(zhuǎn)換結(jié)果映射至三維空間，如將圖10 所示輪廓面的邊映射為拉伸特征的面，再添加端面即可獲得拉伸特征的CSG 表示。本文采用半空間分解法，其拉伸特征MF的B-Rep→CSG 轉(zhuǎn)換步驟如下：

（1）獲取拉伸特征體對應(yīng)的二維圖形，并對二維圖形進行B-Rep→CSG 轉(zhuǎn)換，獲得二維圖形的CSG表示，見圖10（b）。

（2）將二維圖形CSG 表達式中的邊映射至面，如直線映射為平面、圓弧映射為圓柱面，獲得兩端無界的拉伸體的CSG 表示，見圖10（c）。

（3）根據(jù)拉伸特征的端面情況，為步驟（2）所得的CSG 表達式添加端面，最終獲得拉伸特征的完整CSG 表示，見圖10（d）。

因步驟（2）可根據(jù)拉伸特征的定義直接完成映射，不再贅述。若拉伸特征的端面為單個平面，則步驟（3）可直接解決，若端面由多個面組成，則比較復(fù)雜，筆者在工程實踐中采用的是遞歸半空間分割法。因為本文的核心是拉伸特征的識別和應(yīng)用，且在工程實踐中，端面多為平面，所以僅考慮端面為平面的情況，對步驟（2）和（3）不再做詳細討論。

圖10 拉伸特征B-Rep→CSG 轉(zhuǎn)換過程示意Fig.10 Schematic diagram of B-Rep→CSG conversion process of stretch feature

由文獻［18］知，在半空間分割方法中，二維圖形B-Rep→CSG 轉(zhuǎn)換的難點是如何將復(fù)雜的二維圖形分解為一組簡單圖形。如果二維圖形是多邊形，則將多邊形分解為一組凸多邊形。因為將任意多邊形分解為一組凸多邊形是圖形學(xué)領(lǐng)域的經(jīng)典問題，有大量優(yōu)秀成果可以利用，本文僅考慮利用相關(guān)算法解決二維圖形的B-Rep→CSG 轉(zhuǎn)換問題。文獻［19］中的多邊形分解算法具有計算量小、分解所得的凸多邊形邊少等優(yōu)點，能簡化多邊形的CSG 表示。如圖11（a）所示的復(fù)雜多邊形，用文獻［19］中的基于頂點可見的多邊形分解算法，得到如圖11（b）所示的結(jié)果，而任意分解結(jié)果如圖11（c）所示，可見文獻［19］算法的分解結(jié)果更優(yōu)。

圖11 不同多邊形分解算法效果對比Fig.11 Comparison of different polygon decomposition methods

因為cosVMPT 軟件要求B-Rep 模型只能包含平面、球面、圓柱面、圓錐面和圓環(huán)面，所以當拉伸特征的拉伸面為平面或圓柱面時，所對應(yīng)的二維圖形的邊為圓弧或直線。如圖12 所示，若二維圖形M2D中包含圓弧，則可通過以下方法將其轉(zhuǎn)換為多邊形，再采用多邊形分解算法（不考慮出現(xiàn)自交多邊形的情況）：

（1）用弦代替對應(yīng)圓弧，形成多邊形P2D。

（2）記錄圓弧和弦包圍形成的二維圖形，將所有凸圓弧和凹圓弧對應(yīng)的圖形分別記為{conf1，conf2，…，confn} 和{concf1，concf2，…，concfm}。

那么M2D的CSG 表示為

圖12 輪廓面的多邊形化過程Fig.12 Polygonization process of profile

3 實驗與應(yīng)用

本文算法已應(yīng)用于我國自主核能設(shè)計軟件包COSINE 的輔助建模cosVMPT 軟件，其主界面如圖 13 所示。 該軟件基于開源造型引擎OpenCascade 7.3.0，在windows 平 臺 采 用visual studio 2017 開發(fā)。 本文中的所有實驗均基于cosVMPT 完成。

圖13 cosVMPT 主界面Fig.13 The main interface of cosVMPT

首先由簡單到復(fù)雜構(gòu)造3 個模型，見圖14 中的（1）、（2）和（3）。分別對模型進行測試，并對采用本文算法前后的轉(zhuǎn)換時間和轉(zhuǎn)換效果進行比較，見表1 和圖14。因為半空間分割法B-Rep→CSG 轉(zhuǎn)換的核心是分解復(fù)雜模型，所以圖14 未采用最終的CSG表達式，而是以分解結(jié)果表示轉(zhuǎn)換效果。

表1 轉(zhuǎn)換時間比較Table 1 Time comparison of conversion

由圖14 可知，本文算法的分解結(jié)果更簡潔或其CSG 表示更簡潔。如本文算法可將模型（2）分解為4 個子模型，而半空間分割法則將模型（2）分解為9個子模型，且本文算法分解結(jié)果更符合模型的特點，即具有更強的語義性；雖然用半空間分割法分解模型（1），子模型數(shù)更少，但其分解結(jié)果的CSG 表示更復(fù)雜，需要添加輔助分割面。由表1 可知，在轉(zhuǎn)換時間上，本文算法也具明顯優(yōu)勢，3 個模型均提速30%以上，且模型越復(fù)雜，提速效果越明顯。

圖14 測試分解結(jié)果展示Fig.14 Display of test results

用具有代表性的AP1000 裂變堆堆芯模型進行測試（如圖3 所示）。AP1000 是我國引進的由美國西屋公司設(shè)計的第3 代先進反應(yīng)堆，其包含665 個B-Rep 模型，所有模型均為拉伸體，采用本文算法后，B-Rep→CSG 轉(zhuǎn)換時間由130 079 ms 降至7 781 ms，速度提升了39%。但由于此案例中的BRep 對象均較簡單，尚難體現(xiàn)本文算法的優(yōu)勢。

本文算法的主要優(yōu)勢是降低了對布爾運算的依賴，提高了算法的穩(wěn)定性。但因布爾運算失敗具有偶然性，難以準確復(fù)現(xiàn)，本文尚無法用實驗證明此優(yōu)勢。

4 結(jié) 語

半空間分割法是應(yīng)用最廣泛的B-Rep→CSG轉(zhuǎn)換算法之一，其核心是將B-Rep 模型分解為一組簡單模型，在實現(xiàn)過程中，依賴三維造型引擎的布爾運算，但因造型引擎的布爾運算存在失敗概率，從而影響B(tài)-Rep→CSG 轉(zhuǎn)換算法的穩(wěn)定性，尤其對批量轉(zhuǎn)換軟件，不穩(wěn)定性會嚴重影響軟件的可用性和友好性。本文利用拉伸特征，將三維B-Rep 模型的B-Rep→CSG 轉(zhuǎn)換問題轉(zhuǎn)變?yōu)槎S圖形的B-Rep→CSG 轉(zhuǎn)換問題，從而降低對布爾運算的依賴，提高轉(zhuǎn)換算法的穩(wěn)定性，同時提高了轉(zhuǎn)換算法的速度。

提出了基于拉伸邊的拉伸特征識別方法，通過觀察和總結(jié)，得到拉伸邊的相互平行性、首尾相連性、方向相反性、唯一連接性4 個特征，在此基礎(chǔ)上提出基于平行邊連接圖的拉伸特征識別算法。在拉伸特征識別算法的基礎(chǔ)上，結(jié)合基于環(huán)收縮的模型分割算法和基于頂點可見的多邊形分解算法，實現(xiàn)了三維模型的B-Rep→CSG 轉(zhuǎn)換，并在cosVMPT軟件中進行了測試，測試結(jié)果驗證了算法的有效性和優(yōu)越性。

本文的拉伸特征識別算法依賴相互平行性、首尾相連性、方向相反性、唯一連接性等實踐經(jīng)驗，沒能對算法的完備性進行嚴格證明，有待今后進一步研究；另外，本文討論的是拉伸特征，在實踐中存在大量旋轉(zhuǎn)特征，將旋轉(zhuǎn)特征的三維問題轉(zhuǎn)換為二維問題，也有待下一步研究，以進一步擴大本文算法的應(yīng)用領(lǐng)域。