Optimization-based Meshing Techniques for Mesh Quality Improvement and Deformation

Open Access
Kim, Jibum
Graduate Program:
Computer Science and Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
October 24, 2012
Committee Members:
  • Suzanne Michelle Shontz, Dissertation Advisor
  • Suzanne Michelle Shontz, Committee Chair
  • Jesse Louis Barlow, Committee Member
  • Padma Raghavan, Committee Member
  • Qiang Du, Committee Member
  • Mesh Optimization
  • Mesh Untangling
  • Mesh Deformation
  • Finite Element Method
High quality meshes are important for the accuracy, stability, and efficiency of numerical techniques in computational simulations involving partial differential equations (PDEs), nonlocal peridynamics, mesh deformation, or shape matching. Several applications involving these mesh-based computational techniques include ocean dynamics (PDEs), surface cracks (nonlocal peridynamics), hydrocephalus (mesh deformation), and object recognition (shape matching). The first part of the dissertation explores the best combinations of mesh quality metrics, preconditioners, and sparse linear solvers for solving various elliptic PDEs, multiobjective mesh optimization methods, and the effect of mesh anisotropy, mesh refinement, and kernel functions on the conditioning of nonlocal peridynamics models. Engineers use various mesh quality improvement methods for solving PDEs to improve the efficiency and accuracy as well as various types of preconditioners and sparse linear solvers for various PDE problems. However, little research has been performed with respect to choosing the most efficient combinations of these three factors for solving various elliptic PDE problems. First, we investigate the effect of choosing various combinations of mesh quality metrics, preconditioners, and sparse linear solvers on the numerical solution of elliptic PDEs. Many PDE-based engineering and scientific applications have multiple requirements for the finite element mesh discretizing the geometric domain; however, most traditional mesh optimization algorithms improve only one aspect of the mesh, Second, we propose a multiobjective mesh optimization framework for simultaneous mesh quality improvement and mesh untangling for PDE-based applications for optimizing two or more aspects of the mesh. Recently, a new paradigm called nonlocal peridynamics, which employs integral equations, was proposed to model discontinuous domains. Third, we investigate the effect of mesh anisotropy, mesh refinement, and kernel functions on the conditioning of the global stiffness matrix for a nonlocal peridynamics model. The second part of the dissertation studies mesh deformation algorithms for robust anisotropic mesh deformation and for shape matching. First, we propose a robust mesh deformation algorithm using the anisotropy of the boundary deformation and multiobjective mesh optimization. When mesh deformation occurs, it is challenging to preserve element shape and noninverted mesh elements. In order to achieve this on the deformed domain, we use the direction of the boundary deformation to estimate the interior vertex positions and employ multiobjective mesh optimization for simultaneously preserving element shape and untangling the mesh. Second, we propose an improved shape matching algorithm for deformable objects modeled by triangular meshes. We use dynamic programming to find the optimal mapping from the source image to the target image.