A Geometric Characterization of Parametric
Cubic Curves
MAUREEN C. STONE
Xerox PARC
andTONY D. DEROSE
University of Washington

In this paper, we analyze planar parametric cubic curves to determine conditions for loops, cusps, orinflection points. By expressing the curve to be analyzed as a linear combination of control points, it
can be transformed such that three of the control points are mapped to specific locations on theplane. We call this image curve the canonical curue. Affine maps do not affect inflection points, cusps,
or loops, so the analysis can be applied to the canonical curve instead of the original one. Since thefirst three points are fixed, the canonical curve is completely characterized by the position of its
fourth point. The analysis therefore reduces to observing which region of the canonical plane thefourth point occupies. We demonstrate that for all parametric cubes expressed in this form, theboundaries of these regions are tonics and straight lines. Special cases include Bezier curves, Bsplines, and Beta-splines. Such a characterization
forms the basis for an easy and efficient solution
to this problem.
Categories and Subject Descriptors:
G.l.l[Numerical
Analysis]:Interpolational-spline
piecework polynomial interpolations;1.3.5 [Computer
Graphics]:
Computational
Geometry
Object Modelling-curue,surface, solid, and object representations
General Terms: Algorithms,
Additional

and
and

Design

Key Words and Phrases: Bezier curves, characterization,

spline curves

1. INTRODUCTION
This paper describes a simple geometric method for determining whether aparametric cubic curve such as a Bezier curve, or a segment of a B-spline, has
any loops, cusps, or inflection points. We call this determination the characterization of the curve, and these properties the characteristics of the curve. A curvewith a loop is self-intersecting,one with a cusp has a point where the unit tangent
This work was supported in part by the National Science Foundation under grant numbers DMC8602141 and DMC-8802949, the Xerox Corporation, and the Digital Equipment Corporation.
Authors’ addresses: M. C. Stone, Electronic Documents Laboratory, Xerox PARC, 3333 Coyote Hill
Rd.; Palo Alto, CA 94304; T. D. DeRose, Department of Computer Science, FR-35, University ofWashington, Seattle, Wash. 98195.
Permission to copy without fee all or part of this material is granted provided that the copies are notmade or distributed for direct commercial advantage, the ACM copyright notice and the title of the
publication and its date appear, and notice is given that copying is by permission of the Association
for Computing Machinery.
To copy otherwise, or to republish, requires a fee and/or specificpermission.
0 1989 ACM 0730-0301/89/0700-0147
501.50
ACM Transactions

on Graphics, Vol. 8, No. 3, July 1989, Pages 147-163.

148

l

M. C. Stone and T. D. DeRose

B3
Arch

One inflectmn point

cusp

Two Inflectton pomts

Fig. 1. Cubic B6zier curves showing a loop, cusp, and inflection
B3 is moving.

Loop

points. Only the point

vector is discontinuous, and one with an inflection point has a point where thecurvature vanishes.
Characterizing
cubic curves has wide-ranging applications. For instance, innumerically controlled milling operations, many of the algorithms rely on thefact that the trace of the curve is smooth-anassumption that is violated if acusp is present. Inflection points often indicate unwanted oscillations in applications such as automobile body design and aerodynamics, and a surface thathas a cross-section curve possessing a loop cannot be manufactured.
In most applications, p.arametric cubic curves are expressed as linear combinations of control points and basis functions. Because the characteristics of thecurve do not change under affine transformations(the transformations
includingrotation, scaling, translation, and skewing), we can map the curve onto a canonical form so that the coordinates of three of the control points are fixed. As the
fourth point moves about the plane, the curve may take on a loop, a cusp, or zero
to two inflection points, depending only on the position of the moving points, as
shown in Figure 1. The plane can therefore be partitioned into regions labeledaccording to the characterizationof the curve segment when the fourth point isin each region, We show that the areas of the plane that define loops, inflection
points, and cusps are all bounded by straight lines and conic curves. The
simplicity of this form makes the characterization
efficient to compute.
Previous work in this area has been done by Wang [12], who produced
algorithms based on algebraic properties of the coefficients of the parametricpolynomial and included some geometric tests using the B-spline control polygon.
Su and Liu [ll] have presented a specific geometric solution for the Bezier
representation,
and Forrest [6] has studied rational cubic curves. This paper
presents a general method for making a geometric characterizationof a (nonrational) parametric cubic that can be applied to any representation that is a linear
combination of control points and basis functions. In Sections 3 and 4, we present
the construction of a characterization
diagram for Bezier curves. This diagram
is simpler than the diagra.m of Su and Liu and can be more efficiently implemented. In Section 5, certain degenerate cases are addressed. Armed with theintuition gained in Sections 3 and 4, in Section 6 we describe a simple generalprocedure for constructing
characterization
diagrams for cubic curves of any
type. This is done by showing that all characterization
diagrams can be obtained
from a two-dimensionalslice through a common three-dimensional
space.
The specific case for Bezier curves is presented before the general method
strictly for purposes of making the material more accessible to less sophisticatedACM Transactions

on Graphics,

Vol. E, No. 3, July 1989.

A Geometric Characterizationof Parametric Cubic Curves-

149

readers who wish to gain a better understanding of B&zier curves. More proficient
readers may therefore wish to read Section 6 before reading Sections 3 and 4.
2. BACKGROUND

AND PREVIOUS

WORK

The general representationof a parametric cubic polynomialconsists of afunction Q(t) = (X(t), Y(t)), where X(t) and Y(t) are each cubic polynomialsY”(t)). Such awith derivatives Q’(t) = (X’(t),Y’(t)) and Q”(t) = (X”(t),representation generally defines a curve of infinite length. To define a curve offinite length it is necessary to restrict the parameter t typically to the interval[0, 11. In this paper, we use the terms cubic curue, parametric cubic, or untrimmed
curve to refer to the infinite curve, and segment, cubic segment, or trimmed curve
to refer to a bounded curve.
The power basis representation for Q(t) is defined as
Q(t) = C aiti
i=OThis is a special case of a more general form where the curve is represented as alinear combination of control points and basis functions:

Q(t) = C Pidi(t),i=Owhere the Pi are the control points, and the d<(t) are the basis functions. Thisequation is often represented in matrix form [l].
Although planar parametric cubic curves are quite flexible, they are somewhat
constrained in the diversity of their characterizations.
A number of previous
papers have examined these issues in the context of computer-aided geometric
design and graphics (cf. [5], [7], [ll] and [12]). Forrest [6] has gone somewhat
further and examined rational cubic curves. For our purposes, the most relevant
works are [ll] and [12]. In particular, these authors show that loops, cusps, andinflection points are mutually exclusive. Thus, if a nondegenerate parametriccubic curve has a cusp, then it cannot have a loop or an inflection point; if it has
a loop, then it cannot have either a cusp or an inflection point, and so forth.
Moreover, a nondegenerate parametric cubic curve cannot have more than one
cusp, one loop, or two inflection points. Further, they show that the presence ofa loop, a cusp, or inflection points can all be determined by examiningF(t)= det(Q’(t),Q”(t))= X’(t)Y”(t)- X”(t)Y’(t),which is a function that is proportional to the signed curvature of the curve at
the point Q(t). (The signed curvature is defined to have a magnitude equal tothe curvature of the curve, with the sign being chosen as positive if the crossproduct of Q’(t) and Q”(t) points in the z direction.)
The vanishing of F(t) indicates the presence of inflection points since at such
points the first and second derivative vectors are linearly dependent, whichcauses the curvature to vanish. Since X(t) and Y(t) are cubic functions, one
would expect that F(t) is a cubic function. However, using the power basis
representation of Q(t), it is not difficult to show that the cubic term is zero,
ACM Transactions

on Graphics, Vol. 8, No. 3, July 1989.

150

-

M. C. Stone and T. D. DeRose

Fig. 2. The coordinate system of Su and Liu showing the construction of the characteristic point R.

implyingthat F(t) is a quadraticof the formF(t)= At2 + Bt + C

where
A = 3 det(a2, (YJ,

B = 3 det(crl, CQ),

C = det(arl, (Ye).

(2)

Solutions for values of t to the equation F(t) = 0, therefore, indicate the presenceof inflection points. The discriminant
A = B2 - 4AC
therefore becomes an important quantity. Wang, Su, and Liu [ll], [12] showthat the characterizationof the curve can be entirely determined from A, B,
and C as follows: If A = 0, then there is exactly one inflection point. Otherwise,
if A > 0, there are exactly two inflection points, if A < 0 there is a loop,
and if A = 0 there is a cusp.
Su and Liu adapt the above results to the Bezier representation of the curve.
Their approach is much the same as ours in that they choose a coordinate system,or equivalently an affine map, to fix six of the eight degrees of freedom in theequation of the curve (each control point is a position in the plane, and, therefore,
embodies two degrees of freedom). Su and Liu map B, to (1, 0), B3 to (0, l), andthe intersections of the lines BoBI and B2B3 to (1,l) as shown in Figure 2. This
mapping effectively fixes the endpoints and the directions of the tangent vectors
at t = 0 and t = 1; the remaining two parameters (U, V) are the lengths of thetangent vectors at the end.s. The characterizationof a cubic curve is, therefore,
completely determined by the characteristic point R = (U, V). The plane can bedivided into regions for the segment of the curve corresponding to 0 5 t 5 1 asshown in Figure 3.
There are a number of difficulties
with the method of Su and Liu that we
address in this paper. First, their method suffers from certain degeneracies thatcan be important in applications. For example, curves in which the first and lastlegs of the control polygon are parallel cannot be characterized by their construction since the point (1,l) (and hence, (0,O)) are not well defined in this case.
Depending on the relative lengths of the legs, such curves can either have a loop,
a cusp, or inflection points. Another (although less severe) degeneracy occurs
when B, and BB are coincident. Second, the diagram of Figure 3 does not provide
much intuition concerning the behavior of Bezier curves since the characteristic
ACM Transactions

on Graphics,

Vol. 8, No. 3, July 1989.

A Geometric Characterization of Parametric Cubic Curvesl151

point must be constructed from the control points, and since the diagram has afairly large number of disconnected regions. The diagrams produced by our
method do not require the construction of an additional characteristic point.
Furthermore, the particular diagram we construct using Bézier control points
has fewer regions, has no ambiguous degeneracies, and is easier to interpret.
3. GEOMETRIC CHARACTERIZATIONIn this section and the next, we describe the construction of a characterization
diagram for Bézier curves. In Section 6 a much more general method is developed,
and it is shown how all characterization diagrams are related.
The prescription for generating the characterization diagram is to select abasis, in this case the Bézier basis, and then choose a coordinate system, or
equivalently an affine map, that fixes the coordinates of three of the four control
points. The coefficients of the parametric equation 1 can then be expressed aslinear combinations of the control points, three of which are constant; this iscalled the canonical form of the curve. As the fourth point varies, the curve may
take on a loop, a cusp, or zero to two inflection points, depending on the positionof the moving point. The plane can, therefore, be partitioned into regions labeledaccording to the characterization of the curve segment when the fourth point isin each region.
Note that it may not be possible to produce the canonical form. We defer
discussing such degenerate cases until Sections 5 and 6.
The Bézier representation for a planar parametric cubic Q(t) is defined by four
control points in the plane, Bo, B,, Bz, and BB. This representation is linearly
related to the basic definition such thati
ACM Transactions on Graphics, Vol. 8, No. 3, July 1989.

152

M. C. Stone and T. D. DeRose'
Bl =(O.l)

BZ=(l.l)

B3

7
\
I :

\

Bo!q

B3/i

T

TB3A

:

-

B3

83
Arch

i/p

Jr

One tnllection

pantFig. 4.

cusp

Two Inflectton points

Cubic B6zier curves in canonical

Loop

form.

We choose a canonical form that maps the first three Bi?zier control points suchthat they fall along the sides of an isosceles triangle, B. = (0, 0), B, = (0, l), and
BZ = (1,l) as shown in Figure 4.
We then substitute the coordinates of BO, B1, and B, into Equation 3 todetermine the X(t) and Y(t) component functions for the canonical curve:
X(t) = (Bsr - 3)t3 + 3t2(4)

Y(t) = B,t3(5)

- 3t2 + 3t.

These equations can be used to compute the characterizing
defined in Equation 2:

values A, B, and C

A = 9(Bz, + B,, - 3)

(6)

B = -9(B3,

(7)

- 3)

c = -9A = B;, - L?B3, + 4B,

(8)
- 3

(9)

Let us look first at the regions of the plane that characterize the untrimmed
cubic curve. We then trim t.he curve and the diagram for the segment corresponding to t E [0, 11.
The untrimmed curve ha.s a cusp if and only if A = 0. For this canonical form,
this equation describes a parabola, symmetric around x = 1, passing through thepoints (-1, 0), (1, l), and (3,O). We call this curve the cusp curue since, if B3 ispositioned somewhere along this curve, the parametric cubic has a cusp. The
cusp curve divides the plane into two regions, one corresponding to loops andone corresponding to two .inflection points. The equation A < 0 is true in theregion below the parabola, indicating that if B, falls in this region the cubic has
a loop. Therefore, if B, falls in the region above the parabola, A > 0 and thecurve has two inflection points.
There are two other characteristics to discuss for the curve, both cases where
the curve degenerates to a more constrained form. The first is the case in which
the cubic terms of Equations 4 and 5 simultaneously
vanish, implying that the
cubic curve reduces to a quadratic curve, that is, a parabola. This occurs when
B3 is located at (3,0). For this reason, we call this point the parabolic point.
The remaining case occurs when the parametric cubic becomes the graph of a
cubic function, that is, one of the parametric equations can be reduced to a linear
function. When this occurs, the degree of F(t) drops from two to one, implying
at most one root, and hence, at most one inflection point. This situation is
ACM Transactions on Graphics, Vol. 8, No. 3, July 1989.

A Geometric Characterization of Parametric Cubic Curves-

153

indicated by the condition A = 0. On our diagram, this characteristic can therefore
be described by the line:

x+y-3=0.
We call this line the one inflection point line. It is tangent to the cusp curve at
the parabolic point (3, 0).
These results are summarized in Figure 5. For a Bézier cubic in canonical form,
the position of B3 on this diagram can be used to determine if the curve has aloop, a cusp, one or two inflection points, or is a parabola. If the parametric cubicis actually a straight line, all four control points are collinear and cannot be put
into canonical form for this diagram.
4. THE REGIONS FOR THE CUBIC SEGMENT
The characterization diagram for the entire cubic curve was determined without
restricting the domain parameter t. The diagram for the cubic segment is obtainedby “trimming” away the portions of the regions that correspond to values of t
outside the interval [0, 1]. We do this by individually trimming the cusp curve,
the loop region, and the inflection point region.
To trim these regions, we use a number of geometric arguments which are
specific to our choice of the Bézier representation. However, we show in Section
6 how these procedures are actually more general.
One particular geometric property we use that may not be familiar to somereaders is the variation diminishing property [3,4]. Simply stated, it guarantees
that every line intersects the control polygon in at least as many points as it
intersects the curve itself.
4.1 Trimming the Cusp Curvethe variation diminishing property. Since a cusp is a degenerate loop, a line
passing through the cusp can intersect the curve three times, whereas a convex
ACM Transactions on Graphics, Vol. 8, No. 3, July 1989.

154

l

M. C. Stone and T. D. DeRose

polygon can only be cut twice by a line. For our canonical form, if B3 is on thecusp curve, the control polygon is always convex when x > 1. The trimmed cusp
curve, therefore, corresponds to the portion of the parabola where x 5 1.
4.2 Trimming the Loop Region
The loop region is trimmed by considering only the region where a loop (i.e., adouble point) occurs for some value t in [0, 11. The boundaries of the new region
correspond to the locus of points where a double point occurs either at t = 0 or
t = 1 as indicated in Figure 6.
The region boundary corresponding to a double point at t = 0 can be found bynoting that such a double point is characterized by the existence of a value of ton the canonical curve Q(t) in the interval [0, l] such that
Q(t) - B, = 0.
If we solve this equation for B3, we get a parametric representation
for thetrimming curve which can then be reduced to algebraic form. We can also use a
result from 1121 which shows that this curve can be expressed as
B2 -3AC=O
The result is a portionof the parabola described byx2 - 3x + 3y = 0,

x < 0, Y < 0.

The region boundary corresponding to a double point at t = 1 can be determinedin a similar fashion. In this case, we seek the existence of a value of t in [0, l]such that Q(t) - BB = 0. The corresponding result from [12] is(B + 2A)2 - 3A(A + B + C).
The resulting

curve is the ellipse:
x2 + y2 + xy - 3x = 0,

OrX<l,O5YCl.

4.3 Trimming the Inflection Point Region
An untrimmed cubic generally has either a loop or two inflection points (ignoring
for the moment the cusp curve and the one inflection point line), whereas a cubic
segment can have zero, one, or two inflection points, depending on whether theroots of F(t) fall on the interval [0, 11. We, therefore, expect to partition theinflection point region into three cases. Figure 7 is used to analyze the untrimmed
inflection point region.
Region 0. Zero Inflection Points.
If B3 lies in this region, then the control
polygon is convex, so a line can intersect the control polygon in at most two
points. If the curve segment had an inflection point, it would be possible tointersect the curve in three points, thereby violating the variation diminishingproperty. Region 0, therefore, corresponds to curves where both inflection points
lie outside t E [0, 11.
Region 1. One Inflection Point.
If B, lies in this region, the signed curvature
at Bo is negative, and the signed curvature at B3 is positive, implying that there
are an odd number of roots in the interior of the curve segment. Since the curve
ACM Transactions

on Graphics,

Vol. 8, No. 3, July 1989.

A Geometric Characterization of Parametric Cubic Curvesl155

Fig. 6. Two curves showing loops appearing at (a) t = 0 and(b) t = 1.

I

Region1

Fig. 7. The untrimmed diagram with the inflection point area broken
into regions 0, 1, and 2, corresponding
to the number of inflection
points in the interval [0, I].

can have a maximum of two inflection points, Region 1 corresponds to curves
where exactly one inflection point occurs inside the curve segment.
Region 2 of Figure 7 corresponds to curves
Region 2. Two Inflection Points.
where exactly two inflection points occur inside the curve segment. If B3 lies inthis region, then the signed curvature is negative at B. and positive at BB,
implying an even number of roots of F (t) (possibly zero) in the interval t E [0, 11.
However, it can be shown [lo, 121 that at least one of the roots occurs in theinterval [0, l] for all points in Region 2, implying that there are at least two roots
corresponding to two inflection points in the interval.
Figure 8 shows Figure 5 trimmed for the cubic segment defined by t E [0, 11.
A region labeled “Arch” has been added to indicate curve segments that have noloops, cusps, or inflection points. The loop region has been trimmed to an irregularshape, and the inflection point region has been partitioned into regions of 0, 1,
and 2 inflection points. The one inflection point line has disappeared. Referring
to Figure 5, we can see that it crosses the regions that correspond to zero or one
inflection point in the untrimmed diagram. Therefore, it is no longer necessary
to distinguish it.
Some intuition for this diagram can be found by looking at the curve sequencein Figure 9. The sequence begins with a curve with B3 in the “Arch” region. As
BB crosses the Y = 1 line,‘it acquires an inflection point at t = 1. As BB moves
above the Y = 1 line, the inflection point moves into the curve. Moving B3
counterclockwise
until it is once more on the Y = 1 line, the curve acquires a
ACM Transactions

on Graphics, Vol. 8, No. 3, July 1989.

156

M. C. Stone arld T. D. DeRosel

Two Inflection

Points
BO=(O.O)

0
Parabok

Point = 13.0)‘0. -2)

Fig. 8. The diagram s#hown in Figure 5 trimmed for the cubic segment definedby t E [0, 11.

second inflection point at t = 1. As B, moves down toward the cusp line, theinflection points move together toward the point of high curvature, becoming
coincident when B3 is on the cusp curve. Moving B3 below the cusp line, thecurve develops a loop at the point of high curvature. This loop gets bigger as B3
moves to the right, opening back to an arched curve once B, passes out of theloop region.
5. DEGENERATEFORMS

The use of our canonical form relies on the ability to map the two internal points
plus one endpoint onto the isosceles triangle (0, 0), (0, l), (1, 1). There are several
cases in which this mapping is degenerate because the control points are collinear
or coincident. The canonical form defines Bo = (0, 0), B1 = (0, l), and B2 = (1,l)
with B, moving. If these three points are collinear but not collinear with B3,then the mapping B3 = (O,O), B2 = (0, l), and B1 = (1, 1) with B. moving
produces identical results since the shape of a Bezier curve is unaffected if its
control points are reversed. If all four control points are collinear but disjoint,
the curve can be drawn as a straight line. However, the motion of t along thisline varies with the order of the points along the line as shown in Figure 10. The
curve is only parametricallya straight line if the four points are equally spaced.
If B, = B2, the curve is a full cubic having an inflection point at each end. If
B, = B2 and this point equals an endpoint, the trace of the curve is a line, andthe parameterization
varies cubically with Q(t) moving monotonicallyalong thecurve. The curve has a zero length tangent vector and zero curvature at the end
with the coincident control points. If B. = B, and Bp = Bs, the trace of the curve
is a line, the parameterizationis still cubic with Q(t) moving monotonically along
the curve, and the curve has a tangent vector of zero length at each end. Finally,
if all four points are coincident, the curve collapses to a single point.
ACM Transactions

on Graphics,

Vol. 8, No. 3, July 1989.

A Geometric Characterization of Parametric Cubic Curvesl157This completes the description of our characterization diagram for Bézier
curves. Further discussion of degenerate situations and a detailed description of
how to implement this particular diagram can be found in [10]. The next section
expands this result to include a large class of similar diagrams.
ACM Transactions on Graphics, Vol. 8, No. 3, July 1989.

158

-

M. C. Stone and T. D. DeRose

6. A MORE GENERAL VIEW
Su and Liu construct a characterization
diagram that is quite different in
structure from the chara.cterization diagram of Figure 8. Yet another diagramwith a different structure could be constructed by fixing Bo, Bz, BB and letting
B1 vary. The diagram obtained in this way would, as indicated by Figure 11, havea disconnected loop region. In addition, one could imagine many more variations,
including the study of ch.aracterization diagrams for other curve types such as
B-splines, Catmull-Rom
splines, or Beta-splines. It is the purpose of this section
to describe the precise relationshipbetween all such diagrams. One of theprinciple results of this section, and indeed of the entire article, is that all region
diagrams produced by fixing three control points and letting the remaining point
vary, no matter what the curve type or which control point varies, can be obtained
from a projective (that is, a rational linear) transformationof Figure 8.
Although characterization
diagrams such as the ones in Figures 3 and 8 are
two dimensional, the relationship between various diagrams only becomes apparent in three dimensions. We refer to the 3-space where all diagrams can be
unified as characterization
space. To see how characterization
space is definedand used, we recall from Section 2 that the characterizationof a curve Q
can be completely determined from the function F(t) = det(Q’(t),Q”(t)) =At2 + Bt + C!, or equivalently, from the numbers A, B, and C. Thus, we associatewith every planar paramel;ric cubic curve a point (A, B, C) in characterization
space. The statement that. the curve Q has a cusp if B2 - 4AC = 0 is viewed
geometrically as saying that the point in characterization
space corresponding to
Q is on the implicit surface defined by B2 - 4AC = 0. This surface is a double
cone through the origin called the cusp cone. Other surfaces of interest are thet = 0 cone defined by B2 -. 3AC = 0 indicating the presence of a loop at t = 0,
the t = 1 cone defined by (B + 2A)2 - 3A(A + B + C) = 0 indicating the presenceof a loop at t = 1, and the single inflection point plane defined by A = 0 indicating
the presence of only one in.tlection point on the untrimmed curve.
Based on these surfaces, regions of characterization
space can be segmented
into volumes corresponding to curve segments possessing loops, cusps, one or
two inflection points, or none of the above. Since each of these surfaces is either
a double cone or a plane, the resulting volumes are relatively simple.
Two-dimensional
characterization
diagrams are obtained by taking twodimensional cuts through characterization
space. For instance, the diagram of
Figure 8 corresponds to taking a planar section through characterization
space.
More specifically, Equations 6, 7, and 8 show that as B3 varies, the point(A, B, Cl = (W&.x + B3y- 31, -9(&

- 31, -9)(10)

in characterization
space traces out the plane C = -9; Figure 8 is, therefore,
the result of intersecting the volumes in characterization
space with the plane
C = -9. Equivalently,
the canonical plane of Figure 8 can be viewed as being
embedded in characterization
space, with the embedding given by eq. 10. The
fact that the C = -9 plane is parallel to a side of the cusp cone explains why thecusp curve in Figure 8 is a parabola instead of some other conic section. Since
the canonical plane never intersects the C = 0 plane, none of the curves where
ACM Transactions

on Graphics,

Vol. 8, No. 3, July 1989.

A Geometric Characterizationof Parametric Cubic Curves(b) One Inflection Pointl

159(4 LOOP

Fig. 11. Bo, BP, and B3 are mapped to (0, 0), (0, l), (1,l). As B, moves, we see that there
are two disjoint loop regions. The gray region is the unit square.

C = 0 can be characterized by the diagram of Figure 8. These curves are
precisely the curves that cause the degeneracies described in Section 5.
The diagram one would obtain by fixing BO, B2, and Bd and letting B, varywould correspond to a different planar cut through characterization
space. In
particular, direct calculation for the dependence of A, B, and C on Bz shows thatthe embedding for this case is given by(A, B, Cl = (9(7&x + 2&y + l), -9(2&x+ BI,), -9Bd,

which is a parametric description for the plane A + 2B + 7C - 9 = 0, meaningthat the diagram can be described by slicing this plane through characterization
space. This plane cuts both branches of the cusp cone (the curve of intersection
being a hyperbola), explaining why the loop regions indicated in Figure 11 aredisconnected.
The fact that the characterization
diagram produced by moving B3 and thecharacterization
diagram produced by moving B2 correspond to planar slices
through characterization
space is not a phenomenon that is peculiar to Bezier
curves. The diagram obtained by varying one coefficient in any polynomial basis
corresponds to a planar cut. This implies, for instance, that the diagram produced
when moving a point in a B-spline, Catmull-Rom,or Beta-spline representationof a curve has regions bounded by lines and conic sections (assuming that theknots of the B-spline and the shape parameters of the Beta-spline are held fixed).
Moreover, the determination of which planar section of characterization
space isappropriate is quite simple. Suppose that all but one of the control points Pi in
eq. 1 is held fixed. To determine which planar section through characterization
space to use, compute A, B, and C as a function of the coordinates of a moving
point, thereby defining the embedding into characterization
space. As we show
ACM Transactions

on Graphics, Vol. 8, No. 3, July 1989.

160

l

M. C. Stone and T. D. DeRose

below, A, B, and C are guaranteed to be linear functions of the moving point,
implying that the diagram in fact corresponds to a planar section.
From Equation 2, each. of A, B, and C are of the form det(ak, LYE)where k # 1.
These functions are, therefore, clearly linear if all but one of oo, . . . , o3 are held
fixed. To show that A, 13, and C are linear if all but one control point is held
fixed, we recall that the representation of a polynomial curve in one basis can beconverted into a representation in any other basis by matrix multiplication(cf.
[l]). If mij denote the coefficients of this matrix, thendet( (lk,N)=

det 2 mkrpr,(

The fact that determinants
rewrite this as

r

c
s

%Ps

.
)

are linear in each of their arguments can be used todet(a!k, LY/) =

c
r

c
s

mk,mLsdet(P,,

ps).

(11)

This shows that if all but one of the Pi are held fixed, then each of the terms inthe double summation of eq. 11 is either a constant or a linear function, thereby
showing that A, B, and C are linear functions.
The plane A - B + 2C + 1 yields a particularly
revealing section throughcharacterization
space as shown in Figure 12. This plane intersects the cusp
cone, the t = 0 cone, and the t = 1 cone in ellipses that show the special natureof these surfaces. The cusp curve meets each of the other two curves tangentiallyat two points, and all three curves meet tangentially at the parabolic point. The
common tangent line at the parabolic point corresponds to A = 0, the tangent
line at the other point of intersection between the cusp curve and the t = 0 trim
curve corresponds to C = 0, and the tangent line at the other point of intersection
between the cusp curve and the t = 1 trim curve corresponds to A + B + C = 0.
Finally, the B = 0 line connects the two points of intersection between the cusp
curve and the t = 0 curve, and the B + 2A = 0 line connects the two points ofintersection between the cusp curve and the t = 1 curve.

Remark. Mathematical purists familiar with projective geometry (cf. [7] and181) may have noticed that since the defining equations for the cusp cone, thet = 0 cone and the t = 1 cone are homogeneous polynomials of degree two, andcharacterization
space is more naturally thought of as a projective 2-space rather
than as a linear 3-space. That is, for characterization
purposes, a curve Q(t)can be placed in correspondence with the point in projective 2-space having
homogeneous coordinates[A, B, C] where A, B, and C are given bydet(Q’(t), Q”(t)) = At* + Bt + C.
In this context, planar sections through 3-space are interpreted as choosing anaffine subspace by sending one of the projective lines to infinity. For the diagramof Figure 8, for instance, the line that has been sent to infinity is the C = 0 line.
As was demonstrated earlier, curves in correspondence with the projective pointsof this line could not be cha.racterized by the diagram. This is not only a problem
with our canonical form, it is a problem with every canonical form obtained by
fixing three control points and moving one. This deficiency is a topologicalconsequence of the fact that these methods correspond to affine subsets-they
ACM Transactions

on Graphics,

Vol. 8, No. 3, July 1989.

A Geometric Characterizationof Parametric Cubic Curves

Fig. 12. A planar section through characterization
critical curves, lines, and tangencies.

space showing

.

161

the

must therefore send some line to infinity and lose the ability to characterize theassociated curves. The projective setting also makes it clear that every suchdiagram can be created via a projective transformationof Figure 12. This follows
from the fact that every pair of affine subsets is related by a projective transformation in much the same way that every pair of bases are related by a linear
transformation.
Interestingly,
the characterization
diagram of Su and Liu (Figure 3) does notcorrespond to a planar cut through characterization
space, but it does correspondto a bilinear one. Wang shows that with a suitable choice of coordinates,
A=3(UV-U-V)
B=3U(2c = U(Vwhere U and V are as indicated(U, V) plane into characterization

V)
- 3),

in Figure 2. The embedding
space is therefore given byof Su and Liu’s(A, II, C) = (3(UV - U - V), 3U(2 - V), U(V - 3)),
which describes a bilinear surface that maps the corners of the unit square in(U, V) space into the points (0, 0, 0), (-2,4, -3), (-2,0, O), and (-2,2,2).
Thenonlinear nature of this surface explains why the characterization
diagram of Su
and Liu (Figure 3) is not a projective transformationof the characterization
diagram of Figure 8.
7. CONCLUSIONSIn this paper, we have developed a simple geometric method for characterizing
cubic curves based on the positions of the control points. The method is basedon the idea that three of the four points can be fixed and the shape determined
ACM Transactions

on Graphics, Vol. 8, No. 3, July 1989.

162

l

M. C. Stone and T. D. DeRoseby analyzing the position of the fourth point. Depending on the position of the
fourth point, the curve scan possess a loop, a cusp, or up to two inflection points.
The presence of these features is determined by partitioning
the plane into
regions based on the position of the fourth point. A specific example is given for
Bezier curves. The resulting characterization
diagram is seen to be simpler andmore instructive than the previous diagram of [ll].
Of course, there is a large choice of which point to move and which representation of the curve to use, each leading to a different characterization
diagram.
It is therefore important to understand at a higher level how these diagrams are
related. We have answered this question by showing that all characterization
diagrams result from exacting two-dimensionalslices from a common, universal
three-dimensional
space that we call characterization
space. It was further shownthat the diagrams obtained by fixing all but one coefficient in any polynomial
basis corresponds to a simple planar section through characterization
space.
Figure 8 is an example of such a planar slice, corresponding to a plane parallel
to one of the axes through characterization
space. Finally, it was shown that theincreased complexity of the diagram of Su and Liu (Figure 3) was a result of thefact that it corresponds to a nonplanar slice through characterization
space.
ACKNOWLEDGMENTS

Much of the intuition for this work was achieved by playing interactively with aBezier cubic segment in the Gargoyle interactive illustration
system at Xerox
PARC [2,9]. Furthermore, we were able to programaticallyconstruct Gargoyle
objects for each of the boundary curves and interactively test the diagram for thetrimmed curve. We also used Gargoyle to explore Su and Liu’s diagram. We
believe that without this interaction we could not have progressed to our results
as quickly and as confidently. Gargoyle was also used to produce all of the figures.
Our motivation to work on this problem at this time was originally inspired by
Jules Bloomenthal’sneed for a method to define tree branches without loops inthem. Jules was also able to provide us with a glimpse of the three cones incharacterization
space and verify their shape and relationship to one another.
Finally, this work has been a pleasant and evenly balanced collaboration,andthe order of the authors names should be considered reverse-alphabetical.
REFERENCES
1. BARTELS, R. H., BEATTY, ,J. C., AND BARSKY, B. A. An Introduction
to Splines For Use in
Computer Graphics and Geometric Modeling. Morgan-Kaufmann,
Palo Alto, Calif. 1987.
2. BIER, E., AND STONE, M. Isnap-dragging. Comput. Graph. 20,4 (Aug. 1986), 233-240.
3. BOEHM, W., FARIN, G., ANI) KAHMANN, J. A survey of curve and surface methods in CAGD.
Comput. Aided Geom. Des. 1, 1 (July 1984), l-60.
4. FARIN, G. Curves and Surfuces for Computer Aided Geometric Design. Academic Press, Orlando,
Fla. 1987.
5. FORREST, A. R. Shape classificationof the non-rational
twisted cubic curve in terms of Bezier
polygons. CAD Group Document No. 52, University of Cambridge, Cambridge, England, Dec.
1970.
6. FORREST, A. R. The twisted cubic curve: A computer-aided geometric design approach. Comput.
Aided Des. 12, 4 (July 1980), 165-172.
7. PATTERSON, R. R. Parametric cubits as algebraic curves. Comput. Aided Geom. Des. 5 (1988),
139-159.
ACM Transactions on Graphics, Vol. 8, No. 3, July 1989.

A Geometric Characterization of Parametric Cubic Curves-

163

8. PENNA, M. A., AND PATTERSON, R. R. Projective Geometry and Its Applications to Computer
Graphics. Prentice-Hall,Englewood Cliffs, NJ, 1986.
9. PIER, K., BIER, E., AND STONE, M. An Introduction
to Gargoyle: An interactive illustration
tool. In Document Manipulation-Typography,
Proceedings of the International
Conference on
Electronic Publishing, Document Manipulation-Typography(EP88) (Nice, France, Apr. 20-22,
1988). Cambridge University Press, 1988, pp. 223-238.
10. STONE, M. C., AND DEROSE, T. D. Characterizing
cubic Bezier curves. Tech. Rep. EDL-88-8,
Xerox Palo Alto Research Center, Palo Alto, Calif., Dec. 1988.
11. SU, B., AND LIU, D. An affine invarient and its application in computational geometry. Scientia
Sinica (Series A) 24, 3 (Mar. 1983), 259-267.
12. WANG, C. Y. Shape classification of the parametric cubic curve and parametric B-spline cubic
curve. Comput. Aided Des. 13, 4 (1981), 199-206.

Received June 1988: revised and accepted February

1989

ACM Transactions on Graphics, Vol. 8, No. 3, July 1989.