%%% BEGIN BEAMER PREAMBLE %%%
\documentclass{beamer}
\usepackage{bm, fourier, anyfontsize, xcolor}

\mode<presentation>
{
  \usetheme{boxes}
  \usecolortheme{crane}
}
\beamertemplatenavigationsymbolsempty

\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection]
  \end{frame}
}

\newcommand{\seti}{\setcounter{saveenumi}{\value{enumi}}}
\newcommand{\conti}{\setcounter{enumi}{\value{saveenumi}}}

\resetcounteronoverlays{saveenumi}

\usepackage{times}
%%% END BEAMER PREAMBLE %%%


%%% BEGIN METADATA %%%

\author{Jordi G. H. $\langle$jordigh@octave.org$\rangle$ }
\institute{Also @JordiGH@mathstodon.xyz on the Fediverse/Mastodon}

\title{X-Splines}
\subtitle{Flexible and user-friendly}

%%% END METADATA%%%

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
\end{frame}

\section{Splines in general}

\begin{frame}{What is a spline?}
  \pause
  \begin{center}
    \pgfimage[height=2.5in]{img/history.pdf}
  \end{center}
  Historically: a mechanical device for drawing curves
\end{frame}

\begin{frame}{What is a spline?}
  You probably know them from computer graphics or CAD.
  \begin{center}
    \pgfimage[height=2.5in]{img/svg-spline.pdf}
  \end{center}
\end{frame}

\begin{frame}{What is a spline?}
  You probably know them from computer graphics or CAD.
  \begin{center}
    \pgfimage[height=2.5in]{img/computer-graphics-spline.pdf}
  \end{center}
\end{frame}

\begin{frame}{Guiding example: b-splines}
  These splines \emph{approximate}.
  \begin{center}
    \pgfimage[height=2.5in]{img/bspline.pdf}
  \end{center}
\end{frame}

\begin{frame}{Guiding example: Catmull-Rom splines}
  These splines \emph{interpolate}.
  \begin{center}
    \pgfimage[height=2.5in]{img/catmullrom.pdf}
  \end{center}
\end{frame}

\begin{frame}{Another famous example: Bézier curves}
  Closely related to B-splines
  \begin{center}
    \pgfimage[height=2.5in]{img/bezier.pdf}
  \end{center}
\end{frame}


\begin{frame}{What makes a spline a spline?}
  General formula:
  
  \pause
  For each \emph{node} in 2d (or 3d) space there is a
  corresponding \emph{blending function}:
  \[
    \begin{matrix}
      (x_0, y_0) = P_0 & \longleftrightarrow & F_0(t) \\
      (x_1, y_1) = P_1 & \longleftrightarrow & F_1(t) \\
      &   \vdots & \\
      (x_n, y_n) = P_n & \longleftrightarrow & F_n(t)
    \end{matrix}
  \]
  \pause
  and we form a \emph{linear combination}
  \begin{align*}
    C(t) &= \sum_{k=0}^{n} F_k(t) P_k \\
         &= F_0(t)P_0 + F_1(t)P_1 + \cdots + F_n(t)P_n.
  \end{align*}
  \pause
  The parameter \(t\) runs continuously from \(0\) to \(n\).
\end{frame}

\begin{frame}{Convexity (optional)}
  \pause
  The blending functions \(F_k(t)\) must satisfy
  \pause
  \begin{itemize}
    \item \(1 = \sum_{k=0}^n F_k(t)\) \pause (technical jargon:
    \emph{partition of unity})
    \pause
    \item \(0 \leq F_k(t) \)
  \end{itemize}
  \pause
  This implies every point on the spline curve
  \[
    C(t) = \sum_{k=0}^{n} F_k(t) P_k
  \]
  \pause
  is a \emph{convex combination} of the spline nodes.
  \begin{center}
    \pgfimage[height=1.2in]{img/convex-combination.pdf}
  \end{center}
\end{frame}

\begin{frame}{Convexity}
  Remember?
  \begin{center}
    \pgfimage[height=2.5in]{img/svg-spline.pdf}
  \end{center}
\end{frame}

\begin{frame}{Smooth and steady}
  Splines must be smooth (not spiky) and steady (not too wobbly)
  
  \pause
  Therefore, blending functions \(F_k(t)\) must look like this:
  \begin{center}
    \pgfimage[height=2.0in, width=3.0in]{img/blending-functions.pdf}
  \end{center}
  \pause
  \begin{itemize}
    \item Bump-shaped (smoothness)
    \pause
    \item Always go in opposite direction when they cross (steadiness)
  \end{itemize}
\end{frame}

\begin{frame}{Local influence}
  Each blending function \(F_k(t)\) must not contribute to nodes
  \(P_k\) that are too far away.
  
  \pause
  Therefore, the blending functions are zero outside of a small zone
  (in technical jargon: \emph{compact support}).
  \begin{center}
    \pgfimage[height=2.0in, width=3.0in]{img/blending-functions.pdf}
  \end{center}
\end{frame}

\section{X-splines}

\begin{frame}{Additional requirements}
  To summarize, we require at first:
  \begin{itemize}
    \pause
    \item convexity
    \pause
    \item smoothness
    \pause
    \item steadiness
    \pause
    \item locality
  \end{itemize}
  \pause
  We want in addition
  \begin{itemize}
    \pause
    \item flexibility of shape
    \pause
    \item intuitive shape parameter
    \pause
    \item smooth transition between approximation and interpolation
  \end{itemize}
\end{frame}

\begin{frame}{The Plan}
  \pause
  Will begin with polynomial blending functions \(F_k(t)\), e.g. one such
  function for Bézier curves
  \[
    f_k(t) = 3t^2(1-t)
  \]
  \pause
  To get convexity, (partition of unity) will normalise each blending
  function, i.e.
  \[
    F_t(t) := \frac{f_k(t)}{\sum_{k=0}^n f_k(t)}
  \]
  giving a \emph{rational function} (a fraction of polynomials).
\end{frame}

\begin{frame}{The Plan}
  The functions will be defined piecewise on equally-spaced intervals
  of the parameter space, i.e.
  \[
    f_k(t) :=
    \begin{cases}
      f\left(\frac{t-k}{2}\right) &\text{if } t \in [k-2, k]  \\
      f\left(\frac{k-t}{2}\right) &\text{if } t \in [k, k+2] \\
      0 &\text{otherwise}
    \end{cases}
  \]
  \pause
  \begin{center}
    \pgfimage[width=3.5in, height=1.8in]{img/piecewise.pdf}
  \end{center}
\end{frame}

\begin{frame}{The Plan}
  Recall: blending functions
  \begin{center}
    \pgfimage[height=2.0in, width=3.0in]{img/blending-functions.pdf}
  \end{center}
  \pause
  Neighbours of $F_k(t)$ cross at $k$, hence \emph{cross-splines} or x-splines.
\end{frame}

\begin{frame}{The Plan}
  We will impose continuity and smoothness (derivatives) conditions at
  the parameter knots.
  \pause
  \begin{itemize}
    \item Values of each segment must be equal
    \pause
    \item First derivatives (tangent lines) must be equal
    \pause
    \item Second derivatives (curvatures) must be equal
  \end{itemize}
\end{frame}

\begin{frame}{The basic ingredient}
  Let's build the basic x-spline function \(f(u)\).

  \pause
  For simplicity, let's work on the interval \([0,1]\) and require
  \begin{align*}
    f(0) &= 0 & f'(0) &= 0 & f''(0) &= 0\\
    f(1) &= 1 & f'(1) &= 0 & f''(1) &= -2p
  \end{align*}
  \pause
  Six equations, so degree 5 polynomial. Solve to get
  \[
    f(u) = (6-p)u^5 + (2p-15)u^4 + (10-p)u^3
  \]
\end{frame}

\begin{frame}{The basic ingredient}
  As free parameter \(p\) varies from \(0\) to \(10\), we have some
  flexibility in shape:
  \begin{center}
    \pgfimage[height=2.5in, width=3.5in]{img/fpu.pdf}
  \end{center}
  \[
    f(u) = (6-p)u^5 + (2p-15)u^4 + (10-p)u^3
  \]
\end{frame}

\begin{frame}{The basic x-spline}
  Summarising, x-spline formula for \(F_k(t)\) is:
  \[
    F_K(t) = \frac{f_k(t)}{\sum_{k=0}^n f_k(t)}
  \]
  \pause
  where
  \[
    f_k(t) :=
    \begin{cases}
      f\left(\frac{t-k}{2}, p_k^{\mathrm{Left}}\right) &\text{if } t \in [k-2, k]  \\
      f\left(\frac{k-t}{2}, p_k^{\mathrm{Right}}\right) &\text{if } t \in [k, k+2] \\
      0 &\text{otherwise}
    \end{cases}
  \]
  \pause
  and
  \[
    f(u, p) = (6-p)u^5 + (2p-15)u^4 + (10-p)u^3.
  \]
  \pause
  Observe that each \(F_k(t)\) has its own \(p_k^{\mathrm{Left}}\) and
  \(p_k^{\mathrm{Right}}\)parameters too!
\end{frame}

\begin{frame}{The basic x-spline}
  Setting all \(p = 8\), we get a very good approximation of B-splines.
  \begin{center}
    \pgfimage[width=3.5in]{img/fakebspline.pdf}
  \end{center}
\end{frame}

\section{X-tended X-splines}

\begin{frame}{Pushing the blending function upwards}
  The parameters \(p_k^{\mathrm{Left}}\) and \(p_k^{\mathrm{Right}}\)
  give us some freedom to modify the spline more.

  \pause
  Will use them to modify the blending functions \(F_k(t)\) like so.

  \begin{center}
    \pgfimage[width=2in, height=2.5in]{img/before.eps}
    \pgfimage[width=2in, height=2.5in]{img/after.eps}
  \end{center}
\end{frame}

\begin{frame}{Exercise for the audience}
  Calculations and notation gets a bit messy, but the idea is
  \begin{enumerate}
    \pause
    \item Assign a new parameter \(s_k \in [0,1]\)  to each blending function
    \(F_k(t)\).
    \pause
    \item When all \(s_k = 1\), we have all \(p = 8\) and a basic
    approximating x-spline.
    \pause
    \item Define new zeroing points for the neighbours of \(F_k(t)\):
    \begin{align*}
      T_{k-1}^{\mathrm{Right}} &:= k + s_k \\
      T_{k+1}^{\mathrm{Left}} &:= k - s_k
    \end{align*}
    \pause
    \item
    To preserve curvature (equality of second derivatives at \(k-1\)
    and \(k+1\)), this requires setting special values of \(p\)
    \begin{align*}
      p_{k-1}^{\mathrm{Right}} &= 2(k - T_{k-1}^{\mathrm{Right}})^2 \\
      p_{k+1}^{\mathrm{Left}} &= 2(k - T_{k+1}^{\mathrm{Left}})^2
    \end{align*}
  \end{enumerate}
\end{frame}

\begin{frame}{Can now interpolate sharply}
  End result: as \(s_k\) goes from \(1\) to \(0\) at a particular
  node, the spline gets closer to the node until it is interpolated
  sharply.
  \begin{center}
    \pgfimage[width=2in, height=2.5in]{img/strumming.pdf}
  \end{center}
\end{frame}

\begin{frame}{Fonts!}
  Good for drawing some basic fonts.
  \begin{center}
    \pgfimage[width=2in, height=2.5in]{img/x-spline.pdf}
  \end{center}
\end{frame}

\section{General X-splines}

\begin{frame}{Smooth interpolation}
  To have smooth interpolation, we have to drop the convexity requirement.

  \pause
  Recall, partition of unity:
  \begin{align*}
    1 &= \sum_{k=0}^n F_k(t) \\
    0 &\leq F_k(t)
  \end{align*}
  \pause
  We'll keep the sum equal to 1, but we'll let the blending functions go negative now.

  \pause We've pushed the tails of the blending functions down to zero
  (via \(s_k\) parameters). We'll push those tails further down into
  the negative.
\end{frame}

\begin{frame}{Pushing way down}
  Blending functions \(F_k(t)\) will now look like this:
  \begin{center}
    \pgfimage[width=2in, height=2.5in]{img/after.eps}
    \pgfimage[width=2in, height=2.5in]{img/waydown.pdf}
  \end{center}
\end{frame}

\begin{frame}{Polynomial requirements again}
  This time use two polynomials, \(g(u)\) for the positive part and
  \(h(h)\) for the negative part.

  \pause
  If we pick the domain of \(h(u)\) to be from \(-1\) to \(0\)
  and that of \(g(u)\) to go from \(0\) to \(1\)...

  \pause
  12 conditions on continuity, tangent line, and curvature:
  \begin{align*}
    h(-1) &= 0 & h'(-1) &= q & h''(-1) &= 0 \\
    h(0) &= 0 & h'(0) &= q & h''(0) &= 4q \\
    g(0) &= 0 & g'(0) &= q & g''(0) &= 4q \\
    g(1) &= 1 & g'(1) &= 0 & g''(1) &= -2p 
  \end{align*}
  \pause
  Degree 5 solutions:
  \begin{align*}
    g(u) &= qu + 2qu^2 + (10 -12q - p)u^3 \\
         &+ (2p + 14q - 15)u^4 + (6 - 5q -p)u^5 \\
    h(u) &= qu + 2qu^2 - 2qu^4 + qu^5
  \end{align*}
\end{frame}

\begin{frame}{Recovering Catmull-Rom}
  New \(q\) parameter to play with, corresponding to the \(s_k\) parameters:
  \[
    q_{k-1}^{\mathrm{Right}} := -\frac{s_k}{2} =: q_{k+1}^{\mathrm{Left}}
  \]

  \pause

  When \(q = 1/2\) everywhere (i.e. \(s=-1\) everywhere), we get an
  almost exact copy of Catmull-Rom.
    \begin{center}
    \pgfimage[height=2in]{img/x-spline-q-full.pdf}
  \end{center}
\end{frame}

\begin{frame}{Letting \(s\) vary slowly}
  Smoothly goes from sharp interpolation to smooth interpolation:
  \begin{center}
    \pgfimage[height=2.5in]{img/morestrumming.eps}
  \end{center}
\end{frame}

\begin{frame}{Thanks!}
  \begin{center}
    jordigh@octave.org or @JordiGH@mathstodon.xyz on Mastodon

    \pause
    Remember xfig?
  \end{center}    
\end{frame}

\end{document}