Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1996-10-16
1999-03-23
Nguyen, Phu K.
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
G06F 1500
Patent
active
058867023
ABSTRACT:
A system and method for the rapid creation of an optimized mesh model of a real world object, terrain or other three-dimensional surface. The mesh construction technique provides dynamic "up resolution/down resolution" mesh construction capabilities. The system inserts points into the mesh incrementally, ordering the points before each insertion so that dynamic resolution construction can be maintained. The point ordering process determines the distance each point has from the surface of a given mesh configuration such that the next point added will always be the point bringing the most significant detail to the mesh. This procedure of "optimal simplification" optimizes the mesh by guaranteeing the fewest number of points for the most detail at any given resolution. The present invention also provides a system and method to ensure an optimal quality of mesh at any level of insertion or deletion, following in an exemplary configuration a regularized systemized checking function to maintain a mesh of optimal quality such as by Delaunay triangulation principles. The system stores a history of the insertion and deletion steps in a compact list, which can be used for rapid removal of points or rapid regeneration of the mesh.
REFERENCES:
patent: 4845651 (1989-07-01), Aizawa et al.
patent: 4888713 (1989-12-01), Falk
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: 5561749 (1996-10-01), Shroeder
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: 5689577 (1997-11-01), Arata
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, 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. 6, 1997.
*Stroustrup, Bjarne, "The 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.
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 1995.
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 Geometrics Models from Unstructured 3D Points," Microsoft Corporation 1995.
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.
Lebedev Alexei
Migdal Alexander
Nguyen Phu K.
Real-Time Geometry Corporation
LandOfFree
System and method for computer modeling of 3D objects or surface 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 computer modeling of 3D objects or surface, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for computer modeling of 3D objects or surface will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2131093