An approach for extracting non-manifold mid-surfaces of thin-wall solids using chordal axis transform

This paper proposes an approach for extracting non-manifold mid-surfaces of thin-wall solids using the chordal axis transform (CAT) (Prasad in CNLS Newsletter—Center for Nonlinear Studies, Los Alamos National Laboratory, vol 139, 1997). There is great demand for extracting mid-surfaces as it is used in dimension reduction. Quadros and Shimada previously used CAT in extracting 2-manifold mid-surfaces of a particular type of thin-wall solids. The proposed approach is an extension of the previous approach (Quadros and Shimada in 11th international meshing roundtable, 2002) in order to extract non-manifold mid-surfaces of general thin-wall solids. The three steps involved in extracting the mid-surface of a thin-wall solid are: (1) generating a tet mesh of a thin-wall solid without inserting interior nodes; (2) generating a raw mid-surface by smart cutting of tets; and (3) remeshing the raw mid-surface via smart clean-up. In the proposed approach, a discrete model (i.e., a tet mesh without any interior nodes) is used instead of working directly on a CAD model. The smart cutting of tets using CAT yields correct topology at the non-manifold region in the raw mid-surface. As the raw mid-surface is not directly suitable for engineering purposes, it is trimmed using a smart clean-up procedure and then remeshed. The proposed approach has been implemented using C++ in commercial ALGOR finite element analysis software. The proposed approach is computationally efficient and has shown effective results on industrial models.     

Hexahedral Mesh Generation by Successive Dual Cycle Elimination

We propose a new method for constructing all-hexahedral finite element meshes. The core of our method is to build up a compatible combinatorial cell complex of hexahedra for a solid body which is topologically a ball, and for which a quadrilateral surface mesh of a certain structure is prescribed. The step-wise creation of the hex complex is guided by the cycle structure of the combinatorial dual of the surface mesh. Our method transforms the graph of the surface mesh iteratively by changing the dual cycle structure until we get the surface mesh of a single hexahedron. Starting with a single hexahedron and reversing the order of the graph transformations, each transformation step can be interpreted as adding one or more hexahedra to the so far created hex complex. Given an arbitrary solid body, we first decompose it into simpler subdomains equivalent to topological balls by adding virtual 2-manifolds. Secondly, we determine a compatible quadrilateral surface mesh for all subdomains created. Then, in the main part we can use the core routine to build up a hex complex for each subdomain independently. The embedding and smoothing of the combinatorial mesh(es) finishes the mesh generation process. First results obtained for complex geometries are encouraging.     

Hexahedral Mesh Generation using the Embedded Voronoi Graph

This work presents a new approach for automatic hexahedral meshing, based on the embedded Voronoi graph. The embedded Voronoi graph contains the full symbolic information of the Voronoi diagram and the medial axis of the object, and a geometric approximation to the real geometry. The embedded Voronoi graph is used for decomposing the object, with the guiding principle that resulting sub-volumes are sweepable. Sub-volumes are meshed independently, and the resulting meshes are easily combined and smoothed to yield the final mesh. The approach presented here is general and automatic. It handles any volume, even if its medial axis is degenerate. The embedded Voronoi graph provides complete information regarding proximity and adjacency relationships between the entities of the volume. Hence, decomposition faces are determined unambiguously, without any further geometric computations. The sub-volumes computed by the algorithm are guaranteed to be well-defined and disjoint. The size of the decomposition is relatively small, since every sub-volume contains a different Voronoi face. Mesh quality seems high since the decomposition avoids generation of sharp angles, and sweep and other basic methods are used to mesh the sub-volumes.     

Adaptive Shape-Sensitive Meshing of the Medial Axis

The medial axis transform provides an alternative representation of geometric shape that has many useful properties for analysis modeling. Applications include decomposition of general solids into subregions for mapped meshing, identification of slender regions for dimensional reduction and recognition of small features for suppression. To serve these purposes effectively, it is important to be able to mesh the medial axis so that its geometry is adequately approximated. This paper describes a general idea, which is based on equal distance criteria, for adaptive mesh refinement on the medial axis, assuming its topology has been defined. The completed set of theories and examples for 2D planar objects and 3D solid objects is presented. ID="A1" Correspondence and offprint requests to: C. Armstrong, The Queen's University of Belfast, Ashby Building, Stranmillis Road, Belfast, BT9 5AH. E-mail: c.armstrong@qub.ac.uk     

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.     

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.     

六面体网格生成和优化研究进展

文中总结了近十几年来六面体网格生成和优化的研究进展.首先概述六面体网格生成的研究进展,将其归为整体生成方法和基于模型分解的生成方法2类,并指出各类方法的优缺点;然后概述六面体网格优化的研究现状,包括几何优化和拓扑优化;最后阐述六面体网格生成与优化的发展趋势.     

Skeleton-based computational method for the generation of a 3D finite element mesh sizing function

This paper focuses on the generation of a three-dimensional (3D) mesh sizing function for geometry-adaptive finite element (FE) meshing. The mesh size at a point in the domain of a solid depends on the geometric complexity of the solid. This paper proposes a set of tools that are sufficient to measure the geometric complexity of a solid. Discrete skeletons of the input solid and its surfaces are generated, which are used as tools to measure the proximity between geometric entities and feature size. The discrete skeleton and other tools, which are used to measure the geometric complexity, generate source points that determine the size and local sizing function at certain points in the domain of the solid. An octree lattice is used to store the sizing function as it reduces the meshing time. The size at every lattice-node is calculated by interpolating the size of the source points. The algorithm has been tested on many industrial models, and it can be extended to consider other non-geometric factors that influence the mesh size, such as physics, boundary conditions, etc.Sandia National Laboratory is a multiprogram laboratory operated by the Sandia Corporation, a Lockheed Martin Company, for the US Department of Energy under contract DE-AC04-94AL85000.     

Medial axis of a planar region by offset self-intersections

The medial axis (MA) of a planar region is the locus of those maximal disks contained within its boundary. This entity has many CAD/CAM applications. Approximations based on the Voronoi diagram are efficient for linear-arc boundaries, but such constructions are more difficult if the boundary is free. This paper proposes an algorithm for free-form boundaries that uses the relation between MA and offsets. It takes the curvature information from the boundary in order to find the self-intersections of successive offset curves. These self-intersection points belong to the MA and can be interpolated to obtain an approximation in Bézier form. This method also approximates the medial axis transform by using the offset distance to each self-intersection.     

HEXHOOP: Modular Templates for Converting a Hex-Dominant Mesh to an ALL-Hex Mesh

This paper presents a new mesh conversion template called HEXHOOP, which fully automates a con-version from a hex-dominant mesh to an all-hex mesh. A HEXHOOP template subdivides a hex/prism/pyramid element into a set of smaller hex elements while main-taining the topological conformity with neighboring elements. A HEXHOOP template is constructed by assembling sub-templates, cores and caps. A dicing template for a hex and a prism is constructed by choosing the appropriate combination of a core and caps. A template that dices a pyramid without losing conformity to the adjacent element is derived from a HEXHOOP template. Some experimental results show that the HEXHOOP templates successfully convert a hex-dominant mesh into an all-hex mesh. ID="A1" Correspondence and offprint requests to: K. Shimada, Department of Mechanical Engineering, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213–3890, USA. E-mail: shimada@cmu.edu     

Parallel generation of unstructured surface grids

In this paper, a new grid generation system is presented for the parallel generation of unstructured triangular surface grids. The object-oriented design and implementation of the system, the internal components and the parallel meshing process itself are described. Initially in a rasterisation stage, the geometry to be meshed is analysed and a smooth distribution of local element sizes in 3-D space is set up automatically and stored in a Cartesian mesh. This background mesh is used by the advancing front surface mesher as spacing definition for the triangle generation. Both the rasterisation and the meshing are MPI-parallelised. The underlying principles and strategies will be outlined together with the advantages and limitations of the approach. The paper will be concluded with examples demonstrating the capabilities of the presented approach.

Medial Axis Construction in Three Dimensions and its Application to Mesh Generation

An algorithm for the construction of the medial axis of a three-dimensional body given by a triangulation of its bounding surface is described. The indirect construction is based on the Delaunay-triangulation of a set of sample points on the bounding surface. The point set is refined automatically so as to capture the correct topology of the medial axis. The computed medial axis (or better medial surface) is then used for hex-dominant mesh generation. Quad-dominant meshes are generated on the medial subfaces first and extruded to the boundary of the body at both sides. The resulting single cell layer is subdivided in direction normal to the boundary, yielding columns of hexahedral and three-sided prismatic cells. The resulting volume mesh is orthogonal at the boundary and ‘semi-structured’ between boundary and medial surface. Mixed cell types (tets, pyramids, degenerate hexahedra) may result along the medial surface. An advancing front algorithm (paving) is used for meshing the subfaces of the medial surface. Development of the mesh generator has not been fully completed with respect to degenerate parts of the medial axis. First medium-complexity bodies have been meshed, however, showing moderate meshing times.     

Fully automatic and fast mesh size specification for unstructured mesh generation

A fully automatic surface mesh generation system is presented in this paper. The automation is achieved by an automatic determination of a consistent mesh size distribution, which is based on geometry rasterisation. The user specifies a minimal and maximal allowed mesh size, and a maximal allowed curvature angle for the complete geometry, or, rather, parts of it. Now, these local curvature and local characteristic lengths of the geometry are computed, which determine the local mesh size. These local mesh sizes are stored and smoothed in a Cartesian background mesh. Afterwards, the triangulation is generated by an advancing front triangulator: the local resolution of the surface triangulation is determined by the mesh sizes stored in the Cartesian background mesh. The object-oriented design and implementation is described. The complete system is very fast due to an efficient parallelisation based on MPI for computer systems with distributed memory.     

A divide and conquer algorithm for medial surface calculation of planar polyhedra

The Medial Axis Transform surface, (or MAT or MS) is proving to be a useful tool for several applications and geometric reasoning tasks. However, calculation of the MAT is a time-consuming task and the benefits of the mathematical-based tool are offset by the cost of the calculation. This paper presents a method for medial surface calculation which uses subdivision to simplify the problem and hence speed up the calculation, a so-called ‘divide-and-conquer’ approach. The basis for this is a modification of the dual structure of the original object. As the calculation proceeds this structure is broken up into sub-pieces each representing a simpler sub-part of the MAT. Perhaps more importantly, this method creates a correct node decomposition of the dual structure. The paper goes on to demonstrate some applications of the results for geometric tasks, specifically offsetting and model subdivision, which are normally expensive but are simpler based on the MAT calculation results.     

Computing medial axes of generic 3D regions bounded by B-spline surfaces

A new approach is presented for computing the interior medial axes of generic regions in R³ bounded by C⁽⁴⁾-smooth parametric B-spline surfaces. The generic structure of the 3D medial axis is a set of smooth surfaces along with a singular set consisting of edge curves, branch curves, fin points and six junction points. In this work, the medial axis singular set is first computed directly from the B-spline representation using a collection of robust higher order techniques. Medial axis surfaces are computed as a time trace of the evolving self-intersection set of the boundary under the the eikonal (grassfire) flow, where the bounding surfaces are dynamically offset along the inward normal direction. The eikonal flow results in special transition points that create, modify or annihilate evolving curve fronts of the (self-) intersection set. The transition points are explicitly identified using the B-spline representation. Evolution of the (self-) intersection set is computed by adapting a method for tracking intersection curves of two different surfaces deforming over generalized offset vector fields. The proposed algorithm accurately computes connected surfaces of the medial axis as well its singular set. This presents a complete solution along with accurate topological structure.