catmull-rom

catmull-rom.js

 // The "Catmull-Rom" Interpolating Splines in ES6
 // - Authors: Nicholas Kyriakides (2017) & Unknown
 // - From "A class of local interpolating splines" 
 // - by Catmull, Edwin; Rom, Raphael
 // - University of Utah, 1974
 //
 // 
 // Barnhill, Robert E.; Riesenfeld, Richard F. (eds.). 
 // Computer Aided Geometric Design. 
 //
 // Interpolates a Catmull-Rom spline through a series of x/y points
 // 
 // - If `alpha` is `0` then the 'Uniform' variant is used.
 // - If `alpha` is `0.5` then the 'Centripetal' variant is used.
 //   Read: https://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline
 // - If `alpha` is `1` then the 'Chordal' variant is used.
 // 
 // @param  {Array}  `points` - `Point` is an object like: `{ x: 10, y: 20 }`
 // @param  {Number} `alpha`  - knot parameterization, can be `0`, `0.5` or `1`
 //
 // @return {String} `d`      - An SVG path of cubic beziers
 //
const toCatmullRom = (points, alpha = 0.5) => {
  if (!Array.isArray(points))
    throw TypeError(`'points' should be an Array. Got: ${typeof points}`)
  
  if (![0.5, 1].includes(alpha))
    throw RangeError(`'alpha' should be: 1 or 0.5. Got: ${alpha}`)
  
  let p0, p1, p2, p3, bp1, bp2, d1, d2, d3, A, B, N, M
  let d3powA, d2powA, d3pow2A, d2pow2A, d1pow2A, d1powA
  let d = 'M' + Math.round(points.at(0).x) + ',' + Math.round(points.at(0).y) + ' '

  for (let i = 0; i < points.length - 1; i++) {
    p0 = i == 0 ? points[0] : points[i - 1]
    p1 = points[i]
    p2 = points[i + 1]
    p3 = i + 2 < points.length ? points[i + 2] : p2

    d1 = Math.sqrt(Math.pow(p0.x - p1.x, 2) + Math.pow(p0.y - p1.y, 2))
    d2 = Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2))
    d3 = Math.sqrt(Math.pow(p2.x - p3.x, 2) + Math.pow(p2.y - p3.y, 2))

    // Catmull-Rom to Cubic Bezier conversion matrix

    // A = 2d1^2a + 3d1^a * d2^a + d3^2a
    // B = 2d3^2a + 3d3^a * d2^a + d2^2a

    // [   0             1            0          0          ]
    // [   -d2^2a /N     A/N          d1^2a /N   0          ]
    // [   0             d3^2a /M     B/M        -d2^2a /M  ]
    // [   0             0            1          0          ]

    d3powA = Math.pow(d3, alpha)
    d3pow2A = Math.pow(d3, 2 * alpha)
    d2powA = Math.pow(d2, alpha)
    d2pow2A = Math.pow(d2, 2 * alpha)
    d1powA = Math.pow(d1, alpha)
    d1pow2A = Math.pow(d1, 2 * alpha)

    A = 2 * d1pow2A + 3 * d1powA * d2powA + d2pow2A
    B = 2 * d3pow2A + 3 * d3powA * d2powA + d2pow2A
    N = 3 * d1powA * (d1powA + d2powA)

    if (N > 0)
      N = 1 / N

    M = 3 * d3powA * (d3powA + d2powA)

    if (M > 0)
      M = 1 / M

    bp1 = {
      x: (-d2pow2A * p0.x + A * p1.x + d1pow2A * p2.x) * N,
      y: (-d2pow2A * p0.y + A * p1.y + d1pow2A * p2.y) * N
    }

    bp2 = {
      x: (d3pow2A * p1.x + B * p2.x - d2pow2A * p3.x) * M,
      y: (d3pow2A * p1.y + B * p2.y - d2pow2A * p3.y) * M
    }

    if (bp1.x == 0 && bp1.y == 0)
      bp1 = p1

    if (bp2.x == 0 && bp2.y == 0)
      bp2 = p2

    d += 'C' + bp1.x + ',' + bp1.y + ' ' + bp2.x + ',' + bp2.y + ' ' + p2.x + ',' + p2.y + ' '
  }
  
  return d
}

@sivakrishna551

I've chopped some parts of the code from somewhere else, was some kind of chart-drawing library I think.
I'm almost positive it was MIT licensed but there's zero-chance I'll remember which one it was, nor do I think it makes any difference,
I don't remember it being anything too significant.

It's MIT from me, so feel free. I'l add it below.

The MIT License
Nicholas Kyriakides, (c) and Unknown Authors 2015

From: "A Class of Local Interpolating Splines"
Edwin Catmull & Raphael Rom.
University of Utah, 1974

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so.

---

Adding a bit more detail; some people seem to be using this.

I've cleaned this up a little bit but bear in mind that I hacked this up haphazardly in a rush, back in 2015.

Somebody forked this and converted it to TypeScript, probably even improved it; click the "Forks" button above
and you'll figure it out.

Original papers

A Class of Interpolating Splines

Published at: Computer Aided Geometric Design
University of Utah, 1974

By Edwin Catmull, Raphael Rom

On the Parameterization of Catmull-Rom Curves

Published at: SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

By Cem Yuksel, Scott Schaefer, John Keyser

This implementation contains parts from another author, I don't remember which one but IIRC it's the parts
conversion to Cubics. I don't personally care about citation but at least cite them as Unknown Authors in the
MIT redistribution.

---

If you came across this for implementing handwriting interpolation, the following is relevant,
otherwise skip it since it's not going to make any sense to you.

This implementation came about ~ 2015, during the R&D phase of a project about a collaborative whiteboard, geared specifically for online tutoring by professional tutors.

Excerpts from 2015:

[...] we ran a series of UX workshops with professional tutors, focusing on Human/Machine interface of pen digitisers and how we could improve the experience > of writing with pen tablets, rather than real paper.
Apart from low latencies, people overwhelmingly appreciate a sensation of fluidity & continuity, which in comp. geometry terms
means the produced output is curve-fitted, interpolated and noise-attenuated.
For whatever physiological reason, people have shaky hands and they don't want that reflected in the output.

[..] most of the algorithms we researched at the time were either too slow to produce a useful result in real-time or they produced a specific type of artifacts, called a "self-intersection", especially on tight cusps

[..] another algorithm that produced nice and continuous curves by Sarah Frisken but its under patent by Mitsubishi Electric Research Laboratories.

[..] The centripetal variant of Catmull-Rom does not produce these artifacts and has been in the public domain for over 40 years.
At the same time it exhibits an exceptionally efficient runtime performance profile.

The Frisken algorithm mentioned above:

Efficient Curve Fitting
Dr. Sarah Frisken
University of Harvard
Citation: “Efficient Curve Fitting”, Journal of Graphics Tools, 13(2), pp. 35-37, 2008

From S.O: Catmull-Rom interpolation on SVG Paths.

Jurg Lehni added the above (with additional improvements), into the PaperJS library.
You can follow our discussion here.

Although it's a bit enmeshed with PaperJS internals, it's an improvement over this implementation.
Our discussion above goes in much more detail than I'd rather to repeat here.

The image below shows the self-intersection issues (rows 4, 5-7) in other algorithms vs Centripetal Catmull-Rom.

Thanks,

black = original path
orange = smoothCatmullRom(0.5); <-- Centripetal Catmull Rom
green = smoothGeometric(0.4); <-- Catmull Rom again, non-centripetal.
red = smoothContinuous(); <-- Catmull Rom Uniform
blue = smooth(); // the old smooth <-- Schneiders Algorithm mentioned above

Nik

From PaperJS: 338