基于空间连通性的快速曲面重建算法

为提高用标准移动立体法进行等值面提取的速度,提出了一种改进算法。算法利用体元的空间连通关系,实现只访问和处理那些与等值面相交的体元;采用缓存技术记录已处理过体元的顶点信息,避免了重复计算,从而提高了重建的效率。文中还给出了接近于最佳搜索七一近邻速度的空间分块方法,大大提高了散乱数据点的处理效率。应用实例说明,算法的效果良好。

Fast Reconstruction of Surface Based on Spatial Connectivity

An exhaustive searching all the cells in a 3D dataset decreases the efficiency of surface reconstruction when the standard Marching Cubes (MC) algorithm is used to extract the isosurface from unorganized points. An extended marching cubes algorithm is proposed. The algorithm can more efficiently extract the isosurface based on the spatial connectivity of cells and hence "marching" only into the cells that contain the surface. Using cache technology, by which the evaluated signed distance from vertices of the cell to the isosurface are saved and copied into its neighboring cells, can improve the efficiency of the algorithm. The spatial partitioning method with a nearly optimal speed of searching k-nearest neighbors, which is put forward in the paper, improves greatly the processing speed of points. The experimental results show that the proposed algorithm is effective.