I am experimenting with creating high-performance, good-looking pencil tools using SVG paths.
I am logging the mouse coordinates to draw a path. To get a high-fidelity path (accurate to the user's movements) I 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 - I do this using the Ramer-Douglas-Peucker algorithm.
But 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:
- It doesn't create self-intersections on tight corners
- 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:
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
Where
Then you can convert it to cubic Bezier curve with 4 control points: Q0, Q1, Q2 and Q3: