Method and device for generating mesh for use in numerical analysis

• US 5,946,479 A
• Filed: 11/23/1998
• Issued: 08/31/1999
• Est. Priority Date: 05/25/1995
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Sakaguchi, Masaya, Mizoh, Yoshiaki
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US09/197,972
• Time in Patent Office: 281 Days
• Field of Search: 395/500, 395/500.01, 395/500.21, 395/500.2, 395/500.23, 345/331, 345/423, 382/154, 364/468.04
• US Class Current: 716/51
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

A method and device for generating mesh to be used in numerical analysis for regions of an object to be analyzed, the regions of an object to be analyzed being input as data for a geometric model which defines their geometric form in a coordinate system which is set as a standard. This geometric model is then divided into equal parts in the coordinate directions of the coordinate system to generate blocks. After this, the vertices, endpoints and points of the shapes formed by the intersection or touching of the boundaries of the geometric model and each of the generated blocks are extracted. These extracted points, along with the vertices, endpoints and points of the geometric model and the vertices of the generated blocks, are set as nodes. Finally, mesh elements are generated for each block using the nodes.

Claims

1. A mesh generating method which generates mesh to be used in numerical analysis for a region of an object to be analyzed, the mesh generating method comprising:

a geometric model inputting step for inputting data for a geometric model that geometrically specifies the region of the object to be analyzed as a standard for a coordinate system;

a block generating step for generating blocks by dividing a space including the input geometric model in at least one coordinate direction of the coordinate system to create blocks of equal size;

a node extracting step for extracting, for every block, vertices of a block, points that define a form of the geometric model present in the block, and intersection points between the geometric model and a boundary of the block as nodes for the block, the intersection points including endpoints of an intersection lines between the geometric model and the boundary of the block;

a polygon candidate generating step for selecting arbitrary combinations of nodes that each form a polygon from nodes extracted for a block to generate polygon candidates;

a polygon selecting step for selecting one of the generated polygon candidates that satisfies a first condition as a formal polygon;

a polyhedron mesh candidate generating step for generating polyhedron mesh element candidates by connecting all vertices of the formal polygon with each node in the block aside from the vertices of the formal polygon;

a polyhedron mesh selecting step for selecting one of the generated polyhedron mesh element candidates that satisfies a second condition as a formal polyhedron mesh element, wherein the polygon candidate generating step, the polygon selecting step, the polyhedron mesh candidate generating step, and the polyhedron mesh selecting step being repeated until an entire region of the block is occupied by polyhedron mesh elements, and wherein polyhedron mesh elements are generated for an entire region of every block; and

wherein, said generated polyhedron mesh elements for a region of an object to be analyzed are subsequently used for numerical analysis of the object being analyzed.

2. The mesh generating method of claim 1, wherein the first condition is that each polygon candidate has to neither enclose a two-dimensional area including any node aside from vertices of the polygon candidate nor cross a boundary of the geometric model, and wherein the second condition is that each polyhedron mesh element candidate has to neither enclose a space including any node aside from vertices of the polyhedron mesh element candidate, nor cross a boundary of the geometric model.

3. The mesh generating method of claim 2, wherein the first condition and the second condition each include a subcondition that when nodes on a boundary surface of the block are connected to form edges of existing polyhedron mesh elements in an adjacent block, polygon candidates and polyhedron mesh element candidates generated in the block must have the nodes on the boundary connected in a same pattern as the existing polyhedron mesh elements in the adjacent block.

4. The mesh generating method of claim 3, wherein the first condition further includes a subcondition that a polygon candidate to be selected is a least elongated of remaining polygon candidates, wherein the second condition further includes a subcondition that a polyhedron mesh element candidate to be selected is a least elongated of remaining polyhedron mesh element candidates, and wherein the subcondition of the first condition and the subcondition of the second condition are respectively used for selecting one of polygon candidates and one of polyhedron mesh element candidates remaining after other conditions are used.

5. The mesh generating method of claim 1, wherein each polygon candidate is a triangle and each polyhedron mesh element candidate is a tetrahedron, and wherein the polygon candidate generating step, the polygon selecting step, the polyhedron mesh candidate generating step, and the polyhedron mesh selecting step are composed of:

a first substep for selecting, from the nodes extracted for the block, one of arbitrary pairs of nodes which remain after eliminating each pair of nodes which is linked by a line including any node between the pair of nodes or a line crossing a boundary of the geometric model, and generating triangular polygon candidates by connecting the selected pair of nodes with each other and with each node in the block aside from the selected pair of nodes;

a second substep for eliminating each triangular polygon polygon candidate that encloses a two-dimensional area including any node aside from vertices of the triangular polygon candidate and each triangular polygon candidate that crosses a boundary of the geometric model and as a result prompts a need to create new nodes;

a third substep for selecting a least elongated of triangular polygon candidates remaining after the second substep as a formal triangular polygon;

a fourth substep for generating tetrahedron mesh element candidates by connecting all vertices of the formal triangular polygon with each node in the block aside from the vertices of the formal triangular polygon;

a fifth substep for eliminating each tetrahedron mesh element candidate that encloses a spare including any node aside from vertices of the tetrahedron mesh element candidate and each tetrahedron mesh element candidate that crosses a boundary of the geometric model and as a result prompts a need to create new nodes; and

a sixth substep for selecting a tetrahedron mesh element candidate, among tetrahedron mesh element candidates remaining after the fifth substep, whose form is closest to a regular tetrahedron as a formal tetrahedron mesh element.

6. The mesh generating method of claim 5, wherein the fifth substep further eliminates each tetrahedron mesh element candidate which meets a condition of being identical to or overlapping an existing tetrahedron mesh element.

7. The mesh generating method of claim 6, wherein the first substep, the second substep, and the fifth substep further eliminate, respectively, each pair of nodes, each triangular polygon candidate, and each tetrahedron mesh element candidate which do not meet a condition that when nodes on a boundary surface of the block are connected to form edges of existing polyhedron mesh elements in an adjacent block, a pair of nodes, a triangular polygon candidate, and tetrahedron mesh element candidate must have the nodes on the boundary connected in a same pattern as the existing polyhedron mesh elements in the adjacent block.

8. The mesh generating method of claim 7, further comprising the following steps between the block generating step and the node extracting step:

a dividing region indicating step for having a user indicate a region of the geometric model to be divided; and

a block dividing step for dividing each block which includes a part of the region indicated in the dividing region indicating step into equal parts in at least one coordinate direction of the coordinate system.

9. The mesh generating method of claim 1, further comprising the following steps between the block generating step and the node extracting step:

a dividing boundary indicating step for indicating at least one of a surface, a line and a point on a boundary of the geometric model to be divided; and

a block dividing step for dividing each block which includes the surface, line or point indicated in the dividing boundary indicating step into equal parts in at least one coordinate direction of the coordinate system.

10. The mesh generating method of claim 8, wherein the block dividing step includes:

a size limit data inputting substep for inputting limit data related to a limit for a difference in size between adjacent blocks;

a size difference judging substep for judging whether a difference in size between a pair of adjacent blocks exceeds the difference stipulated by the limit data, for every pair of adjacent blocks; and

a block dividing substep for dividing a larger block in a pair of adjacent blocks judged in the size difference judging substep to exceed the difference stipulated by the limit data into equal parts in at least one coordinate direction of the coordinate system.

11. The mesh generating method of claim 10, wherein the limit data in the size limit data inputting substep stipulates a limit that a ratio of lengths between at least one side of each block in a pair of adjacent blocks does not exceed 1:

2.

12. The mesh generating method of claim 9, wherein the block dividing step includes:

a geometric model limiting rule inputting substep for inputting predetermined limit rules which make stipulations concerning at least one of points, lines and surfaces which defines a form of the geometric model present in each block; and

a limit rule violation judging substep for judging whether any of the generated blocks violates the limit rules, wherein the block dividing step divides a block judged to violate the limit rules into equal parts in at least one coordinate direction of the coordinate system.

13. The mesh generating method of claim 1, further comprising the following steps between the block generating step and the node extracting step:

a geometric model limit rule inputting step for inputting predetermined limit rules which make stipulations concerning at least one of points, lines and surfaces which defines a form of the geometric model present in each block;

a limit rule violation judging step for judging whether any of the generated blocks violates the limit rules; and

a block dividing step for dividing a block judged to violate the limit rules into equal parts in at least one coordinate direction of the coordinate system.

14. A mesh generating method which generates mesh to be used in numerical analysis for a region of an object to be analyzed, the mesh generating method comprising:

a geometric model inputting step for inputting data for a geometric model that geometrically specifies the region of the object to be analyzed as a standard for a coordinate system;

a block generating step for generating blocks by dividing a space including the input geometric model in at least one coordinate direction of the coordinate system to create blocks of equal size;

a node extracting step for extracting, for every block, vertices of a block, points that define a form of the geometric model present in the block, and intersection points between the geometric model and a boundary of the block as nodes for the block, the intersection points including endpoints of intersection lines between the geometric model and the boundary of the block;

a pattern sorting step for sorting each block according to pattern, based on geometric relations between nodes extracted for a block and any of points, lines and surfaces present in the block and on a boundary of the block which are necessary for generating a form of the geometric model;

a searching step for searching a memory using a pattern of a block as a key to read, if present, a mesh sample corresponding to the pattern, wherein the memory stores patterns which are each based on geometric relations between vertices of a block and intersection points between the geometric model and a boundary of the block, and mesh samples corresponding to the patterns;

a first mesh generating step for generating mesh elements in a block based on a mesh sample read for the block; and

wherein, said generated mesh elements for a region of an object to be analyzed are subsequently used for numerical analysis of the object being analyzed.

15. The mesh generating method of claim 14, further comprising:

a second mesh generating step for generating mesh elements in a block using nodes extracted for the block, when it is judged in the searching step that a mesh sample corresponding to pattern of the block is not stored in the memory; and

a registering step for registering the mesh elements, which are generated in the second mesh generating step, in the memory as a mesh sample corresponding to the pattern of the block.

16. A mesh generating device which generates mesh to be used in numerical analysis for a region of an object to be analyzed, the mesh generating device comprising:

geometric model inputting means for inputting data for geometric model that geometrically specifies the region of the object to be analyzed as a standard for a coordinate system;

block generating means for generating blocks by dividing a space including the input geometric model in at least one coordinate direction of the coordinate system to create blocks of equal size;

node extracting means for extracting, for every block, vertices of a block, points that define a form of the geometric model present in the block, and intersection points between the geometric model and a boundary of the block as nodes for the block, the intersection points including endpoints of intersection lines between the geometric model and the boundary of the block;

polygon candidate generating means for selecting arbitrary combinations of nodes that each form a polygon from nodes extracted for a block to generate polygon candidates;

polygon selecting means for selecting one of the generated polygon candidates that satisfies a first condition as a formal polygon;

polyhedron mesh candidate generating means for generating polyhedron mesh element candidates by connecting all vertices of the formal polygon with each node in the block aside from the vertices of the formal polygon;

polyhedron mesh selecting means for selecting one of the generated polyhedron mesh element candidates that satisfies a second condition as a formal polyhedron mesh element;

repeat controlling means for having the polygon candidate generating means, the polygon selecting means, the polyhedron mesh candidate generating means, and the polyhedron mesh selecting means repeat processing until an entire region of the block is occupied by polyhedron mesh elements; and

wherein, said generated polyhedron mesh elements for a region of an object to be analyzed are subsequently used for numerical analysis of the object being analyzed.

17. The mesh generating device of claim 16, wherein each polygon candidate is a triangle and each polyhedron mesh element candidate is a tetrahedron, and wherein the polygon candidate generating means, the polygon selecting means, the polyhedron mesh candidate generating means, and the polyhedron mesh selecting means are composed of:

a first unit for selecting, from the nodes extracted for the block, one of arbitrary pairs of nodes which remain after eliminating each pair of nodes which is linked by a line including any node between the pair of nodes or a line crossing a boundary of the geometric model, and generating triangular polygon candidates by connecting the selected pair of nodes with each other and with each node in the block aside from the selected pair of nodes;

a second unit for eliminating each triangular polygon candidate that encloses a two-dimensional area including any node aside from vertices of the triangular polygon candidate and each triangular polygon candidate that crosses a boundary of the geometric model and as a result prompts a need to create new nodes;

a third unit for selecting a least elongated of triangular polygon candidates remaining after elimination by the second unit as a formal triangular polygon;

a fourth unit for generating tetrahedron mesh element candidates by connecting all vertices of the formal triangular polygon with each node in the block aside from the vertices of the formal triangular polygon;

a fifth unit for eliminating each tetrahedron mesh element candidate that encloses a space including any node aside from vertices of the tetrahedron mesh element candidate and each tetrahedron mesh element candidate that crosses a boundary of the geometric model and as a result prompts a need to create new nodes; and

a sixth unit for selecting a tetrahedron mesh element candidate, among tetrahedron mesh element candidates remaining after elimination by the fifth unit, whose form is closest to a regular tetrahedron as a formal tetrahedron mesh element.

18. The mesh generating device of claim 16, further comprising:

dividing region indicating means for having a user indicate a region of the geometric model to be divided; and

block dividing means for dividing each block which includes a part of the region indicated by the dividing region indicating means into equal parts in at least one coordinate direction of the coordinate system.

19. The mesh generating device of claim 16, further comprising:

dividing boundary indicating means for indicating at least one of a surface, a line and a point on a boundary of the geometric model to be divided; and

block dividing means for dividing each block which includes the surface, line or point indicated by the dividing boundary indicating means into equal parts in at least one coordinate direction of the coordinate system.

20. The mesh generating device of claim 18, wherein the block dividing means includes:

a size limit data inputting unit for inputting limit data related to a limit for a difference in size between adjacent blocks;

a size difference judging unit for judging whether a difference in size between a pair of adjacent blocks exceeds the difference stipulated by the limit data, for every pair of adjacent blocks; and

a block dividing unit for dividing a larger block in a pair of adjacent blocks judged by the size difference judging unit to exceed the difference stipulated by the limit data into equal parts in at least one coordinate direction of the coordinate system.

21. The mesh generating device of claim 20, wherein the limit data in the size limit data inputting unit stipulates a limit that a ratio of lengths between at least one side of each block in a pair of adjacent blocks does not exceed 1:

2.

22. The mesh generating device of claim 19, wherein the block dividing means includes:

a geometric model limit rule inputting unit for inputting predetermined limit rules which make stipulations concerning at least one of points, lines and surfaces which defines a form of the geometric model present in each block; and

a limit rule violation judging unit for judging whether any of the generated blocks violates the limit rules, wherein the block dividing means divides a block judged to violate the limit rules into equal parts in at least one coordinate direction of the coordinate system.

23. The mesh generating device of claim 16, further comprising:

geometric model limit rule inputting means for inputting predetermined limit rule which make stipulations concerning at least one of points, lines and surfaces which defines a form of the geometric model present in each block;

limit rule violation judging means for judging whether any of the generated blocks violates the limit rules; and

block dividing means for dividing a block judged to violate the limit rules into equal parts in at least one coordinate direction of the coordinate system.

24. A mesh generating device which generates mesh to be used in numerical analysis for a region of an object to be analyzed, the mesh generating device comprising:

geometric model inputting means for inputting data for a geometric model that geometrically specifies the region of the object to be analyzed as a standard for a coordinate system;

block generating means for generating blocks by dividing a space including the input geometric model in at least one coordinate direction of the coordinate system to create blocks of equal size;

node extracting means for extracting, for every block, vertices of a block, points that define a form of the geometric model present in the block, and intersection points between the geometric model and a boundary of the block as nodes for the block, the intersection points including endpoints of intersection lines between the geometric model and the boundary of the block;

pattern sorting means for sorting each block according to pattern, based on geometric relations between nodes extracted for a block and any of points, lines, and surfaces present in the block and on a boundary of the block which are necessary for generating a form of the geometric model;

a memory for storing patterns which are each based on geometric relations between vertices of a block and intersection points between the geometric model and a boundary of the block, and mesh samples corresponding to the patterns;

searching means for searching the memory using a pattern of a block as a key to read, if present, a mesh sample corresponding to the pattern;

first mesh generating means for generating mesh elements in the block according to the read mesh sample; and

wherein, said generated mesh elements for a region of an object to be analyzed are subsequently used for numerical analysis of the object being analyzed.

25. The mesh generating device of claim 24, further comprising:

second mesh generating means for generating mesh elements in the block using nodes extracted for the block, when it is judged by the searching means that the mesh sample corresponding to the pattern of the block is not stored in the memory; and

a registering means for registering the mesh elements, which are generated by the second mesh generating means, in the memory as a mesh sample corresponding to the pattern of the block.

26. A storage medium that stores a mesh generating program for generating mesh to be used in numerical analysis for a region of an object to be analyzed, the mesh generating program comprising:

a block generating step for generating blocks by dividing a space including a geometric model that is inputted as a standard for a coordinate system and that geometrically specifies the region of the object to be analyzed in at least one coordinate direction of the coordinate system to create blocks of equal size;

a node extracting step for extracting, for every block, vertices of a block points that define a form of the geometric model present in the block, and intersection points between the geometric model and a boundary of the block as nodes for the block, the intersection points including endpoints of intersection lines between the geometric model and the boundary of the block;

a polygon candidate generating step for selecting arbitrary combinations of nodes that each form a polygon from nodes extracted for a block to generate polygon candidates;

a polygon selecting step for selecting one of the generated polygon candidates that satisfies a first condition as a formal polygon;

a polyhedron mesh candidate generating step for generating polyhedron mesh element candidates by connecting all vertices of the formal polygon with each node in the block aside from the vertices of the formal polygon;

a polyhedron mesh selecting step for selecting one of the generated polyhedron mesh element candidates that satisfies second condition as a formal polyhedron mesh element, wherein the polygon candidate generating step, the polygon selecting step, the polyhedron mesh candidate generating step, and the polyhedron mesh selecting step being repeated until an entire region of the block is occupied by polyhedron mesh elements, and wherein polyhedron mesh elements are generated for an entire region of every block; and

wherein, said generated polyhedron mesh elements for a region of an object to be analyzed are subsequently used for numerical analysis of the object being analyzed.