三角网格曲面建模算法优化方案

在曲面重建领域，三角网格曲面重建方法正成为研究的一大热点。其中Crust算法、零集法、α-shape法是扫描点云三角网格曲面重建的几种主流算法。

（1）Crust算法

该算法是基于计算几何中Voronoi图和Delaunay三角剖分对离散点云进行曲面重建，输出的离散曲面在细节区域具有密集点，而在无特征区域具有稀疏点。其定义为：

设S是一个点集，V是S的Voronoi顶点集，S′＝S∪V，若S′的Delaunay三角剖分的一条边的两个赚点属于S，则该边也属于Crust。

（2）零集法

Hoppe等人通过定义每个取样点的近似切平面，然后把到点的最近切平面的有符号距离作为距离函数，对这个距离函数进行插值，再通过Marching Cube算法生成多边形网格。

首先，取采样点领域内的k个点，求近似切平面的中心。用这k个点构造协方差矩阵，计算特征值，采用类似于深度优先搜索树的方法计算出切平面的法向量。

其次，定义有符号的距离函数f（p）＝disti（p）＝（p－oi）＊ni。(www.xing528.com)

再次，进行边界追踪，从一个标量函数提取同种曲面。

最后，设定能量函数，去除不需要的点，或者增加点、移动点的位置，改变网格的连接关系，达到能量函数的最小值，最终生成简洁、精确的网格曲面表达式。

（3）α-shape法

α-shape法先对点集进行Delaunay三角划分，然后对所有边、三角形、四面体等单纯形进行检测，当它的外接球内部不包含其他取样点，并且外接球的半径小于或等于α时，那么这个单纯形属于α-shape。在一个α-shape中，细节的水平由参数α控制。

当取样点密度均匀时，α值是全局唯一；而当取样点密度不均匀时，α值无法保证唯一，必须对α-shape规则进行改进。通过估算采样点的局部密度特性，计算点的局部法向量，构造度量张量，使点之间的距离变大，删除那些连接高密度区域和低密度区域的三角形。

形成的α-shape把空间分成了两个部分，一是α shape中的三角形、四面体等所占的空间，二是除α-shape之外的外集。外集和α-shape的交集叫作α-shape的外壳，在外壳上出现的三角形面叫作外部面，其余的面叫作内部面。依次检测面和边，确定外部面和内部面，外部面保留，内部面删除，直到所有的面都是外部面，即完成三角形网格曲面构造。