Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-07-24
2004-10-19
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06806874
ABSTRACT:
TECHNICAL FIELD
These teachings relate generally to computer-implemented methods and apparatus for representing and modeling surfaces, including techniques that use a Catmull-Clark surface representation.
BACKGROUND
Interactive editing is an important element of model creation for a variety of applications, ranging from mechanical design to movie character creation. Modeling typically begins with an existing object on which the user performs a sequence of editing operations that lead to the desired shape. Of particular interest to these teachings are small-scale features such as engravings and embossed details that are encountered on many real-life objects.
Traditionally, geometric modeling has relied on non-uniform rational B-splines (NURBS) for surface design. However, NURBS have well-known limitations, such as an inability to address arbitrary topology, tedious cross-boundary continuity management, and a difficulty in representing different resolution levels. In addition, editing operations such as those considered herein typically require features to be aligned with iso-parameter lines or patch boundaries or other complex manipulations in parameter space.
While techniques such as free-form deformations, wires, and procedural modeling offer alternative ways to edit three-dimensional objects, typically they do not present a unified representation that includes both the original surface and the edits. Thus, in many cases, the resulting representation is not the same as the original, but an extension of it. The main drawback of this approach is that algorithms that have been developed for the original representation are not directly applicable to the result and special cases may have to be considered.
The past few years have seen considerable advances in subdivision theory, and many common NURBS operations have been translated into the subdivision setting. Subdivision theory, parametric evaluation, and applications such as interactive editing, trimming, Boolean operations, and geometry compression have contributed to the increasing popularity of multiresolution subdivision surfaces. To date, they have been used in commercial modelers (e.g., Alias/Wavefront's Maya, Pixar's Renderman, Nichimen's Mirai, and Micropace's Lightwave 3D), and are currently being employed in game engines and hardware implementations.
Subdivision algorithms are attractive because of their conceptual simplicity and efficiency with which they can generate smooth surfaces starting from arbitrary meshes. Multiresolution subdivision surfaces offer additional flexibility by allowing modeling of detail at different resolution levels and ensuring that fine-scale edits blend naturally with coarse shape deformations.
Subdivision surfaces permit an efficient representation of free-form surfaces of arbitrary topology. A subdivision surface is defined over an initial control mesh and a subdivision scheme is used to recursively refine the control mesh by recomputing vertex positions and inserting new vertices according to certain rules (masks). Recursive subdivision produces a hierarchy of meshes that converge to a smooth limit surface.
Most objects of interest to geometric design, however, are only piecewise-smooth, and typically exhibit sharp creases and corners. To model these sharp creases and corners using subdivision, special rules are needed to avoid the smoothing of the desired sharp details.
Reference in this regard can be made to
FIGS. 1A
,
1
B and
1
C, wherein surface editing processes are depicted. In
FIG. 1A
features are added to an initial surface. It should be apparent that smooth and sharp features are fundamentally different: smooth features (
FIG. 1B
) add bumps to the surface, while sharp features create tangent plane discontinuities (FIG.
1
C). Previous work in this area has focused on defining the special rules required to define these surface features.
Hoppe et al. introduced rules to create sharp features on subdivision surfaces. DeRose et al. extended the approach of Hoppe et al. to achieve creases of controllable sharpness by using subdivision rules parameterized by a sharpness factor. Reference can also be made to the curve interpolation work of Nasri.
In all of these techniques, there is the common requirement that features need to be aligned with the edges of the underlying control mesh. Therefore, the control mesh is designed with a particular feature in mind. However, a designer might want to first model an initial shape and then apply small-scale features in later stages of the design. The currently available modeling techniques do not adequately support this type of a modeling approach, and thus also do not allow features to be placed at arbitrary locations on the surface.
Multiresolution subdivision surfaces are a natural extension of subdivision surfaces that accommodate editing of details at different scales, allowing general shape deformations as well as the creation of minute features. Multiresolution, however, does not solve the problem of sharp features, as these types of features can only be placed along edges at discrete locations in the mesh hierarchy.
Reference can be made to Khodakovsky and Schroder, who describe a method for interactive creation of feature curves at arbitrary locations on a surface. To create a feature along a curve, a perturbation according to a given profile is applied in the neighborhood of the curve, while maintaining smooth boundary conditions. There are no restrictions on the position of the curve with respect to the underlying surface, however, the representation used is no longer a pure multiresolution surface. In order to create a sharp feature with this technique, it is necessary to enforce the feature profile at each level of the multiresolution hierarchy. Both the surface and the feature curve are required to represent the resulting surface. Thus, one cannot directly apply subdivision surface operations (i.e., evaluation).
Trimming is an important design operation, however, it has been traditionally difficult to perform trimming for parametric surfaces. One conventional approach is described by Litke et al., where quasi-interpolation is used to approximate a trimmed surface with a combined subdivision surface.
It should thus be apparent that the teachings of the prior art do not adequately address the problem of defining certain features, such as surface creases at arbitrary surface locations, in an efficient and computationally efficient manner.
SUMMARY
The foregoing and other problems are overcome by methods and apparatus in accordance with embodiments of these teachings.
These teachings address the problems of feature placement and feature creation by providing a set of tools that allow fine-scale editing and trimming operations to be applied at any desired location on a surface. Multiresolution subdivision surfaces are preferably employed as the model representation, and this representation is preserved after editing, thereby providing flexibility to integrate this technique with other algorithms developed for multiresolution subdivision surfaces.
In the preferred implementation a subdivision scheme for quadrilateral meshes is used. However, these teachings can also be practiced using algorithms developed for triangular meshes.
An aspect of these teachings is an algorithm to produce sharp features at arbitrary locations on a piecewise-smooth multiresolution surface, without requiring that one remesh the control mesh. The sharp features can be created interactively, along curves drawn by the user on the target surface.
A further aspect of these teachings is the provision of an extended set of rules for the Catmull-Clark subdivision scheme that allow the creation of creases and boundaries along diagonals of quadrilateral mesh faces.
Another aspect of these teachings is the provision of a unified solution to offsetting and trimming operations. Using the presently preferred embodiment a sharp crease having a user-defined profile may be applied along a given curve. Alternatively, the portion of the surface delimited by
Bernardini Fausto
Biermann Henning
Martin Ioana
Zorin Denis
International Business Machines - Corporation
McCartney Linzy
Ohlandt Greeley Ruggiero & Perle L.L.P.
Percello Louis J.
Zimmerman Mark
LandOfFree
Method and apparatus for providing sharp features on... 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 apparatus for providing sharp features on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing sharp features on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3305215