Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-09-29
2003-07-01
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06587105
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention described herein relates to computer graphics, and more particularly to modeling and manipulation of three dimensional surfaces.
2. Related Art
Currently, subdivision surfaces are not widely used in surface design, especially in the high-end design market, such as the automotive industry where surfaces of degree 5 and 7 are frequently used in the modeling of body panels. Such surfaces are important because they give designers enough degrees of freedom to directly control reflection lines in the panels. The main problem these designers currently face is in the manipulation of regions of irregular topology. For example, corners are typically handled by trimming three non-uniform rational B-spline (NURBS) surfaces of high degree. Trimming is a time-consuming process that yields only approximate continuity. Indeed, at the trim the surface may not even be C
0
continuous. Consequently, designers are forced to fine-tune many arcane parameters for the best fit.
Generalizations for uniform B-spline surfaces of degrees two and three were published in 1978 simultaneously by Catmull and Clark (Catmull, E., and Clark, J.,
Computer Aided Design
10:350-355 (1978)) and by Doo and Sabin (Doo, D., and Sabin, M. A.,
Computer Aided Design
10:356-360(1978)). Since then, it seems no attempt has been successful in extending this work to surfaces of higher degrees. This is partly due to the belief that such methods require large subdivision masks and, consequently, would be difficult to implement. Lower-degree surfaces are sufficient for character animation and free-form modeling, which have up to now been the primary applications of subdivision surfaces in industry.
What is needed, therefore, is a method for generalizing uniform B-spline surfaces of higher degree. A method for doing so must create surfaces that are naturally curvature-continuous at as many points as possible, minimizing the number of points where the curvature generally diverges. This would minimize the need for trimming. Note that by using the higher-degree surfaces, the rate of divergence can be reduced. Moreover, such a method should be easy to implement and should not require large subdivision masks.
SUMMARY OF THE INVENTION
The invention described herein is a method and computer program product for converting an arbitrary mesh to a subdivision surface. Where the subdivision surface is to have an odd degree d=2m+1 on the regular part of the mesh, the method includes the steps of subdividing the mesh in a linear fashion, then iteratively smoothing the subdivided mesh m times. Where the subdivision surface is to have an even degree d=2m on the regular part of the mesh, the method includes the steps of subdividing the mesh, calculating the dual of the subdivided mesh, and iteratively smoothing the dual m−1 times. In either case, the resulting subdivision surfaces generalize uniform tensor product B-spline surfaces of any degree to meshes of arbitrary topology. The method uses subdivision rules that involve direct neighbors, and is computationally efficient.
Although these generalizations are not C
2
everywhere, they provide useful alternatives to the current practice in the high end design market. The method offers C
d−1
continuity everywhere except at the irregular points where they are C
1
. This continuity compares favorably with trimmed NURBS, which are often not even C
0
. While the curvature, in general, diverges at the irregular points, it does so very slowly.
REFERENCES:
patent: 5936633 (1999-08-01), Aono et al.
patent: 6037949 (2000-03-01), DeRose et al.
patent: 6271861 (2001-08-01), Sargent et al.
patent: 6285372 (2001-09-01), Cowsar et al.
patent: 6300960 (2001-10-01), DeRose et al.
patent: 6307555 (2001-10-01), Lee
patent: 6222553 (2002-04-01), DeRose et al.
Charles Teorell Loop, “Smooth Subdivision Surfaces Based on Triangles,” Copyright Charles Teorell Loop, Master of Science Thesis, Department of Mathematics, The University of Utah, Aug. 1987.
Leif Kobbelt, “A Variational Approach to Subdivision,” Computer Aided Geometric Design, Elsevier Science B.V., 1996, vol. 13, pp. 743-761.
Charles K. Chui, “Multivariate Splines,” CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics, 1988, pp. 1-189.
Denis N. Zorin, “Subdivision and Multiresolution Surface Representations,” PhD Thesis, California Institute of Technology, Pasadena, California, 1998.
Ulrich Reif, “A Degree Estimate for Subdivision Surfaces of Higher Regularity,” Proceedings of the American Mathematical Society, American Mathematical Society, vol. 124, No. 7, Jul. 1996, pp. 2167-2174.
Jos Stam, “Exact Evaluation of Catmull-Clark Subdivision Surfaces At Arbitrary Parameter Values,” In Computer Graphics Proceedings, Annual Conference Series, Jul. 1998, pp. 395-404.
Henrik Weimer and Joe Warren, “Subdivision Schemes for Thin Plate Splines,” Proceedings of Eurographics 1998, The Eurographics Association and Blackwell Publishers, vol. 17, No. 3, pp. 303-313.
E Catmull and J Clark, “Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,” Computer Aided Design, IPC Business Press, vol. 10, No. 6, Nov. 1978, pp. 350-355.
Ulrich Reif, “A Unified Approach To Subdivision Algorithms Near Extraordinary Vertices,” Computer Aided Geometric Design, Elsevier Science B.V., 1995, pp. 153-174.
Jorg Peters and Ulrich Reif, “Analysis of Algorithms Generalizing B-Spline Subdivision,” Society for Industrial and Applied Mathematics, SIAM Journal of Numerical Analysis, vol. 35, No. 2, Apr. 1998, pp. 728-748.
D Doo and M Sabin, “Behaviour of Recursive Division Surfaces Near Extraordinary Points,” Computer Aided Design, IPC Business Press, vol. 10, No. 6, Nov. 1978, pp. 356-360.
Jeffrey M. Lane and Richard F. Riesenfeld, “A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAM I-2, No. 1, Jan. 1980, pp. 35-46.
Hoppe, Hugues et al., “Piecewise Smooth Surface Reconstruction,” In Computer Graphics Proceedings, Annual Conference Series, Jul. 1994, pp. 295-302.
Cao Huedung X.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
Zimmerman Mark
LandOfFree
Method and computer program product for subdivision... 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 computer program product for subdivision..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and computer program product for subdivision... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3008752