doc/euclidean/catmull-rom-properties.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 overview](catmull-rom.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Properties of Catmull--Rom Splines\n",
    "\n",
    "<cite data-cite-t=\"catmull1974splines\">Catmull and Rom (1974)</cite>\n",
    "present a whole class of splines with a whole range of properties.\n",
    "Here we only consider one member of this class which is\n",
    "a cubic polynomial interpolating spline with $C^1$ continuity and local support.\n",
    "Nowadays, this specific case is typically simply referred to as\n",
    "*Catmull--Rom spline*.\n",
    "\n",
    "This type of spline is very popular because they are very easy to use.\n",
    "Only a sequence of control points has to be specified, the corresponding tangents are calculated automatically from the given points.\n",
    "Using those tangents, the spline can be implemented using\n",
    "cubic [Hermite splines](hermite.ipynb).\n",
    "Alternatively, spline values can be directly calculated\n",
    "with the [Barry--Goldman algorithm](catmull-rom-barry-goldman.ipynb).\n",
    "\n",
    "To calculate the spline values between two control points,\n",
    "the preceding and the following control points are needed as well.\n",
    "The tangent vector at any given control point\n",
    "can be calculated from this control point,\n",
    "its predecessor and its successor.\n",
    "Since Catmull--Rom splines are $C^1$ continuous,\n",
    "incoming and outgoing tangent vectors are equal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following examples use the Python class\n",
    "[splines.CatmullRom](../python-module/splines.rst#splines.CatmullRom)\n",
    "to create both uniform and non-uniform splines.\n",
    "Only closed splines are shown,\n",
    "other [end conditions](end-conditions.ipynb)\n",
    "can also be used, but they are not specific to this type of spline."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "np.set_printoptions(precision=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apart from the [splines](../python-module/splines.rst) module ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import splines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... we also import a few helper functions from [helper.py](helper.py):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper import plot_spline_2d, plot_tangent_2d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's choose a few points for an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "points1 = [\n",
    "    (-1, -0.5),\n",
    "    (0, 2.3),\n",
    "    (1, 1),\n",
    "    (4, 1.3),\n",
    "    (3.8, -0.2),\n",
    "    (2.5, 0.1),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Without specifying any time values,\n",
    "we get a uniform spline:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = splines.CatmullRom(points1, endconditions='closed')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "plot_spline_2d(s1, ax=ax)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tangent Vectors\n",
    "\n",
    "In the uniform case,\n",
    "the tangent vectors at any given control point\n",
    "are parallel to the line connecting the preceding point and the following point.\n",
    "The tangent vector has the same orientation as that line\n",
    "but only half its length.\n",
    "In other (more mathematical) words:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i = \\frac{\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_{i-1}}{2}\n",
    "\\end{equation*}\n",
    "\n",
    "This is illustrated for two control points in the following plot:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for idx, color in zip([2, 5], ['purple', 'hotpink']):\n",
    "    plot_tangent_2d(\n",
    "        s1.evaluate(s1.grid[idx], 1),\n",
    "        s1.evaluate(s1.grid[idx]), color=color, ax=ax)\n",
    "    ax.plot(\n",
    "        *s1.evaluate([s1.grid[idx - 1], s1.grid[idx + 1]]).T,\n",
    "        '--', color=color, linewidth=2)\n",
    "fig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see here that each tangent vector is parallel to\n",
    "and has half the length of\n",
    "the line connecting the preceding and the following vertex,\n",
    "just as promised.\n",
    "\n",
    "However, this will not be true anymore\n",
    "if we are using non-uniform time instances:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "times2 = 0, 1, 2.2, 3, 4, 4.5, 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s2 = splines.CatmullRom(points1, grid=times2, endconditions='closed')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_spline_2d(s2, ax=ax)\n",
    "for idx, color in zip([2, 5], ['green', 'crimson']):\n",
    "    plot_tangent_2d(\n",
    "        s2.evaluate(s2.grid[idx], 1),\n",
    "        s2.evaluate(s2.grid[idx]), color=color, ax=ax)\n",
    "fig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the non-uniform case,\n",
    "the equation for the tangent vector gets quite a bit more complicated:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i =\n",
    "\\frac{\n",
    "(t_{i+1} - t_i)^2 (\\boldsymbol{x}_i - \\boldsymbol{x}_{i-1}) +\n",
    "(t_i - t_{i-1})^2 (\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_i)\n",
    "}{\n",
    "(t_{i+1} - t_i)(t_i - t_{i-1})(t_{i+1} - t_{i-1})\n",
    "}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The derivation of this equation is shown in\n",
    "[a separate notebook](catmull-rom-non-uniform.ipynb#Tangent-Vectors)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equivalently, this can be written as:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i =\n",
    "\\frac{\n",
    "(t_{i+1} - t_i) (\\boldsymbol{x}_i - \\boldsymbol{x}_{i-1})\n",
    "}{\n",
    "(t_i - t_{i-1})(t_{i+1} - t_{i-1})\n",
    "}\n",
    "+\n",
    "\\frac{\n",
    "(t_i - t_{i-1}) (\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_i)\n",
    "}{\n",
    "(t_{i+1} - t_i)(t_{i+1} - t_{i-1})\n",
    "}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also equivalently,\n",
    "with\n",
    "$\\boldsymbol{v}_i = \\frac{\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_i}{t_{i+1} - t_i}$,\n",
    "it can be written as:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i =\n",
    "\\frac{\n",
    "(t_{i+1} - t_i) \\boldsymbol{v}_{i-1} + (t_i - t_{i-1}) \\boldsymbol{v}_i\n",
    "}{\n",
    "(t_{i+1} - t_{i-1})\n",
    "}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wrong Tangent Vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some sources provide a simpler equation\n",
    "which is different from the tangent vector of a Catmull--Rom spline\n",
    "(except in the uniform case):\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i\n",
    "\\overset{?}{=}\n",
    "\\frac{\\boldsymbol{v}_{i-1} + \\boldsymbol{v}_i}{2}\n",
    "=\n",
    "\\frac{1}{2} \\left(\n",
    "\\frac{\\boldsymbol{x}_i - \\boldsymbol{x}_{i-1}}{t_i - t_{i-1}} +\n",
    "\\frac{\\boldsymbol{x}_{i + 1} - \\boldsymbol{x}_i}{t_{i + 1} - t_i}\n",
    "\\right)\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MeanVelocity(splines.CatmullRom):\n",
    "    \n",
    "    @staticmethod\n",
    "    def _calculate_tangent(points, times):\n",
    "        x_1, x0, x1 = np.asarray(points)\n",
    "        t_1, t0, t1 = times\n",
    "        v_1 = (x0 - x_1) / (t0 - t_1)\n",
    "        v0 = (x1 - x0) / (t1 - t0)\n",
    "        return (v_1 + v0) / 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Until April 2023,\n",
    "[Wikipedia](https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull–Rom_spline)\n",
    "showed yet a simpler equation.\n",
    "They mentioned that \"this assumes uniform parameter spacing\",\n",
    "but since $t_{i - 1}$ and $t_{i + 1}$ appeared in the equation,\n",
    "it might be tempting to use it\n",
    "for the non-uniform case as well.\n",
    "We'll see below how that turns out.\n",
    "\n",
    "The authors of the page don't seem to have been quite sure about this equation,\n",
    "because it has changed over time.\n",
    "This was\n",
    "[shown until mid-2021](https://web.archive.org/web/20210420082245/https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull–Rom_spline):\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i \\overset{?}{=} \\frac{\\boldsymbol{x}_{i + 1} - \\boldsymbol{x}_{i - 1}}{t_{i + 1} - t_{i - 1}}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Wikipedia1(splines.CatmullRom):\n",
    "    \n",
    "    @staticmethod\n",
    "    def _calculate_tangent(points, times):\n",
    "        x_1, _, x1 = np.asarray(points)\n",
    "        t_1, _, t1 = times\n",
    "        return (x1 - x_1) / (t1 - t_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And this slight variation was [shown since then](https://web.archive.org/web/20210727071020/https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull–Rom_spline)\n",
    "until April 2023:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\boldsymbol{\\dot{x}}_i \\overset{?}{=} \\frac{1}{2}\\frac{\\boldsymbol{x}_{i + 1} - \\boldsymbol{x}_{i - 1}}{t_{i + 1} - t_{i - 1}}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Wikipedia2(splines.CatmullRom):\n",
    "    \n",
    "    @staticmethod\n",
    "    def _calculate_tangent(points, times):\n",
    "        x_1, _, x1 = np.asarray(points)\n",
    "        t_1, _, t1 = times\n",
    "        return (1/2) * (x1 - x_1) / (t1 - t_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first one is correct in the uniform case\n",
    "(which the Wikipedia page assumes),\n",
    "but not in the general non-uniform case, as we'll see in a moment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second one is obviously wrong in the case where all intervals are\n",
    "of length $1$ (i.e. $t_{i+1} - t_i = t_i - t_{i-1} = 1$):\n",
    "\n",
    "\\begin{equation*}\n",
    "\\frac{\\boldsymbol{x}_{i + 1} - \\boldsymbol{x}_{i - 1}}{4}\n",
    "\\ne\n",
    "\\frac{\\boldsymbol{x}_{i + 1} - \\boldsymbol{x}_{i - 1}}{2}\n",
    "= \\boldsymbol{\\dot{x}}_i\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since April 2023,\n",
    "the page is\n",
    "[showing the correct equation for the uniform case](https://web.archive.org/web/20230411124304/https://en.wikipedia.org/wiki/Cubic_Hermite_spline)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The\n",
    "[X3D standard (version 3.3)](https://www.web3d.org/documents/specifications/19775-1/V3.3/Part01/components/interp.html#HermiteSplineInterpolation)\n",
    "even suggests to use different incoming and outgoing tangents,\n",
    "which destroys $C^1$ continuity!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\boldsymbol{\\dot{x}}_i^{(+)} &\\overset{?}{=} \\frac{\n",
    "(t_i - t_{i-1}) (\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_{i-1})\n",
    "}{\n",
    "t_{i+1} - t_{i-1}\n",
    "}\\\\\n",
    "\\boldsymbol{\\dot{x}}_i^{(-)} &\\overset{?}{=} \\frac{\n",
    "(t_{i+1} - t_i) (\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_{i-1})\n",
    "}{\n",
    "t_{i+1} - t_{i-1}\n",
    "}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class X3D(splines.KochanekBartels):\n",
    "    # We derive from KochanekBartels because the\n",
    "    # incoming and outgoing tangents are different:\n",
    "    @staticmethod\n",
    "    def _calculate_tangents(points, times, _ignored):\n",
    "        x_1, _, x1 = np.asarray(points)\n",
    "        t_1, t0, t1 = times\n",
    "        incoming = (t1 - t0) * (x1 - x_1) / (t1 - t_1)\n",
    "        outgoing = (t0 - t_1) * (x1 - x_1) / (t1 - t_1)\n",
    "        return incoming, outgoing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To illustrate the different choices of tangent vectors,\n",
    "we use the vertex data from\n",
    "<cite data-cite-t=\"lee1989choosing\">Lee (1989)</cite>, figure 6:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "points3 = [\n",
    "    (0, 0),\n",
    "    (10, 25),\n",
    "    (10, 24),\n",
    "    (11, 24.5),\n",
    "    (33, 25),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deciding between \"right\" and \"wrong\" tangent vectors is surprisingly hard,\n",
    "because most of the options look somewhat reasonable in most cases.\n",
    "However, we can try to use quite extreme vertex positions\n",
    "and we can use *centripetal parameterization* (see below)\n",
    "and check if its guaranteed properties hold\n",
    "for different choices of tangent vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_spline(cls, linestyle='-', **args):\n",
    "    # alpha=0.5 => centripetal parameterization\n",
    "    spline = cls(points3, alpha=0.5)\n",
    "    plot_spline_2d(\n",
    "        spline, label=cls.__name__, chords=False,\n",
    "        marker=None, linestyle=linestyle, **args)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_spline(MeanVelocity, linestyle=':')\n",
    "plot_spline(X3D, linestyle='-.')\n",
    "plot_spline(Wikipedia1)\n",
    "plot_spline(Wikipedia2, linestyle='--')\n",
    "plot_spline(splines.CatmullRom, linewidth=3)\n",
    "plt.axis([9, 13, 23.9, 25.6])\n",
    "plt.legend();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can immediately see,\n",
    "the tangents from X3D are utterly wrong\n",
    "and the first one from Wikipedia is also quite obviously broken.\n",
    "The other two don't look too bad,\n",
    "but they slightly overshoot,\n",
    "and according to\n",
    "<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>\n",
    "that is something that centripetal Catmull--Rom splines are guaranteed not to do.\n",
    "\n",
    "Again, to be fair to the Wikipedia article's authors,\n",
    "they mentioned that uniform parameter spacing is assumed,\n",
    "so their equation is not supposed to be used in this non-uniform context.\n",
    "The equation has been changed in the meantime to avoid confusion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cusps and Self-Intersections\n",
    "\n",
    "Uniform parametrization typically works very well\n",
    "if the (Euclidean) distances between consecutive vertices are all similar.\n",
    "However, if the distances are very different,\n",
    "the shape of the spline often turns out to be unexpected.\n",
    "Most notably,\n",
    "in extreme cases there might be even cusps or self-intersections\n",
    "within a spline segment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_catmull_rom(*args, **kwargs):\n",
    "    plot_spline_2d(splines.CatmullRom(*args, endconditions='closed', **kwargs))"
   ]
  },
  {
   "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": [
    "plot_catmull_rom(points4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can try to compensate this\n",
    "by manually selecting some non-uniform time instances:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "times4 = 0, 0.2, 0.9, 1, 3, 3.3, 4.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_catmull_rom(points4, times4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Time values can be chosen by trial and error,\n",
    "but there are also ways to choose the time values automatically,\n",
    "as shown in the following sections."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chordal Parameterization\n",
    "\n",
    "One way to go about this is to measure the (Euclidean) distances\n",
    "between consecutive vertices (i.e. the *chordal lengths*)\n",
    "and simply use those distances as time intervals:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "distances = np.linalg.norm(np.diff(points4 + points4[:1], axis=0), axis=1)\n",
    "distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "times5 = np.concatenate([[0], np.cumsum(distances)])\n",
    "times5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_catmull_rom(points4, times5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This makes the speed along the spline nearly constant,\n",
    "but the distance between the curve and its longer chords\n",
    "can become quite huge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Centripetal Parameterization\n",
    "\n",
    "As a variation of the previous method,\n",
    "the square roots of the chordal lengths\n",
    "can be used to define the time intervals\n",
    "<cite data-cite=\"lee1989choosing\">(Lee 1989)</cite>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "times6 = np.concatenate([[0], np.cumsum(np.sqrt(distances))])\n",
    "times6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_catmull_rom(points4, times6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The curve takes its course much closer to the chords,\n",
    "but its speed is obviously far from constant.\n",
    "\n",
    "Centripetal parameterization has the very nice property that\n",
    "it guarantees no cusps and no self-intersections,\n",
    "as shown by \n",
    "<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>.\n",
    "The curve is also guaranteed to never \"move away\" from the successive vertex:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> When centripetal parameterization is used with Catmull--Rom splines to\n",
    "define a path curve, the direction of motion for the object following this path\n",
    "will always be towards the next key-frame position.\n",
    ">\n",
    "> ---<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>, Section 7.2: \"Path Curves\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parameterized Parameterization\n",
    "\n",
    "It turns out that the previous two parameterization schemes\n",
    "are just two special cases of a more general scheme\n",
    "for obtaining time intervals between control points:\n",
    "\n",
    "\\begin{equation*}\n",
    "t_{i+1} = t_i + |\\boldsymbol{x}_{i+1} - \\boldsymbol{x}_i|^\\alpha,\n",
    "\\text{ with } 0 \\le \\alpha \\le 1.\n",
    "\\end{equation*}\n",
    "\n",
    "In the Python class\n",
    "[splines.CatmullRom](../python-module/splines.rst#splines.CatmullRom),\n",
    "the parameter `alpha` can be specified."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_alpha(alpha, label):\n",
    "    s = splines.CatmullRom(points4, alpha=alpha, endconditions='closed')\n",
    "    plot_spline_2d(s, label=label)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_alpha(0, r'$\\alpha = 0$ (uniform)')\n",
    "plot_alpha(0.5, r'$\\alpha = 0.5$ (centripetal)')\n",
    "plot_alpha(0.75, r'$\\alpha = 0.75$')\n",
    "plot_alpha(1, r'$\\alpha = 1$ (chordal)')\n",
    "plt.legend(loc='center', numpoints=3);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As can be seen here -- and as\n",
    "<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>\n",
    "demonstrate to be generally true --\n",
    "the uniform curve is farthest away from short chords\n",
    "and closest to long chords.\n",
    "The chordal curve behaves contrarily:\n",
    "closest to short chords and awkwardly far from long chords.\n",
    "The centripetal curve is closer to the uniform curve for long chords\n",
    "and closer to the chordal curve for short chords,\n",
    "providing a very good compromise.\n",
    "\n",
    "Any value between $0$ and $1$ can be chosen for $\\alpha$,\n",
    "but $\\alpha = \\frac{1}{2}$ (i.e. centripetal parameterization)\n",
    "stands out because it is the only one of them that guarantees\n",
    "no cusps and self-intersections:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> In this paper\n",
    "we prove that, for cubic Catmull--Rom curves, centripetal parameterization\n",
    "is the only parameterization in this family that guarantees that the curves\n",
    "do not form cusps or self-intersections within curve segments.\n",
    ">\n",
    "> ---<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>, abstract"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> [...] we mathematically prove that\n",
    "centripetal parameterization of Catmull--Rom curves\n",
    "guarantees that the curve segments cannot form cusps or local self-intersections,\n",
    "while such undesired features can be formed\n",
    "with all other possible parameterizations within this class.\n",
    ">\n",
    "> ---<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>, Section 1: \"Introduction\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Cusps and self-intersections are very common with Catmull--Rom curves\n",
    "for most parameterization choices. In fact, as we will show here,\n",
    "the only parameterization choice that guarantees\n",
    "no cusps and self-intersections within\n",
    "curve segments is centripetal parameterization.\n",
    ">\n",
    "> ---<cite data-cite-t=\"yuksel2011parameterization\">Yuksel et al. (2011)</cite>, Section 3: \"Cusps and Self-Intersections\""
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}