面壳封闭技术改进b-rep至csg转换算法

面壳封闭技术改进b-rep至csg转换算法

b-rep模型和结构实体表示法是两种应用最广泛的三维实体表达方法。b-rep模型到csg模型的转换算法具有重要的理论意义和应用价值。现有的b-rep-csg转换算法主要分为三种类型：1）半空间法。该算法首先基于b-rep模型构建了半空间，然后以半空间作为基本单元建立了相应的csg模型。shapilo等人首次系统研究了半空间构建方法，并以csg树为基本单元。另一方面，buchele等人使用二维空间分割树（bps）进一步优化了shapilo等人创建半空间的方法。文献中的模型是直接基于b-rep模型的边界层的。每次，模型分解的策略只能基于b-rep模型的边界层选择，然后根据cloop结构或平面进行构建。然后，根据新结构的平面或平面，在模型的框架中构建半空间。模型分解的策略可以基于b-rep模型的多个边界层优化分解策略，以提高转换效率和结果的可靠性。2）交替和差分法以模型为基础，以凸包为基本包，然后以凸包和模型为基本包。然后，计算位移和位移的凸包。将凸包和位移子视为矩阵，然后以位移和位移子为矩阵。重复周期以空表示sg树的叶子节点。所有中间节点都是“降低”的操作。左左右左协调，右协调，根节点对应于整个模型。3）文本分解方法：首先，b-rep模型划分为一组单元体，然后将相应的单元体构成最大单元，然后使用“并”操作将所有单元体组合形成csg模型。虽然上述算法存在较大差异,但它们都是基于B-Rep模型的边、面、环等基本几何元素确定模型分解策略,未考虑B-Rep模型蕴含的高层特征信息(如孔、凹槽、凸台等),因此转换结果不符合用户的习惯,普遍存在过度分解、可读性不强等问题.罗月童等提出转换特征的概念,并基于扩展属性连接图识别转换特征,然后基于转换特征确定分解B-Rep模型的策略,显著地改进了转换效果;但其仅能处理预定义的转换特征,且需要为每种特征专门设计特征识别算法,导致该算法的可扩展性不强.马露杰等认为多个基本模型进行布尔组合生成新模型时会留下痕迹———新模型的混合区域,因此提出利用混合区域的环分割新模型,并利用面壳封闭技术恢复基本模型,从而实现布尔运算的逆过程,以及模型分解.文献基于“模型组合会留下痕迹”这个观察,无需如文献那样预定义特征,更具普适性;但该文献仅讨论如何将实体模型分解为一组分割体(CSG的基本体元),未考虑如何生成CSG树.本文在文献的基础上提出构建CSG树的算法,进而实现基于面壳封闭的B-Rep至CSG转换算法.1面壳封闭法分解模型基于面壳封闭的B-Rep模型分解方法详见文献.出于论文完整性的考虑,本节对基于面壳封闭的B-Rep模型分解方法进行简要介绍.B-Rep模型中的二次曲面可分为平面、凸曲面和凹曲面,边可分为凸边、凹边和相切边.根据面、边的分类可定义混合区域和切割环:1)混合区域.B-Rep的多个相邻的面所形成的集合称为区域,如果区域中面的凹凸性和边的凹凸性不一致,或者区域中同时存在凹边和凸边,那么称此区域为混合区域.2)切割环、凸切割环、凹切割环.沿着一组封闭环L1,L2,…,Ln将B-Rep模型分割成多个面壳(faceshell,FS)FS1,FS2,…,FSm.如果所有FSi都能通过面壳封闭操作形成封闭实体voli,那么称封闭环L1,L2,…,Ln为切割环,实体voli为分割体.如果构成切割环的所有边都是凸(凹)边,那么称该切割环为凸(凹)切割环.和文献一样,本文仅考虑凹切割环和凸切割环.文献进行B-Rep模型分解过程如下:首先在B-Rep模型M的混合区域中提取所有切割环L1,L2,…,Ln,如图1a所示;然后沿切割环L1,L2,…,Ln将M分割成多个面壳FS1,FS2,…,FSm,如图1b所示;再使用面壳封闭法将FS1,FS2,…,FSm封闭成为分割体(decomposedvolume,DV)DV1,DV2,…,DVm,如图1c所示.虽然文献方法所生成的分割体DV1,DV2,…,DVm可作为CSG模型的基本体元,但缺乏CSG树的信息,不能构成完整的CSG模型,所以本文在文献的基础上进一步改进体关系图(volumerelationgraph,VRG)来表达DV1,DV2,…,DVm之间的关系,并提出基于VRG构建CSG树的算法.在VRG中,每个分割体DVi对应一个节点,每个切割环Lj对应一条无向边(或有向弧).定义1中,DV表示节点v所对应的分割体;OFS(originalfaceshell)表示分割体DV在原始B-Rep模型M上所对应的面壳,如图1b所示;SFS(shrinkingfaceshell)表示收缩e对应的切割环L所形成的面壳,如图1c中黄色表面;w表示e的权重;如果DV面的外法矢量与原始模型面的外法矢量一致,则S为正符号,反之则为负符号;BA(bearc)表示边e是无向边还是有向弧,设置BA的规则如表1所示.2vrg模型生成如果实体模型M的VRG图G的割C(S,T)={ei1,ei2,…}(S和T表示C切割G所形成的2个连通子图)满足:S和T分别表示封闭实体模型MS和MT(满足“可封闭约束”,见第2.2节),且存在O(·)∈{∪,-}使得M=O(MS,MT)(满足“可组合约束”,见第2.2节),则可按下述算法生成CSG模型.输入.VRG图G=(V,E).输出.CSG_TREE的根节点r=(S,O,L,R,DV,BA)./*(说明:S∈{+,-,±}表示实体模型的符号,其中±表示符号未定;DV表示所对应分割体;BA表示所对应的边(或弧)的方向属性;O∈{+,-},L和R分别表示布尔运算符、左孩子节点和右孩子节点;)*?VRG2CSG(G)没有设置CSG树的非叶子节点的运算符,如何设置运算符将在第2.1节中讨论;另外,第2.2节将详细介绍如何生成符合要求的割C(S,T)={ei1,ei2,…}.2.1基于深度优先树遍历算法如果VRG图G=({v1,v2},{e=(v1,v2)})对应的实体模型和CSG树分别为M和T,那么e.BA,v1.S,v2.S,T.O和M.S满足表2所示关系.本文基于深度优先树遍历算法,依据表2设置各非叶子节点的运算符,算法伪代码如下:2.2用于csg树生成的rg分割算法2.2.1c.cv强化k-bs,t问题为保证能正确生成B-Rep模型M的CSG模型,割C(S,T)必须满足可封闭约束和可组合约束,本文称之为硬约束.它们的具体定义如下:1)可封闭约束.对C(S,T)所对应切割环进行封闭时,面壳收缩所形成的面不能与B-Rep模型M相交.C(S,T)的可封闭条件为如图2a所示,对e1所对应封闭环进行封闭操作时,新生成的面会与原始实体模型的蓝色面相交,所以割C({v1},{v2,v3})={e1}不满足可封闭约束.如果选择C({v1},{v2,v3})={e1}分割VRG,那么会生成如图2e所示CSG树,该CSG树对应图2f所示模型,相当于将原始B-Rep模型的蓝色长方体“截去”一段,这显然是错误的.但根据可封闭约束,本文算法会首先选取C({v1,v2},{v3})={e2}分割VRG;在分割所得子图Gsub=({v1,v2},{e1})中,割C({v1},{v2})={e1}也满足可封闭条件,因此可继续分割子图Gsub=({v1,v2},{e1}),最终获得如图2d所示的正确CSG模型.2)可组合约束.C(S,T)={e1,e2,…}是方向一致的,即满足以下条件之一:a.所有边e∈C(S,T)都是无向边,即ue02fe∈C(S,T)→e.BA=false;b.所有边e∈C(S,T)都是有向弧,且弧头顶点属于S,弧尾顶点属于T.如图3c所示,VRG存在3个割:C({v1},{v2,v3})={e1,e2},C({v1,v3},{v2})={e1,e3}和C({v1,v2},{v3})={e2,e3},但后面2个均不满足可组合约束,所以割C({v1},{v2,v3})={e1,e2}将被用于分割VRG.除上述必须满足的约束外,本文还提出2个不是必须满足的约束用于优化CSG树,称之为软约束.具体包括:1)最简分割约束.指一次参与分割的切割环要尽量少,即|C(S,T)|尽量小.因为人们通常倾向于从简单连接处分割模型,所以选择切割环较少的地方分解模型更符合人的习惯.2)最佳平衡约束.指要求由C(S,T)所生成CSG树比较平衡.平衡度其中|S|表示集合S中元素的个数.2.2.2硬约束和软约束本文依据计算VRG边的权和割C(S,T)的容量,从而将通过最小割生成算法解决上述硬约束问题,并同时尽量满足软约束.Stoer-Wagner算法由Stoer等于1997年提出,是目前最常用的最小割算法之一.本文基于Stoer-Wagner算法分割VRG以生成CSG模型,并证明最小割算法的结果能同时体现硬约束和软约束.1)硬约束.如果割C(S,T)不满足任何一个硬约束,那么由式(1)(2)可知w(C)=∞,则显然C(S,T)不会作为最小割被输出.2)软约束.Stoer-Wagner算法输出最小割,结果自然体现最简分割条件;另外,通过简单改造StoerWagner算法中的最小割更新策略,即可体现最佳平衡条件.Stoer-Wagner算法基于以下定理:对任何带权无向图G=(V,E),G的全局最小割是G的s-t最小割(s,t∈V)或G?{s,t}的全局最小割,其中G?{s,t}表示通过合并s和t节点所得新图.本文基于StoerWagner算法提出求解C(S,T)的算法,算法伪代码如下:1)合并s,t顶点:G←G/(s,t)将顶点s和t,以及连接到s和t的所有边从图G中移除,然后加入新顶点v′,之后按下列策略在ue420v∈V-{s,t}和v′间添加新边(v′,v):3mcam中的热变形模型本文采用VisualC++和三维实体几何引擎ACIS实现上述算法,并将这些算法集成到中国科学院FDS团队自主研发的多物理耦合分析自动建模软件(multi-physicscouplinganalysismodelingprogram,MCAM)中.MCAM软件已在40多个国家200多个知名科研与设计机构获得应用,成为核能领域的重要建模软件.MCAM的核心功能之一是将三维CAD模型(采用B-Rep表示方法)转换到粒子输运程序(如SuperMC,MCNP,PHITS,Geant4,FLUKA,TRIPOLI等)的输入文件(采用CSG表示方法).之前,MCAM采用基于半空间的B-Rep至CSG转换算法,现在首先使用本文算法构建初步CSG模型,然后对CSG模型的每个叶子节点应用基于半空间的B-Rep至CSG转换算法,进一步提升了MCAM软件的性能.下面将通过典型零件和国际热核聚变实验堆(internationalthermonuclearexperimentalreactor,ITER)(1)的基准模型展示本文算法的性能.3.1面壳封闭法表3所示为对2个典型零件的半空间分解结果、面壳封闭分解结果和采用不同最佳平衡约束参数时生成的CSG树,可以看出,面壳封闭法能产生更好的分解结果,通过使用最优平衡约束能让所得CSG树更平衡.3.2基准模型的优化ITER由中国、欧盟、俄罗斯、美国、日本、印度和韩国合作在法国建造,用于研究热核聚变反应堆的关键技术.ITER基准模型包含3000多个形状复杂的实体模型(如图4所示),是ITER国际组织用来评估开展核分析的基准模型.表4所示为本文算法对ITER基准模型中部分典型零件的优化效果.图5所示为使用本文算法优化前后部分ITER基准模型零件的转换时间的对比,可以看出,本文算法对多数零件能提高速度,但对少量零件却出现时间性能下降的情况,这是因为这些零件无法使用面壳收缩方法进行分解,却额外增加了试图进行面壳分解的操作.整体而言,本文算法对MCAM的时间性能改进并不显著,但这不影响该算法在MCAM中的应用价值,因为随着计算机性能的不断发展,用户已不太关心速度,而是主要关注转换结果的可读性,这也正是本文算法的优势之处.4带权不等于不同活动区域的s-t割B-Rep至CSG转换算法具有重要的理论意义和实用价值,本文在文献提出的基于面壳封闭的B-Rep模型分解方法的基础上,进一步实现基于面壳封闭的B-Rep至CSG转换算法.主要贡献如下:1)针对B-Rep至CSG转换问题改进VRG;2)提出VRG边权重及割容量的计算方法,将基于VRG生成CSG树的问题转换为求解最小割问题,并基于Stoer-Wagner算法实现;3)将本文算法集成进入自主研发的MCAM软件中,进行了推广应用.实际应用表明,本文算法对某些模型不但不能起到优化效果,而且会增加额外计算开销,下一步我们将探讨如何快速判断给定B-Rep模型是否适用本文算法;另外,我们今后还将考虑增加更多软约束(如面的类型等信息),以进一步优化转换结果.如果(s,v),(t,v)相对割C(V-{s,t},{s,t})的方向一致,那么(v′,v).w=(s,v).w+(t,v).w,(v′,v).BA←(s,v).BA,否则(v′,v).w=∞.2)体现软约束:Update(C(S,T),C′(S′,T′))本文基于s-t割的更新策略体现软约束,策略如下:如果C(S,T)和C′(S′,T′)的容量均小于给定阈值K,那么从C(S,T)和C′(S′,T′)选择平衡度更高的割(满足最佳平衡约束),否则选取容量较小的割(满足最简分割约束).3)正确性证明Stoer-Wagner算法是一种求解带权无向图最小割的算法,但VRG的部分边具有方向,所以进行正确性证明,即证明CutForCSGPhase(G,C′(S′,T′))能生成最小s-t割.设在函数CutForCSGPhase中顶点按v1,v2,…,vn,s,t顺序依次加入A,Av表示在v之前加入A的所有顶点,C(S,T)表示图G任意s-t割,那么Cv=C∩{(u,v)|u,v∈(Av