一种3D打印中带岛层片区域的快速路径规划方法

摘要

本发明公开了一种3D打印中带岛层片区域的快速路径规划方法，能高效地处理可带岛、可凹的待打印层片区域，通过将打印区域剖分为数量有限的多个凸形区域,避开了路径中大量的出岛和进岛几何判断，以及随之而来的频繁激光关闭与开启操作，有效延长了激光器的寿命；该方法包括：使用带岛三角化算法对多边形层片区域

说明书

技术领域

本发明属于电子技术领域，尤其涉及一种3D打印中带岛层片区域的快速路径规划方法。

背景技术

基于分层打印的3D打印中，带岛层片区域的路径规划，由于岛屿(一个，甚至多个)的存在，传统的打印路径规划算法不可避免地出现了大量打印路径穿越岛屿的现象，频繁的进出岛屿，除了大量复杂的相交计算与几何判断之外，也将引发激光的频繁中断与继续问题。从而，一方面打印路径规划的计算复杂度较高、规划效率较低；另一方面，频繁的激光中断与继续，不可避免地将加速激光器的老化，缩短激光器的寿命。

针对带岛的多边形层片打印区域的路径规划，提出了一个二阶段的解决方法(Two-stage Solving Method for Convexify Segment Algorithm，简称TSM4CSA算法)。

发明内容

本发明的目的在于提供一种3D打印中带岛层片区域的快速路径规划方法，旨在解决基于分层打印的3D打印中，带岛层片区域的路径规划，由于岛屿(一个或多个)的存在，不可避免地存在大量的出岛和进岛复杂几何判断，并频繁地引发激光中断与继续的问题，从而明显影响打印路径规划的难度、缩短激光器的使用寿命。

本发明是这样实现的，一种3D打印中带岛层片区域的快速路径规划方法，该3D打印中带岛层片区域的快速路径规划方法包括：首先，使用带岛Delaunay三角化算法对多边形层片区域进行剖分，使得即由一系列三角形组成。其中，T_i为构成层片区域的一个三角形区域；其次，使用贪心策略，在初始三角形区域的基础上进行区域的凸化生长，使得带岛多边形层片区域最终由若干个凸形区域组成；最后，对每个凸形区域使用经典方法进行打印路径规划，获得全局区域的打印路径。带岛层片区域的打印路径，是由各个凸形区域的打印路径组成的复合打印路径。

除对带岛层片区域进行三角化外，该3D打印中带岛层片区域的快速路径规划方法还包括：多边形的凸化生长处理具体包括：

A、遍历凸多边形的边界(记为e＝{e_i|i＝1,2,3,...})，对每条边界e_i，进行步骤B的循环处理；

B、对多边形的边界e_i，首先判断是否存在共享e_i的多边形？若无，则跳到步骤C；若有，记共享e_i的多边形为则进行多边形的凸化生长判断，即多边形与合并后是否为凸形区域？若是，则合并(生长)，形成较大的凸多边形，并用flag标识多边形发生过生长变化；否则，跳到步骤C；

C、跳过当前边界e_i的处理，进入下一条边e_i+1的处理；

D、进行步骤B的循环处理，直到所有边界边e＝{e_i|i＝1,2,3,...}都已经进行过凸化生长测试；然后，判断flag标识是否发生过改变？若是，则将生长后的多边形作为待处理的多边形，进行下一轮处理；否则，将多边形标识为处理完成，剔除出待处理的多边形集合。

进一步，该3D打印中带岛层片区域的快速路径规划方法具体步骤包括：

(1)将带岛的打印区域多边形进行三角剖分，将分割为一系列三角形区域，即由一系列三角形组成，记为其中，T_i为构成层片区域的一个三角形区域；此过程的核心步骤是三角化，功能函数为

(2)对组成层片打印区域的所有多边形进行递归处理，采用贪心策略进行多边形的凸化生长处理，此凸多边形的凸化合并(即区域生长)对应的功能函数记为

(3)对经过凸化处理后组成层片区域的所有凸多边形polygon_t,t＝1,2,3,...，采用经典算法进行打印路径规划，若凸形区域polygon_t对应的打印路径为P_t，则层片打印区域的打印路径是多条打印路径P_t(t＝1,2,3,...)组成的复合打印路径，记为Path＝{P_t|t＝1,2,3,...}；

(4)返回层片打印区域对应的最终打印路径Path。

本发明对于规模为n的多边形打印区域进行带岛层片区域三角化的时间复杂度是O(nlogn)；对由m个三角形组成的层片区域，采用贪心策略的三角形凸化生长算法的时间复杂度为O(m²)。根据欧拉定理，m≤6n+1。可见，TSM4CSA方法的总体时间复杂度不高于O(n²)。

附图说明

图1是本发明实施例提供的TSM4CSA算法的核心流程图。

图2是本发明实施例提供的现有技术和采用本发明的方法进行带岛层片区域路径规划的结果对比图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

下面结合附图及具体实施例对本发明的应用原理作详细描述。

本发明实施例提供的3D打印中带岛层片区域的快速路径规划方法，该3D打印中带岛层片区域的快速路径规划方法包括：(1)使用带岛Delaunay三角化算法对多边形层片区域进行剖分，使得即由一系列三角形组成。其中，T_i为构成层片区域的一个三角形区域。

(2)使用贪心策略，在初始三角形剖分的基础上进行区域的凸化生长，使得带岛多边形层片区域最终由若干个凸形区域组成。

(3)对每个凸形区域，使用经典方法进行打印路径规划，获得全局区域的打印路径。带岛层片区域的打印路径，由各个凸形区域的打印路径组成。

进一步，该3D打印中带岛层片区域的快速路径规划方法还包括：多边形的凸化生长处理具体包括：

A、遍历凸多边形的边界(记为e＝{e_i|i＝1,2,3,...})，对每条边界e_i，进行步骤B的循环处理；

B、对多边形的边界e_i，首先判断是否存在共享e_i的多边形？若无，则跳到步骤C；若有，记共享e_i的多边形为Δ_nei，则进行多边形的凸化生长判断，即多边形与Δ_nei合并后是否为凸形区域？若是，则合并(生长)，形成较大的凸多边形，并用flag标识多边形发生过生长变化；否则，跳到步骤C；

C、跳过当前边界e_i的处理，进入下一条边e_i+1的处理；

D、进行步骤B的循环处理，直到所有边界边e＝{e_i|i＝1,2,3,...}进行过凸化生长测试；然后，判断flag标识是否发生过改变？若是，则将生长后的多边形作为待处理的多边形，进行下一轮处理；否则，将多边形标识为处理完成，剔除出待处理的多边形集合。

进一步，该3D打印中带岛层片区域的快速路径规划方法具体步骤包括：

(1)使用带岛Delaunay三角化算法对多边形层片区域进行剖分，使得即由一系列三角形组成。其中，T_i为构成层片区域的一个三角形区域；

(2)对组成层片打印区域的所有多边形进行递归的凸化生长处理，即采用贪心策略进行多边形的凸化生长处理。此凸多边形的凸化合并(即区域生长)对应的功能函数记为

(3)对经过凸化处理后组成层片区域的所有凸多边形polygon_t,t＝1,2,3,...，采用经典算法进行打印路径规划，若凸形区域polygon_t对应的打印路径为P_t，则层片打印区域的打印路径是多条打印路径P_t(t＝1,2,3,...)组成的复合打印路径，记为Path＝{P_t|t＝1,2,3,...}；

(4)返回层片打印区域对应的最终打印路径Path。

如图1所示，本发明实施例提供的3D打印中带岛层片区域的快速路径规划方法采用TSM4CSA算法，具体包括：

首先，读入可带岛、可凹的多边形待打印层片区域

然后，使用带岛的Delaunay三角化算法，将多边形打印区域进行剖分，使得即由一系列三角形T_i组成。其中，T_i为构成层片区域的一个三角形区域。

紧接着，建立一个队列Queue，用于存储组成多边形打印区域的子区域。初始化时刻，Queue＝∪T_i,i＝1,2,3,...。

之后，进行循环，直到队列Queue为空。若队列Queue不为空，则从中取出一个元素(打印区域的一个子区域，记为ele)。对子区域的所有邻接区域(循着子区域ele的多边形边界进行遍历，与ele共享边界边的区域为邻接区域，记为Nei_k,k＝1,2,...)，使用贪心策略进行子区域ele的凸化生长，若子区域ele与邻接区域Nei_k可合并(生长)为凸形区域，则合并两者成为新凸形区域新区域Area_new，并将合并后的新区域Area_new添加到队列Queue中。

最后，经过上述循环处理后，队列Queue为空，即组成多边形层片区域的子区域的凸化生长过程结束，即打印区域可由一系列凸多边形组成，记为其中，P_t为一个凸多边形。打印区域由最终的一序列凸多边形P_t所组成(覆盖)。

其中TSM4CSA算法实现的核心步骤和伪代码如下：

输入：(1)List<Point>C,List<List<Point>holes表示的一个可能带多个岛屿holes的多边形层片打印区域C，记为

(2)3D打印光斑的直径，记为d。

输出：List<List<Point>>表示的一条或多条子打印路径组成的整体打印路径，记为P＝{P_i|i＝1,2,3,...}，P_i为一条子打印路径。

下面结合具体实施例对本发明的应用原理作进一步描述。

TSM4CSA算法采用二阶段策略，对带岛的多边形层片打印区域进行三角剖分和区域凸化生长。第一阶段先将带岛多边形层片区域分割成互不重叠、互不交叉的三角形区域；第二阶段是在上一阶段生成的三角形序列的基础上，使用贪心策略，进行多边形(初始时刻为三角形)区域生长，若两个共享邻接边的多边形(三角形)区域合并后仍为凸形区域，则合并两个区域；否则停止区域的生长。进行循环处理，直到所有区域不能再进行凸化生长。

图2(0)为实施例处理的带两个岛屿的层片打印区域；图2(1)为现有技术进行带岛层片区域打印路径规划的结果；图2(2.1)是带岛层片区域进行Delaunay三角剖分的结果，图2(2.2)是在三角剖分基础上进行区域凸化生长的一个结果，实施例对应的层片打印区域由11个凸形区域组成；图2(2.3)是对组成带岛层片区域的各个凸形区域、采用经典算法进行路径规划的结果。最终的带岛层片区域的打印路径,由组成带岛区域的11个凸形区域对应的11条打印路径构成。可见，经过TSM4CSA算法的处理，带岛的打印区域多边形被分割为一系列凸形区域，此后使用经典路径规划算法，快速的生成对应的3D打印路径。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。