Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1996-10-16
1999-08-31
Feild, Joseph H.
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
G06T 1700
Patent
active
059459964
ABSTRACT:
A system and method for the rapid creation of a mesh model depicting a real world object, terrain or other three-dimensional surface. The system inserts points into the mesh incrementally, building the mesh point by point. Before incremental building, the system orders the points so that each next point is a near neighbor to the previously inserted point. This ordering procedure optimizes mesh construction by guaranteeing a minimal time for locating the area on the mesh into which the next point will be inserted. The present invention also provides a system and method to ensure an optimal quality of mesh at any level of insertion or deletion, following systematized checking function to maintain quality such as that required in Delaunay triangulation. The system and method can also incorporate a history file to store data concerning the results of the checking to substantially reduce processing time in mesh regeneration applications.
REFERENCES:
patent: 4845651 (1989-07-01), Aizawa et al.
patent: 4888713 (1989-12-01), Falk
patent: 4912644 (1990-03-01), Weiss et al.
patent: 4912664 (1990-03-01), Weiss et al.
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 4941114 (1990-07-01), Shigyo et al.
patent: 4994989 (1991-02-01), Usami et al.
patent: 5107444 (1992-04-01), Wu
patent: 5125038 (1992-06-01), Meshkat et al.
patent: 5189626 (1993-02-01), Colburn
patent: 5193145 (1993-03-01), Akeley
patent: 5214752 (1993-05-01), Meshkat et al.
patent: 5255352 (1993-10-01), Falk
patent: 5257346 (1993-10-01), Hanson
patent: 5303386 (1994-04-01), Fiasconaro
patent: 5345490 (1994-09-01), Finnigan et al.
patent: 5367615 (1994-11-01), Economy et al.
patent: 5377011 (1994-12-01), Koch
patent: 5379371 (1995-01-01), Usami et al.
patent: 5398307 (1995-03-01), Arakawa
patent: 5410644 (1995-04-01), Thier et al.
patent: 5412762 (1995-05-01), Kondo
patent: 5440674 (1995-08-01), Park
patent: 5448686 (1995-09-01), Borrel et al.
patent: 5448687 (1995-09-01), Hoogerhyde et al.
patent: 5465323 (1995-11-01), Mallet
patent: 5475799 (1995-12-01), Yoshioka et al.
patent: 5488692 (1996-01-01), Karasick et al.
patent: 5497451 (1996-03-01), Holmes
patent: 5522019 (1996-05-01), Bala et al.
patent: 5553206 (1996-09-01), Meshkat
patent: 5561749 (1996-10-01), Schroeder
patent: 5563995 (1996-10-01), Shirouzu
patent: 5579454 (1996-11-01), Billyard et al.
patent: 5581673 (1996-12-01), Kikuchi
patent: 5590248 (1996-12-01), Zarge et al.
patent: 5602979 (1997-02-01), Loop
patent: 5617322 (1997-04-01), Yokota
patent: 5630039 (1997-05-01), Fossum
patent: 5677846 (1997-10-01), Kumashiro
patent: 5710878 (1998-01-01), McCoy et al.
patent: 5731817 (1998-03-01), Hahs, Jr. et al.
Hoppe, Hugues, "Surface Reconstruction from Unorganized Points", PhD thesis, Department of Computer Science and Engineering, University of Washington, Jun. 1994 (TR 94-06-01).
Eck, Matthias et al., "Multiresolution Analysis of Arbitrary Meshes" Technical Report #95-01-02.
DeRose, Tony et al., "Fitting of Surfaces to Scattered Data", In J. Warren, editor, Curves and Surfaces in Computer Vision and Graphics III, Proc. SPIE 1830:212-220, 1992.
Hoppe, Hugues, "Generation of 3D Geometric Models from Unstructured 3D Points," Microsoft Corporation.
Turk, Greg et al., "Zippered Polygon Meshes from Range Images" Computer Graphics (SIGGRAPH '94 Proceedings), 28(3):311-318, Jul. 1994.
"Basic Methods and Algorithms: Voronoi Diagrams, Delaunay Triangulation and Construction of a TIN" Internet site http://www.iko.no, Printed Feb. 12, 1996.
Agishtein, Michael et al, "Smooth Surface Reconstruction from Scattered Data Points", Comput. & Graphics, vol. 15, No. 1, pp. 29-39, 1991.
Agishtein, Michael et al., "Geometric Characterization of States in Two-Dimensional Quantum Gravity", submitted to Physics Letters B, pp. 1-12, Mar. 1990.
Agishtein, Michael et al., "Dynamics of Vortex Surfaces in Three Dimensions: Theory and Simulations", Physica D 40, pp. 91-118, 1989.
Certain, Andrew et al., "Interactive Multiresolution Surface Viewing", SIGGRAPH 96 Conference Proceedings, pp. 91-98, 1996.
Cohen, Jonathan et al., "Simplification Envelopes", SIGGRAPH 96, Computer Graphics, Aug. 1996.
*Eckel, Bruce, "C++ Inside and Out", Osborne McGraw Hill, 1993.
Hoppe, Hugues et al., "Mesh Optimization", Computer Graphics Proceedings, Annual Conference Series, pp. 19-26, 1993.
Hoppe, Hugues, "Progressive Meshes", SIGGRAPH 96 Conference Proceedings, pp. 99-108, 1996.
Lindstrom, Peter et al., "Real-Time, Continuous Level of Detail Rendering of Height Fields", SIGGRAPH 96 Conference Proceedings, pp. 109-117, 1996.
Migdal, A.A., "Dynamically Triangulated Random Surfaces", Nuclear Physics B, Proc. Suppl. 9, pp. 625-630, 1989.
*Preparata and Shamos, "Computational Geometry", Springer-Verlag, New York, 1988 (second printing).
Schroeder, William, et al., "Decimation of Triangle Meshes", Computer Graphics, 26(2), pp. 65-80, Jul. 1992.
Shewchuk, Jonathan, "A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator", Triangle Website, http://www.cs.cmu.edu/People/quake/triangle.html, printed Mar. 16, 1997.
*Stroustrup, Bjarne, "C++ Programming Language", Addison Wesley Publishing Co., 1991.
"Multiresolution Modeling", Internet site http://www.cs.cmu.edu/afs..d/www/multires, printed May 7, 1997.
Silicon Graphics Indigo.sup.2 Impact Website, http://www.sgi.com/Products/hardware/Indigo2/tech.html, printed Jun. 22, 1997.
Silicon Graphics Technology Website, http://www.sgi.com/Product/hardware/desktop/tech.html, printed Jun. 22, 1997.
Lebedev Alexei
Migdal Alexander
Feild Joseph H.
Kindred Alford W.
Real-Time Geometry Corporation
LandOfFree
System and method for rapidly generating an optimal mesh model o does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for rapidly generating an optimal mesh model o, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for rapidly generating an optimal mesh model o will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2427524