Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1997-05-23
2000-08-08
Zimmerman, Mark K.
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
345441, G06T 1700
Patent
active
061008931
ABSTRACT:
A solid model is constructed from surface point data that represent layers of an object. The model is represented as the level set of an implicit function that is fitted to the surface point data. In the two-dimensional application of the technique, a Delaunay triangulation is performed for each layer. In this step, surface points are connected to form Delaunay triangles; the data points are the vertices of the Delaunay triangles. A circumcircle is then created around each Delaunay triangle, passing through the three vertices of the triangle. To decimate the circumcircle data, overlapping circumspheres are merged according to a merging criterion. A pseudo-union of implicit functions for the reduced number of circumcircles provides an initial implicit function for the layer. Errors in the implicit function are substantially reduced by optimizing the position and/or radii of the circumcircles. The implicit functions for a plurality of adjacent layers are blended to define an implicit function for the object that is used for reconstruction or modeling of the object. The technique is generally extended to n dimensional objects by using simplices instead of the Delaunay triangles and hyperspheres instead of the circumcircles. The method is capable of constructing solid models with highly localized surface curvature.
REFERENCES:
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 5522019 (1996-05-01), Bala et al.
patent: 5542036 (1996-07-01), Schroeder et al.
patent: 5559935 (1996-09-01), Itoh et al.
patent: 5617322 (1997-04-01), Yokota
patent: 5774696 (1998-06-01), Akiyama
Turner, J; Accurate Solid Modeling Using Polyhedral Approximations; IEEE Computer Graphics & Applications; pp. 14-28, 1988.
Herman, G. et al.; Shape-based Interpolation; IEEE Computer Graphics & Applications; pp. 69-79, May 1992.
Lavender, D. et al.; Voroni Diagrams of Set-Theoretic Solid Models; IEEE Computer Graphics & Applications; pp. 69-77, Sep. 1992.
Zhou, J.M. et al.; Automatic Creation of 3D Meshes for Complicated Solids; IEEE Transactions on Magnetics, vol. 28, No. 2; pp. 1759-1762, Mar. 1992.
Barequet, G., et al., Piecewise-Linear Interpolation Between Polygonal Slices, Proceedings of the Tenth Annual Symposium on Computational Geometry, pp. 93-102. ACM Press, Jun. 1994.
Blechschmidt, J.L., et al., The Use of Algebraic Functions as a Solid Modeling Alternative: An Investigation, Advances in Design Automation: Computer-Aided and Computational Design, vol. DE-23(1), 1990, pp. 33-41.
Blinn, J.F., A Generalization of Algebraic Surface Drawing, ACM Transactions on Graphics, vol. 1, No. 3, Jul. 1982, pp. 235-256.
Bloomenthal, J., An Implicit Surface Polygonizer. Graphic Gems IV, P.S. Heckbert, editor, AP Professionsl, Cambridge, Massachusetts, 1994, pp. 324-349.
Blum, H., A Transformation for Extracting New Descriptors of Shape. Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, editor, MIT Press, 1967, pp. 362-381.
Boissonnat, J.D., Geometric Structures for Three-Dimensional Shape Representation, ACM Transactions on Graphics, 3(4), 1984, pp. 266-286.
Boissonnat, J.D., Shape Reconstruction from Planar Cross Sections, Computer Vision, Graphics, and Image Processing, vol. 44, Oct. 1988, pp. 1-29.
Boult, T.E., et al., Recovery of Superquadrics from Depth Information, Proceedings of Workshop on Spatial Reasoning and Multi-Sensor Fusion, 1987, pp. 128-137.
Chiang, C.S., et al., How to Compute Offsets Without Self-Intersection, Curves and Surfaces in Computer Vision and Graphics II, SPIE, vol. 1610, 1991.
Chou, J.J., Voronoi Diagrams for Planar Shapes. IEEE Computer Graphics and Applications, 15(2), Mar. 1995, pp. 52-59.
Christiansen, H., et al., Conversion of Complex Contour Line Definitions Into Polygonal Element Mosaics, Computer Graphics, 12(3), 1978, pp. 187-192.
Danielsson, P.E., Euclidean Distance Mapping, Computer Graphics and Image Processing, 14, 1980, pp. 227-248.
DeRose, T., et al., Geometric Continuity, Shape Parameters, and Geometric Constructions for Catmull-Rom Splines, ACM Transactions on Graphics, 7(1), 1988, pp. 1-41.
Dobkin, D.P., et al., Primitives for the Manipulation of Three-Dimensional Subdivisions, Algorithmica, vol. 4, 1989, pp. 3-32.
Dong, Y., et al., Building Solid Models From Serial Contour Images, Proceedings of the SPIE-Image and Video Processing III, vol. 2421, San Jose, California, USA, 9-10 Feb. 1995, pp. 152-160.
Dutta, D., et al., On the Skeleton of Simple CSG Objects, ASME Journal of Mechanical Design, 115(1), 1992, pp. 87-94.
Edelsbrunner, H., et al., Three-Dimensional Alpha Shapes, ACM Transactions on Graphics, 13(1), 1994, pp. 43-72.
Ensz, M.T., et al., Implicit Function Alteration Via Radius Mapping and Direct Function Modification, ASME Advances in Design Automation, DE-vol. 82-1, 1995, pp. 57-64.
Ferrie, F.P., Recovery of Volumetric Object Descriptions From Laser Rangefinder Images, Proceedings of Computer Vision, ECCV 90, Antibes, France, 1990, pp. 387-396.
Foley, T.A., et al., Advances in Scattered Data Interpolation, Surveys on Mathematics for Industry, 4(2), 1994, pp. 71-84.
Franke, R., et al., Scattered Data Interpolation and Applications: A Tutorial and Survey, Geometric Modeling, Methods and Applications, Boblingen, Germany, Jun. 1990, pp. 131-160.
Fuchs, H., et al., Optimal Surface Reconstruction From Planar Contours, Communications of the ACM, vol. 20, No. 10, Oct. 1997, pp. 693-702.
Ganapathy, S., et al., A New General Triangulation Method for Planar Contours, Computer Graphics, 16(3), 1982, pp. 69-75.
Ganter, M.A., et al., On Algebraic Methods for Implicit Swept Solids with Finite Extent, Advances in Design Automation, DE-vol. 65-2, vol. 2, Albuquerque, New Mexico, Sep. 1993, pp. 389-396.
Gelston, S.M., et al., Boundary Surface Recovery From Skeleton Curves and Surfaces, Computer Aided Geometric Design, 12(2), 1995, pp. 27-51.
Gursoy, H.N., et al., An Automated Coarse And Fine Surface Mesh Generation Scheme Based On Medial Axis Transform: Part I Algorithms, Engineering with Computers, 8(3), 1992, pp. 121-137.
Hoffman, C.M., How to Construct the Skeletons of CSG Objects, Proceedings of the Fourth IMA Conference: The Mathematics of Surfaces, A. Bowyer and J. Davenport, editors, pp. 77-88. Oxford University Press, 1994.
Hoffman, C.M., Constrained Surface Computations and Applications in Geometric Modeling, Workshop on Computational Geometry, World Scientific Publishing Co., 1993, pp. 175-200.
Hoppe, H., et al., Mesh Optimization, Computer Graphics Proceedings, SIGGRAPH '93, pp. 19-26, Annual Conference Series, 1993, pp. 19-26.
Hoppe, H., et al., Surface Reconstruction From Unorganized Points, Computer Graphics, SIGGRAPH '92, 1992, pp. 71-78.
Hsieh, Y.C., et al., Reconstruction of Sculptured Surfaces Using Coordinate Measuring Machines, Advances in Design Automation, DE-vol. 65-2, ASME, vol. 2, Albuquerque, New Mexico, USA, 1993, pp. 35-46.
Keppel, E., Approximating Complex Surfaces by Triangulation of Contour Lines, IBM Journal of Research and Development, vol. 19, Jan. 1975, pp. 2-11.
Kumar, V., et al., An Assessment of Data Formats for Layered Manufacturing, Advances in Engineering Software, Report No. UM-MEAM-95-22, University of Michigan (1995).
Lee, D.T., Medial Axis Transformation of a Planar Shape, IEEE Transactions of Pattern Analysis and Machine Intelligence, vol. PAMI-4, No. 4, Jul. 1982, pp. 363-369.
Leymarie, F., et al., Simulating the Grassfire Transform Using an Active Contour Model, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, No. 1, Jan. 1992, pp. 56-75.
Lim, C.T., et al., Algebraic Computer Aided-Design with Maple V 2, Mathematical Computation with Maple V: Ideas and Applications, Proceedings of the Maple Summer Workshop and Symposium, T. Lee, editor, University of Michigan, Ann Arbor, Jun. 28-30, 1993, Boston, Massachusetts, USA, 1993, pp. 169-175.
Lim, C.T., et al., Implicit Reconstruction of Solids from Cloud Point Sets, Third Symposium on Solid Modeling and Applications, C. Hoffman and J. Rossignac, editors, ACM Press, Salt Lake City, Utah, 1995, pp. 393-402.
Lim, C.T., et al., Object Reconstruct
Ensz Mark T.
Ganter Mark A.
Lim Chek T.
Storti Duane W.
Turkiyyah George M.
Anderson Ronald M.
Lee Albert K.
Light Sciences Limited Partnership
Zimmerman Mark K.
LandOfFree
Constructing solid models using implicit functions defining conn does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Constructing solid models using implicit functions defining conn, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing solid models using implicit functions defining conn will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1154985