Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-10-13
2001-07-10
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06259453
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a meshing method, and more particularly to a meshing method using bubbles.
2. Description of the Related Art
Meshing or mesh generation is a process for dividing a geometric model-generated computer-aided design (CAD) into a set of small elements. A two-dimensional mesh is provided mainly by a triangular mesh or a quadrilateral mesh. In a computer simulation, such as an analysis of a car crash, a reliable solution cannot be obtained by using a triangular mesh, and a quadrilateral mesh is often employed.
However, while a bubble mesh method for the automatic generation of a triangular mesh is established, as described in, for example, Japanese Unexamined Patent Publication No. Hei 7-230487 and No. Hei 8-315183, there are very few practical methods for automatically generating a quadrilateral mesh. Therefore, in generating a quadrilateral mesh, many analysts rely on a method that is labor-intensive and time-consuming (e.g., several months) to acquire the CAD data for one vehicle.
Further, while there is a large demand for a triangular mesh generation function in the thermal/fluid analysis field, demands also exist for an automatic generation method for a quadrilateral mesh (e.g., a hexahedral mesh in three dimensions) that can be expanded into a three-dimensional shape.
As described above, although there is a large demand for an automatic quadrilateral mesh generation method, not only is automatic generation difficult to achieve, but also the following procedural constituents must be considered.
(1) Little Distortion of Generated Quadrilateral Elements.
According to an analysis performed using computational dynamics, an extremely long element or an element having an extremely large (or small) angle adversely affects the analysis result. Ideally, preferably all the quadrilateral elements have a shape that is as nearly square as possible.
(2) Control of the Direction in which Generated Quadrilateral Elements are Aligned.
According to an analysis performed using the computational dynamics, in many cases it is preferable that elements are aligned in a direction of the physical quantity, such as a stress, or in a direction toward the boundary of a region of a geometric model. Thus, a mesh is desirably generated wherein most of the elements are regularly aligned in a direction designated by a user.
(3) Control of the Distribution of Element Sizes.
To reduce the computation time of applications, preferably fine mesh elements are generated for important portions, and rough mesh elements are generated for less important portions. However, when the size of the mesh elements is suddenly changed, the T-structure (e.g., the state in which the nodal points of adjacent elements lie on a chord) occurs, and adversely affects the analysis. Therefore, the distribution should be provided that is appropriate for the size of the mesh elements, while it can be guaranteed that the connections of the elements will be performed with a nodal point and a chord that is shared.
(4) Applicability to Complicated Curved Model.
There are a variety of shapes that are designed using CAD (e.g., a trim curved shape obtained by cutting one part of a curved region, or a very winding curved shape). It is desirable that a quadrilateral mesh is automatically generated for such a curved shape.
(5) Expansion into a Three-dimensional Mesh.
In accordance with an analysis performed using a current computational dynamics, by providing an improved computation capability, a geometric model is expanded from a two-dimensional model to a three-dimensional model. However, providing a quadrilateral mesh (hexahedral mesh) to be used for a three-dimensional model is still seldom done. Therefore, a method for expanding a two-dimensional mesh into a three-dimensional mesh is desirable that is based on the same operating principle.
According to the above described bubble mesh method, bubbles are generated in a region of a geometric model to be meshed and are moved to stable locations, and the centers of the bubbles are connected to generate a triangle mesh. The main methods employed for generating a quadrilateral mesh from a triangular mesh are as follows:
(1) Method for Linking two Adjacent Triangles to Form a Single Quadrilateral.
Pairing for linking triangles is difficult, and one triangle will remain unlinked if the number of triangles is not even. Further, the thus formed quadrilateral is normally a parallelogram, neither a square nor a rectangle, which are preferable shapes of the mesh element.
(2) Method for Dividing a Triangle into Three Segments.
It is difficult to generate a quadrilateral that is anisotropic.
With either of the above methods problems are encountered in automatic quadrilateral generation with regard to the direction, and currently, merely a heuristic rule is employed in the phase devoted to resolving these problems. Additionally, the method proposed for changing a triangular mesh into a quadrilateral mesh is not very practical, even though the expansion into a three-dimensional mesh is theoretically possible.
Conventional methods for generating a quadrilateral mesh are as follows:
(1) Method for Utilizing Regional Division Performed by a User.
This method is a so-called “mapped mesh” method, whereby a geometric model is divided in advance into regions having three or four sides by manipulating a mouse, and the divided regions are further divided into a lattice shape (e.g., see “Finite Element Mesh Generation Method: a Review and Classification,” Ho-Le K.,
Computer Aided Designing
, Vol. 20, No. 1, 1988, pp. 27-38). According to this method, since the regional division is performed manually, this runs counter to the requirement for automatic generation. When a mesh is to be generated for all the parts of a vehicle, the job will be enormous. Further, since the result of the regional division, which is a pre-process, varies depending on the user, the mesh generation results obtained differ from user to user.
(2) Method for Sequentially Generating Quadrilateral Elements from the Boundary of Regions.
This method is a so-called “advancing front mesh” method (“Paving: A New Approach to Automated Quadrilateral Mesh Generation,” Blacker T. D.,
International Journal for Numerical Methods in Engineering
. Vol. 32, pp. 811-847, 1991). According to this method, a row of quadrilateral elements is generated along a region boundary, and another row of quadrilateral elements is generated inside. This process is repeated until the region is filled with quadrilateral elements. However, since the elements inside the region tend to be deformed, requirement (1) is not satisfied. Additionally, since the direction in which the elements are aligned is limited to the direction along the boundary of the regions, requirement (2) is not satisfied.
(3) Method for Embedding Two-dimensional/three-dimensional Lattices Inside a Region.
Two-dimensional lattices or three-dimensional lattices are embedded inside the region, and the surrounding boundaries of the regions are processed by an exception process to generate a mesh. With this method, since the quality of the mesh around the boundaries may be very low and this tends to adversely affect the accuracy of the analysis, requirement (1) is not satisfied. Additionally, since control of the element size is difficult, requirement (3) is not satisfied.
SUMMARY OF THE INVENTION
In view of the foregoing and other problems and drawbacks of the conventional systems and methods, an object of the present invention is to provide a meshing method for automatically generating a quadrilateral mesh.
Another object of the present invention is to provide a meshing method for generating a quadrilateral mesh having less distortion.
Yet another object of the present invention is to provide a meshing method for designating an alignment direction of a quadrilateral mesh that is to be generated.
A further object of the present invention is to provide a hexahedral mesh generation method which enables mesh generation performed in two
Furuhata Tomotake
Inoue Keisuke
Itoh Takayuki
Yamada Atsushi
International Business Machines - Corporation
McGinn and Gibb, PLLC
Nguyen Phu K.
Percello, Esq. Louis J.
LandOfFree
Meshing method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Meshing method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Meshing method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523856