Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-01-09
2002-12-03
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000
Reexamination Certificate
active
06489960
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the art of computer graphics and the modeling of objects. More particularly the invention relates to the modeling of objects using subdivision surfaces and to the modeling of objects with semi-sharp creases or edges.
BACKGROUND OF THE INVENTION
No real objects have perfectly sharp features. All edges, even those on seemingly sharp objects, have some finite radius of curvature. Though inevitable in real life, this unavoidable lack of precision presents a difficult problem for computer graphics and computer animation. Some modeling methods, e.g., the use of piecewise linear surfaces (polygon meshes) work well for objects with sharp boundaries. Other methods, e.g., NURBS (non-uniform rational B-splines) work well (i.e., are more accurate and compact) for modeling curved surfaces, but fair less well and are less efficient for modeling objects with sharp features.
In recent work, Hoppe, et al. have shown that piecewise smooth surfaces incorporating sharp features, including edges, creases, darts and corners, can be efficiently modeled using subdivision surfaces by altering the standard Loop subdivision rules in the region of such sharp features. Hoppe, et al., Piecewise Smooth Surface Reconstruction,
Computer Graphics
(
SIGGRAPH '
94
Proceedings
), pgs. 295-302. The modified subdivision surface technique developed by Hoppe, et al, provides for an efficient method for modeling objects containing both curved surfaces and sharp features. The resulting sharp features are, however, infinitely sharp, i.e., the tangent plane is discontinuous across the sharp feature.
Even the method of Hoppe, et al. does not, therefore, solve the problem of modeling real objects with finite radius edges, creases and corners. To model such objects with existing techniques, either subdivision surfaces, NURBS, or polygons, requires vastly complicating the model by including many closely spaced control points or polygons in the region of the finite radius contour. As soon as one moves away from infinite sharpness, which can be modeled easily and efficiently with subdivision surfaces following Hoppe, et al. most, if not all of the advantages of the method are lost, and one must create a vastly more complicated model to enjoy the incremental enhancement in realism. Accordingly, there is a need for a way to efficiently model objects with semi-sharp features and, more generally, there is a need for a way to sculpt the limit surface defined by subdivision without complicating the initial mesh.
SUMMARY OF THE INVENTION
The present invention involves a method for modeling objects with surfaces created by sequentially combining different subdivision rules. By subdividing a mesh a finite number of times with one or more sets of “special rules” before taking the infinite subdivision limit with “standard rules” one can produce different limit surfaces from the same initial mesh.
One important application of the invention is to the modeling of objects with smooth and semi-sharp features. The present invention allows one to model objects with edges and creases of continuously variable sharpness without adding vertices or otherwise changing the underlying control point mesh. The result is achieved in the exemplary embodiment by explicitly subdividing the initial mesh using the Hoppe, et al. rules or a variation which like the Hoppe, et al. rules do not require tangent plain continuity in the region of a sharp feature. After a finite number of iterations, one switches to the traditional continuous tangent plane rules for successive iterations. On may then push the final mesh points to their smooth surface infinite subdivision limits. The number of iterations performed with the “sharp” (i.e., discontinuous tangent plane) rules determines the sharpness of the feature on the limit surface. Though the number of explicit subdivisions must be an integer, “fractional smoothness” can be achieved by interpolating the position of points between the locations determined using N and N+1 iterations with the sharp rules.
In another exemplary embodiment, the invention is used to improve the shape of Catmull-Clark limit surfaces derived from initial meshes that include triangular faces.
REFERENCES:
patent: 6222532 (2001-04-01), DeRose et al.
patent: WO 89/07301989 (1989-08-01), None
patent: WO 95/06291 (1995-03-01), None
Hoppe (Hoppe et al. (Piecewise Smooth Surface Reconstruction, Computer Graphics(SIGGRAPH>94 Proceedings). 1994. pp. 295-302).*
PCT Written Opinion dated May 10, 1999 for International Application No. PCT/US98/15703.
Lee, Yuencheng et al., “Realistic Modeling for Facial Animation”, Computer Graphics Proceedings, SIGGRAPH 1995, Annual Conference Series, 1995, pp. 55-62.
Bajaj, Chandrajit L. et al., “Adaptive Reconstruction of Surfaces and Scalar Fields from Dense Scattered Trivariate Data,” Computer Science Technical Report, pp. 1-19 (1995).
Bajaj, Chandrajit L. et al., “Automatic Reconstruction of Surfaces and Scalar Fields From 3D Scans,” Computer Graphics (SIGGRAPH '95 Conference Proceedings, pp. 109-118 (1965).
Brunet, Pere, “Including Shape Handles in Recursive Subdivision Surfaces,” Computer-Aided Geometric Design 5:1:41-50 (1988).
Chadwick, J.E. and E. Parent, “Critter Construction: Developing Characters for Computer Animation,” Proceedings of PIXIM 88, pp. 283-306 (Oct. 24-28, 1988) XP002084381.
Gudukbay, U. et al., “A Spring Force Formulation For Elastically Deformable Models,” Computers & Graphics, 21:3:335-346 (May-Jun. 1997) XP004083258.
Ip, Horace H.S. and C.S. Chan, “Dynamic Simulation of Human Hand Motion Using an Anatomical Correct Hierarchical Approach,” Computational Cybernetics And Simulation (1997 IEEE International Conference On Systems, Man and Cybernetics) vol. 2, pp. 1307-1312 (1997) XP002084380.
Hahn, James K., “Realistic Animation of Rigid Bodies,” Computer Graphics SIGGRAPH '88 Conference Proceedings) 22:4:299-308 (Aug. 1-5, 1988) XP002084382.
Hoppe, Hugues, “View-Dependent Refinement of Progressive Meshes,” Computer Graphics (SUGGRAPH 97 Conference Proceedings) pp. 189-198 (Aug. 3-8, 1997) XP002085290.
Ip, Horace H.S. and C.S. Chan, “Dynamic Simulation of Human Hand Motion Using an Anatomical Correct Hierarchical Approach,” Computational Cybernetics And Simulation (1997 IEEE International Conference On Systems, Man and Cybemetics) vol. 2 pp. 1307-1312 (1997) XP002084380.
Turner, Russell and Daniel Thalmann, “The Elastic Surface Layer Model for Animated Character Construction,” Communicating With Virtual Worlds (Proceedings of Computer Graphics International '93), pp. 399-412 (Jun. 21-25, 1993) XP002084379.
International Search Report dated Nov. 27, 1998 for International Application No. PCT/US 98/15702 (International Filing Date: Jul. 29, 1998.
International Search Report dated Dec. 8, 1998 for International Application No. PCT/US 98/15703 (International Filing Dat: Jul. 29, 1998).
International Search Report dated Nov. 4, 1998 for International Application No. PCT/US 98/15704 (International Filing Date: Jul. 29, 1998).
Hoppe, Hugues, “Progressive Meshes,” Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 99-108 (1996).
Eck, Matthias, and Hughes Hoppe, “Automatic Reconstruction of B-Spline Surfaces of Arbitrary Topological Type,” Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 325-334 (1996).
Halstead, Mark, et al. “Efficient, Fair Interpolation Using Catmull-Clark Surfaces,” Computer Graphics (SIGGRAPH 93 Conference Proceedings), pp. 35-44 (1993).
Krishnamurthy, Venkat and Marc Levoy, “Fitting Smooth Surfaces to Dense Polygon Meshes,” Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 313-324 (1996).
Hoppe, Hugues, et al. “Piecewise Smooth Surface Reconstruction,” Computer Graphics (SIGGRAPH 94 Conference Proceedings), pp. 295-302 (1994).
Doo, D. and M. Savin, “Behavior for Recursive Division Surfaces Near Extraordinary Points,” Computer Aided Design, 10:356-360 (1978).
Catmull, E., and Clark, J., “Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,” Comp
DeRose Anthony David
Kass Michael
Arent Fox Kintner Plotkin & Khan, PLLC
Pixar Animation Studios
Stevenson Philip H
Zimmerman Mark
LandOfFree
Hybrid subdivision in computer graphics does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid subdivision in computer graphics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid subdivision in computer graphics will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2974777