一种二维轮廓区域单轨迹填充生成方法
一种二维轮廓区域单轨迹填充生成方法
【技术领域】
[0001]本发明属于增材制造(3D打印或快速原型)技术领域，特别涉及一种二维轮廓区域单轨迹填充生成方法。
【背景技术】
[0002]增材制造技术中的熔融沉积(FDM)工艺，其零件的成型需要通过熔丝填充分层后的二维轮廓区域完成。填充过程中，每一条单独的填充轨迹都需要熔丝喷嘴开和关、进和退、喷嘴清理等辅助动作。因此，二维轮廓区域填充的连续轨迹数量对填充效率和填充质量有着重要影响，连续轨迹的数量越少，需要的辅助时间越少，熔丝断点也越少，成型质量也就越好。
[0003]目前，增材制造中，二维轮廓区域的填充轨迹生成算法主要有zigzag填充、轮廓偏置填充、Hi Ibert曲线填充、Voronoi图构造螺旋轨迹等。Zigzag填充算法主要是通过连接区域内的平行扫描线来生成“弓”形填充轨迹，如果区域内部包含不需填充区域或在扫描线垂直方向上存在凹区域，则无法形成连续轨迹;轮廓偏置填充算法主要是轮廓线偏置实现区域填充，每条偏置轨迹之间是不连通的，对于复杂轮廓还将出现偏置轮廓自相交或互相交导致偏置轮廓分裂;Hilbert曲线填充算法通过Hilbert曲线来填充区域，由于区域轮廓的不规则，Hilbert曲线不可避免地被截断而产生中断;利用Voronoi图构造螺旋轨迹时，算法较为复杂，在轨迹间的过渡不符合一个偏置轨迹的规则，并且该方法在复杂轮廓下还是会出现很多的退刀次数。由此可见，这些算法虽然能够填充二维轮廓区域，但对于复杂二维轮廓区域，即使是单连通区域，也需多条的连续轨迹才能实现全区域的填充。因此，有必要研究新的复杂二维轮廓区域填充方法，生成连续填充轨迹数量最少的填充轨迹，提高填充效率和填充质量。
【发明内容】
[0004]发明的目的在于克服现有技术之不足，提供一种二维轮廓区域单轨迹填充生成方法，可以由任意复杂的单连通区域生成单条填充轨迹，并最终实现任意复杂二维轮廓区域的最少连续轨迹数量的填充轨迹生成，具有较高的鲁棒性和效率。
[0005]本发明解决其技术问题所采用的技术方案是:提供一种二维轮廓区域单轨迹填充生成方法，包括如下步骤:
[0006]Al、二维区域轮廓线组的分组和连接处理；
[0007]A2、单连通区域连接轮廓线的偏置处理；
[0008]A3、将每个单连通区域内的偏置轮廓线连接生成各单连通区域的单条轨迹。
[0009]优选的，所述步骤Al具体为:
[0010]B1、对符合左手定则、无自相交和互相交的二维区域轮廓线组进行处理，通过各轮廓线极值点判断各轮廓线是内轮廓还是外轮廓，并分别保存到内轮廓动态数组和外轮廓动态数组，计算各轮廓线的AABB包围盒；
[0011]B2、将复杂二维区域轮廓线组分解为单联通区域轮廓线组；
[0012]B3、将单连通区域的内、外轮廓线组连接成为单条轮廓线:设某个单连通区域的外轮廓顶点动态数组为Cf，其包含的内轮廓组为(C1，C2，…，Cn)。
[0013]优选的，所述步骤B2具体为:
[0014]Cl、从内轮廓数组中取出一个取出一个内轮廓C;
[0015]C2、将C的AABB包围盒依次与外轮廓数组中的各外轮廓AABB进行比较，判断C被哪些外轮廓包含；
[0016]C3、如果C只被一条外轮廓包含，则该外轮廓为C的直接包括外轮廓Cw;如果C被多条外轮廓包含，分别计算这些外轮廓的AABB包围盒面积，所求面积最小的外轮廓为内轮廓C的直接包括外轮廓Cw;
[0017]C4、将内轮廓C加入到其直接包括外轮廓Cw的内轮廓索引数组中；
[0018]C5、重复操作步骤①到④，直至所有内轮廓的均被插入各个外轮廓的内轮廓索引数组中；其结果是每一条外轮廓和若干条直接被包含的内轮廓构成一个单连通区域。
[0019]优选的，所述步骤B3具体为:
[0020]Dl、将外轮廓Cw的所有顶点建立一颗k-d树；
[0021]D2、取出Cw所包含的一个内轮廓Ulme (I，2，...，!!)}，分别将Cm每一个点作为搜索点，利用k-d树的查找到C沖最近点，求出距离，比较得到内外轮廓之间的最近点对(W，Vj(Cm)),其中Vi(Cw)为Cw中的第i个点，Vj(Cm)SCm中的第j个点；
[0022]D3、将两个轮廓合并为一个外轮廓:外轮廓Cw在Vi之后插入以Vj(Cm)为起始点的内轮廓Cm中的所有点，然后在Cm末端按顺序插入两个点Vj(Cm)和Vi(Cw)，生成新的Cw;
[0023]D4、清除原k-d树，以新Cw仓Il建新的k-d树；
[0024]D5、删除内轮廓U，跳转至②直至Cw所包含的内轮廓遍历，最终只得到一个轮廓线
Cffo
[0025]优选的，所述步骤A2具体为:
[0026]E1、对轮廓线进行基于顶点线段混合偏置，并去除偏置轮廓的自相交；
[0027]E2、在单连通区域连接轮廓线的第一次偏置时，对轮廓间连接线的偏置进行特殊处理以获得间距一致的轨迹行距；
[0028]E3、对轮廓中的狭长尖角进行截断处理后再进行偏置，以减轻轮廓狭长尖角对加工质量的影响。
[0029]优选的，所述步骤E2具体步骤为:
[0030 ] F1、对轮廓连接点(步骤D2中的各对Vi (Cw)和Vj (Cm))做标记；
[0031]F2、对轮廓连接线段Vi(Cw)Vj(Cm)和Vj(Cm)Vi(Cw)分别偏置0.5d(d为轮廓线偏置距离)，而轮廓线其它线段则偏置距离d。
[0032]优选的，所述步骤E3具体步骤为:
[0033]Gl、复制轮廓线C为C ;
[0034]G2、遍历轮廓线每个顶点，计算顶点的相邻两线段夹角Θ，夹角小于设定值(该值小于90°)时，对该顶点(设为V1)相邻轮廓线段进行截断处理；
[0035]G3、以顶点V1为起点，分别沿顶点两相邻轮廓线段方向，选取两个顶点Vh和Vi+k，要求Vi沿轮廓线到V1-k和Vi+k的距离相等，且要求V1-k和Vi+k之间距离大于L = 2d/cos (Θ/2)，其中d为轮廓线偏置距离；
[0036]G4、将轮廓线在顶AV1处的尖角截断，即删除Vni和V1+k之间的顶点，轮廓线修改为Vo、Vl、."、V1-k、Vi+k、...；
[0037]G5、在轮廓线C中对应顶点V1处的轮廓段，修改为“弓”形轮廓段，实现无空隙填充；
[0038]G6、对轮廓线C进行偏置，获得没有尖角的偏置轨迹。
[0039]优选的，所述步骤A3具体步骤为:
[0040]Hl、偏置轮廓线的分类处理，主要是对偏置自交后产生多个子偏置环进行分类编号；
[0041]H2、分别在每个单连通区域内，进行无全局自相交偏置轮廓线的连接，即对分类编号为I的偏置轮廓线组由外向内进行只进不出的连接，设外层轮廓线为O，直接相邻的内层偏置轮廓线为C;
[0042]H3、分别在每个单连通区域内，对全局自交偏置轮廓线生成的子偏置轮廓线组进行有进有出连接，设外层轮廓线C，其直接相邻的子偏置轮廓为C’。
[0043]优选的，所述步骤Hl具体步骤为:
[0044]I1、令单连通区域的连接轮廓线的分类编号为n(n的初始值为I);
[0045]12、进行轮廓线偏置，偏置时没有出现全局自相交，则新偏置轮廓线的分类编号为η;如果出现全局自相交，偏置后是产生多个子偏置轮廓线，则分别设置新生成的子偏置轮廓线的分类编号为η++;
[0046]13、重复操作步骤12直至确定所有偏置轮廓线的分类编号。
[0047]优选的，所述步骤Η2具体步骤为:
[0048]Jl、遍历轮廓线Cw的顶点，找到最平坦的顶点V1，在该处生成一个距离为轮廓偏置值d的切口，其切口顶点设为V1、Vi+1;按照Vi+1，Vi+2，…，Vn，Vo，V1，…，Vi的顺序，重新存储轮廓线Cw的顶点动态数组；
[0049]J2、分别从Vi 和Vi+1发出与线段ViVi+工的夹角为给定值的射线，与各内层偏置轮廓线相交，获得两个对应顶点Vj和Vj+1;
[0050]】3、将偏置轮廓线(:中的顶点，分别以￥」+1^+2，-_^()，￥1^_，％加入到轮廓线(>顶点动态数组的1之后；
[0051]J4、重复J2-J3的处理，直到分类编号为I的所有偏置轮廓线都处理完毕，获得单一轮廓线Cw。
[0052]优选的，所述步骤H3具体步骤为:
[0053]K1、取出一个类别的子偏置轮廓线组；
[0054]K2、依次从外到内取出第k条(k初值为I)子偏置轮廓线C’，遍历子偏置轮廓线C’的顶点，找到相对平坦的顶点V1;要求当k>l时，第k条子偏置轮廓线上的顶点V1，与第(k-Ι)条子偏置轮廓线上的顶点1要错开一定角度，保证两条轮廓线上的切口没有任何重叠；
[0055]K3、在子偏置轮廓线C’上，以V1A为中心，将V1点相邻前后两线段的夹角平分线分别偏置0.5d，并分别与外层轮廓线C和子偏置轮廓线C’求交，其中与子偏置轮廓线C’的交点设为V1、Vi+1，原Vi点删除;而与外层轮廓线C的交点设为Vj和Vj+1;
[0056]K4、若k为奇数，则将子偏置轮廓线C’中的顶点以逆序插入到轮廓线C的Vj之后，SP分别将Vi，Vh，…V1，，Vo，Vn，Vn-1，…，Vi+1顺序插入到C的Vj之后;若k为偶数，则将子偏置轮廓线^中的顶点顺序插入到轮廓线⑶勺…之后’即分别将^^…^^^’…^插入到轮廓线C的Vj之后；
[0057]K5、重复K2-K4，直到该类子偏置轮廓线都插入到轮廓线C中；
[0058]Κ6、重复Κ1-Κ5，直到所有类别的子偏置轮廓线都插入到轮廓线C中，生成单连通区域内的单条填充轨迹线。
[0059]本发明的有益效果是:
[0060]1、本发明提供的二维轮廓区域单轨迹填充生成方法，能够有效生成任意复杂二维轮廓区域的、最少数量的填充轨迹，且适应性强；
[0061]2、通过将单连通区域的内外轮廓线连接为单条轮廓线后，再进行偏置和连接，可以保证一个单连通区域内只生成一条连续的填充轨迹，同时简化由任意单连通区域生成单条轨迹线的编程实现难度，同时保证结果的可靠性。
[0062]以下结合附图及实施例对本发明作进一步详细说明；但本发明的一种二维轮廓区域单轨迹填充生成方法不局限于实施例。
【附图说明】
[0063]图1是本发明的流程不意图；
[0064]图2是本发明内、外轮廓判断示意图；
[0065]图3是本发明轮廓线的数据结构示意图；
[0066]图4是本发明的单联通区域划分示意图；
[0067]图5是本发明的内外轮廓线最近点示意图；
[0068]图6是本发明的内外轮廓线连接示意图；
[0069]图7是本发明的单连通区域轮廓连接示意图；
[0070]图8是本发明的轮廓线混合偏置示意图；
[0071]图9是本发明的偏置轮廓自交去除示意图；
[0072]图10是本发明的轮廓连接线偏置示意图；
[0073]图11是本发明的轮廓连接线修正偏置示意图；
[0074]图12是本发明的轮廓连尖角截断原理示意图；
[0075]图13是本发明的轮廓连尖角截断后轮廓示意图；
[0076]图14是本发明的偏置轮廓线分类示意图；
[0077]图15是本发明的偏置轮廓线组只进不出的连接原理示意图；
[0078]图16是本发明的偏置轮廓线组只进不出的连接示意图；
[0079]图17是本发明的偏置轮廓线组只进不出的连接效果图；
[0080]图18是本发明的偏置轮廓线组有进有出连接切口示意图；
[0081]图19是本发明的偏置轮廓线组有进有出连接效果示意图；
[0082]图20是本发明的单连通区域单轨迹填充实例一；
[0083]图21是本发明的单连通区域单轨迹填充实例二。
【具体实施方式】
[0084]实施例
[0085]参见图1至图21所示，本发明的一种二维轮廓区域单轨迹填充生成方法，包括如下步骤:
[0086]Al、二维区域轮廓线组的分组和连接处理；
[0087]A2、单连通区域连接轮廓线的偏置处理；
[0088]A3、将每个单连通区域内的偏置轮廓线连接生成各单连通区域的单条轨迹。
[0089]优选的，所述步骤Al具体为:
[0090]B1、对符合左手定则、无自相交和互相交的二维区域轮廓线组进行处理，通过各轮廓线极值点判断各轮廓线是内轮廓还是外轮廓，并分别保存到内轮廓动态数组和外轮廓动态数组，计算各轮廓线的AABB包围盒；
[0091 ]其中内、外轮廓的具体判断方法为:如图2中，Vi为Y轴方向上的极小值点，则矢量可计算ei = Vi_V1-1和e2 = Vi+i_Vi，如果矢量e = ei Xe2的Z轴分量为正，则该轮廓线为逆时针方向，即为外轮廓线，如图2;如果e的Z轴分量为负，则该轮廓线为顺时针方向，即为内轮廓线。
[0092]轮廓线的数据结构如图3所示，其中CVertex为顶点类。轮廓线动态数组同样采用C++标准模板库中的vector容器来实现，其中外轮廓线动态数组为vector〈CContour>vec_OutContour，内轮廓线动态数组为则轮廓线动态数组为vector〈CContour>vec_InContour。
[0093]B2、将复杂二维区域轮廓线组分解为单联通区域轮廓线组；
[0094]B3、将单连通区域的内、外轮廓线组连接成为单条轮廓线:设某个单连通区域的外轮廓顶点动态数组为Cf，其包含的内轮廓组为(C1，C2，…，Cn)。
[0095]优选的，所述步骤B2具体为:
[0096]Cl、从内轮廓数组中取出一个取出一个内轮廓C;
[0097]C2、将C的AABB包围盒依次与外轮廓数组中的各外轮廓AABB进行比较，判断C被哪些外轮廓包含；即比较轮廓线类中的左下角和右上角的坐标值，如果满足C的左下角坐标分量值均大于某外轮廓对应值、且C的右上角坐标分量值均小于某外轮廓对应值，则C被该外轮廓线包含；
[0098]C3、如果C只被一条外轮廓包含，则该外轮廓为C的直接包括外轮廓Cw;如果C被多条外轮廓包含，分别计算这些外轮廓的AABB包围盒面积，所求面积最小的外轮廓为内轮廓C的直接包括外轮廓Cw;
[0099]C4、将内轮廓C加入到其直接包括外轮廓Cw的内轮廓索引数组中；即图3的vec_InnerContour中。
[0100]C5、重复操作步骤Cl到C4，直至所有内轮廓的均被插入各个外轮廓的内轮廓索引数组中；其结果是每一条外轮廓和若干条直接被包含的内轮廓构成一个单连通区域。如图4所示，图中外轮廓线I和内轮廓2、5构成一个单联通区域;外轮廓线3和内轮廓4构成一个单联通区域;外轮廓线6和内轮廓7构成一个单联通区域。
[0101]优选的，所述步骤B3具体为:
[0102]Dl、将外轮廓Cw的所有顶点建立一颗k-d树；
[0103]D2、取出Cw所包含的一个内轮廓Ulme (I，2，...，!!)}，分别将Cm每一个点作为搜索点，利用k-d树的查找到C沖最近点，求出距离，比较得到内外轮廓之间的最近点对(W，Vj (Cm))，如图5所示，其中Vi ( Cf)为Cw中的第i个点，Vj ( Cm)为Cm中的第j个点；
[0104]D3、将两个轮廓合并为一个外轮廓:外轮廓Cw在Vi之后插入以Vj(Cm)为起始点的内轮廓Cm中的所有点，然后在Cm末端按顺序插入两个点Vj(Cm)和Vi(Cw)，生成新的Cw;如图6所不O
[0?05] D4、清除原k-d树，以新Cw仓Il建新的k-d树；
[0106]D5、删除内轮廓U，跳转至②直至Cw所包含的内轮廓遍历，最终只得到一个轮廓线Cw。图7所示。 [0107]优选的，所述步骤A2具体为:
[0108]E1、对轮廓线进行基于顶点线段混合偏置，并去除偏置轮廓的自相交；
[0109]①顶点线段混合偏置法:
[0110]在轮廓线的凸点使用顶点偏置，在凹点使用线段整体偏置，使得凸点一定不会出现自相交，而凹点必定会发生自相交。如图8所示，A点和B点为多边形上两点，其中A点为凹点，B点为凸点。A点使用整体线段偏置，将会得到两个点A’和A〃，B点使用顶点偏置将会得到I个点B’。其中，顶点的凹凸性判断方法为:假设点A、B、C为轮廓线上连续的3个点，设矢量的= B-A，e2 = C_B，e3为ei逆时针旋转90°，e4为e2逆时针旋转90°。计算m= (Θ3+Θ4).(e2_ei)值。如果m>0，B点为凸点，否则表示B点为凹点。
[0111]②偏置轮廓自相交的去除，如图9:
[0112]轮廓线偏置过程中，逐个点偏置填入点表，若是线段偏置则为该偏置点打上标记，每次偏置一个点，将新生点和前一点组成线段，并基于K-D树验证是否和前面的曲线有相交；
[0113]如果有相交，求出交点Rs坐标；
[0114]提取新生成的子偏置轮廓环，查找该子偏置轮廓环中是否存在线段偏置的标记点，如有，则去除该子偏置轮廓环，如图8中顶点A’j'lPV:构成的子偏置轮廓环中，A’、A"均为线段偏置标记点，因此该子偏置轮廓环需要被去除；如果没有线段偏置标记点，则判断生成的子偏置轮廓环的旋向，旋向为顺时针，则去除该子偏置轮廓环，如图9中￥5、^^+1、￥5+1、￥5等顶点构成的子偏置轮廓环需要去除，否则保存新生成的子偏置轮廓环，如如图9中右侧粗实线子偏置轮廓环则保留；
[0115]完成自相交的去除后最终得到无自相交的偏置轮廓线。
[0116]E2、在单连通区域连接轮廓线的第一次偏置时，对轮廓间连接线的偏置进行特殊处理以获得间距一致的轨迹行距；
[0117]E3、对轮廓中的狭长尖角进行截断处理后再进行偏置，以减轻轮廓狭长尖角对加工质量的影响。
[0118]优选的，所述步骤E2具体步骤为:
[0119]F1、对轮廓连接点(步骤D2中的各对Vi (Cw)和Vj (Cm))做标记；
[0120]F2、对轮廓连接线段Vi(Cw)Vj(Cm)和Vj(Cm)Vi(Cw)分别偏置0.5d(d为轮廓线偏置距离)，而轮廓线其它线段则偏置距离d。如图11所示的实线，其中虚线间距离为2d。
[0121]优选的，所述步骤E3具体步骤为:
[0122]Gl、复制轮廓线C为C ;
[0123]G2、遍历轮廓线每个顶点，计算顶点的相邻两线段夹角Θ，夹角小于设定值(该值小于90°)时，对该顶点(设为V1)相邻轮廓线段进行截断处理；
[0124]G3、以顶点V1为起点，分别沿顶点两相邻轮廓线段方向，选取两个顶点Vh和Vi+k，要求Vi沿轮廓线到V1-k和Vi+k的距离相等，且要求V1-k和Vi+k之间距离大于L = 2d/cos (Θ/2)，其中d为轮廓线偏置距离；
[0125]G4、将轮廓线在顶AV1处的尖角截断，即删除Vni和V1+k之间的顶点，轮廓线修改为Vo、Vl、."、V1-k、Vi+k、...；
[0126]G5、在轮廓线C中对应顶点V1处的轮廓段，修改为“弓”形轮廓段，实现无空隙填充；基本方法为:
[0127]a)根据夹角找出狭长尖角，找出垂直于夹角角平分线的线段AB，并且长度为d(如图12所示)；
[0128]b)以d为偏置距离多次偏置线段AB，并延长交于夹角的相邻线段，直至到偏置线段长度大于L，然后沿两个方向偏置角平分线0.5d偏置距离，如图12所示；
[0129]c)修改轮廓线C，使之在尖角处形成“弓”曲线，如图13所示。
[0130]G6、对轮廓线C进行偏置，获得没有尖角的偏置轨迹。如图12中轮廓线C0FF。
[0131]优选的，所述步骤A3具体步骤为:
[0132]Hl、偏置轮廓线的分类处理，主要是对偏置自交后产生多个子偏置环进行分类编号；
[0133]H2、分别在每个单连通区域内，进行无全局自相交偏置轮廓线的连接，即对分类编号为I的偏置轮廓线组由外向内进行只进不出的连接，设外层轮廓线为O，直接相邻的内层偏置轮廓线为C;其连接原理如图15。
[0134]H3、分别在每个单连通区域内，对全局自交偏置轮廓线生成的子偏置轮廓线组进行有进有出连接，设外层轮廓线C，其直接相邻的子偏置轮廓为C’。
[0135]优选的，所述步骤Hl具体步骤为:
[0136]I1、令单连通区域的连接轮廓线的分类编号为n(n的初始值为I);即图3中CContour类内int m_nClassify变量为n(n的初始值为I)。
[0137]12、进行轮廓线偏置，偏置时没有出现全局自相交，则新偏置轮廓线的分类编号为η;如果出现全局自相交，偏置后是产生多个子偏置轮廓线，则分别设置新生成的子偏置轮廓线的分类编号为η++;
[0138]13、重复操作步骤12直至确定所有偏置轮廓线的分类编号。偏置轮廓的分类效果如图14。
[0139]优选的，所述步骤Η2具体步骤为:
[0140]Jl、遍历轮廓线Cw的顶点，找到最平坦的顶点V1，在该处生成一个距离为轮廓偏置值d的切口，其切口顶点设为V1、Vi+1;按照Vi+1，Vi+2，…，Vn，Vo，V1，…，Vi的顺序，重新存储轮廓线Cw的顶点动态数组；
[0141]J2、分别从Vi和Vi+1发出与线段ViVi+工的夹角为给定值的射线，与各内层偏置轮廓线相交，获得两个对应顶点Vj和Vj+1;
[0142]】3、将偏置轮廓线(:中的顶点，分别以￥」+1^+2，-_1，￥()，￥1^_，％加入到轮廓线(>顶点动态数组的1之后；
[0143]J4、重复J2-J3的处理，直到分类编号为I的所有偏置轮廓线都处理完毕，获得单一轮廓线Cw。最后连接示意图如图16，连接效果如图17。
[0144]优选的，所述步骤H3具体步骤为:
[0145]K1、取出一个类别的子偏置轮廓线组；
[0146]K2、依次从外到内取出第k条(k初值为I)子偏置轮廓线C’，遍历子偏置轮廓线C’的顶点，找到相对平坦的顶点V1;要求当k>l时，第k条子偏置轮廓线上的顶点V1，与第(k-Ι)条子偏置轮廓线上的顶点1要错开一定角度，保证两条轮廓线上的切口没有任何重叠；
[0147]K3、如图18所示，在子偏置轮廓线C’上，以V;为中心，将V;相邻前后两线段的夹角平分线分别偏置0.5d，并分别与外层轮廓线C和子偏置轮廓线C ’求交，其中与子偏置轮廓线C’的交点设为V1、Vi+1，原Vi点删除;而与外层轮廓线C的交点设为Vj和Vj+1;
[0148]K4、若k为奇数，则将子偏置轮廓线C’中的顶点以逆序插入到轮廓线C的Vj之后，SP分别将Vi，Vh，…V1，，Vo，Vn，Vn-1，…，Vi+1顺序插入到C的Vj之后;若k为偶数，则将子偏置轮廓线^中的顶点顺序插入到轮廓线⑶勺…之后’即分别将^^…^^^’…^插入到轮廓线C的Vj之后;连接示意图如19所示。
[0149]K5、重复K2-K4，直到该类子偏置轮廓线都插入到轮廓线C中；
[0150]K6、重复K1-K5，直到所有类别的子偏置轮廓线都插入到轮廓线C中，生成单连通区域内的单条填充轨迹线。
[0151]图20和21为本发明的实施实例。
[0152]上述实施例仅用来进一步说明本发明的一种二维轮廓区域单轨迹填充生成方法，但本发明并不局限于实施例，凡是依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均落入本发明技术方案的保护范围内。
【主权项】
1.一种二维轮廓区域单轨迹填充生成方法，其特征在于，包括如下步骤: Al、二维区域轮廓线组的分组和连接处理； A2、单连通区域连接轮廓线的偏置处理； A3、将每个单连通区域内的 偏置轮廓线连接生成各单连通区域的单条轨迹。2.根据权利要求1所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤Al具体为: B1、对符合左手定则、无自相交和互相交的二维区域轮廓线组进行处理，通过各轮廓线极值点判断各轮廓线是内轮廓还是外轮廓，并分别保存到内轮廓动态数组和外轮廓动态数组，计算各轮廓线的AABB包围盒； B2、将复杂二维区域轮廓线组分解为单联通区域轮廓线组； B3、将单连通区域的内、外轮廓线组连接成为单条轮廓线:设某个单连通区域的外轮廓顶点动态数组为Cf，其包含的内轮廓组为(C1，C2，…，Cn)。3.根据权利要求2所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤B2具体为: Cl、从内轮廓数组中取出一个取出一个内轮廓C; C2、将C的AABB包围盒依次与外轮廓数组中的各外轮廓AABB进行比较，判断C被哪些外轮廓包含； C3、如果C只被一条外轮廓包含，则该外轮廓为C的直接包括外轮廓Cw;如果C被多条外轮廓包含，分别计算这些外轮廓的AABB包围盒面积，所求面积最小的外轮廓为内轮廓C的直接包括外轮廓Cw; C4、将内轮廓C加入到其直接包括外轮廓Cw的内轮廓索引数组中； C5、重复操作步骤①到④，直至所有内轮廓的均被插入各个外轮廓的内轮廓索引数组中；其结果是每一条外轮廓和若干条直接被包含的内轮廓构成一个单连通区域。4.根据权利要求2所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤B3具体为: Dl、将外轮廓Cw的所有顶点建立一颗k-d树； D2、取出Cw所包含的一个内轮廓Ulme (I，2，…，η)}，分别将Cm每一个点作为搜索点，利用k - d树的查找到C w中最近点，求出距离，比较得到内外轮廓之间的最近点对(V i (C w )，V j(Cm))，其中Vi(Cw)为Cw中的第i个点，Vj(Cm)SCm中的第j个点； D3、将两个轮廓合并为一个外轮廓:外轮廓Cw在Vi之后插入以Vj(U)为起始点的内轮廓Cm中的所有点，然后在Cm末端按顺序插入两个点Vj(Cm)和Vi(Cw)，生成新的Cw; D4、清除原k-d树，以新Cw创建新的k-d树； D5、删除内轮廓Cm，跳转至②直至Cw所包含的内轮廓遍历，最终只得到一个轮廓线Cf。5.根据权利要求1所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤A2具体为: E1、对轮廓线进行基于顶点线段混合偏置，并去除偏置轮廓的自相交； E2、在单连通区域连接轮廓线的第一次偏置时，对轮廓间连接线的偏置进行特殊处理以获得间距一致的轨迹行距； E3、对轮廓中的狭长尖角进行截断处理后再进行偏置，以减轻轮廓狭长尖角对加工质量的影响。6.根据权利要求5所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤E2具体步骤为: Fl、对轮廓连接点(步骤D2中的各对Vi (Cw)和Vj (Cm))做标记； F2、对轮廓连接线段Vi(Cw)Vj(Cm)和Vj(Cm)Vi(Cw)分别偏置0.5d(d为轮廓线偏置距离)，而轮廓线其它线段则偏置距离d。7.根据权利要求5所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤E3具体步骤为: Gl、复制轮廓线C为; G2、遍历轮廓线每个顶点，计算顶点的相邻两线段夹角Θ，夹角小于设定值(该值小于90°)时，对该顶点(设为V1)相邻轮廓线段进行截断处理； G3、以顶点V1为起点，分别沿顶点1的两相邻轮廓线段方向，选取两个顶点Vni和V1+k，要求Vi沿轮廓线到V1-k和Vi+k的距离相等，且要求V1-k和Vi+k之间距离大于L = 2d/COS(0/2)，其中d为轮廓线偏置距离； G4、将轮廓线在顶点1处的尖角截断，即删除Vni和V1+k之间的顶点，轮廓线C修改为Vo、V1、."、V1-k、Vi+k、…； G5、在轮廓线C中对应顶点V1处的轮廓段，修改为“弓”形轮廓段，实现无空隙填充； G6、对轮廓线C'进行偏置，获得没有尖角的偏置轨迹。8.根据权利要求2所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤A3具体步骤为: Hl、偏置轮廓线的分类处理，主要是对偏置自交后产生多个子偏置环进行分类编号； H2、分别在每个单连通区域内，进行无全局自相交偏置轮廓线的连接，即对分类编号为I的偏置轮廓线组由外向内进行只进不出的连接，设外层轮廓线为Cw，直接相邻的内层偏置轮廓线为C; H3、分别在每个单连通区域内，对全局自交偏置轮廓线生成的子偏置轮廓线组进行有进有出连接，设外层轮廓线C，其直接相邻的子偏置轮廓为C’。9.根据权利要求8所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤Hl具体步骤为: 11、令单连通区域的连接轮廓线的分类编号为n(n的初始值为I); 12、进行轮廓线偏置，偏置时没有出现全局自相交，则新偏置轮廓线的分类编号为η;如果出现全局自相交，偏置后是产生多个子偏置轮廓线，则分别设置新生成的子偏置轮廓线的分类编号为η++; 13、重复操作步骤12直至确定所有偏置轮廓线的分类编号。10.根据权利要求8所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤Η2具体步骤为: J1、遍历轮廓线Cw的顶点，找到最平坦的顶点V1，在该处生成一个距离为轮廓偏置值d的切口，其切口顶点设为V1、Vi+1;按照Vi+1，Vi+2，…，Vn，Vo，V1，…，Vi的顺序，重新存储轮廓线Cw的顶点动态数组； J2、分别从Vi和Vi+1发出与线段ViVi+j^夹角为给定值的射线，与各内层偏置轮廓线相交，获得两个对应顶点Vj和Vj+1; J3、将偏置轮廓线C中的顶点，分别以Vj+1，Vj+2，...，VwV^V1，…，Vj加入到轮廓线Cw顶点动态数组的Vi之后； J4、重复J2-J3的处理，直到分类编号为I的所有偏置轮廓线都处理完毕，获得单一轮廓线Cw011.根据权利要求8所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤H3具体步骤为: Kl、取出一个类别的子偏置轮廓线组； K2、依次从外到内取出第k条(k初值为I)子偏置轮廓线C’，遍历子偏置轮廓线C’的顶点，找到相对平坦的顶点V1;要求当k>l时，第k条子偏置轮廓线上的顶点V1，与第(k-Ι)条子偏置轮廓线上的顶点1要错开一定角度，保证两条轮廓线上的切口没有任何重叠； K3、在子偏置轮廓线C’上，以1点为中心，将V1点相邻前后两线段的夹角平分线分别偏置0.5d，并分别与外层轮廓线C和子偏置轮廓线C’求交，其中与子偏置轮廓线C’的交点设为V1、Vi+1，原Vi点删除;而与外层轮廓线C的交点设为Vj和Vj+1; K4、若k为奇数，则将子偏置轮廓线C’中的顶点以逆序插入到轮廓线C的Vj之后，即分别将Vi，V1-1，…V1，，Vo，Vn，Vn-1，…，Vi+1顺序插入至IjC的Vj之后;若k为偶数，则将子偏置轮廓线C’中的顶点顺序插入到轮廓线C的Vj之后，即分别将，…，V1插入到轮廓线C的Vj之后； K5、重复K2-K4，直到该类子偏置轮廓线都插入到轮廓线C中； K6、重复K1-K5，直到所有类别的子偏置轮廓线都插入到轮廓线C中，生成单连通区域内的单条填充轨迹线。
【专利摘要】本发明为一种二维轮廓区域单轨迹填充生成方法，属于增材制造(3D打印或快速原型)技术领域，其特征在于：对符合左手定则、无自相交和互相交的复杂二维区域轮廓线组，首先将其分解为单联通区域轮廓线组，并将构成单连通区域的内外轮廓线组连接成为单条轮廓线；对单连通区域的单条轮廓线进行偏置时，处理轮廓连接线保证等距偏置，并对轮廓线上的尖角进行截断处理；将各单连通区域轮廓线的偏置轮廓线进行分类，分别进行只进不出的连接和有进有出的连接，最终一个单连通区域生成一条连续的填充轨迹。该方法能够由任意复杂的二维轮廓区域有效生成数量最少的填充轨迹，提高成型效率。
【IPC分类】G06T11/40
【公开号】CN105488830
【申请号】CN201610033910
【发明人】黄常标, 林忠威, 林俊义, 刘斌, 江开勇, 路平
【申请人】华侨大学
【公开日】2016年4月13日
【申请日】2016年1月19日
【技术领域】
[0001]本发明属于增材制造(3D打印或快速原型)技术领域，特别涉及一种二维轮廓区域单轨迹填充生成方法。
【背景技术】
[0002]增材制造技术中的熔融沉积(FDM)工艺，其零件的成型需要通过熔丝填充分层后的二维轮廓区域完成。填充过程中，每一条单独的填充轨迹都需要熔丝喷嘴开和关、进和退、喷嘴清理等辅助动作。因此，二维轮廓区域填充的连续轨迹数量对填充效率和填充质量有着重要影响，连续轨迹的数量越少，需要的辅助时间越少，熔丝断点也越少，成型质量也就越好。
[0003]目前，增材制造中，二维轮廓区域的填充轨迹生成算法主要有zigzag填充、轮廓偏置填充、Hi Ibert曲线填充、Voronoi图构造螺旋轨迹等。Zigzag填充算法主要是通过连接区域内的平行扫描线来生成“弓”形填充轨迹，如果区域内部包含不需填充区域或在扫描线垂直方向上存在凹区域，则无法形成连续轨迹;轮廓偏置填充算法主要是轮廓线偏置实现区域填充，每条偏置轨迹之间是不连通的，对于复杂轮廓还将出现偏置轮廓自相交或互相交导致偏置轮廓分裂;Hilbert曲线填充算法通过Hilbert曲线来填充区域，由于区域轮廓的不规则，Hilbert曲线不可避免地被截断而产生中断;利用Voronoi图构造螺旋轨迹时，算法较为复杂，在轨迹间的过渡不符合一个偏置轨迹的规则，并且该方法在复杂轮廓下还是会出现很多的退刀次数。由此可见，这些算法虽然能够填充二维轮廓区域，但对于复杂二维轮廓区域，即使是单连通区域，也需多条的连续轨迹才能实现全区域的填充。因此，有必要研究新的复杂二维轮廓区域填充方法，生成连续填充轨迹数量最少的填充轨迹，提高填充效率和填充质量。
【发明内容】
[0004]发明的目的在于克服现有技术之不足，提供一种二维轮廓区域单轨迹填充生成方法，可以由任意复杂的单连通区域生成单条填充轨迹，并最终实现任意复杂二维轮廓区域的最少连续轨迹数量的填充轨迹生成，具有较高的鲁棒性和效率。
[0005]本发明解决其技术问题所采用的技术方案是:提供一种二维轮廓区域单轨迹填充生成方法，包括如下步骤:
[0006]Al、二维区域轮廓线组的分组和连接处理；
[0007]A2、单连通区域连接轮廓线的偏置处理；
[0008]A3、将每个单连通区域内的偏置轮廓线连接生成各单连通区域的单条轨迹。
[0009]优选的，所述步骤Al具体为:
[0010]B1、对符合左手定则、无自相交和互相交的二维区域轮廓线组进行处理，通过各轮廓线极值点判断各轮廓线是内轮廓还是外轮廓，并分别保存到内轮廓动态数组和外轮廓动态数组，计算各轮廓线的AABB包围盒；
[0011]B2、将复杂二维区域轮廓线组分解为单联通区域轮廓线组；
[0012]B3、将单连通区域的内、外轮廓线组连接成为单条轮廓线:设某个单连通区域的外轮廓顶点动态数组为Cf，其包含的内轮廓组为(C1，C2，…，Cn)。
[0013]优选的，所述步骤B2具体为:
[0014]Cl、从内轮廓数组中取出一个取出一个内轮廓C;
[0015]C2、将C的AABB包围盒依次与外轮廓数组中的各外轮廓AABB进行比较，判断C被哪些外轮廓包含；
[0016]C3、如果C只被一条外轮廓包含，则该外轮廓为C的直接包括外轮廓Cw;如果C被多条外轮廓包含，分别计算这些外轮廓的AABB包围盒面积，所求面积最小的外轮廓为内轮廓C的直接包括外轮廓Cw;
[0017]C4、将内轮廓C加入到其直接包括外轮廓Cw的内轮廓索引数组中；
[0018]C5、重复操作步骤①到④，直至所有内轮廓的均被插入各个外轮廓的内轮廓索引数组中；其结果是每一条外轮廓和若干条直接被包含的内轮廓构成一个单连通区域。
[0019]优选的，所述步骤B3具体为:
[0020]Dl、将外轮廓Cw的所有顶点建立一颗k-d树；
[0021]D2、取出Cw所包含的一个内轮廓Ulme (I，2，...，!!)}，分别将Cm每一个点作为搜索点，利用k-d树的查找到C沖最近点，求出距离，比较得到内外轮廓之间的最近点对(W，Vj(Cm)),其中Vi(Cw)为Cw中的第i个点，Vj(Cm)SCm中的第j个点；
[0022]D3、将两个轮廓合并为一个外轮廓:外轮廓Cw在Vi之后插入以Vj(Cm)为起始点的内轮廓Cm中的所有点，然后在Cm末端按顺序插入两个点Vj(Cm)和Vi(Cw)，生成新的Cw;
[0023]D4、清除原k-d树，以新Cw仓Il建新的k-d树；
[0024]D5、删除内轮廓U，跳转至②直至Cw所包含的内轮廓遍历，最终只得到一个轮廓线
Cffo
[0025]优选的，所述步骤A2具体为:
[0026]E1、对轮廓线进行基于顶点线段混合偏置，并去除偏置轮廓的自相交；
[0027]E2、在单连通区域连接轮廓线的第一次偏置时，对轮廓间连接线的偏置进行特殊处理以获得间距一致的轨迹行距；
[0028]E3、对轮廓中的狭长尖角进行截断处理后再进行偏置，以减轻轮廓狭长尖角对加工质量的影响。
[0029]优选的，所述步骤E2具体步骤为:
[0030 ] F1、对轮廓连接点(步骤D2中的各对Vi (Cw)和Vj (Cm))做标记；
[0031]F2、对轮廓连接线段Vi(Cw)Vj(Cm)和Vj(Cm)Vi(Cw)分别偏置0.5d(d为轮廓线偏置距离)，而轮廓线其它线段则偏置距离d。
[0032]优选的，所述步骤E3具体步骤为:
[0033]Gl、复制轮廓线C为C ;
[0034]G2、遍历轮廓线每个顶点，计算顶点的相邻两线段夹角Θ，夹角小于设定值(该值小于90°)时，对该顶点(设为V1)相邻轮廓线段进行截断处理；
[0035]G3、以顶点V1为起点，分别沿顶点两相邻轮廓线段方向，选取两个顶点Vh和Vi+k，要求Vi沿轮廓线到V1-k和Vi+k的距离相等，且要求V1-k和Vi+k之间距离大于L = 2d/cos (Θ/2)，其中d为轮廓线偏置距离；
[0036]G4、将轮廓线在顶AV1处的尖角截断，即删除Vni和V1+k之间的顶点，轮廓线修改为Vo、Vl、."、V1-k、Vi+k、...；
[0037]G5、在轮廓线C中对应顶点V1处的轮廓段，修改为“弓”形轮廓段，实现无空隙填充；
[0038]G6、对轮廓线C进行偏置，获得没有尖角的偏置轨迹。
[0039]优选的，所述步骤A3具体步骤为:
[0040]Hl、偏置轮廓线的分类处理，主要是对偏置自交后产生多个子偏置环进行分类编号；
[0041]H2、分别在每个单连通区域内，进行无全局自相交偏置轮廓线的连接，即对分类编号为I的偏置轮廓线组由外向内进行只进不出的连接，设外层轮廓线为O，直接相邻的内层偏置轮廓线为C;
[0042]H3、分别在每个单连通区域内，对全局自交偏置轮廓线生成的子偏置轮廓线组进行有进有出连接，设外层轮廓线C，其直接相邻的子偏置轮廓为C’。
[0043]优选的，所述步骤Hl具体步骤为:
[0044]I1、令单连通区域的连接轮廓线的分类编号为n(n的初始值为I);
[0045]12、进行轮廓线偏置，偏置时没有出现全局自相交，则新偏置轮廓线的分类编号为η;如果出现全局自相交，偏置后是产生多个子偏置轮廓线，则分别设置新生成的子偏置轮廓线的分类编号为η++;
[0046]13、重复操作步骤12直至确定所有偏置轮廓线的分类编号。
[0047]优选的，所述步骤Η2具体步骤为:
[0048]Jl、遍历轮廓线Cw的顶点，找到最平坦的顶点V1，在该处生成一个距离为轮廓偏置值d的切口，其切口顶点设为V1、Vi+1;按照Vi+1，Vi+2，…，Vn，Vo，V1，…，Vi的顺序，重新存储轮廓线Cw的顶点动态数组；
[0049]J2、分别从Vi 和Vi+1发出与线段ViVi+工的夹角为给定值的射线，与各内层偏置轮廓线相交，获得两个对应顶点Vj和Vj+1;
[0050]】3、将偏置轮廓线(:中的顶点，分别以￥」+1^+2，-_^()，￥1^_，％加入到轮廓线(>顶点动态数组的1之后；
[0051]J4、重复J2-J3的处理，直到分类编号为I的所有偏置轮廓线都处理完毕，获得单一轮廓线Cw。
[0052]优选的，所述步骤H3具体步骤为:
[0053]K1、取出一个类别的子偏置轮廓线组；
[0054]K2、依次从外到内取出第k条(k初值为I)子偏置轮廓线C’，遍历子偏置轮廓线C’的顶点，找到相对平坦的顶点V1;要求当k>l时，第k条子偏置轮廓线上的顶点V1，与第(k-Ι)条子偏置轮廓线上的顶点1要错开一定角度，保证两条轮廓线上的切口没有任何重叠；
[0055]K3、在子偏置轮廓线C’上，以V1A为中心，将V1点相邻前后两线段的夹角平分线分别偏置0.5d，并分别与外层轮廓线C和子偏置轮廓线C’求交，其中与子偏置轮廓线C’的交点设为V1、Vi+1，原Vi点删除;而与外层轮廓线C的交点设为Vj和Vj+1;
[0056]K4、若k为奇数，则将子偏置轮廓线C’中的顶点以逆序插入到轮廓线C的Vj之后，SP分别将Vi，Vh，…V1，，Vo，Vn，Vn-1，…，Vi+1顺序插入到C的Vj之后;若k为偶数，则将子偏置轮廓线^中的顶点顺序插入到轮廓线⑶勺…之后’即分别将^^…^^^’…^插入到轮廓线C的Vj之后；
[0057]K5、重复K2-K4，直到该类子偏置轮廓线都插入到轮廓线C中；
[0058]Κ6、重复Κ1-Κ5，直到所有类别的子偏置轮廓线都插入到轮廓线C中，生成单连通区域内的单条填充轨迹线。
[0059]本发明的有益效果是:
[0060]1、本发明提供的二维轮廓区域单轨迹填充生成方法，能够有效生成任意复杂二维轮廓区域的、最少数量的填充轨迹，且适应性强；
[0061]2、通过将单连通区域的内外轮廓线连接为单条轮廓线后，再进行偏置和连接，可以保证一个单连通区域内只生成一条连续的填充轨迹，同时简化由任意单连通区域生成单条轨迹线的编程实现难度，同时保证结果的可靠性。
[0062]以下结合附图及实施例对本发明作进一步详细说明；但本发明的一种二维轮廓区域单轨迹填充生成方法不局限于实施例。
【附图说明】
[0063]图1是本发明的流程不意图；
[0064]图2是本发明内、外轮廓判断示意图；
[0065]图3是本发明轮廓线的数据结构示意图；
[0066]图4是本发明的单联通区域划分示意图；
[0067]图5是本发明的内外轮廓线最近点示意图；
[0068]图6是本发明的内外轮廓线连接示意图；
[0069]图7是本发明的单连通区域轮廓连接示意图；
[0070]图8是本发明的轮廓线混合偏置示意图；
[0071]图9是本发明的偏置轮廓自交去除示意图；
[0072]图10是本发明的轮廓连接线偏置示意图；
[0073]图11是本发明的轮廓连接线修正偏置示意图；
[0074]图12是本发明的轮廓连尖角截断原理示意图；
[0075]图13是本发明的轮廓连尖角截断后轮廓示意图；
[0076]图14是本发明的偏置轮廓线分类示意图；
[0077]图15是本发明的偏置轮廓线组只进不出的连接原理示意图；
[0078]图16是本发明的偏置轮廓线组只进不出的连接示意图；
[0079]图17是本发明的偏置轮廓线组只进不出的连接效果图；
[0080]图18是本发明的偏置轮廓线组有进有出连接切口示意图；
[0081]图19是本发明的偏置轮廓线组有进有出连接效果示意图；
[0082]图20是本发明的单连通区域单轨迹填充实例一；
[0083]图21是本发明的单连通区域单轨迹填充实例二。
【具体实施方式】
[0084]实施例
[0085]参见图1至图21所示，本发明的一种二维轮廓区域单轨迹填充生成方法，包括如下步骤:
[0086]Al、二维区域轮廓线组的分组和连接处理；
[0087]A2、单连通区域连接轮廓线的偏置处理；
[0088]A3、将每个单连通区域内的偏置轮廓线连接生成各单连通区域的单条轨迹。
[0089]优选的，所述步骤Al具体为:
[0090]B1、对符合左手定则、无自相交和互相交的二维区域轮廓线组进行处理，通过各轮廓线极值点判断各轮廓线是内轮廓还是外轮廓，并分别保存到内轮廓动态数组和外轮廓动态数组，计算各轮廓线的AABB包围盒；
[0091 ]其中内、外轮廓的具体判断方法为:如图2中，Vi为Y轴方向上的极小值点，则矢量可计算ei = Vi_V1-1和e2 = Vi+i_Vi，如果矢量e = ei Xe2的Z轴分量为正，则该轮廓线为逆时针方向，即为外轮廓线，如图2;如果e的Z轴分量为负，则该轮廓线为顺时针方向，即为内轮廓线。
[0092]轮廓线的数据结构如图3所示，其中CVertex为顶点类。轮廓线动态数组同样采用C++标准模板库中的vector容器来实现，其中外轮廓线动态数组为vector〈CContour>vec_OutContour，内轮廓线动态数组为则轮廓线动态数组为vector〈CContour>vec_InContour。
[0093]B2、将复杂二维区域轮廓线组分解为单联通区域轮廓线组；
[0094]B3、将单连通区域的内、外轮廓线组连接成为单条轮廓线:设某个单连通区域的外轮廓顶点动态数组为Cf，其包含的内轮廓组为(C1，C2，…，Cn)。
[0095]优选的，所述步骤B2具体为:
[0096]Cl、从内轮廓数组中取出一个取出一个内轮廓C;
[0097]C2、将C的AABB包围盒依次与外轮廓数组中的各外轮廓AABB进行比较，判断C被哪些外轮廓包含；即比较轮廓线类中的左下角和右上角的坐标值，如果满足C的左下角坐标分量值均大于某外轮廓对应值、且C的右上角坐标分量值均小于某外轮廓对应值，则C被该外轮廓线包含；
[0098]C3、如果C只被一条外轮廓包含，则该外轮廓为C的直接包括外轮廓Cw;如果C被多条外轮廓包含，分别计算这些外轮廓的AABB包围盒面积，所求面积最小的外轮廓为内轮廓C的直接包括外轮廓Cw;
[0099]C4、将内轮廓C加入到其直接包括外轮廓Cw的内轮廓索引数组中；即图3的vec_InnerContour中。
[0100]C5、重复操作步骤Cl到C4，直至所有内轮廓的均被插入各个外轮廓的内轮廓索引数组中；其结果是每一条外轮廓和若干条直接被包含的内轮廓构成一个单连通区域。如图4所示，图中外轮廓线I和内轮廓2、5构成一个单联通区域;外轮廓线3和内轮廓4构成一个单联通区域;外轮廓线6和内轮廓7构成一个单联通区域。
[0101]优选的，所述步骤B3具体为:
[0102]Dl、将外轮廓Cw的所有顶点建立一颗k-d树；
[0103]D2、取出Cw所包含的一个内轮廓Ulme (I，2，...，!!)}，分别将Cm每一个点作为搜索点，利用k-d树的查找到C沖最近点，求出距离，比较得到内外轮廓之间的最近点对(W，Vj (Cm))，如图5所示，其中Vi ( Cf)为Cw中的第i个点，Vj ( Cm)为Cm中的第j个点；
[0104]D3、将两个轮廓合并为一个外轮廓:外轮廓Cw在Vi之后插入以Vj(Cm)为起始点的内轮廓Cm中的所有点，然后在Cm末端按顺序插入两个点Vj(Cm)和Vi(Cw)，生成新的Cw;如图6所不O
[0?05] D4、清除原k-d树，以新Cw仓Il建新的k-d树；
[0106]D5、删除内轮廓U，跳转至②直至Cw所包含的内轮廓遍历，最终只得到一个轮廓线Cw。图7所示。 [0107]优选的，所述步骤A2具体为:
[0108]E1、对轮廓线进行基于顶点线段混合偏置，并去除偏置轮廓的自相交；
[0109]①顶点线段混合偏置法:
[0110]在轮廓线的凸点使用顶点偏置，在凹点使用线段整体偏置，使得凸点一定不会出现自相交，而凹点必定会发生自相交。如图8所示，A点和B点为多边形上两点，其中A点为凹点，B点为凸点。A点使用整体线段偏置，将会得到两个点A’和A〃，B点使用顶点偏置将会得到I个点B’。其中，顶点的凹凸性判断方法为:假设点A、B、C为轮廓线上连续的3个点，设矢量的= B-A，e2 = C_B，e3为ei逆时针旋转90°，e4为e2逆时针旋转90°。计算m= (Θ3+Θ4).(e2_ei)值。如果m>0，B点为凸点，否则表示B点为凹点。
[0111]②偏置轮廓自相交的去除，如图9:
[0112]轮廓线偏置过程中，逐个点偏置填入点表，若是线段偏置则为该偏置点打上标记，每次偏置一个点，将新生点和前一点组成线段，并基于K-D树验证是否和前面的曲线有相交；
[0113]如果有相交，求出交点Rs坐标；
[0114]提取新生成的子偏置轮廓环，查找该子偏置轮廓环中是否存在线段偏置的标记点，如有，则去除该子偏置轮廓环，如图8中顶点A’j'lPV:构成的子偏置轮廓环中，A’、A"均为线段偏置标记点，因此该子偏置轮廓环需要被去除；如果没有线段偏置标记点，则判断生成的子偏置轮廓环的旋向，旋向为顺时针，则去除该子偏置轮廓环，如图9中￥5、^^+1、￥5+1、￥5等顶点构成的子偏置轮廓环需要去除，否则保存新生成的子偏置轮廓环，如如图9中右侧粗实线子偏置轮廓环则保留；
[0115]完成自相交的去除后最终得到无自相交的偏置轮廓线。
[0116]E2、在单连通区域连接轮廓线的第一次偏置时，对轮廓间连接线的偏置进行特殊处理以获得间距一致的轨迹行距；
[0117]E3、对轮廓中的狭长尖角进行截断处理后再进行偏置，以减轻轮廓狭长尖角对加工质量的影响。
[0118]优选的，所述步骤E2具体步骤为:
[0119]F1、对轮廓连接点(步骤D2中的各对Vi (Cw)和Vj (Cm))做标记；
[0120]F2、对轮廓连接线段Vi(Cw)Vj(Cm)和Vj(Cm)Vi(Cw)分别偏置0.5d(d为轮廓线偏置距离)，而轮廓线其它线段则偏置距离d。如图11所示的实线，其中虚线间距离为2d。
[0121]优选的，所述步骤E3具体步骤为:
[0122]Gl、复制轮廓线C为C ;
[0123]G2、遍历轮廓线每个顶点，计算顶点的相邻两线段夹角Θ，夹角小于设定值(该值小于90°)时，对该顶点(设为V1)相邻轮廓线段进行截断处理；
[0124]G3、以顶点V1为起点，分别沿顶点两相邻轮廓线段方向，选取两个顶点Vh和Vi+k，要求Vi沿轮廓线到V1-k和Vi+k的距离相等，且要求V1-k和Vi+k之间距离大于L = 2d/cos (Θ/2)，其中d为轮廓线偏置距离；
[0125]G4、将轮廓线在顶AV1处的尖角截断，即删除Vni和V1+k之间的顶点，轮廓线修改为Vo、Vl、."、V1-k、Vi+k、...；
[0126]G5、在轮廓线C中对应顶点V1处的轮廓段，修改为“弓”形轮廓段，实现无空隙填充；基本方法为:
[0127]a)根据夹角找出狭长尖角，找出垂直于夹角角平分线的线段AB，并且长度为d(如图12所示)；
[0128]b)以d为偏置距离多次偏置线段AB，并延长交于夹角的相邻线段，直至到偏置线段长度大于L，然后沿两个方向偏置角平分线0.5d偏置距离，如图12所示；
[0129]c)修改轮廓线C，使之在尖角处形成“弓”曲线，如图13所示。
[0130]G6、对轮廓线C进行偏置，获得没有尖角的偏置轨迹。如图12中轮廓线C0FF。
[0131]优选的，所述步骤A3具体步骤为:
[0132]Hl、偏置轮廓线的分类处理，主要是对偏置自交后产生多个子偏置环进行分类编号；
[0133]H2、分别在每个单连通区域内，进行无全局自相交偏置轮廓线的连接，即对分类编号为I的偏置轮廓线组由外向内进行只进不出的连接，设外层轮廓线为O，直接相邻的内层偏置轮廓线为C;其连接原理如图15。
[0134]H3、分别在每个单连通区域内，对全局自交偏置轮廓线生成的子偏置轮廓线组进行有进有出连接，设外层轮廓线C，其直接相邻的子偏置轮廓为C’。
[0135]优选的，所述步骤Hl具体步骤为:
[0136]I1、令单连通区域的连接轮廓线的分类编号为n(n的初始值为I);即图3中CContour类内int m_nClassify变量为n(n的初始值为I)。
[0137]12、进行轮廓线偏置，偏置时没有出现全局自相交，则新偏置轮廓线的分类编号为η;如果出现全局自相交，偏置后是产生多个子偏置轮廓线，则分别设置新生成的子偏置轮廓线的分类编号为η++;
[0138]13、重复操作步骤12直至确定所有偏置轮廓线的分类编号。偏置轮廓的分类效果如图14。
[0139]优选的，所述步骤Η2具体步骤为:
[0140]Jl、遍历轮廓线Cw的顶点，找到最平坦的顶点V1，在该处生成一个距离为轮廓偏置值d的切口，其切口顶点设为V1、Vi+1;按照Vi+1，Vi+2，…，Vn，Vo，V1，…，Vi的顺序，重新存储轮廓线Cw的顶点动态数组；
[0141]J2、分别从Vi和Vi+1发出与线段ViVi+工的夹角为给定值的射线，与各内层偏置轮廓线相交，获得两个对应顶点Vj和Vj+1;
[0142]】3、将偏置轮廓线(:中的顶点，分别以￥」+1^+2，-_1，￥()，￥1^_，％加入到轮廓线(>顶点动态数组的1之后；
[0143]J4、重复J2-J3的处理，直到分类编号为I的所有偏置轮廓线都处理完毕，获得单一轮廓线Cw。最后连接示意图如图16，连接效果如图17。
[0144]优选的，所述步骤H3具体步骤为:
[0145]K1、取出一个类别的子偏置轮廓线组；
[0146]K2、依次从外到内取出第k条(k初值为I)子偏置轮廓线C’，遍历子偏置轮廓线C’的顶点，找到相对平坦的顶点V1;要求当k>l时，第k条子偏置轮廓线上的顶点V1，与第(k-Ι)条子偏置轮廓线上的顶点1要错开一定角度，保证两条轮廓线上的切口没有任何重叠；
[0147]K3、如图18所示，在子偏置轮廓线C’上，以V;为中心，将V;相邻前后两线段的夹角平分线分别偏置0.5d，并分别与外层轮廓线C和子偏置轮廓线C ’求交，其中与子偏置轮廓线C’的交点设为V1、Vi+1，原Vi点删除;而与外层轮廓线C的交点设为Vj和Vj+1;
[0148]K4、若k为奇数，则将子偏置轮廓线C’中的顶点以逆序插入到轮廓线C的Vj之后，SP分别将Vi，Vh，…V1，，Vo，Vn，Vn-1，…，Vi+1顺序插入到C的Vj之后;若k为偶数，则将子偏置轮廓线^中的顶点顺序插入到轮廓线⑶勺…之后’即分别将^^…^^^’…^插入到轮廓线C的Vj之后;连接示意图如19所示。
[0149]K5、重复K2-K4，直到该类子偏置轮廓线都插入到轮廓线C中；
[0150]K6、重复K1-K5，直到所有类别的子偏置轮廓线都插入到轮廓线C中，生成单连通区域内的单条填充轨迹线。
[0151]图20和21为本发明的实施实例。
[0152]上述实施例仅用来进一步说明本发明的一种二维轮廓区域单轨迹填充生成方法，但本发明并不局限于实施例，凡是依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均落入本发明技术方案的保护范围内。
【主权项】
1.一种二维轮廓区域单轨迹填充生成方法，其特征在于，包括如下步骤: Al、二维区域轮廓线组的分组和连接处理； A2、单连通区域连接轮廓线的偏置处理； A3、将每个单连通区域内的 偏置轮廓线连接生成各单连通区域的单条轨迹。2.根据权利要求1所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤Al具体为: B1、对符合左手定则、无自相交和互相交的二维区域轮廓线组进行处理，通过各轮廓线极值点判断各轮廓线是内轮廓还是外轮廓，并分别保存到内轮廓动态数组和外轮廓动态数组，计算各轮廓线的AABB包围盒； B2、将复杂二维区域轮廓线组分解为单联通区域轮廓线组； B3、将单连通区域的内、外轮廓线组连接成为单条轮廓线:设某个单连通区域的外轮廓顶点动态数组为Cf，其包含的内轮廓组为(C1，C2，…，Cn)。3.根据权利要求2所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤B2具体为: Cl、从内轮廓数组中取出一个取出一个内轮廓C; C2、将C的AABB包围盒依次与外轮廓数组中的各外轮廓AABB进行比较，判断C被哪些外轮廓包含； C3、如果C只被一条外轮廓包含，则该外轮廓为C的直接包括外轮廓Cw;如果C被多条外轮廓包含，分别计算这些外轮廓的AABB包围盒面积，所求面积最小的外轮廓为内轮廓C的直接包括外轮廓Cw; C4、将内轮廓C加入到其直接包括外轮廓Cw的内轮廓索引数组中； C5、重复操作步骤①到④，直至所有内轮廓的均被插入各个外轮廓的内轮廓索引数组中；其结果是每一条外轮廓和若干条直接被包含的内轮廓构成一个单连通区域。4.根据权利要求2所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤B3具体为: Dl、将外轮廓Cw的所有顶点建立一颗k-d树； D2、取出Cw所包含的一个内轮廓Ulme (I，2，…，η)}，分别将Cm每一个点作为搜索点，利用k - d树的查找到C w中最近点，求出距离，比较得到内外轮廓之间的最近点对(V i (C w )，V j(Cm))，其中Vi(Cw)为Cw中的第i个点，Vj(Cm)SCm中的第j个点； D3、将两个轮廓合并为一个外轮廓:外轮廓Cw在Vi之后插入以Vj(U)为起始点的内轮廓Cm中的所有点，然后在Cm末端按顺序插入两个点Vj(Cm)和Vi(Cw)，生成新的Cw; D4、清除原k-d树，以新Cw创建新的k-d树； D5、删除内轮廓Cm，跳转至②直至Cw所包含的内轮廓遍历，最终只得到一个轮廓线Cf。5.根据权利要求1所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤A2具体为: E1、对轮廓线进行基于顶点线段混合偏置，并去除偏置轮廓的自相交； E2、在单连通区域连接轮廓线的第一次偏置时，对轮廓间连接线的偏置进行特殊处理以获得间距一致的轨迹行距； E3、对轮廓中的狭长尖角进行截断处理后再进行偏置，以减轻轮廓狭长尖角对加工质量的影响。6.根据权利要求5所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤E2具体步骤为: Fl、对轮廓连接点(步骤D2中的各对Vi (Cw)和Vj (Cm))做标记； F2、对轮廓连接线段Vi(Cw)Vj(Cm)和Vj(Cm)Vi(Cw)分别偏置0.5d(d为轮廓线偏置距离)，而轮廓线其它线段则偏置距离d。7.根据权利要求5所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤E3具体步骤为: Gl、复制轮廓线C为; G2、遍历轮廓线每个顶点，计算顶点的相邻两线段夹角Θ，夹角小于设定值(该值小于90°)时，对该顶点(设为V1)相邻轮廓线段进行截断处理； G3、以顶点V1为起点，分别沿顶点1的两相邻轮廓线段方向，选取两个顶点Vni和V1+k，要求Vi沿轮廓线到V1-k和Vi+k的距离相等，且要求V1-k和Vi+k之间距离大于L = 2d/COS(0/2)，其中d为轮廓线偏置距离； G4、将轮廓线在顶点1处的尖角截断，即删除Vni和V1+k之间的顶点，轮廓线C修改为Vo、V1、."、V1-k、Vi+k、…； G5、在轮廓线C中对应顶点V1处的轮廓段，修改为“弓”形轮廓段，实现无空隙填充； G6、对轮廓线C'进行偏置，获得没有尖角的偏置轨迹。8.根据权利要求2所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤A3具体步骤为: Hl、偏置轮廓线的分类处理，主要是对偏置自交后产生多个子偏置环进行分类编号； H2、分别在每个单连通区域内，进行无全局自相交偏置轮廓线的连接，即对分类编号为I的偏置轮廓线组由外向内进行只进不出的连接，设外层轮廓线为Cw，直接相邻的内层偏置轮廓线为C; H3、分别在每个单连通区域内，对全局自交偏置轮廓线生成的子偏置轮廓线组进行有进有出连接，设外层轮廓线C，其直接相邻的子偏置轮廓为C’。9.根据权利要求8所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤Hl具体步骤为: 11、令单连通区域的连接轮廓线的分类编号为n(n的初始值为I); 12、进行轮廓线偏置，偏置时没有出现全局自相交，则新偏置轮廓线的分类编号为η;如果出现全局自相交，偏置后是产生多个子偏置轮廓线，则分别设置新生成的子偏置轮廓线的分类编号为η++; 13、重复操作步骤12直至确定所有偏置轮廓线的分类编号。10.根据权利要求8所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤Η2具体步骤为: J1、遍历轮廓线Cw的顶点，找到最平坦的顶点V1，在该处生成一个距离为轮廓偏置值d的切口，其切口顶点设为V1、Vi+1;按照Vi+1，Vi+2，…，Vn，Vo，V1，…，Vi的顺序，重新存储轮廓线Cw的顶点动态数组； J2、分别从Vi和Vi+1发出与线段ViVi+j^夹角为给定值的射线，与各内层偏置轮廓线相交，获得两个对应顶点Vj和Vj+1; J3、将偏置轮廓线C中的顶点，分别以Vj+1，Vj+2，...，VwV^V1，…，Vj加入到轮廓线Cw顶点动态数组的Vi之后； J4、重复J2-J3的处理，直到分类编号为I的所有偏置轮廓线都处理完毕，获得单一轮廓线Cw011.根据权利要求8所述的一种二维轮廓区域单轨迹填充生成方法，其特征在于:所述步骤H3具体步骤为: Kl、取出一个类别的子偏置轮廓线组； K2、依次从外到内取出第k条(k初值为I)子偏置轮廓线C’，遍历子偏置轮廓线C’的顶点，找到相对平坦的顶点V1;要求当k>l时，第k条子偏置轮廓线上的顶点V1，与第(k-Ι)条子偏置轮廓线上的顶点1要错开一定角度，保证两条轮廓线上的切口没有任何重叠； K3、在子偏置轮廓线C’上，以1点为中心，将V1点相邻前后两线段的夹角平分线分别偏置0.5d，并分别与外层轮廓线C和子偏置轮廓线C’求交，其中与子偏置轮廓线C’的交点设为V1、Vi+1，原Vi点删除;而与外层轮廓线C的交点设为Vj和Vj+1; K4、若k为奇数，则将子偏置轮廓线C’中的顶点以逆序插入到轮廓线C的Vj之后，即分别将Vi，V1-1，…V1，，Vo，Vn，Vn-1，…，Vi+1顺序插入至IjC的Vj之后;若k为偶数，则将子偏置轮廓线C’中的顶点顺序插入到轮廓线C的Vj之后，即分别将，…，V1插入到轮廓线C的Vj之后； K5、重复K2-K4，直到该类子偏置轮廓线都插入到轮廓线C中； K6、重复K1-K5，直到所有类别的子偏置轮廓线都插入到轮廓线C中，生成单连通区域内的单条填充轨迹线。
【专利摘要】本发明为一种二维轮廓区域单轨迹填充生成方法，属于增材制造(3D打印或快速原型)技术领域，其特征在于：对符合左手定则、无自相交和互相交的复杂二维区域轮廓线组，首先将其分解为单联通区域轮廓线组，并将构成单连通区域的内外轮廓线组连接成为单条轮廓线；对单连通区域的单条轮廓线进行偏置时，处理轮廓连接线保证等距偏置，并对轮廓线上的尖角进行截断处理；将各单连通区域轮廓线的偏置轮廓线进行分类，分别进行只进不出的连接和有进有出的连接，最终一个单连通区域生成一条连续的填充轨迹。该方法能够由任意复杂的二维轮廓区域有效生成数量最少的填充轨迹，提高成型效率。
【IPC分类】G06T11/40
【公开号】CN105488830
【申请号】CN201610033910
【发明人】黄常标, 林忠威, 林俊义, 刘斌, 江开勇, 路平
【申请人】华侨大学
【公开日】2016年4月13日
【申请日】2016年1月19日
最新回复(0)