在曲面重建中，提高棱边特征重建精度是逆向工程和计算机辅助设计制造等领域的难点问题。采用样点的近似拓扑近邻点集作为曲面局部样本，对α-shape算法进行优化，使α-shape尺度阈值能更为准确地反映样点分布密度，从而提高α-shape曲面拓扑重建结果的正确性。样点的近似拓扑近邻点集的获取本质上是欧氏近邻点集的增益优化，使后者向邻近的稀疏区域适度延伸，从而弥补因数据分布不均匀而导致的拓扑邻域信息缺失。基于增益优化后的样点近邻点集并结合曲面重建先验知识可确定α-shape尺度阈值，使α-shape曲面拓扑重建过程中尺度阈值可自适应调整。试验表明：该算法使所得网格曲面基本不含孔洞和棱边凹痕，能更好保持棱边特征的形位精度，可减少初次过滤结果中的非流形面片，同时具有与主流Delaunay网格过滤算法相近的重建效率。
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.
[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.
