Efficient Parallel Algorithm for Overlaying Surface Meshes

Many computational applications involve multiple physical components, each having its own computational domain discretized by a mesh. An integrated simulation of these physical systems require transferring data across these boundaries, which are typically represented by surface meshes composed of triangles or quadrilaterals and are non-matching with differing connectivities and geometry. It is necessary to constructa common refinement (or common tessellation) of the surface meshes to transfer data between different domains accurately and conservatively. For large-scale problems that involve moving boundary, the common tessellation must be updated frequently within the integrated simulations running on parallel computers. Previously, Jiao and Heath developed an algorithm for constructing a common tessellation by overlaying the surface meshes. The original algorithm is efficient and robust, but unfortunately, it is complex and difficult to parallelize. In this thesis, we develop a modified algorithm for overlaying surface meshes. Our algorithm employs a high-level primitive, face-intersection, which combines the low-level point-projection and edge-intersection primitives of the original algorithm. A main advantage of our modified algorithm is its ease of implementation and parallelization. Our implementation utilizes flexible data structures for efficient computation and query of the common tessellation and avoids potential redundancy in computations to achieve high efficiency. To achieve robustness, we pay special attention to avoid potential topological inconsistencies due to numerical errors, and introduce a preprocessing step to project a far-apart surface mesh onto other before computing the common tessellation. We present numerical examples to demonstrate the robustness and efficiency of our method on parallel computers.M.S.Committee Chair: Jiao Xiangmin; Committee Member: Zha Hongyuan; Committee Member: Rossignac Jare