摘 要： 针对三维点云数据重建效率低、不能实时交互等问题，利用鲁棒性强的Power Crust算法和三维可视化类库Visualization Toolkit(VTK)的良好并行机制与强大的图像处理能力，实现了三维点云数据曲面快速重建。该算法使用Power Crust对三维点云进行曲面重建，接着对得到的网格进行线性调整、简化和平滑，最后引入VTK进行渲染、绘制、显示，并实时交互。实验结果表明，该算法可以加快散乱点云数据的重建速度，较好地保持了点云数据的拓扑结构，提高了曲面重建的精确性和鲁棒性，且交互性强，适合实时处理。

0 引言

随着图像处理技术和激光扫描技术的发展，三维曲面重建技术作为一个重要研究内容广泛应用于逆向工程、模式识别、影视等领域中，并得到快速发展。三维曲面重建是采用三维点云数据快速、准确地构建出复杂的曲面模型。现有的重建算法主要分为两类：容积重建和表面重建[1]。容积重建在密集计算上耗费时间较长，不能够满足实时处理的需要。表面重建处理速度比较快，适合实时处理，主要包括轮廓线连接、等值面提取和Delaunay三角化。轮廓线连接是把相邻的横截面轮廓点连接起来，构建成一个三角网格，但在网格对应、拼接等问题上没有解决好。等值面提取[1]是取当前点的8个邻近点形成一个虚拟的多维数据集，确定一个多边形来代表等值面表面，但等值面涉及到复杂的法向一致性调整，相当耗时。Delaunay三角化(如Power Crust算法[2-4]、Crust算法)是构造一个四面体网格，网格片之间的轮廓点为顶点，重建的不足在于容易遗漏一些轮廓点，导致重建的准确性降低。

针对以上问题，本文提出了一种基于Power Crust的三维点云曲面重建算法，对三维点云数据进行滤波、去噪等预处理，调用Power Crust算法进行曲面重建，利用VTK的pipeline机制对曲面网格进行简化、平滑等处理，通过局部形状校正获得三维模型，显示并交互。实验结果表明，此算法运行速度快，重建曲面较为准确、光滑，图像质量高，适合实时处理。

1 三维可视化类库VTK

VTK[5-7]是美国Kitware公司利用C++语言开发的一套集3D图形学、图像处理和可视化于一体的C++类库。它是一个源码开发、可视化技术和图像处理软件系统，可在C++、Tcl/Tk、Jave、Pyhon语言环境下使用[8]。它融合了计算机图形学、图像处理和可视化三大技术，在可视化和图像处理方面有着绝对的优势，成为世界上研究图像可视化系统的热门工具。

构成VTK体系主要有2种对象模型：图形模型对象和可视化模型对象。图形模型的主要作用是用图形描述几何体构成的场景；可视化模型的主要作用是把几何数据转换成图形数据和负责构建几何体。VTK有着一套3D交互部件，采用流水线机制，支持并行处理，选择适当的算法并构建自己的可视化流程，读取数据、过滤、映射与渲染，最后将所成图像呈现在屏幕上，并能实现人机交互。

2 重建算法简介

准确性和效率性是三维点云曲面重建和可视化的两个关键因素。准确性要求保持拓扑结构和形状良好；效率性要求在保持原始拓扑结构的前提下降低重建时间。Power Crust算法在考虑采样的密度和表面细节基础上，采用一个贪婪的滤波过程来处理那些有噪声的散乱数据，逆向重建了曲面的三角网格，并有理论上的支持。

2.1 Power Crust算法原理

Power Crust 算法原理涉及的概念主要有：中心轴变换[9]、Voronoi 图、Delaunay三角化和Power图[10-11]。

中轴很好地表现了物体形状的特征及连接特性，对基于Voronoi的曲面重建算法有重要的意义,不仅是因为要利用它来定义采样密度,而且位于中轴上的点到表面采样点的向量构成了对该点表面法向量的一个很好的估计和预测。其误差与采样密度相关，很多基于Voronoi的算法都要利用该点来过滤三角片。

Voronoi图在解决点与其他几何对象的距离关系上作用很大。假设在给定平面或空间中，有n个散乱点，点集为P={p1，p2，…，pn}，定义：

其中，H(pi，pj)表示点集中的其他点到pi的距离比到pj的距离更近的轨迹，是一个半平面或者一个半空间；d(p，pi)表示p到pi的欧氏距离；V(pi)为点集中的其他点pj到点pi轨迹的总和。对于点集P中的每个点都有一个对应的Voronoi多边形，所有的多边形总和就称为点集P的Voronoi图。

Delaunay三角化和Voronoi图是对偶关系，具有最小角最大、空洞与局部重连等特性。Power图是Voronoi图的扩展，可视为生成元是Power圆的Voronoi图，只是其距离已不是欧氏距离而是Power距离：

已知d维空间的点集S，p∈S的权为wp(-∞<wp<+∞)，有：

其中，?仔p(x)称为x到p的Power距离。

Power图和其对偶的规则三角剖分是对应于加权点的Voronoi图和Delaunay三角剖分。

可以证明,从极点到表面采样点的向量是该采样点表面法向量的一个很好的近似。这个结论将为中轴的计算和基于Voronoi的曲面重建算法提供强有力的理论支持。

2.2 Power Crust算法实现

Power Crust算法先计算出采样点的中心轴，找出Voronoi顶点从而创建Voronoi图，然后进行Delaunay三角化，把经过三角剖分的原始点云连接成三角网格模型，经过Voronoi图过滤器过滤后，删除不符合要求的网格，最后得到所需要的网格。此算法可以生成一个不漏水的、密封的三维网格，同时还得到原始表面中轴的估计量，能进行含有噪声、有尖角、非封闭的点云数据的曲面重建。Power Crust算法的优势是在细节区域，输出的离散表面具有致密的点；在其他区域，输出的离散表面只有稀疏的点。 具体步骤如下：

(1)对采样点集S进行Delaunay 三角化，找到 Voronoi顶点，边界框上的顶点被认为是Power图上的采样点。

(2)确定哪些Voronoi顶点为极点。

(3)生成极点球集合Bp，计算出Power图。

(4)标记出每个极点是里面的或是外面的。

(5)给出三角化作为输出，并返回结果。

2.3 网格简化、平滑

经过Power Crust算法重建得到的曲面网格由很多多边形数据(主要是三角片)构成，通常包含噪声或者光洁度太差，绘制图形的质量较差，且不能够快速地绘制和处理，而交互的应用程序对于多边形数据的快速绘制有更高的要求。为了减少渲染时间和提高重建效率，本文在重建网格的基础上采用Decimation技术实现网格简化；使用平滑网格技术，通过调整点的位置来降低轮廓面的锯齿效应和分级效应，改善图形的质量。

VTK支持4种Decimation对象：vtkDecimate、vtkDecimatePro、vtkQuadricClustering、vtkQuardricDecimation。vtkDe-

cimatePro执行速度相对较快，并且在削减过程中能够修改拓扑结构，使用边折叠处理消除顶点和三角形，其错误度量方法使用基于到平面或边的距离方法，能够实现被要求的任意削减程度。在vtkDecimatePro中，有两个重要的变量：TargetReduction是被要求减少的三角形的数量；PreserveTopology被设置为是否允许改变拓扑结构。

VTK提供两种平滑过滤器：vtkSmoothPolyDataFilter、
vtkWindowedSincPolyDataFilter。vtkSmoothPolyDataFilter的平滑效果好、平滑速度较快。在vtkSmoothPolyDataFilter过滤器中，重要的变量是SetNumberOfIterations，即设置平滑迭代次数。

3 算法实现

VTK是可视化对象的集合，这些可视化对象可以连接起来形成一个可视化管道。这个管道开始输入数据源，经过一系列的滤波器过滤，最后显示出来[1]。

3.1 点云数据集

实验使用的数据来源于对现实动物猫的三维扫描，通过激光扫描仪扫描到的数据以三维坐标的形式存储在Txt文本中。Txt文本存储的点云数据是一个多行3列的矩阵，每行记录数据点的x、y、z 3个坐标值，保证数据的正确性；在保证完整性的基础上进行数据精简，提高运算速率。

3.2 实验过程

在Microsoft Visual C++平台中，对三维点云进行曲面重建和可视化，主要经过下面5个步骤：

(1)点云预处理。对三维点云数据进行去噪与滤波处理，由vtkPolyData和vtkPoint等VTK函数读入VTK的pipeline流水线中。

(2)调用Power Crust算法对点云进行曲面重建。对VTK流水线机制读入的点云数据，调用Power Crust算法进行顶点聚类、Delaunay三角化特性检测、三角化，得到初步的曲面网格。

(3)简化、平滑曲面网格。对重建后得到的网格，调用vtkDecimatePro、vtkSmoothPolyDataFilter等VTK函数进行简化和平滑处理，减少网格数量，缩短渲染时间和提高运算效率。

(4)渲染、绘制点云曲面。经过简化、平滑后的曲面网格，经过平面法向量估计、数据映射，建立演员类等处理，在VTK流水线机制上进行渲染、绘制。

(5)显示、交互。对得到的点云曲面图，在VTK中进行显示，并实现交互操作。整个三维点云曲面重建的框图如图1所示。

4 实验结果及分析

为了证明算法的有效性，选用兔子、猫、马3组三维点云数据来进行测试。图2(a)、(b)、(c)分别是兔子、猫、马三维点云显示图，图3(a)、(b)、(c)分别是兔子、猫、马三维点云数据调用Power Crust算法得到的重建效果图，图4(a)、(b)、(c)分别是兔子、猫、马三维点云调用本文算法得到的重建效果图。表1总结了两种方法对3组数据的重建结果。

通过以上几种点云数据重建曲面可以看出，使用Power Crust算法曲面重建效果比较粗糙，并带有很多突出和凹陷面;采用本文算法后的点云数据重建效果图表面平滑光顺，效果逼真，绘制速度快、效果好，能够很好地反映三维点云的立体效果，并能保留物体原有的一些细节，对比结果很明显。因此说明，把基于Voronoi 图和Delaunay三角化的Power Crust算法和VTK可视化类库结合起来是一个提高曲面重建效率的有效方法。

5 结语

本文分析了现有的曲面重建技术，在效率较高的基于Voronoi图和Delaunay三角剖分的Power Crust算法基础上，结合具有强大图形处理能力的可视化类库VTK，实现了三维点云曲面重建，并达到实时交互性能。Power Crust算法具有流程简单、重建结果精确等优点，对于没有法向量的大量散乱点云数据，处理速度非常快，但效果不是很准确。所以将经过去噪、滤波后的点云数据集，调用Power Crust算法进行曲面重建，输入具有强大图像处理能力的VTK进行简化、平滑处理，最终得到的重建结果比较逼真，鲁棒性强。这一方法有效提高了重建和可视化的效率，可以很方便地应用在各个需要获取物体近似表面模型的领域，具有很大的现实意义。相信在不久的将来，随着计算机技术的发展以及图像处理技术的深入研究，三维点云曲面重建将会拥有广泛的应用空间。

参考文献

[1] LI J，HUANG S，LI G，et al.Reconstruction and visualiza-tion of 3D surface model from serial-sectioned contourpoints[C].Image and Signal Processing(CISP)，2010 3rdInternational Congress on.IEEE，2010，5：2396-2400.

[2] AMENTA N，CHOI S，KOLLURI R K.The power crust，unions of balls，and the medial axis transform[J].Computa-tional Geometry，2001，19(2)：127-153.

[3] NI T，MA Z.A fast surface reconstruction algorithm for 3Dunorganized points[C].2010 2nd International Conference on

Computer Engineering and Technology，2010，7：15-18.

[4] LI H，MA X，LI J，et al.Research on model correction basedon scattered point cloud data surface reconstruction[C].Wireless Mobile and Computing(CCWMC 2011)，IET Inter-national Communication Conference on.IET，2011：97-101.

[5] WILLIAM J，SCHROEDER，LISA S，et al.The visualizationtoolkit user′s guide：updated for version 4.0[M].Kitware，

1998.

[6] 吕晓琪，李许峰，贾东征.基于可视化工具VTK的几何体构建技术[J].内蒙古科技大学学报，2012，31(2)：167-170.

[7] 肖何，何明耘，白忠建，等.基于VTK的电磁场三维可视化研究及实现[J].计算机应用，2008，27(11)：2773-2775.

[8] 刘伟宁.基于VTK的海底声纳数据实时三维建模软件设计[D].杭州：浙江大学，2010.

[9] AGANJ E，KERIVEN R，PONS J P.Photo-consistent sur-face reconstruction from noisy point clouds[C].Image Pro-cessing(ICIP)，2009 16th IEEE International Conference on，

IEEE，2009：505-508.

[10] 李云.不规则形体点云的三维重建研究[D].乌鲁木齐：新疆大学, 2013：22-32.

[11] 李海生.Delaunay三角剖分理论及可视化应用研究[M].哈尔滨：哈尔滨工业大学出版社，2010：12-22.