Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-08-14
2001-07-03
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S426000, C345S426000, C345S440000, C345S440000, C345S440000, C345S442000
Reexamination Certificate
active
06256039
ABSTRACT:
BACKGROUND
Recent developments in the field of computer animation 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. Typically, this surface is represented in unparameterized form. For example, a common unparameterized surface representation is a polygon mesh, i.e., a collection of polygons joined at their edges. This polygon mesh model of the physical object then forms the basis for subsequent manipulation and animation.
In order to facilitate the manipulation of the polygon mesh, it is desirable for a user to be able to interactively draw curves on the surface of the polygon mesh. Since the user, in general, should be free to dictate the placement of the curves, the ability to precisely position these curves relative to the surface geometry is crucial to effective curve drawing.
Space Curves
A known technique allows the user to draw space curves, i.e., curves in 3-D space defined by specifying a collection of points in space through which the curve is constrained to pass. This technique for drawing and representing curves, however, has various problems when applied to drawing curves on surfaces. Although the space curve can be defined to pass through specified points on the surface, it is not otherwise constrained to the surface of the mesh. Consequently, it usually intersects and is occluded by large portions of the surface itself, making for poor visualizations. In addition, because these space curves are not constrained to the surface, the user must manually ensure that the curve closely follows the surface geometry. If either the surface geometry or the curve shapes (or both) are complex, this process is likely to be tedious and error prone. For example, using space curves it is possible to generate curves that depart significantly from the surface mesh even when they might appear to remain close to it. The fact that the polygonal mesh models are typically very large only serves to further exacerbate these problems.
Surface Curves
While manipulating curves in Euclidean space (
2
or
3
) is a well studied subject, there has been little work on the subject of manipulating curves on arbitrary curved 2-D manifolds. In the case where the manifold is represented as a parameterized surface in 3-D Euclidean space, the curve definition problem is effectively transformed to a problem in the Euclidean plane (i.e., the curve coordinates lie on the parametric plane). In this case, techniques for manipulating curves on parametric surfaces are well studied. Often, however, there is no obvious mapping, or parameterization, of a surface to the Euclidean plane, such as in the case of polygon meshes. Consequently, there are no techniques that allow a user to manipulate curves directly on the surface of a polygon mesh. Moveover, none of the known techniques for manipulating curves on surfaces have addressed the issues of intuitiveness of control, computational complexity of the optimization steps or the interactivity of their algorithms. Further, existing methods all make assumptions about certain restrictive properties of their underlying surface representation, e.g., smoothness, parameterization, and differentiability. While these assumptions may be valid for other problem domains, they do not hold for unparameterized surfaces such as polygonal meshes. Consequently, known methods do not solve many problems with editing and manipulating curves on surfaces in the context of 3-D computer animation.
Active Contours of 2-D Objects in 2-D Euclidean Space
Kass et al. has developed active contours of 2-D objects for the purpose of assisting in the performance of high level pixel image processing operations such as identifying subjective contours, motion tracking and performing stereo matching. These active contours are curves embedded in 2-D Euclidean space that have minimal energy when they closely approximate the 1-D contour of a 2-D object, i.e., when they match the outline of the object in the pixel image. They called these curves snakes for their snake-like behavior during a series of energy minimizing steps. A snake under this definition is an energy minimizing curve associated with an underlying 2-D pixel image. The energy of the snake is measured as a combination of internal constraints, image-based constraints and user supplied (external) constraints. For a curve v(s)=(v
x
(s), v
y
(s)) defined in the x-y plane of the pixel image, this energy is written as:
E
snake
=
∫
0
1
E
internal
(
v
(
s
)
)
+
E
image
(
v
(
s
)
)
+
E
constraint
(
v
(
s
)
)
ⅆ
s
(
1
)
In the equation above, the arc length parameter s varies from 0 to 1 (the length of the curve is normalized to one). The function E
internal
represents the internal energy of the snake due to the internal stretching and bending of the curve. The function E
image
represents the energy of the curve due to properties of the underlying image (e.g. intensity magnitudes or gradients) and E
constraint
represents external energy (e.g. based on user-defined constraints). The snake attempts to reach a final state that minimizes E
snake
.
In order to develop an intuition for what these energy terms represent, consider the internal energy term E
internal
. This can be further expanded as:
E
internal
(v(s))=&agr;(s)|v
s
|
2
+&bgr;(s)|v
ss
|
2
(2)
where &agr; and &bgr; are weighting functions, v
s
=&dgr;v/&dgr;s and v
ss
=&dgr;
2
v/&dgr;s
2
. The presence of the first order term |v
s
|
2
serves to minimize the length of the snake. For an intuition of what this term accomplishes, imagine the behavior of a pliable, elastic band that is constrained to pass through a series of hooks. The elastic band shrinks its length to be as short as possible and still pass through those hooks. For this reason, the first order term is sometimes referred to as the membrane energy or stretching energy of the curve. The term locally characterizes a C
0
curve that need only be continuous but not differentiable, i.e., the curve can have sharp corners.
The second order term |v
ss
|
2
minimizes the curvature over the length of the curve. For an intuition for what this accomplishes, imagine the behavior of a stiff wire that is constrained to pass through a series of hooks (like the membrane in our example above). Since the wire is resistant to bending, the resulting curve is smooth. For this reason, the second order term is sometimes referred to as the thin plate energy or bending energy of the curve.
Quantitatively, the term locally characterizes a C
1
curve, i.e., a curve that is continuous and has a continuous first derivative.
The functions &agr;(s) and &bgr;(s) are referred to as continuity control functions. By changing them one can control the relative strengths of the stretching and bending terms and therefore the shape of the curve. For example, if &bgr;(s′)=0, then v(s′) is a local discontinuity of the curve. If &bgr;(s′)=0, then v(s′) is a sharp corner of the curve. The curve produced by equation 2 is called a controlled continuity spline because one can change the continuity at any point along the curve by manipulating the continuity control functions &agr;(s) and &bgr;(s). Using the controlled continuity spline and judicious formulations for E
image
and E
constraint
, a variety of useful behaviors may be obtained for these snakes.
Although the contour snakes discussed by Kass et al. have some valuable properties in their context, they are limited to the problem of approximating a 1-D outline of an object in a 2-D pixel space. They are not useful in the context of drawing curves on curved 2-D surfaces embedd
Lumen Intellectual Property Services Inc.
Nguyen Kimbinh T.
The Board of the LeLand Stanford Junior University
Zimmerman Mark
LandOfFree
Methods for manipulating curves constrained to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for manipulating curves constrained to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for manipulating curves constrained to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556001