参考：https://mp.weixin.qq.com/s/FfHkVY-lmlOSf4jKoZqjEA

什么是网格

网格主要用于计算机图形学中，有三角、四角网格等很多种。
计算机图形学中的网格处理绝大部分都是基于三角网格的，三角网格在图形学和三维建模中使用的非常广泛，用来模拟复杂物体的表面，如建筑、车辆、动物等，你看下图中的兔子、球等模型都是基于三角网格的

三角形表示网格也叫三角剖分。它有如下几个优点：

• 三角网格稳定性强。

• 三角网格比较简单（主要原因），实际上三角网格是最简单的网格类型之一，可以非常方便并且快速生成，在非结构化网格中最常见。而且相对于一般多边形网格，许多操作对三角网格更容易。

3、有助于恢复模型的表面细节。

网格生成算法要求

网格生成算法有如下的能力：

• 对点云噪声有一定的冗余度。

• 能够重建出曲率变化比较大的曲面。

• 能够处理大数据量，算法时间和空间复杂度不会太高。

• 重建出的网格中包含尽可能少的异常三角片，比如三角片交错在一起、表面法向量不连续或不一致、同一个位置附近出现多层三角片等。

目前点云进行网格生成一般分为两大类方法：

• 插值法。顾名思义，也就是重建的曲面都是通过原始的数据点得到的

• 逼近法。用分片线性曲面或其他曲面来逼近原始数据点，得到的重建曲面是原始点集的一个逼近。

点云贪心三角化原理

主要介绍一种比较简单的贪心三角化法（对应的类名：pcl::GreedyProjectionTriangulation），也就是使用贪心投影三角化算法对有向点云进行三角化。
优点：可以用来处理来自一个或者多个设备扫描到得到、并且有多个连接处的散乱点云。但是也是有很大的局限性，它更适用于采样点云来自表面连续光滑的曲面，并且点云的密度变化比较均匀的情况

贪心投影三角化的大致流程是这样的：

• 先将点云通过法线投影到某一二维坐标平面内

• 然后对投影得到的点云做平面内的三角化，从而得到各点的拓扑连接关系。平面三角化的过程中用到了基于Delaunay三角剖分 的空间区域增长算法

• 最后根据平面内投影点的拓扑连接关系确定各原始三维点间的拓扑连接，所得三角网格即为重建得到的曲面模型

Delaunay 三角剖分简介

对数值分析以及图形学来说，三角剖分（Triangulation）都是极为重要的一项预处理技术。而Delaunay 三角剖分是一种常用的三角剖分的方法，关于点集的很多种几何图都和Delaunay三角剖分相关，如Voronoi图。

Delaunay 三角剖分的有两个优点：

• 最大化最小角，“最接近于规则化的“的三角网。

• 唯一性（任意四点不能共圆）

定义：点集?的Delaunay三角剖分满足满足任意?内任意一个点都不在? 内任意一 个三角面片的外接圆内。

看下面的图就是满足了Delaunay条件，所有三角形的顶点是不是都不在其他三角形的外接圆内？

更简便的方法。你看下面最左图，观察具有公共边缘BD的两个三角形ABD和BCD，如果角度α和γ之和小于或等于180°，则三角形满足Delaunay条件。按照这个标准下图左、中都不满足Delaunay条件，只有右图满足。

贪心投影三角化

// 将点云位姿、颜色、法线信息连接到一起
pcl::PointCloud<pcl::PointNormal>::Ptr cloud_with_normals(new pcl::PointCloud<pcl::PointNormal>);
pcl::concatenateFields(*cloud_smoothed, *normals, *cloud_with_normals);

//定义搜索树对象
pcl::search::KdTree<pcl::PointNormal>::Ptr tree2(new pcl::search::KdTree<pcl::PointNormal>);
tree2->setInputCloud(cloud_with_normals);

// 三角化
pcl::GreedyProjectionTriangulation<pcl::PointNormal> gp3;   // 定义三角化对象
pcl::PolygonMesh triangles; //存储最终三角化的网络模型

// 设置三角化参数
gp3.setSearchRadius(0.1);  //设置搜索时的半径，也就是KNN的球半径
gp3.setMu (2.5);  //设置样本点搜索其近邻点的最远距离为2.5倍（典型值2.5-3），这样使得算法自适应点云密度的变化
gp3.setMaximumNearestNeighbors (100);    //设置样本点最多可搜索的邻域个数，典型值是50-100

gp3.setMinimumAngle(M_PI/18); // 设置三角化后得到的三角形内角的最小的角度为10°
gp3.setMaximumAngle(2*M_PI/3); // 设置三角化后得到的三角形内角的最大角度为120°

gp3.setMaximumSurfaceAngle(M_PI/4); // 设置某点法线方向偏离样本点法线的最大角度45°，如果超过，连接时不考虑该点
gp3.setNormalConsistency(false);  //设置该参数为true保证法线朝向一致，设置为false的话不会进行法线一致性检查

gp3.setInputCloud (cloud_with_normals);     //设置输入点云为有向点云
gp3.setSearchMethod (tree2);   //设置搜索方式
gp3.reconstruct (triangles);  //重建提取三角化

实践

操作步骤：下采样和滤波、重采样平滑、法线计算，贪心投影网格化

#include <pcl/point_types.h>
#include <pcl/io/io.h>
#include <pcl/io/pcd_io.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/filters/radius_outlier_removal.h>
#include <pcl/filters/voxel_grid.h>
#include <pcl/filters/statistical_outlier_removal.h>
#include <pcl/surface/mls.h>
#include <pcl/features/normal_3d.h>
#include <pcl/surface/gp3.h>
#include <pcl/surface/poisson.h>
typedef pcl::PointXYZ PointT;

int main(int argc, char** argv)
{

	// Load input file
	pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);
    pcl::PointCloud<PointT>::Ptr cloud_downSampled(new pcl::PointCloud<PointT>);
	pcl::PointCloud<PointT>::Ptr cloud_filtered(new pcl::PointCloud<PointT>);
	pcl::PointCloud<PointT>::Ptr cloud_smoothed(new pcl::PointCloud<PointT>);
	if (pcl::io::loadPCDFile("/home/xiaohu/learn_SLAM/zuoye15/作业15-点云平滑及法线估计及显示/data/fusedCloud.pcd", *cloud) == -1)
    {
        cout << "点云数据读取失败！" << endl;
    }

    std::cout << "Orginal points number: " << cloud->points.size() << std::endl;

   	// ----------------------开始你的代码--------------------------//
	// 请参考之前文章中点云下采样，滤波、平滑等内容，以及PCL官网实现以下功能。代码不难。
	
	// 下采样
    pcl::VoxelGrid<PointT> downSampled;  //创建滤波对象
    downSampled.setInputCloud (cloud);            //设置需要过滤的点云给滤波对象
    downSampled.setLeafSize (0.01f, 0.01f, 0.01f);  //设置滤波时创建的体素体积为1cm的立方体
    downSampled.filter (*cloud_downSampled);           //执行滤波处理，存储输出
    pcl::io::savePCDFile ("/home/xiaohu/learn_SLAM/zuoye15/作业15-点云平滑及法线估计及显示/data/downsampledPC.pcd", *cloud_downSampled);

	// 统计滤波
    pcl::StatisticalOutlierRemoval<PointT> statisOutlierRemoval;       //创建滤波器对象
    statisOutlierRemoval.setInputCloud (cloud_downSampled);            //设置待滤波的点云
    statisOutlierRemoval.setMeanK (50);                                //设置在进行统计时考虑查询点临近点数
    statisOutlierRemoval.setStddevMulThresh (3.0);                     //设置判断是否为离群点的阀值:均值+1.0*标准差
    statisOutlierRemoval.filter (*cloud_filtered);                     //滤波结果存储到cloud_filtered
    pcl::io::savePCDFile ("/home/xiaohu/learn_SLAM/zuoye15/作业15-点云平滑及法线估计及显示/data/filteredPC.pcd", *cloud_filtered);

	// 对点云重采样  
    pcl::search::KdTree<PointT>::Ptr treeSampling (new pcl::search::KdTree<PointT>);// 创建用于最近邻搜索的KD-Tree
    pcl::PointCloud<PointT> mls_point;    //输出MLS
    pcl::MovingLeastSquares<PointT,PointT> mls; // 定义最小二乘实现的对象mls
    mls.setComputeNormals(false);  //设置在最小二乘计算中是否需要存储计算的法线
    mls.setInputCloud(cloud_filtered);         //设置待处理点云
    mls.setPolynomialOrder(2);            // 拟合2阶多项式拟合
    mls.setPolynomialFit(false);     // 设置为false可以 加速 smooth
    mls.setSearchMethod(treeSampling);         // 设置KD-Tree作为搜索方法
    mls.setSearchRadius(0.05);           // 单位m.设置用于拟合的K近邻半径
    mls.process(mls_point);                 //输出
    // 输出重采样结果
    cloud_smoothed = mls_point.makeShared();
    std::cout<<"cloud_smoothed: "<<cloud_smoothed->size() <<std::endl;
    //save cloud_smoothed
    pcl::io::savePCDFileASCII("/home/xiaohu/learn_SLAM/zuoye15/作业15-点云平滑及法线估计及显示/data/cloud_smoothed.pcd",*cloud_smoothed);

    // 法线估计
    pcl::NormalEstimation<PointT,pcl::Normal> normalEstimation;             //创建法线估计的对象
    normalEstimation.setInputCloud(cloud_smoothed);                         //输入点云
    pcl::search::KdTree<PointT>::Ptr tree(new pcl::search::KdTree<PointT>);// 创建用于最近邻搜索的KD-Tree
    normalEstimation.setSearchMethod(tree);
    pcl::PointCloud<pcl::Normal>::Ptr normals(new pcl::PointCloud<pcl::Normal>); // 定义输出的点云法线
    // K近邻确定方法，使用k个最近点，或者确定一个以r为半径的圆内的点集来确定都可以，两者选1即可
    normalEstimation.setKSearch(10);// 使用当前点周围最近的10个点
    //normalEstimation.setRadiusSearch(0.03);            //对于每一个点都用半径为3cm的近邻搜索方式
    normalEstimation.compute(*normals);               //计算法线
    // 输出法线
    std::cout<<"normals: "<<normals->size()<<", "<<"normals fields: "<<pcl::getFieldsList(*normals)<<std::endl;
    pcl::io::savePCDFileASCII("/home/xiaohu/learn_SLAM/zuoye15/作业15-点云平滑及法线估计及显示/data/normals.pcd",*normals);
	
	// 将点云位姿、颜色、法线信息连接到一起
    pcl::PointCloud<pcl::PointNormal>::Ptr cloud_with_normals(new pcl::PointCloud<pcl::PointNormal>);
    pcl::concatenateFields(*cloud_smoothed, *normals, *cloud_with_normals);
    pcl::io::savePCDFileASCII("/home/xiaohu/learn_SLAM/zuoye15/作业15-点云平滑及法线估计及显示/data/cloud_with_normals.pcd",*cloud_with_normals);
	
	// 贪心投影三角化
    //定义搜索树对象
    pcl::search::KdTree<pcl::PointNormal>::Ptr tree2(new pcl::search::KdTree<pcl::PointNormal>);
    tree2->setInputCloud(cloud_with_normals);

    // 三角化
    pcl::GreedyProjectionTriangulation<pcl::PointNormal> gp3;   // 定义三角化对象
    pcl::PolygonMesh triangles; //存储最终三角化的网络模型

    // 设置三角化参数
    gp3.setSearchRadius(0.1);  //设置搜索时的半径，也就是KNN的球半径
    gp3.setMu (2.5);  //设置样本点搜索其近邻点的最远距离为2.5倍（典型值2.5-3），这样使得算法自适应点云密度的变化
    gp3.setMaximumNearestNeighbors (100);    //设置样本点最多可搜索的邻域个数，典型值是50-100

    gp3.setMinimumAngle(M_PI/18); // 设置三角化后得到的三角形内角的最小的角度为10°
    gp3.setMaximumAngle(2*M_PI/3); // 设置三角化后得到的三角形内角的最大角度为120°

    gp3.setMaximumSurfaceAngle(M_PI/4); // 设置某点法线方向偏离样本点法线的最大角度45°，如果超过，连接时不考虑该点
    gp3.setNormalConsistency(false);  //设置该参数为true保证法线朝向一致，设置为false的话不会进行法线一致性检查

    gp3.setInputCloud (cloud_with_normals);     //设置输入点云为有向点云
    gp3.setSearchMethod (tree2);   //设置搜索方式
    gp3.reconstruct (triangles);  //重建提取三角化

    // 显示网格化结果
    boost::shared_ptr<pcl::visualization::PCLVisualizer> viewer(new pcl::visualization::PCLVisualizer("3D Viewer"));
    viewer->setBackgroundColor(0, 0, 0);  //
    viewer->addPolygonMesh(triangles, "wangge");  //
    while (!viewer->wasStopped())
    {
    	viewer->spinOnce(100);
    	boost::this_thread::sleep(boost::posix_time::microseconds(100000));
    }
    return 1;
}