SVG路径上的Catmull-Rom插值

Question

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

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

保持路径中的每个点都会产生大量的点,这对于后来的协作功能来说并不理想(来回发送大量的点效率不高),而且每次我需要操作它们时解析大路径是瓶颈

在路径的线性区域上,删除冗余点,仅保留表示段所需的点 - 我使用Ramer-Douglas-Peucker算法执行此操作.

但是简化路径会将其转换为低保真多边形

此时,路径实际上只是连接线 - 因此路径看起来是锯齿状的.

一种可能的解决方案是将路径点与Cubic Bezier连接 - 但是这在简化路径上不起作用.每个点之间的距离太大,以至于Cubic Bezier"坐得"不错,因此平滑的路径不再准确地表示用户的预期路径.

另一个解决方案是在原始路径上简单地使用"后处理"算法,例如Schneider算法 - 这个算法实际上不会实时工作,因为它是一个性能猪

理想的解决方案

(我认为)可以使用的解决方案是使用Centripetal Catmull-Rom插值.

在我研究过的所有算法中,这似乎是最有希望的:

1. 它不会在狭窄的角落产生自我交叉
2. 它更适合点,因此它更准确地代表原始路径.

---

是的Catmull-ROM,其插入了一系列的常规X/Y点或完成原始路径必须由曲线的算法？

Answer 1

直接回答您的问题:

1. 是.Catmull-Rom样条曲线是一种插值一系列(x,y,z)点的算法.它将在每两个连续点之间生成三次多项式曲线.
   
2. 您不能直接使用Catmull Rom样条曲线来获取SVG路径.您需要先将其转换为立方贝塞尔曲线.
   

对于由点P0,P1,P2和P3以及结序列t0,t1,t2,t3定义的曲线段,向心Catmull-Rom样条(在点P1和P2之间定义)可以通过https中提供的递归公式计算: //en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline.因此,我在此不再赘述.

要将其转换为三次贝塞尔曲线,您需要计算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 = P1
Q1 = P1 + M1/3
Q2 = P2 - M2/3
Q3 = P2