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.     

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.     

Ray tracing with a space-filling finite element mesh

A new ray-tracing technique is presented which does not work with ray–object intersections per se, but is based on the traversal of an unstructured tetrahedral mesh providing a convex enclosure of a scene of polyhedral objects. The tetrahedral mesh provides tight bounding and an adaptive subdivision of space. This non-hierarchical data structure is traversed adaptively until one is led directly and unconditionally to the first object intersected. Rendering times are directly related to the average thickness of the enclosing mesh since all tetrahedra are traversed in constant time. Since the proposed algorithm operates directly with volume elements, it allows for volumetric rendering effects. Volume rendering or anisotropic media can be implemented without any further effort. This is an important advantage as compared to usual techniques, which only operate on surface data. Timings for several examples show that the use of this type of ray-tracing technique, which is more suitable for general purpose visualization codes than traditional techniques, results in CPU times that are comparable with the best ray-tracing techniques presently used. This is an unexpected and important result, as the vectorization and parallclization of the proposed technique are straightforward, in contrast with traditional ray-tracing techniques.     

A new automatic adaptive 3D solid mesh generation scheme for thin‐walled structures

A new algorithm to generate three‐dimensional (3D) mesh for thin‐walled structures is proposed. In the proposed algorithm, the mesh generation procedure is divided into two distinct phases. In the first phase, a surface mesh generator is employed to generate a surface mesh for the mid‐surface of the thin‐walled structure. The surface mesh generator used will control the element size properties of the final mesh along the surface direction. In the second phase, specially designed algorithms are used to convert the surface mesh to a 3D solid mesh by extrusion in the surface normal direction of the surface. The extrusion procedure will control the refinement levels of the final mesh along the surface normal direction. If the input surface mesh is a pure quadrilateral mesh and refinement level in the surface normal direction is uniform along the whole surface, all hex‐meshes will be produced. Otherwise, the final 3D meshes generated will eventually consist of four types of solid elements, namely, tetrahedron, prism, pyramid and hexahedron. The presented algorithm is highly flexible in the sense that, in the first phase, any existing surface mesh generator can be employed while in the second phase, the extrusion procedure can accept either a triangular or a quadrilateral or even a mixed mesh as input and there is virtually no constraint on the grading of the input mesh. In addition, the extrusion procedure development is able to handle structural joints formed by the intersections of different surfaces. Numerical experiments indicate that the present algorithm is applicable to most practical situations and well‐shaped elements are generated. Copyright © 2004 John Wiley & Sons, Ltd.     

GENERALIZED 3-D PAVING: AN AUTOMATED QUADRILATERAL SURFACE MESH GENERATION ALGORITHM

This paper discusses the extension of the paving algorithm for all quadrilateral mesh generation to arbitrary three-dimensional trimmed surfaces. Methods of calculating angles, projecting elements, and detecting collisions between paving boundaries, for general surfaces are presented. Extensions of the smoothing algorithms for three dimensions are set forth. Advances in the use of scalar sizing functions are presented. These functions can be used to better approximate internal mesh density from boundary densities and surface characteristics.     

Designing reflectors to generate a line-shaped directivity diagram

A novel method of designing a mirror surface to generate a directivity diagram represented as a vector function of one argument is presented. A general relationship for the mirror surface for an arbitrary illuminating beam wavefront is derived as an envelope of a parametric family of surfaces. Each surface in the family transforms the input beam into a beam with plane wavefront of desired direction. For the spherical illuminating beam the mirror surface is given as the envelope of the family of rotational paraboloids. The envelope is represented as a family of curves given by the intersections of paraboloids with circular cones of rays from the point source.     

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.     

Recovery of an arbitrary edge on an existing surface mesh using local mesh modifications

This study describes an algorithm for recovering an edge which is arbitrarily inserted onto a pre‐triangulated surface mesh. The recovery process does not rely on the parametric space of the surface mesh provided by the geometric modeller. The topological and geometrical validity of the surface mesh is preserved through the entire recovery process. The ability of inserting and recovering an arbitrary edge onto a surface mesh can be an invaluable tool for a number of meshing applications such as boundary layer mesh generation, solution adaptation, preserving the surface conformity, and possibly as a primary tool for mesh generation. The edge recovery algorithm utilizes local surface mesh modification operations of edge swapping, collapsing and splitting. The mesh modification operations are decided by the results of pure geometrical checks such as point and line projections onto faces and face‐line intersections. The accuracy of these checks on the recovery process are investigated and the substantiated precautions are devised and discussed in this study. Copyright © 2001 John Wiley & Sons, Ltd.     

Automatic metric 3D surface mesh generation using subdivision surface geometrical model. Part 2: Mesh generation algorithm and examples

In this paper, a new metric advancing front surface mesh generation scheme is suggested. This new surface mesh generator is based on a new geometrical model employing the interpolating subdivision surface concept. The target surfaces to be meshed are represented implicitly by interpolating subdivision surfaces which allow the presence of various sharp and discontinuous features in the underlying geometrical model. While the main generation steps of the new generator are based on a robust metric surface triangulation kernel developed previously, a number of specially designed algorithms are developed in order to combine the existing metric advancing front algorithm with the new geometrical model. As a result, the application areas of the new mesh generator are largely extended and can be used to handle problems involving extensive changes in domain geometry. Numerical experience indicates that, by using the proposed mesh generation scheme, high quality surface meshes with rapid varying element size and anisotropic characteristics can be generated in a short time by using a low‐end PC. Finally, by using the pseudo‐curvature element‐size controlling metric to impose the curvature element‐size requirement in an implicit manner, the new mesh generation procedure can also generate finite element meshes with high fidelity to approximate the target surfaces accurately. Copyright © 2003 John Wiley & Sons, Ltd.     

Applications of mesh smoothing: copy,morph, and sweep on unstructured quadrilateral meshes

Mesh smoothing is demonstrated to be an effective means of copying, morphing, and sweeping unstructured quadrilateral surface meshes from a source surface to a target surface. Construction of the smoother in a particular way guarantees that the target mesh will be a ‘copy’ of the source mesh, provided the boundary data of the target surface is a rigid body rotation, translation, and/or uniform scaling of the original source boundary data and provided the proper boundary node correspondence between source and target has been selected. Copying is not restricted to any particular smoother, but can be based on any locally elliptic second‐order operator. When the bounding loops are more general than rigid body transformations the method generates high‐quality, ‘morphed’ meshes. Mesh sweeping, if viewed as a morphing of the source surface to a set of target surfaces, can be effectively performed via this smoothing algorithm. Published in 1999 by John Wiley & Sons, Ltd. This article is a U.S. government work and is in the public domain in the United States.     

Automatic coarse registration of three-dimensional surfaces by information theoretic selection of salient points

We describe a new method to register surface data measured by optical three-dimensional (3-D) sensors from various views of an object. With our method, complete 3-D models of objects can be generated without user interaction. Circumferential acquisition of 3-D objects is done by taking several views from different directions. To generate a complete 3-D-model, the views must be aligned with each other. This process is called registration and is commonly done interactively by searching for so-called corresponding points in the different views and by use of these points to calculate the appropriate rotation and translation. Our approach is based on automatically finding points that are eye catching or salient compared with other surface points. We derive a quantitative measure of point salience and a feature definition for free-form surfaces by introducing a concept to measure pragmatic information. Experiments confirm that our salient points can be robustly located on general free-form surfaces, even if there are no corners or edges. Furthermore, the neighborhoods of the salient points are highly distinguishable from each other. This results in a large reduction of the complexity of the subsequent geometric matching. The computing time is only a few seconds. We present results from various fields of application.     

Mesh Layer Jamming to Cover and Secure Curved Surfaces without Wrinkles

Layer jamming technologies, which can alter the stiffness of layered sheets enveloped in an elastic bag via internal vacuum pressure, have typically been used for wearable robots. However, wrinkles on the layer jamming element covering the body impair the feeling of wear and are undesirable. Aligning curved surfaces using sheets without wrinkling requires the sheets to be sufficiently elastic, which reduces the stiffness when used for layer jamming. Mesh sheets (i.e., woven fabrics) cannot elongate along the fibers; however, they can elongate and contract in the diagonal direction by changing their shape. This study proposes using mesh sheets for layer jamming and analytically and experimentally demonstrates their ability to fit curved surfaces without wrinkling. The layer jamming element using mesh sheets changes the bending stiffness in proportion to the internal vacuum pressure and the number of sheets, as in conventional layer jamming. The simple structure and flexibility of the mesh layer jamming are not only suitable for fixing a body or fragile objects but also extend the range of applications using layer jamming technologies. This study also provides a foundation for investigating the wrinkle formation associated with curved surface deformation unique to flexible robots.     

A surface mesh smoothing and untangling method independent of the CAD parameterization

A method to optimize triangular and quadrilateral meshes on parameterized surfaces is proposed. The optimization procedure relocates the nodes on the surface to improve the quality (smooth) and ensures that the elements are not inverted (untangle). We detail how to express any measure for planar elements in terms of the parametric coordinates of the nodes. The extended measures can be used to check the quality and validity of a surface mesh. Then, we detail how to optimize any Jacobian-based distortion measure to obtain smoothed and untangled meshes with the nodes on the surface. We prove that this method is independent of the surface parameterization. Thus, it can optimize meshes on CAD surfaces defined by low-quality parameterizations. The examples show that the method can optimize meshes composed by a large number of inverted elements. Finally, the method can be extended to obtain high-order meshes with the nodes on the CAD surfaces.     

基于黎曼度量参数曲面四边形网格生成方法及UG实现

论文给出了基于黎曼度量的参数曲面网格生成的改进铺砖算法。阐述了曲面自身的黎曼度量,并且运用黎曼度量计算二维参数域上单元节点的位置,从而使映射到三维物理空间的四边形网格形状良好。文中对原有铺砖法相交处理进行了改进,在运用铺砖法的同时调用UG-NX强大的二次开发库函数获取相应的信息,直接在UG-NX模型的表面生成四边形网格。算例表明,该法能在曲面上生成质量好的网格。     

Insertion of triangulated surfaces into a meccano tetrahedral discretization by means of mesh refinement and optimization procedures

In this paper, we present a new method for inserting several triangulated surfaces into an existing tetrahedral mesh generated by the meccano method. The result is a conformal mesh where each inserted surface is approximated by a set of faces of the final tetrahedral mesh. First, the tetrahedral mesh is refined around the inserted surfaces to capture their geometric features. Second, each immersed surface is approximated by a set of faces from the tetrahedral mesh. Third, following a novel approach, the nodes of the approximated surfaces are mapped to the corresponding immersed surface. Fourth, we untangle and smooth the mesh by optimizing a regularized shape distortion measure for tetrahedral elements in which we move all the nodes of the mesh, restricting the movement of the edge and surface nodes along the corresponding entity they belong to. The refining process allows approximating the immersed surface for any initial meccano tetrahedral mesh. Moreover, the proposed projection method avoids computational expensive geometric projections. Finally, the applied simultaneous untangling and smoothing process delivers a high‐quality mesh and ensures that the immersed surfaces are interpolated. Several examples are presented to assess the properties of the proposed method.     

A new approach to free-form surface mesh control in a CAD environment

An adaptive process controlling the position of nodes on a surface mesh is presented. The control can depend on one (or more) criterion(ria) about element quality. The mesh is attached, through the concept of classification, to a geometric model issued by a computer aided design software. Thus, the surface domain is described by entities currently available in such systems, i.e. any free-form patches like Non-Uniform Rational B-Spline or Bézier patches can be used, even if they are restricted. Multi-connected surface domains can be treated using the same geometrical definition. The method described allows nodes to slide on a patch or jump from a patch onto another one. Such movements greatly improve the mesh quality with regard to a chosen criterion. Problems occurring with patch-by-patch meshing techniques when surfaces patches exhibit significant size differences are then overcome. The adaptation technique can be made independent of CAD data structures and meshing techniques, hence it constitutes the basis of a mesh management module.     

An extended advancing front technique for closed surfaces mesh generation

An extended advancing front technique (AFT) with shift operations and Riemann metric named as shifting‐AFT is presented for finite element mesh generation on 3D surfaces, especially 3D closed surfaces. Riemann metric is used to govern the size and shape of the triangles in the parametric space. The shift operators are employed to insert a floating space between real space and parametric space during the 2D parametric space mesh generation. In the previous work of closed surface mesh generation, the virtual boundaries are adopted when mapping the closed surfaces into 2D open parametric domains. However, it may cause the mesh quality‐worsening problem. In order to overcome this problem, the AFT kernel is combined with the shift operator in this paper. The shifting‐AFT can generate high‐quality meshes and guarantee convergence in both open and closed surfaces. For the shifting‐AFT, it is not necessary to introduce virtual boundaries while meshing a closed surface; hence, the boundary discretization procedure is largely simplified, and moreover, better‐shaped triangles will be generated because there are no additional interior constraints yielded by virtual boundaries. Comparing with direct methods, the shifting‐AFT avoids costly and unstable 3D geometrical computations in the real space. Some examples presented in this paper have demonstrated the advantages of shift‐AFT in 3D surface mesh generation, especially for the closed surfaces. Copyright © 2007 John Wiley & Sons, Ltd.     

An effective 3D meshing approach for fractured rocks

An effective mesh generation algorithm is proposed to construct mesh representations for arbitrary fractures in 3D rock masses. With the development of advanced imaging techniques, fractures in a rock mass can be clearly captured by a high‐resolution 3D digital image but with a huge data set. To reduce the data size, corresponding mesh substitutes are required in both visualization and numerical analysis. Fractures in rocks are naturally complicated. They may meet at arbitrary angles at junctions, which could derive topological defects, geometric errors or local connectivity flaws on mesh models. A junction weight is proposed and applied to distinguish fracture junctions from surfaces by an adequate threshold. We take account of fracture junctions and generate an initial surface mesh by a simplified centroidal Voronoi diagram. To further repair the initial mesh, an innovative umbrella operation is designed and adopted to correct mesh topology structures and preserve junction geometry features. Constrained with the aforementioned surface mesh of fracture, a tetrahedral mesh is generated and substituted for the 3D image model to be involved in future numerical analysis. Finally, we take two fractured rock samples as application examples to demonstrate the usefulness and capability of the proposed meshing approach. Copyright © 2015 John Wiley & Sons, Ltd.