一种面向三维点集的快速表面重构算法

在对目前比较流行的空间三角化算法进行对比研究的基础上 ,对 Hugues Hoppe提出的算法进行了改进 ,即借鉴 Marching Cubes算法的基本思想 ,首先通过自动选取适当的参数 ,用包围盒方法将三维散乱点划分为数据区域 ;然后求取点的切平面及法向 ,同时采用广度优先算法遍历数据点来调整法向和快速地求取 Marching Cubes的等势函数 ;最后用基于查表法的 Marching Cubes来输出三角面片 ,即得到表面模型 .实验结果表明 ,改进后的算法效率有较大的提高 .新算法不仅适用于表面三维散乱点数据 ,也可以对体数据进行重构 ,具有一定的通用性 .

A Fast Model Reconstruction Algorithm for 3D Unorganized Points

Surface model reconstruction from 3D unorganized points (points of surface or volume) is of great importance in variable fields such as computer vision, images based modeling, 3D reconstruction based on images, scientific computing visualization, etc.. Many approaches have proposed to resolve the problem, such as 3D Delaunay triangulation, CDT, Qull Hull. etc. What makes the problem very difficult is that the reconstruction surface is convex and the efficiency of algorithms is not high. In this paper we present a fast model reconstruction algorithm for 3D unorganized points based on Hugues Hoppe algorithm. First, input points are divided into small logical "cubes" whose size can be decided automatically from the unorganized points according to Marching Cubes. Then the tangible planes and normal vectors at each point are calculated and all of the normal vectors are orientated to the outside of surface based on WFS(Wide First Searching). Finally, the function of iso-surface of scalar field for Marching Cubes algorithm can be obtained. In addition, ,the algorithm improves the efficiency of Marching Cubes by looking up tables. Finally the model can be obtained by the output of Marching Cubes composed of triangular meshes. Experimental results show the high efficiency of the algorithm. And the algorithm can be applied to not only the points of the surface but also the volume data (such as 3D scanning data, MRI data).