libnest2d详解：基于NFP的2D不规则自动套料实践

简介libnest2d是一个用现代C11编写的2D不规则排样与嵌套库定位为二维装箱问题的轻量级解决方案适用于激光切割排版、矩形与异形件下料、CNC加工等需要自动排布的工业场景。库采用模板化几何算法核心逻辑以头文件方式提供使用者可接入已有几何类型也可选择内置的Boost.Geometry默认后端在开箱即用和深度定制之间取得平衡适合具备C基础、希望研究或集成排样算法的开发者和研究者。资源包为ZIP格式压缩后大小约385KB体积非常精简文件数量及类型明细暂无有效数据因此简介不罗列具体文件。该库源自开源项目的fork延续了原始版本并回移稳定更新对实验性新功能保持开放便于对照学习与二次开发。当前仍属完善阶段对孔洞、凹面等复杂形状支持尚有限但作为2D嵌套算法框架具有参考价值已有1185人学习浏览。 做激光切割、水刀切割、服装排料或者板式家具的同行应该都遇到过这种场景客户丢来几十个不规则形状要求你在1220x2440的板材上尽量少浪费。手动拖是能拖但拖完总有一个角落空得让人心疼。我最早接触libnest2d就是因为要在内部工具里做自动套料。这个库用现代C实现了2D不规则装箱和嵌套把“自动排样”这件事做成了可嵌入的算法库不是依赖CAD软件里的宏脚本而是可以直接编译进自己的程序。最吸引我的一点是它稳定、开源背后有PrusaSlicer这种量级的产品在长期使用。这篇文章不打算贴一堆源码就完事而是会聊聊它到底解决了什么问题、核心算法是怎么工作的、我实际接入时踩过哪些坑以及把它做成生产工具还需要补什么。1. 为什么我会在一堆排样方案里挑中libnest2d1.1 手动排样与自动嵌套的差距在哪里不规则形状的排样本质上是一个组合优化问题。两个零件互相咬合空出来的三角区可能正好塞下第三个零件第三个零件旋转15度之后也许还能继续塞进第四个。这个搜索空间极其庞大人的空间想象能力再强也只能在十几个零件的范围内接近最优。一旦零件数量超过五十个手动拖拽基本就是碰运气。矩形排样相对简单因为规则形状的几何约束非常明确。但激光切割、服装裁剪里碰到的多是凹多边形、带孔零件、圆角轮廓这些形状之间的“互补性”很难一眼看出来。自动嵌套算法可以把每个候选位置都计算一遍把所有角度的可能性都列出来然后挑一个综合评价值最高的方案。这不是“省几分钟人工”的问题而是直接决定一块板材能不能少开一张在批量生产里就是实打实的成本差异。1.2 现代C实现的优势可嵌入、高性能、生态成熟当时我对比过几类方案。网页版的SVG Nest胜在交互好但处理几百个复杂多边形时浏览器会卡一些Python库做原型很方便但真要接到C/Qt桌面软件里多一层绑定就多一层维护成本。libnest2d的优势在于它本身就是C库底层几何计算直接跑在本地没有虚拟机或解释器开销。而且它用C17标准模板化程度高几何类型通过Boost.Geometry统一管理。这意味着你可以直接把它和工程里已有的几何处理代码串起来不用来回做数据转换。它的算法实现也经过了PrusaSlicer里“自动排列”功能的长期打磨稳定性和结果质量比那些教科书级的Demo实现可靠得多。对我来说最关键的一点是它不强迫你接受一套完整软件而是可以像一颗算法引擎一样嵌到自己的工具链里边界、旋转规则、间距这些都能自己控制。2. 核心概念先搞清NFP、旋转离散化、余料回收2.1 no-fit polygon判定两片能否靠在一起的数学基础libnest2d的底层核心是no-fit polygon简称NFP中文圈子里一般叫“不适应多边形”或“禁止区多边形”。理解这个概念是理解整个嵌套算法的基础。想象有两个多边形A和B。把A固定不动让B贴着A滑动。选B上任意一个参考点比如它的某个顶点或重心。当B绕着A移动时这个参考点会画出一片区域。如果参考点落在这片区域内部B就和A发生重叠落在边界上B刚好和A相切落在区域外则没有任何交集。这个“内部即重叠”的区域就是NFP。构造NFP本质上是在计算A和B的Minkowski差也就是把B取反、再沿着A的轮廓扫一圈得到的形状。有了NFP之后判断两个零件是否碰撞就从一个复杂的多边形求交问题简化成一个“点是否在多边形内”的问题。在需要反复尝试成千上万个候选位置的嵌套场景里这个加速非常关键。很多人第一次接触嵌套算法时会误解以为核心是“怎么算两个多边形的重叠面积”其实性能瓶颈在于“快速排除非法位置”NFP解决的就是这一点。2.2 角度离散化旋转步长如何影响排样率与计算量实际排样中零件可以旋转任意角度。但连续角度下NFP的计算成本高到不可接受所以工程实现普遍采用角度离散化提前把零件旋转到一组固定角度每个角度单独构造NFP然后在候选位置搜索时直接用这些预计算结果。角度步长通常是5度、2度或1度。步长越小找到更紧凑布局的可能性越高但NFP数量也会成倍增长。我的建议是不要对所有零件统一采用高精细旋转。圆形件、正方形件旋转不旋转几乎没有区别完全可以从旋转列表里去掉而长条形、大弧度零件旋转角度对空间利用率影响很大值得用1度甚至0.5度步长。旋转步长每个零件的候选角度数特点5度72计算快适合大批量粗排可能浪费2%-5%材料2度180折中多数场景够用1度360排样更紧凑NFP占用内存和计算时间明显上升0.5度720只在零件数量少、材料昂贵时推荐2.3 嵌套流程从零件列表到结果姿态的完整链路libnest2d的单次嵌套流程大致是这样的先把待排零件按面积从大到小排序面积大的先定位再处理面积小的。排第一个零件时通常放在板材左下角或边界贴合位置。之后每个新零件都会尝试所有旋转角度和所有可行位置然后根据评价函数挑选最佳位置。评价函数可以是最低重心、最小包围盒增量、最贴边等不同策略会带来完全不同的布局风格。这个过程是贪心的不保证全局最优。但实际效果足够好尤其在零件数量多、板材尺寸大的时候贪心策略的速度优势非常明显。如果想要更优解可以在libnest2d排完之后再对结果做局部搜索比如两两交换位置重新嵌套。我见过不少团队直接拿贪心结果当最终方案因为利用率已经接近商用软件水平再优化可能最多提升1%-2%投入产出比不高。3. 从clone到跑通demo的编译实操3.1 依赖准备与CMake构建libnest2d依赖的第三方库不算多核心是Boost.Geometry。如果你在Ubuntu上操作先把基础依赖装上sudo apt update sudo apt install libboost-dev cmake gBoost.Geometry是一个纯头文件库所以一般不需要额外编译Boost本身。克隆代码之后直接走标准CMake流程git clone https://github.com/PrusaResearch/libnest2d.git cd libnest2d cmake -S . -B build -DBUILD_TESTINGOFF cmake --build build -j$(nproc)如果你的项目要用CMake集成可以把libnest2d作为子目录加进来然后链接它导出的target。有一点要注意不同commit之间的API差异很大类名和命名空间经常会变。当前master和项目release版本可能不是一个接口。最稳妥的方式是先看官方examples目录里面通常有可直接运行的demo再仿照它写自己的代码。3.2 一个最小排样示例矩形板材加7个不规则零件下面这段代码是核心调用关系具体接口以你clone到的版本为准#include libnest2d/libnest2d.hpp // 坐标类型和几何类型一般都在这个命名空间下 using namespace libnest2d; int main() { // 1. 创建矩形板材例如 1220 x 2440 auto bin makeRectangle(1220.0, 2440.0); // 2. 构造待排零件多边形顶点按逆时针排列 std::vectorItem items; // ... 从你的数据源解析出多边形后填充 items // 3. 配置嵌套参数 NestConfig cfg; cfg.rotations 360; // 每1度一个候选角度 cfg.distance 1.0; // 零件间距1mm相当于留刀缝 // 4. 执行嵌套 auto placements nest(items, bin, cfg); // 5. 遍历结果拿到每个零件的最终变换 for (auto p : placements) { auto poly p.polygon(); auto rot p.rotation(); auto tr p.translation(); // 把poly/rot/tr写入DXF或SVG } }如果你用的是较新版本Item、NestConfig这类名字往往会带模板参数甚至会多一层NestingContext。不要慌官方示例里怎么写就跟着怎么写。核心逻辑是一样的构造输入、配置参数、调用嵌套、读取结果。只要第一步跑通后面就能慢慢扩展。3.3 编译期间最容易翻车的三个坑我clone这个库之后第一次编译并不顺利卡了差不多一个晚上。最常见的坑有以下几个Boost版本太旧。某些旧版Boost.Geometry的模板实现不够完善编译时会报大段模板错误定位不到具体原因。升级到较新的libboost-dev后问题直接消失。没开C17。libnest2d用到了很多现代C特性如果CMake没有设置CMAKE_CXX_STANDARD 17编译时会报一堆“没有匹配的构造函数”错误。在vscode里配置C/C环境时也要记得在tasks.json或CMakePresets里把标准版本指对。多边形顶点顺序和闭合问题。输入多边形如果没按逆时针方向或者首尾没闭合NFP计算结果会整体翻转排出来的结果看起来每个零件没有重叠但放到实际坐标里就全错了。建议在接入自己的数据源时写一个清洗函数统一处理顶点顺序和重复点。4. 把参数调稳排样率、间距、时间三者的取舍4.1 间距与“留刀缝”的正确建模方式排样不是让零件严丝合缝地贴在一起。激光切割有光斑直径等离子切割有割缝服装裁片之间要留出裁剪余量。这些工程约束最终都会转化成零件间距。最简单的方式是用cfg.distance直接设置最小间距。底层实现通常会把多边形做一个外扩偏移相当于每个零件都披上一层“安全距离外壳”再用外扩后的形状去嵌套最后拿到的坐标直接用于切割路径。间距设大了浪费材料设小了又可能撞刀或者切穿。以精细激光切割为例0.1mm-0.5mm通常够用如果是数控铣削刀具半径较大间距可能要留2mm以上。我习惯的做法是先在CAD里测一下板材实际可接受的切割精度再反推间距参数而不是拍脑袋填。还有一个隐藏点distance设成负数有没有意义我试过负值理论上可以让零件互相嵌入但实际中很少用到而且容易产生非法结果不要随便玩。4.2 旋转步长的实际选择建议旋转步长的选择要结合零件形状。一个长宽比接近10:1的长条金属件在5度步长下只能转到5的倍数角度可能刚好错过某个能让它“躺着塞进空隙”的最优姿态。而接近方形的零件1度和5度差别不大却要多付出5倍的计算资源。我现在的经验是第一轮用5度或10度步长跑一遍粗排快速估算材料利用率和板材够不够用。如果利用率接近预期就直接用粗排结果如果差太多再对影响最大的几个零件单独设置1度步长重新排。libnest2d允许给不同零件指定不同的旋转列表这是一个很实用的能力。给每个零件配置独立的旋转子集能显著减少NFP数量计算时间从几分钟降到几十秒都见过。4.3 结果评估不能只看利用率还要看可切割性排样率当然重要但生产环境里它不是唯一指标。一个排样率很高的方案可能把所有小零件都塞在板材中央的窄缝隙里导致切割头路径复杂、热变形集中甚至让薄板局部温度过高烧穿。又或者零件之间虽然不重叠但间距太小切完最后一个零件时整板已经松动移位后面全切歪。所以我在项目里会对libnest2d的原始结果做一道“工艺检查”筛选出窄缝宽度小于危险阈值的区域标记出来给人工复核对板材周围的夹持点附近留出非切割区域避免切掉定位用的耳朵。这个动作不在算法库里但决定了算法能不能真正上产线。5. 工程落地时绕不开的边界情况与二次开发5.1 带孔零件、凸包近似、废料区二次嵌套libnest2d支持带孔多边形这一点在衣服裁片和金属框体件里非常有用。很多简易排样库只处理简单外轮廓孔洞会被忽略结果会导致两个零件的孔区域被其他零件占用看着不重叠实际加工时是冲突的。用带孔多边形参与NFP计算虽然会慢一些但结果更真实。如果某个零件的轮廓极其复杂凹进去十几个牙齿形状计算NFP会很吃力。一个工程上常用的妥协是先计算它的凸包用凸包代替原形状参与粗排等粗排结束再把原形状放进去验证。代价是可能浪费少许空间但速度提升非常明显。注意这只是性能优化手段不是默认操作只有在你觉得排样慢到不能接受时才启用。废料区二次嵌套是很容易被忽视的提升利用率的办法。第一轮大件排完后板材上还有很多不规则的空白区域。这些区域本身也是多边形可以提取出来作为新的“板材边界”再把剩余的小零件放进去嵌套一轮。我见过不少团队第一轮结束就直接生成切割文件其实第二轮往往能多塞下10%-20%的小零件。5.2 数据交换从DXF/SVG到libnest2d的几何输入libnest2d本身不做文件解析它接收的是内存里的几何对象。实际项目里数据基本来自DXF、SVG或者企业内部的CAD格式。这部分往往比嵌套算法本身更让人头疼。我遇到过最典型的问题是坐标系不一致。DXF默认是右手坐标系y轴向上SVG是y轴向下。如果不做转换排样结果在导出时会出现镜像零件看起来没问题但实际切割方向反了。单位问题同样要命DXF用毫米SVG可能用像素还有图纸里胡乱缩放的情况。我在接入环节会先做一个统一的“几何清洗管道”解析文件、统一单位、统一坐标系、闭合多边形、去重再进入libnest2d。这个管道写完之后后面换再多的数据格式也只是多写一个解析器的事。5.3 自己维护一个生产可用的套料工具需要补哪些功能libnest2d只负责“把零件放到哪里”不负责“怎么展示、怎么手工干预、怎么变成切割路径”。如果要做一个给车间师傅用的工具至少要补这些模块排样结果预览在Qt或Web端渲染出零件轮廓支持缩放、测量。手动调整允许师傅锁定某个零件的位置其他零件围绕它重新排。旋转角度和间距约束界面里能改参数不需要重新编译程序。导出多格式DXF、DWG、PDF、CSV加工单至少要有一种能直接对接切割设备。布局报告每张板的利用率、零件数量、预计切割时间方便统计成本。这些功能加起来的工作量可能比集成libnest2d本身还大。但如果只是给自己写个小脚本那完全不需要全套平台直接命令行输出SVG结果就够了。5.4 技术栈扩展给C核心加一层桥如果你的前端是Web或者团队更擅长Python/JavaScript没必要把整个排样工具都用C写。libnest2d的核心算法是纯C可以编译成WebAssembly在浏览器里跑也可以封装成C接口供其他语言调用。我自己的项目里就用CFFI封装了一个很小的C接口只暴露“传入多边形列表参数返回位置和姿态”。这样做的好处是算法升级时只替换底层动态库上层界面一行不用改。不过要提醒一句封装层越薄越好。不要把业务逻辑全部塞进C那边否则后续调试和迭代都会很痛苦。保持“C负责几何计算上层负责交互展示”的边界是最不容易翻车的方式。实际用下来libnest2d确实把最难的“2D不规则嵌套”部分做得很扎实。以前需要人工盯半小时的排版现在程序跑完直接出结果剩下的工作主要是核对工艺参数和异常零件。如果你正准备做套料系统我的建议是先花一个晚上把官方demo跑通再拿自己真实的零件数据测一遍排样效果比直接读源代码有用得多。最后分享一个小技巧排样前把所有零件做一次顶点简化删除距离小于0.01mm的重复点NFP构造速度会明显提升这个细节在很多文档里都不会写。本文还有配套的精品资源点击获取