EP0339272A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method for fine decomposition in finite element mesh generation
Assignee: International Business Machines Corp
•
Filing: 1989-03-28
•
Granted: —
•
Expires: 2009-03-28
Abstract
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.
Inventors
- 👤 Siavash N. Meshkat
- 👤 Lee R. Nackman
- 👤 Vijay Srinivasan
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 15:44
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20; G06F; G06F30/00; G06F30/20; G06F30/23
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
179 words
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, the information is processed 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 comprises the steps of: dividing said domain into a plurality of first regions having boundaries which are either straight edges or curved portions, each said first region touching a boundary of said domain at at least a point; replacing any curved portion with at least one straight line connecting 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.
Claim 2
Independent Claim
179 words
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, the information is processed 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 comprises the steps of: dividing said domain into a plurality of first regions having boundaries which are either straight edges or curved portions, each said first region touching a boundary of said domain at at least a point; replacing any curved portion with at least one straight line connecting 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.
Claim 3
Dependent Claim
26 words
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.
Claim 4
Dependent Claim
25 words
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.
Claim 5
Dependent Claim
12 words
A method as recited in Claim 1, further comprising displaying said representation.
Claim 6
Dependent Claim
22 words
A method as recited in Claim 5, wherein responsive to said displaying step new information regarding an adjusted polygonal domain is entered.
Claim 7
Independent Claim
320 words
A method of decomposing a domain bounded by one or more polygonal boundaries, said polygonal boundaries 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, said method comprising 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.
Claim 8
Independent Claim
320 words
A method of decomposing a domain bounded by one or more polygonal boundaries, said polygonal boundaries 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, said method comprising 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.
Claim 9
Dependent Claim
14 words
A decomposition method as recited in Claim 6, wherein said second regions are triangles.
Claim 10
Dependent Claim
23 words
A decomposition method as recited in Claim 6, further comprising manually inputting said boundaries with means including visual feedback of said inputted boundaries.
Claim 11
Dependent Claim
18 words
A decomposition method as recited in Claim 8, further comprising visually displaying said second regions and boundaries thereof.
Claim 12
Dependent Claim
40 words
A prediction method as recited in Claim 8, further comprising the steps of: solving one or more difference equations for a physical quantity extending over said domain; and visually displaying a solution of said difference equations extending over said domain.
Claim 13
Dependent Claim
33 words
A design 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 prediction method.
Claim 14
Dependent Claim
101 words
A decomposition method as recited in Claim 6, further comprising 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.
Claim 15
Dependent Claim
49 words
A decomposition 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.
Claim 16
Dependent Claim
42 words
A decomposition method as recited in Claim 6, further comprising 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.
Claim 17
Dependent Claim
127 words
A computer aided design system, comprising: a display; manual boundary input means 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 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 for decomposing each of said large regions into a plurality of small regions according to a rule proper to its class.
Claim 18
Dependent Claim
127 words
A computer aided design system, comprising: a display; manual boundary input means 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 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 for decomposing each of said large regions into a plurality of small regions according to a rule proper to its class.
Claim 19
Dependent Claim
296 words
A system as recited in Claim 15, wherein said first and second decomposition means comprise: means 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 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 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 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 triangle; and means for dividing each said triangle and trapezoid into second regions according to a rule proper to its class.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.