Top

International Journal of Parallel Programming

Published in:

06-05-2017

MeshCleaner: A Generic and Straightforward Algorithm for Cleaning Finite Element Meshes

Authors: Gang Mei, Salvatore Cuomo, Hong Tian, Nengxiong Xu, Linjun Peng

Published in: International Journal of Parallel Programming | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Mesh cleaning is the procedure of removing duplicate nodes, sequencing the indices of remaining nodes, and then updating the mesh connectivity for a topologically invalid Finite Element mesh. To the best of our knowledge, there has been no previously reported work specifically focused on the cleaning of large Finite Element meshes. In this paper we specifically present a generic and straightforward algorithm, MeshCleaner, for cleaning large Finite Element meshes. The presented mesh cleaning algorithm is composed of (1) the stage of compacting and reordering nodes and (2) the stage of updating mesh topology. The basic ideas for performing the above two stages efficiently both in sequential and in parallel are introduced. Furthermore, one serial and two parallel implementations of the algorithm MeshCleaner are developed on multi-core CPU and/or many-core GPU. To evaluate the performance of our algorithm, three groups of experimental tests are conducted. Experimental results indicate that the algorithm MeshCleaner is capable of cleaning large meshes very efficiently, both in sequential and in parallel. The presented mesh cleaning algorithm MeshCleaner is generic, simple, and practical.

previous article A Framework for Assessing Reusability Using Package Cohesion Measure in Aspect Oriented Systems

next article SIMD Monte-Carlo Numerical Simulations Accelerated on GPU and Xeon Phi

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Alhadeff, A., Leon, S.E., Celes, W., Paulino, G.H.: Massively parallel adaptive mesh refinement and coarsening for dynamic fracture simulations. Eng. Comput. 32(3), 533–552 (2016). doi:10.1007/s00366-015-0431-0 CrossRef

Antepara, O., Lehmkuhl, O., Borrell, R., Chiva, J., Oliva, A.: Parallel adaptive mesh refinement for large-eddy simulations of turbulent flows. Comput. Fluids 110, 48–61 (2015). doi:10.1016/j.compfluid.2014.09.050 MathSciNetCrossRef

Barlas, G.: Chapter 7—the thrust template library. In: Barlas, G. (ed.) Multicore and GPU Programming, pp. 527–573. Morgan Kaufmann, Boston (2015). doi:10.1016/B978-0-12-417137-4.00007-1 CrossRef

Bell, N., Hoberock, J.: Chapter 26–thrust: a productivity-oriented library for CUDA. In: Hwu, W.M.W. (ed.) GPU Computing Gems, Jade Edition, Applications of GPU Computing Series, pp. 359–371. Morgan Kaufmann, Boston (2012). doi:10.1016/B978-0-12-385963-1.00026-5 CrossRef

Bell, N., Hoberock, J., Rodrigues, C.: Chapter 16-thrust: a productivity-oriented library for CUDA. In: Kirk, D.B., Hwu, W.M.W. (eds.) Programming Massively Parallel Processors, 2nd edn, pp. 339–358. Morgan Kaufmann, Boston (2013). doi:10.1016/B978-0-12-415992-1.00016-X CrossRef

Chen, J., Zheng, J., Zheng, Y., Xiao, Z., Si, H., Yao, Y.: Tetrahedral mesh improvement by shell transformation. Eng. Comput. (2016). doi:10.1007/s00366-016-0480-z

Cuomo, S., De Michele, P., Piccialli, F.: 3D data denoising via nonlocal means filter by using parallel gpu strategies. Comput. Math. Methods Med. 2014, 14 (2014). doi:10.1155/2014/523862 CrossRefMATH

Feng, D., Chernikov, A.N., Chrisochoides, N.P.: Two-level locality-aware parallel delaunay image-to-mesh conversion. Parallel Comput. 59, 60–70 (2016). doi:10.1016/j.parco.2016.01.007 MathSciNetCrossRef

Freitas, M.O., Wawrzynek, P.A., Cavalcante-Neto, J.B., Vidal, C.A., Carter, B.J., Martha, L.F., Ingraffea, A.R.: Parallel generation of meshes with cracks using binary spatial decomposition. Eng. Comput. 32(4), 655–674 (2016). doi:10.1007/s00366-016-0444-3 CrossRef

10.

Hatipoglu, B., Ozturan, C.: Parallel triangular mesh refinement by longest edge bisection. SIAM J. Sci. Comput. 37(5), C574–C588 (2015). doi:10.1137/140973840 MathSciNetCrossRefMATH

11.

Hoberock, J., Bell, N.: Thrust—a parallel algorithms library (2017). https://thrust.github.io/

12.

Lage, M., Martha, L.F., Moitinho de Almeida, J.P., Lopes, H.: Ibhm: index-based data structures for 2d and 3d hybrid meshes. Eng. Comput. (2015). doi:10.1007/s00366-015-0395-0

13.

Laug, P., Guibault, F., Borouchaki, H.: Parallel meshing of surfaces represented by collections of connected regions. Adv. Eng. Softw. 103, 13–20 (2017). doi:10.1016/j.advengsoft.2016.09.003 CrossRef

14.

Leischner, N., Osipov, V., Sanders, P.: GPU sample sort. In: 2010 IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pp. 1–10 (2010). doi:10.1109/IPDPS.2010.5470444

15.

Lo, S.: 3D delaunay triangulation of 1 billion points on a PC. Finite Elem. Anal. Des. 102C103, 65–73 (2015). doi:10.1016/j.finel.2015.05.003 CrossRef

16.

Lu, Q.K., Shephard, M.S., Tendulkar, S., Beall, M.W.: Parallel mesh adaptation for high-order finite element methods with curved element geometry. Eng. Comput. 30(2), 271–286 (2014). doi:10.1007/s00366-013-0329-7 CrossRef

17.

Mei, G., Tian, H.: Impact of data layouts on the efficiency of GPU-accelerated IDW interpolation. Springerplus 5, 104 (2016). doi:10.1186/s40064-016-1731-6 CrossRef

18.

Mei, G., Tipper, J.C., Xu, N.: A generic paradigm for accelerating laplacian-based mesh smoothing on the GPU. Arab. J. Sci. Eng. 39(11), 7907–7921 (2014). doi:10.1007/s13369-014-1406-y CrossRef

19.

NVIDIA: CUDA (Compute Unified Device Architecture) (2017). http://www.nvidia.com/object/cuda_home_new.html

20.

OpenMP_ARB: The OpenMP API Specification for Parallel Programming (2017). http://www.openmp.org/

21.

Palma, G., Comerci, M., Alfano, B., Cuomo, S., Michele, P.D., Piccialli, F., Borrelli, P.: 3D non-local means denoising via multi-GPU. In: 2013 Federated Conference on Computer Science and Information Systems, pp. 495–498 (2013)

22.

Ranokphanuwat, R., Kittitornkun, S.: Parallel partition and merge QuickSort (PPMQSort) on multicore CPUs. J. Supercomput. 72(3), 1063–1091 (2016). doi:10.1007/s11227-016-1641-y CrossRef

23.

Sastry, S.P., Shontz, S.M.: A parallel log-barrier method for mesh quality improvement and untangling. Eng. Comput. 30(4), 503–515 (2014). doi:10.1007/s00366-014-0362-1 CrossRef

24.

Satish, N., Harris, M., Garland, M.: Designing efficient sorting algorithms for manycore GPUs. In: 2009 IEEE International Symposium on Parallel Distributed Processing, pp. 1–10 (2009). doi:10.1109/IPDPS.2009.5161005

25.

Satish, N., Kim, C., Chhugani, J., Nguyen, A.D., Lee, V.W., Kim, D., Dubey, P.: Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pp. 351–362. ACM, New York, NY, USA (2010). doi:10.1145/1807167.1807207

26.

Schepke, C., Maillard, N., Schneider, J., Heiss, H.U.: Online mesh refinement for parallel atmospheric models. Int. J. Parallel Prog. 41(4), 552–569 (2013). doi:10.1007/s10766-012-0235-4 CrossRef

27.

Sengupta, S., Harris, M., Zhang, Y., Owens, J.D.: Scan primitives for GPU computing. In: Proceedings of the 22Nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. GH ’07, pp. 97–106. Eurographics Association, Aire-la-Ville, Switzerland, Switzerland (2007)

28.

Si, H.: TetGen, a delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. (2015). doi:10.1145/2629697 MathSciNetMATH

29.

Soner, S., Ozturan, C.: Generating multibillion element unstructured meshes on distributed memory parallel machines. Sci. Program. (2015). doi:10.1155/2015/437480

30.

Xu, N., Tian, H.: Wire frame: a reliable approach to build sealed engineering geological models. Comput. Geosci. 35(8), 1582–1591 (2009). doi:10.1016/j.cageo.2009.01.002 CrossRef

31.

Xu, N., Tian, H., Kulatilake, P.H., Duan, Q.: Building a three dimensional sealed geological model to use in numerical stress analysis software: a case study for a dam site. Comput. Geotech. 38(8), 1022–1030 (2011). doi:10.1016/j.compgeo.2011.07.013 CrossRef

32.

Yilmaz, Y., Ozturan, C.: Using sequential NETGEN as a component for a parallel mesh generator. Adv. Eng. Softw. 84, 3–12 (2015). doi:10.1016/j.advengsoft.2014.12.013 CrossRef

Title: MeshCleaner: A Generic and Straightforward Algorithm for Cleaning Finite Element Meshes
Authors: Gang Mei
Salvatore Cuomo
Hong Tian
Nengxiong Xu
Linjun Peng
Publication date: 06-05-2017
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 3/2018
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-017-0507-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2018

Guest Editorial for Programming Models and Algorithms for Data Analysis in HPC Systems

Multilevel Data Processing Using Parallel Algorithms for Analyzing Big Data in High-Performance Computing

Adapting MCP and HLFET Algorithms to Multiple Simultaneous Scheduling

A GPU Implementation of OLPCA Method in Hybrid Environment

A Framework for Assessing Reusability Using Package Cohesion Measure in Aspect Oriented Systems

SIMD Monte-Carlo Numerical Simulations Accelerated on GPU and Xeon Phi

Premium Partner