PCB/FPC 智能拼版：四层级计算链路与多边形放置引擎的设计与实现

PCB/FPC 智能拼版四层级计算链路与多边形放置引擎的设计与实现一、问题背景在 PCB印制电路板和 FPC柔性线路板制造行业板材原材料成本在总生产成本中占比极高。拼版排版这道工序决定了多少面积的产品能从一张基材大板上切出——利用率每提升 1%都是真金白银的利润。但拼版排版的现状是绝大多数工厂仍依赖工程人员凭经验手动排布。问题在于组合空间巨大一块大板排多少行、多少列单板 0° 还是 90° 放置不同工序的工艺边怎么留——排列组合多到人脑无法穷举。异形板难度陡增矩形板是基础题L 形、T 形、十字形的 FPC 软板才是真正的考验。人工做异形相嵌排版出错率极高。四层级嵌套PCB 拼版不是一维问题——从单片Pcs到出货片Set到生产小板WPnl再到基材大板Sheet每一层都对上一层的结果有依赖。本文记录 PCB 最佳化拼版系统的核心算法设计包括四层级计算链路、基于 JTS 的多边形放置引擎、12 种 AB 板策略以及效果验证数据。二、四层级计算链路Pcs → Set → WPnl → SheetPCB 拼版的独特性在于它不是把单板排进大板这么简单而是四层嵌套结构┌──────┐ ┌──────┐ ┌────────┐ ┌────────┐ │ Pcs │───▶│ Set │───▶│ WPnl │───▶│ Sheet │ │ 单片 │ │ 出货片│ │ 生产小板│ │ 基材大板│ └──────┘ └──────┘ └────────┘ └────────┘2.1 Pcs → Set单片组成出货片客户真正需要的是出货片Set一个 Set 上通常拼了多个 Pcs。加上四边的折断边Breakaway Edge才是一个完整的出货单元。// FourLevelCalculator.buildPcsLevel()Set宽度cols ×Pcs宽度(cols-1)× 间距左折断边右折断边Set高度rows ×Pcs长度(rows-1)× 间距上折断边下折断边四个方向的折断边各自独立配置最小宽度 / 最大宽度系统会自动尝试 4 种折断边交换配置选择面积最小的方案// autoReverseBreakaway: 尝试 4 种折断边交换// 例上折断边与下折断边交换、左与右交换找出 Set 面积最小组合同时支持 Set 尺寸约束minWidth/maxWidth, minLength/maxLength防止生成的 Set 超出设备处理范围。2.2 Set → WPnl出货片排入生产小板这一步的搜索空间最大。系统采用 20×20 网格枚举策略// FourLevelCalculator.calcSetToWpnl()for(introwsminRows;rowsmaxRows;rows){for(intcolsminCols;colsmaxCols;cols){// 计算 WPnl 候选尺寸// 每个候选评估 3 种放置策略evaluateStandard(rows,cols);// 标准矩形网格evaluateStaggered(rows,cols);// 花式拼奇偶行偏移evaluateHvMaterial(rows,cols);// 横直料横竖交替}}// 评选标准总 Set 数多者优先相同时利用率高者优先三种放置策略的核心差异策略排列方式适用场景标准矩形行列对齐网格常规矩形板花式拼Staggered奇数行右移 50% 单元宽度FPC 窄条、柔性板横直料HV Material横竖交替放置板材纹向有要求花式拼的列数计算偶数行: cols floor((有效宽度 gap) / (cellW gap)) 奇数行: cols floor((有效宽度 - cellW × 0.5 gap) / (cellW gap))工整的偏移让奇数行凸起嵌入偶数行间隙中减少上下方向的板材浪费。2.3 WPnl → Sheet生产小板排入基材大板最后一层是开料把 WPnl 排列到基材大板上。这层引入了**中裁Center Cut**的概念——对于超长板可以按行/列切分成子区域// 四种中裁模式enumCutMode{NONE,// 标准矩形网格HORIZONTAL,// 水平分区 底部剩余补充VERTICAL,// 垂直分区 右侧剩余补充MIXED// 横竖同时分区形成格子布局}// MIXED 模式计算水平分区数floor((Sheet长中裁宽)/(行数 ×WPnl长(行数-1)× 间距中裁宽))垂直分区数floor((Sheet宽中裁宽)/(列数 ×WPnl宽(列数-1)× 间距中裁宽))总WPnl数水平分区 × 垂直分区 × 行数 × 列数工艺边处理支持 NONE / SINGLE / OPPOSITE / ALL 四种模式由ProcessEdgeUtils统一处理。三、多边形放置引擎异形板的解法矩形板排布是基础题真正拉开差距的是异形板。PCB/FPC 行业大量存在 L 形连接板、T 形驱动板、十字形、弧形等非矩形外形。3.1 为什么不用外接矩形传统做法是把异形板的外接矩形Bounding Box当作占位区域来排。问题很明显——一个 L 形板外接矩形面积可能是真实面积的 1.6 倍L 形板真实面积: 约 6 平方单位 外接矩形面积: 约 10 平方单位 如果用 bbox 排 → 利用率虚高实际浪费 40% 空间解决方案使用 JTS Topology Suite 对真实多边形轮廓进行碰撞检测而非外接矩形。3.2 核心类架构┌─────────────────────────────────────────────────┐ │ MultiUnitPanelOptimizer │ │ 遍历 boardIds × (m,n) 切割组合 │ │ 对每个工作板同时运行条带分配 多边形引擎取最优 │ │ 利用率 Σ(真实多边形面积) / 工作板面积 │ └────────────────────┬────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────────────┐ │ StrategySelector.selectAndPlace() │ │ 根据 ShapeClassifier 形状分类自动选择策略 │ │ 并行运行所有适用策略取利用率最优 │ │ │ │ ┌──────────┐ ┌──────────────┐ ┌──────────┐ │ │ │BottomLeft│ │InterleavedRow│ │Staggered │ │ │ │Strategy │ │Strategy │ │Strategy │ │ │ │(贪心底左) │ │(混排行) │ │(错缝排布) │ │ │ └──────────┘ └──────────────┘ └──────────┘ │ │ │ │ 如有 L/T 形单元 → 先运行 MirrorPairStrategy │ │ 拼合形成 CompositeUnit 后再参与排版 │ └────────────────────┬────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────────────┐ │ FragmentFiller.fillFragments() │ │ 主排版后 → 计算剩余空间 → 凸分解 → 填充小尺寸单元 │ └─────────────────────────────────────────────────┘3.3 BottomLeftStrategy 核心算法这是最核心的放置策略采用贪心底左放置输入单元请求列表含多边形轮廓、数量、放置板、间距 1. 展开候选变体 每单元 × 4 旋转0°/90°/180°/270°× 2 镜像 → 去重对称项 2. 按面积降序排列大件优先 3. 轮询贪心放置多类型时轮流放置保证每种单元都有代表 a. 候选位置 有效区域原点 每个已放置单元 bbox 的 4 个角 间距偏移 b. 按 y 升序、x 升序排列底左优先 c. 对每个候选位置 - 板材边界检查原始多边形必须在板材内 - JTS 间距检查新多边形与每个已放置多边形的 distance ≥ spacing d. 第一个满足条件的位置即为放置位置 4. 碎片填充主排版后调用 FragmentFiller 填充边角余料// 间距检查的核心JTS distance 方法// 精度 0.001mm满足 PCB 制程要求booleanhasCollisionplacedOutlines.stream().anyMatch(placed-placed.distance(newOutline)spacing);3.4 MirrorPairStrategy镜像拼合L 形和 T 形器件单独排利用率极低~60%。但如果把它们两两镜像配对呢原始 L 形利用率 ~60%大量空隙 ┌─────┐ ┌─────┐┌─────┐ │ │ │ ││ │ │ L1 │ 镜像 → L1 ││ L1 │ ≈ 近矩形 │ │ │ ││ │ └──┘ │ └──┘ │└──┘ │ │ │ │ │ │ │ └──┘ └──┘ └──┘ 拼合后利用率~95%接近矩形算法实现// MirrorPairStrategy 核心逻辑for(Unitunit:lShapeUnits){for(Rotationrot:Rotation.values()){for(Edgeedge:Edge.values()){// 左/右/上/下Polygonmirroredunit.getOutline().mirror(edge).rotate(rot);Polygonunionunit.getOutline().union(mirrored);doublefillRateunion.getArea()/union.getBbox().getArea();if(fillRate0.7){// 拼合后填充率 ≥ 70%// 接受形成 CompositeUnit近矩形复合单元}}}}3.5 形状自动分类ShapeClassifier根据顶点数和凹角数自动分类形状判定规则顶点数策略RECTANGLE4 顶点 或 填充率 0.954标准矩形网格L_SHAPE6 顶点 1 凹角6MirrorPair BottomLeftT_SHAPE8-10 顶点 2 凹角8-10MirrorPair BottomLeftIRREGULAR其他十字形、弧形等不定Interleaved / Staggered3.6 碎片填充主排版完成后还有边角余料可以塞小尺寸单元。FragmentFiller的工作流程1. 计算剩余空间 板材 ⊖ 已放置单元 2. 使用 PolygonDecomposer 将剩余空间做凸分解 Delaunay 三角剖分 贪心合并为凸多边形 3. 网格扫描各凸碎片空间 4. 小单元 × 多旋转尝试 → 优先填入最小碎片四、AB 板拼版12 种策略当两种单板需要混拼在同一张 WPnl 上时系统提供 12 种策略按分割比例[0.25, 0.33, 0.5, 0.67, 0.75]遍历标准 AB 策略8 种序号策略说明1左右分左侧 A 区 右侧 B 区按比例分割2上下分上方 A 区 下方 B 区3交错行A/B 行交替排列4填空隙A 填满标准网格后B 填入剩余空隙5单行交替每行内 ABAB 水平交替6双行交替AABB 行块交替7单列交替每列内 ABAB 垂直交替8自定义间隔N 行 A M 行 B 循环花式 AB 混拼4 种序号策略说明9花式左右分左右分区 奇偶行偏移10花式上下分上下分区 奇偶行偏移11花式交错行交错行 奇偶行偏移12花式双行交替双行交替 奇偶行偏移每种策略下A 板和 B 板各自尝试 0°/90° 旋转4 种组合最终选总单元数最多的配置。五、智能板材推荐另一个实用功能是——不用人工去猜用什么规格的基材大板最划算。系统提供自动推荐// POST /api/v1/schemes/multi-panel/recommend-boards// 算法1.在虚拟无限大板5000×5000mm上紧凑排版得到 footprint2.对每块候选板材枚举(m×n)切割组合评分 scoreutilization ×0.7-normalizedCost ×0.33.生成推荐定制开料尺寸footprint边距向上取整到10mm返回结果包括各候选板材的利用率、推荐切割行列数、评分以及根据排版轮廓推算的定制开料建议尺寸。六、多格式文件解析系统支持三种行业标准格式的自动解析格式版本提取内容DXFR12 ~ 2018工件轮廓、外形坐标、有效加工区域GerberRS-274X / X2 / X3外形边框、工艺边、有效区域、属性信息ODB—Profile 轮廓、工艺层级、生产参数Gerber 解析时区分四种外形识别策略X2/X3 属性标记FileFunction,Profile文件名规则outline.gbr/.gko/.gm1线宽启发式 0.5mm 封闭轮廓优先用户手动指定图层解析时的异常检测非封闭轮廓首尾端点距离 0.01mm → 警告自交多边形 → 拒绝板尺寸 2mm → 警告多余碎线 0.1mm → 自动过滤七、技术架构总览┌──────────────────────────────────────────────┐ │ 前端 (Vue 3 Canvas 2D) │ │ Naive UI · Canvas 渲染 · 拖拽编辑 · 5px吸附 │ ├──────────────────────────────────────────────┤ │ 解析引擎 │ │ DXF/Gerber/ODB 文件解析服务 │ ├──────────────────────────────────────────────┤ │ 算法核心 (Spring Boot 3) │ │ 四层级计算 · 多边形引擎 · 多策略并行 · 板材推荐 │ ├──────────────────────────────────────────────┤ │ 数据层 │ │ PostgreSQL PostGIS (几何数据) │ │ Redis (缓存) · MinIO/OSS (文件存储) │ └──────────────────────────────────────────────┘核心技术栈Vue 3 Spring Boot 3 JTS Topology Suite PostgreSQL/PostGIS Redis Docker Kubernetes。Canvas 2D 可视化支持拖拽编辑、5px 边缘吸附、批量对齐操作。导出方面支持 PDF 方案报告OpenPDF和 DXF 生产图纸LWPOLYLINE 实体可直接对接制造设备。八、效果验证指标数值板材利用率提升10% ~ 20%相比人工参数系统101 可配置字段混合拼版最多支持 4 种单板文件格式DXF R12~2018 / Gerber RS-274X/X2/X3 / ODB碰撞检测精度0.001mmJTS对于一个中型 PCB 工厂来说月消耗基材金额通常在百万级别。利用率提升 10%意味着每月直接节省六位数的原材料成本。九、总结PCB 拼版系统的算法设计面临三个核心挑战层级嵌套Pcs → Set → WPnl → Sheet 四层级不是简单累加每一层的最优解不一定构成全局最优异形处理不用外接矩形、用真实多边形放置是利用率从差不多到逼近最优的关键策略多样性矩形阵列、花式拼、横直料、AB 板 12 策略、镜像拼合——没有万能算法但组合在一起能覆盖绝大多数场景核心代码围绕FourLevelCalculator四层级计算、BottomLeftStrategy多边形底左放置、MirrorPairStrategy镜像拼合、AbPanelOptimizerAB 板优化、FragmentFiller碎片填充五个模块职责清晰、可独立测试。产品详情https://qiancaosoft.com/products/pcb-optimization