Energy-Minimizing Curve Fitting for High-Order Surface Mesh Generation

Karsten Bock, Jörg Stiller

Institute of Fluid Mechanics (ISM), Technische Universität Dresden, Dresden, Germany.

DOI: 10.4236/am.2014.521309                

Abstract

We investigate different techniques for fitting Bézier curves to surfaces in context of high-order curvilinear mesh generation. Starting from distance-based least-squares fitting we develop an incremental algorithm, which incorporates approximations of stretch and bending energy. In the process, the algorithm reduces the energy weight in favor of accuracy, leading to an optimized set of sampling points. This energy-minimizing fitting strategy is applied to analytically defined as well as triangulated surfaces. The results confirm that the proposed method straightens and shortens the curves efficiently. Moreover the method preserves the accuracy and convergence behavior of distance-based fitting. Preliminary application to surface mesh generation shows a remarkable improvement of patch quality in high curvature regions.

Keywords

Curvilinear Mesh Generation, High-Order Methods, Bézier Curves, Curve Fitting, Energy Minimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Karniadakis, G.E. and Sherwin, S. (2005) Spectral/hp Element Methods for Computational Fluid Dynamics. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford.
[2]	Deville, M., Fischer, P.F. and Mund, E.H. (2002) High-Order Methods for Incompressible Fluid Flow. Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/CBO9780511546792
[3]	Cockburn, B.B., Karniadakis, G.E. and Shu, C.-W. (2000) Discontinuous Galerkin Methods: Theory, Computation and Applications. Lecture Notes in Computational Science and Engineering. Springer, Berlin. http://dx.doi.org/10.1007/978-3-642-59721-3
[4]	Hesthaven, J.S. and Warburton, T. (2008) Nodal Discontinuous Galerkin Methods/Algorithms, Analysis, and Applications. Springer, Berlin.
[5]	Dey, S., O’Bara, R.M. and Shephard. M.S. (1999) Curvilinear Mesh Generation in 3d. Proceedings of the Eighth International Meshing Roundtable, John Wiley & Sons, Hoboken, 407-417.
[6]	Sherwin, S.J. and Peiró, J. (2002) Mesh Generation in Curvilinear Domains Using Highorder Elements. International Journal for Numerical Methods in Engineering, 53, 207-223. http://dx.doi.org/10.1002/nme.397
[7]	Persson, P.-O. and Peraire, J. (2009) Curved Mesh Generation and Mesh Refinement Using Lagrangian Solid Mechanics. Proceedings of the 47th AIAA Aerospace Sciences Meeting and Exhibit.
[8]	Toulorge, T., Geuzaine, C., Remacle, J.-F. and Lambrechts, J. (2013) Robust Untangling of Curvilinear Meshes. Journal of Computational Physics, 254, 8-26. http://dx.doi.org/10.1016/j.jcp.2013.07.022
[9]	Hoschek, J. and Lasser, D. (1996) Fundamentals of Computer Aided Geometric Design. Wellesley, Massachusetts.
[10]	Farin, G. (2002) Curves and Surfaces for CAGD—A Practical Guide. 5th Edition, Academic Press, Waltham.
[11]	Veltkamp, R.C. and Wesselink, W. (1995) Modeling 3D Curves of Minimal Energy. Blackwell Science Ltd., Computer Graphics Forum, 14, 97-110. http://dx.doi.org/10.1111/j.1467-8659.1995.cgf143_0097.x
[12]	Wang, W., Pottmann, H. and Liu, Y. (2006) Fitting B-Spline Curves to Point Clouds by Curvature-Based Squared Distance Minimization. ACM Transactions on Graphics, 25, 214-238. http://dx.doi.org/10.1145/1138450.1138453
[13]	Alhanaty, M. and Bercovier, M. (2001) Curve and Surface Fitting and Design by Optimal Control Methods. Computer-Aided Design, 33, 167-182. http://dx.doi.org/10.1016/S0010-4485(00)00089-0
[14]	Flöry, S. and Hofer, M. (2008) Constrained Curve Fitting on Manifolds. Computer-Aided Design, 40, 25-34. http://dx.doi.org/10.1016/j.cad.2007.01.012
[15]	Hofer, M. and Pottmann, H. (2004) Energy-Minimizing Splines in Manifolds. ACM Transactions on Graphics, 23, 284-293. http://dx.doi.org/10.1145/1015706.1015716
[16]	Hofer, M. (2007) Constrained Optimization with Energy-Minimizing Curves and Curve Networks: A Survey. Proceedings of the 23rd Spring Conference on Computer Graphics, Comenius University, Bratislava, 27-35. http://dx.doi.org/10.1145/2614348.2614353
[17]	Lawonn, K., Gasteiger, R., R?ssl, C. and Preim, B. (2014) Adaptive and Robust Curve Smoothing on Surface Meshes. Computers & Graphics, 40, 22-35. http://dx.doi.org/10.1016/j.cag.2014.01.004
[18]	Max, N. (1999) Weights for Computing Vertex Normals from Facet Normals. Journal of Graphics Tools, 4, 1-6. http://dx.doi.org/10.1080/10867651.1999.10487501
[19]	Vlachos, A., Peters, J., Boyd, C. and Mitchell, J.L. (2001) Curved PN Triangles. Proceedings of the 2001 Symposium on Interactive 3D Graphics, I3D’01, New York, 159-166.
[20]	Phong, B.T. (1975) Illumination for Computer Generated Pictures. Communications of the ACM, 18, 311-317. http://dx.doi.org/10.1145/360825.360839
[21]	Bock, K. and Stiller, J. (2014) Generation of High-Order Polynomial Patches from Scattered Data. In: Azaïez, M., El Fekih, H. and Hesthaven, J.S., Eds., Spectral and High Order Methods for Partial Differential Equations-ICOSAHOM 2012, Lecture Notes in Computational Science and Engineering, Vol. 95, Springer International Publishing, 157-167.