Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1998-12-23
2003-04-22
Frejd, Russell (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C700S030000, C700S031000, C345S426000, C345S440000
Reexamination Certificate
active
06553337
ABSTRACT:
BACKGROUND
This invention relates to subdivision surfaces used for computer modeling.
Many computer applications generate or model surfaces and objects. Computer aided design (CAD) systems, computer animation tools, and computer graphics applications are often used to replicate real-world objects, or to generate novel objects. Many objects are not susceptible to exact mathematical description, and are often modeled interactively by a user employing artistic instead of scientific criteria. Computer systems require satisfactory methods of representing these objects and their surfaces. Since computers have finite storage capacity, an object cannot be modeled with an infinite number of coordinate points. Instead, various methods approximate object surfaces with segments such as planes, lines, and other object “primitives” that are easier to describe mathematically.
One method uses a polygon mesh, composed of a set of connected polygonally bounded faces. Rectilinear objects, such as boxes, can be easily modeled with polygon meshes. Representing objects with curved surfaces using a polygon mesh requires approximating a curved surface by a number of smaller faces. Error between the approximated representation and the real object can be made arbitrarily small by using more polygons. Using more polygons requires greater computer memory storage and computation capacity.
Another modeling method uses sets of parametric polynomial surface patches to represent a curved object. By using inherently curved surface segments, the method enables a computer modeler to represent arbitrary curved surfaces very accurately. Typically, an object is broken down into a set of connected surface patches, each patch is modeled with a parametric polynomial surface, and the surfaces are connected together to yield the final object representation. The algorithms for employing parametric polynomial surfaces are more complex than those for polygons, but fewer polynomial surface patches are typically required to approximate a curved surface to a given accuracy then with polygon meshes.
One method of improving the accuracy of a polygonal mesh approximation is to iteratively subdivide the faces of the initial mesh into smaller polygons or surface patches according to a set of rules. The initial mesh serves as a rough approximation of the real object and each successive iteration of subdivision serves to refine the approximation of the model to the real object. The surface resulting from an infinite subdivision of a mesh, is known as a subdivision surface.
A polygonal mesh, and corresponding rules of subdivision can be used for more than just modeling the shape of an object. The resulting subdivision surface can be used as the framework on which the surface of the object is smoothly painted, or to which textures of the object's surfaces are assigned. Furthermore, subdivision surfaces may be used as the basis for drawing curves on a surface, either entirely within one polygon of the mesh or across several polygons. When using subdivision surfaces as a framework with which to draw, paint, shape or otherwise describe a surface it is often desirable to have smooth transitions of parameter values when moving from one position on a subdivision surface to another.
SUMMARY
In general, in a first aspect, the invention features a method for parameterizing a subdivision mesh in a computer system, the subdivision mesh comprising at least two faces, at least two faces sharing an edge, the method including assigning a unique index to each of the at least two faces, assigning, for each of the at least two faces, a first (u) and a second (v) parameter, and at a vertex shared by two faces sharing an edge, setting a first bound for each of the u and v parameters for each of the two faces, and for each of the same two faces, at a respective vertex not shared by the two faces, setting a second bound for each of the u and v parameters.
Embodiments of the invention may include one or more of the following features. The first bound can be the same for the u and v parameters for each of the two faces, and the second bound can be the same for the u and v parameters for each of the two faces. The first bound can be a minimum bound and the second bound can be a maximum bound for each of the parameters u and v. The first bound can be a maximum bound and the second bound can be a minimum bound for each of the parameters u and v. The first bound can be 0 and the second bound can be 1. Or, the first bound can be 1 and the second bound can be 0. Each face can be a quad. Each non-shared vertex can be diagonal from and opposite of the respective shared vertex for each face. For substantially all faces of the subdivision mesh, the method can further include assigning a unique index for substantially all of the faces, assigning, for substantially all of the faces, a first (u) and a second (v) parameter, and for each pair of faces sharing an edge, at a vertex shared by two faces, setting a first bound for each of the u and v parameters for each of the two faces, and for each of the same two faces, at a respective vertex not shared by the two faces, setting a second bound for each of the u and v parameters. The method can further include determining whether a point lies on a boundary between two or more coupled faces, and assigning, to the shared point, the u and v parameters and the index from the coupled face which has the lowest or the highest index.
A point on a local face can be parameterized by initially parameterizing a point on a local face using a first adjacent parameter value and a second adjacent parameter value determined from the u and v parameters of an adjacent face, and determining a local parameterization of the point by assigning to the point the index of the local face, and swapping the first adjacent parameter value to become the second local parameter value, and swapping the second adjacent parameter value to become the first local parameter value. If the first local parameter value is greater than the maximum bound of the second parameter of the adjacent face, then the first local parameter value can be subtracted from twice the maximum bound of the second parameter of the adjacent face, and the result can be assigned as the new first local parameter value. If the first local parameter value is less than the minimum bound of the second parameter of the adjacent face, then the first local parameter value can be subtracted from the minimum bound of the second parameter of the adjacent face, and the result can be assigned as the new first local parameter value. If the second local parameter value is greater than the maximum bound of the first parameter of the adjacent face, then the second local parameter value can be subtracted from twice the maximum bound of the first parameter of the adjacent face, and the result can be assigned as the new second local parameter value. And if the second local parameter value is less than the minimum bound of the first parameter of the adjacent face, then the second local parameter value can be subtracted from the minimum value of the first parameter of the adjacent face, and the result can be assigned as the new second local parameter value.
In general, in another aspect, the invention features a storage device tangibly storing a control program, the control program, when coupled to a control device, operating the control device to perform the function of parameterizing a subdivision mesh, the subdivision mesh comprising at least two faces, at least two faces sharing an edge, by assigning a unique index for each of the at least two faces, assigning, for each of the at least two faces, a first (u) and a second (v) parameter, and at a vertex shared by two faces sharing an edge, setting a first bound for each of the u and v parameters for each of the two faces, and for each of the same two faces, at a respective vertex not shared by the two faces, setting a second bound for each of the u and v parameters.
The advantages of the invention may include one or more of the following. Subdivision surf
Frejd Russell
Silicon Graphics Inc.
Staas & Halsey , LLP
LandOfFree
Parameterization of subdivision surfaces does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parameterization of subdivision surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterization of subdivision surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3060952