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.     

子分元素法:一种体网格压缩算法

提出了一个包含六面体,四面体,金字塔以及三棱柱单元的混合体网格的压缩与解压算法。首先对非四面体单元按照最小节点标号策略进行子分,然后利用修改的增长缝合算法压缩子分后的四面体网格,解压阶段再通过面删除操作来恢复原始网格。压缩后每个四面体约需10bits的存储,初步试验表明,对于通常的六面体网格,能将数据模型压缩至原先的1／4。     

Using sequential NETGEN as a component for a parallel mesh generator

A parallel tetrahedral mesh generator is developed using the existing sequential NETGEN mesh generator. Mesh generation algorithms developed decompose the geometry into multiple sub-geometries sequentially on a master node and then mesh each sub-geometry in parallel on multiple processors. Two methods are implemented. The first decomposes the geometry and produces conforming surface sub-meshes from which volume meshes can be generated in parallel. A second refinement based method also makes use of the CAD geometry information. A scalable mesh migration algorithm that utilizes “owner updates” rule is implemented. Results show that using the refinement based method, a mesh with a billion elements can be generated in about a minute.     

Facial hexahedral mesh transferring by volumetric mapping based on harmonic fields

Hexahedral mesh has obvious mechanical advantages over tetrahedral mesh, but it is no trivial task to generate hexahedral mesh for complex object shapes such as individual faces. This paper presents a novel method to generate patient-specific hexahedral meshes of facial soft tissue models, based on a volumetric cross-parameterization mapping from a standard hexahedral mesh to the individual model. The volumetric parameterization is constructed based on triple of the volumetric harmonic fields, which are adapted to be as close to mutually orthogonal as possible, to achieve some quasi-conformal effect. In addition, some piecewise constraints on the harmonic fields are added to ensure anatomical feature correspondence. Experimental results show that our approach works efficiently for facial soft tissue modeling, avoids element flipping and preserves mesh element angles to a significant extent.     

Parallel adaptive mesh generation and decomposition

An important class of methodologies for the parallel processing of computational models defined on some discrete geometric data structures (i.e. meshes, grids) is the so calledgeometry decomposition or splitting approach. Compared to the sequential processing of such models, the geometry splitting parallel methodology requires an additional computational phase. It consists of the decomposition of the associated geometric data structure into a number of balancedsubdomains that satisfy a number of conditions that ensure the load balancing and minimum communication requirement of the underlying computations on a parallel hardware platform. It is well known that the implementation of the mesh decomposition phase requires the solution of a computationally intensive problem. For this reason several fast heuristics have been proposed. In this paper we explore a decomposition approach which is part of a parallel adaptive finite element mesh procedure. The proposed integrated approach consists of five steps. It starts with a coarse background mesh that isoptimally decomposed by applying well known heuristics. Then, the initial mesh is refined in each subdomain after linking the new boundaries introduced by its decomposition. Finally, the decomposition of the new refined mesh is improved so that it satisfies the objectives and conditions of the mesh decomposition problem. Extensive experimentation indicates the effectiveness and efficiency of the proposed parallel mesh and decomposition approach.     

Customizing 3D garments based on volumetric deformation

Improving the reusability of design results is very important for garment design industry, since designing an elegant garment is usually labor-intensive and time-consuming. In this paper, we present a new approach for customizing 3D garment models. Our approach can transfer garment models initially dressed on a reference human model onto a target human model. To achieve this goal, firstly a spatial mapping between the two human models is established with the shape constraints of cross-sections. Secondly, the space around the clothed reference human model is tetrahedralized into five tetrahedral meshes each of which either can be worked dependently with its adjacent ones or can be worked independently. The clothed reference human model is parametrically encoded in the tetrahedral meshes. Thirdly, these tetrahedral meshes are deformed by fitting the reference human model onto the target human model by using constrained volumetric graph Laplacian deformation. The updated garment models are finally decoded from the deformed tetrahedral meshes. As a result, the updated garment models are fitted onto the target human model. Experiments show that our approach performs very well and has the potential to be used in the garment design industry.     

CCSweep: automatic decomposition of multi-sweep volumes

CCSweep is a new method to automatically decompose multi-sweepable volumes into many-to-one sweepable volumes. Multi-sweepable volumes contain both multiple source and multiple target faces. In hexahedral mesh generation, most sweeping techniques handle many-to-one sweepable volumes that contain multiple source faces, but they are limited to volumes with only a single target face. Recent proposals to solve the multi-sweep problem have several disadvantages, including: indeterminate edge sizing or interval matching constraints, over-dependence on input mesh discretization, loop Boolean restrictions on creating only loops with even numbers of nodes, and unstable loop imprinting when interior holes exist. These problems are overcome through CCSweep. CCSweep decomposes multi-sweep volumes into many-to-one sweepable sub-volumes by projecting the target faces through the volume onto corresponding source faces. The projected faces are imprinted with the source faces to determine the decomposition of the solid. Interior faces are created to decompose the volume into separate new volumes. The new volumes have only single target faces and are represented in the meshing system as real, solid geometry, enabling them to be automatically meshed using existing many-to-one hexahedral sweeping approaches. The results of successful application of CCSweep to a number of problems are shown in this paper.Contract/grant sponsor: Sandia National Laboratories. Sandia National Laboratories is a multi-program laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy under contract DE-AC04-94-AL85000.     

Gradient field based inhomogeneous volumetric mesh deformation for maxillofacial surgery simulation

This paper presents a novel inhomogeneous volumetric mesh deformation approach by gradient field manipulation, and uses it for maxillofacial surgery simulation. The study is inspired by the state-of-the-art surface deformation techniques based on differential representations. Working in the volumetric domain instead of on only the surface can preserve the volumetric details much better, avoid local self-intersections, and achieve better deformation propagation because of the internal mesh connections. By integrating the mesh cell material stiffness parameter into our new discrete volumetric Laplacian operator, it is very convenient to incorporate inhomogeneous materials into the deformation framework. In addition, the system matrix for solving the volumetric harmonic field to handle the local transformation problem is the same used for Poisson reconstruction equation, thus it requires solving essentially only one global linear system. The system is easy to use, and can accept explicit rotational constraints, or only translational constraints to drive the deformation. One typical maxillofacial surgery case was simulated by the new methodology with inhomogeneous material estimated directly from CT data, and compared to the commonly used finite element method (FEM) approach. The results demonstrated that the deformation methodology achieved good accuracy, as well as interactive performance. Therefore, the usage of our volumetric mesh deformation approach is relevant and suitable for daily clinical practice.     

Anisotropic quadrilateral mesh generation: An indirect approach

In this paper a new indirect approach is presented for anisotropic quadrilateral mesh generation based on discrete surfaces. The ability to generate grids automatically had a pervasive influence on many application areas in particularly in the field of Computational Fluid Dynamics. In spite of considerable advances in automatic grid generation there is still potential for better performance and higher element quality. The aim is to generate meshes with less elements which fit some anisotropy criterion to satisfy numerical accuracy while reducing processing times remarkably. The generation of high quality volume meshes using an advancing front algorithm relies heavily on a well designed surface mesh. For this reason this paper presents a new technique for the generation of high quality surface meshes containing a significantly reduced number of elements. This is achieved by creating quadrilateral meshes that include anisotropic elements along a source of anisotropy.     

As-rigid-as-possible mesh deformation and its application in hexahedral mesh generation

This paper presents an efficient and stable as-rigid-as-possible mesh deformation algorithm for planar shape deformation and hexahedral mesh generation. The deformation algorithm aims to preserve two local geometric properties: scale-invariant intrinsic variables and elastic deformation energy, which are together represented in a quadric energy function. To preserve these properties, the position of each vertex is further adjusted by iteratively minimizing this quadric energy function to meet the position constraint of the controlling points. Experimental results show that the deformation algorithm is efficient, and can obtain physically plausible results, which have the same topology structure with the original mesh. Such a mesh deformation method is useful to project the source surface mesh onto the target surfaces in hexahedral mesh generation based on sweep method, and application results show that the proposed method is feasible to mesh projection not only between similar surface contours but also dissimilar surface contours.     

Registration of CAD mesh models with CT volumetric model of assembly of machine parts

X-ray CT (computed tomography) has experienced tremendous growth in industrial application in recent years, and acquiring information about the mechanical parts from CT data has been a great challenge for researchers. This paper presents a new method for the registration of a CT volumetric model of an assembly of parts with a CAD mesh model of a part of the assembly using ICP (iterative closest point) registration method. A few steps to extract feature points should be done as a preprocessing step of the volumetric model and the mesh model before applying the ICP registration algorithm, since the volumetric model and the mesh model are different in their data representation. This preprocessing step is important in order to unify the input of the ICP algorithm, and contributes to the robustness and the speed of the registration process.     

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.     

HEXHOOP: Modular Templates for Converting a Hex-Dominant Mesh to an ALL-Hex Mesh

This paper presents a new mesh conversion template called HEXHOOP, which fully automates a con-version from a hex-dominant mesh to an all-hex mesh. A HEXHOOP template subdivides a hex/prism/pyramid element into a set of smaller hex elements while main-taining the topological conformity with neighboring elements. A HEXHOOP template is constructed by assembling sub-templates, cores and caps. A dicing template for a hex and a prism is constructed by choosing the appropriate combination of a core and caps. A template that dices a pyramid without losing conformity to the adjacent element is derived from a HEXHOOP template. Some experimental results show that the HEXHOOP templates successfully convert a hex-dominant mesh into an all-hex mesh. ID="A1" Correspondence and offprint requests to: K. Shimada, Department of Mechanical Engineering, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213–3890, USA. E-mail: shimada@cmu.edu     

An approach to surface retouching and mesh smoothing

In this paper, we discuss a novel, fast, practical algorithm for surface modification of geometric objects. A space-mapping technique is used to transform a given or damaged part of a surface into a different shape in a continuous manner. The proposed approach is used for surface-retouching and mesh-smoothing problems. The technique, in fact, is based on a local processing of polygonal data that can be applied to the fairing of 3D meshes. We consider shape transformation as a general type of operation for surface modification and attempt to approach the problem from a single point of view, namely, that of the space-mapping technique based on the implementation of radial-basis functions. Experimental results are included to demonstrate the functionality of our mesh-modeling tool.     

An automated approach to information systems decomposition

A method for automating the process of system decomposition is described. The method is based on a formal specification scheme, formal definition of good decomposition, heuristic rules governing the search for good candidate decompositions, and a measure of complexity that allows ranking of the candidate decompositions. The decomposition method has been implemented as a set of experimental computerized systems analysis tools and applied to a standard problem for which other designs already exist. The results are encouraging, in that decompositions generated using other methodologies map easily into those suggested by the computerized tools. Additionally, the use of the method indicates that when more than one `good' decomposition is suggested by the system, the specifications might have been incomplete. That is, the computerized tools can identify areas where more information should be sought by analysis     

A strategy of automatic hexahedral mesh generation by using an improved whisker-weaving method with a surface mesh modification procedure

One of the demands for three dimensional (3D) finite element analyses is the development of an automatic hexahedral mesh generator. For this problem, several methods have been proposed by many researchers. However, reliable automatic hexahedral mesh generation has not been developed at present. In this paper, a new strategy of fully automatic hexahedral mesh generation is proposed. In this strategy, the prerequisite for generating a hexahedral mesh is a quadrilateral surface mesh. From the given surface mesh, combinatorial dual cycles (sheet loops for the whisker-weaving algorithm) are generated to produce a hexahedral mesh. Since generating a good quality hexahedral mesh does not depend only on the quality of quadrilaterals of the surface mesh but also on the quality of the sheet loops generated from it, a surface mesh modification method to remove self-intersections from sheet loops is developed. Next, an automatic hexahedral mesh generator by the improved whisker-weaving algorithm is developed in this paper. By creating elements and nodes on 3D real space during the weaving process, it becomes possible to generate a hexahedral mesh with fewer bad-quality elements. Several examples will be presented to show the validity of the proposed mesh generation strategy.     

Using a computational domain and a three-stage node location procedure for multi-sweeping algorithms

The multi-sweeping method is one of the most used algorithms to generate hexahedral meshes for extrusion volumes. In this method the geometry is decomposed in sub-volumes by means of projecting nodes along the sweep direction and imprinting faces. However, the quality of the final mesh is determined by the location of inner nodes created during the decomposition process and by the robustness of the imprinting process.In this work we present two original contributions to increase the quality of the decomposition process. On the one hand, to improve the robustness of the imprints we introduce the new concept of computational domain for extrusion geometries. Since the computational domain is a planar representation of the sweep levels, we improve several geometric operations involved in the imprinting process. On the other hand, we propose a three-stage procedure to improve the location of the inner nodes created during the decomposition process. First, inner nodes are projected towards source surfaces. Second, the nodes are projected back towards target surfaces. Third, the final position of inner nodes is computed as a weighted average of the projections from source and target surfaces.     

Hexahedral mesh development of free-formed geometry: The human femur exemplified

The objective of the present research is to develop a standard hexahedral Finite Element (FE) model of the human femur accounting for the material characteristics of cortical bone, cancellous bone and bone marrow. The anatomical data were acquired from the Visible Human Project. A detailed outline of the steps necessary in developing hexahedral FE meshes from computed tomography (CT) data is provided, along with a section on modelling strategies providing comprehensive suggestions on how to overcome meshing difficulties due to geometrical non-linearities. The stress and deformation results are discussed.     

Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework

In this work, we present a simultaneous untangling and smoothing technique for quadrilateral and hexahedral meshes. The algorithm iteratively improves a quadrilateral or hexahedral mesh by minimizing an objective function defined in terms of a regularized algebraic distortion measure of the elements. We propose several techniques to improve the robustness and the computational efficiency of the optimization algorithm. In addition, we have adopted an object-oriented paradigm to create a common framework to smooth meshes composed by any type of elements, and using different minimization techniques. Finally, we present several examples to show that the proposed technique obtains valid meshes composed by high-quality quadrilaterals and hexahedra, even when the initial meshes contain a large number of tangled elements.     

New method for graded mesh generation of all hexahedral finite elements

Mapping method is widely applied by most of commercial mesh generators because of its efficiency, mesh quality. One of the obstacles to apply the mapping method and generate a graded all hexahedral mesh of high quality in an arbitrarily three-dimensional domain is the generation of hexahedral parent elements on a super-element that allows for gradations in three co-ordinate directions. This paper presents a pattern module’s method to generate the graded mesh of all hexahedral elements in a cube and thus improves the mapping method. The method requires few calculations.