Surface triangulation over intersecting geometries

A method for the rapid construction of meshes over intersecting triangulated shapes is described. The method is based on an algorithm that automatically generates a surface mesh from intersecting triangulated surfaces by means of Boolean intersection/union operations. After the intersection of individual components is obtained, the exposed surface parts are extracted. The algorithm is intended for rapid interactive construction of non‐trivial surfaces in engineering design, manufacturing, visualization and molecular modelling applications. Techniques to make the method fast and general are described. The proposed algorithm is demonstrated on a number of examples, including intersections of multiple spheres, planes and general engineering shapes, as well as generation of surface and volume meshes around clusters of intersecting components followed by the computation of flow field parameters. Copyright © 1999 John Wiley & Sons, Ltd.     

三维鞋样交互设计方法研究

提出了一种在三角网格鞋楦模型上生成三维帮样曲线的离散表示及其交互编辑修改方法。基于改进的能量模型对鞋楦曲面的选择区域进行展平,利用展平过程建立的三维帮面与展平后二维帮面间的拓扑对应关系,实现鞋样曲线在三维空间与二维展平空间的实时关联;所生成的二维帮样曲线以3次非均匀B-spline表示,并以DXF格式输出,便于其他程序调用。算例结果显示,本文方法具有交互性好、实时直观的优点,能够满足基于楦型的帮样交互设计要求。     

基于递归分割的曲面造型算法

对常用复杂曲面造型方法的缺点进行了分析，给出了基于递归分割构造任意拓扑结构复杂曲面的有关算法，避免了参数方法在构造复杂曲面时费时而且难于处理的参数曲面求交和曲面拼接等问题，为优质高效建立复杂曲面模型奠定了基础。     

An imprint and merge algorithm incorporating geometric tolerances for conformal meshing of misaligned assemblies

A size tolerant algorithm for imprinting and merging adjacent part geometries is presented in this paper. This approach cleans up misaligned and dirty assembly geometry that is intended for conformal mesh generation. The algorithm first discretizes the boundary edges of adjacent faces into linear segments. The segments are then intersected and a partial intersection graph is calculated from the intersection results. The intersections are calculated by accounting for size tolerances to minimize the effect of misaligned parts on the meshing process. The partial intersection graph is next used to imprint the adjacent faces as appropriate. The imprints are generated using virtual geometry so that the tolerant topology created therein can be employed. Several examples are given to demonstrate the resulting improvement in the mesh quality of conformal meshes. The approach is shown to work robustly with misaligned and poorly defined parts. Copyright © 2004 John Wiley & Sons, Ltd.     

Automatic merging of tetrahedral meshes

A generic algorithm is proposed to merge arbitrary solid tetrahedral meshes automatically into one single valid finite element mesh. The intersection segments in the form of distinct nonoverlapping loops between the boundary surfaces of the given solid objects are determined by the robust neighbor tracing technique. Each intersected triangle on the boundary surface will be triangulated to incorporate the intersection segments onto the boundary surface of the objects. The tetrahedra on the boundary surface associated with the intersected triangular facets are each divided into as many tetrahedra as the number of subtriangles on the triangulated facet. There is a natural partition of the boundary surfaces of the solid objects by the intersection loops into a number of zones. Volumes of intersection can now be identified by collected bounding surfaces from the surface patches of the partition. Whereas mesh compatibility has already been established on the boundary of the solid objects, mesh compatibility has yet to be restored on the bounding surfaces of the regions of intersection. Tetrahedra intersected by the cut surfaces are removed, and new tetrahedra can be generated to fill the volumes bounded by the cut surfaces and the portion of cavity boundary connected to the cut surfaces to restore mesh compatibility at the cut surfaces. Upon restoring compatibility on the bounding surfaces of the regions of intersection, the objects are ready to be merged together as all regions of intersection can be detached freely from the objects. All operations, besides the determination of intersections structurally in the form of loops, are virtually topological, and no parameter and tolerance is needed in the entire merging process. Examples are presented to show the steps and the details of the mesh merging procedure. Copyright © 2012 John Wiley & Sons, Ltd.     

Coarsening unstructured meshes by edge contraction

A new unstructured mesh coarsening algorithm has been developed for use in conjunction with multilevel methods. The algorithm preserves geometrical and topological features of the domain, and retains a maximal independent set of interior vertices to produce good coarse mesh quality. In anisotropic meshes, vertex selection is designed to retain the structure of the anisotropic mesh while reducing cell aspect ratio. Vertices are removed incrementally by contracting edges to zero length. Each vertex is removed by contracting the edge that maximizes the minimum sine of the dihedral angles of cells affected by the edge contraction. Rarely, a vertex slated for removal from the mesh cannot be removed; the success rate for vertex removal is typically 99.9% or more. For two‐dimensional meshes, both isotropic and anisotropic, the new approach is an unqualified success, removing all rejected vertices and producing output meshes of high quality; mesh quality degrades only when most vertices lie on the boundary. Three‐dimensional isotropic meshes are also coarsened successfully, provided that there is no difficulty distinguishing corners in the geometry from coarsely‐resolved curved surfaces; sophisticated discrete computational geometry techniques appear necessary to make that distinction. Three‐dimensional anisotropic cases are still problematic because of tight constraints on legal mesh connectivity. More work is required to either improve edge contraction choices or to develop an alternative strategy for mesh coarsening for three‐dimensional anisotropic meshes. Copyright © 2003 John Wiley & Sons, Ltd.     

Generation of oriented three-dimensional Delaunay grids suitable for the control volume integration method

A fully automatic algorithm for three-dimensional mesh generation is presented. The algorithm preserves the robustness and time efficiency of the finite octree technique; replacing octrees by more general 2–4–8- trees, it is capable of generating oriented meshes. In a post-processing step, meshes are transformed in order to satisfy the Delaunay criterion, and so that non-overlapping, closed control volumes can be defined for each mesh point through edge bisectors. The method is shown to be appropriate for modelling semiconductor devices, where the control volume scheme is the method of choice due to the peculiarities of the partial differential equations involved, and where locally refined and oriented meshes are essential to describe the relevant internal physical quantities adequately while keeping the number of mesh points practical.     

任意拓朴网上构造高阶连续曲面的方法及应用

本文提出了一种任意拓朴网上构造高阶连续曲面的QB(Quartic B-spline)方法。理论分析表明,曲面除个别“超常点”外,均可达到C~3连续,在超常点处曲面至少达到一阶几何连续。在引入了内边界的概念及边界控制的新方法后,实现了任意拓朴网上构造多连通域曲面的设想。实际应用表明,该方法具有简单,构造曲面灵活,计算效率高等优点。     

Crack modeling in FE analysis of circular tubular joints

By mapping circles in two-dimensional planes to three-dimensional intersection curves between tubular members, a complicated three-dimensional mesh generating procedure for tubular joints is changed to a procedure similar to a two-dimensional case. More detailed modeling of welds and cracks can be included to analyze the fracture behavior of cracked tubular joints. Different types of crack tip models are discussed and a four-tip crack model is introduced to model crack propagation. These crack models can be applied to both through-thickness cracks and surface cracks. A procedure for transforming crack elements around a plane curve into crack elements for a doubly curved semi-elliptical surface crack around an intersection is also introduced. High-quality meshes can be obtained.     

参数曲面与平面求交的一种新方法

本文提出了一种新的参数曲面与平面求交算法，基于平面的半空间性质，通过参数域平面的二向线性插值，将求交问题转化为一系列简单的离散、判断、比较、排序等运算，能较好的解决曲面片内的交线不连续和交线丢失问题，算法简便，可靠性好，计算精度高，在ＮＣ自动编程中具有广泛的应用场合。     

COMBINATION OF ADAPTIVITY AND MESH SMOOTHING FOR THE FINITE ELEMENT ANALYSIS OF SHELLS WITH INTERSECTIONS

A compatible hierarchical adaptive scheme is proposed which allows to control both density and geometrical properties of meshes with four-node linear finite shell elements. The algorithm produces a sequence of meshes with two aims, nearly equal distribution of the local error in each element and a mesh with regular elements, thus internal element angles near 90° and length ratios of adjacent element sides near unity. This goal is achieved in an efficient manner imposing a combination of a local smoothing algorithm with the adaptive mesh generation. New created nodes are positioned on the real shell surface and shell boundaries which may be given e.g. by CAD data. Also the shell directors are determined from the normals on the real geometry. Shell intersections are detected automatically as common curves of two adjacent shell parts. As a shell continuum cannot be assumed for these intersections and thus simple standard adaptive schemes fail, shell intersections have to be treated in a way similar to shell boundaries. For some numerical examples the developed algorithms are demonstrated and the resulting meshes are shown. © 1997 by John Wiley & Sons, Ltd.     

Small blend suppression from B-rep models in computer-aided engineering analysis

In mechanical design, small blending is a common operation used to improve the strength and aesthetics of the workpiece. In blending operations, certain smooth faces are added to the boundary representation (B-rep) model to smooth sharp edges and vertices. These faces are termed ‘blend faces.’ However, they may affect the quality of analysis; these faces should be meshed with tiny meshes, which may result in an increase in computational time and reduced accuracy of simulation results. Hence, small blend suppression is an approach for improving the quality of generated meshes. Blend suppression is a technique for reverting a blended computer-aided design model to its original unblended status. This study proposes a blend suppression algorithm for removing blend faces in computer-aided engineering (CAE) analysis. The proposed algorithm operates as follows: (1) edge blend faces and vertex blend faces are grouped individually, (2) new geometric data are computed, (3) new elements are added to the data structure of the B-rep model, (4) all data related to blend faces are deleted, and (5) all topological data in the B-rep model are updated. Several examples are presented in this paper to demonstrate the feasibility of the proposed method for blend suppression as well as its advantage in improving the quality of meshes in CAE analysis.     

Marching volume polytopes algorithm

This paper presents an algorithm for the refinement of two- or three-dimensional meshes with respect to an implicitly given domain, so that its surface is approximated by facets of the resulting polytopes. Using a Cartesian grid, the proposed algorithm may be used as a mesh generator. Initial meshes may consist of polytopes such as quadrilaterals and triangles, as well as hexahedrons, pyramids, and tetrahedrons. Given the ability to compute edge intersections with the surface of an implicitly given domain, the proposed marching volume polytopes algorithm uses predefined refinement patterns applied to individual polytopes depending on the intersection pattern of their edges. The refinement patterns take advantage of rotational symmetry. Since these patterns are applied independently to individual polytopes, the resulting mesh may encompass the so-called orientation problem, where two adjacent polytopes are rotated against one another. To allow for a repeated application of the marching volume polytopes algorithm, the proposed data structures and algorithms account for this ambiguity. A simple example illustrates the advantage of the repeated application of the proposed algorithm to approximate domains with sharp corners. Furthermore, finite element simulations for two challenging real-world problems, which require highly accurate approximations of the considered domains, demonstrate its applicability. For these simulations, a variant of the fictitious domain method is used.     

Checking the topological consistency of a finite element mest

Algorithms are described for checking the topological consistency of two- or three-dimensional meshes. Two-dimensional meshes may include mixtures of triangles, quadrilaterals and other polygons with optional edge or centre nodes; three-dimensional meshes may include mixtures of cuboids and tetrahedra with optional edge; sie or internal nodes.     

Q‐Morph: an indirect approach to advancing front quad meshing

Q‐Morph is a new algorithm for generating all‐quadrilateral meshes on bounded three‐dimensional surfaces. After first triangulating the surface, the triangles are systematically transformed to create an all‐quadrilateral mesh. An advancing front algorithm determines the sequence of triangle transformations. Quadrilaterals are formed by using existing edges in the triangulation, by inserting additional nodes, or by performing local transformations to the triangles. A method typically used for recovering the boundary of a Delaunay mesh is used on interior triangles to recover quadrilateral edges. Any number of triangles may be merged to form a single quadrilateral. Topological clean‐up and smoothing are used to improve final element quality. Q‐Morph generates well‐aligned rows of quadrilaterals parallel to the boundary of the domain while maintaining a limited number of irregular internal nodes. The proposed method also offers the advantage of avoiding expensive intersection calculations commonly associated with advancing front procedures. A series of examples of Q‐Morph meshes are also presented to demonstrate the versatility of the proposed method. Copyright © 1999 John Wiley & Sons, Ltd.     

Quality improvement of non‐manifold hexahedral meshes for critical feature determination of microstructure materials

This paper describes a novel approach to improve the quality of non‐manifold hexahedral meshes with feature preservation for microstructure materials. In earlier works, we developed an octree‐based isocontouring method to construct unstructured hexahedral meshes for domains with multiple materials by introducing the notion of material change edge to identify the interface between two or more materials. However, quality improvement of non‐manifold hexahedral meshes is still a challenge. In the present algorithm, all the vertices are categorized into seven groups, and then a comprehensive method based on pillowing, geometric flow and optimization techniques is developed for mesh quality improvement. The shrink set in the modified pillowing technique is defined automatically as the boundary of each material region with the exception of local non‐manifolds. In the relaxation‐based smoothing process, non‐manifold points are identified and fixed. Planar boundary curves and interior spatial curves are distinguished, and then regularized using B‐spline interpolation and resampling. Grain boundary surface patches and interior vertices are improved as well. Finally, the optimization method eliminates negative Jacobians of all the vertices. We have applied our algorithms to two beta titanium data sets, and the constructed meshes are validated via a statistics study. Finite element analysis of the 92‐grain titanium is carried out based on the improved mesh, and compared with the direct voxel‐to‐element technique. Copyright © 2009 John Wiley & Sons, Ltd.     

Anisotropic mesh optimization and its application in adaptivity

The construction of solution-adapted meshes is addressed within an optimization framework. An approximation of the second spatial derivative of the solution is used to get a suitable metric in the computational domain. A mesh quality is proposed and optimized under this metric, accounting for both the shape and the size of the elements. For this purpose, a topological and geometrical mesh improvement method of high generality is introduced. It is shown that the adaptive algorithm that results recovers optimal convergence rates in singular problems, and that it captures boundary and internal layers in convection-dominated problems. Several important implementation issues are discussed. © 1997 John Wiley & Sons, Ltd.     

A compact adjacency‐based topological data structure for finite element mesh representation

This paper presents a novel compact adjacency‐based topological data structure for finite element mesh representation. The proposed data structure is designed to support, under the same framework, both two‐ and three‐dimensional meshes, with any type of elements defined by templates of ordered nodes. When compared to other proposals, our data structure reduces the required storage space while being ‘complete’, in the sense that it preserves the ability to retrieve all topological adjacency relationships in constant time or in time proportional to the number of retrieved entities. Element and node are the only entities explicitly represented. Other topological entities, which include facet, edge, and vertex, are implicitly represented. In order to simplify accessing topological adjacency relationships, we also define and implicitly represent oriented entities, associated to the use of facets, edges, and vertices by an element. All implicit entities are represented by concrete types, being handled as values, which avoid usual problems encountered in other reduced data structures when performing operations such as entity enumeration and attribute attachment. We also extend the data structure with the use of ‘reverse indices’, which improves performance for extracting adjacency relationships while maintaining storage space within reasonable limits. The data structure effectiveness is demonstrated by two different applications: for supporting fragmentation simulation and for supporting volume rendering algorithms. Copyright © 2005 John Wiley & Sons, Ltd.     

An L∞–Lp mesh‐adaptive method for computing unsteady bi‐fluid flows

This paper discusses the contribution of mesh adaptation to high‐order convergence of unsteady multi‐fluid flow simulations on complex geometries. The mesh adaptation relies on a metric‐based method controlling the L ^p‐norm of the interpolation error and on a mesh generation algorithm based on an anisotropic Delaunay kernel. The mesh‐adaptive time advancing is achieved, thanks to a transient fixed‐point algorithm to predict the solution evolution coupled with a metric intersection in the time procedure. In the time direction, we enforce the equidistribution of the error, i.e. the error minimization in L ^∞ norm. This adaptive approach is applied to an incompressible Navier–Stokes model combined with a level set formulation discretized on triangular and tetrahedral meshes. Applications to interface flows under gravity are performed to evaluate the performance of this method for this class of discontinuous flows. Copyright © 2010 John Wiley & Sons, Ltd.     

A new algorithm for contact detection between spherical particle and triangulated mesh boundary in discrete element method simulations

In discrete element method (DEM) simulations of real scale, the spherical particles are commonly employed for increasing the computation speed, and the complex boundary models are represented by triangle meshes with controllable accuracy. A new contact detection algorithm has been developed to resolve the contacts between the spheres and the triangle mesh boundaries. The application of the barycentric coordinates makes this algorithm more efficient to identify contacts in the intersection test. As a particle probably collides with several triangles at the same time, the multiple contacts would be reported as face contacts, edge contacts, or vertex contacts. Moreover, the particle embedding in a triangle can be also contact with the edges or vertices of the next triangles. These contacts should be considered as invalid for updating contact forces in the DEM. To exclude invalid records from the multiple contacts, the algorithm gives attention to the mesh structure nearby contacts and analyzes all possible collision situations. Numerical experiments have been conducted to verify this algorithm by using the algorithm in the DEM simulation framework. The numerical results suggest that the algorithm can resolve all contacts precisely and stably when the spherical particles collide on the complex boundary circumstances. Copyright © 2013 John Wiley & Sons, Ltd.