×

Variational shape approximation of point set surfaces. (English) Zbl 1505.65093

Summary: In this work, we present a translation of the complete pipeline for variational shape approximation (VSA) to the setting of point sets. First, we describe an explicit example for the theoretically known non-convergence of the currently available VSA approaches. The example motivates us to introduce an alternate version of VSA based on a switch operation for which we prove convergence. Second, we discuss how two operations – split and merge – can be included in a fully automatic pipeline that is in turn independent of the placement and number of initial seeds. Third and finally, we present two approaches how to obtain a simplified mesh from the output of the VSA procedure. This simplification is either based on simple plane intersection or based on a variational optimization problem. Several qualitative and quantitative results prove the relevance of our approach.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

PCL; Matlab
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Attene, M.; Patanè, G., Hierarchical structure recovery of point-sampled surfaces, (Computer Graphics Forum (2010), Wiley Online Library), 1905-1920
[2] Berger, M.; Tagliasacchi, A.; Seversky, L. M.; Alliez, P.; Guennebaud, G.; Levine, J. A.; Sharf, A.; Silva, C. T., A survey of surface reconstruction from point clouds, Comput. Graph. Forum, 36, 1, 301-329 (2017)
[3] Cohen-Steiner, D.; Alliez, P.; Desbrun, M., Variational shape approximation, (ACM Transactions on Graphics. ACM Transactions on Graphics, TOG (2004), ACM), 905-914
[4] Cutler, B.; Whiting, E., Constrained planar remeshing for architecture, (Proceedings of Graphics Interface 2007 (2007)), 11-18
[5] Dai, M.; Newman, T. S., Hyperbolic and parabolic quadric surface fitting algorithms-Comparison between the least squares approach and the parameter optimization approach (1998), University of Alabama, Technical Report
[6] Garland, M.; Heckbert, P. S., Surface simplification using quadric error metrics, (Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (1997)), 209-216
[7] Grilli, E.; Menna, F.; Remondino, F., A review of point clouds segmentation and classification algorithms, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., XLII-2, W3, 339-344 (2017)
[8] Harris, P.; Brunsdon, C.; Charlton, M., Geographically weighted principal components analysis, Int. J. Geogr. Inf. Sci., 25, 1717-1736 (2011)
[9] Hu, Y.; Zhou, Q.; Gao, X.; Jacobson, A.; Zorin, D.; Panozzo, D., Tetrahedral meshing in the wild, ACM Trans. Graph., 37, Article 60 pp. (2018)
[10] Hua, Z.; Huang, Z.; Li, J., Mesh simplification using vertex clustering based on principal curvature, Int. J. Multimed. Ubiquitous Eng., 10, 99-110 (2015)
[11] Lee, K. W.; Bo, P., Feature curve extraction from point clouds via developable strip intersection, J. Comput. Des. Eng., 3, 102-111 (2016)
[12] Levoy, M.; Whitted, T., The use of points as a display primitive (1985), University of North Carolina, Department of Computer Science: University of North Carolina, Department of Computer Science Chapel Hill, NC, USA, Technical Report
[13] Lloyd, S. P., Least squares quantization in pcm, IEEE Trans. Inf. Theory, 28, 129-137 (1982) · Zbl 0504.94015
[14] Mathworks; Matlab, Solve a constrained nonlinear problem, problem-based
[15] Nguyen, A.; Le, B., 3d point cloud segmentation: a survey, (2013 6th IEEE Conference on Robotics, Automation and Mechatronics. 2013 6th IEEE Conference on Robotics, Automation and Mechatronics, RAM (2013)), 225-230
[16] Pauly, M.; Gross, M.; Kobbelt, L., Efficient simplification of point-sampled surfaces, (Proceedings of the Conference on Visualization ’02 (2002), IEEE Computer Society), 163-170
[17] Rabbani, T.; Van Den Heuvel, F.; Vosselmann, G., Segmentation of point clouds using smoothness constraint, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., 36, 248-253 (2006)
[18] Rusu, R.; Cousins, S., 3d is here: point cloud library (pcl), (IEEE International Conference on Robotics and Automation. IEEE International Conference on Robotics and Automation, ICRA (2011)), 6324-6328
[19] Schnabel, R.; Wahl, R.; Klein, R., Efficient RANSAC for point-cloud shape detection, (Computer Graphics Forum (2007), Wiley Online Library), 214-226
[20] Skrodzki, M., Neighborhood Data Structures, Manifold Properties, and Processing of Point Set Surfaces (2019), Freie Universität Berlin: Freie Universität Berlin Berlin, Germany, Ph.D. thesis
[21] Skrodzki, M.; Jansen, J.; Polthier, K., Directional density measure to intrinsically estimate and counteract non-uniformity in point clouds, Comput. Aided Geom. Des., 64, 73-89 (2018) · Zbl 1505.65092
[22] Skrodzki, M.; Zimmermann, E.; Polthier, K., Variational shape approximation of point set surfaces, (IGS 2019 International Geometry Summit - Poster Proceedings (2019)), 54-57
[23] Sosorbaram, B.; Fujimoto, T.; Chiba, N., Simplification of point set surfaces using bilateral filter and multi-sized splats, J. Soc. Art Sci., 9, 3, 140-153 (2010)
[24] Wu, J.; Kobbelt, L., Structure recovery via hybrid variational surface approximation, (Computer Graphics Forum (2005), Wiley Online Library), 277-284
[25] Xie, Y.; Tian, J.; Zhu, X. X., A review of point cloud semantic segmentation (2019)
[26] Yan, D. M.; Liu, Y.; Wang, W., Quadric surface extraction by variational shape approximation, (Kim, M. S.; Shimada, K., Geometric Modeling and Processing - GMP 2006 (2006), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg), 73-86 · Zbl 1160.68662
[27] Yao, L.; Huang, S.; Xu, H.; Li, P., Quadratic error metric mesh simplification algorithm based on discrete curvature, Math. Probl. Eng., 2015 (2015) · Zbl 1394.65015
[28] Zimmer, H.; Campen, M.; Herkrath, R.; Kobbelt, L., Variational tangent plane intersection for planar polygonal meshing, (Hesselgren, L.; Sharma, S.; Wallner, J.; Baldassini, N.; Bompas, P.; Raynaud, J., Advances in Architectural Geometry 2012 (2012), Springer), 319-332
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.