Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-04-11
2003-08-05
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000
Reexamination Certificate
active
06603473
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of object modeling, and, more specifically, to detail data relating to the shape of an object surface.
2. Related Art
In the area of computer aided geometric design (CAGD), an object surface is sought to be manufactured from a representation of the object surface. Because the manufactured surface is often subject to very tight tolerances, it is critical that the object representation be as accurate as possible. Unfortunately, for several reasons, current object modeling techniques, such as tensor product NURBS (non-uniform rational B-splines), are often unable to achieve the required numerical precision.
First, NURBS methods can represent surfaces of arbitrary topology only by partitioning the object representation into a collection of individual NURBS patches. Adjacent patches must then be explicitly stitched together using geometric continuity conditions. This requires careful patch layout and cumbersome cross boundary continuity management to build complex shapes. This practice is particularly cumbersome in computer animation, where it often leads to the appearance of kinks and cracks, especially when such patch complexes are animated.
A second problem with NURBS is in the context of trimming operations, that is, operations in which an object representation is cut along a prescribed border or trim curve to, for example, insert a rivet hole. To trim a NURBS patch, the specified area in the representation to be trimmed is typically not altered. Instead, the specified area bounded by the trim curve is represented in the parametric domain. This parametric representation of the bounded area is then retained during the manufacturing process to ensure that the prescribed area is left unfilled. Unfortunately, a parametric representation of a trim curve is often prohibitively difficult to achieve with precision. Consequently, topological inconsistencies such as cracks are often introduced.
Subdivision surface modeling, in which an object surface is modeled as a mesh of polygons such as triangles, provides a means for modeling objects of arbitrary topology that may include both smooth curved surfaces and sharp edges. Unlike NURBS, the technique does not require the use of separate patches or the enforcement of continuity conditions. Therefore, subdivision surface modeling has been increasingly adopted in high-end animation production and game engines and are provided as primitives in many popular modeling programs (e.g., Maya, Mirai, 3D Studio Max, Lightwave, etc.).
However, for many CAGD applications, subdivision surface modeling does not currently provide the necessary numerical exactness. Moreover, current trimming operations performed on such models frequently introduces unacceptable distortion, either because the operation does not guarantee substantially exact reproduction of the trim curve, or because the operation introduces unacceptable distortion in the area around the trim curve. The failure to reproduce the trim curve in the operation is especially problematic because it frequently introduces topological inconsistencies such as cracks during tessellation.
3. Related Applications
This application is being filed concurrently with U.S. patent application Ser. No. To Be Determined, Howrey Dkt. No. 01339.0005.00US01, entitled “METHOD OF TRIMMING A REPRESENTATION OF AN OBJECT SURFACE COMPRISING A MESH OF TESSELLATED POLYGONS AND RELATED SYSTEM,” and U.S. patent application Ser. No. To Be Determined, Howrey Dkt. No. 01339.0005. NPUS02, entitled “OBJECT SURFACE REPRESENTATION AND RELATED METHODS AND SYSTEMS,” both of which are owned in common by the assignee hereof, and both of which are hereby fully incorporated by reference herein as though set forth in full.
SUMMARY
The present invention provides a method for determining detail data relating to the shape of an object surface. In one application, the detail data may be used to augment a representation of an object surface comprising a tessellated mesh of subdivided or repeatedly subdivided polygons. The detail data provides information about the object surface which may not be captured by the polygonal mesh. By augmenting the mesh representation with this detail data, a more accurate representation of the object surface results.
In one embodiment, the detail data comprises a plurality of detail vectors which are each associated with one of the vertices of the polygonal mesh. Each polygon in the mesh may have one or more vertices, and, in one embodiment, may have three or more vertices. The detail vectors may also be associated with any of the vertices in the hierarchy of meshes produced by subdivision. A detail vector affects the shape of the surface near the limit point corresponding to the vertex. The limit surface results by subdividing the mesh representation of the object surface infinitely. The limit point of a vertex is the point on the limit surface that the vertex converges to.
In one example, the detail vector for a vertex is determined by first producing difference vectors for the vertex in question as well as vertices in the neighborhood of the vertex in question. A difference vector for a vertex is the vector formed from the difference between the vertex as mapped onto the original object surface, and the limit of the vertex. These difference vectors are then weighted using a set of prescribed weights, and the results summed to arrive at the detail vector for the vertex in question.
In a second example, a detail vector for a vertex is produced by first determining the difference vector for that vertex, and then weighting that difference vector by a prescribed weight to arrive at the detail vector for the vertex in question. Difference vectors for other vertices in the neighborhood of the vertex in question are not utilized in this example.
In yet another example, the detail vector for a vertex is produced by first determining detail vectors for vertices adjacent to the vertex in question. These detail vectors are then weighted using prescribed weights, and the results added to arrive at the detail vector for the vector in question.
In one embodiment, the prescribed weights are embodied in the form of predetermined stencils which are selected and applied based on the vertex type, the valence, and the level of subdivision involved. In one implementation, a stencil may be an interpolating stencil or a quasi-interpolating stencil. An interpolating stencil is one that provides an approximation that exactly matches the data being approximated. A quasi-interpolating stencil is one that is interpolating up to a certain polynomial degree, in this case, cubic. In one implementation example, the method selects a quasi-interpolating stencil for all vertices which are interior vertices at level j=0 in the hierarchy; interior vertices of valence six at levels j>0 in the hierarchy; boundary vertices; and corner vertices (which are a species of boundary vertices). In this implementation example, for interior vertices having valences other than six which are located at levels j>0 in the hierarchy, the method selects an interpolating stencil.
In this implementation example, for all interior vertices at level j=0, and all interior vertices at levels j>0 having a valence of six, the method applies a stencil which, in effect, weights the difference vector for the vertex in question, as well as several neighboring vertices, by prescribed weights, and sums the results to arrive at the detail vector for the vertex in question.
In this implementation example, for all interior vertices at level j>0 having a valence other than six, the method applies a stencil which, in effect, weights the difference vector for the vertex in question by a prescribed weight to arrive at the detail vector for that vertex.
For all non-corner boundary vertices in this implementation example, the method applies a stencil which, in effect, weights the difference vectors for several neighboring vertices by prescribed weights, and sums the r
Levin Adi
Litke Nathan Jacob
Schroeder Peter
California Institute of Technology
Howrey Simon Arnold & White , LLP
Sealey Lance W.
Zimmerman Mark
LandOfFree
Detail data pertaining to the shape of an object surface and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detail data pertaining to the shape of an object surface and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detail data pertaining to the shape of an object surface and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3107435