1、背景

点云数据只是一种基本的、对物理目标三维结构的理解形式，一般无法直接使用。从点云重建网格模型的关键是从离散点构造出拓扑连接关系。

对于点云来说，法线是很重要的一个属性。

• 点云渲染：在进行光照渲染时需要发现信息才能正常进行。
• 点云重建：用于计算点到隐式曲面的有符号几何距离，从而构建隐式曲面。
• 其他：区分正反面。

2、法线计算原理

确定表面一点法线的问题近似于估计表面的一个相切面法线的问题，因此转换过来以后就变成一个最小二乘法平面拟合估计问题。

对一个平面来说，可以使用法线方式表示一个平面，$ax+by+cz=d(d>=0),a^2+b^2+c^2=1$。为了使得平面最准确，则使用最小二乘法构造代价函数：

$d_i=|ax+by+cz-d|$

则目标是求$min{\sum }_{i=1}^n{d}_i^2$,$a^2+b^2+c^2=1$

• 构造拉格朗日：

$f={\sum }_{i=1}^n{d}_i^2-\lambda (a^2+b^2+c^2-1)$

f对d求导则，
$d=\frac{1}{n}(a{\sum }_{i=1}^n{x}_i+b{\sum }_{i=1}^n{y}_i+c{\sum }_{i=1}^n{z}_i)=a\overline{x}+b\overline{y}+c\overline{z}$

$d_i=|a{x}_i+b{y}_i+c{z}_i-a\overline{x}+b\overline{y}+c\overline{z}|=|a\Delta x_i+b\Delta b_i+c\Delta z_i|$

令$\Delta x_i=x_i-\bar{x},\Delta y_i=y_i-\bar{y},\Delta z_i=z_i-\bar{z}$则$d_i=|a\Delta x_i+b\Delta b_i+c\Delta z_i|$

• 另一边，f分别对a、b、c求导：

$\frac{\partial f}{\partial a}=2{\sum }_{i=1}^n(a\Delta x_i+b\Delta b_i+c\Delta z_i)\Delta x_i-2\lambda a$

$\frac{\partial f}{\partial b}=2{\sum }_{i=1}^n(a\Delta x_i+b\Delta b_i+c\Delta z_i)\Delta y_i-2\lambda b$

$\frac{\partial f}{\partial c}=2{\sum }_{i=1}^n(a\Delta x_i+b\Delta b_i+c\Delta z_i)\Delta z_i-2\lambda c$

则
$$\left[\begin{array}{ccc}\sum \Delta x_i^2& \sum \Delta x_i\Delta y_i& \sum \Delta x_i\Delta z_i\\ \sum \Delta x_i\Delta y_i& \sum \Delta y_i^2& \sum \Delta y_i\Delta z_i\\ \sum \Delta x_i\Delta z_i& \sum \Delta y_i\Delta z_i& \sum \Delta z_i^2\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\end{array}\right]=\lambda \left[\begin{array}{c}a\\ b\\ c\end{array}\right]$$
则需要求的$(a,b,c)$即为$\lambda$特征值对应的特征向量。

对于上面左右同时乘$\left[\begin{array}{ccc}a& b& c\end{array}\right]$，即 $\lambda ={\sum }_{i=1}^n(a\Delta x_i+b\Delta b_i+c\Delta z_i{)}^2={\sum }_{i=1}^n{d}_i^2$.
则我们的目标就是求最小特征值对应的特征向量。

3、pcl库计算法向量

	pcl::NormalEstimation<pcl::PointXYZ, pcl::Normal> n;//创建法向估计对象
	pcl::PointCloud<pcl::Normal>::Ptr normals(new pcl::PointCloud<pcl::Normal>);//创建法向数据指针
	pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>);//创建kdtree用于法向计算时近邻搜索
	tree->setInputCloud(cloud);//为kdtree输入点云
	n.setInputCloud(cloud);//为法向估计对象输入点云
	n.setSearchMethod(tree);//设置法向估计时采用的搜索方式为kdtree
	n.setKSearch(20);//设置法向估计时,k近邻搜索的点数
	n.compute(*normals);  //进行法向估计