Email this article Conformal Alpha Shape-based Multi-scale Curvature Estimation from Point Clouds
Abstract
Multi-scale geometrical and topological analyses
of point clouds can reveal their rich structures. Because
conformal alpha shapes of point clouds are hierarchical
shapes under different mesh resolution or internal alpha
values, their surface curvature estimations are one of the
multi-scale geometrical analyses. We present a robust
method for computing surface curvature of conformal alpha
shapes on point cloud data, and provide theoretical
guarantees on the robustness of our method. An approach is
proposed to estimate the internal alpha scale parameters.
The methods can be used to extract local curvatures of
hierarchical shapes and as a multi-scale geometrical analysis
method of point clouds. It is useful in many applications
ranging from bio-geometric modeling to surface
reconstruction. We describe an implementation of the
algorithm and show example outputs.
Keywords
References
[1] N. Amenta, M. Bern: Surface reconstruction by Voronoï filtering. Discrete and Computational Geometry 22 (1999), 481–504. 1, 3
[2] D. Aiger, N. Mitra, and D. Cohen-Or: 4-points congruent sets for robust pairwise surface registration, ACM Trans. Graph., vol. 27, no. 3, 2008.
http://dx.doi.org/10.1145/1360612.1360684
[3] Yi An, Cheng Shao, Xiaoliang Wang, Zhuohan Li: Estimating Principal Curva-tures and Principal Directions from Discrete Surfaces Using Discrete Curve Model, Journal of Information & Computational Science 8: 2 (2011) 296–311.
[4] Banchoff T., Lovett S.: Differential Geometry of Curves and Surfaces. A K Peters Ltd, 2010.
[5] F. Cazals, J. Giesen, M. Pauly, A. Zomorodian: Conformal Alpha Shapes. 2nd Symposium on Point Based Graphics, 2005
http://dx.doi.org/10.1109/PBG.2005.194064
[6] Gregory Cipriano, George N. Phillips Jr., and Michael Gleicher: Multi-Scale Sur-face Descriptors, IEEE Transactions on Visualization and Computer Graphics, Dec. 2009, vol.15, no.6, pp. 1201-1208.
http://dx.doi.org/10.1109/TVCG.2009.168
PMid:19834190 PMCid:2873089
[7]Chen, G., Wu, Y., Estimating normal vectors and curvatures by centroid weights. Computer Aided Geometric Design, 21:447-458, 2004.
http://dx.doi.org/10.1016/j.cagd.2004.02.003
[8]Dong Chenshi, Wang Guozhao, Curvatures estimation on triangular mesh, Journal of Zhejiang University -SCIENCE, Volume 6, Supplement 1, 128-136, 2005.[9] H. Edelsbrunner: Geometry and Topology for Mesh Generation. Cambridge Univer-sity Press, New York, NY, 2001. 2
[10] Edelsbrunner: Alpha shapes --- a survey. In Tessellations in the Sciences, 2010.
[11]S. Fortune: Voronoi diagrams and Delaunay triangulations. In J. E.Goodman and J. O’Rourke, editors, Handbook of Discrete and Computational Geometry. CRC Press, second edition, 2004.
http://dx.doi.org/10.1201/9781420035315.ch23
[12] Gatzke T., Grimm C.: Estimating curvature on triangular meshes. International Journal of Shape Modeling 12, 1 (2006), 1--29.
http://dx.doi.org/10.1142/S0218654306000810
[13]Cindy Grimm, William D. Smart: Shape classification and normal estimation for non-uniformly sampled, noisy point data, Computers and Graphics (2011).
http://dx.doi.org/10.1016/j.cag.2011.03.036
[14]J. P. Gois, E. Tejada, T. Etiene, L. G. Nonato, A. Castelo, and T. Ertl: Curva-ture-driven modeling and rendering of point-based surfaces, in Braz. Symp. Comp. Graph. Imag. Proc, 2006, pp. 27–36.
[15] Wesley Griffin, Yu Wang, David Berrios, Marc Olano: GPU curvature estimation on deformable meshes, I3D '11 Symposium on Interactive 3D Graphics and Games.
[16]E. Kalogerakis, D. Nowrouzezahrai, P. Simari, K. Singh: Extracting lines of curva-ture from noisy point clouds, pecial Issue of the Computer-Aided Design on Point-Based Computational Techniques, Vol. 41, No. 4, April 2009.
[17] C. Lange and K. Polthier: Anisotropic smoothing of point sets, Comp. Aided Geom. D., vol. 22, no. 7, pp. 680–692, 2005.
http://dx.doi.org/10.1016/j.cagd.2005.06.010
[18] Quentin Merigot, Maks Ovsjanikov, and Leonidas Guibas: Voronoi-based Curva-ture and Feature Estimation from Point Clouds, Visualization and Computer Graphics, IEEE Transactions, Vol. 17, Issue 6, June 2011, pp. 43 – 756
[19] M. Pauly, N. Mitra, J. Wallner, H. Pottmann, and L. Guibas: Discovering struc-tural regularity in 3d geometry, ACM Trans. Graph., vol. 27, no. 3, 2008.
http://dx.doi.org/10.1145/1360612.1360642
[20] Helmut Seibert, Dietmar Hildenbrand, Meike Becker, Arjan Kuijper: Estimation of curvatures in point sets based on geometric algebra, 2010.
[21] Szilvasi-Nagy, M., About Curvatures on Triangle Meshes, KoG•10–2006.
[22]Pawel Winter, Henrik Sterner, Peter Sterner: Alpha Shapes and Proteins, In-terna-tional Symposium on Voronoi Diagrams in Science and Engineering, pp. 217-224, 2009 Sixth International Symposium on Voronoi Diagrams, 2009.
http://dx.doi.org/10.1109/ISVD.2009.25
Full Text: PDF