网格修复

1. 网格介绍

网格指的是三维多边形网格模型，以下简称为“网格”。简单来说，可以给网格下一个简单定义：由多边形集合定义的，用以表示三维模型表面轮廓的拓扑和空间结构称为“网格”，英文称作“polygon mesh”或“mesh”。

其中，尤以三角网格应用最为广泛（表示最为简单且稳定），因此本文一般讨论的网格是三角网格，但即便是由四边形及以上的多边形构成的网格也可以通过三角剖分（Triangulation）算法来获得三角网格。

2. 网格修复介绍

在3D打印，CAD研发，多目重建，三维扫描重建，数字文物建模以及其他三维图形处理领域，多半会遇到网格表面的质量不够好的情况。

四种典型的网格质量问题

总结来说，网格的问题可以归结为六种：
1. 法向错误（反向？）
  
  三角形的顶点次序与三角形面片的法向量不满足规则。这主要是由于生成STL文件时顶点顺序的混乱导致外法向量计算错误。这种错误不会造成以后的切片和零件制作的失败，但是为了保持三维模型的完整性，我们必须加以修复。
2. 孔洞
  
  这主要是由于三角面片的丢失引起的。当CAD模型的表面有较大曲率的曲面相交时，在曲面相交部分会出现丢失三角面片而造成孔洞。孔洞修复通过添加新的面片以填补缺失的区域。
3. 缝隙
  
  通常由于顶点不重合引起的。缝隙和孔洞都可以看作是三角面片缺失产生的。但对于裂缝，修复通常是移动点将其合并在一起。
4. 多壳体
  
  壳体的定义是一组相互正确连接的三角形的有限集合。一个正确的STL模型通常只有一个壳。存在多个壳体通常是由于零件块造型时没有进行布尔运算，结构与结构之间存在分割面引起的。
  
  STL文件可能存在由非常少的面片组成、表面积和体积为零的干扰壳体。这些壳体没有几何意义，可以直接删除。
5. 重叠或相交
  
  重叠面错误主要是由三角形顶点计算时舍入误差造成的，由于三角形的顶点在3D空间中以浮点数表示的，如果圆整误差范围较大，就会导致面片的重叠或者分离。
6. 错误边界
  
  在STL格式中，每一个三角面片与周围的三角面片都应该保持良好的连接。如果某个连接处出了问题，这个边界称为错误边界，并用黄线标示，一组错误边界构成错误轮廓。面片法向错误、缝隙、孔洞、重叠都会引发错误的边界，对不同位置的错误确定坏边原因，找到合适的修复方法。
注意：大多数的网格处理算法都是基于表面封闭且符合2-manifold特性的网格来设计的（可以暂时理解成网格表面封闭且光滑），甚至有些算法还需要多边形在网格上分布均匀。

3. 现有算法介绍

Untitled

目前网格修复算法分类：

基于点云或基于网格：
- 体数据修复（Volume-based methods）：先构建体数据（例如LDI，Octree，Uniform grid等），在体数据上修复完成后重建网格。
- 表面数据修复（Surface-based methods，网格修复）：直接在网格表面进行修补孔洞和其他缺陷。
神经网络/模式学习：
- 学习某些区域的特征来修复
- 利用同类或相似三维模型的局部相近区域进行拷贝修整

3.1. 基于点云

基于点云的方法是最先被研究的，其中确实有一些有价值的理论，可能对未来的研究者来说，对孔洞填充的研究有所启发。随着计算机图形学的快速发展，基于网格的方法得到了越来越多的关注，并在曲面重建中发挥了基础作用。尽管存在不同种类的网格，只有三角网格是最流行的重建表面的方法。所以2018年的综述只讨论了基于网格的方法。

3.2. 基于网格

体数据修复

The biggest difference between this method and others is that it guarantees the full preservation of the input mesh, Fig.10 confirms this point. The main strength of volume-based hole filling methods in meshes is that they are robust to resolve geometric defects and produce a manifold output mesh surface without self-intersections. The major weakness is that in the diffusion phase, geometric details are lost inevitably, even in the remainder areas far from the hole.
- VolFill2002[20]
  - Davis, J., Marschner, S. R., Garr, M., Levoy, M.: filling holes in complex surfaces using volumetric diffusion. In 3D Data Processing Visualization and Transmission. Proceedings. IEEE. First International Symposium on pp. 428-441.(2002)
  - 介绍了一种典型的修复技术，采用体积扩散程序来完成孔的表面。它的目的是针对那些详细的孔在几何上和拓扑上过于复杂而无法用一般的surface-based methods解决的情况。
- JuTao2004[21]
  - Ju T. Robust repair of polygonal models[J]. ACM Transactions on Graphics (TOG), 2004, 23(3): 888-895.
  - It partitions the space into disjoint internal and external volume using an octree grid to repair polygonal model surface by contouring. Though it guarantees a closed output model, it alters the input mesh which may lose sharp features and fine details of the models, as can be seen from the results in Fig.4, this approach alters the organization of the original input mesh obviously.
  - **PolyMender：**windows+非开源？需要登录wustl大学账号
- Guo2006[22]
  - Guo T Q, Li J J, Weng J G, et al. Filling holes in complex surfaces using oriented voxel diffusion[C]//2006 International Conference on Machine Learning and Cybernetics. IEEE, 2006: 4370-4375.
  - It introduces an oriented voxel global diffusion method to fill holes in complex surfaces. In particular, the diffusion direction of the oriented distance field is controlled accurately inward the hole to restore the sharp features of the incomplete input. While this algorithm is able to fix the incomplete surface smoothly and handle complex holes which contain islands, it consumes large quantity of memory to store these oriented volumetric units such that it lacks the ability to tackle large size input models.
- Ramesh2015[23]
  - Centin M, Pezzotti N, Signoroni A. Poisson-driven seamless completion of triangular meshes[J]. Computer Aided Geometric Design, 2015, 35: 42-55.
  - It employs a Poisson Reconstruction step to obtain an implicit function and then deploys an interpolation method to reconstruct missing parts of the input mesh. A fast and continuous surface-oracle computation exploited to efficiently guide the restricted Delaunay triangulation is one of the crucial elements to perform hole filling works.
  - windows系统，闭源：https://drive.google.com/file/d/1bbnwyYe550L3Un69ix-SdzCZvk-FfNDy/view
表面数据修复
- Liepa2003[24]
  - Liepa P. Filling holes in meshes[C]//Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing. 2003: 200-205.
  - It proposes a surface oriented method to smoothly fill holes such that the vertex densities around the holes are interpolated.
  - python（非官方？）：https://github.com/russelmann/hole-filling-liepa
- Jun2005[17]
  - Jun Y. A piecewise hole filling algorithm in reverse engineering[J]. Computer-aided design, 2005, 37(2): 263-270.
  - It splits a complex hole into several simple holes and fills each divided simple hole with planar triangulation method consecutively until the entire complex hole is closed.
- ReMESH2006
  - Attene M, Falcidieno B. Remesh: An interactive environment to edit and repair triangle meshes[C]//IEEE International Conference on Shape Modeling and Applications 2006 (SMI'06). IEEE, 2006: 41-41.
  - C++：https://github.com/huxingyi/autoremesher
- MeshFix2010[25]
  - M. Attene. A lightweight approach to repairing digitized polygon meshes. The Visual Computer, 2010. (c) Springer. DOI: 10.1007/s00371-010-0416-3
  - python源码：https://github.com/pyvista/pymeshfix
  - C++源码：https://github.com/MarcoAttene/MeshFix-V2.1
  - It concentrates on converting a low-quality digitized polygon mesh to a single manifold and watertight triangle mesh without degenerating or intersecting elements. It assumes that the resulting mesh should be a single connected manifold bounding a polyhedron and the sampling density should not vary significantly from one part of the mesh to another. Its inherited characteristics don’t guarantee that the filled surface will converge eventually, which is the main drawbacks of this method.
  - 主要模块：
    
    https://zhuanlan.zhihu.com/p/53269870
    - 拓扑重建（Topology reconstruction）：删除离群点，冗余小连通块，修补孔洞等。
    - 几何校正（Geommtry correction）：包括矫正退化元素（比如夹角近乎0或180度，长度近乎0的线段等等，但暂时都可以统一为近乎空面积或夹角过小的三角形），自交多边形，甚至是超过阈值的某个三角边长等。
- Qiang2010[18]
  - Qiang H, Shusheng Z, Xiaoliang B, et al. Hole filling based on local surface approximation[C]//2010 International Conference on Computer Application and System Modeling (ICCASM 2010). IEEE, 2010, 3: V3-242-V3-245.
  - It creates new triangles by the constraint Delaunay triangulation method to fill holes.
- Wei2010[26]
  - Wei M, Wu J, Pang M. An integrated approach to filling holes in meshes[C]//2010 International Conference on Artificial Intelligence and Computational Intelligence. IEEE, 2010, 3: 306-310.
  - It generates a minimal triangulation to the hole. In order to assort with the density of neighbor meshes, the new triangles are subdivided according to their edge length. The defect of the method is obvious for the filling results dependent heavily on the geometry of the hole neighbors.
- Harary2014[27]
  - Harary G, Tal A, Grinspun E. Context-based coherent surface completion[J]. ACM Transactions on Graphics (TOG), 2014, 33(1): 1-12.
  - It introduces a hole filling algorithm for a given triangle mesh to synthesize missing geometry by learning the knowledge of the similar geometry in the remainder mesh. Different from other context-based approaches, it completes the hole field coherently to the local neighborhood while maintaining a proper triangulation of the mesh surface.
- [28]和[29] has been used widely to deal with large scattered data sets. Without the requisite of prior knowledge of the object topology, the methods construct the implicit signed distance function constrained by the exterior points near the hole to approximate the surface and interpolate new points into hole regions
  - Branch2006[28]
    - Branch J, Prieto F, Boulanger P. Automatic hole-filling of triangular meshes using local radial basis function[C]//Third International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'06). IEEE, 2006: 727-734.
    - An implicit surface representation based on Radial Basis Functions(RBF).
  - Tekumalla2014[29]
    - Tekumalla L S, Cohen E. Reverse engineering point clouds to fit tensor product B-spline surfaces by blending local fits[J]. arXiv preprint arXiv:1411.5993, 2014.
    - An implicit surface representation based on Moving Least Squares. Functions(RBF)
- Dellepiane2009[30]
  - Dellepiane M, Venturi A, Scopigno R. Image guided reconstruction of un-sampled data: a coherent filling for uncomplete Cultural Heritage models[C]//2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops. IEEE, 2009: 939-946.
  - An image facilitates the hole filling process efficiently and precisely.
- Quinsat2015[31]
  - Quinsat Y. Filling holes in digitized point cloud using a morphing-based approach to preserve volume characteristics[J]. The International Journal of Advanced Manufacturing Technology, 2015, 81(1): 411-421.
  - It requires a priori knowledge of the input model and it mainly focuses on the hole filling problem of the CAD model, so this algorithm cannot be applied to other common inputs.
  - 这个需要通用性不强。
其他4个软件类工具
- Mesh Repairing Software on the Web：http://www.meshrepair.org/
- MeshLab：https://github.com/cnr-isti-vclab/meshlab
新的一些算法

关键词：
- site:thecvf.com mesh holes patching
- site:thecvf.com mesh filling holes
- Shi2021
  - Shi Y, Ni B, Liu J, et al. Geometric Granularity Aware Pixel-To-Mesh[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021: 13097-13106.
已知算法对比试验结果