开发自动排料软件的难度
-------------2022.11.12------------
关于技术难度问题,就本人从业以来接触过的几个项目大致做一个比较
- cad(b样条曲线曲面插值拟合求交等)
进入软件行业第一个接触的项目,以现在的眼光看,难度约为2星。 不过对于当时的技术水平而已,还是有点费力的,c++也不熟,甚至写文件也费了好几天才搞懂。 总体来说是基于成熟理论的技术实现,不需要创新。
2. 光刻模拟几何检测(LRC或称ORC)
从事eda行业的首个项目,结果还是比较满意的,当时(2013年左右)对比mentor的同类型产品,性能有一个数量级的提升,不过据我们团队当时的分析,mentor非常有可能为了多卖license而故意降低性能。
难度4星
3. 芯片版图hierarchy优化
这个项目算是本人从业以来的得意之作,当时苦思冥想,终于灵感大爆发,算法主体实现花了一个月时间完成。 不过在进入Synopsys工作后惊奇地发现Synopsys居然有个类似的quasi架构(主要用在drc相关操作上),而且比我设计的更为精巧也适用更广泛,果真是天外有天人外有人。看这个架构诞生日期似乎比我还要早一年左右。
难度5星
4. 自动排料
毫无疑问,自动排料涉及到的技术是非常之难,不能单纯用项目来表达,定义为产品更合适。可以把它拆分为很多小项目,每个小项目都是4-5星的。 而且改进/优化没有止境,我觉得就整体而言超出了5星评价系统,给7星也不为过
需要指出的是,绝大部分的几何算法都是以高性能实现为前提,拿左底混排为例,如果不考虑性能,难度大概是1星,高性能实现难度至少3.5星以上。 这之间的性能差异通常会有几十倍。
--------------------------------------------
有不少童鞋和盆友都向我咨询开发自动排料引擎的技术问题, 今天就专门讲一下这个问题.
首先,开发一个自动排料引擎门槛很低, 开发人员可能并不需要太高深的数学, 太高深的编程技巧, 就可以开始工作, 最终也能完成一个可以工作的排料引擎. 当然这个只能算是最基本的一步, 就是摆脱手工排料这个耗时过程. 但是自动排料引擎的优秀与否的最主要的评价指标是利用率. 要开发一个优秀的自动排料引擎, 其实真的门槛很高.
自动排料引擎的研究从上世纪六十年代就开始了, 只是国内真正开始有高校或者商业机构开始研究其实已经到了九十年代, 因为199X年个人PC才开始慢慢在国内普及. 从国内近二十年的研究来看, 基本上是在做一些基础的重复性的工作, 比如高校的研究, 基本上是一拨学生研究了两三年, 换一批再从头又开始研究, 周而复始. 没有技术上的递进. 对于企业来说, 也是如此, 一般来说两三年是国内研发的一个生命周期, 两三年没什么进展,这个项目就会被毙掉. 这个应该不止是软件行业, 其他行业大部分都是如此. 所以大家才看到今天的局面--- 凡是需要长时间技术积累的行业, 国内大部分都是短板.
我可以大概说一下我研究自动排料引擎的时间历程.
大约在2007年第一次真正接触自动排料软件, 那时在一家港资服装CAD软件公司(从加拿大服装CAD公司收购)工作, 他们有自己的自动排料引擎, 虽然和当时最牛的shapeshifter(新西兰)比相差甚远. 但代码量其实不小, 基本上使用的是三角几何和智能优化的方法. 我当时工作的一部分是对自有引擎的改进. 两年后我离开了这家公司, 不过这个研究一直没有停.
中间大概六七年, 我是从事EDA行业的几何算法工作. 期间参与了光刻模拟检测(ORC) 项目, 其实当时我们团队的技术可以接着做OPC了, 但是老板是个纯技术型的美籍华人(清华本科,伯克利博士,当时五十出头), 在资金匮乏的时候求助科技部, 科技部说你去找工信部更合适, 工信部说这个还是科技部合适, 呵呵, 踢球水平那是一点都不含糊.
这六七年其实没有专门的去挤出很多时间研究, 更多的情况是看看有没有什么相关的新论文, 平均每隔两年会写点东西尝试一下. 现在回想翻过的论文, 应该不下千篇. 其实我当时基本就没想过能够有所突破, 单纯的兴趣. 大概2015-2016年左右, 算是有点小收获了. 比之前的算法有了明显的提升, 当然最直接用的技术就是重叠移除技术 , 底层的几何算法是NFP(我就从来没想过用基本三角几何的原理去处理底层的多边形距离/碰撞问题, 因为基于这些无论怎么优化, 运行效率的数量级都不对). 这个小收获并没有让我惊喜, 因为距离世界上最好的自动排料引擎平均还差3%甚至可能更多. 虽然我知道大概在国内能做到这个水平的应该没几个,甚至没有.
然后是去Synopsys工作了两年半, Synopsys是家好公司, 员工整体水平挺高, 不过牛人其实也不多, 一百出头的大Team里有那么一两个牛人, 这样算起来整个公司牛人总数也有上百个, 也是相当厉害的. 离开Synopsys后和一帮热血中年折腾EDA行业的创业, 不出意料的以失败告终, 即使是卡脖子的大背景下, 大部分官方投入的资金都没有落到实处, 这种形势倒是让我静下心来研究一下自动排料引擎了. 这段时间的工作是持续最长的, 几个月的连续奋战, 终于在小规模上能在很多esicup数据集上稳定地跑出创纪录的结果. 我当时的第一感觉就是, 这次可以拿得出手了. 这个时间点是2019年.
应该说这个突破带来的不仅仅是一个点的突破, 很显然, 站在6楼和站在2楼看到的东西不一样. 接下来也突破了大中规模的排料算法,虽然也费了一番周折.
从自动排料引擎的结构上讲, 程序实现和理论同样重要. 理论是一个方向, 方向不对,可能所有的工作都是徒劳. 而程序实现在自动排料引擎这个产品上是个超严重的瓶颈. 60-70%的时间是在优化性能, 基本上是无所不用其极. 本质上说代码和算法的性能优化就是让时间都花在有效的计算上. 这个有效的计算不仅是指冗余计算少, 还可以是算法的有效性. 打个比方, 数学上有个最速下降法, 应用到算法选择上, 两种算法如果A算法比B算法在同样有效的情况下收敛更快, 那当然选收敛更快的.
即使费了这么大劲, 其实目前的利用率水平离世界最好水平还有平均约0.5%的差距. 大概是世界顶级行列的靠尾水平. 不过真正做排料引擎的到世界顶级行列水平的也就三四家, 大家看到的很多不同排料软件底层用的引擎可能是同一家的. 钣金行业也差不多, 到顶级的也就4/5家. 对比服装自动排料引擎, 钣金自动排料更难, 一是零件数量多, 可能达数万个甚至数十万个零件, 二是零件可以自由旋转. 钣金自动排料要达到顶级水平要难得多. 这也是我们在努力的方向.
说到很多切割设备厂商, 数控设备厂商, CAD集成厂商都有在研发自动排料引擎. 我很难用一两句话来提出建议. 从预期结果来看, 成功的概率接近0. 很多原因吧, 我随便列举几个, 1 . 需要持续研发, 这个没几家公司做的到, 即使是阿里和华为. 这个不仅需要资金 ,还需要耐心, 不仅是时间上的递进,还需要技术上的递进. 2 .重视技术, 看起来这个和第一点有些雷同, 但是有必要单独拿出来说, 有不少厂商尝试和我们合作都觉得我们报价太贵, 我评估下来他们能接受的价格不会超过两千块一套. (对比一下, 德国的服装排料引擎大概是2w一套,而机械行业的lantek,radan,alma,sigmanest等顶级排料软件一般报价超10w). 如果抱着这样的心理, 他们找来研发人员开发自动排料引擎, 那么结果就是他们开发的引擎价值和水平不会超过2千. 3 . 水平足够的开发人员. 这点比较难评估. 我自认为智力只是中上, 比我聪明的大有人在, 不过我也并不觉得, 随便找几个博士就能做的比我好. 更关键的是, 对于这种需要持续技术积累的产品来说, 天才并不管用.
___________
这里对国内自动排料引擎的现阶段水平做个简单的分析
服装自动排料
服装自动排料引擎之前在国内的研发基本处于空白状态, 这也是我们决心推出产品的重要原因. 仅有的几家涉及服装自动排料引擎的厂家, 利用率水平乐观估计的话, 应该比世界顶级服装排料引擎平均低3%以上. 从我们部分客户那里了解到的信息看, 情况更糟糕, 有的差距在10%, 20%以上.
钣金自动排料
钣金的情况比服装要好些, 国内有几家做的产品还过得去. 这个和钣金行业的特点有关系. 我们从两种情况分析:
一是小规模的, 一般就一两张板材, 几十到小几百个零件. 这种测例下, 国内几家的产品其实与世界顶级水平的差距和服装行业类似, 差距非常明显.
二是中大规模的, 这种规模下, 大部分情况是零件中大中小尺寸的零件分布相对均匀(这其实是客户有意为之, 能有效提高板材利用率), 这样, 即使普通的软件出来的结果也不会那么糟糕, 一个直观的解释就是各种尺寸的零件可以相互插空.
我们做个简单的测试,
六种零件,每种零件20个, 分成大小两组,
在板材相同高度的情况下测试
大组 3种大零件, 60个单独排料如下:

小组 3种小零件, 60个,单独排料如下:

大小混合排料, 共120个零件:

大小组单独排料耗费的板材总长度是: 4711.57 + 762.82 = 5474.39
大小组混合排料耗费长度是: 5185.48
尺寸比较均衡(这种情况下, 没有明显的大小关系, 都是小零件,就无所谓小了, 都是大零件, 也无所谓大了)的情况是非常考验排料引擎的性能的, 比如大小组分开排, 好的排料引擎可能领先普通的引擎7%-10%-甚至更多, 但是在大小组混合后, 领先的幅度就会急剧缩小, 可能差距就3%甚至更小.
__________________
有些朋友觉得上面说的还是泛泛而谈, 那我们就探一下自动排料技术的几大技术坎
一. 底层多边形的距离/碰撞算法
我们这里讨论自动排料所有行业通用的多边形, 即包含圆弧的多边形. 为什么忽略曲线呢(bezier,BSpline,甚至NURBS)? 由于曲线之间的距离求解过于耗时, 做过曲线求交算法的朋友可能知道, 简单的牛顿迭代法就折腾了, 如果要在几分钟内做几百万次的曲线距离求解, 绝无可能. 所以通常曲线会预先离散化. 圆弧也可以离散化为线段, 但是由于圆弧与直线或圆弧的距离计算有公式, 所以很多情况下计算更有优势.
多边形的距离或者说是否碰撞, 如果用三角几何的方法做, 其耗时程度取决于多边形的顶点数(或边数). 一般对于顶点数不超过10个的, 用三角几何方法可以应付, 至少不会比其它算法慢出一个数量级. 但是实际服装/机械等工业应用中, 多边形的平均顶点数一般在几十个以上, 有些行业, 比如广告行业雕刻一条龙的多边形, 顶点数可能几百上千. 所以正常情况下都会不会采取传统三角几何算法, 而是寻求更快速的方法. 比较常见的有下面几种
1, Phi-function
就是通过简单图元的组合(拆分)而成实际的裁片形状, 裁片形状之间的相互关系转化为所有的所谓的基本Phi-Object之间的关系的约束集合. 相对来说, 这个方法对于典型的钣金零件更合适, 但如果形状非常复杂, 处理起来也是相当不容易.

2, NFP(no-fit polygon)
这个大多数从事自动排料的都比较清楚, 就不描述细节. 使用NFP算法也比较难逾越的一道坎: Robust, 即健壮性问题. 对于一个商业排料软件来说, 不允许说是"能应付大多数情况". 另外一个是性能, 相对来说性能问题在目前CPU高主频和多核数的情况下会弱化, 但是要做到一个合理的客户能接受的运行时间并不容易. 大名鼎鼎的CGAL的NFP算法性能是较差的, 只能算是勉强能用. 如果CPU比较老旧, 算个几百种多边形之间的NFP,有可能会超过几分钟.
对于钣金行业来说, NFP的可用度并不高. 特别是形状非常不规则的. 钣金零件大部分可以自由旋转, 这种情况下, 你没有办法去预先计算好所有的两两多边形的NFP, 因为理论上多边形的数目是无穷的, 即使你使用每隔5度转一下, 100中多边形将需要至少计算 72*100*99/2 = 25660800个NFP多边形, 至少要几个小时, 并且最要命的是没有足够的内存把这个结果保存下来.
3. 使用若干个圆来近似表达多边形

也有用不重叠的圆来近似表达一个裁片形状的方法. 圆的最大优点是旋转不变性. 这种方法的缺点是不够精确, 需要另外的算法来压紧布局.
二. 布局策略
国内大部分的研究是基于按次序的裁片排放策略. 这种方法相对来说简单快速. 国外目前的主流研究大部分集中在重叠移除, 图形特征匹配, 以及使用各种数学模型表达布局并通过解方程组来改进.
对于不规则裁片来说, 基于排放次序的策略获得较优解. 受限于两点: 1. 基于次序的理论最好值距离真实的理论值差距比较大. 较优解通常永远不能通过按固定规则以按次序方式获得. 即理论最好值有限. 2. 但裁片达几十个以上时, 即使按次序的理论最好解也无法在正常时间内获得. 比如 50个裁片, 所有的组合数是 50! = 3.04*10 ^64. 即使考虑一种裁片有多个的情况, 这也是个天文数字. 50个裁片的一次按序排列所需要的时间通常在 几个毫秒~几百个毫秒之间(试具体实现而定). 我们按50毫秒计算, 这个时间约为 4.8*10^55年.
而重叠移除算法理论上只要时间足够都找到最好解. 当然, 受限于运行时间和规模, 实际上最好解也是不可能达到的, 达到了最好解也无法证明是不是最好解.
对比一下按次序排放的算法结果和重叠移除的算法结果

按序排放, 长度: 10015.45

重叠移除算法, 长度 9704.84
2021-09/20
与市面上流行的某超排软件NE (推测可能使用的是盗版的ss)的对比
esicup 数据对比
swim 论文最好记录(75.94%)
5分钟 NE 76.4%; yotuNester 77.76% ;


该软件号称排料速度快, 有默认1分钟快速排版选项, 下面这个trousers例子使用1分钟测试: (论文最好纪录 91.00%)


1分钟 NE 90.5%; yotuNester 91.92%;
shapes (论文纪录 76.73%)


NE 68.8%; yotuNester 76.73%
生产实例
例1 72片 180度旋转


NE 84.5%; yuotuNester 85.65%;
例2 388片 180度旋转


NE 88.10%; yotuNester 89.4%;
例3 天池大赛初赛数据 314片 间距 5mm, 180度旋转


NE 83.8% 单边间距 0.25 cm
yotuNester 85.33% 间距 5mm (此为任意两个裁片之间的最小间距, 与NE单边间距 2.5mm等价); 可以看到, yotuNester的初解 84.76%已经超过NE的5分钟解, 耗时仅 3秒。
————————————————————————————
钣金类套料/排料实例
支持内孔套料; 支持零件间距;支持零件与板材边距;
典型机械钣金排料实例

非典型机械钣金排料实例

_______________未完