research-article

Public Access

On Orienting Edges of Unstructured Two- and Three-Dimensional Meshes

Authors:

Michael Anderson,

Wolfgang Bangerth,

William L. BarthAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 44, Issue 1

Article No.: 5, Pages 1 - 22

https://doi.org/10.1145/3061708

Published: 24 July 2017 Publication History

Abstract

Finite element codes typically use data structures that represent unstructured meshes as collections of cells, faces, and edges, each of which require associated coordinate systems. One then needs to store how the coordinate system of each edge relates to that of neighboring cells. However, we can simplify data structures and algorithms if we can a priori orient coordinate systems in such a way that the coordinate systems on the edges follow uniquely from those on the cells by rule.

Such rules require that every unstructured mesh allow the assignment of directions to edges that satisfy the convention in adjacent cells. We show that the convention chosen for unstructured quadrilateral meshes in the deal.II library always allows to orient meshes. It can therefore be used to make codes simpler, faster, and less bug prone. We present an algorithm that orients meshes in O(N) operations. We then show that consistent orientations are not always possible for 3D hexahedral meshes. Thus, cells generally need to store the direction of adjacent edges, but our approach also allows the characterization of cases where this is not necessary. The 3D extension of our algorithm either orients edges consistently, or aborts, both within O(N) steps.

References

[1]

M. Ainsworth and J. Coyle. 2003. Hierarchic finite element bases on unstructured tetrahedral meshes. International Journal for Numerical Methods in Engineering 58, 2103--2130.

[2]

W. Bangerth, R. Hartmann, and G. Kanschat. 2007. deal.II—A general purpose object oriented finite element library. ACM Transactions on Mathematical Software 33, 4, Article No. 24.

Digital Library

[3]

W. Bangerth, T. Heister, L. Heltai, G. Kanschat, M. Kronbichler, M. Maier, B. Turcksin, and T. D. Young. 2015. The deal.II library, version 8.2. Archive of Numerical Software 3, 100, 1--8.

[4]

P. Bastian, M. Blatt, A. Dedner, C. Engwer, R. Klöfkorn, R. Kornhuber, M. Ohlberger, and O. Sander. 2008. A generic grid interface for parallel and adaptive scientific computing. Part II: Implementation and tests in DUNE. Computing 82, 121--138.

Digital Library

[5]

E. Bertolazzi and G. Manzini. 2002. Algorithm 817: P2MESH: Generic object-oriented interface between 2-D unstructured meshes and FEM/FVM-based PDE solvers. ACM Transactions on Mathematical Software 28, 2, 101--132.

Digital Library

[6]

Glen E. Bredon. 1993. Topology and Geometry. Graduate Texts in Mathematics, Vol. 139. Springer.

[7]

C. D. Cantwell, D. Moxey, A. Comerford, A. Bolis, G. Rocco, G. Mengaldo, D. De Grazia, et al. 2015. Nektar++: An open-source spectral/hp element framework. Computer Physics Communications 192, 205--219.

[8]

C. Geuzaine and J.-F. Remacle. 2009. Gmsh: A three-dimensional finite element mesh generator with built-in pre- and post-processing facilities. International Journal for Numerical Methods in Engineering 79, 1309--1331.

[9]

F. Haglund and D. T. Wise. 2008. Special cube complexes. Geometric and Functional Analysis 17, 1551--1620.

[10]

G. Hetyei. 1995. On the Stanley ring of a cubical complex. Discrete and Computational Geometry 14, 305--330.

Digital Library

[11]

M. Homolya and D. A. Ham. 2015. A parallel edge orientation algorithm for quadrilateral meshes. arXiv:1505.03357. http://arxiv.org/abs/1505.03357

[12]

B. Kirk, J. W. Peterson, R. H. Stogner, and G. F. Carey. 2006. libMesh: A C++ library for parallel adaptive mesh refinement/coarsening simulations. Engineering with Computers 22, 3--4, 237--254.

Digital Library

[13]

A. G. Kurosh. 1963. Lectures on General Algebra. Chelsea Publishing.

[14]

J. Lee. 2011. Introduction to Topological Manifolds (2nd ed.). Graduate Texts in Mathematics, No. 202. Springer.

[15]

R. Lidl and G. Pilz. 1998. Applied Abstract Algebra (2nd ed.). Springer, New York, NY.

[16]

J. Munkres. 1996. Elements of Algebraic Topology. Westview Press.

[17]

M. E. Rognes, R. C. Kirby, and A. Logg. 2009. Efficient assembly of H(div) and H(curl) conforming finite elements. SIAM Journal on Scientific Computing 31, 4130--4151.

Digital Library

[18]

A. Schwartz and G. M. Ziegler. 2004. Construction techniques for cubical complexes, odd cubical 4-polytopes, and prescribed dual manifolds. Experimental Mathematics 13, 385--413.

[19]

M. Spivak. 1965. Calculus on Manifolds. Perseus Books.

[20]

D. Teleaga and J. Lang. 2008. Numerically Solving Maxwell’s Equations: Implementation Issues for Magnetoquasistatics in KARDOS. Technical Report. TU Darmstadt.

[21]

S. Zaglmayr. 2006. High Order Finite Element Methods for Electromagnetic Field Computation. Ph.D. Dissertation. Johannes Kepler University, Linz, Austria.

Cited By

Albornoz‐Basto ADenny BBrio M(2024) An Unstructured Mesh Coordinate Transformation‐Based FDTD Method International Journal of Numerical Modelling: Electronic Networks, Devices and Fields10.1002/jnm.330737:6Online publication date: 6-Nov-2024
https://doi.org/10.1002/jnm.3307
Amor-Martin AGarcia-Castillo L(2023)Second-Order Nédélec Curl-Conforming Hexahedral Element for Computational ElectromagneticsIEEE Transactions on Antennas and Propagation10.1109/TAP.2022.321655471:1(859-868)Online publication date: Jan-2023
https://doi.org/10.1109/TAP.2022.3216554
Klinkovský JOberhuber TFučík RŽabka V(2022)Configurable Open-source Data Structure for Distributed Conforming Unstructured Homogeneous Meshes with GPU SupportACM Transactions on Mathematical Software10.1145/353616448:3(1-30)Online publication date: 20-May-2022
https://dl.acm.org/doi/10.1145/3536164
Show More Cited By

Index Terms

On Orienting Edges of Unstructured Two- and Three-Dimensional Meshes
1. Applied computing
  1. Physical sciences and engineering
    1. Mathematics and statistics
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Generating well-shaped d-dimensional Delaunay meshes
Computing and combinatorics

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It ...
Delaunay Triangular Meshes in Convex Polygons

An algorithm for producing a triangular mesh in a convex polygon is presented. It is used in a method for the finite element triangulation of a complex polygonal region of the plane in which the region is decomposed into convex polygons. The interior ...
Adaptive skin meshes coarsening for biomolecular simulation

In this paper, we present efficient algorithms for generating hierarchical molecular skin meshes with decreasing size and guaranteed quality. Our algorithms generate a sequence of coarse meshes for both the surfaces and the bounded volumes. Each coarser ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 44, Issue 1

March 2018

308 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3071076

Editor:
Daniel Kressner
EPF Lausanne, Switzerland

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2017

Accepted: 01 March 2017

Revised: 01 October 2016

Received: 01 December 2015

Published in TOMS Volume 44, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation
Computational Infrastructure in Geodynamics initiative (CIG) through the National Science Foundation
University of California at Davis

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
385
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)10

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Albornoz‐Basto ADenny BBrio M(2024) An Unstructured Mesh Coordinate Transformation‐Based FDTD Method International Journal of Numerical Modelling: Electronic Networks, Devices and Fields10.1002/jnm.330737:6Online publication date: 6-Nov-2024
https://doi.org/10.1002/jnm.3307
Amor-Martin AGarcia-Castillo L(2023)Second-Order Nédélec Curl-Conforming Hexahedral Element for Computational ElectromagneticsIEEE Transactions on Antennas and Propagation10.1109/TAP.2022.321655471:1(859-868)Online publication date: Jan-2023
https://doi.org/10.1109/TAP.2022.3216554
Klinkovský JOberhuber TFučík RŽabka V(2022)Configurable Open-source Data Structure for Distributed Conforming Unstructured Homogeneous Meshes with GPU SupportACM Transactions on Mathematical Software10.1145/353616448:3(1-30)Online publication date: 20-May-2022
https://dl.acm.org/doi/10.1145/3536164
Weiss MKalscheuer TRen Z(2022)Spectral element method for 3-D controlled-source electromagnetic forward modelling using unstructured hexahedral meshesGeophysical Journal International10.1093/gji/ggac358232:2(1427-1454)Online publication date: 11-Sep-2022
https://doi.org/10.1093/gji/ggac358
Kronbichler MKormann K(2019)Fast Matrix-Free Evaluation of Discontinuous Galerkin Finite Element OperatorsACM Transactions on Mathematical Software10.1145/332586445:3(1-40)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3325864
Olm MBadia SMartín A(2019)On a general implementation of h- and p-adaptive curl-conforming finite elementsAdvances in Engineering Software10.1016/j.advengsoft.2019.03.006Online publication date: Mar-2019
https://doi.org/10.1016/j.advengsoft.2019.03.006
Badia SMartín APrincipe J(2017)FEMPAR: An Object-Oriented Parallel Finite Element FrameworkArchives of Computational Methods in Engineering10.1007/s11831-017-9244-125:2(195-271)Online publication date: 11-Oct-2017
https://doi.org/10.1007/s11831-017-9244-1

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents