[metapost] a generic class of cubic bezier curves
Larry Siebenmann
laurent at math.toronto.edu
Mon Feb 14 02:45:13 CET 2005
Hi All,
As I mentioned here a few days ago, back in december 1901,
specifically in a note on the metafont list entitled
"cubic (but nonquadratic) bezier curves" <Date: Sat, 15
Dec 2001 15:17:14 0500>, I was on the verge of posting
an affine classification of a generic class of bezier cubic
curves in R^2:
<< It is the first (nondegenerate) case that is of
most geometric interest since one always finds a pair of
inflection points, or else one double point, or else
(exceptionally) a cusp. No time to explain this further
trichotomy today! >>
The archives of the metafont list are at
http://www.gutenberg.eu.org/pub/GUTenberg/archives/metafont/
and my postings of that month are all fairly basic to an
understanding of bezier cubics and bezier quadratics.
The longish sequel posting that I prepared back then has
slept quietly for several years. I am posting it today since
several mp experts are exploring in this direction.
Today, I would be inclined to explain this classification
somewhat differently, placing more emphasis on derivation
and integration of bezier curves. On the other hand,
leaving things as originally explained is sometimes best.
If the exposition is unclear just ask questions
and someone will answer.
A couple of a posteriori comments may help readers:
(i) The (constant!) cubic axis vector C, which plays a
central role in what follows, is (1/6) of the third time
derivative vector F'''(t) of the Bezier cubic curve F(t).
It is equally the asymptotic direction of F(t) from any point
in R^2 as time tends to \pm \infty.
(ii) Bezier cubics with cusp (which are affinely
unstable) could have been excluded from the discussion by
reinforcing the genericity conditions imposed 
insisting that the first derivative path F'(t) describe a
nondegenarate parabola in R^2. The reinforced genericity
then becomes equivalent to affine stability.
Laurent S.
MY UNPOSTED NOTE(S) OF DEC 2001:
 a generic class of cubic bezier curves

 ~t metafont at ens.fr

 ** a generic class of cubic bezier curves **

 Today, I will answer the basic question: What is
 (up to affine equivalence) the global shape of a
 *typical* cubic bezier curve:

 F(t) = s^3*a + 3s^2*t*b + 3s*t^2*c + t^3*d

 where

  s=(1t)
  the paramater t varies in *all* of R
  F(0)=a,b,c,d=F(1) are any four control points in R^2
 ??

 The conclusion will be that only two shapes occur with
 nonzero probabability:

 1) bump (two inflexion points):

 t > (t^3 + t,t^2)

 2) loop (one transverse double point)

 t > (t^3  t,t^2)

 In each case there are no other (affinely
 distinguished!) points of type "double", "inflexion", or
 "singular". Two bezier curves of the same shape (1) or
 (2) respectively are related by an affine linear map
 of source R together with an affine linear map of
 target R^2 (we here allow orientation reversals).

 Both these shapes are affine stable in the sense that all
 sufficiently small perturbations of a,b,c,d yield
 another curve of the same shape. This is untrue for all
 other affine types of bezier curve since with probability
 1 the perturbed curve has one of the above two shapes!

 Jacko has repeatedly asked me "why and how" wierd
 and wonderful things happen to bezier cubics outside
 the parameter interval that metafont uses. Thus I
 originally wanted to explain all in terms of control
 points. I ultimately yielded to the charm of cartesian
 coordinates since this is one of the rare situations in
 affine geometry where there really are *natural*
 cartesian coordinates that "reveal all".

 There are neverthless numerous delightful ways to
 predict or see aspects of shape in terms of control
 points; more on that in due course.

 RECOLLECTIONS

 To begin, I review what we already know. For the
 cubic bezier curve F(t), 0<=t<=1, with control points
 F(0)=a,b,c,d=F(1) in the plane R^2, the cubic axis
 direction vector introduced in <metafont list Sat, 15 Dec
 2001 15:14:54 0500> is:

 (#) C =  a + 3 b + 3 c + d

 It has direction independent of tparameter choice
 provided curve orientation is respected. But change of
 parameter t to t changes C to C.

 This C will be nonzero generically, ie with probability
 1 in any open set of bezier control point quadruples.
 Then the projection parallel to C

 p o F : R > L_C

 of F(t) onto any line L_C transverse to direction C is
 quadratic. This p o F is similarly of degree 2
 with probability 1.

 The two conditions "C<>0" and "p o F degree 2"
 define the "generic" class of bezier cubics that I
 propose to analyze into three mutually exclusive affine
 equivalence classes, namely, (1), and (2), each affine
 stable under perturbation, *plus* a third, the affine
 *unstable* class:

 (3) there is a single cusp singularity:

 t > (t^3,t^2)


 I noted <metafont list Sat, 15 Dec 2001 15:17:14 0500>
 15:17:14 0500> that the closed convex hull of the
 complete bezier curve (t \in R) is a closed half plane
 whose frontier line has direction C; we call the
 frontier the "(oriented) line C" hoping no confusion
 results. There is exactly one point of the bezier
 cubic, say B = F(t_0), that lies on line C. Call it the
 *basepoint* of F. This t_0 is the unique time when the
 quadratic function p o F above reaches its extremum.

 We will usually adjust time parameter so that
 t_0 = 0.


 

 So much for introduction and recollections; let us
 get into the constructions and proofs.



 CONSTRUCTIONS AND PROOFS

 The derivative vector F'(t) must be tangent to
 line C at t=t_0. We claim that F'(t_0) is

  positive multiple of C in "bump" case (1)
  negative multiple of C in "loop" case (2)
  zero in "cusp" case (3)

 We prove this claim by introducing a canonical
 coordinate system in R^2 with origin B = F(t_0)
 that is also called the base point of F(t).

 From this point we linearly reparametrize F so that
 t_0=0.

 The first axis (xaxis) is the oriented line C with
 origin F(0)=F(t_0) specified above and a unit point
 still to be specified.

 The second axis (yaxis) is the fixed point set of an
 affine linear reflection \rho of R^2 such that

 \rho(F(t)) = F(t) for all t \in R

 I now seize an opportunity to use special control points
 to make \rho obvious. A line parallel to C and in the
 interior of the convex hull of F, always meets the
 bezier cubic F at exactly two parameter values t and t;
 futher, these points of intersection are clearly
 distinct for all small t <> 0 and for all large t. Pick
 a positive parameter value t_1 so that

 F(t_1) <> F(  t_1)

 We can and do rechoose control points for F:

 F( t_1) = a',b',c',d' = F(t_1)

 Complements to come later will make this a *practical*
 posibility. Since d'  a' is by definition parallel to
 the constant cubic direction C of F(t) the same is true
 of c'  b' in view of the universal expression (#) for
 the cubic direction (up to positive scaling).

 View the following diagram with a constant width font:


 > (direction C)


 a' o  o d'
 \ /
 \ /
 \ /
 \ /
 \ /
 \ /
 \ /
 b' o  o c'


 Thus, there is a unique affine linear reflection that
 respects every line parallel to C and exchanges a' <>
 d' and b' <> c'. This is clearly the required \rho
 respecting the bezier cubic. Its reflection axis is a
 line transverse to C and running through 0.5(a'+d') and
 0.5(b'+c') and also the base point B = F(0). We make
 this preferred choice of L_C the second axis through B =
 F(0). Then, with respect to these axes, we set up
 cartesian coordinates with origin (0,0)=B.

 Beware that \rho is not an isometry of R^2 for the
 original metric unless it happens that C and L_C are
 perpendicular. (Affine reflections in R^2 are not in
 general isometric!)

 Here is the casebycase description of t > F(t),
 involving u,v,w, positive constants:

 (1) t > (ut^3 + vt,wt^2)
 (2) t > (ut^3  vt,wt^2)
 (3) t > (ut^3,wt^2)

 Indeed, the xcoordinate is an odd function of t, while
 the ycoordinate is an even function without constant
 term. (The special choices of base point B as origin and
 then of L_C assures this.)

 By scaling the t parameter we make u = v in cases (1)
 and (2). Then by choosing length unit on the first axis
 we make u = v = 1. Similarly for the second axis, we
 make w = 1. Thus we get "normalized" cartesian
 coordinates with

 (1) model bump t > (t^3 + t,t^2)
 (2) model loop t > (t^3  t,t^2)
 (3) model cusp t > (t^3,t^2)

  In case (1) the inflexion points are where
 F''(t) and F'(t) are parallel. But

 F'(t) = ( 3t^2 + 1 , 2 t )
 F''(t) = ( 6 t , 2 )

 and vanishing of the cross product of these two vectors
 is the test for parallelism:

 6 t^2 + 2 12 t^2 = 0

 This gives t = 1 / sqrt(3) so the two inflexion points
 are:

 ( (4sqrt3)/9 , 1/3 ) and ( (4sqrt3)/9 , 1/3 )

  In case (2), the double point is

 F(1) = F(1) = (0,1)

  In case (3), the cusp point is the base point B =
 (0,0).

 It is routine to check  using the normalized
 cartesian formulae for these three cases  that there
 are no inflection points, or double points, or singular
 points, *other* than those already noted.

 This completes the proof of the trichotomy.

 Cheers

 Laurent S.


 PS. I have not made precise the intuitive notion of
 probability 1 or 0 for a set of bezier cubics. One
 approach is to use any smooth volume form in the space of
 all choices. It would be much more difficult to deal
 correctly with a11 probabilities in the interval [0,1].

 


 ** generic cubic bezier curves (some complements) **

 COMPLEMENT (Generic rigidity)

 In the (jointly) generic cases (1) and (2), the only nontrivial
 affine linear map g of R^2 that respects the image of F
 is the reflection \rho.

 Proof: The map g must fix the base point (0,0) and
 respect the two canonical axes.

 It fixes the whole yaxis since it fixes not just
 the base point, but:

  in case (1), the barycenter (0,1/3) of the two
 inflexion points, and

  in case (2) the double point is (0,1).

 The composition g\rho also fixes the xaxis since, for
 some t large it fixes the 3 distinct points with x
 coordinates F(t),0,F(t) on the line y=t^2.

 It follows that g\rho is the identity and
 hence g is \rho.



 COMPLEMENT (Cusp quasihomogenity)

 In the cusp case (3), the group of orientation
 *preserving* affine linear maps g of R^2 respecting
 the image of F is nontrivial and made up of the maps:

 (x,y) > (u^3 x, u^2 y) with u > 0

 It is therefore isomorphic to the positive reals under
 multiplication.

 The proof is an easy exercise.



 COMPLEMENT (Generic classification)

 Every generic bezier cubic segment F(t), 0<=t<=1,
 is equivalent to a *unique* segment a<=t<=b with a<b of
 one of the the two models

 (1) bump t > (ut^3 + vt,wt^2)
 (2) loop t > (ut^3  vt,wt^2)

 where the equivalence is by a unique orientation
 preserving affine map of R^2 and the unique orientation
 preserving affine map of [0,1] <> [a,b].

 Thus, up to this oriented affine equivalence, there are
 two 2parameter families of inequivalent doubly
 *non*degenerate bezier curve segments.



 SOME HANDY CALCULATIONS TO ASSIST NORMALIZATION

 (i) Let a,b,c,d be the collinear control point
 sequence of a cubic bezier curve F(t) confined to a line
 L, whose cubic term vanishes while its quadratic term
 does not. Then F(t) is also a quadratic bezier curve in
 L with control point sequence a,e,d where:

 e = (1/2).5(d+a) + (3/2).5(b+c)
 = (1/4)(a + 3b + 3c + d)

 Further the frontier of the image of F in L is the
 solution of the singular point equation 0 = F'(t), while
 F'(t) is linear in t. In more detail:

 2s a + 2(s+t) e + 2t b = 0 with s = 1t
 or (2t  2) a + 2(2t1) e + 2t b = 0
 or (2a + 4e + 2b) t = 2a + 2e

 or t = (a + e)/(a + 2e + d)

 (ii) With usual notations, apply (i) to the projection
 p o F to L_C of a doubly *non*degenerate cubic bezier
 curve F in the plane R^2 to determine the parameter value
 t_0 at the base point B of F, and then determine B itself.

 (iii) For F as in (ii), let F(t_1) be a known point on F
 (say a or d), that is distinct from B, and let t_2 be the
 image of t_1 by reflection in point t_0 on the parameter
 line R. Then the mirror symmetry axis of F in R^2 is the
 line through the the points

 .5 (F(t_1) + F(t_2)) and B = F(t_0)

 All the facts above are "known to experts". If
 there is a textbook exposition as suitable (or more
 suitable ;) for mathematically curious metafont users,
 please point it out!


More information about the metapost
mailing list