2023年6月30日发(作者：)

CGAL,VTK,MeshLab,Gts开源库⽹格算法⽐较 最近在学习⽹格算法，本⼈关⼼的主要是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形状，3DAlpha形状）　　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 libraryMeshLab官⽅介绍：　　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等，有机会再学习介绍。