Cubic Interpolation on Riemannian Manifolds

Russell O’Connor
Math 240
Fall 2003
University of California, Berkeley

Introduction

The author’s interest in cubic splines comes from the problem of making key-framed animations in computer graphics. To produce computer animations the user specifies specific positions and orientations of objects at certain points in time [t1,t2,…,tn]. These points are called key-frames. It is left up to the computer to interpolate the positions and orientations between these key-frames in order to make enough frames to produce an animation. Additionally the user usually wants some degree of smoothness in this interpolation.

The complete animation path of one object in space is given by a function f:[t1,tn]→ℝ3SO(3). The problem is for the computer to find a suitable function such that for all i, f(ti) has the specified position and orientation. The problem of finding f can be divided into finding the two components:

  1. f1:[t1,tn]→ℝ3
  2. f2:[t1,tn]→SO(3)

where f(t)=(f1(t),f2(t)).

One method of interpolating between key-frames by connecting them with geodesics. Although this method generates a continuous function, in general the function fails to be C1 continuous. This means that there will be instantaneous changes in velocity and angular velocity during the animation. Generally one wants more smoothness from the interpolation than this.

A common method for generating a C1 function for f1 is by using cubic polynomials. Assume for the moment that somehow at each time ti a derivative f1′(ti) has been specified. For instance, the derivative could be generated by averaging the derivatives of geodesics that connect to the adjacent key-frames, or the user could specify the derivative in addition to the position. In any case, there is a unique cubic polynomial p defined on [ti,ti+1] such that

  1. p(ti)=f1(ti)
  2. p(ti+1)=f1(ti+1)
  3. p′(ti)=f1′(ti)
  4. p′(ti+1)=f1′(ti+1)

A piecewise cubic polynomial created in this manner is C1 continuous because the first derivatives match up at the key-frames.

Because the interest is in animation, one cares about the complete parametric function, and not just the image the function has. In particular, different reparameterization of a function will be considered different.

Riemannian Cubic Polynomials

The interpolation problem is solved over ℝ3, but what about SO(3)? The rest of this paper will give the basic theory of cubic polynomials over general Riemannian manifolds. How to compute such curves will not be discussed. From here on we will focus on the problem of finding an interpolating function f:[a,b]→M on a complete n-dimensional Riemannian manifold M subject to the conditions

  1. f(a)=p:M
  2. f(b)=q:M
  3. Tf(a)=ξ:TpM
  4. Tf(b)=η:TqM

There are many smooth functions that could be used to interpolate between the given points and the given tangent vectors. In the case of Euclidean space, the cubic polynomial solution is the unique solution that minimizes the functional J:Ω→ℝ

J(f)= ∫[a,b]<DtTf(t), DtTf(t)>dt

where Ω is the space of all C1 piecewise smooth functions [a,b]→M.

This quantity, J(f), is basically a measure of the total acceleration of the curve. We will call any function which is a critical point of J a cubic polynomial.

Theorem. A curve f:[a,b]→M is a cubic polynomial if and only if it is smooth and it satisfies the fourth-order differential equation

Dt3Tf+R(DtTf,Tf)Tf=0.

where R is the curvature of M.

Proof. See Noakes, Heinzinger and Paden, p. 468, Theorem 1.

This formula is the Euler-Lagrange equation. In the special case of Euclidean space R=0 and the Euler-Lagrange equation reduces to

Dt3Tf=d4f/dt=0

and this implies that f is a cubic polynomial.

Jacobi Fields

The Euler-Lagrange equation gives necessary conditions for finding the minimum of the functional J. To find sufficient conditions for a function f to locally minimize J, it is useful to study Jacobi fields along the curve f. The development of Jacobi fields on cubic polynomials parallels the development of Jacobi fields for geodesics. For example, Lee gives a presentation of the theory of geodesics.

The development is so similar that one might hope that one could describe it by using the theory of geodesics on TM with a suitable metric. Camarinha shows that for a generalization of cubic polynomials called elastic curves, such a reduction is possible by using the Sasaki metric; however in the specific case of cubic polynomials, the reduction does not work.

Crouch and Silva Leite find the Jacobi equation for a vector field W along a cubic polynomial f to be

Dt4W+F(W,Tf)=0

where

F(X,V)= (Dt2R)(X,V)V +(∇XR)(DtV,V) +R(R(X,V)V,V)V +R(X,Dt2V)V +2[(DtR)(DtX,V)V+(DtR)(X,DtV)V] +2R(Dt2X,V)V +3(DtR)(X,V)DtV +3[R(X,V)Dt2V+R(X,DtV)DtV] +4R(DtX,V)DtV

Any vector field along a cubic polynomial that satisfies the Jacobi equation is called a Jacobi field. These definitions of Jacobi fields and Jacobi equations parallel the same definitions in the geodesic case. For comparison, the Jacobi equation for a field W on a geodesic γ is

Dt2W+R(W,)=0

We define a Jacobi variation of a cubic polynomial f to be a smooth function Γ:]-ε,ε[[a,b]→M such that

  1. Γ(0) = f
  2. For all s:]-ε,ε[, Γ(s) is a cubic polynomial.

For each Jacobi variation Γ we define an associated variational vector field W by

W(t)=∂sΓ(0,t).

Theorem. The associated variational vector field W of a Jacobi variation Γ is a Jacobi field. Also every Jacobi field W is the variational vector field for some Jacobi variationΓ.

Proof. See Camarinha, Silva Leite and Crouch, p. 117. Theorem 4.2.

Since the Jacobi equation is a linear fourth order differential equation, each Jacobi field W is uniquely determined by its value at a and its first three covariant derivatives at a.

  1. W(a)
  2. DtW(a)
  3. Dt2W(a)
  4. Dt3W(a)

Each cubic polynomial f admits two trivial Jacobi fields the same way that each geodesic γ admits two trivial Jacobi fields. The first field is W=Tf and the second field is W=tTf. These are the associated variational vector fields of Γ(s,t)=f(s+t) and Γ(s,t)=f(est) respectively.

These trivial Jacobi fields arise from trivial reparameterizations of the cubic polynomial f. In the case of geodesics the class of normal Jacobi fields are studied. It can be shown that for Jacobi fields W of geodesics γ there are α,β:ℝ such that <W(t),(t)>=αt+β. This function is identically 0 when W is a normal Jacobi field. We cannot expect to have this same property in the case of cubic Jacobi fields, but there is a similar relation.

Theorem. For any Jacobi field W along a cubic polynomial f:[0,b]→M

<Dt2W(t),Tf(t)> -2<DtW(t),DtTf(t)> +3<W(t),Dt2Tf(t)>= αt+β

where

α= <Dt3W(0),Tf(0)> -<Dt2W(0),DtTf(0)> +<DtW(0),Dt2Tf(0)> -3<W(0),R(DtTf(0),f(0))f(0)>

and

β= <Dt2W(0),Tf(0)> -2<DtW(0),DtTf(0)> +3<W(0),Dt2Tf(0)>

Proof. See Camarinha, Silva Leite and Crouch, p. 114. Lemma 3.3.

Most Jacobi fields W can be decomposed into the sum of three Jacobi fieldsW=δ1Tf+δ2tTf+Z where δ1,δ2:ℝ. Z can be thought of the non-trivial portion of the Jacobi field W. In fact <Dt2Z,Tf>-2<DtZ,DtTf>+3<Z,Dt2Tf>=0. This fact is stated in the following theorem.

Theorem. If 2<Dt2Tf,Tf>-<DtTf,DtTf>≠0 then every Jacobi field W along a cubic polynomial f can be uniquely decomposed into the form W=δ1Tf+δ2tTf+Z where δ1,δ2:ℝ and Z is a Jacobi field such that <Dt2Z,Tf>-2<DtZ,DtTf>+3<Z,Dt2Tf>=0.

Proof. See Camarinha, Silva Leite and Crouch, p. 115, Theorem 3.4.

Even in the geodesic case, there fails to be a unique decomposition in the case that =0. The case 2<Dt2Tf,Tf>-<DtTf,DtTf>=0 in the above decomposition theorem is somewhat analogous to the geodesic case where the geodesic is just a single point.

Conjugate Points

The discussion of Jacobi fields has focused on cubic polynomials in general. However for our interpolation problem we are interested in cubic polynomials that interpolate between end points having given tangent vectors. In general it is possible that there may not be one unique cubic polynomial that interpolates the endpoint conditions. In some cases one can find a Jacobi variation of a cubic polynomial f where all curves in the family satisfy the the end point conditions. When this happens the two endpoints are considered conjugate along the curve f. The notion of being conjugate is slightly more general and is given in the following definition

For a cubic polynomial f, the points t1,t2:[a,b] are said to be conjugate along f if there is a non-zero Jacobi field W along f such that

  1. W(t1)=0
  2. W(t2)=0
  3. DtW(t1)=0
  4. DtW(t2)=0

The conjugate points have a multiplicity equal to the dimension of the subspace of all such Jacobi fields.

This definition of conjugate points is analogous the the definition of conjugate points for geodesics. The results about conjugate points on cubic polynomials are also similar.

Theorem. If a and b are not conjugate along a cubic polynomial f, then any Jacobi field W along f is uniquely determined by its values of

  1. W(a)
  2. W(b)
  3. DtW(a)
  4. DtW(b)

Proof. See Camarinha, Silva Leite and Crouch, p. 118, theorem 5.2.

The Second Variation Formula

For a cubic polynomial f define TfΩ to be the space of C1 piecewise smooth vector fields X on f satisfying

  1. X(a)=0
  2. X(b)=0
  3. DtX(a)=0
  4. DtX(b)=0

Using the tool of Jacobi fields we can now turn out attention to finding a sufficient condition for a cubic polynomial f to be a local minimum of our functional J. The idea is to create a second derivative test for our functional J. There is a symmetric bilinear form on TfΩ on f called the index form.

If(X,Y)=∫[a,b]<Dt2X,Dt2Y>+<X,F(Y,Tf)>dt

where F is defined as before.

Theorem. If f is a cubic polynomial, that locally minimizes J, then If is positive semi-definite.

Theorem. If f is a cubic polynomial and there are two points t1 and t2 which are conjugate along f, then there is some vector field X on f such that If(X,X)<0. Hence f does not minimize J.

Proof. See Camarinha, Silva Leite and Crouch, p. 123, theorem 7.2.

We also have that sufficiently small segments of cubic polynomials are local minimizers of J.

Theorem. For a cubic polynomial f, if [a,b] is sufficiently small then f is a local minimizer of J and a and b are not conjugate alongf.

Proof. See Camarinha, Silva Leite and Crouch, p.129-130, Corollary 8.3 and Corollary 8.4.

Index Theorem

The analogue of the Morse index theorem holds in the case of cubic polynomials as well. For a cubic polynomial f define the index of If to be the maximal dimension of a subspace of TfΩ where If is negative definite.

Theorem. The index of If is equal to the number of points t0:]a,b[ which are conjugate to a along f counted with its multiplicity.

Global Minimizer

Finally it can be show that there are globally minimizing functions on J. Let H2([a,b];ℝn)⊆L2([a,b];ℝn) denote the Sobolev space of C1 functions having all their first and second derivative in L2([a, b]; ℝn). Let H2([a,b];M) be the set of all functions f:[a,b]→M such that whenever (U,φ) is a local chart of M and I⊆[a,b] is a closed subinterval such that f(I)⊆U, then φf|IH2(I;ℝn). Finally, given p,q:M, and ξ:TpM and η:TqM, let H2ξ,η be the set of all functions fH2([0,1];M) such that f(0)=p, f(1)=q, Tf(0)=ξ, and Tf(1)=η. On this set the existence of a global minimizer can be shown.

Theorem. The functional J attains its minimum on H2ξ,η.

Proof. See Giamb, Giannoni and Piccione, p.451, Proposition 3.3.

References

Crouch, P. & Silva Leite, F. (1995) The dynamic interpolation problem on Riemannian manifolds, Lie groups and symmetric spaces. J. Dynam. Control Systems, 1, 177-202.
Camarinha, M. (1996) The Geometry of Cubic Polynomials on Riemannian Manifolds, Ph. D. Thesis in Pure Mathematics, University of Coimbra (Portugal).
Camarinha, M., Silva Leite, F. & Crouch, P. (2001) On the geometry of Riemannian cubic polynomials. Diff. Geom. Appl., 15, 107-135.
Giamb, R., Giannoni, F. & Piccione, P. (2002) An analytic theory for Riemannian cubic polynomials. IMA J. Math. Control Inform., 19, 445-460.
Lee, John M. Riemannian Manifolds: An Introduction to Curvature. Springer-Verlag, New York, 1997
Noakes, L., Heinzinger, G. & Paden, B. (1989) Cubic splines on curved spaces. IMA J. Math. Control Inform., 6, 465-473.