【作者】 钱归平；

【导师】 童若锋；

【作者基本信息】 浙江大学 ， 计算机科学与技术， 2008， 博士

【摘要】 在计算机图形学邻域里,点云的三维曲面重建一直是一个相当令人关注的研究课题,在科学计算可视化、CAD/CAM、动画和游戏中具有广泛的应用。本文对点云曲面网格重建和网格修补方法进行了深入分析与研究总结,结合二次多项式隐式曲面拟合和三角形网格化这两种主要方法,重点研究了点云的降噪和自适应网格化,及其保持尖锐特征的网格修补。全文主要内容如下:第一部分,指出点云网格重建的研究意义,总结归纳了点云网格重建技术方法和研究现状,并给出本文的主要创新点和章节安排。第二部分,针对点绘制方法中移动最小二乘(Moving Least Squares,MLS)曲面在寻找参考平面和局部双变量多项式时,涉及非线性优化计算所导致计算开销大的问题,提出了一种简化的MLS曲面投影方法,并将MLS曲面投影方法用于网格重建。该方法对点云建立包围盒,通过权化的协变矩阵估计局部点云曲面变化,并进行自适应的八叉树细分。在每个八叉树单元内,利用局部点云均值建立局部坐标系,并向MLS曲面投影产生用于网格化的顶点。然后对包含网格顶点的八叉树单元建立包围球,利用包围球之间的相交关系建立初始化的三角形网格拓扑。最后清理非流形网格部分,产生封闭的模型。该方法能够使点云产生自适应的三角网格,在时间和内存消耗方面都达到较好的效果。第三部分,针对Ohtake的二次误差函数迭代降噪方法降噪能力有限和基于区域增长式网格化效率低下的问题,提出了一种快速鲁棒的网格重建算法。首先建立描述散乱点云分布特征的贝叶斯模型,使用分段二次多项式函数为先验概率模型,同时局部点云均值服从高斯概率分布。通过求取后验概率极大值获得点云的降噪,并且保持细节和尖锐特征。降噪后的点云按照表面复杂程度进行自适应采样得到较小数量的顶点集合,一种新的区域增长式三角化方法应用到该点集中,该方法通过建立增量式圆球快速查找顶点构造三角形。为了保持网格的边和角等尖锐特征,将网格度量扭曲标准和二面角度量相结合产生新三角形,使得网格化后的模型表面能够充分接近物体表面。第四部分,研究了三维快速傅立叶变换在曲面重建中的应用,该方法过高的内存需求限制了重建最大分辨率,导致很难充分表示物体细节特征。针对该问题,提出了一种保持特征的点云网格重建方法。首先对协方差矩阵估计的不精确法向进行增强特征的法向扩散调整。将三维点云进行较低分辨率的三维快速傅立叶变换进行高斯滤波,然后转换到时域中过滤离群点,按照梯度方向迭代移动到离散等值面。对点云分布不足产生空洞的表面,增加离散采样点,使用圆球相交网格化方法对降噪后的点云进行网格化。第五部分,研究了分段二次多项式隐式曲面拟合技术,提出了保持尖锐特征的网格空洞修补方法。首先对带空洞的模型网格顶点,建立自适应的八叉树。利用分段二次多项式函数局部光滑可微的特性,采用分段二次多项式对网格空洞周围顶点进行拟合。而在尖锐特征处周围,则采用两个或者多个系数不同的二次多项式函数,分别进行拟合,从而获取原始网格所在曲面的尖锐特征边和角。利用扩展的Marching Cube方法获得空洞处的三角网格面片,并和原始网格模型缝合。最后,对于空洞处的网格面片,进行增强特征处理,消除锯齿状网格,获得清晰的尖锐特征。实验结果表明,该方法达到了预期的良好效果。第六部分对全文进行总结,并指出今后进一步的研究方向。更多还原

【Abstract】 3D surface reconstruction from point cloud is an attractive subject in computer graphics community, which plays an important role in many application fields, such as scientific computing visualization, CAD/CAM, movie and game. This dissertation comprehensively analyzes and summaries the related methods and techniques of mesh completion and surface mesh reconstruction from scattered point cloud. Based on two main approach integrating quadratic implicit surfaces fitting with triangle meshing from point cloud, the research on denoising, adaptive mesh and mesh completion preserving sharp features is emphasized. The main content reads as follows:In the first chapter, the meaning of meshing point cloud is presented. Then we summarize its techniques, methods and current advances. Finally, the main achievements and plan of contents in this dissertation are presented.In the second chapter, the moving least squares projection procedure is dicussed. It needs to find a reference plane and compute a local bivariate polynomial approximation to the surface, which is a non-linear optimization problem. A simple projection approach is proposed and used to mesh point cloud. By weighted covariance matrix estimating local surface variation, an octree-based subdivision of the box bounding the point cloud is created. Local coordinates are introduced with the origin of coordinates located at the weighted average of local points. Project points are created by projecting the origin to MLS surface. They are connected according to the analysis of the intersections among the spheres bounding the octree cell with mesh vertices. Finally, the mesh generated is cleaned out from non-manifold parts and small hole are filled. The method can generate adaptive high quality triangle mesh within limited time and low memory usage.In the third chapter, a new efficient robust mesh reconstruction, which improves the limited denoising of Ohtake’s quadric-error function iterations and low efficiency in region growing mesh reconstruction, is proposed based on Bayesian model. The model estimates the intrinsic property of point cloud. Prior probability part is piecewise quadratic implicit function and the average of local point cloud follow a Gaussian distribution. The maximum of posterior probability smoothes away noise while preserving surface detail and sharp features. After denoising, smaller numbers of points are generated by using surface splatting which decimates adaptively the point cloud. The reconstruction mesh from the new point set uses improved region growing mesh approach which searches neighboring points by a spatial sphere progressively growing along the surface of object. New triangles are generated according to integrating new mesh metric distortion principle with dihedral measurement to preserve sharp features. The resulting model has the reconstruction mesh as close as possible to the surface of the sampled point cloud.In the fourth chapter, surface reconstruction approach based on Fast Fourier Transform (FFT) is discussed. It limits the maximal reconstruction resolution to a level where the reconstruction of fine details of the input data is difficult. A feature-preserving mesh reconstruction algorithm from point cloud is proposed on the basis of the research about the application of the Fast Fourier Transform to surface reconstruction. This algorithm begins on a simple feature-enhancing diffusion applied to the normals estimated roughly by covariance matrix. Gaussian filter is applied to low resolution 3D FFT from point cloud. In time domain outliers are removed and points are moved onto the iso-surface by an iterative clustering along gradient field. Sample data are added to repaired defective surface, and then a new triangle mesh is generated by sphere-intersected method. The experimental results have shown that the algorithm is fast, robust and exhausts low memory.In the fifth chapter, based on the piecewise quadratic polynomial implicit surfaces fitting technology, this dissertation proposes a feature-preserving mesh completion algorithm. To create implicit representation, the algorithm starts with a box that bounds the mesh vertices and creates an octree-based subdivision of this box. Piecewise quadratic polynomial functions which are local smooth differentiable are used to fit the mesh vertices near the hole. Around the sharp features, two or more quadratic functions with different coefficients are used so as to capture sharp features such as edges or corners. The extended Marching Cube algorithm extracts the triangle mesh patch which is stitched with the hole boundary of the original model to complete the polygon mesh. Finally a feature enhancement process is applied to get rid of aliasing artifacts to obtain fine sharp features. The results of experimental tests show that excellent hole repairing mesh can be achieved.In the sixth chapter, the main results are proposed and the main points in future studies are briefly introduced.更多还原