桌面应用智能硬件【免费下载链接】OrcaSlicer-bambulab项目地址https://gitcode.com/gh_mirrors/or/OrcaSlicer-bambulab点击查看免费下载Earcut 是 Mapbox 出品的快速多边形三角剖分库 earcut.js 中。它在经典耳切ear clipping算法的基础上引入 z-order 曲线哈希加速并原生支持孔洞holes、非简单多边形含自相交与退化情形的健壮处理。在 OrcaSlicer-bambulab 中该库被集成在 deps_src/earcut 目录下作为切片器 UI 的零件拾取Skip Part画布三角化工具见 SkipPartCanvas.cpp本文将从 API 使用、算法原理到仓库实际集成完整讲解这一工具的正确打开方式。Earcut 是什么定位与设计目标Earcut 的定位非常明确针对二维平面多边形的高性能三角剖分。它实现的是经过 z-order 曲线哈希优化的改良耳切算法设计目标并非在所有输入上都保证数学意义上的严格正确而是对地理图形等实际数据始终给出可接受的结果——这一定位在官方 README 中有明确说明attempts to always produce acceptable results for practical data like geographical shapes。在算法思想上Earcut 主要借鉴了两份经典文献Martin Held 的 FIST: Fast Industrial-Strength Triangulation of PolygonsDavid Eberly 的 Triangulation by Ear Clipping。后者正是 Earcut 中findHoleBridge孔洞桥接寻找算法的基础——源码注释中明确标注了 David Eberlys algorithm for finding a bridge between hole and outer polygon见 earcut.hpp。需要注意 Earcut 的能力边界它工作在 2D 平面上。如果输入数据具有三维或更高维度官方建议先投影到二维平面再三角剖分或改用 CGAL 等更专业的库。快速上手最小的三角剖分示例Earcut 的 API 极其精简。核心入口是mapbox::earcutN(polygon)模板函数它接受一个多环polygon容器返回三角形索引数组。#include earcut.hpp // 三角剖分使用的坐标数值类型 using Coord double; // 索引类型默认 uint32_t若顶点数确定不超过 65536可用 uint16_t 节省内存 using N uint32_t; // 点类型std::arrayCoord, 2 using Point std::arrayCoord, 2; std::vectorstd::vectorPoint polygon; // 填充多边形数据。任何环绕方向顺/逆时针均可。 // 第一条 polyline 定义主多边形。 polygon.push_back({{100, 0}, {100, 100}, {0, 100}, {0, 0}}); // 后续 polyline 定义孔洞。 polygon.push_back({{75, 25}, {75, 75}, {25, 75}, {25, 25}}); // 执行三角剖分 // 返回的索引数组指向输入多边形的顶点 // 例如索引 6 对应本例中的 {25, 75}。 // 每三个连续的索引构成一个三角形输出三角形为顺时针方向。 std::vectorN indices mapbox::earcutN(polygon);索引语义详解理解返回值语义是正确使用 Earcut 的关键indices是扁平的顶点索引数组长度为3 × 三角形数量三个连续的索引构成一个三角形(indices[0], indices[1], indices[2])、(indices[3], indices[4], indices[5])……以此类推索引是全局扁平编号所有环外环 各孔洞的顶点被按顺序统一编号编号 0 起从第一个环开始累积。README 中明确指出 the index 6 would refer to {25, 75} in this example——本例中第一个环占 03 四个索引第二个环孔洞的顶点从 4 开始{75, 25}为 4、{75, 75}为 5、{25, 75}为 6、{25, 25}为 7输出三角形为顺时针clockwise方向输入多边形可以任意环绕方向内部会自动归一化。在 OrcaSlicer 的实际代码中可以看到完全一致的用法SkipPartCanvas::LoadPickImage将 OpenCV 提取的轮廓外轮廓 层级子轮廓组装成std::vectorstd::vectorFloatPoint多边形调用mapbox::earcutuint32_t(polygon)后按每 3 个索引一组展开成三角形顶点序列用于渲染SkipPartCanvas.cpp。输入数据模型多边形、孔洞与自定义点类型容器约定Earcut 的输入是环的集合外层 vector表示多边形polygon其第一个元素是外环其余元素是孔洞内层 vector表示一个环ring/polyline即按顺序排列的顶点序列每个点通过mapbox::util::nth0/1, Point::get(point)访问其 X/Y 坐标。默认情况下库为std::tuple、std::pair和std::array提供了开箱即用的访问器。若使用自定义点类型如 Clipper 库的IntPoint只需在mapbox::util命名空间内特化nth模板即可// struct IntPoint { // int64_t X, Y; // }; namespace mapbox { namespace util { template struct nth0, IntPoint { inline static auto get(const IntPoint t) { return t.X; }; }; template struct nth1, IntPoint { inline static auto get(const IntPoint t) { return t.Y; }; }; } // namespace util } // namespace mapbox自定义的环容器同样可行只要类似std::vectorT满足 C Container。孔的语义所有后续polyline 均被视为孔洞holes。这意味着 Earcut 支持带孔的多边形这一常见且重要的输入形态——这在 3D 打印切片场景中尤其关键模型截面轮廓island/contour天然就是外环 多个孔洞的复合结构。算法原理改良耳切 z-order 加速 多级纠错从源码结构看Earcut 的算法流水线可分为五个阶段全部封装在mapbox::detail::EarcutN类中earcut.hpp阶段一构建环形双向链表linkedListearcut.hpp首先通过叉积求和计算每个环的原始环绕方向然后按目标方向外环顺时针、孔洞逆时针把顶点链接成环形双向链表。这一设计使得后续切耳操作只需局部指针重排代价极低。重复坐标点会在此时被剔除。阶段二剔除共线与重复点filterPointsearcut.hpp遍历链表删除相邻的重复点以及三点共线area 0的中间点避免退化三角形。阶段三消除孔洞eliminateHolesearcut.hpp将每个孔洞环按最左点getLeftmostearcut.hpp排序后从左到右处理通过findHoleBridge基于 David Eberly 算法的射线扫描earcut.hpp找到孔洞与外部环之间的桥再用splitPolygonearcut.hpp把孔洞缝合进外环最终形成单一无孔环。sectorContainsSectorearcut.hpp用于在桥接候选点角度相同时进行扇形包含判定。阶段四z-order 曲线哈希加速这是 Earcut 性能的核心。在operator()中会先统计顶点总数并计算包围盒earcut.hpp顶点总数较小时阈值threshold 80见 earcut.hpp关闭哈希走朴素路径否则启用hashing将坐标归一化映射到 15 位整数范围inv_size 32767 / max(rangeX, rangeY)通过位交织bit interleaving计算 z-order 值zOrderearcut.hpp再用 Simon Tatham 的链表归并排序sortLinkedearcut.hpp建立 z-order 有序链表。在earcutLinked主循环earcut.hpp中isEarHashedearcut.hpp利用 z-order 顺序只检查候选三角形包围盒附近的点而不是遍历所有顶点做点包含测试从而将耳切从 O(n²) 显著加速到接近 O(n log n) 的实用性能。indexCurveearcut.hpp负责在首次切耳前完成 z-order 链表的构建。阶段五多级纠错兜底earcutLinked的核心循环earcut.hpp采用三趟递进的纠错策略处理切不出耳的死局pass 0正常切耳 z-order 哈希pass 1filterPoints过滤后再切仍失败则调用cureLocalIntersectionsearcut.hpp局部修复自相交pass 2最后手段splitEarcutearcut.hpp寻找有效对角线把剩余多边形一分为二分别递归三角剖分。配套的几何判定原语包括有向面积areaearcut.hpp、点在三角形内测试pointInTriangleearcut.hpp、线段相交intersects/onSegmentearcut.hpp、对角线合法性isValidDiagonalearcut.hpp等共同支撑了 Earcut 对退化情形、自相交和拧麻花多边形的鲁棒处理。内存管理对象池Earcut内部还内置了一个按块分配的ObjectPoolNodeearcut.hpp预分配len * 3 / 2个节点earcut.hpp避免高频三角剖分时的频繁小对象分配——这在切片器逐层、逐轮廓反复调用的场景下对性能影响显著。源码级验证OrcaSlicer 中的真实调用链集成方式在本仓库中earcut 以纯头文件 INTERFACE 库的形式集成构建配置见 deps_src/earcut/CMakeLists.txtadd_library(earcut INTERFACE)将earcut.hpp所在的 deps_src/earcut 目录作为系统包含目录导出在 deps_src/CMakeLists.txt 中通过add_subdirectory(earcut)被纳入依赖构建树与 agg、nanosvg、nlohmann 等一同归为 header-only 库组。因此在使用侧只需要#include earcut/earcut.hpp并链接earcutINTERFACE 目标无需任何源文件参与编译。实际调用场景Skip Part 零件拾取画布Earcut 在 OrcaSlicer 中的实际消费点在 GUI 层的 src/slic3r/GUI/SkipPartCanvas.cpp第 11 行#include earcut/earcut.hpp引入头文件LoadPickImage流程中OpenCV 的cv::findContours以树形层级cv::RETR_TREE提取图像轮廓后代码把最外层轮廓parent -1的根轮廓作为外环将其全部子轮廓hierarchy[i][2]链作为孔洞依次emplace_back进 polygonSkipPartCanvas.cpp调用mapbox::earcutuint32_t(polygon)得到索引数组SkipPartCanvas.cpp随后按每 3 个索引一组将flat_points展开为三角形顶点序列SkipPartCanvas.cpp供 OpenGL 画布渲染跳过零件的拾取遮罩。这一用例完美印证了 README 的核心 API第一条 polyline 定义主多边形后续 polyline 定义孔洞并且输入点类型FloatPoint含x/y浮点成员也能被uint32_t索引正常驱动展示了自定义点类型方案的现实可行性。构建与测试三种接入方式方式一仅作库使用推荐Earcut 是单头文件库直接拷贝earcut.hpp到你的项目按上文 Usage 示例#include earcut.hpp即可使用无需构建任何东西。方式二构建官方测试/基准/可视化程序克隆完整仓库后按以下步骤生成并编译git clone --recursive https://github.com/mapbox/earcut.hpp.git cd earcut.hpp mkdir build cd build cmake .. make # ./tests # ./bench # ./viz依赖要求git、CMake 3.2、OpenGL SDK以及 GCC 4.9 / Clang 3.4 / MSVC12 等编译器在 Windows 等系统上可能需手动把 cmake 和 git 加入 PATH。其中./tests验证正确性、./bench评估性能、./viz提供可视化验证。方式三IDE 生成工程Visual Studio / Eclipse / XCode 用户可用 CMake 生成器创建 IDE 工程git clone --recursive https://github.com/mapbox/earcut.hpp.git cd earcut.hpp mkdir project cd project cmake .. -G Visual Studio 14 2015 ::you can also generate projects for Visual Studio 12 2013, XCode, Eclipse CDT4 - Unix Makefiles生成后直接用 IDE 打开工程即可。CLion、Visual Studio 2017 则可以直接导入该仓库。版本与状态本仓库 deps_src/earcut 所携带的版本基于earcut 2.2.4对应上游 earcut.js 2022-07-05 发布的 2.2.4 版本属于成熟稳定的里程碑版本。该版本在孔洞消除、z-order 哈希与多级纠错方面均已经过大量实践验证。总结与实践建议Earcut 之所以被 OrcaSlicer 选中用于零件拾取画布这类高频调用的场景核心在于其零依赖单头文件、接口极简、性能优异且能容忍脏数据的组合优势接口层mapbox::earcutN(polygon)一行调用输入支持任意环绕方向、任意环数的多边形输出为可直接喂给 GPU 的顺时针三角形索引类型层通过nth特化与 Container 概念解耦坐标访问从std::array到 ClipperIntPoint都能无缝适配算法层z-order 哈希将耳切的点包含测试从全量扫描降为包围盒局部查询配合对象池与链表结构在高顶点数轮廓上依然保持流畅鲁棒层三趟递进纠错过滤 → 局部修复自交 → 对角线拆分保证了实际脏数据总能得到可用三角化结果。对于在 3D 打印切片软件中需要外环 孔洞复合轮廓三角化的读者直接复用 earcut 的这套模式参考 SkipPartCanvas.cpp 的组装-调用-展开三段式写法即可获得生产级可用性若输入数据维度超过二维请按官方建议先投影到平面或转向 CGAL 等专用库。赞分享桌面应用智能硬件【免费下载链接】OrcaSlicer-bambulab项目地址https://gitcode.com/gh_mirrors/or/OrcaSlicer-bambulab点击查看免费下载相关推荐仓颉 JSON 流式序列化格式控制实战WriteConfig 配置详解cangjie_stdx仓颉 JSON 流式序列化格式控制实战WriteConfig 配置详解cangjie_stdx 本文围绕 cangjie_stdx 中 stdx.enco标准库网络密码学并发编程three.js 中的 Earcut 多边形三角剖分API 用法与源码级原理解析three.js 中的 Earcut 多边形三角剖分API 用法与源码级原理解析 本文围绕 three.js 仓库内建的多边形三角剖分模块 Earcut 前端3D渲染图形学如何在5分钟内为Minecraft搭建高性能模组加载环境Fabric Loader实战攻略如何在5分钟内为Minecraft搭建高性能模组加载环境Fabric Loader实战攻略 你是否曾为Minecraft模组加载的复杂配置而烦恼或是厌倦了传上一篇用 Terratest 为 Azure Resource Group 的 Terraform 模块编写自动化测试terratest 实战指南下一篇Ubuntu Autoinstall Generator5分钟实现无人值守系统部署的终极方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
