Least-squares approximation of affine mappings for sweep mesh generation: functional analysis and applications

Sweep methods are one of the most robust techniques to generate hexahedral meshes in extrusion volumes. The main issue in sweep algorithms is the projection of cap surface meshes along the sweep path. The most competitive technique to determine this projection is to find a least-squares approximation of an affine mapping. Several functional formulations have been defined to carry out this least-squares approximation. However, these functionals generate unacceptable meshes for several common geometries in CAD models. In this paper we present a new comparative analysis between these classical functional formulations and a new functional presented by the authors. In particular, we prove under which conditions the minimization of the analyzed functionals leads to a full rank linear system. Moreover, we also prove the equivalences between these formulations. These allow us to point out the advantages of the proposed functional. Finally, from this analysis we outline an automatic algorithm to compute the nodes location in the inner layers.     

A new least-squares approximation of affine mappings for sweep algorithms

This paper presents a new algorithm to generate hexahedral meshes in extrusion geometries. Several algorithms have been devised to generate hexahedral meshes by projecting the cap surfaces along a sweep path. In all of these algorithms the crucial step is the placement of the inner layer of nodes. That is, the projection of the source surface mesh along the sweep path. From the computational point of view, sweep methods based on a least-squares approximation of an affine mapping are the fastest alternative to compute these projections. Several functionals have been introduced to perform the least-squares approximation. However, for very simple and typical geometrical configurations they may generate low-quality projected meshes. For instance, they may induce skewness and flattening effects on the projected discretizations. In addition, for these configurations the minimization of these functionals may lead to a set of normal equations with singular system matrix. In this work we analyze previously defined functionals. Based on this analysis we propose a new functional and show that its minimization overcomes these drawbacks. Finally, we present several examples to assess the properties of the proposed functional.     

扫掠法有限元网格生成方法

为了提高有限元网格的生成质量,扫掠法生成六面体网格过程中内部节点定位成为关键一步,在研究复杂扫掠体六面体有限元网格生成算法过程中,提出了一种基于扫掠法的六面体网格生成算法,算法利用源曲面已经划分好的网格和连接曲面的结构化网格,用仿射映射逐层投影,生成目标曲面,提出基于Roca算法的内部节点定位的新算法,运用由外向内推进的波前法思想,生成全部的六面体网格。通过实例表明,该算法快速,稳定,可靠,可处理大量复杂2.5维实体六面体网格生成问题。     

Reliable Whisker Weaving via Curve Contraction

Whisker Weaving is an advancing front algorithm for all-hexahedral mesh generation. It uses global information derived from grouping the mesh dual into surfaces, the STC, to construct the connectivity of the mesh, then positions the nodes afterwards. Currently, we are able to reliably generate hexahedral meshes for complicated geometries and surface meshes. However, the surface mesh must be modified locally. Also, in large, highly-unstructured meshes, there are usually isolated regions where hex quality is poor. Reliability has been achieved by using new, provable curvecontraction algorithms to sequence the advancing front process. We have also demonstrated that sheet moving can remove certain types of invalid connectivity.     

Segmenting a deforming mesh into near-rigid components

Given a deforming mesh in an animation, we propose a new method to segment this mesh into several near-rigid sub-meshes. From this deforming mesh over all frames of an animation, we can analyze the degree of deformation between two nearby faces on the mesh. Then, our algorithm partitions the given deforming mesh into near-rigid components where the segmentation boundaries always pass at regions of large deformation. As a result, the mesh segmentation is invariant to all frames of the given animation and the motion of faces in each near-rigid-component can be represented by the same approximate affine transformation. To demonstrate the usefulness of the algorithm, we solve the restriction of deformation transfer for triangle meshes [31] which requires similar reference poses between source mesh and target mesh.     

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.     

Array-based,parallel hierarchical mesh refinement algorithms for unstructured meshes

In this paper, we describe an array-based hierarchical mesh refinement capability through uniform refinement of unstructured meshes for efficient solution of PDE’s using finite element methods and multigrid solvers. A multi-degree, multi-dimensional and multi-level framework is designed to generate the nested hierarchies from an initial coarse mesh that can be used for a variety of purposes such as in multigrid solvers/preconditioners, to do solution convergence and verification studies and to improve overall parallel efficiency by decreasing I/O bandwidth requirements (by loading smaller meshes and in-memory refinement). We also describe a high-order boundary reconstruction capability that can be used to project the new points after refinement using high-order approximations instead of linear projection in order to minimize and provide more control on geometrical errors introduced by curved boundaries.The capability is developed under the parallel unstructured mesh framework “Mesh Oriented dAtaBase” (MOAB Tautges et al. (2004)). We describe the underlying data structures and algorithms to generate such hierarchies in parallel and present numerical results for computational efficiency and effect on mesh quality. We also present results to demonstrate the applicability of the developed capability to study convergence properties of different point projection schemes for various mesh hierarchies and to a multigrid finite-element solver for elliptic problems.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

采用向量化运算进行图像融合的真实感纹理映射

提出一种基于向量运算体现纹理形变要求的映射对应点获取方法,根据场景表面纹理走势特点划分表面形变控制网格,以网格边界为形变控制向量,通过对控制向量的合成取得映射点;同时,根据对应点亮度进行图像融合达到纹理真实感融入．对于场景表面纹理走势细节性变化给出了网格调整方法,进一步使用三次参数样条曲线拟合映射区域,基于曲率半径进行边界多边形化以实现对映射区域的精确判断．该方法能产生高度真实感的虚拟实景效果．     

Automatic hexahedral mesh generation for multi-domain composite models using a hybrid projective grid-based method

This paper presents an algorithm to generate an all-hexahedral mesh of a multi-domain solid model using a hybrid grid-based approach. This is based on a projective concept during the boundary adaptation of the initial mesh. In general, the algorithm involves the generation of a grid structure, which is superimposed on the solid model. This grid structure forms an initial mesh consisting of hexahedral elements, which intersect fully or partially with the solid model. This initial mesh is then shrunk in an outside-in manner to the faces of the model through a node projection process using the closest position approach. To match the resulting mesh to the edges of the model, a minimal deformation angle method is used. Finally, to match the vertices with the nodes on the mesh, a minimal warp angle method is employed. To create the mesh of a multi-domain solid model, an outside-in and inside-in hybrid of the grid-based method is used. This hybrid method ensures that the meshes of the different domains are conforming at their common boundary. This paper also describes two methods for resolving cases of degenerate elements: a splitting technique and a wedge insertion technique.     

Optimized triangle mesh reconstruction from unstructured points

A variety of approaches have been proposed for polygon mesh reconstruction from a set of unstructured sample points. Suffering from severe aliases at sharp features and having a large number of unnecessary faces, most resulting meshes need to be optimized using input sample points in a postprocess. In this paper, we propose a fast algorithm to reconstruct high-quality meshes from sample data. The core of our proposed algorithm is a new mesh evaluation criterion which takes full advantage of the relation between the sample points and the reconstructed mesh. Based on our proposed evaluation criterion, we develop necessary operations to efficiently incorporate the functions of data preprocessing, isosurface polygonization, mesh optimization and mesh simplification into one simple algorithm, which can generate high-quality meshes from unstructured point clouds with time and space efficiency. Published online: 28 January 2003 Correspondence to: Y.-J. Liu     

A consistent octree hanging node elimination algorithm for hexahedral mesh generation

A new algorithm for hanging node elimination in octree structures is developed. The proposed algorithm utilizes hanging node elimination by refinement templates and a new mesh conditioning technique based on decoupling templates. Refinement templates insert transition elements to eliminate hanging nodes. Decoupling templates insert circular loops in the dual mesh without introducing or removing hanging nodes. Decoupling templates are introduced to avoid full refinement in the cases that do not match any of the available refinement templates. The proposed algorithm eliminates hanging nodes for concavely refined regions without excessive refinement. Another advantage of the proposed algorithm lies in eliminating narrow gaps of coarse meshes between refined regions. This step has a positive effect on the mesh quality as it avoids introducing non-regular templates with a limited penalty of uniform refinement. The presented algorithm produces good quality meshes and provides a consistent and complete method for producing conformally refined octree structures.     

Mesh filtering algorithm using an adaptive 3D convolution kernel applied to a volume-based vector distance field

This paper addresses the problem of feature preserving mesh filtering, which occurs in surface reconstruction of scanned objects, which include acquisition noise to be removed without altering sharp edges. We propose a method based on a vector field distance transform of the mesh to process. It is a volume-based implicit surface modeling, which provides an alternative representation of meshes. We use an adaptive 3D convolution kernel applied to the voxels of the distance transform model. Weights of the kernel elements are determined according to the angle between the vectors of the implicit field. We also propose a new adaptation of the Marching Cubes algorithm in order to extract the isosurface from the vector implicit field after the filtering process. We compare our method to the previous one introduced using the vector field representation and to other feature preserving adaptive filtering algorithms. According to error metric evaluations, we show that our new design provides high quality filtering results while better preserving geometric features.     

The receding front method applied to hexahedral mesh generation of exterior domains

Two of the most successful methods to generate unstructured hexahedral meshes are the grid-based methods and the advancing front methods. On the one hand, the grid-based methods generate high-quality hexahedra in the inner part of the domain using an inside–outside approach. On the other hand, advancing front methods generate high-quality hexahedra near the boundary using an outside–inside approach. To combine the advantages of both methodologies, we extend the receding front method: an inside–outside mesh generation approach by means of a reversed advancing front. We apply this approach to generate unstructured hexahedral meshes of exterior domains. To reproduce the shape of the boundaries, we first pre-compute the mesh fronts by combining two solutions of the Eikonal equation on a tetrahedral reference mesh. Then, to generate high-quality elements, we expand the quadrilateral surface mesh of the inner body towards the unmeshed external boundary using the pre-computed fronts as a guide.     

基于向量投影的支持向量机增量算法

提出一种新的基于向量投影的支持向量机增量式学习算法.该算法根据支持向量的几何分布特点,采用向量投影的方法对初始样本及增量样本在有效地避免预选取失效情况下进行预选取.选取最有可能成为支持向量的样本形成边界向量集,并在其上进行支持向量机训练.通过对初始样本是否满足新增样本集KKT条件的判断,解决非支持向量向支持向量转化的问题,有效地处理历史数据.实验表明,基于向量投影的支持向量机增量算法可以有效地减少训练样本数,积累历史信息,提高训练的速度,从而具有更好的推广能力.     

A local tangential lifting differential method for triangular meshes

In this note we present a local tangential lifting (LTL) algorithm to compute differential quantities for triangular meshes obtained from regular surfaces. First, we introduce a new notation of the local tangential polygon and lift functions and vector fields on a triangular mesh to the local tangential polygon. Then we use the centroid weights proposed by Chen and Wu [4] to define the discrete gradient of a function on a triangular mesh. We also use our new method to define the discrete Laplacian operator acting on functions on triangular meshes. Higher order differential operators can also be computed successively. Our approach is conceptually simple and easy to compute. Indeed, our LTL method also provides a unified algorithm to estimate the shape operator and curvatures of a triangular mesh and derivatives of functions and vector fields. We also compare three different methods : our method, the least square method and Akima’s method to compute the gradients of functions.     

A generalized finite difference method using Coatmèlec lattices

Generalized finite difference methods require that a properly posed set of nodes exists around each node in the mesh, so that the solution for the corresponding multivariate interpolation problem be unique. In this paper we first show that the construction of these meshes can be computerized using a relatively simple algorithm based on the concept of a Coatmèlec lattice. Then, we present a generalized finite difference method which provides a numerical solution of a partial differential equation over an arbitrary domain, using the generated meshes. The accuracy and mesh adaptivity of the method is evaluated using elliptical equations in several domains.     

A modified advancing layers mesh generation for thin three-dimensional objects with variable thickness

A method of generating modified advancing layers mesh is proposed. In this paper the mesh generation process of semi-unstructured prismatic/tetrahedral mesh is presented for relatively thin three-dimensional geometries with variable thickness, as in the case of injection molding analysis. Prismatic meshes are generated by offsetting initial surface triangular meshes. During the mesh generation process, mesh quality is efficiently improved with the use of a new node relocation method. Finally, tetrahedral meshes are automatically generated in the rest of the domain. The mesh generating capability of the proposed algorithm is demonstrated with the several practical test cases.     

A local tangential lifting differential method for triangular meshes

In this note we present a local tangential lifting (LTL) algorithm to compute differential quantities for triangular meshes obtained from regular surfaces. First, we introduce a new notation of the local tangential polygon and lift functions and vector fields on a triangular mesh to the local tangential polygon. Then we use the centroid weights proposed by Chen and Wu [4] to define the discrete gradient of a function on a triangular mesh. We also use our new method to define the discrete Laplacian operator acting on functions on triangular meshes. Higher order differential operators can also be computed successively. Our approach is conceptually simple and easy to compute. Indeed, our LTL method also provides a unified algorithm to estimate the shape operator and curvatures of a triangular mesh and derivatives of functions and vector fields. We also compare three different methods : our method, the least square method and Akima’s method to compute the gradients of functions.     

基于小波变换的3维网格水印

3维网格数据是不规则采样的数据集,传统的图像变换域水印算法不能直接应用到网格上.提出了一种小波变换域的鲁棒网格水印算法.该算法对半规则的多分辨率网格进行小波变换,得到一个基网格和一系列小波系数.在对小波系数的统计特性进行实验分析的基础上,选择在低频子带的小波系数中嵌入水印,并对小波系数的切向和法向分量设计了不同的嵌入强度,以减小几何失真.实验结果表明,该水印算法满足不可见性,并具有较强的鲁棒性.