(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210911001.6 (22)申请日 2022.07.29 (71)申请人 燕山大学 地址 066004 河北省秦皇岛市海港区河北 大街西段438号 (72)发明人 汪飞雪　朱词明　刘嘉琦　王泽坤　 杨士超　姚静　 (74)专利代理 机构 大连东方专利代理有限责任 公司 21212 专利代理师 吴婷婷　李洪福 (51)Int.Cl. G06F 30/10(2020.01) G06N 3/12(2006.01) G06T 17/00(2006.01) G06F 111/04(2020.01) (54)发明名称 一种基于遗传算法的STL三维模 型排布优化 方法 (57)摘要 本发明提供一种基于遗传算法的STL三维模 型排布优化方法。 首先将要排布的组件的几何模 型转化成易处理的STL模型并导入MATLAB， 通过 导入顺序对S TL模型编号， 利用S TL模型三角面片 的顶点信息来表征三维模型的结构特征及空间 位姿； 之后根据遗传算法对模型的空间位置和旋 转角度进行更新， 利用投影 法和三角网格求交法 判断模型之间是否发生干涉， 将 干涉的体积作为 约束条件； 根据适应度函数重复迭代， 直至达到 终止条件， 此时的排布结果为理想排布方案。 本 发明采用了遗传算法直接对具有复杂结构的ST L 模型进行排布优化设计， 以最小特征体积为适应 度函数， 确定所有模型最小特征体积所对应的摆 放位置和旋转角度。 权利要求书2页 说明书6页 附图6页 CN 115270219 A 2022.11.01 CN 115270219 A 1.一种基于 遗传算法的STL 三维模型排布优化方法， 其特 征在于， 包括： S1、 将需要排布的组件的几何模型转换成STL模型并导入MATLAB， 读取各个组件包含的 三角面片的顶点和法向量信息； S2、 对遗传算法模型进行初始化， 包括定义适应度函数、 设定迭代次数， 并产生种群数 量为p的初始种群； S3、 通过p个初始种群中个体的遗传信息x对STL模型的排布姿态进行调整， 刷 新STL模 型三角面片的顶点信息； S4、 针对步骤S3得到的STL模型的三角面片顶点信息， 计算出各STL模型之间干涉部分 包围盒的体积V1， 并将所述干涉部分包围盒的体积V1设置为约束条件； S5、 基于步骤S4得到的干 涉部分包围盒的体积V1， 以及包含所有组件的AABB包围盒的体 积V2的和求取适应度函数； S6、 基于S4所定义的约束条件和S5定义的适应度函数， 利用遗传算法对当前种群进行 迭代优化， 逐步使得V1等于0， V2趋于最小值； S7、 判断是否 达到最大迭代次数， 若是则输出排布结果， 若否则返回步骤S4。 2.根据权利要求1所述的一种基于遗传算法的STL三维模型排布优化方法， 其特征在 于， 将需要排布的组件的几何模型转换成STL模型， 包括： 通过CAD绘制的三维模型导出STL 模型。 3.根据权利要求1所述的一种基于遗传算法的STL三维模型排布优化方法， 其特征在 于， 获取个 体的遗传信息x 包括： 将组件的自由度直接编码得到的1 ×6n的数组作为作为基因x， 且x(6(i ‑1)+1～6i)依 次表示第i个组件 x、 y、 z轴方向上的平 移距离和绕x、 y、 z轴的旋转角度。 4.根据权利要求3所述的一种基于遗传算法的STL三维模型排布优化方法， 其特征在 于， 获取个体的遗传信息x还包括： 通过对STL模型上三角面片进行平移旋转即可将模型转 换至任意 位姿v。 5.根据权利要求1所述的一种基于遗传算法的STL三维模型排布优化方法， 其特征在 于， 计算各STL模型之间干涉部分包围盒的体积V1之前， 还包括对各STL模型之间干涉情况 进行判断， 具体包括： 使用投影法对各STL模型之间的干涉情况进行初始判断， 倘若两个组件在任意一个坐 标平面上的投影不相交即可确定两个组件不 发生干涉； 若两组件在各个坐标平面上的投影 都相交， 则对STL模 型求交， 若STL模 型相交则判定模 型之间发生干涉， 反之则认 为不发生干 涉。 6.根据权利要求5所述的一种基于遗传算法的STL三维模型排布优化方法， 其特征在 于， 计算各STL模型之间干涉部分包围盒的体积V1， 包括： S401、 求得组件1在x、 y及z轴上投影的最大值与最小值(X  max,X min)、 (Y max,Y min) 及Z max,Z min， 取： L1＝X max‑X min,W1＝Y max‑Y min,H1＝Z max‑Z min 作为组件的A ABB包围盒Box1的长 宽高,同理可求得组件2的A ABB包围盒Box2的长 宽高； S402、 求Box1和Box2的长、 宽、 高的交集L、 W、 及H， 若L、 W、 及H都不为空集， 则以L、 W、 及H 建立Box3， 筛 选出组件1及组件2与Box3相交的三角面片集 合u1和u2；权　利　要　求　书 1/2 页 2 CN 115270219 A 2S403、 倘若未达到最大迭代次数且u1和u2都不为空， 将u1和u2绕z轴旋转一定角度后作 为组件1和组件2重复S401 ‑S402， 否则跳出循环， 进入S404； S404、 u1和u2中存在空集时， 直接令干 涉部分体积V1＝0； 反之则计算干 涉部分体积包围 盒相交区域体积V1， 求得组件1和组件2的包围盒体积之和为V， 令 设定阈值u1， 若u> ＝u1,则令V1保持原值不变， 若u<u1,就对u1和 u2两集合的三角面片求交， 若三角面片相交， 令V1保持原值 不变， 反之则令V1＝0。 7.根据权利要求1所述的一种基于遗传算法的STL三维模型排布优化方法， 其特征在 于， 所述适应度函数为： f＝V2+θV1 V2＝(X max‑X min)(Y max‑Y min)(Z max‑Z min) 其中， f为适应度 函数， X max为三角面片顶点坐标在x轴投影的最大值， X  min为三角面 片顶点坐标在x轴投影的最小值， Y  max为三角面片顶点坐标在y轴投影的最大值， Y  min为 三角面片顶点坐标在y轴投影的最小值， Z  max为三角面片顶点坐标在z轴投影的最大值， Z   min为三角面片顶点 坐标在z轴投影的最小值， θ 为权 重系数。权　利　要　求　书 2/2 页 3 CN 115270219 A 3