Dynamic Meshing Techniques for Quality Improvement, Untangling, and Warping
Open Access
- Author:
- Sastry, Shankar Prasad
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 18, 2012
- Committee Members:
- Suzanne Michelle Shontz, Dissertation Advisor/Co-Advisor
Padma Raghavan, Committee Member
Mahmut Taylan Kandemir, Committee Member
Keefe B Manning, Committee Member - Keywords:
- mesh quality improvement
mesh untangling
mesh warping - Abstract:
- In order to numerically solve partial differential equations (PDEs) on physical domains using finite element (FE) techniques, discretizations of the equations and the domains are generated. The discretizations of the domain are called meshes. The discretized PDEs and meshes form a system of equations (in this dissertation, they are linear and sparse), which are solved using sparse linear solvers to obtain a solution to the PDEs. High-quality meshes are necessary for stability, efficiency, and convergence of a FE solver and the accuracy of the associated PDE solution. Meshes are accordingly warped to obtain accurate results from the simulations in which the domains change their shape. In this dissertation, we analyze existing techniques and develop new techniques to improve mesh quality and to warp meshes more efficiently. In the first part of the dissertation, we focus on mesh quality improvement algorithms. First, we characterize existing gradient- and Hessian-based mesh optimization algorithms to improve the quality of mesh elements. The characterization is carried out in the context of both local and global implementations of the mesh quality improvement algorithms. Second, we study the effect the choice of mesh quality metric, preconditioner, and sparse linear solver have on the numerical solution of elliptic partial differential equations (PDEs). We focus on determining the most efficient quality metric/preconditioner/linear solver combination for mesh quality improvement and the numerical solution of various elliptic PDEs. Third, we develop a mesh quality improvement algorithm that improves the quality of the worst element in a mesh. This technique is based on a log-barrier interior point method for constrained optimization. We extend our algorithm to perform mesh untangling. In the second part of the dissertation, we focus on mesh warping techniques. First, we analyze the performance of a finite-element based mesh warping algorithm (FEMWARP). In our parallel implementation, we reorder the mesh vertices and elements using space-filling curves to improve the cache utilization in shared-memory, multi-core processors. The reordering also helps improve the efficiency of the block-Jacobi preconditioner used in our implementation. Second, we propose superelasticity- and linear elasticity-based mesh warping techniques, which are employed in a computational pipeline to generate patient-specific meshes. The meshes are used in computational fluid dynamics simulations of blood flow for improved prevention of pulmonary embolism.