专利摘要

本发明涉及一种避免轮廓相交的快速成型切片处理方法，其步骤如下：步骤一、根据成型精度确定层高和切片总数，并获取各层切片平面与STL模型上每个三角面片的交点；步骤二、将每层切片内的交点集合映射为一个图G，并确定图G的极大连通子图Gi；步骤三、获取每个连通子图Gi中的节点度数，并根据节点度数特性识别轮廓相交情况，创建有序封闭轮廓；步骤四、利用每层切片得到的轮廓建立打印封闭区域，并与相邻切片层的区域进行布尔运算以对打印区域进行修正。本发明利用图的节点度数特性，智能识别切片轮廓相交情况，避免了网格拓扑关系的复杂计算，能够有效去除多余轮廓分支，建立正确的打印区域，适用于各种规则和非规则模型的切片处理。

权利要求

1.一种避免轮廓相交的快速成型切片处理方法，其特征在于，其步骤如下：

步骤一、根据成型精度确定层高和切片总数，并获取各层切片平面与STL模型上每个三角面片的交点；

步骤二、将每层切片内的交点集合映射为一个图G，并确定图G的极大连通子图Gi；

步骤三、获取每个连通子图Gi中的节点度数，根据节点度数特性识别轮廓相交情况，并根据轮廓相交情况采用深度优先搜索算法或三角剖分方法创建有序封闭轮廓；

步骤四、利用每层切片得到的轮廓建立打印封闭区域，并与相邻切片层的区域进行布尔运算以对打印区域进行修正。

2.根据权利要求1所述的一种避免轮廓相交的快速成型切片处理方法，其特征在于，步骤二中，对于每层切片求得的交点集合，首先进行冗余点去除，获得节点集合V，然后根据每个三角面片上的两个交点构成一条边的特性将节点集合V映射为一个图G＝(V，E)，其中E为节点集合V中的节点构成的所有边集，对图G进行深度优先遍历，得到图G的极大连通子图Gi，i＝1，2，3，...，n，n为连通分量总数。

3.根据权利要求1所述的一种避免轮廓相交的快速成型切片处理方法，其特征在于，所述步骤三中节点度数特性包括：①连通子图Gi中所有节点的度数都≤2；②连通子图Gi中存在一个节点v的度数deg(v)＞2，其中节点v的度数deg(v)定义为与v关联的所有边的数目总和。

4.根据权利要求3所述的一种避免轮廓相交的快速成型切片处理方法，其特征在于，当连通子图Gi中所有节点的度数都≤2时，采用深度优先搜索算法创建有序封闭轮廓，首先从子图Gi中的某一节点v0出发，搜索与它关联的邻接节点v1，然后从节点v1出发，搜索与v1邻接且未被访问过的节点v2，依次进行搜索，直到回到起点v0，即创建一条有序封闭轮廓。

5.根据权利要求3所述的一种避免轮廓相交的快速成型切片处理方法，其特征在于，当连通子图Gi中存在一个节点v的度数deg(v)＞2时，采用三角剖分方法创建有序封闭轮廓。

6.根据权利要求5所述的一种避免轮廓相交的快速成型切片处理方法，其特征在于，所述三角剖分方法如下：

Step1，将连通子图Gi内的所有节点利用Delaunay三角剖分方法构建一个三角网格DT；

Step2，搜索三角网格DT的边界集合Boundary，边界边按照如下规则定义：Boundary＝{<vi，vj>|Dep<vi，vj>＝1}，其中<vi，vj>代表三角网格DT中由节点vi、vj构成的边，Dep<vi，vj>为依附于边<vi，vj>的三角形的个数，当Dep<vi，vj>＝1时，<vi，vj>为边界边，vi、vj为边界节点；

Step3，判断边界集合Boundary中的每一条边<vi，vj>是否属于连通子图Gi的边集Ei，①若存在将与该边<vi，vj>相连的三角形删除，更新三角网格DT后，转Step2；②若不存在直接转Step4；

Step4，依次连接三角网格DT的边界节点即为连通子图Gi内的有序封闭轮廓。

7.根据权利要求1所述的一种避免轮廓相交的快速成型切片处理方法，其特征在于，步骤四中包括以下步骤：

Step1，在每层切片内，根据各个封闭轮廓之间的内外包含关系建立多边形封闭区域；

Step2，获取第i层切片的封闭区域Ai与第i+j层切片的封闭区域Ai+j的差集d1j＝Ai-Ai+j，j＝1，2,...，N，并求出它们的并集：获取第i层切片的封闭区域Ai与第i-j层切片的封闭区域Ai-j的差集d2j＝Ai-Ai-j，j＝1，2,...，N，并求出它们的并集：

Step3，将区域Si＝d1∪d2作为物体第i层切片的表层打印区域，区域Ti＝Ai-Si作为物体第i层切片的内部打印区域。

说明书

技术领域

本发明涉及快速成型领域，具体涉及一种避免轮廓相交的快速成型切片处理方法。

背景技术

快速成型，又称为3D打印或增材制造，是一种以数字模型文件为基础，通过逐层累积堆叠材料来构造物体的技术。在打印加工前，首先需沿三维模型的成型方向建立一系列切片，以提取模型的截面轮廓，然后根据截面轮廓生成打印填充区域。目前已有的针对STL模型进行切片处理的算法主要分为两大类：

1)基于点的处理方法.首先计算层切平面与模型上所有三角片的交点，然后对交点进行排序以构成有序封闭轮廓，例如文献1(田仁强，张义飞.快速成型中STL模型直接切片新算法研究[J].机床与液压，2019，47(16)：55-59)；

2)基于三角片的处理方法.首先求得层切平面与第一个三角片的交点，然后根据拓扑关系找到与之相邻的三角片，依次求交后即可得到首尾相连的有向封闭轮廓，例如文献2(徐敬华，盛红升，张树有，等.基于邻接拓扑的流形网格模型层切多连通域构建方法[J].计算机辅助设计与图形学学报.2018，30(1)：180-190)。

无论是传统的基于点的方法还是基于三角片的方法，都是在构建成一条有序封闭轮廓后，进行下一条轮廓的创建；但当同一层切片内的多条轮廓相交时，会造成排序结果混乱。因此，改善分层切片算法的有效性和准确性，对于提高快速成形系统的可靠性和制作精度具有重要意义。

发明内容

针对现有技术存在的不足，本发明的目的在于提供一种避免轮廓相交的快速成型切片处理方法。

为实现上述目的，本发明提供了如下技术方案：

一种避免轮廓相交的快速成型切片处理方法，其步骤如下：

步骤一、根据成型精度确定层高和切片总数，并获取各层切片平面与STL模型上每个三角面片的交点；

步骤二、将每层切片内的交点集合映射为一个图G，并确定图G的极大连通子图Gi；

步骤三、获取每个连通子图Gi中的节点度数，根据节点度数特性识别轮廓相交情况，并根据轮廓相交情况采用深度优先搜索算法或三角剖分方法创建有序封闭轮廓；

步骤四、利用每层切片得到的轮廓建立打印封闭区域，并与相邻切片层的区域进行布尔运算以对打印区域进行修正。

所述步骤二中，对于每层切片求得的交点集合，首先进行冗余点去除，获得节点集合V，然后根据每个三角面片上的两个交点构成一条边的特性将节点集合V映射为一个图G＝(V，E)，其中E为节点集合V中的节点构成的所有边集，对图G进行深度优先遍历，得到图G的极大连通子图Gi，i＝1，2，3，...，n，n为连通分量总数。

所述步骤三中节点度数特性包括：①连通子图Gi中所有节点的度数都≤2；②连通子图Gi中存在一个节点v的度数deg(v)＞2，其中节点v的度数deg(v)定义为与v关联的所有边的关联数目总和。

当连通子图Gi中所有节点的度数都≤2时，采用深度优先搜索算法创建有序封闭轮廓，首先从子图Gi中的某一节点v0出发，搜索与它关联的邻接节点v1，然后从节点v1出发，搜索与v1邻接且未被访问过的节点v2，依次进行搜索，直到回到起点v0，即创建一条有序封闭轮廓。

当连通子图Gi中存在一个节点v的度数deg(v)＞2时，采用三角剖分方法创建有序封闭轮廓。

所述三角剖分方法如下：

Step1，将连通子图Gi内的所有节点利用Delaunay三角剖分方法构建一个三角网格DT；

Step2，搜索三角网格DT的边界集合Boundary，边界边按照如下规则定义：Boundary＝{<vi，vj>|Dep<vi，vj>＝1}，其中<vi，vj>代表三角网格DT中由节点vi、vj构成的边，Dep<vi，vj>为依附于边<vi，vj>的三角形的个数，当Dep<vi，vj>＝1时，<vi，vj>为边界边，vi、vj为边界节点；

Step3，判断边界集合Boundary中的每一条边<vi，vj>是否属于连通子图Gi的边集Ei，①若存在 将与该边<vi，vj>相连的三角形删除，更新三角网格DT后，转Step2；②若不存在 直接转Step4；

Step4，依次连接三角网格DT的边界节点即为连通子图Gi内的有序封闭轮廓。

所述步骤四中包括以下步骤：

Stepl，在每层切片内，根据各个封闭轮廓之间的内外包含关系建立多边形封闭区域；

Step2，获取第i层切片的封闭区域Ai与第i+j层切片的封闭区域Ai+j的差集d1j＝Ai-Ai+j，j＝1，2，...，N，并求出它们的并集： 获取第i层切片的封闭区域Ai与第i-j层切片的封闭区域Ai-j的差集d2j＝Ai-Ai-j，j＝1，2，...，N，并求出它们的并集：

Step3，将区域Si＝d1∪d2作为物体第i层切片的表层打印区域，区域Ti＝Ai-Si作为物体第i层切片的内部打印区域。

本发明的有益效果：利用图的节点度数特性，智能识别切片轮廓相交情况，避免了网格拓扑关系的复杂计算，能够有效去除多余轮廓分支，建立正确的打印区域，适用于各种规则和非规则模型的切片处理。

附图说明

图1为本发明的技术流程示意图。

图2a、b、c、d为本发明的三角剖分交点排序示意图。

图3a、b、c、d、e、f、g为本发明和现有方法处理切片轮廓相交的实例效果图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明公开了一种避免轮廓相交的快速成型切片处理方法，其步骤如下：

步骤一、根据成型精度确定层高和切片总数，并获取各层切片平面与STL模型上每个三角面片的交点；

步骤二、将每层切片内的交点集合映射为一个图G，并确定图G的极大连通子图Gi；

步骤二中，对于每层切片求得的交点集合，首先进行冗余点去除，获得节点集合V，然后根据每个三角面片上的两个交点构成一条边的特性将节点集合V映射为一个图G＝(V，E)，其中E为节点集合V中的节点构成的所有边集，对图G进行深度优先遍历，得到图G的极大连通子图Gi，i＝1，2，3，...，n，n为连通分量总数。

步骤三、获取每个连通子图Gi中的节点度数，根据节点度数特性识别轮廓相交情况，并根据轮廓相交情况采用深度优先搜索算法或三角剖分方法创建有序封闭轮廓；

步骤三中节点度数特性包括：①连通子图Gi中所有节点的度数都≤2；②连通子图Gi中存在一个节点v的度数deg(v)＞2，其中节点v的度数deg(v)定义为与v关联的所有边的数目总和。

当连通子图Gi中所有节点的度数都≤2，表示该连通子图内不存在轮廓相交情况。采用深度优先搜索算法创建有序封闭轮廓，首先从子图Gi中的某一节点v0出发，搜索与它关联的邻接节点v1，然后从节点v1出发，搜索与v1邻接且未被访问过的节点v2，依次进行搜索，直到回到起点v0，即创建一条有序封闭轮廓。

当连通子图Gi中存在一个节点v的度数deg(v)＞2，表示该连通子图内存在轮廓相交情况。由于快速成型会只在轮廓构成的封闭区域内部进行材料填充，因此对于此种类型的节点拓扑排序，只需找到该连通子图的外边界节点，因此采用三角剖分方法创建有序封闭轮廓，具体为：

Step1，将连通子图Gi内的所有节点利用Delaunay三角剖分方法构建一个三角网格DT；

Step2，搜索三角网格DT的边界集合Boundary，边界边按照如下规则定义：Boundary＝{<vi，vj>|Dep<vi，vj>＝1}，其中<vi，vj>代表三角网格DT中由节点vi、vj构成的边，Dep<vi，vj>为依附于边<vi，vj>的三角形的个数，当Dep<vi，vj>＝1时，<vi，vj>为边界边，vi、vj为边界节点；

Step3，判断边界集合Boundary中的每一条边<vi，vj>是否属于连通子图Gi的边集Ei，①若存在 将与该边<vi，vj>相连的三角形删除，更新三角网格DT后，转Step2；②若不存在 直接转Step4；

Step4，依次连接三角网格DT的边界节点即为连通子图Gi内的有序封闭轮廓。

例如，图2a所示的连通图Gi＝(Vi，Ei)，其节点集合Vi＝{1，2，...，9}，边集Ei＝{<1，2>，<2，3>，<3，4>，<4，5>，<5，9>，<9，8>，<9，6>，<6，8>，<8，7>，<7，1>}，其中节点8和9的度数为3。首先将节点集合Vi进行三角剖分得到三角网格DT，如图2b所示，然后搜索网格DT的边界集合F＝{<1，2>，<2，3>，<3，4>，<4，5>，<5，7>，<7，1>}，由于集合F中的边界这 因此将与边<5，7>相连的三角形△578删除，得到新的三角网格DT后(图2c)，重新搜索其边界集合F，发现边界边 因此删除与之相连的△589，此时新的三角网格DT的边界集合F完全属于图Gi中的边集Ei(图2d)，故依次连接边界节点，得到有序封闭轮廓为1→2→3→4→5→9→8→7→1。

步骤四、利用每层切片得到的轮廓建立打印封闭区域，并与相邻切片层的区域进行布尔运算以对打印区域进行修正。具体如下：

Step1，在每层切片内，根据各个封闭轮廓之间的内外包含关系建立多边形封闭区域；

Step2，获取第i层切片的封闭区域Ai与第i+j层切片的封闭区域Ai+j的差集d1j＝Ai-Ai+j，j＝1，2，...，N，并求出它们的并集： 获取第i层切片的封闭区域Ai与第i-j层切片的封闭区域Ai-j的差集d2j＝Ai-Ai-j，j＝1，2，...，N，并求出它们的并集：

Step3，将区域Si＝d1∪d2作为物体第i层切片的表层打印区域，区域Ti＝Ai-Si作为物体第i层切片的内部打印区域。

实施例：

如图3a所示的曲柄零件模型，在切片P内产生的交点如图3b所示，若采用传统方法会产生如图3c所示的交点排序错乱。本发明首先将切片P内的交点集合映射为图，并利用Delaunay三角剖分方法构建三角网格，如图3d所示；然后利用图的边集对剖分网格进行裁剪，得到最终的三角网格如图3e所示；顺序连接网格的边界节点即得到有序封闭轮廓，如图3f所示；将该封闭轮廓构建成封闭区域，并和相邻切片层的区域进行布尔运算，得到该层切片的有效打印区域如图3g所示，其中直线填充区域为该零件在切片P的表层打印区域，网格填充区域为该零件在切片P的内部打印区域。

由此，本发明利用图的节点度数特性，智能识别切片轮廓相交情况，避免了网格拓扑关系的复杂计算，能够有效去除多余轮廓分支，建立正确的打印区域，适用于各种规则和非规则模型的切片处理。

实施例不应视为对本发明的限制，但任何基于本发明的精神所作的改进，都应在本发明的保护范围之内。

一种避免轮廓相交的快速成型切片处理方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。