Note: Descriptions are shown in the official language in which they were submitted.
CA 02379459 2002-07-09
WO 01/08102 PCT/US99/16844
GEOMETRIC DESIGN AND MODELING SYSTEM
USING CONTROL GEOMETRY
FIELD OF THE INVENTION
The present invention relates to a system and method for performing computer
aided design, and, in particular, to
efficient computational techniques for blending between representations of
geometric objects.
BAC GROUND
A designer using a computer aided design (CAD) computational system will
typically approach the design of a free form
geometric object (such as a surface} by first specifying prominent and/or
necessarysubportions of the geometric object through
which the object is constrained to pass. Subsequently, a process is activated
for generating the geometric object that conforms
I 0 to the constraining subportions provided. In particular, such subportions
may be points, curves, surfaces and/or higher
dimensional ~ometric objects. For example, a designer that designs a surface
may construct and position a plurality of turves
through which the intended surface mutt pass (each such curve also being
denoted herein as a "feature line" or "feature curve").
Thus, the intended surface is, in general, expected to have geometric
characteristics (such as differentiability and curvature) that,
substantially, only change to the extent necessary in order to satisfy the
constraiMS placed upon the surface by the plurality of
I 5 curves. That is, the designer expects the generated surface to be what is
typically referred to as "fair" by those skilled in the art.
Thus, the designer typically constructs such feature curves and positions them
where the intended surface is likely to change its
geometric shape in a way that cannot be easily interpolated from other
subportions of the surface already designed.
As a more specific example, when designing containers such as bottles, an
intended exterior surface of a bottle may
be initially specified by subportions such as: (a) feature curves positioned
in high curvature portions of the bottle surface, and
20 (b) surface subareas having particular geometric characteristic such as
having a shape or contour upon which a botEle label tan
be smoothly applied. Thus, the iMe~ion of a bottle surface designer is to
construct a bottle design that satisfies his/her input
constraints and that is alto fair. Moreover, the designer may desire to
generate holes for handles, as well as, e.g., ergonomic
bottle grips by deforming various portions of the bottle surface and still
have the bottle surface fair.
CA 02379459 2002-07-09
WO 01/08102 PCT/US99/16844
There has heretofore, however, been no UD system wherein a designer (or more
generally, user) of geometric objects
can easily and efficiently express his/her design intent by inputting
constraints and haring the resulting geometric object be fair.
That is, the designer/user may encounter lengthy delays due to substantial
computational overhead and/or the designer/user may
be confronted with non-intuitive geometric objea definition and deformation
techniques that require substantial experience to
effectively use. for example, many priorart UD systems provide techniques for
allowing surfaces to be designed and/or deformed
bydefiningand/ormanipulatingdesignatedpoirnsdenotedas"control points."
However,suchtechniquesanbecomputationally
expensive, non-intuitive, and incapable of easily deforming more than a local
area of the surface associated with such a control
point.
Additionally,somepriorartCADsystemsprovidetechniquesfordefiningand/ordeformings
urfacesviacertainindividually
designated control vectors. That is, the direction of thesc vectors may be
used to define the shape or rnntour of an associated
I 0 surface. However, a designer s intent may not easily correspond to a
surface design technique using such control vectors since
each of the control vectors typically corresponds to only a single point of
the surface isolated from other surface points having
corresponding control vectors. Thus, such techniques are, at most, only able
to deform an area of the surface local to such points
having corresponding control vectors.
Additionally, such prior art CAD systems may also have difficulties in
precisely performing blending and trimming
I 5 operations. for example, two geometric objects intended to abut one
another along a common boundary may not be within a
sufficient tolerance to one another at the boundary. That is, there may be
sufficiently large gaps between the geometric objects
that the boundary may not be considered "water tight," which may be
problematic in certain machining operations and other
operations like Boolean operations on solids.
Accordingly, it would be rery desirable to have a CAD system that includes one
or more geometric design techniques
20 for allowing UD designers/users to more easily, efficiently and precisely
design geometric objects. further, it would be desirable
to have such a systcm and/or computational techniques for graphically
displaying geometric objects, wherein there is greater user
CA 02379459 2002-07-09
WO O1J08102 PCT/US99/16844
rnMrol over the defining and/or deforming of computational geometric objects,
and in particular, more intuitive global control
over the shape or contour of computationally designed geometric objects.
fiini ' ns
This section provides some of the fundamental definitions that are used in
describing the present invention. These
definitions are also illustrated in Figs. IS and Ib.
A "parametricgeametrlc object"S is a geometric object that is the image of a
function f, wherein the domain
of f is in a geometric shape embedded within a coordinate system (denoted the
"parameter space') and the range of f is
in another geometric space (denoted the "object space. Typically, the inverse
or pre-image, f', of a geometric object such
as S will be a geometrically simpler object than its image in object space.
Far example, the pre-image of a curve 110 in object
I 0 space may be a simple line segment 172, L, in parameter space. Thus if S
denotes the curve in object space, then notationally f
and S are sometimes identified suth that for uEl, a corresponding point in the
curve S is denoted S(u). Similarly, the pre-image
of an undulating surface 204 (fig. 1b) in object space may be a simple bounded
plane 180 in parameter space. Thus, if S denotes
the undulating surface X04, then for (u,v)E fi~(S), S(u,v) denotes a
corresponding point on the undulating surface 204.
A °proTle"~00 (fig. 1b) is a geometric object, such as a curve in
object space, through which an associated object
I S space geometrical 1y modeled object (e.g. wrface Z04) must pass. That is,
such profiles Z00 are used to generate the geometrically
modeled object. Thus, profiles provide a common and natural way for artists
and designers to geometrically design objects, in
that such a designer may think in terms of the feature or profile curves when
defining the characteristic shape of a geometric
object (surface) being designed. for example, profile curves on a surface may
substantially define the geometry of a resulting
derived geometric object; e.g., its continuity, curvature, shape, boundaries,
kinks, etc. Note, that for many design applications,
20 profiles are typically continuous and differentiable. However, such
constraints are not necessary. for example, a profile may.
in addition to supplying a general shape or trend of the geometric object
passing therethrough, also provide a texture to the
surface of the geometric object. Thus, if a profile is a fracral or iractal-
like, the fractal contours may be in some measure
CA 02379459 2002-07-09
WO 01108102 PCT/US99/168~14
imparted to the surface of the derived geometric object adjacent the profile.
further note that it is within the scope of the present
invention to utilize profiles that are of higher dimension (~I). Thus, a
profile may also be a surlace or a solid. Accordingly, if
a profile is a surface, then a solid having locally (i.e., adjacent to the
profile) at least some of the geometric characteristics of
the profile may be derived.
Moreover, profiles (and/or segments thereof) may have carious computational
representations such as linear (e.g.,
hyperplanes), elliptic, NURBS, or Bezier. Note, however, that regardless of
the computational representation, a method (such
as interpolation) fordeforming or reshaping each profile is preferable. More
particularly, it may be preferable that such a method
results in the profile satisfying certain geometric constraints such as
passing through (or substantially so) one or more
predetermined points, being continuous, being differentiable, having a minimal
curvature, etc. further, note that such a
I 0 deformation method may also include the ability to decompose a profile
into subprofiles, wherein the common boundary (e.g.,
a point) between the subprofiles may be "slidable" along the extent of the
original profile.
A °marker'208 (fig. l6) is a point on a profile that can be moved to
change the shape of the profile 200 in a region
about the marker. A marker also designates a position on a profile where the
shape of a geometric object having the profile
thereon can be deformed.
I 5 A °prorle handle"212 (Fig. l6) is a geometric object tangent to the
profile I00. Such a profile handle maycontrol
the shape of the profile locally by modifying the slope (derivative) of the
profile at the marker 208. Alternatively, for non-
differentiable profiles, a profile handle may be used to control the general
shape of the profile by indicating a trend direct'ron and
magnitude of the corresponding profile. For example, if the profile is a
fractal or other nondifferentiable geometric object, then
a profile handle may, for example, provide a range within the object space to
which the profile must be confined; i.e., the range
20 may be of a tubular configuration wherein the profile is confined to the
interior of the tubular configuration, Note that the profile
handle ~I~ affects the fullness of the profile 200 (e.g., the degree of
convexity deviating from a straight line between markers on
the profile) by changing the length of the profile handle.
CA 02379459 2002-07-09
WO 01108102 PCT/US99/16844
An isociine boundary"220 is the boundary curve opposite the profile 200 on the
isocline ribbon Z 16. In one
embodiment, at each point on the profile 200 there is a paired corresponding
point on the isocline boundary 200, wherein each
such pair of points defines a vector 224 (denoted a "picket") that is
typically transverse to a tangent vector at the point on
the profile. More particularly, for a parameteriied profile, the isodine
boundary 220 can be viewed as a collection of pickets at
S all possible parameter values for the profile 200.
An "isocline ribbon'~or simply isodine) is a geometric objea, such as a
surface 216, which defines the slope of
the geometric object (e.g., surface) 204 (more generally a geometric object
204) at the profile 200. Equivalently, the isocline
ribbon may be considered as the representation of a geometric object delimited
by the profile 200, the isodine handles 218a and
2186 (discussed hereinbelow), and the isodine boundary 220. In other words,
the geometric object 204 must "heel" to the
I 0 isocline ribbon 216 along the profile 200. Said another way, in one
embodiment, the geometric object 204 must be continuous
at the isocline 216 and also be continuously differentiable across the profile
200. In an alternative embodiment, the geometric
object 204 may be constrained by the isocline 216 so that the object 204 lies
within a particular geometric range in a similar
manner as discussed above in the description of the term "profile." Note that
there may be two isocline ribbons 216 associated
with each profile 200. In particular, for a profile that is a boundary for two
abutting surfaces (e.g. two abutting surfaces 204),
I S there can be an isocline ribbon along the profile for each of the two
surfaces. Thus we may speak of a right and a left hand
isocline ribbon.
An "isocifne handle'~2B is a geometric objea (e.g., a vector) for controlling
the shape of the isocline ribbon 216
at the marker 208, wherein the profile handle and isodine handle at the marker
may define a plane tangent to the surface 204.
Hence the isocline handle is used to determine the shape of the surfact 204
(or other underlying geometric object) about the
20 marker. In particular, an isocline handle 228 is a user manipulatible
picket 224. If all the profile handles 212 and isocline
handles 228 (e.g., for two or more abutting surfaces) are coplanar at a marker
208, then the surface 204 will be smooth at the
marker {assuming the surface is continuously differentiable), otherwise the
surface may have a crease or dart. Note that by
CA 02379459 2002-07-09
WO 01/08102 PCT/US99/16844
6
pulling one of the handles (either isodine or profile) out of the plane of the
other handles at a marker, one may intentionally
generate a crease in the surface 104 along the profile I00.
The part of the profile I00 between two markers 208 is denoted a "proFie
segment"'I32. Similarly, the part of
the isotline ribbon 116 between two isodine handles I28 is denoted a ribbon
segment240.
A "boundarysegment"244 denotes the part of the boundary 1I0 between two
isocline handles 218.
The vector 146 that is the derivative tangent to the isodine boundary 220 at
an isodine handle 228 is denoted a
"ribbon tangent." Note that modifications of ribbon tangents can also be used
by the present invention to control andlor
modify the shape of an underlying geometric object such as surface I04.
Isodine handles 1Z8 may be generalized to alto specifycurvature of the surface
I04. That is, instead of straight vectors
I 0 as isodine handles, the handles may be curved and denoted a "isociine ribs
"248. Thus, such ribs may facilitate preserving
curvature continuity between surfaces having associated isodine ribbons along
a common profile boundary, wherein the isodine
ribbons are composed of isodine ribs. Accordingly, the curvature of such
surfaces will match the curvature of their corresponding
isocline ribs, in much the same way as they match in tangency.
A "develop~able surface" is a surface that ran be conceptually rolled out flat
without tearing or kinking is
I 5 developable. It is a special case of a "ruled surface," this latter
surface being defined by being able to lay a ruler (i.e.,
straight edge) at any point on the surface and find an orientation so that the
ruler touches the surface along the entirety of the
ruler, for a developable surfacc, the surface perpendiculars are alt equal in
direction along the ruling.
"La6eisurlaces"denote special 2-dimensional (developable or nearlydevelopable)
surfaces wherein a label may
be applied on, e.g., a container. label surfaces allow application of a decal
without tearing or creasing. These surfaces are highly
20 constrained and are not typically deformed by the geometric modification of
an isodine ribbon Z16.
CA 02379459 2002-07-09
WO O1J08102 PCT/I;S99/16844
A "trim prone"is a geometric objea (curve) that is a profile for trimming
another geometric objea (e.g., a
surface). The trim profile may have a single corrtsponding isodine ribbon 216
since if the surlace to be trimmed is a label surface,
it will not be modified and, accordingly, no isodine ribbon can be used to
change its shape.
A trim profile (curve) nn be used to delimit am surface, not just a label
surhce. A surface, S, that is blended along
a trim profile with one or more other surfaces is called an
"orerbuiltsurfatc~' when the surface S overhangs the trim profile.
For example, in fig. I2, surface 130 a an overbuilt surface, wherein the
portion of the surface outside of the area 134 is typically
not shown to the designer once it has been trimmed away.
A convex combination of arguments F; is a summation ~ ci Fi where the 5 are
ualar coefficients and
scalar multipliation is well-defined far the f; (e.g., f; being vettors,
functions, or differential operators), and where c;20 and
I 0 ~ c f =1. If the f; are points in space, for instance, then the set of all
possible such combinations yields the convex hull of
the points F;, as one skilled in the art will understand.
A "forward evaluation" is a geometric object evaluation technique, wherein in
orderto generate a set of sample
values from a function, f(x), argument values for x are incremented and f is
subsequently evaluated. This type of evaluation is
usually fast and efficient, but does not give function values at chosen
positions between the increments.
I 5 An "implicit function" is one written in the form i(x)=0. XER" When a
parametric curve or surface is
converted to an implicit form, the conversion is called "implicitization."
Hence f(t)=(sin(t), cos(t)) in parametric form
may be implicitized by f(x,y) = x' + y~-I =0. Both forms deuri6e a circle.
Dividing a vector by its length "normalizes" it. The normalized vector then
has unit length. A vector function
may be divided by its gradient, which will approximate unit length, as one
skilled in the art will understand.
20 Given a function defined by a ~ p f ( t ) F~ ( t ) where p;(t) are
weightingfunct'rons, it ~ pi ( t ) =1 for
f ,-
all values of t, then the p; are said to form a "partition of unit)r."
CA 02379459 2002-07-09
WO 01/08102 PCT/US99/16844
"GI" continuity denotes herein a geometric continuity condition wherein
direction vectors along a continuous
parametric path on a parametrically defined geometric object are continuous,
e.g., tangent vector magnitudes are notconsidered.
SUMMARY Of THE INVENTION
The present invention is a computational geometric design system that is
capable of sufficiently efficient computations
so as to allow real-time deformations to objects such as surfaces while a user
is supplying the object modifying input. Thus, the
present invention is a paradigm shift away from typical CAD systems since, in
a typical CAD system the user must supply input
for changing or modifying a geometric object and subsequently explicitly
request processing of the input to commence. Thus, in
such prior art CAD systems, the user receives feedback about his/her design at
discrete user requested times. Instead, with the
present invention, updates may be processed in real-time immediately upon
input receipt without the user explicitly indicating
I 0 that update processing is to be performed.
Given the enhanced computational efficiency of the present invention, a user
of the present invention can more
efficiently perform iterative approximations to a geometric object being
designed. The user may speedily design without the need
to precisely calculate design geometric characteristics for portions of the
abject where such precision may not be necessary. That
is, the user can be less concerned about getting it "right the first time'
since the ease of modification and speed of computing
I 5 modifications allows the user to more rapidly approximate and/or prototype
a geometric object. Thus, the present invention can
have substantial efficiency benefits in that for many geometrically designed
objects (including machined parts), substantial
portions of such objects may be satisfactorily designed with a wide range of
geometric characteristics.
The UD system of the present invention enables novel design techniques by
providing a novel computational technique
for blending between two parametric geometric objects such as surfaces. In one
embodiment of the present invention, this novel
20 blending technique blends between two parametric surfaces S,(u,v) and
Si(u,v), wherein each surface has, e.g., the unit square
as its parameter space. Assuming each surface S, and Sl has a respective
blending function B,(u,v) and B~(u,v) such that each
CA 02379459 2002-07-09
WO 01/08102 PCT/US99/16844
9
of the blending functions has, for example, (0,1 ) as its range for a and v
(as well as satisfying other properties given hereinbelow),
a new surface, S, may be defined by the following formula:
S(u,v) = S1 (u, v) ~Bz(u,v) +Sz(u,v) ~BZ(u,v) (1)
Note that the blending funaions B, and B~ are typically chosen so that the
resulting blended surface S is the same as S, on a
boundary with S" and the same as St on a boundary with S,. This is achieved by
devising B, and Bi so that B, = I and Bz=0 on
the boundary with S, while having B~=I and B,=0 on the boundary with S~.
In a more general embodiment, the present invention may be used for blending
between a pluralityofgeometric objects,
S;, i=I,...,N, wherein each of the geometric objects is parameterized by a
corresponding function fsiwhose domain includes
a parameter space PS common to all f S , . Thus, for the resulting blended
surface S, substantially every one of its points, S(q),
(or q in PS is determined using a weighted sum of points obtained from the
points f S 1 ( q ) . Moreover, since it is desirable
I 0 to blend 5 to a boundary portion P; of each S;, when interpreting S as a
function from PS to the common geometric space GS having
the geometric objects S;, then S ( f S ~ ( P1 ) ) ~ P 1 . Additionally, 5 may
be also continuous at each f S 1 ( P i ) '
Note that formula (I) above is representative of various formulas for
generating a blended surface (more generally,
geometric object) S, other embodiments of such formulas are provided in the
Detailed Description hereinbelow. Further note that
such formulas may be generalized wherein the parameter space coordinates (u,v)
of Formula (I) above can be replaced by
I 5 representations of other parameter space coordinates such as triples
(u,v,w) or merely a single coordinate u. Moreover, the
blending functions B, and Bz may also be defined for such other parameter
spaces. Additionally, it is worthwhile to note that such
blending functions B, and Bi may be considered as weights of a weighted sum of
points selected from the surfaces (more generally,
geometric objects) S, and Si. Further, this weighted sum notion may also be
extended in various ways. for example, referring
to the mare general embodiment wherein a plurality of geometric objects S;,
i=I,...,N are provided, a corresponding
20 weight/blending function B; may be provided for each value of i so that the
following variation of Formula (I) is obtained:
CA 02379459 2002-07-09
WO 01108102 PCT/US99/16844
S ( q ) _ ~ B i ( q ) S i ( q ) for points q in a common parameter space far
the S;.
=i
In another aspect of the present invention, it is within the invention scope
to also generate blended geometric objects
S, wherein at least some of the S; geometric objects used to generate S are of
a higher dimension than 2. for example, if S, and
St are parameterized solids, then S may be generated as a solid blended from
S, and St using another variation of Formula (I),
5 as one skilled in the art will understand. Thus, S may extend between S, and
Sr so that a surface P, of S, and a surface Pl of St
are also boundaries of S, and S is represented as a weighted sum of points of
S, and St similar to formula (I).
I n yet another aspen of the present invention, one or more of the parametric
geometric objects S; of Formula ( I ) (or
variations thereof such as Formula (~), (4), (S), (5.02}, (5.03}, etc.
provided in the Detailed Description hereinbelow) may have
one of: a Bezier, NURBS, or some other multivariant parametric computational
representation instead of, e.g., isocline ribbons
I 0 as illustratively used in the description herein. Moreover, as one skilled
in the art will also understand, it is within the scope of
the present invention that the underlying geometric objects that define the S;
s (e.g., for the S; being isodine ribbons, such
underlying geometry being markers, profiles, isocline handles and profile
handles) may be different for a different computational
representation. for example, in a Bezier or NURBS representation of an S;
"control points" and/or geometric entities derived
therefrom, may be used to change a shape of the S; and therefore change the
shape of the resulting geometric object S derived
therefrom.
In another aspect of the present invention, when a blended surface S is
generated from one or more isodine ribbons
5,,...,5~, Nz2, the surface S can be deformed by changing geometric
characteristics of the isodine ribbons S;. In particular, by
changing the shape of one of the isocline ribbon boundaries for some S;, the
points S;(u,v) change and accordingly, the blended
surface S changes since it is a weighted sum a( such points. In particular,
rates of change of geometric characteristics of S (such
as curvature, tangent vectors, and/or tangent planes) may be determined by the
shape of the itocline ribbons S;. More
particularly, assuming a substantially linear parameterization along each
isocline picket, the greater the relative magnitude of
such pickets for a particular isocline ribbon, the more the shape of S will be
skewed in the directions) of such pickets. Moreover,
CA 02379459 2002-07-09
WO 01108102 PCT/US99/16844
11
as the direction of such pickets changes, the curvature of S changes. That is,
since the weighted sums, such as Formula (I), cause
S to always heel to the surfaces S;, the shape of S will change so that S
heels to the isodine ribbons) S; having pickets whose
directions have changed. Thus, the shape of the blended surface S may be
changed by any user interaction technique that: (a)
changes one or more geometric characteristics of one or more of the S;,
wherein such changes may include: changing a shape of
S; (wherein shape denotes a plurality of geometric characteristics such as
continuity, differentiability, curvature, and higher order
continuity), (b) changes a parameterization of an S;.
Also note that such user interaction techniques for deforming a blended
surface may also be used with higher
dimensional geometric objects. For example, if the S; geometric objects are
solids rather than surfaces, then a resulting blended
solid, S may be deformed by changing a shape of one or more of the solids S;
used in determining S.
I 0 It is also within the scope of the presets invention that the geometric
objects S; used to generate a blended geometric
object S may be such that the S; s can be modified indirectly via other
geometric objects from which the S; s may be themselves
generated. Far example, if S is a surface blended from isodine ribbons S, and
Si (having corresponding profiles P, and P2,
respectively), and the ribbon S, is interpolated from the profile handle, the
isocline handle, and the ribbon tangent at the end
points of P" then the present invention provides user interaction techniques
for modifying such handles and/or ribbon tangents
I 5 for thereby modifying the blended surface S. Moreover, in one user
interface technique, only the handles may be displayed,
wherein such handles are displayed as connected to the blended surface S.
Thus, by changing such handles, the blended surface
changes. Note that such user interaaion techniques may be responsive in real
time to user changes to such handles and/or ribbon
tangents. Thus, a user's design intent may be immediately displayed while the
user is inputting such changes. Accordingly, using
the present invention, user interactions in the design process may become
closer to the techniques in used in constructing actual
20 geometric models rather than prior art fAD user interaction techniques.
It is another aspect of the present invention that various geometric
constraint criteria are capable of being applied to
geometric objects generated according to the present invention. In particular,
features and/or subgeometry of a geometric object
CA 02379459 2002-07-09
WO 01/08102 t'CT/US99/16844
12
Oo are capable of being constrained to lie within another geometric object,
0,, so that as 0, is deformed, the features and/or
subgeometry of 0, deform correspondingly, and thereby cause Oo to deform
accordingly. for example, the present invention
allows an objea space point p to be defined (i.e., panmeterized) so that it
must remain in/on a given geometric object 0,, where
Oi may be a curve, surface, volume or solid. Thus, as 0, is deformed, Oa also
deforms. Moreover, instead of a point p, other
geometric subobjects may also be similarly constrained, such as curves,
surfaces or solids. Additionally, features of a geometric
object Oo such as control points, handles (of various types, e.g., profile and
isocline), normals, twist vectors, etc. may also be
similarly constrained by the present invention so that as 0, is deformed, Oa
is caused to also deform. For instance, using the
geometric object interpolation techniques provided by the present invention,
e.g., Formula (I) and variations thereof, the
geometric object Oo can be efficiently regenerated (e.g., reinterpolated)
substantially in real-time when constrained features
I 0 and/or subgeometries of 0o are correspondingly deformed with a deformation
of 0,. More particularly, this aspect of the present
invention provides for the combining of various geometric objects
hierarchically so that geometric deformation control of a parent
object causes corresponding geometric changes in dependent child geometric
objects. For example, when a surface patch
represents fine scale detail of a larger surface, it may be advantageous to
attach the fine detail surface patch to the larger surface
to thereby give a user automatic control aver the shape of the fine detail
surface patch by controlling the shape of the larger
I 5 surface. Moreover, similar hierarchical control can be provided with other
geometric objects of types such as curves, points and
three-dimensional deformation spaces.
Note that such hierarchical control may be also used with a persistent
deformation space wherein it is desirable for
a geometric object in this space to be repeatedly deformed and restored to its
original non-deformed state. Note that this is
difficult to do in real-time by repeatedly applying a one-time deformation.
Accordingly, by utilizing such hierarchical control
20 of the present invention, a geometric object embedded in such a three-
dimensional deformation space and/or the control
structures of the geometric object embedded therein provides for the
deformation of the geometric object when the three-
dimensional deformation space is deformed. Further, if one or more such
deformation spaces are, in turn, made dependent upon
CA 02379459 2002-07-09
WO 01/08102 PCT/CS9911684.1
13
a simpler geometry such as a surface or curve, then substantial control over
the shape of the geometric object, however complex,
can be provided by manipulating the shape of the simpler geometry.
Other features and benefits of the present invention are provided in the
Detailed Description and the drawings provided
herewith.
BRIEF DESCRIPTION OF THE DRAWINGS
fig. I shows a surface 62 generated according to the present invention,
wherein the surface interpolates between the
surfaces 30 and 34, and also passes through the curves 54, 58 and 60 at
predetermined directions according to the itodine
ribbons 61 and 63;
fig. ~ shows a further modification of the surfaces of fig. l, wherein the
surface 30 has a circular disk 66 blended
I 0 thereto according to a method of the present invention;
Fig. 3 shows a blended surface 62a generated according to the present
invention between the surfaces 30 and 34,
wherein the surface 62a passts through the curves 54 and 58 and wherein the
blending is performed according to a navel surface
generation formula provided herein (Formula (I));
fig.4 illustrates a correspondence between geometricentities in parameter
space and geometric entities in object space,
I 5 wherein lines 78a and 18b of parameter space have object space images of
curve 54 and S8, respectively, and additionally,
parameter space line 86 has as an object space image curve 80;
Fig. 5 provides a graphical representation of two blending functions, B, and
BZ, utilized in some embodiments of the
present invention;
figs. 6A-6D show graphs of additional blending functions that may be used with
the present invention;
20 Fig. l provides a further illustration of the correspondences between
geometric entities in parameter space and abject
space;
CA 02379459 2002-07-09
WO 01108102 PCT/L'S99/16844
14
Fig. 8 shows an elliptic region 100 that is blended into a cylinder 108
according to the present invention, wherein the
closed curve I10 delimits the elliptic region from the delormed portion of the
cylinder 108 that blends to the closed curve;
Fig. 9 shows a simple boss I II created on a cylinder I I6 according to the
method of the present invention;
Fig. (0 shows a composite curve 120 (as dtfined hereinbelow) that includes two
crossing subcurves 124 and 128;
Fig. I I shows a surface 130 from which a label surface 134 is trimmed;
Fig. II illustrates one computational technique far determining a distance-
like measurement from a point p that is
interior to the polygon having rertices v,, vI, v~, v,, and vs, whertin the
distance-like measurement to each side of this polygon
is determined using a corresponding apex 150 provided by a stellating process;
Fig. l3 shows two boundary curves 156a and 156b in parameter space (i.e., the
unit square), wherein area patches 168
I 0 therebetween are capable of being themselves parameteriied by coordinates
(s,t) where s varies linearlywith the distance between
two corresponding points on a pair of opposing subcurves 160a and I60b, and t
determines a corresponding point on each of the
subcurves of the pair I60a and I60b;
Fig. 14 illustrates a region that has sides and ribbons defined by three
surfaces S" St and S~, wherein the present
invention is able to proride a surface patch for the region 300 using formula
(5) provided hereinbelow;
I 5 Figs. l5 and 16 illustrate both general computational geometry concepts,
as welt as novel concepts that are fundamental
to the present invention. Hate that these figures are used to illustrate the
terms defined in the Definitions Section hereinabove;
Fig. l7 shows a block diagram of the typical flow of design construction
operations performed by a user of the present
invention in designing a geometric object;
Fig, l8 shows three profile curves 404, 408 and 412 meeting at a profile
marker 4I0, wherein the surfaces 416 and 418
20 join smoothly at the marker 4I0 due to the isocline handles (for the marker
420) being in a common plane 460;
Fig. 19 shows profile curves x and y that define a surface 480 which forms a
fillet between surfaces 484 and 486.
Typially, profiles x and y are defined using distances 488 and 490 Iram the
intersection curve 48I of surfaces 484 and 486;
CA 02379459 2002-07-09
WO 01/(18102 F'CT/US99/168~J:i
1.5
Fig. 20 illustrates one embodiment for computing a blended surface from
isocline ribbons 508 and 516 according to
the present invention;
Figs. 21A - 21C illustrate a procedure for creating a hole 600 according to
the present invention;
Fig. ~2 shows a blended surface 110 according to the present invention,
wherein the blended surface extends between
a degenerate profile (point) 714 and the circular end 718 of a cylinder 722;
Fig. 23 shows a blended surface 750 according to the present invention that
extends between the degenerate profile
(point) 754 and the planar disk 758 having a circular curve 760 therein;
Fig. 24 illustrates the results of a blending technique of the present
invention fur blending a surface between semi-
circular ribbons 784a and 784b, wherein the resulting surface 786 is blended
between these two ribbons.
I ~ Fig. 25 shows a blended surface 808 according to the present invention
whose points p(u,v) are determined using a
"forward algorithm", wherein points in parameter space 158 are themselves
parameteriied according to points in an additional
parameter space 828, and wherein the points 830 of the additional parameter
space are used to efficiently determine the distance-
like measurements to the pre-images (in parameter space 158) of the profiles
812 and 81G (in object space);
fig. 26 is a flowchart showing the steps for computing an interpolating curve
according to the present invention using
t S a one-dimensional embodiment of the computational techniques novel to the
present invention;
fig. 27 shows a flowchart of the steps performed when constructing an
approximation to an isacline baundary of an
isocline ribbon, wherein the boundary is apposite the profile for the isocline
ribbon;
Figs. 28A and 288 show a flowchart for a program that constructs a more preose
isocline ribbon boundary than the
approximation resulting from Fig. 27;
20 Figs. 29A - 29C illustrate a flowchart for modifying one or more
subsurfaces S;of a composite surface So by changing
a geometric characteristic of an isocline handle and/or a nbbon tangent for a
marker on one or more profile curves defining the
boundaries for the subsurfaces S;;
CA 02379459 2002-07-09
wo ovaa~oz PcTiosmn6sa=t
I6
Figs. 30A and 30B provide a flowchart of a program invoked by the flowchart of
Figs. 29 for deforming subsurfaces
S; in real time as a user modifies an isocline handle andlor ribbon tangent;
fig. 31 is a flowchart of the high level steps performed by a user interacting
with an embodiment of the present
invention for changing the shape of a surface;
Fig. 32 pictorially illustrates examples of values for parameters used in the
flowchart of fig. 26 far computing an
interpolating curve f(u);
Fig. 33 shows four profile curves P", P,t, P" and Pz~ wherein it is desired to
generate a surface, bounded by these
profiles and wherein the surface is defined by these four profiles (and their
associated isocline ribbons);
Figs. 34 and 35 illustrate the intermediary surfaces generated during the
performance of one method for creating a
I 0 4-sided patch (Fig. 36) from two 2-sided blends using the four profile
curves of fig. 33. That is, a blended surface S, (Fig. 34)
is generated using the isocline ribbons R" and R,t (for the profiles P" and
P,~, respectively),. and a blended surface St (Fig. 35)
is generated using the isocline ribbons Ri, and Rii (for the profiles P~, and
Pzt, respectively);
Fig. 36 shows a resulting blended surface S derived from S, (shown in Fig.
34), and Sj (shown in Fig. 3S), wherein S
is generated according to Formula (I I) provided in Section S of the detailed
description hereinbelow;
I S Fig. 37 shows the geometric objects used in an embodiment of the present
invention for generating a surface S from
two surfaces S~ and SR. In particular, this figure introduces the notational
conventions subsequently used in figs. 38 through 41;
Fig. 38 illustrates one embodiment of the present invention for generating a
four-sided patch;
Fig. 39 illustrates an alternative embodiment of the present invention for
generating the four-sided patch also
generated in Fig. 38;
20 Fig. 40 shows the notational correspondences between the geometric objects
of Fig. 38 and those of fig. 39;
Fig. 41 shows a possible geometric configuration of fig. 38, wherein the
profiles P3 and P4 of Fig. 38 are degenerate;
CA 02379459 2002-07-09
WO 111/(181(12 PCT/US99/168~14
figs. 42A and 42B illustrate the movement of a marker 2002 that is constrained
to reside on the profiles curves 2003
and 2004;
Fig.43 illustrates constraints on rnmposed profile curves and their
corresponding isocline ribbons for proridingtangent
plane continuity between two blended surfaces S, and S~;
Fig. 44 shows a profile P, associated isocline ribbons RL and RR, and various
handles used in describing the conditions
for achieving GI continuity on P.
DETAILED DESCRIPTION
I. Introduction
Fig. I illustrates the use of an embodiment of the present invention for
designing a surface 62 that interpolates any
I 0 two parametric surfaces such as between the half cylinder surface 30 and
the surface 34. That is, the surface 62 is generated
via a novel surface interpolation process, wherein constraints on surface 62
shape are provided by the feature curves 54, 58 and
60, and their associated novel control geometry (e.g., isocline ribbons). In
particular, the following constraints are satisfied by
the surface 62:
(a) one or more geometric charatteristics of the surface 30 along the feature
curve 54 are imposed
I S on the surface 62,
(b) one or more geometric characteristics of the surface 34 along the feature
curve 58 are imposed
on the surface 62, and
(c) the surface 62 interpolates through the feature curve 60, wherein the
surface 62 tangents along
the extent of curve 60 are derived from (e.g., identical to) the isodine
ribbons 6i and 63.
20 Thus, using the present invention, a designer can design a surface
specified in terms of: (a) a relatively small number of carefully
constructed and positioned feature curves, and (b) the desired slopes) of the
surface along the extent of these feature curves (via
CA 02379459 2002-07-09
WO 111/1181112 PCT/CS9)/168-4d
18
isocline ribbons). Moreover, using the present invention, such a designed
surface not only interpafates fairly between the feature
curves but also may obey other imposed constraints such as convexity,
concavity, and/or predetermined curvature ranges.
Additionally, the present invention can be used to blend a surface region into
an object being designed. for exampie,
fig. 2 illustrates the blending of a circular disk 66 into the cylindrical
surface 30. Moreover, the present invention can also be
used to construct bosses, dimples, logos, and embossing as well as to
recursively design surfaces as one skilled in the an will come
to appreciate from the disclosure herein.
At least one embodiment of the present invention differs from traditional
approaches to computer-aided design (CAD)
in that with the present invention, a desired geometric abject (e.g., a
surface) that may be created as a plurality of geometrially
and computationally unrelated patches (e.g., three-, four-, fire-sided bounded
surfaces), which may be subsequently pieced
I 0 together in a way that satisfies certain constraints at the boundaries
between the patches. Thus, the desired geometric object
can be designed by piecingtogether the plurality of unrelated geometric sub-
objects (subsuriaces) in a manner that interpolates,
blends and/or trims these sub-objects so that, across the boundaries and/or
regions therebetween, constraints such as continuity,
differentiability, and/or curvature are satisfied. This is fundamentally
different from the traditional approaches to CAD in that
only four-sided NURBS, Bezier, Hermite, Coons, Gordon or Booleans of implicit
surfaces are patched together in prior art systems.
I 5 2. Blending between Geometric Objects
A fundamental geometric object design technique of the present invention is
the blending between two parametric
geometric objects such as surfaces and, more particularly, the manner in which
such blending is performed. As defined in the
Definitions Section above, a "parametricgeometric object" (e.g. a surface) may
be defined as a result of a mapping
from a (simple) coordinatized geometric object (parameter space) such as a
bounded plane to another (typically, more complex)
20 geometric object (object space). When the parameter space is a bounded
plane, two coordinates or parameters (denoted a and
v) may by way of example be used to uniquely identify each point in the
parameter space. When the abject space is three-
CA 02379459 2002-07-09
WO 011081112 PCT/US99/16844
19
dimensional, for every (u,v) point in the bounded plane parameter space, a
function may associate a point (x,y,z) in the object
space.
By convention, a planar parameter space is usually assumed to be the unit
square, which means that both a and v vary
between 0 and I, although it is within the scope of the present invention to
utilize other parameter space geometries and
coordinate ranges.
In oneembodiment of the present invention, in orderto blend between two
parametric surfaces S,(u,v) and S~(u,v) each
having the unit square as their parameter space, each surface S, and Sz has
associated therewith a respective blending function
B,(u,v) and Bz(u,v), wherein each of the blending functions has, for example,
(0,1) as its range (as well as satisfying other
properties given hereinbelow). Consequently, a new surface may be defined by
the following formula:
S(u.v) - S1 (u. v) ~B1(u~v) +Sz(u,v) ~B2 (u, v) (1)
Note that the blending functions B, and B~ are typically chosen so that the
resulting blended surface S is the same as S, on a
boundary with S,, and the tame as S~ on a boundary with S,. This is achieved
by devising B, and Bt so that B,= I and Bt =0 on
the boundary with S, while having Bl=I and B,=0 on the boundary with Sz. In
Fig. 3, for example, if S, is the surface 30 and
ST the strip 34, and one boundary is the vertical line 54 of the surface 30
and the other boundary is the curve 58 on the strip 34,
I 5 then the surface 62a is S, which runs between these two boundaries and is
tangent to S, and S~ at the boundaries.
2.1. The Blending Functions
Blending functions may be provided for blending between geometric objects of
various types. for example, blending
functions for blending between two volumes filling geometric objecu can be
provided. However, to simplify (and clearly
illustrate) the novel blending process and the associated blendingfunctionsof
the present invention, thediscussion here is initially
limited to blending between two curves, or blending between two surfaces.
Accordingly, for two surfaces S, and S~ to be blended
together, the blending functions B,(u,v) and Bi(u,v), respectively, are
appropriately set to either 0 or I on the boundaries of a
blended surface generated by the present invention.
CA 02379459 2002-07-09
WO 01108102 PCTlUS99/lf>>8-1-t
Referring to Fig. 4, wherein it is assumed that the boundaries 18a,18b in
parameter space correspond to the profiles
54 and 58 in object space, for any curve 80 on the blended surface such as
surface 62a, there is a related pre-image (e.g., line
86) defined in parameter space as indicated. Note that for simplicity the
boundaries 18a and 18b, and the pre-image of curve
80 are straight, but they need not be so.
5 Assuming (again for simplicity) the blending functions B~(u,r) and B~(u,v)
have their domains in the unit square (as
their parameter space), for any point (u, v) in this parameter space it is
important to determine some measure of how "close"
the paint (u,v) is to the boundary curves (e.g., boundary curves 78a and 78b)
and, mare generally, to the pre-images of profile
curves. Such closeness or distance-like measurements may be used in specifying
the blending functions and/or their resulting
values. Note that there are many ways to compute such a closeness or distance-
like measurement in parameter space. For
I 0 instance, if a boundary 78 (or profile pre-image) is a straight line, then
such a parametrrc distance to a (u,v) point is easily
calculated as the length of a perpendicular fine segment to the boundary line
through the point. Additional techniques for
computing parametric distances are described hereinbelow (e.g., Sections ~.3
and 2.4).
Assuming parameter space is still the 2-dimensional space of (u,v) points, a
blending function B i (wherein I s is: N
for some fixed N number of boundary curves) can be computed a function of a
univariate distance-tike function B ~ ( Di ) .
I 5 where D; is ;n turn a function of (u,v) so that B ( D 1 ) - E~ 1~D ~ ( u,
v ) } = B ~ ( a , v ) , wherein D;(u,v) is a
distance-like function to the pre-image C;' of a boundary curve C; (in object
space) of a surface S. Note that such distance-like
functions must satisfy the condition that as (u,v) gets arbitrarily close to
the i'" boundary curve pre-image C;' (such as measured
in conventional Euclidian distance), then D~(u,v) gets arbitrarily close to
iero. Examples of such blending functions B i and
distance-like functions D~ are provided hereinbelow.
20 Since many of the most useful blending functions B; are of the form B 1
(D;), unless additional specificity is required,
B; will be used hereinbelow to denote both: (a) the blending function B;(u,v)
initially discussed above, and (b) the blending
function B i ( Di ) for some distance-Pike function D;. If, however, a clear
distinction is required between the blending
CA 02379459 2002-07-09
WO Il 1/118102 PCT/U S99/168~4~
)1
functions of (a) and (b), the domain of the blending funaion can be used to
indicate which blending function is indicated. As
an aside, note that formula (I) applies equally well far the blending funaions
B i ( Dl ) , i =1, 2_ ; that is,
S (u, V1 = S. (u, v) ~ Bl~D,~+Sa (u~ V) ~ B2~D~~. (2)
If a point (u,v) is close to the id pre-image boundary i=1,2, then iii ( D L )
is expected to be small and the point is mapped
(into object space) close to the i~' boundary.
A good collection of blending funaions B; not only allows the mapping, S, of a
blended surface to be coincident with
the desired perimeter (profile) curves, but will do so in a manner so that the
resulting blended surface between two or more such
perimeter curves of, e.g. for example, different initial surfaces will
preserve such characteristics as the continuity of curvature
with these initial two surfaces. That is, the blended surface "heels" to each
of the initial surfaces. Also, it is preferred that the
blending functions B; allow the new surface to be fair. Figure 5 shows a graph
of a pair of desirable blending functions for B;,
i= I,~.
For profile curves P,, Pt of two surfaces S, and Si, wherein a blended surface
is desired between P, and Pt, assume that
the profiles P, and Pz have parametric pre-images that correspond,
respectively, to u=0, u=I of the unit square
~(u,v) ~ 0 s a I and 0 ~ v < I ~, then some useful properties for blending
functions B, and BZ are:
(1I) B,=I at u=0 and B,=0 at u=I. B1=0 at u=0 and B3 =I at u-I.
I 5 (1.2) The derivatives B;' and B~' equal 0 wherever D;(u,v)=0 and
D;(u,v)=I, i=1,2. This enforces
smooth (tangent continuous) transitions between the blended surface S and the
initial surfaces S, and St. If higher
order derivatives are also zero, then higher order continuity between surfaces
can be realized, usually improving its
fairness.
CA 02379459 2002-07-09
wo onostoz pc~riUS~9imHaa
?2.
(1.3) B,+B1= I for all poinu (u,v). This is called a partition otunit~; "and
it provides for the
generation of a convex cambiirationof the surfaces S~ and Sz to which a new
blended surface abuts. Note that this
tends to keep the new blended surface from drifting too far from the initial
surfaces S, and S~.
There are numerous embodiments for defining blending functions. One useful
embodiment is:
B1(DL) = case (D1 4 ) and B2(D2) = sine (D2 ~ ) (3)
which gives arbitrarily high order continuity of the blending functions, which
is needed to achieve the same high order continuity
between the initial blended surfaces. Another alternative is to choose
polynomial functions with the above properties (1I)
through (1.3). forexample, a quintic polynomial can be chosen with zero second
derivative at D=0 and D= I, thereby providing
beneficial curvature characteristics (see Section 4.4).
In addition to the blending functions described hereinabove, the following are
examples of additional blending
funaions:
B,(x) and Bz(x) are polynomials satisfying the following constraints:
B,(0)=l, B',(0)=0. B(1)=0. and B'(I)=0
Byx)' I-Bi(x)
Note that additional constraints regarding high order derivatives (e.g., equal
to 0 at x=0 and/or I) may
I 5 also be imposed. For example, if B";(0)= B";(I)=0, i=1,2, then C~
continuity is attained with the objects from
which interpolating and/or blending is performed.
An example of polynomial blending functions satisfying these constraints is:
Bi(x) _ (I-x)' + 5x(I-x)' + IOx~(t-x)'
B~lx? = I_B,(x).
CA 02379459 2002-07-09
WO (11/08102 PCT/USJ91168~a
03
Note that B,(x) may he derived as a Bezier curve with six control points,
Pi,...,Pb, as shown in fig. 6D.
Moreover, note that since
B',(x) _ -30x' ~(I-x)' and
B"t(x) = 60x ~(I-x)'-60x' ~(I-x),
that
gn(I)=O, B"(0}=0, g",(I)=Od B',(A)=0. Bn(I)==0. g",(1)-0 B'UO)=0 and
8 "2(0)=0.
(c) Any composition of blending functions as described hereinabove with a
bijective (e.g., one-to-one and onto)
parameterization function P:[0,1]--[0,1] may be composed wrth a blending
function to obtain another
I 0 blending function. As a specific example, let P(x) = 2t(x-x') + x', where
c is a constant "skeri' factor,
then a new blending function may be construed as B(P(x)). Thus, when c = %i,
P(x)= x. Moreover, as
c varies, the inflection paint of the graph of P(x) moves as shown in figs. 6A-
bC. Note that the blending
function of Fig. 6B (wherein c > r1) will cause the blending curve (and/or
surface or other geometric
object) to retain the geometric characteristics of the object used for
blending that corresponds to the x= 0
I 5 axis in the graph of Fig. 6B for a larger part of the surface.
To reduce the real-time design computational overhead incurred for evaluating
blending functions, the values for the
blending functions may, in one embodiment, be tabulated prior to a design
session at a sufficiently high resolution and stored
in memory in a manner that allows efficient indexed access to a closest
approximation to the actual blending funaion value.
L2. Exx~tending Blending to N-sided Regions
20 In one embodiment of the present invention, a novel general form for
blending over a region that is bounded by each
edge e; of a parametric wrface S; (i=1,2,...,N and Nz~) is the following
weighted sum of points S,(u;(p},v;(p)):
CA 02379459 2002-07-09
WO 01It18102 1'C;'1'/CSI~)/168d-t
24
N
S (P) _ ~ ~ $.;~D~ (P) ) Si (ui (p) . Vi (P) (
j ~i
where:
(a) p is a variable denoting points in a common parameter space for the
surfaces S;;
{b) D~(p) is a distance-like measurement to the pre-image of the i'" edge e;
in the common parameter space;
{c) B~ is a blending function which is zero when D~ is zero and monotanically
increases as D~ increases; and
(d) u; and v; are parameterization functions that transform p from the common
parameter space to the (any)
intermediate parameter space for S .
Note that by dividing by the sum of the products of the blending functions,
B~,
N
(e-g. , ~ ~ E3~ )
i_. J =1
jsi
the formula (4) tan be normalized with respect to the blending functions.
further note that Formula (4) resembles formula (I)
when N---2, and is in fact an extension thereof. That is, for N =2, B, of
formula (4) has the functional behavior of B~ in Formula
I 0 (I), and B~ of Formula (4) has the functional behavior of B, in Formula
(I). That is, there is a subscripting notational change
between the two formulas.
As an example of Formula (4), consider the three-sided region 300 shown (in
object space) in Figure 14. Applying
Formula (4) to thereby generate a surface, S, For region 300, the following
equation is obtained:
S(P) °BZ(v)B3(w)S1(u) ~~B1(u)H,~(w)SZ(V) +Bi(~t)B2(v)S3(W) {S)
I 5 where u, v and w as parameterization functions are the barycentric
coordinates of p as one skilled in the art will understand.
CA 02379459 2002-07-09
WO t)1!(18102 PCT/l1S'19116844
i' J
An alternative method to define a blended surface over N-sided (N~4) regions
is provided by first applying the two-
sided approach based on Formula(I) using R" and R,~ of fig. 34 as S, and S~,
respectively in Formula (I) to thereby generate S,
of fig. 34. Additionally, formula (I ) is applied to the surfaces of Fig. 35,
wherein S, and St of Formula (I) are replaced by Rz, and
Rtt respectively, to thereby generate S~ of Fig. 35. The two resulting
surfaces S, and Si of figs. 34 and 35 respectively are, in turn,
blended using formula (2) wherein blending functions B, and BZ are as
described hereinabove, and the corresponding D; are
described hereinbelow For example, given that each of the ribbons R", R,t,
Rt,, and Ru, have a common pre-image, the D; used
in Formula (2) to compute distance-like measurements to the pre-images of the
pair of edges P", P,1, Pi,, and Pzz (figs. 34 and
35) may be:
(a) For a point P, of the (common) pre-image far S, of Fig. 34, D,(P,)= min
(D(P,,P"1), D(P,,P,~)) wherein D
I 0 is the Euclidean distance between P, and the corresponding profile P,;,
and
(b) For a point P~ of the (common) pre-image for Sz of Fig. 35, Dz(P~) -= min
(D(Pt,P~,r), D(Pl,Pi~)).
Accordingly, the two surfaces S, and S7 can be blended together using Formula
(2) to obtain surface S of fig. 36.
In another embodiment that is particularly useful for generating a four-sided
blended patch, assume the following
restricted but versatile scheme for defining profiles and ribbons:
I S (a) All handles are piecewise linear segments; and
(b) All blending is done with the functions B,(x) and Bl(x) of formulas (3.1).
Moreover, referring first to fig. 37 in describing the present patch
generation technique, the following labeling scheme is used.
For the profile, P:
mr, mR: the left and right hand markers, respectively, of the profile, P;
20 hr, hR: the left and right hand profile handles, respectively, of the
profile, P;
s~, sR: the left and right hand isocline handles, respectively, of the
profile, P;
CA 02379459 2002-07-09
wo umgioa ~~TiUS~mncsaa
:? H
b~, bR: the left and right hand ribbon tangents at the respective left and
right end points of isocline boundary R (these
ribbon tangents also being denoted as "boundary handles").
Using the notation of Fig. 37, surfaces S~ and SA may be defined, wherein S~
is bounded by the line segments
corresponding to: sr, h~, b~, and dr = (s~ + br) - h~, and S~ is bounded by
the line segments corresponding to: s~, hp, br, and dA
= (s~ + b,~ - hR. In particular, Si and Sr are known in the art as "twisted
flats," and accordingly, S~ is denoted as the left
twisted flat, and SA is denoted as the right twisted flat. Moreover, these
surfaces may be evaluated using the following formulas
(S.OIa) and (S.OIb):
SL(u~~) _. (1-~,~ ~) mL hL ~luu.~ (5.01a)
SL bL
wherein the parameters a and v increase in transversedirections as illustrated
by the u-direction arrow and the v-direction arrow
(fig.37).
.~~ (u, v) - ( 1-vr, v) hR mR ~ lu~~~ ( 5. 01b)
~R SR
wherein the parameters a and v also increase in transverse direction, with the
u-direction being the reverse direction of the u-
direction arrow of Fig. 31.
Accordingly, the isocline ribbon surface S (fig. 37) can now be defined as
follows:
CA 02379459 2002-07-09
W'O I»108102 P~CT/US)'l/168~14
:?
S (u,v) - B; (u) SL (u, v) + B, (u) SR(u,v) (5.02)
where conveniently, the a parameter is also the distance measure needed for B,
and B~ of Formulas (3.1). Thus, when v = 0,
S(u,0) is the profile; i.e., a blend between the control handles (hr-m,) and
(h~ m~). Additionally, note that when v -- I, S(u,i)
is the ribbon boundary R derived as a blend of vectors (b,-s;) and {bR s~).
Also note that if br and bA are translates of hr and h~,
respectively, along sr-m~ and s~-ma, respectively, then R is a translation of
P, and such similarities may simplify the data storage
S requirements of the present invention.
Far a plurality of isocline ribbons S" 5,,...,5N, wherein each S; is generated
by Formula (5.01), such ribbons may now
be used in the mare general N-sided surface form below, which is a variation
of formula (4).
N
TT BI (D~ (_;, t) Si (ui (s, t) , vi (s, t) )
t
S (s,t) - _._.. ~-1 ___
N ~N
d rt x3. (D. (s, t) )
I 7 7
1 r~,i~l (5.03)
Note that Di(s,t), u;(s,t) and v;(s,t) must be defined for this formula, m.e.,
the distance measure and the mappings from the general
N-side patch parameter space (in s and t) to the parameter space of the
ribbons S; (in a and v).
i 0 For specific cases where N = 2, 3, 4 and N ~ 5 using the blended ribbons
S;, notice first that Formula (5.02) for the
ribbon is a special case of Formula (5.03). For example, in Formula (5.02) the
denominator is 1, the distance measure is just
the u-parameter, and a and v correspond exactly to s and t. The formula for a
two-sided surface is similar, except that the base
surfaces are ribbons derived according to Formula (5.02) {denoted herein also
a "twisted ribbons"); thus,
S (u, v) B2 (v) S (u, ~r) + B1 (v) S" (u, v) (5.04)
CA 02379459 2002-07-09
wo ov~Hmz PcTms~mnr>H:~a
28
in Formula (5.0~), wherein the parameter a measures distance. It varies
alongthe direction of the profile curve. Now, in Formula
(5.04), the parameter v measures distance.
Referring to Fig. 38, wherein the isodine ribbons S, and S7 are parameteriied
as indicated by the a and v direction
arrows on each of these ribbons, these ribbons may be used to generate a four-
sided patch. The two profiles P, and Pi that vary
in a are blended using the twisted ribbons S, and S,. The other two sides P~
and P, are blended profiles derived from the isodine
handles; that is, P, is a blend (e.g., using Formula (I)) of h F, and h Tl,
wherein hR i s S 1 and h~' i s S ,
in Formula (I), and similarly, Pq is a blend of hR a nd h? .
Note that the blended surface, S, of fig. 38 has tensor product form. This can
be shown by decomposing Formula (5.04)
into a tensor form, wherein each of the ribbons S, and St is derived from the
Formula (5.01a) and (S.OIb). That is, S, is a blend
I 0 of SL and SR (fig. 38) and Si is a blend of SR arid Sp . Accordingly, the
decomposition is as follows:
Sl ( u, v)
S ( u, v) - ( B2 ( v) B~ ( v) )
S.. ~; u, v)
S,~ ,, .'z, v) SR ( u, v) B2 u)
-- (B2 (v) By (v) ) (5.05)
Si r, u~ v) SR ( u~ v) Bi ( u) .
B., a )
( B2 ( v) SI + E31 ( v) SL Ba ( v) S~ -+ Bl ( v) SR )
B, ( a )
Thus, the last expression above shows that the same surface S can be generated
by first creating the twisted ribbons in the v
parameterization, and then second, blending in u. However, since the roles of
a and v are symmetric, the twisted ribbons may
begena~sdabngd~euperartima~timadsudedadrgnerhepa~6m~edovThata,~gdresuriaorsS,an
d SR, SL and S
of fig. 39 gives the same surface S as in Fig. 38. Thus, in either technique
for deriving 5, the inputs are the same; that is,
CA 02379459 2002-07-09
WO U1IOR102 P1~T/US99/1G844
>9
mL , mR , hL , h,~ , sL , sk , bi , and br~,
where"i"denotestheprofileP,(i=1,2,3,4)towhichthe inputs
apply. Note that the correspondences between the various inputs is shown in
fig. 40.
So, overall, the two-sided patch of formula (5.04) provides a very versatile
four-sided patch. Monover, its evaluation
is also efficient. Thus, by expandingthe S ii and S R of formula (5.05) using
Formulas (S.OIa) and (5.01 b), the following
expression may be obtained:
a l
B~ (u)
(B (v). B, (v» (y__v~ v) Ir ~ RI 1-L. (5.06)
2
( L ~ ~ R) .
where ( L ~ and ( R ) are the appropriate matrices from Formulas (S.OIa) and
(5.01 b). Note that when evaluating an
instantiation of this expression, the B, should probably be table driven.
The above formulation is mathematicallysound, but to use it in a geometrically
intuitive fashion still requires judgment
on the user's part. Thus, in certain degenerate cases, some mathematical aids
are also in order. A common instance is where two
I 0 of the profiles (e.g., P, and P~) intersect each other, as in fig. 41.
This is a degenerate case since profiles P; and P4 (of fig. 38)
are zero length, and share end markers (i.e., m~ = m,a and mR = mr,' ) _
Note, however, that formula (5.04) still defines a surface S, but it is easy
to see that the surface may loop at the profile
intersections. To eliminate this looping and still maintain handle-like
control at the markers, the twisted ribbon of Formula
(5.04j may be sealed by a function of u. One funaion that is I at a _ % and 0
at u=0, is:
a (u) - ! '9 (u-~)2 (5_07)
CA 02379459 2002-07-09
WO llt/Q81(l2 PI~T/CS99/1G8a4
Thus, Formula (5.01)o is adjusted to be.
S(u, v) --- B2;v) a(u) Slcu, v. * B1 (v) a(u;~ SZ(u. v) (5.08)
Such a function (5.08) will likely remove most loops.
The ability to diminish the ribbon at the ends suggests other applications. A
scaling function such as
ay (u) = 1-u' (5.09)
diminishes the ribbon at the u= I end, while
a, (u) - 1 - (u-:l)' (5.091)
5 diminishes it at the a = 0 end. This is an effective way to make a
triangular (three-sided) surface, as one skilled in the art will
understand.
2.2.1 Bosses and Dimples from 2-Ed>res
The so-called "bossN feature may be obtained from a blending between two
profile edges. The profiles may be provided
as, for example, semicircles 780a and 7806 of Fig. Z4 having isodine ribbons
184a and 784b, respectively. The ribbons 184a and
I 0 784b are in distinct parallel planes. When these ribbons are blended
together, a surface 786 (fig. 24) is obtained which may be
considered a bass or a dimple. Note that many variations, o.e., domes, rocket
tips, mesas, apple tops, etc. may be generated
similarly. Moreover, if the top semicircular ribbon is rotated, the boss can
be made to twist. This scheme can be used to
transition between tubes, like a joint, as one skilled in the art will
understand.
Note that in another embodiment, blending may bt performed by using a
neighborhood about each boundary curve
I 5 (in object space) as a default isodine ribbon from which to blend using
Formula (1) or formula (4). Thus, by defining a value
> 0, and taking a strip and width of each surface along the boundary to which
the surface is to be blended, these strips may
CA 02379459 2002-07-09
WO 01108102 P~CT/US9~)/168a.t
3.
be used as isocline ribbons. Accordingly, the surface boundaries become
profile curves and pre-images thereof may be used in
the formula (I) or formula (4).
Z.3. Profile Curves
Since the present invention can take a few well-positioned (object space)
profile curves of various types and generate
a corresponding surface therethrough, as a blended surface according to
formula (I ) above, there are two parameter spate pre-
image curves for each of the surfaces S, and St wherein these turves are
boundaries for the blending functions B, and Bi; that is,
a curve at 0;=0 and at D;=I for each blending function B; In fact, there may
be eight turves, as illustrated in fig. 7, that may
be used to define a blended surface. That is, there may be two turves 78a and
18b in the parameter space of S, and two additional
curves 78c and 78d in the parameter space for Si (of course, in many cases
these two parameter spaces are identified).
I 0 Additionally, there are the mappings of the curves 78 to the two surfaces
30 and 34, thereby providing the corresponding image
curves 90, S4, 58 and 91, these having respective pre-images 78a,18b, 78c and
7Bd.
Note that in the case where S, and Si have identical parameter spaces, profile
78b is the pre-image of the profile 54.
Moreover, if S~ of 78d (- 78b) is profile 58, then 186 is included in the pre-
image of each of S,, St and blended surface 62.
When the present invention is used for surface design, a ustr or designer may
think of designing a blended surface by
I S continuously pulling or deformingone profile curve of an initial surface
tothereby create a new surface between this initial surface
and a profile curve of another initial surface.
Note that different types of profile or boundary curves may be used with the
present invention. In some embodiments
of the present invention, such a profile curve, C, may typically have a
parametric pre-image in a parameter space, i.e.
C-'(s)={u(s),v(s)) where s is a parameterization of the pre-image (e.g., 0 s s
< I). Note that parametrit turves such as C
20 include curves having the following forms: (a) tonics including lines,
parabolas, circles and ellipses; Bezier, Hermite and non-
uniform rational b-splines (NURBS); (b) trigonometric and exponential forms;
and (c) degenerate farms like points- Additionally,
CA 02379459 2002-07-09
wo uvustOZ P~cTiL~s9~imsaa
32
note that these curve forms may be categorized orthogonally by other
characteristics such as open, closed, degenerate and
composite, as one skilled in the art will understand.
Profile curves include tunes from the following curve-type categories (2.3.1)
through (2.3.5).
2.3.1. Open Curves
S An "open turve'°is one in which the end points of the curve are not
constrained to be coincident; e.g., the end points
may be freely positioned. Open curves are probably the most common type used
by the present invention when defining an
arbitrary collection of curves (profiles) for generating a surface (in object
space), wherein the surface is constrained to pass
through the collection of curves.
Z.3.2. Closed Curves
I 0 When a curve's end points match, the curve is denoted as "closed. " This
means that the beginning point of the curve
is the same as the ending point of the curve. Closed curves delimit regions
of, e.g., a surface, and are especially useful for setting
special design areas apart. One example of this is the label surface for
containers (described in the Definitions Section
hereinabove); e.g., surface 66 of Fig. 2. That is, a label surface is a region
that must be of a particular surface type, denoted a
developable surface, so that a label applied thereto will not crease or tear.
Each such label surface is highly constrained and is
I 5 usually separated from the rest of the design by a closed tune (such a
curve ran also serve aesthetit purposes in the design of
the container). Fig. 8 shows an elliptic region 100 blended into a cylinder
108, wherein the closed curve ! 10 delimits the elliptic
region. A closed curve may oaten match tangencies at end points.
2.3.3. Degenerates
Several ways exist to generate a degenerate profile. In one technique, an open
curve may be of zero length, or a closed
20 curve may enclose a region of no area. In such cases, the result is a paint
that may blend with an adjacent surface. Fig. 9 shows
a point blend created from blending between a degenerate circular disk (i.e.,
the point labeled S,) and the cylinder l 1b (also
denoted as S~). Accordingly a simple boss I 12 is created on the cylinder 116.
In particular, for appropriate blending functions
CA 02379459 2002-07-09
WO 01/08102 PCT/US99/IGBa=i
_:c 3
B;, i=1,2, a blended surface between S, and St can be obtained using Formula
(I). Moreover, since Formula (4) can be used
instead of Formula (I), a surface can be generated that blends between a
plurality of points (i.e., degenerate profiles) and an
adjacent surface. Figs. 23 and 24 show additional blends to degenerate
profiles.
Fig. 23 shows a blended surface 110 that extends between the degenerate
profile (point) J14, and the circular end 718
of the cylinder 722. In particular, the blended surface 710 is a blending of
the isocline ribbons 726 and 130, wherein the isocline
ribbon 726 is a planar disk having the degenerate profile 714 as its center
point, and the isocline ribbon 130 has the circular end
718 as its profile. Thus, letting S, be the isodine ribbon 726, and St he the
isodine ribbon 730 in formula (I), the distance-like
measurements (in their corresponding parameter spaces) can be equated to:
(a) the radial distance from the degenerate profile 714 on the isocline ribbon
726;
I 0 (b) the distance away from the profile 718 on the isocline ribbon 130.
Fig. 24 shows another blended surface l50 that extends between the degenerate
profile (point) 754, and the planar
annulus 758 having a circular curve 760 therein (and having, optionally, a
central hole 762 therethrough with curve 760 as its
boundary). In particular, the blended surface 710 is a blending of the isoclme
ribbon 766 (lor the degenerate profile 754), and
the annulus 158 (which, e.g., can optionally be an isocline ribbon to the
surface 770 wherein curve 760 is a profile). Thus, letting
I 5 S, be the isocline ribbon J66 and St be the annulus 758, the distance-like
measurements (in thcircorresponding parameter spaces)
tan be equated to:
(a) the radial distance from the degenerate profile 754 on the isodine ribbon
766;
(b) the distance away from the curve 160 on the annulus 158.
2.3.4. Composite Curves
20 The novel geometric design techniques of the present invention can also be
utilised with composite curves. Composite
curves are general curve forms that include other curves as sub-curves,
wherein the sub-curves may cross or may kink, e.g., at
endpoints. In utilizing composite curves as, e.g., profiles, the definition of
a distance-like measurement for a composite curve
CA 02379459 2002-07-09
WO Ul/U81112 PCTIUS99/1C>8a~t
34
is important. fig.10 shows a composite curve 120 that includes two crossing
sub-curves 124 and 1~8. However, such composite
curves can also have their sub-curves strung end-to-end.
Assuming the sub-curves C~, j=1,2...,N of a composite curve C are
parameterized and have a common parameter space,
a distance formula (in parameter space) for determining a distance-like
measurement D to the pre-images of the sub-curves C~
is:
D(p) = DNtP), and
Dk(P) ~dktP)+Dk..l(P)_ ~dA'(p)+ Da_ (P)]'
(5..5)
where k=2,...,N and D,(p) = d,(P) = a distance measurement between P and C,,
and Dk(P) = a distance measurement
between P and C,. Thus, D(p) can be used as the input to a blending funaion,
B(D), for blending one or more surfaces to the
composite curve, C.
23.5. Trimming Curve
I C) The present invention allows a surface to be "trimmed," wherein trimming
refers to a process for constraining or
delimiting a surface to one side of a particular boundary curve (also denoted
a trim curve). In particular, for parameterized
surfaces, the pre-image of a trim curve, e.g., in the (u,v) parameter space of
the surface, identifies the extent of the pre-image
of the surface to remain after a trimming operation. A trim curve may be a
profile curve, and the desired trimmed surface is that
part of the original untrimmed surface that typically lies on only one side of
the trim curve. An example is shown in Fig. I I,
I 5 wherein the original untrimmed surface is the generally rectangular
portion t30. The rounded surface 134 is a "label" surface
that is trimmed to the curve 138 from the original surface 130. Note the trim
profile 138 may have an associated isocline ribbon
(not shown) for one or more adjacent surfaces (e.g., surface 141) that heel to
an isodine ribbon at the trimming profile 138.
The use of isoclines for modifying the shape of such adjacent surfaces is an
important technique in creating a smooth transition
from the adjacent surfaces to a trimmed surface.
CA 02379459 2002-07-09
WO OllOR102 PCT/USJ9/1684d
Note that the present invention may include a trimming technique to create a
hole in a geometric object. By extruding
a depression in a front surface of the geometric object through a back surface
of the object, and then trimming the front surface
to exclude the corresponding portion on the back surface, a hole can be
constructed that tan be used, e.g., as a handle of a
container.
2.4. Distance Metrics
Some techniques for computing distance-like measurements have already been
provided hereinabove. In this seaion,
additional such techniques are described. The efficiency in computing how
close a point in parameter space is to one or more
particular geometric object pre-images (turves) in parameter space can
substantially impact the performance of a geometric
design and modeling embodiment of the present invention. In general, for
computing such distance-like measurements (these
I 0 being, in general, a monotonic function of the conventional Euclidean
distance metric) in parameter space between points and
curves, there is a trade-off between the complexity of the curve and how
efficiently such measurements can be evaluated. In
general, the simpler the turve, the faster such distances can be determined.
As an aside, it should be noted that for a parameter
space curve and its image curve (in objea space), these curves need not be of
the same computational type (e.g., polynomial,
transcendental, open, closed, etc.). Indeed, a parameter space curve may be
quite simple and still be the pre-image of a
I 5 complicated surface curve in object space. for example, the parameter
space curve correspnnding to the Bezier curve 58 in Fig.
I may be a straight line. By keeping the parameter space curve as simple as
possible, fast distance computations are possible.
2.4.1. Parametric Distance Calculations for Blending
This section describes a variety of methods for calculating a distance-like
measurement (more generally, a monotonic
function of the conventional Euclidean distance metric) to a number of
candidate parameter space curves, wherein the methods
20 are listed in a roughly increasing order of computational complexity.
Assume a blended surface is to be generated between two profile curves P~ and
P2, each having isodine ribbons, wherein
each ribbon is parametric and has, e.g., the planar unit square [0,1]x(l),I]
as the common parameter space for the ribbons. One
CA 02379459 2002-07-09
WO (111081(12 PCT/1,'S99/1G84d
36
distance-like function capable of being used for blending is a function that
is dependent on only one or the other coordinate of
points represented by the coordinate pairs (u,v) in the common parameter
space. That is, assuming the profile curves P, and Pt
of the isotline ribbons are such that their pre-images are the vertical lines
u=k, and u=k, far 0 s k, s k~ s I, then the
corresponding distance-Iikefunctions can beD,(u,v)=(u-k,)/{k,-k~)andDa(u,v)=(u-
k,)/(ki-k,). Moreover, if the pre-images
are the parameter space bounding vertical lines u=0 and u= I (i.e., k,=0 and
k,= I), then the corresponding distance-like
function can be D,(u,v)=I-a and Dt(u,v)=u, and accordingly such simple
distance-like functions can be computed very
efficiently.
In order to maintain the desired simplicity in parametric distance
tomputations when there are pre-images to more
than two profiles for blending therebetween, three methods can be employed for
computing parametric distance-like
I 0 measurements. Each of the three methods is now described.
A triangular domain in parameter space bounded by, e.g_, three profile curve
pre-images (that are also curves) can
be parameterized with respect to the vertices v,, v1 and v3 of the triangular
domain using three (real valued) parameters r, s and
t with the additional constraint that r+s+t=I. In other words, a point p in
the triangular domain having the vertices v,, yr
and v, can be represented as p=r*v, + s*vz + t*vj. The r, s, t parameters are
called "barycentntcoordinates"and are used
I 5 for three-sided surfaces such as the surface 300 of Fig. l4 ~n parameter
space.
Domains in parameter space that are bounded by the pre-images of four profiles
{denoted the tour-sided case) can be
a simple extension of the domain having bounds on two opposing sides (denoted
the two-sided case). In the two-sided case, if
parameterized properly, only one parameter, u, need be used in the distance-
like function computation. In the four-sided case,
both parameters a and v may be employed, as well as their complements
(assuming an appropriate representation such as the
20 unit square in parameter space). Thus the distance to the four profile pre-
image boundaries in parameter space can be u, v, I-u,
and I-v (i.e., assuming the pre-images of the profiles are u=0, v= 0, v== I,
u= I).
CA 02379459 2002-07-09
WO Oll(18102 PCT/US99/1(i8:l:l
3'7
To determine barycentric coordinates for parametric space domains, assuming
the pre-images of the profiles are line
segments that form a polygon, the approach illustrated in Fig. I~ (illustrated
for a five-sided polygon (4B having vertices v,, vi,
v,, v, and vs) may be utilized, wherein the profile pre-images are the heavy
lines labeled 149a through 149e. To determine a
distance-like function, first, stellate, i.e., make a star from, the pre-image
polygon 148 by extending each of the sides 149a
S through 149e of the polygon until they intersect with another extended side
having a side 149 therebetween. Thus, the intersection
points 150a through 150e are determined in the five-sided case of Fig. l2.
Subsequently, the line segments 152a through IS2e
from the corresponding points 150a through 150e to a point p in the polygon
may be constructed. The resulting distance-like
measurements are the lengths of the line segments 153a through 153e from p to
the sides 149a through 149e of the polygon 148.
Accordingly, the distance from p to the i"" side 149 (i=a,b,c,d,e) of the
polygon 148 is the distance along the i'" line segment 153
I 0 from p to the boundary edge of the polygon 148. Note that by dividing each
resulting distance-like measurement by the sum of
all the distance-like measurements to the point p, the distance-like
measurements can be nonnalized.
2.4.2. Straight Line
A straight line is represented by the equation, au +bv==c, wherein a, b, c are
constants. A convenient (unsigned)
distance to a line is obtained by
15 D(u, v) - I (;~, b) ( (u. v) - ~ ~. (6)
For a more intuitive version that corresponds to Euclidean
distance, Formula (6) can be normalized to obtain
D(u~ v) . , (a, b) ( (u. ~) -~ ~ 1 (a'+b2 . (T)
by dividing by the length of the gradient.
20 2.4.3. Conits
Conks include parabolas, hyperbolas and ellipses. The general form of a conic
~s
Au?+Buv+~u~+L;u+Ev+F = C.
CA 02379459 2002-07-09
wo otloHU~z p~c~ruJS~~mcs-t.~
38
Its unsigned distance can be computed by
L,
D(u.v? - (u. V) ' ? .(tlJ l .~ 'E~~ ~u'VI + F (B,)
B
2
This can also be normalised by dividing through by the length of the gradient
of the function to make a mare suitable
distance-like function, which is Euclidean in the case of the circle. Note
that Farin in Introduaion to Curves and Surfaces,
S Academic Press, 4th ed., 1996, gives the conversion between the implicit
form above and a rational parametric form. Thus,
Formula (8) can be used regardless of whether the conic is represented
implicitly or parametrically.
t.4.4. Polynomial Curves, both Parametric and Implicit
Assume that a parametric curve has been converted to a Bezier form as, for
example, is described in the Farin referenre
cited hereinabove. Vaishnav in Blending Parametric Objects by Im,~hcit
Techniques. Proc. ACM Solid Modeling Conf., Map 1993
gives a method to change a curve from a parametric curve to an implicit curve
numerically, wherein distance is implicitly
measured in object space by offsetting the curve in a given direction that is
based on some heuristics about how the offset is to
be computed. The value of the offset distance that forces the offset to go
through the point is the distance measurement for that
point. In particular, for a Bezier curve, this distance-like measurement may
be worthwhile in that it is robust (i.e., not ill-
conditioned) and reasonably fast to evaluate, requiring only two or three
Newton-Raphson iterations on average, as one skilled
I S in the art will understand. White this may be an order of magnitude slower
than computing a distance measurement of a conic
representation, it is much faster than the traditional method of computing a
perpendicular distance, which is also unstable.
2.4.5. Piecewise Parametric Curves
The present invention also includes a novel technique for computing a distance-
like measurement on complex curves
in parameter space.
CA 02379459 2002-07-09
WO (111081(12 PCT/US99/1G84d
.9
Referring to Fig. l3, assume that both boundary turves 156a and ISbb are in
the unit square parametric space 158 and
are piecewise parametric polynomial curves that have corresponding sub-curves
160a, I60b of the same degree n. By connecting
end points of the corresponding sub-curves with tine segments 164 (i.e.,
degree one curves), degree n by I Bezier patches 168 can
be constructed in the unit square representation of parameter space 158. Note
that each patch 168 can be considered as a second
parameter space unto itself having coordinates (s,t) wherein:
(a) for two Bezier wb-curves 160a and 160b (denoted herein b,(t) and b~(t),
Osts I), each value, t,, of t
corresponds to a line segment, Leo, between b,(ta) and bz(t,), and
(b} the L to line segment is parameterized by s so that L to (s)E b(to) when s-
-0 and L to (s) E b~(t,) when
s- I, wherein s varies proportionally with the distance between b,(ro) and
b~(to) when 0 < s c I. Accordingly, if the
I 0 distance-like measurement between the curves b,(t} and b;{t)(and/or patch
bounding line segments 164} is computed
in the second parameter space, then for any (u,v) point interior to the patch,
it is necessary to find the corresponding
{s,t) point relative to the boundary curves of such a patch that can then be
evaluated for determ fining the distance-like
measurement. Since s is the linear parameter (corresponding to the distance of
a point between the two corresponding
sub-curves I60a and 160b that are joined at their endpoints by the same two
segments 164), simple functions f,(s) and
I S fl(s), such as f,(s) =s and f,(s) = I-s, can serve as distance functions
to b,(t) and b~(t), respectively. Note that the
parameters a and v can both be represented as Bezier functions of s and t. In
particular, to rnnvert from (s,t)
coordinates to (u,v) parameter space coordinates, a Newton type algorithm may
be used, as one skilled in the art will
understand.
Another approach for determining the distance-like measurement, in some
circumstances, is to evaluate such patches
20 168 with a "forward algorithm:' That is, referring to fig. 25, an object
space blended surface 808 that blends between, e.g..
profiles 812 and 816 (having isocline ribbons 820 and 814, respectively, to
which the surface 808 heels} is shown. The profile
81~ has as its pre-image curve lb0a (in parameter space 158), and the profile
816 has as its pre-image curve 160b (in parameter
CA 02379459 2002-07-09
WO ()1J118102 P'CTIUS99/lG8d.~
space I S8), wherein the portion of parameter space 158 for surface 808 is the
patch 168. An additional parameter space 828 in
s and t can be considered as a pre-image parameter space for the parameter
space IS8 wherein the pre-image of curve I60a is
the vertical line segment at s=0, and the pre-image of curve 160b is the
vertical line segment at s= I. If a sufficiently dense
set of points 830 denoted by "x"s in additional parameter space 828 is used to
evaluate points (u,v) in patch 168 (e.g., by
5 determining a closest paint 830), then the corresponding poets p(u,v) on a
blended surface 808 can be efficientlycomputed since
the distance-like functions to pre-image curves 160a and 160b ran be
0,(u(s,t),v(s,t) = s and Di(u(s,t),v(s,t)) = I-s, respectively.
This approach will generate the blended surface easily and quickly. Note, if
the surface 808 does not require a subsequent
trimming operation, this method is particularly attractive.
3. Blending Programs
I 0 Figure 11 shows a block diagram of the typical flow of design construaion
operations performed by a user of the present
invention. Thus, profile handles may be needed to construct an associated
profile, and the profile is required to construct the
associated isocline ribbon, and the isocline ribbon may be required to obtain
the desired shape of the associated object (e.g., a
surface), which, in turn, is required to construct the desired geometric
model.
Figs. 26 through 30 provide a high level description of the processing
performed by an embodiment of the present
I 5 invention that enables the novel real-bme manipulation of the shape of
geometric objea representations so that a user can more
efficiently and directly express his/her design intent. Moreover, it should be
noted that a fundamental tenet of the present
invention is a paradigm shift away from typical CAD systems. That is, in a
typical CAD system the user must supply input for
changing or modifying a geometric object and subsequently request processing
of the input to commence. Thus, the user receives
feedback about his/her design at discrete user requested times. Instead, with
the present invention, updates may be processed
20 in real-time immediately upon input without the user explicitly indicating
that update processing is to be performed. Accordingly,
a user of the present invention can efficiently perform iterative
approximations to a geometric object being designed without
requiring the user to precisely calculate geometric characteristics for
substantially all portions of the object. In particular, this
CA 02379459 2002-07-09
WO (11108102 PCT/US)9/1C>8:1:1
X11
can have substantial efficiency benefits in that for many geometrically
designed objects (including machined parts), substantial
portions of such objects may be satisfactorily designed using a wide range of
geometrically shaped objects. Accordingly, the
present invention allows many of these geometric objects to be designed
without the user haring to needlessly specify precision
in those portions of the object where the precision is unnecessary.
in Fig. ~6, the steps are shown for computing an interpolating curve according
to the present invention using a one-
dimensional variation of Formula (I) discussed in Section 2 hereinabove.
Accordingly, in step 1004, the end points and tangents
at the end points fat the interpolating curve, C(u), to be generated are
obtained. In particular, the end points of this curve are
assigned to the variables PTI and PT2. Additionally, ditedion vectors for the
interpolating curve C(u) at the points PTI and PT?
are assigned to the variables TAN I and TAN2, respectively. Note that PTI,
PT2, TAN I and TAN2 can be supplied in a variety of
I 0 ways. For example, one or more of these variables can have values assigned
by a user and/or one or more may be derived Pram
other geometric object representations available to the user (e.g., another
curve, surface or solid representation). In particular,
the direction tangent vectors denoted by TAN I and TAN2 may be determined
automatically according to a parameterization of
a geometric object (e.g., a surface) upon which the points PTI and PTZ reside.
In steps 1008 and 101, the blendingfunctions B, and BI are selected as
discussed in Section (2.1) hereinabave. Note,
I 5 however, that the blending functions provided may be defaulted to a
particular pair of blending functions so that a user may not
need to explicitly specify them. However, 'n is also within the scope of the
present invention that such blending functions may
be specifically selected by the user. ! n this regard, note that since the
present invention is intended to express the user's geometric
design intent, there may be a wide variety of blending functions that are
acceptable since typically a user's intent is often
adequately expressed without the user purposefully determining highly precise
input. That is, it is believed that a wide variety
20 of blending functions may be acceptable for iterative approximation of a
final geometric design since progressively finer detail
can be provided by generating and/or modifying progressnely smaller portions
of the geometric object being designed using
substantially the same blending functions. Said another way, since the present
invention supports bath the entering of precise
CA 02379459 2002-07-09
wo uvosioa Pc~rius~mobs~a
~2
(geometric or otherwise) constraints as well as the iterative expression of
the user's intent at progressively higher magnifications,
the high precision and/or small scale design features rnay be incorporated
into a user design only where necessary.
In step 1016, the interpolating curve, C(u), is computed using a variation of
formula (~) applied to a one-dimensional
parameter space. An example of an interpolating curve, C(u), with points PTI,
PT2, and rectors TANI and TAN1 identified, is
illustrated in fig. 32.
In fig. 27, a flowchart is provided showing the steps performed when
constructing an approximation to an isodine
boundary R(u) for an object (e.g., a surface) S, wherein the poims PTI and PT2
delimit a profile curve corresponding to the
isocline ribbon boundary approximation to be generated. In particular, the
approximate isocline ribbon boundary generated by
this flowchart is intended to approximately satisfy the isocline ribbon
boundary definition in the Definitions Section hereinabove.
I 0 More precisely, the isocline ribbon boundary approximation determined by
the present Nowchart will tend to match the isocline
ribbon boundary definition for a portion of the abject S between PTI and PT2
depending on, e.g., how smooth the object is along
the profile curve generated between PTI and PT2. That is, the smoother
(reduced curvature fluctuations), the more likely the
match. Accordingly, in step I 104 of fig. 27, the curve interpolation program
represented in fig. 26 is invoked with PTI, PT2 and
their respectne tangents TAN I and TAN2 for the object (surface) S. Thus, an
interpolating curve, C(u), is returned that is an
I 5 approximation to the contour of S adjacent to this curve.
In steps I 108 and I I (2, a tangent (i.e., a picket) along the
parameterization of the object S at each of the points PTI
and PT2 is determined, and assigned to the variables PICKETI and PICKET2,
respectively. Note that typially the pickets, PICKETI
and PiCKET2, will be transverse to the vectors TAN I and TAN2, although this
need not be so. Subsequently, in steps I I 16 and I 120,
the isodine ribbon points corresponding to PTI and PT2 are determined and
assigned to the variables, RIBBON_PTI and
20 RIBBON PT2, respectively. Then, in step 1124, the curve interpolation
program of fig. 26 is again invoked with the values
AIBBON_._PTI, RIBBON-PT2, TANI and TAN2 to thereby generate the isocline
ribbon boundary approximation, R(u}. It is
worthwhile to note that in some cases, the isocline ribbon approximation
bounded by the interpolating (profile) curve ((u), the
CA 02379459 2002-07-09
WO OIIORlp2 1'CT/US99/168-t4
43
corresponding pickets (PICKETI and PICKET2), and the newly generated isocline
boundary R(u) does not necessarily form a
surface. In fact, the curves, C(u) and R(u) may be substantially coincident
(e.g., if PICKETI is identical to TANI, and PICKET?
is identical to TAN2).
In figs. 28A and 28B, a flowchart far a program is provided far constructing a
more precise isodine ribbon boundary
than the approximation resulting from fig. 27. In particular, in the flowchart
of Figs. 28A and 28B, the program of Fig. 27 is
repeatedly and adaptively invoked according to the variation in the objea
(e.g. surface) S along the path of the profile curve
provided thereon. Accordingly, in step 1204 of Fig. 28A, a sequence of one or
more markers M;, i=1,2,...N, N~ I, is assigned to
the variable MARKER SET, wherein these markers are on the surface, S, and the
markers are ordered according to their desired
occurrences along a profile turve to be generated. Note that in one typical
embodiment, the rnarkers are generally provided (e.g.
I 0 constructed and/or selected) by a user of the present invention. Moreover,
for the present discussion, it is assumed that the
tangents to the surface S corresponding to the markers M; are tangents to S
entered by the user. However, it is within the scope
of the present invention that such tangent vectors may be provided
automatically by, for example, determining a tangent of the
direction of a parameterization of the surface S.
In step 108 of Fig. 28A, the first marker in the set, MARKER~SET, is assigned
to the variable, MAAKERI. Subsequently,
I 5 in step 121, a determination is made as to whether there is an additional
marker in MARKER SET. If so, then in step 1216, the
variable, INTRVL, is assigned a parametric increment value (or incrementally
selecting points on the profile curves) to be
subsequently generated hereinbelow. In one embodiment, INIRYI may be assigned
a value in the range greater than or equal
to approximately !0~'to 106.
In step 120, the variable, MARKER2, is assigned the value of the next marker
in MARKER SET. Subsequently, in step
20 1224, the curve interpolation program of Fig. 26 is invoked with MARKERI
and MARKER2 (and their corresponding user- identified
tangent vectors) for thereby obtaining an interpolating curve, C~(u) between
the two markers (where j=1,2,..., depending on the
number of times this step is performed). Then in step 1228, an isotline
boundary approximation is determined according to fig.
CA 02379459 2002-07-09
wo nvostoi NcTmsu<m6~a~
44
21 using the values of MARKERI, MARKER2 and the interpolating tune, C(u), for
obtaining the isodine boundary approximation
tune, R~(u).
Subsequently, in step 1240, the variable, ulVAL, is assigned the initial
default value INTRYIfor selecting points on the
tunes, G(u) and Ri(u). following this, in step 1244, the variable INCRMT_PT is
assigned the point corresponding to C~(u YAL).
Subsequently, in step 1245, the variable, S PT, is assigned a point on S that
is "closest" to the point Ci(u YAL) Mote precisely,
assuming S does not fold back upon itself closer than s > 0, for some:;, a
point on S is selected that is in a neighborhood less
than E of G. Note that since C~(u VAL) may not be on S, by setting the value
of INTRYL so that this variable's value corresponds
to a maximum length along the interpolating curve C~ of no more than one-half
of any surface S undulation traversed by this
curve, then it is believed that the interpolating tune C~ will effectively
follow or be coincident with the surface S. Subsequently,
I 0 in step 1246, a determination is made as to whether the point INCRMT_PT is
within a predetermined distance of S_PT (e.g., the
predetermined distance may be in the range of 10''to 10 6). In particular, the
predetermined distance may be user set and/or
defaulted to a system value that is changeable depending upon the application
to which the present invention is applied.
Accordingly, assuming that INCRMT PT and S~PT are within the predetermined
distance, then step 1248 is encountered wherein
the point R~(u VAL) on the isocline boundary approximation is determined and
assigned to the variable, RIBBON_PT.
I S Subsequently, in step 1252, an approximation to an isodine picket at C~(u
VAL) is determined and assigned to the variable,
PICKET.
tn step 1254, the tangent to the surface (more generally, object) S at the
point C~(yVAI) is determined and assigned
to the variable, INCRMT TAN, this tangent being in the direction of the
parameterization of S.
In step 1256, a determination is made as to whether the vectors, INCRMT TAN
and PICKET are sufficiently close to one
20 another (e.g., within one screen pixel. If so, then a subsequent new point
on the interpolating tune G is determined by
incrementing the value of u~VAI in step 1264. Following this, in step 1268, a
determination is made as to whether the end of
the interpolating curve, C~(u), has been reached or passed. Note that the
assumption here is that 0 su s I. Accordingly, if a VAL
CA 02379459 2002-07-09
WO 111/08102 PCTll;S99/168d4
is less than I, then step 1244 is again encountered, and some or all of the
steps through 1256 are performed in determining
whether the isodine ribbon point approximation, R~(u YAL), is close enough to
the actual ribbon point as theoretically defined
in the Definitions Section hereinabove.
Referring again to step 1246, note that if INCRMT "PT is not close enough to
S, then an interpolating curve more finely
5 identified with the actual points of S is determined. That is, the point,
S_PT, is made into a marker and inserted into
MARKER SET, thereby causing new interpolating ribbon curves, C~(u) and RI(u)
to be generated that will deviate less from S
(assuming S is continuously differentiable). That is, step 12)2 is performed
wherein a marker is generated for the point, S PT,
and this new marker is inserted into MARKER SET between the current marker
values for MARKERI and MARKER2. Subsequently,
the marker currently denoted by MARKER2 is flagged as unused (step 1276), and
in step 1280, the most recently constructed
I 0 interpolating curve C~(u) and any associated ribbon boundary curve RI(u)
are deleted. Then, step 1220 and subsequent steps are
again performed for determining new interpolating and ribbon boundary curves,
C~(u) and AI(u).
Note that steps 1212 through 1280 and step 1220 are also performed if in step
1256, INCRMT TAN and PICKET are not
determined to be sufficiently close to one another in the object space of S.
Referring again to step 1268, if the end of the interpolating curve, Ci(u),
has been reached or passed, then it is assumed
I 5 that C~(u) is sufficiently close approximation to points on S (between
MARKERI and MARKER2), and fli(u) is insufficiently close
to an isodine ribbon for these points on S. Thus, if there are additional
markers wherein an interpolating curve C~(u) and
corresponding ribbon approximation R~(u) has not been determined, then the
next pair of consetutive markers (of the marker
ordering} in MARKER SET is determined and various of the steps 1220 and beyond
are performed. That is, in step 1284, MARKERI
is assigned the value of MARKER2, and in 1288, a determination is made as to
whether there is a next unused marker in
20 MARKER SET. If so, theca variations of the steps 120 and beyond are
performed as described above. Alternatively, if all markers
have been designated as used, then in step 1292 the resulting curves C~(u),
R~(u), for each used j= I,~,..., is graphically displayed
CA 02379459 2002-07-09
wo uuostoZ PcTiuso~m~sa~t
46
and stored for subsequent retrieval. Note that the profile curves C~(u) may be
optionally reparameterized so that these curves
may be parameterized collectively as a single curve, C {u), wrch C (0) = Ci{0}
and C {I) = CN(I).
figs. 29 and 30 provide high-level descriptions of flowcharts for modifying
one or more surfaces (mare generally
geometric objects) by modifying isocline handles, ribbon tangents, and their
associated isocline ribbons. In particular, for
simplicity, the flowcharts of these figures assume that there is a composite
surface, So, that is provided (at least in part) by one
or more subsurfaces, S~, i= I,~,...N, N z I, where these subsurfaces S~ are
connected to one another (e.g., patched together) along
common boundaries so that So does not have disconnected portions. Accordingly,
given such a composite surface, So, the
flowcharts of Figs. 29 and 30 can be described at a high level as follows. In
Fig. 29, an isocline handle and/or a ribbon tangent
having at least one geometric characteristic {e.g. length, direaian,
curvature, etc.) to be changed is determined along with the
I 0 subsurfaces S; that are to be modified to reflex the isacline handle
and/or ribbon tangent changes. Subsequently, in the flowchart
of Fig. 30, the modifications to the subsurfaces are computed and displayed in
real-time as the user enters the modifications to
the selected isocline handle and/or ribbon tangent. Note that the computing of
surface (more generally geometric object)
modifications in real-time has not heretofore been feasible for surfaces in
higher dimensional geometric objects in that the
computational overhead has been too great. Accordingly, the present invention
has reduced this overhead by providing a novel
I 5 technique of computing blended surfaces which is very effiaent and which
generates surfaces that are lair.
The following is a more detailed description of figs. 29A and ~9B. In step
1400, if there are not profiles and isocline
ribbons corresponding to the entire boundary of each subsurface S;, then make
profiles and isocline ribbons that approximate the
entire boundary of each subsurface S;. Note that this may be performed using
the program of the flowchart of figs. 28. In step
1404, the isocline handles and ribbon tangents corresponding to markers on the
surface Sa are graphically displayed to the user.
20 In step 1408, a determination is made as to whether the user has requested
to add one or more additional isocline ribbons to the
surface So, or extend an existing isocline ribbon having its profile curve on
So. If the user has made such a request, then step 141
is performed to assure that in addition to any other markers added by the
user, markers are added: (a) whenever a profile
CA 02379459 2002-07-09
wo ot~osto2 P~~nus<rm~saa
contacts a boundary of a subsurface S;, and (b) so that profile curves will be
extended in a manner that terminates each one on
a boundary of a subsurface S;. Moreover, additional markers may be also added
at intersections of curve profiles. Thus, for these
latter marker, there may be two distinct ribbon tangents associated therewith
(i.e., one for each subsurface).
Subsequently, in step 1416, the program of Fig. I8 ~s invoked with each S;, i
=1,2,...N for thereby obtaining the desired
S additional profiles and isorJine boundaries. As an aside, note that fig.18
need only be invoked with the subsurfaces S; to which
new markers are added.
In step 1420 following step 1416, all newly added isocline handles and ribbon
tangents are displayed. Note that in some
embodiments, only the isocline handles are displayed initially, and the user
is able to selectively display the ribbon tangents as
desired.
I 0 Subsequently, in step 144, a determination is made as to whether the user
has requested to add one or more additional
markers within existing profiles. If so, then the additional new markers are
added and at least the corresponding new isocline
handles are determined (or these new markerz. As an aside, note that in one
embodiment of the present invention, when a new
marker is added to an existing profile, the profile will change somewhat since
it is now exactly identical to the surface So at
another point and the interpolating curve generated (via Fig. ~6) between
consecutive markers of a profile is now generated using
I 5 the newly added marker. Accordingly, a profile with one or more additional
markers should, in general, conform more closely
to the shape of the adjacent portions of the surface So.
Subsequently, in step 1432, the additional new markers and optionally, their
corresponding isocline handles and ribbon
tangents, ate graphically displayed to the user.
Note that it is not necessary for steps 1408 through 140, and steps 1424
through 1432 to be performed sequentially.
20 One skilled in the art of computer user interface design will understand
that with event driven user interfaces, the processing of
each new marker can be performed individually and displayed prior to obtaining
a next new marker location from the user. Thus,
CA 02379459 2002-07-09
wo ouusioa Nc~r~US~~ncHaa
4 F3
consecutive executions of the steps 1408 through 1420 may be interleaved with
one or more executions of the steps 1424 through
1431.
In step 1436, a determination is made as to whether an isodine handle and/or a
ribbon tangent is selected by the user
for modification. Note that the identifier, ISO, will be used to denote the
isocline handle and/or the ribbon tangent to be modified.
In step 1440, the marker corresponding to ISO is determined and access thereto
is provided via the variable, MRKR.
Subsequently, in step 1444, the collection of one or more subsurfaces
5;,...,SN adjacent to MRKR are determined and access to these
adjacent subsurfaces is provided by the variable, ADJ SURFACES.
In steps 1448 through 1460, boundary representations of portions ofthe
subsurfaces, S;, adjacent MRKRare determined
(step 1452) and inserted into a collection of surface boundary representations
denoted MOD. SET (step 1456). In particular, for
I 0 each of the subsurfaces in ADJ SURFACES, a data representation of the
boundary of the smallest portion of the subsurface that
is adjacent to MRKR that is bounded by isodine ribbons is entered into the
set, MOD SET.
Finally, in step 1464, the program of fig. 30 is invoked for modifying, in
real-time as the user modifies ISO, the portion
of Sp within the boundary representations contained in MOD-.SET. In
particular, the program of Fig. 30 is invoked with the values,
MAKR and MOD SET.
I 5 In the flowchart of Fig. 30, the high-level steps are shown for modifying
in real-time the surface portions identified
by the surface boundary representations in MOD SET, wherein these surface
portions are adjacent to the marker, MRKR.
Accordingly, in step 1504, the first (ncxtj modified version of the isocline
handle and/or ribbon tangent corresponding to the
marker, MRKR, is obtained and assigned to, ISO. Subsequently, in step 1508,
all isacline ribbons containing the modified isocline
handle and/or ribbon tangent of ISO are regenerated to reflect the most recent
modification requested by the user. Note that this
20 is performed using the one-dimensional version of formula ( I ), and
modifying each such isocline ribbon along its extent between
MRKR and the adjacent markers on each isocline ribbon containing MRKR.
CA 02379459 2002-07-09
WO 1»108102 P~CT/US991168d4
~g
Subsequently, in step 151, the first (next) boundary representation in MOD SET
is assigned to the variable, B. Then
in step IS 16, the set of isocline ribbons for the (profile) boundary segments
contained in B are assigned to the variable, R. Note
that Rincludes at least one isocline ribbon containing the marker, MRKR.
In step 1520, a blended surface is generated that is delimited by the profiles
of the isocline ribbons of A. The formula
used in this step is similar to Formula (4). However, there are additional
functions, Q;(p}, provided in the present formula. Note
that, in general, the portion of a parameter space used in generating the
surface, S(p), of this step may have two, three, fourN
five or more sides (profile pre-images) that also have isocline ribbon pre-
images. Thus, translation functions, Q;(p), for each
isocline ribbon ~ of I~ wherein for the points p in the parameter space that
are in the interior, I, to the pre-images of the profiles,
P;, for the isoclines Ry of ~ it is desirable that these points p be
translated into points in the parameter space for R; so that a
I 0 corresponding point in the object space of the isocline ribbon R; can be
determined and used in the blending function of the
present step. Note that the translation functions, Q;(p), preferably satisfy
at least the following constraints:
(a) Q;(p) is a continuous function far continuous surfaces;
LIMIT
(b) P-'Q;n~~~ 0) ~QiIP?~ - cu,0~
That is, when a sequence of points in I converges to the pre-image of the
profile point P;(u), then Q;(p) converges to the isocline
f 5 ribbon parameter space paint (u,0).
Subsequently, in step 154, the surface S(p) is displayed, and in step 1528 a
determination is made as to whether there
is an additional boundary representation in MOD'SET for generating an
additional blended surface S(p). If so, then step 151
is again performed. Alternatively, if there are no further boundary
representations, then in step 1532, a determination is made
as to whether there is an additional user modification of the isocline handle
and/or ribbon tangent corresponding with MRKR.
20 If there is, then at least the steps 1504 through 158 are again performed.
Note that the steps of fig. 30 can be sufficiently
CA 02379459 2002-07-09
WO 011081(12 P~T/US99/118:44
', 0
efficiently performed so that incremental real-time changes in the isocline
handle and/or ribbon tangent for MRKA designated
by the user can be displayed as the user continuously modifies this isocline
handle and/or ribbon tangent.
4. A Geometric Design User Interface
The general principles described above form a basis for
a novel user interlace for computer aided geometric design.
In one user interface embodiment for the present invention, a user interface
may be provided for defining isoclines.
Using such an interface, a designer may, for example, require that an isocline
be perpendicular to a given fight direction along
an entire profile curve so as to create a reflection line, as one skilled in
the art will understand. More generally, the novel user
interface may allow for various constraints to be input for generating isodine
ribbons, isocfine handles and/or ribbon tangents
I 0 that satisfy such constraints. In particular, the user interface allows
for global constraints such as light direction, curvature,
tangency, level comours, dihedral angle funaions with a plane, etc., as one
skilled in the art will appreciate.
In one embodiment of the user interface, the user wilt start with a given
geometrit object, far example a cylinder. The
user may then inscribe a profile curve on the cylinder by placing markers at
various points on the cylinder. The profile tangents
and/or isocline handles may be defaulted by adopting the slope information
from the qiinder. For example, at each marker; the
I 5 profile tangents are in the plane tangent to the cylinder at the marker.
The user may then select and modify the markers, add additional markers,
and/or modify the position and the direction of the
isodine handles and/or ribbon tangents. As the isocline ribbon is accordingly
modified, the cylinder (mare generally, geometric
object) will reflect the changes in the modification of the isocfine ribbon.
Additional profiles and markers may be added in this
manner until the desired shape of the geometric object (derived from the
cylinder) is obtained. An example of these steps is
20 illustrated in the flowchart of fig. 31. That is, the user selects a
graphically displayed surfaee (more generally, geometric object)
in step 1904. Subsequently, in step 1908, the user constructs a profile curve
on the selected surface (object).
Subsequently, in step 1912, an isocline ribbon (or at least the isocline
boundary) is generated for the profile. Note that
this ribbon/boundary can, if desired, 6e generated substantially without
additional user input. That is, an isocline
CA 02379459 2002-07-09
WO 01/118102 ~'CT/US99/168:1:1
JI
ribbon/boundary may be generated from the tangency characteristics of the
surface upon which the profile resides. In particular,
for a parametric surface (more generally geometric object}, the parametric
tangents on the surface at points on the profile can
be utilized to generate an isodine ribbon/boundary for the profile. Thus,
surface neighborhoods on one side of the profile curve
may be used to determine a first isocline ribbon/boundary for a first surface
having the profile, and if the profile is on the seam
between the first surface and a second surface, then surface neighborhoods on
the other side of the profile may be used to
determine a second isodine ribbon/boundary.
Additionally, note that other surface characteristics may be preserved in an
isodine ribbon/baundary. for example,
in addition to preserving the parametric tangents at profile curve points, the
isocline ribbon/boundary may also optionally
preserve the surface characteristics such as curvature, high order ( > =2)
derivative continuitywith the surface. Note, however,
I 0 it is within the scope ofthe present invention that further surface
characteristics can be preserved in the isodine ribbon/boundary.
In step 1916, the generated isodine ribbon/boundary may be used to modify the
surface{s) having the profile curve
as discussed hereinabove with reference to the programs of the flowcharts of
Figs. 29 and 30.
In some embodiments of the user interface, an operation is provided to the
designer wherein a common boundary
between two object space surfaces can be selected and the operation
automatically forces the surfaces to join at a higher order
I 5 continuity criteria (e.g., curvature continuity) than that of tangent
plane continuity. For example, a higher order continuity
constraint imposed on an isodine ribbon deriving from one of the surfaces at
the common boundary, can be used to similarly
constrain an isodine ribbon for the other surface haring the common boundary.
Accordingly, this operation helps alleviate the
so-called "Mach band" effect in which the human eye deteas discontinuities in
curvature m some instances.
Other user interface operations provided by the present invention are:
20 (a) Rounde~iz~irg, which is a tweaking operation that modifies an existing
surface to round off painted edges,
or to create darts (i.e., surfaces that are smooth except at a single point,
where the surface kinks) that dissipate sharp
edges. Such operations can be performed using the present invention by
position=ing profile curves an the surface on
CA 02379459 2002-07-09
WO ()1108102 1'CT/US99l1G8d4
opposite sides of a sharp edge and blending smoothly between the profiles
(e.g., using formula (I) as described in
Section 1.3.5; and subsequently eliminating the surface in between the profile
including the sharp edge.
(b) fmbeddng, which is an iterative user interface procedure that can take one
finished model, scale it, and
perhaps rotate or otherwise deform it to fit into part of another model.
S 4.1. Defining the Isocline via Markers, Profiles and the User Interface
Explicit profiles are the profile curves that express a designer's intent.
Explicit profiles may be unconstrained
(freeform) or partially constrained (trim). Implicit profiles may be visible
boundaries between surface patches caused, for
example, by a surface discontinuity (i.e., a kink or curve defined between an
end surface of a rylinder and the cylindrical side
thereof).
I 0 Implicit profiles are created automatically when the user introduces,
e.g., a surface discontinuity. All profiles in a
model are either explicit or implicit.
4.1.1 Creating Markers
Profile markers and handles are created in the following ways:
A. Markers are automatically created at the ends of new implicit and explicit
profiles.
I S B. Inserted by a designer (e.g., by double clicking at a point) on an
explicit profile. To the designer, he/she
is inserting a point on the profile. The newly placed marker only minimally or
not at all changes the shape
of the profile in the profile segment containing the new marker. Subsequently,
profile and isocline handles
are determined according to the shape of the profile and surfaces) attached at
the new marker.
A marker may be identified with a plurality of coincident points on the same
profile (e.g. a profile that loops back and
20 attaches to itself). Such an identification of the marker with the
plurality of profile points cannot be broken, except by deletion
of the marker. In the case of two or more profiles meeting at a common point
having a profile marker, such profiles each have
CA 02379459 2002-07-09
WO !)1108102 IvCT/US99/1684-t
'~ 3
a marker at the common point and the markers are constrained to maintain
coincidence so that moving one marker will move
both.
Profile markers inserted by the designer may be inserted for providing profile
handle points, or for setting specific
isocline values. Note that a profile handle point may have a set of
constraints on its isocline handles; i.e., isodine handle may
inherit value{s) by an interpolation of the nearest two adjacent isodine
handles.
4.1.2. Viewing Markers and Profiles
Profile and isodine handles may have various constraints placed upon them,
wherein these handles may be displayed
differently auording to the constraints placed upon them. In particular, the
following constraints may be placed upon these
handles:
I 0 (a) constrain a handle to a particular range of direaions;
(b) constrain a handle to a particular range of magnitudes;
{c) constrain a handle to lie in a plane with other handles;
{d) constrain a handle to a particular range of curvatures;
(e) constrain a handle with a transform of another handle, e.g., identical
rotations and/or translations.
I 5 the designer can choose to display the constraints through a display
request for the properties of geometric objects. In one
embodiment,differentcalorsmaybedisplayedforthedifferenttypesofconstrainedprofil
emarkers. forexample,handleshaving
no variability (also denoted herein as "fully constrained") may be displayed
in blue.
In some embodiments of the user interface, vectors are "grayed out" that are
constrained to thereby demonstrate to the designer
that such vectors cannot be changed. for example, in one embodiment, fully
constrained handles are typically grayed out.
20 4.1.3 Connecting Profiles Together
In one embodiment of the user interface, it supports the linking together of
two or more profiles that intersect at the
same X,Y,Z location. Such intersection points are denoted "tie points," when
the parameterization of the point on each profile
CA 02379459 2002-07-09
W O Il1 /U81112 t'CT/U 599/ 16844
54
is invariant under profile modifications. Note that such tie points may or may
not have markers associated therewith. When such
a tie point is modified, all corresponding profile curve points associated
therewith at the tie point are modified as a group. Such
a tie point may be an endpoint of a profile or an internal (ne. "knot") point.
Alternatively, a profile marker of a first profile may be constrained to lie
within the object space range of a second
profile (either implicitly or explicitly). Far example, referring to Figs. 42A
and 42B, the user interface may provide the user with
the capability to slide a profile marker 2002 (contained on a first profile
2003 and a second profile 2004) along the second profile
2004 for thereby changing the profile 2004 of Fig. 42A into the profile 2004
of Fig. 42B when the marker 2001 is slid along the
profile in the direction of direction arrow 2006. Such a slidable marker 2002
is denoted as a "slide point."
Profile intersections are either "slide" or "tie" points. Moreover, these
different types of points may be distinguished
I 0 graphically from one another by different colors and/or shapes. Note, if a
profile slides along another profile, and the isocline
ribbon for the sliding profile is used to compute a blended surface, S, then S
will be recomputed.
4.1.4 Creating Markers and Profiles
The user interface may support the creation of a profile curve in a number of
way:
A. Sketch the profile on the surface similarly to the data driven technique a(
Figs. 28, wherein additional
I 5 markers may be provided for tying the profile to the surface within a
predetermined tolerance. Alternatively, in a second
embodiment, a profile can be sketched across one or more surfaces by having
the user selen all markers for the pro(iie. Note
that in either case, a profile may be sketched across one or more surfaces.
Moreover, in the second embodiment, the user interface
supports the following steps to successfully create a profile
(AI) Marker points are specified which lie an the surface(s). A fitted curve
is generated through the points in
20 parameter space and then this fitted curve is evaluated to obtain a
corresponding image curve in object space.
(A2) For each surface that the new profile crosses, the user may specify the
profile type (freeform or trim) for
the portion of the profile uossing the surface. A profile sketched on a
surface either trims one side of that surface or splits that
CA 02379459 2002-07-09
wo onos~oa rc~rius<rm~sa.~
surface into two new surfaces. Accordingly, note that any (non-degenerate)
profile that enters the interior of a surface must cross
the surface's boundary at an entering point and an exiting point. That is; the
two surfaces along a common profile boundary are
always finked to the profile, wherein, with respect to this profile, these
surfaces may be characterized as follows: (a) one surface
is a trim surface and one is a non-trimmed surface (also denoted a "freeform
surface"), or (b) two freeform surfaces.
B. Copy a Profile: A designer selects a profile to copy. The profile is copied
to a buffer (denoted a clipboard).
The user then selects the mode of copy (examples: keep profile handles, or
adapt profile handles to the geometrywhere the profile
is to be copied). The user selects where to position the new profile (which
may be additionally scaled, rotated, andlor mirrored,
etc). The user selects a location for the new profile. Note that the new
profile can be constrained by constraints on the original
profile. for example, the new profile may be mirrored abouta plane from an
existing profile, such that any change to the original
I 0 profile will result in a change to the copy. When a new profile is
created, profile markers are automatically generated
at both ends of the new profile. Profile handles and isodine (ribbon tangent)
handles are derived from the geometric
characteristics of the surfaces that the new profile splits.
4.1.5 Modifying Markers and Profiles
Modification of markers and/or (profile, isodine) handles is dependent on the
constraints placed upon the markers
I 5 and/or handles. They may be constrained in one of the following ways:
A. Interactive modification by selecting a handle (profile or isodine) at a
particular marker, m, and moving
the handle endpoint so that it is constrained to lie in a normal plane, i.e.,
either a plane normal to a surface having a profile
containing m, or a plane defined by the isodine and profile handles of the
profile at m. A pop-up property sheet is also available
for the user to key-in specific numerical values for magnitude and angle for
modifying a selected profile and/or isodine handle.
20 B. far markers that are constrained so that their pre-images lie within the
pre-image of a profile, the marker
will may slide along such a parent profile via, e.g., interactive modification
by dragging such marker points. Note that for
positi0nal unconstrained markers, the marker points may be moved freely (i.e.,
under a user s direction and without other
CA 02379459 2002-07-09
WO tlllf181(12 PC'T/11599/168~d
56
restrictions) along the parent profiles) upon which such markers reside.
Additionally, note that the user can select multiple
profile marker points by clicking on each, or by selecting ail markers within
a designated region (e.g., bounding rectangle).
Accordingly, the user is able to move a display pointing dente (e.g., a mouse)
which will then cause all of the selected markers
to uniformly move in a corresponding direction to the movement of the display
pointing device. However, movement of the
markers depends on the constraints set on these markers. for example, a
constrained marker will only move within the limits
placed upon it. Thus, if a first selected marker moves only within a first
profile and a second selected marker only moves within
a different second profile oriented orthogonally to the first profile, then
depending on the direction of movement desired, one of
the following occurs:
(f) the first marker is able to move, but the second marker can not;
I 0 (ii) the second marker is able to move, but the first marker can not;
(iii) both the first and second markers are able to move;
(iv) neither marker may be able to move.
C. Marker and handle constraints may be set by default rather than exploitly
by the user. A pap-up property
display form allows the user to set or remove specific constraints. D.
Additional constraints on profile and/or
I 5 isocline handles may be set that are dependent on the characteristics of
other geometry. for example, profile and isocline handles
can be constrained to be normal or parallel to a selected reference plane.
Note that the position of a profile marker also can be
constrained to be dependent on characteristics of other geometry. for example,
a marker can be constrained to lie on a parting
plane. That is, a plane of front/back symmetry for designing a bottle. Another
example of these constraints is in generating
symmetric designs, i.e., a profile marker copy that is reflected about a
parting plane will be constrained to be symmetric to the
20 parent profile marker.
CA 02379459 2002-07-09
WO 1)1/(181(12 1'CT/US99/1(8:1:1
57
E. Surfaces adjacent to a profile may have to satisfy either C0, CI, or C2
continuity, wherein CO is positional,
CI is tangency, and C2 forces smooth surface blends. One constraint that can
be set on a marker is to force CI continuity between
surfaces surrounding the marker by maintaining equal length tangent vectors
interior markers.
Freezing (eliminating the ability to modify) the profile and isodine handles
at a marker will cause the profile segment
containing the marker to rebuild based on the profile handles of the next two
closest markers, effectively changing this marker's
handles to reflect the curve built by the two markers on either side.
For the most part, modifying profiles is a function of user interface
techniques for modifying the profile marker
positions and handles that control the shape of the profile. The following are
examples of such user interface techniques.
A. Direct method: Profiles are modified directly on an object space (3D)
model. This is done by modifying the profile
I 0 markers and handles that make up the profile.
If the designer modifies a trim profile, the profile always laes within the
parameter space of the surface it is trimming.
That is, the trim profile needs to be modified in the context of its original,
overbuilt surface within which it is embedded. Selecting
a trim profile (or one of its components) to modify causes the overbuilt,
construction geometry to be highlighted. It remains
highlighted while the user is modifying the trim profile.
I 5 A designer may have the option to turn on profiles and modify them using
the direct method. For example, modifying
a profile that defines an overbuilt surface will cause the overbuilt surface
to be updated. Since the profile that trims this overbuilt
surface is constrained to lie within the parameter space of the surface, the
trim profile is also recomputed.
B. Design Ribbon method: This method is used to modify a specified region of a
profile. It allows, (or example,
the user to simplify the designer's interactions by modifying a profile in one
view that is complex in another view. The designer
20 identifies two markers that lie on the same profile. The profile segments)
between the two markers are extruded in at least one
graphical view of the profile, thereby creating a design ribbon (not to be
confused with an isocline ribbon). The design ribbon
is a simple extruded surface {i.e., a curve which is swept along given
directions to generate a surface; for example, for markers
CA 02379459 2002-07-09
WO 01108102 1'CT/1;599/168=to
5th
at the ends of a profile, offset the corresponding profile handles by their
corresponding isocline handles to obtain boundary
handles and interpolate an isocline boundary, e.g., by a lower dimensional
version of Formula (2); the surface having a perimeter
consisting of the profile, the isacline handles, and the isocline boundary
defines the new extruded surface). The three-dimensional
profile segments identified between the markers always lie within the pre-
image of this design ribbon. The user modifies the
profile in one of two ways:
(BI) Modify the two-dimensional driving curve from which the design ribbon was
extruded, and which is instanced
at the end of the ribbon, wherein, by default, this curve is a two-dimensional
representation of the three-dimensional
profile segments defining the design ribbon. The user may "simplify" the
driving curve by selecting a subset of the two-
dimensional points. Each time the user modifies a driving curve point, the
ribbon is updated and the three-dimensional
I 0 profile is modified to lie within the parameter space of the modified
ribbon. Operations on the driving curve include
any of those listed in the Profile Marker section (pointlslope modification,
insert, delete, etc.).
(B2) Modify the two-dimensional profile points within the design ribbon. The
user directly modifies the two
dimensional profile in a view that is perpendicular to the primary view. The
two-dimensional points always lie in the
parameter space of the ribbon. Operations include any of those listed in the
Profile Marker section (point/slope
I S modification, insert, delete, etc.).
Only one design ribbon may exist per surface per profile segment. Design
ribbons may be created, modified, and
deleted. Once they are «eated, they are persistent, i.e. they remain
unmodified until a designer modifies the same segment at
a later point in time. A design ribbon is displayed only when a designer is
modifying it. A single profile may have multiple
ribbons corresponding to multiple surfaces containing the profile.
20 Note that modifying a profile using the direct method deletes any design
ribbons spanning the points being modified.
This invalidates the ribbon and requires a designer to re-specify the ribbon.
CA 02379459 2002-07-09
WO ()1J08102 t'CT/US99/168d.1
59
C. Move Profiles}: The designer selects and moves two or more profiles in
unison. That is, this user interface
command selects all of the profile markers on a profile (or segment thereof
and moves them together as a unit.
D. Merge Profiles: The designer may sketch a new profile and attach it to an
existing profile so that an endpoint
of each profile is coincident. Additionally, the designer may specify which
segment or segments of the existing profile
to delete. Subsequently, the new profile and the remaining connected portion
of the existing profile having the
coincident end point with the new profile are merged. Note that merging
profiles causes the set of the respective profile
handles, isocline handles and ribbon tangents for each of the two coincident
endpoints to be combined into a single
such set.
E. Split profile: Split one profile iota two at a single point, p. An endpoint
of each of the two new profiles is
I 0 constrained to be coincident at p.
4.1.6 Deleting Markers and Profiles
Deleting a profile marker is always possible, except at the endpoints of a
profile. However, in some embodiments of
the present invention may need to replace a marker with a marker having
constraints if it is needed for maintaining smooth
patches. Note that a new constrained replacement marker may or may not be in
the same location as the previous marker.
I 5 If an entire profile is deleted, then the user interface both highlights
any dependent geometric objed(s} and requests
user confirmation before deletingthe profile and the dependent geometric
objects}. Accordingly, note that the present invention
retains sufficient dependency information regarding dependencies between
geometric objects in a model so that for modifications
of an object that is used for deriving other objects, appropriate additional
modifications can ae performed on these other objects
automatically.
20 4.1.7 Profile Markers and Handles
Note that there are typically two profile handles, two isocline handles and
two ribbon tangents for a profile marker,
i.e., a profile handle, an isodine handle and ribbon tangent per surface on
each surface having the profile as a boundary curve.
CA 02379459 2002-07-09
WO 011118102 F'CT/US99/16844
6C
However, there may be more handles associated with a profile where several
profiles converge or fewer if the profile is the edge
of a surface.
4.2 Isoclines and the User Interlace
The slope of an isodine handle controls surface tangency at a marker and at a
surrounding portion of the profile
S containing the marker. The magnitude of an isodine handle controls the
fullness of the dependent surface. That is, how much
the surface bellies out. An isodine handle may be constrained to be offset
from another isotline handle (i.e. -10 degrees from
other side). An isodine handle can be calculated at any point along a profile
(by inserting a marker on the profile).
4.2.1 Creating an Isocline Handle
The user interface supports the constraining of isocline handles relative to
one another. Such handles can be forced
I 0 to always be tangent, of equal magnitude, or offset by some amount. In one
embodiment of the present invention, the user
interface provides a pop-up menu to display and change isodine handle
constraint values, such as length and direction.
4.2.2 Modifying an Isocline Handle
If the user slides a profile marker along a profile, the user may fix the
isodine handle for the marker, thereby causing
the surfaces adjacent to (and dependent upon) the profile to change or have
the isodine handles interpolated between the nearest
I S two isocline handles on the profile (which case implies that the dependent
surfaces are not affected;!
4.2.3 Deleting an Isocline Handle
The user interface supports the deletion of isocline handles. The following
steps apply when deleting an isodine.
4.3 Special Geometric Objects and the User Interface
The present invention provides for the «eation and manipulation of a number of
specialized geometric object types
20 that can substantially facilitate the design of objects such as containers.
4.3.1 Label Surfaces
A label surface is a special case of a trimmed surface. The special case
aspects of a label surface are:
CA 02379459 2002-07-09
WO Ol/IIR102 F'CT/US99/168~t.1
hl
(i) there is a "watershed" profile that runs from the bottom to the top of the
label;
(ii) there are label curves between which the corresponding label surface is
ruled (e.g., label curves 132 of Fig.
(iii) there is a boundary (trim) profile (e.g., trim profile 138 of Fig. I I).
The key difference that makes a label surface different from other trimmed
surfaces is that the original surface (from
which the label surface is trimmed) is a ruled surface. In particular, the
label surface defining curves are constrained such that
a ruled surface is maintained within the boundary of these defining curves.
Note that other surfaces may be blended to a trim profile for a label, but the
trim profile can only be modified in a
manner that insures that it bounds a ruled surface.
I 0 In one embodiment of the present invention, a two dimensional "rolled out"
representation of the label surface can
be generated. That is, the surface can be associated in a one-to-one fashion
with the plane by rolling it flat. Such a representation
simulates a label surface in which a designer can thereon create a piece of
artwork that c:an subsequently be wrapped on a
container. 43.1.1 Creation of a Label Surface
To create a label surface, an overbuilt surface to be trimmed must be a ruled,
approximately developable surface, i.e.,
I S a ruled surface in which all surface normals on any ruling are parallel.
Subsequently, the user then follows the normal trim
surface steps; i.e., sketching a profile on the ruled surface, generating the
(sub)surfaces on bath sides of the profile (i.e., the label
surface and the portion of the surface to be trimmed away)" trimming the label
surface and blending other surfaces to the trim
profile.
Note that the trimmed away surface portion is hidden from normal viewing
(i.e., it is no longer a part of the visible
20 model).
The following procedure may be provided for generating a label surface. At a
high level, the steps for this procedure
are:
CA 02379459 2002-07-09
WO 01/1)8102 1'CT/US99/lfi8d4
Fi ~
(i) Make sure the surface is ruled. That is, the user interface supports
automatic modification of user selected
profiles so that these profiles satisfy 4.3.1(i) and (ii). In particular, to
perform this step, the following
substeps are performed:
(ii) The user sketches a boundary profile on the surface defining the bounds
of the label;
(iii) Construct a graphical representation of a label (i.e., a ruled surface
having text, artwork, and/or designs thereon);
(iv) Allow the user to graphically apply the label representation to the kabel
surface (or a representation
thereof). In particular, the user interface for applying the label
representation may automatically attach
the label representation to the label via a groupng type of operation so that
the label representation
maintains its position on the label surface during, e.g., label surface
rotations, translations, scaling
I 0 operations, etc.;
(v) Allow the user to undo the design when the label surface and/or the label
is not satisfactory.
4.3.1.2, Modification of a Label Surface
Modification of the label surface components is somewhat different than those
of a trimmed surface.
The portion of the watershed profile that is a straight line segment is
constrained to remain straight.
I 5 The boundary opposite of the watershed (the "other side, of the parent
ruled surface) cannot be modified. It is simply
astraightlinesegmentbetweenthetopandbottom boundaries. The top and bottom
boundary profiles can be modified.
They are constrained so no additional tree profile markers can be inserted on
them. Also, the profile marker at the end away from
the watershed is constrained to move only to maintain a ruled surface. It can
be extended (extrapolated along the same
curvature) and the angles at its endpoints can be adjusted - again, as long as
it maintains a ruled surface.
20 4.3.1.3. Deleting of a Label Surface
Deleting a label surface removes the constraints on all of the profiles used
in creating the label surface. Additionally,
all of the construction geometry for the label surface that is invisible to
the user will also be deleted. The constraints for
CA 02379459 2002-07-09
WO (11/118102 F'CT/US99/lCB:ld
maintaining a ruled surface will also be removed. Thus, the remaining
geometric objects are then freed from the label surface
constraints, and can be modified in ways not previously available.
4.4. Hole Tool User Interface
The present invention may also provide a user with a novel computational
method that helps the user add a hole to
a geometric model (such as for adding a handle to grasp to a non-handled
bottle). The information required to add a hole to
a model using this procedure includes: a loop of profile segments on a front
surface, a loop of profile segments on an opposite
back surface, the type of each profile in a loop of profiles (freeform or
trim), and optional profiles) to shape the interior of the
hole.
4.4.1. Creation of a Hole
I 0 The hole creation tool guides the user through a series of steps to add a
hole. figs. 22A-22C illustrate the procedure
for creating a hole 600 (Fig.2~C) on a geometric object 604 using the present
invention. The corresponding steps performed far
creating the hole 600 are as follows:
(a) Sketch a profile loop 608 on the front surface d12;
(b) Sketch a profile loop 616 on the back surface (optionally project the
profile 608 to the back surface).
I S Note that isocline handles are automatically placed on both profiles 608
and 616.
(c) If one or more of the profiles for one of the profile loops 608 and 616
are freeform profiles, then the user
may add new profiles (to complete such a profile loop), and/or profiles merge
correspondingto such a loop
whereby these profiles are constrained so that they are utilized as if they
were a single profile. Accordingly,
once the profile loops are constructed, then surfaces may be skinned between
the loops to thereby replace
20 the original surface occupying the hole.
If a trim profile loop is specified, the surface region inside the profile
loop is trimmed.
CA 02379459 2002-07-09
WO ()1/081112 PCT/h'S99/1684.1
If specified, the hole creation procedure uses additional profiles to place
and shape surfaces on interior boundaries for
the hole. Otherwise, surfaces are skinned automatically between the front and
back profile loops.
4.4.2. Modification of a Hole
Modifying a hole is a function of modifying profile markers and handles that
make up the geometry of the hole.
4.43. Deleting of a Hole
Deleting a hole is also a function of deleting the components that make up the
geometry of the hole; i.e., profiles and
other geometry for the hole.
4.5. Smoothness Considerations via the User Interface
We consider the order of transition between adjacent surfaces (which meet at
the profiles). This section does, however"
I 0 contain some broader implications for the general theory in Section 2.
4.5.1. Continuous Profiles via the User Interface
Given two profile curves that intersea, derivative continuity across an
intersection point may be assured if several
conditions are met:
(a) an end point of one profile is coincident with an end paint of the other
profile (positional continuity);
f 5 (b) the blending functions B; used in generating the profiles (as per
Figs. 26 and 27) are equal at the
intersection marker; and
(c) the profile handles at the intersection marker are collinear and equal
length.
Tangent directional continuity is a weaker condition that can be satisfied if
condition (c) above is changed to:
(c"') the profile handles at the interseaion marker are only colinear. The
magnitudes of the profile handles may differ
20 in this Case.
The designer may intentionally produce a kink at a marker by breakngthe
collinearity of the two profile handles at
the intersection marker. This means that the two profile handles do not have a
common direction.
CA 02379459 2002-07-09
WO (11108102 PCT/lS'l9/168:1~
F5
4.5.2. Continuous Surfaces
The notion of tangent plane continuity between surfaces may be defined as
follows: for each point p of a boundary
between two surfaces S, and St, the tangent plane, T,(p), of S, at p is
identical to the tangent plane, T~(p), of Sl at p. To achieve
tangent continuity between surfaces across a profile boundary therebetween, it
is necessary that the isocline handles (for each
of the surfaces) at each marker on the profile boundary lie in a common plane
with each other and the profile handle at that
marker. If this is not done then a kink in the surface along the profile will
be created.
Note that when there are two or more surface patches to be generated wherein
these patches must be constrained to
meet at a common marker point, p, the present invention may automatically
generate isocline handles, denoted "common
direction handles." That is, for each profile, P (having p) used in defining
one or more of the surfaces, there may be a
I 0 corresponding automatically generated common direction handle which is a
vector, V, oriented from p, wherein Y is perpendicular
to the profile handle of the profile P, this profile lying in the common plane
formed by the profile handles for the other profiles
also having the point p. Further note, the user interface supports allowing
the user to either display or not display the common
direction handles.
Note that it is not necessary to have profile handles and isodine handles that
match for profiles that adjoin at a
I 5 tomrnon marker in order to achieve smooth surfaces there, only that they
all lie in a common plane. In fig. ( 8, there are three
profile curves 404, 408 and 412 for the surfaces 416 and 418. Each of the
three profile curves meets at the profile marker 420,
and each of the profiles has a corresponding isodine ribbon 424 (for profile
404), 428 (for profile 408), and 432 (for profile 412).
Additionally, the profile and isocline handles associated with the profiles
404, 408 and 412 and the marker 420 are:
(i) profile handle 436 and isocline handle 440 for profile 404;
20 (ii) profile handle 444 and isocline handle 448 for profile 408;
(iii) profile handle 452 and isodine handle 456 for profile 412.
CA 02379459 2002-07-09
wo ouastoa t'cTUs~mt~sa.~
E E;
Thus, if the profile and isodine handles 436, 440, 444, 448, 452 and 456 all
lie within the plane 460 (indicated by the dashed
rectangular portion), then the surfaces 416 and 418 smoothly loin at the
marker 420.
At any marker, two isocline ribbons are likely to meet in the way that two
profiles may meet, that is, two isocline
ribbons may have a common isocline handle as an edge for each of the ribbons.
To achieve tangent plane continuity between different (blended) surface
regions !i, and S, (Fig. 43) joined by a
composite profile, not only is tangent continuityacross profiles P, and Pi
needed, but tangent continuitybetween adjacent ribbons
R, and R~ is also needed. That is, for the profiles P, (between markers 2010
and 2014) and P~(between markers 2014 and 2018),
the respective ribbons R, and R~, when thought of as surfaces, must be tangent
plane continuous, and share a common isocline
handle 202. Note that in mast cases, tangent continuity between ribbons is
equivalent to tangent continuity between profiles
I 0 and tangent continuity between ribbon boundaries that is required for
smooth transitions across surface patch boundaries.
Moreover, the user interface of the present invention provides techniques for
assuring tangent plane continuity between ribbon
boundaries wherein these techniques are substantially identical to those used
for assuring tangent plane continuity between
profiles. Thus, the present invention can provide tangent plane continuity
between adjacent surfaces generated from isocline
ribbons according to the present invention.
I 5 In some circumstances, it is possible to break the continuity of composite
ribbons intentionally, thereby causing a
crease across the surface generated from the ribbons wherein the erease does
not correspond with a coincident profile along the
crease. However, in some embodiments of the present invention, an
iinpl~atp~oFle'can be created that is coincident with the
crease.
4.5.3. Curvature Continuity
20 The visual quality of a surface depends not only on tangent plane
continuity, but also on higher order derivatives. A
user can be acutely sensitive to discontinuous changes in surface curvature,
especially if the surface is rendered with specular
highlights or reflected texture mappings, which is common in simulating
realistic scenes. The user may perceive a distracting
CA 02379459 2002-07-09
WO 0111181112 1'CT/US99llfi84-t
visual artifact known as a "Math band." Accordingly, raising the order of
continuity between transitions to that of curvature
continuity ameliorates this.
Analysis has shown that the curvature of the surface defined by Formula (I) or
Formula (4) depends on the second
derivatives of the B; and the S;. The dependencies of the B; are non-trivial
and it is advantageous to choose the blending function'.
S so that their second derivatives are zero and let the surface functions S;
determine the curvature. The cosine squared function
of Section 2.1 fulfills this condition. There also exist certain quintic
polynomials that are satisfaaory. For example, the
polynomial B,(x) of Formulas (3.1).
If the curvature of a blended surface generated from Formula (I) or Formula
(;4) depends only on the S; (e.g.,
B;" = 0), it is then possible to raise the curvature order between the
bounding surface patches S; analogous to the methods in
I 0 the previous seaion for achieving tangent continuity. To do this, simply
define the corresponding profiles and isodine handles
so they match in their second derivative at each marker along the profile
boundary. Note, however, that each profile handle may
be considered as a linear function of one parameter and therefore has a zero
second derivative. Thus curvature continuity is
achieved; albeit by making the curvature across the profile "flat," i.e."
zero. This is useful at points where there is an inflection
point on the profile, but can be undesirable elsewhere. To rectify this
situation, the linear handles may be replaced with curved
I S r~bf such as parabolic arcs. Accordingly, the handles now become arcs, and
at the markers, the curvature is made to match that
of the given arc.
By extending the concept of providing a nonzero curvature to all handles,
e.g., profile, isodine and boundary handles,
along with the zero second derivatives of the blending functions and the
effects of the Mach banding can be mollified.
4.5.4. GI ContinuitX Using Roll, lfaw and Magnitude Representations.
20 The present invention also provides a user interface method to specify
handle veaars (e.g., isocline handles) relative
to a corresponding profile curve, wherein GI continuity (as defined in the
Definitions hereinabove) between surfaces joined
together by the profile is assured. This method, which is denoted herein as
the roll-yaw method, specifies a vector V in terms of
CA 02379459 2002-07-09
WO UI/0810Z PCT/LS991168d4
F~ 8
three scalar terms called roll, yaw and mag (magnitude), wherein roll and yaw
are determined at a point P on a curve using the
tangent vector T at the point P, and a vector N normal to the curve at the
point P. The yaw component of the vector V represents
the angular deviation from T at P. For instance, f( the vector V is in a
direction perpendicular to T, the yaw value (in at least one
framework) is 0°, and if the vector V at P is in the same direction as
T, then the yaw value is 90°. Regarding the roll component
of the vector Y, this scalar represents the amount of angular rotation about T
as the axis of rotation, and wherein the baseline
axis for measuring the angle is the vector N at P. Accordingly, the vector N
represents 0° of roll and the rotational range extends
from -180° to 180° using the right-hand rule, as one skilled in
the art will understand. Regarding the magnitude component of
vector V, this is simply the length of the vector Y. Note that any vector
expressed in terms of three-dimensional Cartesian
coordinates can be transformed one-for-one into the roil, yaw, mag notation
for a given T and N.
I 0 Note that the vector N may be selected from among vectors in the plane
normal to f. However, this does not precisely
define N. Thus, several methods may be used to define N. A first such method
for defining N is simply to choose a constant vector
YC and then determine N by the following equation: N =- T x VC. This method,
however, produces an undefined value for N when
T and VC are colinear. To provide values for N where this equation yields a
zero vector, N can be approximated in a topological
neighborhood of the colinearity. Alternatively, in a second method of
generating N, the frenet-Serrat frame of thevnderlying
I 5 curve may be chosen, as one skilled in the art will understand. However,
the Erenet-Serrat frame may be discontinuous at
inflection points along the curve. Accordingly, the present invention provides
a method for creating a minimally rotating reference
frame for a complex (i.e., three-dimensional) curve that obviates difficulties
in definingthe vector N regardless of the orientation
or shape of the curve and its tangent veetor T.
As previously mentioned the roll-yaw method provides a novel way to achieve GI
continuity across a profile. As an
20 example, consider the geometry illustrated in Fig. 44, wherein a profile P
along with left and nght isocline ribbons LR and RR arc
shown. Each of the isocline ribbons LR and RR has two corresponding isocline
handles at its ends, i.e., HLI and Hl2 for LA, and
HRI and HR2 for RR. Assuming the profile P endpoints have handles denoted HPI
and HPZ, for any point pp on the profile"
CA 02379459 2002-07-09
W~ f)llt)8102 !'CT/US99/1G8:J4
J
continuity across the profile for surfaces bounded thereby is determined by
the interpolated isodine values IL and IR. Further,
IR is interpolated (according to the techniques of the present invention) from
HRI and HRZ, and IL is interpolated from HLI and
HL2. Thus, one skilled in the art will understand that for G I continuity
across the profile P, IL and IR must at least be in opposite
(calinear) directions. Further, it can be shown by one skilled in the art that
if IR and Il are formed using a cubic Hermite
S interpolation between Hll and HL~ for IL, and, HRI and HR2 for iR that the
conditions for Gi continuity are that HLI and HRI
must be equal and opposite vectors. Further, the same must be true for HL2 and
HR2. However, if instead of interpolating the
isodine values IL and IR in Cartesian space, the interpolation is performed in
(roll, yaw, mag) space, GI continuity can be
achieved with a less strict condition, namely, that the roll value of Hll and
HL2 must be the same. Accordingly, this is equivalem:
to saying that HLI, HRI and HPI must be no more than coplanar (with the same
being true for H12, HRH and HP~) in order to
I 0 guarantee G I continuity everywhere on the profile P. Further, note that
similar conditions may be imposed if the isodine handles
are curved rather than straight. In particular, tangent vectors to the
isocline handles at their common points with the profile
P may be used in place of any corresponding isocline handle vector represented
in Fig. 44. Thus, as one skilled in the art will
appreciate, computational steps can be provided that embody the roll-yaw
method far, if necessary, converting from Cartesian
vectors to roll, yaw, mag vectors, and then assuring that the above described
coplanar constraint is satisfied for guaranteeing
I 5 that surfaces are GI continuous atross the profile P.
4.6. Embedding Models Within Models
The present invention allows parts of a surface bounded by profiles to be
designed separately from one another. For
example, a triangular portion of a surface may be designed as a free standing
surface model. That is, a designer may add profiles
and isodine ribbons as desired until a satisfactory design of the model is
obtained (using barycentric mappings as one skilled
20 in the art will understand). Afterwards this piece may be distorted,
rotated and fit into a triangular portion of another model.
Hence, a finely detailed model may be designed and embedded into another
model. By maintaining links this process can be used
CA 02379459 2002-07-09
WO 01/1)81(12 IP('T/US99/168~J4
7 c7
for level of detail management. That is, for example, when the model is viewed
from a distance, the detailed portion is unneeded
for display, but as the viewer moves closer the embedded object is linked in
for the extra detail it affords. Two examples of types
of embeddings follow in the next subsections.
4.6.1. A Rounderizing Technique
Referring to fig. 20, a small blended surface rounds an edge 482 between two
intersecting surfaces 484 and 486. This
blended surface 480 is blended from the thin surface strips 488 and 490 whose
pre-images are a "small" offset from the pre-
image of the edge 482 in parameter space. This process is a straightforward
application at Formula (I) where the two surfaces
484 and 486 are blended using their common parameter space (not shown).
The new surface types lead to new evaluation routines that are especially
efficient in special cases described.
5. Evaluation
We will first consider the evaluation of the two-edge blend, recognizing that
other farms derive from this fundamental
form. Because of its importance we will recall Formula (I), which is
S~u,v) _ Si(u,v) Bi(u,v) + St(u,r) B~(u,r). (I)
There are both blending functions B; and isodine ribbons S; to determine when
evaluating the surface S. The blending function
is calculated as a univariate function of distance in the parameter space. As
discussed in Section 1, the evaluation of the distance
funaion varies considerably depending on how complex the pre-image is in
parameter space. Once determined, the actual
blending value can be calculated by a simple table look up; thxt is, the
blending functions are tabulated to a sufficiently high
resolution and stored in memorywhere they can be indexed by the input
variable. Consider the function of B,(x) of Formula (3.1).
Evaluate this function at x = 0, .01, .02,..., 0.99, and I. These 1001 values
are stared as an array. When a point X is given, it
is used to locate the nearest point in the array, e.g., between .52 and .53.
Subsequently, B(.S2) or B(.S3) are used as the function
value.
CA 02379459 2002-07-09
WO O1/U81t12 I'CT1L1S99/1fi84~t
71
There are many techniques that may apply based on what the distance and
isocline ribbon functions are. The present
discussion is focused on a method that assumes a simple model computationally,
but nevertheless, retains considerable design
flexibility. The isocline ribbons 508 (S,) and 516 (St) will be given as in
Fig. 21. These are parameterized from 0 to I in both a
and r parameters. for each fixed value of v along the profile line 504, if the
corresponding picket on isocline ribbon 508 is a
straight line segment (e.g. line segment 512), the isocline ribbon is a ruled
surface as one skilled in the art will understand.
Accordingly, the parameter a provides a distance-like measurement along the
ruling where the point (u,v) is found. Assume that
each of the isocline ribbons 508 and 516 are ruled surfaces. further assume
that the pre-image of each of the profiles 504 and
506 in parameter space are the profiles themselves and the distance-like
measurement is the parametric a value of a point (u,vo)
on the va ruling of the isocline. Because the isocline ribbons 508 and 516 are
ruled surfaces, for the constant vv parameter we
I 0 can scan out a set of equidistant points along line segments S 11 and S~0
by simply adding the appropriate offset vector to the
previous value. The initial value is S;(O,va). The afiset vector is obtained
as
i,~_l~l(1,~~) ;;i.o,~~)11n, (1p)
where n is the number of points desired on the ruling line to scan from one
isocline ribbon (pre-image) edge to the opposing other
edge.
I 5 If we impose the restriction that the blendingfunctions are a partition of
unity, i.e., f3W 1 -Bz ~ which is desirable
from a design perspective, then the formula (I) yields
S(u,v)==(~;1(a,v)-S?(u,v)1'B~(u.m)+.'~?(u,v) (1l)
In one embodiment, this form and with the previous simplifications, it is seen
that each point requires three veaor adds
(for S,, St and the "+"), one table look up (for B,(u,v))and one scalar
multiply. This is after initialisation which consists of
20 finding each S;(O,v) and computing To, the offset vector (uswng formula
(10)). To scan out a set of points on S, one simply
increments through the parameter v, and then computes points along the rulings
in u.
CA 02379459 2002-07-09
WO OIIOSlll2 N('T/1:599/168=t4
72
In the case of the defined four-edge surface (as in Section 4.5.1 ), some S;
are as the two edge case above, but the others
blend longitudinally across the ribbon first. Specifically, in fig. 34 the v-
loft case is the same as Fig. 35 with re-labeling, while
the u-loft of fig. 34 is a horizontal blend of isodine ribbons. The four-edge
surface results from the barycentric blend of all four.
In Fig. 33, four profile curves P~" Pn, P" and PzI are shown between which a
surfate is desired to be placed. In fig.
33, the profiles P" and P,~ togetherwith their corresponding respective
isodine ribbons R" and R,l, are used to create the blended
surface S,.
While S, evaluates exactly as the two-edge case already described, the
generation of St (Fig. 35) differs because the a
and v parameters are reversed; In this case, the straight line segment on the
isoclines Ri, and A~1 corresponds to fixing a and
scanning in r; a situation which is incompatible to rapid scanning. However,
it is desirable to fix just one parameter and scan
I 0 the other in both Figs. 34 and 35. In one embodiment, this can be resolved
by defining the isotlines flyz and R~i differently. That
is, each such ribbon becomes a blend of two ruled surfaces defined by simple
user inputs. For example, consider isocline ribborr
R2,. It may be defined by blending two bilinear surfaces 1950 and 1952 in a
manner similar to the surface generation techniques
described in section 2.2 and illustrated in Figs. 37 through 39. That is, the
edges of the bilinear surfaces 1950 and 1952 that are
tangent on the profile Pt, are the profile handles 1956 and f 960; the
boundary handles 1964 and 1968 are tangent to the ribbon
I 5 boundary 1972 and form the opposite edges of the bilinear surfaces. The
other two line segmenu 1976 and 1980 are user inputs.
It is now possible to fix v in the second (u-loft) as well and scan by adding
a single vector offset. This effort produces
points on the isocline ribbons, St, and Stt, each at the identical cast of
producing points on the v-loft. Additionally, we must blend
the new points to compute the point on SE,. In operation counts, there are,
therefore, eleven vector additions, five scalar multiplies
and one table look-up. The additions include three for the v-loft, three each
for the u-loft isoclines, one far blending these
20 isoclines and one for blending the two lofts.
CA 02379459 2002-07-09
WO 111/(18102 I'CT/US99/1684~
73
for the general N-sided surface it is first necessary to compute a distance on
each ribbon. The parameters are
calculated using the N-sided parameterizatian technique from Section ~.~.
These distances are then plugged into the blending
funttions of formula (d). They are adjusted so they vary from 0 to I.
The parameters for the ribbons must be set from the distance so given. That
is, one parameter will be the distance
(from the profile). The other parameter can be deduced by determining where
the parameter line of Figure 12 crosses the edge
of the N-sided polygon. It is assumed that the polygon has edges of length I.
After these parameters are figured then Formula
(4) has all constituents needed for calculation.
6. Applications
The present invention may he used in a large number of computational design
domains. In particular, the following
I 0 list provides brief descriptions of some of the areas where the present
invention can be applied.
6.1 Container Design
Free-form design of containers such as battles has been heretofore non-
intuitive and tedious. The present invention
alleviates these drawbacks.
6.2 Automotive Design
I 5 In the automotive industry, the present invention can be used for auto
body design as well as for auto component
design. In particular, the ease with which deformations of parts and contours
can be performed with the present invention allows
for straightforward deformation of components and recesses so that the
fittingofcomponents in particular recesses is more easily
designed.
6.3 Aerospace
20 The present invention provides high preasion trimming and surface patching
operations which are required by the
aerospace industry.
6.4 Shipbuilding
CA 02379459 2002-07-09
wo nvostn2 ncTms~»in6sa~
~a
Unique to the shipbuilding industry is the need for the design of ship hulls
and propellers. Designs of both hulls and
propellers may be driven by the physics of the constraints related to water
flow. The satisfaction of suth constraints can be
incorporated into the present invention.
6.5 Traditional CAD/CAM Applications
Applications for the design of engines, piping layouts and sheet metal
products typically require trimming and blending
capabilities. Thus, since the present invention is particularly efficient at
providing such operations as well as providing easy
deformations of surfaces, its effectiveness in these areas may be of
particular merit.
6.6 Other Applications
The following is a list of other areas where the present invention may be used
for computational design. These are:
I 0 home electronic and appliance design, plastic injection mold design, tool
and die design, toy design, geological modeling,
geographical modeling, mining design, art and entertainment, animation,
sculpture, fluid dynamics, meteorology, heat flow,
electromagnetics, plasticsurgery, burn
masks,orthodontics,prosthetics,clothingdesign,shoedesign,architectural
design,virtual
reality design, scientific visualization of data, geometric models for
training personnel (e.g., medical training}.
The foregoing discussion of the invention has been presented for purposes of
illustration and description. Further, the
I S description is not intended to limit the invention to the form disclosed
herein. Consequently, variations and modifications
commensurate with the above teachings, within the skill and knowledge of the
relevant art, are within the scope of the present
invention. The embodiment described hereinabove is further intended to explain
the best mode presently known of practicing
the invention and to enable others skilled in the art to utilize the invention
as such, or in other embodiments, and with the various
modifications required by their particular application or uses of the
invention. It is intended that the appended claims be
20 construed to include alternative embodiments to the extent permitted by the
prior art.
