[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Untangling polygonal and polyhedral meshes via mesh optimization

  • Original Article
  • Published:
Engineering with Computers Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

We propose simple and efficient optimization-based untangling strategies for 2D polygonal and 3D polyhedral meshes. The first approach uses a size-based mesh metric, which eliminates inverted elements by averaging element size over the entire mesh. The second method uses a hybrid quality metric, which untangles inverted elements by simultaneously averaging element size and improving element shape. The last method using a variant of the hybrid quality metric gives a high penalty for inverted elements and employs an adaptive sigmoid function for handling various mesh sizes. Numerical experiments are presented to show the effectiveness of the proposed untangling strategies for various 2D polygonal and 3D polyhedral meshes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Peric M (2004) Flow simulation using control volumes of arbitrary polyhedral shape. ERCOFTAC Bulletin (62)

  2. Aurenhammer F (1991) Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput Surv 23(3):345–405

    Article  Google Scholar 

  3. Batdorf M, Freitag LA, Ollivier-Gooch C (1997) Computational study of the effect of unstructured mesh quality on solution efficiency ,13th Annual AIAA Computational Fluid Dynamics Conference, AIAA

  4. Garimella R, Kim J, Berndt M (2013) Polyhedral mesh generation and optimization for non-manifold domains, $22nd International Meshing Roundtable, Sandia National Laboratories, pp 239–250

  5. Spiegel M, et al. (2009) Tetrahedral and polyhedral mesh evaluation for cerebral hemodynamic simulation—a comparison, 31st Annual International Conference of the IEEE EMBS, Sandia National Laboratories, pp 2787–2790

  6. Escobar JM et al (2003) Simultaneous untangling and smoothing of tetrahedral meshes. Comput Methods Appl Mech Eng 192(25):2775–2787

    Article  MATH  Google Scholar 

  7. Franks JW, Knupp PM (2010) A new strategy for untangling 2D meshes via node-movement, CSRI Summer Proceedings, Sandia National Laboratories, pp 152–165

  8. Knupp PM (2001) Hexahedral and tetrahedral mesh untangling. Eng Comput 17(3):261–268

    Article  MATH  Google Scholar 

  9. Dyadechko V, Garimella RV, Shashkov MJ (2004) Reference Jacobian re-zoning strategy for arbitrary Lagrangian–Eulerian methods on polyhedral grids, 13th International Meshing Roundtable, Sandia National Laboratories, pp 459–470

  10. Sastry SP, Shontz SM, Vavasis SA (2011) A log-barrier method for mesh quality improvement, 20th International Meshing Roundtable, Sandia National Laboratories, pp 329–346

  11. Knupp PM (2007) Updating meshes on deforming domains: an application of the target-matrix paradigm. Commun Num Meth Engr 24:467–476

    Article  MathSciNet  Google Scholar 

  12. Benitez D, Rodriguez E, Escobar JM, Montenegro R (2013) Performance evaluation of a parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes, 22nd International Meshing Roundtable, Sandia National Laboratories, pp 579–598

  13. Kim J, Panitanarak T, Shontz SM (2013) A multiobjective mesh optimization framework for mesh quality improvement and mesh untangling. Int J Numer Methods Eng 94(1):20–42

    Article  MathSciNet  Google Scholar 

  14. Kim J, Garimella R, Berndt M (2013) A practical approach for solving mesh optimization problems using Newton’s method, 22nd International Meshing Roundtable, Sandia National Laboratories

  15. Bhowmick S, Shontz SM (2010) Towards high-quality, untangled meshes via a force-directed graph embedding approach. Proc Int Conf Comput Sci 1(1):357–366

    Article  Google Scholar 

  16. Danczyk J, Suresh K (2012) Finite element analysis over tangled meshes, Proceeding of the ASME 2012 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, Chicago, IL

  17. Yan DM, Wenping W, Levy B (2010) Efficient computation of 3D clipped Voronoi diagram, advances in geometric modeling and processing, pp 269–282

  18. Nocedal J, Wright S (2006) Numerical optimization. Springer, Berlin

    MATH  Google Scholar 

  19. Knupp P (2000) Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II: A framework for volume mesh optimization. Int J Numer Methods Engrg 48:1165–1185

    Article  MATH  Google Scholar 

  20. Danczyk J, Suresh K (2013) Finite element analysis over tangled simplicial meshes: theory and implementation. Finite Elem Anal Des 70–71:57–67

    Article  MathSciNet  Google Scholar 

  21. Park J, Shontz SM, Drapaca CS (2013) A combined level set/mesh warping algorithm for tracking brain and cerebrospinal fluid evolution in hydrocephalic patients. Image-based geometric modeling and mesh generation, lecture notes in computational vision and biomechanics, Springer 3:107–141

  22. Ebeida M, Mitchell S (2011) Uniform random Voronoi meshes, 20th International Meshing Roundtable, Sandia National Laboratories

Download references

Acknowledgments

This research was begun when the first author was a Postdoctoral Fellow at the Los Alamos National Laboratory. The first author would like to thank to Rao Garimella at the Los Alamos National Laboratory for providing test meshes and helpful discussions. The first author was supported by the Incheon National University Research Grant in 2013. The authors also wish to thank the three anonymous referees for their careful reading of the paper and for their helpful suggestions.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Incheon National University, Incheon, 406-772, South Korea

    Jibum Kim

  2. Department of Electronics Engineering, Incheon National University, Incheon, 406-772, South Korea

    Jaeyong Chung

Authors
  1. Jibum Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jaeyong Chung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jaeyong Chung.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kim, J., Chung, J. Untangling polygonal and polyhedral meshes via mesh optimization. Engineering with Computers 31, 617–629 (2015). https://doi.org/10.1007/s00366-014-0379-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00366-014-0379-5

Keywords

Search

Navigation