第四部分 点云重构与艺术风格化
第11章 点云曲面重建
基于点云数据重建出三角网格的过程，即利用点云数据携带的信息构建出原始曲面的几何模型的过程，称为点云曲面重建。在科学计算可视化（visualization in scientific computing，VISC）、计算机辅助几何设计（computer-aided geometric design，CAGD）、计算机图形学、逼近论等领域，为更好地研究被测对象，需要根据给定的点云模型进行曲面重建。点云曲面重建是很多研究领域中的关键步骤，如逆向工程、医学影像可视化，也是现代技术研究的热点。
曲面表达形式主要有隐函数表达形式、参数表达形式、网格表达形式和点云表达形式等几类。常见的基于点云的曲面重建方法相应地可以分为三类，分别是隐式曲面重建方法、参数曲面重建方法和网格曲面重建方法。本章主要阐述由点云表达形式到其他三种表达形式的转换方法。
11.1 点云曲面重建经典方法
Voronoi图是一种空间分割算法，其空间划分思想来源于笛卡儿的凸域分割空间理论。Voronoi图与 Delaunay三角剖分互为对偶，基于点之间的连接关系和规则形成的 Voronoi图与 Delaunay三角剖分的过程，实质是基于点云形成网格曲面重建的过程[1，2]。
接下来，介绍基于 Voronoi图和 Delaunay三角剖分的点云曲面重建的相关方法。
11.1.1 基于 Voronoi图的点云曲面重建
对于平面上任意两点 p、q，将二者之间的欧氏距离记为 dist( pq)，那么，可，将表示为
（11-1）
设为平面上任意 n个互异的点，这些点被称为基点。将平面划分为 n个单元（cell），且对于位于点 pi所对应的单元中的任一点 q，当且仅当对于任何的 ，都有，则称其为 P对应的 Voronoi ，图，记作 Vor(P)或 V(P)。
Voronoi图实际上是一种连续多边形，由一组邻点直线的垂直平分线连接形成，又称 Dirichlet图、泰森多边形，如图11-1所示。构建 Voronoi图的关键在于形成离散数据点的 Delaunay三角形，即对平面的一个子区域进行划分，将整个平面划分成若干个单元。
图11-1 Voronoi图的构建过程
1．Voronoi图的性质
（1）对偶特性。 Voronoi图与 Delaunay三角形互为对偶（三个 Voronoi顶点构成一个 Delaunay三角形）。
（2）*近邻特性。对于欧氏平面上一组互不相同的点，当且仅当其中两个点的 Voronoi图（其中的一个多边形区域）共享一条有限长度的边时，这两个点为近邻点。
（3）空圆特性。在 Voronoi图中选取任意结点 q，记 q所在的 Voronoi边对应的离散点集（3个或更多）为 S，并构建圆 C，若 C内不包含点集 S中的其他离散点，则圆 C称为空圆。其中，半径*大的空圆称为*大空圆。
（4）线性特性。 Voronoi图是含有 n个多边形以及三个及以上结点的平面图形。假设分别表示图中的生长点、Voronoi边与 Voronoi结n点的个数。由于每一条 Voronoi边存在两个结点，而每个结点至少属于三条边，那么有2ne ≥3nv 。运用欧拉规则可得，这说明 Voronoi图随着生长点的个数 n呈线性增长。
2．与 Voronoi图相关的概念
中轴：一个对象的中轴是一个离散点集，这个点集中至少有两个距离该三维对象边界*近的点，该点集构成的线条称为中轴，即拓扑骨架，如图11-2所示。
局部特征尺寸：给定一个光滑流形 M（有关流形的概念参阅文献[3]），M上任意一点的局部特征尺寸指该点和 M的中轴之间的距离，如图11-3所示。
图11-2 中轴
图11-3 局部特征尺寸
采样：在曲面 S上对各点采样密度*大为这些点的局部特征尺寸的.倍的一种非均匀密度采样方法。采样的相关方法如下：
（1）如果点集 P是对曲面的.-采样，记为 VP，且.满足式（11-2）所示条件，则具有闭球属性。
（11-2）
（2）如果点集 P是对曲面 S的.-采样，P对应的 Voronoi图 V(P)的极点随着.接近于0而收敛于曲面 S的中轴。
（3）如果点集 P是对曲面 S的.-采样，对点集 P中的任意点 p，令 P+代表点 p的 Voronoi图原胞的极点，那么曲面 S在 p点处的法矢与向量的夹角不超过。
3．Voronoi图的生成方法
关于平面点集的 Voronoi图生成方法，代表性的方法主要分为两类[1]：①直接法，如增量法、分治法、半平面法和扫描线法等；②间接法，即利用 Voronoi图的对偶性，先生成 Delaunay三角形，然后构造 Voronoi图，有换边法和升维法等。
下面以增量法为例，介绍 Voronoi图的生成过程。
假定在二维空间中有 n个生长点，这 n个生长点按某种方式排序，如从 p1到 pn或者从 pn到 p1。设 vm表示前 m个生长点的 Voronoi图。从 v3开始，每增加一个生长点 pm( m≤n)，对vm1进行局部重新剖分，得到 vm。由vm.1扩展至 vm的过程中，主要包括两个步骤（图.11-4）。
（1）搜索邻近元。从对应的生长点中寻找与新增生长点 pm*近的生长点 pm(m)。
（2）局部更新。作线段 pmpm(m)的垂直平分线，寻找垂直平分线与 Voronoi多边形vm.1[ pm(m)]的交点，并确定与其邻近的 Voronoi多边形。然后，作边 pmpm1(m)的垂直平分线，并找出其与 Voronoi多边形的另一个交点和邻近的多边形vm.1[ pm2(m)]。重复此过程，可以获得 pm的 Voronoi多边形 vm。
图11-4 Voronoi图的生成过程（以增量法为例）
有关 Voronoi图的详细内容，可参阅文献[1]。
4．基于 Voronoi图的三角网格曲面重建
下面介绍基于 Voronoi 图的三角网格曲面重建的常见方法，典型的有 Crust方法和 Cocone方法等。
1）Crust方法 Crust方法可以在二维平面上进行曲线重建或在三维空间进行曲面重建[4，5]。 Crust二维算法在二维平面上进行曲线重建过程如下：首先计算光滑曲线 F的离散采样点集 S的 Voronoi图，令代表 Voronoi图的顶点，对 SV进行 Delaunay三角剖分， Crust由点集 S中的点形成的边组成，这些边均为 Delaunay三角形边且对采样点集 S和 Voronoi图顶点 V满足空圆特性。其中， Voronoi图顶点 V起过滤作用。
Crust方法需要保证重建曲线在拓扑结构上与原采样曲线一致，在采样密度满足.-采样的前提下，所得曲线与原采样曲线微分同胚。 Crust 方法对二维曲线重建示例如图11-5所示。
图11-5 Crust方法对二维曲线重建示例在三维空间上拓展 Crust二维算法，得到 Crust三维算法。但是， Voronoi图
展开
