A parallel log-barrier method for mesh quality improvement and untangling

The development of parallel algorithms for mesh generation, untangling, and quality improvement is of high importance due to the need for large meshes with millions to billions of elements and the availability of supercomputers with hundreds to thousands of cores. There have been prior efforts in the development of parallel algorithms for mesh generation and local mesh quality improvement in which only one vertex is moved at a time. But for global mesh untangling and for global mesh quality improvement, where all vertices are simultaneously moved, parallel algorithms have not yet been developed. In our earlier work, we developed a serial global mesh optimization algorithm and used it to perform mesh untangling and mesh quality improvement. Our algorithm moved the vertices simultaneously to optimize a log-barrier objective function that was designed to untangle meshes as well as to improve the quality of the worst quality mesh elements. In this paper, we extend our work and develop a parallel log-barrier mesh untangling and mesh quality improvement algorithm for distributed-memory machines. We have used the algorithm with an edge coloring-based algorithm for synchronizing unstructured communication among the processes executing the log-barrier mesh optimization algorithm. The main contribution of this paper is a generic scheme for global mesh optimization, whereby the gradient of the objective function with respect to the position of some of the vertices is communicated among all processes in every iteration. The algorithm was implemented using the OpenMPI 2.0 parallel programming constructs and shows greater strong scaling efficiency compared to an existing parallel mesh quality improvement technique.     

Surface remeshing with robust high-order reconstruction

Remeshing is an important problem in variety of applications, such as finite element methods and geometry processing. Surface remeshing poses some unique challenges, as it must deliver not only good mesh quality but also good geometric accuracy. For applications such as finite elements with high-order elements (quadratic or cubic elements), the geometry must be preserved to high-order (third-order or higher) accuracy, since low-order accuracy may undermine the convergence of numerical computations. The problem is particularly challenging if the CAD model is not available for the underlying geometry, and is even more so if the surface meshes contain some inverted elements. We describe remeshing strategies that can simultaneously produce high-quality triangular meshes, untangling mildly folded triangles and preserve the geometry to high-order of accuracy. Our approach extends our earlier works on high-order surface reconstruction and mesh optimization by enhancing its robustness with a geometric limiter for under-resolved geometries. We also integrate high-order surface reconstruction with surface mesh adaptation techniques, which alter the number of triangles and nodes. We demonstrate the utilization of our method to meshes for high-order finite elements, biomedical image-based surface meshes, and complex interface meshes in fluid simulations.     

A geometrical approach to mesh smoothing

We study the problem of smoothing finite element meshes of triangles and tetrahedra, where vertices are recursively moved to improve the overall quality of the elements with respect to a given shape quality metric. We propose a geometric approach to solving the local optimization problem. Level sets of the given metric are used to characterize the set of optimal point(s). We also introduce a new mesh quality metric for tetrahedra.     

Constrained mesh optimization on boundary

This paper presents a new mesh optimization approach aiming to improve the mesh quality on the boundary. The existing mesh untangling and smoothing algorithms (Vachal et al. in J Comput Phys 196: 627–644, 2004; Knupp in J Numer Methods Eng 48: 1165–1185, 2002), which have been proved to work well to interior mesh optimization, are enhanced by adding constrains of surface and curve shape functions that approximate the boundary geometry from the finite element mesh. The enhanced constrained optimization guarantees that the boundary nodes to be optimized always move on the approximated boundary. A dual-grid hexahedral meshing method is used to generate sample meshes for testing the proposed mesh optimization approach. As complementary treatments to the mesh optimization, appropriate mesh topology modifications, including buffering element insertion and local mesh refinement, are performed in order to eliminate concave and distorted elements on the boundary. Finally, the optimization results of some examples are given to demonstrate the effectivity of the proposed approach.     

Performance characterization of nonlinear optimization methods for mesh quality improvement

We characterize the performance of gradient- and Hessian-based optimization methods for mesh quality improvement. In particular, we consider the steepest descent and Polack-Ribière conjugate gradient methods which are gradient based. In the Hessian-based category, we consider the quasi-Newton, trust region, and feasible Newton methods. These techniques are used to improve the quality of a mesh by repositioning the vertices, where the overall mesh quality is measured by the sum of the squares of individual elements according to the aspect ratio metric. The effects of the desired degree of accuracy in the improved mesh, problem size, initial mesh configuration, and heterogeneity in element volume on the performance of the optimization solvers are characterized on a series of tetrahedral meshes.     

A dual element based geometric element transformation method for all-hexahedral mesh smoothing

Due to their increased complexity hexahedral elements are more challenging with respect to mesh generation and mesh improvement techniques than tetrahedral elements. In particular, there is a lack of geometry-based all-hexahedral smoothing methods for mesh quality improvement being easy to implement, practicable, and efficient. The recently introduced geometric element transformation method represents a new promising element oriented smoothing concept to resolve this deficiency. By giving a dual octahedron based regularizing transformation this new approach is adapted in order to smooth all-hexahedral meshes. First numerical tests indicate that the resulting smoothing method yields high quality results at least comparable to those of a state of the art global optimization-based approach while being significantly faster.     

Automatic Delaunay mesh generation method and physically-based mesh optimization method on two-dimensional regions

Delaunay mesh generation method is a common method for unstructured mesh (or unstructured grid) generation. Delaunay mesh generation method can conveniently add new points to the existing mesh without remeshing the whole domain. However, the quality of the generated mesh is not high enough if compared with some mesh generation methods. To obtain high-quality mesh, this paper developed an automatic Delaunay mesh generation method and a physically-based mesh optimization method on two-dimensional regions. For the Delaunay mesh generation method, boundary-conforming problem was ensured by create nodes at centroid of mesh elements. The definition of node bubbles and element bubbles was provided to control local mesh coarseness and fineness automatically. For the physically-based mesh optimization method, the positions of boundary node bubbles are predefined, the positions of interior node bubbles are adjusted according to interbubble forces. Size of interior node bubbles is further adjusted according to the size of adjacent node bubbles. Several examples show that high-quality meshes are obtained after mesh optimization.

     

构造最优Delaunay三角剖分的拓扑优化方法

最优Delaunay三角剖分(ODT)是生成区域网格剖分的一种优化方法.从数值优化的角度来看,现有的ODT优化方法属于局部方法,对于任意给定初值容易陷入较差的局部极小值点,从而不能产生高质量网格.为此提出一种简单的拓扑优化方法,使得ODT方法能有效地从局部极小值点中跳出,进一步提高网格的质量.该方法只涉及到局部的边翻转操作,实现简单;而且具有显式的目标函数,能在理论上保证算法的收敛性.实验结果表明,文中算法运行速度快,不论是在拓扑连接关系还是在三角形的形状上都显著地提高了ODT方法生成的网格质量.     

Quality encoding for tetrahedral mesh optimization

We define quality differential coordinates (QDC) for per-vertex encoding of the quality of a tetrahedral mesh. QDC measures the deviation of a mesh vertex from a position which maximizes the combined quality of the set of tetrahedra incident at that vertex. Our formulation allows the incorporation of different choices of element quality metrics into QDC construction to penalize badly shaped and inverted tetrahedra. We develop an algorithm for tetrahedral mesh optimization through energy minimization driven by QDC. The variational problem is solved efficiently and robustly using gradient flow based on a stable semi-implicit integration scheme. To ensure quality boundary of the resulting tetrahedral mesh, we propose a harmonic-guided optimization scheme which leads to consistent handling of both the interior and boundary tetrahedra.     

Eulerian shape design sensitivity analysis and optimization with a fixed grid

Conventional shape optimization based on the finite element method uses Lagrangian representation in which the finite element mesh moves according to shape change, while modern topology optimization uses Eulerian representation. In this paper, an approach to shape optimization using Eulerian representation such that the mesh distortion problem in the conventional approach can be resolved is proposed. A continuum geometric model is defined on the fixed grid of finite elements. An active set of finite elements that defines the discrete domain is determined using a procedure similar to topology optimization, in which each element has a unique shape density. The shape design parameter that is defined on the geometric model is transformed into the corresponding shape density variation of the boundary elements. Using this transformation, it has been shown that the shape design problem can be treated as a parameter design problem, which is a much easier method than the former. A detailed derivation of how the shape design velocity field can be converted into the shape density variation is presented along with sensitivity calculation. Very efficient sensitivity coefficients are calculated by integrating only those elements that belong to the structural boundary. The accuracy of the sensitivity information is compared with that derived by the finite difference method with excellent agreement. Two design optimization problems are presented to show the feasibility of the proposed design approach.     

Optimum design of plano-milling machine structure using finite element analysis

The problem of optimum design of plano-milling machine structure is formulated as a nonlinear mathematical programming problem with the objective of minimizing the structural weight. The plano-milling machine structure is idealized with triangular plate elements and three dimensional frame elements based on finite element displacement method. Constraints are placed on static deflections and principal stresses in the problem formulation. The optimization problem is solved by using an interior penalty function method in which the Davidon-Fletcher-Powell variable metric unconstrained minimization technique and cubic interpolation method of one dimensional search are employed. A numerical example is presented for demonstrating the effectiveness of the procedure outlined. The results of sensitivity analysis conducted with respect to design variables and fixed parameters about the optimum point are also reported.     

A hybrid ant colony optimization approach for finite element mesh decomposition

This paper examines the application of the ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite element analysis. The concept of the ant colony optimization technique for finding approximate solutions to combinatorial optimization problems is described.The application of ant colony optimization for partitioning finite element meshes based on triangular elements is described.A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh decomposition is carried out using normal and predictive modes for which the predictive mode uses a trained multilayered feed-forward neural network which estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite element meshes is examined by decomposing two mesh examples.     

Construction of an objective function for optimization-based smoothing

An objective function for optimization-based smoothing is proposed for both linear and quadratic triangular and quadrilateral elements. Unlike currently published objective functions that are used to perform smoothing or untangling separately, this objective function can be used to untangle and smooth a mesh in a single process. The objective function is designed in such a way that it is easy and straightforward to be extended to higher order elements. The objective function has higher order continuous derivatives that make it suitable for optimization techniques. It has been shown empirically that the proposed function only has one minimum. With the integration of the proposed new objective function into our optimization-based smoothing algorithm, our combined Laplacian/optimization smoothing scheme provides us with satisfactory high quality meshes.     

无人机三维路径规划及避障方法

针对无人机(UAV)在三维环境中如何由起始点到目标点合理地规划路径避开障碍物,提出了一种基于改进粒子群算法与滚动策略相结合的UAV路径规划与避障方法.该方法首先以UAV为中心,通过传感器建立UAV的可视区域模型;其次结合滚动策略滚动探知UAV周围环境信息;最后,利用改进的粒子群算法进行路径搜索,并加入综合转角控制提高路径的平滑性.在传统粒子群算法中加入信息素与启发函数,增强算法的全局搜索能力,并对参数进行特定设计提高算法的收敛速度.仿真结果表明,该方法可以实现实时避障,所规划的路径相对平滑,且改进算法比传统算法具有较高的收敛性.     

Hexahedral mesh smoothing via local element regularization and global mesh optimization

The quality of finite element meshes is one of the key factors that affect the accuracy and reliability of finite element analysis results. In order to improve the quality of hexahedral meshes, we present a novel hexahedral mesh smoothing algorithm which combines a local regularization for each hexahedral mesh, using dual element based geometric transformation, with a global optimization operator for all hexahedral meshes. The global optimization operator is composed of three main terms, including the volumetric Laplacian operator of hexahedral meshes and the geometric constraints of surface meshes which keep the volumetric details and the surface details, and another is the transformed node displacements condition which maintains the regularity of all elements. The global optimization operator is formulated as a quadratic optimization problem, which is easily solved by solving a sparse linear system. Several experimental results are presented to demonstrate that our method obtains higher quality results than other state-of-the-art approaches.     

Inverse adaptation of a Hex-dominant mesh for large deformation finite element analysis

In the finite element analysis of metal forming processes, many mesh elements are usually deformed severely in the later stage of the analysis because of the corresponding large deformation of the geometry. Such highly distorted elements are undesirable in finite element analysis because they introduce error into the analysis results, and, in the worst case, inverted elements can cause the analysis to terminate prematurely. This paper proposes a new inverse-adaptation method that reduces or eliminates the number of inverted mesh elements created in the later stage of finite element analysis, thereby lessening the chances of early termination and improving the accuracy of the analysis results. By this method, a simple uniform mesh is created initially, and a pre-analysis is run in order to observe the deformation behavior of the elements. Next, an input hex-dominant mesh is generated in which each element is “inversely adapted”, or pre-deformed in such a way that it has approximately the opposite shape of the final shape that normal analysis would deform it into. Thus, when finite element analysis is performed, the analysis starts with an input mesh of inversely adapted elements whose shapes are not ideal. As the analysis continues, the element shape quality improves to almost ideal, and then, toward the final stage of analysis, degrades again, but much less than would be the case without the inverse adaptation. This method permits the analysis to run to the end, or to a further stage, with no inverted elements. Besides its pre-skewing the element shape, the proposed method is also capable of controlling the element size according to the equivalent plastic strain information collected from the pre-analysis. The proposed inverse adaptation can be repeated iteratively until reaching the final stage of deformation.     

Affine-based registration of CT and MR modality images of human brain using multiresolution approaches: comparative study on genetic algorithm and particle swarm optimization

We present a non-linear 2-D/2-D affine registration technique for MR and CT modality images of section of human brain. Automatic registration is achieved by maximization of a similarity metric, which is the correlation function of two images. The proposed method has been implemented by choosing a realistic, practical transformation and optimization techniques. Correlation-based similarity metric should be maximal when two images are perfectly aligned. Since similarity metric is a non-convex function and contains many local optima, choice of search strategy for optimization is important in registration problem. Many optimization schemes are existing, most of which are local and require a starting point. In present study we have implemented genetic algorithm and particle swarm optimization technique to overcome this problem. A comparative study shows the superiority and robustness of swarm methodology over genetic approach.     

Jacobian-based repair method for finite element meshes after registration

Registration methods are used in the meshing field to “adapt” a given mesh to a target domain. Finite element method (FEM) is applied to the resulting mesh to compute an approximate solution to the system of partial differential equations (PDE) representing the physical phenomena under study. Prior to FE analysis the Jacobian matrix determinant must be checked for all mesh elements. The value of this Jacobian depends on the configuration of the element nodes. If it is negative for a given node, the element is invalid and therefore the FE analysis cannot be carried out. Similarly, some elements, although valid, can present poor quality regarding Jacobian-based indicator values, such as the Jacobian ratio. Mesh registration procedures are likely to produce invalid and/or poor quality elements if the Jacobian parameter is ignored. To repair invalid and poor quality elements after mesh registration, we propose a relaxation procedure driven by specific validity and quality energy formulations derived from the Jacobian value. The algorithm first recovers mesh validity and further improves elements quality, focusing primarily on nodes that make the elements invalid or of poor quality. Our novel approach has been developed in the context of non-rigid mesh registration and validated on a data set of 60 clinical cases in the context of orthopaedic and orthognathic hard and soft tissues modelling studies. The proposed repair method achieves a valid state of the mesh and also raises the quality of the elements to a level suitable for commercial FE solvers.     

Multi‐Resolution Cloth Simulation

We propose a novel, multi‐resolution method to efficiently perform large‐scale cloth simulation. Our cloth simulation method is based on a triangle‐based energy model constructed from a cloth mesh. We identify that solutions of the linear system of cloth simulation are smooth in certain regions of the cloth mesh and solve the linear system on those regions in a reduced solution space. Then we reconstruct the original solutions by performing a simple interpolation from solutions computed in the reduced space. In order to identify regions where solutions are smooth, we propose simplification metrics that consider stretching, shear, and bending forces, as well as geometric collisions. Our multi‐resolution method can be applied to many existing cloth simulation methods, since our method works on a general linear system. In order to demonstrate benefits of our method, we apply our method into four large‐scale cloth benchmarks that consist of tens or hundreds of thousands of triangles. Because of the reduced computations, we achieve a performance improvement by a factor of up to one order of magnitude, with a little loss of simulation quality.