[1]Tsung-Wei Hu

[1]Department of Mathematics, University of Georgia, Herty Drive, Athens,
30602, Georgia, U.S.A

2]Department of Mathematics, University of Georgia, Herty Drive, Athens,
30602, Georgia, U.S.A

# A Construction of Interpolating Space Curves with Any Degree of Geometric
Continuity

<EMAIL_ADDRESS>Ming-Jun Lai<EMAIL_ADDRESS>*  [

###### Abstract

This paper outlines a methodology for constructing a geometrically smooth
interpolatory curve in $\mathbb{R}^{d}$ applicable to oriented and flattenable
points with $d\geq 2$. The construction involves four essential components:
local functions, blending functions, redistributing functions, and gluing
functions. The resulting curve possesses favorable attributes, including
$G^{2}$ geometric smoothness, locality, the absence of cusps, and no self-
intersection. Moreover, the algorithm is adaptable to various scenarios, such
as preserving convexity, interpolating sharp corners, and ensuring sphere
preservation. The paper substantiates the efficacy of the proposed method
through the presentation of numerous numerical examples, offering a practical
demonstration of its capabilities.

###### keywords:

Spline, interpolation, Smooth curve, CAGD

##  1 Introduction

Curves are fundamental geometric objects with applications in various fields
that require different types of curve construction and design. The study of
constructing smooth interpolatory space curves has been ongoing for many
decades. In this paper, we are interested in constructing space curves in
$\mathbb{R}^{d}$ with $d\geq 3$, aiming to satisfy the following requirements:

  * •

interpolation, that is, the curve $\Gamma$ passes the given designed points;

  * •

smoothness, that the curve must be geometrically smooth $G^{r}$ with $r\geq
1$, We shall present our construction of $G^{2}$ curves in this paper.

  * •

locality, i.e., any local change of the given points only affects the curve
locally.

  * •

no cusp points and no self-intersection unless there is such a need;

  * •

convexity control capability;

  * •

conic preservation, i.e. if a part of the given data points is from a sphere,
the curve passing these points is also on the sphere.

  * •

invariant under the translation and rotation of the data points;

  * •

corner points are also possible. In particular, the sharpness of the corner
points is controllable.

Many approaches are available in the literature and practice to construct
smooth space curves due to the active study in the last several decades.
However, constructive methods satisfying all the above requirements are few,
The requirement of the high order smoothness, say $C^{2}$ is one of the main
hurdles for interpolating curve construction. The high-order smoothness needs
a lot of more parameters than the construction of $C^{1}$ curves and hence the
parameters are hard to control while easy to produce the cusps and/or
overshoots in the curve. It is well-known that the smoothness of the
parametric functions for a curve does not ensure the smoothness of the graph
of the curve or a geometrically continuous curve. An example will be presented
in Example 2.1. Typically, the distinction between the ”smoothness of graph”
and ”smoothness of function” is made using the concept of geometric continuity
(cf. [1] [2] [3]). In this paper, we define the geometric continuity of a
curve by considering the regularity of its parametric functions. Please refer
to Section 2.3 for the formal definition.

Let us first present two examples of curves based on our construction in
Figure 1 and Figure 2. We give sets data set $\\{{\bf v}_{1},{\bf
v}_{2},\cdots,{\bf v}_{N}\\}$ in $\mathbb{R}^{3}$ which are oriented data
sets, and the data sets are flattenable to be explained in Definition 2.1.
These figures show that our construction works nicely for various sizes of
data points. In Figure 1, we have 20 points while in Figure 2, we have 2776
space points. More examples will be given in a later section to demonstrate
that our construction can preserve the corners, preserve circle or sphere when
the data points are on a circle or on a sphere.

Figure 1: A $C^{2}$ smooth interpolating curve(right) based on a Lissajous
knot (left). The curvature of the curve is shown by the color on the curve.
The curve change shows that the curvatures are all continuous.

Figure 2: A $C^{2}$ smooth interpolating curve(bottom) based on a plane data
(top).

Our method of construction shares similar steps with previous methods in the
literature. More precisely, our algorithm can be decomposed into four parts:
local curve construction, redistribution, blending function construction, and
gluing two pieces together. Let us quickly outline each of the four components
as follows.

  * •

Local Curves Consider the series of points $\\{{\bf v}_{1},{\bf
v}_{2},\cdots,{\bf v}_{N}\\}\subset\mathbb{R}^{n}$, we define a local curve
${\bf f}_{i}(t)$ be a the curve pass ${\bf v}_{i-1},{\bf v}_{i},{\bf
v}_{i+1}$, where ${\bf f}_{i}(t_{j})={\bf v}_{j}$ for $j=i-1,i,i+1$. There are
few canonical options for local curves: parabola, circle, or Bézier curves. We
shall explain them in much more detail in Section 3.1.

  * •

Redistribution Once we have a local curve (function) ${\bf f}_{i}(t)$, the
reparametrization of the function will not change the graph. Therefore, we can
reparametrize the curve in a conventional way. One of the convenience ways is
let $t(s)$ where $t(j)=t_{j}$ for $j=i-1,i,i+1$, and $t(s)$ is linear on
$[i-1,i]$ and $[i,i+1]$. We define ${\bf F}_{i}(s)={\bf
f}(t(s)):[i-1,i+1]\to\mathbb{R}^{n}$. Note that $t(s)$ is piecewise linear, so
${\bf F}_{i}$ is only $C^{0}$, but since it parametrizes the same curve as
${\bf f}(t)$, so ${\bf F}_{i}(s)$ is still has a smooth graph.

  * •

Blending Function For short, a blending function is a pair of functions
$B_{1},B_{2}:[0,1]\rightarrow[0,1]$ with $B_{1}(0)=B_{2}(1)=0$,
$B_{1}(1)=B_{2}(0)=1$, and $B_{1}(s)+B_{2}(s)=1$ for all $s\in[0,1]$. One can
understand it by weighted functions of endpoints $0$ and $1$. We shall impose
an additional assumptions on the derivative in need for the smoothness, see
details in Section 3.3.

  * •

Gluing Two Pieces Together After redistribution, ${\bf F}_{i}$ and ${\bf
F}_{i+1}$ have over lapping domain $[i,i+1]$. We can define a new function

$\Gamma(s)=\begin{cases}{\bf F}_{i}(s)&s\in[i,i-1)\\\ {\bf
F}_{i}(s)B_{1}(s-i)+{\bf F}_{i+1}(t)B_{2}(s-i)&s\in[i,i+1]\\\ {\bf
F}_{i+1}(s)&s\in(i+1,i+2]\end{cases}$

More generally, if we have a continuous function
${\bf\phi}(s,u):[i,i+1]\times[0,1]\to\mathbb{R}^{n}$ with ${\bf\Phi}(s,1)={\bf
F}_{i}$ and ${\bf\Phi}(s,0)={\bf F}_{i+1}$, we can gluing the function as

$\Gamma(s)=\begin{cases}{\bf F}_{i}(s)&s\in[i,i-1)\\\
{\bf\Phi}(s,B_{1}(s-i))&s\in[i,i+1]\\\ {\bf
F}_{i+1}(s)&s\in(i+1,i+2]\end{cases}$

This is particularly useful if we know some extra features of the original
data. For instance, in the section on numerical experimental results, we will
have two examples to show when the point data are on the sphere, we can make
sure our interpolating curve is on the same sphere as well by choosing a
suitable $\bf\Phi$.

###  1.1 Related works

The realm of curve construction is vast, and a complete overview is not within
the scope of this paper. Here, we present a selection of essential works that
are more related to our work. Farin [4] provides a thorough organization of
curve interpolation methods using $B$-splines in his book. He also discusses
Bézier curves, a group of smooth curves based on polynomials. Two primary
challenges associated with Bézier curves are the need for a local shape
control algorithm adaptable to various cases and the difficulty in achieving a
higher order of continuity due to the flexibility in choosing control points.
To achieve a local shape control, various methods are employed to interpolate
curves. One example is the Non-uniform Rational B-spline (NURB) [5], which
utilizes a rational polynomial as a substitute for the conventional
polynomial. This substitution provides a broader range of shape options with a
reduced number of control points. Addressing the specific need for circle
interpolation, a blending technique of the circular functions was introduced
[6]. Notably, Yuksel [7] made significant advancements by replacing the local
circular function with an ellipse function when the given data points deviate
from a circle. Another noteworthy approach involves the use of clothoids to
interpolate curves, offering a method for achieving curves with uniform
curvature changes [8]. While these algorithms enhance curve fitting in diverse
scenarios, it’s important to note that they may introduce increased curve
complexity, and the highest achievable smoothness of these algorithms are
limited to $G^{2}$.
Some approaches center around polynomials and aims to enhance smoothness. One
approach is to interpolate the curve independently along different axes. Let
${\bf v}_{i}=(x_{i},y_{i},z_{i})$, one can interpolate $x_{i}$, $y_{i}$, and
$z_{i}$ by $X(t)$, $Y(t)$, and $Z(t)$, where
$(X(t_{i}),Y(t_{i}),Z(t_{i}))=(x_{i},y_{i},z_{i})$ for
$t_{1}<t_{2}<\cdots<t_{i}<\cdots<t_{N}$. Further details are expounded in the
book by Knott [9]. Subsequent to this, Lee refined the selection of $t_{i}$
[10] and made the curve more appealing. Key challenges associated with
interpolating along different axes include the absence of locality and a
deficiency in rotational stability.

Our algorithm is grounded in the notion of blending functions. By introducing
the $r$-blending function, one can craft an interpolation function with a
desired shape and achieve any desired level of smoothness. We redefine
geometric continuity in an alternative manner and provide a robust methodology
for generating curves without cusps or self-intersections.

###  1.2 Organization of the paper

The paper is organized as follows. We will explain the concept of the oriented
data point set and points that are flattenable. Then, we explain the concept
of geometric continuity and the geometrical smoothness of the graph of a
curve. These will be done in Section 2. we explain our constructive steps with
emphasis on the four components that we explained in the introduction. We will
give a very general definition of these components and provide a detailed
justification of how smooth these curves are. We also use the ideas to create
a few new categories of curves that achieve any given smoothness while
consisting of piecewise polynomials or preserving the shape of a circle and/or
sphere.

##  2 Preliminaries

In this section, we first explain the concepts of oriented point sets and
flattenable point sets. Then, we explain the regularity of a graph and
geometric continuity/smoothness.

###  2.1 Oriented Set of Points and Flattenable Points

Consider the set of space points ${\bf v}_{i},i=1,\cdots,N$ in
$\mathbb{R}^{n}$ which is oriented in the sense that ${\bf v}_{i}$ is
connected to ${\bf v}_{i+1}$ for all $i=1,\dots,N-1$ in the setting of space
curves. We call it sometimes a 1D-oriented point set, sometimes an oriented
curve data set, or sometimes a curve data set, just for simplicity. Next, we
introduce the concept of flattenable points.

######  Definition 2.1.

An 1D-oriented point set $\\{{\bf v}_{i},i=1,\cdots,N\\}\subset\mathbb{R}^{n}$
is said to be flattenable if for any three consecutive points ${\bf
v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ there exist a line $L_{i}$ in
$\mathbb{R}^{n}$ such that the projections of these three points ${\bf
v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ to $L_{i}$ preserve the order of these
three points, i.e. the projection of ${\bf v}_{i}$ is in the middle of the
projections of ${\bf v}_{i-1}$ and ${\bf v}_{i+1}$.

###  2.2 Regularity of the Graph of Curves

Consider a curve consisting of points in $\mathbb{R}^{n}$ which are defined by
one variable parametric functions. For instance, a non-self intersects curve
in $\mathbb{R}^{n}$ can be defined by $\Gamma(t)=(x_{1}(t),\ldots,x_{n}(t))$,
where $t\in[a,b]$ for an interval $[a,b]$ and $x_{i}(t),i=1,\cdots,n$ are
coordinate functions of $\mathbb{R}^{n}$, where $n\geq 2$. We call $\Gamma(t)$
a parametrization function of the arc, and the arc which it parameterized is
called the graph of $\Gamma$. Obviously, if $\Gamma(t)$ is continuous, then
its graph is continuous. However, the parametrization functions’ smoothness is
insufficient for the graph to be smooth. Let us look at the following example.

######  Example 2.1.

Let $\Gamma(t)=(t^{2},t^{3})$ for $t\in[-1,1]$. The parametric functions are
differentiable, but the graph of $\Gamma(t)$ is not. As shown in Figure 3, the
curve has a cusp at $t=0$. That is, the smoothness of the parametric functions
did not guarantee that the graph of the parametric curve looks smooth.

Figure 3: The differentiability of the parametric functions of
$\Gamma(t)=(t^{2},t^{3}),t\in[-1,1]$ does not imply the graph is smooth.

In the Example 2.1, the cusp happens at $t=0$ where the tangent vector
$\Gamma^{\prime}(0)$ vanishes. Indeed, if the graph looks smooth, it should at
least have a continuous tangent. However, the $C^{1}$ of its parametric
function does not imply this property as we saw in the Example 2.1. To
distinguish the ideas, we call a graph of a parametric function has a
geometric continuity of degree 1 (denoted as $G^{1}$) if it has tangent lines
on each point on it. If we think about the sufficient condition for a
parametric function to have a $G^{1}$ graph, we use the following definition:

######  Definition 2.2.

A $C^{1}$ parametrization function $\Gamma(t)=(x_{1}(t),\cdots,x_{n}(t))$ is
said to be regular at $t\in(a,b)$ if
$\|\Gamma^{\prime}(t)\|:=\|(x_{1}^{\prime}(t),\cdots,x_{n}^{\prime}(t))\|>0$.

The vanish of the first derivative of $\Gamma$ gives us the graph without
continuous tangent. We can easily see the following property is true.

######  Proposition 2.2.

If a pasteurization function $\Gamma(t):[a,b]\to\mathbb{R}^{n}$ is regular,
then its graph is $G^{1}$.

We may now extend the ideas to the high order of geometric smoothness. In
addition, if $\Gamma(t)$ is $C^{2}$ continuously differentiable in parameter
$t$, its curvature which can be formulated as [11]:

$\kappa(t)=\dfrac{\sqrt{\|\Gamma^{\prime}(t)\|^{2}\|\Gamma^{\prime\prime}(t)\|^{2}-\|\Gamma^{\prime}(t)\cdot\Gamma^{\prime\prime}(t)\|^{2}}}{\|\Gamma^{\prime}(t)\|^{3}}$
(1)

Since $\Gamma^{\prime}(t)\not=0$, the curvature is well defined. If the
curvature is continuous, we can say that the graph of $C^{2}$ parametric curve
has continuous tangent and curvature. In general, the non-vanish of the first
derivative is sufficient for a $C^{r}$ curve that has geometric continuity up
to order $r$.

To summarize, the regularity of the parameterization makes the graph have
geometric continuity up to the smoothness of the parameterization. We remark
that:

######  Remark 2.1.

A $C^{1}$ regular curve has continuous tangents on its graph. A $C^{2}$
regular curve has continuous curvatures of its graph.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$ Figure 4: The graph of a curve is not necessary to be $G^{r}$ without
the regularity of the parametric functions.

In the end of this subsection, let us present an example that a linear
combination of two regular curve pieces may not be regular any more.

######  Example 2.3.

Let ${\bf F}(t)=(0.5+4(t-0.5)^{3},t(1-t)^{2})$, ${\bf
G}(t)=(0.5+4(t-0.5)^{3},t^{2}(1-t))$ and 1-blending function
$B_{1}=1-B_{2}=1+2t^{3}-3t^{2}$ with $B_{2}=-2t^{3}+3t^{2}$. ${\bf F}$ and
${\bf G}$ are $C^{r}$ regular curve with $r\geq 1$ which connect two points
$(0,0)$ and $(1,0)$ for $t\in[0,1]$. However, the weighted sum ${\bf
F}(t)B_{1}(t)+{\bf G}(t)B_{2}(t)$ is not regular and not $G^{1}$ at $t=0.5$.
See the graph on the right of Figure 5.

Figure 5: A linear combination of two regular curves may not be regular

###  2.3 Connection of Geometric Continuity Curves

For curves, the regularity of its parametric function can guarantee nice-
looking graphs. However, in most practical applications, joining multiple
curves with different parametric functions is required to express a long
curve. That is, we may not have a global regular parametric function for the
entire curve. It is possible that we may still have a nice-looking entire
curve even if the parametric functions of each piece are not joined smoothly.
Let us see the following example.

######  Example 2.4.

Consider a parametric curve defined below.

$\Gamma(t)=\begin{cases}(t,t)&t\in[-1,0]\\\ (3t,3t)&t\in(0,1].\end{cases}$

The graph of $\Gamma(t)$ is a line segment from $(-1,-1)$ to $(3,3)$ in
$\mathbb{R}^{2}$ which joins smoothly at $t=0$. However, the parametric
function itself is not differentiable at $t=0$. Nevertheless, we can define a
bijection $t=S(s)$, where

$S(s)=\begin{cases}s&s\in[-1,0]\\\ \frac{s}{3}&t\in(0,3]\end{cases}$

such that $\Gamma(S(s))=s$ for $s\in[-1,3]$. We can see that $\Gamma\circ S$
is now a regular parametric function even though $\Gamma$ and $S$ are not
smooth at $t=S(0)=0$.

We see the existence of a regular parametric function is crucial to the
geometrical smooth feature. We are now ready to formally define $G^{r}$
smoothness for $r\geq 1$ for a curve consisting of multiple pieces.

######  Definition 2.3.

[cf. [12]] Fix $r\geq 1$. A graph $\Gamma$ of curve in $\mathbb{R}^{n}$ is
said to be $G^{r}$ continuity at a point ${\bf p}\in\Gamma$ if there exist a
regular $C^{r}$ parametrization of functions $x_{i}(t),i=1,\cdots,n$ and a
constant $\epsilon>0$ such that
$\Gamma(t)=(x_{1}(t),\cdots,x_{n}(t)):t\in(-\epsilon,\epsilon)\rightarrow\Gamma$
with $\Gamma(0)={\bf p}$ and $\nabla\Gamma(0):=\Gamma^{\prime}(0)$ is a
nonzero vector, i.e. $\|\nabla\Gamma(0)\|>0$. An entire curve $\Gamma$ in
$\mathbb{R}^{n}$ is said to be $G^{r}$ continuous if the curve is of $G^{r}$
continuity at each point on the curve.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not regular}\end{subarray}$ Figure 6: Only the Graph with $G^{r}$ Property
can have a regular Parametric Function, While the non $G^{r}$ Graph can

In short, the $G^{r}$ continuity is a property of a curve-like subset $\Gamma$
in $\mathbb{R}^{n}$. Regularity and $C^{r}$ are properties of the underlying
parametric functions of the curve. Figure 6 shows the idea of the Definition
2.3. Let us summarize the above discussion in the following remark.

######  Remark 2.2.

  * •

A curve with $C^{r}$ parametric function does not imply the graph of the curve
is $G^{r}$. See Example 2.1.

  * •

If a curve with $C^{r}$ parametric function is regular, the graph of the curve
is $G^{r}$.

  * •

The graph $\Gamma$ is of $G^{r}$ does not imply its parametric function is
regular or $C^{r}$. See Example 2.4. However, if $\Gamma(t)$ is a continuous
function, for any $t=t_{0}$, there exist a bijection function $t=S(s)$, which
defined on small interval $(-\epsilon,\epsilon)$ with $S(0)=t_{0}$, such that
$\Gamma(S(s))$ is regular and $C^{r}$ on $(-\epsilon,\epsilon)$.

In other words, a bad graph (not $G^{r}$) may have a $C^{r}$ smooth parametric
function, but it can not have a regular $C^{r}$ smooth function. Vice versa, a
$G^{r}$ graph could adapt different parametric functions ${\bf f}_{1}$ and
${\bf f}_{2}$, see Example 2.4. Figure 7 shows the relation between the
function and graph. It’s unnecessary to describe a $G^{r}$ smooth curve with a
smooth parametric function. However, there must exist one regular $C^{r}$
function which parametrizes the curve.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not regular}\end{subarray}$$f$$\Gamma$$f\ \ is\ C^{r}$$f\ \ is\ regular\
C^{r}$$\Gamma\ is\ G^{r}\ \Leftrightarrow\ f\ can\ be\ reparamertrize\ as\
regular\ C^{r}$ Figure 7: The Relation Between Parameterize Function $f$ and
its Gragh $G$.

##  3 Construction of Geometric Smooth Interpolatory Curves

This section is divided into five subsections. In the first four subsection,
we explain our construction. We shall suppose that a point cloud ${\bf
P}=\\{{\bf v}_{i},i=0,1,\cdots,N\\}$ in $\mathbb{R}^{3}$ is oriented and is
flattenable. We start the construction with the local curves, reparametrizing
them (i.e. redistribution), constructing a blending function, and gluing them
together. In addition to these four subsections, we shall show that the
regularity of the curves based on our construction in the fifth subsection.

###  3.1  Construction of Local Curves

Given 3 ordered point ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ in ${\bf P}$,
we want to construct a $C^{r}$ regular curve interpolating these three points.

######  Definition 3.1.

A function ${\bf f}_{i}:[p_{i},r_{i}]\to\mathbb{R}^{3}$ is said to be a local
$G^{r}$ interpolating function of ${\bf P}$ (at point ${\bf v}_{i}$) if ${\bf
f}_{i}$ is regular $C^{r}$ function and there exist a point
$q_{i}\in(p_{i},r_{i})$ such that ${\bf f}_{i}(q_{i})={\bf v}_{i}$.

Note that we do not require ${\bf f}_{i}(p_{i})={\bf v}_{i-1}$ or ${\bf
f}_{i}(r_{i})={\bf v}_{i+1}$ during our construction and we will still get an
interpolating curve after gluing them together. However, having local curves
pass ${\bf v}_{i-1}$ and ${\bf v}_{i+1}$ gives us more pleasing curves in most
cases. Let us construct a few different types of local interpolating curves in
the following examples.

######  Example 3.1 (Spatial Parabola).

Suppose $\\{{\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}\\}$ are three successive
points in a flattenable data set. We define $\tilde{x}$ and $\tilde{y}$ are
two vectors which ${\bf p}_{0}+span\\{\tilde{x},\tilde{y}\\}$ is an plane that
contains ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$. Since ${\bf v}_{i-1},{\bf
v}_{i},{\bf v}_{i+1}$ is flatenable, one may choose $\tilde{x}$ such that the
projections of ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ to the
$\tilde{x}$-axis preserve the order, says $p_{i},q_{i},r_{i}$. Moreover, we
can interpolate ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ by $\\{{\bf
p}_{0}+s\tilde{{\bf x}}+Q(s)\tilde{{\bf y}}\,|\,s\in[p_{i},r_{i}]\\}$, where
$Q(s)$ is a quadratic function satisfying $Q^{\prime}(q_{i})=0$ by choosing
$\tilde{\bf x}$ and $\tilde{\bf y}$ carefully, see Figure 8. The proof of the
existence of such construction is left to the reader.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not
regular}\end{subarray}$$v_{i-1}$$v_{i}$$v_{i+1}$$p_{0}$$\tilde{x}$$\tilde{y}$
Figure 8: Choosing $\tilde{{\bf x}}$ and $\tilde{{\bf y}}$ such that the
parabola pass ${\bf v}_{i-1}$ ${\bf v}_{i}$, and ${\bf v}_{i+1}$ has a extreme
at ${\bf v}_{i}$.

To obtain a parametric function from the above construction, we need a
rotation. Let us use $(x,y,z)$ for as the coordinate in $\mathbb{R}^{3}$, as
the example. We rewrite $\tilde{\bf x}=R_{11}x+R_{12}y+R_{13}z$ , $\tilde{\bf
y}=R_{21}x+R_{22}y+R_{23}z$. We can then define ${\bf f}_{i}(s)={\bf
p}_{0}+s\tilde{{\bf x}}+Q(s)\tilde{{\bf y}}$, i.e.

${\bf f}_{i}(s)=\begin{bmatrix}x_{i}(s)\\\ y_{i}(s)\\\
z_{i}(s)\end{bmatrix}={\bf p}_{0}+\begin{bmatrix}R_{11}&R_{12}&R_{13}\\\
R_{21}&R_{22}&R_{23}\end{bmatrix}^{T}\begin{bmatrix}s\\\ Q(s)\end{bmatrix}.$

We can see that ${\bf f}_{i}$ is regular by

${\bf f}^{\prime}_{i}(s)=\begin{bmatrix}R_{11}&R_{12}&R_{13}\\\
R_{21}&R_{22}&R_{23}\end{bmatrix}^{T}\begin{bmatrix}1\\\
Q^{\prime}(s)\end{bmatrix},$

which is never zero. Hence, the parabola is a local $G^{\infty}$ interpolating
function.
The various ${\bf f}_{i}$ can be visualized in Figure 9.

${\bf f}_{i-1}$$p_{i-1}$$q_{i-1}$$r_{i-1}$$\bullet$${\bf v}_{i-2}$${\bf
f}_{i+1}$$\bullet$${\bf
v}_{i+2}$$p_{i+1}$$q_{i+1}$$r_{i+1}$$p_{i}$$q_{i}$$r_{i}$${\bf
f}_{i}$$\bullet$${\bf v}_{i-1}$$\bullet$${\bf v}_{i}$$\bullet$${\bf v}_{i+1}$
Figure 9: An illustration of point cloud and different local curves

######  Example 3.2 (Arc of Circle or Ellipse).

It it known that 3 points ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ in
$\mathbb{R}^{2}$ can uniquely determine a circle (a line can be seen as a
degenerated circle) so are the points in $\mathbb{R}^{n}$ when they are
flattenable for $n\geq 3$. If ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ are
flattenable, we can choose an arc of the circle in which ${\bf v}_{i}$ is
located within the arc while ${\bf v}_{i-1}$ and ${\bf v}_{i+1}$ are the
endpoints of the arc, see the left of Figure 10. However, the circle arc could
be very off when the angle ${\bf v}_{i-1},{\bf v}_{i},{\bf v}_{i+1}$ is
relatively small (Middle of Figure 10). In [7], Yuksel proposes to use the
ellipse arc instead if one of the arc ${\bf v}_{i-1}-{\bf v}_{i}$, ${\bf
v}_{i}-{\bf v}_{i+1}$ has corresponding to an angle larger than 90 degrees.
The construction can be described as follows: first, place ${\bf v}_{i}$ on
one axis of the ellipse. Second, place either ${\bf v}_{i-1}$ or ${\bf
v}_{i_{1}}$ on another axis of the ellipse, depending on which further from
${\bf v}_{i}$. Then, there is a unique ellipse that passes through three
points with the axis with the specified property. See the right of Figure 10.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not
regular}\end{subarray}$$v_{i-1}$$v_{i}$$v_{i+1}$$v_{i-1}$$v_{i}$$v_{i+1}$$v_{i+1}$$v_{i-1}$$v_{i}$
Figure 10: Left: an Arc Passing Through ${\bf v}_{i-1},{\bf v}_{i}$, and ${\bf
v}_{i+1}$. Mid: ${\bf v}_{i-1},{\bf v}_{i}$, and ${\bf v}_{i+1}$ are Flatenale
(As they can Project to the Blue Dash Line and Preserve the Order). However,
the Local Curve is Off. Right: The Construction of the Ellipse Local Curve.

The parametric function of the arc can be defined by the polar coordinate. As
shown in Figure 11, We can parameterize the arc by ${\bf f}_{i}(t)={\bf
p}_{0}+\cos(-t)\tilde{{\bf x}}+\sin(-t)\tilde{{\bf y}}$, where $\tilde{{\bf
x}}$ and $\tilde{{\bf y}}$ axis of circle or ellipse. One can easily see that
the parametric function is a regular $G^{r}$ local function.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not
regular}\end{subarray}$$v_{i+1}$$v_{i-1}$$v_{i}$$v_{i+1}$$v_{i-1}$$v_{i}$$\tilde{x}$$\tilde{y}$$\tilde{y}$$p_{0}$$p_{0}$
Figure 11: The Coordinate of Circle and Ellipse Local Curve.

######  Remark 3.1.

If the curve has endpoints, then we need a local curve that passes through
${\bf v}_{0}$ (and ${\bf v}_{N}$). One natural choice is the line segment
connecting ${\bf v}_{0}$ and ${\bf v}_{1}$ (${\bf v}_{N-1}$ and ${\bf
v}_{N}$). Or, if our local curve of ${\bf v}_{1}$ also passes ${\bf v}_{0}$,
we can use the same local curve as ${\bf v}_{1}$. If the curve is a closed
circle, say ${\bf v}_{0}={\bf v}_{N}$, we have to get another local curve at
${\bf v}_{0}={\bf v}_{N}$, which may be a parabola pass ${\bf v}_{N-1}$, ${\bf
v}_{0}={\bf v}_{N}$, and ${\bf v}_{1}$ or other local curves depend on needs.

###  3.2 Redistribution and Quasi-regular Local Curves

Suppose ${\bf v}_{i}$ is a local $G^{r}$ curve at ${\bf v}_{i}$, where ${\bf
f}_{i}(p_{i})={\bf v}_{i-1}$, ${\bf f}_{i}(q_{i})={\bf v}_{i}$, and ${\bf
f}_{i}(r_{i})={\bf v}_{i+1}$. Redistribution of ${\bf f}_{i}$ is a re-
parameterization of the function by ${\bf f}_{i}(t)={\bf
f}_{i}(S_{i}^{-1}(s))$ using $t=S_{i}^{-1}(s)$, where the bijection
$S:[p_{i},r_{i}]\to[i-1,i+1]$ with $S_{i}(p_{i})=i-1$, $S_{i}(q_{i})=i$, and
$S(r_{i})=i$. We call ${\bf F}_{i}(s)={\bf f}_{i}(S_{i}^{-1}(s))$ quasi-
regular function (QR function). The formal definition of the quasi-regular
local parametric function can be described below:

######  Definition 3.2.

A function ${\bf F}_{i}:[i-1,i+1]\to\mathbb{R}^{3}$ is said to be a local
$G^{r}$ quasi-regular interpolating function of ${\bf P}$ (at point ${\bf
v}_{i}$) if:

  * •

${\bf F}|_{(i-1,i)}$ and ${\bf F}|_{(i,i+1)}$ are regular and $C^{r}$.

  * •

$\lim\limits_{t\to i^{+}}\nabla{\bf F}(t)\neq\bf 0$ for $t=i-1,i$, and
$\lim\limits_{t\to i^{-}}\nabla{\bf F}(t)\neq\bf 0$ for $t=i,i+1$.

  * •

There exists a local re-parameterization
$S_{i}:[q_{i}-\epsilon,q_{i}+\epsilon]\to[i-1,i]$ with $S_{i}(q_{i})=i$ such
that ${\bf F}(S_{i}(s))$ is a regular $C^{r}$ function on
$[q_{i}-\epsilon,q_{i}+\epsilon]\subset[p_{i},r_{i}]$ for a $\epsilon>0$.

By condition 1) and 2) in Definition 3.2, we can see that ${\bf F}_{i}$ is
$G^{r}$ on $[i-1,i+1]\setminus\\{i\\}$. By condition 3), we can see that ${\bf
F}_{i}$ is $G^{r}$ at $i$. Hence, ${\bf F}$ is $G^{r}$ on $[i-1,i+1]$. This is
not a surprise if we see that ${\bf F}_{i}$ is just the re-parametrize of
${\bf f}_{i}$. The main problem is to choose the distribution function
$S_{i}$. We see that using a piece-wise linear function will work.

######  Lemma 3.3.

For a local curve ${\bf f}_{i}:[p_{i},r_{i}]\to\mathbb{R}^{n}$ which
interpolate ${\bf v}_{i-1},{\bf v}_{i}$, and ${\bf v}_{i+1}$. Suppose
$S_{i}:[p_{i},r_{i}]\rightarrow[i-1,i+1]$ is a piecewise linear function
consisting of two line segments such that $S_{i}(p_{i})=i-1,S_{i}(q_{i})=i$
and $S_{i}(r_{i})=i+1$. Then ${\bf F}_{i}(t)={\bf f}_{i}(S_{i}^{-1}(t))$ is a
$G^{\infty}$ quasi-regular parametric function such that ${\bf F}_{i}(j)={\bf
v}_{j}$ for $j=i-1,i,i+1$.

Proof.  First, $S_{i}(s)$ is a linear function on $s\in[p_{i},q_{i}]$. We have
${\bf F}^{\prime}_{i}(t)={\bf
f}_{i}^{\prime}(S_{i}^{-1}(t))(S_{i}^{-1})^{\prime}(t)$. Hence, ${\bf F}$ is a
regular curve on $(i-1,i)$ because $(S_{i}^{-1})^{\prime}(t)$ is a constant
and ${\bf f}_{i}$ is regular (so that ${\bf f}_{i}^{\prime}(S_{i}^{-1}(t))$ is
never zero). Similarly, ${\bf F}$ is a regular curve on $(i,i+1)$. Secondly,
one can easily see that ${\bf F}^{\prime}_{i}(t)$ exists when
$t\to(i-1)_{+},i_{-},i_{+},or(i+1)_{-}$. Finally, it easy to see that ${\bf
F}_{i}(S_{i}(s))={\bf f}_{i}(s)$ and $S_{i}$ is a regular $C^{\infty}$
function. Thus, ${\bf F}_{i}(t)$ is a $G^{\infty}$ quasi-regular parametric
function.
The interpolation property could be obtained by ${\bf F}_{i}(i-1)={\bf
f}_{i}(S_{i}^{-1}(i-1))={\bf f}_{i}(p_{i})={\bf v}_{i-1}$, ${\bf
F}_{i}(i)={\bf f}_{i}(S_{i}^{-1}(i))={\bf f}_{i}(q_{i})={\bf v}_{i}$, and
${\bf F}_{i}(i+1)={\bf f}_{i}(S_{i}^{-1}(i+1))={\bf f}_{i}(r_{i})={\bf
v}_{i+1}$. $\Box$

Since ${\bf F}$ and ${\bf f}$ only differ in the parameterization, they have
the same graph, which is $G^{r}$. Although ${\bf F}$ loses its regularity at
the nodes, it stores the point cloud at integer nodes, which is a more
desirable property in computer programming.

Before we move on to constrict some local curves, we shall define another
important property of these $G^{r}$ quasi-regular functions.

######  Definition 3.3.

We say a local $G^{r}$ interpolating QR function ${\bf
F}_{i}:[i-1,i+1]\to\mathbb{R}^{3}$, as we defined in Definition 3.2, is
contracted if the inner products

$\langle{\bf F}_{i}(s)-{\bf L}_{i}(s),{\bf v}_{i}-{\bf
v}_{i-1}\rangle>0,\text{ for }s\in(i-1,i)$

and

$\langle{\bf F}_{i}(s)-{\bf L}_{i}(s),{\bf v}_{i}-{\bf
v}_{i+1}\rangle>0,\text{ for }s\in(i,i+1),$

where ${\bf L}_{i}$ is the piecewise linear function with ${\bf
L}_{i}(i-1)={\bf v}_{i-1}$, ${\bf L}_{i}(i)={\bf v}_{i}$, and ${\bf
L}_{i}(i+1)={\bf v}_{i+1}$

We illustrated the contracted local curve in Figure 12. Generally speaking, a
parametric function is contracted if it is always closer to ${\bf
v}_{i}=f(q_{i})$ than the linear interpolating on both sides.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not
regular}\end{subarray}$$v_{i-1}$$v_{i}=F(i)$$v_{i+1}$$F_{i}(i+1)$$F_{i}(i-1)$$L_{i}(s)$$F_{i}(s)$
Figure 12: The Contracted Local Curve. The red point is ${\bf L}_{i}(s)$ and
the blue points is ${\bf F}_{i}(s)$. Generally speaking, the contracted QR
function is always closer to ${\bf v}_{i}$ than linear interpolation after
projection to the line connecting the vertex.

Another important property is the positive definiteness:

######  Definition 3.4.

We say a local regular (which also imply $C^{1}$) function
$F:[a,b]\to\mathbb{R}^{n}$ on an interval $(\alpha,\beta)\subset[a,b]$ if
$\langle F^{\prime}(x),F(\beta)-F(\alpha)\rangle>0$ for all
$x\in(\alpha,\beta)$.

Generally speaking, if a curve is positive definite, then it’s target is
always toward the endpoint.
The contractness and the positive definite are sufficient conditions of the
final gluing curve to be $G^{r}$. Hence, we shall prove our construction of
local curves are contracting and positive definite.

######  Example 3.4 (Contractness and Positive definite of Spatial Parabola).

Let ${\bf F}_{i}(s)={\bf f}_{i}(S^{-1}_{i}(s))$, where ${\bf f}_{i}$ is
defined as in Example 3.1, and $S:[p_{i},r_{i}]\to[i-1,i+1]$ is join of two
linear functions with $S_{i}(p_{i})=i-1$, $S_{i}(q_{i})=i$, and $S(r_{i})=i$.
We can prove that ${\bf F}_{i}:[i-1,i]\rightarrow\mathbb{R}^{3}$ is a
$C^{\infty}$ positive definite curve and contracted at $i$, ${\bf
F}_{i}:[i,i+1]\rightarrow\mathbb{R}^{3}$ is a $C^{r}$ positive definite curve
and contracted at $i$.

For positive definiteness, we check the graph on $\tilde{\bf x},\tilde{\bf y}$
as in Example 3.1, where the parabola curve can be described as $(s,Q(s))$ on
the coordinate systems $\tilde{\bf x},\tilde{\bf y}$ with origin at ${\bf
p}_{0}$. Since $Q(q_{i})$ is the vertex of the parabola, all the derivative is
toward the vertex, i.e. $Q^{\prime}(s)(Q(q_{i})-Q(s))\geq 0$. For
$t\in(i-1,i)$, we have

$\displaystyle\langle{\bf F}_{i}^{\prime}(t),{\bf F}_{i}(i)-{\bf
F}_{i}(i-1)\rangle$ $\displaystyle=\langle{\bf
f}_{i}^{\prime}(s)(S_{i}^{-1})^{\prime}(t),{\bf f}_{i}(q_{i})-{\bf
f}_{i}(p_{i})\rangle$ $\displaystyle=(S_{i}^{-1})^{\prime}(t)\langle
Q^{\prime}(s)\tilde{{\bf y}}+\tilde{{\bf
x}},\left(Q(q_{i})-Q(p_{i})\right)\tilde{{\bf y}}+(q_{i}-p_{i})\tilde{{\bf
x}}\rangle$
$\displaystyle=(S_{i}^{-1})^{\prime}(t)(Q^{\prime}(s)\left(Q(q_{i})-Q(p_{i})\right)+(q_{i}-p_{i}))>0.$

Note that $S_{i}^{-1}$ is a linear incresing function on $[i-1,i]$ so
$(S_{i}^{-1})^{\prime}(t)$ is a positive constant. Similarly $\langle{\bf
F}_{i}^{\prime}(t),{\bf F}_{i}(i+1)-{\bf
F}_{i}(i)\rangle=(S_{i}^{-1})^{\prime}(t)(Q^{\prime}(s)\left(Q(r_{i})-Q(q_{i})\right)+(r_{i}-q_{i}))>0$.

For contractness (cf. Definition 3.3), let $t\in(i-1,i)$, since ${L}(t)$ is a
linear function from ${\bf v}_{i-1}$ to ${\bf v}_{i-1}$ and $S_{i}$ is a
linear function, we have $L(S_{i}(s))=l(s)\tilde{{\bf y}}+s\tilde{\bf x}$,
where $l(s)$ is a linear function with $l(p_{i})=Q(p_{i})$ and
$l(q_{i})=Q(q_{i})$. Now let $t=S_{i}(s)$ we can calculate $\langle{\bf
F}_{i}(t)-{L}(t),{\bf F}_{i}(i)-{\bf F}_{i}(i-1)\rangle=\langle
f_{i}(s)-L(S_{i}(s)),f_{i}(q_{i})-f_{i}(p_{i})\rangle=\langle
Q(s)-l(s)\tilde{\bf y},\left(Q(q_{i})-Q(p_{i})\right)\tilde{\bf
y}+(q_{i}-p_{i})\tilde{\bf
x}\rangle=(Q(s)-l(s))\left(Q(q_{i})-Q(p_{i})\right)\geq 0$. Because if $Q$ is
convex, $Q(s)\leq l(s)$ and $Q(q_{i})\leq Q(p_{i})$ and if $Q$ is concave,
$Q(s)\geq l(s)$ and $Q(q_{i})\geq Q(p_{i})$. Similarly, for $t\in[i,i+1]$.

###  3.3 Blending Functions

We begin with a construction of blending functions.

######  Definition 3.5.

A pair of r-blending polynomials $B_{1},B_{2}:[0,1]\rightarrow\mathbf{R}$ is a
polynomial satisfying the following:

  * •

$1>B_{1}$, $B_{2}>0$ on $(0,1)$.

  * •

$B_{1}(1)=B_{2}(0)=0$ and $B_{1}(0)=B_{2}(1)=1$.

  * •

$B_{1}^{(\alpha)}(0)=B_{1}^{(\alpha)}(1)=B_{2}^{(\alpha)}(0)=B_{2}^{(\alpha)}(1)=0$
for all $0<\alpha\leq r$.

  * •

$B_{1}+B_{2}=1$ on $[0,1]$.

  * •

$-B_{1}$ and $B_{2}$ are non decreasing.

An example of a 0-blending function is

$\begin{cases}B_{1}(t)&=1-t,\forall t\in[0,1]\\\ B_{2}(t)&=t,\forall
t\in[0,1].\end{cases}$ (2)

An example of a 1-blending function is

$\begin{cases}B_{1}(t)&=2t^{3}-3t^{2}+1,\forall t\in[0,1]\\\
B_{2}(t)&=-2t^{3}+3t^{2},\forall t\in[0,1]\end{cases}$ (3)

Another example of a 1-blending function is

$\begin{cases}B_{1}(t)&=\cos^{2}(t),\forall t\in[0,1]\\\
B_{2}(t)&=\sin^{2}(t),\forall t\in[0,1].\end{cases}$ (4)

We can also generate $\infty$-blending function. let $f(x)=e^{-\frac{1}{x}}$,
we define

$\begin{cases}B_{1}(t)&=\dfrac{f(1-x)}{f(x)+f(1-x)},\forall t\in[0,1]\\\
B_{2}(t)&=\dfrac{f(x)}{f(x)+f(1-x)},\forall t\in[0,1].\end{cases}$ (5)

is not hard to find that $B_{1}$ $B_{2}$ satisfying Definition 3.5.
Principally, this will give you a $G^{\infty}$ interpolation function if you
use these in Algorithm 1. However, the derivatives of those blending functions
are complex, which may not be suitable for computational manner.

In general, we can generate $r$-blending functions by polynomials
$B_{1}(x)=\displaystyle\int_{x}^{1}ct^{r}(1-t)^{r}dt$, $B_{2}(x)=1-B_{1}(x)$,
where $c=(\int_{0}^{1}t^{r}(1-t)^{r}dt)^{-1}$. This is equivalent to
$B_{1}(x)=\displaystyle\sum_{0\leq i\leq r}b_{i,2r+1}(x)$ and
$B_{2}(x)=\displaystyle\sum_{r+1\leq i\leq 2r+1}b_{i,2r+1}(x)$, where
$b_{i,2r+1}$ are $i$-th Bernstein basis polynomials of degree $2r+1$. We call
this polynomial r-blending function. There are still many ways to define
r-lending functions. We leave them to the interested reader.

###  3.4 Linear Gluing of QR Curves and Main Theorem

Consider ${\bf F}_{i}:[i-1,i+1]\to\mathbb{R}^{n}$ are $G^{r}$ QR interpolating
functions of the data points $\\{{\bf v}_{i},i=0,1,\cdots,N\\}$. Our final
glued function $\Gamma:[0,N]\to\mathbb{R}^{3}$ to be:

$\Gamma(t)|_{[i,i+1]}={\bf F}_{i}(t)B_{1}(t-i)+{\bf F}_{i+1}(t)B_{2}(t-i)$

for $i=1,2,\cdots,N-1$. Note that ${\bf F}_{0}$ and ${\bf F}_{N}$ are
boundaries QR function. See Remark 3.1. We will show that $\Gamma$ can be
$G^{r}$ if we carefully choose our ${\bf f}_{i}$, $S_{i}$, $B_{1}$, and
$B_{2}$. Indeed, we have:

######  Theorem 3.5.

Suppose a set of oriented data point $P=\\{{\bf v}_{0},{\bf v}_{1},\cdots,{\bf
v}_{N}\\}$. We define a curve

$\Gamma(t)|_{[i,i+1]}={\bf F}_{i}(t)B_{1}(t-i)+{\bf F}_{i+1}(t)B_{2}(t-i)$

where:

1) ${\bf f}_{i}:[p_{i},r_{i}]\to\mathbb{R}^{n}$ are $C^{r}$ local curve which
$f_{i}(q_{i})={\bf v}_{i}$ for some $q_{i}\in(p+i,r_{i})$ for
$i=1,2,\cdots,N-1$. ${\bf f}_{0}:[q_{0},r_{0}]\to\mathbb{R}^{n}$ is a $C^{r}$
function with ${\bf f}_{0}(q_{0})={\bf v}_{0}$, and ${\bf
f}_{N}:[p_{N},q_{N}]\to\mathbb{R}^{n}$ is a $C^{r}$ function with ${\bf
f}_{N}(q_{N})={\bf v}_{N}$.

2) ${\bf F}_{i}={\bf f}_{i}\circ S_{i}^{-1}:[i-1,i+1]\to\mathbb{R}^{n}$ is
positive definite and contracted to ${\bf v}_{i}$, where $S^{i}:[p_{i},r_{i}]$
piecewise linear function with $S_{i}(p_{i})=i-1$, $S_{i}(q_{i})=i$, and
$S_{i}(r_{i})=i+1$. When $i=0,N$, $S_{i}$ are linear function where
$S_{0}(q_{i})=0$, $S_{0}(r_{i})=1$, $S_{N}(p_{i})=N-1$, and $S_{N}(q_{i})=N$.

3) $B_{1}$, $B_{2}$ are $r$-blending function.

Then the graph of $\Gamma(t)$ is $G^{r}$ which $\Gamma(0)={\bf
v}_{0},\Gamma(1)={\bf v}_{1},\cdots,\Gamma(N)={\bf v}_{N}$.

We divided the proof into three claims:

######  Claim 3.6.

The $\Gamma(t)$ defines in Theorem 3.5 interpolate the data points $P$.

Proof.  The simple substitution $\Gamma(i)={\bf F}_{i}(i)B_{1}(0)+{\bf
F}_{i+1}(i)B_{2}(0)={\bf F}_{i}(i)={\bf f}_{i}(S_{i}^{-1}(i))={\bf
f}_{i}(q_{i})={\bf v}_{i}$. $\Box$

######  Claim 3.7.

The graph of $\Gamma(t)$ is $G^{r}$ at integer points.

Proof.  Consider $\Gamma_{i}:=\Gamma|_{(i-1,i+1)}$ for $i=1,2,\cdots,N-1$. We
want to show that $\Gamma$ is $G^{r}$ at $i$. We can consider a re-
parameterization ${\bf g}_{i}=\Gamma_{i}\circ
S_{i}:[p_{i},r_{i}]\to\mathbb{R}^{n}$. We can show ${\bf
g}_{i}^{(\alpha)}(q_{i})={\bf f}_{i}^{(\alpha)}(q_{i})$, for $1<\alpha\leq r$,
by calculate:

$\displaystyle\lim\limits_{s\to q_{i}^{+}}\frac{d^{\alpha}}{(ds)^{\alpha}}{\bf
g}_{i}(s)$ $\displaystyle=$ $\displaystyle\lim\limits_{s\to
q_{i}^{+}}\dfrac{d^{\alpha}}{(ds)^{\alpha}}\Bigl{(}{\bf
F}_{i}(S_{i}(s))B_{1}(S_{i}(s)-i)+{\bf
F}_{i+1}(S_{i}(s))B_{2}(S_{i}(s)-i\Bigr{)}$ $\displaystyle=$
$\displaystyle\lim\limits_{s\to
q_{i}^{+}}\dfrac{d^{\alpha}}{(ds)^{\alpha}}\Bigl{(}{\bf f}_{i}(S_{i}^{-1}\circ
S_{i}(s))B_{1}(S_{i}(s)-i)$ $\displaystyle\qquad+{\bf
f}_{i+1}(S_{i+1}^{-1}\circ S_{i}(s))B_{2}(S_{i}(s)-i)\Bigr{)}$
$\displaystyle=$ $\displaystyle\lim\limits_{s\to
q_{i}^{+}}\dfrac{d^{\alpha}}{(ds)^{\alpha}}\Bigl{(}{\bf
f}_{i}(s)B_{1}(S_{i}(s)-i)+{\bf f}_{i+1}(S_{i+1}^{-1}\circ
S_{i}(s))B_{2}(S_{i}(s)-i)\Bigr{)}$ $\displaystyle=$ $\displaystyle{\bf
f}_{i}^{(\alpha)}(q_{i})+\lim\limits_{s\to
q_{i}^{+}}\displaystyle\sum_{\begin{subarray}{c}m+n=\alpha\\\
n>1\end{subarray}}{\bf
f}_{i}^{(m)}(s)\dfrac{d^{n}}{(ds)^{n}}B_{1}(S_{i}(s)-i)$
$\displaystyle\qquad\quad+\lim\limits_{s\to
q_{i}^{+}}\displaystyle\sum_{m+n=\alpha}(\dfrac{d^{m}}{(ds)^{m}}{\bf
f}_{i+1}(S_{i+1}^{-1}\circ
S_{i}(s)))(\dfrac{d^{n}}{(ds)^{n}}B_{2}(S_{i}(s)-i)).$

For the second and third term, Note that $S_{i}|_{(q_{i},r_{i})}$ are a linear
function to $(i,i+1)$, so $(S_{i}(s)-i)$ has range on $(0,1)$ when
$s\in(q_{i},r_{i})$. We have $\frac{d^{n}}{(ds)^{n}}B_{1}(S_{i}(s)-i)=0$ for
$1\leq n\leq\alpha$ and $\frac{d^{n}}{(ds)^{n}}B_{2}(S_{i}(s)-i)=0$ for
$0\leq\alpha$, since $B_{1}$ and $B_{2}$ are $r$-blending function and
$\alpha\leq r$. This leads to the conclusion that the second term is vanish.
For the third term, we know the derivative of $B_{2}$ is zeros but we need to
check if $\dfrac{d^{m}}{(ds)^{m}}{\bf f}_{i+1}(S_{i+1}^{-1}\circ S_{i}(s))$ is
exist and finite. Note that $S_{i+1}^{-1}\circ S_{i}|_{(q_{i},r_{i})}$ is a
linear function from $(q_{i},r_{i})$ to $(p_{i+1},q_{i+1})$. We can conclude
that $\dfrac{d^{m}}{(ds)^{m}}{\bf f}_{i+1}(S_{i+1}^{-1}\circ S_{i}(s))$ is
exist and finite. Hence, the second and third terms all vanish and

$\lim\limits_{s\to q_{i}^{+}}\frac{d^{\alpha}}{(ds)^{\alpha}}{\bf
g}_{i}(s)={\bf f}_{i}^{(\alpha)}(q_{i}).$

Similar to the left-hand limit, we have ${\bf g}_{i}^{(\alpha)}(q_{i})={\bf
f}_{i}^{(\alpha)}(q_{i})$ for $0\leq\alpha\leq r$. Therefore, ${\bf g}$ is
regular $C^{r}$ function (so $G^{r}$) near ${\bf v}_{i}$. $\Gamma$ is $G^{r}$
near ${\bf v}_{i}$ because it and ${\bf g}_{i}$ have same graph.

$\Box$

######  Claim 3.8.

The graph of $\Gamma(t)$ is $G^{r}$ on intervals $(i,i+1)$ for
$i=0,1,\cdots,N-1$.

Proof.  By definition of $\Gamma$, is not hard to see that $\Gamma$ is a
$C^{r}$ function on $(i,i+1)$. For $G^{r}$, we only need to show that $\Gamma$
is regular, that is, $\Gamma^{\prime}(t)\neq 0$. We can calculate:

$\displaystyle{\bf\Gamma}^{\prime}(t)|_{(i,i+1)}$ $\displaystyle={\bf
F}^{\prime}_{i}(t)B_{1}(t-i)+{\bf F}^{\prime}_{i+1}(t)B_{2}(t-i)$ (6)
$\displaystyle+{\bf F}_{i}(t)B^{\prime}_{1}(t-i)+{\bf
F}_{i+1}(t)B^{\prime}_{2}(t-i)$ $\displaystyle={\bf
F}^{\prime}_{i}(t)B_{1}(t-i)+{\bf F}^{\prime}_{i+1}(t)B_{2}(t-i)+\bigl{(}{\bf
F}_{i+1}(t)-{\bf F}_{i}(t)\bigr{)}B^{\prime}_{2}(t-i)$

Note that in the last line, we use
$B^{\prime}_{1}=(1-B_{2})^{\prime}=-B^{\prime}_{2}$. Now consider the inner
product
$\langle{\bf\Gamma}^{\prime}(t),{\bf\Gamma}(i+1)-{\bf\Gamma}(i)\rangle$. We
have $\langle{\bf F}^{\prime}_{i}(t),{\bf\Gamma}(i+1)-{\bf\Gamma}(i)\rangle$
and $\langle{\bf
F}^{\prime}_{i+1}(t),{\bf\Gamma}(i+1)-{\bf\Gamma}(i)\rangle>0$ because ${\bf
F}_{i}$ and ${\bf F}_{i+1}$ are positive definite function. For the last
component in 6, we consider ${\bf L}:[i,i+1]\rightarrow\mathbb{R}^{3}$ be a
linear function with ${\bf L}(i)={\bf\Gamma}(i)={\bf v}_{i}$ and ${\bf
L}(i+1)={\bf\Gamma}(i+1)={\bf v}_{i+1}$. We can calculate

$\displaystyle\langle\bigl{(}{\bf F}_{i+1}(t)-{\bf
F}_{i}(t)\bigr{)}B^{\prime}_{2}(t-i),{\bf\Gamma}(i+1)-{\bf\Gamma}(i)\rangle$
$\displaystyle=$ $\displaystyle\langle({\bf F}_{i+1}(t)-{\bf L}(t))-({\bf
F}_{i}(t)-{\bf L}(t)),{\bf v}_{i+1}-{\bf v}_{i}\rangle\cdot
B^{\prime}_{2}(t-i)$ $\displaystyle=$ $\displaystyle\Bigl{(}\bigl{\langle}{\bf
F}_{i+1}(t)-{\bf L}(t),{\bf v}_{i+1}-{\bf
v}_{i}\bigr{\rangle}+\bigl{\langle}{\bf F}_{i}(t)-{\bf L}(t),{\bf v}_{i}-{\bf
v}_{i+1}\bigr{\rangle}\Bigr{)}\cdot B^{\prime}_{2}(t-i)\geq 0.$

Where we apply the contractness of ${\bf F}_{i}$ at ${\bf v}_{i}$ and ${\bf
F}_{i+1}$ at ${\bf v}_{i+1}$ in the last line. We have ${\bf\Gamma}(t)$ is a
positive definite on $(i,i+1)$, so it is regular because the first derivative
never vanishes. $\Box$

By the claim 3.6, 3.7, and 3.6, the Theorem 3.5 is proved.

######  Corollary 3.8.1 (Bonus Smoothness).

If the local function ${\bf f}_{i}$ in Theorem 3.5 is $C^{r+1}$ and pass three
point ${\bf f}_{i}(p_{i})={\bf v}_{i-1}$, ${\bf f}_{i}(q_{i})={\bf v}_{i}$,
and ${\bf f}_{i}(r_{i})={\bf v}_{i+1}$, and the $r$-blending function are
differentiable up to $r+1$ (The derivative still vanish up to $r$). Then the
curve $\Gamma$ is $G^{r+1}$.

Proof.  We already show the curve $\Gamma$ is regular. We only need to show
that the $r+1$-th derivative is equal to the Local QR function on its
boundary. From Equation 6, we have

$\displaystyle{\bf\Gamma}^{(r+1)}(t)|_{(i,i+1)}$
$\displaystyle=\Bigl{(}\sum_{\begin{subarray}{c}m+n=r+1\\\
n<r+1\end{subarray}}{\bf F}^{(m)}_{i}(t)B_{1}^{(n)}(t-i)+{\bf
F}^{(m)}_{i+1}(t)B_{2}^{(n)}(t-i)\Bigr{)}$ (7) $\displaystyle+\bigl{(}{\bf
F}_{i+1}(t)-{\bf F}_{i}(t)\bigr{)}B^{(r+1)}_{2}(t-i).$

When $t\to i$, the first term equal to $F^{r+1}_{i}$ because $B_{1}(0)=1$ and
the rest terms of $B^{(n)}_{1}$, $B^{(n)}_{2}$ goes to zeros. For the second
term, although $B^{(r+1)}_{2}(t-i)$ is not zeros, ${\bf F}_{i+1}(i)-{\bf
F}_{i}(i)={\bf v}_{i}-{\bf v}_{i}=0$. Hence ${\bf\Gamma}^{(r+1)}(t)={\bf
F}^{(r+1)}_{i}(t)$ when $t\to i^{+}$. Similarly, ${\bf\Gamma}^{(r+1)}(t)={\bf
F}^{(r+1)}_{i=1}(t)$ for $t\to i+1^{-}$.

$\Box$

##  4 Numerical Examples of 3D Smooth Curves

In this section, we present several examples to demonstrate that the method
discussed in the previous section can be used to construct smooth 3D curves.
We begin with our computational algorithm below, which has been implemented in
MATLAB.

Algorithm 1 The Curve Interpolation Algorithm. (See Figure 13.)

Step 1 For each point ${\bf v}_{i}$, use ${\bf v}_{i-1}$ and ${\bf v}_{i+1}$
to generate ${{\bf f}_{i}}$ as in Definition 3.1 for $i=1,2,\cdots,N-1$.
Step 1.5 For boundary point ${\bf v}_{0}$ and ${\bf v}_{N}$, constructing the
local curve ${{\bf f}_{0}}$ and ${{\bf f}_{N}}$. Some canonical choices are:
Linear Using linear function ${{\bf f}_{0}}$ connect ${\bf v}_{0}$ and ${\bf
v}_{1}$, and ${{\bf f}_{N}}$ connect ${\bf v}_{N-1}$ and ${\bf v}_{N}$.
Natural If local function ${\bf f}_{1}$ pass ${\bf v}_{0}$ and ${\bf
f}_{N-1}$, simply use them as the ${{\bf f}_{0}}$ and ${{\bf f}_{N}}$.
Close If ${\bf v}_{N}={\bf v}_{0}$, means the data points is a close curve, we
can define ${\bf f}_{N}={\bf f}_{0}$ be the local function using ${\bf
v}_{N-1}$,${\bf v}_{N}={\bf v}_{0}$, and ${\bf v}_{1}$.
Step 2 Redistribution the local function $F_{i}=f_{i}(S_{i}^{-1})$.
Step 3 Given smoothness $r\geq 1$, choose a suitable blending function
$B_{1}$, $B_{2}$.
Step 4 For each interval $[i-1,i]$, evaluate the function ${{\bf
f}_{i-1}}(S^{-1}(x))B_{1}(x)+{{\bf f}_{i}}(S^{-1}({\bf x}))B_{2}(x)$.

In addition, we present a computational flowchart to illustrate the steps of
Algorithm 1 in Figure 13.

Figure 13: Flowchart of our Algorithm 1.

###  4.1 Computational Experiments

Let us show some numerical results based on our Algorithm 1 above.

######  Example 4.1 ($G^{r}$ Spline Interpolating Curves).

Fix $r=2$. We start with the $G^{r}$ interpolation with piecewise polynomial
construction. We use the parabolic local function from Example 3.1. We already
proved that the local QR function is positive definite and contracted in
Example 3.4. Therefore, by theorem 3.5 and Corollary 3.8.1, the interpolation
is $G^{r+1}$, where $r$ is only depending on the choice of $r$-blending
function. We use the polynomial $r$-blending function defined in Section 3.3.
The degree of $r$-blending function is $2r+1$. In this case, we can construct
$G^{r}$ interpolation spline with piecewise polynomials of degree $2r+1$. In
the case $r=1$, we use degree $3$ polynomial to interpolate $G^{1}$ data in
any dimension. This result is quite comparable to $G^{1}$ Bernstein
interpolation. Our algorithm automating the local curve so the user does not
have to specify the local control points. In addition, our algorithm can
increase the smoothness at a very low extra cost. Because the local curve is
the same we only have to compute the blending function which the explicit
formula of the function was given.
For a set of random points in 3d space, we use $2$-blending function to have
$G^{3}$ smooth curve interpolation. As shown in Figure 14, every point in the
original data set (red) is passed by the curve. On the other hand, We can
calculate the curvature of the curve to show that the curve can achieve at
least $G^{2}$, see Figure 1 for the color pattern for the curvature. To show
the smoothness of the spline interpolatory curve, another example is given in
Figure 14 in tube view.
As we can see in Figure 1, the curvature is higher near data points, which is
a desired feature. Some other methods like Circular spline will have curvature
peaks in the middle between data points.

Figure 14: 3D interpolatory curve (top) with the given points in red and it’s
in tube view (bottom)

Let us give two more examples in Figure 15 and 16.

|
---|---
Figure 15: A $C^{2}$ smooth interpolating curve (right) based on a given data set (left).  |
---|---
Figure 16: Two views of smooth interpolating curve based on a data set of
human head

######  Example 4.2 (Corner Preservation).

On planar data points, the data points themselves are not always suitable for
smooth interpolation. See Figure 17. In the Figure, we see that in order to
interpolate the point at the corner, we must have a curve that is not a
straight line. To address this feature, we have the following definition:

######  Definition 4.1 (Lacol Convex and Degenerate Points).

Consider a series of $5$ data points ${\bf v}_{1},{\bf v}_{2},\cdots,{\bf
v}_{5}$ on $\mathbb{R}^{2}$, we say point ${\bf v}_{3}$ is a local convex
point if $det({\bf v}_{2}-{\bf v}_{1},{\bf v}_{3}-{\bf v}_{2})$, $det({\bf
v}_{3}-{\bf v}_{2},{\bf v}_{4}-{\bf v}_{3})$, and $det({\bf v}_{4}-{\bf
v}_{3},{\bf v}_{5}-{\bf v}_{4})$ are non-zeros and have same sign. We say 3 is
degenerated if at least one of these three determination are zero.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not regular}\end{subarray}$ Figure 17: The Points at the Corner of Two
Straight Lines Can Not be Smooth without Adding Extra Structure.

We can illustrate the local convex points in the Figure 18. In the figure, let
ray $R_{1}$ start from ${\bf v}_{2}$ with direction ${\bf v}_{1}\to{\bf
v}_{2}$, and ray $R_{2}$ start from ${\bf v}_{4}$ with direction ${\bf
v}_{5}\to{\bf v}_{4}$. We can get a region by these two rays and line ${\bf
v}_{2}-{\bf v}_{4}$ (See shading region in Figure 18). One can easily check
that if ${\bf v}_{3}$ is located in the slash region, then ${\bf v}_{3}$ is a
local convex point. If ${\bf v}_{3}$ is on the boundary of the slash region,
then it’s degenerated. One important case of degenerate points is when ${\bf
v}_{3}$ is at the intersection $A$ of $R_{1}$ and $R_{2}$. The smooth
interpolation curve will not be pleasing. We say ${\bf v}_{3}$ is a corner in
this case. In Figure 17, the red points are corner points. We see that the
interpolation curves lose local convexity when the original polygon is local
convex. In practice, we can easily detect corner points and replace the local
function to be piecewise linear.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not regular}\end{subarray}$${\bf v}_{1}$${\bf v}_{2}$${\bf v}_{4}$${\bf
v}_{5}$$A$$R_{1}$$R_{2}$${\bf v}_{1}$${\bf v}_{2}$${\bf v}_{4}$${\bf
v}_{5}$$R_{1}$$R_{2}$ Figure 18: The degenerated ${\bf v}_{3}$ is located in
the Edges of the slashed Area. The local convex point ${\bf v}_{3}$ will be in
the interior of the slash area. If two rays $R_{1}$ and $R_{2}$ have an
intersection point $A$ (As Shown on the Left), then ${\bf v}_{3}$ would be
categorized as corner if it close to A.

We show an example of taking care of the corners of a given data set. Suppose
that we have a set of data with four corners. If we use our method
straightforwardly, our smooth interpolating curve will have rounded corners.
See the left of Figure 19. When the code recognizes a point as a corner, it
skips the local constructive step and produces the curve with corners by
replacing the local curve with a piecewise linear function, as shown on the
right of Figure 19.

Figure 19: A smooth interpolation curve without and with corners

######  Example 4.3 (Convex Planar Data).

We defined local convex points in Definition 4.1. A natural question arises
here: could we preserve the local convexity? That is, if ${\bf v}_{i}$ is a
local convex point, could we have ${\bf F}_{i}$ such that ${\bf
F}_{i}|_{[i-1,i+1]}$ do not change sign on its curvature? The answer is
affirmative. We can achieve this by choosing a linear local curve. Indeed, let
${\bf v}_{1},{\bf v}_{2},\cdots,{\bf v}_{5}$ be a series of points and ${\bf
v}_{2}$, ${\bf v}_{3}$, and ${\bf v}_{4}$ are local convex points. Suppose
tangent line ${\bf v}_{2}-{\bf v}_{1}$, ${\bf v}_{3}-{\bf v}_{2},\cdots,{\bf
v}_{5}-{\bf v}_{4}$ are ordered clock-wisely as show in Figure 20. Then there
must be a line pass through ${\bf v}_{3}$ which one of its direction vectors
is located between ${\bf v}_{3}-{\bf v}_{2}$ and ${\bf v}_{4}-{\bf v}_{3}$,
shown as the blue line in Figure 20. Because ${\bf v}_{2}$ and ${\bf v}_{4}$
are also local convex, we can find two similar lines pass ${\bf v}_{2}$ and
${\bf v}_{4}$, shown as orange lines in Figure 20. The $P$ and $Q$ are
intersections of the blue line and orange lines. The linear function from $P$
to $Q$ is defined as the local function in this example.

Parametric SpaceGraph$G^{r}$Not nessasary be $G^{r}$Regular $C^{r}$Only
$C^{r}$GraphParametric Space$G^{r}$Not $G^{r}$Existence of regular
$C^{r}$$C^{0}$$\begin{subarray}{c}\text{\tiny Can be }C^{r},\\\ \text{\tiny
but not regular}\end{subarray}$${\bf v}_{1}$${\bf v}_{2}$${\bf v}_{4}$${\bf
v}_{5}$${\bf v}_{3}$$P$$Q$ Figure 20: The local function is chosen to be the
linear function from $P$ to $Q$.

We claim that if we use these local functions and the polynomial $r$-blending
function, then the resulting curve is local convex as long as the data points
are local convex. The proof is quite straightforward. We already claim that
the $r$-bending function is equivalent to Bernstein polynomials:

$\begin{cases}B_{1}(x)=\displaystyle\sum_{\tiny 0\leq i\leq r}b_{i,2r+1}(x)\\\
B_{2}(x)=\displaystyle\sum_{\tiny r+1\leq i\leq
2r+1}b_{i,2r+1}(x).\end{cases}$ (8)

Back to our example in Figure 20. We shall show that the line segment from
${\bf v}_{2}$ to ${\bf v}_{3}$ is local convex. We know that on $[2,3]$, ${\bf
F}_{2}={\bf v}_{2}(1-t)+P\cdot t$ and ${\bf F}_{3}=P\cdot(1-t)+{\bf
v}_{3}\cdot t$. Combine with the formula of $r$ blending curve, one can write
down the curve $\Gamma(t)|_{[2,3]}={\bf F}_{2}(t)B_{1}(t-2)+{\bf
F}_{3}(t)B_{2}(t-2)$ by Bezier polynomial:

$\displaystyle\Gamma(t)|_{[2,3]}$ $\displaystyle={\bf v}_{2}\cdot
b_{0,2r+2}+\displaystyle\sum_{\tiny 1\leq i\leq r}(\frac{2r+2-i}{2r+2}{\bf
v}_{2}+\frac{i}{2r+2}P)b_{i,2r+1}(x)+P\cdot b_{r+1,2r+2}$
$\displaystyle+\displaystyle\sum_{\tiny r+2\leq i\leq
2r+1}(\frac{2r+2-i}{2r+2}P+\frac{i}{2r+2}{\bf v}_{3})b_{i,2r+1}(x)+{\bf
v}_{3}\cdot b_{2r+2,2r+2},$

where $b_{i,j}$ are $i$-th Bezier base polynomial of degree $j$. As we can
see, this line segment is a Bezier curve where all control points are located
on the ${\bf v}_{2}$-$P$ and $P$-${\bf v}_{3}$. The control points form a
convex polygon. By variation diminishing property, the curve is a local convex
curve.

######  Example 4.4 (Sphere Preserving Curves).

In this subsection, we present a few examples to show that when the given data
points on spheres, our smooth interpolating curves will be on the
corresponding spheres. In Example 3.2 of Section 3.1, we already explained the
local curve of the arc. One of the advantages of using arcs as local curves is
that the curve is locally a circle if the dataset itself is intended to behave
like a circle, see Figure 21.

Figure 21: The curve is locally adaptive to circles when the data points are
locally scattered on two circles.

In the case of three-dimensional space, one may need to adapt a curve on
spherical data. Because we use the circular local function, we can always
expect our local curves to be located on the sphere when the data cloud is on
the sphere. When we glue the two local curves on a sphere, all we have to do
is to use a special gluing function. For instance, when we glue two arcs on a
sphere from $P$ to $Q$, see Figure 22. We can define $\Phi(s,x)$, where
$\Phi(s,0)$ and $\Phi(s,1)$ are two arcs pass $P$ and $Q$ that we are going to
glue. We can define ${\bf f}_{x}(s)=\Phi(s,x)$ as a series of arcs on the
sphere pass $P$ and $Q$ with uniform arc length so that ${\bf f}_{x}(0)=P$ and
${\bf f}_{x}(1)=Q$ for all $x\in[0,1]$. For the $x$ direction, one can easily
find that the center of these arcs will be located on a circle inside the
sphere. Therefore, we can parametrize the $x$ direction by the center location
of these arcs. More specifically, let $C(x)$ be the center of the arc of ${\bf
f}_{x}(s)$ and we choose $|dC(x)/dx|$ to be a constant. In this way, we define
the gluing function by $\Phi(s,B_{1}(s))$, where $B_{1}$ is the blending
function.

Figure 22: The grid defined by $\phi(x,t)$on the sphere. Two red curves are
the arcs to be glued. And the green line is the resulting curve after gluing.

As shown in Figure 23, two curves are presented to demonstrate that our
interpolating curves will be on the corresponding spheres when the given data
points are on the spheres. We can see that the curve fits the sphere whenever
the data points are on the sphere.

|
---|---
Figure 23: Two examples of smooth interpolating curves which show that the
curves will be on the sphere according to the given data points

In the next example, we have a lot of points on the unit sphere. Our smooth
interpolating curve is also on the same sphere as shown in Figure 24.

Figure 24: Our Smooth Interpolating Curve is on the Sphere (right) as the
Given Data Points on the Sphere(left)

##  5 Conclusion and Future works

In this paper, we present an organized framework for constructing smoothly
interpolating curves in $\mathbb{R}^{n}$ with a high level of smoothness
customization. While incorporating and refining existing approaches, our
algorithm breaks down the smooth curve construction into four key components:
the local function, blending function, distributing function, and gluing
function.
The local function depends on the needs of shape design. One could use pure
polynomials to simplify the calculation and save the storage, as shown in
Example 4.1. In addition to the oriented points, some tangent vectors and
normal vectors are also given, we can modify our algorithm easily by using
local functions with derivative interpolation properties. Some useful local
functions like circular functions in Example 3.2 and linear functions to
preserve the convexity in Example 4.3 are also useful in various scenarios.
Note that the local functions are not necessarily the same for all points. For
instance, on the boundary, one may apply different boundary local functions to
get the desired curve. In Example 4.2, we also show that by replacing the
local function on the degenerated points, the curve can have the corner that
we expected. In another example 4.3, we explained a convexity of the data
points could be preserved if we use linear functions as local functions. The
choice of local function is not limited to the example we have shown in this
paper.

The Blending functions are used to determine the smoothness of the final
curves. Applying $r$-blending functions can give us a $G^{r}$ curve in most
cases. We also saw that we can use the trigonometric function or other
functions to replace the polynomial blending functions if they satisfy
Definition 3.5.
The redistribution function maps the coordinate of the local function to a
standard coordinate, which has one unit between each node. In this paper, we
only use the piecewise linear map as our redistribution function. By Theorem
3.5, we may need our function ${\bf F}_{i}$ after redistribution to be
positive definite and regular. For the same local function, we could make the
redistributed function positive definite by choosing a suitable redistribution
function. The only non positive definite ${\bf F}_{i}$ in this paper is the
circular functions. However, Yuksel has proved that the curve is $G^{2}$ in
his paper [7]. So, using the piecewise linear function in this case is fine.
When linear gluing may be a good choice, most of the time, we may need a
different way to glue the two curves together. In Example 4.4, we demonstrate
a special way to glue two curves together so that the final curve will locate
on the same sphere as its original two curves. In the example, the gluing
function does not affect the final smoothness because it is $C^{\infty}$. If
one uses other gluing functions, they may lose smoothness if the function is
not smooth enough.

In this paper, we analyze previous works and decompose them into four parts of
the function. Each part take there unique role in the construction of the
final curve. We also indicated that the blending functions take an important
role of smoothness. By providing $r$-blending functions, we can now push the
smoothness to any degree. We also give a necessary conditions that make the
curve to be $G^{r}$ so when people use there preferred local function in our
algorithm, they would expect a smooth curve as long as there formulate meets
the condition.

Acknowledgments The authors are very grateful to the editor and referees for
their helpful comments.

## Declarations

  * •

Funding. The second author is supported by the Simons Foundation for
collaboration grant #864439.

  * •

Competing interests. On behalf of all authors, the corresponding author states
that there is no conflict of interest.

## References

  *   * DeRose [1985] DeRose, A.D.: Geometric continuity: A parametrization independent measure of continuity for computer aided geometric design. PhD thesis, EECS Department, University of California, Berkeley (Aug 1985). http://www2.eecs.berkeley.edu/Pubs/TechRpts/1985/6081.html
  * Gregory [1989] Gregory, J.A.: Geometric Continuity. In: Lyche, T., Schumaker, L.L. (eds.) Mathematical Methods in Computer Aided Geometric Design, pp. 353–371. Academic Press, ??? (1989). https://doi.org/10.1016/B978-0-12-460515-2.50028-7 . https://www.sciencedirect.com/science/article/pii/B9780124605152500287 Accessed 2022-07-31
  * Garrity and Warren [1991] Garrity, T., Warren, J.: Geometric continuity. Computer Aided Geometric Design 8(1), 51–65 (1991) https://doi.org/10.1016/0167-8396(91)90049-H . Accessed 2022-07-31
  * Farin [1993] Farin, G.: Curves and Surfaces for Computer-Aided Geometric Design (Third Edition), Third edition edn., pp. 229–249. Academic Press, Boston (1993). https://doi.org/%****␣sn-article.bbl␣Line␣100␣****10.1016/B978-0-12-249052-1.50019-2 . https://www.sciencedirect.com/science/article/pii/B9780122490521500192
  * Les Piegl [1995] Les Piegl, W.T.: The NURBS Book. Monographs in Visual Communication, vol. XIV, 646. Springer, Heidelberg (1995)
  * Wenz [1996] Wenz, H.-J.: Interpolation of curve data by blended generalized circles. Computer Aided Geometric Design 13(8), 673–680 (1996) https://doi.org/10.1016/0167-8396(95)00054-2
  * Yuksel [2020] Yuksel, C.: A class of c2 interpolating splines. ACM Transactions on Graphics 39(5), 160–116014 (2020) https://doi.org/10.1145/3400301
  * Bertolazzi and Frego [2018] Bertolazzi, E., Frego, M.: On the g2 hermite interpolation problem with clothoids. Journal of Computational and Applied Mathematics 341, 99–116 (2018) https://doi.org/10.1016/j.cam.2018.03.029
  * Knott [2000] Knott, G.D.: Function and Space Curve Interpolation, pp. 59–61. Birkhäuser Boston, Boston, MA (2000). https://doi.org/10.1007/978-1-4612-1320-8_4 . https://doi.org/10.1007/978-1-4612-1320-8_4
  * Lee [1989] Lee, E.T.Y.: Choosing nodes in parametric curve interpolation. Computer-Aided Design 21(6), 363–370 (1989) https://doi.org/10.1016/0010-4485(89)90003-1
  * Carmo [2016] Carmo, M.P.d.: Differential Geometry of Curves and Surfaces: Revised and Updated Second Edition. Courier Dover Publications, ??? (2016). Google-Books-ID: gg2xDQAAQBAJ
  * Hu [2023] Hu, T.-W.: Computational methods for smooth mapping and interpolation using multivariate spline techniques. PhD thesis, University of Georgia (2023)