[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 non-quadratic) 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 (non-degenerate) 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
non-degenarate 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=(1-t)
| -- 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 t-parameter 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 (x-axis) 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 (y-axis) 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 case-by-case 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 x-coordinate is an odd function of t, while
| the y-coordinate 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 y-axis 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 x-axis 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 quasi-homogenity)
|
| 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 2-parameter 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 = 1-t
| or (2t - 2) a + 2(2t-1) 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