Laplace–Beltrami Operator on Point Clouds Based on Anisotropic Voronoi Diagram

Computer Graphics Forum 2018

Hongxing Qin1,2          Yi Chen1,2          Yunhai Wang3          Xiaoyang Hong1,2           Kangkang Yin4           Hui Huang5

1Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts & Telecommunications

2College of Computer Science and Technology, Chongqing University of Posts & Telecommunications
3Shandong University           4Simon Fraser University          5Shenzhen University


The symmetrizable and converged Laplace–Beltrami operator (△M) is an indispensable tool for spectral geometrical analysis of point clouds. The △M, introduced by Liu et al. [LPG12] is guaranteed to be symmetrizable, but its convergence degradesn when it is applied to models with sharp features. In this paper, we propose a novel △M, which is not only symmetrizable but also can handle the point-sampled surface containing significant sharp features. By constructing the anisotropic Voronoi diagram in the local tangential space, the △M can be well constructed for any given point. To compute the area of anisotropic Voronoi cell, we introduce an efficient approximation by projecting the cell to the local tangent plane and have proved its convergence. We present numerical experiments that clearly demonstrate the robustness and efficiency of the proposed △M for point clouds that may contain noise, outliers, and non-uniformities in thickness and spacing. Moreover, we can show that its spectrum is more accurate than the ones from existing △M for scan points or surfaces with sharp features.

Figure 1: The comparisons of eigenvectorsH2 (the first three lines) and H10 (the last three lines) on the model with sharp features. The first and fourth lines are the results generated by BSW [BSW09], the second and fifth lines are the results generated by PBMH [LPG12]. The third and sixth lines are the results generated by our approach.

Figure 2: The reconstruction of point clouds data based on bases. From left to right, we show the original hand model (7k points), the reconstruction results with 2k bases corresponding to the largest eigenvalues on BSW, PBMH and our AVD, and corresponding errors between the reconstructed models and the original model in BSW, PBMH and our AVD.


The authors wish to thank the anonymous reviewers for their remarks that helped us improving the paper. This work is partly supported by the grants of Natural Science Foundation of China (61772097),NSFC Guangdong Joint Fund (U1401252, U1501255),
the National Key Research & Development Plan of China (2016YFB1001404), Science Challenge Project, No. TZ2016002, Guangdong Science and Technology Program (2015A030312015), Shandong Provincial Natural Science Foundation (2016ZRE27617)

and the Fundamental Research Funds of Shandong University.


    title = {Laplace–Beltrami Operator on Point Clouds Based on Anisotropic Voronoi Diagram},
    author = {Hongxing Qin and Yi Chen and Yunhai Wang and Xiaoyang Hong and Kangkang Yin and Hui Huang},
    journal = {Computer Graphics Forum 2018},

    volume = {37},

    number = {6}
    pages = {106--117},
    year = {2018}

Downloads (faster for people in China)

Downloads (faster for people in other places)