Delaunay Refinement is a way to generate high quality meshes for various applications, including fluid simulations. While algorithms do exist that give good meshes, they are difficult to scale, especially when applied to 3D inputs. In our project, we will utilize the theoretical strategies researched by Andrey Chernikov and Nikos Chrisochoides to efficiently parallelize and scale the refinement process. The main strategy revolves around a “block course-grained mesh decomposition” and concurrent point insertion, which minimizes non-local communication at the expense of some dynamic load balancing.
All digital simulations and models of objects are approximations based on the number of polygons used to approximate the actual surface of the object being modeled. The more polygons there are, the more realistic the model looks, and consequently the more time it takes for the object to render. However, just adding more polygons to a model is inefficient, and the task for modeling has become how to simulate the necessary surface with the least amount of polygons possible. The Delaunay Triangulation is a common “mesh”, or polygon mapping, to accomplish this task with high quality. To simulate large models, an initial Delaunay Triangulation is typically done and then points are inserted into the mesh until a certain quality is met, while keeping some Triangulation invariants called a “constrained Delaunay triangulation”. Sequential algorithms exist to accomplish this refinement, such as Chew’s and Ruppert’s algorithms (both piecewise linear systems).
The largest challenge in generating high quality meshes is how to efficiently parallelize the insertion of points, or refinement of the mesh. In dividing the regions of the mesh between processors, some might get more work depending on which points are inserted, which means there needs to be either more dynamic load balancing or a better way to divide the mesh computation in the first place. To achieve higher parallelism for Delaunay refinement, there have been efforts to identify which properties of the triangles/polygons in the mesh remain independent to allow for concurrent insertion of points while keeping the target invariants. In “PARALLEL GUARANTEED QUALITY DELAUNAY UNIFORM MESH REFINEMENT”, CHERNIKOV and CHRISOCHOIDES propose their coarse grain partitioning approach for 2D mesh generation. Experimentation and expansion into 3D inputs is not done in the paper, and will be our ultimate goal to extend the utility of their algorithm to these. At the moment, since we are in the midst of refining our exact project deliverables, the actual 3D inputs that we would generate meshes for are to be determined later.
We will be using a variety of repositories and articles as beginning resources, which include
PARALLEL GUARANTEED QUALITY DELAUNAY UNIFORM MESH REFINEMENT
and the The Computational Geometry Algorithms Library.
4/18: Finish a mesh refinement function that allows user-defined predicate to refine triangles in a subset
4/19: Finish up the scheduling code that distributes refinement tasks (shared-address-space model)
4/20: Complete pre-processing and loading code
4/23: Finish the shared-address-space implementation
4/24 - 4/30: Performance debugging
5/1 - 5/5: Testing on PSC, writing up reports
Background visual adapted from 3D Terrain Generation with Perlin Noise by Daniel Shiffman