Geometry-aware partitioning of complex domains for parallel quad meshing. (April 2017)

• Record Type: Journal Article
• Authors: Li, Xin; Yu, Wuyi; Liu, Celong
• Is Part Of: Computer aided design. Volume 85(2017)
• Page Start: 20
• Page End: 33
• Publication Date: 2017-04
• Subjects: Geometry-aware data partitioning -- Parallel mesh generation -- Large-scale regular meshing; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2016.07.014
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We develop a partitioning algorithm to decompose complex 2D data into small and simple subregions suitable for effective distributed and parallel quadrilateral mesh generation. To support high-quality quad mesh generation, the partitioning reduces to solving an integer quadratic optimization problem with linear constraints. Directly solving this problem is expensive for large-scale data. Hence, we also suggest a more efficient two-step algorithm to obtain an approximate solution. First, we partition the region into a set of cells using L ∞ Centroidal Voronoi Tessellation (CVT), then we solve a graph partitioning on the dual graph of this CVT to minimize the total partitioning boundary length, while enforcing the load balancing and each subregion's connectivity. With this decomposition, subregions are distributed to multiple processors for parallel mesh generation. Through comparisons on the quality of the final meshes and the performance of simulations run on these meshes, we show that our decomposition algorithm outperforms existing partitioning approaches by offering more simulation-friendly regular meshes. Highlights: A new data partitioning algorithm for large-scale quad mesh generation. A parallel computing framework for distributed geometric processing and meshing. A quad mesh generator for efficient scientific simulations of large geometric data.