结合Delaunay三角面分离法与搜索球策略的三维曲面重建算法

3D Surfaces Reconstruction Algorithm Via Detaching Delaunay Triangular Mesh and Search-Ball Approach

基于曲面重建在计算机图形学、三维GIS、逆向工程等领域有重要应用,结合区域生长法与Delaunay三角剖分的优势,提出了一种新的散乱点云曲面重建算法。首先根据曲面中轴性质提出了分离角定义并推导了相关结论,利用局部Delaunay三角形分离角性质抽取大量位于模型表面三角形,从而构建种子三角网增加初始区域的生长面积其次运用自适应搜索球法加快邻域三角形搜索并识别曲面边界。对比传统的基于Delaunay法和传统区域生长法,该方法只需要一次三角剖分,无需极点与法向量计算,重建速度快,具有Delaunay三角网格的优良结构特性,孔洞数量少,重建出的三维模型几何信息与拓扑关系准确。实验表明,结合Delaunay三角剖分与区域生长法重构有向的流形三角网格模型,能够提高三维模型的重建效果与速度,有效地自动识别曲面边界。

3D surface reconstruction are becoming increasing important in geometric modeling and related applications such as in computer graphics,3D GIS,reverse engineering.This paper presents an algorithm that holds the advantages of both region-growth approaches and Delaunay based on unorganized point cloud.Separation angle is defined and deduced the related conclusion according to the nature of the surface axis,which is applied to extract triangles from the surface of model and increase the initial growth area of the region.An approach of adaptive search-ball method is presented to speed up searching the neighbourhood-triangles and identify the surface boundary.Compared with the traditional Delaunay-based approach,this algorithm requires only one-pass Delaunay computation and reconstruct surfaces rapidly without calculation of pole and the vector.Compared with the traditional region growing method,this algorithm inherits the structural characteristics of the Delaunay triangulation with fewer holes and accurate the 3D geometry information and topology.Experimental results shows that it is highly efficient compared with other existing algorithms and capable of handling surfaces with complex topology,boundaries,which holds the advantages of both region-growth approaches and Delaunay.