Computerized method for decomposing a geometric model of surface or volume into finite elements

• US 5,497,451 A
• Filed: 01/22/1992
• Issued: 03/05/1996
• Est. Priority Date: 01/22/1992
• Status: Expired due to Term

• Current Assignee: David Holmes
• Original Assignee: David Holmes
• Inventors: Holmes, David
• Primary Examiner(s): JANKUS, ALMIS R
• Application Number:
  US07/823,109
• Time in Patent Office: 1,504 Days
• Field of Search: 395/119, 395/120, 395/123, 395/124, 395/127, 395/133, 395/140-143, 364/191, 364/474.24, 364/571.01
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A computerized process for defining finite elements in a surface or volume for ultimately predicting a physical characteristic of the surface or volume. For the surface, for example, the process includes a first step of inputting surface boundary point coordinates of a geometric model of the surface to a computer system, the computer system including an image display screen displaying the geometric model. The process further includes preparing the boundary edges of surface by generating piecewise geometrically smooth bezier curves between boundary points and converting the bezier curves to cubic interpolation polynomials and defining evenly spaced points on each cubic interpolation polynomial and decomposing the surface with divider curves, if the surface is not already 3, 4, or 5 sided, into 3, 4, and 5 sided primitives. Thereafter, a determination is made of the largest acceptable element size and the number of elements disposed along each edge of each primitive. The next steps are readjusting one of the divider curves to match a closest even element vertices and mapping in 3 and 5 sided clusters and then preparing remaining 4 sided primitives for decomposition into 4 sided elements and mapping in elements and element patches. Thereafter, method includes the steps of optimising the elements in the mesh and writing the resulting mesh to a storage file.

Claims

1. A method for defining finite elements in a surface for ultimately predicting a physical characteristic of the surface, which method comprises:

providing a computer system having a computer connected to an input device, to an image display screen and to a storage file, the storage file including instructions and data for at least steps (iii) through (xi) of said method;

(i) inputting, through the input device, surface boundary point coordinates of a geometric model of a surface;

(ii) displaying a surface object on the image display screen, the surface object consisting of the geometric model of the surface;

(iii) preparing boundary edges of the surface object by generating piecewise geometrically smooth bezier curves between boundary points and converting the bezier curves to cubic interpolation polynomials and defining evenly spaced points on each cubic interpolation polynomial;

(iv) decomposing the surface object with divider curves, if the surface object is not already 3, 4, or 5 sided, into 3, 4, and 5 sided primitives;

(v) determining a largest acceptable element size;

(vi) determining a number of elements disposed along each edge of each primitive; and

(vii) readjusting one of the divider curves to match closest even element vertices;

(viii) mapping in 3 and 5 sided clusters;

(ix) preparing remaining 4 sided primitives for decomposition into 4 sided elements;

(x) mapping in elements and element patches to develop a mesh from the surface object;

(xi) optimizing the elements in the mesh; and

(xii) writing the mesh having the optimized elements to the storage file.

2. The method as described in claim 1 further including:

if all sub-surfaces thereof remaining after definition of primitives are not already 3, 4, or 5 sided, into 3, 4, and 5 sided primitives includes;

considering a first sub-surface making up the surface that is not 3, 4, or 5 sided;

generating a straight line base of a divider curve;

if no resulting sub-surface is a trivial surface then generating a divider curve; and

if a resulting surface is a trivial surface then decomposing the trivial surface.

3. The method as described in claim 2 wherein the step of decomposing the trivial surface includes:

if one of the resulting sub-surfaces is trivial then place an alternative extruded divider curve between the two longest edges of the sub-surface containing the shortest boundary edge;

considering the part of the trivial surface that is not composed of the shortest boundary edge and generating a straight line base of divider curve;

verifying successful decomposition of the sub-surface;

if decomposition of the trivial surface is unsuccessful then moving the alternative extruded divider curve along the two longest boundary edges away from the shortest base surface edge; and

if decomposition is successful generating a divider curve.

4. The method as described in claim 3 wherein the decomposition of the trivial surface includes:

generating a straight line base of a divider curve;

finding two points not located on the extent of any two adjacent boundaries that are the closest together of any other corresponding two points on the boundaries of the surface;

testing the resulting line segment to verify if both ends form angles which are substantially between 80 and 100 degrees with the surface boundary tangents; and

if these angles are not substantially between 80 and 100 degrees then excluding these two points.

5. The method as described in claim 4 wherein the step of preparing the boundary edges includes:

generating piecewise geometrically smooth bezier curves between the boundary points convert bezier curves to cubic interpolation polynomials; and

defining evenly spaced points on each cubic interpolation polynomial.

6. The method as described in claim 5 wherein the step of determining the largest acceptable element size includes:

finding the primitive edge having the shortest length; and

divide the primitive edge having the shortest length by 4 using the resulting number as the largest possible element size for the surface.

7. The method as described in claim 6 wherein the step of determining the number of elements disposed along each edge of each primitive includes:

specifying the largest element size;

if the specified element size is greater than the largest possible element size then repeat the preceding step;

if the specified element size is less than the largest possible element size calculate the nearest even number of elements along each primitive edge by dividing each edge length by the given element size and rounding the result off to the nearest even number.

8. The method as described in claim 7 wherein the step of readjusting one of the divider curves includes:

considering the next to last, in order of creation, divider curve that has been previously defined;

if one of the endpoints of this divider curve contacts a previously created divider curve then relocate this divider curve end point so that it is compatible with the vertex of an even element located on the previously divider curve; and

sequentially consider the next divider curve, in opposite order of creation, if one of the endpoints contacts a previously created divider curve then relocate this divider curve end point so that it is compatible with the vertex of an even element located on the previously created divider curve.

9. The method as described in claim 8 wherein the step of mapping in 3 and 5 sided clusters includes:

optimizing the 3 and 5 sided primitives by optimizing the shape of the 3 and 5 sided clusters in the 3 and 5 sided primitives;

mapping 3 and 5 sided clusters into the 3 and 5 sided primitives;

generating the remaining 4 sided primitives in each 3 and 5 sided primitive.

10. The method as described in claim 9 wherein the step of preparing the remaining 4 sided primitives for decomposition into 4 sided elements includes:

splitting each 4 sided primitive into patch halves;

generating layers in each half;

storing the layers in the order of the decreasing difference between opposing edge lengths along the corresponding patch half axis;

calculating the nearest even number of elements along each layer edge perpendicular to the corresponding patch axis by dividing each edge length by the given element size; and

determining the number of and direction of patches per layer.

11. The method as described in claim 10 wherein the step of mapping in elements and element patches includes:

placing element patch configurations into each layer in the descending order of the difference between opposing edge lengths repeatedly until the difference in the number of elements on each patch half opposing edge is matched; and

mapping in the remainder of the layers with 2×

N filler elements where N is any even integer greater than zero.

12. The method as described in claim 11 wherein the step of optimizing the elements in the mesh includes the steps of sequentially:

optimizing all 3 sided cluster elements;

optimizing all 5 sided cluster elements; and

optimizing all elements having sequential included angles of substantially 60-90-120-90 degrees in each element patch configuration to more nearly have a more precise 60-90-120-90 degree angular relationship.

13. A method for defining finite elements in a volume for ultimately predicting a physical characteristic of said volume, which method comprises:

(i) providing a computer system having a computer connected to an input device, to an image display screen and to a storage file, the storage file including instructions and data for at least steps (iv) through (xviii) of said method;

(ii) inputting, through the input device, surface boundary point coordinates of a geometric model of each surface of a volume;

(iii) displaying on the image display screen a surface object for each surface of the volume, each surface object consisting of the geometric model of the surface;

(iv) inputting points defining boundaries of each surface of the volume to produce an outward pointing normal away from an interior of the volume;

(v) setting up an initial surface adjacency description for the volume;

(vi) initializing a volume adjacency array;

(vii) excising non-linear extrusions from the volume;

(viii) decomposing remaining sub-volumes not having 3, 4, or 5 sides into volumes with 3, 4, or 5 sides;

(ix) decomposing any composite sub-volumes;

(xi) decomposing any symmetric sub-volumes;

(xii) generating real divider surfaces for each volume adjacency array axis;

(xii) converting sub-volume data to an extrusion volume data format;

(xiii) optimizing all three sided extrusions;

(xiv) optimizing all five sided extrusions;

(xv) determining a number of elements per extrusion edge;

(xvi) generating extrusion surface;

(xvii) mapping in elements and element patches into the extrusion surfaces to develop a mesh from each surface object of the volume;

(xviii) converting the volume to hexahedron elements; and

(ixx) writing the mesh to a file in the storage file.

14. The method as described in claim 13 wherein the step of excising non-linear extrusions from the volume:

if the volume has any edges that are associated with one of the non-linear volumes or has at least one 3 sided surface and is not already a 3 sided extrusion then begin placement of the generic divider surfaces for the decomposition of the corresponding sub-volume from a data file;

creating all the generic divider surfaces that are necessary to excise the non-linear volume or a 3 sided extrusion from the volume;

continuing decomposition through the volume adjacency array;

if there is a non-linear volume then breaking existing non-linear extrusions into 4 and 5 sided extrusions;

continuing the decomposition through the volume adjacency array; and

considering another non linear sub-volume or a sub-volume with at least one surface that has 3 edges.

15. The method as described in claim 14 wherein the step of decomposing remaining sub-volumes without 3, 4, or 5 sides into volumes with 3, 4, or 5 sides includes:

repetitively, for each sub-surface of the sub-volume not having 3, 4, or 5 edges and has the greatest number of edges of any other surface in the sub-volume, generating the generic divider surface that has the greatest number of sides for the sub-volume starting it on the largest surface edges.

16. The method as described in claim 15 wherein the step of decomposing any composite sub-volumes;

if any sub-volume is a composite volume then creating a generic divider surface for the composite sub-volume;

continue decomposition through the volume adjacency array; and

consider another composite volume from the volume adjacency array.

17. The method as described in claim 16 wherein the step of decomposing any symmetric sub-volumes includes:

create generic divider surfaces.

18. The method as described in claim 17 wherein the step of generating real divider surfaces includes:

defining the original surfaces of the volume using surface decomposition;

if there are any divider surfaces then plotting N×

N meshes into each original surface primitive and calculate the spacing of each divider surface edge along the original surface edges;

generating skeleton curves for the new divider surfaces on the original volume surfaces;

mapping all the divider surface edges into the original volume surface primitives based on the skeleton curve entry and exit points of the surface primitives;

if there is more than one axis of the volume adjacency array then locating any divider surface edge intersection points edge within each original surface primitive;

if there is a first axis of divider surfaces then defining the surfaces along a first axis with the new edges;

if there is a second axis of divider surfaces then defining the divider surfaces and the curves resulting from surface intersection with the surfaces along the first axis as skeleton curves beginning and ending at the corresponding divider surface edge intersection points defined within the original volume surface primitives; and

if there is a third axis of divider surfaces then defining the divider surfaces and the curves resulting from surface intersection with the first and second axis surfaces as skeleton curves using the same points on the first and second surfaces intersection curves as one of the corner vertices for the resulting sub-surfaces.

19. The method as described in claim 18 wherein the step of optimizing all three sided extrusions includes:

if a sub-volume is a first three sided extrusion then begin optimizing the first 3 sided extrusion;

continuing decomposition through the volume adjacency array;

sequentially optimize other sub-volumes from the volume adjacency array that are 3 sided extrusions.

20. The method as described in claim 19 wherein the step of optimizing all five sided extrusions includes:

if a first sub-volume is a five sided extrusion then begin optimizing the first 5 side extrusion;

continuing decomposition through the volume adjacency array;

sequentially optimizing other sub-volumes from the volume adjacency array that are 5 sided extrusions.

21. The method as described in claim 20 wherein the step of determining the number of elements per extrusion edge:

inputting the number of elements per extrusion surface edge;

if the number of elements is less than 4 and not an even number then repeatting the preceding step.

22. The method as described in claim 21 wherein the step of converting the volume to hexahedron elements includes:

mapping 3, 4, or 5 sided meshes onto the extrusion surfaces;

optimizing the elements for each extrusion surface; and

converting the mesh into hexahedron elements.