Method for fine decomposition in finite element mesh generation

• US 4,933,889 A
• Filed: 04/29/1988
• Issued: 06/12/1990
• Est. Priority Date: 04/29/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nackman, Lee R., Srinivasan, Vijay, Meshkat, Siavash N.
• Primary Examiner(s): Gruber, Felix D.
• Application Number:
  US07/187,715
• Time in Patent Office: 774 Days
• Field of Search: 364/300, 364/505, 364/522, 364/578, 364/505, 382/25, 382/26
• US Class Current: 703/2
• 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

A method for fine decomposition in finite element mesh generation, in which a polygonal boundary of a domain is input into the system by an analyst and the domain is automatically divided into rough elements generally corresponding to Voronoi regions, that is, regions which are closer to respective ones of the polygonal line segments or reflex vertices therebetween. Any arc portion of these regions is converted to a straight line. Additional lines are formed between interior vertices of the rough regions so that all rough regions are either triangles or trapezoids. Adjacent rough regions are then paired across internal boundaries and are classified into four types. The rough regions are then subdivided into fine regions of triangular shape according to rules associated with each of the four types. The degree of fine subdivision can be controlled according to known equations providing the total number of fine elements. Finite difference equations are solved on the so generated fine regions and a physical variable is displayed in pictorial form. The analyst then readjusts the domain boundary and repeats the process.

Claims

1. A method of generating a multiple polygonal representation of a predicted physical phenomenon, said method being of the type wherein information regarding a polygonal domain of a multi-dimensional object is entered into a computer, the information is processed by said computer and the representation is generated in accordance with the results of said processing, said method being characterized in that said step of processing said information by said computer comprises the steps of:

dividing said domain into a plurality of first regions, at least one of which has a boundary which includes a curved portion, each said first region touching a boundary of said domain at at least a point;

replacing said curved portion with at least one straight line connecting ends of said curved portion, thereby adjusting said first regions, whereby said adjusted first regions are bounded on all sides by straight line segments;

classifying pairs of said adjusted first regions separated by a common boundary into a finite number of classes; and

dividing each of said first regions into second regions according to a rule proper to its class, said second regions being used in generating said representation.

2. A method as recited in claim 1, wherein said adjusted first regions consist of triangles and right trapezoids and wherein there are four of said classes.

3. A method as recited in claim 2, wherein each said common boundary touches said boundary of said domain at at most an acute corner thereof.

4. A method as recited in claim 1, further comprising displaying said representation.

5. A method as recited in claim 4, wherein responsive to said displaying step new information regarding an adjusted polygonal domain is entered.

6. A computerized method of analyzing at least one physical condition across a domain, said domain being bounded by one or more polygonal boundaries composed of straight line segments with vertices between adjacent ones thereof, some of said vertices possibly being reflex vertices with respect to an interior or said domain, said method comprising the steps of decomposing said domain via computer processing into a plurality of finite elements, analyzing said condition across each of said finite elements to obtain finite element analysis results, combining a plurality of said finite element analysis results to obtain a domain analysis result and providing a physical representation of said domain analysis result, wherein said step of decomposing said domain comprises the steps of:

dividing said domain into a plurality of first regions, each of said first regions being closer to a respective one of said line segments and said reflex vertices of said boundaries than to any other of said line segments and said reflex vertices of said boundaries, said first regions filling said domain, wherein said first regions are divided by first lines not touching said boundaries, by straight second lines touching said boundaries at vertices thereof other than said reflex vertices and by straight third lines touching said reflex vertices of said boundaries, said first lines consisting of further straight second lines and arc portions;

replacing said arc portions with further straight second lines which are straight lines connecting respective ends of said arc portions, said first regions being adjusted by said replacing step, all of said second lines being connected at internal vertices;

dividing said first regions by further straight third lines extending from said internal vertices to intercept said line segments at a right angle or to touch said reflex vertices, whereby each of said first regions after said dividing is bounded by two of said third lines;

classifying each pair of said divided first regions separated by a second line into one of four classes, a pair of a first class being two congruent right trapezoids, a pair of a second class being two congruent right triangles, a pair of a third class being a right trapezoid and a triangle, a pair of a fourth class being two congruent triangles; and

dividing each said triangle and trapezoid into second regions according to a rule proper to its class to obtain said finite elements.

7. A method as recited in claim 6, wherein said second regions are triangles.

8. A method as recited in claim 6, further comprising manually inputting said boundaries and providing visual feedback of said inputted boundaries.

9. A method as recited in claim 8, further comprising visually displaying said second regions and boundaries thereof.

10. A method as recited in claim 8, wherein said physical condition is represented by one or more difference equations extending over said domain and wherein said step of providing a physical representation of said domain analysis result comprises visually displaying a solution of said difference equations extending over said domain.

11. A method as recited in claim 10, further comprising changing said boundaries in response to said visual displaying of said solution of said difference equations and repeating steps of said decomposing method.

12. A method as recited in claim 6, wherein said decomposing step further comprises the steps of:

determining a number of second regions formed by said step of dividing said each triangle and trapezoid for each of said pairs of divided first regions as a function of a density variable, said density variable being contained in all of said proper rules;

summing said numbers to form an algebraic sum;

comparing said algebraic sum with a maximum element number;

solving said compared algebraic sum for said density variable; and

dividing said triangles and trapezoids according to said proper rules evaluated according to said solved density variable.

13. A method as recited in claim 12, wherein said second regions are triangles and said step of dividing said triangles and trapezoids comprising dividing said third lines into sub-segments of a number equal to said density variable plus one, said second regions having said sub-segments as a side.

14. A method as recited in claim 6, wherein said step of decomposing further comprises the step of collapsing at least some of said second regions which are contained in a first region having an aspect ratio of lengths of sides thereof falling outside a predetermined range.

15. A computer aided design system, comprising:

a display (192);

manual boundary input means (194,

     196) for inputting at least one polygonal boundary to be displayed on said display, said at least one polygonal boundary bounding a domain and being composed of straight line segments with vertices between adjacent ones thereof, some of said vertices possibly being reflex vertices with respect to an interior of said domain;

first decomposition means (190, 148, FIG.

     15) for decomposing said domain into a plurality of large triangular and trapezoidal regions each touching said boundary, pairs of said large regions separated by a common edge being classified according to a finite number of classes; and

second decomposition means (190,

     172) for decomposing each of said large regions into a plurality of small regions according to a rule proper to its class.

16. A system as recited in claim 15, wherein said first and second decomposition means comprise:

means (190,

     147) for dividing said domain into a plurality of first regions, each of said first regions being closer to a respective one of said line segments and said reflex vertices of said boundary than to any other of said line segments and said reflex vertices of said boundary, said first regions filling said domain, wherein said first regions are divided by first lines not touching said boundary, by straight second lines touching said boundary at vertices of said boundary other than said reflex vertices and straight third lines touching said reflex vertices of said boundary, said first lines consisting of further straight second lines and arc portions;

means (190,

     147) for replacing said arc portions with further straight second lines which are straight lines connecting respective ends of said arc portions, said first regions being adjusted by said replacing means, all of said second lines being connected at internal vertices;

means (190,

     158) for dividing said first regions by further straight third lines extending from said internal vertices to intercept said line segments at a right angle or to touch said reflex vertices, whereby each of said first regions after said dividing is bounded by two of said third lines;

means (190,

     162) for classifying each pair of said divided first regions separated by a second line into one of four classes, a pair of a first class being two congruent right trapezoids, a pair of a second class being two congruent right triangles, a pair of a third class being a right trapezoid and a triangle, a pair of a fourth class being two congruent triangles; and

means (190,

     172) for dividing each said triangle and trapezoid into second regions according to a rule proper to its class.