Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-01-10
2004-07-06
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06760022
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer modeling of geometric shapes and, in particular, to the modeling object surfaces using simple soft creases for subdivision surfaces.
BACKGROUND OF THE INVENTION
In the world of 3 dimensional computer graphics, simple elements such as boxes and spheres are used to construct complex figures. For example, an arm may be initially depicted by joining a couple of boxes together. A mesh is applied to this initial representation of an arm. The mesh subdivides the initial representation of the arm with intersecting lines. Then subdivision algorithms are used to refine the mesh to get a smoother appearing arm.
Subdivision is an algorithmic technique that is used to generate smooth surfaces as a sequence of successively refined polyhedral meshes. Its origin dates back to 1978 when Catmull and Clark first proposed to generalize spline-patch methods to meshes of arbitrary topology. The algorithms they developed are often referred to as Catmull-Clark subdivision rules. These rules are exceptionally simple and work for arbitrary control meshes to produce smooth surfaces. Subdivision-based representations of complex geometry can be manipulated and rendered very efficiently, which makes subdivision a highly suitable tool for interactive animation and modeling systems.
The Catmull-Clark subdivision rules can be expressed as “vertex masks” by which the vertices at a one level (M+1) are constructed from vertices at the previous level (M). The following are the formulas for Catmull-Clark:
Standard Catmull-Clark
In normal Catmull-Clark, the subdivision masks are as follows:
A new level M+1 vertex is created in the center of each face, where the position of the new vertex is determined by the formula:
P
(
F
)=Sum(
F.v
j
)/
F
deg 1.
where P(F) is the position of the new vertex in the center of face F;
Sum(F.v
j
) is the sum of the positions of all vertices that define the face F; and
F deg is the degree of face F.
A new level M+1 vertex is also created in the center of each edge. The position of each new mid-edge vertex is determined by the formula:
P
(
E
)=(
E.v
0
+E.v
1
+P
(
E.f
0
)+
P
(
E.f
1
))/4 2(a).
where P(E) is the position of the new vertex in the middle of edge E;
E.v
0
and E.v
1
are the positions of the two endpoints of edge E;
and P(E.f
0
) and P(E.f
1
) are the positions of the face centers (as created by equation 1) for each of the two faces which use edge E.
Finally, the position of each level-M vertex is modified by the position of its neighbors to obtain the level M+1 version of the same vertex. For a vertex with valence n (e.g., n faces and n edges), this formula is given by
P
(
V
)=((
n−
2)/
n
)*
V
+Sum(
V.E
j.
ov
)/
n
2
+Sum(
P
(
V.F
j
))/
n
2
3(a).
where P(V) is the new position of vertex V;
V.E
j
.ov represents the vertex at the other end of edge V.E
j
from V (for each edge which uses vertex V);
and P(V.F
j
) represents the position of the face center (as created by equation 1) for each of the faces which use vertex V.
Equation 3(a) is referred to herein as the “zero crease vertex rule”.
The above completely describes the position of the vertices for the next level. To describe the faces and edges for the next level, we merely note that every face at level M is divided up into a bunch of 4-sided faces at level M+1, as follows: a new face is created in every “corner” of the level-M face using a face point, an edge point, a vertex point, and another edge point. This is illustrated in FIG.
5
and FIG.
6
.
FIG. 5
shows one face of a level-M mesh.
FIG. 6
shows a level M+1 mesh where the one face of the level-M mesh is divided into 4 faces. Each face at level M+1 uses one of the original vertices, plus the edge midpoint on each side, and the face center point. Level M+1 edges are just those resulting from this arrangement of faces—there are new edges connecting edge points with face points as well as dividing the level M edges in two, thus connecting edge points to vertex points.
The subdivided mesh that results from several iterations of Catmull-Clark formulas is very smooth. For example,
FIG. 1
illustrates a cube, and
FIG. 2
depicts a smooth, spherical shape produced by iteratively applying the Catmull-Clark formulas to all surfaces of the cube in FIG.
1
. Unfortunately, smooth surfaces are insufficient in addressing all of the needs of computer graphics. For example, a finger is rounded everywhere except the fingernail. Creases are used to delineate the fingernail. A well established “hard crease” variation on the subdivision rules allows the subdivision result to retain such creases.
Hard Creases
A hard crease may be applied to edges in the original (level-0) mesh to create a discontinuity in the smoothness of a surface. For example,
FIG. 3
depicts a shape produced by assigning hard creases to each of the four edges on the top of a box, and then applying the modified subdivision rules as described below.
The path that defines the edges associated with a hard crease is a border between where the smoothness of the various surfaces affect each other. The flat surface top of the shape in
FIG. 3
is achieved because the surface top only depends on the four points on the top of the box. The four points at the top of the box do not influence the rest of the points of the box because the hard crease defines the limit of what affects the top surface.
A widely accepted standard for “hard creases” holds that the edges forming the crease should behave like a cubic spline, ignoring the contributions of geometry on either side. The following formulas are standard modifications made to the Catmull-Clark formulas to achieve hard creases:
The formula for determining the position of the vertex at the center of a face is unchanged.
Edge vertices for hard-crease edges discard the face contributions and become simple midpoints:
P
(
E
)=(
E.v
0
+E.v
1
)/2 2(b).
For vertices with 2 hard-creased edges on edges V.E
c1
and V.E
c2
, contributions are included only from those vertices and their neighbors along the crease:
P
(
V
)=3 *
V/
4+(
V.E
c1
.ov+V.E
c2
.ov
)/8 3(b).
where V.E
c1
.ov and edges.
Equation 3(b) is referred to herein as the “unmodified 2-crease vertex rule”.
Vertices with only 1 creased edge have traditionally been treated the same as non-creased vertices, as in 3(a).
Vertices with three or more creased edges have been fixed in place, i.e.
P
(
V
)=
V.
3(c).
where vertices with three or more creased edges are herein referred to as “corners”, and equation 3(c) is referred to herein as the “corner rule”.
The method for creating faces and edges for each subdivision level is identical to the method used in the uncreased version above.
These rules are further disclosed in co-pending application Ser. No. 09/296,046, filed Apr. 21, 1999, by Thomas Burke entitled RELATIONAL MODELING OF TRIMMED NURBS SURFACES, the contents of which is hereby incorporated by reference its entirety.
Although there are methods for creating vertices, modifying those vertices, and creating hard creases, there remains a need for modifying hard creases to achieve an interpolation between hard creases and smooth surfaces. Furthermore there is a need for a simple user interface to execute this interpolation.
SUMMARY OF THE INVENTION
Techniques are provided for creating soft creases for subdivision surfaces. Specifically, techniques are provided for creating an interpolation between a hard crease and a smooth surface at every iteration of subdivision, and providing a mechanism for users to determine the degree to which such an interpolation resembles a hard crease or a smooth surface. Techniques are also provided to more consistently handle vertices with some number of creased edges other than 0 or 2 by interpolating between the unmodified Catmull-Clark vertex rule, the 2-crease vertex rule, and the corner rule, which has 3 or more creases.
According
Autodesk, Inc.
Cao Huedung X.
Moser Patterson & Sheridan LLP
Zimmerman Mark
LandOfFree
Simple soft creases for subdivision 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 Simple soft creases for subdivision surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple soft creases for subdivision surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3247385