Identification of Inflection Points and Cusps on Rational Curves

Abstract: Using homogeneous coordinates, a rational curve can be represented in a non-rational form. Based on such a non-rational representation of a curve, a simple method to identify inflection points and cusps on 2-D and 3-D rational curves is proposed.

Key words: rational parametric curves, inflection points, cusps.

1  Introduction

From the theory of algebraic curves, a point of multiplicity r is a point at which every line intersects the curve r times. In particular, a point of multiplicity one is a simple point, and a point of multiplicity two is a double point. A loop of a curve is a double point where the curve crosses itself and has two distinct tangents. A cusp is a double point at which two (cuspidal) tangents are coincident. An inflection point of a curve is a simple point at which the tangent intersects the curve three or more times. Accordingly, we say such an inflection point is of multiplicity three or more. From this geometric point of view, we shall derive the inflection point and cusp conditions in the form of determinants. Consequently, inflection points and cusps can be identified by solving a univariate polynomial. There are some advantages with respect to our approach. Firstly, we can easily identify the multiplicity of an inflection point, which has a practical importance in manufacturing since the normal of a curve changes directions only at an inflection point with odd multiplicity. Secondly, the occurrence of cusps and inflection points on a 3-D curve corresponds to zeros of one univariate polynomial rather than zeros of three polynomials. Therefore, efficiency and stability in computing such zeros can be assured.

In the subsequent sections, we shall assume that our rational parametric curves are properly parametrised; i.e., these curves cannot be identically described by a rational polynomial parametrisation of lower degree. From the theory of algebraic geometry it is known that such proper parametrisation always exists for rational curves. Detailed discussion on proper parametrisation can be found in [Sederberg'84, 86'].

2  Planar rational curves

r(t)=(x(t),y(t))= æ ç è X(t) W(t) , Y(t) W(t) ö ÷ ø ,        W(t) ¹ 0,

where X(t), Y(t), and W(t) are polynomials of degree n in t Î [a,b]. Using homogeneous coordinates, we may map r(t) into a 3-D space to obtain a non-rational representation of a curve; i.e., R(t)=(X(t),Y(t),W(t)). In CAGD applications, it is often desirable to find the conditions such that R(t) may or may not have inflection points and cusps. By generalising the approach in [Patterson'88], we shall derive such conditions for planar rational curves of any degree.

A comprehensive treatment of planar rational curves can be found in [Walker'50] and a very readable treatment in [Primrose'55]. To be consistent, we briefly review some relevant properties of planar rational curves and then derive the inflection point and cusp conditions for R(t). In a homogeneous coordinate system, the point (X,Y,W) is a loop if two distinct parameters t₁, t₂ give the same ratio for (X,Y,W), i.e.,

X(t1):X(t2)=Y(t1):Y(t2)=W(t1):W(t2).

A cusp may be regarded as the limit of a loop. Then, by using Taylor's expansion in the vicinity of t it can be proved [Primrose'55] that a cusp occurs if

X¢(t):X(t)=Y¢(t):Y(t)=W¢(t):W(t)

(1)

where a dash denotes differentiation with respect to t. If one or two of X(t), Y(t), W(t) are zero, relation (1) needs to be modified. For example, if X(t)=0 (1) becomes X^¢(t)=0; Y^¢(t):Y(t)=W^¢(t):W(t) and if X(t)=Y(t)=0 (1) becomes X^¢(t)=Y^¢(t)=0; W^¢(t)=W(t).

We now consider an inflection point. A straight line in homogeneous coordinates is given by AX+BY+CW=0, with A,B,C Î Â. If this line is an inflectional tangent line to the curve, it must meet the curve at least three times at an inflection point with parameter t. Thus, we have

AX(t)+BY(t)+CW(t)=0

AX¢(t)+BY¢(t)+CW¢(t)=0

AX¢¢(t)+BY¢¢(t)+CW¢¢(t)=0

When A,B, and C are not all zero, the above system of equations holds simultaneously if and only if

I(t)= ê ê ê ê ê X(t) Y(t) W(t) X¢(t) Y¢(t) W¢(t) X¢¢(t) Y¢¢(t) W¢¢(t) ê ê ê ê ê =0.

By rearranging each row of the determinant to be of degree n-2 (e.g., substituting (n-1)X^¢(t)-tX^¢¢(t) for X^¢(t) and similar for other elements), we can see that I(t) is of degree not more than 3(n-2) in t, indicating a planar rational curve of degree n may have at most 3(n-2) inflection points. We note that I(t)=0 is satisfied by the parameter of a cusp since the first two rows of the determinant are proportional. Differentiating the determinant I(t), we have

I¢(t)= ê ê ê ê ê X(t) Y(t) W(t) X¢(t) Y¢(t) W¢(t) X¢¢¢(t) Y¢¢¢(t) W¢¢¢(t) ê ê ê ê ê .

Again, the first two rows are proportional at a cusp, hence I^¢(t)=0. Thus, the parameter of a cusp appears as a multiple root of I(t)=0. In the case of non-rational curves, I(t)=X^¢(t)Y^¢¢(t)-X^¢¢(t)Y^¢(t) and is of degree not more than 2(n-2). We may write I(t)=(R(t)×R^¢(t))·R^¢¢(t) to facilitate algebraic manipulation.

From the above discussion, we may conclude that distinct real roots of I(t)=0 correspond to real inflection points of multiplicity three (the case most CAD users are interested in), and multiple roots to either cusps or inflection points of multiplicity more than three. A multiple root (with multiplicity m, for example) of I(t)=0 is the parameter value of a cusp if (1) is satisfied. Otherwise, it is an inflection point of multiplicity m+2. It is noted that we have differentiated the tangent line twice to obtain I(t)=0. Therefore, a root of multiplicity m of I(t)=0 indicates that the tangent meets a curve m+2 times.

Example 1. Find all cusps and inflection points on a planar rational curve X(t)=t², Y(t)=1+t, W(t)=t³+t⁴. Since I(t)=t²(t²+3t+1)=0, we have two inflection points at t=[(-3±Ö5)/2] and a cusp at t=0. To investigate points at infinity, we reparametrise the curve by t=¹/_u and obtain I(u)=u²(u²+3u+1), giving the same inflection points and an additional cusp u=0 which is at infinity with respect to t.

3  Space parametric rational curves

r(t)=(x(t),y(t),z(t))= æ ç è X(t) W(t) , Y(t) W(t) , Z(t) W(t) ö ÷ ø ,       W(t) ¹ 0,

where X(t), Y(t), Z(t), and W(t) are polynomials of degree n in t. The curvature vector of the above curve is given by

k(t)= r¢(t)×r¢¢(t) |r¢(t)|3 .

If the curve r(t) is regular (i.e. r^¢(t) ¹ 0) in a given interval, an inflection point occurs where three components of the numerator of k(t) vanish simultaneously. From this point of view, the detection of inflection points is addressed in [Manocha & Canny'90]. We now derive the inflection point and cusp conditions for 3-D rational curves based on the approach of section 2.

In a homogeneous coordinate system, a 3-D rational curve is given in non-rational form as R(t)=(X(t),Y(t),Z(t),W(t)), and a plane is given by AX+BY+CZ+DW=0, with A,B,C,D Î Â. Let P and Q be any two points on a curve. Then, the plane containing the tangent at P and the point Q is called the osculating plane as Q merges to P. From this definition it is seen that the osculating plane meets a curve three times at P. Assume that AX+BY+CZ+DW=0 is an osculating plane to the curve whose coordinates are X(t),Y(t),Z(t),W(t). From the fact that the osculating plane meets a curve three times, we have

AX+BY+CZ+DW=0

AX(t)+BY(t)+CZ(t)+DW(t)=0

AX¢(t)+BY¢(t)+CZ¢(t)DW¢(t)=0

AX¢¢(t)+BY¢¢(t)+CZ¢¢(t)+DW¢¢(t)=0

Eliminating A,B,C,D gives the osculating plane

W(t)= ê ê ê ê ê ê X Y Z W X(t) Y(t) Z(t) W(t) X¢(t) Y¢(t) Z¢(t) W¢(t) X¢¢(t) Y¢¢(t) Z¢¢(t) W¢¢(t) ê ê ê ê ê ê =0.

We may express W(X,Y,Z,W)=0 as a(t)X+b(t)Y+c(t)Z+d(t)W=0, where a(t), b(t), c(t), and d(t) are polynomials in t of degree not more than 3(n-2). Assume the curve has an inflection point at t=t₀. Then, the tangent meets the curve at least three times at t₀. Hence any plane containing this stationary tangent must satisfy W(X,Y,Z,W)=0, indicating a(t), b(t), c(t), and d(t) vanish at t₀. Therefore, the necessary and sufficient condition for an inflection point is

a(t)=b(t)=c(t)=d(t)=0.

(2)

It is readily verified that if any three polynomials a(t), b(t), c(t), d(t) vanish at t₀, so does the fourth. Therefore, the detection of inflection points becomes the problem of searching for zeros of the greatest common divisors (GCDs) of any three polynomials. Customarily, we may search for zeros of a(t), b(t), and c(t). Up to now we have obtained nothing new comparing with the results in [Manocha & Canny'90], except for the way we derived the inflection point conditions. However, we can progress further to find a univariate polynomial whose zeros correspond to inflection points and cusps.

If an osculating plane meets a curve more than three times, we call it a stationary osculating plane. From the fact that a stationary osculating plane meets a curve at least four times, we deduce that the stationary osculating plane AX+BY+CZ+DW=0 should satisfy the following relations at an inflection point with parameter t:

AX(t)+BY(t)+CZ(t)+DW(t)=0

AX¢(t)+BY¢(t)+CZ¢(t)DW¢(t)=0

AX¢¢(t)+BY¢¢(t)+CZ¢¢(t)+DW¢¢(t)=0

AX¢¢¢(t)+BY¢¢¢(t)+CZ¢¢¢(t)+DW¢¢¢(t)=0

When A,B,C, and D are not all zeros, the above relations hold if and only if the following condition is satisfied:

Y(t)= ê ê ê ê ê ê X(t) Y(t) Z(t) W(t) X¢(y) Y¢(t) Z¢(t) W¢(t) X¢¢(t) Y¢¢(t) Z¢¢(t) W¢¢(t) X¢¢¢(t) Y¢¢¢(t) Z¢¢¢(t) W¢¢¢(t) ê ê ê ê ê ê =0

In general, Y(t) is of degree at most 4(n-3) in t, and thus may have as many as 4(n-3) real solutions in t at which the osculating plane is stationary.

In a 4-D homogeneous coordinate system, the cusp condition for a 3-D curve is

X¢(t):X(t)=Y¢(t):Y(t)=Z¢(t):Z(t)=W¢(t):W(t)

(3)

(The proof is similar to that for a 2-D curve in a 3-D homogeneous coordinate system.) We note that Y(t)=0 and Y¢(t)=0 are satisfied by a parameter of a cusp since the first two rows of Y(t) are proportional. Therefore, the parameter of a cusp appears as a multiple root of Y(t)=0.

It should be noted that not every solution of Y(t)=0 indicates the occurrence of an inflection point or a cusp. This can be checked by examining a planar rational curve whose osculating plane is the plane of the curve and is thus stationary everywhere. In fact, distinct roots of Y(t)=0 correspond to either inflection points of multiplicity three (note the osculating plane intersects the curve four times at the inflection point of multiplicity three) or points where the torsion vanishes (Torsion measures the rate at which the osculating plane turns about the tangent to the curve), and multiple roots to either cusps or inflection points of multiplicity more than three. A root of Y(t)=0 corresponds to an inflection point if (2) is also satisfied, and to a cusp if relation (3) is met. As a particular example, we examine a cubic curve for which either Y(t)= constant or Y(t) º 0. The former indicates that a true 3-D curve has no inflection points, and the latter indicates that the curve is actually a 2-D curve. We give more examples below.

Example 2. Given a 3-D non-rational Bézier curve of degree 4 whose control vertices are

p0=(1,-1,1), p1= 1 2 (3,1,2), p2=(2,0,1),  p3= 1 2 (5,-1,-2), p4=(3,1,1)

we obtain Y(t)=-4608(2t-1)². Noting W(t)=1, we have W^¢(¹/₂):W(¹/₂)=0 but X^¢(¹/₂):X(¹/₂) ¹ 0. Therefore, t=¹/₂ gives an inflection point where the osculating plane intersects the curve five times.

Example 3. Given a 3-D rational curve of degree 4,

X(t)=t2, Y(t)=t3, Z(t)=t4, W(t)=t+1,

we obtain Y(t)=-12t³(t+4). Since X^¢(0)=Y^¢(0)=Z^¢(0)=0, and W^¢(0)=W(0)=1, t=0 gives a cusp where the osculating plane meets the curve six times. At t=-4, the curve does not inflect since a(-4) ¹ 0. Therefore, t=-4 gives a point on the curve where the torsion vanishes.

4  Conclusions

Sometimes, we may want to know the conditions under which we can manipulate certain control vertices and/or weights such that the resulting curve will or will not have inflection points and cusps. Such a problem is referred to as the characterisation of a curve in CAGD [Liu'85, DeRose & Stone'89, Meek & Walton'90, Li & Cripps'93a,b]. With our approach, one may express the inflection point and cusp conditions in terms of such control vertices/weights and thus obtain the required characterisations.

We wish to express our thanks to the referees of this paper for their valuable comments and suggestions.

References

DeRose, T.D. and Stone, M. (1989), A geometric characterisation of parametric cubic curves, ACM Trans. Graphics 8(3), 147-163.

Li, Y.M. and Cripps, R.J. (1993), Characterisation of planar rational cubic curves, 3rd SIAM Conference on Geometric Design, Tempe, Arizona, 1993.

Li, Y.M. and Cripps, R.J. (1993), Detecting and controlling inflection points on planar rational Bézier curves, proceedings of 3rd International Conference on Computational Graphics and Visualisation Techniques, Algarve, Portugal, 390-394.

Liu, D. (1985), Rational Bézier curves, Acta Mathematicae Applicatae Sinica 8(1), 70-83.

Machona, D. and Canny, J.F. (1992), Detecting cusps and inflection points in curves, Computer Aided Geometric Design 9, 1-24.

Meek, D.S. and Walton, D.J. (1990), Shape determination of planar uniform B-spline segments, Computer Aided Design 22(7), 434-441.

Patterson, R.R. (1988), Parametric cubics as algebraic curves, Computer Aided Geometric Design 5, 139-159.

Primrose, E.J. (1955), Planar Algebraic Curves, Macmillan & Co Ltd., New York.

Sederberg, T.W. (1984), Degenerate parametric curves, Computer Aided Geometric Design 1, 301-307.

Sederberg, T.W. (1986), Improperly parametrised rational curves, Computer Aided Geometric Design 3, 67-75.

Walker, R.J. (1950), Algebraic Curves, Princeton University Press, Princeton, NJ.