Keywords

1 Introduction

The problem of constructing smooth interpolating curves in non-linear spaces, or manifolds plays an important role in a wide variety of applications. For instance, interpolation in the rotation group SO(3) has immediate application not only in computer graphics and animation of 3D objects [1,2,3], but also in applications ranging from robot motion planning to machine vision [4,5,6]. Such applications encourage us to further search for some efficient methods to generate smooth interpolating curves on non-linear spaces.

Motivated by potential applications in engineering science and technology, our goal is to develop a new framework for generating \(C^{2}\) Bézier curves on Riemannian manifolds that interpolate a given ordered set of points at specified time instants. While quite general, we will focus on a special class of Riemannian symmetric spaces. The task of constructing interpolating curve on SO(n) has attracted the attention of several authors. One of the most widely cited approaches is the work of Shoemake [7] on SO(3), who adopts a re-parametrization of the rotation matrices based on unit quaternion representation. Shoemake’s approach can essentially be viewed as a generalization of the de Casteljau’s algorithm for Bézier curves to SU(2) in which two elements of SO(3) are interpolated by the geodesic that joins them. Although this algorithm seems computationally efficient, unfortunately the resulting curve depends on the choice of local system coordinates. A few years later, taking into account the Shoemake algorithm, a more careful geometric analysis of unit-quaternion-based method was introduced by Barr et al. [1], Hart et al. [8], Ge and Ravani [9], and Nielson et al. [10]. Despite the fact of producing an intrinsic curves, these approaches does not generalize to higher-dimensional manifold.

In this paper, we present a novel framework to treat the interpolation problem in the setting of Riemannian geometry and Bézier curve approach. We show that it makes sense to define a \(C^{2}\) interpolating Bézier curve on Riemannian symmetric spaces as the result of a least squares minimization and a recursive algorithm. In particular, we will focus on a special class of Riemannian symmetric spaces: the special orthogonal group SO(n). Indeed, working in such Riemannian manifold allows nice properties to solve the issues above. The key point to give explicit solution for the interpolation problem and ensures the \(C^{2}\) differentiability condition at joint points is the use of global symmetries in these last points. In fact, we will first derive equations for control points of a \(C^{2}\) Bézier curve on the Euclidean space \(\mathbb {R}^{m}\). Then, building upon prior works [6, 11], we use these equations to find the control points of a \(C^{1}\) interpolating Bézier curve on Riemannian manifolds as a generalization of the Bézier based fitting in the Euclidean space and by means of methods of Riemannian geometry. These results are sufficient to give explicit formula for control points of the \(C^{2}\) interpolating Bézier curve on SO(n). The proposed method will be shown to enjoy a number of nice properties and the solution is unique in many common situations.

The rest of the paper is organized as follows. In Sect. 2, we present our new algorithm to construct a \(C^{2}\) Bézier curve on the Euclidean space. This will help with the visualization of its main features and motivate its generalization on SO(n). In Sect. 3, the generalization of our approach on the Lie group SO(n) is prescribed. We conclude the paper with numerical examples and a conclusion.

2 \(C^{2}\) Interpolating Bézier Curves on \(\mathbb {R}^{m}\)

In this section, we first describe our approach on the Euclidean space \(\mathbb {R}^{m}\). For simplicity we will assume that the time instants are \(t_{i}=i\). In this work, we only use Bézier curves of degree 2 and 3 such that the segment joining \(p_{0}\) and \(p_{1}\), as well as the segment joining \(p_{N-1}\) and \(p_{N}\) are Bézier curves of order two, while all the other segments are Bézier curves of order three. Explicitly, the Bézier curve \(\beta _{k}\) of degree \(k \in \left\{ 2,3 \right\} \) are expressed in \(\mathbb {R}^{m}\) with a number of control points \(b_{i}\), represented as their coefficients in the Bernstein basis polynomials by:

$$\begin{aligned}&\beta _2(t;b_0,b_1,b_2)=b_0(1-t)^2+2b_1(1-t)t+b_2t^2,\\&\beta _3(t;b_0,b_1,b_2,b_3)=b_0(1-t)^3+3b_1t(1-t)^2+3b_2t^2(1-t)+b_3t^3.\nonumber \end{aligned}$$

Moreover, we assume that there exists two artificial control points \((\widehat{b}^{-}_{i}, \widehat{b}^{+}_{i})\) on the left and on the right hand side of the interpolation point \(p_{i}\) for \(i=1,...,(N-1)\). Consequently, the Bézier curve \(\beta \) on \(\mathbb {R}^{m}\) is given by:

figure a

Then \(\beta \) is \(C^{\infty }\) on \([t_{i},t_{i+1}]\), for \(i=0,..N-1\). To ensure that \(\beta \) is \(C^{1}\) at knots \(p_{i}\), for \(i=1,..N-1\), we shall make the following assumption:

$$\begin{aligned} \dot{\beta }_{k^i}(b_0^i,...,b_{k^i}^i; t-i+1)|_{t=i}=\dot{\beta }_{k^{i+1}}(b_0^{i+1},...,b_{k^{i+1}}^{i+1}; t-i)|_{t=i}&\quad \quad i=0,...,N-2. \end{aligned}$$
(1)

This differentiability condition allows us to express \(\widehat{b}_{i}^{+}\) in terms of \(\widehat{b}_{i}^{-}\) as:

$$\begin{aligned} \widehat{b}_{1}^{+}&= \frac{5}{3}p_{1}-\frac{2}{3}\widehat{b}_{1}^{-}, \end{aligned}$$
(2)
$$\begin{aligned} \widehat{b}_{i}^{+}&= 2p_{i}-\widehat{b}_{i}^{-},i=2,...,N-2 \end{aligned}$$
(3)
$$\begin{aligned} \widehat{b}_{N-1}^{+}&= \frac{5}{2}p_{N-1}-\frac{3}{2}\widehat{b}_{N-1}^{-}, \end{aligned}$$
(4)

We are left with the task of computing the control points \(\widehat{b}_{i}^{-}\), for \(i=1,...,N-1\), that generate the \(C^{1}\) Bézier curve \(\beta \). In [11], we have shown that solutions of the problem of minimization of the mean square acceleration of the Bézier curve \(\beta \) are exactly the control points of the curve:

$$\begin{aligned}&\min _{\widehat{b}_1^-,...,\widehat{b}_{N-1}^-} E(\widehat{b}_1^-,...,\widehat{b}_{N-1}^-) := \min _{\widehat{b}_1^-,...,\widehat{b}_{N-1}^-} \int _{0}^{1} \Vert \ddot{\beta _{2}^{0}}(t;p_{0}, \widehat{b}_{1}^{-}, p_{1})\Vert ^{2} \nonumber \\&\qquad \qquad \,\,\,\,\,\, +\, \sum _{i=1}^{N-2} \int _{0}^{1} \Vert \ddot{\beta _{3}^{i}}(t;p_{i},\widehat{b}_{i}^{-}, \widehat{b}_{i+1}^{-},p_{i+1})\Vert ^{2} + \int _{0}^{1} \Vert \ddot{\beta _{2}^{N-1}} (t;p_{N-1}, \widehat{b}_{N-1}^{-}, p_{N}) \Vert ^{2} \end{aligned}$$
(5)

It turns out that the optimal solution \(Y=[\widehat{b}_{1}^{-},...,\widehat{b}_{N-1}^{-}]^{T} \in \mathbb {R}^{ (N-1) \times m}\) of (5) is the unique solution of a tridiagonal linear system

$$\begin{aligned} Y = A^{-1}CP = DP \; \text {with} \; \sum _{j=0}^{j=N+1}d_{ij}=1. \end{aligned}$$
(6)

where A is a tridiagonal sparse square matrix of size \((N-1)\times (N-1)\) with a dominant diagonal, C a matrix of size \((N-1)\times (N+1)\) and P the matrix of \(p_i\)’s of size \((N+1)\times m\) given by:

figure b

Now, let us assume that \(\beta \) is \(C^{1}\), so that (1) is met and the solution Y given by (6) is obtained. The additional \(C^{2}\) condition for a \(C^{1}\) curve is the equality of the second derivative at the joint point \(p_{i}\), for \(i=1,...,N-1\):

$$\begin{aligned} \ddot{\beta }_{k^i}(b_0^i,...,b_{k^i}^i; t-i+1)|_{t=i}=\ddot{\beta }_{k^{i+1}}(b_0^{i+1},...,b_{k^{i+1}}^{i+1}; t-i)|_{t=i}&\quad \quad i=0,...,N-2. \end{aligned}$$

It is obvious that with this \(C^{2}\) condition the position of the control points \(\widehat{b}_{i}^{-}\) and \(\widehat{b}_{i}^{+}\) that generate the curve \(\beta \) will be modified. Therefore, it is more convenient to use another notation. Let us denote by \(b^{-}_{i}\) and \(b^{+}_{i}\) the new control points on the left and on the right hand side of the interpolation point \(p_{i}\), for \(i=1,...,N-1\). Computing the acceleration of \(\beta \) on respective intervals and taking into account that \(\beta \) is \(C^{1}\), we shall replace \(b_{1}^{+}\) by (2), \(b_{i}^{+}\) by (3), and \(b_{N-1}^{+}\) by (4). We deduce that:

$$\begin{aligned} b_{2}^{-}&= \frac{1}{3}p_{0}-\frac{1}{2}b_{1}^{-}+\frac{8}{3}p_{1}, \end{aligned}$$
(15a)
$$\begin{aligned} b_{i+1}^{-}&= b_{i-1}^{+}+4p_{i}-4b_{i}^{-}, i=2,...,N-2 \end{aligned}$$
(15b)
$$\begin{aligned} p_{N}&= 2p_{N-1}+ 2b_{N-1}^{+}-6b_{N-1}^{-}+3b_{N-2}^{+}, \end{aligned}$$
(15c)

We see at once that points that will be modified by the additional \(C^{2}\) condition are \(\widehat{b}_{i}^{-}\) and hence \(\widehat{b}_{i}^{+}\), for \(i=2,...,N-1\). The point \(\widehat{b}_{1}^{-}\) remains invariant and consequently it will be the case for \(\widehat{b}_{1}^{+}\). We thus get \(b_{1}^{-}=\widehat{b}_{1}^{-}\), with \(\widehat{b}_{1}^{-}\) is the first row of the matrix Y obtained as a solution of the optimization problem (5). However, the endpoint \(p_{N}\) is affected as we can deduce from Eq. (15c). Nevertheless, it follows that giving the control point \(b_{1}^{-}\) allows us to find all the other control points including \(b_{2}^{-}\) with Eq. (15a) and hence \(b_{2}^{+}\) with (3), then \(b_{i+1}^{-}\) for \(i=2,...,N-2\) with (15b) and therefore \(b_{i}^{+}\), for \(i=3,...,N-2\) with (3) and \(b_{N-1}^{+}\) with (4).

3 \(C^{2}\) Interpolating Bézier Curves On SO(n)

Our objective in this section is to work out concretely the extension of our approach used to find control points that define a \(C^{2}\) Bézier curve in the Euclidean space to the Riemannian manifold SO(n). In other words, given \(R_{0}, ...,R_{N}\) a set of \((N+1)\) distinct points in SO(n) and \(0=t_{0}<t_{1}< ...<t_{N}=N\) an increasing sequence of time instants, we present a conceptually simple framework to construct a \(C^{2}\) Bézier curve \(\gamma : [0,N] \rightarrow SO(n)\) such that \(\gamma (t_{k} ) = R_{k}, \; k=0,...,N\). For the most part of Riemannian manifolds, the generalization of our approach is not straightforward. For the case treated here, of the Lie group SO(n), since it is a symmetric space and all the important geometric functions have nice, closed-form expressions, the problem of finding a \(C^{2}\) Bézier curve that interpolates a given set of points in such space can be completely solved.

Let us start by briefly sketch the differential structure of SO(n). We illustrate this with the geometric toolbox described in Table 1. For more details concerning the differential geometry of SO(n), see [12, 13].

Table 1. Geometric toolbox for the Riemannian manifold SO(n)
Full size table

The shortest geodesic arc joining \(R_{1}\) to \(R_{2}\) in SO(n) can be parameterized explicitly by:

$$\begin{aligned} \alpha (t, R_{1},R_{2}) =R_{1}\exp (t\log (R_{1}^{T}R_{2})) , \; t \in [0,1]. \end{aligned}$$
(16)

and we write:

$$\begin{aligned} \dot{\alpha }(t, R_{1},R_{2}):= \frac{\partial }{\partial u}|_{u=t} \; \alpha (t, R_{1},R_{2}). \end{aligned}$$

Furthermore, for each \(R_{1}\in SO(n)\), there exists a symmetry

$$ \varphi _{R_{1}}: SO(n) \longrightarrow SO(n), \; R_{2} \longrightarrow R_{1}R_{2}^{T}R_{1}$$

that reverses geodesics through \(R_{1}\). It is easy to check that \(\varphi _{R_{1}}\) is an isometry and thus SO(n) turns into a Riemannian symmetric space. For \(R_{1}, R_{2} \in SO(n)\), let us denote by \((d \text {Exp}_{R_{1}})_{H}\) the derivative of \( \text {Exp}_{R_{1}}\) at \(H \in T_{R_{1}}SO(n)\) and by \((d\varphi _{R_{1}})_{R_{2}}\) the derivative of the geodesic symmetry \(\varphi _{R_{1}}\) at \(R_{2}\). Then, the following result can be easily proved and will be very important for the derivation of the results presented along this section.

Lemma 1

Let \(R_{1} \in SO(n)\).

  1. (i)

    \((d\varphi _{R_{1}})_{R_{2}}^{-1} = (d\varphi _{R_{1}})_{\varphi _{R_{1}}(R_{2})}, \; \text {for all} \; R_{2} \in SO(n) \)

  2. (ii)

    \((d \text {Exp}_{R_{1}})^{-1}_{H}= - (d \text {Exp}_{R_{1}})_{-H}\circ (d\varphi _{R_{1}})_{ \text {Exp}_{R_{1}}(H)} , \; \text {for all} \; H \in T_{R_{1}}SO(n) \)

Let us now denote by \(\gamma _{k}(t,V_{0},...,V_{k}) \) the Bézier curve of order \(k \in \lbrace 2,3 \rbrace \) on SO(n) with a number of control points \(V_{i}\) for \(i=0,...,k\). Furthermore, similar to the Euclidean case, we will suppose that there exists two artificial control points \((\widehat{Z}^{-}_{i}, \widehat{Z}^{+}_{i})\) on the left and on the right hand side of the interpolation point \(R_{i}\) for \(i=1,...,(N-1)\). Hence, the Bézier Curve \(\gamma :[0,N] \longrightarrow SO(n)\) is defined by:

figure c

In order to obtain equations that govern the control points of the \(C^{2}\) Bézier curve on SO(n), one should begin to compute \((\widehat{Z}^{-}_{i}, \widehat{Z}^{+}_{i})\), for \(i=1,...,N-1\), control points of the Bézier curve \(\gamma \) that ensure the \(C^{1}\) differentiability condition of \(\gamma \) at knots \(R_{i}\) on SO(n). To do this, our main idea is to treat the fitting problem on the tangent space \(T_{R_{i}}SO(n)\) at a point \(R_{i} \in SO(n)\) as for the Euclidean case. Consequently, for each \(i=1,...,N-1\), we would like to transfer the data \(R_{0}, ...,R_{N}\) in each tangent space \(T_{R_{i}}SO(n)\) using Riemannian logarithmic map. The mapped data are then given by \(Q=(Q_{0}^{i},...,Q_{N}^{i})\) with \(Q_{k}^{i}= \text {Log}_{R_{i}}(R_{k})\) for \(k=0,...,N\). Applying our approach used to define a \(C^{2}\) Bézier curve on the Euclidean space \(\mathbb {R}^{m}\) in each tangent space \(T_{R_{i}}SO(n)\), for \(i=1,...,N-1\), provides a natural and intrinsic method to compute control points \((\widehat{Z}^{-}_{i}, \widehat{Z}^{+}_{i})\) of the desired \(C^{1}\) Bézier curve \(\gamma \) on SO(n).

Theorem 1

Let \(R_{0},...,R_{N}\) be a finite sequence of distinct points in the special orthogonal group SO(n) with \(R_{i}^{T}R_{k}\), \(i \ne k\), sufficiently close to \(I_{n}\). For each \(i=1,...,N-1\), \(Q=(Q_{0}^{i},...,Q_{N}^{i})\) are the corresponding mapped data in the tangent space \(T_{R_{i}}SO(n)\) at \(R_{i}\) defined by \(Q_{k}^{i}= \text {Log}_{R_{i}}(R_{k}) \) for \(k=0,...,N\). Set \(t_{0}=0<...<t_{N}=N\) a sequence of time instants. Then, there exists a unique matrix \(X_{i}=[(B_1^1)^{-}, ...,(B_{N-1}^1)^{-} ]^{T} \in \mathbb {R}^{n(N-1)\times n }\) containing the \((N-1)\) control points that generate the \(C^{2}\) Bézier curve \(\beta _{i}\), in each tangent space \(T_{R_{i}}SO(n)\) and a matrix \(\tilde{Q}=[\tilde{Q}_{0}^{i},...,\tilde{Q}_{N}^{i}]^{T}\) of size \( n(N + 1)\times n\) containing the new \((N + 1)\) interpolation points in each tangent space \(T_{R_{i}}SO(n)\).

figure d

Proposition 1

Under the same hypotheses of Theorem 1, there exists a unique matrix \(Z=[\widehat{Z}_{1}^{-},...,\widehat{Z}_{N-1}^{-}]^{T} \in \mathbb {R}^{n(N-1)\times n}\), containing the \((N-1)\) control points that generate the Bézier curve \(\gamma \) interpolating the points \(R_{i}\) at \(t_{i}\) on SO(n), for \(i=0,...,N\). The rows of \(\widehat{Z}\) are given by:

$$\begin{aligned} \widehat{Z}_{i}^{-}= \text {Exp}_{R_{i}}(\tilde{x}_{i}), \; i=1,...,N-1. \end{aligned}$$
(17)

where \(\tilde{x}_{i}\), represent the row i of \(X_{i}\) in \(T_{R_{i}}SO(n)\), for \(i=1,..,N-1\). Moreover, the new \((N + 1)\) interpolation points in SO(n) are given by:

$$\begin{aligned} \tilde{R}_{k}= \text {Exp}_{R_{i}}( \tilde{Q}_{k}^{i}), \; k=0,...,N; \; i=1,...,N-1. \end{aligned}$$
(18)

Algorithm 1 provides a detailed exposition of the steps of the proof of Theorem 1 and Proposition 1.

Corollary 1

The Bézier path \(\gamma : [0,1] \rightarrow SO(n)\) is \(C^{1}\) on SO(n).

Proof

The following result may be proved in much the same way as Corollary 3.3. in [11].

Fig. 1.
figure 1

Example of an interpolating path on SO(3) applied to rotate a 12 sided dice at given time instants (1, 5, 9, 13).

Full size image

We are now in a position to formulate the main theorem of this section, which contains the counterpart of the equations derived in the last section that generate control points of a \(C^{2}\) Bézier curve on \(\mathbb {R}^{m}\). Let us assume that \(\gamma \) is \(C^{1}\), so that the solution \(\widehat{Z}\) is obtained. Let us denote by \(Z_{i}^{-}\) and \(Z_{i}^{+}\) the new control points on the left and on the right side of the interpolation point \(\tilde{R}_{i}\) that generate the \(C^{2}\) Bézier curve \(\gamma \) on SO(n). The key point to find the control points \(Z_{i}^{-}\), for \(i=1,...,N-1\) is similar to the Euclidean case. That is, we might know \(Z_{1}^{-}\) (and therefore \(Z_{1}^{+}\) by the \(C^{1}\) differentiability condition on SO(n)) and wish to define iteratively \(Z_{i}^{-}\) for \(i=2,...,N-1\) (and obviously \(Z_{i}^{+}\) in much the same way as \(Z_{1}^{+}\)).

figure e

Theorem 2

Let \(\tilde{R}_{0},...,\tilde{R}_{N}\) be a set of distinct points in the special orthogonal group SO(n) given by Eq. (18) and \(\alpha (t)\) the shortest geodesic arc joining control points of the curve \(\gamma \) on SO(n) given by Eq. (16). Let \(X_{1}=[(B_1^1)^{-}, ...,(B_{N-1}^1)^{-} ]^{T}\) be the matrix of size \(n(N-1)\times n\) containing the control points of the \(C^{2}\) Bézier curve \(\beta _{1}\) in \(T_{R_{1}}SO(n)\). Then, there exists a unique matrix \(Z=[Z_{1}^{-},...,Z_{N-1}^{-}]^{T} \in \mathbb {R}^{n(N-1)\times n}\), containing the \((N-1)\) control points that generate the \(C^{2}\) Bézier curve \(\gamma \) interpolating the points \(\tilde{R}_{i}\) at \(t_{i}\) on SO(n), for \(i=0,...,N\). The rows of Z are given by:

  1. (i)

    \(Z_{1}^{-} = \text {Exp}_{R_{1}}((B_1^1)^{-})\).

  2. (ii)

    \(Z_{2}^{-} = \text {Exp}_{Z_{1}^{+}}\left( \frac{1}{3} \left( (d\varphi _{\tilde{R_{1}}})_{Z_{1}^{-}} \left( \dot{\alpha }(1,\tilde{R_{0}},Z_{1}^{-}) \right) - 4\dot{\alpha }(0,Z_{1}^{-},\tilde{R_{1}})\right) \right) \).

  3. (iii)

    \(Z_{i+1}^{-} = \text {Exp}_{Z_{i}^{+}}\left( \left( (d\varphi _{\tilde{R_{i}}})_{Z_{i}^{-}} \left( \dot{\alpha }(1,Z_{i-1}^{+},Z_{i}^{-}) \right) - 2\dot{\alpha }(0,Z_{i}^{-},\tilde{R_{i}})\right) \right) \),

    \(i=2,...,N-2\).

We illustrate the proposed method to construct a smooth interpolating path on SO(3) from four rotation matrices \(R_1\), \(R_2\), \(R_3\), and \(R_4\). We display the result in Fig. 1 where rotations are applied to rotate a 12 sided dice and the given time instants are displayed in a box. We can easily check that the resulting curve path is smooth including at the interpolation points.

4 Conclusion

In this paper, we have introduced a new framework and algorithms to study the fitting problem of \(C^{2}\) Bézier curves to a finite set of time-indexed data points on the special orthogonal group SO(n). The proposed method takes into account the global symmetries defined in the joint points. Therefore, the presented approach is valid on any locally symmetric space and other Riemannian symmetric spaces. In the future, we intend to extend the theory and then apply it to more general nonlinear manifolds.