The exact reconsctruction of sharp features is a difficult problem concerned by reverse engineering, computer aided design and manufacture. To optimize the α-shape algorithm, our algorithm uses approximation of the topological neighbors of a sample point as the surface local sample, which makes α-shape scale thresholds reflect density of the points better, then the validity of the surface reconstruction is improved. Gaining the approximation of the topological neighbors of a sample point is essentially to achieve gain optimization for the Euclidean neighbors of the point, which extends the latter toward the sparse region of the sampled data so that it decreeses dropping of the topological neighbors caused by non-uniform points. Based on the approximation of the topological neighbors of points and prior knowledge of surface reconstruction, an α-shape scale threshold corresponding to an triangular face could be calculated, so that the scale thresholds used in surface reconstruction could be adjusted by itself adaptively. The tests show that this algorithm can reconstruct non-uniform point set with few holes and edge hollows, better maintain the accuracy of form and position, and reduce non-manifold facets, meanwhile, its efficiency is comparable with mainstream algorithms.
SUN Dianzhu
,
WEI Liang
,
LI Yanrui
,
BAI Yinlai
. Surface Reconstruction with α-shape Based on Optimization of Surface Local Sample[J]. Journal of Mechanical Engineering, 2016
, 52(3)
: 136
-142
.
DOI: 10.3901/JME.2016.03.136
[1] LIM S P，HARON H. Surface reconstruction techniques：A review[J]. Artificial Intelligence Review，2014，42(1)： 59-78.
[2] LAFARGE T，PATEIRO-LóPEZ B，POSSOLO A，et al. R implementation of a polyhedral approximation to a 3D set of points using the α-shape[J]. Journal of Statistical Software，2014，56(4)：1-19.
[3] EDELSBRUNNER H. Alpha shapes—a survey[J]. Tessellations in the Sciences，2010，27，1-25.
[4] JIANG J F，ZHONG Y Q，ZHANG Q P. Three-dimensional garment surface reconstruction based on ball-pivoting algorithm[J]. Advanced Materials Research，2013，821：765-768.
[5] GIESEN J，CAZALS F，PAULY M，et al. The conformal alpha shape filtration[J]. The Visual Computer，2006，22(8)：531-540.
[6] KRASNOSHCHEKOV D，POLISHCHUK V. Order-k α-hulls and α-shapes[J]. Information Processing Letters，2014，114(1)：76-83.
[7] TEICHMANN M, CAPPS M. Surface reconstruction with anisotropic density-scaled alpha shapes[C]//Proceedings of the Conference on Visualization'98. IEEE Computer Society Press，1998：67-72.
[8] XU X，HARADA K. Automatic surface reconstruction with alpha-shape method[J]. The Visual Computer，2003，19(7)：431-443.
[9] DEY T K，DYER R，WANG L. Localized cocone surface reconstruction[J]. Computers & Graphics，2011，35(3)： 483-491.
[10] DEY T K，WANG L. Voronoi-based feature curves extraction for sampled singular surfaces[J]. Computers & Graphics，2013，37(6)：659-668.
[11] CHANG M C，LEYMARIE F F，KIMIA B B. Surface reconstruction from point clouds by transforming the medial scaffold[J]. Computer Vision and Image Understanding，2009，113(11)：1130-1146.
[12] DI ANGELO L，DI STEFANO P，GIACCARI L. A new mesh-growing algorithm for fast surface reconstruction[J]. Computer-Aided Design，2011，43(6)：639-650.
[13] KAZHDAN M，HOPPE H. Screened poisson surface reconstruction[J]. ACM Transactions on Graphics (TOG)，2013，32(3)：29.
[14] CUOMO S，GALLETTI A，GIUNTA G，et al. Surface reconstruction from scattered point via RBF interpolation on GPU[C]//2013 Federated Conference on Computer Science and Information Systems. IEEE，2013：433-440.
[15] MERRY B，GAIN J，MARAIS P. Moving least-squares reconstruction of large models with GPUS[J]. IEEE Transactions on Visualization and Computer Graphics，2014，20(2)：249-261.
[16] 孙殿柱，刘华东，史阳，等. 基于核密度估计的散乱点云边界特征提取[J]. 农业机械学报，2013，44(12)：275-279. SUN Dianzhu，LIU Huadong，SHI Yang，et al. Boundary feature abstraction of unorganized points based on kernel density estimation[J]. Transactions of the Chinese Society for Agricultural Machinery，2013，44(12)：275-279.
[17] ANAND S，MITTAL S，TUZEL O，et al. Semi-supervised kernel mean shift clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(6)：1201-1215.
[18] HE K，SUN J. Computing nearest-neighbor fields via propagation-assisted kd-trees[C]// 2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE，2012：111-118.
[19] 孙殿柱，刘健，李延瑞，等. 三维散乱点云的 Voronoi 拓扑近邻点集查询算法[J]. 武汉大学学报：信息科学版，2011，36(1)： 86-91. SUN Dianzhu，LIU Jian，LI Yanrui，et al. An algorithm inquiring voronoi topological neighbors for 3D scattered point-cloud[J]. Eomatics and Information Science of Wuhan University，2011，36(1)：86-91.
[20] BARBER C B，DOBKIN D P，HUHDANPAA H. Quickhull algorithm for computing the convex hull[J]. ACM Transaction on Mathematical Software，22(4)：469-483.
