Modeling of quality parameter values for improving meshes. (English) Zbl 1131.65017

Egorova, O.; Savchenko, M.; Hagiwara, I.; Savchenko, V.

Japan J. Ind. Appl. Math. 24, No. 2, 181-195 (2007).

Summary: A novel quasi-statistical approach to improve the quality of triangular meshes is presented. The present method is based on modeling of an event of the mesh improvement. This event is modeled via modeling of a discrete random variable. The random variable is modeled in a tangent plane of each local domain of the mesh. One domain collects several elements with a common point. The values of the random variable are calculated by a modeling formula according to the initial sampling data of the projected elements with respect to all neighbors of the domain.
A geometrical equivalent called potential form is constructed for each element of the domain with a mesh quality parameter value equal to the modeled numerical value. Such potential forms create potential centers of the domain. Averaging the coordinates of potential centers of the domain gives a new central point position. After geometrical realization over the entire mesh, the shapes of triangular elements are changed according to the normal distribution. It is shown experimentally that the mean of the final mesh is better than the initial one in most cases, so the event of the mesh improvement is likely occurred. Moreover, projection onto a local tangent plane included in the algorithm allows preservation of the model volume enclosed by the surface mesh.
The implementation results are presented to demonstrate the functionality of the method. Our approach can provide a flexible tool for the development of mesh improvement algorithms, creating better-input parameters for the triangular meshes and other kinds of meshes intended to be applied in finite element analysis or computer graphics.

MSC:

65D18	Numerical aspects of computer graphics, image analysis, and computational geometry
65N30	Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N50	Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs

Keywords:

numerical examples; random variable modeling; randomness; triangulation; mesh quality parameter; mesh improvement; triangular meshes; finite element; computer graphics

References:

[1]	N. Amenta, M. Bern and D. Eppstein, Optimal point placement for mesh smoothing. J. Algorithms30 (1999), 302–322. · Zbl 0919.65070 · doi:10.1006/jagm.1998.0984
[2]	B. Balendran, A direct smoothing method for surface meshing. Proceedings of the 8th International Meshing Roundtable. South Lake Tahoe, CA, USA, 1999, 189–193.
[3]	O. Egorova, M. Savchenko, N. Kojekine, I. Semenova, I. Hagiwaraand V. Savchenko, Improvement of mesh quality using a statistical approach. Proceedings of the 3th IASTED International conference on Vizualization. Imaging and Image Processing (VHP), Spain, 2003, 1016–1021.
[4]	P.J. Frey, About Surface Remeshing. Proceedings of the 9th International Meshing Roundtable. Sandia National Laboratories, 2000, 123–136.
[5]	M. Holder and J. Richardson, Genetic algorithms, another tool for quad mesh optimization? Proceedings of the 7th International Meshing Roundtable. Sandia National Lab., 1998, 497–504.
[6]	F.J. Bossen and P.S. Heckbert, A Pliant method for anisotropic mesh generation. Proceedings of the 5th International Meshing Roundtable. Pittsburgh, PA, 1996, 63–74.
[7]	D.A. Field, Laplacian smoothing and delaunay triangulations. J. Communications in Applied Numerical Methods,4 (1998), 709–712. · Zbl 0664.65107 · doi:10.1002/cnm.1630040603
[8]	T. Zhou and K. Shimada, An angle-based approach to two-dimensional mesh smoothing. Proceedings of the 9th International Meshing Roundtable. 2000, 373–384.
[9]	L.A. Freitag, On Combining Laplacian and Optimization-Based Mesh Smoothing Techniques. AMD220, Trends in Unstructured Mesh Generation, 1997, 37–43.
[10]	L.A. Freitag and C. Olliver-Gooch, A comparison of tetrahedral mesh improvement techniques. Proceedings of the 5th International Roundtable. Sandia National Lab., Albuquerque NM, 1996, 87–106.
[11]	V. Parthasarathy and S. Kodiyalam, A constrained optimization approach to finite element mesh smoothing. J. Finite Elements in Analysis and Design,9 (1991), 309–320. · Zbl 0850.73326 · doi:10.1016/0168-874X(91)90004-I
[12]	S.A. Canann, J.R. Tristano and M.L. Staten, An approach to combined Laplacian and optimization-based smoothing for triangular, quadrilateral, and quad-dominant meshes. Proceedings of the 7th International Meshing Roundtable, 1998, 479–494.
[13]	O.P. Jacquotte and G. Coussement, Structured mesh adaptation: space accuracy and interpolation methods. Computer Methods in Applied Mechanics and Engineering,101 (1992), 397–432. · Zbl 0777.76074 · doi:10.1016/0045-7825(92)90031-E
[14]	S.A. Canann, M.B. Stephenson and T.D. Blacker, Optismoothing: an optimization-driven approach to mesh smoothing. J. Finite Elements in Analysis and Design,13 (1993), 185–190. · Zbl 0816.65089 · doi:10.1016/0168-874X(93)90056-V
[15]	R. Lohner, K. Morgan and O.C. Zienkiewicz, Adaptive Grid Refinement for the Euler and Compressible Navier Stokes Equation. Proceedings of the International Conference on Accuracy Estimates and Adaptive Refinement in Finite Element Computations. Lisbon, 1984.
[16]	I. Babuska, O.C. Zienkiewicz, J. Gago and E.R. de A. Oliviera (eds.), Accuracy Estimates and Adaptive Refinements in Finite Element Computations. John Wiley & Sons, Chichester, 1986, 281–297.
[17]	K. Shimada and D.C. Gossard, Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing. Proceedings of the ACM Third Symposium on Solid Modeling and Applications. 1995, 409–419.
[18]	K. Shimada, Anisotropic triangular meshing of parametric surfaces via close packing of ellipsoidal bubbles. Proceedings of the 6th International Meshing Roundtable. Sandia National Laboratories, 1997, 375–390.
[19]	H.N. Djidjev, Force-directed methods for smoothing unstructured triangular and tetrahedral meshes. Proceedings of the 9th International Meshing Roundtable. Sandia National Laboratories, 2000, 395–406.
[20]	G. Taubin, A signal processing approach to fair surface design. Proceedings of SIGGRAPH’ 95,29 (1995), 351–358.
[21]	M. Desbrun, M. Meyer, P. Schrder and A.H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow. Proceedings of SIGGRAPH’ 99,33 (1999), 317–32.
[22]	J. Warren and H. Weimer, Subdivision Methods for Geometric Design. Academic Press, 2002.
[23]	L. Kobbelt, S. Campagna, J. Vorsatz and H-P. Seidel, Interactive multi-resolution modeling on arbitrary meshes. Proceedings of SIGGRAPH’ 98,32 (1998), 105–114. · Zbl 0959.65043
[24]	J.R. Shewchuk, What is a good linear element? interpolation, conditioning, and quality measures. Proceedings of the 11th International Meshing Roundtable. Sandia National Laboratories, 2002, 115–126.
[25]	K.E. Jansen, M.S. Shepard, and M.W. Beall, On anisotropic mesh generation and quality control in complex flow problems. Proceedings of the 10th International Meshing Roundtable. Sandia National Laboratories, 2001, 341–349.
[26]	I.M. Sobol, Monte Carlo Numerical Methods. Nauka, Moscow, 1973, in Russian. · Zbl 0289.65001
[27]	H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle, Surface reconstruction from unorganized points. Proceedings of SIGGRAPH’ 92, 1992, 71–78.