3D finite element meshing from imaging data

This paper describes an algorithm to extract adaptive and quality 3D meshes directly from volumetric imaging data. The extracted tetrahedral and hexahedral meshes are extensively used in the finite element method (FEM). A top-down octree subdivision coupled with a dual contouring method is used to rapidly extract adaptive 3D finite element meshes with correct topology from volumetric imaging data. The edge contraction and smoothing methods are used to improve mesh quality. The main contribution is extending the dual contouring method to crack-free interval volume 3D meshing with boundary feature sensitive adaptation. Compared to other tetrahedral extraction methods from imaging data, our method generates adaptive and quality 3D meshes without introducing any hanging nodes. The algorithm has been successfully applied to constructing quality meshes for finite element calculations.     

A template-based approach for parallel hexahedral two-refinement

We provide a template-based approach for generating locally refined all-hex meshes. We focus specifically on refinement of initially structured grids utilizing a 2-refinement approach where uniformly refined hexes are subdivided into eight child elements. The refinement algorithm consists of identifying marked nodes that are used as the basis for a set of four simple refinement templates. The target application for 2-refinement is a parallel grid-based all-hex meshing tool for high performance computing in a distributed environment. The result is a parallel consistent locally refined mesh requiring minimal communication and where minimum mesh quality is greater than scaled Jacobian 0.3 prior to smoothing.     

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.     

支持裂纹扩展的三维有限元网格生成算法

描述了任意形状三维区域的非结构四面体网格生成算法,该算法对不含裂纹的区域、含单裂纹或多裂纹的区域都适用。算法首先使用八叉树来确定网格单元大小,然后采用前沿推进技术来生成网格。在前沿推进过程中,采用基于几何形状和基于拓扑结构的两个步骤来保证前沿向前移动过程中发生问题时仍能进行正确执行,并且使用了一种局部网格优化方法来提高网格划分的质量。最后,将算法运用到带有裂纹的复杂实体模型,实验结果表明该算法具有较强的适用性和较高的性能。     

Hybrid Booleans

In this paper, we present a novel method to compute Boolean operations on polygonal meshes. Given a Boolean expression over an arbitrary number of input meshes we reliably and efficiently compute an output mesh which faithfully preserves the existing sharp features and precisely reconstructs the new features appearing along the intersections of the input meshes. The term "hybrid" applies to our method in two ways: First, our algorithm operates on a hybrid data structure which stores the original input polygons (surface data) in an adaptively refined octree (volume data). By this we combine the robustness of volumetric techniques with the accuracy of surface-oriented techniques. Second, we generate a new triangulation only in a close vicinity around the intersections of the input meshes and thus preserve as much of the original mesh structure as possible (hybrid mesh). Since the actual processing of the Boolean operation is confined to a very small region around the intersections of the input meshes, we can achieve very high adaptive refinement resolutions and hence very high precision. We demonstrate our method on a number of challenging examples.     

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

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

Transformation of Hexaedral Finite Element Meshes into Tetrahedral Meshes According to Quality Criteria

The paper is concerned with algorithms for transforming hexahedral finite element meshes into tetrahedral meshes without introducing new nodes. Known algorithms use only the topological structure of the hexahedral mesh but no geometry information. The paper provides another algorithm which is then extented such that quality criteria for the splitting of faces are respected.     

大型网格模型多分辨率的外存构建与交互绘制

结合多分辨率、网格排布和基于视点的绘制技术,提出一种外存多分辨率构建和绘制算法.采用适应性八叉树对模型的包围盒进行划分,自顶向下构建模型的多分辨率层次结构,较好地保持了原模型的细节分布;并对多分辨率结构中每个节点所包含的三角形片段进行网格排布优化,降低了缓存的平均失效率;在实时绘制时,采用基于视点的细节层次选择策略进行模型的细化;最后通过引入数据预取机制来隐藏磁盘I/O延时,进一步提高绘制性能.实验结果表明,该算法在绘制速度与细节保留上均优于同类MRMM算法.     

Stable Real-Time Surgical Cutting Simulation of Deformable Objects Embedded with Arbitrary Triangular Meshes

Surgical simulators need to simulate deformation and cutting of deformable objects. Adaptive octree mesh based cutting methods embed the deformable objects into octree meshes that are recursively refined near the cutting tool trajectory. Deformation is only applied to the octree meshes; thus the deformation instability problem caused by degenerated elements is avoided. Biological tissues and organs usually contain complex internal structures that are ignored by previous work. In this paper the deformable objects are modeled as voxels connected by links and embedded inside adaptive octree meshes. Links swept by the cutting tool are disconnected and object surface meshes are reconstructed from disconnected links. Two novel methods for embedding triangular meshes as internal structures are proposed. The surface mesh embedding method is applicable to arbitrary triangular meshes, but these meshes have no physical properties. The material sub-region embedding method associates the interiors enclosed by the triangular meshes with physical properties, but requires that these meshes are watertight, and have no self-intersections, and their smallest features are larger than a voxel. Some local features are constructed in a pre-calculation stage to increase simulation performance. Simulation tests show that our methods can cut embedded structures in a way consistent with the cutting of the deformable objects. Cut fragments can also deform correctly along with the deformable objects.     

Cost Minimizing Local Anisotropic Quad Mesh Refinement

Quad meshes as a surface representation have many conceptual advantages over triangle meshes. Their edges can naturally be aligned to principal curvatures of the underlying surface and they have the flexibility to create strongly anisotropic cells without causing excessively small inner angles. While in recent years a lot of progress has been made towards generating high quality uniform quad meshes for arbitrary shapes, their adaptive and anisotropic refinement remains difficult since a single edge split might propagate across the entire surface in order to maintain consistency. In this paper we present a novel refinement technique which finds the optimal trade-off between number of resulting elements and inserted singularities according to a user prescribed weighting. Our algorithm takes as input a quad mesh with those edges tagged that are prescribed to be refined. It then formulates a binary optimization problem that minimizes the number of additional edges which need to be split in order to maintain consistency. Valence 3 and 5 singularities have to be introduced in the transition region between refined and unrefined regions of the mesh. The optimization hence computes the optimal trade-off and places singularities strategically in order to minimize the number of consistency splits — or avoids singularities where this causes only a small number of additional splits. When applying the refinement scheme iteratively, we extend our binary optimization formulation such that previous splits can be undone if this prevents degenerate cells with small inner angles that otherwise might occur in anisotropic regions or in the vicinity of singularities. We demonstrate on a number of challenging examples that the algorithm performs well in practice.     

基于内容的网格生成算法

在基于模型的编码技术中,选择合适的网络模型对提高模糊的运动估计精度、编码效率和得到高质量的解码图像都是至关重要的。本文提出的基于图像内容的自适应网络模型生成算法,首先利用数学形态学中的水线算法把编码图像分割成许多纹理一致的区域,所分割的区域反映了图像的结构、轮廓和边界;再对这些区域的边界进行多边形拟合,得到多边形各个边的端点作为网格模型的节点,以这些节点为基础就能生成一个Ｄｅｌａｕｎａｙ三角形网格     

Refinement and coarsening of surface meshes

This paper presents an adaptation scheme for surface meshes. Both refinement and coarsening tools are based upon local retriangulation. They can maintain the geometric features of the given surface mesh and its quality as well. A mesh gradation tool to smooth out large size differences between neighboring (in space) mesh faces and a procedure to detect and resolve self-intersections in the mesh are also presented. Both are driven by an octree structure and make use of the presented refinement tool.     

Feature-preserving T-mesh construction using skeleton-based polycubes

This paper presents a novel algorithm which uses skeleton-based polycube generation to construct feature-preserving T-meshes. From the skeleton of the input model, we first construct initial cubes in the interior. By projecting corners of interior cubes onto the surface and generating a new layer of boundary cubes, we split the entire interior domain into different cubic regions. With the splitting result, we perform octree subdivision to obtain T-spline control mesh or T-mesh. Surface features are classified into three groups: open curves, closed curves and singularity features. For features without introducing new singularities like open or closed curves, we preserve them by aligning to the parametric lines during subdivision, performing volumetric parameterization from frame field, or modifying the skeleton. For features introducing new singularities, we design templates to handle them. With a valid T-mesh, we calculate rational trivariate T-splines and extract Bézier elements for isogeometric analysis.     

非结构化四边形网格生成新算法

改进了一类基于递归区域分解过程的四边形网格生成算法。引入一套健壮的网格模板,为子域的网格剖分提供统一的处理方案,不再限制最终子域为4节点、6节点或8节点子域,提高了算法的时空效率。结合新的子域网格生成过程和自动区域分解算法,利用背景网格和网格源控制分解线上点的布置,得到一个全自动的非结构化四边形网格生成算法。最后通过网格及数值模拟实例验证了算法性能和实用性。     

Parallel generation of meshes with cracks using binary spatial decomposition

This work describes a technique to generate tetrahedral meshes with cracks using parallel computers with distributed memory. This technique can be used for models without cracks as well. It employs a binary partitioning structure that uses axis-aligned planes to decompose the domain. Those decomposing planes are determined based on a refined octree that is built to estimate the amount of work necessary to generate the whole mesh, so that the amount of work in each subdomain is approximately the same. A serial advancing front technique is used in each subdomain concurrently, in such a way that the generated tetrahedra do not cross the decomposing planes. After local synchronizations, meshes are generated interfacing the subdomains. The results show that the prediction of the number of elements in each subdomain is accurate, leading to a well-balanced algorithm and to a good speed-up. Also, the meshes generated in parallel have very good quality, similar to the that of a serially generated mesh.     

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.     

Feature-Sensitive Tetrahedral Mesh Generation with Guaranteed Quality

Tetrahedral meshes are being extensively used in finite element methods (FEM). This paper proposes an algorithm to generate feature-sensitive and high-quality tetrahedral meshes from an arbitrary surface mesh model. A top-down octree subdivision is conducted on the surface mesh and a set of tetrahedra are constructed using adaptive body-centered cubic (BCC) lattices. Special treatments are given to the tetrahedra near the surface such that the quality of the resulting tetrahedral mesh is provably guaranteed: the smallest dihedral angle is always greater than 5.71°. The meshes generated by our method are not only adaptive from the interior to the boundary, but also feature-sensitive on the surface with denser elements in high-curvature regions where geometric feature most likely reside. A variety of experimental results are presented to demonstrate the effectiveness and robustness of this algorithm.     

Guaranteed-quality all-quadrilateral mesh generation with feature preservation

In this paper, a quadtree-based mesh generation method is described to create guaranteed-quality, geometry-adapted all-quadrilateral (all-quad) meshes with feature preservation for arbitrary planar domains. Given point cloud, our method generates all-quad meshes with these points as vertices and all the angles are within [45°, 135°]. For given planar curves, quadtree-based spatial decomposition is governed by the curvature of the boundaries and narrow regions. 2-refinement templates are chosen for local mesh refinement without creating any hanging nodes. A buffer zone is created by removing elements around the boundary. To guarantee the mesh quality, the angles facing the boundary are improved via template implementation, and two buffer layers are inserted in the buffer zone. It is proved that all the elements of the final mesh are quads with angles between 45° ± ε and 135° ± ε (ε ≤ 5°) with the exception of badly shaped elements that may be required by the sharp angles in the input geometry. We also prove that the scaled Jacobians defined by two edge vectors are in the range of [sin(45° ? ε), sin90°], or [0.64, 1.0]. Furthermore, sharp features and narrow regions are detected and preserved automatically. Boundary layer meshes are generated by splitting elements of the second buffer layer. We have applied our algorithm to a set of complicated geometries, including the Lake Superior map and the air foil with multiple components.     

Numerical simulation of incompressible flows using adaptive unstructured meshes and the pseudo-compressibility hypothesis

The numerical simulation of incompressible viscous flows, using finite elements with automatic adaptive unstructured meshes and the pseudo-compressibility hypothesis, is presented in this work. Special emphasis is given to the automatic adaptive process of unstructured meshes with linear tetrahedral elements in order to get more accurate solutions at relatively low computational costs. The behaviour of the numerical solution is analyzed using error indicators to detect regions where some important physical phenomena occur. An adaptive scheme, consisting in a mesh refinement process followed by a nodal re-allocation technique, is applied to the regions in order to improve the quality of the numerical solution. The error indicators, the refinement and nodal re-allocation processes as well as the corresponding data structure (to manage the connectivity among the different entities of a mesh, such as elements, faces, edges and nodes) are described. Then, the formulation and application of a mesh adaptation strategy, which includes a refinement scheme, a mesh smoothing technique, very simple error indicators and an adaptation criterion based in statistical theory, integrated with an algorithm to simulate complex two and three dimensional incompressible viscous flows, are the main contributions of this work. Two numerical examples are presented and their results are compared with those obtained by other authors.     

平面任意区域自适应网格生成技术

介绍了研制的适用于平面问题的四边形单元与三角形单元的网格生成器，利用文中建议的网格生成技术，可对各类复杂曲线组成的平面任意区域进行自适应网格加密，计算结果表明，按指定区域进行局部加密，加密效果令人满意。