对于Mesh，我们通常分为结构化网格和非结构化网格。理解很简单，除了四边形和六面体是结构化网格，其它都是非结构化网格

最近在学习网格算法，本人关心的主要是3D网格相关的算法，总结了一下主要包括：网格生成，网格平滑，网格参数化，网格重新剖分，网格简化，网格修复，网格变形，其他算法（细分，布尔操作，偏置，抽壳，雕刻，曲面切割）等。

从开源的算法库入手，分别用了CGAL，VTK，MeshLab，GTS四个开源库的算法功能，先小小的做个总结。

CGAL，The Computational Geometry Algorithms Library（计算几何算法库）

官方的介绍：

CGAL是高效、可靠的C++几何算法库。CGAL可用于多个需要几何计算的领域，例如地理信息系统（GIS），计算机辅助设计（CAD），分子生物学，医学影像，计算机图形学和机器人学。

该算法库提供几何相关的数据结构和算法，例如三角网格化，Voronoi图，多边形和多面体的布尔运算，点集处理，曲面整理，曲面网格和体积网格生成，几何处理，Alpha形状，凸壳算法，KD树等。

在CGAL4.9的手册里面可以了解到，CGAL包含：

算数和代数计算

组合算法（矩阵的单调排序，线性和二次方程求解）

几何内核（2D，3D和dD）

凸壳算法（2D，3D和dD）

多边形（2D多边形，2D多边形布尔操作，2D多边形分解，二维多边形Minkowski和，2D线段简化，2D可视化计算）

复合单元和多面体（3D多面体面，半边数据结构，曲面网格，复合映射，线性复合单元，多面体3D布尔操作，多面体凸壳分解，多面体3DMinkowski和）

曲线整理（2D整理，2D曲线交点，2D快速近似，2D包络线，3D包络面）

三角剖分和Delaunay剖分（2D剖分，2D剖分数据结构，2D周期剖分，3D剖分，3D剖分数据结构，ND剖分，2D Alpha形状，3D Alpha形状）

Voronoi图（2D分割Delaunay图，L无限分割Delaunay图，2D Apollonius图，2DVoronoi图适配器）

网格生成（2D整合剖分和网格，3D曲面网格生成，3D表面曲面网格化，3D网格生成）

形状重建（泊松曲面重建，尺度空间曲面重建，高级点集曲面重建，优化传输曲面重建）

几何处理（多边形网格处理，3D曲面细分方法，三角化曲面网格分割，三角化曲面网格简化，三角化曲面网格变形，三角化曲面网格参数化，三角化曲面网格最短路径，三角化曲面网格骨架，三角化曲面网格的脊和中心，采样点曲面的局部微分特性的估计，点集的处理，点集形状检测，2D流线分布）

空间搜索和排序（2D最近邻搜索，区间空间隔列表，dD空间搜索，dD分割树，dD同向盒的相交序列，3D快速相交和距离计算，空间排序）

几何优化（体积包围盒，内切区域，优化距离，PCA）

插值（2D曲面函数插值，广义质心坐标）

运动数据结构（运动数据结构，运动框架）

支持库（STL扩展，Boost图形库，求解器（Solvers），Boost属性映射，Cone-Based Spanners,Handles and Circulators，几何对象生成器，分析工具和hash映射，IO流）

可视化（Geomview，Qt图形可视化框架，CGAL Ipelets）。

从CGAL官方手册提供的功能可以看出，CGAL能够提供网格生成，网格剖分，网格简化，网格变形，网格布尔运算，网格曲面参数化的功能，但是缺少网格修复的功能（可能有，但是本人没有发现）。

GTS，the GNU Triangulated Surface Library（GNU三角网格化曲面库）

官方介绍：

GTS表示the GNU Triangulated Surface Library，它提供一系列开源、有用的函数，用于处理包含连接三角面片的3D曲面网格。

它的代码是基于面向对象的方法用C实现的。需要注意的是，GTS最初的目的是为科研人员提供简单高效的处理3D曲面网格的函数库。

该算法库的主要特点：

简单的面向对象的数据结构，快速获取拓扑特性

2D动态Delaunay剖分和约束Delaunay剖分

稳定的几何预测用于快速自适应浮点计算

稳定的曲面布尔操作

曲面修复和简化

基于视角的动态连续LOD

基于视角LOD的预处理

包围盒树和KD树，用于高效点的定位和交点检测

图操作：图的遍历和分解

矩阵计算

快速生成三角面

从官方提供的信息可以看出，GTS能够提供网格简化，三角面片剖分，3D曲面网格的布尔运算，网格修复的处理，但是功能都相对较为简单，不能处理复杂的网格和体数据网格。

另外需要注意的是，GTS是为GNU开发的，基本数据结构是基于Glib，这就使得在windows平台下编译和使用非常困难，所以不推荐使用。

VTK，Visualization toolkit（可视化工具）

官方介绍：

VTK是开源免费的软件系统，可用于3D计算机图形学，图像处理和可视化。VTK包含C++类库和一些集成接口层，如Tcl/Tk，Java和Python。VTK支持标量，矢量，纹理和体数据的可视化算法，也提供一些高级模型算法，例如隐式函数建模，多边形消减，网格平滑，裁剪，轮廓提取，Delaunay剖分等。VTK包含一个广泛信息可视化框架和一系列3D交互工具。VTK支持并行处理和多种GUI工具数据的集成，如Qt和tk。VTK具有跨平台特性。

VTK官方提供了丰富的文档和丰富的例子教程。VTK虽然是3D可视化工具，但是提供了大量图像和网格处理算法，易于使用。但是个人感觉VTK存在的问题是效率太低，为了满足跨平台特性和易用性，VTK选择的数据结构包含几乎所有的数据信息，导致计算效率较低。并且，VTK提供的算法大部分是传统通用的算法，没有进行效率上的优化，能够实现功能，但是效率是问题。另外，由于历史的问题，VTK的可视化一直只支持OpengGL1.2左右的版本，在VTK7.0之后才逐渐升级到OpenGL2.0，这对于OpenGL已经发布到4.5且停止更新的前提下，VTK的渲染效率也存在一些问题。为了满足管线框架，VTK的源代码比较难懂，对于新手来说，很难进行扩展，所以使用要慎重（个人意见）。

MeshLab/VCG library

MeshLab官方介绍：

MeshLab是一个开源，易用和扩展的系统，可用于处理和编辑非结构化3D三角面片网格。

该系统的主要目的是处理一般3D扫描的生成的非简单非结构化模型。该系统提供了网格编辑，清除，检查，诊断，渲染和转换工具。

该系统基于VCG算法库，VCG算法库是ISTI-CNR的可视化计算实验室开发，可处理所有网格处理核心任务。MeshLab系统开始于2005年，最初是由比萨大学计算机科学系FGT课程中一些动手能力强的学生自愿开发的，第一版的代码量约为15k行。在接下来的几年中，FGT的学生继续完善这个工作，并提供了越来越多的功能特性。

特点：

交互拾取和删除网格的任意部分，包括较大的网格模型。

网格的绘制交互拾取，平滑和上色

多种输入输出格式；第一个支持U3D格式的开源工具

网格清除：

删除重复顶点，未引用顶点，空面片

删除小的孤立组件

调整法矢不一致和法矢翻转

清除非流形面片

自动填补孔洞

重新剖分：

高质量边界的塌陷简化（包括纹理坐标限制的情况）

点集的网格重建（MC和泊松重建）

曲面细分（loop和bufferfly）

特征保持的平滑和光顺

手动填补孔洞

着色和检测：

高斯和均值曲线

扩展边界，测地线距离

非流形边和非流形顶点

自相交面片

环境光遮蔽

交互式网格画刷：画刷颜色；画刷选择；平滑

测量工具：显示网格上点之间的线性测量。

切片工具：导出SVG格式的平面切片

3D扫描工具：

基于ICP的范围映射校正工具，将网格变换到相同的索引空间

融合多个泊松重建的网格

基于渲染的OpenGL Shader

高质量的超大渲染打印（16K x 16K）

可扩展插件架构，可以简答快速添加新的处理，着色和输入输入格式的功能。

VCG Library官方介绍：
　　VCG是The Visualization and Computer Graphics Library的缩写，是一个开源易用的C++模板库，用于三角网格和四边形网格的操作，处理和显示。

该算法库包含超过100K行代码，基于GPL协议， 该算法库是意大利国家研究委员会中可视化计算实验室多款工具软件的基础算法，例如metro和MeshLab.

VCG算法库专注于三角网格处理功能：提供广泛且最先进的网格处理功能。例如：

高质量网格简化功能用于处理面片错误和边界塌陷

高效的空间数组结构（均匀网格，hash网格，kd树）

高级网格平滑和光顺算法

曲面计算

纹理坐标优化

Hausdorff距离计算

测地线路径

网格修复能力

等值面提取和高级网格重建算法

泊松圆盘采样和其他点的采样工具

曲面细分

从官方提供的文档可以看出，MeshLab软件依赖于VCG算法库，VCG算法库提供网格检测，网格修复功能，这是CGAL所不具备的功能。另外作为完整的软件,MeshLab提供完成的可视化和交互功能，提供多种OpenGL Shader，还提供了用于快速开发的插件框架，这是其他网格处理工具所不具备的功能，也是MeshLab所独有的优势。

综上所述，要实现原定的功能，没有一个现有的开源算法库能够满足所有的功能，还是需要了解不同的算法库，了解基本原理才是关键。

另外，本次只是比较了现有的4个开源算法库，现有的开源算法库还有OpenMesh，PCL等，有机会再学习介绍。