doc/euclidean/re-parameterization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "This notebook is part of https://github.com/AudioSceneDescriptionFormat/splines, see also https://splines.readthedocs.io/.\n",
    "\n",
    "[back to Euclidean splines](index.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Re-Parameterization\n",
    "\n",
    "\n",
    "As we have seen previously\n",
    "-- for example with\n",
    "[Hermite splines](hermite-non-uniform.ipynb#Example-Plot)\n",
    "and\n",
    "[Catmull--Rom splines](catmull-rom-properties.ipynb#Parameterized-Parameterization) --\n",
    "changing the relative amount of time\n",
    "(or more generally, the relative size of the parameter interval)\n",
    "per spline segment leads to different curve shapes.\n",
    "Given the same underlying polynomials,\n",
    "we cannot simply re-scale the parameter values\n",
    "without affecting the shape of the curve.\n",
    "\n",
    "However, sometimes we want to keep the shape\n",
    "(or more accurately,\n",
    "the [image](https://en.wikipedia.org/wiki/Image_(mathematics)))\n",
    "of a curve intact\n",
    "and only change its timing.\n",
    "\n",
    "This can be done by introducing a function\n",
    "that maps from a new set of parameter values\n",
    "to the parameter values of the original spline."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arc-Length Parameterization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of using a curve $\\boldsymbol{x}(t)$\n",
    "with a free parameter $t$ (which we often interpret as time),\n",
    "it is sometimes useful to have a curve $\\boldsymbol{x}_\\text{arc}(s)$\n",
    "with the same image\n",
    "but where the parameter $s$ represents the distance travelled\n",
    "since the beginning of the curve.\n",
    "The length of a piece of curve is called\n",
    "[arc length](https://en.wikipedia.org/wiki/Arc_length)\n",
    "and therefore $\\boldsymbol{x}_\\text{arc}(s)$\n",
    "is called *arc-length parameterized*.\n",
    "Sometimes, this is also called \"natural\" parameterization\n",
    "-- not to be confused with [natural splines](natural.ipynb)\n",
    "and [natural end conditions](end-conditions-natural.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An interesting (and slightly confusing) thing to do now,\n",
    "is to use $\\boldsymbol{x}_\\text{arc}(s)$ with time as a parameter.\n",
    "Note that the speed along a curve is calculated as\n",
    "distance per time interval ($v = \\frac{ds}{dt}$),\n",
    "but if time and distance are the same ($s \\equiv t$),\n",
    "we get a constant speed $v = \\frac{ds}{ds} = 1$.\n",
    "In other words,\n",
    "the tangent vector of an arc-length parameterized curve\n",
    "always has unit length."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To turn an existing curve\n",
    "$\\boldsymbol{x}(t)$\n",
    "into its arc-length parameterized counterpart\n",
    "$\\boldsymbol{x}_\\text{arc}(s)$,\n",
    "we need the parameter $t$ as function of travelled distance $s$,\n",
    "i.e. $t(s)$:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{x}_\\text{arc}(s) = \\boldsymbol{x}(t(s))\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sadly, we don't know $t(s)$,\n",
    "but we can find $s(t)$ and then try to find the inverse function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the tangent vector\n",
    "$\\frac{d}{d\\tau} \\boldsymbol{x}(\\tau)$\n",
    "(i.e. the velocity)\n",
    "at every infinitesimally small time interval $d\\tau$.\n",
    "The length travelled along the curve in that time interval\n",
    "is the length of the tangent vector\n",
    "$\\left|\\frac{d}{d\\tau} \\boldsymbol{x}(\\tau)\\right|$\n",
    "(i.e. the speed)\n",
    "multiplied by the time interval $d\\tau$.\n",
    "Adding all these small pieces\n",
    "from $t_0$ to $t$\n",
    "results in the arc length\n",
    "\n",
    "\\begin{equation*}\n",
    "s(t) = \\int\\limits_{t_0}^t \\left| \\frac{d}{d\\tau}\\boldsymbol{x}(\\tau) \\right| d\\tau.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This looks straightforward enough,\n",
    "but it turns out that this integral cannot be solved analytically\n",
    "if $\\boldsymbol{x}(t)$ is cubic (or of higher degree).\n",
    "The reason for that is the\n",
    "[Abel–Ruffini theorem](https://en.wikipedia.org/wiki/Abel–Ruffini_theorem).\n",
    "\n",
    "We'll have to use\n",
    "[numerical integration](https://en.wikipedia.org/wiki/Numerical_integration)\n",
    "instead."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we need to invert this function.\n",
    "In other words, given an arc length $s$,\n",
    "we have to provide a way to obtain the corresponding $t$.\n",
    "This can be reduced to a root finding problem,\n",
    "which can be solved with different numerical methods,\n",
    "for example with the\n",
    "[bisection method](https://en.wikipedia.org/wiki/Bisection_method)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arc-length re-parameterization is implemented in the Python class\n",
    "[splines.UnitSpeedAdapter](../python-module/splines.rst#splines.UnitSpeedAdapter).\n",
    "This is using\n",
    "[scipy.integrate.quad()](https://docs.scipy.org/doc/scipy/reference/generated/scipy.integrate.quad.html)\n",
    "for numerical integration and\n",
    "[scipy.optimize.bisect()](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.bisect.html)\n",
    "for root finding.\n",
    "\n",
    "Let's show an example spline using the vertices from the\n",
    "[section about centripetal parameterization](catmull-rom-properties.ipynb#Centripetal-Parameterization):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "points4 = [\n",
    "    (0, 0),\n",
    "    (0, 0.5),\n",
    "    (1.5, 1.5),\n",
    "    (1.6, 1.5),\n",
    "    (3, 0.2),\n",
    "    (3, 0),\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import splines\n",
    "from helper import plot_spline_2d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we create a centripetal Catmull--Rom spline ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = splines.CatmullRom(points4, alpha=0.5, endconditions='closed')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... which we then convert to an arc-length parameterized spline:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s2 = splines.UnitSpeedAdapter(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "plot_spline_2d(s1, dots_per_second=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Evaluating the arc-length parameterized spline takes quite a bit longer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "plot_spline_2d(s2, dots_per_second=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are plotting 10 dots per second,\n",
    "and we can count about 10 dots per unit of distance,\n",
    "which confirms that the spline has a speed of 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spline-Based Re-Parameterization\n",
    "\n",
    "We can choose any function to map a new parameter to old parameter values.\n",
    "Since we are already talking about splines,\n",
    "we might as well use a one-dimensional spline.\n",
    "To rule out backwards movement along the original spline,\n",
    "we should use use a\n",
    "[monotone spline](piecewise-monotone.ipynb#Monotone-Interpolation)\n",
    "as implemented, for example, in the class\n",
    "[splines.MonotoneCubic](../python-module/splines.rst#splines.MonotoneCubic).\n",
    "\n",
    "A tool for re-parameterizing an existing spline is available in the class\n",
    "[splines.NewGridAdapter](../python-module/splines.rst#splines.NewGridAdapter).\n",
    "\n",
    "This is especially useful when applied to\n",
    "an already arc-length parameterized spline,\n",
    "because then the slope of the parameter re-mapping function\n",
    "directly corresponds to the speed along the spline.\n",
    "\n",
    "Not all new parameter values have to be explicitly given.\n",
    "If unspecified, they are interpolated from the surrounding values.\n",
    "\n",
    "For closed curves it might be useful to have the same slope\n",
    "at the beginning and the end of the spline.\n",
    "This can be achieved by using `cyclic=True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_grid = [-1, -0.5, None, None, 2, None, 3]\n",
    "s3 = splines.NewGridAdapter(s2, new_grid, cyclic=True)\n",
    "s3.grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "plot_spline_2d(s3, dots_per_second=10)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}