Image analysis – Applications – Surface texture or roughness measuring
Reexamination Certificate
1998-07-15
2002-05-14
Boudreau, Leo (Department: 2721)
Image analysis
Applications
Surface texture or roughness measuring
C382S100000, C345S582000
Reexamination Certificate
active
06389154
ABSTRACT:
BACKGROUND OF THE INVENTION
Computers offer increasingly sophisticated methods of modeling surfaces. Applications of these surface models range from producing realistic display images to providing simulations with accurate surface information.
Referring to
FIG. 1
, a free-form surface
10
appears in three-dimensional space (e.g., displayed on a computer monitor). Referring to
FIG. 2
, a surface
10
in a computer modeling program can be thought of as being covered by a connected set of surface patches
12
,
14
such as bicubic surface spline patches. One common type of bicubic surface spline is a Bezier-Spline (B-Spline). Referring to
FIG. 3
, control vertices
16
offer computer surface modelers an intuitive method of controlling the contour of a selected patch
12
. Moving a control vertex
16
causes a corresponding change in the contour of patch
12
. For example, moving control vertex
16
a
could significantly alter the coordinates' of the upper right portion of patch
12
. To a lesser extent, the movement of control vertex
16
a
may also effect the lower left portion of patch
12
.
Referring again to
FIG. 2
, each patch of the surface
10
has a corresponding set of control vertices. Adjoining patches (e.g., patch
12
and patch
14
) share control vertices. Thus, moving a single control vertex affects several neighboring surface patches. However, this movement has no effect on patches not sharing the moved control vertex. Thus, control vertices
16
provide a convenient tool for adjusting contours of a local area of neighboring patches.
Referring to
FIG. 4
, although a graphical user interface (GUI) that allows a user to visually move control vertices (e.g., by selecting and dragging a control vertex) may shield a modeler from the mathematics involved, the coordinates of the control vertices
16
act as the coefficients of a set of functions
22
that can determine the contour of a B-Spline patch
12
in three-dimensions. Sixteen B-Spline basis functions
22
, labeled b
1
-b
16
in
FIG. 4
, translate a set of parameters u and v
20
that describe a surface location (e.g., the u and v values that describe coordinates of surface location
20
within two-dimensional plane
18
) into the coordinates of the location in three-dimensions
24
. The process shown in
FIG. 4
is known as parameterization. A wide variety of techniques exist for working with parameterized surfaces.
Referring to
FIG. 5
, subdividing control vertices (i.e., determining a new set of control vertices based on a previous set of control vertices) enables a modeler to gain greater control of over a finer set of patches. Subdivision rules guide determination of new control vertices from existing control vertices. Many different subdivision rules exist. For example, Catmull-Clark subdivision rules produce new control vertices
28
from a set of original control vertices
16
that control a B-Spline patch
12
. Catmull-Clark surfaces have many properties which make them attractive as a free-form surface design tool. For example, regardless of the initial topology of a set of control vertices, after a single application of Catmull-Clark subdivision rules, the faces formed by the new control vertices form quadrilaterals. Further, a wide variety of algorithms have been written for these surfaces, for example, fairing algorithms that reduce unwanted surface undulation.
To understand subdivision rules, it is helpful to imagine each control vertex
16
as a corner of a polygon. Catmull-Clark subdivision rules insert new control vertices
28
in the middle of each polygon face formed by the original control vertices
16
and in the middle of each polygon edge other than the outermost edge of the set of polygons. The new set of control vertices
28
also includes original control vertices
16
other than the outermost original control vertices
16
. Application of subdivision rules to original control vertices
16
does not, without movement of a new control vertex
28
, alter the contour of patch
12
. Subsets of the new control vertices
28
, however, offer control over sub-patches, essentially making four smaller new patches out of the original surface patch
12
. For example, new control vertices
28
a
-
28
p
control sub-patch
26
of original patch
12
. However, B-Spline basis functions (and the basis functions for other surface geometries) can only evaluate a surface when the arrangement of control vertices conform to a rigid set of constraints.
Referring to
FIG. 6A
, a set of control vertices
30
, also known as a “mesh”, defines a smooth surface. Each control vertex
30
has a valence corresponding to the number of edges that meet at the vertex. For example, control vertex
32
a
which appears at the meeting point of three edges has a valence of three. In the case of a free-form surface divided into quadrilateral patches, a vertex having a valence not equal to four is called an extraordinary vertex.
FIG. 6A
includes three extraordinary vertices. Vertices
32
a
and
32
c
have a valence of three. Vertex
32
b
has a valence of five.
A surface patch controlled by a regular set of control vertices (i.e., a set of control vertices having no extraordinary control vertices) can be evaluated using the basis functions shown in FIG.
4
.
FIGS. 6A-6C
shade regular faces formed by sets of regular control vertices. Referring to
FIG. 6B
, application of Catmull-Clark subdivision rules to the control vertices
30
of
FIG. 6A
produces a new set of the control vertices
30
′. In turn,
FIG. 6C
illustrates application of the subdivision rules to the control points
30
′ of
FIG. 6B
which produce yet another set of control points
30
″. As shown in
FIGS. 6A-6C
, the portion of the surface comprised of shaded regular patches grows with each subdivision. Patches adjacent to the extraordinary vertices
32
a
-
32
c
, while shrinking with each application of the subdivision rules, nevertheless remain irregular and, hence, cannot be evaluated with the basis functions developed for regular patches (FIG.
4
). Further, each subdivision consumes significant computing resources as software tracks increasing numbers of control vertices.
SUMMARY OF THE INVENTION
In general, in one aspect, a computer-based method for determining a property of a location on a computer surface model where the location is described by a set of parameters and the surface model is described by a set of control vertices having a corresponding set of subdivision rules, and the control vertices admit a parameterization of regular sets of control vertices, includes receiving input specifying coordinates of control vertices that describe the surface model, projecting the specified coordinates of the control vertices into an eigenspace derived from a matrix representation of the subdivision rules to produce a set of projected control vertices, determining which of a hierarchically nested set of regular tiles of the surface model contains the location, and evaluating the location as a function of a valence of one of the control vertices, the determined nested tile, and the set of projected control vertices. The evaluated location is stored in a computer memory.
Embodiments of the computer-based method may include the following. One of the control vertices may be a control vertex having an extraordinary valence. The subdivision rules may include Catmull-Clark and/or Loop subdivision rules. The evaluating may determine coordinates of the location. The evaluating may determine a derivative of any order of the surface model at the location. The computer-based method may also include processing the evaluation to determine a display characteristic such as shading or texture mapping. The evaluating may be done according substantially to:
s
(
u
,
v
)
=
∑
i
=
1
K
ϕ
i
(
u
,
v
)
p
i
.
as described below. The evaluating may be done according substantially to:
s
(
v, w
)=
Ĉ
0
T
&PHgr;(
v, w
).
as described below. The computer-based method may produce a graphics display based on the evalu
Boudreau Leo
Choobin Barry
Silicon Graphics Inc.
Staas & Halsey , LLP
LandOfFree
Exact evaluation of subdivision surfaces generalizing box... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Exact evaluation of subdivision surfaces generalizing box..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact evaluation of subdivision surfaces generalizing box... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2832796