Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-09-29
2001-07-24
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C345S423000
Reexamination Certificate
active
06266062
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the computer geometric modeling of a body as needed through the use of finite element analysis. In particular the invention relates to the generation of an improved and/or refined and/or derefined mesh of finite elements using an improved and flexible mesh generation method, an improved mesh data structure, and an apparatus therefor.
BACKGROUND OF THE INVENTION
Finite element analysis is a powerful computer-aided tool for solving engineering and physical problems governed by partial differential equations. Finite element analysis is used in approximating any continuous physical characteristic of an object or a geometric region, such as temperature, heat, vibration, fluid flow, electric field, pressure, etc. Finite element analysis is specially important when the geometry of the object to be modeled is relatively complex, e.g. includes small details, since the differential equations for such applications become increasingly difficult to approximate accurately.
An initial step of a finite element analysis involves the construction of a mesh of finite elements covering the geometric region whose vertices are in turn points selected on the surface and in the interior of the object. Accurate and modern finite element analysis requires that a flexible mesh improvement/refinement/derefinement method, alternatively described as a point placement/elimination method, be used in order to produce a mesh that satisfies at least five criteria: (1) the overall point or vertex density is able to be specified and modified; (2) the density of vertices should increase and/or decrease in critical regions, (i.e., in those which have small features and concave corners or as needed in some time dependent problems); (3) badly-shaped finite elements should be avoided; (4) a mesh derived from a set of vertices should be able to be refined and/or derefined in certain areas by the user or the finite element analysis solving method; (5) the mesh should respect the object boundaries and interfaces.
It is known that the generation of a 3-D mesh suitable for finite element analysis has been one of the most time consuming steps in using the computer to analyze a complex engineering problem. Most previous work on 3-dimensional mesh improvement/refinement/derefinement and/or point placement/elimination has been heuristic in nature. For accurate analysis many approaches have required significant manual interaction between the user and the mesh generation system.
Several scientific articles considering mesh generation methods for use in finite element analysis have been published. In particular several papers appearing in the International Journal for Numerical Methods in Engineering consider the generation of a mesh by using the Delaunay triangulation. These papers are as follows: Cavendish et al., vol. 21, pp. 329-347, (1985); Frey, vol. 24, pp. 2183-2200, (1987); Schroeder et al., vol. 26, pp. 2503-2115, (1988); Schroeder et al. vol. 29, pp. 35-55, (1990); Golias et al., vol. 37, pp. 793-812, (1994); Field et al. vol. 31, pp. 413-425, (1991); Wheaterill et al., vol. 37, pp. 2005-2039 (1994);
Other papers considering Delaunay triangulation are the following: Baker, Engineering with Computers, vol. 5, pp. 161-175, (1989); Mitchell et al., IEEE Transactions on Magnetics, vol. 28, pp. 1751-1754 (1992); Ruppert, Journal of Algorithms, vol. 18, 548-585 (1995); Rebay, J. Comp. Physics, vol. 106, 125-138 (1993); Joe, Siam J. Sci. Comput. vol. 16, 1292-1307 (1995).
Each of the aforementioned papers employs a teaching of Delaunay to achieve planar triangulation and three-dimensional tetrahedrization. A tetrahedral mesh is defined as a “Delaunay tetrahedrization” if and only if, for each tetrahedron in the mesh, the sphere defined by the four vertices of the tetrahedron, called its circumsphere, contains no mesh vertices in its interior. Vertices on the circumsphere's boundary are permitted. The same property applies to two-dimensional surfaces: a surface triangulation is defined as a Delaunay triangulation if and only if, for each triangle in the mesh, a circle defined by the three vertices contains no other vertices in its interior.
However, it is well known to those skilled in the art that the ability of the 3-dimensional Delaunay technique to produce quality meshes strongly depends on the point placement method. Quality is a very important factor since a bad-quality mesh can result in inaccurate numerical approximation. Consequently bad-shaped tetrahedra are to be avoided, especially undesirable “slivers,” that is tetrahedra formed by 4 almost coplanar vertices and whose longest-edge and smallest-edge are of “comparable size”. Most of the aforementioned papers discuss some point placement strategies and some mesh improvement and/or mesh refinement tools.
Cavendish et al. (1985) implement such a triangulation by rejecting from the set of all possible triangles which might be formed, those with non-empty associated circles. Those triangles not rejected, form the Delaunay triangulation. Schroeder et al. (1988) apply those teachings to three-dimensional surfaces.
Frey (1987) teaches a method for selective refinement of an initial triangulation. Grading of the mesh is controlled by a node spacing function wherein a prospective node is inserted and its spacing from adjacent nodes is evaluated. Each new prospective node is also tested to see if its insertion would lead to a Delaunay triangulation with an acceptable degree of spacing at new node. Shroeder et al. (1990) use an octree method for producing a set of points representing the geometry of the object.
Golias et al. (1994) describe an element-based method to perform automatic mesh refinement producing almost-Delaunay triangulations as follows: the midpoint of the longest edge of each target element is chosen and all the elements having this edge in common are partitioned; the non-Delaunay mesh thus obtained is then subjected to the repeated application of a set of local topological transformations performed over all the elements of the mesh, followed by an overall node relaxation technique, until the equilibrium of the mesh is achieved.
Field et al. (1991) also use local transformations for producing almost-Delaunay meshes satisfying a local max-min solid angle criterion. Weatheril et al. (1994) select the points to be added to the mesh between the centroids of the elements of the mesh by using different point distribution functions interpolated to the interior vertices. Baker (1989) considers the addition of a new vertex near each sliver followed by a retriangulation step. Mitchell et al. (1992) use an element size function throughout the mesh and a local realignment of the nodes for improving the mesh. Joe (1995) also uses local topological transformations for producing improved almost Delaunay meshes.
Ruppert (1995) teaches a point insertion method which guarantees the construction of good-quality 2-D Delaunay triangulations by adding points in the circumcenter of the worst small-angled triangles of the current mesh. Rebay (1993) teaches an alternative point insertion method based on selecting a maximal non-accepted triangle which is also adjacent to an accepted triangle; then selecting a point situated over the segment that joins the circumcenter of the two triangles.
In the scientific literature considerable attention has been also paid to methods that consider the refinement of any general non-Delaunay mesh by performing selective longest-edge bisection of a set of appropriate elements of the mesh. In 2-dimensions, longest-edge bisection is obtained by partitioning the element by the line defined by the midpoint of the longest-edge and the opposite vertex. In 3-dimensions, longest-edge bisection is in turn obtained by partitioning the element by the plane defined by the midpoint of the longest-edge and the two opposite vertices. It has been shown that longest-edge refinement methods improve the point distribution by maintaining some small-angled triangles which depend on the quality of the initial mesh. The
Santiago Enrique L
Yablon Jay R.
Zimmerman Mark
LandOfFree
Longest-edge refinement and derefinement system and method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Longest-edge refinement and derefinement system and method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest-edge refinement and derefinement system and method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2465405