插入点的分段三次贝塞尔路径算法

Question

插入点的分段三次贝塞尔路径算法

algorithmvector-graphicsbezier

14

我正在寻找一种在不改变贝塞尔曲线形状的情况下插入新控制点的算法。

有没有人知道关于贝塞尔算法（插值，优化，de Casteljau等）的库或参考资料？

- sorush-r

2

计算机图形学算法常见问题解答，问题4.02和4.03。您需要使用哪种语言查找库？ - bobince

3个回答

2

您也可以采用数学方法。

具有控制点

的三次贝塞尔曲线可以写成： b(t)=(1-t)^3 p_1+3t(1-t)^2 p_2+3t^2 (1-t) p_3+t^3 p_4

它关于

的导数是 $\frac{\partial b}{\partial t} = 3(1-t)^2 (p_2-p_1 )+6t(1-t)(p_3-p_2 )+3t^2 (p_4-p_3 )$ 为了将曲线限制在

到

之间，您需要新的控制点 q_1,q_2,q_3,q_4

:

$q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}$ $q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}$ 证明：

代入 $s=\frac{t-t_0}{t_1-t_0}$ t=t_0+s(t_1-t_0 )

我们得到 $\frac{\partial b}{\partial s} = \frac{\partial b}{\partial t} \frac{\partial t}{\partial s} = (t_1-t_0) \frac{\partial b}{\partial t}$ 子曲线的第一个和最后一个点是新的第一个和最后一个控制点 q_1=b(t_0),q_4=b(t_1)

这些点的切线为

$\frac{\partial{b}}{\partial{s}}_{(s=0)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}=3(q_2-q_1)$

$\frac{\partial{b}}{\partial{s}}_{(s=1)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}=3(q_4-q_3)$

因此

$q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}$

$q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}$

- Michael Litvin

1

为了完整起见添加此内容。

许多Bézier路径操作的开源实现可以在GIMP源代码中找到，在 gimpbezierstroke.c 中。有关插入新锚点的参考，请搜索 gimp_bezier_stroke_anchor_insert 。

- Michael Litvin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Philippe Beaudoin · Accepted Answer

这被称为“结点插入问题”。对于Bézier曲线，de Casteljau算法将给出正确的答案。下面是三次Bézier曲线的简单算法。

假设您希望在由P0，P1，P2，P3定义的Bézier曲线的参数空间的分数t处插入一个结点。以下是具体步骤：

P0_1 = (1-t)*P0 + t*P1
P1_2 = (1-t)*P1 + t*P2
P2_3 = (1-t)*P2 + t*P3

P01_12 = (1-t)*P0_1 + t*P1_2
P12_23 = (1-t)*P1_2 + t*P2_3

P0112_1223 = (1-t)*P01_12 + t*P12_23

那么你的第一个贝塞尔曲线将由：P_0，P0_1，P01_12，P0112_1223定义；你的第二个贝塞尔曲线将由：P0112_1223，P12_23，P2_3，P3定义。

几何解释很简单：在贝塞尔多边形的每个线段上按比例划分点，然后连接这些划分点形成一个新的多边形并重复此过程。当只剩下一个点时，该点位于曲线上，前/后一个划分点形成前/后一个贝塞尔多边形。相同的算法也适用于更高阶的贝塞尔曲线。

如果您想在空间中的特定位置插入控制点，则可能会变得更加棘手。个人建议，在此处可使用二分查找来查找接近所需划分点的t值......但如果性能很关键，您可能可以找到更快速的解析解决方案。