SVG 路径上的 Catmull-Rom 插值 [英] Catmull-Rom interpolation on SVG Paths

问题描述

我正在尝试使用 SVG 路径创建高性能、美观的铅笔工具.

我正在记录鼠标坐标以绘制路径.为了获得高保真路径(精确到用户的运动)，我需要为每个像素运动记录一个点.

保留路径中的每一个点都会产生大量的点，这对于以后的协作功能不是的理想选择(来回发送大量的点效率不高)，再加上解析每次我需要操纵它们的巨大路径都是一个瓶颈

在路径的线性区域，删除冗余点，只保留表示线段所需的点 - 我使用 .因此，我不会在这里详述.

要将其转换为三次贝塞尔曲线，您需要计算第一个P1 和 P2 处的导数为

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))

哪里

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

然后您可以将其转换为具有 4 个控制点的三次贝塞尔曲线:Q0、Q1、Q2 和 Q3:

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

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:

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

这篇关于SVG 路径上的 Catmull-Rom 插值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！