Consistent computation of first- and second-order differential quantities for surface meshes

ABSTRACT

Differential quantities, including normals, curvatures, principal directions, and associated matrices, play a fundamental role in geometric processing and physics-based modeling. Computing these differential quantities consistently on surface meshes is important and challenging, and some existing methods often produce inconsistent results and require ad hoc fixes. In this paper, we show that the computation of the gradient and Hessian of a height function provides the foundation for consistently computing the differential quantities. We derive simple, explicit formulas for the transformations between the first- and second-order differential quantities (i.e., normal vector and curvature matrix) of a smooth surface and the first- and second-order derivatives (i.e., gradient and Hessian) of its corresponding height function. We then investigate a general, flexible numerical framework to estimate the derivatives of the height function based on local polynomial fittings formulated as weighted least squares approximations. We also propose an iterative fitting scheme to improve accuracy. This framework generalizes polynomial fitting and addresses some of its accuracy and stability issues, as demonstrated by our theoretical analysis as well as experimental results.

REFERENCES

• 1: Gady Agam , Xiaojing Tang, A Sampling Framework for Accurate Curvature Estimation in Discrete Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.11 n.5, p.573-583, September 2005 [doi>10.1109/TVCG.2005.69]
• 2: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: F. Cazals , M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Computer Aided Geometric Design, v.22 n.2, p.121-146, February 2005 [doi>10.1016/j.cagd.2004.09.004]
• 4: David Cohen-Steiner , Jean-Marie Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777839]
• 5: De Boor, C., and Ron, A. 1992. Computational aspects of polynomial interpolation in several variables. Math. Comp. 58, 705--727.
• 6: Do Carmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.
• 7: Do Carmo, M. P. 1992. Riemannian Geometry. Birkhäuser Boston.
• 8: Jean Gallier, Curves and surfaces in geometric modeling: theory and algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 9: Gatzke, T., and Grimm, C. 2006. Estimating curvature on triangular meshes. Int. J. Shape Modeling 12, 1--29.
• 10: Jack Goldfeather , Victoria Interrante, A novel cubic-order algorithm for approximating principal direction vectors, ACM Transactions on Graphics (TOG), v.23 n.1, p.45-63, January 2004 [doi>10.1145/966131.966134]
• 11: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 12: Grinspun, E., Gingold, Y., Reisman, J., and Zorin, D. 2006. Computing discrete shape operators on general meshes. Eurographics (Computer Graphics Forum) 25, 547--556.
• 13: Hildebrandt, K., Polthier, K., and Wardetzky, M. 2006. On the convergence of metric and geometric properties of polyhedral surfaces. Geometria Dedicata 123, 89--112.
• 14: Lancaster, P., and Salkauskas, K. 1986. Curve and Surface Fitting: An Introduction. Academic Press.
• 15: Langer, T., Belyaev, A. G., and Seidel, H.-P. 2005. Analysis and design of discrete normals and curvatures. Tech. rep., Max-Planck-Institut Fur Informatik.
• 16: Langer, T., Belyaev, A. G., and Seidel, H.-P. 2005. Exact and approximate quadratures for curvature tensor estimation. In Poster Proc. of Symposium on Geometry Processing.
• 17: D. S. Meek , D. J. Walton, On surface normal and Gaussian curvature approximations given data sampled from a smooth surface, Computer Aided Geometric Design, v.17 n.6, p.521-543, July 2000 [doi>10.1016/S0167-8396(00)00006-6]
• 18: Meyer, M., Desbrun, M., Schröder, P., and Barr, A. 2002. Discrete differential geometry operators for triangulated 2-manifolds. In Visualization and Mathematics, H.-C. Hege and K. Poltheir, Eds., vol. 3. Springer, 34--57.
• 19: Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, Ridge-valley lines on meshes via implicit surface fitting, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 20: Ońate, E., and Cervera, M. 1993. Derivation of thin plate bending elements with one degree of freedom per node. Engineering Computations 10, 543.
• 21: Sylvain Petitjean, A survey of methods for recovering quadrics in triangle meshes, ACM Computing Surveys (CSUR), v.34 n.2, p.211-262, June 2002 [doi>10.1145/508352.508354]
• 22: Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 15--36.
• 23: Razdan, A., and Bae, M. 2005. Curvature estimation scheme for triangle meshes using biquadratic Bézier patches. Comput. Aid. Des. 37, 1481--1491.
• 24: Szymon Rusinkiewicz, Estimating Curvatures and Their Derivatives on Triangle Meshes, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.486-493, September 06-09, 2004 [doi>10.1109/3DPVT.2004.54]
• 25: G. Taubin, Estimating the tensor of curvature of a surface from a polyhedral approximation, Proceedings of the Fifth International Conference on Computer Vision, p.902, June 20-23, 1995
• 26: Holger Theisel , Christian Rossl , Rhaleb Zayer , Hans-Peter Seidel, Normal Based Estimation of the Curvature Tensor for Triangular Meshes, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.288-297, October 06-08, 2004
• 27: Van Der Sluis, A. 1969. Condition numbers and equilibration of matrices. Numer. Math. 14, 14--23.
• 28: Wardetzky, M. 2007. Convergence of the cotan formula - an overview. In Discrete Differential Geometry, A. I. Bobenko, J. M. Sullivan, P. Schröder, and G. Ziegler, Eds. Birkhäuser Basel.
• 29: Xu, G. 2004. Convergence of discrete Laplace-Beltrami operators over surfaces. Comput. Math. Appl. 48, 347--360.
• 30: Yong-Liang Yang , Yu-Kun Lai , Shi-Min Hu , Helmut Pottmann, Robust principal curvatures on multiple scales, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 31: Denis Zorin, Curvature-based Energy for Simulation and Variational Modeling, Proceedings of the International Conference on Shape Modeling and Applications 2005, p.198-206, June 13-17, 2005 [doi>10.1109/SMI.2005.14]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
curvatures, height function, normals, principal directions, shape operators, stabilities