Abstract
We present a preliminary method to generate polyhedral meshes of general non-manifold domains. The method is based on computing the dual of a general tetrahedral mesh. The resulting mesh respects the topology of the domain to the same extent as the input mesh. If the input tetrahedral mesh is Delaunay and well-centered, the resulting mesh is a Voronoi mesh with planar faces. For general tetrahedral meshes, the resulting mesh is a polyhedral mesh with straight edges but possibly curved faces. The initial mesh generation phase is followed by a mesh untangling and quality improvement technique.We demonstrate the technique on some simple to moderately complex domains.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lee, J.M.: Introduction to Topological Manifolds. Springer (2000)
Sieger, D., Alliez, P., Botsch, M.: Optimizing Voronoi Diagrams for Polygonal Finite Element Computations. In: Proceedings of the 19th International Meshing Roundtable, Chattanooga, TN, USA, pp. 335–350 (2010)
Fortune, S.: A sweepline algorithm for Voronoi diagrams. In: Proceedings of the 2nd Annual Symposium on Computational Geometry, Yorktown Heights, NY, USA, pp. 313–322 (1986)
Peric, M.: Flow Simulation using Control Volumes of Arbitrary Polyhedral Shape. ERCOFTAC Bulletin (62) (September 2004), http://www.plmmarketplace.com/The_Advantage_of_polyhedral.pdf , Also see http://www.cd-adapco.com/products/star_ccm_plus/meshing.html
Barber, C.B., Dobkin, D.P., Huhdanpapp, H.T.: The Quickhull algorithm for convex hulls. ACM Trans. on Mathematical Software 22(4), 469–483 (1996), http://www.qhull.org
Owen, S.J.: A Survey of Unstructured Mesh Generation. In: Proceedings of the 7th International Meshing Roundtable, Dearborn, MI, USA, pp. 239–267 (1998)
Aurenhammer, F.: Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys 23(3), 345–405 (1991)
Frey, P.J., George, P.-L.: Mesh Generation - Application to Finite Elements. Wiley, London (2008)
Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006)
Vanderzee, E., et al.: Well-centered Triangulation. SIAM Journal on Scientific Computing 31(6), 4497–4523 (2010)
Escobar, J.M., et al.: Simultaneous Untangling and Smoothing of Tetrahedral Meshes. Computer Methods in Applied Mechanics and Engineering 192(25), 2775–2787 (2003)
Murdoch, P.J., Benzley, S.E.: The Spatial Twist Continuum. In: Proceedings of the 4th International Meshing Roundtable, Albuquerque, NM, USA, pp. 243–251 (1995)
Rycroft, C.H.: Voro++: A three-dimensional Voronoi cell library in C++. Chaos 19, 041111 (2009)
Oaks, W., Paoletti, S.: Polyhedral Mesh Generation. In: Proceedings of the 9th International Meshing Roundtable, New Orleans, LA, USA, pp. 57–67 (2000)
Shephard, M.S., Georges, M.K.: Reliability of Automatic 3-D Mesh Generation. Computer Methods in Applied Mechanics and Engineering 101, 443–462 (1992)
Yan, D.-M., Wang, W., Lévy, B., Liu, Y.: Efficient Computation of 3D Clipped Voronoi Diagram. In: Mourrain, B., Schaefer, S., Xu, G. (eds.) GMP 2010. LNCS, vol. 6130, pp. 269–282. Springer, Heidelberg (2010)
Ebeida, M.S., Mitchell, S.A.: Uniform Random Voronoi Meshes. In: Quadros, W.R. (ed.) Proceedings of the 20th International Meshing Roundtable, vol. 90, pp. 273–290. Springer, Heidelberg (2011)
Knupp, P.: Achieving Finite Element Mesh Quality Via Optimization of the Jacobian Matrix Norm and Associated Quantities. Part II - A Framework for Volume Mesh Optimization and the Condition Number of the Jacobian Matrix. International Journal of Numerical Methods in Engineering 48, 1165–1185 (2000)
Dyadechko, V., Garimella, R.V., Shashkov, M.J.: Reference Jacobian Rezoning Strategy for Arbitrary Lagrangian-Eulerian Methods on Polyhedral Grids. In: Proceedings, 13th International Meshing Roundtable, Williamsburg, VA, Sandia National Laboratories report SAND #2004-3765C, pp. 459–470 (September 2004)
Garimella, R.V., Shashkov, M.J., Knupp, P.M.: Triangular and Quadrilateral Surface Mesh Quality Optimization using Local Parametrization. Computer Methods in Applied Mechanics and Engineering 193(9-11), 913–928 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Garimella, R.V., Kim, J., Berndt, M. (2014). Polyhedral Mesh Generation and Optimization for Non-manifold Domains. In: Sarrate, J., Staten, M. (eds) Proceedings of the 22nd International Meshing Roundtable. Springer, Cham. https://doi.org/10.1007/978-3-319-02335-9_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-02335-9_18
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02334-2
Online ISBN: 978-3-319-02335-9
eBook Packages: EngineeringEngineering (R0)