Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-11-19
2001-08-07
Cuchlinski, Jr., William A. (Department: 3661)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06271856
ABSTRACT:
BACKGROUND
Recent developments in the field of computer aided modeling enable designers to manipulate representations of physical objects that have been scanned into a computer using lasers. The representation is often a two-dimensional (2-D) surface (i.e., a 2-dimensional manifold) embedded in three-dimensional (3-D) Euclidean space. The surface is constructed by collecting laser range information from various viewing angles and combining it to reconstruct the surface of the object. Initially, this surface is represented in unparameterized form. For example, a common unparameterized surface representation is a dense, seamless polygon mesh, i.e., a collection of polygons joined at their edges. This polygon mesh model of the physical object often then forms the basis for subsequent manipulation and animation. A typical model generated from 75 scans of a physical object using a laser range scanner might contain on the order of 350,000 polygons.
Dense polygon meshes are an adequate representation for some applications such as stereolithographic manufacturing or computer renderings. However, for a number of other application domains, smooth, parameterized surface representations are required in order to permit useful editing and manipulation of the surface. By smooth or parameterized surfaces we mean surfaces whose mathematical representation has a higher order mathematical property such as the existence of a global analytical derivative. In contrast to smooth surface representations, polygonal meshes are just a set of connected planar facets; they do not posses an analytical derivative.
Smooth surface representations offer useful advantages over an irregular polygonal mesh representation. Some of these advantages are:
Smooth appearance: Several applications such as consumer product design require for aesthetic reasons that 3-D surface models possess a smooth appearance. Polygonal meshes cannot be used in these applications because they may appear faceted (unless the polygons are made extremely small, which increases the expense of processing and storing the model).
Compact representation: A smooth surface representation can usually represent complex surface shapes more efficiently than polygonal meshes.
Flexible control: Smooth surface representations usually offer an easier interface to design, control and modify surface geometry and texture.
Mathematical differentiability: Several applications use computational procedures that require the surface to be everywhere differentiable or curvature continuous (e.g., finite element analysis). For such applications, polygonal meshes cannot be used because they are merely piecewise linear surfaces.
Manufacturability: Some manufacturing procedures such as CNC milling require a smooth surface representation to create high quality results.
Hierarchical modeling: Creating manipulable hierarchies from smooth surfaces is a significantly simpler task than doing the same with dense, irregular, polygonal meshes.
Examples of smooth surfaces include parametric representations such as NURBS, B-spline and Bezier surfaces, implicit representations such as spheres and cylinders, algebraic representations based on explicit equations, and so on. To satisfy users that prefer or require smooth surface representations, techniques are needed for creating and fitting smooth surfaces to dense polygonal meshes.
Unfortunately, known techniques for automatically creating parameterizations often result in undesirable parameterizations. For example, it is desirable that a parameterization appropriately follow the surface contours of the mesh. To construct such parameterizations, users are currently required to manually edit the automatically created parameterization, or to specify from scratch an entire collection of isoparametric curves on the surface of the polygonal mesh. In either case, the user is faced with a labor-intensive task.
SUMMARY
In view of the above, it is a primary object of the present invention to provide a method for interactively creating and modifying a parameterization of a surface independent of surface fitting. In particular, it is an object of the invention to provide such a method that allows the user to intuitively and quickly construct parameterizations that are suited to the surface contours of an underlying surface.
In one aspect of the invention, a computer-implemented method is provided for creating a parameterization of an input surface. The input surface could either be previously unparameterized or it could be parameterized in a manner that is not suitable for its intended use. Typically, the input surface is an unparameterized polygon mesh representation of a 2-dimensional manifold embedded in a 3-dimensional ambient space. In any case, the surface must at least permit a positional adjacency structure to be defined locally at each point where the parameterization is to take place. The method comprises specifying a plurality of boundary curves on the surface, where the boundary curves define a patch of the surface. The boundary curves may be specified automatically from the input surface, or may be specified from user-interactive input. The method also includes specifying a feature curve on the surface. The feature curve may be specified automatically from calculated properties of the input surface (e.g., its shape) or may be specified from user-interactive input, or both. The method further includes automatically generating a parameterization of the patch. The parameterization is selected to minimize a discretized higher order energy functional defined on the surface subject to the constraint that iso-curves of the parameterization are attracted to follow the feature curve. In a preferred embodiment of the invention, the iso-curves are interpolated between the boundary curves and define an array of sub-patches, and the sub-patches are subjected to predetermined criteria that propagate across iso-curves, e.g., arc length uniformity, aspect ratio uniformity, and parametric fairness criteria.
Some uses of our parameterization (or reparameterization) technique are listed below.
SURFACE FITTING WITH CONTROLLED PARAMETERIZATION
An important application of this invention is creating smooth, controlled parameterizations of scanned data for purposes of fitting higher order surfaces to scanned data. The scanning technique used to acquire the data could be based on any of a number of paradigms that are used to generate polygonal meshes, e.g., lasers, white light, and photogrammetry. Some benefits of fitting smooth surfaces to scanned data are enumerated in the previous section. In contrast with previous approaches to surface fitting, the present invention advantageously separates the surface fitting process into two distinct and independently controlled steps:
1. Controlled parameterization
2. Controlled surface approximation based on the parameterization
Previous techniques combine both these steps into one step that consists of creating a fixed “ideal” parameterization and a fixed “ideal” surface approximation based on the parameterization. As a result the user does not have enough control over each individual step in the process. In contrast, our methods allow for fine control over both the parameterization step as well as the approximation step of the surface fitting process. Since the two steps are separately controlled, the user can generate several possible parameterizations for the same approximated shape. In other words, our surface fitting strategy solves separately for patch parameterization and for patch geometry. In this strategy the geometry is always fixed to be that of the polygonal mesh. However, the parameterization of the patch can be arbitrary. The fidelity of the spring mesh to the original polygonal geometry is maintained regardless of the particular parameterization of the data. The independently controllable design of a surface's parameterization is of critical importance to most modelers because it influences several important properties of the surface. For example, surface parameterizations determine the flow
Cuchlinski Jr. William A.
Lumen Intellectual Property Services Inc.
Nguyen Thu
Paraform, Inc.
LandOfFree
Creating and modifying parameterizations of 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 Creating and modifying parameterizations of surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Creating and modifying parameterizations of surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2545866