Method and apparatus for generating a mesh for finite element analysis

• US 4,912,664 A
• Filed: 02/01/1988
• Issued: 03/27/1990
• Est. Priority Date: 02/01/1988
• Status: Expired due to Term

• Current Assignee: Mentor Graphics Corporation (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Weiss, Jonathan, Fortner, Patrick D.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Dixon, Joseph L.
• Application Number:
  US07/151,105
• Time in Patent Office: 785 Days
• Field of Search: 364/577, 364/578, 364/754, 364/518, 364/521, 364/522, 364/746.1, 382/21, 382/22, 340/729, 340/747
• US Class Current: 716/55
• CPC Class Codes: G06F 30/23 using finite element methods [FEM] or finite difference methods [FDM]
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

The method of mesh generation comprises a two-step automatic process that requires no user input once a geometric representation of the object has been provided to the apparatus. In the method, the object geometry is first defined in terms of object (subdomain) points, wherein each subdomain is a separate geometric region of the object such as a printed circuit board, a hole in the board, and a component mounted on the board. Bounding points defining a frame around the object geometry are then generated for producing a mesh consisting of at least one element. From the object points and the bounding points an initial mesh of elements is automatically generated according to a unique algorithm. In the second step of the process, each element in this mesh is then individually examined to determine if it meets a predetermined standard of acceptability and, if not, is refined. This process step employs a rule-based expert system to add additional points to the mesh at automatically determined locations for further mesh generation according to the unique algorithm employed. The steps of refinement repeat until each element in the mesh meets the acceptability standard or is considered no longer refinable.

Claims

1. Apparatus for generating a mesh of elements for finite element analysis of an object, comprising:

means for defining the object geometry in terms of points;

means for generating bounding points around the object; and

means for generating from the bounding points and object points a mesh of elements.

2. The method of claim 1 including means for refining each element that fails to meet a predetermined standard of acceptability.

3. Apparatus for generating a mesh of elements for finite element analysis of an object, comprising:

means for defining the object geometry in terms of points;

means for generating from the object points an initial mesh; and

means responsive to the initial mesh for refining each element that fails to meet a predetermined standard of acceptability.

4. A method of generating a mesh of elements for finite element analysis of an object, comprising:

defining the object geometry in terms of points;

generating bounding points around the object geometry for producing a mesh with an element;

generating from the bounding points and object points a mesh of elements; and

refining each element that fails to meet a predetermined standard for acceptability.

5. The method of claim 4 in which defining the object geometry comprises:

deriving a polyline segment approximation of each curved section that may exist in the object geometry;

gathering endpoints of each line segment of the object;

geometry; and

marking the endpoints that define the beginning and end of each subdomain of the object geometry.

6. The method of claim 4 in which generating bounding points around the object comprises constructing a frame around the object and connecting opposite end points of the frame to form an initial mesh of elements.

7. The method of claim 4 in which generating a mesh of elements comprises;

adding an object point within an enclosing element having nodes;

constructing elements by connecting the object point with each node of the enclosing element;

circumcircling each constructed element that comprises a portion of a convex quadrilateral having nodes to determine if a node of the quadrilateral lies within the circle created; and

if a quadrilateral node lies within the circle created, swapping a first quadrilateral diagonal for the second quadrilateral diagonal to change the shape of the constructed element.

8. The method of claim 7 including skipping the diagonal swapping if the first quadrilateral diagonal connects the added object point with another object point.

9. The method of claim 4 in which refining each element comprises:

adding a point to the existing mesh according to a rule applied in response to an antecedent mesh condition; and

regenerating the mesh with the added point to change the shape of the element.

10. The method of claim 4 in which refining each element comprises:

determining which rule of a set of rules should be applied to the element to refine its shape;

applying the rule to the element; and

repeating the above steps until each element in the mesh meets the standard of acceptability or can no longer be refined.

11. The method of claim 10 in which the rules are applied in a predetermined order to minimize the time required to refine the elements of the mesh.

12. The method of claim 10 in which the rules are constructed so that they apply without conflict.

13. The method of claim 4 in which refining each element comprises:

determining if the element has three edges either reserved against change and/or on the mesh boundary; and

14. The method of claim 4 in which refining each element comprises:

determining if the element has two edges either reserved against change and/or on the mesh boundary;

if so, determining if a shortest edge in the element is reserved;

if the shortest edge is reserved, determining a longest of the two edges that are either reserved and/or on the mesh boundary and placing a point at the midpoint of the longest edge;

if the shortest edge is not reserved, marking this element as undefinable; and

regenerating the mesh if the point is added.

15. The method of claim 4 in which refining each element comprises:

determining if the element'"'"'s longest edge is either reserved against change and/or on the mesh boundary;

if so, place a point on that edge 1/4 to 1/2 of the way from a minimum angle vertex of the element; and

regenerating the mesh if the point is added.

16. The method of claim 4 in which refining each element comprises:

determining if the neighboring element across from the element'"'"'s longest edge does not have its longest edge either reserved against change and/or on the mesh boundary;

if so, determining if an element containing the circumcenter of the element to be refined has a longest edge reserved or on the mesh boundary;

if the containing element does have such an edge, placing a point at the midpoint of that edge;

if the containing element does not have such an edge, placing a point at the center of the circumcircle; and

regenerating the mesh if the point is added.

17. The method of claim 16 further comprising:

determining if the added point is placed outside the mesh boundary or across a reserved edge from the element to be refined;

if so, replacing the prior point with a point at the intersection of the line connecting the center of the circumcircle to the element'"'"'s centroid and the nearest reserved edge; and

regenerating the mesh.

18. The method of claim 4 in which refining the element comprises:

determining if the neighboring element across from the element'"'"'s longest edge has an edge either reserved and/or on the mesh boundary;

if so, placing a point at the midpoint of the neighboring element'"'"'s longest edge; and

regenerating the mesh if the point is added.

19. The method of claim 4 in which refining the element comprises:

determining if the element has an edge either reserved or on the mesh boundary;

if so, placing a point at the midpoint of the edge; and

regenerating the mesh if the point is added.

20. The method of claim 4 in which refining each element comprises:

placing a point at the element'"'"'s centroid; and

regenerating the mesh.