Static structures (e.g. – buildings) – Compound curve structure – Geodesic shape
Reexamination Certificate
2001-06-08
2003-09-30
Friedman, Carl D. (Department: 3635)
Static structures (e.g., buildings)
Compound curve structure
Geodesic shape
C052S081300, C052S081500
Reexamination Certificate
active
06625938
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by any one of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention broadly relates to automatic volume discretization of a geometric object using hexahedral elements, and, more particularly, to a system and method to convert a hex-dominant mesh structure into an all-hex mesh structure using all-hex templates where each template is composed of a family of modular hexahedral sub-templates and where triangular and rectangular patterns can be freely combined on the template's exterior faces.
2. Description of the Related Art
Finite element analysis is a numerical method that solves mathematical problems in engineering and physics for determining the physical behavior of a geometric object or region. Finite element analysis is used in approximating any continuous physical characteristic or behavior (such as structural mechanics, effect of temperature, pressure, heat, or an electric field, etc.) of a geometric region by a discrete model of a set of piece-wise continuous functions. The geometric region is broken into discrete elements interconnected at discrete node points. Typically, finite element analysis is performed on a computer in a three-step procedure comprising the steps of pre-processing, processing, and post-processing. In the pre-processing step, geometric boundary data representing the geometric region to be analyzed is taken, and a mesh of geometrical elements covering the domain of the geometric region is generated. Thus, mesh generation is the process of discretizing a continuous geometry into small elements for use in the finite element analysis. In the processing step, the element data are taken and mathematical equations are applied to solve for the characteristic of interest across the domain through use of matrix equations. For example, a stimulus is applied to the mesh data and the reaction of the mesh data to the stimulus is analyzed. In the post-processing step, the results of this finite element analysis are output, for example, in a graphical representation of the characteristic of interest.
Traditionally, generating a mesh for a given geometry has been very tedious, time consuming, and error prone. However, with the advent of sophisticated computing machines, the mesh generation process is substantially automated. The automated meshing systems for general three-dimensional (3D) volumes traditionally give tetrahedral- or hexahedral-shaped elements, or a combination of the two types. A mesh is constrained in terms of how elements share subfacets within the mesh. This problem is much less constrained for tetrahedral or mixed element meshes, hence tetrahedral and mixed element meshing algorithms have. received the most attention in the past. However, due to increased- accuracy and efficiency of eight-node hexahedral elements for non-linear structural mechanics and other applications, there is a growing demand for all-hex meshing systems. The discussion hereinbelow refers to a hexahedral element as a “hex.”
FIG. 1
shows a hex-dominant mesh
10
and its constituent elements. A hex-dominant mesh (e.g., the mesh
10
) is a three-dimensional mesh that consists of four types of elements—hexahedral elements (e.g., elements
16
in the mesh
10
), prism elements (e.g., elements
18
in the mesh
10
), pyramid elements (e.g., elements
12
in the mesh
10
) and tetrahedral elements (e.g., elements
14
in the mesh
10
)—as illustrated in FIG.
1
. An all-hex mesh is a mesh that consists of exclusively hexahedral elements.
Although it would be ideal if an all-hex mesh could be generated for an arbitrary three-dimensional shape without going through a hex-dominant mesh, the direct all-hex meshing problem is known to be highly challenging, and none of the existing methods always succeeds to create a valid all-hex mesh for a complex three-dimensional geometry. A few of such existing methods of all-hex mesh creation are described in the following: (1) Blacker, T. D. and R. J. Meyers, “Seams and Wedges in Plastering: A 3-D Hexahedral Mesh Generation Algorithm,” Engineering with Computers, 1993, 2(9), pp. 83-93 (hereinafter, “Meyers”); (2) Tautges, T. J., T. Blacker, and S. A. Mitchell, “The Whisker Weaving Algorithm: A Connectivity-Based Method for Constructing All-Hexahedral Finite Element Meshes”, International Journal for Numerical Methods in Engineering, 1996, vol. 39, pp. 3327-3349 (hereafter, “Blacker”); and (3) U.S. Pat. No. 5,768,156, issued on Jun. 16, 1998 to Tautges et al. (hereafter, “Tautges”). Although there exists a trivial solution—reating a tetrahedral mesh first and subdividing each of the tetrahedral elements (hereafter, “tet”) into four smaller hex elements—topological and geometric irregularity of such an all-hex mesh is so poor that this method is not used in practice. Creating a quality hex-dominant mesh, on the other hand, is an easier problem, either by hand or by an automated algorithm as described in (1) Owen, S. J., S. A. Canann, and S. Saigal, “Pyramid Elements for Maintaining Tetrahedra to Hexahedra Confornability”, AMD-Vol. 220, Trend in Unstructured Mesh Generation, ASME, 1997, pp. 123-129 (hereafter “Owen”); and (2) Owen, S. J. and S. Saigal, “H-Morph: An Indirect Approach to Advancing Front Hex Meshing”, International Journal for Numerical Methods in Engineering, 2000, 49, pp. 289-312 (hereafter “Saigal”). The disclosures of Owen and Saigal are incorporated herein by reference in their entireties.
In order to highlight the difficulty in developing conversion templates for all-hex meshing, it is important to take a look at a much easier, two-dimensional problem of converting a quad-dominant mesh to an all-quad mesh.
FIG. 2
illustrates conversion of a quad-dominant mesh
20
into an all-quad mesh
22
. The input quad-dominant mesh
20
includes a number of quadrilaterals (or quads)
21
and triangles
23
.
FIG. 3
illustrates two types of templates for converting a quad-dominant mesh into an all-quad mesh. The template quadrilateral
30
is shown with its constituent all-quad elements
32
, and the, template triangle
34
is shown with its constituent all-quad elements
36
. The conversion of the mesh
20
in
FIG. 2
is accomplished with only these two types of templates shown in FIG.
3
. In
FIG. 2
, the quad elements for quadrilaterals
21
are depicted by the numeral
25
, and the quad elements for triangles
23
are depicted by the numeral
27
. With the two types of templates shown in
FIG. 3
, it is guaranteed that any quad-dominant mesh can be converted to an all-quad mesh.
During this all-quad mesh conversion it is important to maintain the interface conformity, or the topological and geometric conformity between adjacent mesh elements. To maintain the conformity each of the all interior edges of a final mesh must be shared by exactly two elements. By using the two templates shown in
FIG. 3
, it is trivial to satisfy such conformity in the all-quad mesh conversion because all the edges of an input quad-dominant mesh are always split into two segments.
In the all-hex mesh conversion problem, a similar interface comformity requirement still exists. The common method for converting a hex-dominant mesh into an all-hex mesh is to subdivide, or dice, a non-hex element into a set of smaller hexes. A hex in the original mesh is also subdivided into a set of smaller hexes. However, it is noted that in a final all-hex mesh, all the interfaces between adjacent hexes must be quadrilaterals, and each of the quadrilaterals must be shared by exactly two hexes in order to maintain the conformity.
Despite the apparent similarity of the problem statement, the all-hex mesh conversion problem turns out significantly more challenging than the all-quad mesh conversion proble
Shimada Kenji
Yamakawa Soji
Carnegie Mellon University
Friedman Carl D.
Katcheves Basil
Kirkpatrick & Lockhart LLP
LandOfFree
System and method for converting a hex-dominant mesh to an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for converting a hex-dominant mesh to an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for converting a hex-dominant mesh to an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3039803