CN112873855A - 一种3dp工艺中stl模型中心排样方法 - Google Patents

Abstract

本发明为一种3DP工艺中STL模型中心排样方法，该方法包括以下内容：得到所有待排样STL模型后，设定Z方向为零件成型方向，首先计算每个STL模型XOY平面最小不规则外包框的投影面积和无重复法向量数量，根据最小不规则外包框的投影面积和无重复法向量数量确定模型摆放顺序，优先摆放投影面积大、模型复杂程度高的STL模型；成型空间中心位置优先摆放投影面积大、零件复杂程度高的零件，剩余的零件按照模型摆放顺序寻找距中心距离最近的排样位置进行布置。旨在解决3DP工艺中不规则零件的受成型方向限制不能多方向旋转来确定最优排样位置且排样密度有待提高的问题。

Description

一种3DP工艺中STL模型中心排样方法

技术领域

本发明涉及零件排样方法领域，尤其涉及一种3DP工艺中STL模型中心排样方法。

背景技术

3DP工艺采用了和传统二维喷墨打印类似的技术，通过喷头喷出粘结剂将粉末粘结成整体来制作零部件。利用了离散化的思想将要进行打印的零件切片化，然后将每一层中需要打印的路径输入到计算机中，通过计算机控制打印机的逐层打印，相对于传统的材料去除(切削加工)技术，是一种“自下而上”材料累加的制造方法。目前大部分3DP工艺使用STL格式文件进行贴合零件实际表面，通过对STL模型切片得到每一层的轮廓信息逐层制造零件。

随着3D打印技术的研究进步，越来越多的产业对其进行了应用，进行制造生产。制造业中优化排样应用范围非常广法，在工程应用领域中，型材和棒材下料、冲裁件排样、玻璃切割、报刊排版、家具下料、服装裁件、皮革裁剪、造船、车辆和发电设备生产中都存在大量的下料问题。从计算复杂性理论上，优化排样问题是具有最高复杂性的NP完全问题，同时其具有几何特性，对矩形件、异形件排样离不开图形运算，排样问题至今尚无有效的求解方法。所以需要高效的几何计算工具和快速的排样算法来解决排样问题。

传统三维零件排样方法主要是对实际零件模型进行二维矩形包围或最小长方体包围，之后对包围框进行排样。二维矩形包围的方法简化了三维零件排样的计算难度，将三维空间位置计算问题转化为二维平面问题，但该方法增加了零件的占用面积，并不能很好的提高排样密度。

3DP工艺中也存在成型零件的排列问题，由于工艺特点，零件之间不能实现紧密排列，粉床中心的成型质量要高于四周。并且零件的成型方向由于粘结剂渗透误差的原因而受到限制，零件不能绕XY轴自由旋转，所以3DP工艺中零件排样技术不同于传统的制造工艺，三维空间位置计算复杂度高，会提高算法的计算成本，3DP工艺中零件成型方向对成型精度有很大影响，在零件排样时，不能通过对零件进行多个方向旋转找到最优的排样位置。本方法针对3DP工艺中STL模型排样问题提出中心排样方法解决排样问题。

发明内容

针对现有排样技术上的不足，本发明旨在解决3DP工艺中不规则零件的受成型方向限制不能多方向旋转来确定最优排样位置且排样密度有待提高的问题，提出一种3DP工艺中STL模型中心排样方法。

本发明解决所述技术问题采用的技术方案是：

一种3DP工艺中STL模型中心排样方法，特征在于，该方法包括以下内容：

STL模型投影：得到所有待排样STL模型后，设定Z方向为零件成型方向，首先计算每个STL模型XOY平面最小不规则外包框的投影面积和无重复法向量数量，根据最小不规则外包框的投影面积和无重复法向量数量确定模型摆放顺序，优先摆放投影面积大、模型复杂程度高的STL模型；

中心排样：成型空间中心位置优先摆放投影面积大、零件复杂程度高的零件，剩余的零件按照模型摆放顺序寻找距中心距离最近的排样位置进行布置。

中心排样的具体过程是：计算所有待排样模型投影平面的最小外接圆，以第一个排入模型为中心，沿圆周方向按照排样顺序依次排入模型，每次排入的模型的外接圆都至少与一个已排入模型外接圆相切，再通过几何关系得到待排入模型的初始位置；一周排完后进行下一周的排布，直至所有模型按照外接圆相切的方式排好；

去除所有模型的外接圆，将所有模型按照模型摆放顺序向中心靠接，找到每个模型最优的摆放位置和姿态，获得整个排样图；再将整体排样图中心移动到坐标系中心，完成模型排样。

STL模型投影的过程是：首先确定零件的成型方向并将模型上所有点投影到投影平面，然后将投影平面坐标系进行扇区划分，找到每个扇区内的最远投影点作为外轮廓计算点，计算出模型的最小不规则外包框。本排样方法中提出STL模型投影方式，对零件进行二维投影，将三维零件排样问题简化为二维不规则排样问题。

中心排样包括：排序方案、排样路径和多边形重叠检测。

基于3DP铺粉过程的研究发现，成型空间中间的粉床成型质量要优于四周，因此本排样方法提出中心排样策略，中心排样策略的过程是：首先成型空间中心位置优先摆放投影面积大、零件复杂程度高的零件，剩余的零件按照零件顺序寻找距中心距离最近的排样位置。

排序方案：需要将打印的所有模型进行排序，计算所有模型的投影面积和无重复法向量数量。由于这两个参数数量级上差别较大，需要对其进行归一化处理，并加上对应权值作为Key值进行零件排序，排样时按照顺序依次排入零件。

排样路径：零件排序完成后计算所有零件投影的最小外接圆，将首个零件放在坐标系中心，其他零件依次排入。首先需定义零件排样层进行外接圆排样，排样层记录每一层零件位置信息，定义每一层起始和终止零件。每层排入结束后开始下一层的零件排样，与上一层路径反向，通过该方法实现零件的中心排样。每个零件中心坐标计算规则全部相同，由相邻两个零件位置及尺寸确定，之后按照相同规则排放零件。当零件摆放完成后，将零件向中心靠拢来消除间隙增加排样密度。

每次零件向中心靠接一个单位并对零件进行绕成型方向Z轴旋转，当零件位置所有旋转角度外包框全部重叠，零件后退一个单位并以该后退一个单位时所对应的第一个可行的排样姿态和中心坐标作为模型最终的排样位置，此时零件靠接完成。

重叠检测：多边形重叠检测是排样问题的重要计算步骤，目前的排样技术研究者大多对高效的零件分离算法进行研究，好的重叠检测方法可以提高排样效率并得到更好的排样效果。本方法中采用分离轴检测算法并进行改进，将投影计算得到的最小不规则外包框进行分割，以最小不规则外包框的中心点为顶点将多边形拆分成多个小三角形，得到更多潜在分离轴，再应用分离轴检测算法进行凹多边形重叠检测，只要有一个小三角形重叠，则认为重叠，不可行。

与现有技术相比，本发明的有益效果是：

本发明的实质性特点是：由于3DP工艺中铺砂工艺特点，成型空间中心部分砂床的成型质量要高于四周，本发明针对3DP工艺中零件排样方法进行研究，提出了适合工艺特点的中心排样方法，并且对3DP工艺通用格式STL文件提出了计算最小不规则外包框投影的方式来作为模型排序的依据，将三维零件排样问题简化为二维不规则排样问题。

目前大多数排样算法中主要针对二维制造工艺中的零件排样问题，例如服装加工、一刀切问题，3DP工艺中零件排样研究较少，或是对打印批次规划进行研究。三维零件排样问题计算难度大，需要考虑多种复杂情况，零件的重叠检测计算量远超过二维平面情况，现有排样方法中三维零件排样问题大部分简化为二维矩形排样问题，传统方法在某一平面对零件进行最小矩形包围，简化了零件重叠检测计算，但增加了零件的占用面积，相对会降低排样密度，降低生产效率。本申请针对3DP工艺特点，对三维零件进行二维投影，在投影平面计算零件的最小不规则外包围框代替零件投影轮廓，对比传统矩形包围零件的方法，本申请计算的最小不规则外包围框减少了零件的分配面积，提高了零件排样密度。

3DP工艺中零件的打印过程有固定的方向，首先需要对三维模型进行离散化操作，将其分割为许多的层，然后将每一层所对应的数字信息输入到计算机当中，计算机通过分析处理指挥打印机进行层与层之间的粘连。而在离散的过程当中，需要对每一层的厚度以及打印成型件时的打印方向进行设定，不同的分层厚度与成型方向能够对成型制件的精度以及打印的效率产生明显的影响，本排样方法中假定3DP工艺中零件成型方向为Z方向，按照成型方向对模型进行摆放，零件不能绕X、Y轴旋转，对三维模型排样进行简化，将三维排样问题变为XOY平面的二维排样。传统排样通常对零件进行最小矩形外包框包围，本方法中对零件进行最小不规则外包围框包围(零件投影后计算所得二维多边形)，可以提高排样密度，提高工艺成型效率。

此外，传统的重叠检测方法中有多种判断零件是否重叠的方法，方法1：主要通过两个判据来判断零件是否重叠，判据1，零件A所有顶点都在零件B之外，并且B所有顶点也都在零件A之外；判据2，A的每条边都不与B的边相交。该方法计算复杂度高、数据量大。方法2：临界多边形方法，临界多边形方法是判别两个多边形相互关系的一个非常有效的方法，但是由于直接求解两个凹多边形的临界多边形比较困难，长期以来限制了其应用。优选地本发明计算得到的多边形，采用分离轴检测的物理碰撞方法对多边形进行重叠检测。对多边形的每一个顶点(外轮廓的角点上)在投影轴进行投影，保留投影的最低点和最高点为一条线段，如果两个多边形在分离轴上的投影线段存在重叠，则多边形相交，否则多边形分离。本申请的这种重叠检测方法在二维排样中存在通用性。

附图说明

图1为坐标系扇区划分；

图2为线段插点判断以及插点方式；

图3为单个扇区外轮廓计算；

图4为插点前后扇区外包框计算对比；

图5为模型外接圆形排样策略示意图；

图6为分离轴算法投影计算示例；

图7为投影外接圆排样图；

图8为靠接前多边形外接圆去除；

图9-12为模型靠接过程示例；

图13为模型靠接完成后排样图；

图14为待排模型外包框计算图；

图15为软件中模型排样图。

具体实施方式

下面结合实施例及附图进一步解释本发明，但并不以此作为对本申请保护范围的限定。

本发明一种3DP工艺中STL模型中心排样方法，包括STL模型投影算法和中心排样策略。

STL模型XOY平面最小不规则外包框的计算过程是；

1)首先计算STL模型XOY平面的中心坐标：计算STL模型在XOY平面的最小矩形外包框，规定矩形外包框的中心坐标为该STL模型中心坐标；得到STL模型中心坐标后，将STL模型移动至坐标系中心，使STL模型中心坐标与坐标系中心重合；

2)对坐标系的四个象限进行均匀扇区划分，有60-80个扇区；扇区划分如图1，后续外包框的确定全部基于此扇区进行计算。扇区数量越少，STL模型最小外包框精度越低，适合轮廓相对简单的模型；扇区数量越多，STL模型最小外包框精度越高，适合轮廓复杂的模型，但重叠检测计算成本也会提高。

3)对零件STL模型进行预处理：去除掉STL模型(只有三角面片的三个顶点)中每个坐标点的Z坐标值，将所有点(即三个顶点)投影到XOY平面上，记录全部点投影数据到待计算的模型外包框坐标容器中，同时计算XOY平面上每个顶点的极坐标，并构造STL模型的边信息哈希表，得到STL模型无重复的边列表信息，并记录STL模型的每条边的首尾点之间的跨度(线段两点所跨的完整扇区的个数)，如果线段(线段也就是一条边)的跨度大于1，则需要对该条边进行插点处理，将插点数据加到待计算的模型外包框坐标容器中用于之后外包框计算。插点处理的过程是：对线段所跨每个完整扇区极角中心位置插入新点，若边的跨度小于1，则不需要进行插点处理。(插点处理时，也可以设置对完整扇区多插入几个点，如扇区极角的三等分、四等分点等，插入点越多，所形成的投影点越多。)

如图2，直线为扇区边界，线段AB、CD跨度为3，需要插点处理，对每个扇区进行插点，虚线为扇区角平分线，相交于线段CD、AB，交点E、F、G、H即为插入新点；

根据STL模型的边信息哈希表按照上述的插点处理方式循环计算表内的每一条边，将插点及原来的顶点均记为对应模型的投影点，获得待计算模型的所有投影点；

4)计算所有投影点的极坐标，按照极角大小进行分类，分类后确定每个扇区内的极径最远点，以极径最远点作为外轮廓计算点，获得外轮廓计算点的极径(在极坐标系下的对应的极角和极径)，在外轮廓计算点所在扇区的两条扇区边界上找到与该极径相等的坐标点位置，并以该坐标点位置为垂足向对应扇区内做垂线，两条扇区边界的这两条垂线相交于一点，以两个垂足及垂线相交点这三个点作为该扇区的外轮廓的顶点，顶点依次连接，进而获得所有扇区的外轮廓，得到当前模型的最小不规则外包框，单个扇区计算如图3，图中A、N、M、L、I、H、K、J点为扇区内投影点，A点的极径最大，得到最远投影点为A点，以A点为外轮廓计算点找到在扇区边界上找到与A点极径相同的坐标点为E、G点，过E、G两点做扇区边界垂线相交于F点，线段EF、FG即为模型单个扇区内模型外包框轮廓；

图4为两种方式计算所得部分最小不规则外包框，线段CD为模型最外侧投影轮廓，A、B为其他线段投影点，虚线边界为模型没有进行插点处理按照本申请计算所得模型外包框轮廓，如图所示相比于最外侧投影线段CD有很大误差，实线边界为对线段进行插点后计算所得模型外包框轮廓，插入新点为E、F、G、H，相对于虚线边界，模型外包框精度有很大提高，继续增加扇区数量外包框精度也会相应提高；

对STL模型进行二维平面投影后再进行中心排样。所述中心排样策略是：

1)计算所有STL模型投影平面的最小不规则外包框的投影面积，并统计STL模型中无重复法向量数量，无重复法向量数量越高则模型复杂程度越高，对最小不规则外包框投影面积和无重复法向量数量这两类数据分别进行归一化处理，归一化处理后通过二者加权求和作为Key值，为了提高排样密度，面积对应权值设置为0.9，无重复法向量数量权值设置为0.1。按照Key值从大到小对所有模型摆放顺序进行排序，依次为每个模型进行编号,根据工艺特点，优先摆放投影面积大且模型复杂程度高的模型，即第一个模型的Key值最大；

2)计算所有待排样模型投影平面的最小外接圆，按照确定的模型摆放顺序进行初排，以第一个模型为中心，围绕第一个模型沿径向分层布置，同一层中排入多个模型，多个模型以第一个模型为中心，保证模型可绕模型自身的中心坐标自由旋转，每个模型都针对自身的中心坐标进行移动和旋转；

3)将第一个模型中心位置放在坐标系原点，第二个模型从极角为零开始逆时针排入，第二个模型与已排入的第一个模型外切，此时第二个模型记为第一层起始模型，接着排入第三个模型：

第三个模型位置由前两个排入模型位置确定，三个模型的外接圆两两相切，根据三个外接圆直径和已经确定位置的两个模型的圆心坐标计算另一个模型的圆心坐标；

之后按照模型摆放顺序排入下一模型，下一个待排入模型的外接圆与上一个已排入模型和第一个模型的外接圆均相切，进而确定下一个待排入模型位置，以此类推；当待排模型按照之前规则排入并与第一层起始模型重叠时，则该待排模型不再与中心位置模型(即第一个模型)相切，要与第一层起始模型和上一个排入模型同时相切，记录该待排模型为第一层终止模型，此时完成第一层排样，并从下一待排模型开始记作第二层排样；

第二层排样按照顺时针反向排入第一层排样中相邻两个模型中心并与对应的第一层排样中相邻两个模型外接圆相切：首先计算与第一层起始模型和终止模型相切模型的位置并作为第二层排样的起始模型位置，每次排入模型时判断上一层相邻两个模型的中心距离h和待排模型外接圆的直径d大小关系，如果距离h<d，则待排模型与上一层两相邻模型相切摆放；当h>d时，上一层两个相邻模型间需要排入多个模型，继续向下寻找下一待排零件的直径大小，直到所找到的多个模型的外接圆直径和大于h，多个模型排样时选择和同层已排入的相邻排样模型外接圆相切并与相邻的上一层模型外接圆相切；

当待排模型与第二层起始模型重叠时，则该待排模型不再与上一层的相邻模型外接圆相切，要与第二层起始模型和上一个排入模型同时相切，记录该待排模型为第二层终止模型，此时完成第二层排样；

重复第二层排样过程进行下一层排样，每个排样层规则相同，每次排样完成后反向排样，排样策略示例如图5,虚线圆形表示每一层起始模型，斜线填充表示每一层终止模型，模型排样层数通过数字进行标注共三层排样模型。

每次排入的模型都至少与一个已排入模型外接圆相切，再通过几何计算得到待排入模型的初始位置，所有模型外接圆直径确定，由两圆位置则能确定另一圆心位置。

4)当所有模型排样完成后，去除所有模型投影外接圆进行模型靠接：

按照模型排入顺序对模型向中心靠接，每次向中心移动一个单位距离，移动方向为模型中心位置和原点连线方向，每次移动模型有4个姿态，无旋转、旋转90°、180°、270°，每次旋转时进行重叠检测判断该姿态是否可行并记录可行的排样姿态，如果存在可行旋转角度，则模型继续向中心移动直到四个排样姿态全部重叠，此时模型后退一个单位并以该后退一个单位时所对应的第一个可行的排样姿态和中心坐标作为模型最终的排样位置。

之后对其余模型依次靠接，当模型靠接完成后，对整个排样图进行最小矩形包围计算中心坐标获得整体零件排样图中心，将整体零件排样图中心移动到坐标系中心，模型排样完成。

对于凸多边形重叠检测，如果能在两个多边形之间画出一条线，则说明两个多边形并无重叠，分离轴算法利用了投影的思想，将多边形投影在一条分离轴上，只要存在一条分离轴上的投影之间没有重叠，则两个多边形分离。分离轴算法步骤如图6，先选择两个多边形其中一条边的垂线作为分离轴，对多边形所有点进行投影，得到每个多边形的最大投影线段IJ、KN，并检测是否有重叠部分。分离轴算法计算速度快，完美的使用了基本的数学向量知识。本排样方法采用改进的分离轴算法作为底层几何算法。

本申请中模型最小不规则外包围框是通过多个扇区投影点计算得到，使得模型最小不规则外包围框不能为凸多边形，在多边形重叠检测算法中分离轴算法只能检测凸多边形是否重叠。本方法中计算得到模型的最小不规则外包框是由多个三角形组成，所以对分离轴算法进行改进，对多边形进行拆分，以模型中心为顶点，将多边形拆分成多个子三角形，将多边形的重叠计算问题收敛为粒度更小的三角形重叠问题，从而得到更精确的潜在分离轴。只要存在一个子三角形发生了重叠，则多边形重叠，该位置不可行，不可行的意思即不能在该位置进行模型排放。

本发明中零件的成型方向对成型精度有很大影响，不同的成型方向会产生不同的误差，所以需要先确定零件的成型方向，然后相对于以往排样方法，不再通过最小矩形外包三维零件，而是对零件进行二维平面投影，计算零件的最小不规则外包框，将三维零件排样问题简化为二维不规则排样问题；之后计算所有零件的最小不规则外包围框面积及无重复法向量数量并做归一化处理，之后计算所有零件的排序Key值，按照新的顺序进行排样。

中心排样策略适合于3DP工艺特点，3DP工艺流程是通过预先铺好粉床，然后喷头按照计算机规定路线进行喷射粘结剂打印零件。对于同一批次打印的零件，要优先将成型复杂、占用面积大的零件放在成型槽中心位置。

本发明方法针对提出的STL模型投影算法进行多边形重叠检测，多边形重叠检测作为排样技术的底层几何算法对零件排样有很大影响。采用分离轴算法并根据投影算法作出了相应改进，通过对凹多边形进行拆分获得凹多边形，解决凹多边形重叠问题，将用于解决凸多边形检测的分离轴算法进行改进，进而解决凹多边形的重叠检测问题。

实施例

原理讲述以简单三维多边形为例，成型参数(分层厚度、成型方向)固定；

步骤一、获取所有排样零件，每个零件对应一个STL模型，零件成型方向确定为Z方向，将所有模型中心移动到坐标系中心位置，对坐标系进行扇区划分，扇区划分精度和外包框精度相关，本次软件实施例中将坐标系划分为80扇区，计算所有模型外包框，之后计算所有模型最小不规则外包框面积和无重复法向量数量，进行模型排序；

步骤二、按照排样顺序对模型外接圆进行排样，通过简单模型说明排样效果如图7，图中数字对模型顺序做出了标注，标注1数字表示最先排入，虚线表示多边形为每层起始模型，斜线填充多边形为每层终止模型。按照排样路径，1号模型位于坐标系中心，2号模型为第一层起始模型，中心坐标极角为0，和1号模型外接圆相切；3号模型位置与1、2号模型外接圆相切，其余模型依次计算，9号模型排入时与2号模型重叠，因此不能使9号模型与中心模型(1号模型)相切，而将9号模型与上一排入模型和起始模型相切，记录9号模型为第一层终止模型并与2、8号模型同时相切；第一层排样结束后，开始第二层排样，10号模型确定为第二层起始模型，与上一层起始和终止模型相切，之后模型排入上一层相邻模型中间，11号与8、9号模型相切，外接圆排样结束；

步骤三、外接圆排样完成后进行模型靠接，首先去掉所有多边形外接圆如图8，按照模型顺序将多边形向中心靠拢，图9-12为2号模型单步靠接过程中的4个旋转角度，图9、10、11、12为对2号模型旋转0°、90°、180°、270°，如果存在可行旋转角度，则继续向中心靠接，直到所有旋转角度全部重叠，模型选择上一靠接步骤中第一个可行旋转角度，之后对每个模型进行靠接过程，靠接完成后如图13；

步骤四、输出排样图；

当模型靠接完成后，对整个排样图进行最小矩形包围计算中心坐标获得整体零件排样图中心，将整体零件排样图中心移动到坐标系中心，模型排样完成；保存排样图，完成排样计算，获得最终打印排样方案。

在软件中进行测试，打开10个STL模型，图14为所有待排模型最小不规则外包框计算，通过上述算法原理，排样效果如图15。本发明未述及之处适用于现有技术。

Claims (7)

1.一种3DP工艺中STL模型中心排样方法，其特征在于，该方法包括以下内容：

STL模型投影：得到所有待排样STL模型后，设定Z方向为零件成型方向，首先计算每个STL模型XOY平面最小不规则外包框的投影面积和无重复法向量数量，根据最小不规则外包框的投影面积和无重复法向量数量确定模型摆放顺序，优先摆放投影面积大、模型复杂程度高的STL模型；

中心排样：成型空间中心位置优先摆放投影面积大、零件复杂程度高的零件，剩余的零件按照模型摆放顺序寻找距中心距离最近的排样位置进行布置。

2.根据权利要求1所述的排样方法，其特征在于，中心排样的具体过程是：计算所有待排样模型投影平面的最小外接圆，以第一个排入模型为中心，沿圆周方向按照排样顺序依次排入模型，每次排入的模型的外接圆都至少与一个已排入模型外接圆相切，再通过几何关系得到待排入模型的初始位置；一周排完后进行下一周的排布，直至所有模型按照外接圆相切的方式排好；

去除所有模型的外接圆，将所有模型按照模型摆放顺序向中心靠接，找到每个模型最优的摆放位置和姿态，获得整个排样图；再将整体排样图中心移动到坐标系中心，完成模型排样。

3.根据权利要求1所述的排样方法，其特征在于，STL模型投影的过程是：首先确定零件的成型方向并将模型上所有点投影到投影平面，然后将投影平面坐标系进行扇区划分，找到每个扇区内的最远投影点作为外轮廓计算点，计算出模型的最小不规则外包框。

4.根据权利要求1所述的排样方法，其特征在于，中心排样包括：排序方案、排样路径和重叠检测；

排序方案：需要将打印的所有模型进行排序，计算所有模型的投影面积和无重复法向量数量，对这两个参数进行归一化处理，并加上对应权值作为Key值进行模型排序，确定模型摆放顺序，排样时按照顺序依次排入零件；

排样路径：零件排序完成后计算所有零件投影的最小外接圆，将首个零件放在坐标系中心，其他零件依次排入；首先零件排样层进行外接圆排样，排样层记录每一层零件位置信息，定义每一层起始和终止零件；每层排入结束后开始下一层的零件排样，与上一层路径反向，实现零件的中心排样；每个零件中心坐标计算规则全部相同，由相邻两个零件位置及尺寸确定，之后按照相同规则排放零件；当零件摆放完成后，将零件向中心靠拢来消除间隙增加排样密度；

每次零件向中心靠接一个单位并对零件进行绕成型方向Z轴旋转，当零件位置所有旋转角度都经重叠检测后发生重叠，则零件后退一个单位并以该后退一个单位时所对应的第一个可行的排样姿态和中心坐标作为模型最终的排样位置，此时零件靠接完成；

所述重叠检测：将投影计算得到的最小不规则外包框进行分割，以最小不规则外包框的中心点为顶点将多边形拆分成多个小三角形，得到更多潜在分离轴，再应用分离轴检测算法进行凹多边形重叠检测，只要有一个小三角形重叠，则认为重叠。

5.根据权利要求1所述的排样方法，其特征在于，所述最小不规则外包框的计算过程是；

1)首先计算STL模型XOY平面的中心坐标：计算STL模型在XOY平面的最小矩形外包框，规定矩形外包框的中心坐标为该STL模型中心坐标；得到STL模型中心坐标后，将STL模型移动至坐标系中心，使STL模型中心坐标与坐标系中心重合；

2)对坐标系的四个象限进行均匀扇区划分；

3)对零件STL模型进行预处理：去除掉STL模型中每个坐标点的Z坐标值，将所有顶点投影到XOY平面上，记录全部点投影数据到待计算的模型外包框坐标容器中，同时计算XOY平面上每个顶点的极坐标，并构造STL模型的边信息哈希表，得到STL模型无重复的边列表信息，并记录STL模型的每条边的首尾点之间的跨度，跨度为线段两点所跨的完整扇区的个数，如果线段的跨度大于1，则需要对该条边进行插点处理，将插点数据加到待计算的模型外包框坐标容器中用于之后外包框计算；插点处理的过程是：对线段所跨每个完整扇区极角中心位置插入新点；

若边的跨度小于1，则不需要进行插点处理；

根据STL模型的边信息哈希表按照上述的插点处理方式循环计算表内的每一条边，将插点及原来的顶点均记为对应模型的投影点，获得待计算模型的所有投影点；

4)计算所有投影点的极坐标，按照极角大小进行分类，分类后确定每个扇区内的极径最远点，以极径最远点作为外轮廓计算点，获得外轮廓计算点的极径，在外轮廓计算点所在扇区的两条扇区边界上找到与该极径相等的坐标点位置，并以该坐标点位置为垂足向对应扇区内做垂线，两条扇区边界的这两条垂线相交于一点，以两个垂足及垂线相交点这三个点作为该扇区的外轮廓的顶点，顶点依次连接，进而获得所有扇区的外轮廓，得到当前模型的最小不规则外包框。

6.根据权利要求4所述的排样方法，其特征在于，Key值的计算方式为对最小不规则外包框投影面积和无重复法向量数量这两类数据分别进行归一化处理，面积对应权值设置为0.9，无重复法向量数量权值设置为0.1，二者加权求和即得。

7.根据权利要求4所述的排样方法，其特征在于，排样路径的具体过程是：

计算所有待排样模型投影平面的最小外接圆，按照确定的模型摆放顺序进行初排，以第一个模型为中心，围绕第一个模型沿径向分层布置，同一层中排入多个模型，多个模型以第一个模型为中心，保证模型能绕模型自身的中心坐标自由旋转；

将第一个模型中心位置放在坐标系原点，第二个模型从极角为零开始逆时针排入，第二个模型与已排入的第一个模型外切，此时第二个模型记为第一层起始模型，接着排入第三个模型：

第三个模型位置由前两个排入模型位置确定，三个模型的外接圆两两相切，根据三个外接圆直径和已经确定位置的两个模型的圆心坐标计算另一个模型的圆心坐标；

之后按照模型摆放顺序排入下一模型，下一个待排入模型的外接圆与上一个已排入模型和第一个模型的外接圆均相切，进而确定下一个待排入模型位置，以此类推；当待排模型按照之前规则排入并与第一层起始模型重叠时，则该待排模型不再与中心位置模型相切，要与第一层起始模型和上一个排入模型同时相切，记录该待排模型为第一层终止模型，此时完成第一层排样，并从下一待排模型开始记作第二层排样；

第二层排样按照顺时针反向排入第一层排样中相邻两个模型中心并与对应的第一层排样中相邻两个模型外接圆相切：首先计算与第一层起始模型和终止模型相切模型的位置并作为第二层排样的起始模型位置，每次排入模型时判断上一层相邻两个模型的中心距离h和待排模型外接圆的直径d大小关系，如果距离h<d，则待排模型与上一层两相邻模型相切摆放；当h>d时，上一层两个相邻模型间需要排入多个模型，继续向下寻找下一待排零件的直径大小，直到所找到的多个模型的外接圆直径和大于h，多个模型排样时选择和同层已排入的相邻排样模型外接圆相切并与相邻的上一层模型外接圆相切；

当待排模型与第二层起始模型重叠时，则该待排模型不再与上一层的相邻模型外接圆相切，要与第二层起始模型和上一个排入模型同时相切，记录该待排模型为第二层终止模型，此时完成第二层排样；

重复第二层排样过程进行下一层排样，每个排样层规则相同，每次排样完成后反向排样；

当所有模型排样完成后，去除所有模型投影外接圆进行模型靠接：

按照模型排入顺序对模型向中心靠接，每次向中心移动一个单位距离，移动方向为模型中心位置和原点连线方向，每次移动模型有4个姿态，无旋转、旋转90°、180°、270°，每次旋转时进行重叠检测判断该姿态是否可行并记录可行的排样姿态，如果存在可行旋转角度，则模型继续向中心移动直到四个排样姿态全部重叠，此时模型后退一个单位并以该后退一个单位时所对应的第一个可行的排样姿态和中心坐标作为模型最终的排样位置。

Images