Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-12-10
2001-07-03
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S440000
Reexamination Certificate
active
06256038
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.
Known techniques for creating and fitting smooth surfaces to polygon meshes, however, consist of a single-step parameterized fit that creates a fixed “ideal” parameterization with a fixed “ideal” surface approximation having that parameterization. Because the parameterization and fit are created simultaneously in one step, the user has limited control over the properties of the parameterization and the properties of the fit. Since having flexibility and control over surface parameterization and fit is crucial for most applications, improved and more flexible techniques for fitting smooth surfaces to polygon meshes are needed.
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 smooth parameterization of an input surface and fitting the parameterization to the 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 dividing the input surface into patches. Typically this involves 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 further includes automatically generating a parameterization of the patch. The parameterization can be represented as a mapping M into
3
from a parameter space region I in
2
such that the image surface M(I) substantially coincides with the surface patch. The parameterization is selected to minimize a discretized higher order energy functional defined on the surface. In a preferred embodiment of the invention, the iso-curves of the parameterization 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. In addition, the parameterization is preferably performed such that the discretized higher order energy functional is minimized subject to the constraint that iso-curves of the parameterization are attracted to follow a user-defined feature curve on the surface.
The method further includes the step of fitting to the patch a smooth surface derived from the generated parameterization. The smooth surface may be represented as a mapping M′ into
3
from the parameter space region I in
2
such that the image surface M′(I) approximately fits the surface patch. The smooth surface has a parameterization corresponding to the generated parameterization, i.e., the parameterization of M′ substantially coincides with the parameterization of M. Significantly, the processes of generating the parameterizations and fitting smooth surfaces to the surface are independently controlled, thereby providing the user with a high degree of flexibility. In particular, the independent control of fitting and parameterization provides the user with a high degree of flexibility and control in the process. An especially advantageous technique in the preferred embodiment is the provision for both global and local control of the fidelity of the smooth surface fit to the underlying surface patch. Various other important advantages of the invention will become apparent below in the course of the detailed description of exemplary embodiments of the invention.
Some uses of our hybrid parameterization and fitting technique are as follows.
S
URFACE FITTING
T
O
S
CANNED
D
ATA WITH
I
NDEPENDENT CONTROL OF
P
ARAMETERIZATION
A
ND
F
ITTING
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 photogr
Lumens Intellectual Property Services, Inc.
The Board of Trustees of the Leland Stanford Junior University
Vo Cliff N.
LandOfFree
Parameterized surface fitting technique having independent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parameterized surface fitting technique having independent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized surface fitting technique having independent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2545975