三维实体仿真建模的网格自动生成方法

有限元网格模型的生成与几何拓扑特征和力学特性有直接关系。建立网格模型时，为了更真实地反映原几何形体的特征，在小特征尺寸或曲率较大等局部区域网格应加密剖分；为提高有限元分析精度和效率，在待分析的开口、裂纹、几何突变、外载、约束等具有应力集中力学特性的局部区域，网格应加密剖分。为此，该文提出了基于几何特征和物理特性相结合的网格自动生成方法。该方法既能有效地描述几何形体，又能实现应力集中区域的网格局部加密及粗细网格的均匀过渡。实例表明本方法实用性强、效果良好。     

Adaptive Multilevel Correction Method for Finite Element Approximations of Elliptic Optimal Control Problems

In this paper we propose an adaptive multilevel correction scheme to solve optimal control problems discretized with finite element method. Different from the classical adaptive finite element method (AFEM for short) applied to optimal control which requires the solution of the optimization problem on new finite element space after each mesh refinement, with our approach we only need to solve two linear boundary value problems on current refined mesh and an optimization problem on a very low dimensional space. The linear boundary value problems can be solved with well-established multigrid method designed for elliptic equation and the optimization problems are of small scale corresponding to the space built with the coarsest space plus two enriched bases. Our approach can achieve the similar accuracy with standard AFEM but greatly reduces the computational cost. Numerical experiments demonstrate the efficiency of our proposed algorithm.     

Goal-Oriented Adaptivity and Multilevel Preconditioning for the Poisson-Boltzmann Equation

In this article, we develop goal-oriented error indicators to drive adaptive refinement algorithms for the Poisson-Boltzmann equation. Empirical results for the solvation free energy linear functional demonstrate that goal-oriented indicators are not sufficient on their own to lead to a superior refinement algorithm. To remedy this, we propose a problem-specific marking strategy using the solvation free energy computed from the solution of the linear regularized Poisson-Boltzmann equation. The convergence of the solvation free energy using this marking strategy, combined with goal-oriented refinement, compares favorably to adaptive methods using an energy-based error indicator. Due to the use of adaptive mesh refinement, it is critical to use multilevel preconditioning in order to maintain optimal computational complexity. We use variants of the classical multigrid method, which can be viewed as generalizations of the hierarchical basis multigrid and Bramble-Pasciak-Xu (BPX) preconditioners.     

Adaptive mesh refinement in stress-constrained topology optimization

We present a topology structural optimization framework with adaptive mesh refinement and stress-constraints. Finite element approximation and geometry representation benefit from such refinement by enabling more accurate stress field predictions and greater resolution of the optimal structural boundaries. We combine a volume fraction filter to impose a minimum design feature size, the RAMP penalization to generate “black-and-white designs” and a RAMP-like stress definition to resolve the “stress singularity problem.” Regions with stress concentrations dominate the optimized design. As such, rigorous simulations are required to accurately approximate the stress field. To achieve this goal, we invoke a threshold operation and mesh refinement during the optimization. We do so in an optimal fashion, by applying adaptive mesh refinement techniques that use error indicators to refine and coarsen the mesh as needed. In this way, we obtain more accurate simulations and greater resolution of the design domain. We present results in two dimensions to demonstrate the efficiency of our method.     

Multilevel mesh simplification

The goal of a multilevel simplification method is to produce different levels of refinement of a mesh, reducing the resolution (total number of faces), while preserving the original topology and a good approximation to the original geometry. A new approach to simplification based on the evolution of surfaces under p-Laplacian flow is presented. Such an evolution provides a natural geometric clustering process where the spatial effect of the p-Laplacian allows for identifying suitable regions that need to be simplified. The concrete scheme is a multiresolution framework composed, at each simplification level, of a spatial clustering diffusion flow to determine the potential candidates for deletion, followed by an incremental decimation process to update the mesh vertex locations in order to decrease the overall resolution. Numerical results show the effectiveness of our strategy in multilevel simplification of different models with different complexities, in particular for models characterized by sharp features and flat parts.     

A cascadic geometric filtering approach to subdivision

A new approach to subdivision based on the evolution of surfaces under curvature motion is presented. Such an evolution can be understood as a natural geometric filter process where time corresponds to the filter width. Thus, subdivision can be interpreted as the application of a geometric filter on an initial surface. The concrete scheme is a model of such a filtering based on a successively improved spatial approximation starting with some initial coarse mesh and leading to a smooth limit surface.

In every subdivision step the underlying grid is refined by some regular refinement rule and a linear finite element problem is either solved exactly or, especially on fine grid levels, one confines to a small number of smoothing steps within the corresponding iterative linear solver. The approach closely connects subdivision to surface fairing concerning the geometric smoothing and to cascadic multigrid methods with respect to the actual numerical procedure. The derived method does not distinguish between different valences of nodes nor between different mesh refinement types. Furthermore, the method comes along with a new approach for the theoretical treatment of subdivision.     

An adaptive multilevel multigrid formulation for Cartesian hierarchical grid methods

A Cartesian grid method with adaptive mesh refinement and multigrid acceleration is presented for the compressible Navier-Stokes equations. Cut cells are used to represent boundaries on the Cartesian grid, while ghost cells are introduced to facilitate the implementation of boundary conditions. A cell-tree data structure is used to organize the grid cells in a hierarchical manner. Cells of all refinement levels are present in this data structure such that grid level changes as they are required in a multigrid context do not have to be carried out explicitly. Adaptive mesh refinement is introduced using phenomenon-based sensors. The application of the multilevel method in conjunction with the Cartesian cut-cell method to problems with curved boundaries is described in detail. A 5-step Runge-Kutta multigrid scheme with local time stepping is used for steady problems and also for the inner integration within a dual time-stepping method for unsteady problems. The inefficiency of customary multigrid methods on Cartesian grids with embedded boundaries requires a new multilevel concept for this application, which is introduced in this paper. This new concept is based on the following novelties: a formulation of a multigrid method for Cartesian hierarchical grid methods, the concept of averaged control volumes, and a mesh adaptation strategy allowing to directly control the number of refined and coarsened cells.     

Adaptive Grid Refinement Procedures for Efficient Optical Flow Computation

Two approaches are described that improve the efficiency of optical flow computation without incurring loss of accuracy. The first approach segments images into regions of moving objects. The method is based on a previously defined Galerkin finite element method on a triangular mesh combined with a multiresolution segmentation approach for object flow computation. Images are automatically segmented into subdomains of moving objects by an algorithm that employs a hierarchy of mesh coarseness for the flow computation, and these subdomains are reconstructed over a finer mesh on which to recompute flow more accurately. The second approach uses an adaptive mesh in which the resolution increases where motion is found to occur. Optical flow is computed over a reasonably coarse mesh, and this is used to construct an optimal adaptive mesh in a way that is different from the gradient methods reported in the literature. The finite element mesh facilitates a reduction in computational effort by enabling processing to focus on particular objects of interest in a scene (i.e. those areas where motion is detected). The proposed methods were tested on real and synthetic image sequences, and promising results are reported.     

As-Rigid-As-Possible Surface Morphing

This paper presents a new morphing method based on the "as-rigid-as-possible" approach.Unlike the original as-rigid-as-possible method,we avoid the need to construct a consistent tetrahedral mesh,but instead require a consistent triangle surface mesh and from it create a tetrahedron for each surface triangle.Our new approach has several significant advantages.It is much easier to create a consistent triangle mesh than to create a consistent tetrahedral mesh.Secondly,the equations arising from our approach can be solved much more efficiently than the corresponding equations for a tetrahedral mesh.Finally,by incorporating the translation vector in the energy functional controlling interpolation,our new method does not need the user to arbitrarily fix any vertex to obtain a solution,allowing artists automatic control of interpolated mesh positions.     

A modified multilevel algorithm for large-scale scientific and engineering computing

A modified multilevel algorithm for solving the excessive storage requirements and ill-conditioning encountered in the boundary-type discretization method is proposed. The modified multilevel algorithm is an extension of the modified dual-level algorithm from dual levels to multiple levels. The method is a kernel-independent method. The core idea is the layer-by-layer calculation and then layer-by-layer correction. Making use of a multilevel structure, the original sparse matrix of the modified dual-level algorithm breaks down into a series of smaller sparse matrices corresponding to different fine meshes. The final matrix to be solved is hereby transformed to a series of smaller sparse matrices instead of a fully-populated matrix. The preconditioning effect originating from the recursive computations among the coarse mesh and fine meshes constitutes its core competitive attribute. The method evaluates far-field contributions only by the coarse mesh and uses a gradual approach to evaluate the near-field contributions. The storage requirements and computing complexity are hereby further reduced significantly.     

High order compact scheme with multigrid local mesh refinement procedure for convection diffusion problems

We derive a new fourth order compact finite difference scheme which allows different meshsize in different coordinate directions for the two-dimensional convection diffusion equation. A multilevel local mesh refinement strategy is used to deal with the local singularity problem. A corresponding multilevel multigrid method is designed to solve the resulting sparse linear system. Numerical experiments are conducted to show that the local mesh refinement strategy works well with the high order compact discretization scheme to recover high order accuracy for the computed solution. Our solution method is also shown to be effective and robust with respect to the level of mesh refinement and the anisotropy of the problems.     

Multilevel algorithms for Rannacher–Turek finite element approximation of 3D elliptic problems

Generalizing the approach of a previous work of the authors, dealing with two-dimensional (2D) problems, we present multilevel preconditioners for three-dimensional (3D) elliptic problems discretized by a family of Rannacher Turek non-conforming finite elements. Preconditioners based on various multilevel extensions of two-level finite element methods (FEM) lead to iterative methods which often have an optimal order computational complexity with respect to the number of degrees of freedom of the system. Such methods were first presented by Axelsson and Vassilevski in the late-1980s, and are based on (recursive) two-level splittings of the finite element space. An important point to make is that in the case of non-conforming elements the finite element spaces corresponding to two successive levels of mesh refinement are not nested in general. To handle this, a proper two-level basis is required to enable us to fit the general framework for the construction of two-level preconditioners for conforming finite elements and to generalize the method to the multilevel case. In the present paper new estimates of the constant γ in the strengthened Cauchy–Bunyakowski–Schwarz (CBS) inequality are derived that allow an efficient multilevel extension of the related two-level preconditioners. Representative numerical tests well illustrate the optimal complexity of the resulting iterative solver, also for the case of non-smooth coefficients. The second important achievement concerns the experimental study of AMLI solvers applied to the case of micro finite element (μFEM) simulation. Here the coefficient jumps are resolved on the finest mesh only and therefore the classical CBS inequality based convergence theory is not directly applicable. The obtained results, however, demonstrate the efficiency of the proposed algorithms in this case also, as is illustrated by an example of microstructure analysis of bones.      

Parallel quadrilateral subdomain generation for finite element analysis

In this article the Sub-domain Generation Method (SGM) previously developed for finite element meshes composed of triangular elements is generalised to account for meshes composed of arbitrary quadrilateral elements. A neural network of enhanced accuracy was developed to predict the number of quadrilaterals generated within each coarse quadrilateral element after refinement using an adaptive re-meshing procedure. Partitioning of the meshes was undertaken on the coarse mesh using a genetic algorithm to optimise the partitions considering both load balancing and interprocessor communication of the subsequent finite element analysis. A series of examples of increasing refinement were decomposed by considering a single coarse mesh of a fixed number of elements.     

On the reference mapping for quadrilateral and hexahedral finite elements on multilevel adaptive grids

We study the properties of the reference mapping for quadrilateral and hexahedral finite elements. We consider multilevel adaptive grids with possibly hanging nodes which are typically generated by adaptive refinement starting from a regular coarse grid. It turns out that for such grids the reference mapping behaves – up to a perturbation depending on the mesh size – like an affine mapping. As an application, we prove optimal estimates of the interpolation error for discontinuous mapped -elements on quadrilateral and hexahedral grids.     

Generation of 3D mixed element meshes using a flexible refinement approach

This paper describes and discusses the main characteristics and implementation issues of a 3D mixed element mesh generator based on a generalization of the modified octree approach. This mesh generator uses primitive elements of different type as internal nodes, a flexible refinement approach as refinement strategy (primitive elements are not always bisected), and bricks, pyramids, prisms and tetrahedra as final elements. The mesh generation process is divided in several steps: the generation of the initial mesh composed of primitive elements, the refinement of primitive elements until the point density requirements are fulfilled, the generation of a graded mesh between dense and coarse regions, and finally, the recognition of the final elements. The main algorithms and data structures are described in detail for each step of the mesh generation process. As result, examples of meshes that satisfy the Delaunay condition and that can be used with the control volume method are shown.     

Terrain simplification simplified: a general framework for view-dependent out-of-core visualization

We describe a general framework for out-of-core rendering and management of massive terrain surfaces. The two key components of this framework are: view-dependent refinement of the terrain mesh and a simple scheme for organizing the terrain data to improve coherence and reduce the number of paging events from external storage to main memory. Similar to several previously proposed methods for view-dependent refinement, we recursively subdivide a triangle mesh defined over regularly gridded data using longest-edge bisection. As part of this single, per-frame refinement pass, we perform triangle stripping, view frustum culling, and smooth blending of geometry using geomorphing. Meanwhile, our refinement framework supports a large class of error metrics, is highly competitive in terms of rendering performance, and is surprisingly simple to implement. Independent of our refinement algorithm, we also describe several data layout techniques for providing coherent access to the terrain data. By reordering the data in a manner that is more consistent with our recursive access pattern, we show that visualization of gigabyte-size data sets can be realized even on low-end, commodity PCs without the need for complicated and explicit data paging techniques. Rather, by virtue of dramatic improvements in multilevel cache coherence, we rely on the built-in paging mechanisms of the operating system to perform this task. The end result is a straightforward, simple-to-implement, pointerless indexing scheme that dramatically improves the data locality and paging performance over conventional matrix-based layouts.     

Distribution Update of Deformable Patches for Texture Synthesis on the Free Surface of Fluids

We propose an approach for temporally coherent patch‐based texture synthesis on the free surface of fluids. Our approach is applied as a post‐process, using the surface and velocity field from any fluid simulator. We apply the texture from the exemplar through multiple local mesh patches fitted to the surface and mapped to the exemplar. Our patches are constructed from the fluid free surface by taking a subsection of the free surface mesh. As such, they are initially very well adapted to the fluid's surface, and can later deform according to the free surface velocity field, allowing a greater ability to represent surface motion than rigid or 2D grid‐based patches. From one frame to the next, the patch centers and surrounding patch vertices are advected according to the velocity field. We seek to maintain a Poisson disk distribution of patches, and following advection, the Poisson disk criterion determines where to add new patches and which patches should e flagged for removal. The removal considers the local number of patches: in regions containing too many patches, we accelerate the temporal removal. This reduces the number of patches while still meeting the Poisson disk criterion. Reducing areas with too many patches speeds up the computation and avoids patch‐blending artifacts. The final step of our approach creates the overall texture in an atlas where each texel is computed from the patches using a contrast‐preserving blending function. Our tests show that the approach works well on free surfaces undergoing significant deformation and topological changes. Furthermore, we show that our approach provides good results for many fluid simulation scenarios, and with many texture exemplars. We also confirm that the optical flow from the resulting texture matches the fluid velocity field. Overall, our approach compares favorably against recent work in this area.     

隐式曲面的多分辨率法向网格逼近

法向网格是一种新型的曲面多分辨率描述方式，其中每个层次都可以表示为其前一个粗糙层次的法向偏移．文中提出一种基于法向网格表示的隐式曲面多分辨率网格逼近算法．首先通过基于空间剖分技术的多边形化算法获得隐式曲面的粗糙逼近网格，并利用网格均衡化方法对粗糙网格进行优化，消除其中的狭长三角形；然后利用法向细分规则迭代地对网格中的三角面片进行细分，并利用区间算术技术沿法向方向对隐式曲面进行逼近．最终生成的隐式曲面分片线性逼近网格为法向网格．该逼近网格为隐式曲面提供了一种多分辨率表示，网格具有细分连通性，其数据量较传统的多边形化算法所生成的网格有大幅度的压缩．该算法可用于隐式曲面的多级绘制、累进传输及相关数字几何处理．     

Approximate Shape Quality Mesh Generation

We present two techniques for simplifying the list processing required in standard iterative refinement approaches to shape quality mesh generation. The goal of these techniques is to gain simplicity of programming, efficiency in execution, and robustness of termination. ‘Shape quality’ for a mesh generation method usually means that, under suitable conditions, a mesh with all angles exceeding a prescribed tolerance is generated. The methods introduced in this paper are truncated versions of such methods. They depend on the shape improvement properties of the terminal-edge LEPP-Delaunay refinement technique; we refer to them as approximate shape quality methods. They are intended for geometry-based preconditioning of coarse initial meshes for subsequent refinement to meet data representation needs. One technique is an algorithm re-organization to avoid maintaining a global list of triangles to be refined. The re-organization uses a recursive triangle processing strategy. Truncating the recursion depth results in an approximate method. Based on this, we argue that the refinement process can be carried out using a static list of the triangles to be refined that can be identified in the initial mesh. Comparisons of approximate to full shape quality meshes are provided.