Proceedings of the 18th International Meshing Roundtable (eBook)

Brett W. Clark (Herausgeber)

eBook Download: PDF

2009 | 2010
XIV, 654 Seiten
Springer Berlin (Verlag)
978-3-642-04319-2 (ISBN)

Infos

This volume contains the articles presented at the 18th International Meshing Roundtable (IMR) organized, in part, by Sandia National Laboratories and held October 25-28, 2009 in Salt Lake City, Utah, USA. The volume presents recent results of mesh generation and adaptation which has applications to finite element simulation. It introduces theoretical and novel ideas with practical potential.

Inhalt

Preface 4
Organization 5
Reviewers 7
Contents 9
Session 1A: Surface Meshing 9
Size Function Smoothing Using an Element Area Gradient 13
Introduction 13
Size Function Smoothing Using an Element Area Gradient 14
Size Function Smoothing Tools in SMS 21
Examples 22
Conclusion 23
References 23
Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge Hammering, and Face Lifting 25
Introduction 25
Previous Work 26
Typical Sources of a Self Intersection 27
Detail of the Proposed Method 30
Improvement Criteria 30
Edge Swapping 31
Edge Hammering 31
Face Lifting 33
Order-Dependency Issues 35
Potential Expansions and Discussions 36
Expanding the Proposed Method for a Quadrilateral Mesh 36
Locally Adjusting the Clearance Requirement 37
Boundary Fidelity Issue 38
Examples 38
Conclusions 40
References 40
Conformal Refinement of Unstructured Quadrilateral Meshes 42
Introduction 42
Previous Work 43
Description of Mesh Refinement/Coarsening Algorithm 45
Overview 45
Subdivision Templates 45
Coarsening 47
Refinement 48
Remapping or Solution Transfer 50
Results 50
Discussion 52
References 54
Guaranteed-Quality All-Quadrilateral Mesh Generation with Feature Preservation 56
Introduction 56
Previous Work 57
Guaranteed-Quality Meshing of Point Cloud 59
Guaranteed-Quality Meshing of Smooth Curves 61
Curve Decomposition 61
Adaptive Quadtree Construction 61
Buffer Zone Clearance 62
Template Implementation 63
First Buffer Layer Construction 66
Second Buffer Layer Construction 69
Sharp Feature and Boundary Layer 69
Results 71
Conclusion and Future Work 73
References 73
Session 1B: Hexahedral Meshing 9
Advances in Octree-Based All-Hexahedral Mesh Generation: Handling Sharp Features 75
Introduction 75
Motivation 75
Limitations of Available Octree-Based Software 76
Objective 76
Octree Building 77
An Almost Regular Octree 77
Subdivision Criteria 77
Balancing and Pairing Rules 78
Polyhedral Cutting 79
Connecting Hanging Vertices 79
2-Dimensional Case 80
3-Dimensional Case 80
Dual-Mesh Generation 82
2-Dimensional Case 82
3-Dimensional Case 82
Subdomains Coloring 84
Geometry and Features Detection 85
Buffer-Layer Insertion 86
Smoothing 87
Conclusion 89
Some Results 90
References 94
Conforming Hexahedral Mesh Generation via Geometric Capture Methods 95
Introduction 95
Background 96
Dual Sheets and Columns 96
Sheet Operations 97
Fundamental Hexahedral Meshes 98
Theory and Assertions 99
Non-conforming Meshes to Fundamental Meshes 100
Assertion on Hexahedral Quality 101
Algorithm 102
Establishing 2-Manifolds 102
Capturing Geometric Topology 103
Fundamental Conversions 105
Mesh Optimization 106
Examples 107
Alternate Methods 109
Tri-valent Vertices 109
Regularizing Mesh Near Boundaries 110
Conclusion 110
References 111
Efficient Hexahedral Mesh Generation for Complex Geometries Using an Improved Set of Refinement Templates 113
Introduction 113
Refinement Templates 114
Options for Hexahedral Mesh Generation 117
Temporal Rotation 117
Temporal Local Inflation 117
Applications 120
Ramses Model 123
Pediatric Brain Model 123
Three-Year-Old Child Model 123
Conclusions 123
References 124
Embedding Features in a Cartesian Grid 126
Background 126
Feature Embedding 129
Embedding Procedures 132
Embedding Vertices 133
Embedding Curves 138
Embedding Surfaces 141
Embedding Volumes 143
Completing the Mesh 144
Conclusion 145
References 146
Session 2A: Optimization 10
Label-Invariant Mesh Quality Metrics 148
Measuring Quality $Within$ Mesh Elements 148
Label-Invariance of Quality Metrics 152
Linear Planar Triangles 154
The Linear Map 154
The Reference Element 154
Label-Invariance 154
Quadratic Planar Triangles 156
The Quadratic Map 156
Symmetry Points for Maps to Triangular Elements 157
Symmetry Relation for Jacobian of the Quadratic Map 157
Label-Invariance 158
The Shape Quality of Quadratic Triangles 161
Summary 162
References 163
Perturbing Slivers in 3D Delaunay Meshes 165
Introduction 165
Slivers 165
Tetrahedron Quality 166
Previous Work 167
Contribution 170
Algorithm 171
Circumsphere Radius 173
Volume 174
Random Perturbation 175
Experiments and Results 175
Conclusion and Discussion 179
References 180
Mesh Smoothing Algorithms for Complex Geometric Domains 182
Introduction 182
Review of Smoothing Algorithms 183
Laplacian Smoothing 184
Smart Laplacian Smoothing 185
Centroidal Voronoi Tessellation (CVT)-Based Smoothing 185
Optimal Delaunay Triangulation (ODT)-Based Smoothing 186
Angle-Based Smoothing (AB) 187
Well-Centered Triangulation (WCT) Smoothing 188
New Smoothing Algorithms 189
Modifying Existing Algorithms for Complex Geometry 189
Centroid of Off-Centers (CO) 191
Distance Weighted Centroid of Incenters (WCI) 191
Sliced-Petal Smoothing 192
Results and Discussions 192
Implementation and Data Sets 193
Experiments 193
Future Work 197
References 198
A Novel Method for Surface Mesh Smoothing: Applications in Biomedical Modeling 201
Introduction 201
Surface Mesh Smoothing Algorithm 203
Initial Mesh Smoothing 203
Curvature Estimation and Labeling 206
Adaptive Mesh Smoothing 207
Mesh Quality Improvement 208
Implementation and Results 211
Conclusions 214
References 215
Quality Improvement of Non-manifold Hexahedral Meshes for Critical Feature Determination of Microstructure Materials 217
Introduction 217
Previous Work 219
Data Acquisition and All-Hex Mesh Generation 221
Vertex Classification 221
Quality Improvement of Non-manifold Hex Meshes 223
Modified Pillowing for Non-manifold Boundaries 223
Fairing and Regularization for Curves 224
Geometric Flow and Optimization 227
Finite Element Analysis and Results 228
Conclusion and Future Work 233
References 234
Session 2B: Geometry 10
Automatic CAD Models Comparison and Re-meshing in the Context of Mechanical Design Optimization 237
Introduction 237
Comparison between CAD Models 239
Vectorial Space, Metric Tensor and Initia Tensor 239
Comparison between CAD Models 241
Automatic Remeshing 243
Algorithm 243
Results 248
Conclusion 250
References 250
Distance Solutions for Medial Axis Transform 252
Introduction 252
Solutions of Eikonal Equation 253
H-J/Eikonal Equation for $d$ 253
Domain and Initialization 254
Distance Solution Examples 255
Medial Axis Transform via Distance Field: $d$ MAT 256
Feature Detection Criteria 257
Thinning and Representation 259
Solution Superposition 263
Conclusion 265
A Finite Difference Solution Procedures 266
A.1 Fast-Marching Method 266
A.2 Fast-Sweeping Method 267
References 268
Automatic Non-manifold Topology Recovery and Geometry Noise Removal 271
Introduction 271
Algorithm Description 273
Pre-requisites 273
The Optional e Tolerance Parameter 274
Pre-processing 274
Vertex Association and Projection 274
Edge Association 275
Topology Post-processing 276
Applications 279
Conclusion 282
References 282
A New Procedure to Compute Imprints in Multi-sweeping Algorithms 284
Introduction 284
The Multi-sweeping Method 286
Basic Definitions 287
Sweep Node 287
Loop Geometry Engine 287
Control Loop 288
Computational Domain 289
Loop Face Projection and Imprinting 290
Loop Face Projection 290
Loop Face Imprinting Pre-process 291
Mapping of Sweep Nodes from the Computational Domain to a Source Surface 291
Loop Face Imprinting 293
Final Location of Inner Sweep Nodes 295
Loop Edge Meshing and Volume Decomposition 297
Examples 298
Conclusions 300
References 301
Defeaturing CAD Models Using a Geometry-Based Size Field and Facet-Based Reduction Operators 303
Introduction 303
Background 305
Defeaturing Algorithm 308
Obtaining a Discrete Model 310
Detection of Features for Suppression 310
Suppressing Features 315
Meshing the Defeatured Model 316
Results 316
Conclusion 319
References 319
Session 3A: Parallel & Hybrid
Towards Exascale Parallel Delaunay Mesh Generation 321
Introduction 321
Background 323
Related Work in Parallel Mesh Generation 323
Related Work in Parallel Runtime Systems 324
Multi-layered Runtime System 325
Multi-layered Parallel Mesh Generation 327
Domain Decomposition Step 329
Parallel Delaunay Mesh Generation Step 329
Putting It All Together 331
Preliminary Data 331
Conclusions 335
References 336
On the Use of Space Filling Curves for Parallel Anisotropic Mesh Adaptation 339
Introduction 339
A Brief Overview of the Mesh Adaptation Platform 341
The Considered Test Cases 342
The Hilbert Space Filling Curve 343
Mesh Entities Renumbering 343
Exploiting Space Filling Curves for Efficient Shared-Memory Multi-threaded Parallelization 346
A Shared Memory Multi-threaded Parallelization 346
Parallelizing the Flow Solver 348
Parallelizing the Error Estimate 350
Exploiting Space Filling Curves for Efficient Out-of-Core Parallelization 351
A Fast Mesh Partitioning Algorithm 351
Parallelizing the Local Adaptive Remesher 353
Parallelizing the Solution Interpolation 355
Conclusion 356
References 357
Mesh Insertion of Hybrid Meshes 360
Introduction 360
An Optimal Non-manifold Hybrid Mesh Data Structure (NHMD) 362
Mesh Insertion Algorithm 365
Detection of the Undesired Entities of the Target Mesh 366
Connecting One-Dimensional and Two-Dimensional Entities to the Tool Mesh 368
Connecting Three-Dimensional Entities to the Tool Mesh 369
Examples 373
Conclusion and Future Work 374
References 375
Tensor-Guided Hex-Dominant Mesh Generation with Targeted All-Hex Regions 377
Introduction 377
Related Work 380
Technical Approach and Preliminaries 381
Metric Field Representation, Support, and Operations 382
Generating Metric Tensor Fields 384
Boundary Field Form-Fitting 384
Interior Form-Fitting 385
Hex-Dominant Mesh Generation 386
Topological Insertion Operators and Face Groups 386
Planning and Scheduling Insertions 388
Element Shaping 389
Boundary Conformity 390
Hex-Dominant Mesh Finalization 390
Results 390
Conclusion 393
References 394
Session 3B: Applications 11
Using Parameterization and Springs to Determine Aneurysm Wall Thickness 397
Introduction 397
Previous Work 398
Wall-Thickness Estimation 400
Deformation through Parameterization 401
Relaxation Using Springs 404
Thickness Calculation 405
Boundary-Layer Meshing 406
Results 407
Conclusion 412
References 412
Hybrid Mesh Generation for Reservoir Flow Simulation in CPG Grids 415
Problem Statement 416
Mathematical Model of Flow Simulation 416
Numerical Schemes 417
Meshes Overview 417
Hybrid Meshes and Non Cartesian Grids 418
General Methodology and Its Restriction 418
A Solution Using Grid Deformation 418
Hybrid Meshes for Real Grids with High Deformation 419
Mapping the Cavity Space 419
Correction of the Mapping 421
Numerical Example 424
Conclusions 426
References 427
VECTIS Mesher – A 3D Cartesian Approach Employing Marching Cubes 428
Introduction 428
Context of the Mesher in VECTIS-MAX System 430
Requirements for Mesh Quality 431
General Approach 431
Scaling 432
Dual Levels 432
Shoeboxes 433
In/Out Status 433
Box Generation 433
Types of Refinement 435
Generation of Patches 435
Tying of Patches 437
Generation of Inner Faces 438
Removal of Small Cells 438
Problem of Concave Cells 439
Examples of Generated Meshes 440
Description of the Meshing Algorithm 441
Tools Helping to Decrease Time and Memory Demands 443
Features Improving Time Efficiency 443
Features Improving Memory Efficiency 444
References 445
Shape Operator Metric for Surface Normal Approximation 446
Introduction 446
Framework 447
Surface Approximation 448
Normal Approximation 448
Behavior 449
Shape Operator Metric for Normal Approximation 450
Implementation of SOM 451
Results 452
Numerical Validation 454
Summary and Conclusion 457
References 457
Appendix 458
Appendix A: Distance Tightness Bounds 458
Appendix B: Limit Approximation Efficiency 459
Appendix C: Shape Operator Metric and Aspect Ratio 460
Session 4: Tetrahedral Meshing 11
The Meccano Method for Automatic Tetrahedral Mesh Generation of Complex Genus-Zero Solids 461
Introduction 461
Meccano Technique Algorithm 462
Meccano Technique for a Complex Genus-Zero Solid 463
Meccano 464
Mapping from Cube Faces to Solid Surface Patches 465
Coarse Tetrahedral Mesh of the Meccano 467
Local Refined Tetrahedral Mesh of the Meccano 467
External Node Mapping on Solid Boundary 470
Relocation of Inner Nodes 470
Solid Mesh Optimization: Untangling and Smoothing 471
Test Examples 472
Example 1: Bust 472
Example 2: Bunny 474
Conclusions and Future Research 476
References 477
Collars and Intestines: Practical Conforming Delaunay Refinement 479
Introduction 479
Preliminaries 480
Definitions 480
Generic Delaunay Refinement Algorithm 481
Delaunay Refinement in 2D 481
Collar Protection Region 482
Intestine Protection Region 484
Delaunay Refinement in 3D 485
Collar Protection Region 485
Intestine Protection Region 488
Implementation Details and Examples 492
References 494
An Analysis of Shewchuk’s Delaunay Refinement Algorithm 496
Introduction 496
The Algorithm 498
Proof of Termination 499
Parent Sequences 504
Output Edge Lengths 508
Vertex Degrees 509
Output Mesh Size 511
Conclusions 514
References 514
Hexagonal Delaunay Triangulation 516
Introduction 516
Previous Work 517
Hexagonal Subdivision 518
Subdividing a Hexagon 518
Reverse Operation 518
Adaptive Refinement 519
Simple Refinement 519
Refinement Rules 519
Extracting the Dual Mesh 520
Proving Angles 520
Extended Refinement 521
Classification of Hexagons 522
Extended Refinement Rules 523
Local Coarsening 523
Modifications to the Dual Mesh 524
Properties 528
Angle Bounds 528
Aspect Ratio 529
Minimum Triangle Size 529
Delaunay Property 530
Triangulating Planar Straight-Line Graphs 530
Input Line Segment 530
Extended Refinement Rules 530
Line intersections 531
Adding Triangles 532
Results 532
Conclusion and Future Work 534
References 535
Tetrahedral Mesh Improvement Using Multi-face Retriangulation 536
Introduction and Motivation 536
Related Work 538
Mesh Smoothing 539
Topological Operations 540
Vertex Insertion 540
Tetrahedral Mesh Quality Improvement 541
Multi-face Retriangulation 542
Edge Collapse 543
Quality Measures 543
Implementation 544
Tests and Results 546
Discussion and Future Work 550
References 551
Session 5: Adaptivity 12
Automatic All Quadrilateral Mesh Adaption through Refinement and Coarsening 553
Introduction 553
Background 554
Current Methods 554
Concurrent Refinement and Coarsening 555
Automated Mesh Adaptation 555
Sizing Functions 555
Tools and Requirements 556
Algorithm 558
Algorithm Example 558
Examples 564
Nosecone 564
Plate with Hole in Tension 565
Conclusion 567
Further Research 568
References 569
Optimal 3D Highly Anisotropic Mesh Adaptation Based on the Continuous Mesh Framework 571
Continuous Mesh Framework 574
Interpolation Error: Discrete-Continuous Duality 576
Optimal Control of the Interpolation Error in L$^{p}$ Norm 580
3D Numerical Validations 582
References 589
Anisotropic Mesh Adaptation for Solution of Finite Element Problems Using Hierarchical Edge-Based Error Estimates 591
Introduction 591
Interpolation Error Analysis 592
Edge-Based Error Estimates and a Tensor Metric 592
Metrics for the $L^{p}$-norm of Error and Its Gradient 596
Extension to General Functions 597
On Selection of a$_{k}$ 598
Error Estimates as Functions of N$_{h}$ 598
Mesh Adaptation Algorithm 599
Numerical Results 599
Interpolation Problems 599
Applications to PDEs 601
Conclusion 605
References 605
On 3D Anisotropic Local Remeshing for Surface, Volume and Boundary Layers 607
Introduction 607
Metric-Based Anisotropic Local Remeshing 608
Metric Tensors in Mesh Adaptation 608
Adaptive CFD Simulations 610
Metric-Based Estimates 611
Techniques for Enhancing Robustness and Performance 611
L$^{p}$ Norm Interpolation Error 613
Geometric Estimate for Surfaces 614
Boundary Layers Metric 616
Quality-Driven Local Mesh Operators 618
Insertion and Collapse 618
Using the Boundary Layers Metric 622
Conclusions and Future Work 624
References 624
A Comparison of Gradient- and Hessian-Based Optimization Methods for Tetrahedral Mesh Quality Improvement 627
Introduction 627
Problem Statement 628
Element and Mesh Quality 628
Aspect Ratio Quality Metric 629
Inverse Mean Ratio Quality Metric 629
Vertex Condition Number Quality Metric 630
Quality Improvement Problem 630
Improvement Algorithms 630
Steepest Descent Method 631
Conjugate Gradient Method 631
Quasi-Newton Method 631
Trust-Region Method 631
Feasible Newton Method 632
Numerical Experiments 632
Increasing Problem Size 633
Initial Mesh Configuration 636
Graded Meshes 640
Mesh Quality Metric 640
Future Work 642
References 643
Author Index 645
Index by Affiliation 647

Produkt-Details

• Erscheint lt. Verlag: 26.11.2009
• Zusatzinfo: XIV, 654 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik ► Bauwesen
• Themenwelt: Technik ► Maschinenbau
• Schlagworte: 3D • 3D graphics • adaptive finite elements • algorithm • algorithms • Analysis • Computational Geometry • Computer Graphics • Mesh Generation • Meshing • Modeling • Numerical analysis • Operator • Optimization • Simulation • Topology • Triangulation
• ISBN-10: 3-642-04319-4 / 3642043194
• ISBN-13: 978-3-642-04319-2 / 9783642043192