# Unstructured Mesh Generation

### From DIC

Meshes are fundamental to many forms of numerical simulation, necessary for describing the shape of physical objects, the space around them, and their interactions. At the Pacific Northwest National Laboratory (PNNL) researchers are developing techniques for generating very large unstructured meshes in high dimension space for uses in medical imaging, weather modeling, design engineering, and digital content creation.We design and implement novel methods and algorithms which take advantage of the efficient fine grained synchronization and load balancing available on the Cray XMT. Our algorithms are intended to be used on meshes too large for conventional cluster systems and to provide consistent performance regardless of the underlying structure.

Using a parallel version of Andrew Moore’s Anchors Hierarchy algorithm, the point cloud is decomposed into independent search spaces which can be operated on concurrently. The first phase of the Anchors Hierarchy produces clusters whose points are sorted with respect to the pivot point, making them well suited for use as Voronoi cell search spaces. Voronoi cell construction proceeds outward from the point nearest the pivot, the search space shrinking with the addition of each new point, until all points have been considered.

The independent Voronoi cells are composited together into a global Voronoi Diagram, new points are selected as pivots and the anchor phase of the anchors hierarchy is performed, and the process is repeated until all the original points are the center of their own Voronoi Cell or have been proven to be on the surface of the mesh. A Voronoi diagram is the dual of the Delaunay Mesh, therefore once the global Voronoi diagram is complete the Delaunay Mesh of the points is also known. Total work for final mesh generation is minimized as a natural consequence of searching ordered anchor spaces which are shrinking as searching proceeds, and by incrementally modifying anchors as new pivots are chosen instead of re-sorting all the points.

**Article Title:** Unstructured Mesh Generation

**Article Added:** 2010/09/18

**Category(s):** Analytic Algorithms