简介这套基于OpenMesh三角网络模型的补洞算法源代码面向从事三维建模、游戏开发及计算机图形学研究的开发者解决三维模型表面孔洞检测与填充问题。算法涵盖孔洞识别、邻接关系分析、填充策略选择、新面生成、拓扑更新及后处理等关键环节可帮助用户理解OpenMesh中网格修复的实现思路并在此基础上进行定制扩展。资源压缩包共66个文件大小33.62MB包含9个cpp源码、8个h头文件、3个ui界面文件及配套dll、ply模型、png图片等其中ui文件可用于可视化操作界面ply文件为带洞模型样例便于测试与演示。另有PPT课件与OpenGL查看器相关文件便于学习参考。目前已有2768人学习下载适合需要掌握网格补洞算法原理并希望获得可运行代码的中高级图形学开发人员。1. 补洞算法是网格处理里最容易被低估的一步拿到一个有洞的三角网格模型最直觉的做法是找到洞的边界点然后一个个连成三角形。等真的下手就会翻车非凸的洞直接扇形填充会出现三角形穿出洞外补出来的曲面在边界处法向突变一眼假。工业级的补洞要解决的不只是“封闭空隙”还要让补丁在曲率、法向和面积上与周围曲面自然衔接。OpenMesh 提供的半边数据结构让“找洞边界”这件事变得透明、可枚举算法核心从“猜哪里是洞”变成“确定性地遍历边界环并做高质量三角化”。这篇文章写给做逆向工程、3D 打印前处理、医学网格修复的从业者从最小可运行的补洞代码讲到保形平滑与高频踩坑全部围绕 OpenMesh 三角网格模型展开。2. 从半边结构到洞检测OpenMesh 给补洞提供了什么2.1 半边结构让“洞边界”成为可枚举的拓扑实体OpenMesh 的核心数据结构是半边Halfedge。每条无向边被拆成方向相反的两条有向半边其中一条属于某个三角形面另一条属于相邻三角形。当三角形网格存在洞的时候洞边缘的那条边只有一侧有三角形另一侧没有此时这条边对应的半边就是边界半边。调用mesh.is_boundary(halfedge_handle)就能直接判断某条半边是否处于洞的边界上这是补洞算法最关键的判定能力。与直接操作顶点索引数组不同半边结构允许你沿着next_halfedge_handle()指针在边界上顺序游走。从一个边界半边出发不断取它指向的下一条半边最终会回到出发点这个闭合的环就是洞的边界环。整个过程不需要额外的邻接表或搜索数据结构纯粹是拓扑层面的遍历。2.2 洞的类型直接影响算法选型从工程角度洞可以按几何特征分为三种简单凸洞边界环投影到平面后是凸多边形直接使用扇形三角化即可最快但适用范围窄。非凸洞边界环投影后是凹多边形扇形三角化会把三角形填充到洞的外部必须做“耳切法”或带约束的 Delaunay 三角化。窄长且扭曲的洞边界环在三维空间中严重弯曲平面投影会造成三角形重叠或翻转此时需要先做投影面估计再做平滑处理。在写代码之前先对洞的类型做一个粗略判断能避免 60% 以上的补洞翻车。常见的判断方式是计算边界环的凸性对环上每个顶点判断其前后两条边的叉积符号是否一致一旦出现符号变化就进入非凸处理流程。2.3 收集所有洞边界的完整代码下面这段代码用于遍历整个网格收集所有边界半边并组装成独立的边界环。这段代码可以直接编译运行读取一个 OBJ 文件后输出每个洞的顶点数量。#include OpenMesh/Core/IO/read_obj.h #include OpenMesh/Core/Mesh/TriMesh_ArrayKernelT.hh #include set #include vector #include iostream using Mesh OpenMesh::TriMesh_ArrayKernelT; // 收集网格中所有边界环每个环为一串顶点索引 std::vectorstd::vectorOpenMesh::VertexHandle extract_boundary_loops(Mesh mesh) { std::setOpenMesh::HalfedgeHandle boundary_hedges; // 第一次遍历把所有属于洞边界的半边放入集合 for (const auto he : mesh.halfedges()) { if (mesh.is_boundary(he)) { boundary_hedges.insert(he); } } std::vectorstd::vectorOpenMesh::VertexHandle loops; // 每次从集合中取出一条未处理的边界半边沿环游走 while (!boundary_hedges.empty()) { auto start_he *boundary_hedges.begin(); auto he start_he; std::vectorOpenMesh::VertexHandle loop; do { // from_vertex_handle 是当前半边的起点 auto from_v mesh.from_vertex_handle(he); loop.push_back(from_v); boundary_hedges.erase(he); // 沿着半边链走到下一条边界半边 he mesh.next_halfedge_handle(he); } while (he ! start_he); loops.push_back(loop); } return loops; } int main(int argc, char* argv[]) { Mesh mesh; if (argc 2) { std::cerr 用法: ./fill_hole input.obj std::endl; return 1; } if (!OpenMesh::IO::read_mesh(mesh, argv[1])) { std::cerr 读取网格失败 std::endl; return 1; } auto loops extract_boundary_loops(mesh); std::cout 检测到 loops.size() 个洞 std::endl; for (size_t i 0; i loops.size(); i) { std::cout 洞 i 边界顶点数: loops[i].size() std::endl; } return 0; }逻辑说明is_boundary(he)判断半边是否属于洞边界next_halfedge_handle(he)沿着边界环前进。整体流程是典型的“集合去重 环遍历”时间复杂度 O(n)n 为边界半边总数。参数说明start_he的选取决定了环的遍历顺序这里取boundary_hedges.begin()保证每个环只会被处理一次。loops中每个环的顶点顺序是沿边界半边方向排列的后续三角化时的顶点索引顺序必须基于这个方向否则新生成三角形的法向会反转。2.4 为什么不用“手动找孔”的替代方案有些网格库没有半边结构查找洞边界的做法是对每条边统计其被多少个三角形使用使用次数为 1 的边就是边界边。这个方案也能工作但需要自己维护边到三角形的映射表而且一旦遇到非流形边三条以上三角形共享就难以判断。OpenMesh 的半边结构把边界状态直接编码在数据结构中流形和非流形边界的处理方式不一致使用半边结构时可以直接用is_boundary()过滤不需要额外的映射表这也是在工程上我更倾向基于 OpenMesh 做补洞的原因。3. 最小可复现的补洞流程从边界环到三角化填充3.1 补洞的主流算法路线基于边界环信息的补洞算法大致分两类。第一类是直接法将边界环投影到平面上在二维空间做带约束的三角化然后把新顶点映射回三维。这种方案速度快、代码量小适合曲率变化不大的洞。第二类是隐式曲面法利用 Poisson 方程或径向基函数重构一个隐式曲面再提取等值面作为补丁。这类方法效果更好但实现复杂、计算量大。我的经验是工程起步阶段先实现直接法用耳切法处理非凸投影多边形配合后续的平滑迭代。直接法补出来的洞虽然曲率不够自然但在绝大多数逆向工程和打印修复场景中配合平滑后已经能达到交付标准。3.2 计算洞边界环的平均法向投影平面的选择是直接法最关键的一步。对边界环上的顶点做 PCA 或最小二乘平面拟合得到投影平面法向。简单场景也可以直接用环上首、中、末三个顶点叉积求法向但边界环一旦有轻微噪声三顶点法向就会不稳定。以下给出基于最小二乘的投影平面估计代码#include Eigen/Dense // 计算边界环顶点的最小二乘拟合平面法向 OpenMesh::Vec3f estimate_plane_normal( const Mesh mesh, const std::vectorOpenMesh::VertexHandle loop ) { size_t n loop.size(); Eigen::Vector3d centroid(0, 0, 0); for (auto v : loop) { auto p mesh.point(v); centroid Eigen::Vector3d(p[0], p[1], p[2]); } centroid / static_castdouble(n); Eigen::MatrixXd points(n, 3); for (size_t i 0; i n; i) { auto p mesh.point(loop[i]); points(i, 0) p[0] - centroid[0]; points(i, 1) p[1] - centroid[1]; points(i, 2) p[2] - centroid[2]; } // 对协方差矩阵做 SVD最小奇异值对应的右奇异向量即法向 Eigen::JacobiSVDEigen::MatrixXd svd(points, Eigen::ComputeThinV); Eigen::Vector3d normal svd.matrixV().col(2); return OpenMesh::Vec3f( static_castfloat(normal[0]), static_castfloat(normal[1]), static_castfloat(normal[2]) ); }逻辑说明通过 SVD 分解协方差矩阵得到最小特征值对应的特征向量此方向即为顶点分布最不显著的方向也就是拟合平面的法向。相比直接取三点叉积这个方案对边界噪声更鲁棒。参数说明centroid是所有边界顶点的重心投影时要把顶点减去重心再映射到二维。拟合平面法向有正反两个方向需要用周围已存在三角形的平均法向做对齐校正否则补丁的法向会整体翻面。3.3 投影与耳切法三角化拿到投影法向之后把边界环顶点投影到二维平面此时问题转化为一个二维多边形的三角化。耳切法Ear Clipping是一种稳定的凹多边形三角化算法核心思路是每次找到一个“耳朵”——即由连续三个顶点组成的三角形且这个三角形内部不包含其他顶点、中间顶点是凸点然后切掉这个耳朵重复直到只剩一个三角形。// 判断顶点 idx 是否为凸点在投影平面内 bool is_convex( const std::vectorEigen::Vector2d pts, int idx ) { int n static_castint(pts.size()); auto a pts[(idx n - 1) % n]; auto b pts[idx]; auto c pts[(idx 1) % n]; double cross (b - a).x() * (c - b).y() - (b - a).y() * (c - b).x(); return cross 0; // 逆时针方向为正 } // 判断点 p 是否在三角形 (a, b, c) 内部 bool point_in_triangle( const Eigen::Vector2d p, const Eigen::Vector2d a, const Eigen::Vector2d b, const Eigen::Vector2d c ) { auto sign [](const Eigen::Vector2d p1, const Eigen::Vector2d p2, const Eigen::Vector2d p3) { return (p1.x() - p3.x()) * (p2.y() - p3.y()) - (p2.x() - p3.x()) * (p1.y() - p3.y()); }; bool has_neg sign(a, b, p) 0; bool has_pos sign(a, b, p) 0; bool d1 sign(p, a, b) 0; bool d2 sign(p, b, c) 0; bool d3 sign(p, c, a) 0; return d1 d2 d3; } // 耳切法输入逆时针排列的二维顶点输出三角形索引对应原边界顶点 std::vectorstd::arrayint, 3 ear_clipping( const std::vectorEigen::Vector2d pts ) { std::vectorint indices; for (int i 0; i static_castint(pts.size()); i) indices.push_back(i); std::vectorstd::arrayint, 3 triangles; while (indices.size() 3) { bool clipped false; int n static_castint(indices.size()); for (int i 0; i n; i) { int prev indices[(i n - 1) % n]; int cur indices[i]; int next indices[(i 1) % n]; if (!is_convex(pts, i)) continue; bool contains_any false; for (int j 0; j n; j) { int v indices[j]; if (v prev || v cur || v next) continue; if (point_in_triangle(pts[v], pts[prev], pts[cur], pts[next])) { contains_any true; break; } } if (contains_any) continue; triangles.push_back({prev, cur, next}); indices.erase(indices.begin() i); clipped true; break; } if (!clipped) { // 退化情况剩余多边形可能自交或共线强制三角形化 for (int i 1; i 1 static_castint(indices.size()); i) { triangles.push_back({indices[0], indices[i], indices[i 1]}); } break; } } if (indices.size() 3) { triangles.push_back({indices[0], indices[1], indices[2]}); } return triangles; }逻辑说明外层循环每次切掉一个耳朵并删掉对应顶点内层循环用于寻找合适的耳朵。is_convex通过叉积正负判断凸性point_in_triangle使用同侧法判断其他顶点是否落在当前耳朵内部。参数说明这些代码要求传入的pts按逆时针排列。如果检测到边界环是顺时针需要先反转顶点顺序再传入。point_in_triangle的边界条件使用了严格不等式所以边界重叠顶点恰好落在三角形边上的情况可能导致三角形包含判定失败但实际工程中遇到这种情况的概率极低。3.4 把二维三角形映射回三维网格完成耳切法三角化后得到的是边界顶点的索引三元组。使用这些索引创建新的三角形面片并加入网格bool add_triangle_faces_to_mesh( Mesh mesh, const std::vectorOpenMesh::VertexHandle loop, const std::vectorstd::arrayint, 3 triangles ) { OpenMesh::Vec3f normal(0, 0, 0); for (auto v : loop) { normal mesh.normal(v); } normal.normalize(); for (const auto tri : triangles) { auto v0 loop[tri[0]]; auto v1 loop[tri[1]]; auto v2 loop[tri[2]]; // 根据法向对齐决定顶点插入顺序 auto face_normal (mesh.point(v1) - mesh.point(v0)) % (mesh.point(v2) - mesh.point(v0)); auto fh mesh.add_face(v0, v1, v2); if (!fh.is_valid()) { // 插入失败可能是退化三角形 std::cerr 警告添加三角形失败 std::endl; return false; } } return true; }逻辑说明add_face是 OpenMesh 的核心方法它会自动处理半边连接关系。上面的法向比较逻辑在前面第 3.2 节得到的法向和实际面的法向不一致时反转顶点顺序避免插入法向相反的三角形。参数说明mesh.normal(v)返回顶点的法向这里取边界环顶点的平均法向作为参考方向。%运算符在 OpenMesh 中已经被重载为叉积运算可以直接使用。4. 让补丁融入曲面法向估算与新顶点平滑策略4.1 直接三角化的结果在视觉上为什么“塌陷”直接三角化只能保证拓扑正确也就是洞被封闭了但补丁的几何形状很差。洞边界上的原始网格是有曲率的而新生成的三角形面片是平的并且耳切法产生的三角形方向只受投影平面影响没有考虑边界附近的曲率趋势。最终结果是补丁区域看起来像一块贴上去的平面在边界处法向突变严重。由于三角形内部没有新顶点单纯靠三角形布局无法模拟曲率变化。要解决这个问题需要对新生成的三角形做细分引入新顶点然后通过平滑迭代优化新顶点的位置。4.2 在新补丁上引入内部顶点对补丁三角形做 1-to-4 细分是一种简单做法。每个三角形被分成四个小三角形新增的三个顶点分别位于原三角形的三条边中点。细分之后内部顶点数量增加曲率表达的灵活性随之提高。// 对补丁区域执行一轮 1-to-4 细分 void subdivide_patch(Mesh mesh, const std::vectorOpenMesh::FaceHandle patch_faces) { std::vectorOpenMesh::VertexHandle edge_midpoint; for (auto fh : patch_faces) { // 收集当前面的三条边避免重复创建中点 for (auto e : mesh.fe_range(fh)) { auto v0 mesh.from_vertex_handle(mesh.halfedge_handle(e, 0)); auto v1 mesh.to_vertex_handle(mesh.halfedge_handle(e, 0)); OpenMesh::VertexHandle mid mesh.add_vertex((mesh.point(v0) mesh.point(v1)) * 0.5f); edge_midpoint.push_back(mid); } } // 三角形拆分需要沿用原三角剖分逻辑这里省略具体面拆分细节 }逻辑说明将原三角形展开为四个子三角形更新半边关系。由于拆分过程要维护半边结构的一致性OpenMesh 建议先收集所有边中点再一次性重建拓扑。参数说明细分迭代次数不宜过多。一次细分产生的内部顶点密度已经足够支撑拉普拉斯平滑的收敛多了反而会让补丁区域出现过度柔和。4.3 均匀拉普拉斯平滑改进补丁形态拉普拉斯平滑是最简单也是最实用的补丁整形手段。每个新顶点的位置向相邻顶点的重心方向移动经过多次迭代补丁区域逐渐变得平滑。void laplacian_smooth( Mesh mesh, const std::vectorOpenMesh::FaceHandle patch_faces, int iterations, double lambda ) { // 收集补丁区域的所有内部顶点排除边界环上的顶点 std::setOpenMesh::VertexHandle boundary_verts; for (auto fh : patch_faces) { for (auto fv : mesh.fv_range(fh)) { if (mesh.is_boundary(fv)) boundary_verts.insert(fv); } } std::vectorOpenMesh::VertexHandle interior_verts; for (auto fh : patch_faces) { for (auto fv : mesh.fv_range(fh)) { if (!boundary_verts.count(fv)) { interior_verts.push_back(fv); } } } for (int it 0; it iterations; it) { std::vectorOpenMesh::Vec3f new_positions; new_positions.reserve(interior_verts.size()); for (auto v : interior_verts) { OpenMesh::Vec3f avg(0, 0, 0); int cnt 0; for (auto vv : mesh.vv_range(v)) { avg mesh.point(vv); cnt; } if (cnt 0) avg / static_castfloat(cnt); OpenMesh::Vec3f current mesh.point(v); new_positions.push_back(current * (1.0f - lambda) avg * lambda); } for (size_t i 0; i interior_verts.size(); i) { mesh.set_point(interior_verts[i], new_positions[i]); } } }逻辑说明boundary_verts是补丁边界上的顶点这些顶点位置应当保持不变否则补丁会向内收缩或向外膨胀。vv_range(v)遍历顶点 v 的所有直接相邻顶点取平均位置作为目标位置。参数说明iterations建议 10~30 次lambda建议 0.5~0.7。lambda 过大会导致补丁区域过度收缩过小则收敛太慢。注意拉普拉斯平滑会缩小整体体积如果对体积敏感可以改用 Taubin 平滑交替使用正负 lambda 进行两步平滑分别记为 lambda 和 mu典型值 lambda0.5mu-0.53能显著抑制收缩效应。4.4 结合边界顶点法向做约束只做拉普拉斯平滑的问题是补丁边界处仍然生硬。改进方案是把边界环顶点的法向作为约束条件将边界顶点向外延伸一个微小距离使补丁与原始网格的过渡更自然。做法是在平滑前将边界顶点的位置沿法向移动一点平滑后再移动回来。实际工程中如果模型精度要求不高平滑后直接导出即可。如果要做高精度修复可以在平滑迭代中加入边界法向约束项// 在平滑位置更新时增加法向约束 OpenMesh::Vec3f constrained_pos current mesh.normal(v) * offset;这里 offset 一般取边界顶点到补丁区域平均距离的 1%~2%过大会导致边界鼓起。这个参数在不同模型上差异明显建议做成可调参数。5. 补洞避坑实录方向、孔洞与拓扑的边界问题5.1 补丁法向整体翻转渲染时出现黑色面片现象补完洞之后洞区域在渲染器里呈黑色或者从外部能看到内部表面。原因边界环的遍历方向与原始网格顶点环绕方向不一致。OpenMesh 的next_halfedge_handle沿边界半边的方向遍历这个方向可能顺时针也可能逆时针取决于半边数据结构的具体状态。如果遍历方向与原网格顶点环绕方向相反那么新生成的三角形顶点顺序也相反法向自然翻转。解决在新三角形加入网格前计算(v1 - v0) % (v2 - v0)得到实际法向与洞边界附近邻域面片的平均法向做点积如果点积为负交换 v1 和 v2 的顺序。这本质上是“先检测后校正”的思路加到代码里不需要额外数据结构成本极低。我一般在add_face之前做一个统一检查。5.2 凹洞填充后三角形跑到洞外面现象补洞后从俯视图看三角形区域明显超出洞的边界轮廓。原因对凹多边形直接做了扇形三角化。扇形三角化的基本原理是从一个固定顶点连接到所有其他顶点当多边形是凹的时候部分三角形必然会落在多边形外部。解决改用耳切法。过程中要注意is_convex的叉积符号与顶点序列的方向有关如果顶点是逆时针排列凸点的叉积为正顺时针排列则为负。建议统一把边界环转为逆时针后再做耳切法减少符号混乱的风险。补充说明如果模型是带噪扫描数据边界环本身可能有轻微自交耳切法的clipped标志会触发强制三角化的兜底逻辑。这些兜底产生的三角形质量较差建议在后续平滑中多迭代几次。5.3 检测到的洞环自相交或者环中包含重复顶点现象提取边界环后发现环的顶点序列中存在顶点位置几乎相同但索引不同的点或者环的路径在空间中交叉。原因输入网格本身存在非流形边或重复顶点。三角网格模型中两个洞靠得很近时边界环在空间上可能交错拓扑上却是两个独立环。解决先做网格清理。合并距离小于阈值的顶点并删除退化三角形。清理后再提取边界环环的质量会稳定很多。实际操作中这一步通常放在读入网格后立即执行而不是等到补洞环节。5.4 补洞后出现“无中生有”的孤立碎片现象补完洞部分正常但网格中出现了与其他三角形完全不相连的孤立三角形簇。原因洞边界环提取时漏掉了某些边界半边导致同一个洞被拆成了多个环或者边界环的起点选择不当导致后半段路径错乱。解决检查extract_boundary_loops的退出条件。while (he ! start_he)只适用于闭合环如果边界环的拓扑不闭合这个循环可能遍历到错误路径。提高鲁棒性的做法是在遍历过程中记录访问过的半边集合一旦遇到已经访问过的半边就中止当前环并输出警告。另外处理完主循环后检查是否还有未被遍历的边界半边若有则说明网格存在非流形边界需要单独处理。5.5 平滑后补丁区域出现明显凹陷或鼓包现象补洞区域经过拉普拉斯平滑后反而出现局部凹陷或鼓包与周围曲面对不上。原因拉普拉斯平滑本身不具有体积保持性。当边界顶点分布不均匀时重心平均的方向会偏向密集区域导致顶点向一侧聚集。另一种情况是平滑迭代次数过多补丁区域过度收缩而边界环上的顶点又没参与平滑导致边界处出现明显的“断崖”。解决改用 Taubin 平滑并控制迭代次数。Taubin 的两步平滑策略可以显著减少收缩效应。更稳健的做法是设定两次迭代之间的位置变化量阈值当最大变化量小于某个值比如网格包围盒对角线长度的 0.001 倍时提前终止迭代。5.6 补洞对精度有要求时普通平滑不再够用以上坑都避掉之后补出来的洞在几何上已经可用了。但精度要求高的场景比如医学模型或精密零件逆向补丁区域仍然能看出“补”的痕迹。这时需要引入更严格的约束在平滑迭代中增加顶点到周围曲面的偏差检查或者改用隐式曲面重建算法。后者实现复杂度明显提升但效果完全是另一个层级。6. 从“能补”到“补得准”面积、曲率与参数收敛的验证方法6.1 用面积偏差作为快速验证指标补洞质量的第一个量化指标是面积。补洞区域的面积应该接近原始表面的面积偏差过大说明补丁形状与真实曲面相差很远。计算方法将补丁三角形面积求和与洞边界环投影到拟合平面上的多边形面积做对比。面积偏差超过 15% 时需要检查平滑参数是否过大或者投影平面估计是否偏差过大。实际操作中快速验证流程很有价值参数调整后先输出面积数据再决定是否进入精细验证。6.2 曲率变化图是更可靠的验证手段面积只能反映整体偏差补丁与周边曲面的曲率连续性则用曲率变化图验证。对网格上每个顶点计算平均曲率然后检查补丁边界两侧的曲率差值。差值过大说明补丁虽然在面积上接近但几何过渡仍然不自然。我会在代码中导出补丁边界顶点和其相邻外部顶点的曲率值输出到表格顶点类型平均曲率范围高斯曲率范围边界环附近外部顶点0.02 ~ 0.080.01 ~ 0.04补丁内部顶点0.01 ~ 0.050.00 ~ 0.02如果两组数据的曲率范围差距过大就把平滑迭代次数增加 5~10 次再测。6.3 参数收敛曲线帮助自动确定迭代次数平滑迭代次数不要拍脑袋定我的习惯是记录每次迭代后的补丁区域最大位移量当位移量小于阈值的迭代次数区间保持稳定时说明参数已经收敛。把迭代次数从 5 逐步增加到 50每次记录面积偏差偏差值不再明显变化的点就是当前模型的最佳迭代次数。这些验证方式都是已经落地的工程习惯并不复杂但能把补洞从“看起来行”变成“有数据支撑地行”。我也多次因为跳过验证环节把参数调到某个局部最优解而不自知后来养成了每改一个参数就导出面积和曲率的习惯翻车概率大幅下降。补洞算法没有万能参数不同来源的网格对参数敏感度差异极大留好可调接口用数据说话才是真正可复用的方案。希望帮到你。本文还有配套的精品资源点击获取