Patent
1993-02-12
1996-09-03
Herndon, Heather R.
395119, G06T 1720
Patent
active
055532063
ABSTRACT:
A method is provided for producing a mesh representation of an arbitrarily shaped object, for applications such as finite element analysis. The method includes the identifying elements of a mesh, such as a tetrahedral mesh, which are suitable, based on predetermined criteria, for merging into one of a predetermined set of target elements. For instance, if the predetermined set of target elements includes pentahedra and hexahedra, and the method operates on a tetrahedral mesh, then tetrahedra of the mesh are identified based on known ways of decomposing the target elements into tetrahedra. The groups of tetrahedra are identified based on whether they share faces in common, and whether they have faces which share a common edge and which are either coplanar or have an angle between the faces which satisfies a predetermined condition. The latter faces are referred to as quadrilateral pairs. A graph representation of the mesh is used, preferably including nodes representing regions of the mesh (i.e., tetrahedra) and edges between the nodes representing faces shared in common and quadrilateral pairs of faces. Using a search tree representation of a graph of a target element, the graph of the mesh is searched to identify subsets of the graph of the mesh, which represent groups of the tetrahedra of the mesh which are suitable for merging into the target element. By merging the tetrahedra this way, the total number of elements of the mesh is reduced, compared with the original tetrahedral mesh.
REFERENCES:
patent: 3889107 (1975-06-01), Sutherland
patent: 4440532 (1984-04-01), D'Apuzzo
patent: 4502257 (1985-03-01), Diamond
patent: 4534813 (1985-08-01), Williamson et al.
patent: 4646251 (1987-02-01), Hayes et al.
patent: 4785399 (1988-11-01), Evans et al.
patent: 4912644 (1990-03-01), Aoyama et al.
patent: 4930092 (1990-05-01), Reilly
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 4995813 (1991-02-01), Francioni
patent: 5020002 (1991-05-01), Malachowsky
patent: 5046988 (1991-09-01), Bennett
patent: 5100358 (1992-03-01), Volgger
patent: 5101444 (1992-03-01), Wilson et al.
patent: 5104125 (1992-04-01), Wilson
patent: 5125038 (1992-06-01), Meshkat et al.
patent: 5128872 (1992-07-01), Malachowsky et al.
patent: 5222202 (1993-06-01), Koyamada
patent: 5315537 (1994-05-01), Blacker
patent: 5345490 (1994-09-01), Finnigan et al.
patent: 5497452 (1996-03-01), Shimizu et al.
Atkinson, Gargantini, and Ramanath, Determination of the 3D Border by Repeated Elimination of Internal Surfaces, 1984, pp. 279-295.
Foley, Van Dam, Feiner and Hughes, PRW Computer Graphics Principles and Practice, 1990, pp. 533-557; 1040-1041.
W. J. Schroeder et al., Geometry-Based Fully Automatic Mesh Generation and the Delaunay Triangulation, International Journal for Numerical Methods in Eng. vol. 26, 2503-2515, 1988.
J. Ruppert et al., On the Difficulty of Tetrahedralizing 3-Dimensional Non-Convex Polyhedra, Proc. 5th ACM Symp. on Computational Geometry, 1989.
B. Chazelle, Triangulating a nonconvex Polytope, ACM 0-89791-318-3/89/0006/0393-400.
Bern, Provably Good Mesh Generation, IEEE Symp. on Found of Computer Science, 31st, pp. 231-241, 1990.
A. Appel et al., Program for the Interactive Design of Polyhedra, IBM TDB vol. 14, No. 7, pp. 2037-2045, Dec. 1971.
J. C. Cavendish et al., An Approach to Automatic Three-Dimensional Finite Element Mesh Generation, International Journal for Numerical Methods in Eng., vol. 21, 329-347, 1985.
J. G. Hocking et al., Topology, Geometric Complexes and Polytopes Polytopes & Triangulated Spaces and Geometric Complexes and Polytopes, pp. 198-207, 1988.
C. L. Liu, Introduction to Combinatorial Mathematics, Chapter 8, Planar and Dual Graphs, pp. 206-233, 1968.
Meshkat et al., Three-Dimensional Automatic Unstructured Grid Generation Based on Delaunay Tetrahedrization, Num. Grid Generation in Comutational Fluid Dynamics and Related Fields, Elsevier Science Publishers B. V. (North-Holland, pp. 841-853, 1991.
S. Moore et al., Adaptive Mesh Generation I: Packing Space, International Journal of Computational Geometry and Applications, Oct. 22, 1990.
N. Sapidis et al., Domain Delaunay Tetrahedrization of Arbitrarily Shaped Curved Polyhedra Defined in a Solid Modeling System, ACM/SIGGRAPH Symposium on Solid Modeling Foundations & CAD/CAM Applications, Feb. 27, 1991.
M. Senechal, Which Tetrahedra Fill Space?, Mathematics Magazine, vol. 54, No. 5, pp. 227-243, Nov. 1981.
O. C. Zienkiewicz, Finite Elements and Approximation, 1983 Piecewise Defined Trial Functions and The Finite Element Method, pp. 126-132 and Higher-Order Finite Element Approximation, pp. 178-192.
V. Srinivasan, L. R. Nackman, J-M Tang, S. N. Meshkat, Automatic Mesh Generation Using the Symmetric Axis Transformation of Polygonal Domains, Proccedings of the IEEE, vol. 80, No. 9, ISSN 0018-9219, pp. 1485-1501, Sep. 1992.
S. C. Agarwal and W. N. Waggenspack Jr., Decomposition Method for Extracting Face Topologies from Wireframe Models, Computer Aided Design, UK, vol. 24, No. 3, ISSN 0010-4485, pp. 123-140, Mar. 1992.
P. K. Goenka and K. P. Oh, A Three-dimensional Mesh Generation Technique, Proceedings of the 1984 International Computers in Eng. Conf. and Exhibit, pp. 727-735, Aug. 12, 1984.
Buchel Rudolph
Herndon Heather R.
International Business Machines - Corporation
Pintner James C.
LandOfFree
Method and system for producing mesh representations of objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for producing mesh representations of objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for producing mesh representations of objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1958361