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

A Fast Model Reconstruction Algorithm for 3D Unorganized Points

作　　者：梁荣华[1,2] 陈纯[1] 潘志庚[3] 张慧[1] 

机构地区：[1]浙江大学计算机科学与工程系 [2]杭州电子工业学院计算机学院,杭州310037 [3]浙江大学CAD&CG国家重点实验室

出　　处：《中国图象图形学报》2003年第1期66-70,共5页Journal of Image and Graphics

基　　金：浙江省自然科学基金资助项目 (60 10 43 )

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

关 键 词：三维重建 空间三角化 广度优先 MarchingCubes 等值面 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]