Automated quadrilateral surface discretization method and apparatus usable to generate mesh in a finite element analysis system

• US 5,315,537 A
• Filed: 04/08/1991
• Issued: 05/24/1994
• Est. Priority Date: 04/08/1991
• Status: Expired due to Term

• Current Assignee: Blacker, Teddy D.
• Original Assignee: Blacker, Teddy D.
• Inventors: Blacker, Teddy D.
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US07/682,838
• Time in Patent Office: 1,142 Days
• Field of Search: 364/570, 364/578, 395/123
• US Class Current: 716/51
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

An automatic quadrilateral surface discretization method and apparatus is provided for automatically discretizing a geometric region without decomposing the region. The automated quadrilateral surface discretization method and apparatus automatically generates a mesh of all quadrilateral elements which is particularly useful in finite element analysis. The generated mesh of all quadrilateral elements is boundary sensitive, orientation insensitive and has few irregular nodes on the boundary. A permanent boundary of the geometric region is input and rows are iteratively layered toward the interior of the geometric region. Also, an exterior permanent boundary and an interior permanent boundary for a geometric region may be input and the rows are iteratively layered inward from the exterior boundary in a first counter clockwise direction while the rows are iteratively layered from the interior permanent boundary toward the exterior of the region in a second clockwise direction. As a result, a high quality mesh for an arbitrary geometry may be generated with a technique that is robust and fast for complex geometric regions and extreme mesh gradations.

Claims

1. An automated system for quadrilateral surface discretization of a geometric region, comprising:

means for inputting a permanent boundary on the exterior of the geometric region; and

processing means for iteratively layering rows of quadrilateral elements inward from said permanent boundary to the interior of the geometric region to form a mesh of the quadrilateral elements defining the geometric region;

wherein said processing means defines a plurality of fixed nodes along said permanent boundary, generates a paving row including the layered rows of quadrilateral elements around the inside of said boundary, smooths said paving row of said boundary, seams said paving row of said boundary, detects when said paving row intersects itself or when said paving row intersects an existing portion of said mesh and connects the intersection portions, determines whether said paving row includes contracting or expanding quadrilateral elements and adjusts said paving row by inserting wedges or forming tucks, determines when six or less nodes remain in said paving row and completes said paving row by forming a seam or adding additional quadrilateral elements when six or less nodes remain, and inserts or deletes elements to improve local aspect ratios, reduce the number of irregular nodes and eliminate elements having interior angles less than a predetermined value to complete said paving row.

2. The automated system of claim 1, wherein said mesh of the quadrilateral elements is boundary sensitive.

3. The automated system of claim 1, wherein said mesh of the quadrilateral elements is orientation insensitive.

4. The automated system of claim 1, wherein substantially all of the quadrilateral elements formed by said mesh at said permanent boundary comprises regular nodes.

5. The automated system of claim 1, wherein said system generates said mesh of the quadrilateral elements for use in finite element analysis of the reaction of said geometric region to a stimulus responsive to an input by an operator.

6. The automated system of claim 5, wherein said finite element analysis is performed by a finite element analysis system including receiving means for receiving the stimulus introduced to model the geometric region and analyzing means for performing finite element analysis on the geometric region to produce analysis data.

7. The automated system of claim 1, wherein said processing means selects a starting node for said paving row by classifying each of the nodes in said boundary, determines whether the nodes form a primitive shape and defines a floating node for one of the quadrilateral elements when generating said paving row.

8. The automated system of claim 7, wherein the node classifications comprise row end nodes, row side nodes, row corner nodes and row reversal nodes.

9. The automated system of claim 7, wherein the nodes are classified based on whether an interior angle of each node is within a predetermined angle tolerance.

10. The automated system of claim 7, wherein said processing means detects an interior angle of the nodes of said paving row, determines the number of attached element edges to the nodes of said paving row and determines whether the nodes are fixed nodes when seaming said paving row of said boundary.

11. The automated system of claim 7, wherein said processing means determines whether the intersecting portions form two new boundaries having an odd number of nodes and adjusts the connection if an odd number of nodes exist when connecting the intersecting portions.

12. The automated system of claim 7, wherein said processing means compares the intersecting portions with intersecting portions one step forward and backward to determine whether a connection should be completed when connecting the intersecting portions.

13. The automated system of claim 7, wherein said processing means determines an expansion ratio of a desired length to the distance between adjacent nodes in said paving row, inserts a wedge between the adjacent nodes when said expansion ratio and said interior angles of the nodes are greater than a first set of predetermined threshold values and forms a tuck by combining two adjacent quadrilateral elements into one quadrilateral element when said expansion ratio and said interior angles of the nodes are less than a second set of predetermined threshold values when adjusting said paving row by inserting wedges or forming tucks.

14. The automated system of claim 7, wherein said processing means completes said paving row with a simple seam when two nodes remain, adds an additional quadrilateral element when four nodes remain and adds two, three or four quadrilateral elements based on the node configuration when six nodes remain when completing said paving row by forming said seams or adding additional quadrilateral elements.

15. The automated system of claim 7, wherein said processing means seams an interior node, seams a fixed node and seams a transition when seaming said paving row of said boundary.

16. The automated system of claim 15, wherein said processing means combines the preceding and following nodes to form a seamed node of each node having said interior angle less than a first predetermined angle and the number of attached elements greater than or equal to 5 or said interior angle less than a second predetermined angle greater than said first predetermined angle when seaming said interior angle.

17. The automated system of claim 15, wherein said processing means combines the preceding and following nodes of the fixed nodes of said paving row to form a seamed node when only one side of the quadrilateral element including the node is on an exterior boundary of the geometric region when seaming said fixed node.

18. The automated system of claim 15, wherein said processing means compares the lengths of first and second element sides of the quadrilateral elements and inserts a wedge element if the ratio of said first element side to said second element side or the ratio of said second element side to said first element side is greater than a predetermined value when seaming said transition seam.

19. The automated system of claim 7, wherein said processing means smooths a paving boundary and an interior boundary of said permanent boundary separately when smoothing said paving row of said boundary.

20. The automated system of claim 19, wherein said processing means smooths said floating nodes failing to be on said paving row of said boundary when smoothing said interior boundary.

21. The automated system of claim 19, wherein said processing means fixes nodes failing to be on said paving row of said boundary and smooths said floating nodes on said paving row when smoothing said paving boundary.

22. The automated system of claim 21, wherein said processing means adjusts a length and angle of said floating nodes from said fixed nodes when smoothing said paving boundary.

23. An automated system for quadrilateral surface discretization of a geometric region having interior and exterior boundaries defining a geometric region interior, comprising:

means for inputting the permanent boundaries of the geometric region including an interior permanent boundary and an exterior permanent boundary; and

processing means for iteratively layering rows of quadrilateral elements outward from said interior permanent boundary to the geometric region exterior and inward from said exterior permanent boundary to the geometric region interior to form a mesh of the quadrilateral elements defining the geometric region, said processing means alternatively layering rows outward from said interior boundary and inward from said exterior boundary until the entirety of the geometric region interior is discretized, respectively.

24. The system of claim 23, wherein said processing means includes,

external layering means for developing a row of discrete elements inward from the exterior boundary in a counterclockwise direction toward the geometric region interior;

interior layering means for developing a row of discrete element outward from the interior boundary in a clockwise direction toward the geometric region interior; and

means for alternatively switching between said external layering means and said external layering means to completely layer rows of quadrilateral elements throughout the entirety of the geometric region interior.

25. The automated system of claim 23, wherein said mesh of the quadrilateral elements is boundary sensitive.

26. The automated system of claim 23, wherein said mesh of the quadrilateral elements is orientation insensitive.

27. The automated system of claim 23, wherein substantially all of the quadrilateral elements formed by said mesh at said permanent boundaries comprise regular nodes.

28. An automated mesh generator according to claim 23, wherein said processing means determines whether one external or internal row contains six or less fixed and floating nodes, determines the location of a subsequent external or interior paving boundary row to said one external or interior paving boundary row by classifying said fixed and floating nodes, smooths said external and interior paving boundary row to maintain a desired size of said quadrilateral elements of said first and second meshes, seams said external and interior paving boundary rows to close cracks between adjacent external and interior paving boundary rows, respectively, and adjusts said external and interior paving boundary rows to prevent expansion and contraction of said quadrilateral elements of said first and second meshes.

29. The automated system of claim 23, wherein said system generates said mesh of the quadrilateral elements for use in finite element analysis of the reaction of said geometric region to a stimulus responsive to an input by an operator.

30. The automated system of claim 29, wherein said finite element analysis is performed by a finite element analysis system including receiving means for receiving the stimulus introduced to model the geometric region and analyzing means for performing finite element analysis on the geometric region to produce analysis data.

31. In a finite element analysis method comprising generating a mesh of quadrilateral elements defining a geometric region to be analyzed, introducing a stimulus responsive to an input by an operator to which the response of the geometric region is to be modeled, performing finite element analysis on the geometric region in response to the stimulus to produce analysis data, and using the resulting analysis data, a method of automatically generating a mesh of quadrilateral elements comprising the steps of:

inputting a permanent boundary on the exterior of the geometric region; and

iteratively layering rows of quadrilateral elements inward from said permanent boundary to the interior of the geometric region to form the mesh of the quadrilateral elements defining the geometric region, said step of iteratively layering including the steps of,

defining a plurality of fixed nodes along said permanent boundary,

generating a paving row including the layered rows of quadrilateral elements around the inside of said boundary,

smoothing said paving row of said boundary,

seaming said paving row of said boundary,

detecting when said paving row intersects itself or when said paving row intersects an existing portion of said mesh and connecting the intersecting portions,

determining whether said paving row includes contracting or expanding quadrilateral elements and adjusting said paving row by inserting wedges or forming tucks,

determining when six or less nodes remain in said paving row and completing said paving row by forming a seam or adding additional quadrilateral elements when six or less nodes remain, and

inserting or deleting elements to improve local aspect ratios, reduce the number of irregular nodes and eliminate elements having interior angles less than a predetermined value to complete said paving row.

32. The method of claim 31, wherein the mesh of the quadrilateral elements is boundary sensitive.

33. The method of claim 31, wherein the mesh of the quadrilateral elements is orientation insensitive.

34. The method of claim 31, wherein substantially all of the quadrilateral elements formed by said mesh at said permanent boundary comprise regular nodes.

35. In a finite element analysis method comprising generating a mesh of quadrilateral elements defining a geometric region to be analyzed having interior and exterior boundaries, introducing a stimulus responsive to an input by an operator to which the response of the geometric region is to be modeled, performing finite element analysis on the geometric region in response to the stimulus to produce analysis data, and using the resulting analysis data, a method of automatically generating a mesh of quadrilateral elements comprising the steps of:

inputting the permanent boundaries of the geometric region including an interior permanent boundary and an exterior permanent boundary; and

iteratively layering rows of quadrilateral elements outward from said interior permanent boundary to the geometric region exterior and inward from said exterior permanent boundary to the geometric region interior to form the mesh of the quadrilateral elements defining the geometric region, said rows being alternatively layered outward from said interior boundary and inward from said exterior boundary until the entirety of the geometric region interior is discretized, respectively.

36. The method of claim 35, wherein the mesh of the quadrilateral elements is boundary sensitive.

37. The method of claim 35, wherein the mesh of the quadrilateral elements is orientation insensitive.

38. The method of claim 35, wherein substantially all of the quadrilateral elements formed by said mesh at said permanent boundary comprise regular nodes.

39. A method of automatically surface discretizing a geometric region into a plurality of quadrilateral elements, comprising the steps of:

(a) inputting a permanent boundary on the exterior of the geometric region; and

(b) iteratively layering rows of quadrilateral elements inward from said permanent boundary to the interior of the geometric region to form a mesh of the quadrilateral elements defining the geometric region, said step (b) including the steps of,

(b)(1) defining a plurality of fixed nodes along said permanent boundary,

(b)(2) generating a paving row including the layered rows of quadrilateral elements around the inside of said boundary,

(b)(3) smoothing said paving row of said boundary,

(b)(4) seaming said paving row of said boundary,

(b)(5) detecting when said paving row intersects itself or when said paving row intersects an existing portion of said mesh and connecting the intersecting portions,

(b)(6) determining whether said paving row includes contracting or expanding quadrilateral elements and adjusting said paving row by inserting wedges or forming tucks,

(b)(7) determining when six or less nodes remain in said paving row and completing said paving row by forming a seam or adding additional quadrilateral elements when six or less nodes, and

(b)(8) inserting or deleting elements to improve local aspect ratios, reduce the number of irregular nodes and eliminate elements having interior angles less than a predetermined value to complete said paving row.

40. The method of claim 39, wherein the mesh of the quadrilateral elements is boundary sensitive.

41. The method of claim 39, wherein the mesh of the quadrilateral elements is orientation insensitive.

42. The method of claim 39, wherein substantially all of the quadrilateral elements formed by said mesh at said permanent boundary comprise regular nodes.

43. The method of claim 39, wherein said step (b)(1) comprises the steps of selecting a starting node for said paving row by classifying each of the nodes in said boundary, determining whether the nodes form a primitive shape and defining a floating node for one of the quadrilateral elements.

44. The method of claim 43, wherein the node classifications comprise row end nodes, row side nodes, row corner nodes and row reversal nodes.

45. The method of claim 43, wherein the nodes are classified based on whether an interior angle of each node is within a predetermined angle tolerance.

46. The method of claim 43, wherein said step (b)(4) comprises the steps of detecting an interior angle of the nodes of said paving row, determining the number of attached element edges to the nodes of said paving row and determining whether the nodes are fixed nodes.

47. The method of claim 43, wherein said step (b)(5) comprises the step of determining whether the intersecting portions form two new boundaries having an odd number of nodes and adjusting the connection if an odd number of nodes exist.

48. The method of claim 43, wherein said step (b)(5) comprises the step of comparing the intersecting portions with intersecting portions one step forward and backward to determine whether a connection should be completed.

49. The method of claim 43, wherein said step (b)(6) comprises the steps of determining an expansion ratio of a desired length to the distance between adjacent nodes in said paving row, intersecting a wedge between the adjacent nodes when said expansion ratio and said interior angles of the nodes are greater than a first set of predetermined threshold values and forming a tuck by combining two adjacent quadrilateral elements into one quadrilateral element when said expansion ration and said interior angles of the nodes are less than a second set of predetermined threshold values.

50. The method of claim 43, wherein said step (b)(7) comprises the steps of completing said paving row with a simple seam when two nodes remain, adding an additional quadrilateral element when four nodes remain and adding two, three or four quadrilateral elements based on the node configuration when six nodes remain.

51. The method of claim 43, wherein said step (b)(3) comprises the steps of paving boundary smoothing and interior smoothing.

52. The method of claim 51, wherein said step of interior smoothing comprises the step of smoothing said floating nodes failing to be on said paving row of said boundary.

53. The method of claim 51, wherein said step of paving boundary smoothing comprises the step of fixing nodes failing to be on said paving row of said boundary and smoothing said floating nodes on said paving row.

54. The method of claim 53, wherein said step of paving boundary smoothing comprises the step of modified isoparametric smoothing for adjusting a length and angle of said floating nodes from said fixed nodes.

55. The method of claim 43, wherein said step (b)(4) comprises the steps of interior node seaming, fixed node seaming and transition seaming.

56. The method of claim 55, wherein said step of interior node seaming comprises the step of combining the preceding and following nodes to form a seamed node of each node having said interior angle less than a first predetermined angle and the number of attached elements greater than or equal to 5 or said interior angle less than a second predetermined angle greater than said first predetermined angle.

57. The method of claim 55, wherein said step of fixed node seaming comprises the step of combining the preceding and following nodes of the fixed nodes of said paving row to form a seamed node when only one side of the quadrilateral element including the node is on an exterior boundary of the geometric region.

58. The method of claim 55, wherein said step of transition seaming comprises the steps of comparing the lengths of first and second elements sides of the quadrilateral elements and inserting a wedge element when the ratio of said first element side to said second element side or the ratio of said second element side to said first element side is greater than a predetermined value.

59. A method of automatically surface discretizing a geometric region having interior and exterior boundaries defining a geometric region interior into a plurality of quadrilateral elements, comprising the steps of:

inputting the permanent boundaries of the geometric region including an interior permanent boundary and an exterior permanent boundary; and

iteratively layering rows of quadrilateral elements inward from said exterior permanent boundary to the geometric region interior and outward from said interior permanent boundary to the geometric region exterior to form a mesh of the quadrilateral elements defining the geometric region, said rows being alternatively layered outward from said interior boundary and inward from said exterior boundary until the entirety of the geometric region interior is discretized, respectively.

60. The method of claim 59, wherein the mesh of the quadrilateral elements is boundary sensitive.

61. The method of claim 59, wherein the mesh of the quadrilateral elements is orientation insensitive.

62. The method of claim 59, wherein substantially all of the quadrilateral elements formed by said mesh at permanent boundary comprise regular nodes.