Catmull-Rom interpolation on SVG Paths

We're experimenting with creating high-performance, good-looking pencil tools using SVG paths.

We log the mouse coordinates to draw a path. To get a high-fidelity path (accurate to the user's movements) we need to log a point for every pixel movement.

Keeping each and every point in the path creates a huge amount of points which is not ideal for collaborative features later-on (sending huge amount of points back and forth is not efficient), plus parsing huge paths every time I need to manipulate them is a bottleneck

On linear areas of the path, redundant points are removed keeping only the points necessary to represent the segment - we're currently doing this using the Ramer-Douglas-Peucker algorithm.

... simplifying a path turns it into a low-fidelity polygon

At this point the paths are effectively just connected lines - therefore the paths look jagged.

A possible solution is to connect the path points with Cubic Bezier's - however this doesn't work nice on simplified paths. The distance between each point is too large for the Cubic Bezier's to "sit" nice so the smoothed path no longer accurately represents the intended path of the user.

Another solution is to simply use a "post-processing" algorithm such as Schneider's Algorithm on the original path - This algorithm won't practically work in real-time though since it's a performance hog

An ideal solution

A solution that(I think) could work is to use a Centripetal Catmull-Rom interpolation.

Out of all the algorithms I researched, this seems to be the most promising since:

1. It doesn't create self-intersections on tight corners
2. It fits more snug on the points thus it more accurately represents the original path.

---

Is Catmull-Rom an algorithm that interpolates a series of regular x/y points or does the original path need to be comprised of curves?

To answer your questions directly:

1. Yes. Catmull-Rom spline is an algorithm to interpolate a series of (x, y, z) points. It will generate a cubic polynomial curve between each two consecutive points.
   
2. You cannot direcly use Catmull Rom spline for SVG path. You need to convert it to cubic Bezier curve first.
   

For a curve segment defined by point P0, P1, P2 and P3 and knot sequence t0, t1, t2, t3, the centripetal Catmull-Rom spline (defined between point P1 and P2) can be computed by the recursive formula provided in https://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline. Therefore, I will not elaborate here.

To convert it to cubic Bezier curve, you need to compute the first derivative at P1 and P2 as

M1 = (t2-t1)*(c1*(P1-P0)/(t1-t0) + c2*(P2-P1)/(t2-t1))
M2 = (t2-t1)*(d1*(P2-P1)/(t2-t1) + d2*(P3-P2)/(t3-t2))

Where

 c1 = (t2-t1)/(t2-t0),
 c2 = (t1-t0)/(t2-t0),
 d1 = (t3-t2)/(t3-t1),
 d2 = (t2-t1)/(t3-t1)

Then you can convert it to cubic Bezier curve with 4 control points: Q0, Q1, Q2 and Q3:

Q0 = P1
Q1 = P1 + M1/3
Q2 = P2 - M2/3
Q3 = P2