Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2006-02-07
2006-02-07
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S001000, C703S006000, C345S419000, C345S428000, C345S619000
Reexamination Certificate
active
06996505
ABSTRACT:
Embodiments automatically generate an accurate network of watertight NURBS patches from polygonal models of objects while automatically detecting and preserving character lines thereon. These embodiments generate from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions using a greedy algorithm that selects edge contractions by their numerical properties. Operations are also performed to connect the triangulations in the hierarchy using homeomorphisms that preserve the topology of the initial triangulation in the coarsest triangulation. A desired quadrangulation of the surface can then be generated by homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation. This quadrangulation is topologically consistent with the initial triangulation and is defined by a plurality of quadrangular patches. These quadrangular patches are linked together by a (U, V) mesh that is guaranteed to be continuous at patch boundaries. A grid is then preferably fit to each of the quadrangles in the resulting quadrangulation by decomposing each of the quadrangles into k2smaller quadrangles. A watertight NURBS model may be generated from the resulting quadrangulation.
REFERENCES:
patent: 4719585 (1988-01-01), Cline et al.
patent: 5103429 (1992-04-01), Gelchinsky
patent: 5214752 (1993-05-01), Meshkat et al.
patent: 5278948 (1994-01-01), Luken, Jr.
patent: 5357599 (1994-10-01), Luken
patent: 5440674 (1995-08-01), Park
patent: 5488684 (1996-01-01), Gharachorloo et al.
patent: 5506785 (1996-04-01), Blank et al.
patent: 5506947 (1996-04-01), Taubin
patent: 5537519 (1996-07-01), Vossler et al.
patent: 5550960 (1996-08-01), Shirman et al.
patent: 5552992 (1996-09-01), Hunter
patent: 5555356 (1996-09-01), Scheibl
patent: 5566281 (1996-10-01), Tokumasu et al.
patent: 5600060 (1997-02-01), Grant
patent: 5617322 (1997-04-01), Yokota
patent: 5668894 (1997-09-01), Hamano et al.
patent: 5701404 (1997-12-01), Stevens et al.
patent: 5726896 (1998-03-01), Jia et al.
patent: 5760783 (1998-06-01), Migdal et al.
patent: 5768156 (1998-06-01), Tautges et al.
patent: 5815401 (1998-09-01), Otsuki et al.
patent: 5850229 (1998-12-01), Edelsbrunner et al.
patent: 5870220 (1999-02-01), Migdal et al.
patent: 5883631 (1999-03-01), Konno et al.
patent: 5886702 (1999-03-01), Migdal et al.
patent: 5903458 (1999-05-01), Stewart et al.
patent: 5923573 (1999-07-01), Hatanaka
patent: 5929860 (1999-07-01), Hoppe
patent: 5945996 (1999-08-01), Migdal et al.
patent: 5963209 (1999-10-01), Hoppe
patent: 5966133 (1999-10-01), Hoppe
patent: 5966140 (1999-10-01), Popovic et al.
patent: 5966141 (1999-10-01), Ito et al.
patent: 5988862 (1999-11-01), Kacyra et al.
patent: 5991437 (1999-11-01), Migdal et al.
patent: 5995650 (1999-11-01), Migdal et al.
patent: 6044170 (2000-03-01), Migdal et al.
patent: 6046744 (2000-04-01), Hoppe
patent: 6064771 (2000-05-01), Migdal et al.
patent: 6100893 (2000-08-01), Ensz et al.
patent: 6108006 (2000-08-01), Hoppe
patent: 6133921 (2000-10-01), Turkiyyah et al.
patent: 6176427 (2001-01-01), Antognini et al.
patent: 6198979 (2001-03-01), Konno
patent: 6201546 (2001-03-01), Bodor et al.
patent: 6205243 (2001-03-01), Migdal et al.
patent: 6208347 (2001-03-01), Migdal et al.
patent: 6256038 (2001-07-01), Krishnamurthy
patent: 6256039 (2001-07-01), Krishnamurthy
patent: 6271856 (2001-08-01), Krishnamurthy
patent: 6278460 (2001-08-01), Myers et al.
patent: 6285372 (2001-09-01), Cowsar et al.
patent: 6313837 (2001-11-01), Assa et al.
patent: 6377865 (2002-04-01), Edelsbrunner et al.
patent: 6417860 (2002-07-01), Migdal et al.
patent: 6654690 (2003-11-01), Rahmes et al.
Heckbert et al, “Optimal Triangulation and Quadric-Based Surface Simplification,” Computational Geometry: Theory and Applications, pp. 1-13 (1999)(paper available at http://citeseer,ist.psu.edu/heckbert99optimal.html).
Ramaswami et al, “Converting Triangulations to Quadrangulations,” Computational Geometry: Theory and Applications, pp. 1-27 (1995)(paper available at http://citeseer.ist.psu.edu/ramaswami95converting.html).
Dey et al., “Topology Preserving Edge Contraction,” Publications De L'Institut Mathematique, vol. 66, No. 80, 1999, pp. 23-45.
Eck et al., “Automatic Reconstruction of B-Spline Surfaces of Arbitrary Topological Type,” Computer Graphics Proceedings, Annual Conference Series, SIGGRAPH 96, New Orleans, LA, Aug. 4-9, 1996, pp. 325-334.
Garland et al., “Surface Simplification Using Quadric Error Metrics,” Computer Graphics Proceedings (SIGGRAPH), 1997, pp. 209-216.
Hagen et al, “Variational Design with Boundary Conditions and Parameter Optimized Surface Fitting,” Geometric Modeling: Theory and Practice, Springer-Verlag, 1997, pp. 3-13.
Hsu et al., “Minimizing the Squared Mean Curvature Integral for Surfaces in Space Forms,” Experimental Math, vol. 1, 1992, pp. 191-207.
Lee et al., MAPS: Multiresolution Adaptive Parameterization of Surfaces, Computer Graphics Proceedings (SIGGRAPH), 1998, pp. 95-104.
Nakamoto, Atsuhiro, “Diagonal Transformations in Quadrangulations of Surfaces,” Journal of Graph Theory, vol. 21, No. 3, 1996, pp. 289-299.
Nakamoto Atsuhiro, “Diagonal Transformations and Cycle Parities of Quadrangulations on Surfaces,” Journal of Combinatorial Theory, Series B 67, 1996, pp. 202-211.
Yang et al., “Segmentation of measured point data using a parametric quadric surface approximation,” Computer-Aided Design 31, 1999, pp. 449-457.
Bajaj et al. “Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans,” Computer Graphics Proceedings, Annual Conference Series, 1995, pp. 109-118.
Bajaj et al., “Modeling with Cubic A-Patches,” ACM Transactions on Graphics, vol. 14, No. 2, Apr. 1995, pp. 103-133.
Bajaj et al., “The Contour Spectrum,” IEEE, 1997, pp. 167-173.
Barequet, Gill “Piecewise-Linear Interpolation between Polygnoal Slices,” Computer Vision and Image Understanding, vol. 63, No. 2, Mar. 1996, pp. 251-272.
Boissonnat, Jean-Daniel, “Geometric Structures for Three-Dimensional Shape Representation,” ACM Transactions on Graphics, vol. 3, No. 1, Oct. 1984, pp. 267-286.
Boissonnat, Jean-Daniel, “Shape Reconstruction from Planar Cross Sections,” Computer Vision, Graphics, and Image Processing, vol. 44, 1988, pp. 1-29.
Bowyer, A. “Computing Dirichlet tessellations”, The Computer Journal, vol. 24, No. 2, 1981, pp. 162-166.
Curless et al., “A Volumetric Method for Building Complex Models from Range Images,” Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 303-312.
Elber et al., “Filleting and Rounding using Trimmed Tensor Product Surfaces,” ACM, 1997, pp. 206-216.
Elber et al., “Tool Path Generation for Freeform Surface Models,” ACM, 1993, pp. 419-428.
Elber et al., “Adaptive Isocurve-Based Rendering for Freeform Surfaces,” ACM Transactions on Graphics, vol. 15, No. 3, Jul. 1996, pp. 249-263.
Edelsbrunner et al., “Incremental Topological Flipping Works for Regular Triangulations,” Algorithmica, vol. 15, 1996, pp. 223-241.
Edelsbrunner et al., “Three-Dimensional Alpha Shapes,” ACM Transactions on Graphics, vol. 13, No. 1, Jan. 1994, pp. 43-72.
Fuchs et al., “Optimal Surface Reconstruction from Planar Contours,” SIGGRAPH 77: The Fourth Annual Conference on Computer Graphics and Interactive Techniques, San Jose, California, Jul. 20-22, 1977, pp. 693-702.
Forsey et al., “Surface Fitting with Hierarchiacal Splines,” ACM Transactions on Graphics, vol. 14, No. 2, Apr. 1995, pp. 134-161.
Hoppe et al., “Piecewise Smooth Surface Reconstruction,” Computer Graphics Proceedings, Annual Conference Series, 1994, pp. 295-302.
Hoppe et al., “Mesh Optimization,” Computer Graphics Proceedings, Annual Conference Series
Edelsbrunner Herbert
Facello Michael
Fu Ping
Nekhayev Dmitry
Williams Steve
Broda Samuel
Meyers Bigel Sibley & Sajovec PA
Raindrop Geomagic, Inc.
LandOfFree
Methods, apparatus and computer program products for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, apparatus and computer program products for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, apparatus and computer program products for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3683208