Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-12-04
2004-04-13
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000
Reexamination Certificate
active
06720962
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the art of computer graphics and more particularly to the modeling and moving of large systems of geometry such as hair and fur which must extend naturally from an arbitrary surface. Such large systems in the natural world share properties with the shape of the underlying surfaces as well as the shape defined by the systems themselves. This invention relates to computer methods that can render and model deformable systems of geometry that have stable dynamics when viewing the object that has been rendered.
BACKGROUND OF THE INVENTION
Modeling and moving extremely large systems of geometry in a stable surfaced based volume has been a central problem in computer graphics and computer animation systems. Hair, in particular, has long presented computer artists with intractable problems when trying to define, shape, and manipulate the millions of geometrical elements which comprise a usual occurrence of hair.
Problems arising from previous methods involve memory management of such large systems of geometry, efficient definition distortion required on a straight line required to create the geometry (like hair), and how to maintain proper orientation of the details of the geometry as it flexes and moves.
Coordinate systems in general are defined by three vectors which represent the pseudo x,y, and z axis respectively and scalars thereof. Most systems of derived matrices comprise only two vectors and an arbitrary “up” vector which is made perpendicular to the first two vectors by a cross product of the first two vectors. When placed in a matrix, the matrix defines a local coordinate system which may also be inverted. This means, that you can multiply a point in Cartesian space by a local matrix to perform local distortions of orientation and scale, and then return the point to Cartesian space by applying the inverse of the matrix to the point. A typical use of a local matrix is a rotation matrix, which is constructed from euler angles for the three axis, then applied to a set of points to orient an object to a local coordinate system. Another common use of a matrix is a perspective matrix. A perspective matrix contains the necessary distortion of Cartesian space to it's projection on a flat viewing plane, usually scaling points close to the plane larger, and ones further away smaller.
PRIOR ART
Hoppe, Hugues, “Progressive Meshes,” Computer Graphics (SIGGRAPH) 96 Conference Proceedings), pp. 99-108 (1996).
Eck, Matthias, and Hugues Hoppe, “Automated 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 of 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,” Computer Aided Design, 10:350-355 (1978).
Lee, Yuencheng, et al., “Realistic Modeling for Facial Animation,” Computer Graphics (SIGGRAPH 95 Conference Proceedings), pp. 55-62 (1995).
Certain, Andrew, et al., “Interactive Multiresolution Surface Viewing,” Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 91-98 (1996).
Nasri, A. H., “Boundary-Corner Control in Recursive-Subdivision Surfaces,” Computer Aided Design, vol. 2, pp. 405-410 (1990).
Nasri, Ahmad H., “Surface Interpolation of Irregular Networks with Normal Conditions,” Computer Aided Geometric Design, 8:89-96 (1991).
Nasri, Ahman H., “Polyhedral Subdivision Methods for Free-Form Surfaces,” ACM Transactions on Graphics, 6:29-73 (1987).
Ball, A. A. and D. J. T. Storry, “A Matrix Approach to the Analysis of Recursively Generated B-Spline Surfaces, ” Computer-Aided Design, 18:437-442 (1986).
Ball, A. A. and D. J. T. Storry, “An Investigation of Curvature Variations Over Recursively Generated B-Spline Surfaces,” ACM Transactions on Graphics, 9:424-437 (1990).
Ball, A. A. and D. J. T. Storry, “Conditions for Tangent Plane Continuity Over Recursively Generated B-Spline Surfaces,” ACM Transactions on Graphics, 7:83-102 (1988).
Reif, U., A Unified Approach to Subdivision Algorithms, Department of Mathematics, University of Stuttgart.
Warren, Joe, Subdivision Methods for Geometric Design (1994).
Dyn, Nira and David Levin, “Analysis of Asymptotically Equivalent Binary Subdivision Schemes,” School of Mathematical Sciences, Tel-Aviv University.
Derfel, G., N. Dyn, and D. Levin, “Generalized Refinement Equations and Subdivision Processes,” Ben-Gurion University and Tel-Aviv University.
Dyn, N., S. Hed, and D. Levin, Subdivision Schemes for Surface Interpolation, Department of Mathematics, Tel Aviv University (1993).
Dyn, N. and D. Levin, “Interpolating Subdivision Schemes for the Generation of Curves and Surfaces,” Multivariate Interpolation and Approximation, W. Haussmann and K.
Jetter, eds. Birkhauser, Verlag, Basel, pp. 91-106 (1990).
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).
Gudukbay, U. et al., “A Spring Force Formulation For Elastically Deformable Models,” Computer & Graphics, 21:3:335-346 (May-June 1991) XP004083258.
Gudukbay, U. and Bulent Ozguc, “Animation of Deformable Models,” Computer-Aided Design, 26:12:868-875 (Dec. 1, 1994) XP000500985.
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 (SIGGRAPH 97 Conference Proceedings) pp. 189-198 (Aug. 3-8, 1997) XP002085290.
Sarraga et al., “Free-Form Surfaces in GMSolid: Goals and Issues,” Solid Modeling by Computers From Theory to Applications, M. S. Pickett and J. W. Boyse, editors, Plenum Press, 1984, pp. 187-209.
Sederberg et al.,
“Free
-
Form Deformation
of Solid Geometric Models,” SIGGRAPH '86, ACM, vol. 20, No. 4, 1986, pp. 151-160.
The U.S. Pat. No. 6,037,949 and the U.S. Pat. No. 5,796,400 which are part of the prior art show use of texture mapping and other uses of scaler fields on subdivision surfaces. The methods, while different in the respect that they don't directly relate to dynamic computer generated hair, are relevant in the use of scalar fields and parameters which will be interpolated over a 2 dimensional surface in a 3D world space. Therefore they can be very instructive as to what is considered as skill in the art in terms of defining and computing the value of scaler fields over a set of points on a surface to model or animate. These patents mention and describe these techniques in computer graphics and computer animation as well as appropriate algorithms used by animators by people skilled in the art on a regular basis.
Since this patent application improves on these patents by a method that uses mesh and coordinates, it is similar to the prior art, but different in many respects based on using coordinates that have underconnectivity and using guide columns having the vector coordinates located thereon and deforming the columns and rendering as will be apparent from the description in this application.
SUMMARY OF THE INVENTION
The present invention, by providing a method for defining stable and arbitrary coordinate systems comprised of a system of matrices that shares similarity with an underlying surface, allows for the pragmatic creation of temporary geometry which may be created on demand, deleted from memory, and repeated on demand with very few actual parameters, thus minimizing mem
Cao Huedung X.
Joseph Alter Inc.
Zimmerman Mark
LandOfFree
Hair generation and other natural phenomena with 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 Hair generation and other natural phenomena with surface..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hair generation and other natural phenomena with surface... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219526