Abstract The generation of high-quality staggered unstructured grids is considered, leading to the development of a new optimisation-based strategy designed to construct weighted ‘Regular-Power’ tessellations appropriate for co-volume type numerical discretisation techniques. This new framework aims to extend the conventional Delaunay–Voronoi primal-dual structure; seeking to assemble generalised orthogonal tessellations with enhanced geometric quality. The construction of these grids is motivated by the desire to improve the performance and accuracy of numerical methods based on unstructured co-volume type schemes, including various staggered grid techniques for the simulation of fluid dynamics and hyperbolic transport. In this study, a new hybrid optimisation strategy is proposed; seeking to optimise the geometry, topology and weights associated with general, two-dimensional Regular-Power tessellations using a combination of gradient-ascent and energy-based techniques. The performance of this new method is tested experimentally, with a range of complex, multi-resolution primal-dual grids generated for various coastal and regional ocean modelling applications.
A number of approaches for the generation of high-quality primal-dual grids have previously been pursued, typically focusing on the optimisation of conventional Delaunay-Voronoi type pairs. Such methods include a range of well-known techniques, including methods based on Centroidal Voronoi Tessellation (CVT) @cite_45 @cite_24 and Optimal Delaunay Triangulation (ODT) @cite_19 @cite_38 @cite_7 that seek to reposition primal vertices to minimise an that depends on the geometry and topology of the grid . While sophisticated CVT ODT schemes have been shown to generate high quality centroidal Voronoi-type tessellations, the construction of structures that are additionally well-centred has proven to be a difficult task; requiring the generation of so-called triangulations in which all angles in the primal mesh are bounded below @math . In @cite_0 @cite_48 , have shown that a non-linear optimisation-based strategy can be used to create such non-obtuse triangulations, though the resulting primal-dual tessellations do not appear to be centroidal or necessarily of optimal quality.
@cite_38 @cite_7 @cite_48 @cite_24 @cite_19 @cite_0 @cite_45
2623449798 2147749513 2114288655 1994842413
An algorithm for the generation of non-uniform, locally orthogonal staggered unstructured spheroidal grids is described. This technique is designed to generate very high-quality staggered Voronoi–Delaunay meshes appropriate for general circulation modelling on the sphere, including applications to atmospheric simulation, ocean-modelling and numerical weather prediction. Using a recently developed Frontal-Delaunay refinement technique, a method for the construction of high-quality unstructured spheroidal Delaunay triangulations is introduced. A locally orthogonal polygonal grid, derived from the associated Voronoi diagram, is computed as the staggered dual. It is shown that use of the Frontal-Delaunay refinement technique allows for the generation of very high-quality unstructured triangulations, satisfying a priori bounds on element size and shape. Grid quality is further improved through the application of hill-climbing-type optimisation techniques. Overall, the algorithm is shown to produce grids with very high element quality and smooth grading characteristics, while imposing relatively low computational expense. A selection of uniform and non-uniform spheroidal grids appropriate for high-resolution, multi-scale general circulation modelling are presented. These grids are shown to satisfy the geometric constraints associated with contemporary unstructured C-grid-type finite-volume models, including the Model for Prediction Across Scales (MPAS-O). The use of user-defined mesh-spacing functions to generate smoothly graded, non-uniform grids for multi-resolution-type studies is discussed in detail. Abstract. A new algorithm, featuring overlapping domain decompositions, for the parallel construction of Delaunay and Voronoi tessellations is developed. Overlapping allows for the seamless stitching of the partial pieces of the global Delaunay tessellations constructed by individual processors. The algorithm is then modified, by the addition of stereographic projections, to handle the parallel construction of spherical Delaunay and Voronoi tessellations. The algorithms are then embedded into algorithms for the parallel construction of planar and spherical centroidal Voronoi tessellations that require multiple constructions of Delaunay tessellations. This combination of overlapping domain decompositions with stereographic projections provides a unique algorithm for the construction of spherical meshes that can be used in climate simulations. Computational tests are used to demonstrate the efficiency and scalability of the algorithms for spherical Delaunay and centroidal Voronoi tessellations. Compared to serial versions of the algorithm and to STRIPACK-based approaches, the new parallel algorithm results in speedups for the construction of spherical centroidal Voronoi tessellations and spherical Delaunay triangulations. We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD), defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd-tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O(mlogn), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches. We introduce Hodge-optimized triangulations (HOT), a family of well-shaped primal-dual pairs of complexes designed for fast and accurate computations in computer graphics. Previous work most commonly employs barycentric or circumcentric duals; while barycentric duals guarantee that the dual of each simplex lies within the simplex, circumcentric duals are often preferred due to the induced orthogonality between primal and dual complexes. We instead promote the use of weighted duals ("power diagrams"). They allow greater flexibility in the location of dual vertices while keeping primal-dual orthogonality, thus providing a valuable extension to the usual choices of dual by only adding one additional scalar per primal vertex. Furthermore, we introduce a family of functionals on pairs of complexes that we derive from bounds on the errors induced by diagonal Hodge stars, commonly used in discrete computations. The minimizers of these functionals, called HOT meshes, are shown to be generalizations of Centroidal Voronoi Tesselations and Optimal Delaunay Triangulations, and to provide increased accuracy and flexibility for a variety of computational purposes.