Adaptive techniques for unstructured nested meshes. (English) Zbl 1062.65127
Summary: The purpose of this paper is twofold. First we introduce improved versions of our algorithms for refining and coarsening 2D and 3D nested triangular and tetrahedral grids, and secondly the application of these algorithms in the simulation of 2D and 3D problems, is demonstrated. A key idea of the algorithms is the use of the topological concept of the skeleton of a triangulation in two or three dimensions in order to reduce the dimension of the refinement problem in a natural hierarchic manner.
Improved skeleton based refinement (SBR) algorithms and their counterpart, the skeleton based derefinement (SBD) algorithms are described in this study. The algorithms are fully automatic and are applied here to a 2D boundary value problem, a 3D approximation problem with a large gradient, a geometric shape modeling problem and a simulation evolution problem in 3D.
Improved skeleton based refinement (SBR) algorithms and their counterpart, the skeleton based derefinement (SBD) algorithms are described in this study. The algorithms are fully automatic and are applied here to a 2D boundary value problem, a 3D approximation problem with a large gradient, a geometric shape modeling problem and a simulation evolution problem in 3D.
MSC:
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 35J65 | Nonlinear boundary value problems for linear elliptic equations |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
Keywords:
Refinement; Coarsening; Grid generation; Skeleton graph; numerical examples; finite elements; algorithms; triangulationReferences:
| [1] | Arnold, D. N.; Mukherjee, A.; Pouly, L., Locally adapted tetrahedral meshes using bisection, SIAM J. Sci. Comput. (2), 22, 443-448 (1997) · Zbl 0973.65116 |
| [2] | Bänsch, E., Local mesh refinement in 2 and 3 dimensions, IMPACT Comput. Sci. Engrg, 3, 181-191 (1991) · Zbl 0744.65074 |
| [3] | Baumgart, B. G., A polyhedron representation for computer vision, (AFIPS Natl. Computer Conf., Anaheim, CA (1975)), 589-596 |
| [4] | Berger, M., Geometry (1987), Springer: Springer Berlin · Zbl 0606.51001 |
| [5] | Bova, S. W.; Carey, G. F., Mesh generation/refinement using fractal concepts and iterated function systems, Internat. J. Numer. Methods Engrg, 33, 287-305 (1992) · Zbl 0756.65132 |
| [6] | Carey, G. F., Computational Grids: Generation, Refinement and Solution Strategies (1997), Taylor and Francis: Taylor and Francis London · Zbl 0955.74001 |
| [7] | Carey, G. F.; Pehlivanov, A. I.; Mastroleo, R. C.; McLay, R.; Shen, Y.; Carey, V.; Dutton, R., Hierarchic visualization and parallel computation, (Proceedings High Performance Computing ’98 (1998)), Boston, MA |
| [8] | Cuillière, J. C., An adaptive method for the automatic triangulation of 3D parametric surfaces, Comput. Aided Design, 30, 139-149 (1998) |
| [9] | Ferragut, L.; Montenegro, R.; Plaza, A., Efficient refinement/derefinement algorithm of nested meshes to solve evolution problems, Comm. Numer. Methods Engrg, 10, 403-412 (1994) · Zbl 0853.65097 |
| [10] | de Floriani, L.; Falcidieno, G.; Nacy, G.; Pieno, C., A hierarchical structure for surface approximation, Comput. & Graph, 31, 2, 183-193 (1984) |
| [11] | François, V.; Cuillière, J. C., Automatic mesh pre-optimization based on the geometric discretization error, Adv. Engrg. Software, 31, 763-774 (2000) · Zbl 1003.68509 |
| [12] | Frey, P. J.; George, P. L., Maillages. Application aux Éléments Finis (1999), Hermes: Hermes Paris |
| [13] | George, P. L., Automatic Mesh Generation (1991), Willey: Willey New York · Zbl 0808.65122 |
| [14] | Hackbush, W., Multigrid Methods and Applications (1985), Springer: Springer Berlin · Zbl 0595.65106 |
| [15] | Hartmann, E., Numerical parametrization of curves and surfaces, Comput. Aided Geom. Design, 17, 251-266 (2000) · Zbl 0939.68131 |
| [16] | Jones, M. T.; Plassmann, P. E., Parallel algorithms for adaptive mesh refinement, SIAM J. Sci. Comput, 18, 686-708 (1997) · Zbl 0871.65100 |
| [17] | Kase, K.; Makinouchi, A.; Nakagawa, T.; Suzuki, H.; Kimura, F., Shape error evaluation method of free-form surfaces, Comput. Aided Design, 31, 495-505 (1999) · Zbl 1041.68528 |
| [18] | Kettner, L., Using generic programming for designing a data structure for polyhedral surfaces, Comput. Geom. Theory Appl, 13, 65-90 (1999) · Zbl 0935.68122 |
| [19] | Kossaczký, I., A recursive approach to local mesh refinement in two and three dimensions, J. Comput. Appl. Math, 55, 275-288 (1994) · Zbl 0823.65119 |
| [20] | Maubach, J. M., Local bisection refinement for \(n\)-simplicial grids generated by reflection, SIAM J. Sci. Statist. Comput, 16, 210-227 (1995) · Zbl 0816.65090 |
| [21] | A. Mukherjee, An Adaptive Finite Element Code for Elliptic Boundary Value Problems in Three Dimensions with Applications in Numerical Relativity, Ph.D. Thesis, Penn. State University, 1996; A. Mukherjee, An Adaptive Finite Element Code for Elliptic Boundary Value Problems in Three Dimensions with Applications in Numerical Relativity, Ph.D. Thesis, Penn. State University, 1996 |
| [22] | M. A. Padrón, A 3D Derefinement Algorithm for Tetrahedral Nested Meshes Based on the Skeleton, Ph.D. Thesis, University of Las Palmas de Gran Canaria, 1999 (in Spanish); M. A. Padrón, A 3D Derefinement Algorithm for Tetrahedral Nested Meshes Based on the Skeleton, Ph.D. Thesis, University of Las Palmas de Gran Canaria, 1999 (in Spanish) |
| [23] | Plaza, A., The fractal behaviour of triangular refined/derefined meshes, Comm. Numer. Methods Engrg, 12, 295-302 (1996) · Zbl 0862.65070 |
| [24] | Plaza, A.; Carey, G. F., About local refinement of tetrahedral grids based on bisection, (5th Inter. Mesh. Roundtable, Sandia Corporation (1996)), 123-136 |
| [25] | Plaza, A.; Carey, G. F., Local refinement of simplicial grids based on the skeleton, Appl. Numer. Math, 32, 2, 195-218 (2000) · Zbl 0940.65142 |
| [26] | Plaza, A.; Montenegro, R.; Ferragut, L., An improved derefinement algorithm of nested meshes, (Papadrakakis, M.; Topping, B. H.V., Advances in Post and Preprocessing for Finite Element Technology (1994), Saxe-Coburg: Saxe-Coburg Edinburgh), 175-180 · Zbl 0853.65097 |
| [27] | Plaza, A.; Padrón, M. A.; Carey, G. F., A 3d refinement/derefinement combination for solving evolution problems, Appl. Numer. Math, 32, 4, 401-418 (2000) · Zbl 0946.65076 |
| [28] | Rivara, M. C., Mesh refinement based on the generalized bisection of simplices, SIAM J. Numer. Anal, 2, 604-613 (1984) · Zbl 0574.65133 |
| [29] | Rivara, M. C., A grid generator based on 4-triangles conforming mesh refinement algorithms, Internat. J. Numer. Methods Engrg, 24, 1343-1354 (1987) · Zbl 0621.65124 |
| [30] | Rivara, M. C., Local modification of meshes for adaptive and/or multigrid finite-element methods, J. Comput. Appl. Math, 36, 79-89 (1991) · Zbl 0733.65075 |
| [31] | Rivara, M. C.; Hitschfeld, N.; Simpson, B., Terminal-edges Delaunay (small-angle based) algorithm for the quality triangulation problem, Comput. Aided Design, 33, 263-277 (2001) |
| [32] | Rivara, M. C.; Venere, M., Cost analysis of the longest-side (triangle bisection) refinement algorithm for triangulations, Engrg. Comput, 12, 224-234 (1996) |
| [33] | J.P. Suárez, Graph Based Data Structures for Refinement/Derefinement Algorithms Based on the Longest Edge Bisection, Applications, Ph.D. Thesis, University of Las Palmas de Gran Canaria, 2001 (in Spanish); J.P. Suárez, Graph Based Data Structures for Refinement/Derefinement Algorithms Based on the Longest Edge Bisection, Applications, Ph.D. Thesis, University of Las Palmas de Gran Canaria, 2001 (in Spanish) |
| [34] | Suárez, J. P.; Carey, G. F.; Plaza, A., Graph based data structures for skeleton based refinement algorithms, Comm. Numer. Methods Engrg, 17, 903-910 (2001) · Zbl 0995.65126 |
| [35] | Suárez, J. P.; Plaza, A.; Carey, G. F., Propagation path properties in iterative longest-edge refinement, (12th Inter. Mesh. Roundtable, Sandia Corp (2003)), 79-90 |
| [36] | Weiler, K., Edge-based data structures and concepts for solid modeling in curved-surface environments, IEEE Comput. Graphics Appl, 5, 1, 21-40 (1985) |
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.
