一种几何网格模型邻接拓扑关联的层切多连通域构建方法

技术领域

本发明涉及先进制造技术领域的复杂机械零件几何模型处理方法，尤其是涉及了增材制造领域几何网格模型的层切多连通域构建方法。

背景技术

3D打印(3D Printing)可实现快速成型(Rapid Prototyping，RP)，是通过逐层增加材料来得到零件，能够直接从CAD实体数据几何模型生成零件模型，其显著优点是可以成型复杂形状零件，在复杂型腔模具、生物医学及雕刻曲面等领域得到日渐广泛的应用。在快速成型工艺中，对零件的CAD几何模型进行分层处理是关键技术。分层处理是用一系列的层切平面与三维实体的数据模型进行截交，获取各层的二维截面轮廓信息，以便获得截面内的连通域并进行填充。通常多边形的方向确定为：沿逆时针方向为正方向，沿顺时针方向为负方向。模型截面轮廓必须满足封闭性和无自交性的要求。封闭网格每个顶点至少有3个邻接顶点，每个网格面片有3个邻接网格面片。存在邻接公共边的两个面片为邻接网格面片。封闭性是指轮廓线的起点和终点重合，对封闭连通域，可用有向面积、面积矩进行封闭性验证。传统方法通常采用共端点判别是否封闭，但存在共端点误判别、有序化成环难、不同步成环的弊端。因此，层切多连通域的构建效率和精度直接影响着增材制造的效率、质量和精度。

三维零件的数据模型有三维零件原生格式和简化的三维零件格式两种。目前，三维零件的原生数据格式主要有基于Parasolid和ACIS几何模型。三维零件格式包含拓扑信息，具有精度高的优点，但存储空间大、计算效率低、共用性差，限制了3D打印的广泛应用。简化的三维零件格式是用几何网格模型描述原生模型，用许多网格面片来逼近模型的表面，主要包括STL文件格式、OBJ文件格式、PLY文件格式、VTK文件格式、WRL文件格式等。基于几何网格模型的分层处理算法通过层切平面与STL(Stereo Litbography)等文件格式模型的三角面片求交，然后将求得的交点连接成一个或多个封闭的轮廓线，得到层切平面的截面轮廓信息。三角面片与层切平面求交时，需要遍历所有的面片，一个复杂的零件模型往往有几万，甚至几百万个面片，将会非常耗时。而且，对求得交点的连接方法会影响截面轮廓的精度。内角接近0°,180°,360°的顶点，通常被称作多边形的奇异顶点。简单多面体表面亏格(Genus)为零，对于亏格不为零的物体，内部存在着多重空洞，其截面轮廓为复合环构成的多连通域，含有奇异顶点时，正方向判断尚存在许多难题。因此，有些学者针对这些问题提出了一些改进的分层切片算法，例如，Ratnadeep Paul等于2015年在《Computer-Aided Design》(63(2015)：第86-100页)的论文“A new Steiner patch based file format for Additive Manufacturing processes”中提出了一种新的模型文件格式，使用曲面Steiner图形来近似表达模型的表面，提高了分层切片的精度。A.Guerrero-de-Mier等于2015在《Procedia Engineering》(132(2015)：第126-131页)的论文“Bricking:A new slicing method to reduce warping”中提出了减小制品翘曲的层切方法。John C.Steuben等于2015年在《Computer-Aided Design》(77(2016)：第107-119页)的论文“Implicit slicing for functionally tailored additive manufacturing”中提出了一种基于计算输入形状的生成路径的隐式切片算法，用来计算平面任意复杂的几何形状截面。

但是，这些方法仍有一些局限性，尤其是对内外表面形态复杂多变的形体的分层切片方面，在效率和精度上都存在问题。已有切片商业软件难以解决二维截切面形状含有奇异点的难题，在截面形状的奇异点处有轮廓信息丢失，难以完整的表达复杂模型的实际截面轮廓。

发明内容

为了解决背景技术中存在的问题，为了使得对几何网格模型的分层切片处理更加鲁棒，得到的截面轮廓精度更高，本发明的目的在于提供了一种几何网格模型邻接拓扑关联的层切多连通域构建方法。针对于机械产品的复杂机械零件的几何网格模型层切，实现含孤立多连通域零件的精度均衡的层切处理，具有鲁棒高效与精度均衡的优势。

为了实现上述目的，如图1所示是本发明方法流程总图，本发明采用的技术方案的步骤如下：

第一步：根据全局容差精度要求、打印喷头尺寸、分层效率要求和耗材要求设定全局数值计算阈值；

第二步：载入零件的几何网格模型，求解几何网格模型点云的凸包围盒，获得凸包围盒的八个顶点；

第三步：根据模型的表面形状和精度要求确定分层方向和坐标变换矩阵，将模型直角坐标系变换到分层直角坐标系；

第四步：确定分层厚度，以分层方向作为层切平面增加方向，构建几何网格模型的层切平面集合Z；

第五步：预分块所有网格面片，先确定各层切平面上与层切平面相交的网格面片集合M，再针对各层切平面，构建索引链表存储相交网格面片集合M；

第六步：建立网格面片之间的局部邻接拓扑关系，构建各层切平面的相交网格面片集M的邻接拓扑链表，获得一个或多个由依次衔接的相交网格面片组成的网格面片环，求取网格面片环中的每相邻两个网格面片之间的公共邻接边；

第七步：沿层切平面上各网格面片环的正方向，求解各层切平面与公共邻接边的交点；

第八步：对每一层切平面得到的交点集，按各网格面片环的邻接关系进行交点有序化连接，得到一个或多个截面轮廓环，由截面轮廓环形成连通域，得到模型的全部截面连通域。

所述的几何网格模型是封闭且无自交的，并且不存在法向量错误、相邻面片不共顶点、顶点分离、重叠面片和孤立面片。

所述的全局数值计算阈值是指模型尺寸和坐标的精度值，全局数值计算阈值适用于几何网格模型的凸包围盒求解、层切坐标系几何变换、层切平面区块划分和邻接拓扑关联面片的公共邻接边与层切平面求交。

本方法采用一种基于模型凸包围盒体对角线测度的成比例精度控制方法，动态设定全局数值计算阈值。所述的全局数值计算阈值是指模型尺寸和坐标的精度值，作为两个坐标点之间坐标误差的衡量，全局数值计算阈值用于第三步中坐标系变换。

对于坐标系变换，具体来说是在将模型直角坐标系变换到分层直角坐标系后通过全局数值计算阈值，调整数值计算精度。

所述的预分块网格面片具体是：先对几何网格模型所有网格面片以分层方向坐标进行升序排序，再按层切平面的层切方向坐标作为边界对所有的网格面片进行同步直接分块，使得所有网格面片处于不同区块，确定每个网格面片所属区块，从而确定每个网格面片的相交层切平面，最终得到每一个层切平面的相交网格面片集，将各个层切平面的相交网格面片集存储在索引链表中。

所述的所有网格面片以分层方向坐标进行升序排序，是指根据每个网格面片顶点中，沿分层方向所在坐标轴的最小值z_min和最大值z_max对所有的网格面片进行排序，对于不同的网格面片，最小值z_min小的排在前面，当最小值z_min相等时，则最大值z_max小的排在前面。

所述按层切平面为边界对所有的网格面片进行分块划分，使得所有网格面片归属于不同区块具体是通过网格面片的顶点中沿分层方向所在坐标轴的最小值z_min和最大值z_max进行判断：

若最小值z_min和最大值z_max均位于相邻区块边界之间，即z_min>z_i&z_max<z_i+1，则网格面片不与任何层切平面相交，为保证模型处理精度，减少相邻两层切平面之间的间隔d重新构建几何网格模型的层切平面集合Z；

若最小值z_min和最大值z_max之间有一条区块边界，网格面片位于两相邻区块上，即只有一个层切平面，也即z_i-1<z_min<z_i≤z_max或z_min≤z_i<z_max<z_i+1，则该网格面片与该层切平面相交，并归属于该层切平面；

若最小值z_min和最大值z_max之间有多条区块边界，网格面片位于多个相邻区块上，即含有多个层切平面，也即z_min≤z_i、…、z_i+u≤z_max，则该网格面片与这几个层切平面都相交，并均归属于这几个层切平面；

若最小值z_min和最大值z_max相同，即z_min＝z_max，则该网格面片不归属于任何层切平面。

所述的网格面片环的正方向是指各层切平面的相交网格面片构成的面片环带的正方向，具体规则为：模型外表面的网格面片的面片环，以逆时针方向为正；模型内表面的网格面片的面片环，以顺时针方向为正。

本发明具有的有益效果是：

1.本发明提出的预分块网格面片，以层切平面作为分层区块边界进行直接划分，可避免网格面片与层切平面位置关系的多次判断，减少了判断次数，先对所有网格面片进行排序，可减少网格面片遍历所需的时间，有效地提高了分层处理的效率。

2.本发明提出的网格面片邻接拓扑关联，可将分区块存储的面片的邻接拓扑关系进行关联，同步对离散的交点集进行有序化成环，避免交线段之间的排序连接和共端点判别，解决含奇异点的复杂多边形的成环，有助于实现复杂几何网格模型的鲁棒高效与精度均衡的几何层切。

附图说明

图1是本发明方法流程总图。

图2是本发明的3D坐标层切平面创建示意图。

图3是本发明的预分块网格面片的示意图。

图4是本发明的层切平面相交网格面片索引链表示意图。

图5是本发明的实例几何网格模型示意图。

图6是本发明的实例模型某一层切平面的相交网格面片集示意图。

图7是本发明的实例模型某一层切平面的截面连通域示意图。

图8是本发明的实例模型全部层切平面的截面轮廓示意图。

具体实施方式

以下结合附图和实例对本发明作进一步的详细描述。

本发明实施例如下：

如图2所示，是本发明构建的3D坐标层切平面创建示意图。图2所示的创建层切平面的步骤为：

第一步：载入零件的几何网格模型，同步获得几何网格模型原坐标系O′-x′y′z′，获得模型所有网格面片顶点集合V‘，以点云V‘创建长方体凸包围盒，并求出包围盒的沿正方向的底面顶点P‘₂,P‘₄,P‘₆,P‘₈及顶面顶点P‘₁,P‘₃,P‘₅,P‘₇；

第二步：设置计算阈值ε，计算包围盒中心坐标x_c＝(P‘₁.x+P‘₅.x)/2，y_c＝(P‘₁.y+P‘₃.y)/2，z_c＝(P‘₁.z+P‘₂.z)/2，计算原始几何网格模型的三个主方向其中，

第三步：由模型表面形状和精度要求，令分层方向为z方向，分层方向可与原始几何网格模型的三个主方向成任意角度，据此确定旋转变换矩阵；

第四步：求解包围盒八个顶点中，沿分层方向坐标值最小的面的中心点，以此中心点为原点O构建一个使包围盒处于第一卦限的新坐标系，即分层坐标系O-xyz，据此确定比例变换和平移变换矩阵；

第五步：将原模型的点云坐标转换为分层坐标系下新坐标：

V＝V‘*T

其中，V表示在分层坐标系下模型的坐标点集，T为坐标变换矩阵，包含了比例变换矩阵、平移变换矩阵和旋转变换矩阵。

第六步：根据变换后点云V的z坐标的最大和最小值，求解包围盒的z方向高度，即z_stroke＝z_max-z_min，根据精度要求，确定第i层切平面的层高z_i,0≤z_i≤z_stroke，i＝1,2,3,…,n，可得第i层切片的厚度d_i，即相邻层切平面之间的间距，同理可求x_stroke,y_stroke，确定分层行程；

第七步：创建分层切平面，以变换后点云V的包围盒底面作为初始层切平面Ω₁，其中P₂＝(x₂，y₂，z₂),P₄＝(x₄，y₄，z₄),P₆＝(x₆，y₆，z₆)，层切平面Ω₁方程用行列式表示为：

以此创建全部层切平面，形成层切平面集Ω。

如图3所示，是本发明的预分块网格面片的示意图。n个层切平面把模型的网格面片划成n-1块区域，不同的网格面片所属区块不同。根据网格面片所属的区块，就可以判断每个网格面片跟哪些层切平面Ω_i相交，进而可知各个层切平面的相交网格面片集合。图中D_i表示被层切平面划分的区块，z_i表示层切平面Ω_i的高度。其步骤为：

首先根据每个网格面片j(j＝1,2,…,)的z坐标的最小值z_j,min和最大值z_j,max，对所有的网格面片进行快速的升序排序。对于不同的网格面片，z_j,min值小的排在前面，当z_j,min相等时，则z_j,max较小的排在前面。

判断每个网格面片所属的区块，具体规则为：若网格面片的z_j,min与z_j,max处于区块边界内(图3中网格面片2，网格面片2处于区块D₂内)，即z_2,min>z₂&z_2,max<z₃，则此网格面片不与任何层切平面相交，对于此类网格面片，为保证模型的特征完整性，可对切片厚度d_i进行适当调整。

若网格面片位于多个区块，则网格面片与这些区块内的层切平面相交(图3中网格面片1与网格面片3，网格面片1处于区块D₁和D₂上，网格面片3处于区块D_i-1、D_i和D_i+1上)，即z₁<z_1,min<z₂<z_1,max<z₃、z_i-1<z_3,min<z_i<z_i+1<z_3,max<z_i+2，则网格面片1与层切平面Ω₂相交，网格面片3与层切平面Ω_i、Ω_i+1相交，与网格面片相交的层切平面Ω_i的高度z_i应满足z_min≤z_i≤z_max；若网格面片的z坐标的z_min和z_max相等，即网格面片与层切平面共面(图3中网格面片4)，即z_4,min＝z_4,max，则不记录此类网格面片，即该网格面片不与任何层切平面相交。

沿分层方向的坐标，对几何网格面片进行升序排序，由前至后，遍历每一个网格面片，确定各网格面片所属区块。因为网格面片是升序的，在遍历到相交网格面片时，排在后面的网格面片可避免再次跟位置低的层切平面进行位置关系判别，具体为：对于某个网格面片，若其顶点的z_min大于区块边界z_i，则此网格面片及其之后的网格面片一定不会位于区块边界z_i下面的区块，即不会与下面的区块内的层切平面相交。

如图4所示，是本发明的层切平面相交网格面片索引链表示意图。

预分块模型的所有网格面片，遍历完所有的网格面片，确定各网格面片的所属区块，进而得到各层切平面的相交网格面片集M，定义一个索引链表用来存储每一个层切平面的相交网格面片集M，图4左边表示各个层切平面，右边表示存储的对应的具有邻接拓扑关系的相交网格面片集M，由于有些网格面片的沿分层方向坐标差z_j,h＝z_j,max-z_j,min≥2d_i，会位于多个层切平面，因此相邻层切平面可能会存储同一个网格面片。

对于索引链表中每一个层切平面存储的相交网格面片集，建立网格面片之间的局部邻接拓扑关系，由于模型本身的特性，同一相交网格面片集中，可能会出现无邻接关系的网格面片，这时候就会有多个环状局部邻接网格面片集(图4中Loop)。环状的邻接网格面片集构成一个环状网格面片带，这个环状网格面片带就是网格面片环，求取网格面片环中的每相邻两个网格面片之间的公共邻接边，使网格面片环和层切平面相交线段形成一个或多个封闭的环。

如图5所示，是本发明的实例几何网格模型示意图。实例几何网格模型含有复杂曲面，沿分层方向截切面内均含有奇异点，长度单位均为mm。几何网格模型网格面片数:1662；顶点数:833；体积：173631；表面积：27507。几何网格模型的凸包围盒顶点坐标为：

P₁＝(190.3813,98.9270,51.8706)；P₂＝(190.3813,98.9270,0.0000)；

P₃＝(190.3813,34.1787,51.8706)；P₄＝(190.3813,34.1787,0.0000)；

P₅＝(89.0301,98.9270,51.8706)；P₆＝(89.0301,98.9270,0.0000)；

P₇＝(89.0301,34.1787,51.8706)；P₈＝(89.0301,34.1787,0.0000).

模型的包围盒顶点的坐标极值：[x_min,x_max,y_min,y_max,z_min,z_max]＝89.0301,190.3813,34.1787,98.9270,0.0000,51.8706。包围盒中心坐标为：139.7057,66.5528,25.9353。所需的分层行程空间[x_stroke,y_stroke,z_stroke]为:101.3513,64.7483,51.8705。

几何网格模型的最大平均曲率0.6538，最小平均曲率0.0012，平均平均曲率0.0481，最大高斯曲率0.0253，最小高斯曲率0.0000，平均高斯曲率0.0017，最大第一曲率0.1347，最小第一曲率0.0000，平均第一曲率0.0157，最大第二曲率1.2899，最小第二曲率0.0023，平均第二曲率0.0805。由此可见，原始几何网格模型是一个具有复杂内外曲面形状的空间网格体。

如图6所示，是本发明的实例模型某一层切平面的相交网格面片集示意图。层高z＝0.83*z_stroke，构建该层相交网格面片集的邻接拓扑关联矩阵，获得每个面片环中的相邻网格面片间的公共邻接边，沿环的正方向对每一公共邻接边与层切平面求交点，几何求交点计算公式为：

其中，(v₁.x，v₁.y，v₁.z)、(v₂.x，v₂·y，v₂.z)为网格面片顶点v₁、v₂的坐标值，所得(x,y,z)∈Ω。取任意网格面片开始，按网格面片的拓扑邻接关系，按环的正方向，对公共邻接边与层切平面依次求交点，顺序化连接各交点获得当前环，继续求解复合环中其余各环交点，获得有序化与成环的封闭截面轮廓。

如图7所示，是本发明的实例模型某一层切平面的截面连通域示意图，是一个含有孤立连通域的多连通域截面轮廓。环具有封闭性、有向性、不交性和相互包含性。从内到外判断相互直接包含性，空集由环的直接包含性可判断环的间接包含性，由此确定每个连通域。第1个环L₁的交点数为150，第2个环L₂的交点数为49，第3个环L₃的交点数为17。每个封闭环的首尾点是重合的。连通域A₁由环L₁和L₂组成，即连通域A₁＝L₁∪L₂，连通域A₂由环L₃组成，即连通域A₂＝L₃。

如图8所示，是本发明的实例模型全部层切平面的截面轮廓示意图，共20层，每层截面有1个或多个连通域。第1层截面，环Loop1组成的连通域几何中心为(142.1927,63.9727)，面积为3459.85；第2层截面，环Loop1组成的连通域几何中心为(141.6093,64.5013)，面积为3467.14；第3层截面，环Loop1组成的连通域几何中心为(140.9803,65.0208)，面积为3481.13；第4层截面，环Loop1组成的连通域几何中心为(140.4745,65.5290)，面积为3481.34；第5层截面，环Loop1组成的连通域几何中心为(139.9452,66.0362)，面积为3499.68；第6层截面，环Loop1组成的连通域几何中心为(139.4840,66.5113)，面积为3504.83；第7层截面，环Loop1组成的连通域几何中心为(139.0948,66.9678)，面积为3517.06；第8层截面，环Loop1组成的连通域几何中心为(138.6933,67.4093)，面积为3537.14；第9层截面，环Loop1组成的连通域几何中心为(138.4911,67.8043)，面积为3541.67；第10层截面，环Loop1组成的连通域几何中心为(138.2461,68.1798)，面积为3564.08；第11层截面，环Loop1组成的连通域几何中心为(138.1610,68.5170)，面积为3570.01；第12层截面，环Loop1组成的连通域几何中心为(138.1439,68.8240)，面积为3586.07；第13层截面，环Loop1组成的连通域几何中心为(138.1593,69.0983)，面积为3603.31；第14层截面，环Loop1组成的连通域几何中心为(138.3915,69.3201)，面积为3609.75；第15层截面，环Loop1组成的连通域几何中心为(138.5647,69.5160)，面积为3631.70；第16层截面，外环Loop1组成的连通域几何中心为(138.9609,69.6630)，面积为3631.03，内环Loop2组成的连通域几何中心为(130.0807,73.7154)，有向面积为-281.46；第17层截面，外环Loop1组成的连通域几何中心为(139.3795,69.7999)，面积为3651.15，内环Loop2组成的连通域几何中心为(122.8425,73.7921)，有向面积为-626.51，内环Loop3组成的连通域几何中心为(122.0422,74.2001)，面积为78.56；第18层截面，外环Loop1组成的连通域几何中心为(139.8564,69.8850)，面积为3655.31，内环Loop2组成的连通域几何中心为(123.3492,73.5932)，有向面积为-628.34，内环Loop3组成的连通域几何中心为(122.5437,74.0003)，面积为78.16；第19层截面，外环Loop1组成的连通域几何中心为(140.4715,69.9459)，面积为3665.33，内环Loop2组成的连通域几何中心为(124.0450,73.3149)，有向面积为-631.31，内环Loop3组成的连通域几何中心为(123.2263,73.7245)，面积为79.33；第20层截面，外环Loop1组成的连通域几何中心为(134.1448,70.0829)，面积为3080.13，内环Loop2组成的连通域几何中心为(124.3270,73.2070)，有向面积为-632.26，内环Loop3组成的连通域几何中心为(123.4997,73.6141)，面积为79.14。

由此可见，本发明方法通过预分块减少了层切平面与网格面片位置的判断次数；避免出现网格面片与层切平面位置关系的无效判断；将网格面片的邻接拓扑关系进行关联，实现了交点的高效有序化成环，避免对交点进行排序；解决了含奇异点的复杂多边形环的求交难题，技术效果显著突出，实现了几何网格模型邻接拓扑关联的层切多连通域构建。

上述具体实施方式用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。