Point placement method for use in a three-dimensional automatic mesh generation system

• US 5,214,752 A
• Filed: 01/22/1991
• Issued: 05/25/1993
• Est. Priority Date: 01/22/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ruppert, James M., Meshkat, Siavash N.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/644,162
• Time in Patent Office: 854 Days
• Field of Search: 364/578, 395/123
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method for producing a set of points for a mesh of finite elements for a body to be analyzed, the body exhibiting boundaries and faces. The method comprises the steps of: producing an initial mesh of elements for the body, each element having a plurality of vertices and edges; for each vertex in a first subset of the vertices, finding points of intersection (POI) between a sphere of radius R, centered at a vertex being considered, and the boundaries and edges; determining if a found POI is either on or within the boundaries of the body and exhibits more than a minimum clearance distance from the boundaries, and vertices, any such POI being classified as a selected POI; inserting a selected POI in the initial mesh; and repeating the aforementioned steps for all POI'"'"'s in the first subset and then proceeding to succeeding subsets of vertices until all POI'"'"'s in all subsets have been considered.

Claims

1. A method for producing a set of points for a mesh of finite elements for a body to be analyzed, said body exhibiting boundaries and faces, said method comprising the steps of:

a. producing an initial mesh of elements for said body, each said element having a plurality of vertices and edges;

b. for each vertex in a first subset of said vertices, finding points of intersection (POI'"'"'s) between a sphere of radius R, centered at said vertex, and said boundaries and edges;

c. determining if a found POI is either on or within boundaries of said body and if so, exhibits more than a minimum clearance distance from said boundaries and vertices, if both conditions are met, said POI is classified as a selected POI;

d. inserting a selected POI in said initial mesh; and

e. repeating steps b-d for all POI in said first subset, and then proceeding to succeeding subsets of said vertices, until all subsets have been considered.

2. The method as recited in claim 1 wherein said method comprises the added step of:

a1. assigning to each subset of said vertices, a priority value from a range of values spanning from highest to lowest, and performing steps b-e on all vertices in a subset exhibiting a higher assigned priority, before vertices are considered in a subset having a lower assigned priority.

3. The method as recited in claim 2 wherein said method comprises the further step of:

d1. assigning a priority value to said selected POI which is a next lower priority than the priority value assigned to the subset of which the vertex at the center of said sphere belongs.

4. The method as recited in claim 3 wherein said method comprises the additional step of:

e1. incrementing the value of radius R to a higher value when said method proceeds to consideration of a next subset of vertices having an assigned lower priority value.

5. The method as recited in claim 4 wherein said method comprises the additional step of:

c1. for any POI found which is within said boundaries of said body and exhibits more than a minimum clearance distance from other vertices, but not from a boundary, projecting said POI onto said boundary and classifying such POI as a selected POI.

6. The method as recited in claim 4, wherein step (a) comprises the additional step of:

a2. assigning to a high priority subset of said vertices, any vertex which is close to a neighbor vertex

7. The method as recited in claim 4, wherein step (a) comprises the additional step of:

a2. assigning to a high priority subset of said vertices, any vertex where a boundary condition is specified.

8. The method as recited in claim 4, wherein step (a) comprises the additional step of:

a2. assigning to a high priority subset of said vertices, any vertex located at a sharp corner or turn of said body.

9. The method as recited in claim 4 comprising the further step of:

d2. revising said mesh of elements to include said inserted, selected POI.

10. The method as recited in claim 9 wherein each said element is a tetrahedron, said method comprising the further steps of

f. calculating a volume to area ratio for each tetrahedron created by step d2;

and

g. adding a point locally to create new tetrahedra having larger volume to area ratio if said calculated volume to area ratio in step f falls below a threshold.

11. The method as recited in claim 10 wherein said added local point falls within a circumsphere surrounding a said tetrahedron.

12. The method as recited in claim 11 wherein said added local point is placed within said circumsphere and at a maximum distance from an adjacent boundary, unless such distance is smaller than a threshold, in which case another local point is selected.