Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1998-05-14
2001-02-20
Lee, Thomas C. (Department: 2782)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S169000, C700S118000, C700S187000, C382S203000
Reexamination Certificate
active
06192293
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for meshing a curved surface that is employed in the fields of analysis of computational dynamics (CAE), NC machining (CAM), building of a three-dimensional shape (CAD), and computer graphics (CG).
2. Related Art
The technique for meshing a curved surface, which divides into a set of triangles a curved surface including a curved shape defined by a parametric curved surface expression, such as a Bezier surface patch or NURBS, has been very important for the above described fields. For example, in the CAE field, the meshing technique is employed for a finite-element method performed by a computer, such as the analysis of a car collision, and in the CAM field, the meshing technique is employed when shaving a curved shape using an NC machine. In the CAD field, the meshing technique is employed for a case wherein a three-dimensional shape is expressed as a set of triangles and a more detailed shape is to be built by repeating the deformation while expending minimum energy. In the CG field, the meshing technique is employed to display a curved surface.
Various methods are employed for meshing a curved surface, and a method that satisfies the following conditions is required.
(1) A trimmed curved surface can be a target for meshing. A trimmed curved surface is a curved shape that is obtained by extracting one necessary part from a curved domain having a triangular or square boundary, such as a Bezier surface patch or NURBS. A shape that has an inside hole is also a trimmed curved surface. Many curved shapes designed by using CAD system are expressed by trimmed curved surfaces, and it is very advantageous to be able to generate meshes relative to a trimmed curved surface.
(2) A complicated curved shape can be processed. It is important to be able to handle a very winding curved shape and a curved shape where two points that are separated by a long interval in parametric space exist close in real space. As a rare case, a self-intersecting curved shape is one example.
(3) Distribution of the sizes of generated elements can be controlled. It is also important that small mesh elements can be generated in an important portion on a curved surface and that large mesh elements can be generated in a portion that is not so important, and that mesh elements that have a distribution in accordance with the curvature of a curved surface can be generated.
(4) A triangular element having a designated shape can be generated. Frequently, required mesh elements have triangular shapes. The triangular shape must be as close to an equilateral triangle as possible. This is because, as well known, when a finite-element analysis method is performed using a mesh that includes extremely distorted elements, it has an adverse effect. Since sometimes an elongated triangle is required, it is also important that a triangle (and/or a square) that is similar to a designated shape can be generated.
(5) The processing should be automatically performed. Although there is a manual meshing method, a desirable method is one for which a pre-process is not required and with which a mesh can be automatically provided by merely inputting the shape type and the mesh distribution.
As a mesh generation method that satisfies the conditions (3) and (5) for a flat surface domain instead of a curved surface, there is a bubble meshing method (“Automatic Mesh Division Using Physical Model,” Kenji Shimada, Japanese Simulation Institute, vol. 12, No. 1, 1993, pp. 11-20). The bubble meshing method is a mesh generation method that employs an optimal allocation of mesh nodes, which is obtained by a dynamic calculation, and Delaunay triangular division. An example where the bubble meshing method is applied for a curved surface has been reported (“Comparison of Discretization Algorithms for NURBS Surfaces with Application to Numerically Controlled Machining,” S. P. Austin, R. B. Jerard and R. L. Drysdale, Computer Aided Design, Vol. 29, No. 1, 1997, pp. 71-83). In this paper, although the distribution of parameters is not uniform in a normal curved shape, normal Delaunay triangular division is performed in parametric space. As a result, a preferable mesh (mesh that can satisfy the condition (4)) can not be generated on a curved surface in real space. Another paper (“Most Tightly Packing in Sphere and Automatic Triangular Mesh Division of Curved Surface by Delaunay Net,” Kenji Shimada, 67th Graphics and CAD Research in Information Processing Institute, 1994, pp. 11-20) describes the movement of a circular or spherical bubble to the optimal position on a curved surface and the adaptive controlling of the number of bubbles on a curved surface. In this paper, since a process for moving a bubble to an optimal position on a curved surface is performed, a process for restricting to a curved surface a bubble whose optimal position is apart from a curved surface because of inter-bubble force is required. In addition, a process concerning three-dimensional space is also required. In the above paper, the previously mentioned condition (4) is not taken into account.
Further, an example for generating an anisotropic mesh having a specific direction has been reported ((1) “Automatic Generation Method For Anisotropic Mesh,” Kenji Shimada, 51st (later half of 1997) National Assembly Of Information Processing Institute, 4C-7, 1995; (2) “A Pliant Method For Anisotropic Mesh Generation,” F. J. Bossen, P. S. Heckbert, Proceeding of 5th International Meshing Roundrable '96, October 1996, pp. 63-74). According to this method, a vector field indicating a direction and a scalar field indicating the size of a bubble are provided instead of a circular bubble to generate an elliptic bubble, and thus a mesh having a direction is generated. Only a flat surface is described in these papers, and accordingly, no explanation was given for parametric space.
Japanese Unexamined Patent Publication No. Hei 8-315183 describes the filling of a curved surface with the above described elliptic bubble, and suggests the employment of parametric space. In this publication, however, parametric space is employed only to locate first bubbles on a curved surface in real space, and the following process is performed at the curved surface in real space. Since in this publication, as well as for the above paper, a process is performed to move an elliptic bubble to an optimal position on the curved surface, a process is required for restricting to the curved surface, a bubble whose optimal position is outside the curved surface because of internal-bubble force. In addition, a process for three-dimensional space is required. In this publication, it is not obvious that condition (2) is satisfied.
In addition to the above conventional techniques, there are the following techniques.
(a) Method for generating a grid in parametric space is described in “Finite element Mesh Generation Method: A Review And Classification,” K. Ho-Le, Computer Aided Designing, Vol. 20, No. 1, 1988, pp. 27-38.
According to this method, a trimmed surface is divided in advance into domains having three sides or four sides, manually or by a specific method, and the domains are divided into grids. Many business analysis software programs employ this method for an associated mesher, but this method does not satisfy the previous mentioned condition (5). Supposing that the mesh generation is performed for all the parts of a single machine, such as a plane or a car, the manual labor required will be enormous. In addition, since the division of domains differs depending on the persons, the resultant meshes are varied depending on the operator. Another problem with the method is the difficulty involved in controlling the size of the mesh elements.
(b) A method using quad-trees is described in: (1) “Comparison Of Discretization Algorithms For NURBS Surfaces With Application To Numerically Controlled Machining,” S. P. Austin, R. B. Jerard and R. L. Drysdale, Computer Aided Design, Vol. 29, No. 1, 1997, pp. 71-83; (2) “A Free-Form
Furuhata Tomotake
Inoue Keisuke
Ito Takayuki
Yamada Atsushi
Drumheller Ronald L.
Du Thuan
International Business Machines - Corporation
Lee Thomas C.
LandOfFree
System for meshing curved surface by generating and... 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 for meshing curved surface by generating and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for meshing curved surface by generating and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2562539